鄧小明

摘要：模式匹配算法在很多場合都有應用，BM算法是輕量級入侵檢測系統(tǒng)SNORT的內(nèi)置的單模式匹配算法，高速網(wǎng)絡環(huán)境下，算法的模式匹配效率的高低在很大程度上影響入侵檢測系統(tǒng)的性能。該文通過對BM及改進后的兩種BM算法進行測試。實驗結果表明，改進后的BM算法在實際匹配次數(shù)、窗口最大位移量以及跳躍發(fā)生的次數(shù)上對比BM算法具有很大的優(yōu)勢，有著實用價值。關鍵詞：BM算法；匹配次數(shù)；窗口最大位移量

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2012)20-4816-03

隨著網(wǎng)絡數(shù)據(jù)流量的不斷增長，對基于網(wǎng)絡數(shù)據(jù)捕獲平臺的網(wǎng)絡入侵檢測系統(tǒng)面臨著新的挑戰(zhàn)。高速網(wǎng)絡環(huán)境中，如何有效提高網(wǎng)絡入侵檢測系統(tǒng)的效率顯得尤為重要。傳統(tǒng)的linux環(huán)境下輕量級snort入侵檢測系統(tǒng)中BM模式匹配算法在匹配效率上存在著匹配次數(shù)多、匹配失敗時最大位移小等缺陷，這些多余的匹配操作將很大程度上影響入侵檢測系統(tǒng)的效率。該文通過分析并改進BM及相關算法，并進行了實驗，結果表明改進后的BM算法有著在小字節(jié)數(shù)據(jù)包的網(wǎng)絡環(huán)境中，滿足了在高速鏈路下網(wǎng)絡入侵檢測系統(tǒng)的要求。 1.1 BM算法[1]

Bm單模匹配算法中使用字符串和模式串從左到右對齊，進行字符匹配時窗口向右滑動，匹配過程從右到左進行，匹配算法在匹配的過程中，取Skip(x)與Shift(x)中的較大者作為跳躍的距離。BM算法在執(zhí)行時按照兩個步驟進行：初始化處理階段以及查找階段。初始化處理時主要進行Badchar()和Goodsuffix()兩個偏移量計算。預處理時間復雜度為O（m+s），查找時的時間復雜度為O(m·n)，最好情況下的時間復雜度為O(n/m)，最壞情況下時間復雜度為O(m·n)。兩個偏移量的計算機流程是：Badchar（）函數(shù)主要計算字符串中單個字符的偏移量，假設其中的一個字符在模式串中不止一次出現(xiàn)，那么它的最右邊出現(xiàn)的偏移量是決定性的。GoodSuffix偏移量主要是計算模式串中的后綴匹配成功時指針可以向右移動的偏移量，其算法描述如下：

設字符串長度為n，模式串長度為m，壞字符和好后綴匹配字串滑動距離用skip（x）和shift（x）表示，x表示在P串中最右邊的位置，dist=max{skip(x),shift(x)}

字符串T和模式串P從左到右對齊，匹配從模式串最右邊的第一個字符開始；搜索P串中是否含有與P串中對應的T串的字符，如果沒有，將P串向右滑動m的長度，如果包含有該字符，則啟動Skip搜索，并計算所需要滑動的距離，然后滑動相應的距離，其中：

ELSE

IF(模式串末字符比較成功)

JUMP（移動距離）=模式長度-DoubleChar[下一字符]-l；

ELSE

JUMP（移動距離）=Max(末字符求得跳轉距離，下—字符求得跳轉距離)；i=新窗口匹配位置；

j=模式串長度-l；}

匹配失敗，返回-1；}

BM算法由sonrt.C文件獲得，C語言編寫主程序中調(diào)用這3個算法，編譯主程序依次進行算法匹配測試,算法對比測試數(shù)據(jù)使用網(wǎng)絡小說英文哈利波特HarryPotter.txt，從中截取文本長度10000個字符，隨機取模式串50個，長度在3字符-20個字符。算法比較次數(shù)統(tǒng)計通過在程序中增加變量實現(xiàn)，算法匹配時間使用GetTickCount( )函數(shù)，單位ms。三種算法分別在字符比較次數(shù)（見圖1）、算法運行時間（見圖2）對比測試結果如下圖所示：

BM模式匹配算法和BM模式匹配算法1以及BM模式匹配算法2的最大位移量分別是m,m+1,m+1,在最大位移量上，相差不大，模式匹配算法的時間復雜度分別是O(n/m)、O(n/m+1)、O(n/m+1)。

評價一個模式匹配算法的優(yōu)劣主要的指標有字符匹配次數(shù)、算法的運行時間等。其中在字符比較次數(shù)上，BM改進算法2比BM算法在在各種長度的模式串中字符比較次數(shù)平均減少了25%，BM改進算法2比BM改進算法1在各種長度的模式串中字符比較次數(shù)平均減少了18%。在算法運行時間上，BM改進算法2比BM算法在各種長度的模式串中算法運行時間平均減少了37%，BM改進算法2比BM改進算法1在各種長度的模式串中算法運行時間平均減少了29.6%。

綜上所述由于在不增加空間的情況下，由于字符比較次數(shù)的減少，同時在運行時間上也有較明顯優(yōu)勢，總體上來說，BM改進算法2比BM算法和BM改進算法1的執(zhí)行效率都高，加快了模式匹配的速度。同時也說明改進后的BM算法在各種應用場合有著良好的性能。

[1]程玉青,梅登華.入侵檢測系統(tǒng)中BM模式匹配算法的改進[J].計算機技術與發(fā)展, 2009,19(3):120-121.

[2]周文秋,呂岳.一種快速模式匹配算法及其在IDS中的應用[J].信息技術,2009,10(3):45-47

[3]王浩.基于入侵檢測系統(tǒng)snort的BM模式匹配Snort和改進[J].計算機技術,2009,2(12):38

[4]劉勝飛,張云泉.改進的BMH模式匹配算法[J].計算機科學,2008,35(11):164-166.

[5]孫克雷.IDS中一種快速模式匹配算法[J].安徽理工大學學報:自然科學版,2006,26(3):52-55.