A Fast Pattern Matching Algorithm in Intrusion Detection System
Liu Weihua · Xi'an Jiaotong Daxue xuebao · 2009
A new fast pattern matching algorithm(called BMHF algorithm) is proposed to improve the detecting efficiency of network data based on attack signature and to decrease the packet loss rate in the intrusion detection system(IDS),by analyzing popular pattern matching algorithms such as BM algorithm,BMH algorithm and BMHS algorithm.A new function Q(X) is employed in BMHF to identify the number of a character X matching in the pattern string.When Q(X) equals one,the matched information is used to enlarge the shifting distance.A new shifting distance is also calculated according to the character next to non-matched characters in the pattern string.The maximum distance among these shifting distances is used in the BMHF algorithm.The process is repeated until the matching is completed.Experimental results show that the BMHF algorithm has better efficiency.The decrease in the operation time of CPU is 5.7 percent,and the decrease in the average number of matchings is 12.5 percent.