多模式匹配算法的性能分析

孫友倉

（西安石油大學 計算機學院，陜西 西安 710065）

多模式匹配算法的性能分析

孫友倉

（西安石油大學 計算機學院，陜西 西安 710065）

多模式匹配算法效率直接影響入侵檢測系統的性能和效率。在分析研究經典的AC算法、WM算法和ExB算法的基礎上,通過上機實驗測試這些算法的模式匹配時間,為改進多模式匹配算法提供有益的借鑒。

多模式匹配；AC算法；WM算法；ExB算法

多模式匹配算法在很多領域都有重要應用,如拼寫檢查、語言翻譯、數據壓縮、搜索引擎、網絡入侵檢測、計算機病毒特征碼匹配等[1]。研究高效的多模式匹配算法具有非常重要的理論和現實意義。

所謂多模式匹配，就是在文本串T[1，…，n]中一次匹配多個模式串P1,P2,…，Pk，其中k為模式串的個數。k=1時，即為單模式匹配。模式串 Pj的長度為mj,即 Pj[1，…，mj]（1≤j≤k），minlen是最短模式串的長度，即minlen=min{mj|（1≤j≤q）}。多模式匹配比多個模式串逐個進行傳統單模式匹配的速度快得多。

1 多模式匹配算法

1.1 AC算法

采用AC算法進行匹配需先對模式串集合進行預處理，形成樹型有限狀態自動機，然后只需對文本串掃描1次就可找出與其匹配的所有模式串[2]。

AC算法在預處理階段生成3個函數：goto（轉移）函數、failure（失效）函數和output（輸出）函數。匹配過程從有限狀態自動機的初始狀態出發，每取出文本串中的一個字符，利用goto函數和failure函數進入下一狀態；當某個狀態的output函數不為空時輸出其值，表示在文本串中匹配到該模式串[3-4]。

AC算法在對文本串進行搜索時無跳躍，而是按順序輸入字符，無法跳過不必要的比較，因此在模式數目不是非常多的實際搜索過程中，AC算法性能不佳。AC算法模式匹配的時間復雜度是O（n），而且與模式集中模式串的個數和每個模式串的長度無關，無論模式串P是否出現在T中，T中的每個字符都必須輸入狀態機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復雜度都是O（n），包括預處理時間在內AC算法的總時間復雜度是O（M+n），其中M為所有模式串的長度總和。

1.2 WM算法

WM快速字符串匹配算法采用BM算法進行跳躍的思想和hash散列方法，在實際應用中，是大規模多模式匹配最快的算法之一[5]。WM算法將文本串以B個字符長度分塊，稱該B個字符為1個塊字符，B為塊字符的長度，B通常取2或3。首先對模式集進行預處理，在預處理階段構造3個表，即shift表、hash表和prefix表。匹配過程從文本串text的第（m-B+1）（m是模式集中模式串的最小長度）個字符處開始，每次計算當前塊字符的hash值h，通過shift[h]的值決定是否向后跳躍；當shift[h]的值為0時，將hash[h]鏈表中的每一個模式串從后向前與text比較，如果未達到text末尾，則將text向后移動1個字符繼續比較。

WM算法的主要優點是字符跳躍距離大，使用shift表可以跳過那些不可能成功的匹配入口，匹配入口點少，從而減少字符比較次數。因此實際應用中，WM算法的效率一般比AC算法高。但WM算法在每個匹配入口點處，要逐個比較hash[h]表中每一個模式，在模式集數目較大時，算法性能明顯下降。

WM算法在模式匹配中采用啟發式搜索策略進行字符跳躍，匹配的時間復雜度平均情況是O（Bn/m），實際應用中B≤m，所以WM算法模式匹配的時間復雜度低于AC算法。

1.3 ExB算法

ExB 算法是一個基于排除的字符串匹配算法，該算法能很快排除數據包負載中不包含匹配模式串的數據包[6]。其思想是：假設要檢測字符串A中是否包含子串s，如果s中至少有1個字符不包含在A中，則s就不是A的1個子串。為了減少錯誤匹配的概率，將該算法擴充到字符對，匹配過程不僅檢測s中每個字符是否出現在A中，還檢測每一字符對中的字符出現的順序是否正確。為了快速判定給定的字符c是否屬于字符串A，該算法采用出現圖的方法。對于A中出現的字符c在出現圖中的相應位置采用二進制值標記，“1”表示c屬于A，“0”表示c不屬于A。對于每個新數據包，出現圖都要進行一次大開銷清零工作。為了減少這種開銷，采用每個數據包的序列號取代二進制值來標記出現圖中的相應位置，這樣出現圖就無需對每一個新數據包都進行清零。

該算法可分為預處理和搜索兩個階段。預處理階段的時間復雜度與數據包負載的大小成線性關系，搜索階段的時間復雜度與所有模式中的長度和成線性關系。由于在多數數據集中，入侵數據包畢竟是少數。另外，據統計僅有1.6%的數據包需要用標準的字符串匹配算法進一步確定該入侵特征串是否在數據包中,因此調用標準串匹配算法的概率很小，所以在實際應用中，該算法的效率高于其他應用于入侵檢測中的匹配算法。

2 算法性能測試和結果分析

對多模式匹配算法進行模擬測試。測試環境：CPU是Intel Pentium E2200 2.2 G，內存1 G，硬盤160 G，操作系統Windows 2003，算法實現環境是Visual C++6.0。利用入侵檢測訓練數據集[7]，選取1天的流量數據（容量約160 MB的Tcpdump文件）作為測試數據集。入侵檢測系統分別采用AC算法、WM算法和ExB算法作為模式匹配檢測引擎,測試這3種情況下平均模式匹配時間與模式數目的變化關系，對比情況如表1所示。

由表1可知，模式數小于20個時ExB算法最優，模式數在50～100時AC算法的匹配效率更好，當模式數大于100時，WM算法性能更好。測試結果與理論分析基本吻合。

?

3 結束語

隨著網絡應用的發展和網絡帶寬的增加，必須提高網絡入侵檢測系統的處理性能。而目前的網絡入侵檢測系統多是基于特征匹配的系統，這類系統中的關鍵運算是模式匹配，因此提高模式匹配的效率是提高這類系統檢測能力的關鍵。本文對已有的多模式匹配算法進行性能分析，為今后改進多模式匹配算法提供有益的借鑒。

[1]唐 謙，張大方.入侵檢測中模式匹配算法的性能分析[J].計算機工程與應用,2005（17）：136-138.

[2]Aho A V,Corasickm J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM,1975,18（6）：333-340.

[3]李 庚，韓 進，謝 立.入侵檢測中一種新的多模式匹配算法[J].計算機應用研究,2008，25（8）：2474-2476.

[4]趙念強，鞠時光.入侵檢測系統中模式匹配算法的研究[J].微計算機信息,2005,21（8-3）：22-24.

[5]WU Sun,Manber U.Fast algorithm for multi-pattern sear ching[R].Tucson:Department of computer science university of arizona,1994.

[6]李紅霞，王新生，王建東.一種應用于入侵檢測的基于排除的模式匹配算法[J].電子技術應用,2006（1）:41-43.

[7]Graf IL，Ippmann R，Cunningham R，et al.Results of DARPA 1998 offline intrusion detection evaluation[EB/OL].1998.http://ideval.ll.mit.edu/results-html-dir.

Performance analysis of multiple pattern matching algorithm

SUN You-cang
（School of Computer Science,Xi＇an Shiyou University，Xi＇an710065,China）

The multiple pattern matching algorithm directly impacts on intrusion detection system performance and efficiency.On the basis of reseaching and analysing the classic AC algorithm,WM algorithm and ExB algorithm,the pattern matching time of these algorithms are tested through hands-on experiment.It provides helpful reference for improving the multiple pattern matching algorithm.

multiple pattern matching;AC algorithm;WM algorithm;ExB algorithm

TP393.08

A

1674－6236（2010）01-0017-02

2009-08-16 稿件編號：200908029

孫友倉（1967—），男，陜西白水人，副教授。研究方向：網絡安全與應用。