王亞南，徐周波，古天龍

(桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林　541004)

?

基于OBDD的模式匹配算法硬件實(shí)現(xiàn)

王亞南，徐周波，古天龍

(桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004)

針對(duì)模式匹配算法硬件實(shí)現(xiàn)過(guò)程中成本高的問(wèn)題，提出一種基于OBDD的模式匹配算法。該算法通過(guò)OBDD刻畫(huà)所有模式串，利用OBDD技術(shù)的S-刪除規(guī)則與合并規(guī)則簡(jiǎn)化OBDD規(guī)模，并利用FPGA技術(shù)對(duì)OBDD結(jié)構(gòu)進(jìn)行硬件實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，該算法硬件實(shí)現(xiàn)較為簡(jiǎn)單，不消耗CAM資源，并可通過(guò)OBDD簡(jiǎn)化規(guī)則減小電路規(guī)模。

OBDD；FPGA；模式匹配算法；CAM

模式匹配是數(shù)據(jù)結(jié)構(gòu)中的一種基本運(yùn)算，被廣泛應(yīng)用于入侵檢測(cè)、信息檢索等眾多領(lǐng)域。根據(jù)單次匹配的模式串?dāng)?shù)量的不同分為單模式和多模式匹配。早期的模式匹配算法多為單模式匹配，如KMP算法[1]、BM算法等。因單模式匹配算法一次只有一個(gè)模式串參與匹配，匹配效率較低，雖然實(shí)現(xiàn)較為簡(jiǎn)單，但較低的匹配效率只適合模式集較少的匹配判定，限制了單模式匹配算法的應(yīng)用[2]。相比單模式匹配算法，AC算法[3]、WM算法[4]等多模式匹配算法在匹配效率上有很大提高，但遠(yuǎn)不能滿(mǎn)足實(shí)際需求對(duì)模式匹配算法性能的要求。

近年來(lái)，針對(duì)傳統(tǒng)基于軟件實(shí)現(xiàn)的模式匹配算法，研究人員開(kāi)始嘗試進(jìn)行硬件實(shí)現(xiàn)。Park等[5]提出針對(duì)字符串匹配的高效并行硬件算法，利用數(shù)據(jù)流算法開(kāi)發(fā)脈動(dòng)陣列結(jié)構(gòu)，并提出特殊用途超大規(guī)模集成電路設(shè)計(jì)方案。李偉男等[6]對(duì)傳統(tǒng)AC算法與WM算法進(jìn)行了改進(jìn)，并通過(guò)硬件實(shí)例介紹了多模式匹配算法的硬件實(shí)現(xiàn)方法及策略，對(duì)今后多模式匹配算法的發(fā)展趨勢(shì)進(jìn)行了展望。嵩天等[7]提出了一種針對(duì)ACC算法的硬件體系結(jié)構(gòu)，將當(dāng)前狀態(tài)保存至狀態(tài)寄存器，將當(dāng)前緩存狀態(tài)保存至狀態(tài)緩存寄存器，通過(guò)片上或片外存儲(chǔ)器存儲(chǔ)所有轉(zhuǎn)換規(guī)則，根據(jù)當(dāng)前狀態(tài)與當(dāng)前輸入字符查找轉(zhuǎn)換規(guī)則實(shí)現(xiàn)跳轉(zhuǎn)，此算法單硬件結(jié)構(gòu)實(shí)現(xiàn)可達(dá)到11 Gbit/s的匹配速度。

相比傳統(tǒng)基于軟件實(shí)現(xiàn)的模式匹配算法，基于硬件實(shí)現(xiàn)的模式匹配算法速度大大提高，可解決數(shù)據(jù)增加帶來(lái)的處理速度緩慢等問(wèn)題。但基于FPGA等硬件器件的模式匹配算法，因硬件器件的存儲(chǔ)空間有限，難以滿(mǎn)足大規(guī)模模式集對(duì)存儲(chǔ)空間的要求，且FPGA等硬件集成電路芯片中內(nèi)容可尋址存儲(chǔ)器(content addressable memory，簡(jiǎn)稱(chēng)CAM)等存儲(chǔ)的價(jià)格較為昂貴。為滿(mǎn)足大規(guī)模模式匹配算法對(duì)存儲(chǔ)空間的要求，很多基于硬件實(shí)現(xiàn)的模式匹配算法不得不添加外部存儲(chǔ)器，這不僅增加了硬件實(shí)現(xiàn)的復(fù)雜性，還在一定程度上增加了額外開(kāi)支。為此，通過(guò)引入有序二叉決策圖(ordered binary decision diagram，簡(jiǎn)稱(chēng)OBDD)結(jié)構(gòu)及其相關(guān)簡(jiǎn)化技術(shù)，無(wú)需或僅需較少的存儲(chǔ)空間來(lái)實(shí)現(xiàn)模式匹配算法。將模式集整合到OBDD結(jié)構(gòu)中，通過(guò)OBDD的S-刪除規(guī)則與合并規(guī)則，簡(jiǎn)化OBDD結(jié)構(gòu)，最后通過(guò)二選一多路選擇器搭建基于OBDD的硬件電路，實(shí)現(xiàn)模式匹配算法。

1　OBDD

OBDD是一種新型的數(shù)據(jù)結(jié)構(gòu)，是布爾函數(shù)的表述和運(yùn)算中最有效的技術(shù)。有關(guān)OBDD的研究最早可追溯至20世紀(jì)50年代Lee的二叉決策程序與70年代Akers的二叉決策圖的概念[8]。OBDD的定義如下。

定義1[9]布爾函數(shù)f(x1,x2,…,xn)從{0,1}n到{0,1}，變量序?yàn)棣?，利用二叉決策圖表示布爾函數(shù)族#f(x1,x2,…,xn)，若任一有向路徑上的變量x1,x2,…,xn都按變量序π的順序出現(xiàn)，則此BDD即為布爾函數(shù)f(x1,x2,…,xn)的有序二叉決策圖。

定義2[9]u為OBDD上的節(jié)點(diǎn)，fu為從{0,1}n到{0,1}的布爾函數(shù)，滿(mǎn)足：

1)若u是終端節(jié)點(diǎn)，則fu=var(u)。

2)若u是非終端節(jié)點(diǎn)，則

定義3[9]OBDD中，若內(nèi)部節(jié)點(diǎn)滿(mǎn)足：

1)對(duì)于節(jié)點(diǎn)u，low(u)≠high(u)；

2)對(duì)于var(u)=var(v)的不同節(jié)點(diǎn)u、v，low(u)≠low(v)∪high(u)≠high(v)∪low(u)≠low(v)∩high(u)≠high(v)，則稱(chēng)此OBDD為簡(jiǎn)化有序二叉決策圖(reduced ordered binary decision diagram，簡(jiǎn)稱(chēng)ROBDD)。

OBDD或ROBDD為布爾函數(shù)族#f(x1,x2,…,xn)中布爾函數(shù)的多根圖描述，也就是多個(gè)布爾函數(shù)的共享圖形描述，所以，OBDD或ROBDD也稱(chēng)共享二叉決策圖(shared binary decision diagram，簡(jiǎn)稱(chēng)SOBDD)。

布爾函數(shù)f(x1,x2,x3)=x1x2x3，在變量序π：x1

圖1　OBDDFig.1　OBDD

圖2　簡(jiǎn)化OBDDFig.2　Simplified OBDD

任何的OBDD均可利用S-刪除規(guī)則與合并規(guī)則進(jìn)行簡(jiǎn)化，得到簡(jiǎn)化的OBDD。給定變量序π，布爾函數(shù)族#πf(x1,x2,…,xn)中的所有布爾函數(shù)僅有唯一的ROBDD表示。簡(jiǎn)化規(guī)則的主要思想是刪除OBDD中的冗余節(jié)點(diǎn)，使其符合定義3。簡(jiǎn)化規(guī)則包括S-刪除規(guī)則與合并規(guī)則。

規(guī)則1(S-刪除規(guī)則)[9]對(duì)OBDD中的節(jié)點(diǎn)u，若low(u)=high(u)，則刪除節(jié)點(diǎn)u，并將節(jié)點(diǎn)u的父節(jié)點(diǎn)直接連接至low(u)所對(duì)應(yīng)的節(jié)點(diǎn)。

規(guī)則2(合并規(guī)則)[9]對(duì)于OBDD中的節(jié)點(diǎn)u、v，若var(u)=var(v)，low(u)=low(v)，且high(u)=high(v)，則刪除節(jié)點(diǎn)u，并將節(jié)點(diǎn)u的父節(jié)點(diǎn)直接連接至節(jié)點(diǎn)v。

S-刪除規(guī)則與合并規(guī)則如圖3所示。

圖3　簡(jiǎn)化規(guī)則Fig.3　Simplified rules

從圖3可看出，當(dāng)節(jié)點(diǎn)u的2條輸出邊均指向同一節(jié)點(diǎn)w時(shí)，可應(yīng)用規(guī)則1所述的S-刪除規(guī)則刪除節(jié)點(diǎn)u。刪除節(jié)點(diǎn)u并不改變OBDD所表示的布爾函數(shù)。若節(jié)點(diǎn)u、v的標(biāo)記變量相同，且其0、1分支節(jié)點(diǎn)也相同，就可對(duì)節(jié)點(diǎn)u、v應(yīng)用規(guī)則2的合并規(guī)則刪除節(jié)點(diǎn)u或v。刪除任一節(jié)點(diǎn)不會(huì)改變OBDD所表示的布爾函數(shù)。

2　模式集的OBDD表示

利用OBDD刻畫(huà)模式集，首先需要將模式串表示為布爾表達(dá)式。當(dāng)模式集中模式串的最大長(zhǎng)度為m時(shí)，字符編碼表中二進(jìn)制數(shù)位長(zhǎng)為k，n(n=m×k)位二進(jìn)制數(shù)的不同取值即可表示模式集中所有模式串。設(shè)布爾函數(shù)f(x1,x2,…,xn)，變量序π：x1

設(shè)模式集{ab, ac, ad, af, ao, ba, bc, bd, cf, mc, mh, mn}，通過(guò)ASCII碼編碼，將字符相應(yīng)的ASCII碼值轉(zhuǎn)化成二進(jìn)制數(shù)值。對(duì)于布爾函數(shù)f(x1,x2,…,x16)，變量序π：x1

表1　模式串對(duì)應(yīng)的布爾表達(dá)式

圖4　模式集的OBDDFig.4　OBDD of patterns set

3　基于OBDD的模式匹配算法硬件實(shí)現(xiàn)

基于OBDD的模式匹配算法的硬件實(shí)現(xiàn)系統(tǒng)主要包括串轉(zhuǎn)并模塊、移位寄存器模塊、OBDD電路模塊，如圖5所示。串轉(zhuǎn)并模塊的輸入端為被測(cè)試的數(shù)據(jù)(比特流)，輸出端為N位并行輸出，N的大小由字符表的大小決定，如字符表大小為256，只需8位二進(jìn)制數(shù)即可，則N=8。移位寄存器模塊為N位并行輸入，M位并行輸出。其中M=N×k，k為模式集中最長(zhǎng)模式串的長(zhǎng)度，N為步長(zhǎng)。OBDD電路模塊是由FPGA多路選擇器搭建的OBDD結(jié)構(gòu)的電路。

經(jīng)S-刪除規(guī)則與合并規(guī)則簡(jiǎn)化后的OBDD結(jié)構(gòu)，利用二選一多路選擇器搭建OBDD結(jié)構(gòu)的硬件電路。OBDD每個(gè)節(jié)點(diǎn)有2個(gè)分支，二選一多路選擇器符合OBDD節(jié)點(diǎn)的規(guī)則要求。

布爾函數(shù)f(x1,x2,x3)=(x1+x2)·x3，變量序

圖5　基于OBDD的模式匹配算法硬件系統(tǒng)Fig.5　Hardware system of the pattern matching algorithm based on OBDD

π：x1

通過(guò)多路選擇器搭建基于圖6的OBDD結(jié)構(gòu)硬件電路(圖7)。其中：OUT為輸出；MUX為多路選擇器。

圖6　OBDD的簡(jiǎn)化Fig.6　The simplification of OBDD

圖7　OBDD的多路選擇器組合電路Fig.7　Multi-channel selector combinational circuits of OBDD

從圖6可看出，經(jīng)S-刪除規(guī)則與合并規(guī)則簡(jiǎn)化后的OBDD規(guī)模大為減小。由圖7可知，硬件實(shí)現(xiàn)過(guò)程中，所需硬件電路的規(guī)模同樣大為減小，節(jié)省了邏輯門(mén)電路數(shù)量。在基于OBDD的多路選擇器組合電路中，布爾變量值通過(guò)移位寄存器賦值，當(dāng)輸出位OUT為1時(shí)，匹配成功，此時(shí)輸出移位寄存器中相應(yīng)的數(shù)據(jù)為檢測(cè)出存在匹配的位段；當(dāng)輸出位OUT為0時(shí)，不匹配。

4　實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

實(shí)驗(yàn)用Altera公司的Quartus II9.0進(jìn)行硬件仿真，利用verilog HDL語(yǔ)言與原理圖輸入方式，在硬件電路上實(shí)現(xiàn)基于OBDD的模式匹配算法。FPGA芯片選用cyclone系列，時(shí)鐘頻率為200 MHz。利用Quartus II9.0開(kāi)發(fā)環(huán)境中的波形仿真器實(shí)現(xiàn)時(shí)序仿真。時(shí)序仿真如圖8所示。

圖8　時(shí)序仿真Fig.8　Timing simulation

當(dāng)輸入的數(shù)據(jù)流中存在與OBDD結(jié)構(gòu)電路中所包含的某模式串相同時(shí)，匹配標(biāo)志端bool_out輸出高電平，其余時(shí)刻bool_out輸出低電平。

實(shí)驗(yàn)結(jié)果表明，在時(shí)鐘頻率200 MHz，M=8時(shí)，8位數(shù)據(jù)只需一個(gè)時(shí)鐘周期即可完成匹配判定，匹配速度為1.6 Gbit/s。通過(guò)并行處理，算法速度可進(jìn)一步提高k倍(k為最長(zhǎng)模式串長(zhǎng)度)，基于OBDD的模式匹配算法硬件實(shí)現(xiàn)相比其他算法的硬件實(shí)現(xiàn)，在速度方面大體相當(dāng)。但基于OBDD的模式匹配算法硬件實(shí)現(xiàn)的優(yōu)勢(shì)在于，無(wú)需消耗FPGA較為昂貴的CAM，只需通過(guò)構(gòu)建基于OBDD結(jié)構(gòu)的多路選擇器組合電路，即可實(shí)現(xiàn)模式匹配，因此算法結(jié)構(gòu)簡(jiǎn)單，利于硬件實(shí)現(xiàn)。

5　結(jié)束語(yǔ)

針對(duì)模式匹配算法在硬件實(shí)現(xiàn)過(guò)程中所需存儲(chǔ)空間較大的問(wèn)題，將OBDD技術(shù)應(yīng)用到模式匹配算法的硬件實(shí)現(xiàn)過(guò)程中，提出一種針對(duì)硬件實(shí)現(xiàn)的模式匹配算法。通過(guò)OBDD結(jié)構(gòu)表示模式集中所有模式串，進(jìn)一步利用OBDD簡(jiǎn)化規(guī)則，簡(jiǎn)化OBDD結(jié)構(gòu)，并通過(guò)二選一多路選擇器構(gòu)建基于OBDD結(jié)構(gòu)的硬件電路，從而達(dá)到無(wú)需存儲(chǔ)器即可實(shí)現(xiàn)模式匹配算法的目的，且算法實(shí)現(xiàn)過(guò)程較為簡(jiǎn)單。

[1]NAVARRO G,KIMMO F.Average complexity of exact and approximate multiple string matching[J].Theoretical Computer Science,2004,321:283-290.

[2]范洪博，姚念民.一種高速精確單模式串匹配算法[J].計(jì)算機(jī)研究與發(fā)展，2009,46(8):1341-1348.

[3]AHO A V,CORASICK M J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18(6):333-340.

[4]WU S,MANBER U.A fast algorithm for multi-pattern searching[R].Tucson:University of Arizona,1994:1-10.

[5]PARK J H,GEORGE K M.Efficient parallel hardware algorithms for string matching[J].Microprocessors and Microsystems,1999,23(3):155-168.

[6]李偉男，鄂躍鵬，葛敬國(guó)，等.多模式匹配算法及硬件實(shí)現(xiàn)[J].軟件學(xué)報(bào)，2006,17(12):2403-2415.

[7]嵩天，李冬妮，汪東升，等.存儲(chǔ)有效的多模式匹配算法和體系結(jié)構(gòu)[J].軟件學(xué)報(bào)，2013,24(4):1650-1665.

[8]古天龍.一類(lèi)新型抽象數(shù)據(jù)類(lèi)型：有序二叉決策圖[J].桂林電子科技大學(xué)學(xué)報(bào)，2010,30(5):374-388.

[9]古天龍，徐周波.有序二叉決策圖及應(yīng)用[M].北京：科學(xué)出版社，2009:23-50.

編輯：張所濱

Hardware implementation of pattern matching algorithm based on OBDD

WANG Yanan， XU Zhoubo， GU Tianlong

(Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541000, China)

In the process of the hardware implementation of pattern matching algorithm, the cost is high. A pattern matching algorithm based on OBDD is proposed. The algorithm is represented by OBDD for all pattern strings. The size of OBDD is simplified by S-deletion rule and the merging rule, and the hardware implementation of OBDD structure is realized by FPGA technology. Experimental results show that this algorithm is relatively simple and does not consume CAM resource. The circuit size of the algorithm can be reduced by using the simplified OBDD.

OBDD; FPGA; pattern matching algorithm; CAM

2016-03-21

國(guó)家自然科學(xué)基金(61262030,61572146,61363030,U1501252)；廣西自然科學(xué)基金(2015GXNSFAA139285,2014GXNSFAA118354)

古天龍(1964―)，男，山西芮城人，教授，博士，研究方向?yàn)樾问交椒?、符?hào)計(jì)算。E-mail:cctlgu@guet.edu.cn

TP393

A

1673-808X(2016)03-0204-06

引文格式： 王亞南，徐周波，古天龍.基于OBDD的模式匹配算法硬件實(shí)現(xiàn)[J].桂林電子科技大學(xué)學(xué)報(bào)，2016,36(3):204-109.