Exhaust: Optimizing Wu-Manber Pattern Matching for Intrusion Detection using Bloom Filters

Intrusion detection systems are widely accepted as one of the main tools for monitoring and analyzing host and network traffic to protect data from illegal access or modification. Almost all types of signature-based intrusion detection systems must employ a pattern matching algorithm to inspect packets for malicious signatures. Unfortunately, pattern matching algorithms dominate the execution time and have become the bottleneck. To remedy that, we introduce a new software-based pattern matching algorithm that modifies Wu-Manber pattern matching algorithm using Bloom filters. The Bloom filter acts as an exclusion filter to reduce the number of searches to the large HASH table. The HASH table is accessed if there is a probable match represented by a shift value of zero. On average the HASH table search is skipped 10.6% of the time with a worst case average running time speedup over Wu-Manber of 33%. The maximum overhead incurred on preprocessing time is 1.1% and the worst case increase in memory usage was limited to 0.33%