基于预定义类的紧凑型正则表达式匹配算法

麦涛涛，潘晓中，王亚奇，苏 阳

(1.武警工程大学 电子技术系，西安 710086； 2.武警部队网络与信息安全保密重点实验室，西安 710086)

(*通信作者电子邮箱wj_maitao@126.com)

基于预定义类的紧凑型正则表达式匹配算法

麦涛涛1，2*，潘晓中1，2，王亚奇1，2，苏 阳1，2

(1.武警工程大学 电子技术系，西安 710086； 2.武警部队网络与信息安全保密重点实验室，西安 710086)

(*通信作者电子邮箱wj_maitao@126.com)

针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战，结合扩展有限自动机(XFA)正则表达式匹配算法，提出了一种预定义类的压缩自动机匹配算法(Pre-Class CFA)。通过预定义类，算法既可以实现正则表达式中类字符匹配，又能够通过优先级的设定匹配特殊字符集，并在XFA消除确定性有限状态机(DFA)状态爆炸问题的基础上进一步压缩了迁移边数目；同时算法根据现场可编程门阵列(FPGA)和迁移边的特征，设计了一种基于并联只读存储器(ROM)结构的迁移边存取方法，可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2- 70上对算法进行测试，实验中系统吞吐量为1.3 Gb/s，可实现千兆网络下的入侵检测和垃圾过滤。

正则表达式匹配；扩展有限自动机；现场可编程门阵列

0 引言

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

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

表1 Snort规则集统计分析结果

正则表达式匹配通常采用确定性有限状态机(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,Σ,δ,q0,F}。其中:Q为状态集，Σ为字母表，δ为迁移函数，q0为初始状态，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,(q0,v0),F}。其中：V表示辅助变量集，U表示每个状态的更新函数，v0表示辅助变量的初始值，其余参数与DFA相同。图1(b)给出了使用XFA匹配{.*ab.*cd, .*ef.*gh}的状态图，在组合XFA状态PV上添加bit1和bit2的赋值操作指令，在状态SV、PY上分别增加bit1和bit2的判断指令，在整个组合XFA中共需要7个状态和2个辅助变量，相比DFA中的15个状态减小了50%。辅助变量的引入使XFA解决了DFA状态空间爆炸问题。

图1 {.*ab.*cd, .*ef.*gh}状态图

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

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

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

Pre-ClassCFA支持多种形式的状态迁移，不仅包括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]”定义为一个类，则匹配仅需要一条迁移边。

图2 “a[bB][^c][0- 8]*9[a-z]”DFA状态图

表2 “a[bB][^c][0- 8]*9[a-z]”状态转移表

Tab.2Statetransitiontableof“a[bB][^c][0- 8]*9[a-z]”

RuleCurrentstateInputNextstatePriorityR0∗∗S00R1∗aS10R2S1[bB]S20R3S2∗S40R4S2aS30R5S2cS00R6S3dS40R7S39S51R8S3[bB]S20R9S4dS40R10S49S50R11S5[a⁃z]S60

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

Pre-ClassCFA(S,δ,Σ)Tran_SetTc=∅;num=0;array[128];For(eachstateSiinS)doFor(eachstateSiinS)doFor(charfrom 8′h00 to 8′h7f) If(Tran tk=Sj→δ(Si,char)) array[char]=1;

num++;

Endfor

If(num=2)If(array中两个存储为1的空间地址相差32)type=不区分大小；

If(num=10)type=数字匹配；

Tc=Tc∪t数字;

Tc=Tc∩t0～9;

⋮

If(num=9)If(array中地址为8′h30-8′h38为1)Tc=Tc∪t0-8; Tc=Tc∩t0～9; Tc=Tc∪t9; t9.priority=1;

Endfor

array[]=0;

Endfor

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

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

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

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

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

2.2.1 迁移边分类与规则定义

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

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

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

如果存储块数目n大于或者等于自动机中所有状态的最大迁移边数目Nmax，则所有的迁移边可以在一个时钟内实现并行处理；若n

图4 “a[bB][^c][0- 8]*9[a-z]”迁移边存储结构

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

图5 匹配引擎结构

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

1)

modulePre-ClassCFA(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 辅助变量存储器设计

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

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

3.1 算法性能分析

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

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

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

c=Ns*N；N≥1,N∈Z+

则

RX/PC=(m+1)/[1+(1-Ratio)×N]

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

3.2 实验评估

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

表3 不同数目并联ROM的实验相关参数

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

表4 Snort规则集参数统计

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

4 结语

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

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

)

[1] 褚衍杰，李云照，魏强.一种改进的多模式匹配算法[J].西安电子科技大学学报(自然科学版), 2014, 41(6): 174-179.(CHUYJ,LIYZ,WEIQ.Improvedmulti-patternmatchingalgorithm[J].JournalofXidianUniversity(NaturalScience), 2014, 41(6): 174-179.)

[2] 嵩天,李冬妮,汪东升,等.存储有效的多模式匹配算法和体系结构[J].软件学报,2013,24(7):1650-1665.(SONGT,LIDN,WANGDS,etal.Memoryefficientalgorithmandarchitectureformulti-patternmatching[J].JournalofSoftware, 2013, 24(7): 1650-1665.

[3]NAVARROG,RAFFINOTM.FlexiblePatternMatchinginStrings:PracticalOn-LineSearchAlgorithmsforTextsandBiologicalSequences[M].NewYork:CambridgeUniversityPress, 2002: 41-75.

[4]Snort[EB/OL].[2016- 07- 12].http://www.snort.org/.

[5]ClamAntiVirus[EB/OL].[2016- 07- 12].http://www.clamav.net/.

[6]SMITHR,ESTANC,JHAS.XFA:fastersignaturematchingwithextendedautomata[C]//SP’08:Proceedingsofthe2008IEEESymposiumonSecurityandPrivacy.Washington,DC:IEEEComputerSociety, 2008: 187-201.

[7] 黄昆,张大方,谢高岗,等.一种面向深度数据包检测的紧凑型正则表达式匹配算法[J].中国科学:信息科学,2010,40(2):356-370.(HUANGK,ZHANGDF,XIEGG,etal.Deeppacketinspectionorientedcompactregularexpressionmatchingalgorithm[J].ScienceChinaInformationSciences, 2010, 40(2): 356-370.)

[8] 张大方,张洁坤,黄昆.一种基于智能有限自动机的正则表达式匹配算法[J].电子学报,2012,40(8):1617-1623.(ZHANGDF,ZHANGJK,HUANGK.Aregularexpressionmatchingalgorithmwithsmartfiniteautomaton[J].ActaElectronicaSinica, 2012, 40(8): 1617-1623.)[9] VAN LUNTEREN J, HAGLEITNER C, HEIL T, et al.Designing a programmable wire-speed regular-expression matching accelerator [C]// MICRO-45: Proceedings of the 2012 45th Annual IEEE/ACM International Symposium on Microarchitecture.Washington, DC: IEEE Computer Society, 2012: 461-472.

[10] SMITH R, ESTAN C, JHA S, et al.Deflating the big bang: fast and scalable deep packet inspection with extended finite automata [C]// SIGCOMM ’08: Proceedings of the 2008 ACM SIGCOMM Computer Communication.New York: ACM, 2008: 207-218.

[11] VAN LUNTEREN J.High-performance pattern-matching for intrusion detection [C]// Proceedings of the IEEE INFOCOM 2006.Washington, DC: IEEE Computer Society, 2006: 1-13.

[12] HAYES C L, LUO Y.DPICO: a high speed deep packet inspection engine using compact finite automata [C]// ANCS ’07: Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems.New York: ACM, 2007: 195-203.

[13] Xilinx, Inc.Virtex 4 family overview [EB/OL].(2010- 08- 30) [2016- 02- 24].http://www.xilinx.com/support/documentation/data_sheets/ds112.pdf.

[14] VASILIADIS G, POLYCHRONAKIS M, IOANNIDIS S.MIDeA: a multi-parallel intrusion detection architecture [C]// CCS’11: Proceedings of the 18th ACM Conference on Computer and Communications Security.New York: ACM, 2011: 297-308.

This work is partially supported by the National Natural Science Foundation of China (61402531), the Natural Science Foundation of Shaanxi Province (2014JQ8307, 2015JQ6231).

MAI Taotao, born in 1992, M.S.candidate.His research interests include network safety, embedded system.

PAN Xiaozhong, born in 1964, M.S., professor.His research interests include network safety, embedded system.

WANG Yaqi, born in 1982, Ph.D., lecturer.His research interests include security of cyberspace.

SU Yang, born in1986, M.S., assistant.His research interests include embedded system.

Predefined-class based algorithm for compact regular expression matching

MAI Taotao1,2*, PAN Xiaozhong1,2, WANG Yaqi1,2, SU Yang1,2

(1.DepartmentofElectronicTechnology,EngineeringCollegeoftheChineseArmedPoliceForce,Xi’anShaanxi710086,China;2.KeyLaboratoryofNetworkandInformationSecurityoftheChineseArmedPoliceForce,Xi’anShaanxi710086,China)

For hardware regular expression matching algorithms are faced with the challenges in memory space and throughput, a Predefined-class Compact Finite Automaton (Pre-class CFA) matching algorithm based on Extended Finite Automaton (XFA) regular expression matching algorithm was proposed.By using the predefined classes, the algorithm not only can achieve class character matching in regular expression, but also can match the special character set by priority setting; besides, the migrating edges were reduced when eliminating the Deterministic Finite Automaton (DFA) state space exploration problem.At the same time, based on the characteristics of Field-Programmable Gate Array (FPGA) and migration edge, a migration edge access method based on parallel Read-Only Memory (ROM) was designed to realize the parallel reading and matching of the same state with mutiple migration edges.The algorithm was tested on ALTERA DE2- 70 FPGA platform, which is a low-performance platform.The throughput of the experimental system is 1.30 Gb/s, which can realize intrusion detection and garbage filtering under gigabit network.

regular expression matching; Extended Finite Automaton (XFA); Field-Programmable Gate Array (FPGA)

2016- 08- 15;

2016- 09- 12。

国家自然科学基金资助项目(61402531);陕西省自然科学基金资助项目(2014JQ8307,2015JQ6231)。

麦涛涛(1992—),男,河南洛阳人,硕士研究生,主要研究方向:网络安全、嵌入式系统; 潘晓中(1964—),男,陕西西安人,教授,硕士,主要研究方向:网络安全、嵌入式系统; 王亚奇(1982—),男,河南周口人,讲师,博士,主要研究方向:网络空间安全; 苏阳(1986—),男,宁夏银川人,助教,硕士,主要研究方向:嵌入式系统。

1001- 9081(2017)02- 0397- 05

10.11772/j.issn.1001- 9081.2017.02.0397

TP393

A