Multi Mode Fast Matching Algorithm

As the situation of the network security is worse and worse, Intrusion Detection System based on pattern-matching has become the hot spot. However, software-based algorithms suffered from speed-limit, hardware-based algorithms suffered from drawbacks such as high power consumption.At first, this paper summarizes Intrusion Detection System and Intrusion Detection Tecnique, and introduces the famous open source Intrusion Detection System-Snort. After elaborate Snort's architecture and principle of work, we focused on its rule set. We give the rule a detailed introduction and analysis. Then, this paper introduces the CAM(Content Addressable memory)/TCAM(Ternary-CAM) and Bloom filter. TCAM can perform exact multi-pattern matching, but it borned with high power-consumption drawback. Bloom filter can perform a quick match, and its match results will never have false negative but have a probability of false positive.This paper proposes a two-level multi-pattern matching aichitecture BF-TCAM, using Bloom filter as the first matching level and TCAM as the second matching level. By grouping the patterns in the pattern set according the pattern length, constructing the (BF, TCAM) match-pair, BF-TCAM gains better memory efficiency and reduces the demand of memory. By filter-matching of Bloom filter, BF-TCAM gains less TCAM active times and reduce the power-consumption. By exact-matching of TCAM, BF-TCAM overcomes Bloom filter's false positive and realizes exact-matching.Because of the discreteness of the pattern length, the architecture of BF-TCAM will become very complicated when the pattern set gets bigger. So this paper uses the truncate-theory to improve the BF-TCAM, and proposes a new two-level multi-pattern matching architecture TBF-TCAM. TBF-TCAM can achieve the same performance as BF-TCAM. At the same time, its architecture is much simpler and easy to implement.This paper simulates both the BF-TCAM and the TBF-TCAM. We focus on the demand of memory and the power-consumption. The results indicates that compares to the TCAM-only matching architecture, both BF-TCAM and TBF-TCAM can save the memory-demand about 3 times, and save the power-consumption more than 20 times.