入侵檢測系統(tǒng)中模式匹配算法的研究

1、入侵檢測系統(tǒng)中模式匹配算法的研究摘要  入侵檢測是網絡安全的最后一道防線，模式匹配算法是基于特征匹配的入侵檢測系統(tǒng)中的核心算法，模式匹配的效率決定這類入侵檢測系統(tǒng)的性能。本文對入侵檢測系統(tǒng)中的模式匹配算法進行了綜述，包括經典的單模式匹配算法-KMP算法、BM算法、RK算法和多模式匹配AC算法。對各種算法的性能進行了分析。最后提出了改進模式匹配算法效率的研究方向。關鍵詞: 網絡安全；入侵檢測；模式匹配；多模式匹配1 引言    隨著Internet應用的普及，網絡安全問題也日益突出。入侵是指試圖破壞資源的完整性、可用性和保密性的活動的集合。作為防火墻之后網

2、絡安全的最后一道防線，入侵檢測系統(tǒng)（IDS）是指檢測上述行為的活動，識別出未經授權或越權訪問系統(tǒng)資源的行為的軟硬件系統(tǒng)。由于入侵檢測系統(tǒng)可以在一定程度上主動預防和檢測出來自系統(tǒng)內、外部的入侵，并作出適當響應，動態(tài)改變網絡的安全性，因此入侵檢測的研究正成為網絡安全研究的熱點。    根據采用的分析技術入侵檢測分為誤用檢測和異常檢測 1。誤用檢測根據已知的攻擊方法，預先定義入侵模式，通過判斷這些模式是否出現來完成檢測任務。異常檢測是指根據用戶的行為或資源的使用狀況的正常程度來判斷是否屬于入侵。由于異常檢測的誤檢率和漏檢率高，因此目前大多數入侵檢測系統(tǒng)產品均屬誤用檢測。

3、誤用檢測中使用的檢測技術主要有：模式匹配、專家系統(tǒng)、狀態(tài)轉移等，而其中因為模式匹配原理簡單、可擴展性好而最為常用，例如著名開放源碼的入侵檢測系統(tǒng)Snort就是基于模式匹配的。    由此可見，模式匹配算法的性能直接影響入侵檢測系統(tǒng)的檢測效率。在高速網絡環(huán)境，如果模式匹配算法來不及處理大量的實時網絡數據包，必然會丟棄部分數據包，而這些被丟棄的數據包中就可能包含入侵信息。本文以下部分介紹幾種著名的模式匹配算法，包括單模式匹配算法和多模式匹配算法，為設計入侵檢測系統(tǒng)選擇模式匹配算法提供指導。2 單模式匹配算法    模式匹配是指在給定長度為

4、n的文本串T=T1T2Tn中查找長度為m的模式串P=P1P2Pm的第一次出現的過程。這里Ti（1in），Pj（1jm）（字符集），若在T中能找到P的出現，則稱匹配成功，否則稱匹配失敗。    一次只能在文本串中對一個模式串進行匹配的算法，稱為單模式匹配算法，可同時對多個模式串進行匹配的算法稱多模式匹配算法。    平凡的模式匹配算法（BF算法）中，一趟匹配失敗后，T只后移一個字符，所以算法簡單，但效率低。高效的模式匹配算法都是設法增大不匹配時T的后移量，本節(jié)下面介紹3種經典的快速單模式匹配算法，第3節(jié)介紹著名的多模式匹配算法AC算法。

5、2.1 KMP算法2.2 BM算法     2) 好后綴規(guī)則(Good Suffix)    壞字符規(guī)則沒有考慮已經取得的部分匹配的情況，而KMP算法卻考慮了。該規(guī)則將KMP算法和BM算法的思想結合起來，在不丟失真解的前提下確定一個新的移動距離delta2，該函數與樣本P有關。具體分以下兩種情況，如圖1所示。l ·P中間的某一子串Pj-s+1.m-s與已比較部分Pj+1.m相同，可讓P右移s位。l ·P已比較部分Pj+1.m的后綴Ps+1.m與P的前綴P1.m-s相同，可讓P

6、右移s位。滿足上面情況的s的最小值為最佳右移距離。delta2的定義如下：delta2（j）=mins|(Pj+1.m=Pj-s+1.m-s)&&(PjPj-s)(j>s),Ps+1.m=P1.m-s(js)     在匹配過程中，取delta1和delta2中的大者。BM算法的最壞時間復雜度為O(mn)，但實際比較次數只有文本串長度的20%30%。2.3 RK算法3 多模式匹配的AC算法3.1 入侵檢測中多模式匹配的必要性3.2 AC算法    AC算法5是基于FSA（有窮狀態(tài)自動機）的，在進行匹配之

7、前先對模式串集合Sp進行預處理，形成樹型FSA，然后只需對文本串T掃描一次就可以找出與其匹配的所有模式串。    預處理生成3個函數：goto（轉移）函數，failure（失效）函數和output（輸出）函數。    設U=0，1，2為狀態(tài)集合，轉移函數g:(U,Sp)U為一映射，其建立過程為：逐個取出Sp中模式串的每個字符，從狀態(tài)0出發(fā)，由當前狀態(tài)和新取出的字符決定下一狀態(tài)。如果有從當前狀態(tài)出發(fā)并標注該字符的矢線，則將矢線所指的狀態(tài)賦為當前狀態(tài)，否則，添加一個標號比已有狀態(tài)標號大1的新狀態(tài)，并用一條矢線從當前狀態(tài)指向新加入的狀態(tài)，并

8、將新加入的狀態(tài)賦為當前狀態(tài)。Sp中的所有模式串處理完后，再畫一條從0狀態(tài)到0狀態(tài)的自返線，標注的字符為不能從0開始的字符集。例如，Sp=he,she,his,hers的goto函數如圖2所示。             圖2 he,she,his,hers的goto函數圖    失效函數f用來指明當某個模式與文本匹配不成功時，應處理的下一狀態(tài)。f的構造方法為：所有第一層狀態(tài)的失效函數為0，如f(1)=f(3)=0；對于非第一層狀態(tài)s，若其父狀態(tài)為r

9、（即存在字符a,使g(r,a)=s），則f(s)=g(f(s*),a)，其中狀態(tài)s*為追溯s的祖先狀態(tài)得到的第一個使g(f(s*),a)存在的狀態(tài)。如f(4)=g(f(3),h)=g(0,h)=1，f(5)=g(f(4),e)=g(1,e)=2。    輸出函數output的作用是在匹配過程中輸出已經匹配的模式串。output的構造分兩步，第一步是在構造轉移函數g時，每處理完一個模式串，則將該模式串加入到當前狀態(tài)s的輸出函數中，如output(2)=he,output(5)=she。第二步是構造失效函數f時，若f(s)=s,則output(s)=output(s)

10、output(s),如output(5)=output(5)output(2)=she,he。    AC算法的匹配過程如下：從狀態(tài)0出發(fā)，每取出文本串中的一個字符，利用g和f函數進入下一狀態(tài)。當某個狀態(tài)的output函數不為空時輸出其值，表示在文本串中找到該模式串。    AC算法模式匹配的時間復雜度是O(n)，而且與模式集中模式串的個數和每個模式串的長度無關。無論模式串P是否出現在T中，T中的每個字符都必須輸入狀態(tài)機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復雜度都是O(n)。包括預處理時間在內，AC算法總時間復雜

11、度是O(M+n)，其中M為所有模式串的長度總和。     對多模式串的匹配而言，雖然AC算法比BM算法高效得多。但AC算法必須逐一地查看文本串的每個字符，而BM算法能夠利用跳轉表躍過文本串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發(fā)式搜索技術應用到AC算法中，則可大大提高多模式匹配算法的效率。Commentz-Walter首先結合了BM算法和AC算法的特征，提出了一種解決多模式匹配問題的算法。實踐表明Commentz-Walter算法要比AC算法快很多。Baeza-Yates也給出了一種組合BMP算法和AC算法的多模式匹配算法。AC-BM算法根據一種前

12、綴關鍵字樹來計算劣勢移動表和優(yōu)勢跳轉表，從而可以跳躍式地并行搜索模式集合。4 結束語    隨著網絡應用的發(fā)展和網絡帶寬的不斷增加，必須加快網絡入侵檢測系統(tǒng)的處理性能，否則，網絡入侵檢測系統(tǒng)只能形同虛設，由于大量的網絡數據來不及處理而使入侵漏報。而目前實用的網絡入侵檢測系統(tǒng)多是基于特征匹配的系統(tǒng)，這類系統(tǒng)中的關鍵運算是模式匹配運算，因此提高模式匹配的效率是提高這類系統(tǒng)檢測能力的關鍵所在。本文對已有的模式匹配算法進行了綜述，主要包括3中重要的單模式匹配算法和AC多模式匹配算法。將快速單模式匹配算法與多模式匹配算法相結合是今后改進模式匹配算法努力的方向。參考文獻1 H

13、ochberg J,Jackson K, Stallings C,et al.NADIR:An Automated System for Detecting Network Intrusion and Misuse.Computers and Security, 1993,12(3):235-2482 Knuth DE , Morris JH , Pratt VR. Fast Pattern Matching in StringsJ , SIAM Journal on Computer , 1977 , 6 (2) :323-350.3 Boyer RS , Moore JS. A Fast String Searching AlgorithmJ . Communications of the ACM ,1977 ,20(