An optimal design of Bloom Filters for fast string matching

Fast string matching is a critical function required for implementing online intrusion detection systems. In signature-based intrusion detection systems such as Snort, the continuous growth of the database makes it a challenge to maintain good scalability, particularly for high-speed hardware-based implementations where physical resources are limited. Ideally, the system should allow for fast, scalable, and real-time detection of suspicious Internet traffic. Recent research has revealed the existence of high redundancy in the SNORT signature database. Many of the rule patterns in the database consist of repetitious unit strings that appear in multiple independent signatures; such unit strings are defined as primary patterns. Bloom Filtering is proposed as a technique to exploit the redundancy reduction enabled by the primary patterns to improve the speed and efficiency of fast string and pattern matching. This thesis focuses on the design of an optimized Bloom Filter for use with the distilled primary patterns.