模式匹配算法在入侵檢測(cè)中的應(yīng)用

預(yù)處理階段，模式樹(shù)的各個(gè)節(jié)點(diǎn)作為狀態(tài)，根節(jié)點(diǎn)作為初態(tài)，標(biāo)簽為模式的節(jié)點(diǎn)作為終態(tài)，利用轉(zhuǎn)向函數(shù)g和失效函數(shù)f作為轉(zhuǎn)移函數(shù)，將模式樹(shù)擴(kuò)展成一個(gè)樹(shù)型有限自動(dòng)機(jī)。
由模式樹(shù)擴(kuò)展所得的AC自動(dòng)機(jī)M是1個(gè)6元組：

M=(Q,∑，g，f，q0，F(xiàn))
其中：
(1)Q是有限狀態(tài)集(模式樹(shù)上的節(jié)點(diǎn))；
(2)∑是有窮的輸入字符表(數(shù)據(jù)包中可能出現(xiàn)的所有字符)；
(3)g是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：g(s，a)：從當(dāng)前狀態(tài)s開(kāi)始，沿著邊上標(biāo)簽為a的路徑所到的狀態(tài)。假如(u，v)邊上的標(biāo)簽為a，那么g(u，a)=v；如果根節(jié)點(diǎn)上出來(lái)的邊上的標(biāo)簽沒(méi)有a，則g(0，a)=O，即如果沒(méi)有匹配的字符出現(xiàn)，自動(dòng)機(jī)停留在初態(tài)；
(4)f(不匹配時(shí)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：
f(s)：當(dāng)w是L(s)最長(zhǎng)真后綴并且w是某個(gè)模式的前綴，那么f(s)就是以w為標(biāo)簽的那個(gè)節(jié)點(diǎn)；
(5)q0∈Q是初態(tài)(根節(jié)點(diǎn)，標(biāo)識(shí)符為0)；
(6)XXXXX是終態(tài)集(以模式為標(biāo)簽的節(jié)點(diǎn)集)。
這樣，在目標(biāo)串中查找模式的過(guò)程轉(zhuǎn)化成在模式樹(shù)中的查找過(guò)程。查找一個(gè)串T時(shí)從模式樹(shù)的根節(jié)點(diǎn)開(kāi)始，沿著以T中字符為標(biāo)簽的路徑往下走：若自動(dòng)機(jī)能夠抵達(dá)終態(tài)v，則說(shuō)明T中存在模式L(v)；否則不存在模式。
AC算法模式匹配的時(shí)間復(fù)雜度是0(n)，并且與模式集中模式串的個(gè)數(shù)和每個(gè)模式串的長(zhǎng)度無(wú)關(guān)。無(wú)論模式串P是否出現(xiàn)在目標(biāo)串T中，T中的每個(gè)字符都必須輸入狀態(tài)機(jī)中，所以無(wú)論是最好情況還是最壞情況，AC算法模式匹配的時(shí)間復(fù)雜度都是O(n)，包括預(yù)處理時(shí)間在內(nèi)，AC算法總時(shí)間復(fù)雜度是O(M+n)，其中M為所有模式串的長(zhǎng)度總和。
2．3 AC―BM算法
對(duì)多模式串的匹配而言，雖然AC算法比BM算法高效得多，但AC算法必須逐一查看目標(biāo)串的每個(gè)字符，即必須按順序輸入，不能實(shí)現(xiàn)跳躍，而B(niǎo)M算法則能夠利用“右滑”跳過(guò)目標(biāo)串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發(fā)式搜索技術(shù)應(yīng)用到AC算法中，則可大大提高多模式匹配算法的效率。許多人據(jù)此給出了各種改進(jìn)的算法。Commentz―Walter最先將BM算法和AC算法結(jié)合在一起給出了Com―mentz―Walter算法；Baeza―Yates結(jié)合BMP算法和AC算法也給出了多模式匹配改進(jìn)算法。
AC―BM算法是Jang―Jong在1993年結(jié)合Ac算法的有限自動(dòng)機(jī)和BM算法的連續(xù)跳躍思想提出來(lái)的新算法，利用劣勢(shì)移動(dòng)表和優(yōu)勢(shì)跳轉(zhuǎn)表來(lái)實(shí)現(xiàn)跳躍式地并行搜索，算法的時(shí)間復(fù)雜度為0(mn)。該算法的思想是：首先把要查找的多個(gè)模式構(gòu)成一個(gè)關(guān)鍵字樹(shù)，把相同的前綴作為樹(shù)的根節(jié)點(diǎn)。模式樹(shù)從目標(biāo)串的右端向左移動(dòng)，一旦模式樹(shù)確定在適當(dāng)?shù)奈恢?，字符比較從左向右開(kāi)始進(jìn)行。模式樹(shù)移動(dòng)時(shí)同時(shí)使用壞字符移動(dòng)和好前綴移動(dòng)。壞字符移動(dòng)的策略為：如果出現(xiàn)不匹配的情況，移動(dòng)模式樹(shù)，使得樹(shù)中其他模式的能與當(dāng)前目標(biāo)串正在比較的字符相匹配的那個(gè)字符移動(dòng)到與當(dāng)前目標(biāo)串正在比較的字符的相同位置上，如果在當(dāng)前的深度上，目標(biāo)字符沒(méi)有出現(xiàn)在任何模式中，則模式樹(shù)的偏移量為樹(shù)中最短模式的長(zhǎng)度。好前綴移動(dòng)的移動(dòng)策略為：將模式樹(shù)移動(dòng)到一個(gè)已被發(fā)現(xiàn)是另一個(gè)模式子串完全前綴的下一個(gè)位置，或者移動(dòng)到作為樹(shù)中另一個(gè)模式后綴能夠正確匹配目標(biāo)串的某個(gè)前綴的下一個(gè)位置。在模式樹(shù)的移動(dòng)過(guò)程中，必須確保模式樹(shù)的偏移量不能大于樹(shù)中最短的模式長(zhǎng)度。
2．4 AC，AC―BM算法改進(jìn)情況簡(jiǎn)介
文獻(xiàn)中盧汪節(jié)等人針對(duì)AC算法在構(gòu)造狀態(tài)機(jī)時(shí)空間冗余較大的情況，對(duì)狀態(tài)機(jī)各結(jié)點(diǎn)進(jìn)行壓縮存儲(chǔ)，使空間性能和時(shí)間性能都有提高；文獻(xiàn)中萬(wàn)國(guó)根等人對(duì)AC―BM算法的改進(jìn)借鑒了BMH算法的思想，取消了原算法的好前綴跳轉(zhuǎn)，優(yōu)化了壞字符跳轉(zhuǎn)，并修改了skip的計(jì)算方法，對(duì)大字符集的情況在平均情況下具有更優(yōu)的性能；文獻(xiàn)對(duì)AC―BM的改進(jìn)則是通過(guò)預(yù)處理思想實(shí)現(xiàn)的，在進(jìn)行AC―BM匹配之前首先掃描首和(或)尾字符，確定其位置，再到相應(yīng)位置進(jìn)行匹配，相當(dāng)于把目標(biāo)串按模式串首、尾字符分成數(shù)段，每段進(jìn)行比較，段間不含首字符的就直接跳過(guò)，不用比較，從而提高效率。

3 算法的實(shí)際執(zhí)行效率
上述這些算法究竟哪種算法具有最好的執(zhí)行效率呢?能不能僅通過(guò)時(shí)間復(fù)雜度來(lái)進(jìn)行衡量呢?時(shí)間復(fù)雜度僅是一個(gè)度量的范圍，表示受幾個(gè)參數(shù)的影響，并不代表一個(gè)具體的值，還需要在具體的環(huán)境中進(jìn)行測(cè)試。
文獻(xiàn)測(cè)試了包括上述算法在內(nèi)的多種單模式和多模式匹配算法的性能。測(cè)試平臺(tái)為：硬件：CPUIntel Xeon 3．46 GHz X 2，內(nèi)存2 GB DDR，硬盤200GB SCSI；軟件：windows 2003 Server，Intel IXASDK4．1。單模式匹配測(cè)試的規(guī)則集，使用隨機(jī)生成的8，16，32，48，128位具有代表意義的規(guī)則，可以對(duì)應(yīng)端口、IP地址，MAC地址、IPv6地址等，對(duì)多模式匹配測(cè)試采用Snort系統(tǒng)2．4．3規(guī)則集。
單模式匹配算法主要測(cè)試模式長(zhǎng)度與匹配時(shí)間、占用空間及預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果表明：各算法的測(cè)試指標(biāo)在規(guī)則長(zhǎng)度增長(zhǎng)的情況下均呈遞增趨勢(shì)，但BM算法的增長(zhǎng)速度最為緩慢，在不太在意存儲(chǔ)空間的情況下，BM可以作為優(yōu)先考慮的算法，同時(shí)對(duì)IPV6地址也更為合適。
多模式匹配算法的測(cè)試項(xiàng)目為規(guī)則數(shù)與單位匹配時(shí)間、占用儲(chǔ)存單元、單位預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果表明AC―BM算法在上述3項(xiàng)測(cè)試中取得了很好的性能平衡。這也是新版的Snort系統(tǒng)中選用AC―BM算法的重要原因。

4 入侵檢測(cè)系統(tǒng)中模式匹配算法的研究方向
常用的模式匹配算法所采用的思想主要有基于字符比較、基于自動(dòng)機(jī)、基于hash查找、基于位邏輯運(yùn)算和基于Tries樹(shù)型機(jī)構(gòu)搜索。鑒于目前網(wǎng)絡(luò)的實(shí)際狀況，多模式匹配算法更加適合于基于模式匹配的入侵檢測(cè)系統(tǒng)。這里認(rèn)為應(yīng)該從下面3個(gè)方面著手：一是繼續(xù)研究和改進(jìn)精確的模式匹配，將快速的單模式匹配算法和多模式匹配算法相結(jié)合，充分借鑒同類算法的先進(jìn)思想，如：引入Hash函數(shù)、引入自動(dòng)機(jī)、對(duì)字符串分塊等來(lái)不斷提高多模式匹配算法的性能；二是嘗試采用模糊匹配的策略，國(guó)外對(duì)此已經(jīng)開(kāi)始進(jìn)行相應(yīng)的研究；三是對(duì)網(wǎng)絡(luò)數(shù)據(jù)包和入侵特征進(jìn)行研究，總結(jié)出這兩類字符串特點(diǎn)，有針對(duì)性地對(duì)這兩類字符串的匹配問(wèn)題進(jìn)行研究。

5 結(jié) 語(yǔ)
網(wǎng)絡(luò)帶寬的不斷增加、日益嚴(yán)重的網(wǎng)絡(luò)安全狀況要求必須盡快提高網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能。雖然入侵檢測(cè)系統(tǒng)可以采用很多技術(shù)，并且這些技術(shù)也在不斷的研究和發(fā)展中，但是目前主流的實(shí)用的入侵檢測(cè)技術(shù)仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測(cè)系統(tǒng)的一個(gè)關(guān)鍵所在。在此對(duì)已有的經(jīng)典模式匹配算法進(jìn)行了系統(tǒng)綜述，并對(duì)入侵檢測(cè)系統(tǒng)中模式匹配算法的未來(lái)研究方向給出了觀點(diǎn)。