DHSWM_一种改进的WM多模式匹配算法

《DHSWM_一种改进的WM多模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第42卷第12期中南大学学报(自然科学版)Vol.42No.122011年12月JournalofCentralSouthUniversity(ScienceandTechnology)Dec.2011DHSWM：一种改进的WM多模式匹配算法刘卫国，胡勇刚(中南大学信息科学与工程学院，湖南长沙，410083)摘要：针对WM算法的查找效率随着模式集规模的增大而降低的问题，提出一种改进算法。在预处理阶段，改变原有Hash表中的链表结构，采用双哈希法将模式串存放在Hash1表中指定的区间，Hash表中存放该存储区间的起始位置与区间长度；Prefix表用于判断模式集中是否存在与当前匹配窗口中

2、文本前缀相同的模式；当Shift表中出现移动值为0时，根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离并存于Shift1表中。在查找阶段，采用双哈希法在Hash1表的某一区间中查找模式串，避免在大规模模式集情况下查找过长的模式链表，扩大匹配操作后匹配窗口滑动的距离，减少冗余的匹配操作，缩短查找时间。研究结果表明：在模式集规模较大时，改进后的算法显著地提高了匹配速度；当模式串数目超过5000条时，改进算法的查找时间要比WM算法缩短40%~47%。关键词：入侵检测；模式匹配；Wu-Manber算法；双哈希查找中图分类号：TP393文献标志码：A文章编号：1672−7207(

3、2011)12−3765−07DHSWM:Animprovedmulti-patternmatchingalgorithmbasedonWMalgorithmLIUWei-guo,HUYong-gang(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)Abstract:Toresolvetheproblemthatwiththeconstantincreaseofthenumberofrules,theperformanceofWu-Manberalgorithm

4、willbecomelessefficient,animprovedWu-ManberalgorithmnameddoubleHashsearchingWu-Manberalgorithm(DHSWM)wasproposed.Inthepre-processingstage,thepatternswerestoredinspecifiedintervalsinHash1tablebydoubleHashmethodwhileHashtablewasusedtostoretheparameterswhichindicatethestartaddressoftheintervalandi

5、tslength.Prefixtablewasusedtodeterminewhetherthepatternsinsetandthetextofcurrentmatchingwindowhadthesameprefix.Whentheshiftingdistancewas0inShifttable,Shift1tablewasusedtostorethemaximumslidingdistanceofmatchingwindowaccordingtothesuffixesappearinginotherlocationsofpatternstring.Inthesearchings

6、tage,doubleHashmethodwasusedtolookuppatternsintheintervalofHash1tabletoavoidsearchingforoverlonglinkedlistinthecaseoflargescalepatternset.Theslidingdistanceofmatchingwindowwasenlargedafterthematchingprocedure,soredundantmatchingoperationswasreducedandthesearchtimewasshortened.Theresultsindicate

7、thatthealgorithmcanimprovethespeedofpatternmatchingwhenthescaleofthepatternsetislarge.ComparedwiththeWMalgorithm,theDHSWMalgorithmcanreducethesearchtimeby40%−47%whenthenumberofpatternsismorethan5000.Keywords:intrusiondetection;pat