文档介绍：: .
第!!卷!第"#期 计!!算!!机!!学!!报 5678!! (68"#
$#"#年"#月 %&'()*)+,-.(/0,1%,23-4).* ,9:8$#"#
!
一种面向网络安全检测的高性能正则表达式匹配算法
"& $& "&%$& $&
张树壮!罗!浩!方滨兴 !云晓春
"&$哈尔滨工业大学计算机科学与技术学院!哈尔滨!"P###"&
$&$中国科学院计算技术研究所信息安全研究中心!北京!"###B=&
摘!要!目前进行正则表达式匹配的典型工具Q1/和(1/都存在匹配效率和内存需求之间不可调和的矛盾%无
法胜任网络安全检测中大规模正则表达式的匹配8为了解决这个问题%文中从网络安全检测的行为特点出发%结合
Q1/'(1/模型各自的特性%提出了一种基于猜测;验证的匹配方法8首先使用Q1/对正则表达式中的部分子特征
进行搜索%完成特征存在性的猜测(当猜测到有可能匹配某个特征后%再使用(1/进行验证8文中方法既充分利用
了Q1/的高效性%减少了对相对较慢的验证过程的调用%又借助(1/避免了内存消耗过于巨大8结果表明%该方
法可以在大大减少内存需求的情况下%实现正则表达式的高效匹配8
关键词!特征匹配(正则表达式(有穷自动机(子特征(猜测;验证
中图法分类号43!B!!!!!"#号!"#8!=$?)*38+8"#"***@8$#"#8#"B=@
$%&''()(*%+,*-./01&231*44(5%60+)7(%-$/-51(+78'51
9*+:51;<*).1(+=#%43*)+(5%
>&/(R*GK;>GKDHI"&!0-, &D6$&!1/(RAEH;SEHI"&%$&!T-(SED6;%GKH$&
"&$!"#$$%$&'$()*+,-!".,/",0/12,"#/$%$34%50-6./7/8+.+*+,$&2,"#/$%$34%50-6./!"P###"&
$&$7/8+.+*+,$&'$()*+./32,"#/$%$34%'#./,8,9"01,(4$&!".,/",8%:,.;./3!"###B=&
$>4+10)+! *EIHD:KNOCD:9GEHIGDJUOOH6HO6L:GOVOW:O9GHEXKOJEHHO:M6NVJO9KNE:WUO9DKJO6L
E:JGEIGOLLE9EOH9WDHYOZD9:HOJJ8/J:GOD::D9VJDHYCD7MDNOJ6HHO:M6NVDNOUO96CEHIC6NO
96C[7OZ%NOIK7DNOZ[NOJJE6HJMGE9GDNOC6NOOZ[NOJJE\O:GDHOZD9:J:NEHIJDNOMEYO7WKJOYEH\D;
NE6KJJO9KNE:WJWJ:OCJ8&6MO\ON%:GOJ:N6HIYOJ9NE[:E6H9D[DUE7E:WD7J6CDVOJ:GOCD:9GEHI6L
NOIK7DNOZ[NOJJE6HJLD9OJJONE6KJ9GD77OHIOJ84NDYE:E6HD77W%NOIK7DNOZ[NOJJE6HCD