模式匹配算法在入侵檢測中的應(yīng)用
預(yù)處理階段,模式樹的各個節(jié)點作為狀態(tài),根節(jié)點作為初態(tài),標(biāo)簽為模式的節(jié)點作為終態(tài),利用轉(zhuǎn)向函數(shù)g和失效函數(shù)f作為轉(zhuǎn)移函數(shù),將模式樹擴(kuò)展成一個樹型有限自動機(jī)。
由模式樹擴(kuò)展所得的AC自動機(jī)M是1個6元組:
M=(Q,∑,g,f,q0,F(xiàn))
其中:
(1)Q是有限狀態(tài)集(模式樹上的節(jié)點);
(2)∑是有窮的輸入字符表(數(shù)據(jù)包中可能出現(xiàn)的所有字符);
(3)g是轉(zhuǎn)移函數(shù),該函數(shù)定義如下:g(s,a):從當(dāng)前狀態(tài)s開始,沿著邊上標(biāo)簽為a的路徑所到的狀態(tài)。假如(u,v)邊上的標(biāo)簽為a,那么g(u,a)=v;如果根節(jié)點上出來的邊上的標(biāo)簽沒有a,則g(0,a)=O,即如果沒有匹配的字符出現(xiàn),自動機(jī)停留在初態(tài);
(4)f(不匹配時自動機(jī)的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù),該函數(shù)定義如下:
f(s):當(dāng)w是L(s)最長真后綴并且w是某個模式的前綴,那么f(s)就是以w為標(biāo)簽的那個節(jié)點;
(5)q0∈Q是初態(tài)(根節(jié)點,標(biāo)識符為0);
(6)XXXXX是終態(tài)集(以模式為標(biāo)簽的節(jié)點集)。
這樣,在目標(biāo)串中查找模式的過程轉(zhuǎn)化成在模式樹中的查找過程。查找一個串T時從模式樹的根節(jié)點開始,沿著以T中字符為標(biāo)簽的路徑往下走:若自動機(jī)能夠抵達(dá)終態(tài)v,則說明T中存在模式L(v);否則不存在模式。
AC算法模式匹配的時間復(fù)雜度是0(n),并且與模式集中模式串的個數(shù)和每個模式串的長度無關(guān)。無論模式串P是否出現(xiàn)在目標(biāo)串T中,T中的每個字符都必須輸入狀態(tài)機(jī)中,所以無論是最好情況還是最壞情況,AC算法模式匹配的時間復(fù)雜度都是O(n),包括預(yù)處理時間在內(nèi),AC算法總時間復(fù)雜度是O(M+n),其中M為所有模式串的長度總和。
2.3 AC―BM算法
對多模式串的匹配而言,雖然AC算法比BM算法高效得多,但AC算法必須逐一查看目標(biāo)串的每個字符,即必須按順序輸入,不能實現(xiàn)跳躍,而BM算法則能夠利用“右滑”跳過目標(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算法的有限自動機(jī)和BM算法的連續(xù)跳躍思想提出來的新算法,利用劣勢移動表和優(yōu)勢跳轉(zhuǎn)表來實現(xiàn)跳躍式地并行搜索,算法的時間復(fù)雜度為0(mn)。該算法的思想是:首先把要查找的多個模式構(gòu)成一個關(guān)鍵字樹,把相同的前綴作為樹的根節(jié)點。模式樹從目標(biāo)串的右端向左移動,一旦模式樹確定在適當(dāng)?shù)奈恢茫址容^從左向右開始進(jìn)行。模式樹移動時同時使用壞字符移動和好前綴移動。壞字符移動的策略為:如果出現(xiàn)不匹配的情況,移動模式樹,使得樹中其他模式的能與當(dāng)前目標(biāo)串正在比較的字符相匹配的那個字符移動到與當(dāng)前目標(biāo)串正在比較的字符的相同位置上,如果在當(dāng)前的深度上,目標(biāo)字符沒有出現(xiàn)在任何模式中,則模式樹的偏移量為樹中最短模式的長度。好前綴移動的移動策略為:將模式樹移動到一個已被發(fā)現(xiàn)是另一個模式子串完全前綴的下一個位置,或者移動到作為樹中另一個模式后綴能夠正確匹配目標(biāo)串的某個前綴的下一個位置。在模式樹的移動過程中,必須確保模式樹的偏移量不能大于樹中最短的模式長度。
2.4 AC,AC―BM算法改進(jìn)情況簡介
文獻(xiàn)中盧汪節(jié)等人針對AC算法在構(gòu)造狀態(tài)機(jī)時空間冗余較大的情況,對狀態(tài)機(jī)各結(jié)點進(jìn)行壓縮存儲,使空間性能和時間性能都有提高;文獻(xiàn)中萬國根等人對AC―BM算法的改進(jìn)借鑒了BMH算法的思想,取消了原算法的好前綴跳轉(zhuǎn),優(yōu)化了壞字符跳轉(zhuǎn),并修改了skip的計算方法,對大字符集的情況在平均情況下具有更優(yōu)的性能;文獻(xiàn)對AC―BM的改進(jìn)則是通過預(yù)處理思想實現(xiàn)的,在進(jìn)行AC―BM匹配之前首先掃描首和(或)尾字符,確定其位置,再到相應(yīng)位置進(jìn)行匹配,相當(dāng)于把目標(biāo)串按模式串首、尾字符分成數(shù)段,每段進(jìn)行比較,段間不含首字符的就直接跳過,不用比較,從而提高效率。
3 算法的實際執(zhí)行效率
上述這些算法究竟哪種算法具有最好的執(zhí)行效率呢?能不能僅通過時間復(fù)雜度來進(jìn)行衡量呢?時間復(fù)雜度僅是一個度量的范圍,表示受幾個參數(shù)的影響,并不代表一個具體的值,還需要在具體的環(huán)境中進(jìn)行測試。
文獻(xiàn)測試了包括上述算法在內(nèi)的多種單模式和多模式匹配算法的性能。測試平臺為:硬件:CPUIntel Xeon 3.46 GHz X 2,內(nèi)存2 GB DDR,硬盤200GB SCSI;軟件:windows 2003 Server,Intel IXASDK4.1。單模式匹配測試的規(guī)則集,使用隨機(jī)生成的8,16,32,48,128位具有代表意義的規(guī)則,可以對應(yīng)端口、IP地址,MAC地址、IPv6地址等,對多模式匹配測試采用Snort系統(tǒng)2.4.3規(guī)則集。
單模式匹配算法主要測試模式長度與匹配時間、占用空間及預(yù)處理時間的變化關(guān)系。測試結(jié)果表明:各算法的測試指標(biāo)在規(guī)則長度增長的情況下均呈遞增趨勢,但BM算法的增長速度最為緩慢,在不太在意存儲空間的情況下,BM可以作為優(yōu)先考慮的算法,同時對IPV6地址也更為合適。
多模式匹配算法的測試項目為規(guī)則數(shù)與單位匹配時間、占用儲存單元、單位預(yù)處理時間的變化關(guān)系。測試結(jié)果表明AC―BM算法在上述3項測試中取得了很好的性能平衡。這也是新版的Snort系統(tǒng)中選用AC―BM算法的重要原因。
4 入侵檢測系統(tǒng)中模式匹配算法的研究方向
常用的模式匹配算法所采用的思想主要有基于字符比較、基于自動機(jī)、基于hash查找、基于位邏輯運(yùn)算和基于Tries樹型機(jī)構(gòu)搜索。鑒于目前網(wǎng)絡(luò)的實際狀況,多模式匹配算法更加適合于基于模式匹配的入侵檢測系統(tǒng)。這里認(rèn)為應(yīng)該從下面3個方面著手:一是繼續(xù)研究和改進(jìn)精確的模式匹配,將快速的單模式匹配算法和多模式匹配算法相結(jié)合,充分借鑒同類算法的先進(jìn)思想,如:引入Hash函數(shù)、引入自動機(jī)、對字符串分塊等來不斷提高多模式匹配算法的性能;二是嘗試采用模糊匹配的策略,國外對此已經(jīng)開始進(jìn)行相應(yīng)的研究;三是對網(wǎng)絡(luò)數(shù)據(jù)包和入侵特征進(jìn)行研究,總結(jié)出這兩類字符串特點,有針對性地對這兩類字符串的匹配問題進(jìn)行研究。
5 結(jié) 語
網(wǎng)絡(luò)帶寬的不斷增加、日益嚴(yán)重的網(wǎng)絡(luò)安全狀況要求必須盡快提高網(wǎng)絡(luò)入侵檢測系統(tǒng)的性能。雖然入侵檢測系統(tǒng)可以采用很多技術(shù),并且這些技術(shù)也在不斷的研究和發(fā)展中,但是目前主流的實用的入侵檢測技術(shù)仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測系統(tǒng)的一個關(guān)鍵所在。在此對已有的經(jīng)典模式匹配算法進(jìn)行了系統(tǒng)綜述,并對入侵檢測系統(tǒng)中模式匹配算法的未來研究方向給出了觀點。
評論