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

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

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

中圖分類號：TP301文獻標(biāo)識碼：B

文章編號：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)用層出不窮。面對日益突出的網(wǎng)絡(luò)安全問題，僅靠傳統(tǒng)的被動防御已經(jīng)不能滿足要求，能夠主動檢測并預(yù)防的入侵檢測系統(tǒng)應(yīng)運而生。

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

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

1 單模式匹配算法

1.1 相關(guān)定義

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

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

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

多模式匹配算法：在目標(biāo)串中可同時對多個模式串進行匹配的算法。

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

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

1.2 KMP算法

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

KMP算法的基本思想是：若某趟匹配過程中T璱和P璲不匹配，而前j-1個字符已經(jīng)匹配。此時只需右移模式串P，目標(biāo)串T不動，即指針i不回溯，讓P璳與T璱繼續(xù)比較。移動后重新開始比較的位置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時

1.3 BM算法

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

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

(1) 好后綴移動。其又分為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的最小值作為移動距離。因此可以定義一個距離函數(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) 壞字符移動。P中的某個字符與T中的某個字符不相同時使用壞字符移動。右滑距離函數(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},

其他情況

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

1.4 RK算法

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

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

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

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

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

式中：q∈［1…n2m］且為素數(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中長度為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中每個長度為m的子串的Hash函數(shù)值計算出來。

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

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

1.5 單模式匹配算法改進情況簡介

研究人員對單模式匹配算法提出了不少變形和改進算法。

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

2 多模式匹配算法

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

與單模式匹配算法相比，多模式匹配算法的優(yōu)勢在于一趟遍歷可以對多個模式進行匹配，從而大大提高了匹配效率。對于單模式匹配算法，如果要匹配多個模式，那么有幾個模式就需要幾趟遍歷。當(dāng)然多模式匹配算法也適用于單模式的情況。在入侵檢測系統(tǒng)中，一條入侵特征可能匹配或部分匹配很多條規(guī)則，如果采用單模式匹配，在匹配每條規(guī)則時都需要重新運行匹配算法，效率很低。然而，日益增多的網(wǎng)絡(luò)攻擊使得入侵檢測的規(guī)則數(shù)目仍在不斷增長，例如，Snort1.8.3的規(guī)則為1 270條，snort2.0的規(guī)則為2 300多條，到Snort 2.6.1則增加到3 600多條規(guī)則，因此，單純提高單模式匹配算法的效率，很難使入侵檢測系統(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)生于貝爾實驗室，最早用于圖書館的書目查詢程序中。該算法基于有限狀態(tài)自動機(FSA),在進行匹配之前先對模式串集合SP進行預(yù)處理，形成模式樹(樹形FSA)，然后只需對目標(biāo)串T掃描一次就可以找出所有與其匹配的模式串P。模式樹K的構(gòu)成如下：

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

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

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

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

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

圖3 模式樹

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

由模式樹擴展所得的AC自動機M是1個6元組：

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

其中：

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

(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é)點上出來的邊上的標(biāo)簽沒有a，則g(0,a) =0，即如果沒有匹配的字符出現(xiàn)，自動機停留在初態(tài)；

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

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

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

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

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

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

2.3 AC－BM算法

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

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

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

2.4 AC，AC－BM算法改進情況簡介

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

參考文獻

［1］龐善臣,王淑棟,蔣昌俊.BM串匹配的一個改進算法［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］張立航,潘正運,劉海峰.基于改進的KR算法在網(wǎng)閘中的實現(xiàn)［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］黃占友,劉悅.對KMP串匹配算法的改進［A］.第四次全國便攜計算機學(xué)術(shù)交流會論文集［C］.北京:科學(xué)出版社,1997.

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

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

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

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

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

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

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

作者簡介

冉占軍 男，1977年出生，陜西西安人，講師，碩士研究生。主要研究方向為算法、網(wǎng)絡(luò)安全。

姚全珠 男，1960年出生，博士，教授。主要研究方向為算法、數(shù)據(jù)庫、網(wǎng)絡(luò)安全。

王曉峰 女，1966年出生，博士，副教授。主要研究方向為信息安全。

鄒又姣 女，1975年出生，碩士，講師。主要研究方向為信息安全。