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

孫友倉

（西安石油大學(xué) 計算機學(xué)院，陜西 西安 710065）

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

孫友倉

（西安石油大學(xué) 計算機學(xué)院，陜西 西安 710065）

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

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

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

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

1 多模式匹配算法

1.1 AC算法

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

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

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

1.2 WM算法

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

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

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

1.3 ExB算法

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

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

2 算法性能測試和結(jié)果分析

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

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

?

3 結(jié)束語

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

[1]唐 謙，張大方.入侵檢測中模式匹配算法的性能分析[J].計算機工程與應(yīng)用,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].計算機應(yīng)用研究,2008，25（8）：2474-2476.

[4]趙念強，鞠時光.入侵檢測系統(tǒng)中模式匹配算法的研究[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]李紅霞，王新生，王建東.一種應(yīng)用于入侵檢測的基于排除的模式匹配算法[J].電子技術(shù)應(yīng)用,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—），男，陜西白水人，副教授。研究方向：網(wǎng)絡(luò)安全與應(yīng)用。