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假阳性误判问题，该方案仅适用于匹配短关键字。

    本文将Bloom Filter与FPGA系统软核相结合，设计了一种资源消耗少、匹配速度快的软硬核结合的分步匹配引擎方案。在系统部分匹配中，文本基于标准Bloom Filter原理，设计了FIBF（Finite-Input Bloom Filter），FIBF对特征码长度不进行区分，通过对固定长度特征前缀的高速扫描，过滤出可疑数据；而后，使用FPGA软核微处理NiosII^[13]和片外存储器SDRAM对数据进行精确扫描。

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资源。

    为了实现数据的快速的查询，设计中可以2个Hash函数共用双端口RAM存储器^[14]，也可以使用单口RAM，每个RAM对应一个Hash函数。通过实验分析，一个双端口RAM占用的资源量是一个单口RAM资源占有量的2倍多，并且双口RAM扇出比较大，延迟多，同时增加了发生虚警的概率，所以本文选择使用单口RAM进行数据存储。

3 性能实验及分析

    实验选取Clam AV特征库main.db类中2 000个特征码，部分匹配关键字为对应特征码的12 B前缀，可接受的误判率f=0.019 6，根据式（5）和图3可计算出当k=4时每个FIBF所需的总存储空间最小为25 093 bit，此时单个向量空间大小为5 019 bit，但是由于存储器空间大小为2的幂次方，所以k=4时每个Hash函数的实际占用空间大小为8 192 bit，这使得总存储空间大小增大到32 768 bit。而取k=6，单个向量大小为3 858 bit，存储所需的存储器大小为4 096 bit，总存储空间为24 576 bit<32 768 bit。引擎使用2个FIBF并行操作，每个FIBF检测长度为6 B。输入本文为“ca21b8005a”检测前缀的FIBF仿真波形如图9。数据输入以ASCII形式，向量输出为高电平表示其对应的Hash空间发生匹配，只有当所有的向量空间输出全为高电平，输出信号“result”才为高电平。从图中可以看出“21b800”为检测出的特征码前缀。

    实验使用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 结论

    本文提出了一种结合了Bloom Filter以及FPGA软硬核的高效匹配引擎设计方案。方案使用分步匹配的方法，使用Bloom Filter结合硬件高度并行的特点一次过滤掉大部分正常数据，而后系统MUP通过指针定位精确匹配特征码在SDRAM中的位置，实现快速的精确匹配。通过流水线的方式，设置缓存空间，将软硬件模块相连接，使系统可以实现高速网络下的数据精确检测。实验中2-FIBF过滤系统吞吐率达到3.12 Gb/s，完全可以满足千兆网络的需求，通过多个FIBF并行同时增大FIBF检测窗口大小，可以实现更高传输速率网络中的数据检测。

参考文献

[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.