一种面向网络安全检测的高性能正则表达式匹配算法

摘要：

目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.

关键词：特征匹配、正则表达式、有穷自动机、子特征、猜测-验证

所属期刊栏目：33

分类号：TP393(计算技术、计算机技术)

资助基金：国家"八六三"高技术研究发展计划项目基金2007AA01Z406,2007AA01Z467,2007AA01Z442,2007AA01Z474;国家"九七三"重点基础研究发展规划项目基金2007CB311101;国家自然科学基金60903209

在线出版日期：2011-01-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1976-1986