陳卓民

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

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

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

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

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

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

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

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

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

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

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

目前模式匹配檢測算法在執(zhí)行任務(wù)的過程中都是通過fpEvalPacket實(shí)現(xiàn)的，在函數(shù)模塊實(shí)現(xiàn)預(yù)處理之后，對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長度文本是T[1…n]，m長度模式P屬于P[1…m]，模式的集合屬于{Pi}，模式集合的總長度屬于M。單模式匹配指的是文本T在對P的尋找；多模式匹配指的是文本T在對多個(gè)模式進(jìn)行尋找。在入侵特征不斷增加的過程中，入侵檢測模式匹配算法也逐漸從單模式轉(zhuǎn)變成為多模式[7]。

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

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

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

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

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

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

表1為狀態(tài)轉(zhuǎn)換矩陣，其匹配的過程為從0狀態(tà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)。其在匹配的過程中要對其文本左端和模式，從模式右端起逐一進(jìn)行字符對比，在出現(xiàn)不匹配的時(shí)候就要使模式向右進(jìn)行移動，移動距離通過預(yù)處理的規(guī)則計(jì)算值進(jìn)行決定。BM算法以壞字符及好后綴的規(guī)則對移動距離進(jìn)行計(jì)算，從而創(chuàng)建壞字符移動表及好后綴的移動表，在實(shí)現(xiàn)匹配的過程中對此表進(jìn)行查找，使用此表移動距離最大的實(shí)現(xiàn)模式移動[11]。BM算法創(chuàng)建壞字符異動表時(shí)間復(fù)雜程度為O（m+Σ），創(chuàng)建之后的好后綴異動表時(shí)間復(fù)雜度屬于O（m）。雖然BM算法最壞的時(shí)間復(fù)雜度表示O（m*n），但是因?yàn)樗惴ㄊ褂锰S式的匹配，所以其實(shí)際的次數(shù)只是文本長度20%～30%。

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

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

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

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

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

之后，創(chuàng)建hash表，其主要是以每個(gè)模式前兩個(gè)字符散列值為基礎(chǔ)進(jìn)行創(chuàng)建。表3為hash表中的內(nè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ò)入侵檢測系統(tǒng)模式匹配算法的優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

3.2 改進(jìn)算法

3.2.1 主要思想

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

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

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

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

3.2.3 算法實(shí)例

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

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

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

4 結(jié)束語

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