0 引言

随着海量信息处理和大数据处理等技术的发展，网络应用对海量信息下匹配引擎的性能提出了更高的要求^[1]。深度包过滤(Deep Packet Inspection,DPI)技术作为网络过滤系统的核心，采用特征匹配算法将数据包中的数据与预定义的恶意数据特征码进行匹配，从而滤除恶意数据包。由木桶原理可知，网络安全应用中，模式匹配在最差情况下的性能决定了系统在线工作性能。为此，提高模式匹配在最差情况下的性能是入侵检测系统的关键问题^[2]。

模式匹配广泛应用于信息检索、模式识别、入侵检测、内容过滤、病毒代码检测、基因匹配等众多领域^[3]。模式匹配根据模式串的描述方式可分为字符串匹配和正则表达式匹配。随着网络的不断发展，恶意数据特征码长度、数目和种类增长迅速，正则表达式描述方式以其较强的表达能力逐步应用成为主流网络安全系统，例如Snort^[4]、Clam AV^[5]等数据库的主要描述形式。表 1给出了不同版本的Snort规则数目以及Pcre规则所占比例^[4]。正则表达式匹配算法是本文研究的主要内容。

正则表达式匹配通常采用确定性有限状态机(Deterministic Finite Automaton,DFA)。DFA处理每个字符仅需要访问一个状态，避免了回溯问题，匹配速度快，但是DFA编译速度慢、空间消耗大等问题，限制了其在基于硬件的正则表达式匹配系统中的发展和应用。

针对DFA存储空间需求大的问题，近几年，研究者提出了多种DFA的改进算法。Smith等^[6]提出一种采用辅助变量代替额外状态的DFA改进算法——扩展有限自动机(Extended Finite Automaton,XFA)匹配算法，其通过简单的指令操作来检测是否匹配成功，能消除DFA状态空间爆炸问题，与DFA相比，XFA的状态空间数减少了4个数量级，匹配时间与DFA接近。黄昆等^[7]在XFA算法的基础上利用优先级压缩和位图存储的方法提出了压缩有限自动机(Compact Finite Automaton,CFA)算法，在迁移边压缩方面取得了不错的效果；但是算法规则匹配使用二次查找，当网络中出现分布式拒绝服务(Distributed Denial of Service,DDoS)攻击时容易出现丢包、漏包的情况。张大方等^[8]提出的智能有限自动机(Smart Finite Automaton，SFA)算法有效解决了XFA算法冗余迁移边的问题，通过增加辅助判断指令避免了状态机重复匹配的情况。IBM苏黎世实验室提出了一种基于紧凑型DFA和XFA的正则表达式匹配引擎，该引擎适用于少量规则的匹配操作，当规则数为600时，吞吐率可达到45 Gb/s，随着规则数目的增多，引擎的吞吐率呈指数下降^[9]。以上基于XFA的改进算法对包含克林闭合组“.*”“[]”以及“{}”等元字符的正则表达式优化效果明显，但是针对\d / [0-9](匹配数字)、[a-z](匹配小写字母)、[bB](不区分大小写)等类字符匹配，XFA并不能对迁移边进行有效压缩。本文结合XFA提出了一种基于预定义类的紧凑型自动机(Pre-Class CFA)匹配算法。

1 扩展有限自动机概述

DFA状态爆炸的根本原因是当多个DFA组合成一个DFA时，单个DFA的歧义路径和非歧义路径相互组合，导致组合DFA产生大量的额外状态，使消耗的空间量呈指数级增长^[8]。DFA的定义如下：D={Q,Σ,δ,q₀,F}。其中:Q为状态集，Σ为字母表，δ为迁移函数，q₀为初始状态，F为接受状态集。例如正则表达式集{.*ab.*cd,.*ef.*gh}，其联合DFA结构图如图 1(a)所示，图中省略了其他状态到初始状态的失败转移。从图 1可以看出，由于单个DFA中存在通配符“.*”，使得当两个DFA的状态进行交叉组合时，状态机中状态数目呈指数级增长，造成组合DFA空间爆炸^[10]。

为消除组合DFA状态空间爆炸的问题，Smith等^[6]提出了XFA解决方案，使用辅助变量代替额外状态来记录部分匹配的结果。XFA匹配时，当读入一个字符，XFA检查当前状态对应迁移边迁移的下一状态，在执行下一状态指令时检测辅助变量，从而判断是否匹配成功^[8]。XFA定义如下：X={Q,V,Σ,δ,U,(q₀,v₀),F}。其中：V表示辅助变量集，U表示每个状态的更新函数，v₀表示辅助变量的初始值，其余参数与DFA相同。图 1(b)给出了使用XFA匹配{.*ab.*cd,.*ef.*gh}的状态图，在组合XFA状态PV上添加bit1和bit2的赋值操作指令，在状态SV、PY上分别增加bit1和bit2的判断指令，在整个组合XFA中共需要7个状态和2个辅助变量，相比DFA中的15个状态减小了50%。辅助变量的引入使XFA解决了DFA状态空间爆炸问题。

2 基于预定义类的紧凑型自动机

从图 1(b)可以看到紧凑型自动机可以有效地解决由克林闭合组“.*”所带来的状态爆炸问题，同时利用辅助变量也可以避免由“[]”“{}”等多次重复匹配元字符所带来的状态爆炸，但是对于规则集中常见的不区分大小写、特殊字符类匹配等元字符匹配所造成的空间复杂度的增加，XFA算法未给出有效的解决方案。本文结合XFA使用的指令方法，提出了可以匹配字符类的Pre-Class CFA正则表达式匹配算法。

2.1 基于预定义类的迁移边压缩方法

Pre-Class CFA支持多种形式的状态迁移，不仅包括XFA中的精确匹配，还支持不区分大小写、类匹配和缺省转移等特殊迁移。

类匹配^[11]可以实现字符类，例如数字([0-9]或\d)、字母([a-z]以及[A-Z])、字类字符([A-Za-z0-9]或\w)以及对应的否定形式等全部或者部分字符的匹配。通过定义类可以实现多条相同初始状态和目的状态迁移边的归一化，减少迁移边的数目，降低算法的空间和时间复杂度。在算法设计中将不区分大小写也归到类匹配进行处理。

例如规则“a[bB][^c][0-8]*9[a-z]”，其DFA状态转移图如图 2所示，规则中出现了不区分大小写匹配[bB]、数字类匹配[0-8]和小写字母匹配[a-z]，若按照传统自动机匹配则以上三个状态转移需要消耗37个存储空间。通过分析ASCII码的特点，不区分大小写、数字、字母等类字符可以通过特殊的匹配规则使用一条转移规则进行处理。例如不区分大小写[bB]，由于在ASCII码中大小写字母ASCII码值相差32，用二进制表示为8′b00100000，则设置匹配规则为Char⊕8′b01×00010。

但是对于上述规则中出现的“0-8”，与数字匹配“\d”相比缺少字符“9”，若使用精确匹配则需要9个转移状态。为解决类似于 “[0-8]”的状态转移问题，采用优先级的方法，如表 2所示，取类匹配“\d”代替“[0-8]”，同时添加精确匹配字符“9”使其匹配优先级高于“\d”的优先级，以避免重新定义字符类，降低自动机构造的计算复杂度，减少迁移边数目。若规则中出现“[0-7]”匹配时，使用上述优先级的匹配方法则需要三条迁移边；但是根据“0-7”ASCII码的特点，可以直接将“[0-7]”定义为一个类，则匹配仅需要一条迁移边。

下面给出了基于预定义类迁移边压缩方法伪代码，S为XFA状态集，δ为转移函数，T_c为迁移边集合，其中初始的T_c为XFA的迁移边集合，最终输出的是压缩后的迁移边集合。算法通过遍历每一个状态来判断该状态的迁移边中是否存在可以压缩的迁移边，若存在，则判断可压缩迁移边的类型，对于未定义的压缩类型，称之为新类型。由于过多的类匹配类型将增加规则类型标识符的位宽，从而增加消耗的存储器资源，因此最终需要对定义的类类型进行筛选，选择最优的类定义。

  Pre-Class CFA(S,δ,Σ)

  Tran_Set T_c=∅;

  num=0;

  array[128];

  For(each state S_i in S) do

   For(each state S_iin S) do

    For(char from 8′h00 to 8′h7f)

     If(Tran t_k=S_j→δ(S_i,char))

      array[char]=1;

     num++;

    Endfor

    If(num=2)

    If(array中两个存储为1的空间地址相差32)

     type=不区分大小；

    If(num=10)

      T_c=T_c∪t_数字;

    T_c=T_c∩t_0～9;

    

    If(num=9)

     If(array中地址为8′h30-8′h38为1)

     T_c=T_c∪t_0-8;

     T_c=T_c∩t_0～9;

     T_c=T_c∪t₉;

     t_9.priority=1;

   Endfor

  array[]=0;

 Endfor

2.2 基于并联存储块的迁移边存储与查找

为提高算法的资源利用率，在构造Pre-Class CFA时使用多条规则构成一个自动机，则在进行匹配时需要查找对应状态的所有迁移边。状态转移边的查找方法可以分为两类：

1) 使用状态值和输入值通过哈希函数产生指针进行查找；

2) 使用内容地址存储器(Content Addressable Memory,CAM)进行查找。

指针方法查找速度快，但是哈希碰撞问题会严重影响查找精度，尤其当规则数目比较大时，哈希碰撞问题更加突出。内容地址存储器可以对CAM中的数据进行快速并行查找，但是CAM作为外部存储器，与片内存储器相比执行频率和延迟都存在一定的差距。本文利用文献[12]提出的可变内容寻址存储器(modified Content Addressable Memory,mCAM)的设计思想，构造设计了适合Pre-Class CFA算法的迁移边查找方案——并联存储块(Interleaved Memory Banks,IMB)迁移边查找方法。

2.2.1 迁移边分类与规则定义

对状态机的存储首先要对迁移边进行处理，根据迁移边的特点，将迁移边分为两类，如图 3所示。一类是精确转移(Exact transition)，其存储内容包括规则类型(Type)、下一状态(Next state)和输入字符(Input char)。规则类型指迁移边的类型，根据迁移边定义类型的多少对其进行编码。另一类是缺省转移(Default transition)，即状态机中的失败转移，缺省转移规则包含当前状态的迁移边数目(Transition number)、失败迁移状态(Next state)和匹配规则号(MatchID)。Tra.num存储该状态中精确转移的数目，标识匹配起始位置到结束位置的偏移量，MatchID表示该状态匹配的规则号。

2.2.2 基于IMB的迁移边查找方法

为实现规则的高速匹配，需要在一个时钟内对某状态的所有迁移边进行分析。当前的现场可编程门阵列(Field-Programmable Gate Array,FPGA)产品内部嵌有数百个片内存储块，使用这些存储块可以构造一个并联存储块，不仅能提高查找效率，也能够充分利用FPGA的存储带宽。

如果存储块数目n大于或者等于自动机中所有状态的最大迁移边数目N_max，则所有的迁移边可以在一个时钟内实现并行处理；若n＜N_max，则查找迁移边需要N_max/n个时钟周期^[13]。就目前使用的FPGA而言，片上存储块数目均大于或者等于256^[13]，可以确保在一个时钟内对状态中的所有迁移边进行匹配。任意一个存储块都可以作为状态迁移边存储的起始位置，起始位置存储缺省迁移边。图 4给出了规则“a[bB][^c][0-8]*9[a-z]”的迁移边存储结构。

图 5给出了由存储器构成的匹配引擎结构。引擎包括地址产生器、IMB、字符匹配器和状态选择器。迁移边按照定义的规则存储在IMB中，每个存储块都包含一个地址产生器，地址产生器根据当前状态值产生对应块匹配起始地址，读取存储的规则后，字符匹配器将与精确匹配中的字符进行匹配，当遇到类匹配时，根据类匹配的类型，选择合适的匹配算法。匹配结束后的结果输入到状态选择器中，状态选择器根据迁移边的优先级决定下一状态值。

下面给出的是基于硬件设计的Pre-Class CFA算法顶层模块Verilog伪代码。第1) 行给出了顶层模块端口信号，其中包括三个输入信号：clk、rst、char和一个输出信号：match_ID，clk和rst作为全局的时钟和复位信号驱动整个模块的运作，char是输入的检测字符，match_ID为匹配得到的特征码ID。第2) ～5) 行为顶层模块调用的子模块，Mult模块是一个数据选择器，在每个时钟确定该时钟的状态指针，若复位则输出初始状态指针，否则输出Comparator输出的指针；Read 模块的作用是通过Mult模块输出的状态指针读取IMB中的迁移边；Sort 模块的作用是将Read 模块读取的迁移边根据状态指针信号将迁移边进行分类及优先级排序；Comparator模块是将迁移边与输入字符进行匹配，匹配时根据迁移边中规则类型标识符，选择对应的匹配电路进行匹配，这其中包括定义的类匹配。

  1)  module Pre-Class CFA(clk,rst,char,match_ID)

  2)  Mult (clk,rst,index,index_next,addr,bank);

  3)  Read (clk,rst,index,addr,bank,char,char1,data0,data1,data2,data3) ;

  4)  Sort (clk,rst,bank,data0,data1,data2,data3,index,char1,char2,exact_data0,exact_data1,exact_data2,bank_num,d_next_state,ID);

  5)  Comparator(clk,rst,bank_num,char,ID,exact_data0,exact_data1,exact_data2,d_next_state,next_state,match_ID);

  6)  endmodule

2.3 辅助变量存储器设计

辅助变量存储器给每一个拥有克林闭合组的规则设置一个地址，存储空间大小等于所有规则中克林闭合组的最大值K_max。在进行ID设置时，确定一个规则阈值Thr，将存在克林闭合组规则的ID值设置在阈值以下，使用ID值中大于阈值的高位存储比较指令值；同时将MatchID的最高位设置为标志位，用来区别规则中是否存在克林闭合组，当最高位为“1”时表示存在，反之不存在。例如设规则数为100，存在克林闭合组的规则数为15，其中K_max=4，则取MatchID为8 bit，阈值Thr=16，设置辅助变量储存器地址空间为4 bit。若规则中仅含有一个，则在存储器中存储“1110”，存在两个则存储“1101”，存在三个则存储“1100”，以此类推。当输入规则ID时，若计数器值为0，则计数器读取规则对应存储器中的数值并加1，同时寄存ID；反之，则检测输入的ID与寄存器输出的ID是否相同，相同则计数器直接加1，不同则计数器读取新规则数据并加1。每次输入都要更新寄存器中的ID值。计数器每计数结束需判断计数值是否为“1111”，若是，则匹配成功，计数器置零，寄存器复位。

3 算法性能分析与实验评估 3.1 算法性能分析

通过分析Pre-Class CFA与XFA的定义PC={Q,V,Σ′,δ′,U,(q₀,v₀),F}和X={Q,V,Σ,δ,U,(q₀,v₀),F}，当初始状态相同时，输入相同的字符二者具有相同的目的状态，可证明Pre-Class CFA与XFA等价。

由于正则表达式的复杂性和多样性，以下通过分析最坏情况迁移边数目来比较Pre-Class CFA与XFA的性能。设自动机中状态总数为N_s，字母表Σ中有m个字母，则XFA迁移边总数X_t=N_s×(m+1) , Pre-Class CFA迁移边总数PC_t=(N_s+c)-(c×Ratio),其中：c表示各个状态非失败转移的迁移边数目之和，Ratio表示各类类匹配在正则表达式迁移边中所占的比例。二者相比，迁移边减少数目为：

$R\text{X/PC}=\frac{N\text{s}\times \left( m+1 \right)}{\left( N\text{s}+c \right)-\left( c\times Ratio \right)}$

在自动机中，非失败转移的迁移边数目之和c为：

c=N_s*N； N≥1,N∈Z⁺

则

R_X/PC=(m+1) /

通过对Snort2.9.8 .0 中的正则表达式规则进行统计分析，发现其中33%的规则进行匹配时不区分大小写，包含字母、数字以及否定形式等其他类匹配的正则表达式规则占规则总数约42%，根据文献[14]统计分析，Snort规则的平均长度为207，则Ratio≈6.8%。在理想情况下，当m=256，N=3时，与XFA相比，Pre-Class CFA在迁移边数目上减少了67.6%。

3.2 实验评估

实验使用ALTERA低成本Cyclone Ⅱ系列的开发平台，平台搭载EP2C70F896C6 FPGA芯片，选择Snort规则库规则集进行仿真实验分析，将规则文件编译为Pre-Class CFA，并将其迁移边存储在IMB中。根据文献[14]给出的实验结果，并联只读存储器(Read-Only Memory,ROM)进行并行流水线操作时，由于多路选择器在数据读取时存在延迟，因而并非并联块数越多数据的处理效率越高。在使用流水线的方式设计Pre-Class CFA时，使用的资源全部是寄存器和查找表等非逻辑资源。表 3给出了使用不同数量并联ROM进行流水线操作时Pre-Class CFA使用的 LTU(Look Up Table)、 REG(REGister)数目以及自动机的最大工作频率。从表中可以看出，自动机消耗的FPGA资源很小，消耗量小于器件资源总量的1%；对比表中流水线结构和非流水线结构自动机的最大频率可以看出，通过在系统中增加流水线级数可以提高系统频率，且采用2级流水线的4-ROM结构自动机的工作频率达到最大值，由于受实验器件性能的约束，系统有最大工作频率为162.06 MHz，系统最大吞吐量可达到1.3 Gb/s。

本文从Snort规则库中选择FTP、exploit、SMTP、Web-client和Web-misc五个规则集对算法进行分析评估，如表 4所示给出了使用XFA、CFA和本文算法编码上述规则集所需的迁移边数目。

从表 4中可以看出,本文算法与XFA算法相比迁移边数目减少了70.21%～90.37%，与CFA算法相比迁移边数目减少了15.41%～33.05%，其中正则表达式中类匹配出现频率越高，迁移边压缩效果越明显。同时本文提出的基于IMB的迁移边查找方法针对FPGA存储器结构设计，充分利用了器件的片内存储器资源，与CFA算法片内片外分步查找方法相比，查询性能有较大的提升，性能提升程度与器件性能相关，在本文使用的FPGA器件中，若使用同步静态随机存取存储器(Synchronous Static Random Access Memory,SSRAM)作为片外存储器，则查询性能提高了56.62%。

4 结语

本文提出了一种基于XFA的改进正则表达式匹配算法——Pre-Class CFA算法。算法通过预定义类，减少了正则表达式中字符类匹配时迁移边条数。在Pre-Class CFA数据存储中，本文基于并联ROM结构设计了适合该算法迁移边特征的IMB迁移边存储结构，通过对迁移边进行编码，将数据全部存储在片内存储器中，大大提高了数据读取速度，从而确保了算法的匹配效率。实验结果表明，Pre-Class CFA在大大压缩迁移边的同时可以在频率上限为260 MHz的中低性能FPGA系统中实现大规模正则表达式的高速匹配，系统吞吐量可达到1.3 Gb/s，可满足千兆网络下的数据检测。

虽然本文算法在迁移边压缩和匹配效率上取得了较好的效果，但是该算法通过软件编程实现的规则预处理过程步骤多、处理过程复杂，尤其是对于极少数特殊的类匹配，由于目前规则处理程序不够完善，仍需要进行人工处理，从而给系统规则的更新造成影响。作者下一步的研究方向是对规则预处理程序进行完善，提高算法的整体性能。