The Research Of String Matching Algorithm In Intrusion Detection System

Computer network has played an important role in the whole national economy now, whichhas become one of indivisible parts in our lives with the quick development of computer technique.Meantime, network safety has increasingly caused people’s attention. As the indispensable measureof safeguarding network, firewall and intrusion detection system are extensively available. Packetfilter is the key technology of firewall system and intrusion detection system. Moreover, as criticaltechnology of packet filter, pattern mating algorithm concerns the efficiency of the whole firewalland intrusion detection system. Thus, the founding of high efficient pattern matching algorithmshows the important significance for enhancing the performance of firewall and intrusion detectionsystem.The event analysis module includes single-pattern matching and multi-pattern matching. Thetypical single-pattern matching includes Brute Force algorithm , Knuth - Morris - Pratt algorithm(KMP algorithm) and the Boyer-Moore algorithm (BM algorithm) ,multi-pattern matchingalgorithm includes Aho-Corasick automaton algorithm (AC algorithm),AC_BM algorithm whichAC algorithm combined with BM algorithm，AC_BMH algorithm which AC algorithm combinedwith BMH algorithm. In these matching algorithms ,however, single-pattern matching algorithmcan not match the patterns in the same time and multi-pattern matching algorithm, just like ACalgorithm can not jumb when unmatched. Although AC_BM algorithm and AC_BMH algorithmslearn single-pattern matching in the skip function, the jump length of the string is limited by theshortest length of patterns in multi-pattern and when establishing the state space tree, it uses 256space to store the state of jump , the space utilization efficiency is very low.In order to offset the defect of AC_BM algorithm and AC_BMH algorithm, AC_SUNDAYalgorithm is proposed as an enhanced multi-pattern mating algorithm in the paper, which combinesthe idea of AC_BM algorithm. Structured pattern tree use finite automata principle of AC algorithm,and decreased the mating using the throry of jumping search of Sunday’s algorithm. It alsoenhances the storge mode of AC_SUNDAY algorithm. However, the improved algorithm in somespecial cases such as skip[i+m-1]<skip[i+m] may appear inefficient ,it should combines the idea ofBMH algorithm to amend. Constructing AC_SUNDAY or AC_BM algorithm state tree needinitializing, which more storage for the 0 . Because of this defect,it will consume a lot of systemmemory and these spaces should be required for compression. Taking advantage of this principle ofsparse matrix to compress the state tree, only trace amounts of time in exchange for sacrificing a lotof memory space is freed. Finally AC_SUNDAY algorithm is tested by using the number of fixed pattern string changingthe pattern string length, fixed pattern length of the string changing the number of patternstring ,and the performance space. The characteristics of AC_SUNDAY algorithm are as follows:Firstly, the skip distance is enlarged exceeding the linmitation that the longest distance can’toverpass the length of the shortest pattern of prefix tree. Secondly, the unnecessary comparisonfrequency is reduced, and the matching speed of character string is speeded-up, because it starts tocompare with the front character and can skip when the character of the text doesn’t exist in anysub-model of the pattern tree. Thirdly, the algorithm can fix the problem of the unefficient inskip[i+m-1]<skip[i+m]. Last but not least, using sparse matrix for storaging pattern tree,it canreduce algorithm memory requirements.