通信学报
通信學報
통신학보
Journal on Communications
2015年
10期
172-180
,共9页
张萍%刘燕兵%于静%谭建龙
張萍%劉燕兵%于靜%譚建龍
장평%류연병%우정%담건룡
入侵检测%多模式串匹配%位向量%递归散列函数%空间高效
入侵檢測%多模式串匹配%位嚮量%遞歸散列函數%空間高效
입침검측%다모식천필배%위향량%체귀산렬함수%공간고효
intrusion detection%multiple string matching%bit-vector%recursive hash function%space-efficient
经典的多模式串匹配算法AC的内存开销巨大,已经无法满足当前高速网络环境下大规模特征串实时匹配的应用需求.针对这一问题,提出一种空间高效的多模式串匹配算法—HashTrie.该算法运用递归散列函数,将模式串集合的信息存储在位向量中,以取代状态转移表来减少空间消耗,并利用Rank操作进行快速匹配校验.理论分析表明,HashTrie算法的空间复杂度为O(|P|),与模式串集合的规模|P|线性相关,与字符集大小σ无关,优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|).在随机数据集和真实数据集(Snort、ClamAV和URL)上的测试结果表明,HashTrie算法比AC算法节约高达99.6％的存储空间,匹配速度约为AC算法的一半左右.HashTrie算法适合于模式串集合规模较大、模式串长度较短的多模式串匹配问题,是一种空间高效的多模式串匹配算法.
經典的多模式串匹配算法AC的內存開銷巨大,已經無法滿足噹前高速網絡環境下大規模特徵串實時匹配的應用需求.針對這一問題,提齣一種空間高效的多模式串匹配算法—HashTrie.該算法運用遞歸散列函數,將模式串集閤的信息存儲在位嚮量中,以取代狀態轉移錶來減少空間消耗,併利用Rank操作進行快速匹配校驗.理論分析錶明,HashTrie算法的空間複雜度為O(|P|),與模式串集閤的規模|P|線性相關,與字符集大小σ無關,優于經典多模式串匹配算法AC的空間複雜度O(|P|σlog|P|).在隨機數據集和真實數據集(Snort、ClamAV和URL)上的測試結果錶明,HashTrie算法比AC算法節約高達99.6％的存儲空間,匹配速度約為AC算法的一半左右.HashTrie算法適閤于模式串集閤規模較大、模式串長度較短的多模式串匹配問題,是一種空間高效的多模式串匹配算法.
경전적다모식천필배산법AC적내존개소거대,이경무법만족당전고속망락배경하대규모특정천실시필배적응용수구.침대저일문제,제출일충공간고효적다모식천필배산법—HashTrie.해산법운용체귀산렬함수,장모식천집합적신식존저재위향량중,이취대상태전이표래감소공간소모,병이용Rank조작진행쾌속필배교험.이론분석표명,HashTrie산법적공간복잡도위O(|P|),여모식천집합적규모|P|선성상관,여자부집대소σ무관,우우경전다모식천필배산법AC적공간복잡도O(|P|σlog|P|).재수궤수거집화진실수거집(Snort、ClamAV화URL)상적측시결과표명,HashTrie산법비AC산법절약고체99.6％적존저공간,필배속도약위AC산법적일반좌우.HashTrie산법괄합우모식천집합규모교대、모식천장도교단적다모식천필배문제,시일충공간고효적다모식천필배산법.
