網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中的模式匹配算法設(shè)計(jì)優(yōu)化

陳卓民

（陜西警官職業(yè)學(xué)院教務(wù)處陜西西安710021）

在現(xiàn)代互聯(lián)網(wǎng)不斷發(fā)展的過(guò)程中，網(wǎng)絡(luò)規(guī)模在不斷的擴(kuò)大，網(wǎng)絡(luò)應(yīng)用也越來(lái)越朝著全球化的方向發(fā)展。在此背景下，網(wǎng)絡(luò)入侵攻擊事件的發(fā)生機(jī)率也在不斷的增加。傳統(tǒng)防火墻技術(shù)已經(jīng)無(wú)法有效保證網(wǎng)絡(luò)安全，網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)屬于積極主動(dòng)安全防護(hù)技術(shù)，其目前已經(jīng)成為網(wǎng)絡(luò)安全領(lǐng)域中的研究熱點(diǎn)內(nèi)容[1]。網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)一般使用被動(dòng)監(jiān)聽(tīng)方式實(shí)現(xiàn)，通過(guò)關(guān)鍵網(wǎng)段實(shí)現(xiàn)網(wǎng)絡(luò)傳輸數(shù)據(jù)包的獲取，并且通過(guò)多種檢測(cè)分析方式對(duì)數(shù)據(jù)包進(jìn)行分析，從而尋找入侵的證據(jù)。網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)能夠基于不對(duì)網(wǎng)絡(luò)性能造成影響然后實(shí)現(xiàn)網(wǎng)絡(luò)檢測(cè)，從而尋找網(wǎng)絡(luò)攻擊事件[2]。現(xiàn)代網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)檢測(cè)分析的方法主要包括兩種，分別為異常檢測(cè)和基于特征檢測(cè)。因?yàn)楫惓z測(cè)需要學(xué)習(xí)時(shí)間，并且具有較高的檢測(cè)誤報(bào)率，無(wú)法滿足大流量網(wǎng)絡(luò)實(shí)時(shí)檢測(cè)需求。所以，目前都使用基于模式匹配特征檢測(cè)。現(xiàn)代網(wǎng)絡(luò)流量在不斷的提高，并且入侵特征庫(kù)在逐漸更新，對(duì)于基于特征匹配網(wǎng)絡(luò)入侵實(shí)時(shí)檢測(cè)性能提出了一定的挑戰(zhàn)[3]。基于此，文中對(duì)網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)模式匹配算法的設(shè)計(jì)進(jìn)行全面的分析。

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

1.1 網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)

網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)屬于標(biāo)識(shí)并且隔離入侵安全的技術(shù)，其也是防火墻以外的第二道防線，圖1為網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的結(jié)構(gòu)。

圖1 網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的結(jié)構(gòu)

網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的主要特點(diǎn)就是經(jīng)濟(jì)性、安全性、時(shí)效性、可擴(kuò)展性，其主要包括事件產(chǎn)生器、事件分析器、響應(yīng)單元和事件發(fā)生庫(kù)。在實(shí)際使用過(guò)程中，入侵檢測(cè)系統(tǒng)主要包括存儲(chǔ)系統(tǒng)、分析系統(tǒng)傳感器及控制臺(tái)，其中存儲(chǔ)系統(tǒng)的主要目的就是實(shí)現(xiàn)系統(tǒng)運(yùn)行數(shù)據(jù)及入侵攻擊過(guò)程進(jìn)行存儲(chǔ)，其中控制臺(tái)的目的就是集中管理[4]。

1.2 網(wǎng)絡(luò)入侵檢測(cè)算法

網(wǎng)絡(luò)入侵檢測(cè)算法對(duì)檢測(cè)精準(zhǔn)性及效率具有直接的影響，現(xiàn)代網(wǎng)絡(luò)入侵檢測(cè)算法主要包括模式匹配、專家系統(tǒng)、狀態(tài)遷移分析、統(tǒng)計(jì)、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)挖掘及免疫學(xué)[5]。

每個(gè)基于模式匹配的入侵檢測(cè)都要求具有已經(jīng)設(shè)置的入侵模式，那么就需要實(shí)現(xiàn)入侵行為描述的方法目前入侵檢測(cè)系統(tǒng)描述方法并不同，不同產(chǎn)商的定義描述方法不同，那么用戶只能夠根據(jù)開(kāi)發(fā)商對(duì)自身入侵檢測(cè)模式庫(kù)進(jìn)行升級(jí)[6]。圖2為基于模式匹配入侵檢測(cè)系統(tǒng)的結(jié)構(gòu)。

圖2 基于模式匹配入侵檢測(cè)系統(tǒng)的結(jié)構(gòu)

目前模式匹配檢測(cè)算法在執(zhí)行任務(wù)的過(guò)程中都是通過(guò)fpEvalPacket實(shí)現(xiàn)的，在函數(shù)模塊實(shí)現(xiàn)預(yù)處理之后，對(duì)Detect函數(shù)進(jìn)行調(diào)用，之后實(shí)現(xiàn)數(shù)據(jù)包內(nèi)容特征的規(guī)則匹配。如果捕捉的數(shù)據(jù)包協(xié)議為Tcp，那么就實(shí)現(xiàn)fpEvalHeaderTcp函數(shù)的調(diào)用。

2 傳統(tǒng)模式匹配算法

傳統(tǒng)模式匹配算法的概念為：

假設(shè)n長(zhǎng)度文本是T[1…n]，m長(zhǎng)度模式P屬于P[1…m]，模式的集合屬于{Pi}，模式集合的總長(zhǎng)度屬于M。單模式匹配指的是文本T在對(duì)P的尋找；多模式匹配指的是文本T在對(duì)多個(gè)模式進(jìn)行尋找。在入侵特征不斷增加的過(guò)程中，入侵檢測(cè)模式匹配算法也逐漸從單模式轉(zhuǎn)變成為多模式[7]。

傳統(tǒng)模式匹配算法主要包括以下：

其一，AC算法。此算法使用最為廣泛，其屬于多模式匹配經(jīng)典算法，目前其主要包括兩個(gè)基本的研究方向，分別為基于自動(dòng)機(jī)和基于BM跳躍及過(guò)濾。其使用有限狀態(tài)機(jī)思想，在實(shí)現(xiàn)模式匹配之前要實(shí)現(xiàn)所有模式預(yù)處理，從而實(shí)現(xiàn)有限狀態(tài)機(jī)生成，之后從其中尋找匹配。AC函數(shù)預(yù)處理的過(guò)程主要包括3個(gè)函數(shù)，分別為狀態(tài)轉(zhuǎn)移函數(shù)goto、失效函數(shù)fail、輸出函數(shù)output，圖3為AC算法轉(zhuǎn)移函數(shù)的轉(zhuǎn)換過(guò)程[8]。

圖3 AC算法轉(zhuǎn)移函數(shù)的轉(zhuǎn)換過(guò)程

基于失效函數(shù)結(jié)構(gòu)過(guò)程，其示意圖詳見(jiàn)圖4虛線部分。

圖4 AC算法失效函數(shù)的示意圖

圖5為AC算法中的輸出函數(shù)示意圖，在預(yù)處理以上3個(gè)函數(shù)之后，AC算法以轉(zhuǎn)移函數(shù)及實(shí)效函數(shù)創(chuàng)建類似確定狀態(tài)自動(dòng)機(jī)，此類能夠?qū)D(zhuǎn)換矩陣存儲(chǔ)狀態(tài)，矩陣中的每行都相互對(duì)應(yīng)某個(gè)狀態(tài)，每個(gè)對(duì)的狀態(tài)要實(shí)現(xiàn)相應(yīng)列對(duì)應(yīng)字符之后的轉(zhuǎn)換狀態(tài)[9]。

表1為狀態(tài)轉(zhuǎn)換矩陣，其匹配的過(guò)程為從0狀態(tài)開(kāi)始，逐一實(shí)現(xiàn)T文本字符的輸入，以狀態(tài)轉(zhuǎn)換矩陣尋找之后狀態(tài)，目前狀態(tài)輸出函數(shù)不空的時(shí)候就要實(shí)現(xiàn)匹配內(nèi)容的輸出，直到文本末尾[10]。AC算法模式匹配時(shí)間復(fù)雜程度表示O（n）。

其二，BM算法。此算法屬于單模式匹配算法中的經(jīng)典算法，目前單模式匹配算法大部分都是基于BM算法進(jìn)行改進(jìn)。其在匹配的過(guò)程中要對(duì)其文本左端和模式，從模式右端起逐一進(jìn)行字符對(duì)比，在出現(xiàn)不匹配的時(shí)候就要使模式向右進(jìn)行移動(dòng)，移動(dòng)距離通過(guò)預(yù)處理的規(guī)則計(jì)算值進(jìn)行決定。BM算法以壞字符及好后綴的規(guī)則對(duì)移動(dòng)距離進(jìn)行計(jì)算，從而創(chuàng)建壞字符移動(dòng)表及好后綴的移動(dòng)表，在實(shí)現(xiàn)匹配的過(guò)程中對(duì)此表進(jìn)行查找，使用此表移動(dòng)距離最大的實(shí)現(xiàn)模式移動(dòng)[11]。BM算法創(chuàng)建壞字符異動(dòng)表時(shí)間復(fù)雜程度為O（m+Σ），創(chuàng)建之后的好后綴異動(dòng)表時(shí)間復(fù)雜度屬于O（m）。雖然BM算法最壞的時(shí)間復(fù)雜度表示O（m*n），但是因?yàn)樗惴ㄊ褂锰S式的匹配，所以其實(shí)際的次數(shù)只是文本長(zhǎng)度20%～30%。

BM算法術(shù)單模式匹配，其在一般使用過(guò)程中的性能比較優(yōu)秀，但是其在每次匹配的時(shí)候都要計(jì)算模式，那么就會(huì)提高預(yù)處理的花費(fèi)，并且其在多模式匹配過(guò)程中的使用效果并不理想，要對(duì)BM算法重復(fù)使用，從而降低了使用效率[12]。

其三，MWM算法。此算法屬于改進(jìn)算法，其主要是利用目前匹配模式集合特征實(shí)現(xiàn)NoBC算法及ExBC算法、EXBW算法的調(diào)用。模式集合中的數(shù)量較多，因?yàn)樽钚∧Ｊ介L(zhǎng)度會(huì)對(duì)算法匹配時(shí)候的文本字符最大的跳躍距離造成影響，假如最小模式為1，那么就使用hash表及NoBC表。其預(yù)處理的過(guò)程為：

圖5 AC算法中的輸出函數(shù)示意圖

表1 狀態(tài)轉(zhuǎn)換矩陣

首先，字典排序，得到msPatArray表的內(nèi)容，詳見(jiàn)表2。

之后，創(chuàng)建hash表，其主要是以每個(gè)模式前兩個(gè)字符散列值為基礎(chǔ)進(jìn)行創(chuàng)建。表3為hash表中的內(nèi)容。

通過(guò)以上可以看出來(lái)，0的前綴字符塊為aa。因?yàn)槠浔硎且宰址疄榛A(chǔ)創(chuàng)建的，所以有256項(xiàng)。本文以BM算法為基礎(chǔ)實(shí)現(xiàn)模單式匹配算法的優(yōu)化[13]。

表2 msPatArray表的內(nèi)容

表3 hash表中的內(nèi)容

3 網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)模式匹配算法的優(yōu)化

網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)能夠?qū)崿F(xiàn)執(zhí)行數(shù)據(jù)包的深入檢測(cè)，其還能夠?qū)ω?fù)載沒(méi)有或者已經(jīng)實(shí)現(xiàn)定義的規(guī)則集相互匹配模式串進(jìn)行掃描，從而對(duì)其是否具有入侵檢測(cè)事件進(jìn)行檢測(cè)。

3.1 分析BM算法中的好后綴函數(shù)

從理論方面進(jìn)行分析，BM算法較為嚴(yán)謹(jǐn)，但是其在實(shí)際使用過(guò)程中的性能并不理想。所以，本文就修改了好后綴規(guī)則中的不足。此實(shí)驗(yàn)需要測(cè)試的指標(biāo)主要為：

其一，BM和BMH算法運(yùn)行的時(shí)間；

其二，BM和BMH算法的字符比較數(shù)量；

其三，BM算法中字符比較數(shù)量及使用好后綴規(guī)則數(shù)量。

因?yàn)槿肭謾z測(cè)中的模式串長(zhǎng)度都是在20～30字符自檢，本文進(jìn)行隨機(jī)選擇進(jìn)行實(shí)驗(yàn)[14]。表4為BM和BMH算法運(yùn)行過(guò)程中總時(shí)間的對(duì)比。

通過(guò)表4可以看出來(lái)，BM算法和BMH算法的總字符數(shù)量相同，但是在時(shí)間復(fù)雜度方面，后者性能更加良好。

通過(guò)表5可以看出來(lái)，BM算法匹配過(guò)程使用好后綴數(shù)量較少，并且沒(méi)有規(guī)律，所以就提高了BM算法總體運(yùn)行時(shí)間。對(duì)于此種問(wèn)題，本文就對(duì)全新模式匹配算法進(jìn)行改進(jìn)，將好后綴規(guī)則進(jìn)行去掉，改進(jìn)壞字符規(guī)則，從而有效提高模式匹配速度。

表4 BM和BMH算法運(yùn)行過(guò)程中總時(shí)間的對(duì)比

表5 BM算法總字符對(duì)比數(shù)量和使用好后綴規(guī)則數(shù)量

3.2 改進(jìn)算法

3.2.1 主要思想

其一，大部分規(guī)則匹配內(nèi)容后綴及前綴都相同，所以改進(jìn)算法要能夠滿足入侵檢測(cè)系統(tǒng)模式匹配；

其二，單模式匹配算法及模式對(duì)其文本字符進(jìn)行偏移量計(jì)算，另外就是通過(guò)下一個(gè)字符對(duì)偏移量進(jìn)行計(jì)算，本文所改進(jìn)的算法就是將兩者相互結(jié)合，從而形成全新的算法[15]。圖6為改進(jìn)算法的工作流程。

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

改進(jìn)算法的實(shí)現(xiàn)步驟主要為兩個(gè)階段，第一階段：預(yù)處理。對(duì)兩個(gè)字符集進(jìn)行計(jì)算，得到計(jì)算結(jié)果；第二階段為初始位置及匹配方向。在開(kāi)始匹配的時(shí)候，要求模式串左端和待測(cè)文本左端相互對(duì)齊，字符對(duì)比通過(guò)模式串末端對(duì)齊文本T開(kāi)始，從右到左開(kāi)始。如果匹配失敗，模式串就要移動(dòng)到右端。

3.2.3 算法實(shí)例

使用改進(jìn)算法，其只移動(dòng)了兩次，一共匹配3次就能夠?qū)ふ夷Ｊ綁K，說(shuō)明本文所設(shè)計(jì)的改進(jìn)算法能夠提高預(yù)處理時(shí)間，并且計(jì)算方式較為簡(jiǎn)單[16]。

圖6 改進(jìn)算法的工作流程

表6 Badchar1與Badchar2的函數(shù)

4 結(jié)束語(yǔ)

在網(wǎng)絡(luò)使用不斷發(fā)展的過(guò)程中，網(wǎng)絡(luò)寬帶在不斷的增加，所以就要提高網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)處理性能，從而使其能夠滿足大流量網(wǎng)絡(luò)環(huán)境需求。本文就對(duì)模式匹配算法進(jìn)行了研究，并且實(shí)現(xiàn)了單模式匹配算法的改進(jìn)。通過(guò)實(shí)例表示，改進(jìn)的匹配模式算法能夠有效滿足網(wǎng)絡(luò)使用需求，提高系統(tǒng)檢測(cè)效率。