葛賢銀,韋素媛,楊百龍,蒲玄及

摘 要:基于模式匹配的檢測方法是目前入侵檢測系統(tǒng)的一種重要方法,因此作為模式匹配方法核心的字符串匹配算法直接影響入侵檢測系統(tǒng)的性能和效率。在研究現(xiàn)有算法的基礎(chǔ)上提出一種改進(jìn)的模式匹配算法New-Search算法。該算法以BM算法為基礎(chǔ),通過預(yù)處理階段處理,首末字符部分定位的思想,增加字符跳轉(zhuǎn)距離,比較穩(wěn)定地減少匹配過程中字符比較的次數(shù),提高了匹配的速度和效率。

關(guān)鍵詞:入侵檢測;模式匹配;KMP算法;BM算法;New-Search算法

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)20-073-03

Research of Improved Pattern Matching Algorithm Based on BM Algorithm

GE Xianyin,WEI Suyuan,YANG Bailong,PU Xuanji

(The Second Artillery Engineering College,Xi′an,710025,China)

Abstract:The detecting method based on pattern matching is an important method in intrusion detection system,the key of this is the efficiency of string matching which influences the efficiency of detection directly.An improved pattern matching algorithm named New-Search which is based on BM algorithm is proposed.This algorithm can increase the jumping distance of characters and decrease the comparison times in matching process through the pretreatment step,which takes the idea of the first and last characters′ partial location.In this case,it improves the matching efficiency.

Keywords:intrusion detection;pattern matching;KMP algorithm;BM algorithm;New-Search algorithm

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展,網(wǎng)絡(luò)環(huán)境變得日益復(fù)雜,對于網(wǎng)絡(luò)安全來說,單純的防火墻技術(shù)暴露出明顯的不足和弱點(diǎn),如不能提供實(shí)時(shí)入侵檢測能力;對于病毒束手無策等。入侵檢測系統(tǒng)是繼防火墻和信息加密等安全保障技術(shù)之后出現(xiàn)的新一代網(wǎng)絡(luò)安全防護(hù)系統(tǒng),能夠有效地彌補(bǔ)上述安全系統(tǒng)的不足[1]。它通過對算機(jī)網(wǎng)絡(luò)或計(jì)算機(jī)系統(tǒng)中的若干關(guān)鍵點(diǎn)收集信息并對其進(jìn)行分析,實(shí)時(shí)地發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象,并采取相應(yīng)措施以避免攻擊的發(fā)展或盡量減少攻擊造成的危害。按照所采用的檢測技術(shù),入侵檢測系統(tǒng)可以分為誤用檢測系統(tǒng)和異常檢測系統(tǒng)。誤用檢測系統(tǒng)使用模式匹配的方法來發(fā)現(xiàn)入侵行為,是目前入侵檢測系統(tǒng)的主流。所以,作為模式匹配方法核心的字符串匹配算法直接影響入侵檢測系統(tǒng)的性能和效率[2]。

1 幾種經(jīng)典的模式匹配算法

1.1 KMP(Knuth Morris Pratt)算法

此算法是Knuth D E與Pratt V R和Morris J H同時(shí)發(fā)現(xiàn)的,因此人們稱為KMP算法[3]。KMP算法的基本思想是:若某趟匹配過程中Ti和Pj不匹配,而前j-1個(gè)字符已經(jīng)匹配。此時(shí)只需右移模式串P,文本串T不動(dòng),即指針i不回溯,讓Pk與Ti繼續(xù)比較。 移動(dòng)后重新開始比較的位置k僅與模式串P有關(guān),而與目標(biāo)串T無關(guān),因此k可以通過下k可以通過下面的next函數(shù)事先確定。

定義next[j]函數(shù)為:k可以通過下面的next函數(shù)事先確定。

next[j]=max{k1

Pj-kPj-k+1…Pj-1,集合非空

0,其他情況-1(標(biāo)記),j=0時(shí)

KMP算法在最壞情況下的復(fù)雜度為O(m+n)。

1.2 BM(Boyer Moore)算法

BM算法[4]的基本思想是:開始時(shí)將目標(biāo)串T與模式串P左對齊,自右至左逐個(gè)字符進(jìn)行比較(即首先比較Tt+m與Tm);當(dāng)某趟比較時(shí)Ti與模式串的對應(yīng)字符不匹配,則把模式右滑一段距離d(x),執(zhí)行由Pm與Ti+d(x)起始的自右至左的匹配檢查,直到找到要匹配的模式或整個(gè)文本搜索完畢。

右滑距離函數(shù)d(x)定義如下:

d(x)=m,x not in P或x=Pm且

x≠Pj(1≤j≤m-1)

m-j,j=max{jPj=x,1≤j≤m-1},

其他情況

最差情況下找到所有模式出現(xiàn)的時(shí)間復(fù)雜度O(mn)。在最好情況下找到模式出現(xiàn)的時(shí)間復(fù)雜度為O(n/m)。

1.3 QS(Quick Search)算法

QS算法[5]思想如下:假設(shè)當(dāng)前文本指針為t,模式串P與Tt,t+m-1對齊?？紤]到文本串字符與模式串字符匹配不成功時(shí),文本指針至少要移動(dòng)1個(gè)位置,那么在下一次匹配過程中,Tt+m是待處理的對象,因而在計(jì)算偏移量時(shí),可將Tt+m考慮進(jìn)去,通過判斷Tt+m是否在模式中,從而決定模式串的移動(dòng)量。對于模式中不出現(xiàn)的字符,其偏移量為m+1。QS算法的主要特征是:模式串的移動(dòng)量大;在模式串較短的情況小更為有效;最壞情況下找到模式所有出現(xiàn)的時(shí)間復(fù)雜度為O(mn)。

1.4 AC(Aho Corasick)算法

AC算法[6]是一個(gè)同時(shí)搜索多個(gè)模式的經(jīng)典多模式匹配算法。所謂多模式匹配算法就是把所有的模式串合并到一個(gè)數(shù)據(jù)結(jié)構(gòu)中,通過對文本進(jìn)行一次掃描,找到所有模式的所有出現(xiàn)。AC算法使用有限自動(dòng)機(jī)的結(jié)構(gòu)來接收所有的字符串。由于自動(dòng)機(jī)是結(jié)構(gòu)化的,這樣每個(gè)前綴都可用惟一的狀態(tài)來標(biāo)識(shí),甚至是那些多個(gè)模式串的共同前綴。當(dāng)文本中下一個(gè)字符不是模式中預(yù)期的下一個(gè)字符中的一個(gè)時(shí),會(huì)有一條失敗鏈指向一個(gè)狀態(tài)。這個(gè)狀態(tài)代表最長的模式前綴,同時(shí)也是當(dāng)前狀態(tài)的相應(yīng)后綴。AC算法在以下方面得到了改進(jìn):同時(shí)支持確定型和不確定型有限狀態(tài)自動(dòng)機(jī);采用線性鏈表來初始化狀態(tài)轉(zhuǎn)移表;在執(zhí)行過程中,將確定型和不確定型有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移表轉(zhuǎn)換成全矩陣形式,有利于減少內(nèi)存開銷;在每一個(gè)狀態(tài)轉(zhuǎn)移鏈表中增加一個(gè)布爾型變量,來指示狀態(tài)中是否存在一個(gè)匹配的模式。AC算法搜索階段的時(shí)間復(fù)雜度為O(n),預(yù)處理階段的時(shí)間復(fù)雜度為O(M),其中M是所有模式串的長度和[7]。

2 改進(jìn)模式匹配算法New Search

2.1 算法提出的背景

隨著網(wǎng)絡(luò)攻擊技術(shù)的發(fā)展和攻擊手段的多樣化,描述攻擊行為的特征數(shù)目指數(shù)上升,檢測算法的效率已成為誤用檢測技術(shù)的瓶頸,直接影響系統(tǒng)的實(shí)時(shí)性能。因而,如何改進(jìn)字符串匹配搜索算法,提高檢測速度,是目前IDS研究的重點(diǎn)之一[8]。另外對于基于誤用的入侵檢測系統(tǒng)來說,入侵特征匹配是檢測過程中最費(fèi)時(shí)的部分。提高入侵檢測引擎的速度一直以來都是研究的熱點(diǎn)問題[9]。在此提出一種基于BM算法的改進(jìn)算法,通過對數(shù)據(jù)進(jìn)行預(yù)處理,增大一次跳過的字符數(shù),從而可進(jìn)一步減少字符匹配次數(shù),提高算法性能。

2.2 算法的基本思想

算法的基本思想:假設(shè)要檢測數(shù)據(jù)報(bào)負(fù)載T中是否包含模式串P,如果模式串中T中的首末字符不在負(fù)載T中,則說明P不在T中;反之,說明P可能在T中,需要調(diào)用標(biāo)準(zhǔn)字符串匹配算法來確定P是否為T的子串。

2.3 算法的實(shí)現(xiàn)

算法的實(shí)現(xiàn)分為兩個(gè)階段:預(yù)處理階段和搜索階段。前者依賴于能快速判斷P中首末字符是否在T中的方法,后者依賴于一個(gè)快速準(zhǔn)確的模式匹配算法。

(1) 預(yù)處理階段。這里主要借助指針函數(shù),首先從負(fù)載T中搜索出模式串P的首子符,接著在搜索出的首字符位置加上模式串P的長度,看P的末字符是否與對應(yīng)位置匹配,如果匹配,標(biāo)記并存儲(chǔ)相應(yīng)位置;如果不匹配,直接丟棄。

(2) 搜索階段。主要思想:借助于BM算法,從左向右移動(dòng)模式串,從預(yù)處理階段中搜索出負(fù)載T中與模式串P的首字符位置Ti處進(jìn)行匹配,即圖中1所在的位置。如果不匹配,借助于BM算法,跳轉(zhuǎn)距離為q,即圖中的4所在的位置。跳轉(zhuǎn)距離p與預(yù)處理階段搜索出的與P首字符且未字符相同的2,3位置進(jìn)行比較,如果p>r,則舍棄2所在位置;以4所在位置為準(zhǔn);如果p

圖1 思想演示圖

流程圖如圖2所示。

從流程圖可以看出最差情況下搜索階段找到模式的所有出現(xiàn)的時(shí)間復(fù)雜度為O(mn),最優(yōu)情況下的時(shí)間復(fù)雜度為O(n/m)。雖然從復(fù)雜度分析上看沒有很大改進(jìn),但因首末子串在T中同時(shí)匹配屬于小概率事件。通過這種方法改進(jìn),大大加強(qiáng)了跳轉(zhuǎn)距離,一定程度上提高了模式匹配的效率。

圖2 算法流程圖

2.4 對比試驗(yàn)

算法的實(shí)際運(yùn)行情況比較復(fù)雜,在真實(shí)語料上的測試數(shù)據(jù)將更能說明各種算法的效率。選擇一篇英文的幫助文件作為測試語料,大小為5.4 MB,選擇其中長度為3~10個(gè)英文單詞、短句作為模式串,總共選擇6個(gè),統(tǒng)計(jì)各模式串在測試語料中出現(xiàn)的總次數(shù),占用CPU的時(shí)間,總的嘗試次數(shù)和總的比較次數(shù)。實(shí)驗(yàn)環(huán)境為:CPU為奔騰4 2.4 GHz,內(nèi)存為2 GHz,操作系統(tǒng)為Windows XP,編譯環(huán)境為VC++6.0。實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 算法比較

算法CPU時(shí)間 /ms嘗試次數(shù)字符比較次數(shù)

BM算法9 543346 521 628364 807 835

改進(jìn)算法7 421292 007 214298 319 791

從實(shí)驗(yàn)結(jié)果來看,改進(jìn)算法較算法在占用時(shí)間、嘗試次數(shù)和比較次數(shù)上效率都有不小的提高,其中占用CPU時(shí)間是BM算法的78.5%,總的嘗試次數(shù)是BM算法的84.2%,總的字符比較次數(shù)是BM算法81.8%。

3 結(jié) 語

隨著網(wǎng)絡(luò)應(yīng)用的不斷出現(xiàn)以及網(wǎng)絡(luò)帶寬的不斷增加,必須加快入侵檢測系統(tǒng)的處理性能以適應(yīng)大流量網(wǎng)絡(luò)環(huán)境的要求。目前入侵檢測系統(tǒng)大多是基于模式匹配的系統(tǒng),因此提高模式匹配的效率是提高系統(tǒng)檢測能力的關(guān)鍵[10]。這里對入侵檢測系統(tǒng)中應(yīng)用的模式匹配算法進(jìn)行了研究,在BM算法基礎(chǔ)上進(jìn)行改進(jìn),增大了跳躍距離。實(shí)驗(yàn)結(jié)果表明,在入侵檢測系統(tǒng)中應(yīng)用此算法,能夠顯著提高模式匹配的效率,從而提高系統(tǒng)的檢測性能。

參考文獻(xiàn)

[1]李庚,韓進(jìn),謝立.入侵檢測中一種新的多模式匹配算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(8):2 474-2 476.

[2]張雷.基于模式匹配的網(wǎng)絡(luò)入侵檢測系統(tǒng)研究[D].成都:西南交通大學(xué),2005.

[3]Knuth D E,Morris J H,Pratt V R.Fast Pattern Matching in Strings[J].SIAM Comput.,1977,6(2):323-350.

[4]Boyer R S,Moore J S.A Fast String Searching Algorithm[J].Commun.ACM,1977,20(10):762-772.

[5]Sunday D M.A Very Fast Substring Search Algorithm[J].Commun.ACM,1990,33(8):132-142.

[6]Aho A V,CorasickM J.Efficient String Matching:An Aid to Bibliographic Search[J].Commun.ACM,1975,18(6):333-340.

[7]張胤.模式匹配型入侵檢測系統(tǒng)的改進(jìn)研究[D].秦皇島:燕山大學(xué),2006.

[8]譚漢松,彭詩力.一種新的多模式匹配算法[J].計(jì)算機(jī)工程,2005,31(18):119-120.

[9]李紅霞.串匹配型入侵檢測系統(tǒng)的改進(jìn)研究[D].秦皇島:燕山大學(xué),2005.

[10]藍(lán)華.基于網(wǎng)絡(luò)匹配的入侵檢測系統(tǒng)的研究與設(shè)計(jì)[D].長春:吉林大學(xué),2005.