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

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

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

中圖分類號:TP311文獻標識碼:A

文章編號: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 引 言

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

1 幾種經典的模式匹配算法

1.1 KMP(Knuth Morris Pratt)算法

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

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

next[j]=max{k1

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

0,其他情況-1(標記),j=0時

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

1.2 BM(Boyer Moore)算法

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

右滑距離函數(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)的時間復雜度O(mn)。在最好情況下找到模式出現(xiàn)的時間復雜度為O(n/m)。

1.3 QS(Quick Search)算法

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

1.4 AC(Aho Corasick)算法

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

2 改進模式匹配算法New Search

2.1 算法提出的背景

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

2.2 算法的基本思想

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

2.3 算法的實現(xiàn)

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

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

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

圖1 思想演示圖

流程圖如圖2所示。

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

圖2 算法流程圖

2.4 對比試驗

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

表1 算法比較

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

BM算法9 543346 521 628364 807 835

改進算法7 421292 007 214298 319 791

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

3 結 語

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

參考文獻

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

[2]張雷.基于模式匹配的網絡入侵檢測系統(tǒng)研究[D].成都:西南交通大學,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)的改進研究[D].秦皇島:燕山大學,2006.

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

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

[10]藍華.基于網絡匹配的入侵檢測系統(tǒng)的研究與設計[D].長春:吉林大學,2005.