計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的多模式匹配算法①

薛 芳,林 麗

1(集美大學(xué) 信息化中心,廈門 361021)

2(集美大學(xué) 計(jì)算機(jī)工程學(xué)院,廈門 361021)

1 引言

隨著現(xiàn)代互聯(lián)網(wǎng)的不斷發(fā)展,網(wǎng)絡(luò)規(guī)模持續(xù)擴(kuò)大,網(wǎng)絡(luò)的使用也開始發(fā)展為全球化的方向.在此背景下,網(wǎng)絡(luò)入侵攻擊事件頻發(fā).傳統(tǒng)的防火墻技術(shù)無法對(duì)網(wǎng)絡(luò)安全性進(jìn)行保證,所以需要實(shí)現(xiàn)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)(IDS)的設(shè)計(jì).網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)指的是主動(dòng)積極的安全防護(hù)技術(shù),其逐漸發(fā)展為網(wǎng)絡(luò)安全領(lǐng)域研究的重點(diǎn)內(nèi)容[1].在網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)工作過程中,大部分為被動(dòng)的監(jiān)聽,利用關(guān)鍵網(wǎng)段得出網(wǎng)絡(luò)傳輸數(shù)據(jù)包,通過多種檢測(cè)分析的方式對(duì)數(shù)據(jù)包進(jìn)行分析,從而尋找入侵的痕跡.在網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)檢測(cè)的時(shí)候,并不會(huì)對(duì)網(wǎng)絡(luò)性能造成影響,還能夠提高網(wǎng)絡(luò)攻擊事件定位的效果.現(xiàn)代分析網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的主要方法為基于特征、異常的檢測(cè),由于異常檢測(cè)過程中的學(xué)習(xí)時(shí)間比較長,所以一般利用基于模式匹配特征檢測(cè)[2].以此,本文就對(duì)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的多模式匹配算法進(jìn)行全面分析.

2 網(wǎng)絡(luò)入侵檢測(cè)

2.1 網(wǎng)絡(luò)入侵檢測(cè)的原理

因?yàn)閭鹘y(tǒng)的安全策略無法有效滿足安全的實(shí)際需求,從而產(chǎn)生了入侵檢測(cè)系統(tǒng),并且在發(fā)展過程中逐漸成為動(dòng)態(tài)安全技術(shù)的代表,使計(jì)算機(jī)安全領(lǐng)域的發(fā)展與研究有所促進(jìn).入侵檢測(cè)系統(tǒng)為計(jì)算機(jī)系統(tǒng)與網(wǎng)絡(luò)中的安全事件檢測(cè)的技術(shù),主要包括數(shù)據(jù)采集、分析與結(jié)果處理3個(gè)功能.圖1為入侵檢測(cè)系統(tǒng)基本的結(jié)構(gòu).

圖1 入侵檢測(cè)系統(tǒng)的基本結(jié)構(gòu)

在網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中,數(shù)據(jù)分析模塊是核心模塊,由于模式匹配原理簡(jiǎn)單、可擴(kuò)展性好,現(xiàn)代網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)利用廣泛采用模式匹配的方法進(jìn)行數(shù)據(jù)分析.隨著科技的日新月異,網(wǎng)絡(luò)的規(guī)模也不斷擴(kuò)大,網(wǎng)絡(luò)帶寬量也逐漸增加,要求網(wǎng)絡(luò)入侵檢測(cè)性能處理的效率得到改進(jìn),否則會(huì)導(dǎo)致出現(xiàn)入侵漏報(bào)的情況,也就無法充分發(fā)揮網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的優(yōu)勢(shì).

模式匹配算法應(yīng)用于入侵檢測(cè)領(lǐng)域,是將攻擊模式庫中的攻擊模式與待檢測(cè)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行匹配,若匹配成功則系統(tǒng)判斷出現(xiàn)了網(wǎng)絡(luò)攻擊.目前的模式匹配算法分為單模式和多模式匹配,其中典型單模式匹配算法包括KMP 算法和BM 算法,多模式匹配算法包括AC 算法和AC-BM 算法[3].

2.2 傳統(tǒng)網(wǎng)絡(luò)入侵檢測(cè)算法

在1977年,Boyer和Moore 提出了BM 算法[4],促進(jìn)了模式匹配算法的發(fā)展.此算法在進(jìn)行匹配時(shí)包含兩個(gè)并行算法,壞字符和好后綴算法,目的是讓模式串每次向右移動(dòng)盡可能大的距離.

多模式匹配即在一個(gè)文本串中同時(shí)查找多個(gè)模式串,較之單模式匹配更易應(yīng)對(duì)不斷擴(kuò)大的入侵特征庫,因此現(xiàn)今主流的IDS 使用的基本都是多模式匹配算法.AC (Aho-Corasick)算法作為最經(jīng)典的多模式匹配算法被許多IDS 采用,該算法包含預(yù)處理和匹配兩個(gè)階段,將待匹配的入侵特征模式串轉(zhuǎn)換為樹狀有限狀態(tài)自動(dòng)機(jī),然后進(jìn)行掃描匹配.

BM 算法是一種性能較好的模式匹配算法,該算法在不匹配的情況下可以產(chǎn)生跳躍,從而減少匹配次數(shù),但無法滿足日益復(fù)雜的網(wǎng)絡(luò)入侵類型;AC 算法記錄的自動(dòng)機(jī)耗費(fèi)了大量的存儲(chǔ)空間.此外,AC與BM 網(wǎng)絡(luò)入侵檢測(cè)算法具有較大的漏配量和無效配的情況,降低系統(tǒng)的檢測(cè)精準(zhǔn)率與匹配速度,所以就要對(duì)網(wǎng)絡(luò)入侵檢測(cè)算法進(jìn)行改進(jìn)[5].

3 檢測(cè)系統(tǒng)模式匹配算法優(yōu)化

3.1 單模式匹配算法的改進(jìn)

1980年,Horspool 提出了改進(jìn)的BM 算法[6],也就是BMH 算法.簡(jiǎn)化了BM 算法,執(zhí)行方便,效率也有所提高.有n長度的文本字符串T與m長度的模式字符串P.在改進(jìn)BM 算法過程中,不匹配過程中的正文與模式移動(dòng)距離有所擴(kuò)大.它不再像BM 算法一樣關(guān)注失配的字符,它的關(guān)注的焦點(diǎn)在于匹配文本每一次匹配失敗的最后一個(gè)字符X,根據(jù)這個(gè)字符X是否在模板出現(xiàn)過來決定跳躍的步數(shù),否則跳躍模板的長度.如果字符X不在模式P中,則跳躍的步數(shù)為模式P的長度,字符X在模式P中,跳躍的步數(shù)為字符X距離離尾部最近的字符X的距離(不包括最后一個(gè)字符).

利用dist函數(shù)的分析表示,dist[T[j]]≤m.以此看出來,模式在所設(shè)置的長度中最大距離的對(duì)右移動(dòng).模式正文匹配的結(jié)構(gòu)詳見圖2,在T[j]≠P[j]時(shí),此模式通過BM 算法在dist[T[j]]個(gè)位置中移動(dòng).利用正文的i+dist[T[j]]位置實(shí)現(xiàn)重新匹配檢查,忽視T[i+v+1]模式串的檢查.如果模式中沒有T[i+v+1],那么使模式P對(duì)右移動(dòng)距離為m+1,不對(duì)T[i+v+1]進(jìn)行匹配檢查[7].

圖2 模式正文匹配示例

本文改進(jìn)算法的主要思想為:

首先,假設(shè)變量k為模式第一次與最后一次的匹配字符,將BM 算法作為基礎(chǔ),在出現(xiàn)不匹配的時(shí)候,能夠?qū)崿F(xiàn)T[k+1]的判斷.如果出現(xiàn)T[k+1],那么模式移動(dòng)距離假設(shè)為L,規(guī)定L=max{dist[T[k+1]],dist[T[j]]}+1,其中的變量i和前文相同,詞表達(dá)式的含義就是對(duì)T[k+1]和dist[T[j]]的大小對(duì)比,實(shí)現(xiàn)正文與模式最大移動(dòng)距離的進(jìn)行接下來的匹配.通過L的賦值表示,在對(duì)是否存在T[k+1]模式判斷過程中,能夠提高下一次匹配的移動(dòng)模式距離.以此匹配移動(dòng)模式,假如完全匹配,表示已經(jīng)成功地進(jìn)行匹配.如果沒有完全匹配,移動(dòng)模式就不發(fā)生改變,直到正文結(jié)束[8].

全面考慮從右到左的正文與模式匹配,模式右邊的字符匹配大于左邊.假如具有長模式的情況,和左邊不匹配時(shí)候進(jìn)行對(duì)比,需要的時(shí)間成本量比較大.為了方便算法的實(shí)現(xiàn),在本文中實(shí)現(xiàn)針對(duì)性方案的設(shè)計(jì).在算法改進(jìn)之前對(duì)比正文位置字符與模式首字符,如果不匹配直接判斷T[k+1],繼續(xù)下個(gè)匹配過程.之后根據(jù)以上改進(jìn)算法實(shí)現(xiàn)匹配對(duì)比,降低不必要匹配過程,從而節(jié)約匹配時(shí)間[9].

3.2 多模式匹配算法的改進(jìn)

網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)能夠深入檢測(cè)執(zhí)行數(shù)據(jù)包,并且全面掃描負(fù)載或者已經(jīng)定義規(guī)則集的匹配模式串,檢測(cè)是否具備入侵檢測(cè)事件[10].

3.2.1 分析算法的后綴函數(shù)

在BM 算法中,在匹配過程中比較了一個(gè)模式的長度,而且存在之前匹配的結(jié)果,在后面的匹配過程中被“遺忘”的情況,模式串長度越長效率越低.本文使改進(jìn)的BMH 算法和傳統(tǒng)BM 算法實(shí)現(xiàn)實(shí)驗(yàn)對(duì)比,此實(shí)驗(yàn)主要包括的測(cè)試指標(biāo)為BM與改進(jìn)BMH 算法字符數(shù)量、運(yùn)行的時(shí)間和BM 算法字符比較數(shù)量和使用后綴規(guī)則數(shù)量.

因?yàn)槿肭謾z測(cè)實(shí)現(xiàn)自檢,其模式串的長度設(shè)置為20–30 字符.本文通過隨機(jī)的選擇開展實(shí)驗(yàn),BM與改進(jìn)BMH 算法的運(yùn)行時(shí)間比詳見表1.通過表可以看出來,兩種算法的總字符數(shù)量是相同的,但是基于時(shí)間復(fù)雜度中,改進(jìn)BMH的性能更加良好.

3.2.2 算法描述

基于傳統(tǒng)BM 算法,充分考慮文本串中的字符T[j]并不會(huì)出現(xiàn)在模式串中,如果其下個(gè)字符T[j+1]和模式串中的首字符P[1]相同,也就是T[j+1]=P[1],以此創(chuàng)建滑動(dòng)距離函數(shù)2,簡(jiǎn)化判斷的過程,使比較次數(shù)降低,提高匹配的效率.在分析傳統(tǒng)BM 模式匹配算法過程中,模式串中出現(xiàn)重復(fù)字符的時(shí)候會(huì)導(dǎo)致指針回溯的問題,那么在本文函數(shù)中使用“取子串”的方法能夠避免出現(xiàn)指針回溯的問題[11].算法流程如算法1.

表1 BM與改進(jìn)BMH 算法運(yùn)行的總時(shí)間對(duì)比(單位:s)

?

BMH 算法在改進(jìn)過程中的重點(diǎn)為定義給定模式P=P1P2···Pm從字母到正整數(shù)的映射:

Slide:C→{1,2,…,m}

其中,c∈∑(假設(shè)∑指的是所有英文字母集合)

Slide1 指的是滑動(dòng)距離函數(shù)設(shè)置為1,其給出正文中的任意字符c在模式中的距離,具體定義為:

Slide2 指的是滑動(dòng)距離函數(shù)2,其能夠給出正文中會(huì)出現(xiàn)的任意字符位置,具體定義為:

3.3 算法實(shí)現(xiàn)

預(yù)處理階段在讀入規(guī)則文件的時(shí)候,使模式組劃分成為多字節(jié)模式組與單字節(jié)模式組,將兩者添加到相應(yīng)模式組中.針對(duì)單字節(jié)模式串組,預(yù)處理階段不進(jìn)行處理.改進(jìn)算法以多字節(jié)模式串組計(jì)算前綴和后綴索引、跳躍距離Shift 表,計(jì)算的方法為:得出最短模式長度m,使其成為匹配窗口大小.取每個(gè)模式最后B個(gè)字符對(duì)Hash 值計(jì)算,B個(gè)字符指的是一個(gè)塊字符.Shift 表中將字符串中全部塊字符在T時(shí)的移動(dòng)距離進(jìn)行計(jì)算.針對(duì)每個(gè)出現(xiàn)的多字節(jié)模式串中字符塊,使二維位圖EXIST_P中的位置標(biāo)記成為1,其他標(biāo)記成為0.以此,在匹配的時(shí)候如果查找文本字符塊處于位圖EXIST_P標(biāo)記成為0,那么此字符串并不會(huì)在多字節(jié)模式串組任何模式串中出現(xiàn).二維圖計(jì)算方法為:

以改進(jìn)算法思想,圖3為改進(jìn)算法的實(shí)現(xiàn)流程.為了能夠有效地簡(jiǎn)化流程,數(shù)組下標(biāo)為字符的位置[13].

圖3 改進(jìn)算法的實(shí)現(xiàn)流程

具體的流程為:

1)對(duì)K≤n(n為待檢測(cè)字符串T的長度)是否成立判斷,如果kn,匹配的過程失敗,程序就結(jié)束.

2)從左到右匹配模式和正文,并且對(duì)比,如果模式字符串和正文字符串進(jìn)行匹配,對(duì)匹配的位置進(jìn)行記錄,以此說明能夠成功匹配,結(jié)束程序.假如某位置的字符串出現(xiàn)不匹配的情況,就進(jìn)入到步驟3).

3)對(duì)目前的匹配操作進(jìn)行判斷,模式中的正文和模式最后一位對(duì)應(yīng)位置是否有下位字符,以判斷結(jié)果變量k值計(jì)算,之后轉(zhuǎn)到步驟1)[14].

處理階段時(shí)間復(fù)雜度為O(m+σ),其中σ為x與已匹配部分在P中的位置,搜索階段最壞情況下時(shí)間復(fù)雜度為O(mn),模式字符串的長度大小將影響到時(shí)間復(fù)雜度,一般文本字符的平均比較數(shù)在1σ和2/(σ+1)之間.

圖4為改進(jìn)算法的匹配過程,算法以二維圖判斷某字符串是否在模式串中出現(xiàn),首先讀入字符串“st”,EXIST_P(st)為0,使窗口向后移動(dòng)一位.EXIST_P(tr)值為0,繼續(xù)使窗口向右移動(dòng)一位.EXIST_P(rc)值為1,此處會(huì)出現(xiàn)匹配,通過本文算法實(shí)現(xiàn)匹配,查找Shift表,后續(xù)文本串根據(jù)同樣方法進(jìn)行匹配.

圖4 改進(jìn)算法的匹配過程

通過上述匹配可以看出來,使用原本算法匹配的時(shí)候,要計(jì)算9 次Hash 值并且查找Shift 表實(shí)現(xiàn)跳躍.改進(jìn)算法能夠以位圖判斷此字符串是否處于模式串中.在以上匹配過程中一共計(jì)算6 次Hash 值,并且查找Shift 表實(shí)現(xiàn)跳躍.

4 算法的實(shí)驗(yàn)和分析

為了對(duì)今后算法性能進(jìn)行校驗(yàn),本文用改進(jìn)后算法和傳統(tǒng)BM 算法實(shí)現(xiàn)實(shí)驗(yàn)對(duì)比.在Win 7 環(huán)境中實(shí)驗(yàn),系統(tǒng)配置2.66 GHz Intel CPU.實(shí)驗(yàn)過程中使用官網(wǎng)中的模式串,以Snort 匹配過程,使所有規(guī)則文件規(guī)則字符串作為模式組,在實(shí)驗(yàn)過程中依次使用此模式組對(duì)改進(jìn)算法實(shí)現(xiàn)校驗(yàn).在查找文本通過MIT Lincoln實(shí)驗(yàn)室中的DARPA99 數(shù)據(jù)集的數(shù)據(jù)構(gòu)成,通過DARPA99 測(cè)試數(shù)據(jù)集中選擇4 MB 測(cè)試數(shù)據(jù).圖5為在不同最小模式中的算法性能對(duì)比.通過圖5可知,在模式串組中具備單字節(jié)模式串與兩個(gè)字節(jié)模式串時(shí),改進(jìn)算法性能有所提高.

圖5 不同最小模式中的算法性能對(duì)比

圖6為不同模式串集的算法性能,通過圖6可知,在模式串集模式串?dāng)?shù)量不斷增加的過程中,改進(jìn)算法與原算法的性能相同.但是在模式串?dāng)?shù)量比較少的時(shí)候,改進(jìn)算法的匹配運(yùn)行時(shí)間比原算法的匹配運(yùn)行時(shí)間要短.在入侵檢測(cè)系統(tǒng)中,匹配規(guī)模集中規(guī)則數(shù)量不超過400 條,改進(jìn)算法的應(yīng)用價(jià)值良好.增加到1200 條時(shí),兩種算法應(yīng)用價(jià)值相當(dāng).在2000 條時(shí),改進(jìn)算法使用價(jià)值良好.實(shí)際應(yīng)用情況中,檢測(cè)條目越多,將嚴(yán)重影響網(wǎng)絡(luò)訪問時(shí)延,導(dǎo)致用戶上網(wǎng)體驗(yàn)差;檢測(cè)條目越少,匹配到的威脅少,對(duì)網(wǎng)絡(luò)安全危害增大,一般檢測(cè)條目約在500–800 之間.

圖6 不同模式串集的算法性能

本文也對(duì)改進(jìn)算法在不同數(shù)據(jù)包時(shí)的情況,模式串組使用Snort 規(guī)則文件ftp.riles.通過圖7表示,數(shù)據(jù)

包越大,改進(jìn)算法所消耗時(shí)間短與原本算法,能夠提高其性能.本文改進(jìn)算法的測(cè)試平均查詢時(shí)間為0.38 s,傳統(tǒng)算法需要2.16 s,以此表示能夠?qū)崿F(xiàn)快速查詢,滿足用戶的實(shí)際使用需求.

圖7 不同數(shù)據(jù)包大小的算法性能

通過實(shí)驗(yàn)結(jié)果表示,改進(jìn)之后的BM 算法性能提高,匹配效率比傳統(tǒng)算法要高.通過本文中的改進(jìn)算法能夠使入侵檢測(cè)系統(tǒng)性能得到提高,實(shí)用價(jià)值良好.

5 結(jié)束語

網(wǎng)絡(luò)帶寬在網(wǎng)絡(luò)技術(shù)持續(xù)發(fā)展過程中不斷增加,入侵監(jiān)測(cè)系統(tǒng)處理的性能也要相應(yīng)不斷得到提高,使得大流量網(wǎng)絡(luò)環(huán)境的需求得到滿足.本文對(duì)模式匹配算法進(jìn)行全面的研究,并且對(duì)傳統(tǒng)模式匹配算法進(jìn)行改進(jìn).通過實(shí)例測(cè)試可以看出來,改進(jìn)的多模式匹配算法能夠有效滿足網(wǎng)絡(luò)使用過程中的需求,并且提高系統(tǒng)檢測(cè)效率.另外,改進(jìn)算法還能夠降低冗余移動(dòng),使匹配速度與查找速率得到提高,對(duì)入侵檢測(cè)系統(tǒng)的性能進(jìn)行改進(jìn).