入侵檢測系統中一種模式匹配算法的研究與改進

摘要:對基于入侵檢測系統來說，模式匹配算法是基于特征匹配的入侵檢測系統中的核心算法，也是當前入侵檢測設備中普遍應用的算法。它的效率直接影響到入侵檢測系統的準確性和實時性，文章通過對模式匹配算法的改進，提出了一種改進的算法，在匹配文本中重復字符串較多時，該算法可以加快入侵檢測系統的檢測速度，提高現有入侵檢測系統的檢測能力。

關鍵詞:BM算法;入侵檢測系統(IDS);模式匹配

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)05-1101-03

Reasching and Improving of Pattern Matching Algorithm in Intrusion Detection System

ZHU Jun，YU Qiang

(School of Computer Information， Hefei University of Technology， Hefei 230601， China)

Abstract: For the Intrusion Detection System(IDS)， pattern matching algorithm is based on feature matching intrusion detection system in the core algorithm， but also the current intrusion detection equipment widely used algorithms. Its efficiency directly affects the accuracy of intrusion detection systems and real-time， the article through improved pattern matching algorithm is proposed an improved algorithm， repeated in the matching text strings more， the algorithm can speed up the intrusion detection system the detection rate， upgrade the existing intrusion detection system detection capability.

Key words: BM algorithm; intrusion detection system(IDS); pattern matching

由于計算機網絡自身存在的局限性和信息系統的脆弱性，使得計算機網絡系統上的硬件資源，通信資源，軟件及信息資源等因為各種原因而遭到破壞、更改、泄露或功能失效，使得信息系統處于異常狀態，甚至引起系統的崩潰癱瘓，造成巨大的經濟損失。在這樣的形式下，以保護網絡中的信息免受各種攻擊為目的的網絡安全變得越來越重要，對安全方面的考慮提高到了越來越重要的地位上。

在設計現有防護系統的時候，只可能考慮到已知的安全威脅與有限范圍的未知安全威脅。防護技術只能做到盡量阻止攻擊企圖的得逞或者延緩這個過程，而不能阻止各種攻擊事件的發生，這時就需要引入入侵檢測手段加以彌補。

入侵檢測系統(IDS)就是按照一定的安全策略建立相應的安全輔助措施的保障系統。目前IDS軟件的開發方式基本上就是按照這個思路進行的。對IDS的要求是:如果系統遭到攻擊，IDS應盡可能的檢測到，甚至是實時的檢測到入侵攻擊，然后采取適當的處理措施[1]。IDS一般不是采取預防的措施以防止入侵 事件的發生，入侵檢測作為安全技術其作用在于:

1) 識別入侵者;

2) 識別入侵行為;

3) 檢測和監視已成功的安全突破;

4) 為對抗入侵及時提供重要信息，阻止事件的發生和事態的擴大。

從這些角度看待安全問題，入侵檢測非常必要，它將彌補傳統安全保護措施的不足。從目前入侵檢測技術的研究來看，一個重要的環節是對入侵行為特征進行匹配，即規則匹配。規則匹配的過程就是對從網絡上捕獲的每一條數據報文和預先定義的入侵規則樹進行匹配的過程。如果發現存在某條規則匹配這個報文，就表示檢測到一個攻擊，然后按照規則指定的行為進行處理;如果搜索完所有的規則都沒有找到匹配的規則，就表示報文是正常的報文。BM算法和KMP算法是入侵檢測中應用范圍最廣的一種字符匹配算法，近年來在IDS中也得到應用，典型的IDS中的Snort就采用了BM算法[2]。但由于BM算法自身存在的缺陷，導致在高速網絡環境下入侵檢測的速度可能跟不上數據包到達速率，進而可能導致丟包現象。 本文提出了BM算法的改進算法，充分利用了Badchar函數在匹配過程中起到的移動指針的主導作用，去掉了GoodSuffix函數的煩瑣計算，并對 Badchar函數進行了一定程度的修改，提高了匹配速度。

1 BM算法

該算法由Boyer和Moore提出，是實用中最為快速的算法，并且被大多數IDS所采用。有實驗數據表明，BM的匹配速度大約是KMP的3-5倍。

BM基本思想[3-4]:BM算法的基本思想是先對模式P進行預處理，計算兩個偏移函數:Badchar(針對某個字符)和GoodSuffix(針對某個子串)，然后將文本和模式對齊，從右往左進行匹配，當文本字符與模式字符不匹配時，根據函數Badchar()和GoodSuffix()計算出的偏移值，取兩者中的大者。將文本指針往右移，匹配成功則予以輸出[3]。

若考慮Badchar()函數的約束，則當文本在字符c與模式不匹配時，下次應移動的距離為Badchar[c]-(m-j)，其中j為c在本次匹配中的位置。這樣就可以實現下次匹配時文本中的c與模式中的c位置對齊，從而加快匹配的速度。

2 改進的BM算法

使用BM算法進行匹配時，有時雖然發現了模式匹配，但在匹配過程中比較次數過多，最長可達一個模式的長度，有時第二次匹配時己匹配的結果在第三次匹配時仍然逐一比較。如果可以利用第二次匹配的匹配結果，對部分匹配文本進行記錄，那么進行第三次匹配時就可以實現跳躍式的比較，這就是改進BM算法的設計思想。

新算法設置了記錄與模式的一個后綴相匹配文本的因子。在本次匹配過程中，當比較到模式中已記錄的上次匹配后綴時，則實現跳躍式比較，跳過此后綴，從而會減小這次匹配過程中的字符比較次數。與BM算法相比，這無疑會對加快字符搜索有所貢獻。

改進BM算法描述

Begin

i:=0;u:=0;shift:=m;

while i≤ n-m do

j:=m;

while j>0 and if p[j]=t[i+j] do

if u<>0 and j=m-shift then

j:=j-u;

else

j:=j-1;

endif

endwhile

if j≤0 then

output (i+1);

shift:=goodsuffix(0);

u:=m-shift;

else

u:=m-j;i:=i+shift;//移動

endwhile

End

改進BM算法的實例:P:hdbhbhbh，T:hdbudhdbhbhbhububdbhubdh

第1次匹配

i=7不匹配移動1位

(goodsuffix[7]=badchar[a]-8+8)

第2次匹配

i=5不匹配則移動4位

(goodsuffix[5]=badchar[c]-8+6)

第3次匹配

完全匹配，則移動7位(goodsuffix[0]

(帶下劃線的字符表示上次已經被匹配了，因此本次匹配將跳過)

第4次匹配

i=5不匹配

(goodsuffix[5]=badchar[c]-8+6)

第5次匹配

不匹配則移動7位(goodsuffix[6]，至串尾，比較結束。從上面的實例可以看出:文本字符數:24，模式字符:8，進行匹配次數:5字符比較:15，在第三次匹配時，由于在第二次己經匹配了bh，所以省略了2次字符比較。

3 改進BM算法與BM算法的性能比較

為了對標準BM算法和改進BM算法進行定量的性能分析，我們使用了WinDump3.6.2在一個局域網內部隨機采集了500M的網絡流量數據，使用了檢測規則120條，分別對兩種算法進行了測試。

1) 時間性能比較[4-5]。通過實驗，得到圖1。

從圖1可見，改進BM算法比BM算法在時間性能上有一定的提高，改善幅度大約在10%-15%左右。由此可見，改進BM算法在處理具有重復后綴的模式匹配時執行速度較快。

2) 空間性能比較[6-7]

表1是BM算法和改進BM算法占用內存空間的比較。可以看出，改進BM算法和BM算法相比所需要的內存空間差別不大。

從測試比較結果可以看出，改進BM算法在執行時間上要比BM算法略快，而占用的內存空間與BM算法基本相等。

4 結論

本文通過對經典的模式算法的分析，提出了改進算法，并用實驗加以驗證，結果證明，改進BM算法在處理具有重復后綴的模式匹配時執行速度較快。比BM算法增加了一些額外計算，在空間占用幾乎與BM算法相等。

參考文獻:

[1] 胡建偉.網絡安全與保密[M].西安:西安電子科技大學出版社，2003.

[2] 楊武.入侵檢測系統中高效模式匹配算法的研究[J].計算機工程，2004(7).

[3] 司鳳山.李東江.基于網絡入侵檢測系統的技術改進[J].棗莊學院學報，2006(2).

[4] 張雷.基于模式匹配的網絡入侵檢測系統研究[D].成都:西南交通大學信息科學與技術學院，2006.

[5] 巫喜紅.凌捷.BM模式匹配算法剖析[J].計算機工程與設計，2007(1).

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

[7] 馮濤.余冬梅.邊培泉.NetBill協議的形式化描述及分析[J].蘭州理工大學學報，2004(4).