一種面向入侵檢測的Ｗｕ－Ｍａｎｂｅｒ算法研究

摘要：模式匹配算法是入侵防御系統中檢測引擎的核心算法，模式匹配算法的效率決定了入侵防御系統的性能。本文對模式匹配算法進行了研究，重點分析了多模式匹配算法Wu-Manber算法，并針對Wu-Manber算法存在的不足，提出了Wu-Manber算法的改進算法。

關鍵詞：入侵防御系統；多模式匹配；Wu-Manber算法

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)12-2pppp-0c

Research on Wu-Manber Algorithm for Intrusion Detection

(1.Department of Computer Science and Technology，Huaihua University，Huaihua 418008，China；2.School of Software .uestc，Chengdu 610054，China)

Abstract:Pattern matching algorithm is one of the core algorithms in the detection engine of the intrusion prevention system. Efficiency of the intrusion prevention system is determined by pattern matching algorithm. A survey of the pattern matching algorithm is described in this thesis. The Wu-Manber algorithm which is one of the multi-pattern matching algorithm is explained in detail， and the improvement of the the Wu-Manber algorithm is presented to improve the efficiency.

Key words:intrusion prevention system; multi-pattern matching; Wu-Manber algorithm

網絡入侵檢測系統(NIDS)作為提高網絡系統安全性的重要技術之一，已經得到了廣泛應用。典型的NIDS是用一系列的規則(特征)來描述已知的攻擊行為。一條規則包含了一個或多個用以識別某種攻擊行為的模式串[1]。隨著網絡速度和入侵檢測規則的持續增長，模式匹配正在成為網絡入侵檢測系統的性能瓶頸。因此有必要對現有的多模式匹配算法進行改進，提高檢測速度。

本文對多模式匹配算法Wu-Manber算法進行了研究，針對Wu-Manber算法存在的不足，提出了Wu-Manber算法的改進算法。通過實驗證明了改進算法相對于原算法具有較高的性能。

1 Wu-Manber算法

Wu-Manber算法是BM算法的擴展算法，是一種實用的多模式匹配算法。它的主要特點是采用了BM算法的不良字符轉移機制，利用塊字符擴展了不良字符轉移的效果，同時使用散列表來篩選匹配階段應進行匹配的模式串，減少匹配計算量。Wu-Manber算法的執行時間不會隨著模式集的增加而成比例增長，而且要遠少于使用每一個模式串和BM算法對文本進行匹配的時間總和[2]。Wu-Manber算法是應用中平均性能最好的一個算法。

在介紹Wu-Manber算法前首先定義以下一些變量：

包含r個模式的模式集 P={p1，p2，…pr}；

文本串T=t1t2…tn；

B:塊字符長度；

m:模式集中最短模式串的長度；

n：文本長度；

hash：塊字符散列函數；

|P|：模式集中模式數量；

∑：字符集。

Wu-Manber算法采用了跳躍不可能匹配字符的策略和hash散列的方法，以加速匹配的進行。算法需要對所有模式進行預處理，預處理需構建SHIFT，HASH 和PREFIX 3個表。SHIFT表用于在掃描文本串的時候，根據讀入字符串決定可以跳過的字符數。HASH表用來存放指針，此指針指向后綴散列值相同的所有模式串的模式串鏈表。PREFIX表存儲每個模式串的前B個字符的字符塊的散列值。掃描時如果SHIFT表中相應的跳躍值為0，則說明可能產生匹配，就要用到HASH表和PREFIX表做進一步判斷，找出有哪些匹配候選模式串，并驗證是哪個或者哪些候選模式與文本完全匹配[3]。

1.1 算法預處理

(1)首先計算模式集P中最小模式串的長度m，并且只考慮每個模式串的前m個字符，即要求所有的模式串有相同的長度m。

(2)以長度為B的塊字符作為比較的基本單位，而不是以單個字符作為比較的基本單位。B的取值為log∑(2*m*r)，通常B的值為2或3。

(3)構建SHIFT表：SHIFT表中存儲字符集中所有快字符在文本中出現時的轉移距離。假設S是當前正在處理的字符集中長度為B個字符的字符塊，計算其散列值為h，作為SHIFT表的索引。如果字符塊S不出現在任何模式串中，則在SHIFT[h]中存放m-B+1。如果S在某些模式串中出現，查看模式串中S出現的最右位置。假設S在pi中的q位出現，并且在其他模式串中出現S的位置都不大于q。那么在SHIFT[h]中存放m-q。

(4)構建HASH表：計算每個模式串的后B個字符的字符塊的散列值h，后B個字符散列值相同的所有模式串組成一個模式串鏈表。在HASH[h]中存放指向此鏈表的指針。

(5)構建PREFIX表：存儲每個模式串的前B個字符的字符塊的散列值[4]。

1.2 算法掃描

匹配從文本的第m個字符開始，對模式的匹配從右向左進行，每次掃描B個字符：

(1)對文本中的當前長度為B的塊字符計算其hash值h。

(2)檢查SHIFT[h]是否為0。如果大于0，移動文本并返回(1)，否則進入第(3)步。

(3)計算當前文本窗口的前綴hash值，記為text_prefix。

(4)檢查滿足HASH[h]≤p

2 改進的Wu-Manber算法

2.1 Wu-ManberM算法的不足

假如文本串T為：“Natural language texts are not random”；

模式串為：texts、language、maxts和boxts；

HASH表和PREFIX表如圖1和圖2所示。

HASH表第一項中的指針p1指向了具有三個元素的模式串鏈表。

當匹配過程進行到第6步時，即SHIFT（hash(ts)）=0。計算文本窗口的B個字符前綴的hash值text_prefix，并轉入HASH表。此時HASH表所對應的項存儲的是指向以ts為尾塊的模式串鏈表的指針。需查找PREFIX表，對模式串鏈表的每一項考察其前綴hash值是否與text_prefix相等[5]。

本例中對于此種情況需進行三次比較。從上面的實例可以總結出Wu-Manber算法具有這樣的不足：隨著模式串的增加，多個模式串擁有相同后綴的情況也會增加，即所構建的HASH表相應表項內的指針所指向的模式串鏈表長度增加，從而增加查找PREFIX表的次數，并導致PREFIX表內容和當前文本窗口的前綴hash值比較次數。這樣必然使匹配過程需要更多的比較次數，影響算法性能。

2.2 改進算法的設計思想

根據上面討論的Wu-Manber算法中存在的不足，提出算法改進思想：

(1)修改HASH表的結構，使它不再以模式串的后綴hash值作為入口。在算法的預處理階段，對每個模式串計算其前綴和后綴所組成字符塊的hash值，以此作為HASH表的入口。

因為通常情況下不同的模式串，同時具有相同的后綴和前綴的情況非常少，因而這樣處理可以減少HASH表中指向的模式鏈表的模式串數量，從而減少文本窗口前綴hash值和PREFIX表項的比較次數，提高算法匹配效率。

(2)由于將每個模式串的前綴和后綴組成的字符塊hash值作為HASH表的入口，即將模式串的前綴信息加入到了HASH表中，而原算法中PREFIX表中存儲的正是模式串前綴hash值，在這種情況下PREFIX表與HASH表功能發生了沖突，因而在改進的Wu-Manber算法中取消PREFIX表的構建。

2.3 改進算法的設計

(1)算法預處理階段

①首先計算模式集P中最小模式串的長度m。并且只考慮每個模式串的前m個字符。即要求所有的模式串具有相同的長度m。

②確定B的值，B的值取2或3。

③構建SHIFT表：與Wu-Manber算法的SHIFT表構建方法相同。

④構建HASH表：計算每個模式串的后B個字符和前B個字符組成的字符塊的散列值h1，散列值相同的所有模式串組成一個模式串鏈表。在HASH[h1]中存放指向此鏈表的指針。

(2)掃描階段

匹配從文本的第m個字符開始，對模式的匹配從右向左進行，每次掃描B個字符：

①對文本中的當前長度為B的塊字符計算其hash值。

②檢查SHIFT[h]是否為0。如果大于0，移動文本并返回(1)，否則進入第③步。

③計算當前文本窗口的前綴，并與后綴組成新的塊字符，并計算其hash值，記為h1。

④檢查滿足HASH[h1]項是否為存在。如過存在，即HASH[h1]=p，則將p指向的模式鏈表中的每個模式串和當前文本比較。如匹配，將其記錄。文本窗口后移一位，返回第①步，直到比較結束。如HASH[h1]項不存在，說明沒有模式串滿足這樣的條件，返回第①步，直到比較結束。

2.4 改進的Wu-Manber算法描述

while (text <= textend) {

h=hashBlock(text) /*計算當前文本塊hash值*/

shift=SHIFT[h];/*查看跳躍距離*/

if(shift==0){

h1=hashBlock(text+text_prefix); /*計算文本前綴和后綴組成

的字符塊的hash值*/

p=HASH[h1];/*得到可能與當前文本匹配

的模式串鏈表入口*/

while(p){

進行完全匹配。如發現匹配，報告結果

}

shift=1;

}

text += shift;

}

2.5 改進的Wu-Manber算法實例

文本串T為：“Natural language texts are not random”；

模式串為：texts、language、maxts和boxts；

最短模式長度：m=5。

(1)計算SHIFT表

這里取B=2。

計算每個塊字符的散列值和塊字符與模式串串尾的距離。此即為當該字符塊在文本中出現時的跳轉距離，參見表1。

(2)構建HASH表，參見圖3。

(3)匹配過程

①Natural language texts are not random

pos = 5，B = 2，所以tpos-B+1…tpos即為t4t5 = ur

SHIFT(hash(ur))=4 不等于0，下次開始搜尋Text的位置pos = 5+4=9

②Natural language texts are not random

pos = 9，B = 2，所以tpos-B+1…tpos即為t8t9 =l

SHIFT(hash( l))=4不等于0，下次開始搜尋Text的位置pos = 9+4=13

③Natural language texts are not random

pos = 13，B = 2，所以tpos-B+1…tpos即為t12t13 = gu

SHIFT(hash(gu))=0，h1=hash(lagu)=13，HASH(13)=p2，比較language與Text。發現相等，標記language出現過。pos=pos+1=14

④Natural language texts are not random

pos = 14，B = 2，所以tpos-B+1…tpos即為t13t14 = ua

SHIFT(hash(ua))=4不等于0，所以下次開始搜尋Text的位置pos = 14+4=18

⑤Natural language texts are not random

pos = 18，B = 2，所以tpos-B+1…tpos即為t17t18 =t

SHIFT(hash( t))=4不等于0，下次開始搜尋Text的位置pos = 18+4=22

⑥Natural language texts are not random

pos = 22，B = 2，所以tpos-B+1…tpos即為t21t22 = ts

SHIFT(hash(ts))=0，h1=hash(tets)=13，HASH(13))=p1，比較texts與Text。發現相等，標記texts出現過。pos=pos+1=23

⑦Natural language texts are random

pos = 23，B = 2，所以tpos-B+1…tpos即為t22t23 = s

SHIFT(hash(s ))=4不等于0，下次開始搜尋Text的位置pos = 23+4=27

⑧Natural language texts are random

pos = 27，B = 2，所以tpos-B+1…tpos即為t26t27 = e

SHIFT(hash(e ))=4不等于0，下次開始搜尋Text的位置pos = 27+4=31

⑨Natural language texts are random

pos = 31，B = 2，所以tpos-B+1…tpos即為t30t31 = nd

SHIFT(hash(nd))=4不等于0，下次開始搜尋Text的位置pos = 31+4=35

⑩ pos > length(Text)，匹配結束。

與未改進的Wu-Manber算法相比，可以看到改進的Wu-Manber算法在匹配過程中的第6步，減少了3次比較次數。

2.6 改進的Wu-Manber算法分析

(1)改進的Wu-Manber算法與原算法相比的不同之處：

①減少了當多個模式串具有相同后綴的情況下的比較次數。

②省去了PREFIX表的構建，節省了算法預處理時間和空間內存的使用。

(2)改進的Wu-Manber算法性能分析和測試

為檢驗改進后的算法性能，將改進后的算法和原算法進行實驗對比。選用衡量算法性能的主要指標——時間消耗和字符比較次數進行實際的算法效率測試。選擇純英文小說《悲慘世界》作為測試文本，測試文本字數為600378字，共3430658個字符。分別選取最小長度為5、10、15、20、30、50、100的模式串。模式串個數分別選取5、50、500。

①實驗結果

圖4—圖6為兩種算法的時間消耗比較圖，表3內容為相同情況下兩種算法的字符比較次數。

表3中的WM表示Wu-Manber算法，LWM表示改進的Wu-Manber算法。

②算法分析

從圖4—8可以看出，隨著模式串數量的增加，兩種算法在特定模式長度的情況下掃描時間都相應增大，改進的WM算法的掃描時間一直小于WM算法所用時間。隨著模式串長度的增加，兩種算法在特定模式串數量的情況下，掃描時間都相應減小，改進的WM算法掃描所用時間一直小于WM算法所用時間，但差距在逐漸縮小。

從表3可以看出，兩算法字符比對次數的比較類似于兩算法所用時間的比較。

產生這種實驗結果的原因是隨著模式串個數的增加，具有相同后綴的模式串不斷增多，當模式串較短時，算法的平均跳躍距離比較短，因而此時WM算法所用時間和改進的WM算法所用時間差距巨大。而隨著模式串長度的增加，兩種算法的平均跳躍距離也在增大，雖然WM算法中具有相同后綴的模式串同樣很多，但隨著跳躍距離的增大，WM算法所用時間也急劇減小，與改進的WM算法的差距也不斷縮小。

從實驗結果可以看出，改進后的算法性能不論在哪種情況下都比原算法有較大提高，達到了預期效果。

3 結束語

本章重點分析了經典的多模式匹配算法Wu-Manber算法，針對Wu-Manber算法在多個模式串具有相同后綴的情況下，算法效率較低的問題進行了改進，提出了改進算法的設計思想、原理，并對其進行了詳細的描述，最后通過程序仿真，證明了改進后的算法性能優于原算法性能。

參考文獻：

[1]謝希仁.計算機網絡(第4版).北京:電子工業出版社，2005.

[2]楊東紅，徐恪，崔勇.改進的Wu-Manber多模式匹配算法.清華大學學報.

[3]張鑫，譚建龍，程學旗. 一種改進的Wu-Manber多關鍵詞匹配算法[J].計算機應用， 2003.

[4]孫曉山，王強，關毅，王曉龍. 一種改進的Wu-Manber多模式匹配算法及應用.中文信息學報.

[5]WU Sun，Manber U.A Fast Algorithm for Multi-Pattern Searching. Technical Report TR 94-17，University of Arizona at Tuscon， 1994.

收稿日期：2008-01-25

作者簡介：王燦明（1980-），男，湖南漣源人，懷化學院計算機系，助教，碩士，主要研究網絡信息安全，RFID技術；肖峰（1983-），男，四川成都人，電子科技大學，在讀碩士，主要研究網絡信息安全。