模式匹配算法在入侵檢測中的應用

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

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

關鍵詞：入侵檢測；KMP算法；BM算法；RK算法；AC算法；AC－BM算法

中圖分類號：TP301文獻標識碼：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 引 言

隨著網絡技術的發展，各種基于網絡的應用層出不窮。面對日益突出的網絡安全問題，僅靠傳統的被動防御已經不能滿足要求，能夠主動檢測并預防的入侵檢測系統應運而生。

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

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

1 單模式匹配算法

1.1 相關定義

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

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

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

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

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

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

1.2 KMP算法

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

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

定義next［j］函數為：

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

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

0，其他情況

-1(標記)，j=0時

1.3 BM算法

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

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

(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的最小值作為移動距離。因此可以定義一個距離函數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中的某個字符不相同時使用壞字符移動。右滑距離函數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］證明算法需要的預處理時間為O(m+σ)，最壞運行時間為O，即掃描部分運行時間為O。在大字母表(相對于模式長度)情況下，BM算法非常快，實際比較次數只有目標串長度的20%~30%。

1.4 RK算法

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

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

Hash函數的構造及相應Hash值的計算如下：

設c∈∑，構造Hash函數：

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

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

映射模式串P為Hash函數值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］))

同理，映射目標串T中長度為m的子串t璱=T［i…i+m-1］為Hash函數值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函數，從而得遞推公式：

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。

根據上述公式可把目標串T中每個長度為m的子串的Hash函數值計算出來。

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

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

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

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

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

2 多模式匹配算法

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

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

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

下面介紹其中2種經典的多模式匹配算法。

2.2 AC算法

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

K的每一條邊e上都用1個字符作為標簽；

與同一節點相連的邊的標簽均不同；

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

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

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

圖3 模式樹

預處理階段，模式樹的各個節點作為狀態，根節點作為初態，標簽為模式的節點作為終態，利用轉向函數g和失效函數f作為轉移函數，將模式樹擴展成一個樹型有限自動機。

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

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

其中：

(1) Q是有限狀態集(模式樹上的節點)；

(2) Σ是有窮的輸入字符表(數據包中可能出現的所有字符)；

(3) g是轉移函數，該函數定義如下：g(s,a)：從當前狀態s開始，沿著邊上標簽為a的路徑所到的狀態。假如(u,v )邊上的標簽為a，那么g ( u,a ) =v；如果根節點上出來的邊上的標簽沒有a，則g(0,a) =0，即如果沒有匹配的字符出現，自動機停留在初態；

(4) f(不匹配時自動機的狀態轉移)也是轉移函數，該函數定義如下：

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

(5) q0∈Q是初態(根節點，標識符為0)；

(6) F罳，是終態集(以模式為標簽的節點集)。

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

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

2.3 AC－BM算法

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

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

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

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

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

3 算法的實際執行效率

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

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

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

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

版的Snort系統中選用AC－BM算法的重要原因。

4 入侵檢測系統中模式匹配算法的研究方向

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

5 結 語

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

參考文獻

［1］龐善臣,王淑棟,蔣昌俊.BM串匹配的一個改進算法［J］.計算機應用,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算法在網閘中的實現［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］.第四次全國便攜計算機學術交流會論文集［C］.北京:科學出版社,1997.

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

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

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

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

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

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

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

作者簡介

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

姚全珠 男，1960年出生，博士，教授。主要研究方向為算法、數據庫、網絡安全。

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

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