The Research Of Multi-pattern Matching Algorithms Based On Bit-split Method

With the rapid development of network technology and the increasingly open of Internet, network applications have become increasingly popular. Meanwhile, the attacks brought by network caused people’s attention to the problem of network security. As an important measure to maintain the network security, intrusion detection system has been widely applied. Pattern matching is the most important kind of detection technology in intrusion detection system, whose innovation and effectiveness become the key to improve the performance and efficiency of intrusion detection system.First, this paper takes a simple summarize of intrusion detection system, and introduces the general process and classification of intrusion detection system, and expounds the application of pattern matching in intrusion detection system. Simultaneously, this paper also introduces several classical pattern matching algorithms in detail, including the single pattern matching algorithm such as BF, KMP, BM etc. and multiple pattern matching algorithm such as AC, AC_BM etc.Then, this paper introduces the principle and application of Bloom Filter. Bloom Filter is a kind of data structure based on multiple hash functions mapping to compress the space, and the performance of Bloom Filter can be improved by finding an optimized hash search algorithm. In view of the low efficiency existed in separate chaining in the present hash algorithm, this paper designed an improved hash table query algorithm, the analysis and practical test demonstrate that the algorithm reduces the search length of executing query without any increase in consumption when conflicts occur, so as to shorten the query response time.According to the problems of low memory utilization and frequent access to the peripheral storage of the state machine built by classical AC algorithm, this paper then puts forward a modified pattern matching algorithm based on K-step. The algorithm designed is mainly composed of the following parts: improved AC algorithm, text conversion, mapping mechanism and matching query. Among, improved AC algorithm redefined the output of each state in original AC state machine, and mapping mechanism is responsible for mapping the correspongding state information in improved AC state machine to K-step state machine. Because of this mapping mechanism, generated K-step state machine only contains some information about skipping and output without failure function, moreover, improved K-step state machine adopts linked storage, only retaining effective input substring, query algorithm can be used to handle those substrings which do not appear in the table. So, compared to primary K-step state machine, improved K-step state machine possesses higher superiority in memory. Although improved K-step state machine has resolved some problems, it doesn’t reach the best usage rate of memory resources.Therefore, on the basic of K-step state machine, finally, this paper presented a method based on bit-split, the original state machine is divided into eight small binary state machines, each is responsible for K bits of K input characters. The matching is determined only when all submachines output matching signals. Two advantages of this algorithm are: first, every state of the submachine has2K input selections at most, which makes the memory more compact; second, several submachines can be run independently in parallel, accelerating the speed of query. At the same time, in order to avoid some unnecessary queries, the characters to be matched can be sent into Bloom Filter to filter out suspicious characters. Due to the false positive probability of Bloom Filter, the filtered characters must have a precise matching. In this paper, accurate matching is completed by bit-split state machine. This combination improved the efficiency of the matching and query.