Research On Pattern Matching Algorithm In Intrusion Detection System

The rapid development of Network brings people a lot of conveniences. However, with the widespread use of Network, the subsequent security problems also bring information security serious challenges. Though traditional technologies of Network security have played their roles in maintaining system security, the technologies mainly focus on enhancing and protecting system itself,at the same time, the drawback of firewall makes that firewall can only protect system from outside but inside. As a static protection technology, firewall can't afford realtime and active protection for intrusion behaviors. Facing more and more needs for more and more increasingly serious Network security problems, Intrusion Detection is born as a complement tofirewall.As an important active method to protect information system security, Intrusion detection has been the research focus in security field recently.A software or hardware system to detect intrusion is called an Intrusion Detection System(IDS).According to data analysis mode, IDS can be classified into two categories: Anomaly IDS and Misuse IDS.Since the higer false positive rate of Anomaly IDS, Misuse IDS has a large portion in IDS market nowadays.How to improve the detection speed is a key problem for current Intrusion detection systems in situation of rapid development of Network speed. For present pattern matching Misuse IDS, Pattern Matching speed(the speed of identifying attack information in an intrusion character library) is the key factor to detection speed.This paper takes the well-known open source intrusion detection system Snort as the research platform, based on the study of Snort system architecture, and emphatically studies the main data structure, function call and intrusion detection algorithm entrance of Snort detection engine. This paper also analyzes three classical pattern-matching algorithms and MWM algorithm. Based on the analysis the working principle of MWM, the key points to improve the performance of MWM algorithm are pointed out.For first matching process,the paper applies Group_Division strategy to MWM. According to the real condition of Snort ruleset, the paper proposes a new algorithm, MWMGD algorithm,which is based on dynamic Group_Division strategy for pattern sets. For second matching process, the paper proposes a heuristics idea. The heuristics idea uses the information among previous pattern and subsequent pattern to guide the subsequent matching process. The paper also gives the theoretical proof of this idea. Based on the idea, the paper proposes a new algorithm, MWMopt.The paper also realizes the two new algorithms in Snort and tests them with DARPA 1999 Intrusion Detection sets.The results show that the two new algorithms are correct and effective. Performance improvement brought by MWMopt algorithm is particularly significant.