DHSWM：一種改進的WM多模式匹配算法

劉衛(wèi)國，胡勇剛

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

目前，大多數(shù)網(wǎng)絡(luò)入侵檢測系統(tǒng)(Network intrusion detection system，NIDS)的檢測引擎采用的是模式匹配技術(shù)。測試結(jié)果表明，系統(tǒng)用于模式匹配的時間占到NIDS整個處理時間的30%，在網(wǎng)絡(luò)流量密集情況下達 80%[1]。因此，通過改進模式匹配算法能有效地提高系統(tǒng)的檢測速度。模式匹配算法包括單模式匹配算法和多模式匹配算法，常見的單模式匹配算法有 Knuth-Morris-Patt(KMP)算法[2]和 Boyer-Moore(BM)算法[3]等。其中，BM算法應(yīng)用較廣泛, 其檢測速度比KMP算法速度快3～5 倍，但在模式集規(guī)模較大時，BM 算法的效率難以滿足實際要求。多模式匹配算法包括 Aho-Corasick(AC)算法[4]和 Wu-Manber(WM)算法[5]等。AC算法是在 KMP算法的基礎(chǔ)上采用有限狀態(tài)機原理構(gòu)造模式樹，在模式數(shù)目較多時能獲得較高的查找效率，但通常構(gòu)造模式樹會占用大量的存儲空間。WM算法主要基于字符跳躍思想和Hash散列技術(shù)，能大大提高匹配速度。近年來，很多研究者通過改進 WM 算法以獲得更高的查找效率。Yang等[6]結(jié)合QS算法思想[7]提出了QWM算法，在查找階段利用文本的前綴匹配信息判斷是否進行匹配操作，并擴大窗口的最大滑動距離，改進后的算法比WM算法查找時間更少。Choi等[8]通過增加最短模式串長度提出L+1-MWM算法，可以得到更長的滑動距離；當(dāng)最短模式串長度小于5時，該算法比WM算法平均查找時間減少38.87%。但改進后的算法在大規(guī)模模式集情況下，也像WM算法那樣無法避免在哈希表中出現(xiàn)長度過長的模式鏈表，為此，研究者們通過減少在Hash表中的鏈表查找時間來提高匹配速度。吳冰等[9]通過對特征串進行優(yōu)化的方法，避免模式鏈表分支不平衡的問題，發(fā)現(xiàn)WM算法的查找效率能得到較大提高；Zhang等[10]在查找時通過判斷前綴鏈表中模式串地址是否在哈希表中鏈表地址范圍來避免遍歷哈希表中的鏈表，減少冗余的匹配操作，但需面臨遍歷前綴表中過長鏈表的問題?？梢姡绾卧谀Ｊ郊?guī)模不斷增大的情況下保持 WM 算法的高效查找特性[11-12]是一個必須解決的問題。本文作者采用雙哈希查找來改進Wu-Manber算法(Double Hash searching Wu-Manber algorithm，DHSWM)，從而提高算法的查找效率。

1 WM算法分析

1.1 約定

定義1 字符集：由一定數(shù)目的字符構(gòu)成的集合，記為Σ，其字符個數(shù)記為|Σ|。本文取∑為ASCII字符集，|Σ|=128。

定義 2 模式集：把用于匹配的字符串稱為模式串，記為 p，由多個模式串組成的集合叫模式集，記為其中：

定義3 滑動：在文本中發(fā)現(xiàn)與模式pi完全匹配的字符串或者在匹配窗口中出現(xiàn)與模式中不同的字符時，將匹配窗口左移或右移，稱為滑動。在滑動過程中跳躍的字符個數(shù)稱為滑動距離。

定義4 模式匹配：給定字符集Σ，模式集為P，長度為n的文本串若在T中能找到pi，則匹配成功；若匹配失敗，則將匹配窗口向左或向右滑動，繼續(xù)匹配。在T中查找pi的過程稱為模式匹配。

1.2 WM算法描述

WM算法主要包含預(yù)處理和查找2個階段。

1.2.1 預(yù)處理階段

(1) Shift表的建立。在每次嘗試匹配時，考慮一個長度為k的字符串，記為S。在Shift表中存儲的是在匹配S時窗口可以滑動的距離，計算k個字符的一個整數(shù)匹配值作為Shift表的索引，假設(shè)S和Shift表中的第i個入口匹配，取所有模式串的前m個字符，存在2種情況：

① 若字符串S不在任何模式中出現(xiàn)，則可以安全地將匹配窗口向右滑動 m-k+1個字符的距離，取Shift[i]=m-k+1。

② 若S在某些模式串中出現(xiàn)，則找出S在這些模式中出現(xiàn)的位置，取最右出現(xiàn)的位置。假設(shè)S在模式pi的q處結(jié)束，且S在其他任何模式中并不結(jié)束于比q大的位置，取Shift[i]=m-q。

(2) Hash表的建立。取模式串的前m個字符，計算其k個字符后綴的哈希值，采用鏈表存儲具有相同哈希值的模式串，哈希表中存儲指向鏈表入口的指針。

(3) Prefix表的建立。Prefix表與Hash表類似，在建立時計算模式串k個字符前綴的哈希值，將具有相同前綴的模式串存儲于同一鏈表中。

1.2.2 查找階段

在查找階段，計算當(dāng)前匹配文本T的后k個字符的哈希值i，Hash表與Shift表采用相同的哈希值作為索引。當(dāng) Shift[i]≠0時，將匹配窗口向右滑動 Shift[i]個字符并繼續(xù)掃描；當(dāng) Shift[i]=0，則 Hash[i]包含 1個指針指向所有具有相同后綴的模式鏈表，遍歷該鏈表，計算各個模式前k個字符的哈希值h和T中前k個字符的哈希值h’，若h≠h’，則可過濾掉后綴相同但前綴不同的模式串；若h=h’，則進行精確匹配，若成功則輸出匹配結(jié)果，同時，將匹配窗口向右滑動1位；若匹配失敗，則匹配窗口向右滑動1位，繼續(xù)查找。

1.3 WM算法存在的主要問題

通過對WM算法的分析，可以發(fā)現(xiàn)以下問題：

(1) 在預(yù)處理階段建立的 3個表的功能有重疊，其中：Shift表用來判斷是否進入精確匹配操作和記錄滑動距離；Hash表存儲后綴相同的模式串鏈表；Prefix表存儲前綴相同的模式串鏈表?？梢允褂?Shift表和Hash表來查找模式串，也可以使用 Shift表和Prefix表來查找模式串，因此，Hash表和Prefix表在功能上可以相互替換。

(2) WM算法中使用Prefix表來過濾具有相同后綴但不同前綴的模式串，判斷是否需要精確匹配。因此，Prefix表實際上是用來進行簡單過濾操作，不需建立模式鏈表。

(3) 在Hash表中存儲的指針指向具有相同后綴的模式鏈表，在進行精確匹配操作時需要遍歷該鏈表。在實際應(yīng)用的入侵檢測系統(tǒng)中，模式集的規(guī)模通常很大[13]，導(dǎo)致具有某些后綴的模式串鏈表長度較長，在查找時進入該鏈表會浪費大量查找時間。

(4) WM算法在匹配操作完成之后，不論匹配成功與否，匹配窗口的滑動距離均為 1，不能跳過更多的字符，無法避免冗余的匹配操作，因此，滑動距離有擴大的可能。

這些問題使得實際應(yīng)用中 WM 算法的查找效率降低，下面針對這些問題改進算法。

2 DHSWM算法

在DHSWM算法中，除了建立Shift表、Hash表和 Prefix表 3個基本表外，另外建立 Shift 1表和Hash 1表。Shift表存儲當(dāng)前匹配窗口可滑動的距離，當(dāng)Shift表中移動值為0時，將查找模式串，Shift 1表用于存儲進行匹配操作后匹配窗口可滑動的距離。在WM 算法中，Hash表中采用鏈表結(jié)構(gòu)存儲模式串，DHSWM算法中不再維持原有的存儲結(jié)構(gòu)，Hash 1表存儲模式集中的所有模式串，具有相同后綴的模式串采用雙哈希法存儲于表中的某一連續(xù)區(qū)間，在查找時只需訪問表中的指定區(qū)間；Hash表中存儲的參數(shù)表示該連續(xù)存儲區(qū)間在 Hash 1表中的起始位置與區(qū)間長度；當(dāng)模式集給定時，模式頭綴也就確定了。Prefix表用于判斷模式集中是否存在與當(dāng)前匹配窗口中文本前綴相同的模式。

2.1 算法描述

DHSWM 算法與 WM 算法一樣也包括預(yù)處理階段和查找階段。

2.1.1 預(yù)處理階段

在預(yù)處理階段，根據(jù)給定的模式集P，建立Shift表、Shift 1表、Hash表、Hash 1表以及Prefix表。

(1) Shift表和Shift 1表的建立。Shift表的建立與WM算法中相同，而Shift 1表在Shift表基礎(chǔ)上建立。假設(shè)由k個字符組成的字符串S和Shift表中的第i個入口匹配，當(dāng)Shift[i]=0即S出現(xiàn)在某些模式串的結(jié)尾時，找出S出現(xiàn)在模式串中除結(jié)尾外的其他位置，當(dāng)S不出現(xiàn)在任何模式串中的其他位置時，取Shift1[i]為m-k+1；當(dāng)S在某個模式串pi中q’處結(jié)束，且S在其他任何模式中并不結(jié)束于比 q’大的位置，取Shift1[i]=m-q’。

(2) Hash表和Hash1表的建立。當(dāng)S出現(xiàn)在某些模式的結(jié)尾時，統(tǒng)計具有相同后綴S的模式個數(shù)，記為 N，將這些同后綴的模式串采用雙哈希法存儲于Hash 1表中的連續(xù)區(qū)間內(nèi)，令起始位置設(shè)為x，分配區(qū)間長度為 y，則具有同后綴 S的模式串存儲于Hash1[x]至 Hash 1[x+y-1]，Hash[i]存儲(x，y)用于表示模式串在Hash1表中的位置。本文分配區(qū)間長度與相同后綴的模式串?dāng)?shù)目關(guān)聯(lián)，y取最接近于2N的梅森素數(shù)[14]，這樣有3個好處：

① 快速得到素數(shù)。對于素數(shù)n=2，3，5，7，13，17等，則2n-1為梅森素數(shù)，本文只需取n=2，3，5，7即可滿足要求。

② 當(dāng)y取素數(shù)時，可以避免因y為二次函數(shù)返回值的倍數(shù)而導(dǎo)致使用二次函數(shù)存儲或查找時進入死循環(huán)的問題。

③ 使得裝載因子約為1/2，有利于發(fā)揮雙哈希法良好的查找性能。令μ為表中已用位置與表總長度的比值，稱為裝載因子。表1所示為不同裝載因子時雙哈希法查找成功和查找失敗所預(yù)計的查找次數(shù)[15]。

表1 雙哈希法查找次數(shù)與裝載因子關(guān)系表Table 1 Relationship between searching times and load factors in double Hash searching

在存儲和查找模式串時，均采用雙哈希法對Hash 1表進行操作。一次哈希函數(shù)返回字符串運算值與y求余的結(jié)果，二次哈希函數(shù)則返回1個小于y的非零整數(shù)值。例如，對模式pi前m個字符的一次哈希運算為：

(3) Prefix表的建立。Prefix表用于判斷當(dāng)前文本中的頭綴是否在模式串的頭綴中出現(xiàn)，存放的是布爾值。分別取每一個模式串前k個字符并計算其哈希值h，則Prefix[h]存放True，表示可以繼續(xù)精確匹配過程，表中的其他位置存放False，表示直接將匹配窗口向前滑動。

2.1.2 查找階段

在查找階段，假設(shè)匹配窗口長度為m，每次匹配的字符串長度為k。查找步驟如下。

(1) 將匹配窗口與匹配文本 T頂端對齊，Tp指向匹配窗口的結(jié)束位置，Tend指向文本結(jié)束位置。

(2) 當(dāng) Tp＜Tend時，取當(dāng)前匹配文本 t1t2…tm，計算文本的后k個字符的哈希值h。

(3) 若 Shift[h]＞0，則窗口向右滑動 Shift[h]個字符并返回步驟(2)；若Shift[h]=0，則轉(zhuǎn)步驟(4)。

(4) 計算當(dāng)前匹配文本前綴t1…tk的哈希值，檢查Prefix表中的值，若為True，則轉(zhuǎn)步驟(5)，若為False，則窗口向右滑動Shift1[h]個字符并轉(zhuǎn)步驟(2)。

(5) 根據(jù)Hash表中給定的參數(shù)，采用雙哈希法查找Hash 1表中對應(yīng)的區(qū)間，并按文本與模式進行精確匹配，若匹配成功，則輸出該模式并將匹配窗口向右滑動Shift1[h]個字符，然后轉(zhuǎn)步驟(2)；若匹配不成功，則將匹配窗口向右滑動 Shift1[h]個字符，然后轉(zhuǎn)步驟(2)。

2.2 算法應(yīng)用范例

假設(shè)模式集 P={still，trill，study，basic，stability}，文本 T 為“This chapter will introduce the basic concepts.”，則匹配窗口長度m=5，且令k=2。下面對WM算法和DHSWM算法的匹配過程進行對比分析。

預(yù)處理階段 WM 算法和 DHSWM 算法建立的Shift表如表2所示。表中記錄的值決定當(dāng)前匹配窗口可滑動的距離，當(dāng)Shift[i]=0時，進入精確匹配操作。DHSWM算法建立Shift1表如表3所示，表中記錄完成匹配操作后匹配窗口可滑動的距離。WM 算法中Prefix表存儲具有相同頭綴的模式鏈表，如圖1所示，計算“st”的哈希值作為索引，Prefix[Hash(st)]存儲的指針指向存放{stability，still，study}的鏈表入口。DHSWM算法改變Prefix表的結(jié)構(gòu)，不再維持模式鏈表。表中除{st，tr，ba}對應(yīng)的位置存放布爾值 True外，其他均為False，表示只有當(dāng)匹配文本的頭綴出現(xiàn)在模式串的頭綴時，才需進入精確匹配操作，如表 4所示。

在Hash表的構(gòu)建上，WM算法通過計算模式串中第m-1個和第m個字符的哈希值作為索引，將具有相同哈希值的模式串以鏈表存放，如圖 2(a)所示。Hash(ll)存儲的指針指向存放{still，trill}的鏈表，當(dāng)匹配窗口中文本的后綴為ll時，將遍歷該鏈表；DHSWM算法中新建 Hash 1表用于存儲所有的模式串，Hash表中不再維持模式鏈表，如圖2(b)所示。Hash(ll)中存儲的是Hash1表中的起始位置和分配的連續(xù)區(qū)間的長度，其值分別為9和3，后綴為ll的模式串以雙哈希法存放于Hash1[9]至Hash1[11]之間。

表2 Shift表Table 2 Shift table

表3 Shift1表Table 3 Shift1 table

圖1 WM Prefix表結(jié)構(gòu)圖Fig.1 Storage structure of WM Prefix table

圖2 Hash表對比圖Fig.2 Comparison of Hash table

表4 DHSWM Prefix表Table 4 DHSWM Prefix table

查找階段如圖3所示，其中：箭頭指向當(dāng)前匹配窗口的尾字符，右邊數(shù)字為窗口滑動的距離。圖 3(a)所示為WM算法查找過程，整個過程經(jīng)歷13次匹配，其中出現(xiàn)2次移動值為0，第1次匹配不成功，無輸出結(jié)果，將匹配窗口向右滑動1位；第2次匹配模式“basic”成功，將結(jié)果輸出同時匹配窗口向右滑動1位。圖 3(b)所示為 DHSWM 算法查找過程，整個過程 11次匹配，在出現(xiàn)移動值為0時，匹配操作完成后使用Shift 1表中的移動值，滑動距離增大至4。

圖3 查找過程示意圖Fig.3 Searching process

3 實驗與分析

測試數(shù)據(jù)：匹配文本取容量為6.82 MB的英文文檔，模式串為在ASCII字符集內(nèi)任意生成的字符串，最短模式串長度為5。模式集規(guī)模取10，50，100，200，500，1 000，5 000，10 000，20 000。編程環(huán)境為 Windows XP和JDK1.5.0。

本文實驗對比DHSWM算法與WM算法的查找時間，測試模式集規(guī)模為10～1 000時匹配成功的模式個數(shù)為5個，當(dāng)模式集規(guī)模大于5 000時匹配成功的模式為50個。實驗結(jié)果如表5所示，表中第1列為模式集中的模式數(shù)目，第2列和第3列分別為使用WM和DHSWM算法對文本匹配的查找時間。表中的查找時間取10次測試結(jié)果的平均值，第4列為DHSWM查找時間提高率。

表5 實驗結(jié)果Table 5 Result of experiment

從表5可以看出：隨著模式集規(guī)模的不斷加大，DHSWM算法與WM算法相比查找效率越來越高。其原因主要如下。

(1) 增大了匹配窗口在匹配操作之后的滑動距離。在通常情況下，Shift表中的值大于0，匹配窗口可以通過滑動跳過大部分文本。當(dāng)文本子串與模式串具有相同的后綴時，Shift表中就會出現(xiàn)值為0的情況，此時進入精確匹配操作；隨著模式集規(guī)模的增大，Shift值為0的概率也隨之增大。表6所示為模式串?dāng)?shù)目不同時，Shift表中移動值為0所占的比例。從表6可見：當(dāng)模式串?dāng)?shù)目超過1 000條時，出現(xiàn)Shift[i]=0的概率超過30%，模式串?dāng)?shù)目為20 000條時達到57%，此時需頻繁進入精確匹配操作，DHSWM算法在查找后采用Shift 1表中的移動值，這樣比WM算法跳過更多的字符，從而減少了更多的冗余匹配操作。

(2) 避免了遍歷模式鏈表。在WM算法中，Hash表以鏈表存儲具有相同后綴的模式。表7所示為模式集規(guī)模不同時其對應(yīng)Hash表中鏈表長度的分布情況。從表7可見：當(dāng)模式集規(guī)模超過500時，開始出現(xiàn)長度較長(＞10)的鏈表；當(dāng)模式集超過5 000時，出現(xiàn)長度超過50的鏈表，在查找過程中若進入此類鏈表中進行匹配操作，將耗費大量的查找時間。而DHSWM算法采用雙哈希法進行查找，當(dāng)裝載因子為1/2時，查找的次數(shù)不超過2次，因此，使用雙哈希法將縮短查找時間，從而提高查找效率。

表6 Shift表中移動值為0的比例Table 6 Percentage of value 0 in Shift table

表7 WM Hash表中鏈表長度分布表Table 7 Distribution of length of linked-list in WM Hash table 個

WM算法的查找時間與模式集規(guī)模線性正相關(guān)，本文使用雙哈希法能有效地降低查找次數(shù)，使模式數(shù)目的增加對 DHSWM 算法中查找時間的影響遠低于對WM算法中查找時間的影響。文獻[6，8，10]中提出的改進算法均能有效地提高WM算法的查找效率，但其實驗中模式數(shù)目均少于2 000條。本文將查找模式集規(guī)模擴大并有效地驗證了模式集規(guī)模增加時，DHSWM算法更能有效地提高查找效率。

4 結(jié)論

(1) DHSWM算法中改變了Prefix表的存儲結(jié)構(gòu)，新增Shift 1表用于存放在匹配操作完成之后匹配窗口可滑動的距離，在查找模式串時通過過濾匹配文本的頭綴，使用Prefix表判斷是否進行精確匹配，減少了進入精確匹配操作的次數(shù)。在完成匹配操作后，匹配窗口采用Shift 1表中的滑動距離，可以跳過更多的文本字符，避免了更多的冗余匹配操作，縮短了查找時間。

(2) DHSWM算法改變了Hash表的存儲結(jié)構(gòu)，新增Hash 1表用于存放所有模式串，在查找模式串時不再采用WM算法中遍歷模式鏈表的匹配操作，使用雙哈希法對Hash 1表進行查找匹配模式串。在模式數(shù)目較多的情況下，避免了遍歷長度較長的模式鏈表，減少了匹配次數(shù)，從而有效地提高了查找效率。

(3) 當(dāng)模式集規(guī)模較大時，DHSWM 算法的查找性能更優(yōu)。目前，網(wǎng)絡(luò)數(shù)據(jù)流量日益增大，入侵規(guī)則模式集的規(guī)模不斷增加，高效的檢測引擎有利于實現(xiàn)高速網(wǎng)絡(luò)數(shù)據(jù)流的實時入侵檢測。

[1] Fisk M, Varghese G. An analysis of fast string matching applied to content-based forwarding and intrusion detection[R]. San Diego: University of California, 2002: 1-9.

[2] Knuth D E, Morris H, Pratt V R．Fast pattern matching in strings[J]. SIAM Journal on Computing, 1977, 6(2): 323-350.

[3] Boyer R S, Moore J S. A fast string searching algorithm[J].Communications of the ACM, 1977, 20(10): 762-772.

[4] Aho A V, Corasick M J. Efficient string matching: An aid to bibliographic search[J]. Communications of the ACM, 1975,18(6): 333-340.

[5] Wu S, Manber U. A fast algorithm for multi-pattern searching[R].Tuscon: University of Arizona, 1994: 1-11.

[6] YANG Dong-hong, XU Ke. An improved Wu-Manber multiple patterns matching algorithm[C]//The 25th IEEE International Performance, Computing, and Communications Conference.Phoenix, USA, 2006: 675-680.

[7] Sunday D M. A very fast substring search algorithm[J].Communications of the ACM, 1990, 33(8): 132-142.

[8] Choi Y H, Jung M Y, Seo S W. L+1-MWM: A fast pattern matching algorithm for high-speed packet filtering[C]//2008 Proceedings IEEE INFOCOM. Phoenix, USA, 2008: 261-265.

[9] 吳冰, 云曉春. 基于網(wǎng)絡(luò)的惡意代碼檢測技術(shù)[J]. 通信學(xué)報,2007, 28(11): 87-91.WU Bing, YUN Xiao-chun. Network-based malcode detection technology[J]. Journal on Communications, 2007, 28(11):87-91.

[10] ZHANG Bao-jun, CHEN Xiao-ping, PING Ling-di. Address filtering based Wu-Manber multiple patterns matching algorithm[C]//Proceedings of the 2009 Second International Workshop on Computer Science and Engineering (WCSE 2009).Qingdao, China, 2009: 408-412.

[11] CAO Bin, LAN Hua, SHEN Xuan-jing. Application of set-based multi-pattern matching algorithm for intrusion detection system[C]//2008 Second International Symposium on Intelligent Information Technology Application. Piscataway, USA, 2008:706-710.

[12] 李雪, 薛一波. 一種適用于大規(guī)模特征集的快速匹配算法[J].計算機工程與應(yīng)用, 2007, 43(34): 168-170.LI Xue, XUE Yi-bo. High-performance string matching algorithm for large scale string set[J]. Computer Engineering and Applications, 2007, 43(34): 168-170.

[13] Wang J S, Kwak H K, Jung Y J. A fast and scalable string matching algorithm using contents correction signature hashing for network IDS[J]. IEICE Electronics Express, 2008, 5(22):949-953.

[14] 李偉勛. Mersenne數(shù) Mp都是孤立數(shù)[J]. 數(shù)學(xué)研究與評論,2007, 27(4): 693-696.LI Wei-xun. All Mersenne numbers are anti-sociable numbers[J].Journal of Mathematical Research and Exposition, 2007, 27(4):693-696.

[15] 塞奇威克. Java 算法[M]. 趙文進, 譯. 北京: 清華大學(xué)出版社, 2004: 474-478.Sedgewick R. Algorithm in Java[M]. ZHAO Wen-jin, trans.Beijing: Tsinghua University Press, 2004: 474-478.