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

李世科

摘 要:網(wǎng)絡(luò)安全已經(jīng)成為國(guó)家和官方安全的重要組成部分,入侵檢測(cè)也就變的至關(guān)重要?，F(xiàn)今大多數(shù)入侵檢測(cè)系統(tǒng)還是采用的基于規(guī)則的模式匹配策略,模式匹配算法的好壞直接影響到入侵檢測(cè)系統(tǒng)的準(zhǔn)確性和實(shí)時(shí)性。提出了一種改進(jìn)的BM算法,并從改進(jìn)的意義、原理和實(shí)驗(yàn)分析說(shuō)明了改進(jìn)算法在匹配效率上的提高。

關(guān)鍵詞:模式匹配;入侵檢測(cè);算法

中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1672-3198(2009)16-0263-02

1 BM算法研究

1977年Boyer和Moore提出了一種全新的算法,即BM算法。它的特點(diǎn)在于匹配過(guò)程中,模式從左向右移動(dòng),但字符比較卻從右向左進(jìn)行。其基本算法思想是:(1)匹配從右至左進(jìn)行。(2)若匹配失敗發(fā)生在P_i≠T_i且T_i不出現(xiàn)在模式P中,則將模式右移直到P_i位于匹配失敗位置T的右邊第一位(即T_i+1位),若T_i在P中有若干地方出現(xiàn),則選擇j=max{k|P_k=T_i}即通過(guò)Skip函數(shù)計(jì)算文本字符T_i失配時(shí)模式向右移動(dòng)的距離,也稱壞字符啟發(fā)。(3)若模式后面k位與文本T中一致的部分有一部分在P中其他地方出現(xiàn),則可以將P向右移動(dòng),直接使這部分對(duì)齊,且要求這一部分盡可能大,Shift函數(shù)通過(guò)對(duì)已經(jīng)匹配部分的考查決定模式向右移動(dòng)的距離,也稱好后綴啟發(fā)。

實(shí)例分析:

第1次匹配:

Example

here is a simple example

第2次匹配(壞字符啟發(fā)):

Example

here is a simple example

第3次匹配(壞字符啟發(fā)):

Example

here is a simple example

第4次匹配(好后綴啟發(fā)):

Example

here is a simple example

第5次匹配(壞字符啟發(fā)):

Example

here is a simple example

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

2 改進(jìn)BM匹配算法研究

2.1 改進(jìn)的意義

綜合分析會(huì)發(fā)現(xiàn)雖然BM算法考慮較全面,但它使用了兩個(gè)數(shù)組,預(yù)處理時(shí)間開(kāi)銷較大,于是在BM算法基礎(chǔ)上我們對(duì)其進(jìn)行了簡(jiǎn)化,使得算法更簡(jiǎn)單、高效,提出了一種改進(jìn)的BM算法。通過(guò)實(shí)驗(yàn)表明改進(jìn)的模式匹配算法能減少比較次數(shù),有效地提高了匹配效率。

2.2 改進(jìn)的原理

在BM算法匹配過(guò)程中,常出現(xiàn)模式的一部分后綴與文本匹配,而模式的前綴卻不匹配,在這種情況下,就進(jìn)行了一些不必要的比較。因此在BMGJ算法中,我們?cè)趯?duì)模式串與文本字符串進(jìn)行匹配時(shí)采用從模式兩端向中間位置交替的匹配順序,模式匹配先從模式最右端P_m開(kāi)始進(jìn)行。若P_m匹配不成功,則通過(guò)Skip函數(shù)計(jì)算出模式向右移動(dòng)的距離,這與BM算法中壞字符啟發(fā)思想相同;若P_m匹配成功,則比較模式P₁與文本中相應(yīng)的字符。若P₁匹配不成功,則考查文本中與模式中P_m下一個(gè)字符對(duì)齊的字符,若該字符不出現(xiàn)在模式中,則模式可以向右移動(dòng)m + 1個(gè)位置,若該字符出現(xiàn)在模式中,則計(jì)算其Skip函數(shù),然后將模式向右移動(dòng)相應(yīng)的長(zhǎng)度;若P₁匹配成功,則按上述方法依次對(duì)P_m-1,P₂,P_m-2,P₃,…進(jìn)行匹配,依此類推,直到匹配過(guò)程完成。實(shí)例分析:

第1次匹配:

Example

here is a simple example

第2次匹配:

Example

here is a simple example

第3次匹配(傳統(tǒng)BM算法匹配中,此遍比較需要從右端比較5次才可以找到一個(gè)壞字符,但對(duì)于改進(jìn)后的算法,只比較兩次就可以找到一個(gè)壞字符):

Example

here is a simple example

第4次匹配:

Example

here is a simple example

第5次匹配:

Example

here is a simple example

在上例中,我們可以看出用傳統(tǒng)的BM算法匹配共進(jìn)行了4次移動(dòng)15次比較,用改進(jìn)的BM算法匹配共進(jìn)行了4次移動(dòng)12次比較,匹配次數(shù)減少。

改進(jìn)后的BM算法的預(yù)處理時(shí)間復(fù)雜度為O(m+s),空間復(fù)雜度為O(s),搜索階段時(shí)間復(fù)雜度為O(mn)。該算法在比較右端字符失配時(shí)采用BM壞字符啟發(fā)的思想,在比較了左端字符失配時(shí)采用對(duì)文本中與模式最右端對(duì)齊的下一個(gè)字符進(jìn)行考查的方法,使得大多數(shù)情況下具有比BM算法更大的右移長(zhǎng)度,從而有更好的平均性能。

2.3 改進(jìn)的實(shí)驗(yàn)分析

我們所做的實(shí)驗(yàn)軟件環(huán)境主要是:采用的操作系統(tǒng)是MicroSoft Windows XP Professional(Service Pack2),使用JBuilder2006編譯工具,所用JDK為jdk1.6。

為了對(duì)各算法的性能進(jìn)行比較次數(shù)和比較用時(shí)的測(cè)試,我們隨機(jī)地選取了一段純英文自然語(yǔ)T文本和模式串P,在同一臺(tái)計(jì)算機(jī)上用不同算法進(jìn)行3萬(wàn)、5萬(wàn)、10萬(wàn)次循環(huán)匹配,分別統(tǒng)計(jì)各算法循環(huán)匹配所進(jìn)行的字符比較次數(shù)和總消耗的時(shí)間。

文本串:T=One day one pig went to a bar and the bar tender asked what can I get for you today and the pig said five beers. He drank up all the beer and then he asked were the bathroom was the bar tender said straight down the hall to the left. Then three more pigs came in and the bar tender asked what can I get you today.

模式串:P= I get you today.

測(cè)試結(jié)果下表1所示:

經(jīng)過(guò)多次匹配實(shí)驗(yàn),結(jié)果顯示改進(jìn)后的BM算法進(jìn)行模式匹配時(shí)字符比較次數(shù)、匹配時(shí)間均少于原BM算法,匹配效率有所提高。

3 結(jié)語(yǔ)

隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大和入侵手段的不斷更新,對(duì)入侵檢測(cè)也提出了更高的要求。目前,BM算法還是入侵檢測(cè)系統(tǒng)中主要使用的模式匹配方法,而它本身存在的一些問(wèn)題使其還是有改進(jìn)的余地,本文對(duì)其進(jìn)行了改進(jìn),并且通過(guò)實(shí)驗(yàn)結(jié)果分析得出改進(jìn)以后在匹配效率的提高。以后我們還可以在檢測(cè)引擎中結(jié)合其他智能化的檢測(cè)方法,如協(xié)議分析、神經(jīng)網(wǎng)絡(luò)、遺傳算法等,這將是我們下一步研究的重點(diǎn)。

參考文獻(xiàn)

[1]@谷曉鋼,江榮安,趙銘偉.Snort的高效規(guī)則匹配算法[J].計(jì)算機(jī)工程,2006,(18).

[2]@唐正軍.入侵檢測(cè)技術(shù)導(dǎo)論(第一版)[M].北京:機(jī)械工業(yè)出版社,2004.

[3]@邊肇祺,閻平凡,楊存榮.模式識(shí)別(第一版)[M].北京:清華大學(xué)出版社,1988.

[4]@郭軍,笹尾勤.入侵檢測(cè)中模式匹配算法的FPGA實(shí)現(xiàn)[J].科技創(chuàng)新導(dǎo)報(bào),2007,(14).