摘要  入侵檢測是網(wǎng)絡(luò)安全的最后一道防線，模式匹配算法是基于特征匹配的入侵檢測系統(tǒng)中的核心算法，模式匹配的效率決定這類入侵檢測系統(tǒng)的性能。本文對入侵檢測系統(tǒng)中的模式匹配算法進(jìn)行了綜述，包括經(jīng)典的單模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法。對各種算法的性能進(jìn)行了分析。最后提出了改進(jìn)模式匹配算法效率的研究方向。
關(guān)鍵詞: 網(wǎng)絡(luò)安全；入侵檢測；模式匹配；多模式匹配

1 引言
    隨著Internet應(yīng)用的普及，網(wǎng)絡(luò)安全問題也日益突出。入侵是指試圖破壞資源的完整性、可用性和保密性的活動的集合。作為防火墻之后網(wǎng)絡(luò)安全的最后一道防線，入侵檢測系統(tǒng)（IDS）是指檢測上述行為的活動，識別出未經(jīng)授權(quán)或越權(quán)訪問系統(tǒng)資源的行為的軟硬件系統(tǒng)。由于入侵檢測系統(tǒng)可以在一定程度上主動預(yù)防和檢測出來自系統(tǒng)內(nèi)、外部的入侵，并作出適當(dāng)響應(yī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)品均屬誤用檢測。誤用檢測中使用的檢測技術(shù)主要有：模式匹配、專家系統(tǒng)、狀態(tài)轉(zhuǎn)移等，而其中因?yàn)槟Ｊ狡ヅ湓砗唵?、可擴(kuò)展性好而最為常用，例如著名開放源碼的入侵檢測系統(tǒng)Snort就是基于模式匹配的。
    由此可見，模式匹配算法的性能直接影響入侵檢測系統(tǒng)的檢測效率。在高速網(wǎng)絡(luò)環(huán)境，如果模式匹配算法來不及處理大量的實(shí)時網(wǎng)絡(luò)數(shù)據(jù)包，必然會丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中就可能包含入侵信息。本文以下部分介紹幾種著名的模式匹配算法，包括單模式匹配算法和多模式匹配算法，為設(shè)計入侵檢測系統(tǒng)選擇模式匹配算法提供指導(dǎo)。

2 單模式匹配算法
    模式匹配是指在給定長度為n的文本串T=T[1]T[2]…T[n]中查找長度為m的模式串P=P[1]P[2]…P[m]的第一次出現(xiàn)的過程。這里T[i]（1≤i≤n），P[j]（1≤j≤m）∈∑（字符集），若在T中能找到P的出現(xiàn)，則稱匹配成功，否則稱匹配失敗。
    一次只能在文本串中對一個模式串進(jìn)行匹配的算法，稱為單模式匹配算法，可同時對多個模式串進(jìn)行匹配的算法稱多模式匹配算法。
    平凡的模式匹配算法（BF算法）中，一趟匹配失敗后，T只后移一個字符，所以算法簡單，但效率低。高效的模式匹配算法都是設(shè)法增大不匹配時T的后移量，本節(jié)下面介紹3種經(jīng)典的快速單模式匹配算法，第3節(jié)介紹著名的多模式匹配算法—AC算法。
2.1 KMP算法
    D.Knuth、J.Morris和V.Pratt提出一種快速模式匹配算法，稱為KMP算法[2]。
    KMP算法的基本思想是：若某趟匹配過程中T[i]和P[j]不匹配，而前j-1個字符已經(jīng)匹配。此時只需右移模式串P，文本串T不動，即指針i不回溯，讓P[k]與T[i]繼續(xù)比較。移動后重新開始比較的位置k僅與模式串P有關(guān)，而與目標(biāo)串S無關(guān)，因此K可以事先確定。若定義函數(shù)next(j)=K，則next函數(shù)的定義應(yīng)為：
    next(j)=Max{k| P[1..K-1]=P[j-k+1.. j-1] }
    KMP算法的時間復(fù)雜度是O(m+n)，空間復(fù)雜度是O(m)，對BF算法進(jìn)行了很大的改進(jìn)。
2.2 BM算法
    KMP算法雖然在不匹配時能使模式串右移若干位，但右移的距離不可能超過一趟匹配操作所進(jìn)行的比較次數(shù)j，存在這一問題的根本原因是KMP算法的匹配操作是從左向右進(jìn)行的。在KMP算法的啟發(fā)下，R.Boyer和J.Moore提出了一種新的快速字符串匹配算法，即BM算法[3]。
    BM算法的基本思想是從右向左進(jìn)行比較。開始時仍是P的最左邊與T的最左邊對齊，但首先進(jìn)行Pm與Tm的比較。當(dāng)某趟比較中出現(xiàn)不匹配時，BM算法采用兩條啟發(fā)性規(guī)則計算模式串右移的距離，即壞字符規(guī)則和好后綴規(guī)則。
1) 壞字符規(guī)則（Bad Character）
    P中的某個字符與T中的某個字符不相同時使用壞字符規(guī)則右移模式串P，P右移的距離可以通過delta1函數(shù)計算出來。delta1函數(shù)的定義如下：

2) 好后綴規(guī)則(Good Suffix)
    壞字符規(guī)則沒有考慮已經(jīng)取得的部分匹配的情況，而KMP算法卻考慮了。該規(guī)則將KMP算法和BM算法的思想結(jié)合起來，在不丟失真解的前提下確定一個新的移動距離delta2，該函數(shù)與樣本P有關(guān)。具體分以下兩種情況，如圖1所示。
 ·P中間的某一子串P[j-s+1..m-s]與已比較部分P[j+1..m]相同，可讓P右移s位。
 ·P已比較部分P[j+1..m]的后綴P[s+1..m]與P的前綴P[1..m-s]相同，可讓P右移s位。
滿足上面情況的s的最小值為最佳右移距離。delta2的定義如下：
delta2（j）=min{s|(P[j+1..m]=P[j-s+1..m-s])&&(P[j]≠P[j-s])(j>s),P[s+1..m]=P[1..m-s](j≤s)}

    在匹配過程中，取delta1和delta2中的大者。BM算法的最壞時間復(fù)雜度為O(m•n)，但實(shí)際比較次數(shù)只有文本串長度的20%～30%。
2.3 RK算法
    RK算法[4]是Turing獎獲得者R.M.Karp和M.O.Rabin在1981年提出來的，該算法采用了與KMP算法和BM算法完全不同的方法。該算法利用Hash方法和素數(shù)理論，首先定義一個Hash函數(shù)，然后將模式串P和文本串T中長度為m的子串利用Hash函數(shù)轉(zhuǎn)換成數(shù)值。顯然只需比較那些與模式串具有相同Hash函數(shù)值的子串，從而提高了效率。當(dāng)然因?yàn)镠ash沖突的存在，還要進(jìn)一步進(jìn)行字符串比較，但只要選擇適當(dāng)?shù)乃財?shù)Hash沖突的概率就會很小。
設(shè)c=|∑|，Hash函數(shù)為h(r)=r mod q，這里q是在區(qū)間[1..n2m]中隨機(jī)選取的適當(dāng)大的素數(shù)，asc(c)為任意字符c的Ascii碼。將模式串P映射成整數(shù)x（0≤x≤q-1）的方法為：
p=h(asc(P[1])cm-1+ asc(P[2])cm-2+…+asc(P[m-1])c1+asc(P[m]))
同理，將文本串T中長度為m的子串ti=T[i..i+m-1] 映射成整數(shù)ti的方法為：
ti=h(asc(T[i])cm-1+ asc(T[i+1])cm-2+…+asc(T[i+m-2])c1+asc(T[i+m-1]))
為了快速計算T中每個長度為m的子串的Hash函數(shù)值，可以推導(dǎo)出遞推公式：
ti+1=h(asc(T[i+1])cm-1+ asc(T[i+2])cm-2+…+asc(T[i+m-1])c1+asc(T[i+m]))
   =(c(ti-asc(T[i])cm-1) +asc(T[i+m])) mod q
    其中i=1..n-m，根據(jù)這一遞推公式可很容易地計算出T中每個長度為m的子串的Hash函數(shù)值。
    如果不考慮字符匹配所需時間，RK算法的時間復(fù)雜度是O(n+m)，若考慮字符匹配所需時間，則RK算法的時間應(yīng)是O(m•n)。但實(shí)際應(yīng)用中，可設(shè)法取q適當(dāng)大，使得在計算機(jī)中求余仍可執(zhí)行而Hash沖突又幾乎不可能發(fā)生，從而使得KR算法的實(shí)際運(yùn)行時間只需O(m+n)。

3 多模式匹配的AC算法
3.1 入侵檢測中多模式匹配的必要性
    在網(wǎng)絡(luò)入侵檢測系統(tǒng)中，一個網(wǎng)絡(luò)數(shù)據(jù)包的內(nèi)容可能匹配或部分匹配很多條規(guī)則，因此在匹配每條規(guī)則時都會重新運(yùn)行匹配算法，導(dǎo)致效率降低。如snort的web-coldfusion.rules規(guī)則就包含16條規(guī)則，而這16條規(guī)則中都包含/cfdocs/。但如果當(dāng)前包中沒有/cfdocs/，則與這16條規(guī)則的匹配完全不必進(jìn)行，但根據(jù)前面單模式匹配的思想這16次匹配又都必須進(jìn)行。隨著攻擊手段的增加，規(guī)則集中的規(guī)則必然成倍增加，如snort 1.6.3的規(guī)則為854條，而snort 1.8.3的規(guī)則為1270條。因此，單純提高單模式匹配算法的效率，很難滿足未來入侵檢測系統(tǒng)的要求。多模式匹配算法只需對文本串掃描一次就可以找出模式串集合中與其匹配的全部模式串，從而大大提高匹配效率。下面介紹最經(jīng)典的多模式匹配算法—AC算法。
3.2 AC算法
    AC算法[5]是基于FSA（有窮狀態(tài)自動機(jī)）的，在進(jìn)行匹配之前先對模式串集合Sp進(jìn)行預(yù)處理，形成樹型FSA，然后只需對文本串T掃描一次就可以找出與其匹配的所有模式串。
    預(yù)處理生成3個函數(shù)：goto（轉(zhuǎn)移）函數(shù)，failure（失效）函數(shù)和output（輸出）函數(shù)。
    設(shè)U={0，1，2…}為狀態(tài)集合，轉(zhuǎn)移函數(shù)g:(U,Sp)→U為一映射，其建立過程為：逐個取出Sp中模式串的每個字符，從狀態(tài)0出發(fā)，由當(dāng)前狀態(tài)和新取出的字符決定下一狀態(tài)。如果有從當(dāng)前狀態(tài)出發(fā)并標(biāo)注該字符的矢線，則將矢線所指的狀態(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)。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)某個模式與文本匹配不成功時，應(yīng)處理的下一狀態(tài)。f的構(gòu)造方法為：所有第一層狀態(tài)的失效函數(shù)為0，如f(1)=f(3)=0；對于非第一層狀態(tài)s，若其父狀態(tài)為r（即存在字符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。
    輸出函數(shù)output的作用是在匹配過程中輸出已經(jīng)匹配的模式串。output的構(gòu)造分兩步，第一步是在構(gòu)造轉(zhuǎn)移函數(shù)g時，每處理完一個模式串，則將該模式串加入到當(dāng)前狀態(tài)s的輸出函數(shù)中，如output(2)={he},output(5)={she}。第二步是構(gòu)造失效函數(shù)f時，若f(s)=s’,則output(s)=output(s)∪output(s’),如output(5)=output(5)∪output(2)={she,he}。
    AC算法的匹配過程如下：從狀態(tài)0出發(fā)，每取出文本串中的一個字符，利用g和f函數(shù)進(jìn)入下一狀態(tài)。當(dāng)某個狀態(tài)的output函數(shù)不為空時輸出其值，表示在文本串中找到該模式串。
    AC算法模式匹配的時間復(fù)雜度是O(n)，而且與模式集中模式串的個數(shù)和每個模式串的長度無關(guān)。無論模式串P是否出現(xiàn)在T中，T中的每個字符都必須輸入狀態(tài)機(jī)中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復(fù)雜度都是O(n)。包括預(yù)處理時間在內(nèi)，AC算法總時間復(fù)雜度是O(M+n)，其中M為所有模式串的長度總和。
    對多模式串的匹配而言，雖然AC算法比BM算法高效得多。但AC算法必須逐一地查看文本串的每個字符，而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ù)一種前綴關(guān)鍵字樹來計算劣勢移動表和優(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ù)來不及處理而使入侵漏報。而目前實(shí)用的網(wǎng)絡(luò)入侵檢測系統(tǒng)多是基于特征匹配的系統(tǒng)，這類系統(tǒng)中的關(guān)鍵運(yùn)算是模式匹配運(yùn)算，因此提高模式匹配的效率是提高這類系統(tǒng)檢測能力的關(guān)鍵所在。本文對已有的模式匹配算法進(jìn)行了綜述，主要包括3中重要的單模式匹配算法和AC多模式匹配算法。將快速單模式匹配算法與多模式匹配算法相結(jié)合是今后改進(jìn)模式匹配算法努力的方向。

參考文獻(xiàn)
[1] Hochberg J,Jackson K, Stallings C,et al.NADIR:An Automated System for Detecting Network Intrusion and Misuse.Computers and Security, 1993,12(3):235-248
[2] Knuth DE , Morris JH , Pratt VR. Fast Pattern Matching in Strings[J ] , SIAM Journal on Computer , 1977 , 6 (2) :323-350.
[3] Boyer RS , Moore JS. A Fast String Searching Algorithm[J ] . Communications of the ACM ,1977 ,20(10) :762-772.
[4] Crochemorc M,Rytter W.Text Algorithms.Oxford University Press.1994
[5] Aho AV,Corasick MJ.Efficient String Matching:An Aid to Bibliographic Search. Communications of the ACM ,1975 ,18(6) :333-340.