網絡入侵檢測系統中的模式匹配算法設計優化

陳卓民

（陜西警官職業學院教務處陜西西安710021）

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

1 網絡入侵檢測系統和算法

1.1 網絡入侵檢測系統

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

圖1 網絡入侵檢測系統的結構

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

1.2 網絡入侵檢測算法

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

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

圖2 基于模式匹配入侵檢測系統的結構

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

2 傳統模式匹配算法

傳統模式匹配算法的概念為：

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

傳統模式匹配算法主要包括以下：

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

圖3 AC算法轉移函數的轉換過程

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

圖4 AC算法失效函數的示意圖

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

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

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

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

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

圖5 AC算法中的輸出函數示意圖

表1 狀態轉換矩陣

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

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

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

表2 msPatArray表的內容

表3 hash表中的內容

3 網絡入侵檢測系統模式匹配算法的優化

網絡入侵檢測系統能夠實現執行數據包的深入檢測，其還能夠對負載沒有或者已經實現定義的規則集相互匹配模式串進行掃描，從而對其是否具有入侵檢測事件進行檢測。

3.1 分析BM算法中的好后綴函數

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

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

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

其三，BM算法中字符比較數量及使用好后綴規則數量。

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

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

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

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

表5 BM算法總字符對比數量和使用好后綴規則數量

3.2 改進算法

3.2.1 主要思想

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

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

3.2.2 算法實現

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

3.2.3 算法實例

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

圖6 改進算法的工作流程

表6 Badchar1與Badchar2的函數

4 結束語

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