一種快速單模式匹配算法的設計與實現(xiàn)

韋安壘 李開科 張榆

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

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

中圖分類號：TN915.08 文獻標識碼：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 引言

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

2 BMH2CKMP算法

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

2.1 算法設計思想

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

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

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

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

2.2 算法描述

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

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

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

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

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

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

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

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

算法流程如圖1所示。

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

2.3 算法分析

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

算法效果演示分析：

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

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

（3）進行模式匹配

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

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

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

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

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

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

3 實驗

3.1 系統(tǒng)設計

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

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

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

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

3.2 系統(tǒng)測試

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

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

防火墻最大并發(fā)連接數(shù)代表著防火墻可以支持的最大的網(wǎng)絡同時建立連接的數(shù)量，它的大小表示了防火墻對網(wǎng)絡規(guī)模大小的支持程度，最大并發(fā)連接數(shù)越大意味著支持的網(wǎng)絡規(guī)模越大。使用Smart Bits網(wǎng)絡性能測試儀和WebSuite測試軟件測試防火墻的并發(fā)連接數(shù)指標，測試網(wǎng)絡拓撲如圖5所示。

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

3.2.2 吞吐量

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

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

防火墻每秒鐘能打開的TCP連接數(shù)越多，即意味著防火墻同時處理的請求越多，也就意味著防火墻的速度越快。使用Smart Bits網(wǎng)絡性能測試儀測試防火墻的每秒鐘可打開的TCP連接數(shù)。測試網(wǎng)絡拓撲如圖6所示。

4 結(jié)束語

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

參考文獻

[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]. 小型微型計算機系統(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]. 武漢理工大學學報（交通科學與工程版）， 2006， 30（3）： 528-30.

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