0 引言

　　正则表达式使用标准的语法规则来描述模式，与精确字符串相比，正则表达式可以描述复杂的字符序列，并降低空间复杂度。强大的表达能力使正则表达式在网络安全领域广泛应用，成为描述规则的主要工具[1]，目前主流的入侵检测/防御系统(NIDS/NIPS)，例如Snort[2]、ClamAV[3]等已经将基于正则表达式的规则集成到其过滤系统中，且所占比重逐渐增大。

　　有限状态机（FA）和正则表达式所描述的语言都是正则语言，因此有限状态机是实现正则表达式匹配的主要方法。有限状态机通常分为两种：确定性有限状态机(DFA)和非确定性有限状态机(NFA)，通过对两种状态机深入而细致的研究和分析，Washington University的Kumar和Becchi等人提出了D2FA[4]、混合自动机(Hy brid-FA)[5]以及XFA[6]等方法来实现大规模正则表达式的实用化[7]。

　　XFA算法是比较高效的正则表达式匹配算法，算法使用辅助变量和简单的操作指令消除了由*、[ ]和{ }等重复匹配造成的DFA空间爆炸问题，降低了状态空间的存储需求。

　　为提高检测引擎的吞吐量，同时摆脱系统对引擎的约束以及引擎对系统的性能影响，使用专用器件实现入侵检测的包过滤过程成为目前的发展趋势。FPGA由于高速并行可在线编程等优点成为硬件检测引擎的实验开发和应用平台。

　　硬件实现XFA算法，若使用辅助变量和指令解决约束重复计数问题，则需要对存在约束重复的规则单独进行处理，消耗大量的硬件资源。本文针对这个情况设计专用计数器结构解决约束重复问题。

1 约束重复问题

　　1.1 问题的提出

　　传统处理约束重复问题的方法是将约束重复的内容展开，描述为精确匹配串的形式，在Snort规则集中存在约束重复数百上千次的规则，若使用展开的方法进行匹配将消耗大量的硬件资源，匹配效率低下。此外为现在4种类型的约束匹配，必须设计多种类型的匹配电路，例如要实现“abc{3,5}”的匹配，传统的方法将表达式展开为“abc{3}”，“abc{4}”和“abc{5}”，而后使用OR门连结三者对应的电路。因此在正则表达式匹配中设计高效的计数器实现约束匹配是非常必要的。

　　表1给出了4种约束重复Exactly，At Least，At Most和Between的规则表述及相关实例，其中Sub-RE表示约束重复的对象。

　　M.Faezipour and M.Nourani在文献[8]提出了一种针对NFA匹配算法的约束重复检测方案，算法使用Sub-Regex单元实现输入数据，使用Counter Reset单元实现约束重复匹配。Le Hoang Long等对文献[8]的方案进行改进，方案压缩了复位单元，同时给出了NFA编译方案，使通过编译过程直接避免了字符重叠所造成的失配情况[9]。

　　1.2 解决方案

　　为解决约束重复问题，同时达到最佳的匹配效率和资源利用率，提出了一种基于FPGA的重复约束检测方案。该方案与之前提出的基于IMB状态迁移方案相结合，约束重复模块仅需要考虑单字符计数功能。匹配整体架构如图1(a)所示，匹配模块通过并联RAM查找匹配结果，将匹配结果转换为Inc、Rst_inc等控制信号输入到计数模块中，同时根据匹配结果查询约束重复参数N、M和g值，并输入到计数模块中。计数模块根据控制信号进行计数操作，将得到的计数值与N、M进行比较，然后将比较输出通过一系列与或操作得到最终的匹配信号。

2 基于FPGA的约束重复检测匹配

　　2.1 匹配模块

　　将规则集编译为XFA后，需要将XFA的状态值和迁移边进行存储，我们提出了一种高效的迁移边存取方案，如图2。方案利用FPGA内部丰富的存储器资源，构造一个并联存储块，使用存储器并行查找的方法快速读取可能迁移边信息，通过匹配确定下一状态地址。

　　迁移边根据目的状态的不同分为两种，一种为精确转移，一种为缺省转移。为实现约束重复匹配，迁移边的定义如图3所示，精确转移迁移边规则最高位为约束重复标志位CR，当CR位为1则表示在对应匹配字符处存在约束重复；而后存储的是规则类型（Type），下一状态（Next state）和匹配字符（Matching char）。缺省转移迁移边由高位到低位分别存储转移边数目（Transition number）、下一状态（Next state）、匹配规则号（MatchID）/约束重复参数地址（CR_addr），当CR位为1时，MatchID/CR_addr中存储的是CR_addr。转移规则各个部分的空间大小由规则集对应的XFA大小决定。

　　约束重复参数存储在内部存储器中，每一个地址存储的数据包括标识信号g，数据存储格式标识符Flag，数据Data，如图4所示。标识符Flag用于区别数据的存储格式，当Flag=0时，表示约束重复中N=M类，即Exactly、At Most类。另外，为方便计算，我们将At Least 类也归为N=M类，此时Data域中存储的数据为M/N值。当Flag=1时表示约束重复中M>N类，即Between类，此时Data域分为data1、data2两部分，分别储存M值和N值。存储器大小的设置由存储规则决定，例如Snort规则集，N=M类约束重复M/N的最大取值Mmax=Nmax=1 286，取b=11 bit；M>N类M和N的最大取值分别为，取a=7 bit，b=16 bit。二者比较取大值则取b=16 bit，此时存储器大小为18 bit。

　　2.2 计数模块

　　计数模块由计数器、比较器、数据选择器以及与门或门组成。计数器根据输入的Inc、Rst_inc控制信号进行计数操作，Inc信号为约束重复标识，当匹配模块匹配的字符为约束重复Sub-RE的最后一个字符时，其输出信号Inc为高电平，当Inc为高电平时，每个时钟计数器计数值q进行一次加1操作；Rst_inc为局部复位信号，当匹配模块约束重复匹配成功或者失败时产生一次局部复位信号，计数值q的复位值为1。比较器将计数值q与数据信号M和N进行比较，当n≤q≤m时比较器输出为1。数据选择器根据控制信号g来控制在At Least约束重复情况下计数器的使能。

　　根据约束类型的不同，计数器参数取值如表2示所示。

　　之前的计数器对At Least约束类处理是将“(Sub-RE){n,}”分解为“(Sub-RE){n}(Sub-RE)*”。“(Sub-RE){n}”使用计数器exactly模式进行匹配，而“(Sub-RE)*”则通过匹配模式的状态迁移来实现，两者结合需要在匹配模块与计数器模块之间增加额外的控制信号，增大系统的资源开销。

　　经过分析，当计数器计数值q介于n和m之间时，除At Least情况，其它情况输入信号O均为高电平，此时g=0；而当q≥m时，At Least输出O为高电平，此时g=1。由此我们可以通过在输入时加入标识信号g来解决At Least类的计数问题。得到O的输出取值为：

　　2.2.1 约束重复重叠情况分析与处理

　　重叠的定义为：输入字符部分字符在同一RE的不同位置发生匹配。约束重复重叠情况通常出现在Exactly类和Between类中。例如子正则表达式为“a{3}cd”，匹配字符为“aaaaacd”，当匹配到第四个“a”时，匹配失败，此时计数器置位，重新匹配则字符串为“aacd”，输出结果为不匹配，出现漏检的情况。

　　根据约束重复重叠情况出现位置的不同，我们分3种情况进行处理。当出现在开始位置时，上述例子的漏检情况将会发生，此时仅需要将Exactly类和Between类改为At Least类即可；当出现在中间位置，例如子正则表达式为“9a{3}cd”，匹配字符为“9aaaacd”，两者显然不匹配，计数器在匹配三个“a”后置位将不会影响匹配结果；当出现在末尾时，此时Exactly类和Between类匹配效果与At Least类相同，不会造成漏检的情况。

　　2.2.2 计数器溢出处理

　　At Least约束重复当出现恶意攻击使重复匹配数超过计数器计数值q最大值时造成计数器的溢出，此时计数器的输出将发生错误。为避免计数器的溢出，我们设置计数值q的位宽qn≥?骔logMmax」，其中Mmax为约束重复M的最大值，在匹配时，当计数值q≥m时取q=m。此时O的输出取值为：

　　图1(b)所示是根据式(2)生成的约束重复结构图。

3 实验及性能分析

　　实验从Snort2.9.7.3中选择约束重复规则进行计数模块实验仿真，辅助存储器中存储的参数向量宽度为18 bit，其中a=7 bit，b=16 bit，标志位Flag和g各占1 bit。仿真在Quartus软件使用ALTERA DE2-70系列开发平台，通过综合得到计数器模块使用硬件资源为：23个LE，11个reg，模块工作最大时钟频率为373.83 MHz，而匹配模块最大时钟频率为281.9 MHz，完全可以满足匹配系统的计数操作。如图5所示是计数器对M=N类约束重复（图5(a)）和M>N类约束重复（图5(b)）使用ModelSim软件进行功能仿真得到的仿真波形图。

　　在Snort2.9.7.3[2] 13 529条包含正则表示式的规则中，8 036条规则包含约束重复匹配，占规则数的59.4%。表3给出了使用Snort规则集Oracle、Web-misc、Web-cgi进行实验分析的结果，从表中可以看出，使用计数器对约束重复问题进行处理，与传统的展开匹配方式相比，大大降低了存储器的消耗量，规则中约束重复所占比例越高，优化效果越明显。

4 结束语

　　本文我们针对XFA设计了一种高效的基于FPGA的约束重复检测匹配模块，模块与基于并联RAM的匹配模块相结合，通过约束重复参数储存器可以实现约束重复高效检测匹配。计数模块在实现约束重复检测匹配的同时避免了因At Least类在起始位置可能引起的失配情况。计数器模块的实现仅需要少量的基本逻辑单元LE和寄存器，工作频率可达到373.83 MHz，将Snort中部分规则集进行编译分析，该方案可以压缩50%以上的正则表达式规则存储空间，部分规则集的压缩比例可达99%。

　　参考文献

　　[1] 张树壮，罗浩，方滨兴，等.一种面向网络安全检测的高性能正则表达式匹配算法[J].计算机学报，2010，33(10)：1976-1986.

　　[2] Snort 2.9.7.3.2016.http：//www.snort.org.

　　[3] DIEN N K，HIEU T T，THINH T N.Memory-based multipattern signature scanning for clamAV antivirus[M].Future Data and Security Engineering.Springer International Publishing，2014：58-70.

　　[4] KUMAR S，DHARMAPURIKAR S，YU F，et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection[C].Proceedings of the 2006 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York：ACM Press，2006：339-350.　

　　[5] BECCHI M，ROWL C E P.A hybrid finite automaton for 　practical deep packet inspection.Proceedings of the ACM CoNEXT.New York，2007：1-12.

　　[6] 魏德志，洪联系，林丽娜，等.一种改进的XFA在深度包检测中的应用[J].Computer Engineering and Applications，2012，48(34).

　　[7] 张树壮，罗浩，方滨兴.面向网络安全的正则表达式匹配技术[J].软件学报，2011，22(8)：1838-1853.

　　[8] AEZIPOUR M，NOURANI M.Constraint repetition inspection for regular expression on FPGA[C].Proc.of the 2008 16th IEEE Symp.on High Performance Interconnects.Washington，2008.111-118.

　　[9] LONG H L，HIEU T T，TAI V T，et al.ECEB：enhanced constraint repetition block for regular expression matching on FPGA[J].ECTI Transactions on Electrical Engineering，Electronics，and Communications，2011，9：65-74.