面向网络安全的正则表达式匹配技术.pdf

《面向网络安全的正则表达式匹配技术.pdf》由会员分享，可在线阅读，更多相关《面向网络安全的正则表达式匹配技术.pdf（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、软件学报ISsN 1000一9825。CODEN RU)(UEw面“M口，D，跏憎，20ll，22(8)：1838一1854【doi：lO3724，sPJ1001201104034】o中国科学院软件研究所版权所有面向网络安全的正则表达式匹配技术张树壮1+，罗浩2，方滨兴121(哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001)2(中国科学院计算技术研究所信息安全研究中心，北京 l00190)Regular Expressions Matching 1or Network SecurityE-mail：josisccnhttp：，wwwJosorgcnTel，】Fax：+8610一

2、62562563ZHANG Shu-ZhlKm91+， LU0 Ha02，FANG Bin-Xin91，21(school ofComput四Sci钮ce锄d Tecbnology，Harbin Ins6tIle ofTechnoIogy，H呐in 15000l，china)2(I墒眦ati衄s叫ty Research ccnt盱。Institute ofComp眦ing TechnoIogy，ne chinese Acad锄y ofSciences，Beijing lool90，Chim)+Corsponding肌也or：Email：吐姐gshllzllu蛆gpact5 1 8hiteduc

3、n，http：，p扯t5 l 8hite血cnZhang SZ，Luo H，Fang BXRegular expressions matching for network security，扫口，I一口f口，S砸，四，臂，201l，22(8)：1838_18S4http：1nnjosorgcn1000一98254034h臼丑Abstract： This paper analyzes the regular expression matching metllodstime complexityspace complexity锄dthe tradeoff between themThe exper

4、iences，problems，姐d challenges encountered by也e regular expressionmatching in network securi哆field awellcl豁sified and discussed in dcpthFocusing on the伽o issues，acoInprchensive overview of tlle current optimizing techniques and s仃ategies adopted by academic柚d busiesscommunities is presentedFinallya c

5、onclusion and s哪e suggestions for mtIlre research are put forw砌Key words： signature matching；deep packet inspection；regul盯expression；finite叭tomata；memory reduction摘要： 分析了基于有穷状态自动机的正则表达式匹配方法的时间复杂度、空问复杂度以及二者之间的制约关系深入讨论了在网络安全应用中遇到的特有问题与挑战围绕这两个问题，对当前出现的多种优化技术和策略进行了全面的综述和评价。最后对未来的研究方向进行了总结和展望关键词： 特征匹配；深度

6、包检测；正则表达式；有穷自动机；内存缩减中图法分类号：TP393 文献标识码：A传统的网络安全检测是对数据包的结构化头部进行分析然而随着网络的不断发展，许多病毒、恶意代码、入侵指令、垃圾邮件等信息都隐藏在数据包的内容之中因此，当前在进行安全检测时，除了要对数据包头部进行检查之外，也要对数据包的内容进行检测，例如，入侵检测系统会针对各种入侵行为的特点建立一组入侵行为的特征模式集。并定义针对各种行为所应该采取的措施这些行为特征和对应的措施构成系统的安全规则，当发现给定数据命中系统的某条特征模式时则采取相应的措施病毒检测系统有个庞大的病毒特征库据统计，到2010年6月，网络病毒已接近758 473万

7、种。病毒检测的主要操作就是在每一个文件中搜索病毒库中的特征基金项目：国家自然科学基金(60903209)；国家重点基础研究发展计划(973)(2007cB311loo)；国家高技术研究发展计划(863)(2009从0lz437，2007从Olz406，2007从Olz467，2007从Olz442，2007从Olz474，2011从012504)收稿时间：201003-22；修改时间：2010IO-ll；定稿时间：201l一03-07C：Nn网络优先出版：20ll05-12 ll：47。http：饷伸Wcnkinetl【啪“detan，112560TP201105121147005h血l万方数

8、据张树壮等：面向网络安全的正则表达式匹配技术 1839这种使用一组给定的“特征”与网络中的数据内容进行比较。从而发现其中的恶意特征的方法称为深度包检测(deep packet inspection)对于网络安全应用来说，“特征”通常是指入侵检测、防病毒、垃圾邮件过滤等应用中定义的模式串，用来表示攻击、病毒或者垃圾邮件区别于正常网络流量的特征最初的安全规则以精确字符串为主然而，随着网络的不断发展，网络安全攻防双方的技术也在不断发展为了躲避检测，各种攻击、恶意代码等又都在不断刻意隐藏自己的特征，这使得安全系统中所需要的检测规则也越来越复杂例如，蛆o“1】规则：Alerttcp$HOMENET an

9、yj$EXTERNALJmT 1 863(msg：“CHAT MSN login attempt”；now：toserver，established；content：“usR”；d印th：4；nocase；content“TwN”；dist姐ce：1；nocase；)表示要同时匹配“usR”和“TwN”这两个关键词；同样，对于原本为简单字符串的关键词，在实际中也可能以各种不同的形式出现(例如，“模式匹配”可能会写成“模撑式群匹挣配”)这就需要逐一识别各个部分后再进行一定限定条件(位置顺序、有限间距等)的判断来进行识别可见，为了表达更精确的语义和上下文信息，需要将多个特征按照一定的顺序和限定条件

10、进行组合，形成一条复合的匹配规则上述这些问题所需要的规则形式无法用精确串来描述，因此，经典的多模串匹配算法如Ac【2】sBoM【3】wuMANBER【4】等也无法直接使用当人们发现应用层上各种复杂的协议和网络中的攻击方式已经越来越难以提取出准确的字符串特征时，正则表达式以其强大、灵活的表达能力，迅速成为描述新一代规则的主要工具商业界和开源社区都开始广泛使用正则表达式来增强协议特征和安全特征的描述例如，Li肌x应用层协议分类器(1inux application protocolclassifier，简称L7filter)【5】就全部采用正则表达式来识别100多种应用层协议，其中包含了多个复杂的

11、P2P协议开源的入侵检测系统snort在2003年以前，检测规则全部为精确字符串特征，但最新发布的规则集中，正则表达式的比例已经超过了40Bro入侵检测系统【6】也直接使用正则表达式来描述它的规则集在商业市场上，3com的TippingPointx505【7】以及Cisco的各种网络安全系统【8】都开始使用正则表达式目前，Cisco已经将基于正则表达式的内容检测集成到了其网络操作系统中在研究领域，UC Berkeley，bell1abs以及google的胁g yu等人网论述了正则表达式在网络安全检测和协议识别中的优势，对不同的匹配方法进行了分析和评价，并提出了规则改写和分组匹配等方法随后，由于

12、cisco公司的推动，Washin舀on University的Sailesh K_um碣Michela Becchi等人对这个问题进行了更为深入和细致的研究，提出了D2FA【10】、状态合并(state merging)【11】、HF“12】、混合自动机(hybrid FA)【13】以及)(】1A【14】等方法来实现大规模正则表达式的实用化这些工作大大提高了某些特殊类型的正则表达式的实用化和匹配效率国内学术界对高性能正则表达式匹配技术的研究也在不断加强，哈尔滨工业大学网络与信息安全技术研究中心、清华大学、国防科学技术大学、中国科学院计算技术研究所信息安全中心等，都在逐渐投入到这一关键技术的研

13、究中使用正则表达式来描述应用层各种协议和攻击的特征，比传统的提取精确匹配字符串方法更准确、更方便、更有效，然而，其强大的能力也使得它在实际应用中面临诸多的挑战本文第1节给出正则表达式匹配的定义并对各种匹配方法进行分析和比较，最后着重强调正则表达式在网络安全应用中所面临的挑战第2节第4节详细介绍正则表达式匹配技术亟待深入研究的两个关键问题：空间缩减和性能保证。详细论述解决这些问题的多种方法及策略，对其优缺点进行评价第5节对全文进行总结，并指出未来研究的若干方向1问题描述11正则表达式的匹配方法有穷自动机(finite automaton，简称FA)和正则表达式所表示的语言都是正则语言【15】，因

14、此通常用来实现对正则表达式的匹配有两种典型的有穷自动机可以完成这个任务：非确定型有穷自动机(nondeteministic finite跏tomaton，简称小砸A)和确定型有穷自动机(deteministic finite automaton，简称DFA)一个DFA包括5个部分：(1)有穷状态集合Q；(2)有穷的输入符号集合五又称为字母表；(3)转换函数磊又称为跳转函数，它以一个状态和一个输入符号作为变量，返回值为一个状态；(4)初始状态勖OoEQ)；(5)接受状态集合F一个NFA同样包含这5个部分NFA与DFA的区别在于，DFA中6的返回值确定为1个状态；NFA中踞一个以状态和输入字符为变

15、量的函数，但是返回值是可能包含0个或多个状态的集合NFA和DFA之间可以进行相互转化，但是在从、A万方数据1840 面蝴耐矿绔删腮软件学报vol。22，No8，Au目娥20l l到DFA的转化过程中，可能会出现状态数目的剧烈增长，称为状态“爆炸”在本节的后面将会详细说明这种情况实际应用中，由于对需要处理的数据没有任何先验知识，因此无法确定是否存在一个子串匹配给定规则或者匹配的子串从何处开始在这种情况下，有两种方法来正确实现搜索：重复搜索和“一遍搜索(one pass search)”重复搜索的具体做法为：用给定表达式直接构建自动机，然后以输入字符串的每个字符为开始位置重复搜索在每次搜索过程中，

16、顺次读取并处理字符，直到找出了所有的匹配子串下一次搜索从上一次起始点的下一个字符开始(如果匹配类型为穷举匹配)或从最后一个匹配子串的下一个字符开始(如果匹配类型为非重叠匹配)。重复搜索通常用于语言的解析中因为可能要对同一个字符串进行多次搜索，所以其效率非常低在安全检测类应用中，通常使用“一遍搜索”法其做法为，将“，放在没有“”标记的表达式的开头，然后再构建成自动机这就意味着表达式所表示的模式可以出现在输入数据的任何地方只要从前到后一次扫描并处理每一个字符，就可以识别出从任何位置开始的匹配子串，本文后面的讨论都是针对这种情况12正则表达式匹配方法所面临的挑战在实际的应用系统中，通常都配置了多条规

17、则例如，17filter的正则表达式规则为100多条，而snort则为数千条为了叙述方便，本节中用m表示规则集中正则表达式的数目，以表示一条正则表达式的长度为了完成对m条正则表达式的匹配，有两种策略可供选择：(1)将每一条正则表达式编译成单独的一个FA；(2)将研条规则编译到同一个FA中。前者使用在snort和Linll】【L7 filter中，后者则在文献【9，lO】中被提出前面提到，对正则表达式的匹配需要使用有穷自动机来完成，但是A和DFA在实际应用中却有不同的优点和缺点NFA的优点是空间复杂度比较低，因为NFA的状态数目与正则表达式的长度成线性关系然而在处理每一个字符时，由于必须逐个处理

18、活动状态集合中的多个状态，因此匹配效率非常低若将多条规则编译到同一个M1A中，虽然可以在处理过程中同时匹配所有正则表达式的公共前缀，但在实际应用中却会形成更大数量的活动状态集合，处理一个字符的时间复杂度和将每个正则表达式编译成单独一个NFA的时间复杂度相同相比之下，虽然DFA处理一个字符只需要访问一个状态，但若将每条正则表达式编译成单独的DFA，其时间复杂度同样将随着规则数目的增多而增大而将所有的正则表达式编译成一个混合DFA时，则会导致其空间需求大大增加，以当前的硬件条件将无法满足如此大的内存需求使用不同的方法和策略进行匹配时所需要的空间复杂度和处理一个字符的时间复杂度见表1Table l

19、Time锄d space co唧lex时of Various categories孤d methods表l 不同策略和方法下的时空复杂度!坐P!坦翌!g!型!P堡!i!墅!翌坠 !坐P!丝!耻!些!P堡!i!墅i!堕!g!垒!i型!罂P!坠i垒 曼P竺!虫!i丝 !i堕!磐!坠!壁 !P堑!坐!i盟NFA D伽州) 0(小n) D伽2刖) 0(m厅1旦坠 2f竺2 g兰：=2 912 Q(；：2从表1中可以看出，两种方法以及两种策略所形成的4种组合都无法同时满足空间复杂度和时间复杂度比较低的需求要想对正则表达式进行实际应用。必须降低NFA处理一个字符所需要的时间复杂度或者对DFA所需要的内存空

20、间进行缩减NFA的时间复杂度是由其理论模型所决定的。所以在不改变处理器体系结构的情况下很难对其进行改进，因此，当前的研究大多集中于对DFA的内存进行缩减DFA的内存消耗主要用于存储各个状态及其转换表，其空间需求由状态数目决定下面给出几种典型的情况，它们会导致DFA状态数目急剧增长而又在实际规则中频繁出现121 单条正则表达式构建DFA时的状态膨胀第1种导致状态增长的情况是，带有n符号的表达式中某个字符后面带有重复标记，且这个字符与其前驱字符出现了重叠覆盖，此时，需要大量的状态对所有可能的字符排列组合情况进行区分，例如，表达式“qH【，、3)D”中，【】与字符曰的交集为曰，其构成的DFA如图l所

21、示一般来讲，如果重复次数为，次，则阴影部分所包括的状态所形成三角形高为pl，长为p1，总共需要的状态为D酽)万方数据张树壮等：面向网络安全的正则表达式匹配技术Fig1 A DFA for pattem“佃+“切】3D图l模式“忸+【“3D”形成的DFA1841第2种导致状态增加的原因是，不带有“符号的表达式通配符或者一组字符后带有有限重复操作符(册，栉，咒)此时，DFA需要考虑任取字母表中的拧个字符可以组成的所有情况，因此需要o(24)个状态来记录例如，叫一CD，如果在后续的字符串中出现了爿，那么如图2所示，每个状态都需要处理似和not彳)两种情况为什么虽然第2种表达式与第1种表达式形式类似却

22、有截然不同的空间复杂度(D(朋2)和D(2“)呢?因为在第1种情况下，中间的状态每个只需要派生出一种新状态，或者转回到某个旧状态；而在第2种情况下，每个中间状态都可能派生出多个状态，从而造成指数级增长 彳AFig2 A DFA for pattem“切2)C-D”图2模式“物2)cD”形成的DFA122 多条正则表达式构建DFA时的交互作用上面描述了单条正则表达式构建在DFA时导致状态数目增长的情况然而有些情况下，即使原来的单条规则不会引发状态数目的增加，一旦当将多条正则表达式编译在同一个DFA中，它们之间也会由于相互作用而造成DFA状态数目的急剧增长例如，口6谢和够劝，如图3所示，这两条规则

23、在单独构建时都不会引起DFA数目的增长，但由于两个表达式中的“妒都可以匹配另一条正则表达式所匹配的所有字串，因此将它们编译到一个DFA中时，必须用额外状态记录所有可能的组合情况，形成的DFA和示意图如图4和图5所示一般而言，当多条规则编译在一起时，如果有七个正则表达式，每个表达式中出现工次“，则需要o(H)勺个状态来记录所有可能出现的前缀的幂集在这种情况下，即使每个规则只有1个“，操作符，增加一个类似的规则也会使得DFA的状态数目增加1倍在L7filter中有很多类似的规则，例如，识别远程桌面协议的“fdpdr万方数据1842 乃“埘讲矿S够w口愆软件学报v0122，No8，AugIIst 2

24、叭1幸cliprdr+rdpsnd”和Int锄et radio协议的“membemame事session+player”snort中也存在大量类似规则，而且某些规则中，“符号的数目甚至达到了6个Fig3 DFAs for pattem如+cd and巧+曲图3模式曲+甜和盯+办各自形成的DFAFig4 Composite DFA for pattem口64cd and盯+办图4模式曲甜和盯+劝编译在一起形成的DFAFig5 Exemplification ofDFA obtained by compiling“幸船l口幸衄16”and“2宅E2口十月点26together图5将模式“+见914

25、+兄E16”和“+兄改口+尼眈6”编译在一起时的DFA结构示意图本节叙述了一些能使DFA状态发生巨大膨胀的正则表达式操作符，丽这这些操作符也正是在实际中最常用的截止到2007年11月，8 536条snort规则中有5 549条正则表达式在这些表达式中，含有“的规则有905(163)条，而含有“，z”操作符的规则有2 445(44)条通过上述分析可知，将这些规则构建成DFA需要极大的内存空间，因此，基于DFA的匹配方法无法直接应用在实际中2基于冗余消除的内存空间缩减一个DFA状态通常由两部分组成：表示占函数的转换表和接受规则列表前者为一个大小为l捌的数组，在实际应用中，默茜常选取为AscII表，

26、其大小为256项，每一项表示当前状态在接到一个字符输入时将跳转向哪个状态后者通常为一个链表，表示匹配过程中若经由一系列转换跳转到了当前状态，则当前输入的字符串与哪些正则表达式匹配这个列表可以为空，也可能为多项如果某个状态的接受列表不为空则称其为接受状态一个具有n个状态DFA的丰要存储消耗为一个n闭的二维表，它占用DFA空问的95以上本节介绍的方法都是对这个二维表的存储空间进行缩减21减少字母表的大小对一个DFA来讲，转换表为一个二维表，其行数等于DFA的状态数目，而列数等于字母表中字符的个数如果可以减少整个转换表的列数，则可以有效地降低内存消耗基于寻找等价类的字母表压缩法就是利用这一原理来减少

27、DFA的内存消耗其基本思想是，字母表三中的字符可以分成若干类cI，I，G，每一类包含1个或多个字符如果其中一类包含多个字符，那么这个类中的任意两个字符。和c，必须满足：对于给定DFA的所有状态，都万方数据张树壮等：面向网络安全的正则表达式匹配技术 1843有s，c沪s，c，)陈曙晖等人在文献【16】中提出一种基于集合交割的方法来对输入字符进行预编码，从而减少自动机转换表的列数文献1l】中也提出了类似的方法，它们首先将整个字母表看成属于同一等价类，然后对自动机的状态进行遍历，根据每个状态的转换表不断将现有的等价类进行分割文献17】中进一步扩展了这种方法文献【18的作者则观察到，目标为同一个状态的

28、转换，其对应的字符往往都是相同的因此，它将状态和输入字符进行联合编码，形成statechar编码，进一步提高了对字母表中字符的压缩效果22缩减单个状态的冗余转换DFA结构类似于一个有向图，它的每一个状态都可以在接受一个输入字符后跳转向另外一个状态但是对于不同的字符，其跳转的目标状态却可能是相同的，这就形成了单个状态内的转换表项冗余图6中给出了一个简单的DFA以及状态l的转换表，假设字母表器=口，6，c，讲，町以看l叶，状态l的跳转表中6和c两项的值是相同的，因此可以通过消减这种相同表项的冗余来减少跳转表需要的空间文献【ll】中提出了一种增加间接转换表的方法来消除冗余，其基本思想是，将原始的表改

29、用两个表来表示：一个表用来存储跳转的目标，称为转换表，但是对于多个相同的表项只存储1次；另一个表有阁项，对应字母表中的每一个字符，但是它不存储实际的跳转目标，而是存储跳转目标在转换表中的索引，称为索引表在实际应用中，跳转目标通常为整数或者指针，且最多有l司种不同的值，因此索引表只需要用log闭bits就可以对转换表进行索引当原始表项中存在大量冗余时，使用这种索引表的方式就可以节约大量的空间例如在图3中，假设原始表项为32bits，则索引表的每一项可以用2bits来表示由于有两个跳转项相同，冈此可以节约32432324=24bits 沪沪文“bd cP一Oginal仃ansition ta曲le

30、岛Index tabIe圜Tmsition table圉Fig6 DFA and its嘶ginal transition table，transition table锄d index table图6 DFA及其原始转换表和索引表在实际的DFA中，多数状态往往只对少数几个字符有不同的目标状态，而大多数字符都会跳转向初始状态so或者DFA所形成的有向图中的某些起连接作用的关键节点，因此会存在大量的冗余项，使用索引表的方式可以节约大量的存储空间然而这种方法在处理一个字符时，需要先访问一次索引表，然后再从转换表中找到真正的目标状态，比直接读取原始跳转表增加了一次访存操作23消除不同状态间“等价”项的

31、冗余在DFA中，不但单个状态的转表内存在着冗余项，不同的状态之间也存在着大量的相同项冗余图7给出了这种情况的一个典型例子如图7所示的DFA由“口+”，“6+c”和“c矿这3个正则表达式构建而成，共有5个状态。并且任何一个状态的转换表内部都不存在相同项的冗余然而通过观察其原始转换表可以发现，在各个状态间却存在着大量的相同项冗余为了描述方便，给出如下定义：两个不同的状态J和f，如果对于相同的输入字符具有同样的跳转目标，则称这两个跳转项为等价项如果可以消除不同状态之间由等价项引起的冗余，则可以进一步减少存储空间2006年，K啪ar等人在文献10】中首先提出了消除等价项冗余的方法，其基本思想是：如果两

32、个状态s和f对于相同的字符具有相同的跳转目标，则在其中一个状态s中去掉所有和f中等价的表项，然后再引入一条从嚣到f的转换，称为缺省转换(default打ansition)，它不需要输入字符也能进行跳转在进行匹配时，如果访问到了状态J，并且J对当前的输入字符c没有定义跳转目标，则根据其缺省转换跳转到f，然后从f中取出跳转目标或者万方数据乃“埘口，矿蜘陀软件学报v0122，No8，AugIlst 201l继续到f的缺省目标状态中去找跳转目标这种为每个状态增加了缺省转换的DFA称为Delayed InputDFA(D2FA)D2FA的构建方法为：首先以DFA的状态为顶点形成一个完全图，然后计算任意两

33、个状态间具有的等价项的数目，并以此数目作为完全图中每条边的权值；接着使用克鲁斯卡尔算法生成1个或多个最大生成树，称为消减树：最后以消减树的边作为缺省转换，完成冗余项的消除图8给出了图7中DFA对应的D2FA及其转换表，其中，状态l为整个消减树的根节点，加粗的黑线表示缺省转换，跳转表中空白项为消减掉的项，有值的转换项称为有效转换可见，D2FA中的转换项数从原始DFA的20项缩减为9项匹配时，若当前活动状态为状态3，而输入字符为“矿，则由于状态3对应于“矿的跳转项已经被缩减，因此必须沿着其缺省转换，读取状态l的转换表并取得对应于字母d的跳转目标：状态4n 6 C d1 2 3 l 42 2 3 l

34、 43 2 3 5 44 2 3 l 45 2 3 l 4Fig7 DFA and its odginal transition table图7 DFA及其原始转换表口 6 C d De凤lltl 2 3 l 42 I3 5 14 l5 lFig8 D2FA and is reduced缸|ansition table图8 D2FA及其缩减后的转换表虽然D2FA结构可以消除不同状态间等价项带来的冗余，极大地降低了DFA需要的空间，但是它增加了处理一个字符的时间复杂度因为在原始的DFA中，每一个转换都会“消耗”一个字符，而D2FA中，缺省转换是不消耗字符的对于一个字符，D2FA可能需要经过多次缺

35、省转换才能找到其跳转日标为了能够在消减空间消耗的基础上保持匹配效率，Kumar在文献19】中对D2FA进行了改进，提出了CD2FACD2FA在转换项中不再直接存储跳转的目标状态，而是存储以下信息：(1)从消减树根节点到状态自身的路径所经过的祖先节点；(2)这些祖先节点的有效转换；(3)当前节点所拥有的有效转换；(4)路径中所经过的接受状态节点因此在cD2FA中，转换项被称为content label同时还提出了一种构造哈希函数的方法，这个哈希函数可以用content 1abel为输入，计算出对应于每个字符的跳转目标的地址使用content label可以使cD2FA能够和原始DFA一样，在处理

36、一个字符时仅访问1个状态但是由于每个content l曲el项的容量有限，因此消减树的直径不能过大，通常取小于等于2，这就影响了缺省转换的消减效果Becchi在文献20】中提出了另一种简单而有效的办法：首先将原始DFA的每个状态附加一个深度值，这个值等于从初始状态J。到其自身所需要经过的最短路径；然后在构造消减树时，只允许缺省转换从深度值较高的状态指向深度值较低的状态，但不需要限制消减树的半径这种方法生成的D2FA在处理某一个字符时可能会访问多个状态，但是可以证明，在处理一个长度为n的字符串时，其访问的状态数目不大于2以，2008年，Ficara等人在文献【18】中提出了另一种消除状态间由等价

37、项而形成的冗余的方法这种方法的思想源于D2FA，但是却没有使用缺省转换，而是为DFA增加了一个临时转换表(10cal set)他们观察到：在DFA中相邻的状态之间，一般会有大量的等价项例如，在图7中，状态2和状态l具有完全相同的转换表，而状态3仅与状态l在输入字符c时具有不同的跳转目标因此，如果每个状态仅仅存储与其相邻状态不同的表项，而其余表项直接从其父节点继承而来，则形成的DFA与原始DFA等价这种仅仅存储与其上级节点不同的项而形成的DFA也因此被称为6FA其构造过程为：首先申请一个新的二维转换表，然后从原始DFA的初始状态Jo开始，先将初始状态的转换项全部拷贝到新表中的对应行，再从这个状态

38、出发遍历DFA中所有状态，如果一个状态对应某个字符转换项与其任意一个父节点的相应项不同，则需要在新表的对应项中存储这一项，否则丢弃此项万方数据张树壮等：面向网络安全的正则表达式匹配技术 1845图7中DFA形成的6FA及其转换表如图9所示可以看出，除了状态1和原始DFA具有相同的转换表之外，其余状态都只存储了l项有效转换，并且不需要引入额外的缺省转换6FA将原始DFA的20项转换缩减到了8项在匹配时，6FA需要一个临时转换表，其初始值为6FA初始状态如的转换表，每次经过转换到达一个新状态时，首先根据新状态的转换表更新临时转换表的表项，然后再根据输入字符从临时转换表中找到目标状态因此，处理每个输

39、入字符只需访问1个状态图10给出了图9中6FA在处理字符串d6c时的过程，圆圈中表示状态及其转换表，下面的表为临时转换表在遍历到相应状态时的内容在初始状态1时，其内容与状态1的转换表完全一致；而通过字符口跳转到状态2时，它首先将对应于字符c的转换表项进行更新，然后通过6跳转向3此时，再次将对应c的表项更新成5，然后再继续执行6FA并不能完全避免冗余，例如，图中状态2和状态l对应于c的跳转目标依然相同这是因为对应于字母c的转换虽然与状态l相同，但是却与状态5不同，而在遍历中，状态1和状态5都可能成为状态2的前驱节点，因此状态2必须存储对应于字符c的转换，才能保证在各种情况下都与原始DFA等价它还

40、必须增加额外的操作来更新全局表项，如果一个状态存储的有效状态比较多，则更新操作将会降低匹配的效率Trnsition tableFig9 6FA of口+，I+c，cd+and its re(1ucedtransition table图9口+，6+c，c+办所形成的6FA及其缩减后的转换24消除不同状态间非等价项形成的冗余Local岫sition setFig10 A Iookup example of 6FA图10 6FA查找过程示例上面介绍的方法都是消减不同状态间等价项形成的冗余，这意味着只有两个状态的转换表项对应的转换字符和目标状态都相等时才能进行消减但还存在另一种形式的冗余：不同状态间非

41、等价项的冗余下面以图ll为例说明这种情况图11的左半部分给出了由正则表达式(a6一Pp州，Lg一)斛生成的DFA，右边给出了状态l状态4的索引表和转换表为了便于观察，图中省略了所有目标为状态为O的转换可以发现，虽然在实际的转换表中仍存在冗余，但这些表项却不都是等价项，因此不能使用上面的方法来消除例如，状态3和状态4中都有跳转向状态5的项，但却分别对应字符g-妇和，为了能够对这种冗余进行消除，2007年，Michela提出了状态合并(state merging)的方法【11】其基本思想是，如果两个状态具有目标相同的转换表项(无论是否对应于相同的字符)，则将两个状态合并起来，形成一个混合状态混合状

42、态拥有合并前原始状态的两个索引表以及一个合并后的转换表图12中给出了图11中DFA经过状态合后并得到的新的DFA及其对应的转换表如图所示，状态l和状态2合并之后形成了混合状态l 2，状态3和状态4合并之后形成了混合状态3 4在状态合并之后，还必须进行以下两个操作来保持新的DFA与原始DFA等价：(1)在对状态进行合时，将原来的两或多个转换表合并成了1个，所以某些目标表项的索引位置可能会发生变化例如，状态2的对应于字母2和|Il的项，在原来的索引表中为3，而合并后，其索引值变成了4因此，在合并转换表后必须对混合状态的索引表进行更新，使其指向的目标转换项与原来的项致(2)状态合并后，两个状态变成了

43、1个状态，原来目标指向这两个状态的转换也都更新为指向这个混合状态但是这会使得遍历到混合状态后无法决定选取哪个索引表来进行下一次跳转目标的选择，因此在状态合并后还需要对合并前的索引表进行标记以图12为例，状态3的索引表成了标记为3 4O。而状态3的索引表则标记为3 41，原来指向万方数据1846 面啪口，矿所坦理软件学报v0122，No8，Aug吣t 2011状态3的跳转目标项也相应地添加一个标记O，目标为4的项则增加一个标记1这样，原来跳转向状态3的项就可以根据标记O去状态3_4中的索引表3-40中去查找下一次跳转的目标为清晰起见，图12中的转换表没有给出这个标记，而是在DFA示意图中的转换上

44、标出Index table一d 6 C d P f g Jl躁l 3 3 3 3 2 O 0 0 ：_】2 l 0 0 0 0 2 3 3 O3 l O 0 O 0 2 3 3 3 O蠡譬，； l 0 0 O 0 2 O 0 0 3Transmon tablo感ol 2 3露弱o 1 2 4蹩冀j o l 2 5幽ol2 5F培11 DFA狮d its transition table and index table图11 DFA及其索引表Indext曲k口 6 C d e g I Jl 2O l 3 3 3 3 2 0 0 O O1 21 1 0 O 0 0 2 4 4 0 03 4O 1

45、0 0 O O 2 3 3 3 03 41 l 0 O O 0 2 O O O 3Mergl狙岫si60n table日墨出乎Fig12 DFA a船r state me玛ing髓d its merged transition table and index table图12状态合并后的DFA及其合并后的转换表和索引表状态合并与基于消除等价项的方法相比有两个优点：首先，它不需要被消减项是完全等价的，只要有相同的跳转目标就可以：其次，随着合并的进行，还可以创造出更多的合并机会，而消除等价项的方法是静态的其不足之处在于：首先，它需要和D2FA一样建立一个以DFA状态为顶点、顶点间公共转换数目为权值

46、的完全图，因此当DFA状态为n时，需要o(甩2)的额外空间其次；在原文的方法中，每个混合状态最多可以容纳的状态数目是需要人为指定的(用max肠6eb表示)，由于在每一次合并之后需要重新计算和合并后状态相关的权值，因此整个合并过程的时间复杂度高达(11max肠6Pb)以3log九)同时，由于max肠6Pb为人为指定，所以每个混合状态的转换表项数不相等，这会造成相应索引表项所用的bit位数也不相等在实现中，要么使用额外的标记进行记录从而付出额外的空间代价，要么选取统一的长度(最长bit位数)，这也会造成空间的浪费后一种浪费的本质是对索引表项的索引能力的浪费为此，文献【21】中提出了转换表共享方法以

47、改进状态合并方法转换表共享的基本思想是：对有相同转换项的多个状态不进行合并，而是让它们共享同一个转换表和状态合并一样，它首先将多个状态的转换表合并，形成一个大的公共转换表，然后对共享这一转换表的状态的索引表进行更新，以保持与原始DFA的等价性不同之处在于，它并不将这些状态合并成一个混合状态，而是保持状态的独立，因此不需要对转换和索引表进行额外的标记更重要的一点是，它并不直接指定ma)【肠6e括，而是指定索引表项的bit数目w，然后在共享的过程中使用启发式共享策略，逐个选择下一个状态，使得最后形成的公共转换表项恰好等于2”项，这能够使得索引表项的表达能力被充分利用考虑到DFA中相邻状态往往具有更

48、多的等价转换，转换表共享可以从DFA的初始状态开始，按照宽度优先的顺序进行试探，从而省去装换表合并时对以状态为顶点的权值图的搜索和更新过程万方数据张树壮等：面向网络安全的正则表达式匹配技术3基于自动机结构改进的内存缩减1847第2节所述的基于冗余消除的内存缩减技术可以大规模缩减D队所需要的内存空间，甚至可以缩减掉原始DFA所占用内存的90以上然而这类方法无法彻底解决DFA的空间占用问题：首先，DFA的内存是随状态数目的增长而增长，从第l节的分析可知，DFA的状态数目是平方级甚至指数级的增长，而无论怎样缩减，要想保持与原始DFA的等价性，都至少要保持其状态之间的连通性，这意味着最多将DFA的图形结构缩减成一棵以各个状态为顶点的树，而树的边与顶点是成线性关系的，因此冗余消除只是线性的缩减，无法解决状态的指数级增长带来的空间消耗；其次，基于冗余消除的缩减