模式匹配算法在入侵檢測(cè)中的應(yīng)用

冉占軍　姚全珠　王曉峰　鄒又姣

摘 要：僅依靠傳統(tǒng)的被動(dòng)防御技術(shù)已經(jīng)不能滿足如今的網(wǎng)絡(luò)安全需要，基于模式匹配的入侵檢測(cè)系統(tǒng)正成為研究和應(yīng)用的熱點(diǎn)，模式匹配效率的高低決定了這類入侵檢測(cè)系統(tǒng)的性能。全面綜述了應(yīng)用于入侵檢測(cè)系統(tǒng)的經(jīng)典的模式匹配算法，包括單模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC－BM算法，并對(duì)各種算法的執(zhí)行效率進(jìn)行了總結(jié)。通過分析算法的思想，提出了未來此類算法的研究方向。

關(guān)鍵詞：入侵檢測(cè)；KMP算法；BM算法；RK算法；AC算法；AC－BM算法

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004 373X(2009)02 063 05

Application of Pattern Matching Algorithm in Intrusion Detection Technique

RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1

(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)

Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.

Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC－BM algorithm

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，各種基于網(wǎng)絡(luò)的應(yīng)用層出不窮。面對(duì)日益突出的網(wǎng)絡(luò)安全問題，僅靠傳統(tǒng)的被動(dòng)防御已經(jīng)不能滿足要求，能夠主動(dòng)檢測(cè)并預(yù)防的入侵檢測(cè)系統(tǒng)應(yīng)運(yùn)而生。

根據(jù)采用的分析方法，入侵檢測(cè)分為誤用檢測(cè)和異常檢測(cè)。誤用檢測(cè)是指：根據(jù)己知的攻擊方法，預(yù)先定義入侵特征，通過判斷這此特征是否出現(xiàn)來完成檢測(cè)任務(wù)。異常檢測(cè)是指：根據(jù)用戶的行為或資源的使用狀況的正常程度來判斷是否屬于入侵。由于異常檢測(cè)的誤檢率和漏檢率高，因此目前大多數(shù)入侵檢測(cè)系統(tǒng)產(chǎn)品均主要采用誤用檢測(cè)的方法。誤用檢測(cè)中使用的檢測(cè)技術(shù)主要有: 模式匹配、專家系統(tǒng)、狀態(tài)轉(zhuǎn)移等，其中模式匹配原理簡(jiǎn)單，可擴(kuò)展性好，而且最為常用。據(jù)統(tǒng)計(jì)，現(xiàn)在大約95%的入侵檢測(cè)都是特征匹配的入侵檢測(cè)。

由此可見，模式匹配算法性能的好壞直接影響到入侵檢測(cè)系統(tǒng)的效率。隨著網(wǎng)絡(luò)傳輸速度的大幅度提高，入侵檢測(cè)系統(tǒng)需要處理的數(shù)據(jù)量越來越大，如果模式匹配算法來不及處理這些實(shí)時(shí)的大量的數(shù)據(jù)包，必然會(huì)丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中很可能就包含有入侵信息，從而造成漏報(bào)。在此介紹幾種著名的用于入侵檢測(cè)的模式匹配算法，包括單模式匹配算法和多模式匹配算法，通過對(duì)它們進(jìn)行剖析和實(shí)際測(cè)試，提出入侵檢測(cè)系統(tǒng)中模式匹配算法的選擇策略和未來的研究方向。

1 單模式匹配算法

1.1 相關(guān)定義

模式匹配：是指在給定長(zhǎng)度為n的目標(biāo)串T=T1T2…T璶中查找長(zhǎng)度為m的模式串P=P1P2…P璵的首次出現(xiàn)或多次出現(xiàn)的過程。這里T璱(1≤i≤n)，

P璲(1≤j≤m)∈∑(字符集)，若P在T中出現(xiàn)1次或多次，則稱匹配成功，否則稱匹配失敗。

單模式匹配算法：在目標(biāo)串中1次只能對(duì)1個(gè)模式串進(jìn)行匹配的算法。

多模式匹配算法：在目標(biāo)串中可同時(shí)對(duì)多個(gè)模式串進(jìn)行匹配的算法。

最簡(jiǎn)單的模式匹配算法是Brute－Force算法(BF算法)。在BF算法的目標(biāo)串和模式串的字符比較中，只要有1個(gè)字符不相等，而不管前面已有多少個(gè)字符相等，就需要把目標(biāo)串T回退，下次比較時(shí)目標(biāo)串T只后移1個(gè)字符。雖然算法簡(jiǎn)單，但效率低下，不適合用于入侵檢測(cè)系統(tǒng)中，不做重點(diǎn)介紹。

高效的模式匹配算法都是設(shè)法增大不匹配時(shí)目標(biāo)串T或模式串P之間的偏移量，以減少總的比較次數(shù)。下面介紹3種經(jīng)典的快速單模式匹配算法。

1.2 KMP算法

1970年，S.A.Cook從理論上證明了一維模式匹配問題可以在O(m+n)時(shí)間內(nèi)解決［1］。D.E.Knuth，V.R.Pratt和T.H.Morris 在BF算法的基礎(chǔ)上提出了一種快速模式匹配算法，稱為KMP算法［1］，該算法消除了BF算法的目標(biāo)串指針在相當(dāng)多個(gè)字符比較相等后，只要有1個(gè)字符比較不等便需要回溯的缺點(diǎn)，使算法的效率得到了大幅度提高，時(shí)間復(fù)雜度達(dá)到最理想的O(m+n)，空間復(fù)雜度是O(m)。

KMP算法的基本思想是：若某趟匹配過程中T璱和P璲不匹配，而前j-1個(gè)字符已經(jīng)匹配。此時(shí)只需右移模式串P，目標(biāo)串T不動(dòng)，即指針i不回溯，讓P璳與T璱繼續(xù)比較。移動(dòng)后重新開始比較的位置k僅與模式串P有關(guān)，而與目標(biāo)串T無關(guān)，因此k可以通過下面的next函數(shù)事先確定。

定義next［j］函數(shù)為：

next［j］=max{k|1＜k＜j且 P1P2…P璳=

P璲-kP璲-k+2…P璲-1} ，集合非空

0，其他情況

-1(標(biāo)記)，j=0時(shí)

1.3 BM算法

相對(duì)于BF算法，KMP算法雖然消除了主串指針的回溯，在不匹配時(shí)能使模式串右滑若干位，但由上述next函數(shù)可知：右滑的最大距離不會(huì)超過1趟匹配操作所進(jìn)了的比較次數(shù)j，原因在于KMP算法的匹配操作是從左到右進(jìn)行的。受到KMP算法的啟發(fā)，R.S.Boyer和J.S.Moore提出一種新的快速字符串匹配算法－BM算法［1－3］。

BM算法基本思想是：開始時(shí)將目標(biāo)串T與模式串P左對(duì)齊，自右至左逐個(gè)字符進(jìn)行比較(即首先比較P璵與T璵)；當(dāng)某趟比較時(shí)T璱與模式串的對(duì)應(yīng)字符不匹配，則把模式串右滑d(x)一段距離，執(zhí)行由P璵與T璱+d(x)起始的自右至左的匹配檢查。BM算法采用以下兩條規(guī)則計(jì)算模式串右移的距離：

(1) 好后綴移動(dòng)。其又分為2種情況：

① P已比較部分P［j+1…m］與其中間的某一子串P［j-s+l…m-s］相同，P右移s位。如圖1所示。

圖1 右滑距離s,(s＜j)

② P已比較部分P［j+l…m］的后綴P［s+l…m］與P的前綴P［l…m-s］相同，P右移s位。如圖2所示。

圖2 右滑距離s,(s≥j)

取滿足上述兩種情況的s的最小值作為移動(dòng)距離。因此可以定義一個(gè)距離函數(shù)dist1(j)：

dist1(j)=min{s| P［j+1…m］=［j-s+l…m-s］&&P;［j］≠P［j-s］(s＜j),P［s+l…m］= P［l…m-s］}

(2) 壞字符移動(dòng)。P中的某個(gè)字符與T中的某個(gè)字符不相同時(shí)使用壞字符移動(dòng)。右滑距離函數(shù)dist2(x)定義如下：

dist2(x)=

m,(x not in P)或

(x=P璵且x≠P璲(1≤j≤m-1))

m-j,j=max{ j | P璲=x,1≤j≤m-1},

其他情況

匹配時(shí)取移動(dòng)距離為：dist=max{dist1(j),dist2}。文獻(xiàn)［4］證明算法需要的預(yù)處理時(shí)間為O(m+σ)，最壞運(yùn)行時(shí)間為O，即掃描部分運(yùn)行時(shí)間為O。在大字母表(相對(duì)于模式長(zhǎng)度)情況下，BM算法非?？?，實(shí)際比較次數(shù)只有目標(biāo)串長(zhǎng)度的20%~30%。

1.4 RK算法

Karp和Rabin在1981年提出來的RK算法［5］利用了Hash方法和素?cái)?shù)理論。

RK算法的思想是：首先定義一個(gè)Hash函數(shù)，用該函數(shù)計(jì)算出模式串P的Hash函數(shù)值，再計(jì)算出目標(biāo)串T中所有長(zhǎng)度為m的子串的Hash函數(shù)值，然后用相應(yīng)的Hash函數(shù)值進(jìn)行比較。當(dāng)出現(xiàn)Hash沖突時(shí)，再進(jìn)行相應(yīng)字符串的比較，當(dāng)構(gòu)造Hash函數(shù)的素?cái)?shù)選擇得合理，Hash沖突出現(xiàn)的概率就可以做到很小。

Hash函數(shù)的構(gòu)造及相應(yīng)Hash值的計(jì)算如下：

設(shè)c∈∑，構(gòu)造Hash函數(shù)：

h(asc(c))=asc(c) mod q

式中：q∈［1…n2m］且為素?cái)?shù)；asc(c)為任意字符c的ASCII碼。

映射模式串P為Hash函數(shù)值x(0≤x≤q-1)的方法為：

令：

X=h(asc(P［1］)cm-1+asc(P［2］)cm-2+…

+asc(P［m-1］)c1+asc(P［m］))

同理，映射目標(biāo)串T中長(zhǎng)度為m的子串t璱=T［i…i+m-1］為Hash函數(shù)值t璱的方法是：

令：

t璱=h(asc(T［i］)cm-1+asc(T［i+1］)cm-2+…+asc(T［i+m-2］)c1+asc(T［i+m-1］))

用i+1替換i，并帶入Hash函數(shù)，從而得遞推公式：

t璱+1=h(asc(T［i+1］)cm-1+asc(T［i+2］)cm-2+

…+asc(T［i+m-1］)c1+asc(T［i+m］))

=(c(t璱-asc(T［i］)cm-1) +asc(T［i+m］)) mod q

式中，i=1，2，…，n-m。

根據(jù)上述公式可把目標(biāo)串T中每個(gè)長(zhǎng)度為m的子串的Hash函數(shù)值計(jì)算出來。

如果Hash沖突不發(fā)生，即不再需要額外的字符匹配，RK算法的時(shí)間復(fù)雜度是O(m+n)；若考慮字符匹配，則RK算法的時(shí)間復(fù)雜度是O(mn)。在實(shí)際應(yīng)用中，可設(shè)法取適當(dāng)大的素?cái)?shù)q，使得mod q仍可執(zhí)行并且Hash沖突又幾乎不發(fā)生，從而使得KR算法的實(shí)際運(yùn)行時(shí)間只需O(m+n)。

RK算法采用了與KMP和BF算法不同的思路，盡量減少字符之間的比較次數(shù)，從而達(dá)到提高效率的目的。

1.5 單模式匹配算法改進(jìn)情況簡(jiǎn)介

研究人員對(duì)單模式匹配算法提出了不少變形和改進(jìn)算法。

在文獻(xiàn)［6］中黃占友等人提出的KMP算法的改進(jìn)對(duì)特殊的字符串能夠提高效率；文獻(xiàn)［1］ 中龐善臣等人對(duì)BM算法的改進(jìn)有效地減少了最壞情況下的比較次數(shù)，同時(shí)方便在二位匹配和不精確匹配中推廣；文獻(xiàn)［7］中賀龍濤等人通過將好后綴與壞字符兩種情況合并進(jìn)行處理對(duì)BM進(jìn)行改進(jìn)。采用該思想的同類改進(jìn)算法還有很多，如：發(fā)表于2006年12月32卷23期《計(jì)算機(jī)工程》上渠瑜等人的對(duì)《對(duì)BM模式匹配算法的一個(gè)改進(jìn)》，限于篇幅，不一一列舉。在文獻(xiàn)［8］中張國(guó)平等人對(duì)BM算法的改進(jìn)是通過定義一個(gè)距離函數(shù)來求出每次匹配失敗時(shí)的最大可能移動(dòng)距離；文獻(xiàn)［9］ 蔡曉妍等人對(duì)BM算法的改進(jìn)則是結(jié)合了BM算法和TunedBM算法的優(yōu)點(diǎn)，采用TunedBM的壞字符和BM的好后綴對(duì)模式進(jìn)行預(yù)處理，然后根據(jù)當(dāng)前嘗試中匹配失敗字符的位置信息，決定查找好后綴跳躍表還是壞字符跳躍表以期獲得更大的跳躍距離。文獻(xiàn)［3］張立航等人對(duì)RK算法的改進(jìn)是通過引入2次Hash運(yùn)算進(jìn)行的。通過兩次Hash運(yùn)算使出現(xiàn)Hash沖突的情況大為減少。

2 多模式匹配算法

2.1 入侵檢測(cè)中采用多模式匹配的必要性

與單模式匹配算法相比，多模式匹配算法的優(yōu)勢(shì)在于一趟遍歷可以對(duì)多個(gè)模式進(jìn)行匹配，從而大大提高了匹配效率。對(duì)于單模式匹配算法，如果要匹配多個(gè)模式，那么有幾個(gè)模式就需要幾趟遍歷。當(dāng)然多模式匹配算法也適用于單模式的情況。在入侵檢測(cè)系統(tǒng)中，一條入侵特征可能匹配或部分匹配很多條規(guī)則，如果采用單模式匹配，在匹配每條規(guī)則時(shí)都需要重新運(yùn)行匹配算法，效率很低。然而，日益增多的網(wǎng)絡(luò)攻擊使得入侵檢測(cè)的規(guī)則數(shù)目仍在不斷增長(zhǎng)，例如，Snort1.8.3的規(guī)則為1 270條，snort2.0的規(guī)則為2 300多條，到Snort 2.6.1則增加到3 600多條規(guī)則，因此，單純提高單模式匹配算法的效率，很難使入侵檢測(cè)系統(tǒng)滿足越來越大的網(wǎng)絡(luò)數(shù)據(jù)吞吐量和日益增加的攻擊。

目前比較常見的多模式匹配算法有Aho－Corasick算法、Aho－Corasick－Boyer－Moore算法、Manber－Wu算法、Set－Wise Boyer－Moore－Hospool算法等。

下面介紹其中2種經(jīng)典的多模式匹配算法。

2.2 AC算法

AC算法［10］1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，最早用于圖書館的書目查詢程序中。該算法基于有限狀態(tài)自動(dòng)機(jī)(FSA),在進(jìn)行匹配之前先對(duì)模式串集合SP進(jìn)行預(yù)處理，形成模式樹(樹形FSA)，然后只需對(duì)目標(biāo)串T掃描一次就可以找出所有與其匹配的模式串P。模式樹K的構(gòu)成如下：

K的每一條邊e上都用1個(gè)字符作為標(biāo)簽；

與同一節(jié)點(diǎn)相連的邊的標(biāo)簽均不同；

每1個(gè)模式p∈SP都存在1個(gè)節(jié)點(diǎn)v，使得L(v)=p，其中L(v)表示從根節(jié)點(diǎn)到v所經(jīng)過的所有邊上的標(biāo)簽的拼接；

每一個(gè)葉子節(jié)點(diǎn)v，都存在一個(gè)模式p∈SP使得以L(v′)=p。

例如：對(duì)于模式集SP={he,she,his,hers}模式樹如圖3所示，其中圓圈表示節(jié)點(diǎn)，雙圈是根節(jié)點(diǎn)，邊上的字符就是該邊的標(biāo)簽，填充點(diǎn)圈的標(biāo)簽就是各個(gè)模式。

圖3 模式樹

預(yù)處理階段，模式樹的各個(gè)節(jié)點(diǎn)作為狀態(tài)，根節(jié)點(diǎn)作為初態(tài)，標(biāo)簽為模式的節(jié)點(diǎn)作為終態(tài)，利用轉(zhuǎn)向函數(shù)g和失效函數(shù)f作為轉(zhuǎn)移函數(shù)，將模式樹擴(kuò)展成一個(gè)樹型有限自動(dòng)機(jī)。

由模式樹擴(kuò)展所得的AC自動(dòng)機(jī)M是1個(gè)6元組：

M=(Q,Σ,g,f,q0,F )

其中：

(1) Q是有限狀態(tài)集(模式樹上的節(jié)點(diǎn))；

(2) Σ是有窮的輸入字符表(數(shù)據(jù)包中可能出現(xiàn)的所有字符)；

(3) g是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：g(s,a)：從當(dāng)前狀態(tài)s開始，沿著邊上標(biāo)簽為a的路徑所到的狀態(tài)。假如(u,v )邊上的標(biāo)簽為a，那么g ( u,a ) =v；如果根節(jié)點(diǎn)上出來的邊上的標(biāo)簽沒有a，則g(0,a) =0，即如果沒有匹配的字符出現(xiàn)，自動(dòng)機(jī)停留在初態(tài)；

(4) f(不匹配時(shí)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：

f(s)：當(dāng)w是L(s)最長(zhǎng)真后綴并且w是某個(gè)模式的前綴，那么f(s)就是以w為標(biāo)簽的那個(gè)節(jié)點(diǎn)；

(5) q0∈Q是初態(tài)(根節(jié)點(diǎn)，標(biāo)識(shí)符為0)；

(6) F罳，是終態(tài)集(以模式為標(biāo)簽的節(jié)點(diǎn)集)。

這樣，在目標(biāo)串中查找模式的過程轉(zhuǎn)化成在模式樹中的查找過程。查找一個(gè)串T時(shí)從模式樹的根節(jié)點(diǎn)開始，沿著以T中字符為標(biāo)簽的路徑往下走：若自動(dòng)機(jī)能夠抵達(dá)終態(tài)v，則說明T中存在模式L (v)；否則不存在模式。

AC算法模式匹配的時(shí)間復(fù)雜度是O(n)，并且與模式集中模式串的個(gè)數(shù)和每個(gè)模式串的長(zhǎng)度無關(guān)。無論模式串P是否出現(xiàn)在目標(biāo)串T中，T中的每個(gè)字符都必須輸入狀態(tài)機(jī)中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時(shí)間復(fù)雜度都是O(n)，包括預(yù)處理時(shí)間在內(nèi)，AC算法總時(shí)間復(fù)雜度是O(M+n)，其中M為所有模式串的長(zhǎng)度總和。

2.3 AC－BM算法

對(duì)多模式串的匹配而言，雖然AC算法比BM算法高效得多，但AC算法必須逐一查看目標(biāo)串的每個(gè)字符，即必須按順序輸入，不能實(shí)現(xiàn)跳躍，而BM算法則能夠利用“右滑”跳過目標(biāo)串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發(fā)式搜索技術(shù)應(yīng)用到AC算法中，則可大大提高多模式匹配算法的效率。許多人據(jù)此給出了各種改進(jìn)的算法。Commentz－Walter最先將BM算法和AC算法結(jié)合在一起給出了Commentz－Walter算法；Baeza－Yates結(jié)合BMP算法和AC算法也給出了多模式匹配改進(jìn)算法。

AC－BM算法［5］是Jang－Jong在1993年結(jié)合AC算法的有限自動(dòng)機(jī)和BM算法的連續(xù)跳躍思想提出來的新算法，利用劣勢(shì)移動(dòng)表和優(yōu)勢(shì)跳轉(zhuǎn)表來實(shí)現(xiàn)跳躍式地并行搜索，算法的時(shí)間復(fù)雜度為O(mn)。

該算法的思想是：首先把要查找的多個(gè)模式構(gòu)成一個(gè)關(guān)鍵字樹，把相同的前綴作為樹的根節(jié)點(diǎn)。模式樹從目標(biāo)串的右端向左移動(dòng)，一旦模式樹確定在適當(dāng)?shù)奈恢?，字符比較從左向右開始進(jìn)行。模式樹移動(dòng)時(shí)同時(shí)使用壞字符移動(dòng)和好前綴移動(dòng)。壞字符移動(dòng)的策略為:如果出現(xiàn)不匹配的情況，移動(dòng)模式樹，使得樹中其他模式的能與當(dāng)前目標(biāo)串正在比較的字符相匹配的那個(gè)字符移動(dòng)到與當(dāng)前目標(biāo)串正在比較的字符的相同位置上，如果在當(dāng)前的深度上，目標(biāo)字符沒有出現(xiàn)在任何模式中，則模式樹的偏移量為樹中最短模式的長(zhǎng)度。好前綴移動(dòng)的移動(dòng)策略為：將模式樹移動(dòng)到一個(gè)已被發(fā)現(xiàn)是另一個(gè)模式子串完全前綴的下一個(gè)位置，或者移動(dòng)到作為樹中另一個(gè)模式后綴能夠正確匹配目標(biāo)串的某個(gè)前綴的下一個(gè)位置。在模式樹的移動(dòng)過程中，必須確保模式樹的偏移量不能大于樹中最短的模式長(zhǎng)度。

2.4 AC，AC－BM算法改進(jìn)情況簡(jiǎn)介

文獻(xiàn)［10］中盧汪節(jié)等人針對(duì)AC算法在構(gòu)造狀態(tài)機(jī)時(shí)空間冗余較大的情況，對(duì)狀態(tài)機(jī)各結(jié)點(diǎn)進(jìn)行壓縮存儲(chǔ)，使空間性能和時(shí)間性能都有提高；文獻(xiàn)［11］中萬國(guó)根等人對(duì)AC－BM算法的改進(jìn)借鑒了BMH算法的思想，取消了原算法的好前綴跳轉(zhuǎn)，優(yōu)化了壞字符跳轉(zhuǎn)，并修改了skip的計(jì)算方法，對(duì)大字符集的情況在平均情況下具有更優(yōu)的性能；文獻(xiàn)［12］對(duì)AC－BM的改進(jìn)則是通過預(yù)處理思想實(shí)現(xiàn)的，在進(jìn)行AC-BM匹配之前首先掃描首和(或)尾字符，確定其位置，再到相應(yīng)位置進(jìn)行匹配，相當(dāng)于把目標(biāo)串按模式串首、尾字符分成數(shù)段，每段進(jìn)行比較，段間不含首字符的就直接跳過，不用比較，從而提高效率。

3 算法的實(shí)際執(zhí)行效率

上述這些算法究竟哪種算法具有最好的執(zhí)行效率呢?能不能僅通過時(shí)間復(fù)雜度來進(jìn)行衡量呢？時(shí)間復(fù)雜度僅是一個(gè)度量的范圍，表示受幾個(gè)參數(shù)的影響，并不代表一個(gè)具體的值，還需要在具體的環(huán)境中進(jìn)行測(cè)試。

文獻(xiàn)［13］測(cè)試了包括上述算法在內(nèi)的多種單模式和多模式匹配算法的性能。測(cè)試平臺(tái)為：硬件：CPU Intel Xeon 3.46 GHz X 2，內(nèi)存2 GB DDR，硬盤200 GB SCSI；軟件：Windows 2003 Server,Intel IXA SDK4.1。單模式匹配測(cè)試的規(guī)則集，使用隨機(jī)生成的8，16，32，48，128位具有代表意義的規(guī)則，可以對(duì)應(yīng)端口、IP地址，MAC地址、IPv6地址等，對(duì)多模式匹配測(cè)試采用Snort系統(tǒng)2.4.3規(guī)則集。

單模式匹配算法主要測(cè)試模式長(zhǎng)度與匹配時(shí)間、占用空間及預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果表明：各算法的測(cè)試指標(biāo)在規(guī)則長(zhǎng)度增長(zhǎng)的情況下均呈遞增趨勢(shì)，但BM算法的增長(zhǎng)速度最為緩慢，在不太在意存儲(chǔ)空間的情況下，BM可以作為優(yōu)先考慮的算法，同時(shí)對(duì)IPV6地址也更為合適。

多模式匹配算法的測(cè)試項(xiàng)目為規(guī)則數(shù)與單位匹配時(shí)間、占用儲(chǔ)存單元、單位預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果表明AC－BM算法在上述3項(xiàng)測(cè)試中取得了很好的性能平衡。這也是新

版的Snort系統(tǒng)中選用AC－BM算法的重要原因。

4 入侵檢測(cè)系統(tǒng)中模式匹配算法的研究方向

常用的模式匹配算法所采用的思想主要有基于字符比較、基于自動(dòng)機(jī)、基于hash查找、基于位邏輯運(yùn)算和基于Tries樹型機(jī)構(gòu)搜索。鑒于目前網(wǎng)絡(luò)的實(shí)際狀況，多模式匹配算法更加適合于基于模式匹配的入侵檢測(cè)系統(tǒng)。這里認(rèn)為應(yīng)該從下面3個(gè)方面著手：一是繼續(xù)研究和改進(jìn)精確的模式匹配，將快速的單模式匹配算法和多模式匹配算法相結(jié)合，充分借鑒同類算法的先進(jìn)思想，如：引入Hash函數(shù)、引入自動(dòng)機(jī)、對(duì)字符串分塊等來不斷提高多模式匹配算法的性能；二是嘗試采用模糊匹配的策略，國(guó)外對(duì)此已經(jīng)開始進(jìn)行相應(yīng)的研究；三是對(duì)網(wǎng)絡(luò)數(shù)據(jù)包和入侵特征進(jìn)行研究，總結(jié)出這兩類字符串特點(diǎn)，有針對(duì)性地對(duì)這兩類字符串的匹配問題進(jìn)行研究。

5 結(jié) 語(yǔ)

網(wǎng)絡(luò)帶寬的不斷增加、日益嚴(yán)重的網(wǎng)絡(luò)安全狀況要求必須盡快提高網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能。雖然入侵檢測(cè)系統(tǒng)可以采用很多技術(shù)，并且這些技術(shù)也在不斷的研究和發(fā)展中，但是目前主流的實(shí)用的入侵檢測(cè)技術(shù)仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測(cè)系統(tǒng)的一個(gè)關(guān)鍵所在。在此對(duì)已有的經(jīng)典模式匹配算法進(jìn)行了系統(tǒng)綜述，并對(duì)入侵檢測(cè)系統(tǒng)中模式匹配算法的未來研究方向給出了觀點(diǎn)。

參考文獻(xiàn)

［1］龐善臣,王淑棟,蔣昌俊.BM串匹配的一個(gè)改進(jìn)算法［J］.計(jì)算機(jī)應(yīng)用,2004,12(12):11－13.

［2］Boyer R S,Moore J S.A Fast String Searching Algorithm ［J］.Communications of ACM,1977,20(10):762－772.

［3］張立航,潘正運(yùn),劉海峰.基于改進(jìn)的KR算法在網(wǎng)閘中的實(shí)現(xiàn)［J］.微計(jì)算機(jī)信息(管控一體化),2008(24):137－138.

［4］Johnson T,Newman－Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks ［J］.Journal of Parallel and Distributed Computing,1996,32(1):74－89.

［5］Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort ［EB/OL］.http://www.silicondefense.com/sotfware/acbm/speed－of－snort－03－16－2001.padf,2003.

［6］黃占友,劉悅.對(duì)KMP串匹配算法的改進(jìn)［A］.第四次全國(guó)便攜計(jì)算機(jī)學(xué)術(shù)交流會(huì)論文集［C］.北京:科學(xué)出版社,1997.

［7］賀龍濤,方濱興,胡銘曾.對(duì)BM串匹配算法的一個(gè)改進(jìn)［J］.計(jì)算機(jī)應(yīng)用,2003,23(3):6－8.

［8］張國(guó)平,徐汶東.字符串模式匹配算法的改進(jìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì),2007,28(20):4 881－4 884.

［9］蔡曉妍,戴冠中,楊黎斌.一種快速的單模式匹配算法［J］.計(jì)算機(jī)應(yīng)用研究,2008,25(1):45－46,81.

［10］盧汪節(jié),鞠時(shí)光.入侵檢測(cè)系統(tǒng)中一種改進(jìn)的AC算法［J］.計(jì)算機(jī)工程與應(yīng)用,2006(15):146－148.

［11］萬國(guó)根,秦志光.改進(jìn)的AC－BM字符串匹配算法［J］.電子科技大學(xué)學(xué)報(bào),2006,35(4):531－533.

［12］周四偉,蔡勇.AC－BM算法的改進(jìn)及其在入侵檢測(cè)中的應(yīng)用［J］.微計(jì)算機(jī)應(yīng)用,2007,28(1):27－31.

［13］王琢,趙永哲,姜占華.網(wǎng)絡(luò)處理模式匹配算法研究［J］.計(jì)算機(jī)應(yīng)用研究,2007,24(12):310－312.

作者簡(jiǎn)介

冉占軍 男，1977年出生，陜西西安人，講師，碩士研究生。主要研究方向?yàn)樗惴?、網(wǎng)絡(luò)安全。

姚全珠 男，1960年出生，博士，教授。主要研究方向?yàn)樗惴ā?shù)據(jù)庫(kù)、網(wǎng)絡(luò)安全。

王曉峰 女，1966年出生，博士，副教授。主要研究方向?yàn)樾畔踩?/p>

鄒又姣 女，1975年出生，碩士，講師。主要研究方向?yàn)樾畔踩?/p>