多模式匹配及其改進算法在協議識別中的應用

朱姣姣，葉 猛

(1.光纖通信技術和網絡國家重點實驗室，湖北 武漢 430074;2.武漢郵電科學研究院通信與信息系統，湖北 武漢 430074;3.武漢虹旭信息技術有限責任公司安全產品部，湖北 武漢 430074)

隨著互聯網的飛速發展，網絡信息安全［1］與對抗已經成為網絡信息時代的一個至關重要的問題。為了能夠準確地對網絡上的內容進行監控，就需要搞清楚網絡上傳輸的數據包協議類型，但在目前，TCP/IP協議體系下的網絡中，若要弄清楚數據包的協議類型，就必須要能夠準確地識別數據包的應用層協議類型。而傳統的采用端口的協議識別［2］對于采用動態端口進行通信卻力所不能及，由于模式匹配算法檢測原理簡單易實現、實時性好、準確率高而備受廣大軟件愛好者喜愛，且技術上已經相對成熟，在協議識別領域得到了廣泛應用，基于以上分析，本文重點討論多模式匹配算法，以及其改進算法在協議識別中的應用，并分析模式匹配算法的今后研究方向。

1 模式匹配算法

單模式匹配算法是指在文本串中一次只對一個模式進行匹配;多模式匹配算法則可同時對多個模式進行匹配，在很大程度上提高了匹配效率，且多模式匹配算法同樣也適用于單模式的情況。

1.1 單模式匹配算法

常用的單模式匹配算法有BF算法、KMP算法、BM算法［3］，下面簡要分析這幾種算法。

BF算法是最早最簡單的單模匹配算法，其特點是直觀、簡單，但涉及多次回溯，算法效率極低。

無需回溯指示文本串的指針是KMP算法的最大優勢，其充分利用部分已匹配字符，將模式串盡可能向右滑動一段距離。但KMP算法存在著重復比較的缺陷。

BM算法基本思想是先對模式串進行預處理，當存在不匹配時，通過采用壞字符規則和好后綴規則，來計算模式串的偏移值，取兩者中的較大值，實現跳躍式的遍歷匹配。BM算法在單模式匹配中效率很高，但BM算法使用了兩個數組，預處理開銷大，計算兩個偏移量的過程也很復雜。

針對單模式匹配算法，假如要匹配多個模式，則有幾個模式，那么就需要進行幾趟遍歷，在效率上是很低的。而多模式匹配算法一次遍歷則可匹配出多個模式，因此，根據多模式匹配算法所占有的優勢，將其應用于協議識別中。

1.2 AC多模式匹配算法

AC算法［4］是基于應用層報文內容實時分析的核心算法。這種簡單有效的算法用來在一串文本中確定給定的一組關鍵字在文本中發生的頻度，它具有匹配速度快、占用CPU少、適合海量數據的網絡環境等優點。

AC算法的基本思想是在處理階段分別建立3個函數，即轉向函數(goto)、失效函數(fail)以及輸出函數(output)，由此形成一個樹型有限自動機;在搜索查找階段，互相交叉使用以上3個函數，然后進行掃描文本，可定位出關鍵字在文本中的所有出現位置。

算法描述:構造P={P1，P2，…，Pk}對應的 k樹。首先，從唯一的根節點開始;然后，通過添加一條從根節點出發的路徑的方式，依次插入每一個模式Pi。新的節點和邊被插入到K樹中，以致產生了一條能拼寫出關鍵字Pi的路徑。在路徑的終點存儲Pi的標識i，關鍵字Pi會被添加到輸出函數中。

1.2.1 生成樹型有限自動機

例如，模式集{at，ater，eat，a＆e}的樹型有限自動機，轉向函數goto如圖1所示。

圖1 轉向函數goto示意圖

失效函數fail和輸出函數output如表1所示。

表1 失效函數fail和輸出函數output

1.2.2 生成確定有限自動機

由以上3個函數生成的狀態樹為不確定有限狀態機(NFA)，當發現匹配失敗后，需要通過fail函數來完成狀態跳轉，使用確定有限狀態機(DFA)，通過合并fail函數和goto函數，生成新DFA。利用這個確定的有窮自動機可以減少狀態轉移的次數，使得效率得到一定的提高。例如在狀態1下輸入字符e:NFA中，首先跳轉至狀態0，再在0狀態下輸入字符e，跳轉至狀態5，需查詢2次狀態表;DFA中，直接跳轉至狀態5，僅需查詢1次狀態表即可。

2 AC多模式匹配算法的改進

由于AC算法不能實現跳躍式搜索，研究者據此提出了多種基于AC的改進算法。Commentz－Walter提出一種結合AC和BM的算法(簡稱CW算法［5］)，該算法將BM算法跳躍思想應用于多模式匹配中，匹配效率較高。Jang－Jong Fan和Keh－Yih SuCrochemore結合RF算法給出的 Dawg－Match 算法性能更優(簡稱 Dawg 算法［6］)，王永成通過反向構建goto函數來實現模式匹配，該算法從右到左進行模式串比較，采取連續跳躍的思想，在匹配過程中盡可能跳過多的字符(簡稱Wang算法［7］)。

另外針對AC算法對內存需求大的問題，研究者們也提出了多種快速和高效存儲的優化算法，Norton［8］等提出了 Banded－Row Forma(帶狀行格式)和Sparse－Row Format(稀疏行格式)的稀疏存儲格式。Tuck等采用位圖壓縮和路徑壓縮方法來減小自動機內存消耗，改善了儲存性能。但均可能不同程度地引起匹配性能的下降。

在存在短模式串的情況下，CW算法、Dawg算法以及Wang算法的匹配性能會急劇下降，平均每字符檢查的次數驟然增加，比不上AC算法的效率。

針對這一問題，本文提出一種基于AC的多模式匹配改進算法，其關鍵技術在于它不僅利用匹配過程中的“壞字符”信息，盡可能跳躍更多的字符，還利用模式匹配的信息，增加跳躍的步長。本文的算法基于這樣一個前提，短模式串比長模式串匹配概率更高，且以更高的概率優先命中。

2.1 預處理階段

算法的預處理階段包括構建模式串集合的AC狀態機，以及跳躍表shift。

AC狀態機是一個有限狀態自動機(DFSA)，可描述為(Q，δ，f，s0，T)。其中Q表示狀態機中狀態的有限集合，δ表示狀態轉移函數，f表示失配狀態轉移函數，s0表示初始狀態，T表示匹配的狀態。在具體實現中，可以通過消除”壞字符”回溯取消f，使得δ對任何輸入的字符轉移到非空狀態(包括s0)。這樣AC狀態機簡化為(Q，δ，s0，T)，圖 2 表示了一個模式集合 P={aabbaa，bbaabb，abb，aa}對應的狀態機，狀態上方表示輸出的模式集合output。

構建模式子集的shift表之前，首先按照模式串的長度將所有的模式分為L個相交的子集。給定P=p1，p2，…，pm，計算集合 SL={distinct|pi|，1≤i≤m}，有SL=L，則 SL 可進一步記為 SL={l1，l2，…，lL}。令 SL={pi，|pi|=l，1≤i≤m}，顯然有 ?pi∈SL，≡l，且在預處理階段pi的狀態均是未匹配的。

圖2 模式集合P的AC自動機

令集合 Setj={pi，|pi|≥lj，1≤i≤m}，1≤j≤L，這樣就得到了L個相交模式集合的子集，且Setj－Set1={|pi|=lj－1}，2≤j≤L。從QS算法的描述可知壞字符qsBc表定義為

式中:c∈Σ，p為任意模式串。而在多模式匹配算法情況下shift表可定義為

式中:c∈Σ，1≤j≤L。

設 P={aabbaa，bbaabb，abb，aa}，將 P 劃分為{aabbaa，bbaabb}，{aabbaa，bbaabb，abb，aa}，{aabbaa，bbaabb，abb}3個子集，且最大跳躍值分別為3，4和7。

此外還需要將每一個存在output輸出的狀態做一個標記j，決定模式串屬于哪一個Setj可以加快跳躍的判斷。形式描述為{j，max(|output|)=lj}，其中output為節點輸出的模式串集合，如果使用鏈表存儲的話，則output指向第一個模式串，output－＞next指向下一個模式串，直到next域指向NULL。具體實現可以規定|output|≥|output－＞next|≥…≥|ε|，則有 max(|output|)=|output|。

設置所有存在output輸出的節點所屬的集合下標的算法采用了深度優先的遍歷方式，其中δ為構建狀態機后得到的狀態轉移函數。算法描述如下:

2.2 搜索階段

搜索算法結合了AC算法和QS算法的技術。在QS算法中，比較窗口內比較次序可以是任意的，一旦發生了失配的情況，可根據左鄰比較窗口的第一個字符決定下一個比較窗口跳躍的距離。本算法采用了由左往右的方式比較模式串，并依次讀入字符實現AC狀態的轉移。

算法在比較的過程中，如果某個短模式的集合匹配成功，則使用在預處理中計算的新的shift表，可以預期字符跳躍距離將動態增加，并能以更高的匹配速度處理余下的文本串。算法描述如下，其中T表示目標文本串，size表示目標文本串的長度。

下面舉例說明，如模式集合P={aabbaa，bbaabb，abb，aa}，目標文本串T=aabbaxxxaabbaa。

第一個比較窗口初始大小為2，如圖3所示。

圖3 比較窗口

直到遇到字符x，此時已匹配了{abb，aa}，尚未匹配的模式集合為{aabbaa，bbaabb}，窗口滑動 shift［x，2］=8，且窗口動態增加到6，如圖4所示。

圖4 比較窗口

比較一直到文本T結束，模式{aabbaa}被匹配。算法總共比較了12個字符。

3 實驗分析

測試環境是編譯器gcc version 4.1.2，優化開關全部打開，CPU Pentium III 800 MHz，內存為256 Mbyte，操作系統為Linux 2.6.40，測試文本T為30 Mbyte文本串。選取AC算法、去掉fail的AC算法、Wang算法、CW算法作為比較對象。

1)模式數量一定，模式長度的變化對匹配速度的影響如圖5所示，圖5中給出的模式數量固定為100個，可預先在模式集合中設置一些短模式串。

圖5 不同模式長度下算法的匹配速度

2)模式長度一定，模式個數的變化對匹配速度的影響如圖6所示，圖6中給出的模式長度固定為10 byte。

圖6 不同模式數量下算法的匹配速度

測試結果證明圖5在模式集合中存在長度較短的模式情況時，本文的算法能夠顯著抵抗由此引起的性能衰減。圖6驗證了本算法隨著模式個數的增加，匹配速度不會出現陡然惡化的情況。綜合實驗的結果，可以得出在大多數情況下本文的算法相比其他算法有最好的匹配速度，匹配效果不受模式數目的限制，抗短模式影響比較好。

4 多模式匹配在協議識別中的應用

通過對常見網絡協議的特征進行分析或者查閱某應用層協議公開的RFC文檔，提取出協議的特征信息，作為鑒別應用層協議網絡數據流的標識。每種應用的分組中都攜帶有特定的報文信息，一般是幾個字節長的固定字段，例如，SMTP協議報文中含有RCPT TO，MAIL等特征信息，根據此特征進行模式匹配，由此判斷出該報文是屬于哪種網絡協議的應用。根據多模式匹配算法，對某種協議所具有的關鍵字建立一棵模式樹，一個規則表示一個協議，一個規則對應一個模式集合，在文本串中通過模式匹配進行協議識別，當某個規則中的所有模式都被找到時，再繼續檢查報文是否滿足其他如IP限制、端口限制等條件，只有這些都滿足，才說明這個報文完全匹配這個規則。

5 小結

隨著新的應用協議不斷出現，需要不斷改進模式匹配算法以提高其在協議識別中的準確性和高效性。本文主要提出了一種基于AC的多模式匹配改進算法，利用匹配過程中“壞字符”信息，盡可能跳躍更多的字符和模式匹配信息，動態增加跳躍的步長。這種算法能較好地抵抗短模式引起的性能衰減。本文的算法可以繼續分析空間的復雜性，以及壓縮狀態轉移表對性能的影響。

網絡帶寬的不斷增加給網絡安全技術帶來巨大的挑戰。協議識別作為網絡安全技術的一個重點，提出了更高的要求。雖然協議識別可以采用很多技術，但模式匹配算法仍然是目前的主流協議識別技術。因此如何繼續改進模式匹配來提高匹配速度，成為今后研究協議識別技術的一個關鍵，這里可以從以下幾個方面著手:一是將各種模式匹配算法相結合;二是模式匹配算法與其他智能方法的結合;三是對模糊匹配的深入研究。

［1］楊明，孫洪峰.信息與因特網絡安全防范技術［J］.電視技術，2003，27(1):30－32.

［2］陳亮，龔儉，徐選.應用層協議識別算法［J］.計算機科學，2007，34(7):73－75.

［3］冉占軍，姚全珠，王曉峰，等.模式匹配算法在入侵檢測中的應用［J］.現代電子技術，2009(2):63－67.

［4］AHO A C，CORASICK M J.Efficient string matching:an aid to bibliographic search［J］.Communications of the ACM，1975，18(6):330－343.

［5］COMMENTZ－WALTER B.A string matching algorithm fast on the average［C］//Proc.6th ICALP.［S.l.］:IEEE Press，1979:118－132.

［6］FAN J J，SU K Y.An efficient algorithm for matching multiple patterns［J］.IEEE Transactions on Knowledge and Data Engineering，1993，5(2):339－351.

［7］王永成，沈州，許一震.改進的多模式匹配算法［J］.計算機研究與發展，2002，39(1):55－60.

［8］NORTON M.Optimizing pattern matching for intrusion detection［EB/OL］.［2006－05－11］.http://docs.idsresearch.org./Optimizing Pattern-MatchingForIDS.pdf.