0 引言

    高速網(wǎng)絡(luò)在提供便利的同時(shí)也帶來很多安全問題，數(shù)據(jù)流管理系統(tǒng)是目前解決網(wǎng)絡(luò)安全問題最主要的防御手段^[1]?；谲浖姆烙到y(tǒng)可以滿足普通用戶的應(yīng)用需求，但是對于網(wǎng)絡(luò)傳輸速度達(dá)到G bit/s的企業(yè)級網(wǎng)絡(luò)來說，系統(tǒng)容易出現(xiàn)丟包、漏檢的情況，且較大資源占用量也大大影響了整體系統(tǒng)的性能。因此設(shè)計(jì)專用的硬件匹配引擎成為防御系統(tǒng)的發(fā)展趨勢。

    隨著網(wǎng)絡(luò)中惡意數(shù)據(jù)的種類急劇增加，使得將匹配的特征碼全部存到內(nèi)部存儲器成本也越來越高，但若使用外存又將大大降低系統(tǒng)吞吐率。Bloom Filter（布魯姆過濾器）作為一種精簡的信息表示方案，在實(shí)現(xiàn)高速的數(shù)據(jù)查找的同時(shí)可以降低存儲資源的消耗。

    基于標(biāo)準(zhǔn)Bloom Filter和改進(jìn)Bloom Filter^[2-7]的匹配方案有很多，例如文獻(xiàn)[8]使用雙Hash的方案，利用FPGA中的雙端口存儲器實(shí)現(xiàn)特征碼Hash值的存儲和查找，同時(shí)可以實(shí)現(xiàn)數(shù)據(jù)的在線更新，但是雙Hash方案沒有解決Bloom Filter假陽性誤判(即不屬于集合中的元素而誤判為屬于集合中)^[9]問題，較高的錯(cuò)誤率將大大降低系統(tǒng)的可靠性。文獻(xiàn)[10]提出了一個(gè)基于Bloom Filter和位拆分狀態(tài)機(jī)的多模式分步匹配引擎設(shè)計(jì)方案，可以實(shí)現(xiàn)數(shù)據(jù)流的高速精確檢測，方案的精確匹配部分使用選擇位狀態(tài)機(jī)，在檢測時(shí)依然占用較大內(nèi)存。文獻(xiàn)[11]使用窗口折疊Bloom Filter與軟件結(jié)合的設(shè)計(jì)方案，方案提高了系統(tǒng)的資源利用率，但系統(tǒng)匹配精度不高，同時(shí)軟件低頻率也大大影響了系統(tǒng)的吞吐率。文獻(xiàn)[12]構(gòu)造了一種特殊結(jié)構(gòu)的Bloom Filter，其向量空間存儲值并非0或1，而是由計(jì)數(shù)器和編碼值兩部分組成，在匹配中，通過這兩部分值可以恢復(fù)匹配位置存儲的數(shù)據(jù)，解決了傳統(tǒng)Bloom Filter假陽性誤判問題，該方案僅適用于匹配短關(guān)鍵字。

    本文將Bloom Filter與FPGA系統(tǒng)軟核相結(jié)合，設(shè)計(jì)了一種資源消耗少、匹配速度快的軟硬核結(jié)合的分步匹配引擎方案。在系統(tǒng)部分匹配中，文本基于標(biāo)準(zhǔn)Bloom Filter原理，設(shè)計(jì)了FIBF（Finite-Input Bloom Filter），F(xiàn)IBF對特征碼長度不進(jìn)行區(qū)分，通過對固定長度特征前綴的高速掃描，過濾出可疑數(shù)據(jù)；而后，使用FPGA軟核微處理NiosII^[13]和片外存儲器SDRAM對數(shù)據(jù)進(jìn)行精確掃描。

1 Bloom Filter原理

    Bloom Filter可以實(shí)現(xiàn)高速數(shù)據(jù)傳輸下的數(shù)據(jù)查找，算法實(shí)質(zhì)是將集合中的數(shù)據(jù)通過K個(gè)Hash函數(shù)映射到位串向量中。與傳統(tǒng)的Hash表的鏈?zhǔn)酱鎯Y(jié)構(gòu)相比，Bloom Filter過濾器的Hash表查找快，占用的存儲空間大小與集合規(guī)模和集合中數(shù)據(jù)位寬無關(guān)，僅與映射后向量的位數(shù)相關(guān)。

    Bloom Filter數(shù)據(jù)結(jié)構(gòu)如圖1所示。設(shè)數(shù)據(jù)集合C={c₁，c₂，…，c_n}，其n個(gè)元素通過k個(gè)相互獨(dú)立Hash函數(shù)h₁，h₂，…，h_k映射到長度為m的位串向量V中，Hash函數(shù)的取值范圍為{0，1，…，m-1}。對字符串c′進(jìn)行檢測，若輸出值為1，則元素c′是可能需要查找的字符串，否則肯定不是。

    Bloom Filter存在假陽性誤判，因而，在應(yīng)用中需要對查詢誤判率進(jìn)行評估，設(shè)計(jì)出符合應(yīng)用需求的Bloom Filter^[9]。

    假設(shè)Hash函數(shù)取值服從均勻分布，則當(dāng)集合中所有元素都映射完畢后，向量V中任意一位為0的概率p′為：

    不屬于集合中的元素被誤判屬于的概率(即誤判率)f為：

    在實(shí)際應(yīng)用中k必須是整數(shù)并且要盡量小，因此，在計(jì)算Hash個(gè)數(shù)時(shí)取在集合元素個(gè)數(shù)和向量空間大小已知的情況下，可以計(jì)算出最小k值。如圖2所示是取m=16 384、n=2 000時(shí)，誤判率f與Hash個(gè)數(shù)的關(guān)系。當(dāng)k=6時(shí)，f取最小值f_min=f(16 384，2 000，8)=0.019 6。

    取n=2 000，f′=f_min=0.019 6，如圖3所示，圖中單個(gè)向量空間大小m隨著k成指數(shù)遞減，但是所需的存儲器總量m′隨k成“√”變化，當(dāng)Hash函數(shù)個(gè)數(shù)k=4時(shí)所需的存儲空間總量最小。

2 高效過濾器設(shè)計(jì)

2.1 過濾系統(tǒng)結(jié)構(gòu)

    病毒過濾系統(tǒng)的總體設(shè)計(jì)模型如圖4所示，系統(tǒng)由硬件系統(tǒng)和MPU系統(tǒng)兩個(gè)部分組成。系統(tǒng)的工作流程如下：

    (1)軟件系統(tǒng)抓取數(shù)據(jù)包或者讀入磁盤信息，此過程由軟件掃描引擎來完成。例如ClamAV掃描引擎，其將文件數(shù)據(jù)讀入，對文件進(jìn)行有效性掃描，這個(gè)過程主要用于檢測文件大小是否越界、文件是否可以打開，然后將有效數(shù)據(jù)輸出。

    (2)部分匹配引擎對輸入的文本數(shù)據(jù)進(jìn)行高速掃描，此過程由硬件過濾系統(tǒng)完成。硬件過濾系統(tǒng)將數(shù)據(jù)流與特征碼前綴進(jìn)行匹配，將匹配的可疑數(shù)據(jù)經(jīng)指針產(chǎn)生器處理后輸入到精確匹配模塊。

    (3)精確匹配引擎對可疑數(shù)據(jù)進(jìn)行深度過濾，此過程由MPU完成。MPU根據(jù)指針產(chǎn)生器給出的地址讀取特征碼，使用KMP算法對文本進(jìn)行匹配，若前綴匹配失敗則匹配產(chǎn)生虛警，精確匹配結(jié)束。

2.2 FIBF設(shè)計(jì)

    FIBF由c個(gè)移位寄存器和一個(gè)Bloom Filter組成，如圖5。數(shù)據(jù)由輸入端口輸入到移位寄存器中，移位寄存器在每個(gè)時(shí)鐘上升沿都要進(jìn)行一次右移操作，同時(shí)將寄存器中的數(shù)據(jù)輸出到Bloom Filter中。

    FIBF與標(biāo)準(zhǔn)Bloom Filter引擎設(shè)計(jì)，其每個(gè)結(jié)構(gòu)中只使用一個(gè)Bloom Filter，檢測特定長度8c bit的文本信息。N個(gè)FIBF并行操作可以同時(shí)查找N×8c bit信息，圖6所示是使用3個(gè)FIBF構(gòu)成的部分匹配引擎模型，每個(gè)FIBF掃描6 B信息。

    在Bloom Filter設(shè)計(jì)中，選擇Hash函數(shù)是非常重要的一個(gè)環(huán)節(jié)。在本設(shè)計(jì)中，Hash函數(shù)的選擇遵循以下兩條原則：

    (1)Hash函數(shù)要適合硬件實(shí)現(xiàn)。硬件電路具有強(qiáng)大的邏輯運(yùn)算能力，因此在算法選取時(shí)要盡量多使用邏輯運(yùn)算，降低算術(shù)運(yùn)算量。

    (2)輸出結(jié)果要與每一比特位相關(guān)，以降低Hash沖突的概率。

    文獻(xiàn)[14]給出的Hash函數(shù)構(gòu)造方案H₃很適合硬件實(shí)現(xiàn)。對于有a個(gè)比特的字符串S={s₁，s₂，…，s_a}，通過H3算法構(gòu)造的Hash函數(shù)可以表示為：

2.3 指針產(chǎn)生器設(shè)計(jì)

    當(dāng)3-FIBF部分匹配引擎發(fā)生匹配時(shí)，F(xiàn)IBF2和FIBF3并不能確定已匹配的前綴是其對應(yīng)子串的前綴，即在匹配中會(huì)出現(xiàn)排列組合的情況，這將大大增加匹配的誤判率。而精確匹配耗時(shí)多效率低，若產(chǎn)生的誤判率過高，精確匹配逐一匹配特征碼將大大影響整個(gè)系統(tǒng)的吞吐率。指針產(chǎn)生器的設(shè)計(jì)可以檢測匹配的多個(gè)子串是否可能對應(yīng)于某一特征碼，同時(shí)產(chǎn)生精確匹配中特征碼的地址，提升精確匹配效率。指針產(chǎn)生器設(shè)計(jì)如圖7所示。

    指針產(chǎn)生器從緩存中取出w bit的可疑數(shù)據(jù)，經(jīng)過一次Hash變換得到v bit的Hash值，以此Hash值作為地址到存儲器中查找可疑數(shù)據(jù)對應(yīng)特征碼在SDRAM中的地址。若查找的地址空間的數(shù)據(jù)為全“1”，則表示匹配產(chǎn)生虛警。

    例如，設(shè)特征庫集合中元素個(gè)數(shù)為n=7，使用2-FIBF掃描數(shù)據(jù)，每個(gè)FIBF掃描2 B，則匹配的前綴長度為4 B。經(jīng)Hash函數(shù)H(b)=bQ^[14]，n個(gè)前綴經(jīng)Hash運(yùn)算后產(chǎn)生的地址、指針對應(yīng)關(guān)系如圖8所示。b是由緩存數(shù)據(jù)表示的1×16向量，Q是一個(gè)16×4的隨機(jī)向量。

    對于特征編號為“1”的特征，其前綴為“21b8”，經(jīng)Hash函數(shù)運(yùn)算后得到的Hash值為“1010”，把Hash值作為地址到存儲器中查找對應(yīng)的位置的數(shù)據(jù)，對應(yīng)數(shù)據(jù)為精確匹配中特征碼存儲的地址。若輸入數(shù)據(jù)為“2100”，在FIBF檢測中輸出發(fā)生匹配，此時(shí)指針查找器讀取緩存中的“2100”，經(jīng)Hash變換后產(chǎn)生Hash值“1011”，對應(yīng)的特征地址為“111”，可判斷產(chǎn)生虛警。若輸入數(shù)據(jù)為2150，在FIBF檢測中同樣發(fā)生匹配，但是經(jīng)指針查找器輸出的地址數(shù)據(jù)為“101”，未排除虛警，但是由于給出的地址對應(yīng)的特征前綴為“5055”，在精確匹配中，首字母匹配失敗，則直接結(jié)束匹配。

    Hash實(shí)現(xiàn)多對少映射，上邊例子使用的Hash函數(shù)由H3算法構(gòu)造，當(dāng)特征集合中元素?cái)?shù)目增多，且字符串?dāng)?shù)據(jù)隨機(jī)性比較差的情況下，H₃算法產(chǎn)生的碰撞概率比較大，此時(shí)可以采用文獻(xiàn)[15]提出的多IGU（Index Generation Unit）并行方案。IGU的預(yù)處理階段首先使用特征碼中的比特位構(gòu)成二維數(shù)組，數(shù)組中的數(shù)據(jù)對應(yīng)特征碼的地址指針。通過對數(shù)組進(jìn)行分析，選擇合適的X、Y坐標(biāo)的位進(jìn)行異或操作，以產(chǎn)生的值作為Y值，使用Y可以唯一地確定指針。對于少部分產(chǎn)生碰撞的數(shù)據(jù)，文獻(xiàn)[15]通過設(shè)計(jì)一個(gè)額外的IGU存儲器存儲這些數(shù)據(jù)。

2.4 地址存儲空間設(shè)計(jì)

    Bloom Filter必須使用一定的存儲空間來存儲向量，設(shè)計(jì)好的存儲設(shè)計(jì)方案可以提高內(nèi)存利用率并提高系統(tǒng)吞吐率。在模式匹配中，存儲大容量的特征碼數(shù)據(jù)內(nèi)部存儲器無法實(shí)現(xiàn)，只能使用片外存儲，但是對于數(shù)據(jù)量比較小的向量，若使用片外存儲器，不僅降低了系統(tǒng)頻率，而且降低了內(nèi)存使用率，浪費(fèi)FPGA資源。

    為了實(shí)現(xiàn)數(shù)據(jù)的快速的查詢，設(shè)計(jì)中可以2個(gè)Hash函數(shù)共用雙端口RAM存儲器^[14]，也可以使用單口RAM，每個(gè)RAM對應(yīng)一個(gè)Hash函數(shù)。通過實(shí)驗(yàn)分析，一個(gè)雙端口RAM占用的資源量是一個(gè)單口RAM資源占有量的2倍多，并且雙口RAM扇出比較大，延遲多，同時(shí)增加了發(fā)生虛警的概率，所以本文選擇使用單口RAM進(jìn)行數(shù)據(jù)存儲。

3 性能實(shí)驗(yàn)及分析

    實(shí)驗(yàn)選取Clam AV特征庫main.db類中2 000個(gè)特征碼，部分匹配關(guān)鍵字為對應(yīng)特征碼的12 B前綴，可接受的誤判率f=0.019 6，根據(jù)式（5）和圖3可計(jì)算出當(dāng)k=4時(shí)每個(gè)FIBF所需的總存儲空間最小為25 093 bit，此時(shí)單個(gè)向量空間大小為5 019 bit，但是由于存儲器空間大小為2的冪次方，所以k=4時(shí)每個(gè)Hash函數(shù)的實(shí)際占用空間大小為8 192 bit，這使得總存儲空間大小增大到32 768 bit。而取k=6，單個(gè)向量大小為3 858 bit，存儲所需的存儲器大小為4 096 bit，總存儲空間為24 576 bit<32 768 bit。引擎使用2個(gè)FIBF并行操作，每個(gè)FIBF檢測長度為6 B。輸入本文為“ca21b8005a”檢測前綴的FIBF仿真波形如圖9。數(shù)據(jù)輸入以ASCII形式，向量輸出為高電平表示其對應(yīng)的Hash空間發(fā)生匹配，只有當(dāng)所有的向量空間輸出全為高電平，輸出信號“result”才為高電平。從圖中可以看出“21b800”為檢測出的特征碼前綴。

    實(shí)驗(yàn)使用ALTERA低成本Cyclone II系列的開發(fā)平臺。第一步部分匹配，每個(gè)FIBF存儲2 000個(gè)特征碼的6 B關(guān)鍵字需要使用6個(gè)M4K RAM，總的存儲器消耗量為27 648 bit，單字節(jié)輸入的最大工作頻率為260 MHz。指針產(chǎn)生器將2 000個(gè)特征碼的地址數(shù)據(jù)存儲到一個(gè)12輸入、11輸出的儲存器，使用11個(gè)M4K。第二步精確匹配，全部特征碼存儲在外部存儲器SDRAM中，匹配算法使用NiosII/f嵌入式軟核，使用4002 LE，工作頻率為100 MHz。

    實(shí)驗(yàn)中系統(tǒng)最大吞吐率為3.12 Gb/s，設(shè)存儲器利用率(MUC)為每個(gè)特征字節(jié)需要的存儲器大小，單個(gè)FIBF的

    為了與其他算法相比較，使用標(biāo)準(zhǔn)化吞吐率Th/MUC^[16]，結(jié)果如表1所示，Th表示引擎的吞吐率單位是Gb/s， Pattern表示存儲的特征碼的數(shù)目，Tool表示使用的硬件器件。

4 結(jié)論

    本文提出了一種結(jié)合了Bloom Filter以及FPGA軟硬核的高效匹配引擎設(shè)計(jì)方案。方案使用分步匹配的方法，使用Bloom Filter結(jié)合硬件高度并行的特點(diǎn)一次過濾掉大部分正常數(shù)據(jù)，而后系統(tǒng)MUP通過指針定位精確匹配特征碼在SDRAM中的位置，實(shí)現(xiàn)快速的精確匹配。通過流水線的方式，設(shè)置緩存空間，將軟硬件模塊相連接，使系統(tǒng)可以實(shí)現(xiàn)高速網(wǎng)絡(luò)下的數(shù)據(jù)精確檢測。實(shí)驗(yàn)中2-FIBF過濾系統(tǒng)吞吐率達(dá)到3.12 Gb/s，完全可以滿足千兆網(wǎng)絡(luò)的需求，通過多個(gè)FIBF并行同時(shí)增大FIBF檢測窗口大小，可以實(shí)現(xiàn)更高傳輸速率網(wǎng)絡(luò)中的數(shù)據(jù)檢測。

參考文獻(xiàn)

[1] 徐東亮，張宏莉，張磊，等.模式匹配在網(wǎng)絡(luò)安全中的研究[J].電信科學(xué)，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] 葉明江，崔勇，徐恪，等.基于有狀態(tài)Bloom Filter引擎的高速分組檢測[J].軟件學(xué)報(bào)，2007，18(1)：117-126.

[8] 鄭堯.硬件防火墻中多模式匹配算法的設(shè)計(jì)與實(shí)現(xiàn)[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2009.

[9] 謝鯤，文吉?jiǎng)偅瑥埓蠓?，?布魯姆過濾器查詢算法[J].軟件學(xué)報(bào)，2009，20(1)：96-108.

[10] 劉威，郭淵博，黃鵬.基于Bloom Filter的多模式匹配引擎[J].電子學(xué)報(bào)，2010，38(5)：1095-1099.

[11] 駱瀟，郭健，黃河.基于Bloom Filter的多模式匹配優(yōu)化設(shè)計(jì)和硬件實(shí)現(xiàn)[J].電信技術(shù)研究，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開發(fā)特權(quán)和你一起學(xué)NIOS II[M].北京：北京航空航天大學(xué)出版社，2011.

[14] RAMAKRISHNA M，F(xiàn)U 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.