韋安壘 李開科 張榆

摘 要：基于已有的單模式匹配算法，論文設(shè)計(jì)了一種改進(jìn)的快速單模式匹配算法，實(shí)現(xiàn)了一個(gè)基于DPI技術(shù)的下一代防火墻系統(tǒng)，并將改進(jìn)后的算法應(yīng)用于該系統(tǒng)。測(cè)試發(fā)現(xiàn)，新設(shè)計(jì)的下一代防火墻的性能和功能都得到了優(yōu)化。

關(guān)鍵詞：模式匹配算法；DPI技術(shù)；下一代防火墻

中圖分類號(hào)：TN915.08 文獻(xiàn)標(biāo)識(shí)碼：C

Design and implementation of a fast single pattern matching algorithm

Abstract： Based on the existing single pattern matching algorithm， a next generation firewall system based on DPI technology is designed and implemented. And the improved algorithm is applied to this system. Tests have found that the performance and functionality of the next generation firewall are optimized.

Key words： pattern matching algorithm； DPI technology； next generation firewall

1 引言

針對(duì)KMP算法可保證字符適配后，模式串不回溯，但由于跳轉(zhuǎn)距離較小，算法平均性能較BM算法要低；BMH2C算法具有較大的跳轉(zhuǎn)距離，具有較好的平均性能，但由于不能保證字符適配后模式不回溯，在最壞和較壞的情況下，具有較差的性能，其復(fù)雜度為O（mn）。結(jié)合二者優(yōu)點(diǎn)，本文提出一種改進(jìn)的快速單模式匹配算法——BMH2CKMP算法。通過將該算法應(yīng)用于下一代防火墻，從而測(cè)試該算法的是否有效。

2 BMH2CKMP算法

BMH2CKMP算法結(jié)合了KMP算法和BMH2C算法二者的優(yōu)勢(shì)，彌補(bǔ)各算法的不足，從而解決既能大幅跳轉(zhuǎn)又無需回溯的問題。

2.1 算法設(shè)計(jì)思想

KMP算法復(fù)雜度為O（n），可保證字符適配后，模式串不回溯，則在最壞情況（模式串位于文本串的末尾處）下，具有較高的性能。但由于跳轉(zhuǎn)距離較小，算法平均性能較BM算法要低。BM算法及其改進(jìn)算法具有較大的跳轉(zhuǎn)距離，具有較好的平均性能，但由于不能保證字符適配后模式不回溯，在最壞和較壞的情況下，具有較差的性能，其復(fù)雜度為O（mn）。本文結(jié)合KMP于BMH2C算法各自的優(yōu)勢(shì)提出一種新的單模式匹配算法BMH2CKMP算法。BMH2CKMP算法的設(shè)計(jì)思想是：

第一步：以BMH2C算法為基礎(chǔ)，將其修改為正向匹配；

第二步：預(yù)處理對(duì)patten串求next數(shù)組；

第三步：模式匹配時(shí)，若字符失配，則判斷跳躍值為正向還是負(fù)向。正向則選擇跳躍，獲取最大位移，負(fù)向則查找next數(shù)組，挪動(dòng)j的位置，來強(qiáng)制i不回溯。

2.2 算法描述

在KMP算法中，為了確保在字符失配后，下次匹配時(shí)j的位置，引入了next數(shù)組，next[j]的值表示P[0...j-1（不含j本身）]中最長的后綴等于前綴的長度。

對(duì)于next數(shù)組的定義如下：

next[]函數(shù)取值如表1所示。

即next[j]=k>0時(shí)，表示P[0...k-1]=P[j-k，j-1].

因此KMP算法的思想就是：在匹配過程中，若發(fā)生不匹配的情況，如果next[j]>=0，則目標(biāo)串的指針i不變，將模式串的指針j移動(dòng)到next[j]的位置繼續(xù)進(jìn)行匹配；若next[j]=-1，則將i右移1位，并將j置0，繼續(xù)進(jìn)行比較，復(fù)雜度為O（n）。

在BMH2C這個(gè)算法中，我們將與模式的最后一個(gè)字符相對(duì)應(yīng)的文本字符及其下一個(gè)字符作為一個(gè)子串，當(dāng)子串在模式中出現(xiàn)時(shí)，則模式向右移，使得該子串與它在模式中最右邊的出現(xiàn)對(duì)齊；否則，模式右移時(shí)，直接跳過這個(gè)子串，即右移量為m+1。

由于使用兩個(gè)字符來決定右移量，所以用二維數(shù)組來表示偏移量數(shù)組skip[char1][char2]，在數(shù)組初始化時(shí)，第一步就將二維數(shù)組的值全部設(shè)置為m+1。同時(shí)還考慮到一種特殊情況，即當(dāng)子串S[i]S[i+1]的后一個(gè)字符S[i+1]與模式的第一個(gè)字符P[0]相同時(shí)，雖然子串S[i]S[i+1]不在模式中出現(xiàn)，但如果右移m+1很可能漏掉一種匹配情況，因此只應(yīng)該右移m，使模式的第一個(gè)字符P[0]與子串的后一個(gè)字符S[i+1]對(duì)齊。因此我們?cè)诔跏蓟牡诙骄蛯?duì)skip數(shù)組的值做了修正，將skip[i][p[0]]置為m。初始化的第三步是為模式串中出現(xiàn)的所有子串設(shè)置相應(yīng)的右移量。由于BMH2C算法不能確保j不回溯，所以復(fù)雜度為O（mn）。

本算法結(jié)合KMP和BMH2C算法各自的優(yōu)勢(shì)，初始化構(gòu)建skip和next數(shù)組，匹配時(shí)，文本串S與模式串P左對(duì)齊，然后依次匹配字符。失配后，查找skip數(shù)組，獲取位移。此時(shí)判斷位移為正還是負(fù)。若位移為正，則按位移跳轉(zhuǎn)。若位移為負(fù)，則查詢next數(shù)組，獲取新位移。直至匹配成功或到文本串末尾為止。由于next數(shù)組位移恒為正，則可保證該算法的j值永不回溯，盡量以最大位移跳轉(zhuǎn)，且復(fù)雜度為O（n）。

算法流程如圖1所示。

算法C語言實(shí)現(xiàn)如下：

2.3 算法分析

BMH2CKMP算法基于KMP和BMH2C算法的優(yōu)勢(shì)，實(shí)現(xiàn)一種更加快速的單模式匹配算法，進(jìn)一步提升模式匹配速度，應(yīng)用于下一代防火墻DPI技術(shù)，可進(jìn)一步提升下一代防火墻的工作效率。

算法效果演示分析：

（1）預(yù)處理得到next數(shù)組

（2）預(yù)處理得到Skip跳轉(zhuǎn)表：

（3）進(jìn)行模式匹配

（4）匹配結(jié)果演示：

由以上演示過程我們可以得出幾個(gè)結(jié)論：

（1）最好情況下，BMH2C算法復(fù)雜度O（n），性能要好于KMP（復(fù)雜度O（m+n））算法；新算法與BMH2C算法速度幾乎一致；

（2）最壞情況下，BMH2C算法由于i的回溯，復(fù)雜度為O（mn）性能低于KMP算法；新算法與KMP算法速度幾乎一致；

（3）一般情況下，新算法的復(fù)雜度為O（n），性能最高；

（4）新算法性能在各種情況下總是優(yōu)于或等于兩種算法。

3 實(shí)驗(yàn)

3.1 系統(tǒng)設(shè)計(jì)

下一代防火墻系統(tǒng)系統(tǒng)由帳戶管理、系統(tǒng)管理、安全策略管理、日志管理、安全檢測(cè)、網(wǎng)絡(luò)計(jì)費(fèi)、VPN虛擬專網(wǎng)等七大部分組成，其中包括了網(wǎng)絡(luò)配置、路由管理、IP-MAC綁定、規(guī)則配置等多個(gè)功能模塊。

（1）系統(tǒng)物理架構(gòu)如圖2所示，用戶使用瀏覽器跟HTTP服務(wù)器雙向交互，HTTP服務(wù)器聯(lián)通防火墻用戶管理接口，用戶無需和防火墻底層結(jié)構(gòu)打交道，通過瀏覽器可以直接訪問管理防火墻。

（2）系統(tǒng)程序架構(gòu)如圖3所示，各個(gè)功能模塊間通過用戶接口相互協(xié)作，共同完成防火墻系統(tǒng)功能。

（3）系統(tǒng)邏輯流程如圖4所示，防火墻系統(tǒng)包括賬戶管理、系統(tǒng)管理、安全檢測(cè)、日志管理、安全策略、網(wǎng)絡(luò)計(jì)費(fèi)和虛擬專網(wǎng)等七大功能模塊。其中系統(tǒng)管理和安全策略模塊又分為多個(gè)子功能模塊。

3.2 系統(tǒng)測(cè)試

測(cè)試硬件條件：下一代防火墻一臺(tái)（配置為：處理器Intel Core I3-4160，CPU主頻3.6G，內(nèi)存DDR3 8G，硬盤SSD120G，接口數(shù)8*GE RJ45、4*GE SFP），Win2000 服務(wù)器三臺(tái)，100MbpsHub一臺(tái)，網(wǎng)絡(luò)連接均為100Mbps以太網(wǎng)。本節(jié)主要對(duì)下一代防火墻的最大并發(fā)連接數(shù)、吞吐量、每秒TCP新建連接數(shù)等性能指標(biāo)進(jìn)行測(cè)試。

3.2.1 最大并發(fā)連接數(shù)

防火墻最大并發(fā)連接數(shù)代表著防火墻可以支持的最大的網(wǎng)絡(luò)同時(shí)建立連接的數(shù)量，它的大小表示了防火墻對(duì)網(wǎng)絡(luò)規(guī)模大小的支持程度，最大并發(fā)連接數(shù)越大意味著支持的網(wǎng)絡(luò)規(guī)模越大。使用Smart Bits網(wǎng)絡(luò)性能測(cè)試儀和WebSuite測(cè)試軟件測(cè)試防火墻的并發(fā)連接數(shù)指標(biāo)，測(cè)試網(wǎng)絡(luò)拓?fù)淙鐖D5所示。

改進(jìn)前防火墻最大并發(fā)連接數(shù)為700 Mbps，改進(jìn)后防火墻實(shí)際測(cè)試最大并發(fā)連接數(shù)750 Mbps，使用新算法后的防火網(wǎng)最大并發(fā)連接數(shù)高于使用新算法之前的并發(fā)連接數(shù)。

3.2.2 吞吐量

防火墻吞吐量是以待測(cè)設(shè)備不丟棄數(shù)據(jù)包為前提的最大速率，吞吐量越大意味著防火墻的性能越高。為了全面衡量防火墻的吞吐能力，按照RFC建議，采用雙向測(cè)試，整個(gè)測(cè)試時(shí)長為120秒，并設(shè)置多流的情況進(jìn)行吞吐率測(cè)試。多流設(shè)置為雙向、100對(duì)流、UDP（即內(nèi)、外網(wǎng)的地址共200個(gè)且互不相同），源和目標(biāo)地址都同時(shí)變化，即在防火墻的狀態(tài)表內(nèi)會(huì)存在200個(gè)狀態(tài)連接。使用Smart Bits網(wǎng)絡(luò)性能測(cè)試儀和SmartFlow測(cè)試軟件測(cè)試防火墻的雙向吞吐量指標(biāo)。預(yù)計(jì)吞吐量：64字節(jié)幀長500Mbps，512字節(jié)幀長4Gbps，1518字節(jié)幀長10Gbps，并且規(guī)則數(shù)對(duì)吞吐量的影響應(yīng)該小于2%。實(shí)際測(cè)試結(jié)果如表2所示。

3.2.3 每秒鐘可打開的TCP連接數(shù)

防火墻每秒鐘能打開的TCP連接數(shù)越多，即意味著防火墻同時(shí)處理的請(qǐng)求越多，也就意味著防火墻的速度越快。使用Smart Bits網(wǎng)絡(luò)性能測(cè)試儀測(cè)試防火墻的每秒鐘可打開的TCP連接數(shù)。測(cè)試網(wǎng)絡(luò)拓?fù)淙鐖D6所示。

4 結(jié)束語

針對(duì)KMP算法跳轉(zhuǎn)距離較小以及BMH2C算法不能保證字符適配后模式不回溯的問題，本文設(shè)計(jì)了一種快速的單模式匹配算法——BMH2CKMP算法，并應(yīng)用于下一代防火墻，通過測(cè)試可以發(fā)現(xiàn)。本文設(shè)計(jì)的使用了改進(jìn)后的模式匹配算法的下一代防火墻從吞吐量、最大并發(fā)連接數(shù)、每秒新建連接數(shù)等關(guān)鍵性能指標(biāo)均優(yōu)于改進(jìn)前的防火墻。

參考文獻(xiàn)

[1] MORRIS J H， PRATT V R. A linear pattern-matching algorithm [J]. 1970，

[2] KNUTH D E， JR J H M， PRATT V R. Fast Pattern Matching in Strings [J]. 1974， 6（2）： 323-10.

[3] DENNING D E. An Intrusion-Detection Model [M]. IEEE Press， 1987.

[4] 錢屹， 侯義斌. 一種快速的字符串匹配算法 [J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2004， 25（3）： 410-3.

[5] BOYER R S， MOORE J S. A fast string searching algorithm， F， 1977 [C].

[6] 閔聯(lián)營， 趙婷婷. BM算法的研究與改進(jìn) [J]. 武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版）， 2006， 30（3）： 528-30.

[7] 燕紅文. 基于Snort的改進(jìn)BMH單模式匹配算法研究 [J]. 計(jì)算機(jī)工程與應(yīng)用， 2012， 48（31）： 78-81.