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.