高效匹配引擎的設(shè)計與實現(xiàn)*

麥濤濤，潘曉中，李曉策

(武警工程大學 電子技術(shù)系，陜西 西安710086）

高效匹配引擎的設(shè)計與實現(xiàn)*

麥濤濤，潘曉中，李曉策

(武警工程大學 電子技術(shù)系，陜西 西安710086）

針對軟件模式匹配引擎速度慢、占用系統(tǒng)資源大的問題，提出了一種基于 Bloom Filter的 FIBF結(jié)構(gòu)，結(jié)合FPGA NIOSII微處理器（MUP），設(shè)計了軟硬核相結(jié)合的匹配引擎方案。引擎通過FIBF過濾過濾掉大部分正常數(shù)據(jù)，將過濾出的可疑字符串輸入到NIOSII軟核進行精確匹配，兩者之間通過一個指針產(chǎn)生器連接，整個系統(tǒng)以流水線方式工作。FIBF結(jié)構(gòu)資源消耗低，n-FIBF并行處理，系統(tǒng)引擎可以達到較高的吞吐率。實驗表明，在使用相同資源的情況下，本方案系統(tǒng)吞吐率要優(yōu)于其他算法。

FIBF；指針產(chǎn)生器；NIOSII微處理器；流水線方式

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ù)查找的同時可以降低存儲資源的消耗。

基于標準 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ù)器和編碼值兩部分組成，在匹配中，通過這兩部分值可以恢復匹配位置存儲的數(shù)據(jù)，解決了傳統(tǒng)Bloom Filter假陽性誤判問題，該方案僅適用于匹配短關(guān)鍵字。

本文將 Bloom Filter與FPGA系統(tǒng)軟核相結(jié)合，設(shè)計了一種資源消耗少、匹配速度快的軟硬核結(jié)合的分步匹配引擎方案。在系統(tǒng)部分匹配中，文本基于標準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表的鏈式存儲結(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= {c1，c2，…，cn}，其 n個元素通過 k個相互獨立 Hash函數(shù)h1，h2，…，hk映射到長度為 m的位串向量 V中，Hash函數(shù)的取值范圍為{0，1，…，m-1}。對字符串c′進行檢測，若輸出值為1，則元素c′是可能需要查找的字符串，否則肯定不是。

圖1　BF結(jié)構(gòu)圖

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

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

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

式(2)兩側(cè)對k進行求導，令導數(shù)為0，得：

當k=kmin時，，此時元素出現(xiàn)誤判的最小概率fmin為：

圖2　誤判率f與Hash個數(shù)k的關(guān)系

若設(shè)計時對k個Hash函數(shù)，每個Hash函數(shù)使用獨立的向量，則向量中某比特位為1的概率，此時元素出現(xiàn)誤判的概率為：

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

圖3　Hash個數(shù)k與單個向量空間大小m及總向量空間大小m′關(guān)系圖

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

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

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

圖4　過濾系統(tǒng)設(shè)計模型

(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.2FIBF設(shè)計

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

圖5　FIBF結(jié)構(gòu)圖

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

圖6　3-FIBF并行部分匹配引擎模型

在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)造方案H3很適合硬件實現(xiàn)。對于有 a個比特的字符串 S={s1，s2，…，sa}，通過H3算法構(gòu)造的 Hash函數(shù)可以表示為：

式中，“·”為與門，“⊕”為異或門，q表示一個 a×a′的隨機數(shù)陣列。矩陣行數(shù)a對應(yīng)輸入字符串的比特位數(shù)，列數(shù) a′對應(yīng)Hash值的位數(shù)，a′的值由 Bloom Filter中向量空間大小決定。

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

當 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所示。

圖7　指針產(chǎn)生器

指針產(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的隨機向量。

圖8　特征前綴與Hash值、指針對應(yīng)關(guān)系

對于特征編號為“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)造，當特征集合中元素數(shù)目增多，且字符串數(shù)據(jù)隨機性比較差的情況下，H3算法產(chǎn)生的碰撞概率比較大，此時可以采用文獻[15]提出的多 IGU（Index Generation Unit）并行方案。IGU的預處理階段首先使用特征碼中的比特位構(gòu)成二維數(shù)組，數(shù)組中的數(shù)據(jù)對應(yīng)特征碼的地址指針。通過對數(shù)組進行分析，選擇合適的X、Y坐標的位進行異或操作，以產(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個特征碼，部分匹配為對應(yīng)特征碼的12 B前綴，可接受的誤判率 f=0.019 6，根據(jù)式（5）和圖3可計算出當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ā)生匹配，只有當所有的向量空間輸出全為高電平，輸出信號“result”才為高電平。從圖中可以看出“21b800”為檢測出的特征碼前綴。

圖9　FIBF仿真波形圖

實驗使用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。

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

表1　本文算法與其他算法性能比較

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].電信科學，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].軟件學報，2007，18(1)：117-126.

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

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

[10]劉威，郭淵博，黃鵬.基于 Bloom Filter的多模式匹配引擎[J].電子學報，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)和你一起學NIOS II[M].北京：北京航空航天大學出版社，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.

The design and implementation of high-performance matching engine

Mai Taotao，Pan Xiaozhong，Li Xiaoce
(Department of Electronic Technology，Engineering College of the Chinese Armed Police Force，Xi′An 710086，China)

According to the problem that the pattern matching engine based on software having slowly matching-speed and occupying large system resources，this paper proposed a FIBF structure based on Bloom Filter.Using the FPGA NIOSII microprocessor (MUP)，a matching engine combination of hard and soft core is designed.Though FIBF,the engine filtered out most of the normal data,then sent the suspicious string to the precise matching module.The FIBF module and the precise matching module were connected together by an index generator.The whole system was performed in pipeline method.The FIBF has low consumption of hardware resource.N-FIBF process in parallel can achieve high system throughput.Simulation results show that this engine is superior to other algorithms by using the same resources.

FIBF；index generator；NIOSII MUP；pipeline method

TP391

A

10.16157/j.issn.0258-7998.2016.05.024

國家自然科學基金項目（61402531，61309022）

2015-12-19)

麥濤濤(1992-)，男，碩士研究生，主要研究方向：嵌入式系統(tǒng)、網(wǎng)絡(luò)安全。

潘曉中(1964-)，男，教授，主要研究方向：信息研究與安全。

李曉策（1991-），男，碩士研究生，主要研究方向：可信計算。

中文引用格式：麥濤濤，潘曉中，李曉策.高效匹配引擎的設(shè)計與實現(xiàn)[J].電子技術(shù)應(yīng)用，2016，42(5)：85-89.

英文引用格式：Mai Taotao，Pan Xiaozhong，Li Xiaoce.The design and implementation of high-performance matching engine[J]. Application of Electronic Technique，2016，42(5)：85-89.