麥濤濤，潘曉中，李曉策

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

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

麥濤濤，潘曉中，李曉策

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

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

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

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方案沒(méi)有解決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= {c1，c2，…，cn}，其 n個(gè)元素通過(guò) k個(gè)相互獨(dú)立 Hash函數(shù)h1，h2，…，hk映射到長(zhǎng)度為 m的位串向量 V中，Hash函數(shù)的取值范圍為{0，1，…，m-1}。對(duì)字符串c′進(jìn)行檢測(cè)，若輸出值為1，則元素c′是可能需要查找的字符串，否則肯定不是。

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

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為：

式(2)兩側(cè)對(duì)k進(jìn)行求導(dǎo)，令導(dǎo)數(shù)為0，得：

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

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

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

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

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

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)的工作流程如下：

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

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

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

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

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信息。

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

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

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

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

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

指針產(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ī)向量。

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

對(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ī)性比較差的情況下，H3算法產(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è)特征碼，部分匹配為對(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è)出的特征碼前綴。

圖9　FIBF仿真波形圖

實(shí)驗(yàn)使用ALTERA低成本Cyclone II系列的開(kāi)發(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。

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

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

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è)。

[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]吳厚航.愛(ài)上 FPGA開(kāi)發(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.

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

國(guó)家自然科學(xué)基金項(xiàng)目（61402531，61309022）

2015-12-19)

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

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

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

中文引用格式：麥濤濤，潘曉中，李曉策.高效匹配引擎的設(shè)計(jì)與實(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.