巫喜紅，凌 捷

WU Xi-hong1，LING Jie2

(1. 嘉應(yīng)學院 計算機學院，梅州 514015；2. 廣東工業(yè)大學 計算機學院，廣州 510090)

0 引言

網(wǎng)絡(luò)帶給人們方便的同時也存在安全隱患，而入侵檢測系統(tǒng)(IDS)也越來越廣泛地應(yīng)用到網(wǎng)絡(luò)系統(tǒng)中，因為它是提高網(wǎng)絡(luò)系統(tǒng)安全性的重要技術(shù)之一。目前，許多IDS都是依靠模式匹配技術(shù)來進行入侵檢測的，但是，在進行入侵檢測時，花費在模式匹配上的時間占到整個IDS總處理時間的30%，對于密集型的流量，這一消耗達到80%[1]。因此，模式匹配性能的提高成為解決IDS的關(guān)鍵技術(shù)。目前，國內(nèi)外對于模式匹配算法已有不少的研究成果，比如典型的單模式算法有Brute Force算法[2]、Knuth-Morris-Pratt(KMP)算法[3]、Byoer-Moore(BM)算法[4]、Sunday算法[5]，多模式算法主要有Aho_Corasick(AC)算法[6]、Wu_Mander算法[7]。這些算法在實際應(yīng)用中忽略了字符串的特征，沒有實際考慮到字符的頻率情況，為此，本文提出了利用字符統(tǒng)計特征的算法，在掃描過程中利用某個頻率字符去進行匹配，跳過了一系列無用的字符，從而提高匹配速度。

1 幾種經(jīng)典的模式匹配算法

設(shè)文本串T=T0……Tn-1，n為文本串的長度；模式串P=P0……Pm-1，m為模式串的長度，(n＞＞m)；T和P都建立在有限字符集上，大小為σ。

對于文本串T和模式串P，在T中尋找等于P的子串，如果在T中存在等于P的子串，則稱匹配成功，函數(shù)值返回為P中第一個字符相等的字符在主串T中的序號，否則稱為匹配失敗，這個搜索過程就是模式匹配。至于如何在T中尋找等于P的子串，各種算法各顯神通，各有各的尋找方法，在此簡要介紹4種經(jīng)典匹配算法。

BF算法[2]是效率最低的算法，從左到右進行匹配。首先將T[1]與P[1]進行比較，若不同，就將T[2]與P[1]進行比較，……，否則從T[2]開始與P[1]進行比較，繼續(xù)開始下一趟的比較，重復上述過程。

KMP算法是由BF改進后不產(chǎn)生回溯的一種算法，每當匹配過程中出現(xiàn)字符串比較不等時，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右滑動盡可能遠的一段距離后，繼續(xù)進行比較。

BM算法是把P同文本串進行比較時從右向左，當某趟匹配失敗時，采用壞字符啟發(fā)規(guī)則和好后綴啟發(fā)規(guī)則計算模式串右移的距離，并取兩者最大值來決定模式串的右移量，移動盡可能遠的距離，直到匹配成功或文本串匹配結(jié)束，其匹配時從右至左進行。

Sunday算法采用BM算法中的壞字符啟發(fā)規(guī)則，開始時P的最左邊與T的最左邊對齊，模式匹配過程中進行P與T的比較時，可以從左向右或從右向左進行比較，在發(fā)現(xiàn)不匹配時，選取當前匹配窗口的下一個字符來判斷右移量以跳過盡可能多的字符，從而提高了匹配效率。其匹配時從右至左進行或者從左至右均可。

2 字符頻率描述及其已有的應(yīng)用

在網(wǎng)絡(luò)的流量中，絕大部分的報文屬于正常報文，鑒于此特征，考慮各字符在報文中出現(xiàn)的頻率來實現(xiàn)算法。文獻[8]給出了ASCII字符（頻率分布程序）的頻率分布表，如表1所示。

表1 英文字母頻率表

根據(jù)表1中字母出現(xiàn)的頻率值，從小到大排序后獲得的字母順序為：zqxjkvbpygfwmucldrhsnioate。

字符頻率在模式匹配中的應(yīng)用也有一些研究，如文獻[1]是預(yù)處理T中所有出現(xiàn)字符的頻率，并記錄其在T中出現(xiàn)的位置，之后根據(jù)這些信息查找P在T中的位置，若找到，先匹配頻率最低的，再匹配次低的，直到最后成功或遇到不匹配的字符。文獻[9]盡可能選擇失配率高度的字符進行比較，利用切分字符（T中不在模式字符串里出現(xiàn)而且在T中相對居中的字符）把T及T的子串不斷地一分為二，直到找到P或沒有長度大于或等于P的T的子串為止。文獻[10]是把字符頻率應(yīng)用到Sunday算法的改進中，它在預(yù)處理階段先確定P中最小頻率值的某個字符及其在P中的位置，在匹配過程中只是第一次根據(jù)預(yù)處理階段的信息進行匹配，第二次的右移距離還是采用Sunday算法的右移量進行跳轉(zhuǎn)。文獻[11]是在模式串中找出使用頻率最低的和次低的兩個漢字(或字符)，將它們提取作為模式串的特征子串，其他漢字(或字符)做模糊處理。

以上各文獻對字符頻率在模式匹配算法中的應(yīng)用各有千秋，在此提出另一種基于字符頻率的模式匹配算法Characters-Frequency-Pattern-Matching算法，簡稱為CFPM，其思想是：1)在預(yù)處理階段有兩個任務(wù)，一是確定P中頻率值最小的那個字符稱為關(guān)鍵字符及其在P中的位置值，二是掃描T串，確定關(guān)鍵字符在T中的位置；2)匹配階段，根據(jù)預(yù)處理階段的信息，把關(guān)鍵字符與其在T中出現(xiàn)的位置進行一一對齊，并進行雙向匹配。

3 CFPM算法

3.1 CFPM算法的預(yù)處理

在預(yù)處理階段有兩個任務(wù)，首先確定關(guān)鍵字符及其在P中的位置值，設(shè)計思路是：

1)輸入P串，計算其長度m=strlen(P)；

2)定義char *CF_value=″zqxjkvbpygfwmucldr hsnioate″，就是按照字母出現(xiàn)的頻率值從小到大的排序；

3)從CF_value[0]開始尋找P中的每個字符，若沒找到，則從CF_value[1]開始，直到找到為止，此時記錄找到的字符即關(guān)鍵字符key_ch，并記錄其在P中的位置。

其具體算法如下：

輸入：P模式串；

定義：字符串的頻率字符串CF_value，關(guān)鍵字符key_ch，key_ch在P中的位置pos，其它循環(huán)變量；

賦值：P的長度m；

功能：確定關(guān)鍵字符key_ch及其位置pos的值。

其次確定關(guān)鍵字符及其在P中的位置值，設(shè)計思路是：

1)輸入T串，計算其長度n=strlen(T)；

2)從T的第1個字符開始查找，若等于key_ch，則記錄其位置在數(shù)字數(shù)組index[]當中。

其具體算法如下：

輸入：T文本串

定義：數(shù)組index[]，其下標值為num，num的初值為0；

功能：記錄關(guān)鍵字符key_ch在T中的位置

3.2 CFPM算法的匹配過程

CFPM算法的匹配思路是進行雙向匹配，即：以關(guān)鍵字符為始點，先進行向左匹配，再進行了向右匹配，當發(fā)現(xiàn)左部分失配時，直接進行下一輪的匹配，而不用進行右部分的匹配。當兩部分均匹配成功，則輸出匹配的位置，若不在成功，則輸出失配的信息。具體算法描述如下：

1)i=0；

2)以T[index[i]]為起始點，進行T[index[i]-1]的字符與P[pos-j](j的初值是1)進行比較，若匹配，j加1不斷地進行匹配，直到匹配至P[0]；若出現(xiàn)第一個不匹配的字符，則結(jié)束左部分的匹配，執(zhí)行4)；否則執(zhí)行3)；(說明：此步驟是向左匹配)

3)進行T[index[i]+k](k的初值是1)的字符與P[pos+k]進行比較，若匹配，k加1不斷地進行匹配，直到匹配至P[m-1]；若出現(xiàn)第一個不匹配的字符，則結(jié)束右部分的匹配，執(zhí)行4)；否則執(zhí)行5)；

4)之后i加1，若i小于num，執(zhí)行2)，否則執(zhí)行6)；

5)若雙向匹配成功，則輸出匹配的位置；

6)結(jié)束匹配

其具體算法如下：

定義：定義向左、向右匹配的變量j，k，初值均為1；定義成功匹配的標志 flag，初值為0；

功能：確定P在T中的位置。

3.3 CFPM與典型算法的實例對比

對于CFPM算法，在此通過簡單實例進行匹配演示，并將之與效率較高的BM算法、Sunday算法進行對比。

例如：T=”theykasenjoyformingworks”，P=”works”，現(xiàn)通過BM算法、Sunday算法、CFPM算法分別演示P在T中的實現(xiàn)，以對比CFPM算法的優(yōu)越性。

1）BM算法的匹配演示

首先生成字符集C {k,o,r,s,w},BM_Bc函數(shù)值對應(yīng)為{1,3,2,5,4}，其余字符值均為5，其匹配過程如表2所示(表中的?表示不需要匹配的字符，粗體的字符表示匹配過的字符)。

表2 BM算法匹配過程

本例結(jié)果：匹配次數(shù)是7，匹配的字符個數(shù)是11。

表3 Sunday算法匹配過程

本例結(jié)果：匹配次數(shù)是5，匹配的字符個數(shù)是9。

表4 CFPM算法匹配過程

本例結(jié)果：匹配次數(shù)是2，匹配的字符個數(shù)是5，因為關(guān)鍵字符不需要再進行匹配。

2）Sunday算法的匹配演示

首先生成字符集C {k,o,r,s,w},Sunday_Bc函數(shù)值對應(yīng)為{2,4,3,1,5}，其余字符值均為6，其匹配過程如表3所示(表中的?表示不需要匹配的字符，粗體的字符表示匹配過的字符)。

3）CFPM算法的匹配演示

根據(jù)char *CF_value=″zqxjkvbpygfwmucldrhs nioate″，得P ="works"的關(guān)鍵字符key_ch= 'k'，其在P中的位置pos=3。在T中查找key_ch的位置分別是index[0]=4，index[1]=22。之后根據(jù)這些信息進行左右匹配，其匹配過程如表4所示(表中的?表示不需要匹配的字符，包括key_ch，即字符 'k'，只要把'k'與T[index[0]]對齊；粗體的字符表示匹配過的字符)。

從表2、表3和表4的結(jié)果可看出，CFPM算法在匹配次數(shù)和匹配的字符個數(shù)方面比BM算法、Sunday算法有明顯的改進。

3.4 CFPM算法性能分析

CFPM算法在預(yù)處理階段要進行兩個任務(wù)，其一是確定key_ch在P中的位置，根據(jù)文獻[8]，在所有的ASCII碼當中，26個小寫字母出現(xiàn)的概率較高，所以在這一過程的時間復雜度是O(m)；其二是在掃描T的過程中記錄key_ch在T中的所有位置，這一過程定義了index[]數(shù)組，由于key_ch是P中概率最小的，所以index[]數(shù)組的長度遠遠小于n，這一過程的時間復雜度是O(n)。綜合這兩點，CFPM算法在預(yù)處理階段的時間復雜度是O(m+n)。

CFPM算法在匹配階段的跳躍次數(shù)完全取決于key_ch在T中出現(xiàn)的次數(shù)也就是index[]數(shù)組的大小，而算法在匹配最多次數(shù)是m-1(key_ch不需要進行匹配)，假設(shè)key_ch的概率為p，則此階段的時間的時間復雜度是p*O(m)。當字符集較大、關(guān)鍵字符出現(xiàn)概率越小時，復雜度越小，效率越高。

4 CFPM算法性能測試

為了檢測CFPM算法的性能，隨機抽取一段文本和一個模式串，在同一臺計算機上實現(xiàn)BM算法、Sunday算法和CFPM算法。測試的操作系統(tǒng)用Windows XP，實現(xiàn)算法的軟件是Visual C++6.0。測試文本如下：

Many networks are managed by a computer called a file server. A file server has a large－capacity hard disk and special software that manages access to flies on the network. It controls how data and database are shared among users on the network and how users access master copies of data and application software on the centralized hard disk. It is the file server's job to make sure that users don't accidentally try to update a file at the same time and scramble the data. The file server may also manage the access to an expensive piece of hardware such as a laser printer.

模式串為hardware。分別測試三種算法的匹配次數(shù)和匹配字符個數(shù)，結(jié)果如表5所示。

表5 BM算法、Sunday算法和CFPM算法的實驗結(jié)果對比表

從表5可以看出：CFPM算法無論是在匹配次數(shù)還是匹配的字符個數(shù)方面，均比BM算法、Sunday算法有明顯的優(yōu)勢，這是因為匹配時只選取P中字符頻率最小的字符進行匹配，那么該字符在T中出現(xiàn)的次數(shù)也就最小，所需要右移的次數(shù)當然是最少的。另外，匹配時采用左右兩部分比較方式，在一定程度上能夠快速地判斷是否匹配。因此，CFPM算法效率更高。

5 結(jié)束語

模式匹配算法效率高低由相關(guān)算法的移動距離決定，對于移動距離和匹配字符的順序，各算法也大相徑庭。BM算法由當前匹配窗口的末字符在P中的位置來決定下一輪的移動距離，匹配方向是從右向左，Sunday算法下一輪的移動距離則由當前匹配窗口的下一位字符在P中的位置來決定，本文提出的CFPM算法是與這兩種算法不同，其移動距離是根據(jù)P中字符頻率最低的字符在T中的位置來移動，匹配時是先匹配左邊的，再匹配右邊的。由于CFPM算法能夠很大幅度地跳過壞字符，大大減少了移動的次數(shù)和比較的字符個數(shù)，減少了匹配時間，而且CFPM算法在編程方面容易實現(xiàn)，再加上入侵檢測系統(tǒng)中模式匹配的成功率很低，所以更能提高匹配失敗的概率。從總體上看，CFPM算法更符合入侵檢測系統(tǒng)的需求，在入侵檢測系統(tǒng)中更實用、更有效。

[1] 陳論,魏海平,王福威.一種面向入侵檢測的模式匹配算法[J]. 遼寧石油化工大學學報.2009,29(1):69-72.

[2] 王成,劉金剛.一種改進的字符串匹配算法.計算機工程.2006,32(2):62-64.

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

[4] Boyer RS.Moore JS.A Fast String Searching Algorithm.Communications of the ACM,1977 20(10):762-772.

[5] SUNDAY D M.A very fast substring search algorithm.Communications of the ACM,1990,33(3):132-142.

[6] Aho A V,Corasick M J. Ef ficient String Matching: An Aid to Bibliographic Search[J].Communications of the ACM,1975,18(6):333-340.

[7] S. Wu. U.Manber. A Fast Algorithm For Multi-Pattern Searching.Technical Report TR-94-17.University of Arizona.,1994,1-11.

[8] http://zh.wikipedia.org/wiki/%E8%8B%B1%E6%96%87%E5%AD%97%E6%AF%8D.

[9] 鄧一貴.基于字符頻率及分治法的字符串模式匹配算法[J]. 計算機科學.2008,35(6):168-170.

[10] 萬曉榆,楊波,樊自甫.改進的Sunday模式匹配算法[J].計算機工程.2009,35(7):125-126.

[11] 洪濤,侯整風.基于字頻的模式匹配算法[J].微計算機信息.2010,26(11-3):188-189.