Research And Application Of Efficient String Matching Algorithm In Intrusion Detection System

With the rapid development of Internet, network brings great convenience to people. IDS (Intrusion Detection System) is produced as a weapon against network attack. On the one hand, with the high-speed development of network, it’s important to improve test speed of IDS; on the other hand, network attack techniques become more diversified, it’s important to detect the attacks more accurate. IDS is put forward higher requirements on its performance. Generally, NIDS uses string matching algorithm to detect the intrusion. It is proved that appropriate string matching algorithm has been playing an important role in improving the performance of IDS. This thesis designs two efficient multi-mode string matching algorithms-BSP-AC algorithm and D-AC algorithm.Firstly, the thesis analyzes and researches IDS and string matching algorithms. The thesis compares several classical string matching algorithms and analyzes the advantages and disadvantages of these algorithms. The thesis finally selects the Aho-Corasick (AC) algorithm as the focus of research. In the thesis, two improved AC algorithm are proposed. One is BSP-AC algorithm, another one is D-AC altorithm. In the BSP-AC algorithm, all pattern strings and the input strings are divided into K substrings. Then, K pattern search engines are employed to scan the substrings in parallel, so BSP-AC algorithm can process many char. As a result, BSP-AC algorithm can largely save the memory space and improve the matching performance. The D-AC algorithm adds a reverse FSM (Finite State Machine) and it matches strings in manner of two-way parallel. The D-AC algorithm can accelerate the matching speed and improve matching efficiency.In order to verify the efficiency of D-AC algorithm, this thesis integrates D-AC algorithm into the open source Snort. The thesis tests the system with intrusion detection evaluation data sets which are proposed by MIT Lincoln laboratory, the experiment test uses the way which receives the same packets. Then the experimental results show that D-AC algorithm is superior to the other algorithms, D-AC algorithm can reduce the frequency of matching and can detect intrusions much faster and more accurately.