入侵檢測模式匹配算法的研究與改進

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

關鍵詞：模式匹配算法；BM算法；BMH算法；入侵檢測

1 引言

隨著信息技術的發展，計算機成為社會活動中的必不可少的工具，大量重要的信息存儲在系統中，同時，連入網絡中的計算機數量也在成倍增加，這些都使得信息安全問題日益嚴重。入侵檢測作為一種新的計算機系統安全防御措施，已經成為網絡安全的一個重要的研究領域。

入侵檢測系統(Intrusion Detection System，IDS)是一種能夠通過分析系統安全相關數據來檢測入侵活動的硬件或者軟件系統。該系統對系統資源的非授權使用能夠做出及時的判斷、記錄和報警。在基于規則的入侵檢測系統中，模式匹配算法非常重要，它直接影響到系統的準確性和實時性能，其效率的高低直接決定了整個入侵檢測系統的性能的高低。

2 BM和BMH算法介紹

2.1 BM算法

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

BM算法的主要思想為：

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

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

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

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

2.2 BMH算法[3]

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

BMH算法的基本思想是：首先比較文本指針所指字符和模式的最后一個字符，如相等再比較其余m-1個字符。無論文本串T中哪個字符造成了匹配失敗，都將由文本中和模式最后一個位置對應的字符來啟發模式向右的滑動。首先比較模式末尾的字符，其余的字符比較順序沒有限制。對于不匹配的情況只進行壞字符機制處理，處理方式改變為發生不匹配后，依據模式串最末處的文本字符的壞字符啟發來移動。

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

3 改進的模式匹配算法

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

算法思想描述如下：

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

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

改進后的算法預處理時間復雜度為O(m+s)，空間復雜度為O(s)，搜索階段時間復雜度為O(mn)。

在模式串P中重復的字符較多時或T中字符大多在模式串P中出現時，該算法可進一步改進為，若文本串T中與模式串P最后字符對應的字符以及其下一個字符都出現在模式串P中，則比較兩者最終按壞字符啟發需要滑動的距離大小，然后按滑動距離大的字符滑動，重新進行比較。

進一步的改進后的算法增加了預處理時間，和比較選擇滑動距離的時間。由于只是在必要時進行簡單的大小比較，進行比較所花費的時間不會太多。該算法能夠確保在不失真值的情況下滑動盡可能大的距離，以提高匹配效率。

改進后的算法預處理時間復雜度為O(m+s)，空間復雜度為O(s)，搜索階段時間復雜度為O(mn)。

通過舉例比較，可以看出改進后的算法比BM算法減少了匹配次數，性能有所提高，具有一定的優越性。

4 算法測試結果

實驗機配置：CPU P42.0、內存1GB、硬盤80GB，操作系統RedHat Linux9.0。

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

第二組測試，在網絡中隨機捕獲100MB數據。從經典入侵檢測軟件Snort模式庫中隨機地抽出模式字符串來進行實驗測試。測試的結果如下表2所示：

通過反復測試發現，在比較的四個算法中，新算法1每次查找所匹配的次數最少，效率方面與BMH算法接近。新算法2每次匹配的次數少于BM算法，效率方面與BM算法接近。通常在查找的模式串出現在文本中重復率高時，新算法的效率明顯高于BM算法和BMH算法。

5 小結

本文通過分析BM和BMH等模式匹配算法，提出了一種以BM算法思想為基礎，結合BMH算法的簡化思想的進一步改進BM算法的方法。該算法采用了BM算法中的跳躍比較思想和BMH簡化方法以及向下一位匹配的思想，進而簡化了初始化過程，加大了匹配失敗后向后跳躍的幅度，減少了比較次數，提高了模式匹配效率。通過算法測試比較，達到了預期效果。

參考文獻

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

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

2490.

[3]賀龍濤，方濱興，余翔湛.一種時間復雜度最優的精確串匹配算法[J].軟件學報.2005，16(5): 676-683.

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