Multiple Pattern Matching Algorithm And Its Used In Intrusion Detection System

Pattern matching is a basic problem in computer science, pattern matching have an important value in information retrieval, pattern recognition and other numerous fields of the spell checking, it is also an important role in the language translation and data compression, search engines, the inspection, content filtering, the computer virus characteristics to match the genetic code and sequence for applications. Intrusion Detection System (IDS) is an active technology in the security protection technology to provide for internal and external attacks and the false operation of real-time and in the network systems were injured and response before an intrusion.Taday,the speed of the network is rapid, the efficiency of the intrusion detection algorithms to the network security and computer security is significance.This paper briefly describe the intrusion detection system (Intrusion Detection System, IDS) of the basic concepts, development prospects, the working principle, IDS's standards, and then analyze and compare the pattern matching algorithms such as KMP, AC, BM, WM, BOM, SBOM. On this basis, this paper proposes a time-and space- efficient multi-pattern matching algorithm. In this algorithm to match the pattern from the left of the end to the right, using the skip table to jump to filter out unnecessary characters, and then enter the state machine to match patterns,this improved the matching speed. When constructed the state machine using the Chinese remainder theorem and bitmap compression state machine to compress the stored space, this will reduce storage space for the state machine. The algorithm uses compression to store and jumping character thought can reduce the memory storage capacity and visits, so that the algorithm easily implemented by hardware. Experiments show that the algorithm significantly improves search efficiency with a good performance.For the disadvantage of the AC algorithm, we design a hardware implementation matching algorithm, the algorithm used a K state matchine as a model state machine to search. Characters first enter the system through the Bloom Filter structure to remove not exist pattern, and then access RAM to match it exactly, use K state machine and hash technology can greatly reduces the number of visits to RAM,. Finally, Implements a system in Verilog language, and introduced the data path module, hash matching module, analysis and key modules arbitration module design, and give simulation verification of it at last.