Snort入侵檢測系統的算法分析研究

摘要：本文對Snom入侵檢測系統的幾種算法進行了介紹和分析，分析了各種不同的算法對入侵檢測系統效率的影響，通過改進匹配算法來提高匹配的效率，使檢測系統的效率得到了提高。

關鍵詞：Snort；AC算法；KMP算法；BM算法

中圖分類號：TP393．08 文獻標識碼：A 文章編號：1006-3315(2011)12-177-002

隨著網絡技術的不斷發展和網絡用戶的不斷增加，人們得益于網絡帶來的便利的同時，計算機和網絡系統的安全問題也越顯突出。目前的網絡安全技術如：防火墻、信息加密，作為網絡安全的第一道防線遠不能有效阻止來自網絡上的入侵。針對網絡系統攻擊的普遍性，攻擊手法的復雜性，入侵檢測技術也隨著網絡技術和相關學科的發展日趨成熟，成為網絡安全的第二道防線。它對計算機和網絡資源上的惡意使用行為進行識別和響應，它不僅可以檢測到來自外部的入侵，也可以監督內部用戶的未授權活動。

一、入侵檢測系統Snon

Snort是由Sourcefire公司Mar-tyRoeseh等人開發的一個基于Libpcap的輕量級入侵檢測系統，是一個開放源代碼的網絡安全解決方案，是一個多功能的輕量級網絡入侵檢測系統。從檢測機制上看，它不僅具有基于規則的誤用檢測方法，而且還有基于異常的檢測方法預處理功能。從體系結構上看，它充分考慮到擴展的需求，大量使用了插件機制。從功能模塊上看，各個模塊功能明晰，相對獨立，設計合理。從編碼上看，具有很好的設計風格和詳細的注釋，易于理解的體系結構功能模塊設計獨立，功能明晰。Sno，總體模塊圖[1]如下圖1所示：

二、入侵檢測系統Snort算法

1．AC算法

Aho-Corasick[2]算法簡稱(Ac)算法，是多模式檢測算法之一，該算法的基本思想是：在預處理階段，有限自動機算法建立三個函數，轉向函數goto，失效函數failure和輸出函數output，由此構造一個樹型有限自動機。這樣模式匹配的處理過程就變成了狀態轉換的處理過程，由“start”狀態開始。在搜索查找階段，通過這三個函數的交叉使用掃描文本，定位出關鍵字在文本中的所有出現位置。

Snort應用AC算法時，做了以下改進，使得該算法在運行時具有更好的性能：

(1)同時支持確定型和不確定型有限狀態自動機；

(2)采用線性鏈表來初始化狀態轉移表；

(3)執行過程中，自動機的狀態轉移表轉換成全矩陣形式，有利于減少內存開銷；

(4)在每一個狀態轉移鏈表中增加一個布爾型變量，來指示狀態中是否存在一個匹配的模式。

Aho-Corasick算法在對文本進行搜索的過程中沒有跳躍，而是按順序輸入文本yi，無法跳過不必要的比較。因此在實際搜索過程中，Aho-Corasick算法不是性能最佳的搜索算法，并且有限自動機算法是以空間換時間的經典算法。當模式集較大時可能產生空間膨脹問題，這是因為對于一個總長度為m個字節的模式集，根據有限自動機的構造原理，在最壞的情況下具有m個狀態，對于每個狀態可能有256種不同的輸入。因此描述有限自動機的二維表所需內存空間為256*m字節，當模式集較大時對于內存的要求將會變得很高。

2．KMP算法

KMP算法的基本思想是每當一趟匹配過程中出現字符比較不等時，不需回溯j指針，而是利用已經得到的部分匹配的結果將模式向右滑動盡可能遠的一段距離后，繼續進行比較。

設s為目標串，t為模式串，設i指針和j指針分別指示目標串和模式串中正待比較的字符，開始時，令i=O，j=0。如果s=tj，則使i和j的值分別增加1；反之，i不變，j的值退回到j=next[j]的位置(即模式串右滑)，然后再對si和tj進行比較。依此類推，直到出現下列兩種情況之一：

(1)j值退回到某個j=next[j]時，有si=tj，則指針的值各增加l后，再繼續匹配；

(2)j值退回到j=-1，此時令指針的值各增加1，也即下一次對si+l和t0進行比較。

模式匹配KMP算法的時間復雜度為0(m+n)，只有當模式與珠串之間存在許多“部分匹配”的情況下顯得比樸素字符匹配算法快得多。但是KMP算法最大的特點就是指示主串的指針不需要回溯，整個過程中，對主串僅需從頭至尾掃描一遍，這對處理從外設輸入的龐大文件很有效，可以便讀入邊匹配，而無需回頭重讀。

3．BM算法

Boyer-Moore算法(簡稱為BM算法)是一個著名的字符串匹配算法，它把被匹配的字符串模板(下文簡稱為“文本串”)與匹配字符串(下文簡稱為“字符串”)自左向右對齊，并從字符串的最后一個字符開始自右向左進行比較。

在用于查找子字符串的算法當中，BM算法是目前相當有效又容易理解的一種，一般情況下，比KMP算法快3--5倍。

BM算法的規則如下：

1從后向前匹配。我們看到圖2中指針是從pat的最后一個字符開始比較的。與英文的單詞組成相關，英文單詞很多都是采用相同前綴構造的，還有就是一個單詞的很多形式前綴也都是相同的，而后綴不同，所以這樣可以盡快地排除不符合要求的單詞，使指針在string中快速前移。