As the core algorithm and the most time consuming part of almost every modern network intrusion management system （NIMS）, string matching is essential for the inspection of network flows at the line speed. This pape...As the core algorithm and the most time consuming part of almost every modern network intrusion management system （NIMS）, string matching is essential for the inspection of network flows at the line speed. This paper presents a memory and time efficient string matching algorithm specifically designed for NIMS on commodity processors. Modifications of the Aho-Corasick （AC） algorithm based on the distribution characteristics of NIMS patterns drastically reduce the memory usage without sacrificing speed in software implementations. In tests on the Snort pattern set and traces that represent typical NIMS workloads, the Snort performance was enhanced 1.48%-20% compared to other well-known alternatives with an automaton size reduction of 4.86-6.11 compared to the standard AC implementation. The results show that special characteristics of the NIMS can be used into a very effective method to optimize the algorithm design.展开更多
基金河南省杰出人才创新基金项目(the Innovation Fundation for Talents of Henan Province under Grant No.074200510013)河南省教育厅自然科学基金项目(the Natural Science Foundation for Education Department of Henan Province under Grant No.2007520048)。
基金the Juniper Research Grant and Intel IXA Univer-sity Program
文摘As the core algorithm and the most time consuming part of almost every modern network intrusion management system （NIMS）, string matching is essential for the inspection of network flows at the line speed. This paper presents a memory and time efficient string matching algorithm specifically designed for NIMS on commodity processors. Modifications of the Aho-Corasick （AC） algorithm based on the distribution characteristics of NIMS patterns drastically reduce the memory usage without sacrificing speed in software implementations. In tests on the Snort pattern set and traces that represent typical NIMS workloads, the Snort performance was enhanced 1.48%-20% compared to other well-known alternatives with an automaton size reduction of 4.86-6.11 compared to the standard AC implementation. The results show that special characteristics of the NIMS can be used into a very effective method to optimize the algorithm design.
