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

摘要：

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

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

作者: 张树壮 罗浩 方滨兴 云晓春

作者单位: 哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001 中国科学院计算技术研究所信息安全研究中心,北京,100097 哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001;中国科学院计算技术研究所信息安全研究中心,北京,100097

会议类型: 国内会议

会议名称: 2010年中国计算机大会

会议地点: 杭州

会议语种:中文

页码: 1976-1986

在线出版日期: 2010-10-11（万方平台首次上网日期，不代表论文的发表时间）