拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測、計(jì)算機(jī)病毒特征碼匹配等都會用到多模式匹配加密算法，可謂應(yīng)用之廣。那么我們今天就給大家介紹一下多模式匹配加密算法。

一、多模式匹配

所謂多模式匹配，就是在文本串T[1，…，n]中一次匹配多個模式串P1,P2,…，Pk，其中k為模式串的個數(shù)。k=1時，即為單模式匹配。模式串Pj的長度為mj,即Pj[1，…，mj]（1≤j≤k），minlen是最短模式串的長度，即minlen=min{mj|（1≤j≤q）}。多模式匹配比多個模式串逐個進(jìn)行傳統(tǒng)單模式匹配加密算法的速度要快得多。

二、常見多模式匹配加密算法

1、AC加密算法

采用AC加密算法進(jìn)行匹配需先對模式串集合進(jìn)行預(yù)處理，形成樹型有限狀態(tài)自動機(jī)，然后只需對文本串掃描1次就可找出與其匹配的所有模式串。 AC加密算法在預(yù)處理階段生成3個函數(shù)：goto（轉(zhuǎn)移）函數(shù)、failure（失效）函數(shù)和output（輸出）函數(shù)。

匹配過程從有限狀態(tài)自動機(jī)的初始狀態(tài)出發(fā)，每取出文本串中的一個字符，利用goto函數(shù)和failure函數(shù)進(jìn)入下一狀態(tài)；當(dāng)某個狀態(tài)的output函數(shù)不為空時輸出其值，表示在文本串中匹配到該模式串。

AC加密算法在對文本串進(jìn)行搜索時無跳躍，而是按順序輸入字符，無法跳過不必要的比較，因此在模式數(shù)目不是非常多的實(shí)際搜索過程中，AC加密算法性能不佳。AC極愛算法模式匹配的時間復(fù)雜度是O（n），而且與模式集中模式串的個數(shù)和每個模式串的長度無關(guān)，無論模式串P是否出現(xiàn)在T中，T中的每個字符都必須輸入狀態(tài)機(jī)中，所以無論是最好情況還是最壞情況，AC加密算法模式匹配的時間復(fù)雜度都是O（n），包括預(yù)處理時間在內(nèi)AC加密算法的總時間復(fù)雜度是O（M+n），其中M為所有模式串的長度總和。

2、WM加密算法

WM快速字符串匹配加密算法采用BM加密算法進(jìn)行跳躍的思想和hash散列方法，在實(shí)際應(yīng)用中，是大規(guī)模多模式匹配最快的加密算法之一。WM加密算法將文本串以B個字符長度分塊，稱該B個字符為1個塊字符，B為塊字符的長度，B通常取2或3。首先對模式集進(jìn)行預(yù)處理，在預(yù)處理階段構(gòu)造3個表，即shift表、hash表和prefix表。匹配過程從文本串text的第（m-B+1）（m是模式集中模式串的最小長度）個字符處開始，每次計(jì)算當(dāng)前塊字符的hash值h，通過shift[h]的值決定是否向后跳躍；當(dāng)shift[h]的值為0時，將hash[h]鏈表中的每一個模式串從后向前與text比較，如果未達(dá)到text末尾，則將text向后移動1個字符繼續(xù)比較。

WM加密算法的優(yōu)點(diǎn)：

是字符跳躍距離大，使用shift表可以跳過那些不可能成功的匹配入口，匹配入口點(diǎn)少，從而減少字符比較次數(shù)。因此實(shí)際應(yīng)用中，WM加密算法的效率一般比AC加密算法高。

WM加密算法的缺點(diǎn)：

WM加密算法在每個匹配入口點(diǎn)處，要逐個比較hash[h]表中每一個模式，在模式集數(shù)目較大時，算法性能明顯下降。

WM加密算法在模式匹配中采用啟發(fā)式搜索策略進(jìn)行字符跳躍，匹配的時間復(fù)雜度平均情況是O（Bn/m），實(shí)際應(yīng)用中B≤m，所以WM加密算法模式匹配的時間復(fù)雜度低于AC加密算法。

3、ExB加密算法

ExB加密算法是一個基于排除的字符串匹配加密算法，該加密算法能很快排除數(shù)據(jù)包負(fù)載中不包含匹配模式串的數(shù)據(jù)包。

ExB加密算法原理：

假設(shè)要檢測字符串A中是否包含子串s，如果s中至少有1個字符不包含在A中，則s就不是A的1個子串。為了減少錯誤匹配的概率，將該算法擴(kuò)充到字符對，匹配過程不僅檢測s中每個字符是否出現(xiàn)在A中，還檢測每一字符對中的字符出現(xiàn)的順序是否正確。為了快速判定給定的字符c是否屬于字符串A，該加密算法采用出現(xiàn)圖的方法。對于A中出現(xiàn)的字符c在出現(xiàn)圖中的相應(yīng)位置采用二進(jìn)制值標(biāo)記，“1”表示c屬于A，“0”表示c不屬于A。對于每個新數(shù)據(jù)包，出現(xiàn)圖都要進(jìn)行一次大開銷清零工作。為了減少這種開銷，采用每個數(shù)據(jù)包的序列號取代二進(jìn)制值來標(biāo)記出現(xiàn)圖中的相應(yīng)位置，這樣出現(xiàn)圖就無需對每一個新數(shù)據(jù)包都進(jìn)行清零。

ExB加密算法算法可分為預(yù)處理和搜索兩個階段。預(yù)處理階段的時間復(fù)雜度與數(shù)據(jù)包負(fù)載的大小成線性關(guān)系，搜索階段的時間復(fù)雜度與所有模式中的長度和成線性關(guān)系。由于在多數(shù)數(shù)據(jù)集中，入侵?jǐn)?shù)據(jù)包畢竟是少數(shù)。另外，據(jù)統(tǒng)計(jì)僅有1.6%的數(shù)據(jù)包需要用標(biāo)準(zhǔn)的字符串匹配算法進(jìn)一步確定該入侵特征串是否在數(shù)據(jù)包中，因此調(diào)用標(biāo)準(zhǔn)串匹配算法的概率很小，所以在實(shí)際應(yīng)用中，該加密算法的效率高于其他應(yīng)用于入侵檢測中的匹配加密算法。

三、多模式加密算法性能測試和結(jié)果分析

測試環(huán)境：CPU是In-telPentiumE22002.2G，內(nèi)存1G，硬盤160G，操作系統(tǒng)Win-dows2003，加密算法實(shí)現(xiàn)環(huán)境是VisualC++6.0。 利用入侵檢測訓(xùn)練數(shù)據(jù)集，選取1天的流量數(shù)據(jù)（容量約160MB的Tcp-dump文件）作為測試數(shù)據(jù)集。入侵檢測系統(tǒng)分別采用AC加密算法、WM加密算法和ExB加密算法作為模式匹配檢測引擎，測試這3種情況下平均模式匹配時間與模式數(shù)目的變化關(guān)系，對比情況如表所示。

由上表可知，模式數(shù)小于20個時ExB加密算法最優(yōu)，模式數(shù)在50～100時AC加密算法的匹配效率更好，當(dāng)模式數(shù)大于100時，WM加密算法性能更好。

隨著網(wǎng)絡(luò)應(yīng)用的發(fā)展和網(wǎng)絡(luò)帶寬的增加，必須提高網(wǎng)絡(luò)入侵檢測系統(tǒng)的處理性能。而目前的網(wǎng)絡(luò)入侵檢測系統(tǒng)多是基于特征匹配的系統(tǒng)，這類系統(tǒng)中的關(guān)鍵運(yùn)算是模式匹配，因此提高模式匹配加密算法的效率是提高這類系統(tǒng)檢測能力的關(guān)鍵。

admin

收藏 海報分享