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

辽宁石油化工大学学报 ›› 2008, Vol. 28 ›› Issue (1): 66-69.

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

张雪松，田宏

大连交通大学软件学院，辽宁大连 116052

收稿日期:2007-08-29 出版日期:2008-03-20 发布日期:2017-07-22

Memory Consumption Studying of Aho-Corasick Algorithm in Intrusion Detection

ZHANG Xue-song, TIAN Hong

Software Institute of Dalian Jiaotong University, Dalian Liaoning 116052, P.R.China

Received:2007-08-29 Published:2008-03-20 Online:2017-07-22

摘要/Abstract

摘要： 多模式匹配算法在网络入侵检测系统中有着广泛的应用，目前的研究主要集中在如何提高算法的匹配速度上，对于算法的内存消耗研究较少。对于基于硬件实现的嵌入式入侵检测而言，如何降低多模式匹配算法的内存消耗也是一个值得关注的问题。Aho-Corasick（AC）算法是一个基于有限状态机的多模式匹配算法，该算法具有O(n)的时间复杂度，但是由于状态表存储开销较大使其难以应用到嵌入式入侵检测系统中。对AC算法的内存消耗进行了深入地研究，分析了几种可行的AC有限状态机存储策略，提出了一种改进的Banded-Row格式的AC有限状态机存储策略。实验结果表明，该策略能够在较小地影响AC算法匹配速度的前提下，更加有效地降低其内存消耗。

关键词: Aho-Corasick算法, 多模式匹配, 稀疏矩阵, 入侵检测

Abstract: 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.

Key words: Aho-Corasick algorithm , Multi-pattern matching , Sparse matrix, Iintrusion detection

张雪松，田宏. 面向入侵检测的Aho-Corasick算法内存消耗研究[J]. 辽宁石油化工大学学报, 2008, 28(1): 66-69.

ZHANG Xue-song, TIAN Hong. Memory Consumption Studying of Aho-Corasick Algorithm in Intrusion Detection[J]. Journal of Liaoning Petrochemical University, 2008, 28(1): 66-69.