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

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

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

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

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

5、2.1 KMP算法2.2 BM算法     2) 好后綴規(guī)則(Good Suffix)    壞字符規(guī)則沒有考慮已經(jīng)取得的部分匹配的情況，而KMP算法卻考慮了。該規(guī)則將KMP算法和BM算法的思想結(jié)合起來，在不丟失真解的前提下確定一個(gè)新的移動(dòng)距離delta2，該函數(shù)與樣本P有關(guān)。具體分以下兩種情況，如圖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算法的最壞時(shí)間復(fù)雜度為O(mn)，但實(shí)際比較次數(shù)只有文本串長度的20%30%。2.3 RK算法3 多模式匹配的AC算法3.1 入侵檢測中多模式匹配的必要性3.2 AC算法    AC算法5是基于FSA（有窮狀態(tài)自動(dòng)機(jī)）的，在進(jìn)行匹配之

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

8、將新加入的狀態(tài)賦為當(dāng)前狀態(tài)。Sp中的所有模式串處理完后，再畫一條從0狀態(tài)到0狀態(tài)的自返線，標(biāo)注的字符為不能從0開始的字符集。例如，Sp=he,she,his,hers的goto函數(shù)如圖2所示。             圖2 he,she,his,hers的goto函數(shù)圖    失效函數(shù)f用來指明當(dāng)某個(gè)模式與文本匹配不成功時(shí)，應(yīng)處理的下一狀態(tài)。f的構(gòu)造方法為：所有第一層狀態(tài)的失效函數(shù)為0，如f(1)=f(3)=0；對(duì)于非第一層狀態(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è)使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。    輸出函數(shù)output的作用是在匹配過程中輸出已經(jīng)匹配的模式串。output的構(gòu)造分兩步，第一步是在構(gòu)造轉(zhuǎn)移函數(shù)g時(shí)，每處理完一個(gè)模式串，則將該模式串加入到當(dāng)前狀態(tài)s的輸出函數(shù)中，如output(2)=he,output(5)=she。第二步是構(gòu)造失效函數(shù)f時(shí)，若f(s)=s,則output(s)=output(s)

10、output(s),如output(5)=output(5)output(2)=she,he。    AC算法的匹配過程如下：從狀態(tài)0出發(fā)，每取出文本串中的一個(gè)字符，利用g和f函數(shù)進(jìn)入下一狀態(tài)。當(dāng)某個(gè)狀態(tài)的output函數(shù)不為空時(shí)輸出其值，表示在文本串中找到該模式串。    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ù)雜

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

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