高效匹配引擎的设计与实现

麦涛涛，潘晓中，李晓策

(武警工程大学 电子技术系，陕西 西安710086）

摘 要：针对软件模式匹配引擎速度慢、占用系统资源大的问题，提出了一种基于Bloom Filter的FIBF结构，结合FPGA NIOSII 微处理器（MUP），设计了软硬核相结合的匹配引擎方案。引擎通过FIBF过滤过滤掉大部分正常数据，将过滤出的可疑字符串输入到NIOSII软核进行精确匹配，两者之间通过一个指针产生器连接，整个系统以流水线方式工作。FIBF结构资源消耗低，n-FIBF并行处理，系统引擎可以达到较高的吞吐率。实验表明，在使用相同资源的情况下，本方案系统吞吐率要优于其他算法。

中图分类 ：TP391

文献标识码：A

DOI：10.16157/j.issn.0258-7998.2016.05.024

中文引用格式： 麦涛涛，潘晓中，李晓策. 高效匹配引擎的设计与实现[J].电子技术应用，2016，42(5)：85-89.

英文引用格式：Mai Taotao，Pan Xiaozhong，Li Xiaoce. The design and implementation of high-performance matching engine[J].Application of Electronic Technique，2016，42(5)：85-89.

0 引言

高速 络在提供便利的同时也带来很多安全问题，数据流管理系统是目前解决 络安全问题最主要的防御手段^[1]。基于软件的防御系统可以满足普通用户的应用需求，但是对于 络传输速度达到G bit/s的企业级 络来说，系统容易出现丢包、漏检的情况，且较大资源占用量也大大影响了整体系统的性能。因此设计专用的硬件匹配引擎成为防御系统的发展趋势。

随着 络中恶意数据的种类急剧增加，使得将匹配的特征码全部存到内部存储器成本也越来越高，但若使用外存又将大大降低系统吞吐率。Bloom Filter（布鲁姆过滤器）作为一种精简的信息表示方案，在实现高速的数据查找的同时可以降低存储资源的消耗。

基于标准Bloom Filter和改进Bloom Filter^[2-7]的匹配方案有很多，例如文献[8]使用双Hash的方案，利用FPGA中的双端口存储器实现特征码Hash值的存储和查找，同时可以实现数据的在线更新，但是双Hash方案没有解决Bloom Filter假阳性误判(即不属于集合中的元素而误判为属于集合中)^[9]问题，较高的错误率将大大降低系统的可靠性。文献[10]提出了一个基于Bloom Filter和位拆分状态机的多模式分步匹配引擎设计方案，可以实现数据流的高速精确检测，方案的精确匹配部分使用选择位状态机，在检测时依然占用较大内存。文献[11]使用窗口折叠Bloom Filter与软件结合的设计方案，方案提高了系统的资源利用率，但系统匹配精度不高，同时软件低频率也大大影响了系统的吞吐率。文献[12]构造了一种特殊结构的Bloom Filter，其向量空间存储值并非0或1，而是由计数器和编码值两部分组成，在匹配中，通过这两部分值可以恢复匹配位置存储的数据，解决了传统Bloom Filter假阳性误判问题，该方案仅适用于匹配短关键字。

1 Bloom Filter原理

Bloom Filter可以实现高速数据传输下的数据查找，算法实质是将集合中的数据通过K个Hash函数映射到位串向量中。与传统的Hash表的链式存储结构相比，Bloom Filter过滤器的Hash表查找快，占用的存储空间大小与集合规模和集合中数据位宽无关，仅与映射后向量的位数相关。

Bloom Filter数据结构如图1所示。设数据集合C={c₁，c₂，…，c_n}，其n个元素通过k个相互独立Hash函数h₁，h₂，…，h_k映射到长度为m的位串向量V中，Hash函数的取值范围为{0，1，…，m-1}。对字符串c′进行检测，若输出值为1，则元素c′是可能需要查找的字符串，否则肯定不是。

Bloom Filter存在假阳性误判，因而，在应用中需要对查询误判率进行评估，设计出符合应用需求的Bloom Filter^[9]。

假设Hash函数取值服从均匀分布，则当集合中所有元素都映射完毕后，向量V中任意一位为0的概率p′为：

不属于集合中的元素被误判属于的概率(即误判率)f为：

在实际应用中k必须是整数并且要尽量小，因此，在计算Hash个数时取在集合元素个数和向量空间大小已知的情况下，可以计算出最小k值。如图2所示是取m=16 384、n=2 000时，误判率f与Hash个数的关系。当k=6时，f取最小值f_min=f(16 384，2 000，8)=0.019 6。

取n=2 000，f′=f_min=0.019 6，如图3所示，图中单个向量空间大小m随着k成指数递减，但是所需的存储器总量m′随k成“√”变化，当Hash函数个数k=4时所需的存储空间总量最小。

2 高效过滤器设计

2.1 过滤系统结构

病毒过滤系统的总体设计模型如图4所示，系统由硬件系统和MPU系统两个部分组成。系统的工作流程如下：

(1)软件系统抓取数据包或者读入磁盘信息，此过程由软件扫描引擎来完成。例如ClamAV扫描引擎，其将文件数据读入，对文件进行有效性扫描，这个过程主要用于检测文件大小是否越界、文件是否可以打开，然后将有效数据输出。

(2)部分匹配引擎对输入的文本数据进行高速扫描，此过程由硬件过滤系统完成。硬件过滤系统将数据流与特征码前缀进行匹配，将匹配的可疑数据经指针产生器处理后输入到精确匹配模块。

(3)精确匹配引擎对可疑数据进行深度过滤，此过程由MPU完成。MPU根据指针产生器给出的地址读取特征码，使用KMP算法对文本进行匹配，若前缀匹配失败则匹配产生虚警，精确匹配结束。

2.2 FIBF设计

FIBF由c个移位寄存器和一个Bloom Filter组成，如图5。数据由输入端口输入到移位寄存器中，移位寄存器在每个时钟上升沿都要进行一次右移操作，同时将寄存器中的数据输出到Bloom Filter中。

FIBF与标准Bloom Filter引擎设计，其每个结构中只使用一个Bloom Filter，检测特定长度8c bit的文本信息。N个FIBF并行操作可以同时查找N×8c bit信息，图6所示是使用3个FIBF构成的部分匹配引擎模型，每个FIBF扫描6 B信息。

在Bloom Filter设计中，选择Hash函数是非常重要的一个环节。在本设计中，Hash函数的选择遵循以下两条原则：

(1)Hash函数要适合硬件实现。硬件电路具有强大的逻辑运算能力，因此在算法选取时要尽量多使用逻辑运算，降低算术运算量。

(2)输出结果要与每一比特位相关，以降低Hash冲突的概率。

文献[14]给出的Hash函数构造方案H₃很适合硬件实现。对于有a个比特的字符串S={s₁，s₂，…，s_a}，通过H3算法构造的Hash函数可以表示为：

2.3 指针产生器设计

当3-FIBF部分匹配引擎发生匹配时，FIBF2和FIBF3并不能确定已匹配的前缀是其对应子串的前缀，即在匹配中会出现排列组合的情况，这将大大增加匹配的误判率。而精确匹配耗时多效率低，若产生的误判率过高，精确匹配逐一匹配特征码将大大影响整个系统的吞吐率。指针产生器的设计可以检测匹配的多个子串是否可能对应于某一特征码，同时产生精确匹配中特征码的地址，提升精确匹配效率。指针产生器设计如图7所示。

指针产生器从缓存中取出w bit的可疑数据，经过一次Hash变换得到v bit的Hash值，以此Hash值作为地址到存储器中查找可疑数据对应特征码在SDRAM中的地址。若查找的地址空间的数据为全“1”，则表示匹配产生虚警。

例如，设特征库集合中元素个数为n=7，使用2-FIBF扫描数据，每个FIBF扫描2 B，则匹配的前缀长度为4 B。经Hash函数H(b)=bQ^[14]，n个前缀经Hash运算后产生的地址、指针对应关系如图8所示。b是由缓存数据表示的1×16向量，Q是一个16×4的随机向量。

对于特征编 为“1”的特征，其前缀为“21b8”，经Hash函数运算后得到的Hash值为“1010”，把Hash值作为地址到存储器中查找对应的位置的数据，对应数据为精确匹配中特征码存储的地址。若输入数据为“2100”，在FIBF检测中输出发生匹配，此时指针查找器读取缓存中的“2100”，经Hash变换后产生Hash值“1011”，对应的特征地址为“111”，可判断产生虚警。若输入数据为2150，在FIBF检测中同样发生匹配，但是经指针查找器输出的地址数据为“101”，未排除虚警，但是由于给出的地址对应的特征前缀为“5055”，在精确匹配中，首字母匹配失败，则直接结束匹配。

Hash实现多对少映射，上边例子使用的Hash函数由H3算法构造，当特征集合中元素数目增多，且字符串数据随机性比较差的情况下，H₃算法产生的碰撞概率比较大，此时可以采用文献[15]提出的多IGU（Index Generation Unit）并行方案。IGU的预处理阶段首先使用特征码中的比特位构成二维数组，数组中的数据对应特征码的地址指针。通过对数组进行分析，选择合适的X、Y坐标的位进行异或操作，以产生的值作为Y值，使用Y可以唯一地确定指针。对于少部分产生碰撞的数据，文献[15]通过设计一个额外的IGU存储器存储这些数据。

2.4 地址存储空间设计

Bloom Filter必须使用一定的存储空间来存储向量，设计好的存储设计方案可以提高内存利用率并提高系统吞吐率。在模式匹配中，存储大容量的特征码数据内部存储器无法实现，只能使用片外存储，但是对于数据量比较小的向量，若使用片外存储器，不仅降低了系统频率，而且降低了内存使用率，浪费FPGA资源。

3 性能实验及分析

实验使用ALTERA低成本Cyclone II系列的开发平台。第一步部分匹配，每个FIBF存储2 000个特征码的6 B关键字需要使用6个M4K RAM，总的存储器消耗量为27 648 bit，单字节输入的最大工作频率为260 MHz。指针产生器将2 000个特征码的地址数据存储到一个12输入、11输出的储存器，使用11个M4K。第二步精确匹配，全部特征码存储在外部存储器SDRAM中，匹配算法使用NiosII/f嵌入式软核，使用4002 LE，工作频率为100 MHz。

实验中系统最大吞吐率为3.12 Gb/s，设存储器利用率(MUC)为每个特征字节需要的存储器大小，单个FIBF的

为了与其他算法相比较，使用标准化吞吐率Th/MUC^[16]，结果如表1所示，Th表示引擎的吞吐率单位是Gb/s， Pattern表示存储的特征码的数目，Tool表示使用的硬件器件。

4 结论

参考文献

[1] 徐东亮，张宏莉，张磊，等.模式匹配在 络安全中的研究[J].电信科学，2015，31(3)：115-123.

[2] BONOMI F，MITZENMACHER M，PANIGRAHY R，et al.An improved construction for counting Bloom Filters[M].Algorithms-ESA 2006.Springer Berlin Heidelberg，2006.

[3] MITZENMACHER M.Compressed Bloom Filters[J].IEEE/ACM Transactions on Networking(TON)，2002，10(5)：604-612.

[4] 肖明忠，代亚非，李晓明.拆分型Bloom Filter[J].Acta Electronica Sinica，2004，32(2)：241-245.

[5] GUO D，WU J，CHEN H，et al.Theory and network applications of dynamic Bloom Filters[C].INFOCOM，2006：1-12.

[6] XIE K，MIN Y，ZHANG D，et al.A scalable Bloom Filter for membership queries[C].Global Telecommunications Conference，2007.GLOBECOM’07.IEEE，2007：543-547.

[7] 叶明江，崔勇，徐恪，等.基于有状态Bloom Filter引擎的高速分组检测[J].软件学 ，2007，18(1)：117-126.

[8] 郑尧.硬件防火墙中多模式匹配算法的设计与实现[D].哈尔滨：哈尔滨工业大学，2009.

[9] 谢鲲，文吉刚，张大方，等.布鲁姆过滤器查询算法[J].软件学 ，2009，20(1)：96-108.

[10] 刘威，郭渊博，黄鹏.基于Bloom Filter的多模式匹配引擎[J].电子学 ，2010，38(5)：1095-1099.

[11] 骆潇，郭健，黄河.基于Bloom Filter的多模式匹配优化设计和硬件实现[J].电信技术研究，2011(5)：8-13.

[12] XIONG S，YAO Y，CAO Q，et al.kBF：a Bloom Filter for key-value storage with an application on approximate state machines[C].INFOCOM，2014 Proceedings IEEE.IEEE，2014：1150-1158.

[13] 吴厚航.爱上FPGA开发特权和你一起学NIOS II[M].北京：北京航空航天大学出版 ，2011.

[14] RAMAKRISHNA M，FU E，BAHCEKAPILI E.Efficient hardware hashing functions for high performance computers[J].Computers，IEEE Transaction on，1997，46(12)：1378-1381.

[15] NAKAHARA H，SASAO T，MATSUURA M，et al.A virus scanning engine using a parallel finite-input memory machine and MPUs[C].Field Programmable Logic and Applications，2009.FPL 2009.International Conference on.IEEE，2009：635-639.

[16] NAKAHARA H，SASAO T，MATSUURA M，et al.The parallel sieve method for a virus scanning engine[C].Digital System Design，Architectures，Methods and Tools，2009.DSD’09.12th Euromicro Conference on.IEEE，2009：809-816.

[17] ATTIG M，DHARMAPURIKAR S，LOCKWOOD J.Implementation results of Bloom Filters for string matching[C].IEEE Symposium on Field-Programmable Custom Computing Machines(FCCM’04)，2004：322-323.