BM及其改進(jìn)算法性能對(duì)比研究

鄧小明

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

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)20-4816-03

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

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

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

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

ELSE

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

JUMP（移動(dòng)距離）=模式長(zhǎng)度-DoubleChar[下一字符]-l；

ELSE

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

j=模式串長(zhǎng)度-l；}

匹配失敗，返回-1；}

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

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

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

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

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

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

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

[4]劉勝飛,張?jiān)迫?改進(jìn)的BMH模式匹配算法[J].計(jì)算機(jī)科學(xué),2008,35(11):164-166.

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