一種快速單模式匹配算法的設計與實現

韋安壘 李開科 張榆

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

關鍵詞：模式匹配算法；DPI技術；下一代防火墻

中圖分類號：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算法可保證字符適配后，模式串不回溯，但由于跳轉距離較小，算法平均性能較BM算法要低；BMH2C算法具有較大的跳轉距離，具有較好的平均性能，但由于不能保證字符適配后模式不回溯，在最壞和較壞的情況下，具有較差的性能，其復雜度為O（mn）。結合二者優點，本文提出一種改進的快速單模式匹配算法——BMH2CKMP算法。通過將該算法應用于下一代防火墻，從而測試該算法的是否有效。

2 BMH2CKMP算法

BMH2CKMP算法結合了KMP算法和BMH2C算法二者的優勢，彌補各算法的不足，從而解決既能大幅跳轉又無需回溯的問題。

2.1 算法設計思想

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

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

第二步：預處理對patten串求next數組；

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

2.2 算法描述

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

對于next數組的定義如下：

next[]函數取值如表1所示。

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

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

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

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

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

算法流程如圖1所示。

算法C語言實現如下：

2.3 算法分析

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

算法效果演示分析：

（1）預處理得到next數組

（2）預處理得到Skip跳轉表：

（3）進行模式匹配

（4）匹配結果演示：

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

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

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

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

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

3 實驗

3.1 系統設計

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

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

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

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

3.2 系統測試

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

3.2.1 最大并發連接數

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

改進前防火墻最大并發連接數為700 Mbps，改進后防火墻實際測試最大并發連接數750 Mbps，使用新算法后的防火網最大并發連接數高于使用新算法之前的并發連接數。

3.2.2 吞吐量

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

3.2.3 每秒鐘可打開的TCP連接數

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

4 結束語

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

參考文獻

[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]. 小型微型計算機系統， 2004， 25（3）： 410-3.

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

[6] 閔聯營， 趙婷婷. BM算法的研究與改進 [J]. 武漢理工大學學報（交通科學與工程版）， 2006， 30（3）： 528-30.

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