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

王亞南，徐周波，古天龍

(桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林　541004)

?

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

王亞南，徐周波，古天龍

(桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林541004)

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

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

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

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

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

1　OBDD

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

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

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

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

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

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

1)對于節(jié)點u，low(u)≠high(u)；

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

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

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

圖1　OBDDFig.1　OBDD

圖2　簡化OBDDFig.2　Simplified OBDD

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

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

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

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

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

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

2　模式集的OBDD表示

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

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

表1　模式串對應的布爾表達式

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

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

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

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

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

圖6　OBDD的簡化Fig.6　The simplification of OBDD

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

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

4　實驗驗證及結(jié)果分析

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

圖8　時序仿真Fig.8　Timing simulation

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

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

5　結(jié)束語

針對模式匹配算法在硬件實現(xiàn)過程中所需存儲空間較大的問題，將OBDD技術應用到模式匹配算法的硬件實現(xiàn)過程中，提出一種針對硬件實現(xiàn)的模式匹配算法。通過OBDD結(jié)構(gòu)表示模式集中所有模式串，進一步利用OBDD簡化規(guī)則，簡化OBDD結(jié)構(gòu)，并通過二選一多路選擇器構(gòu)建基于OBDD結(jié)構(gòu)的硬件電路，從而達到無需存儲器即可實現(xiàn)模式匹配算法的目的，且算法實現(xià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].計算機研究與發(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]李偉男，鄂躍鵬，葛敬國，等.多模式匹配算法及硬件實現(xiàn)[J].軟件學報，2006,17(12):2403-2415.

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

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

[9]古天龍，徐周波.有序二叉決策圖及應用[M].北京：科學出版社，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

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

古天龍(1964―)，男，山西芮城人，教授，博士，研究方向為形式化方法、符號計算。E-mail:cctlgu@guet.edu.cn

TP393

A

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

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