Applying Fast String Matching to Intrusion Detection

The performance of signature-based network intrusion detection tools is dominated by the string matching of packets against many signatures. This paper studies how the popular intrusion detection system Snort can be best optimized to utilize different string matching algorithms. The paper analyzes the performance of Snort's current string matching algorithm, Boyer-Moore, and several alternate algorithms. The paper shows that no single algorithm is fastest in the context of a real Snort rule set. Instead, the paper develops a hybrid system that utilizes three different search algorithms, including one new algorithm presented in this paper. The result is a system that matches many common packets 5 times faster with an average speedup of 50%.