摘 要：僅依靠傳統(tǒng)的被動(dòng)防御技術(shù)已經(jīng)不能滿足如今的網(wǎng)絡(luò)安全需要，基于模式匹配的入侵檢測系統(tǒng)正成為研究和應(yīng)用的熱點(diǎn)，模式匹配效率的高低決定了這類入侵檢測系統(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)的被動(dòng)防御已經(jīng)不能滿足要求，能夠主動(dòng)檢測并預(yù)防的入侵檢測系統(tǒng)應(yīng)運(yùn)而生。
    根據(jù)采用的分析方法，入侵檢測分為誤用檢測和異常檢測。誤用檢測是指：根據(jù)己知的攻擊方法，預(yù)先定義入侵特征，通過判斷這此特征是否出現(xiàn)來完成檢測任務(wù)。異常檢測是指：根據(jù)用戶的行為或資源的使用狀況的正常程度來判斷是否屬于入侵。由于異常檢測的誤檢率和漏檢率高，因此目前大多數(shù)人侵檢測系統(tǒng)產(chǎn)品均主要采用誤用檢測的方法。誤用檢測中使用的檢測技術(shù)主要有：模式匹配、專家系統(tǒng)、狀態(tài)轉(zhuǎn)移等，其中模式匹配原理簡單，可擴(kuò)展性好，而且最為常用。據(jù)統(tǒng)計(jì)，現(xiàn)在大約95%的入侵檢測都是特征匹配的入侵檢測。由此可見，模式匹配算法性能的好壞直接影響到入侵檢測系統(tǒng)的效率。隨著網(wǎng)絡(luò)傳輸速度的大幅度提高，入侵檢測系統(tǒng)需要處理的數(shù)據(jù)量越來越大，如果模式匹配算法來不及處理這些實(shí)時(shí)的大量的數(shù)據(jù)包，必然會(huì)丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中很可能就包含有入侵信息，從而造成漏報(bào)。在此介紹幾種著名的用于入侵檢測的模式匹配算法，包括單模式匹配算法和多模式匹配算法，通過對它們進(jìn)行剖析和實(shí)際測試，提出入侵檢測系統(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個(gè)模式串進(jìn)行匹配的算法。
    多模式匹配算法：在目標(biāo)串中可同時(shí)對多個(gè)模式串進(jìn)行匹配的算法。
    最簡單的模式匹配算法是Brute—Force算法(BF算法)。在BF算法的目標(biāo)串和模式串的字符比較中，只要有1個(gè)字符不相等，而不管前面已有多少個(gè)字符相等，就需要把目標(biāo)串T回退，下次比較時(shí)目標(biāo)串T只后移1個(gè)字符。雖然算法簡單，但效率低下，不適合用于入侵檢測系統(tǒng)中，不做重點(diǎn)介紹。
    高效的模式匹配算法都是設(shè)法增大不匹配時(shí)目標(biāo)串T或模式串P之間的偏移量，以減少總的比較次數(shù)。下面介紹3種經(jīng)典的快速單模式匹配算法。
1．2 KMP算法
    1970年，S．A．Cook從理論上證明了一維模式匹配問題可以在O(m+2)時(shí)間內(nèi)解決。D．E．Knuth，V．R．Pratt和T．H．Morris在BF算法的基礎(chǔ)上提出了一種快速模式匹配算法，稱為KMP算法，該算法消除了BF算法的目標(biāo)串指針在相當(dāng)多個(gè)字符比較相等后，只要有1個(gè)字符比較不等便需要回溯的缺點(diǎn)，使算法的效率得到了大幅度提高，時(shí)間復(fù)雜度達(dá)到最理想的O(m+n)，空間復(fù)雜度是O(m)。
    KMP算法的基本思想是：若某趟匹配過程中Ti和Pj不匹配，而前j一1個(gè)字符已經(jīng)匹配。此時(shí)只需右移模式串P，目標(biāo)串T不動(dòng)，即指針i不回溯，讓Pk與Ti繼續(xù)比較。移動(dòng)后重新開始比較的位置k僅與模式串P有關(guān)，而與目標(biāo)串T無關(guān)，因此k可以通過下面的next函數(shù)事先確定。
    定義next[j]函數(shù)為：

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

    (2)壞字符移動(dòng)。P中的某個(gè)字符與T中的某個(gè)字符不相同時(shí)使用壞字符移動(dòng)。右滑距離函數(shù)dist2(x)定義如下：

   
    匹配時(shí)取移動(dòng)距離為：dist=max{distl(j)，dist2}。文獻(xiàn)證明算法需要的預(yù)處理時(shí)間為O(m+σ)，最壞運(yùn)行時(shí)間為O[(n—m+1)m+σ]，即掃描部分運(yùn)行時(shí)間為O[(n—m)m]。在大字母表(相對于模式長度)情況下，BM算法非常快，實(shí)際比較次數(shù)只有目標(biāo)串長度的20％～30％。
1．4 RK算法
    Karp和Rabin在1981年提出來的RK算法利用了Hash方法和素?cái)?shù)理論。
    RK算法的思想是：首先定義一個(gè)Hash函數(shù)，用該函數(shù)計(jì)算出模式串P的Hash函數(shù)值，再計(jì)算出目標(biāo)串T中所有長度為m的子串的Hash函數(shù)值，然后用相應(yīng)的Hash函數(shù)值進(jìn)行比較。當(dāng)出現(xiàn)Hash沖突時(shí)，再進(jìn)行相應(yīng)字符串的比較，當(dāng)構(gòu)造Hash函數(shù)的素?cái)?shù)選擇得合理，Hash沖突出現(xiàn)的概率就可以做到很小。
    Hash函數(shù)的構(gòu)造及相應(yīng)Hash值的計(jì)算如下：

    設(shè)c∈∑，構(gòu)造Hash函數(shù)：
    h(asc(c))=asc(c)mod q
    式中：q∈[1…n2m]且為素?cái)?shù)；asc(c)為任意字符c的ASCII碼。
    映射模式串P為Hash函數(shù)值x(0≤x≤q一1)的方法為：
    令：

   
    同理，映射目標(biāo)串T中長度為m的子串t1=T[i…i+m一1]為Hash函數(shù)值ti的方法是：
    令：

    根據(jù)上述公式可把目標(biāo)串T中每個(gè)長度為m的子串的Hash函數(shù)值計(jì)算出來。
    如果Hash沖突不發(fā)生，即不再需要額外的字符匹配，RK算法的時(shí)間復(fù)雜度是O(m+n)；若考慮字符匹配，則RK算法的時(shí)間復(fù)雜度是0(mn)。在實(shí)際應(yīng)用中，可設(shè)法取適當(dāng)大的素?cái)?shù)q，使得mod q仍可執(zhí)行并且Hash沖突又幾乎不發(fā)生，從而使得KR算法的實(shí)際運(yùn)行時(shí)間只需O(m+n)。
    RK算法采用了與KMP和BF算法不同的思路，盡量減少字符之間的比較次數(shù)，從而達(dá)到提高效率的目的。
1．5 單模式匹配算法改進(jìn)情況簡介
    研究人員對單模式匹配算法提出了不少變形和改進(jìn)算法。
    在文獻(xiàn)中黃占友等人提出的KMP算法的改進(jìn)對特殊的字符串能夠提高效率；文獻(xiàn)中龐善臣等人對BM算法的改進(jìn)有效地減少了最壞情況下的比較次數(shù)，同時(shí)方便在二位匹配和不精確匹配中推廣；文獻(xiàn)中賀龍濤等人通過將好后綴與壞字符兩種情況合并進(jìn)行處理對BM進(jìn)行改進(jìn)。采用該思想的同類改進(jìn)算法還有很多，如：發(fā)表于2006年12月32卷23期《計(jì)算機(jī)工程》上渠瑜等人的對《對BM模式匹配算法的一個(gè)改進(jìn)》，限于篇幅，不一一列舉。在文獻(xiàn)中張國平等人對BM算法的改進(jìn)是通過定義一個(gè)距離函數(shù)來求出每次匹配失敗時(shí)的最大可能移動(dòng)距離；文獻(xiàn)蔡曉妍等人對BM算法的改進(jìn)則是結(jié)合了BM算法和TunedBM算法的優(yōu)點(diǎn)，采用TunedBM的壞字符和BM的好后綴對模式進(jìn)行預(yù)處理，然后根據(jù)當(dāng)前嘗試中匹配失敗字符的位置信息，決定查找好后綴跳躍表還是壞字符跳躍表以期獲得更大的跳躍距離。文獻(xiàn)張立航等人對RK算法的改進(jìn)是通過引入2次Hash運(yùn)算進(jìn)行的。通過兩次Hash運(yùn)算使出現(xiàn)Hash沖突的情況大為減少。

2 多模式匹配算法
2．1 入侵檢測中采用多模式匹配的必要性
    與單模式匹配算法相比，多模式匹配算法的優(yōu)勢在于一趟遍歷可以對多個(gè)模式進(jìn)行匹配，從而大大提高了匹配效率。對于單模式匹配算法，如果要匹配多個(gè)模式，那么有幾個(gè)模式就需要幾趟遍歷。當(dāng)然多模式匹配算法也適用于單模式的情況。在入侵檢測系統(tǒng)中，一條入侵特征可能匹配或部分匹配很多條規(guī)則，如果采用單模式匹配，在匹配每條規(guī)則時(shí)都需要重新運(yùn)行匹配算法，效率很低。然而，日益增多的網(wǎng)絡(luò)攻擊使得入侵檢測的規(guī)則數(shù)目仍在不斷增長，例如，Snort1．8．3的規(guī)則為1 270條，snort2．O的規(guī)則為2 300多條，到Snort 2．6．1則增加到3 600多條規(guī)則，因此，單純提高單模式匹配算法的效率，很難使入侵檢測系統(tǒng)滿足越來越大的網(wǎng)絡(luò)數(shù)據(jù)吞吐量和日益增加的攻擊。
    目前比較常見的多模式匹配算法有Aho—Corasick算法、Aho—COrasick—Boyer-Moore算法、Manber—Wu算法、Set一Wise Boyel-Moore一Hospool算法等。下面介紹其中2種經(jīng)典的多模式匹配算法。
2．2 AC算法
    AC算法1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，最早用于圖書館的書目查詢程序中。該算法基于有限狀態(tài)自動(dòng)機(jī)(FSA)，在進(jìn)行匹配之前先對模式串集合SP進(jìn)行預(yù)處理，形成模式樹(樹形FSA)，然后只需對目標(biāo)串T掃描一次就可以找出所有與其匹配的模式串P。模式樹K的構(gòu)成如下：
    K的每一條邊e上都用1個(gè)字符作為標(biāo)簽；
    與同一節(jié)點(diǎn)相連的邊的標(biāo)簽均不同；
    每1個(gè)模式p∈SP都存在1個(gè)節(jié)點(diǎn)v，使得L(v)=p，其中L(v)表示從根節(jié)點(diǎn)到口所經(jīng)過的所有邊上的標(biāo)簽的拼接；
    每一個(gè)葉子節(jié)點(diǎn)v，都存在一個(gè)模式p∈SP使得以L(v’)=p。
    例如：對于模式集SP={he，she，his，hers}模式樹如圖3所示，其中圓圈表示節(jié)點(diǎn)，雙圈是根節(jié)點(diǎn)，邊上的字符就是該邊的標(biāo)簽，填充點(diǎn)圈的標(biāo)簽就是各個(gè)模式。

    預(yù)處理階段，模式樹的各個(gè)節(jié)點(diǎn)作為狀態(tài)，根節(jié)點(diǎn)作為初態(tài)，標(biāo)簽為模式的節(jié)點(diǎn)作為終態(tài)，利用轉(zhuǎn)向函數(shù)g和失效函數(shù)f作為轉(zhuǎn)移函數(shù)，將模式樹擴(kuò)展成一個(gè)樹型有限自動(dòng)機(jī)。
    由模式樹擴(kuò)展所得的AC自動(dòng)機(jī)M是1個(gè)6元組：

    M=(Q,∑，g，f，q0，F(xiàn))
其中：
    (1)Q是有限狀態(tài)集(模式樹上的節(jié)點(diǎn))；
    (2)∑是有窮的輸入字符表(數(shù)據(jù)包中可能出現(xiàn)的所有字符)；
    (3)g是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：g(s，a)：從當(dāng)前狀態(tài)s開始，沿著邊上標(biāo)簽為a的路徑所到的狀態(tài)。假如(u，v)邊上的標(biāo)簽為a，那么g(u，a)=v；如果根節(jié)點(diǎn)上出來的邊上的標(biāo)簽沒有a，則g(0，a)=O，即如果沒有匹配的字符出現(xiàn)，自動(dòng)機(jī)停留在初態(tài)；
    (4)f(不匹配時(shí)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：
    f(s)：當(dāng)w是L(s)最長真后綴并且w是某個(gè)模式的前綴，那么f(s)就是以w為標(biāo)簽的那個(gè)節(jié)點(diǎn)；
    (5)q0∈Q是初態(tài)(根節(jié)點(diǎn)，標(biāo)識(shí)符為0)；
    (6)XXXXX是終態(tài)集(以模式為標(biāo)簽的節(jié)點(diǎn)集)。
    這樣，在目標(biāo)串中查找模式的過程轉(zhuǎn)化成在模式樹中的查找過程。查找一個(gè)串T時(shí)從模式樹的根節(jié)點(diǎn)開始，沿著以T中字符為標(biāo)簽的路徑往下走：若自動(dòng)機(jī)能夠抵達(dá)終態(tài)v，則說明T中存在模式L(v)；否則不存在模式。
    AC算法模式匹配的時(shí)間復(fù)雜度是0(n)，并且與模式集中模式串的個(gè)數(shù)和每個(gè)模式串的長度無關(guān)。無論模式串P是否出現(xiàn)在目標(biāo)串T中，T中的每個(gè)字符都必須輸入狀態(tài)機(jī)中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時(shí)間復(fù)雜度都是O(n)，包括預(yù)處理時(shí)間在內(nèi)，AC算法總時(shí)間復(fù)雜度是O(M+n)，其中M為所有模式串的長度總和。
2．3 AC—BM算法
    對多模式串的匹配而言，雖然AC算法比BM算法高效得多，但AC算法必須逐一查看目標(biāo)串的每個(gè)字符，即必須按順序輸入，不能實(shí)現(xiàn)跳躍，而BM算法則能夠利用“右滑”跳過目標(biāo)串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發(fā)式搜索技術(shù)應(yīng)用到AC算法中，則可大大提高多模式匹配算法的效率。許多人據(jù)此給出了各種改進(jìn)的算法。Commentz—Walter最先將BM算法和AC算法結(jié)合在一起給出了Com—mentz—Walter算法；Baeza—Yates結(jié)合BMP算法和AC算法也給出了多模式匹配改進(jìn)算法。
    AC—BM算法是Jang—Jong在1993年結(jié)合Ac算法的有限自動(dòng)機(jī)和BM算法的連續(xù)跳躍思想提出來的新算法，利用劣勢移動(dòng)表和優(yōu)勢跳轉(zhuǎn)表來實(shí)現(xiàn)跳躍式地并行搜索，算法的時(shí)間復(fù)雜度為0(mn)。該算法的思想是：首先把要查找的多個(gè)模式構(gòu)成一個(gè)關(guān)鍵字樹，把相同的前綴作為樹的根節(jié)點(diǎn)。模式樹從目標(biāo)串的右端向左移動(dòng)，一旦模式樹確定在適當(dāng)?shù)奈恢茫址容^從左向右開始進(jìn)行。模式樹移動(dòng)時(shí)同時(shí)使用壞字符移動(dòng)和好前綴移動(dòng)。壞字符移動(dòng)的策略為：如果出現(xiàn)不匹配的情況，移動(dòng)模式樹，使得樹中其他模式的能與當(dāng)前目標(biāo)串正在比較的字符相匹配的那個(gè)字符移動(dòng)到與當(dāng)前目標(biāo)串正在比較的字符的相同位置上，如果在當(dāng)前的深度上，目標(biāo)字符沒有出現(xiàn)在任何模式中，則模式樹的偏移量為樹中最短模式的長度。好前綴移動(dòng)的移動(dòng)策略為：將模式樹移動(dòng)到一個(gè)已被發(fā)現(xiàn)是另一個(gè)模式子串完全前綴的下一個(gè)位置，或者移動(dòng)到作為樹中另一個(gè)模式后綴能夠正確匹配目標(biāo)串的某個(gè)前綴的下一個(gè)位置。在模式樹的移動(dòng)過程中，必須確保模式樹的偏移量不能大于樹中最短的模式長度。
2．4 AC，AC—BM算法改進(jìn)情況簡介
    文獻(xiàn)中盧汪節(jié)等人針對AC算法在構(gòu)造狀態(tài)機(jī)時(shí)空間冗余較大的情況，對狀態(tài)機(jī)各結(jié)點(diǎn)進(jìn)行壓縮存儲(chǔ)，使空間性能和時(shí)間性能都有提高；文獻(xiàn)中萬國根等人對AC—BM算法的改進(jìn)借鑒了BMH算法的思想，取消了原算法的好前綴跳轉(zhuǎn)，優(yōu)化了壞字符跳轉(zhuǎn)，并修改了skip的計(jì)算方法，對大字符集的情況在平均情況下具有更優(yōu)的性能；文獻(xiàn)對AC—BM的改進(jìn)則是通過預(yù)處理思想實(shí)現(xiàn)的，在進(jìn)行AC—BM匹配之前首先掃描首和(或)尾字符，確定其位置，再到相應(yīng)位置進(jìn)行匹配，相當(dāng)于把目標(biāo)串按模式串首、尾字符分成數(shù)段，每段進(jìn)行比較，段間不含首字符的就直接跳過，不用比較，從而提高效率。

3 算法的實(shí)際執(zhí)行效率
    上述這些算法究竟哪種算法具有最好的執(zhí)行效率呢?能不能僅通過時(shí)間復(fù)雜度來進(jìn)行衡量呢?時(shí)間復(fù)雜度僅是一個(gè)度量的范圍，表示受幾個(gè)參數(shù)的影響，并不代表一個(gè)具體的值，還需要在具體的環(huán)境中進(jìn)行測試。
    文獻(xiàn)測試了包括上述算法在內(nèi)的多種單模式和多模式匹配算法的性能。測試平臺(tái)為：硬件：CPUIntel Xeon 3．46 GHz X 2，內(nèi)存2 GB DDR，硬盤200GB SCSI；軟件：windows 2003 Server，Intel IXASDK4．1。單模式匹配測試的規(guī)則集，使用隨機(jī)生成的8，16，32，48，128位具有代表意義的規(guī)則，可以對應(yīng)端口、IP地址，MAC地址、IPv6地址等，對多模式匹配測試采用Snort系統(tǒng)2．4．3規(guī)則集。
    單模式匹配算法主要測試模式長度與匹配時(shí)間、占用空間及預(yù)處理時(shí)間的變化關(guān)系。測試結(jié)果表明：各算法的測試指標(biāo)在規(guī)則長度增長的情況下均呈遞增趨勢，但BM算法的增長速度最為緩慢，在不太在意存儲(chǔ)空間的情況下，BM可以作為優(yōu)先考慮的算法，同時(shí)對IPV6地址也更為合適。
    多模式匹配算法的測試項(xiàng)目為規(guī)則數(shù)與單位匹配時(shí)間、占用儲(chǔ)存單元、單位預(yù)處理時(shí)間的變化關(guān)系。測試結(jié)果表明AC—BM算法在上述3項(xiàng)測試中取得了很好的性能平衡。這也是新版的Snort系統(tǒng)中選用AC—BM算法的重要原因。

4 入侵檢測系統(tǒng)中模式匹配算法的研究方向
    常用的模式匹配算法所采用的思想主要有基于字符比較、基于自動(dòng)機(jī)、基于hash查找、基于位邏輯運(yùn)算和基于Tries樹型機(jī)構(gòu)搜索。鑒于目前網(wǎng)絡(luò)的實(shí)際狀況，多模式匹配算法更加適合于基于模式匹配的入侵檢測系統(tǒng)。這里認(rèn)為應(yīng)該從下面3個(gè)方面著手：一是繼續(xù)研究和改進(jìn)精確的模式匹配，將快速的單模式匹配算法和多模式匹配算法相結(jié)合，充分借鑒同類算法的先進(jìn)思想，如：引入Hash函數(shù)、引入自動(dòng)機(jī)、對字符串分塊等來不斷提高多模式匹配算法的性能；二是嘗試采用模糊匹配的策略，國外對此已經(jīng)開始進(jìn)行相應(yīng)的研究；三是對網(wǎng)絡(luò)數(shù)據(jù)包和入侵特征進(jìn)行研究，總結(jié)出這兩類字符串特點(diǎn)，有針對性地對這兩類字符串的匹配問題進(jìn)行研究。

5 結(jié) 語
    網(wǎng)絡(luò)帶寬的不斷增加、日益嚴(yán)重的網(wǎng)絡(luò)安全狀況要求必須盡快提高網(wǎng)絡(luò)入侵檢測系統(tǒng)的性能。雖然入侵檢測系統(tǒng)可以采用很多技術(shù)，并且這些技術(shù)也在不斷的研究和發(fā)展中，但是目前主流的實(shí)用的入侵檢測技術(shù)仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測系統(tǒng)的一個(gè)關(guān)鍵所在。在此對已有的經(jīng)典模式匹配算法進(jìn)行了系統(tǒng)綜述，并對入侵檢測系統(tǒng)中模式匹配算法的未來研究方向給出了觀點(diǎn)。