基于Snort入侵檢測系統(tǒng)模式匹配改進算法研究

1、基于Snort入侵檢測系統(tǒng)模式匹配改進算法研究    摘 要：網(wǎng)絡技術的應用已經(jīng)從傳統(tǒng)的小型業(yè)務系統(tǒng)逐漸擴展到大型的關鍵業(yè)務系統(tǒng)中，但是在浩瀚的 Internet 網(wǎng)絡中，系統(tǒng)容易受到外界的攻擊與破壞，信息被竊取和修改等網(wǎng)絡安全問題越來越嚴重。研究現(xiàn)有的 snort 入侵檢測系統(tǒng)算法，并進行優(yōu)化改進，使其在實際應用中提高信息安全防范能力。關鍵詞 ：網(wǎng)絡入侵檢測 ；Snort ；BM 算法 ；Wu-Manber 算法1 入侵檢測技術的現(xiàn)狀自從計算機網(wǎng)絡誕生以來，人們對網(wǎng)絡安全的保護最傳統(tǒng)的方法就是防火墻技術，但是防火墻只是一種被動防御性的網(wǎng)絡安全工具，由于

2、網(wǎng)絡日趨復雜化，傳統(tǒng)防火墻是不足以滿足如今復雜多變的網(wǎng)絡安全問題。入侵檢測從二十世紀八十年代產(chǎn)生以來，它就受到了各界人士的密切關注。它是一種積極主動的安全防護技術，其核心在于它的檢測引擎，如何實現(xiàn)高效快速的檢測是入侵檢測技術的一個重要研究重點。目前入侵檢測技術主要分為兩大類，分別是基于異常的入侵檢測和基于規(guī)則的入侵檢測。其檢測算法種類繁多，諸如專家系統(tǒng)、模式匹配、數(shù)據(jù)挖掘、統(tǒng)計方法以及免疫學等，其中模式匹配算法具有較高的時間效率的優(yōu)點，人們一直關注并研究如何能提高模式匹配算法的效率，模式匹配算法的發(fā)展方向就是提高算法的平均性能和較少資源消耗，其主要方法就是在實際的匹配過程中設法減少實際匹配的次

3、數(shù)，同時設法將部分匹配算法移植到硬件中或在并行的體系結構下實現(xiàn)，從而減少匹配所消耗的時間和空間1。2 Snort 工作流程分析Snort 是一個用 C 語言編寫的輕量級開放源代碼的軟件，它是目前入侵檢測系統(tǒng)中最主要的工具，現(xiàn)已被廣泛的安裝和使用。它有很多有用的功能 ：數(shù)據(jù)包嗅探、數(shù)據(jù)包記錄、入侵檢測等。其工作原理是基于共享網(wǎng)絡上的原始網(wǎng)絡傳輸數(shù)據(jù)，通過分析所捕獲的數(shù)據(jù)包，將這些數(shù)據(jù)包與 Snort 規(guī)則特征庫進行模式匹配來檢測異常行為，發(fā)現(xiàn)入侵行為進行報警，并將報警信息記錄以便進行分析。Snort 系統(tǒng)工作流程如圖 1 所示。Snort 從體系結構上看，它充分考慮了擴展的需求，大量使用了插件機

4、制 ；從功能模塊上看，各個模塊功能清晰、相對獨立、設計合理 ；從檢測機制上看，它不僅具有基于規(guī)則的誤用檢測方法，而且還有基于異常的檢測方法 ；從編碼上看，具有很好的設計風格和詳細的注釋，易于理解。Snort 可以執(zhí)行幾大簡單功能，如果我們要更深地去了解Snort 的結構并對其進行配置，它就可以實現(xiàn)強大的功能，Snort 功能的強大主要體現(xiàn)在其擁有重要的功能模塊。這些模塊主要包括 ：主控模塊、解碼模塊、規(guī)則處理模塊、預處理插件模塊、輸出插件模塊等等2。具體模塊的性能和要求參照 Snort 使用說明，這里不再贅述。3 Snort 系統(tǒng)中模式匹配算法Snort 工具本身提供了多種模式匹配算法，比如

5、Boyer-Moore 算法、AC 算法以及 Wu-Manber算法等，Snort 早期版本的系統(tǒng)檢測引擎主要采用單模式 BM 模式匹配算法，隨著網(wǎng)絡流量的不斷增加，現(xiàn)在的版本多采用多模式匹配算法來加快系統(tǒng)的匹配速度，下面對幾種比較常用的快速算法分別進行分析。3.1 單模式 Boyer-Moore 算法分析BM 算法3歸類為一種精確、單模式匹配算法，它是利用啟發(fā)式策略，它以減少算法時間來提高匹配效率。算法描述為 ：模式串記為 P，文本串記為T。左對齊 P 與 T，把模式串與文本串從右向左開始匹配，如果 Pi=Ti，就同時向左挪一個位置再比較，否則就要滑動 P 進行重新對齊，模式串就要向后滑動。

6、移動距離時要對模式串 P 定義一個滑動距離函數(shù) dist，dist 函數(shù)的具體定義如圖 2 所示。情況一 ：根據(jù)算法描述，開始比對位不匹配，即從右向左比較時，第一個字符不匹配，而且這個未匹配上的字符在 P 中不存在，那么 P 可以直接右移模式串長度個單位，如圖 2 中 j 與 z 不匹配，且z 在 P 中不存在，那么我們可以把 P 右滑 4 個單位，如圖 3 所示。情況二 ：根據(jù)算法描述，開始比對位也不匹配，但這個未匹配上的字符串在 P 中存在，如果有多個，那就找最靠右的那個與模式串 P 中相同的字符串直接對齊，如圖 3 中 2 與 j 不匹配，但 2 存在于 P 中，右移 P 使得兩個 2

7、對上，移動后如圖 4 所示。情況三 ：若 T 與 P 有部分已經(jīng)匹配上，且已經(jīng)匹配上的部分在 T 中后其他地方也存在，那么就將P 右移，直接將已匹配部分對齊即可，這里可以說是 BM 算法中的好后綴思想，如圖 5 所示。BM 算法是目前基于主機的入侵檢測系統(tǒng)應用中最為常用、效率較高的單模式匹配算法之一，進行模式串匹配時是從右到左，并且用好后綴和壞字符兩種啟發(fā)方式來進行智能啟發(fā)跳躍，在基于主機的入侵檢測系統(tǒng)中能夠發(fā)揮較好的作用。3.2 多模式 Wu-Manber 算法分析在多模式串匹配算法中，模式串數(shù)量越多 , 模式串后端出現(xiàn)相同的概率也相應增大，根據(jù) Wu-Manber 算法中 SHIFT 表描

8、述可以看出，模式串的移動距離也就減小，從而模式匹配算法效率就大大降低。Wu-Manber 算法4是一種快速實用的多模式串匹配算法，目前主要是用在基于網(wǎng)絡的入侵檢測系統(tǒng)中，它是借鑒單模式串 BM 算法的一些思想構造出來的，Wu-Manber 算法采用字符塊 B(B 是字符塊的長度 ) 擴展壞字符移動規(guī)則來解決這個問題，同時用散列表來篩選匹配階段應進行匹配運算的模式，從而減少算法匹配時間，提高運行效率5。Wu-Manber 算法首先對模式串進行預處理，也就是我們熟知的在預處理階段建立三個表格 ：SHIFT表 ,HASH 表和 PREFIX 表。SHIFT 表存儲著字符集中所有字符塊在模式串中出現(xiàn)時

9、的移動距離，HASH 表用來存儲塊尾字符散列值相同的模式串的值，REFIX 表用來存儲塊尾字符散列值相同的模式串的首塊字符散列值，匹配過程很簡單，就是利用這三個表來完成文本的掃描和尋找，在計算匹配移動距離時有以下兩個原則6：(1) 如果窗口中的字符塊 B 不出現(xiàn)在任何模式串中，則利用計算公式 SHIFTh=m-B+1，其中，h 為字符塊 B 的 hash 值。其中 B 取決于最短模式串的長度和模式串個數(shù)，字符塊 B 通常取 2 或3，m 是模式的最短長度，SHIFT 的移動距離是計算每個塊字符與匹配窗口內模式串串尾的距離。(2) 如 果 字 符 塊 B 出 現(xiàn) 在 某 些 模 式 串 中 ,而

10、且在所有模式串中的最右出現(xiàn)位置為 l，則SHIFTh=m l。算法匹配步驟如下 ：1) 選取所有模式串中最短的模式串的長度記為m ；2) 構建 HASH 表，值記為 HASHh ；3) 構建 PREFIX 表，值記為 PREFIXh ；4) 檢查 SHIFTh 的值，如果 SHIFTh>0,將窗口向右移動 SHIFTh 大小位置 SHIFTh=0，則進入第 5) 步進行進一步驗證 ；5) 對符合 HASHh P<HASHh+1 的每一個 p 值 , 檢驗是否存在 PREFIXp=PREFIXh。如果相等，那么模式串和文本串匹配成功。4 改進的 Snort 模式匹配算法4.1 改進的

11、 Boyer-Moore 算法分析通過對 BM 算法的分析，發(fā)現(xiàn)它在基于主機的入侵檢測系統(tǒng)中的應用還是有一些不足 ：(1) 仍舊存在重復的比較 ；(2) 如果模式串只有一個字符，那么它和 BF 算法就沒有區(qū)別 ；(3) 隨著匹配規(guī)則的增多，多次訓練的話效果越來越不明顯?，F(xiàn)在對 BM 算法進行如下改進 ：假如把模式串的整體長度作為一個塊單位，一塊一塊進行比較，就可以按如下方法改進，首先還是比較文本指針所指字符和模式的最后一個字符，如相等再比較前一個字符，無論文本中哪個字符造成了匹配失敗 , 現(xiàn)都將由文本中和模式最后一個位置對應的下一個字符之后向右的滑動。例如 , 文本串 T 為“fatefine

12、gwxcicl”，模式串 P 為“wxcicl”。若仍用 BM 算法進行匹配的過程如圖 6 所示，如用 BM原算法進行匹配如下 ：說明 ：第一次，i 與 l 不匹配 , 但 i 存在于模式串中 , 向右滑 2 個字符使兩個 i 對齊。第二次，e與 l 仍不匹配，但 e 不存在于模式串中，則向右滑6 個字符的距離。第三次，指針 =14，dc=1，向右滑 1 個字符，匹配成功。接下來看 BM 算法的改進 ：由文本串和模式串最后一個位置對應的字符的下一個字符做啟發(fā)向右滑動。其作用在于在每次匹配失敗后，把模式向右滑動位數(shù)又會增大，減少重復比較次數(shù)。示例如下 ：同樣把“fatefinegwxcicl”作

13、為文本串 T，“wxcicl”作為模式串 P，用改進的BM 算法匹配過程如圖 7 所示。圖 7 改進 BM 算法在匹配過程中，第一次用文本串末尾 i 的下一個字符 n 做啟發(fā)，n 在模式串中不存在，那么就將模式串向右移動 6+1 個位置，第二次再用文本串的第 14 位的 c 做啟發(fā)，因為 c 存在于模式串中，但上例中模式串有多個 c，取模式串最靠右的那個與文本串中的 c 對齊，匹配成功。通過示例可以看出，本文提出的改進的 BM 算法比原算法比較次數(shù)提高了一次，從而提高了模式匹配的速度。4.2 改進的 Wu-Manber 算法分析通過分析Wu-Manber 算法，可以看出以下不足：(1) 隨著模

14、式串數(shù)量的增加，許多模式串所擁有相同后綴的概率也會增加，即所構建的 HASH 表相應表項內的指針所指向的模式串鏈表長度增加，從而增加查找 PREFIX 表的次數(shù)，這樣必然使匹配過程需要更多的比較次數(shù)。(2) 如果模式串最小長度 m 的值很小，則移動距離的值也就不可能很大，對匹配效率也有很大影響，從而影響算法性能。改進的 Wu-Manber 算法 ：1) 改進 Wu-Manber 算法的思想通過對 Wu-Manber 算法的分析，由于 Wu-Manber 算法中 PREFIX 表中存儲的是模式串前綴hash 值，HASH 表中存儲的是模式串后綴模式串的 hash 值，在這種情況下 PREFIX

15、表與 HASH表功能類似，因此，在改進的 Wu-Manber 算法中可以取消 PREFIX 表的構建，那么修改 HASH 表的結構，將其分成兩個區(qū)。2) 改進 Wu-Manber 算法的設計步驟(1) 首先選取模式串中最小模式串的長度 m ；(2)確定 B 的值 ,B 的值取 2 或 3 ；(3) 構建 SHIFT 表 ：與 Wu-Manber 算法的 SHIFT 表構建方法相同 ；(4)構建 HASH 表 ：這一步很關鍵，現(xiàn)在把 HASH 表分成左右兩個半?yún)^(qū)，左半?yún)^(qū)存儲原算法中的 hash 值，右半?yún)^(qū)用來存儲原算法 PREFIX 表的值。3) 改進 Wu-Manber 算法的匹配過程(1)

16、計算 SHIFT 表。(2) 計算當前文本窗口的前綴和后綴，將其hash 值分別存儲在 HASH 表的左右半?yún)^(qū)。(3) 整體開始匹配從左向右，根據(jù) SHIFT 表進行掃描，匹配從文本串左端的第 m 個字符開始，對模式的匹配從右向左進行，每次掃描字符塊 B 個字符。如果移動距離大于 0，則將模式串向后移動SHIFT 表所指示值的距離，如果移動距離等于 0則轉入 (4)。(4) 查看此后綴是否在 HASH 表的左半?yún)^(qū)，如果存在 , 就再查找 HASH 表的右半?yún)^(qū)，查看右半?yún)^(qū)是否有與其匹配的字符串，如果有則完全匹配，如果沒有與其匹配的字符串，說明沒有模式串滿足這樣的條件，則返回 3)，直到比較結束。

17、如此看來，改進的 Wu-Manber 算法比原來省去了 PREFIX 表的構建，它是通過把 HASH 表分成左右半?yún)^(qū)，代替 PREFIX 表的功能，從而節(jié)省系統(tǒng)開銷空間，提高了算法的查找匹配效率，舉例分析改進的 Wu-Manber 算法如下 ：假設在文本串“Each of us will have abetter tomorrow”中匹配模式串 have 和 better。取 B=2，匹配步驟如下 ：步驟 1 ：計算 SHIFT 表。計算每個塊字符與匹配窗口內模式串串尾的距離，即當該塊字符在文本中出現(xiàn)時的轉移距離。其他未出現(xiàn)在匹配窗口內的塊字符的 SHIFT 表值均為 m-B+1=4-2+1=

18、3。SHIFT 表如表 1 所示。步驟 2 ：計算 HASH 表。( 左半?yún)^(qū)存儲原算法中 HASH 表的值，右半?yún)^(qū)存儲原算法中 PREFIX表的值 ) 如表 2 所示。步驟 3 ：算法匹配過程 ：文本串為“Each ofus will have a better tomorrow”首先從右向左掃描文本串的前端的 4 個字符，因為取 B 為 2，就通過此 4 個字符的后 2 位來查找 SHIFT 表，發(fā)現(xiàn)ch 在 SHIFT 表的移動距離為 3，那么就向后移動3 個距離，接下來考察 of，發(fā)現(xiàn) of 在 SHIFT 表的移動距離也為 3，以此往下匹配，直到發(fā)現(xiàn) ve的移動距離為 0，轉入 HASH 表的左半?yún)^(qū)，發(fā)現(xiàn)有 have，然后再計算 have 在 HASH 表右半?yún)^(qū)的hash 值，發(fā)現(xiàn)也有 have，因此判斷完全匹配，剩余文本匹配也即如此。5 結論