面向入侵检测的Aho-Corasick算法内存消耗研究  

Memory Consumption Studying of Aho-Corasick Algorithm in Intrusion Detection

作　　者：张雪松[1] 田宏[1] 

机构地区：[1]大连交通大学软件学院,辽宁大连116052

出　　处：《辽宁石油化工大学学报》2008年第1期66-69,共4页Journal of Liaoning Petrochemical University

摘　　要：多模式匹配算法在网络入侵检测系统中有着广泛的应用,目前的研究主要集中在如何提高算法的匹配速度上,对于算法的内存消耗研究较少。对于基于硬件实现的嵌入式入侵检测而言,如何降低多模式匹配算法的内存消耗也是一个值得关注的问题。Aho-Corasick(AC)算法是一个基于有限状态机的多模式匹配算法,该算法具有O(n)的时间复杂度,但是由于状态表存储开销较大使其难以应用到嵌入式入侵检测系统中。对AC算法的内存消耗进行了深入地研究,分析了几种可行的AC有限状态机存储策略,提出了一种改进的Banded-Row格式的AC有限状态机存储策略。实验结果表明,该策略能够在较小地影响AC算法匹配速度的前提下,更加有效地降低其内存消耗。Multi--pattern matching algorithm is widely used in network intrusion detection system. At present, the research is mostly focused on how to improve the algorithm＇s matching speed but pays little attention to the memory consumption. It is a valuable problem to degrade the multi-- pattern matching algorithm＇s memory consumption for embedded IDS based on hardware implementation. Aho--Corasick algorithm is based on finite state machine and has O（n） time complexity. Since the algorithm needs large memory to store the state table, it has great difficulty to be applied to memory restrained intrusion detection system. The Aho--Corasick algorithm＇s memory consumption and several feasible AC FSM storage strategies were deeply discussed. Finally an improved FSM storage strategy was present. The experiment shows that the strategy can effectively degrade the AC algorithm＇s memory consumption and has little affects on matching speed.

关 键 词：Aho—Corasick算法 多模式匹配 稀疏矩阵 入侵检测 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]