基于SBOM算法的網絡入侵檢測系統的實現

摘 要： 入侵檢測系統的核心部分就是檢測引擎，檢測引擎采用的算法的優劣直接關系到入侵檢測系統的性能。在分析SBOM算法的數據結構和模式匹配過程的基礎上，將SBOM算法引入Snort網絡入侵檢測系統中，得到了實現Snort檢測引擎的一種新的方法。實驗結果表明，SBOM算法在模式集較大的情況下性能比較具有優勢，并且隨著最小模式長度以及模式集的增長算法具有更好的性能。

關鍵詞： 入侵檢測系統； Snort； 模式匹配； SBOM

中圖分類號： TP309 文獻標識碼： A 文章編號：2095-2163（2013）03-0090-03

The Implementation of Network Intrusion Detection System based on SBOM Algorithm

ZHOU Lihua

（Computer Network Center， Guizhou Minzu University， Guiyang 550025， China）

Abstract： The detection engine is the core module of the intrusion detection system. The efficiency of pattern matching algorithm used in detection engine decides the performance of this type of intrusion detection system. This paper implements the SBOM algorithm in Snort and obtains a new method of Snort detection engine. The result of experiment indicates that algorithm being comparatively excellent for large keyword sets， and progressively better for large alphabets as the minimum keyword length increases and as the keyword set size increases.

Key words： Intrusion Detection System； Snort； Pattern Matching； SBOM

0 引 言

隨著計算機網絡的蓬勃發展和快速普及，計算機網絡信息安全已成為當今社會的一個焦點問題。傳統的計算機網絡信息安全防御技術，如防火墻、數字簽名等，已經難于適應當前計算機網絡攻擊的多樣性。在此背景之下，入侵檢測系統即成為研究的探索方向。入侵檢測系統是一種積極主動防御的技術，其工作原理是動態的，可以在入侵過程中對防護系統進行實時監控，無論是發生內部攻擊或是外部攻擊，入侵檢測系統均能對其提供實時的保護。入侵檢測系統的核心部分就是檢測引擎，檢測引擎的算法優劣將直接關系入侵檢測系統的性能[1]。

1 SBOM算法數據結構

本文將近年來較新提出的基于Factor Oracle自動機的SBOM（Set Backward Oracle Matching）算法運用到Snort中。多模式的SBOM算法是BOM（Backward Oracle Matching）算法的擴展。BOM算法通過模式串建立一種類似于Trie的數據結構Oracle因子[2]，Oracle由一系列節點因子連接而成，能接收模式串中所有的節點因子。事實上，Oracle的數據結構就是一種結構緊湊的確定型自動機，能夠識別其所建立的關鍵字的所有因子，構建Oracle因子的算法可參考文獻[3]，此處不再贅述。圖1是BOM的Oracle數據結構。

多模式的SBOM（Set Backward Oracle Matching）算法繼承了BOM算法的Oracle數據結構和Aho-Corasick算法的Trie數據結構。在進行預處理過程中將根據所有模式串構造模式匹配的Oracle結構，以識別匹配窗口的最長字串。由于各個模式串的長度可能互不相同，為了不致遺漏正確的匹配，SBOM算法對模式串進行了如下處理[4]：

圖1 BOM算法的Oracle數據結構

Fig.1 Oracle data structure of the BOM algorithm

（1）求模式串中最小串的長度，記為Imin。

（2）根據模式串集合P'={prefix（p，Imin）| p∈P}進行構造Oracle，即使用每個模式串的長度為Imin的前綴來完成構造。

多個模式串的Oracle結構為實現構造使用了BOM算法中的一個函數——supply function S，S函數的作用是對于某個狀態p，能識別另外的一個狀態k作為其替代狀態。SBOM算法的Oracle數據結構的構建方法如下：

（1）根據所有模式串反相構造Trie連接結構。

（2）指定Trie的根節點I的supply function為空，即S[I]=Φ。

（3）按寬度優先法則遍歷Trie中的所有節點q，對于所有的q∈oracle（q≠I）：

（a）初始化變量k←S[parent（q）]；

（b） 初始化變量σ（σ表示從parent（q）到q結點的遷移值）；

（c）如k=Φ，則S（q） ←I；

（d）如k≠Φ并且沒有從k到q值為σ的遷移，那么建立一個從k到q值為σ的遷移，置k←S（k），重復步驟（c）；

（e）如k≠Φ并且有從k狀態開始值為σ的指向狀態s的遷移，那么S（q）←s，完成狀態q的建立。第3期 周麗華：基于SBOM算法的網絡入侵檢測系統的實現 智能計算機與應用 第3卷

現舉一例，如模式串barbarian和bomb的Oracle結構，如圖2所示。

圖2 SBOM算法的Oracle數據結構

Fig.2 Oracle data structure of the SBOM algorithm

2 SBOM算法匹配過程

SBOM算法的匹配過程采用一個長度為Imin的滑動窗口來掃描輸入文本，在這個窗口中可從右到左讀取最長的從初始狀態開始標示的后綴。SBOM算法的最壞時間復雜度是O（n*M），但在平均意義下則能亞線性地執行達到n[2]。SBOM算法的匹配過程寫成偽代碼，如下所示：

（1）預處理過程，構建模式的Oracle結構；

（2）得到模式串中最小串的長度Imin，I←oracle root（根節點）；

（3）i←0（文本當前的匹配位置），匹配過程開始；

驗證y[i]...y[i+Imin -1]是否與q指向的模式串匹配

以下將通過實例來說明SBOM算法匹配過程。

由圖2可得，數據串如3所示。

容易知道，匹配窗口移動2位，如圖4所示。

圖3 數據串

Fig.3 Data string

圖4 SBOM算法匹配過程

Fig.4 The matching procedure of the

SBOM algorithm3 實驗驗證

為了評價加入SBOM算法后的NIDS的功能，本文將SBOM算法加入到Snort中并重新編譯后得到Snort2.8.0.1版本，采用的編譯環境是VC++6.0。硬件的配置如下：處理器為Pentium（R）4，內存為512M，操作系統為windows 2003 server。在檢測基于SBOM算法的網絡入侵監測系統的性能的同時，還選擇了幾個Snort自帶模式匹配算法選項如AC-Full、acs、ac-banded、ac-bnfa、low-mem來比較彼此之間的性能[5]。實驗比較不同算法選項所對應的檢測引擎的處理時間、系統消耗的內存隨規則、模式、數據包的數量增減的變化情況。實驗過程中，Snort以4 990條規則作為基數，每次減少約1 000條，對于每次選取的規則數的運行時間和內存消耗進行了3次記錄，結果取其平均值。為了更準確地檢測算法的性能，一組測試數據采用的是Shmoo工作組[6]所使用數據集，另外一組則采用與前者差距較大的美國麻省理工大學林肯實驗室提供的1999 DARPA intrusion Detection Evaluation Data Sets，也就是著名的林肯數據集[7]。其中，林肯數據集在評估入侵檢測系統性能方面具有公認的權威性，目前國際上的商用系統及處于實驗室階段的科學研究原型系統均采用這個數據集進行測試，這個數據集記錄了七個星期的主機系統記錄日志和所有的網絡流量記錄，其數據是采用tcpdump和BSM審計數據的格式來進行記錄的。本實驗采用的則是其中一天的攻擊數據。經處理后，這兩個數據集大小分別為42.3MB和365.1MB，內含的數據包分別為406 815個和1 406 063個，實驗結果分別如圖5、圖6所示。

圖5 各算法運行時間

Fig.5 The running time of the algorithms

圖6 各算法消耗內存

Fig.6 The memory usage of the algorithms 由圖5和圖6可以得出以下結論：

算法運行時間和數據包的大小有關，數據包越大，算法運行時間越長并且各算法之間的時間差距越大。在各個算法中，運行時間最優的是AC-Full和acs，其次是lowmem算法。 算法的內存消耗和數據包大小無關而與規則的數量有關，規則越多，消耗的內存越大。在各個算法中，消耗內存最多的是AC-Full算法，內存消耗最少的是ac-bnfa和lowmem。消耗內存最多的是AC-Full和SBOM算法，這兩者的內存消耗基本上一致，多數時候SBOM略大于AC-Full，則是因為SBOM算法的Trie結構是用AC算法實現的，這一部分消耗的內存和AC-Full算法消耗的內存一致，多出來的部分用于構建Oracle數據結構，這一部分的構建是基于反向的最短關鍵字，可以看到構建Oracle數據結構消耗的內存比構建Trie結構要少得多。

SBOM算法的平均運行時間能達到亞線性，從圖5和圖6可以看到在模式較多、也就是規則較多的情況下，SBOM算法在性能上較有優勢，但是如果規則較少，優勢則并不十分明顯。

4 結束語

在AC算法的各種變體中，AC-Full完全是以空間換時間，在性能上相較其他幾種算法并沒有極大的優勢；ac-bnfa在內存消耗上比較低但是同時又有比較高的性能，雖然lowmem也同樣消耗內存較少，但其性能并不是很高。由此得出結論，沒有一種算法能適用于所有的情況，在實際的應用中，可以根據系統的具體情況以選擇相應的算法。

參考文獻：

[1]（美）KOZIOL J著.Snort入侵檢測實用解決方案[M]. 吳溥峰 ，孫默，許成，等譯.北京：機械工業出版社：35—53.

[2]ALLAUZEN C，RAFFINOT M. Oracle des facteurs d’un ensemble de mots[R]. Technical Report IGM 99-11， Institut Gaspard Monge， Universit/e de Marne-la-Vall/ee，France， 1999.

[3]MANBER S WU. U.S.A Fast Algorithm for Multi-pattern Searching[R].Tuscon， USA：University of Arizona，Technical Report：94-1-17-1994，1994-05.

[4]譚建龍.串匹配算法及其在網絡內容分析中的應用[D].北京：中國科學院研究生院，2003：31-32.

[5]楊衛平，黃煙波，段丹青.智能入侵檢測技術評述〔J〕.網絡安全技術與應用，2005，4：58-59.

[6]http：//cctf.shmoo.com/data/cctf-defcon10/

[7]http：//www.ll.mit.edu/