一种面向网络安全检测的高性能正则表达式匹配算法_张树壮
第33卷 第10期2010年10月
计  算  机  学  报
CH INESE JOURNA L OF COM PU TERS
V ol.33N o.10
Oct.2010
收稿日期:2010-08-22.本课题得到国家 八六三 高技术研究发展计划项目基金(2007AA01Z406,2007AA01Z467,2007AA01Z442,2007AA01Z474)、国家 九七三 重点基础研究发展规划项目基金(2007CB311101)、国家自然科学基金(60903209)资助.张树壮，男,1982年生，博士研究生，主要研究方向为网络安全、信息内容安全.E -m ail:zhangshuz huang@softw are.ict.ac.罗 浩，男,1979年生，博士，副研究员，主要研究方向为网络安全.，男,1960年生，教授，博士生导师，中国工程院院士，主要研究领域为计算机网络与信息安全.云晓春，男,1971年生，研究员，博士生导师，主要研究领域为网络安全.
一种面向网络安全检测的高性能正则表达式匹配算法
张树壮1) 罗 浩2)
减免学费申请书
1),2)
云晓春
2)
1)(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)
2)(
中国科学院计算技术研究所信息安全研究中心 北京 100097)
摘 要 目前进行正则表达式匹配的典型工具DF A 和N FA 都存在匹配效率和内存需求之间不可调和的矛盾，无法胜任网络安全检测中大规模正则表达式的匹配.为了解决这个问题，文中从网络安全检测的行为特点出发，结合DFA 、N F A 模型各自的特性，提出了一种基于猜测-验证的匹配方法.首先使用D FA 对正则表达式中的部分子特征进行搜索，完成特征存在性的猜测；当猜测到有可能匹配某个特征后，再使用N FA 进行验证.文中方法既充分利用了DFA 的高效性，减少了对相对较慢的验证过程的调用，又借助N FA 避免了内存消耗过于巨大.结果表明，该方法可以在大大减少内存需求的情况下，实现正则表达式的高效匹配.关键词 特征匹配；正则表达式；有穷自动机；子特征；猜测-验证
中图法分类号T P 393  DOI 号:10.3724/SP.J.1016.2010.01976
冬奥会首金
An Efficient Regular Expression Matching Algorithm for
Network Security Inspection
ZH ANG Shu -Zhuang 1) LUO H ao 2) FAN G Bin -Xing 1),2) YUN Xiao -Chun 2)
1)
(S ch ool of Comp uter Sc ie nc e an d Te chnolog y ,H ar bin I nstitu te of Te chnolog y ,H ar bin  150001)
2)
(In stitute of Compu ting T echnolog y ,Chine se Ac ade my of S cience s,Beij ing  100097)
Abstract  Signature matching has been one of the key techniques in netw ork security because of its high efficiency and ex actness.As the attacks and malw ares on netw ork are beco ming m ore
com plex ,r eg ular ex pressions w hich are mor e ex pressive than exact string s are w idely used in va -r io us secur ity system s.H ow ever ,the strong description capability also makes the matching of
reg ular expressio ns faces serious challenges.T raditionally ,regular ex pression m atching is based on either DFA or NFA.H ow ever,bo th of them hav e an irreconcilable co ntradiction betw een memory requirement and processing speed,w hich makes them impractical o n larg e -scale rule set.In order to address this issue,this paper proposes a m atching alg orithm based on g uessing and verification.It first searches special sub patterns o f each r ule by DFA,and checks the result by NFA once the previous g uessing is successful.T his algor ithm takes advantag e o f the hig h pro -cessing efficiency o f DFA and compact representatio n of NFA.It can im pro ve the m atching eff-i
ciency by reducing the fr equency of calling the slow er verification behaviors.The result show s that this proposal can prov ide a high throughout as w ell as a mo derate memory requirement.Keywords  signature m atching;reg ular ex pression;finite autom ato n;sub pattern;g uessing and verification
1 引 言
在网络上的信息随时间呈指数增长的今天，网络安全的一个重要任务就是阻止有害信息在网络上蔓延以及机密信息通过网络泄露.使用特征匹配技术对数据进行搜索是发现这种有害信息流的基本手段之一.在网络安全检测中，特征匹配的特点是规则数量多且对实时性要求高.作为重要的支撑技术，匹配算法性能的好坏是影响系统性能的决定性因素之一.对于精确字符串匹配，过去的几十年里从理论到技
术都已经进行了深入的研究，并取得了重大的突破，出现了多个接近理论性能上限的算法，如AC、WU-M ANBER、SBOM等等.这些经典算法在网络安全检测中发挥了巨大的作用.然而，随着网络的不断发展，攻击者也在不断地针对各种安全检测技术进行躲避和隐藏，这使得网络中的攻击和恶意代码变得越来越复杂，简单的精确字符串模式已经难以准确地描述其特征.因此，正则表达式以其强大、灵活的表达能力，迅速成为描述新一代规则的主要工具，开源社区和商业界都开始广泛使用正则表达式来增强协议特征和安全特征的描述.例如Linux应用层协议分类器(Linux Application Pro-to col Classifier,L7-filter )就全部采用正则表达式来识别100多种应用层协议.入侵检测系统Snort 的过滤规则在2003年以前全部为精确字符串，但最新发布的规则集中，正则表达式的比例已经超过了40%.入侵检测系统Bro 也直接使用正则表达式来描述它的过滤规则.在商业市场上,3Co m的TippingPo int X505 以及Cisco的各种网络安全系统 ，都开始使用正则表达式.目前Cisco已经将基于正则表达式的内容检测集成到了其网络操作系统中.
使用正则表达式来描述攻击的特征，比传统的提取精确字符串方法更准确、方便和有效，然而其强大的能力也令它在实际应用中面临诸多的挑战.有穷自动机(FA)和正则表达式所表示的语言都是正则语言，因此有穷自动机通常用来实现对正则表达式的匹配.有两种典型的有穷自动机可以完成这个任务：非确定型有穷自动机(NFA)和确定型有穷自动机(DFA).NFA的优点是空间复杂度比较低，其状态数目与正则表达式的长度呈线性关系.然而在处理每一个字符时,NFA必须逐个处理活动状态集合中的所有状态，
匹配效率非常低.相比之下,DFA 处理一个字符则只需要访问一个状态.但若将每条正则表达式编译成单独的DFA，其时间复杂度将随着规则数目的增多而增大，而将所有的正则表达式编译成一个混合DFA时，又会导致其空间需求大大增加，当前的硬件条件将无法满足如此大的内存需求.例如在L7-filter中，当规则数目为40时，其DFA的状态数目将超过136000，内存需求为1 5GB以上[1].由于DFA和NFA在内存需求和处理效率上的矛盾，它们都不能同时满足网络安全检测中处理大规模规则集和实时性的要求.针对这种情况，近些年来出现了一系列的研究.UC Berkeley、Bel-l Labs以及Goo gle的Yu等人首先系统地论述了正则表达式在网络安全检测和协议识别中的优势，对不同的匹配方法进行了分析和评价，并提出了规则改写和分组匹配等方法.随后由于Cisco公司的推动,Washing ton U niv ersity的Kumar和Becchi 等人对这个问题进行了更为深入和细致的研究，提出了D2FA[2]、状态合并(State M er ging)[3]、H-FA[4]、混合自动机(H ybr id-FA)[5]以及XFA[6]等方法来实现大规模正则表达式的实用化.这些工作大大提高了某些特殊类型正则表达式的实用化和匹配效率.国内对高性能正则表达式匹配技术的研究也在不断加强，哈尔滨工业大学网络与信息安全技术研究中心、清华大学、国防科技大学、中国科学院计算技术研究所以及国家互联网应急响应中心等等，都已投入到这一关键技术的研究中.
本文从网络安全检测的行为特点出发，结合DFA、NFA模型各自的特性，提出了一种基于猜测-验证的匹配方法.这种方法考虑到了网络中的数据只有很少一部分是带有攻击的恶意数据，因此使用猜测过程
分检出不值得怀疑的正常数据，而只对少数具有部分恶意特征的数据进行验证.由于使用了DFA和NFA两种不同的模型来分别完成猜测和验证，本文方法可以在大大减小内存需求的情况下，实现正则表达式的高速匹配.本文第2节对当前的主要研究成果进行分类介绍；第3节对基于猜测-验证的匹配方法的原理和实现进行详细地描述和分析；第4节对第3节提出的方法进行扩展；第5节给出
猴的吉祥语1977
10期张树壮等：一种面向网络安全检测的高性能正则表达式匹配算法
Application Layer Packet Class ifier for Linux.l7-filter.s ou rceforge.n et/
<[EB/OL].h ttp://w ww.
Bro Intrusion Detection Sys tem./Over-view.htm
TippingPoint X505.w w w.tippingpoint/prod-ucts_ips.html
Cisco IOS IPS Deployment Guide.h ttp://w w w.cisco
实验结果，并与当前代表性方法的结果进行对比分析；第6节是最后的结论，同时对未来的工作进行展望.
鼠标左键不灵
2 相关工作介绍
要想对正则表达式进行实际应用，必须降低NFA处理一个字符所需要的时间或者减少DFA所需要的内存空间.NFA的时间复杂度是由其理论模型所决定的，所以在不改变处理器体系结构的情况下，很难对其进行改进，当前的大多数研究都集中于对DFA的内存进行缩减，这些研究可以大致分为两类，下面就分别对其中的代表性方法进行一下简要介绍.
DFA的主要存储消耗为一个n | |的二维转换函数表，其中n为状态数目,| |为字母表大小.它占用DFA空间的95%以上，因此缩减DFA的第1类方法是缩减DFA的转换表.要缩减二维表，第1种方法是缩减其列数.陈曙晖等人[7]提出一种基于集合交割的方法来对输入字符进行预编码，文献[3]和文献[8]中则提出了等价类分割的方法.这两种方法都是通过将整个字母表分成多个不相交子集，并使用子集来代替字母表中的元素，从而减少表的列数.文献[9]则进一步将状态和输入字符进行联合编码来提高对字母表的压缩效果.第2种缩减二维表的方法是减少表项，使其成为稀疏表.2006年Kum ar等人在文献[2]中首先提出了D2FA的方法，其基本思想是：如果两个状态s和t对于相同的字符具有相同的跳转目标，则在其中一个状态s中去掉所有和t中等价的表项，然后再引入一条从s 到t的转换，称为缺省转换(default transition)，它不需要输入字符也能进行跳转，这种方法可以消除大量的转换表项.Kumar还在文献[10]中对这种方法进行了改进，提出了CD2FA，以便在引入缺省转换的情况下也能通过访问一个状态完成一个输入字符的处理.Becchi在文献[11]中提出了另一种简单且有效的改进办法，即使用状态的深度属
性生成D2FA.在处理一个长度为n的字符串时，这种方法访问的状态数目不大于2n.2008年Ficara等人在文献[9]中提出了 FA结构，这种结构中每个状态仅仅存储与其相邻状态不同的表项，而其余表项直接从其父节点继承而来.为了进一步消除转换项冗余，文献[3]中提出了状态合并(State M er ging)的方法.其基本思想是：如果两个状态具有目标相同的转换表项(无论是否对应于相同的字符)，则将两个状态合并起来，形成一个混合状态，这样就大大减少了转换表的行数.文献[12]中提出了转换表共享方法来改进状态合并方法.上述冗余消除的方法虽然可以消减掉DFA中90%以上的转换边，但却无法彻底解决DFA的空间占用问题.因为DFA的内存是随状态数目呈平方级甚至指数级的增长，但转换的消除只能是线性的缩减.因为无论怎样缩减，要想保持与原始DFA的等价性，都至少要保持其状态之间的连通性，即保持树形结构.
使用DFA进行匹配的第2类方法是在匹配中不再使用原始的DFA结构，而是使用NFA和DFA 的混合结构或者改进的DFA结构，从而避免DFA 状态的膨胀.Yu等人在文献[1]中提出了将正则表达式规则集进行简单分组的思想.而文献[13]中则提出一种更加合理的分组策略：它首先定义膨胀率DR来描述正则表达式的空间膨胀特性，然后基于DR提出一种分片算法，这种方法有效地选择出导致DFA状态膨胀的片段并进行隔离，从而降低了单个正则表达式的存储需求.同时文中还基于正则表达式的组合关系提出了一种选择性分组算法.对规则进行分组匹配实际上是在广义上使用了NFA 的组织形式，只是每次转换的活动状态数目是一定的(等于分组的数目).文献[5]中将这种方法进一步推广和细化，提出了H ybrid-FA.
其特点就是首先将整个规则集编译成一个NFA，然后只将一部分NFA转化成DFA，形成DFA状态和NFA状态同时存在的情形，匹配时对两种不同的状态使用不同过程.H-FA[4]和XFA[6,14]则引入了额外的信息来对DFA的匹配过程进行记录，从而大大减少了DFA为了记录各种不同情况所需要的状态数目.文献[4]还提出一种方法，依据字符出现的概率将正则表达式划分为前缀和后缀两部分，并使用不同的自动机(fast path auto maton and slow path auto ma-ton)分别进行处理，通过减少对速度较慢的后缀匹配的调用来提高整个系统的匹配效率.
本文的方法借鉴了上述的研究成果，但又不同于上述研究.本文方法分为猜测和验证两个步骤，分别由单独一个DFA和一组NFA来完成，但是并不将它们编译在一个统一的结构中，而是在DFA的接受状态和NFA之间建立联系，以便完成猜测后的验证.本文方法中也使用额外的信息来辅助匹配，但并不试图使得到的DFA和经典方法构建的DFA
1978计  算  机  学  报2010年拾金不昧是什么意思
完全等价，而是为了针对网络安全检测的特点，将同一个正则表达式的两个邻接子特征的匹配结果关联起来，使猜测更准确并保证匹配结果的正确性.
3 基于猜测-验证的正则表达式匹配
3.1 网络安全检测中的正则表达式匹配
网络安全中使用正则表达式作为匹配规则，是为了能够更准确地捕获各种攻击和恶意代码的特征，这与用它来表示形式化语言的初衷有着很大的不同，这些不同也正是本文的基本出发点.首先，检测规则更加注重描述攻击行为的多个阶段或恶意代码多个部分之间的逻辑关系与位置关系，所以网络检测类的应用中所使用的规则一般都可以明显地分成若干个部分，如图1所示.图中每个部分表示一个完整规则的子特征，下文中称为sub _pattern，子特征之间用正则表达式的运算符连接起来；第二，网络安全检测所关心的结果并不是两种不同形式语言的等价性，而是更注重验证正则表达式所描述特征的存在性.因此这里的匹配更确切的说法应该是搜索(为了保持一致，下文仍称之为匹配).第三，在网络检测中，通常对要检验的数据没有任何先验知识，因此不知道在输入数据中是否存在一个子串能够命中规则集中某个正则表达式，也不知道这个子串从哪里开始.通常的做法是假定匹配子串可能在任意位置出现，从而在每个不是以 $ 开始的正则表达式前面加上 .* 操作符，但这种做法也导致了自动机所需要内存的增多.第四，网络检测中，匹配是一个短暂但频率很高的动作，通常是以包或者流为输入单位，并且只有极少数输入才能完全命中某个完整特征，绝大多数被检测的数据都是正常数据，不含有任何目标特征
.
图1 安全规则的示意图( 表示正则运算符)
3.2 基于猜测-验证的匹配算法
DFA 和NFA 的结构都可以看成是一个有向图，其中状态构成图的顶点，状态之间的转换构成有
向边.上面的分析中提到，在网络安全检测中只有极少数输入才会命中特征.假设初始状态的深度为0，那么这个特点反映在具体的匹配过程中则表现为大部分遍历行为都只是访问图的浅层顶点，这部分顶点只占整个图的一小部分.深度比较大的顶点则必
须当某个输入和特征吻合程度较大乃至完整匹配到某个特征时才会被访问.直接使用原始DFA 来进行大规模正则表达式匹配之所以不可行，就是因为它需要将所有的正则表达式完整地表示在一个结构中，而安全规则中将多个sub_patter n 连接成一个整体的时候使用了特殊的操作符，这些操作符导致了DFA 状态数目的剧烈增长，从而带来在现有资源下无法接受的内存消耗.这种将规则全部编译到一个DFA 中的行为，不仅造成了DFA 的内存需求不可接受，同时也不符合当前计算机结构的分级内存体系特点，从而降低处理效率.因为匹配类算法的过程主要是通过查表来进行，它的时间消耗取决于访存的次数和cache 的使用效率[15].
为此本文提出了基于猜测-验证的匹配方法：它首先从整条规则中还原出各个sub_pattern，然后以sub
_patter n 的出现为依据来猜测一个输入是否有可能匹配某个特征.只有某个输入通过猜测后，才进行最后的完整性验证.验证过程主要是检验各个sub_pattern 之间是否符合一定的逻辑和位置关系，即处理图1中所示的连接符号.本文主要针对 .* 、 .{n} 、 [$c 1c 2 c k ]* 和 [$c 1c 2 c k ]{n} 4类连接符.因为以往的大量研究表明，正是这些操作符导致了在使用子集构造法从N FA 生成DFA 时状态数目的剧烈增长.这种方法有两个好处:(1)在提取的时候选择那些简单形式的sub_pattern，从而可以将这些sub_patter n 放在一起形成一个混合的DFA 结构而不会引起巨大的内存需求，使猜测过程可以依靠DFA 快速完成.(2)猜测过程可以将大部分输入过滤掉，只剩下少数能命中某条规则中所有sub_pattern 的数据才需要进行完整的验证过程，因此可以使用速度相对较慢但内存需求对操作符不敏感的NFA 来完成.
为了描述方便，规定:R 表示正则表达式集合,r 表示R 中的某一条正则表达式，即{r j  R |1 j
|R |}.M 表示每个正则表达式中sub_pattern 的数目,s j ,k 表示r j 的第k 个sub_pattern (1 k  M).S 表示sub_pattern 组成的集合，而由只属于r j 中的sub_pattern 组成的集合则表示为S j .由r j 形成的NFA 表示为s _N FA j ，所有s _N FA 形成的集合称为S _N FA.字符串用T 表示,T 的子串用t 表示，不同的子串用下标区分.基于猜测-验证的正则表达式匹配算法其预处理和匹配过程如算法1和算法2所示.
1979
10期张树壮等：一种面向网络安全检测的高性能正则表达式匹配算法
算法1. pre_pro cess(R).
//预处理过滤规则，构建猜测用的D FA和验证用的NF A
1.S= ,S_N FA=
2.for(each r j R)do
3. S j=ex tr act_s ub(r j)
4. S=S S j
5. for(k=1to M)do
6.  if(s j,k S j)then
7.  set_map(map j,1,k)
8.  end if
9. end for
10.s_N FA j=build_N FA(S j)
11.S_N FA=S_N FA s_N FA j
13.DFA=build_D FA(S)
算法2. M atch(DFA,S_N FA,T).
//对输入数据T进行匹配
1.for(each p T)do
2. state=df a_match(DFA,p)
3.  if(s tate DF A.accep t_states)then
4.  for(each s_N FA j in state.r ule_list)do
5.    set_bit(map j,0,state.index_list[j])
6.    if(map j==0)then
7.    nf a_match(s_N FA j,T)
8.    end if
9.  end for
10. end if
算法1给出了预处理过程.对于每个正则表达式r j，首先从中抽取出若干个sub_pattern作为猜测条件.为了对同一正则表达式中的多个sub_patter n 进行记录，算法中使用了一个bitmap型变量map 来追踪各个sub_pattern的出现情况.如果一个r j的第k个sub_pattern被抽取作为猜测条件，那么map的第k个bit则会被set_map函数设置为1；预处理过程为每个r j构建一个s_N FA j，并在最后使用选取出来的全部sub_pattern构建一个混合DFA.需要注意的是，不同的正则表达式中可能存在相同的sub_pattern，所以一个sub_pattern可能与多个正则表达式相关联.为了记录这种关联，在DFA的接受状态中增加了两个
链表:rule_list和index_list.rule_list用来记录包含这个接受状态所代表的sub_pattern的所有正则表达式,index_list 用来记录这个sub_pattern在相应m ap中的索引位置.
算法2对匹配过程进行了描述.对于一个输入字符串T，匹配过程首先使用算法1中构建的DFA 逐个处理每个字符，如果访问到了一个接受状态，则更新其对应rule_list中所有规则的map结构，但只有在同一个输入T中到某个map所对应的全部sub_pattern后才会将这个数据交由相应的s_NFA 进行完整的验证.需要注意的是：同一个表达式中的sub_pattern不需要按顺序出现，且预处理中生成的m ap结构并不参与真正的匹配过程，而是在每次匹配前作为模板来生成对应的实例，每次匹配过程的操作都是在其实例上进行.
3.3 算法分析
3.3.1 正确性证明
在网络安全应用中，匹配就是在给定规则集R 和文本T的情况下，出T中是否存在一个或者多个恰好是正则表达式r j(r j R)所表示的语言的子串t.如果T的某个子串t i是r j表示的语言，则称t i 匹配r j.如果能够在T中到t i匹配r j，则称T被命中.下面证明本文提出的基于猜测-验证的匹配结果与使用NFA匹配的结果相同.
定理1. T在基于猜测-验证的匹配中被命中当且仅当它在NFA的匹配中被命中.
证明. 由于猜测-验证法在最后一步使用了NFA进行结果验证，因此能够被猜测-验证法命中的T必然也会被NFA命中.
假设一个输入T能够被NFA命中.不妨设子串t i匹配了r j，那么t i必然可以匹配所有的s j,k S j.而预处理过程中从r j中抽取的sub_pattern集合是S j的子集，因此t i必然可以匹配r j的所有猜测条件，因此T会被输入到s_N FA j中进行验证.所以T必然也会被猜测-验证法命中.当T中出现多个匹配子串时，情况与此类似.得证.证毕.
3.3.2 算法性能分析
下面对猜测-验证法进行一下讨论和分析，给出影响其性能的因素和优化策略.从算法2中可知，本文方法对一个输入的处理由两部分组成：使用DFA 来完成的猜测过程和使用NFA来完成的验证过程.假设对于输入字符串T，使用DFA处理它所需要的时间为Dt(T)，使用NFA处理它所需要的时间为N t(T)，处理过程中验证过程被调用的概率为P，则处理T所需要的总时间为
Dt(T)+P N t(T)(1)
兴趣爱好1980计  算  机  学  报2010年

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。