多模式匹配算法研究和優(yōu)化

曹為政 葛蒙蒙

摘 要： 模式匹配在網(wǎng)絡安全領域有著重要的應用，隨著網(wǎng)絡環(huán)境的日益復雜，模式集合也隨之增加。如何高效處理千萬模式集下的字符串匹配成為網(wǎng)絡安全的瓶頸之一。本文針對多模式匹配算法AC算法和WM算法進行了研究，采用了新型基于層次掃描和子節(jié)點數(shù)目搜索的雙數(shù)組AC算法；從hash函數(shù)的選取和模式串的Tree樹存儲對WM算法進行了優(yōu)化。能有效減少系統(tǒng)的內(nèi)存占用，提高匹配效率。

關鍵詞： AC算法；WM算法；多模式匹配；信息安全；哈希函數(shù)

Abstract：Pattern matching has important applications in the field of network security. With the increasingly complex network environment the collection of patterns has also increased. How to efficiently handle string matching in the tens of millions of patterns becomes a bottleneck in network security. In this paper AC algorithm and WM algorithm which are the multi-pattern matching algorithm are studied and a double-array AC algorithm based on hierarchical scan and subnode number search are proposed. The WM algorithm is optimized from the hash function selection and Tree tree storage of the pattern string. The research could effectively reduce the system's memory footprint and improve the matching efficiency.

Key words： AC algorithm；WM algorithm；multipattern matching； information security；hash function

引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡安全已經(jīng)吸引了業(yè)界的高度關注。 “現(xiàn)今網(wǎng)絡環(huán)境下，所有網(wǎng)絡數(shù)據(jù)流量總和僅僅是當前近十個月的網(wǎng)絡數(shù)據(jù)量[1]”。當今時代每天的信息數(shù)據(jù)量更是呈現(xiàn)爆炸式的增長，能夠快速高效地對網(wǎng)絡數(shù)據(jù)流量進行處理是當前信息安全的重點研究方向。以字符串為代表的模式匹配是處理此類問題的核心，字符串匹配算法研究也隨即成為網(wǎng)絡安全領域的熱點項目內(nèi)容。

字符串匹配是指從眾多模式集合中找到符合特定規(guī)則的字符串或者模式集[2]。在現(xiàn)今龐大的網(wǎng)絡數(shù)據(jù)流量和不斷增多的模式集合情況下，對字符串匹配算法的匹配時間、內(nèi)存占用空間都提出了更高的要求。針對骨干路由節(jié)點，設計需要的模式集合更是高達幾十萬、甚至百萬，為了滿足實時處理的需求，算法就要在千萬集合下也能穩(wěn)定高效地展開運行、并輸出結果?；诖?，本文擬對傳統(tǒng)的多模式匹配算法AC[3]算法和WM[4]算法進行研究，同時結合不同的模式特征，對算法提出了一定的優(yōu)化與改進，從而使得算法在時間、空間和穩(wěn)定性上均獲提高。

1 字符串匹配算法原理

1.1 多模式字符串匹配概念

1.2.1 算法原理

1.2.1.1 算法原理分析

AC算法由3個部分構成，分別是：goto表、fail表和output表。其中，goto表是模式集合P中所有模式構成的自動轉移狀態(tài)機。fail表是記錄跳轉到的狀態(tài)不接受輸入的字符時，下一個要跳轉的狀態(tài)。output表記錄當跳轉到一個可輸出狀態(tài)時，需要輸出的模式集合。下面，關于各表的功能闡析可詳述如下。

（1）goto表。goto表是模式集合P中所有模式構造的狀態(tài)轉移自動機。構造時，由goto函數(shù)依次讀入模式集合中的每一個模式，并把這個模式添加到AC算法的Tree狀結構中。如果Tree中不包含該模式的分支，則創(chuàng)建該分支。最后把該模式的最后一個字符狀態(tài)標記為終止狀態(tài)。

（2）fail表。fail表記錄當狀態(tài)機處在某個狀態(tài)D，此時輸入的字符s沒有狀態(tài)接受時，下一個應該跳轉的狀態(tài)。實際構造思路是，對于狀態(tài)D，已經(jīng)匹配的模式前綴為pi，對于pi的所有后綴，計算其能跳轉到的最終狀態(tài)，深度最大的那個狀態(tài)就是fail表中D所對應的狀態(tài)。

（3）output表。output表記錄當?shù)竭_終止狀態(tài)時，所有包含的模式集合。每一個狀態(tài)都會有一個output表，在初始化goto表時，每一個添加成功的字符串的最后一個字符狀態(tài)都會添加一個output。在構造fail表的過程中，當某一狀態(tài)的失效狀態(tài)是終止狀態(tài)時，該狀態(tài)也會添加其失效狀態(tài)為output。

1.2.1.2 算法原理示例

以模式集合P={he，s he，hi s，he r s}構建自動機，研究推得，AC算法goto表構建流程步驟可見如下。

步驟一 如圖1所示，將模式he加入goto表。

步驟二 如圖2所示，將模式s he加入goto表。

步驟三 如圖3所示，將模式hi s加入goto表。

步驟四 如圖4所示，將模式he r s加入goto表。

1.2.1.3 掃描過程

輸入文本p，依次讀入文本的字符，按照狀態(tài)機進行狀態(tài)跳轉，當狀態(tài)失效時，則遵照fail表發(fā)生跳轉，以此類推直至掃描到最后一個字符的狀態(tài)，再根據(jù)output表將匹配到的模式來發(fā)送輸出。本次研究示例中的fail表和output表內(nèi)容可分見表1、表2。

1.2.3 算法總結

綜上分析可知，AC算法具有匹配速度快，掃描速度穩(wěn)定，對模式集合沒有要求，算法性能和模式集合無關的特點。缺點是算法的空間復雜度呈指數(shù)級增長，在大規(guī)模模式集的情況下，過大的內(nèi)存開銷會成為算法運行的瓶頸。

1.3 基于后綴的WM匹配算法

WM（Wu-Manber）算法，是基于后綴掃描的跳躍算法，利用了BM壞字符的思想。算法將建立一個掃描窗口，窗口的大小為模式集合中最短字符串的長度，在掃描窗口內(nèi)進行最大距離的跳轉。WM算法關鍵的數(shù)據(jù)結構為3個表，分別是：后綴Hash表、Shift表、Prefix表。

1.3.1 算法原理

算法預處理階段，需要根據(jù)模式集合建立后綴Hash表、Shift表、Prefix表三個數(shù)據(jù)結構，詳情即如圖2所示。

由圖5可知，各表的功能闡析可如下論述：

（1）后綴Hash表。所有模式集合以最短長度對齊后，Hash表存儲著所有B長度字符塊的Hash值大小。

（2）Shift表。記錄當字符塊不匹配時，跳轉的距離是多少。研究僅對所有模式集合的前m個字符構建Shift表，m為所有模式的最短長度。在B的選取中，通常選擇2或者3。在構建Shift表的過程中，如果字符塊s未出現(xiàn)在模式集的任何一部分子串中，則Shift〖JB（[〗s〖JB）]〗=m-B+1；如果字符塊s出現(xiàn)在模式集的子串中，則選擇s在模式集合中最靠右的位置。

（3）Prefix表。即前綴表，因為在大模式集合下，后綴Hash計算時容易產(chǎn)生沖突，為了加快掃描速度，利用Prefix表記錄模式串的前幾個字符的哈希值，能有效避免相同后綴Hash值的集合過大，提高掃描效率。

至此，研究給出算法掃描過程為：計算模式集合最短長度m，設定掃描窗口。計算后綴字符B的Hash值h。在Hash表中查找h。如果未查找到，則跳躍m-B+1個字符，若找到，則查閱表Shift。如果跳轉距離為正數(shù)，則直接跳轉相應的距離；如果跳轉距離為0，則計算前綴的Hash值，找到Prefix中相應的項，再進行完全掃描，判斷模式是否命中。

1.3.2 算法分析

WM算法通過計算Hash值，對于不能匹配的壞字符塊進行跳躍匹配，提高了掃描效率。在WM算法中，一般假設字符表中每個字符出現(xiàn)的概率是相同的，計算一個B塊Hash值的時間復雜度為O（B）。當存在一個匹配時，檢查整個模式的時間復雜度為O（m），整個掃描過程的時間復雜度為O（BN/m）。

1.3.3 算法總結

綜合前述分析發(fā)現(xiàn)，WM算法的內(nèi)存占用很小，且內(nèi)存開銷穩(wěn)定。WM算法在匹配情況較為少見的時候，掃描速度非?？?，但是當模式集合中有大量的短模式集時，就會大大降低跳轉效率，因此WM算法不適合較短的模式集合。

2 改進算法研究

2.1 AC算法的DAT實現(xiàn)和優(yōu)化

雙數(shù)組樹算法（Double Array Tree，DAT）是一種有窮自動機，基于trie的搜索算法，其復雜度和文本的長度有關，最佳時間復雜度為O（1），最壞為O（n），其中n為文本的長度。利用雙數(shù)組來實現(xiàn)AC算法，能有效減少稀疏矩陣引起的空間浪費，也可以復用未標記的空間來存儲新的狀態(tài)。

DAT由2個數(shù)組組成，分別是：base數(shù)組和check數(shù)組。2個數(shù)組大小和元素位置一一對應。base數(shù)組中的下標對應自動機中的狀態(tài)值，數(shù)組數(shù)據(jù)關聯(lián)了狀態(tài)轉移的狀態(tài)值；check數(shù)組記錄了當前狀態(tài)的父節(jié)點。i為base數(shù)組和check數(shù)組的下標，base[i]=check[i]=0時，表示這個節(jié)點還未使用；base[i]為負數(shù)時，表示此節(jié)點為終止狀態(tài)。

2.1.1 DAT算法構造過程

（1）初始化root節(jié)點，其下標為0，則base[0] = 1 check[0] = 0。

（2）對于子節(jié)點s，當節(jié)點s存在子節(jié)點時，尋找到一個k值使得check[k+ci]=0，0

（3）在check數(shù)組中，使check[t]=s。

（4）遍歷所有節(jié)點，直到所有節(jié)點均加入到數(shù)組中。

在構造了雙數(shù)組后，接著要構造fail函數(shù)和output函數(shù)。構造fail函數(shù)和KMP算法中的回溯思想類似，在求取當前狀態(tài)的fail值時，其前一個狀態(tài)（父節(jié)點）的fail值必須先行求得。首先，令tree樹中的第一層節(jié)點的fail值都為0，并依次送入隊列，這相當于初始化。然后，依次取出每一個節(jié)點m，計算m的所有子節(jié)點n的fail值，如果節(jié)點n還有子節(jié)點，則將節(jié)點n存入隊列，直到隊列為空。

2.1.2 DAT算法掃描過程

在雙數(shù)組、fail函數(shù)、output函數(shù)構建過后，就可以對文本序列進行掃描。對于當前狀態(tài)s，讀入字符c，如果check[base[s]+c]=s，則狀態(tài)s接收字符c，跳轉到下一個狀態(tài)t=base[s]+c；否則說明狀態(tài)s不接收字符c，需要跳轉到狀態(tài)s的失效狀態(tài)，直到字符c被接收或者跳轉到根狀態(tài)。

通過雙數(shù)組的方式實現(xiàn)了AC算法，在保證高效掃描的同時，也極大地壓縮地狀態(tài)內(nèi)存，其最大時間復雜度仍為O（n），這里的n為文本序列的長度。

2.1.3 DAT算法優(yōu)化

DAT算法能有效減少傳統(tǒng)AC算法tree樹實現(xiàn)過程中稀疏矩陣帶來的內(nèi)存開銷，用base數(shù)組來記錄其跳轉狀態(tài)，check數(shù)組記錄其父節(jié)點的狀態(tài)。但是在生成雙數(shù)組的過程中，仍會產(chǎn)生部分空間浪費，在構造時就會涉及到數(shù)組數(shù)據(jù)的局部調(diào)整，從而占用過多的時間。本次研究主要從初始化時間和內(nèi)存占用方面展開設計優(yōu)化。

通常的雙數(shù)組構造都是采用基于深度優(yōu)先或者廣度優(yōu)先的搜索方法，這種方法容易導致數(shù)組數(shù)據(jù)沖突，會生出更大的內(nèi)存占用和數(shù)組調(diào)整的時間開銷。為此，本文將采用基于層次遍歷的方法構造雙數(shù)組，并優(yōu)先將子節(jié)點個數(shù)多的節(jié)點加入到數(shù)組中，如圖6所示，從而減少在構造base數(shù)組中產(chǎn)生的沖突。優(yōu)化后的DAT算法構造步驟可表述如下。

（1）將所有模式集合按照字典序列從小到大循序排列。

（2）初始化節(jié)點列表，把第一層所有節(jié)點加入到列表。

（3）選擇子節(jié)點最多的節(jié)點，計算其base表值、子節(jié)點的check表值，然后將其所有子節(jié)點加入到列表中。

（4）重復（3）直到列表為空。

（5）構建fail表和output表。

2.2 WM算法優(yōu)化

WM算法是基于后綴掃描的跳躍算法，主要包括利用hash函數(shù)對字符串掃描和對沖突字符串的完全掃描。這里主要將針對這2部分內(nèi)容提供設計優(yōu)化。研究可得過程內(nèi)容如下。

2.2.1 hash函數(shù)選取

針對不同規(guī)模的數(shù)據(jù)，不同的hash函數(shù)產(chǎn)生沖突的大小也不一致[8]。在這里，研究選取了5種常用的hash函數(shù)DJBHash[9]、APHash[9]、JSHash[9]、RSHash[9]和PJWHash[10]，并對其進行了數(shù)據(jù)沖突對比。

測試過程為：3次隨機產(chǎn)生1 000萬的模式集合，記錄每種hash方法產(chǎn)生的沖突個數(shù)測試結果如圖7所示。通過對比發(fā)現(xiàn)APHash算法沖突最小。同時，關于APHash算法，進一步研發(fā)得到如下執(zhí)行代碼：

輸入：待計算字符串

輸出：哈希值

方法：通過移位異或操作計算

unsigned int APHash（char*str）{

unsigned int hash=0 ；

int i ；

for（i=0；*str；i++）{

if（（i&1）==0）{

hash^=（（hash<<7）^（*str++）^（hash>>3））；

}else{

hash^=（～（（hash<<11）^（*str++）^（hash>>5）））；

}

}

return（hash % M）；

}

2.2.2 采用tree存儲沖突模式串

在完全掃描沖突模式的過程中，以往就是采用鏈表的形式來存儲沖突的模式集合，在千萬模式集合下，沖突的模式串會比較多，此時的掃描時間復雜度為O（M*l），其中M為沖突模式個數(shù)，l為模式的長度。顯而易見，時間花費較為可觀。

本次研究采用了tree樹來存儲沖突的模式字符串，采用樹來存儲后，只需掃描一遍就能確定命中的字符串，其時間復雜度為O（l），其中l(wèi)為沖突模式串長度。

3 實驗結果分析

3.1 實驗環(huán)境

系統(tǒng)環(huán)境為：centos 7；硬件平臺為：X86_64；系統(tǒng)內(nèi)存為：16 G。

3.2 實驗分析

測試時，將AC算法和優(yōu)化后的DAT算法同時處理2萬～12萬的模式集合，從而比較2種算法的匹配速度。測試結果如表3所示。由表3可以看到優(yōu)化后的DAC算法效率大約是AC算法的2～3倍，提升效果相當明顯。

同時，也測試了優(yōu)化后WM算法的性能情況。測試數(shù)據(jù)集從50萬增長到500萬。測試結果見表4。由表4可以看到初始化時間基本小于10 s，即使數(shù)據(jù)規(guī)模達到500萬時，其預處理時間也不超過15 s。在匹配掃描時，掃描時間更是大大提高，整體時間均小于15 us。研究可知即使針對千萬模式集合匹配，優(yōu)化后的WM算法也具有良好效果。

4 結束語

本文對多模式匹配算法AC算法和WM算法進行了研究，分析了其原理和優(yōu)缺點。并針對算法特點提出了基于層次遍歷和子節(jié)點數(shù)目搜索的雙數(shù)組算法，對AC算法進行了優(yōu)化；針對WM算法的哈希和模式存儲方面也實現(xiàn)了相關優(yōu)化。從而使得多模式匹配算法在空間利用和匹配效率方面均已獲得了改良與提高。

參考文獻

[1] GRAY J. What next？A few remaining problems in information technology[Z]. Atlanta：ACM FCRC，1998.

[2] 張麗霞，陳莉 . 一種改進的模式匹配算法[J]. 微計算機信息 2008，24（30） ：68-70.

[3] AHO A V CORASICK M J. Efficient string matching： An aid to bibliographic search[J]. Communications of the ACM 1975，18（6）：333-340.

[4] WU S MANBER U. A fast algorithm for multipattern searching[R]. Tucson AZ：University of Arizona 1994.

[5] YAO A C. The complexity of pattern matching for a random string[J]. SIAM Journal of Computing 1979 8（3）： 368-387.

[6] NAVARRO G FREDRIKSSON K. Average complexity of exact and approximate multiple string matching[J]. Theoretical Computer Science 2004 321（2-3）：283-290.

[7] 劉燕兵. 串匹配算法優(yōu)化技術的研究[D]. 北京：中國科學院（計算技術研究所） 2006.

[8] 張鑫，譚建龍，程學旗. 一種改進的WuManber多關鍵詞匹配算法[J]. 計算機應用 2003 23（7）： 29-31.

[9] DUAN Fei ZHENG Yan. Analysis of duplicated Web pages identification methods in search engine[C]//2010 2nd international Workshop on Database Technology and Applications. Wuhan China： IEEE，2010：1-5.

[10]LITTLE M C SHRIVASTAVA S K，SPERIS N A. Using bloom filters to speedup name lookup in distributed systems[J]. The Computer Journal 2002 45（6）： 645-652.