一种适合于超大规模特征集的匹配方法

发布时间：2017-11-10 12:01

  本文关键词：一种适合于超大规模特征集的匹配方法

  更多相关文章： 网络安全 超大规模特征匹配 串匹配 混合自动机 算法 信息安全

【摘要】：串匹配技术是入侵检测系统中的关键技术,随着特征数量的增加,现有的自动机类匹配算法都会面对内存占用过大的问题.当特征超过一定数目后,自动机可能根本无法构造.文中提出了一种针对超大规模特征匹配(SLSPM)环境的匹配算法SLSPM.SLSPM算法借助一个块式匹配自动机和若干个普通自动机完成匹配工作,而且能够支持至少上万规模的特征集.与普通匹配自动机先读入状态再判断读入符号的方式不同,SLSPM首先使用散列函数判断当前文本块是否可以被过滤掉.如果文本块无法被过滤且为合法文本块时,再检查当前状态是否是一个能够识别当前文本块的状态.仅在当前状态吻合的情况下再读入下一个文本块进行后续匹配.理论证明显示SLSPM算法具有近似O(n)的复杂度.由于SLSPM算法未能保存全部的跳转信息,其匹配速度相对于高级AhoCorasick算法未有大幅提升.算法的优势在于,该算法在软件环境下能够维持与AC算法相同的匹配性能,而且能够将特征加载规模至少提升至上万以适应超大规模特征集匹配环境.
【作者单位】： 哈尔滨工业大学计算机网络与信息安全技术研究中心;
【基金】：国家“九七三”重点基础研究发展规划项目基金(2011CB302605) 国家“十一五”科技支撑计划(2012BAH37B01) 国家“八六三”高技术研究发展计划项目基金(2012AA012502,2011AA010705,2012AA012506)资助
【分类号】：TP393.08;TP391.1
【正文快照】： 1引言字符串匹配可以被理解为从给定符号序列中找出一个具有某种属性的模式,最简单的例子是从给定字符序列中找出一个给定的字符串.字符串匹配是计算机科学中最古老、研究最广泛的问题之一,并且,字符串匹配的应用随处可见[1],比如生物领域和计算机科学中.本文专注的是计算机科

【参考文献】

中国期刊全文数据库 前3条

1 胡s，

本文编号：1166530