双向AC算法及其在入侵检测系统中应用  

Two-Way AC Algorithm and its Application to Intrusion Detection System

作　　者：杨超[1] 

机构地区：[1]合肥学院基础教学部,合肥230601

出　　处：《计算机系统应用》2011年第3期222-225,共4页Computer Systems & Applications

摘　　要：在经典的多模式字符串匹配算法-AC算法的基础上,提出了双向AC算法。该算法在预处理阶段构造正向和反向两个有限状态自动机,匹配时使用正向有限自动机从文本串中间位置向右扫描,同时依据反向有限状态自动机从中间位置向左扫描。将该算法应用于开放源码的入侵检测系统Snort中,实验结果表明较BM算法、WM算法和AC算法本算法有更好的时间性能。如使用发现攻击即停止匹配方式检测,则该算法的效率约为AC算法的1.5倍。Based on AC algorithm for performing multiple string matching algorithms,two-way AC algorithm was proposed.The algorithm constructs a forward finite automaton and a reversed finite automaton in the preprocessing stage.In the Matching stage it scans the text string from middle to right with a forward finite automaton and concurrently from middle to left with a reversed finite automaton.The algorithm has been implemented by modifying the source code of Snort.The experimental result shows that the time performance of two-way AC algorithm is superior to BM algorithm,WM algorithm and AC algorithm.Efficiency of the algorithm is about 1.5 times AC algorithm if the mode of detection is to discover and stop.

关 键 词：AC算法 WM算法 BM算法 串匹配算法 入侵检测系统 SNORT 

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