網絡入侵檢測系統(tǒng)中的模式匹配算法設計優(yōu)化

陳卓民

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

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

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

1.1 網絡入侵檢測系統(tǒng)

網絡入侵檢測系統(tǒng)屬于標識并且隔離入侵安全的技術，其也是防火墻以外的第二道防線，圖1為網絡入侵檢測系統(tǒng)的結構。

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

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

1.2 網絡入侵檢測算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首先，字典排序，得到msPatArray表的內容，詳見表2。

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

通過以上可以看出來，0的前綴字符塊為aa。因為其表是以字符串為基礎創(chuàng)建的，所以有256項。本文以BM算法為基礎實現(xiàn)模單式匹配算法的優(yōu)化[13]。

表2 msPatArray表的內容

表3 hash表中的內容

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

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

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

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

其一，BM和BMH算法運行的時間；

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

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

因為入侵檢測中的模式串長度都是在20～30字符自檢，本文進行隨機選擇進行實驗[14]。表4為BM和BMH算法運行過程中總時間的對比。

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

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

表4 BM和BMH算法運行過程中總時間的對比

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

3.2 改進算法

3.2.1 主要思想

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

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

3.2.2 算法實現(xiàn)

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

3.2.3 算法實例

使用改進算法，其只移動了兩次，一共匹配3次就能夠尋找模式塊，說明本文所設計的改進算法能夠提高預處理時間，并且計算方式較為簡單[16]。

圖6 改進算法的工作流程

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

4 結束語

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