薛 芳,林 麗

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

2(集美大學 計算機工程學院,廈門 361021)

1 引言

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

2 網(wǎng)絡入侵檢測

2.1 網(wǎng)絡入侵檢測的原理

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

圖1 入侵檢測系統(tǒng)的基本結構

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

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

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

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

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

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

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

3.1 單模式匹配算法的改進

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

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

圖2 模式正文匹配示例

本文改進算法的主要思想為:

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

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

3.2 多模式匹配算法的改進

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

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

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

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

3.2.2 算法描述

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

表1 BM與改進BMH 算法運行的總時間對比(單位:s)

?

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

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

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

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

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

3.3 算法實現(xiàn)

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

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

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

具體的流程為:

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

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

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

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

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

圖4 改進算法的匹配過程

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

4 算法的實驗和分析

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

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

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

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

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

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

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

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

5 結束語

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