0 引言

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

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

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

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

1 Bloom Filter原理

    Bloom Filter可以實現(xiàn)高速數(shù)據(jù)傳輸下的數(shù)據(jù)查找，算法實質(zhì)是將集合中的數(shù)據(jù)通過K個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個元素通過k個相互獨立Hash函數(shù)h₁，h₂，…，h_k映射到長度為m的位串向量V中，Hash函數(shù)的取值范圍為{0，1，…，m-1}。對字符串c′進行檢測，若輸出值為1，則元素c′是可能需要查找的字符串，否則肯定不是。

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

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

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

    在實際應(yīng)用中k必須是整數(shù)并且要盡量小，因此，在計算Hash個數(shù)時取在集合元素個數(shù)和向量空間大小已知的情況下，可以計算出最小k值。如圖2所示是取m=16 384、n=2 000時，誤判率f與Hash個數(shù)的關(guān)系。當(dāng)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成指數(shù)遞減，但是所需的存儲器總量m′隨k成“√”變化，當(dāng)Hash函數(shù)個數(shù)k=4時所需的存儲空間總量最小。

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

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

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

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

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

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

2.2 FIBF設(shè)計

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

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

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

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

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

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

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

    當(dāng)3-FIBF部分匹配引擎發(fā)生匹配時，F(xiàn)IBF2和FIBF3并不能確定已匹配的前綴是其對應(yīng)子串的前綴，即在匹配中會出現(xiàn)排列組合的情況，這將大大增加匹配的誤判率。而精確匹配耗時多效率低，若產(chǎn)生的誤判率過高，精確匹配逐一匹配特征碼將大大影響整個系統(tǒng)的吞吐率。指針產(chǎn)生器的設(shè)計可以檢測匹配的多個子串是否可能對應(yīng)于某一特征碼，同時產(chǎn)生精確匹配中特征碼的地址，提升精確匹配效率。指針產(chǎn)生器設(shè)計如圖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è)特征庫集合中元素個數(shù)為n=7，使用2-FIBF掃描數(shù)據(jù)，每個FIBF掃描2 B，則匹配的前綴長度為4 B。經(jīng)Hash函數(shù)H(b)=bQ^[14]，n個前綴經(jīng)Hash運算后產(chǎn)生的地址、指針對應(yīng)關(guān)系如圖8所示。b是由緩存數(shù)據(jù)表示的1×16向量，Q是一個16×4的隨機向量。

    對于特征編號為“1”的特征，其前綴為“21b8”，經(jīng)Hash函數(shù)運算后得到的Hash值為“1010”，把Hash值作為地址到存儲器中查找對應(yīng)的位置的數(shù)據(jù)，對應(yīng)數(shù)據(jù)為精確匹配中特征碼存儲的地址。若輸入數(shù)據(jù)為“2100”，在FIBF檢測中輸出發(fā)生匹配，此時指針查找器讀取緩存中的“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實現(xiàn)多對少映射，上邊例子使用的Hash函數(shù)由H3算法構(gòu)造，當(dāng)特征集合中元素數(shù)目增多，且字符串?dāng)?shù)據(jù)隨機性比較差的情況下，H₃算法產(chǎn)生的碰撞概率比較大，此時可以采用文獻[15]提出的多IGU（Index Generation Unit）并行方案。IGU的預(yù)處理階段首先使用特征碼中的比特位構(gòu)成二維數(shù)組，數(shù)組中的數(shù)據(jù)對應(yīng)特征碼的地址指針。通過對數(shù)組進行分析，選擇合適的X、Y坐標(biāo)的位進行異或操作，以產(chǎn)生的值作為Y值，使用Y可以唯一地確定指針。對于少部分產(chǎn)生碰撞的數(shù)據(jù)，文獻[15]通過設(shè)計一個額外的IGU存儲器存儲這些數(shù)據(jù)。

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

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

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

3 性能實驗及分析

    實驗選取Clam AV特征庫main.db類中2 000個特征碼，部分匹配關(guān)鍵字為對應(yīng)特征碼的12 B前綴，可接受的誤判率f=0.019 6，根據(jù)式（5）和圖3可計算出當(dāng)k=4時每個FIBF所需的總存儲空間最小為25 093 bit，此時單個向量空間大小為5 019 bit，但是由于存儲器空間大小為2的冪次方，所以k=4時每個Hash函數(shù)的實際占用空間大小為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。數(shù)據(jù)輸入以ASCII形式，向量輸出為高電平表示其對應(yīng)的Hash空間發(fā)生匹配，只有當(dāng)所有的向量空間輸出全為高電平，輸出信號“result”才為高電平。從圖中可以看出“21b800”為檢測出的特征碼前綴。

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

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

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

4 結(jié)論

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

參考文獻

[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é)報，2007，18(1)：117-126.

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

[9] 謝鯤，文吉剛，張大方，等.布魯姆過濾器查詢算法[J].軟件學(xué)報，2009，20(1)：96-108.

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

[11] 駱瀟，郭健，黃河.基于Bloom Filter的多模式匹配優(yōu)化設(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.