模式匹配算法在入侵檢測中的應(yīng)用

摘 要：僅依靠傳統(tǒng)的被動防御技術(shù)已經(jīng)不能滿足如今的網(wǎng)絡(luò)安全需要，基于模式匹配的入侵檢測系統(tǒng)正成為研究和應(yīng)用的熱點，模式匹配效率的高低決定了這類入侵檢測系統(tǒng)的性能。全面綜述了應(yīng)用于入侵檢測系統(tǒng)的經(jīng)典的模式匹配算法，包括單模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC―BM算法，并對各種算法的執(zhí)行效率進(jìn)行了總結(jié)。通過分析算法的思想，提出了未來此類算法的研究方向。
關(guān)鍵詞：入侵檢測；KMP算法；BM算法；RK算法；AC算法；AC―BM算法

0 引 言
隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，各種基于網(wǎng)絡(luò)的應(yīng)用層出不窮。面對日益突出的網(wǎng)絡(luò)安全問題，僅靠傳統(tǒng)的被動防御已經(jīng)不能滿足要求，能夠主動檢測并預(yù)防的入侵檢測系統(tǒng)應(yīng)運而生。
根據(jù)采用的分析方法，入侵檢測分為誤用檢測和異常檢測。誤用檢測是指：根據(jù)己知的攻擊方法，預(yù)先定義入侵特征，通過判斷這此特征是否出現(xiàn)來完成檢測任務(wù)。異常檢測是指：根據(jù)用戶的行為或資源的使用狀況的正常程度來判斷是否屬于入侵。由于異常檢測的誤檢率和漏檢率高，因此目前大多數(shù)人侵檢測系統(tǒng)產(chǎn)品均主要采用誤用檢測的方法。誤用檢測中使用的檢測技術(shù)主要有：模式匹配、專家系統(tǒng)、狀態(tài)轉(zhuǎn)移等，其中模式匹配原理簡單，可擴(kuò)展性好，而且最為常用。據(jù)統(tǒng)計，現(xiàn)在大約95%的入侵檢測都是特征匹配的入侵檢測。由此可見，模式匹配算法性能的好壞直接影響到入侵檢測系統(tǒng)的效率。隨著網(wǎng)絡(luò)傳輸速度的大幅度提高，入侵檢測系統(tǒng)需要處理的數(shù)據(jù)量越來越大，如果模式匹配算法來不及處理這些實時的大量的數(shù)據(jù)包，必然會丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中很可能就包含有入侵信息，從而造成漏報。在此介紹幾種著名的用于入侵檢測的模式匹配算法，包括單模式匹配算法和多模式匹配算法，通過對它們進(jìn)行剖析和實際測試，提出入侵檢測系統(tǒng)中模式匹配算法的選擇策略和未來的研究方向。

1 單模式匹配算法
1．1 相關(guān)定義
模式匹配：是指在給定長度為n的目標(biāo)串T=T1T2…Tn中查找長度為m的模式串P=P1P2…Pm的首次出現(xiàn)或多次出現(xiàn)的過程。這里Ti(1≤i≤n)，Pj(1≤j≤m)∈∑(字符集)，若P在T中出現(xiàn)1次或多次，則稱匹配成功，否則稱匹配失敗。單模式匹配算法：在目標(biāo)串中1次只能對1個模式串進(jìn)行匹配的算法。
多模式匹配算法：在目標(biāo)串中可同時對多個模式串進(jìn)行匹配的算法。
最簡單的模式匹配算法是Brute―Force算法(BF算法)。在BF算法的目標(biāo)串和模式串的字符比較中，只要有1個字符不相等，而不管前面已有多少個字符相等，就需要把目標(biāo)串T回退，下次比較時目標(biāo)串T只后移1個字符。雖然算法簡單，但效率低下，不適合用于入侵檢測系統(tǒng)中，不做重點介紹。
高效的模式匹配算法都是設(shè)法增大不匹配時目標(biāo)串T或模式串P之間的偏移量，以減少總的比較次數(shù)。下面介紹3種經(jīng)典的快速單模式匹配算法。
1．2 KMP算法
1970年，S．A．Cook從理論上證明了一維模式匹配問題可以在O(m+2)時間內(nèi)解決。D．E．Knuth，V．R．Pratt和T．H．Morris在BF算法的基礎(chǔ)上提出了一種快速模式匹配算法，稱為KMP算法，該算法消除了BF算法的目標(biāo)串指針在相當(dāng)多個字符比較相等后，只要有1個字符比較不等便需要回溯的缺點，使算法的效率得到了大幅度提高，時間復(fù)雜度達(dá)到最理想的O(m+n)，空間復(fù)雜度是O(m)。
KMP算法的基本思想是：若某趟匹配過程中Ti和Pj不匹配，而前j一1個字符已經(jīng)匹配。此時只需右移模式串P，目標(biāo)串T不動，即指針i不回溯，讓Pk與Ti繼續(xù)比較。移動后重新開始比較的位置k僅與模式串P有關(guān)，而與目標(biāo)串T無關(guān)，因此k可以通過下面的next函數(shù)事先確定。
定義next[j]函數(shù)為：

1．3 BM算法
相對于BF算法，KMP算法雖然消除了主串指針的回溯，在不匹配時能使模式串右滑若干位，但由上述next函數(shù)可知：右滑的最大距離不會超過1趟匹配操作所進(jìn)了的比較次數(shù)j，原因在于KMP算法的匹配操作是從左到右進(jìn)行的。受到KMP算法的啟發(fā)，R．S．Boyer和J．S．Moore提出一種新的快速字符串匹配算法一BM算法。
BM算法基本思想是：開始時將目標(biāo)串T與模式串P左對齊，自右至左逐個字符進(jìn)行比較(即首先比較Pm與Tm)；當(dāng)某趟比較時Ti與模式串的對應(yīng)字符不匹配，則把模式串右滑d(x)一段距離，執(zhí)行由Pm與Ti+d(x)起始的自右至左的匹配檢查。BM算法采用以下兩條規(guī)則計算模式串右移的距離：
(1)好后綴移動。其又分為2種情況：
①P已比較部分P[j+1…m]與其中間的某一子串P[j一s+l…m―s]相同，P右移s位。如圖1所示。

②P已比較部分P[j+l…m]的后綴P[s+l…m]與P的前綴P[l…m―s]相同，P右移s位。如圖2所示。

取滿足上述兩種情況的s的最小值作為移動距離。因此可以定義一個距離函數(shù)distl(j)：