正则表达式优化算法研究

摘要：当前对正则表达式匹配算法的研究大都集中与解决算法所占存储空间太大的问题。DFA算法XFA算法中普遍都存在反馈边过多的问题，对算法在存储方面的要求影响较大。该文提出了XFA算法的改进算法CXFA算法，解决了XFA算法中的反馈边问题，存储效率达到了XFA算法的18倍，D2FA算法的40倍。

关键词：反馈边；XFA；CXFA；存储效率

中图分类号：TP391文献标识码：A文章编号：1009-3044(2012) 05-1171-05

The Research on Pattern Matching Algorithm

CHEN Yan-ting, LU Hong-sheng

(Jiangnan Institute of Computing Technology, Wuxi 214128, China)

Abstract: The regular expression matching algorithm research is focused and solution algorithm for the problem of too much storage space. DFA algorithm XFA algorithm generally feedback transition too many problems in the storage requirements of influence. This paper pres? ents an improved XFA algorithm, CXFA algorithm, XFA algorithm is solved in the feedback boundary problem, storage efficiency reaches 18 times of XFA algorithm, DDFA algorithm 40 times.

Key words: feedback transition; XFA; CXFA; storage efficiency

随着互联网技术的高速发展，传统的正则表达式匹配算法己无法满足其性能要求。NFA算法的存储高效，但是匹配效率低下。DFA的匹配速度快，但是存在存储状态空间爆炸的问题，使得DFA的存储空间需求难以忍受。由于DFA具有高效的匹配效率，目前的研究重点主要围绕DFA而展开，即在保证DFA匹配效率不下降太多情况下，减少DFA的存储空间需求从而降低硬件实现难度，实现正则表达式匹配的优化。

1反馈边问题

DFA算法和XFA算法中都存在反馈边过多的问题，极大的影响了算法对存储空间的需求，下面本文将给出自动机中转移边的分类方法以及其中反馈边问题的定义和描述。

1.1反馈边的定义

图1所表示的是正则表达式{abcad}采用AC（Aho-Corasick）算法构造出的DFA，图中包括6个状态，15条转移边。根据转换目标的不同可以将这15条边分为4类：匹配失败边，重启边，反馈边，基本边。

失败边：图1中所有浅色边表示的转换称为失败边，失败边是指从某一个状态S转移到起始状态S0所经过的的转移边，表示当前输入的字符不在正则表达式{abcad}所描述的字符集范围内，匹配失败，重新开始对下一个字符进行匹配。

重启边：图1中所有虚线边表示的转换称为重启边，重启边是指从当前状态S转移到状态S1所经过的转移边，表示当前输入的字符为正则表达式{abcad}中的第一个字符，状态机跳到状态S1继续进行匹配。

反馈边：图1中加粗的边表示的转换称为反馈边，反馈边是指从当前状态S转换到状态S2的转移边，表示当前输入的字符与前一个输入的字符刚好匹配正则表达式{abcad}中的前两个字符，状态跳转到状态S2继续进行匹配。

基本边：图1中从状态S0一直连接到接收状态S5的一系列成功匹配的转移边称为基本边，它是所有成功匹配的输入必须要经过的边。

观察正则表达式{abcad}可以发现，该正则表达式中出现了2次字符a，而且其中一次出现在整个正则表达式的起始位置。在这种情况下，根据AC算法构造出的DFA就会产生一条反馈边，这条反馈边负责完成匹配输入为abcab*的功能。当输入字符a时，状态机跳转到状态S1，接着输入bca，状态机跳转到状态S4，当继续输入字符b的时候不能跳转到匹配失败时的状态S0，因为字符b的前一个输入字符为a，ab满足了反馈边的要求，所以应该指向第3个状态，状态S2。这样构造出的DFA才能够匹配类似与abcabcad这样的字符输入，符合正则表达式{abcad}描述的正确语义。

1.2 XFA中的反馈边

正则表达式{.*ab.*cd}与{.*df.*gh}合并后的XFA如图2所示，按照XFA构造算法的要求，首先第一步将两个正则表达式中带有.* 结构的部分拆分，于是{.*ab.*cd}与{.*df.*gh}被拆分成{.*ab}、{.*cd}、{.*df }、{.*gh}四个表达式，然后转化成对应的DFA之后，状态S2添加一条指令信息：Bit1=true来表示{.*ab}被部分匹配的情况，与此同时状态S4添加一条指令信息：if (Bit1==true)Accept(regex1)来判断是否完成正则表达式{.*ab.*cd}的匹配。同样，在状态S6以及结束状态S8都添加了类似的指令信息，以达到消除DFA里面中间状态，避免出现状态爆炸的目的。

图1转移边的分类

图2 XFA中的反馈边

从图2中我们可以看到，存在一条从状态S4到状态S6的反馈边L4-6，产生这条反馈边的原因和多个DFA融合所产生的反馈边相同，都是因为在两个正则表达式中，存在某个公共字符位于其中的某一个表达式的首部。当出现公共字符的情况时，XFA中也必然会出现雷同的现象，在某些状态之间新增了一些反馈边。图3描述的是正则表达式{.*abcd.*cefg}与{.*dcge.*gkda}合并以后的XFA，从图中可以很明显的看到正则表达式之间的公共字符所引起的反馈边数量随着正则表达式长度的增加而明显增多，图3中所描述的XFA拥有状态数17个，基本边16条，1级反馈边7条，约占了所有边总数的1/3，根据图3中反馈边所占比例的分布情况可以预计随着正则表达式条数的增多和正则表达式长度的增长，反馈边的条数所占比例将会大大超过基本边的所占的比例。

图3 XFA中的多条反馈边

2 CXFA算法

2.1算法动机

动机一：反馈边问题不仅仅在DFA融合中存在，而且在高度压缩的XFA中也存在，甚至比DFA更加严重；动机二：所有的反馈边所指向的状态都存在一条接收相同字符的边存在；

动机三：一级反馈边所占比例最大，消除一级反馈边可以极大的压缩存储空间；

动机四：一级反馈边的公共字符在第一级处理，消除一级反馈边相对于消除多级反馈边来讲实现代价最低。

2.2形式化定义

传统的XFA进行匹配的基本模式如图4所示，Rule selector根据当前状态寄存器的值到转移边存储器中，通过查找的方法得到当前输入字符对应的下一状态，反馈回去，更新状态寄存器的值。与此同时，另外一边当前状态的值输入给变量存储器，通过查询和更新变量寄存器，完成XFA中指令信息的更新和查询功能。然后根据查询的结果输出XFA在当前输入字符下的匹配情况。

传统的XFA结构中并没有考虑到自动机状态之间的转移边的处理问题，基于算法动机二“反馈边所指向的状态都存在另外一条接收相同字符的基本边存在”的思想，我们可以试图通过利用这条接收相同字符的基本边来代替反馈边，从而达到消除一级反馈 边，压缩自动机存储空间的目的。

图4 XFA自动机结构

这里我们提出一种CACHE-XFA自动机（简称CXFA）来达到消除失败边、重启边和1级反馈边，压缩存储空间的目的。在XFA自动机的基础上，增加一个独立的CACHE状态寄存器，由当前状态寄存器和CACHE状态寄存器共同配合完成XFA自动机状态切换，CXFA的详细结构如图5所示。

图5 CXFA自动机结构

传统的XFA下一个状态的生成只与当前状态和输入字符相关，CXFA中下一状态的生成不仅与当前状态和当前输入字符相关，同时CACHE状态也对下一状态的生成产生影响。CXFA利用一个CACHE寄存器存储备用状态，输入字符在当前状态没有下一个状态的情况下，启用CACHE寄存器中存储的备用状态来接收当前字符，达到压缩自动机中冗余转移边的目的。CXFA的形式化定义如下：

定义基于状态的CXFA是一个九元组（Q，Σ，D，C，δ，θ，U，(q0，d0)，F），其中：

（1）Q是一个有穷的状态集合。

（2）Σ是一个有穷的输入符号集合，一般称为字母表Σ。

（3）D是一个有穷的变量值的集合。

（4）C是一个CACHE状态集合，C是Q的一个子集。

（5）迁移函数δ是一个以Q中一个状态、C中的一个状态和Σ中一个输入字母为变量并返回Q中状态的函数。

（6）CACHE生成函数θ是一个以起始状态q0和Σ中一个输入字母为变量并返回C中状态的函数。

（7）变量更新函数U是一个对每个状态以Q中一个状态和D中一个变量值为变量并返回D中变量的函数。

（8）(q0，d0，c0)是初始配置，初始配置包含初始状态q0，变量的初始值d0，cache的初始值c0。

（9）接受配置F是Q和D的子集，集合的每个元素包含接受状态和变量的值。

2.3 CXFA中的Cache策略

在预处理阶段，删除从正则表达式集合生成出的CXFA中的失败边、重启边和1级反馈边，转移边集合中只包括基本边和n级反馈边。在字符匹配的阶段，CXFA通过状态转移函数和Cache状态生成函数来完成自动机的状态切换。

CXFA采用了3个输入状态的查表机制，在只存有基本边和n级反馈边的转移边存储器内查找Cache_State、Cur_State、S0所对应的INPUT字符的下一个状态，得到3个不同优先级的next状态S0_next、Cur_next、Cache_next。其中Cur_next优先级最高，Cache_next其次，S0_next优先级最低，通过一个优先级仲裁器输出最终的下一个状态返回给Cur_State寄存器完成一轮自动机状态切换。每一轮的转换过后将S0_next的输出返回给Cache_State寄存器，完成Cache更新操作。

图6 CXFA中的Cache策略

如图7所示的CXFA是图3中的XFA经过删除失败边、重启边、1级反馈边以后得到的自动机。

对于正则表达式{.*abcd.*cefg}与{.*dcge.*gkda}对应的CXFA，输入字符流{ abcgkdcgegkda }的状态转换过程如表1所示。表中第 一列代表当前的输入字符，第二列代表当前状态，第三列代表CACHE状态，第4，5，6列分别代表生成Next_state的三个仲裁项Cache_state、Cur_next和Cache_next，最后两列代表CXFA中的两个变量的值。首先初始化Cur_state为S0，Cache_state为NULL，在收到第一个字符a的时候经过查找运算得到Cur_next为S1，Cache_next为NULL，S0_next为S1。Next_state取优先级最高的Cur_next，更新第二行的Cur_state为S1，同时更新Cache_state为第一行的S0_next：S1。依此类推，当状态上出现变量更新操作时，更新右边两栏对应的变量值。第13行，Cur_state为S15，Cache_next为S9时，当前输入的字符为a，根据查表运算得到Cur_next为S16，Cache_next为NULL，S0_next为S1，更新下一行。当前Cur_state为S16，Next_state为NULL，同时检查变量Bit2，看到Bit2等于1，输出匹配成功标志accept，完成CXFA匹配。从这里可以看出CXFA算法和XFA算法在功能上是等价的。

图7正则表达式{.*abcd.*cefg}与{.*dcge.*gkda}对应的CXFA

表1 CXFA匹配算法执行流程示意表

通过分析字符流{abcgkdcgegkda}的CXFA处理过程可以看出，在删除了失败边、重启边以及1级反馈边的基础上，CXFA在增添了1个Cache状态寄存器和一个优先级仲裁机制之后。通过对S0_next、Cur_next、Cache_next进行仲裁产生了正确的下一状态，能够顺利的完成状态更新，指令执行，变量赋值等XFA基本操作，成功的完成正则表达式匹配的任务，达到了压缩状态转移表，进一步缩小XFA存储空间的目的。

3算法性能测试

本节将对CXFA算法在SNORT规则集上面的性能进行全面的测试，并对CXFA算法在SNORT规则的适用性进行评估。

本节的适用性测试选取了SNORT规则集中最具有代表性的六种应用层协议规则集作为基准测试集，它们分别是FTP.rules、SMTP.rules、POP3.rules、IMAP.rules、VoIP.rules和Web-IIS.rules。

图8 CXFA算法相对于D2FA、XFA的压缩比

SMTP.rules、POP3.rules、IMAP.rules、VoIP.rules和Web-IIS.rules规则集中CXFA算法相对于D2FA算法和XFA算法的存储规模比如图8所示。从图中线条的走势可以看出CXFA算法具有非常高的压缩率，同时CXFA算法相对于两种算法的压缩比与规则集的大小成正比。SMTP.rules规则集的总长度为2746，CXFA算法无论是相对于D2FA还是XFA都拥有超过30倍的压缩比；相反在规则集规模较小的POP3和IIS中，CXFA算法相对于D2FA的压缩比仅为16.7倍和2.7倍。在POP3和IIS规则集中，D2FA算法的存储压缩 效果优于XFA算法。出现这样的情况的原因是由于，在规则集规模减小的情况下，转移边数目对存储的需求大于状态爆炸所引起的存储需求，此时XFA算法压缩效果比较一般。CXFA算法的提出避免了以上情况的发生，在规则集规模较小的情况下，CXFA仍然能够保证非常高的压缩性能。

CXFA算法在XFA算法致力于消除中间状态的基础上，消除了原本自动机中的失败边、重启边、1级反馈边，极大的压缩了边存储空间。在SNORT规则适用性的测试结果表明CXFA算法的存储性能平均是D2FA算法存储性能的40倍，是XFA算法的18倍。

4总结

本文详细阐述了正则表达式匹配算法中存在的反馈边问题，巧妙的采用cache策略解决了反馈边过多对算法存储规模的影响的问题。并对CXFA算法在SNORT规则集上的适用性进行了全面的测试，结果表明CXFA算法才存储效率方面平均是XFA算法的18倍，D2FA算法的40倍。

参考文献：

[1] Sidhu R,Prasanna V.Fast Regular Expression Matehing using FPGAs[J].In Proeeedings of IEEE SymPosiuxn on Field-Programmable Cus? tom ComPuting Machines (FCCM’01),2001(4):227-238.

[2] Mitra A,Najjar W,Bhuyan piling PCRE to FPGA for aceelerating SNORT IDS[J].In Proeeedings of the 3rd ACM/IEEE Symposium on Achiteeture for networking and communication systems, Deeember,2007.

[3] Bispo J C,Sourdis I,Cardoso J M.Vassiliadis S.Regular expression matehing for reconfigurable Packet inspection[J].In IEEE International Conference on Field Programmable Technology(FPT’06), Dee.2006:119-126.

[4] Cho Y H,Mangione-Smith W H.A partemmatching coproeessor for network seeurity[C].In Proceedings of the 42nd Alinual Conf.onDesign Automation(DAC’05),Jun.2005:234-239.

[5] Paolieri M,Bonesan I,Santambrogio M D.ReCPU:a Parallel and Pipelined Architecture for Regular Expression Matehing[C].In Proc.IF? IP-VLSI,Oct.2007.

[6] Clark C R,Schimel D E.Design of Efficient FPGA Circuits for Matching Complex Patterns in Network Intrusion Detection Systems[C].In Proceedings of the 13th International Conference on Field Programmable Logic and Applications, June 2003.

[7] C.H.Lin, C.T.Huang, C.P.Jiang, S.C.Chang.Optimization of regular expression pattern matching circuits on FPGA. In proceedings of the conference on Design, automation and test in Europe(DATE’06),Mar.2006:12-17.

[8] Sourdis I,Pnevmatikatos D.Pre-decoded CAMs for Efficient and High Speed NIDS Pattern Matching[J].In Proceedings of the 12th Annual IEEE SymPosium on Field-Programmable Custom Computing Machines(FCCM’04),APr.2004:258-267.

[9] LEVANDOSKIJ,SOMMERE,STRAITM.Applieation layer Paeket classifier for Linux[EB/OL].[2009-07-07]..

[11] Brodie B C,Cytron R K,Taylor D E.A Scalable Architecture for High-Throughput Regular-Expression Pattern Matching[C].In 33rd Inter? national Symposium on Computer Architecture,ISCA,2006.

[12] F.Yu,Z.Chen,Y.Diao,et al.Fast and memory-efficient regular expression matching for deep packet inspection[C].In: Proc of ACM/IEEE ANCS.San Jose,Calif ornia,2006:93-12.

[13] Kumar S,Turner J,Williams J.Advanced algorithms for gast and scalable deep packet inspection[C].In:Proc of ANCS. San Jose,California, USA:2006,81-92.