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

被引：26

作者：

张树壮 ^{[1
]}

罗浩 ^{[2
]}

方滨兴 ^{[1
,2
]}

云晓春 ^{[2
]}

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

[2] 不详

来源：

计算机学报 | 2010年 / 33卷 / 10期

关键词：

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

D O I：

暂无

中图分类号：

TP393.08 [];

学科分类号：

0839 ; 1402 ;

摘要：

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

引用

页码：1976 / 1986

页数：11

共 4 条

[1] 深度包检测中一种高效的正则表达式压缩算法 [J].

徐乾 ;

鄂跃鹏 ;

葛敬国 ;

钱华林 .

软件学报, 2009, 20 (08) :2214-2226

[2] 一种基于深度报文检测的FSM状态表压缩技术 [J].

陈曙晖 ;

苏金树 ;

范慧萍 ;

侯婕 .

计算机研究与发展, 2008, (08) :1299-1306

[3] An Improved DFA for Fast Regular Expression Matching [J].

Ficara, Domenico ;

Giordano, Stefano ;

Procissi, Gregorio ;

Vitucci, Fabio ;

Antichi, Gianni ;

Di Pietro, Andrea .

ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2008, 38 (05) :31-40

[4]

Memory-efficient regular expression search using state merging. Becchi M,Cadambi S. Proceedings of the IEEE Info-com . 2007

← 1 →