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

• 作者: 云晓春 张树壮 方滨兴 罗浩
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 特征匹配 正则表达式 有穷自动机 子特征 猜测-验证
• 年，卷（期）: 2010,（10）
• 页码范围: 1976-1986
• 分类号: TP393
• 字数: 11381字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.01976

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	方滨兴	哈尔滨工业大学计算机科学与技术学院	175	3885	33.0	56.0
3	云晓春	中国科学院计算技术研究所信息安全研究中心	46	890	15.0	29.0
4	罗浩	中国科学院计算技术研究所信息安全研究中心	15	168	6.0	12.0
7	张树壮	哈尔滨工业大学计算机科学与技术学院	4	125	4.0	4.0