入侵檢測中一種新的多模式匹配算法

摘 要：基于模式匹配的檢測方法是目前入侵檢測系統(tǒng)的一種重要方法，因此作為模式匹配方法核心的字符串匹配算法直接影響入侵檢測系統(tǒng)的性能和效率。在AC算法和Wu-Manber算法的研究基礎(chǔ)上，提出了一種新的多模式匹配算法——AC-WM。該算法能夠增加字符跳轉(zhuǎn)距離，比較穩(wěn)定地減少匹配過程中字符比較的次數(shù)，提高匹配的速度和效率。

關(guān)鍵詞：入侵檢測；多模式匹配；AC算法；Wu-Manber算法；AC-WM算法

中圖分類號：TP393.08 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695(2008)08-2474-03

New multiple patterns matching algorithm in intrusion detection

LI Genga，b， HAN Jina，b， XIE Lia，b

(a. Dept.of Computer Science Technology， b. State Key Laboratory for Novel Software Technology， Nanjing University， Nanjing 210093， China)

Abstract:The detection method based on patterns matching is an important method in intrusion detection system， and the key of this is the efficiency of string matching which influences the efficiency of detection directly. This paper analyzed some multiple patterns matching algorithms， such as AC algorithm and Wu-Manber algorithm， and then presented a new multiple patterns matching algorithm named AC-WM. AC-WM algorithm can increase the jumping distance of characters and decrease the comparison times in matching process. In this case， it improves the matching efficiency.

Key words:intrusion detection; multiple patterns matching; AC algorithm; Wu-Manber algorithm; AC-WM algorithm

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)環(huán)境變得越來越復(fù)雜，對于網(wǎng)絡(luò)安全來說，單純的防火墻技術(shù)暴露出明顯的不足和弱點，如無法解決安全后門問題；不能阻止網(wǎng)絡(luò)內(nèi)部攻擊；不能提供實時入侵檢測能力；對于病毒束手無策等。入侵檢測系統(tǒng)是繼防火墻和信息加密等安全保障技術(shù)之后出現(xiàn)的新一代網(wǎng)絡(luò)安全防護(hù)系統(tǒng)，能夠有效地彌補上述安全系統(tǒng)的不足。它通過對計算機網(wǎng)絡(luò)或計算機系統(tǒng)中的若干關(guān)鍵點收集信息并對其進(jìn)行分析，實時地發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象，并采取相應(yīng)措施以避免攻擊的發(fā)展或盡量減少攻擊造成的危害。按照所采用的檢測技術(shù)，入侵檢測系統(tǒng)可以分為誤用檢測系統(tǒng)和異常檢測系統(tǒng)。誤用檢測系統(tǒng)使用模式匹配的方法來發(fā)現(xiàn)入侵行為，是目前入侵檢測系統(tǒng)的主流。所以，作為模式匹配方法核心的字符串匹配算法直接影響入侵檢測系統(tǒng)的性能和效率。

字符串匹配算法分為單模式匹配算法和多模式匹配算法兩大類。經(jīng)典的單模式匹配算法包括Knuth-Morris-Patt算法(KMP算法)^[1]、Boyer-Moore算法(BM算法) ^[2]和Quick Search算法^[3]等。經(jīng)典的多模式匹配算法包括AC算法^[4]和Wu-Manber快速字符串匹配算法^[5，6]等。本文主要討論在入侵檢測系統(tǒng)中廣泛應(yīng)用的多模式匹配算法。

1 多模式匹配算法分析

1.1 Aho-Corasick算法^[4](AC算法)

Aho-Corasick算法是同時搜索多個模式的經(jīng)典匹配算法。它在進(jìn)行匹配之前先對模式串集合進(jìn)行預(yù)處理，形成樹型有限狀態(tài)自動機，然后只需對文本串掃描一次就可以找出與其匹配的所有模式串。

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

對多模式串的匹配而言，AC算法比KMP、BM等單模式匹配算法高效得多。但是AC算法在對文本串進(jìn)行搜索時沒有跳躍，而是按順序輸入字符，無法跳過不必要的比較，因此在模式數(shù)目不是非常多的實際搜索過程中，AC算法性能不佳。

1.2 Wu-Manber算法^[5，7~9]

Wu-Manber快速字符串匹配算法采用了BM算法進(jìn)行跳躍的思想和hash散列的方法，在實際應(yīng)用中，是大規(guī)模多模式匹配最快的算法之一。

Wu-Manber算法將文本串以B個字符長度分塊，稱該B個字符為一個塊字符，B為塊字符的長度，B通常取2或3。首先對模式集進(jìn)行預(yù)處理，在預(yù)處理階段構(gòu)造三個表，即shift表、hash表和prefix表。匹配過程從文本串text的第m-B+1個字符處開始（m是模式集中模式串的最小長度），每次計算當(dāng)前塊字符的hash值h，通過shift[h]的值決定是否向后跳躍；當(dāng)shift[h]的值為0時，將hash[h]鏈表中的每一個模式串從后向前與text比較，如果沒有達(dá)到text末尾，那么將text向后移動一個字符繼續(xù)進(jìn)行比較。

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

2 新的多模式匹配算法——AC-WM

根據(jù)以上分析，本文提出一種新的多模式匹配算法（AC-WM），其基本原理是：應(yīng)用Wu-Manber算法的啟發(fā)式搜索策略產(chǎn)生字符跳躍，并對跳躍的位移表進(jìn)行改進(jìn)，以增加盡可能多的位移；同時應(yīng)用AC算法的有限狀態(tài)自動機構(gòu)造模式樹，匹配過程中使用模式樹，減少字符比較次數(shù)。

AC-WM算法分為兩個部分，即預(yù)處理階段和匹配階段。

2.1 AC-WM算法的預(yù)處理

預(yù)處理階段構(gòu)造兩個位移表（shift表和shift2表）和一個樹型有限狀態(tài)自動機。Shift表用來在匹配過程中進(jìn)行字符跳躍；shift2表用來存放當(dāng)shift表的值為0時字符跳躍的距離；有限狀態(tài)自動機用來在shift表的值為0時進(jìn)行字符串比較，它構(gòu)造時生成兩個函數(shù)，即goto（轉(zhuǎn)移）函數(shù)和output（輸出）函數(shù)。其中，goto函數(shù)根據(jù)有限狀態(tài)自動機的當(dāng)前狀態(tài)和文本串的下一個字符進(jìn)行狀態(tài)轉(zhuǎn)移；output函數(shù)的作用是在匹配過程中輸出已經(jīng)匹配成功的模式串。

2.1.1 構(gòu)造位移表

與Wu-Manber算法類似，AC-WM算法也將文本串以B個字符長度分塊，B通常取2或者3。設(shè)模式串的最小長度為m，構(gòu)造位移表時將所有模式串從最后一個字符對齊，截取每個模式串的最后m個字符來計算位移值。

Shift表的構(gòu)造方法如下：設(shè)X是長度為B的塊字符，X被映射到shift[h]，則shift[h]是X在所有模式串中出現(xiàn)的最后面位置。有以下兩種情況：

a）如果X不在任何模式串中出現(xiàn)，則shift[h]=m-B+1。

b）如果X出現(xiàn)在有些模式串中，設(shè)X在模式串P的位置q結(jié)束，并且X在任何其他模式串中都不會在比q更后面的位置結(jié)束，則shift[h]=m-q。

Shift2表的構(gòu)造方法如下：設(shè)X是長度為B的塊字符，X被映射到shift2[h]，則shift2[h]是X在所有模式串中出現(xiàn)的次后面位置。有以下兩種情況：

a）如果X不在任何模式串中出現(xiàn)或在所有模式串中共出現(xiàn)一次，則shift2[h]=m-B+1。

b）如果X出現(xiàn)在模式串中的總次數(shù)≥ 2，設(shè)X在模式串P的位置q結(jié)束，并且X在其他模式串中有且只有一次在比q更后面的位置結(jié)束，則shift2[h]=m-q。

對于模式集{they，she，his，hers}，表1顯示了取B=2時的shift表和Shift2表。

表1{they，she，his，hers}的shift表和shift2表

BCheeyshhiiserrsothersshift100110102shift2122222222.1.2 構(gòu)造有限狀態(tài)自動機

AC-WM算法在匹配時對文本從后向前進(jìn)行字符串比較，所以構(gòu)造有限狀態(tài)自動機時按照與AC算法相反的方向來掃描模式串。Goto函數(shù)和output函數(shù)按照如下方法生成：初始狀態(tài)為0；然后依次取出模式集中的每一個模式串執(zhí)行如下操作：從模式串的最后一個字符開始從后向前，逐個取出模式串的每個字符，從狀態(tài)0出發(fā)，由當(dāng)前狀態(tài)和新取出的字符決定下一狀態(tài)。如果下一狀態(tài)不為空，則將下一狀態(tài)賦為當(dāng)前狀態(tài)；否則，添加一個標(biāo)號比已有狀態(tài)標(biāo)號大1的新狀態(tài)，并用一條矢線從當(dāng)前狀態(tài)指向新加入的狀態(tài)，并將新加入的狀態(tài)賦為當(dāng)前狀態(tài)。每處理完一個模式串，將該模式串加入到當(dāng)前狀態(tài)的output函數(shù)中。

對于模式集{they，she，his，hers}，圖1顯示了有限狀態(tài)自動機的goto函數(shù)。表2顯示了output函數(shù)。

圖1{they，she，his，hers}的goto函數(shù)

表2{they，she，his，hers}的output函數(shù)

state471013output{they}{she}{shi}{hers} 2.2 AC-WM算法的匹配過程

AC-WM算法的匹配過程如下：

a)計算文本串text的當(dāng)前B個字符的hash值h（從text的第m-B+1個字符處開始）。

b)檢查shift[h]的值。如果shift[h] > 0，則將text向后移動shift[h]個字符，然后轉(zhuǎn)到a）執(zhí)行；否則，轉(zhuǎn)到c）執(zhí)行。

c)利用有限狀態(tài)自動機進(jìn)行字符串比較。從text的當(dāng)前字符開始，從后向前逐個取出text的每個字符，從狀態(tài)0出發(fā)，根據(jù)goto函數(shù)進(jìn)入下一狀態(tài)；當(dāng)某個狀態(tài)的output函數(shù)不為空時輸出其值，表示在文本串中找到該模式串。

d)如果達(dá)到text末尾，循環(huán)結(jié)束；否則，將text向后移動shift2[h]個字符，轉(zhuǎn)到a）執(zhí)行。

下面是AC-WM算法匹配過程的程序偽代碼：

a） while (text < textend) {

b） h=hashBlock(text);

c） if(shift[h]>0) {

d）將text向后移動shift[h]個字符;

e）continue;

f） }

g） //利用有限狀態(tài)自動機從后向前進(jìn)行比較

textcurrent = text;state = 0;

h） while (textcurrent>=textstart goto(state，

textcurrent) != NULL) {

i）state=goto(state， textcurrent);

j）if(output(state) != NULL)

k）輸出匹配成功的模式串;

l） 將textcurrent向前移動1個字符;

m） }

n） 將text向后移動shift2[h]個字符;

o）}

3 算法時間復(fù)雜度分析

設(shè)N是文本串的長度，m是模式串的最小長度，L是模式串的最大長度，B是塊字符的長度。

AC算法按順序逐個掃描文本中的每個字符，無論能否匹配成功，文本中的每個字符都必須輸入狀態(tài)機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復(fù)雜度都是O(N) ^[4]。

Wu-Manber算法在模式匹配過程中采用啟發(fā)式搜索策略進(jìn)行字符跳躍，匹配的時間復(fù)雜度平均情況是O(BN/m) ^[5]。在實際應(yīng)用中B≤m，所以Wu-Manber算法模式匹配的時間復(fù)雜度低于AC算法。

AC-WM算法采用了與Wu-Manber算法類似的字符跳躍方法，因此AC-WM算法模式匹配的時間復(fù)雜度平均情況也是O(BN/m)。AC-WM算法對Wu-Manber算法的性能改進(jìn)主要有以下兩個方面：

a）在Wu-Manber算法中，shift表中的最大位移是m-B+1；但是在實際匹配過程中，當(dāng)shift[h]=0時，不管能否匹配成功，向后跳躍的字符數(shù)總是等于1。在AC-WM算法中，增加了shift2表，shift2表中的最大位移是m-B+1；在匹配過程中，當(dāng)shift[h] = 0時，不管能否匹配成功，向后跳躍的字符數(shù)是shift2[h]。因此AC-WM算法將shift[h] = 0時字符跳躍的最大距離從1擴大到了m-B+1。

b）在Wu-Manber算法中，每個匹配入口點處都需要對hash表中的模式串逐個進(jìn)行比較。而AC-WM算法使用有限狀態(tài)自動機，將符合條件的多個模式串同時進(jìn)行比較，在每個匹配入口點處只需要對所有模式串比較一次，最壞情況下的字符比較次數(shù)僅為L。因此在模式集數(shù)目較大時，AC-WM算法匹配過程中的字符比較次數(shù)比Wu-Manber算法減少很多。

綜上所述，AC-WM算法比AC算法和Wu-Manber算法提高了匹配的速度和效率。

4 算法實驗測試結(jié)果

基于以上的研究，對模式匹配算法進(jìn)行模擬測試。利用I.Graf等人^[10]提供的入侵檢測訓(xùn)練數(shù)據(jù)集，選取一天的流量數(shù)據(jù)（容量大約160 MB的Tcpdump文件）作為測試數(shù)據(jù)集。入侵檢測系統(tǒng)分別采用AC-WM算法、AC算法和Wu-Manber算法作為模式匹配檢測引擎，測試這三種情況下每個數(shù)據(jù)報的平均模式匹配時間與模式數(shù)目的變化關(guān)系。實驗環(huán)境：CPU 2 GHz，內(nèi)存512 MB，硬盤40 GB，操作系統(tǒng)Linux 2.6.20。

表3比較了三種算法的平均匹配時間隨著模式數(shù)目增加的變化情況，并給出了AC-WM算法對AC算法和Wu-Manber算法的效率提高程度。其中，AW表示AC-WM算法;WM表示W(wǎng)u-Manber算法。

表3 模式匹配算法對比測試

模式數(shù)目(個)AW/μsAC/μsWM /μs1-AW/AC/%1- AW/WM/%101.1251.2501.14010.001.31201.2401.2891.4563.8014.83501.3191.5891.67716.9921.341001.5321.8312.02016.3224.152001.7822.6242.17232.0817.955002.2734.0792.70644.2716.001 0002.7605.7653.26652.1215.49表3顯示，AC-WM算法的匹配效率明顯優(yōu)于AC算法，同樣優(yōu)于Wu-Manber算法。表3中的最后兩列是AC-WM算法對AC算法和Wu-Manber算法的效率提高程度，從中可以看出，當(dāng)模式數(shù)目較大（如> 50）時，AC-WM算法的效率顯著提高，比AC算法平均約提高16%~52%，比Wu-Manber算法平均約提高15%~24%；當(dāng)模式數(shù)目較小（如< 50）時，三種算法的效率比較接近，AC-WM算法同樣具有明顯的優(yōu)勢。圖2是表3中三個算法的平均匹配時間的折線圖。

從圖2可以看出，三種算法中AC-WM算法的平均匹配時間是最少的，主要原因是在匹配時盡可能多地進(jìn)行字符跳躍，同時利用有限狀態(tài)自動機，減少了字符比較的次數(shù)。AC-WM算法和Wu-Manber算法由于在匹配時都可以進(jìn)行字符跳躍，性能比較穩(wěn)定，隨著模式數(shù)目的增加，匹配時間的變化不大。根據(jù)以上的實驗結(jié)果和數(shù)據(jù)分析，可以看出，在入侵檢測系統(tǒng)中應(yīng)用AC-WM算法，能夠顯著提高模式匹配的效率。

5 結(jié)束語

隨著網(wǎng)絡(luò)應(yīng)用的不斷出現(xiàn)以及網(wǎng)絡(luò)帶寬的不斷增加，必須加快入侵檢測系統(tǒng)的處理性能以適應(yīng)大流量網(wǎng)絡(luò)環(huán)境的要求。目前入侵檢測系統(tǒng)大多是基于模式匹配的系統(tǒng)，因此提高模式匹配的效率是提高系統(tǒng)檢測能力的關(guān)鍵。本文對入侵檢測系統(tǒng)中應(yīng)用的多模式匹配算法進(jìn)行了研究，在AC算法和Wu-Manber算法的基礎(chǔ)上，提出了一種新的多模式匹配算法AC-WM，充分利用了Wu-Manber算法的啟發(fā)式搜索技術(shù)和AC算法的有限狀態(tài)自動機同時匹配的特點，并擴大了啟發(fā)式搜索中的字符跳躍距離。實驗結(jié)果表明，在入侵檢測系統(tǒng)中應(yīng)用AC-WM算法，能夠顯著提高模式匹配的效率，從而提高系統(tǒng)的檢測性能。

參考文獻(xiàn):

[1]KNUTH D E， MORRIS H， PRATT V R. Fast pattern matching in strings[J]. SIAM J Comp，1977，6(1): 323-350.

[2]BOYER R S， MOORE J S. A fast string searching algorithm[J].Communications of the ACM，1977，20(10):762-772.

[3]SUNDAY D M.A very fast substring search algorithm[J].Communications of the ACM，1990，33(8): 132-142.

[4]AHO A V， CORASICKM J. Efficient string matching: an aid to bibliographic search[J].Communications of the ACM，1975，18(6):333-340.

[5]WU Sun， MANBER U. A fast algorithm for Multi-pattern searching[R].Tucson:Department of Computer Science，University of Arizona，1994.

[6]DUA-ning， FANG Bin-xing， YUNXiao-chun，et al. Comparison of stringmatching algorithms: an aid to information content security[C]//Proc of the 2nd International Conference on Mache Learning and Cybernetics.Xi’an:[s.n.]，2003:2996-3001.

[7]TUCKN， SHERWOODT， CALDERB， et al. Deterministic memory efficient string matching algorithms for intrusion detection[C]//Proc of IEEE Infocom Conference.Hong Kong:[s.n.]，2004:333-340.

[8]YANG Dong-hong， XU Ke， CUI Yong. An improved Wu-Manber multiple patterns matching algorithm[J]. Journal of Tsinghua University Science and Technology，2006，46(4):555-558.

[9]UDI M. AGREP， an approximate GREP [EB/OL].[2005]. http://www.tgries.de/agrep/.

[10]GRAF I， LIPPMANN R， CUNNINGHAM R， et al. Results of DARPA 1998 offline intrusion detection evaluation[EB/OL].[1998]. http://ideval.ll.mit.edu/results-html-dir.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文