0 引言

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

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

    基于標(biāo)準(zhǔn)Bloom Filter和改進(jìn)Bloom Filter^[2-7]的匹配方案有很多，例如文獻(xiàn)[8]使用雙Hash的方案,，利用FPGA中的雙端口存儲(chǔ)器實(shí)現(xiàn)特征碼Hash值的存儲(chǔ)和查找,，同時(shí)可以實(shí)現(xiàn)數(shù)據(jù)的在線更新，但是雙Hash方案沒有解決Bloom Filter假陽(yáng)性誤判(即不屬于集合中的元素而誤判為屬于集合中)^[9]問(wèn)題,，較高的錯(cuò)誤率將大大降低系統(tǒng)的可靠性,。文獻(xiàn)[10]提出了一個(gè)基于Bloom Filter和位拆分狀態(tài)機(jī)的多模式分步匹配引擎設(shè)計(jì)方案，可以實(shí)現(xiàn)數(shù)據(jù)流的高速精確檢測(cè),，方案的精確匹配部分使用選擇位狀態(tài)機(jī),，在檢測(cè)時(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,，其向量空間存儲(chǔ)值并非0或1,，而是由計(jì)數(shù)器和編碼值兩部分組成，在匹配中,，通過(guò)這兩部分值可以恢復(fù)匹配位置存儲(chǔ)的數(shù)據(jù),，解決了傳統(tǒng)Bloom Filter假陽(yáng)性誤判問(wèn)題，該方案僅適用于匹配短關(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對(duì)特征碼長(zhǎng)度不進(jìn)行區(qū)分，通過(guò)對(duì)固定長(zhǎng)度特征前綴的高速掃描,，過(guò)濾出可疑數(shù)據(jù),；而后，使用FPGA軟核微處理NiosII^[13]和片外存儲(chǔ)器SDRAM對(duì)數(shù)據(jù)進(jìn)行精確掃描,。

1 Bloom Filter原理

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

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

    Bloom Filter存在假陽(yáng)性誤判，因而,，在應(yīng)用中需要對(duì)查詢誤判率進(jìn)行評(píng)估,，設(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ù)遞減,，但是所需的存儲(chǔ)器總量m′隨k成“√”變化，當(dāng)Hash函數(shù)個(gè)數(shù)k=4時(shí)所需的存儲(chǔ)空間總量最小,。

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

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

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

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

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

    (3)精確匹配引擎對(duì)可疑數(shù)據(jù)進(jìn)行深度過(guò)濾，此過(guò)程由MPU完成,。MPU根據(jù)指針產(chǎn)生器給出的地址讀取特征碼,，使用KMP算法對(duì)文本進(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，檢測(cè)特定長(zhǎng)度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)。對(duì)于有a個(gè)比特的字符串S={s₁,，s₂,，…，s_a},，通過(guò)H3算法構(gòu)造的Hash函數(shù)可以表示為：

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

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

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

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

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

    Hash實(shí)現(xiàn)多對(duì)少映射，上邊例子使用的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ù)對(duì)應(yīng)特征碼的地址指針,。通過(guò)對(duì)數(shù)組進(jìn)行分析,，選擇合適的X、Y坐標(biāo)的位進(jìn)行異或操作,，以產(chǎn)生的值作為Y值,，使用Y可以唯一地確定指針。對(duì)于少部分產(chǎn)生碰撞的數(shù)據(jù),，文獻(xiàn)[15]通過(guò)設(shè)計(jì)一個(gè)額外的IGU存儲(chǔ)器存儲(chǔ)這些數(shù)據(jù),。

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(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引擎的高速分組檢測(cè)[J].軟件學(xué)報(bào),，2007,，18(1)：117-126.

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

[9] 謝鯤,，文吉?jiǎng)?，張大方，?布魯姆過(guò)濾器查詢算法[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.