Many parallelization systems detect memory access conflicts across concurrent threads by disambiguating address-sets using bit-vector-based Bloom filters, which are efficient, but can report false conflicts that do not exist. Systems with lazy conflict detection often use Bloom filters unconventionally by testing sets for null-intersection via Bloom filter intersection, contrasting with the conventional approach of issuing membership queries into the Bloom filter. In this dissertation we develop much-needed theory for probability of false conflicts in Bloom filter null-intersection tests, notably demonstrating that Bloom filter intersection requires substantially larger bit-vectors to provide equivalent statistical behavior to querying. Furthermore, we recognize that our theoretical implications counter practical intuition, and thus use RingSTM to evaluate theory in practice by implementing and comparing the Bloom filter configurations. We find that despite its overheads, the queue-of-queries approach reduces execution time and is thus the most compelling alternative to Bloom filter intersection for lazy address-set disambiguation.

Many parallelization systems detect memory access conflicts across concurrent threads by disambiguating address-sets using bit-vector-based Bloom filters, which are efficient, but can report false conflicts that do not exist. Systems with lazy conflict detection often use Bloom filters unconventionally by testing sets for null-intersection via Bloom filter intersection, contrasting with the conventional approach of issuing membership queries into the Bloom filter. In this dissertation we develop much-needed theory for probability of false conflicts in Bloom filter null-intersection tests, notably demonstrating that Bloom filter intersection requires substantially larger bit-vectors to provide equivalent statistical behavior to querying. Furthermore, we recognize that our theoretical implications counter practical intuition, and thus use RingSTM to evaluate theory in practice by implementing and comparing the Bloom filter configurations. We find that despite its overheads, the queue-of-queries approach reduces execution time and is thus the most compelling alternative to Bloom filter intersection for lazy address-set disambiguation.

Firewalls are an integral part of network security. They are pervasive throughout networks and can be found in mobile phones, workstations, servers, switches, routers, and standalone network devices. Their primary responsibility is to track and discard unauthorized network traffic, and may be implemented using costly special purpose hardware to flexible inexpensive software running on commodity hardware. The most basic action of a firewall is to match packets against a set of rules in an Access Control List (ACL) to determine whether they should be allowed or denied access to a network or resource. By design, traditional firewalls must sequentially search through the ACL table, leading to increasing latencies as the number of entries in the table increase. This is particularly true for software firewalls implemented in commodity server hardware. Reducing latency in software firewalls may enable them to replace hardware firewalls in certain applications. In this thesis, we propose a software firewall architecture which removes the sequential ACL lookup from the critical path and thus decreases the latency per packet in the common case. To accomplish this we implement a Bloom filter-based, stochastic pre-classification stage, enabling the bifurcation of the predicted good and predicted bad packet code paths, greatly improving performance. Our proposed architecture improves firewall performance 67% to 92% under anonymized trace based workloads from CAIDA servers. While our approach has the possibility of incorrectly classifying a small subset of bad packets as good, we show that these holes are neither predictable nor permanent, leading to a vanishingly small probability of firewall penetration.

Hash tables (HTs) are used to implement various lookup schemes and they need to be efficient in terms of speed, space utilization, and power consumptions. For IP lookup, the hashing schemes are attractive due to their deterministic O(1) lookup performance and low power consumptions, in contrast to the TCAM and Trie based approaches. As the size of IP lookup table grows exponentially, scalable lookup performance is highly desirable. For next generation high-speed routers, this is a vital requirement when IP lookup remains in the critical data path and demands a predictable throughput. However, recently proposed hash schemes, like a Bloomier filter HT and a Fast HT (FHT) suffer from a number of flaws, including setup failures, update overheads, duplicate keys, and pointer overheads. In this dissertation, four novel hashing schemes and their architectures are proposed to address the above concerns by using pipelined Bloom filters and a Fingerprint filter which are designed for a memory-efficient approximate match. For IP lookups, two new hash schemes such as a Hierarchically Indexed Hash Table (HIHT) and Fingerprint-based Hash Table (FPHT) are introduced to achieve a a perfect match is assured without pointer overhead. Further, two hash mechanisms are also proposed to provide memory and power efficient lookup for packet processing applications. Among four proposed schemes, the HIHT and the FPHT schemes are evaluated for their performance and compared with TCAM and Trie based IP lookup schemes. Various sizes of IP lookup tables are considered to demonstrate scalability in terms of speed, memory use, and power consumptions. While an FPHT uses less memory than an HIHT, an FPHT-based IP lookup scheme reduces power consumption by a factor of 51 and requires 1.8 times memory compared to TCAM-based and trie-based IP lookup schemes, respectively. In dissertation, a multi-tiered packet classifier has been proposed that saves at most 3.2 times power compared to the existing parallel packet classifier. Intrinsic hashing schemes lack of high throughput, unlike partitioned Ternary Content Addressable Memory (TCAM)-based scheme that are capable of parallel lookups despite large power consumption. A hybrid CAM (HCAM) architecture has been introduced. Simulation results indicate HCAM to achieve the same throughput as contemporary schemes while it uses 2.8 times less memory and 3.6 times less power compared to the contemporary schemes.

Computers were not built with security in mind. As such, security has and still often takes a back seat to performance. However, in an era where there is so much sensitive data being stored, with cloud storage and huge customer databases, much has to be done to keep this data safe from intruders. Control flow hijacking attacks, stemming from a basic code injection attack to return-into-libc and other code re-use attacks, are among the most dangerous attacks. Currently available solutions, like Data execution prevention that can prevent a user from executing writable pages to prevent code injection attacks, do not have an efficient solution for protecting against code re-use attacks, which can execute valid code in a malicious order. To protect against control flow hijacking attacks, this work proposes architecture to make Control Flow Integrity, a solution that proposes to validate control flow against pre-computed control flow graph, practical. Current implementations of Control Flow Integrity have problems with code modularity, performance, or scalability, so I propose Dynamic Bloom Cache, a blocked-Bloom-filter-based approach, to solve current implementation issues.

Longest prefix matching is a well-studied problem in the context of IP-packet forwarding, an area of computational specialization where high performance with low memory impact is of the essence. Numerous specialized data structures exist for longest prefix matching in this setting, among them is Waldvogels binary search on lengths, WBSL for short. This data structure has previously been augmented with a Bloom filter to improve its performance, resulting in a new data structure: WBSL-BF. This study concerns the potential performance improvement of adding length-awareness to WBSL-BF. Performance of the augmented data structure is evaluated by recording the number of hash table accesses performed to carry out a series of queries, along with false positive rates for the Bloom filters. A test program is created to run multiple series of queries with different test configurations. The data structure is evaluated using two datasets containing prefixes from routing information base snapshots from real route collectors. The two datasets contain roughly 80000 and 900000 prefixes respectively. The results indicate that on the given datasets, augmenting the Bloom filter with length-awareness can reduce the number of hash table accesses when performing longest prefix matching by up to 44% in a best case scenario without increasing memory usage. However, the performance gain is limited in other scenarios, since the optimally configured standard Bloom filter leaves little to improve upon when applied to Waldvogels binary search on lengths.

NeMeSys is a NUMA-aware graph pattern processing engine, which uses the Near Memory Processing paradigm to allow for high scalability. With modern server systems incorporating an increasing amount of main memory, we can store graphs and compute analytical graph algorithms like graph pattern matching completely in-memory. Our system blends state-of-the-art approaches from the transactional database world together with graph processing principles. We demonstrate, that graph pattern processing - standalone and workloads - can be controlled by leveraging different partitioning strategies, applying Bloom filter based messaging optimization and, given performance constraints, can save energy by applying frequency scaling of CPU cores.

In modern Mobile Ad hoc Networks (MANETs), service discovery is a major component for mobile devices to exchange data and find available services. However, service discovery architectures developed and adopted by the industry either are not appropriate for MANETs or cannot provide security and privacy protection to clients. Service discovery architectures could be either directory-based or directory-less. Both of the two types of architectures suffer from certain security or privacy issues: The directory-based architecture requires a directory server to facilitate communication between service providers and users, which makes the directory server a single point of failure and may harm users’ privacy if the directory server is honestbut- curious; the directory-less architecture solves these two problems but without a trusted directory, the Denial of Service (DoS) attacks can be easily performed on all entities in the system since the mutual authentication between entities consumes significant computational resource. Wi-Fi Aware, a recently introduced Wi-Fi-based connectivity, allows MANETs nodes to discover and connect directly to each other without any infrastructure. Moreover, the size of the message transmitted in this process is large enough (around 255 bytes) for security and privacy protection. So in this thesis, we implemented a Wi-Fi Aware-based decentralized secure service discovery system that allows the clients to directly discover nearby service providers and provide mutual authentication between them without a directory server. In our system we leverage several schemes, including bloom filter, Timed Efficient Stream Loss- Tolerant Authentication (TESLA), and client puzzle. A set of experiments are carried out for the evaluation of the implemented system. The evaluation results show that our system meets most of the security requirements of service discovery architectures with acceptable processing delays. / I moderna moblie ad hoc -nätverk (MANETs) är service discovery en huvudkomponent för noder för att utbyta data och hitta andras tjänster. Men serviceupptäcktsarkitekturerna som utvecklats och antagits av branschen är antingen inte lämpliga i MANET eller kan inte ge kunderna säkerhet och integritetsskydd. service discovery-arkitekturer är katalogbaserade eller kataloglösa. Båda de två arkitekturerna lider av vissa säkerhetseller sekretessproblem: Den katalogbaserade arkitekturen kräver att katalogservern underlättar kommunikationen mellan tjänsteleverantörer och användare, vilket gör katalogservern till en enda felpunkt och kan skada användarnas integritet om katalogservern är ärlig-men-nyfiken; Den kataloglösa arkitekturen löser dessa två problem men utan en pålitlig katalog kan Denial of Service (DoS) -attacker enkelt utföras på alla enheter i systemet eftersom den ömsesidiga autentiseringen mellan enheter förbrukar massor av beräkningsresurser. Nyligen, med den nyaWi-Fi-funktionen som kallas WiFi-Aware cite wifiaware, kan MANET-noder upptäcka och ansluta direkt till varandra utan någon annan typ av anslutning mellan dem . Dessutom är storleken på meddelandet som överförs i denna process tillräckligt stor (cirka 255 byte) för säkerhetsautentisering. Så i denna avhandling implementerade vi ett Wi-Fi Aware-baserat Decentralized Secure service discovery-system som gör att klienterna direkt kan upptäcka närliggande tjänsteleverantörer och tillhandahålla ömsesidig autentisering mellan dem utan en katalogserver. I vårt system används flera system för att skydda vårt system från ovanstående säkerhets- och integritetsfrågor, bland annat blomfilter, Timed Efficient Stream Loss-Tolerant Authentication (TESLA) och klientpussel. En uppsättning utvärderingsförsök utförs för det implementerade systemet. Utvärderingsresultaten visar att vårt system uppfyller de flesta säkerhetskraven för service discovery -arkitekturer med en acceptabel bearbetningsfördröjning.

We consider the distributed access enforcement problem for Role-Based Access Control (RBAC) systems. Such enforcement has become important with RBAC’s increasing adoption, and the proliferation of data that needs to be protected. Our particular interest is in the evaluation of a new data structure that has recently been proposed for enforcement: the Cascade Bloom Filter. The Cascade Bloom Filter is an extension of the Bloom filter, and provides for time- and space-efficient encodings of sets. We compare the Cascade Bloom Filter to the Bloom Filter, and another approach called Authorization Recycling that has been proposed for distributed access enforcement in RBAC. One of the challenges we address is the lack of a benchmark: we propose and justify a benchmark for the assessment. Also, we adopt a statistically rigorous approach for empirical assessment from recent work. We present our results for time- and space-efficiency based on our benchmark. We demonstrate that, of the three data structures that we consider, the Cascade Bloom Filter scales the best with the number of RBAC sessions from the standpoints of time- and space-efficiency.

This thesis addresses the problem of local intrusion detection for SCADA (Supervisory Control and Data Acquisition) field devices in the smart grid. A methodology is proposed to detect anomalies in the communication patterns using a combination of n-gram analysis and Bloom Filter. The predictable and regular nature of the SCADA communication patterns is exploited to train the intrusion detection system. The protocol considered to test the proposed approach is MODBUS which is used for communication between a SCADA server and field devices in power system. The approach is tested for attacks like HMI compromise and Man-in-the-Middle. Bloom Filter is chosen because of its strong space advantage over other data structures like hash tables, linked lists etc. for representing sets. The advantage comes from its probabilistic nature and compact array structure. The false positive rates are found to be minimal with careful choice of parameters for Bloom Filter design. Also the memory-efficient property of Bloom Filter makes it suitable for implementation in resource constrained SCADA components. It is also established that the knowledge of physical state of the power system i.e., normal, emergency or restorative state can help in improving the accuracy of the proposed approach.