入侵檢測(cè)模式匹配算法的研究與改進(jìn)

摘要：模式匹配算法是實(shí)現(xiàn)基于規(guī)則檢測(cè)的核心技術(shù)，其效率直接影響到入侵檢測(cè)系統(tǒng)的準(zhǔn)確性和實(shí)時(shí)性。通過(guò)分析傳統(tǒng)的模式匹配算法BM算法和BMH算法等，提出一種基于BM跳躍思想的模式匹配改進(jìn)算法，簡(jiǎn)化了初始化過(guò)程，加大了匹配失敗后向后跳躍的幅度。經(jīng)過(guò)算法測(cè)試，與原算法相比新算法可以有效的減少比較次數(shù)，提高模式匹配效率。

關(guān)鍵詞：模式匹配算法；BM算法；BMH算法；入侵檢測(cè)

1 引言

隨著信息技術(shù)的發(fā)展，計(jì)算機(jī)成為社會(huì)活動(dòng)中的必不可少的工具，大量重要的信息存儲(chǔ)在系統(tǒng)中，同時(shí)，連入網(wǎng)絡(luò)中的計(jì)算機(jī)數(shù)量也在成倍增加，這些都使得信息安全問(wèn)題日益嚴(yán)重。入侵檢測(cè)作為一種新的計(jì)算機(jī)系統(tǒng)安全防御措施，已經(jīng)成為網(wǎng)絡(luò)安全的一個(gè)重要的研究領(lǐng)域。

入侵檢測(cè)系統(tǒng)(Intrusion Detection System，IDS)是一種能夠通過(guò)分析系統(tǒng)安全相關(guān)數(shù)據(jù)來(lái)檢測(cè)入侵活動(dòng)的硬件或者軟件系統(tǒng)。該系統(tǒng)對(duì)系統(tǒng)資源的非授權(quán)使用能夠做出及時(shí)的判斷、記錄和報(bào)警。在基于規(guī)則的入侵檢測(cè)系統(tǒng)中，模式匹配算法非常重要，它直接影響到系統(tǒng)的準(zhǔn)確性和實(shí)時(shí)性能，其效率的高低直接決定了整個(gè)入侵檢測(cè)系統(tǒng)的性能的高低。

2 BM和BMH算法介紹

2.1 BM算法

R.Boyer和J.Moore于1977年提出了一種快速字符串匹配算法，即BM算法。該算法是一個(gè)非常著名的模式匹配算法，它是目前所知道的平均情況下效率最好的算法，也是目前基于規(guī)則入侵檢測(cè)系統(tǒng)常用的算法。

BM算法的主要思想為：

匹配自右向左進(jìn)行，將長(zhǎng)度為m的模式串P和長(zhǎng)度為n的文本串T從左端對(duì)齊，使得P1與T1對(duì)齊。匹配先從模式串P的最右端字符開(kāi)始，判斷Pm是否與Tm相等，如果匹配成功，則向左移動(dòng)，判斷Pm-1是否與Tm-1相等。這樣繼續(xù)下去，直到模式串P全部匹配成功或是有不匹配的情況出現(xiàn)；

若匹配失敗發(fā)生在Ti≠Pj，且Ti不出現(xiàn)在模式P中，則將模式右移，直到Pl位于匹配失敗位Ti的右邊第1位(即Ti+l位)，若Ti在模式串P中有若干地方出現(xiàn)，則應(yīng)選擇i=dist[x]，其中dist[x]=m-max{k|P[k]=x， 1≤k＜m}；

若模式串P后面k位和文本串T中一致的部分，有一部分在模式串P中其他部分出現(xiàn)，則可將P向右移動(dòng)，直接使這部分對(duì)齊，且要求這一致部分盡可能地大。

BM算法德語(yǔ)處理時(shí)間復(fù)雜度為O(m+s)，空間復(fù)雜度為O(s)，搜索階段時(shí)間復(fù)雜度為O(mn)。最壞情況下要進(jìn)行3n次比較，最好情況下的時(shí)間復(fù)雜度為O(n/m)。其中m為模式串P的長(zhǎng)度，n為文本串T的長(zhǎng)度，s是與P、T相關(guān)的有限字符集長(zhǎng)度。

2.2 BMH算法[3]

BM算法為了確定在不匹配的情況下最大的可行移位距離而使用了兩種啟發(fā)，即壞字符和好后綴啟發(fā)。兩種啟發(fā)均能導(dǎo)致最大為m（若子模式串的長(zhǎng)度為m）的移動(dòng)距離，但是由于好后綴啟發(fā)的預(yù)處理非常難以理解和實(shí)現(xiàn)，Horspool于1980年發(fā)表了改進(jìn)與簡(jiǎn)化BM算法的論文，即BMH算法。該算法在移動(dòng)模式時(shí)僅考慮了壞字符啟發(fā)。

BMH算法的基本思想是：首先比較文本指針?biāo)缸址湍Ｊ降淖詈笠粋€(gè)字符，如相等再比較其余m-1個(gè)字符。無(wú)論文本串T中哪個(gè)字符造成了匹配失敗，都將由文本中和模式最后一個(gè)位置對(duì)應(yīng)的字符來(lái)啟發(fā)模式向右的滑動(dòng)。首先比較模式末尾的字符，其余的字符比較順序沒(méi)有限制。對(duì)于不匹配的情況只進(jìn)行壞字符機(jī)制處理，處理方式改變?yōu)榘l(fā)生不匹配后，依據(jù)模式串最末處的文本字符的壞字符啟發(fā)來(lái)移動(dòng)。

BMH算法預(yù)處理時(shí)間復(fù)雜度為O(m+s)，空間復(fù)雜度為O(s)，搜索階段時(shí)間復(fù)雜度為O(mn)。在一般情況下，BMH算法比BM有更好的性能，它只使用了一個(gè)數(shù)組，簡(jiǎn)化了初始化過(guò)程，省去了求最大值的計(jì)算。

3 改進(jìn)的模式匹配算法

基于對(duì)上述幾種模式匹配算法的分析研究，本文提出了一種對(duì)BM算法進(jìn)一步改進(jìn)的算法。

算法思想描述如下：

當(dāng)模式匹配失敗時(shí)，首先判斷文本串T中和模式串P的最后一個(gè)位置對(duì)應(yīng)字符的下一個(gè)字符i是否出現(xiàn)在模式串P中，如果該字符i不出現(xiàn)在模式串P中，將該字符i的下一個(gè)字符與模式串的最左端P1對(duì)齊，重新進(jìn)行比較。否則，判斷與模式串P的最后一個(gè)位置對(duì)應(yīng)的字符j是否出現(xiàn)在模式串P中，如果該字符j不出現(xiàn)在模式串P中，將該字符j與模式串P的最左端P1對(duì)齊，重新進(jìn)行比較；若字符j出現(xiàn)在模式串P中，無(wú)論文本中哪個(gè)字符造成了匹配失敗，都將由文本中和模式最后一個(gè)位置對(duì)應(yīng)的字符的下一字符來(lái)按壞字符啟發(fā)模式向右滑動(dòng)相應(yīng)的位數(shù)s，重新進(jìn)行比較。依次循環(huán)，直到完全匹配成功或都不匹配為止。舉例描述如表3所示：

本例中按改進(jìn)后的算法匹配了四趟，共比較了7+6次。

改進(jìn)后的算法預(yù)處理時(shí)間復(fù)雜度為O(m+s)，空間復(fù)雜度為O(s)，搜索階段時(shí)間復(fù)雜度為O(mn)。

在模式串P中重復(fù)的字符較多時(shí)或T中字符大多在模式串P中出現(xiàn)時(shí)，該算法可進(jìn)一步改進(jìn)為，若文本串T中與模式串P最后字符對(duì)應(yīng)的字符以及其下一個(gè)字符都出現(xiàn)在模式串P中，則比較兩者最終按壞字符啟發(fā)需要滑動(dòng)的距離大小，然后按滑動(dòng)距離大的字符滑動(dòng)，重新進(jìn)行比較。

進(jìn)一步的改進(jìn)后的算法增加了預(yù)處理時(shí)間，和比較選擇滑動(dòng)距離的時(shí)間。由于只是在必要時(shí)進(jìn)行簡(jiǎn)單的大小比較，進(jìn)行比較所花費(fèi)的時(shí)間不會(huì)太多。該算法能夠確保在不失真值的情況下滑動(dòng)盡可能大的距離，以提高匹配效率。

改進(jìn)后的算法預(yù)處理時(shí)間復(fù)雜度為O(m+s)，空間復(fù)雜度為O(s)，搜索階段時(shí)間復(fù)雜度為O(mn)。

通過(guò)舉例比較，可以看出改進(jìn)后的算法比BM算法減少了匹配次數(shù)，性能有所提高，具有一定的優(yōu)越性。

4 算法測(cè)試結(jié)果

實(shí)驗(yàn)機(jī)配置：CPU P42.0、內(nèi)存1GB、硬盤(pán)80GB，操作系統(tǒng)RedHat Linux9.0。

為了測(cè)試本文所涉及到的算法的效率，我們進(jìn)行了兩組測(cè)試。第一組測(cè)試分別用不同的文本和模式，對(duì)BM算法、BMH算法、改進(jìn)的算法進(jìn)行匹配次數(shù)的測(cè)試。測(cè)試結(jié)果如表1所示：

第二組測(cè)試，在網(wǎng)絡(luò)中隨機(jī)捕獲100MB數(shù)據(jù)。從經(jīng)典入侵檢測(cè)軟件Snort模式庫(kù)中隨機(jī)地抽出模式字符串來(lái)進(jìn)行實(shí)驗(yàn)測(cè)試。測(cè)試的結(jié)果如下表2所示：

通過(guò)反復(fù)測(cè)試發(fā)現(xiàn)，在比較的四個(gè)算法中，新算法1每次查找所匹配的次數(shù)最少，效率方面與BMH算法接近。新算法2每次匹配的次數(shù)少于BM算法，效率方面與BM算法接近。通常在查找的模式串出現(xiàn)在文本中重復(fù)率高時(shí)，新算法的效率明顯高于BM算法和BMH算法。

5 小結(jié)

本文通過(guò)分析BM和BMH等模式匹配算法，提出了一種以BM算法思想為基礎(chǔ)，結(jié)合BMH算法的簡(jiǎn)化思想的進(jìn)一步改進(jìn)BM算法的方法。該算法采用了BM算法中的跳躍比較思想和BMH簡(jiǎn)化方法以及向下一位匹配的思想，進(jìn)而簡(jiǎn)化了初始化過(guò)程，加大了匹配失敗后向后跳躍的幅度，減少了比較次數(shù)，提高了模式匹配效率。通過(guò)算法測(cè)試比較，達(dá)到了預(yù)期效果。

參考文獻(xiàn)

[1] 伊靜，劉培玉.入侵檢測(cè)中模式匹配算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件，2005，22(1):112-114.

[2]牟永敏，李美貴，梁琦.入侵檢測(cè)系統(tǒng)中模式匹配算法的研究[J].電子學(xué)報(bào).2006，34(12):2488-

2490.

[3]賀龍濤，方濱興，余翔湛.一種時(shí)間復(fù)雜度最優(yōu)的精確串匹配算法[J].軟件學(xué)報(bào).2005，16(5): 676-683.

[4]孫克雷.IDS中一種快速模式匹配算法[J].安徽理工大學(xué)學(xué)報(bào).2006，26()