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

An Efficient Regular Expression Matching Algorithm for Network Security Inspection

作　　者：张树壮[1] 罗浩[2] 方滨兴[1,2] 云晓春[2] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]中国科学院计算技术研究所信息安全研究中心,北京100097

出　　处：《计算机学报》2010年第10期1976-1986,共11页Chinese Journal of Computers

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

摘　　要：目前进行正则表达式匹配的典型工具DFA和NFA都存在匹配效率和内存需求之间不可调和的矛盾,无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题,文中从网络安全检测的行为特点出发,结合DFA、NFA模型各自的特性,提出了一种基于猜测-验证的匹配方法.首先使用DFA对正则表达式中的部分子特征进行搜索,完成特征存在性的猜测;当猜测到有可能匹配某个特征后,再使用NFA进行验证.文中方法既充分利用了DFA的高效性,减少了对相对较慢的验证过程的调用,又借助NFA避免了内存消耗过于巨大.结果表明,该方法可以在大大减少内存需求的情况下,实现正则表达式的高效匹配.Signature matching has been one of the key techniques in network security because of its high efficiency and exactness. As the attacks and malwares on network are becoming more complex, regular expressions which are more expressive than exact strings are widely used in va- rious security systems. However, the strong description capability also makes the matching of regular expressions faces serious challenges. Traditionally, regular expression matching is based on either DFA or NFA. However, both of them have an irreconcilable contradiction between memory requirement and processing speed, which makes them impractical on large-scale rule set. In order to address this issue, this paper proposes a matching algorithm based on guessing and verification. It first searches special sub patterns of each rule by DFA, and checks the result by NFA once the previous guessing is successful. This algorithm takes advantage of the high pro- cessing efficiency of DFA and compact representation of NFA. It can improve the matching effi- ciency by reducing the frequency of calling the slower verification behaviors. The result shows that this proposal can provide a high throughout as well as a moderate memory requirement.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]