孫友倉

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

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

孫友倉

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

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

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

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

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

1 多模式匹配算法

1.1 AC算法

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

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

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

1.2 WM算法

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

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

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

1.3 ExB算法

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

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

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

對多模式匹配算法進(jìn)行模擬測試。測試環(huán)境：CPU是Intel Pentium E2200 2.2 G，內(nèi)存1 G，硬盤160 G，操作系統(tǒng)Windows 2003，算法實(shí)現(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í)間與模式數(shù)目的變化關(guān)系，對比情況如表1所示。

由表1可知，模式數(shù)小于20個(gè)時(shí)ExB算法最優(yōu)，模式數(shù)在50～100時(shí)AC算法的匹配效率更好，當(dāng)模式數(shù)大于100時(shí)，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)鍵運(yùn)算是模式匹配，因此提高模式匹配的效率是提高這類系統(tǒng)檢測能力的關(guān)鍵。本文對已有的多模式匹配算法進(jìn)行性能分析，為今后改進(jìn)多模式匹配算法提供有益的借鑒。

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

[4]趙念強(qiáng)，鞠時(shí)光.入侵檢測系統(tǒng)中模式匹配算法的研究[J].微計(jì)算機(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)用。