基于Snort入侵檢測的后綴搜索算法的研究與改進

◆胡朝舉 石 倩

（華北電力大學（保定）控制與計算機工程學院 河北 071000）

基于Snort入侵檢測的后綴搜索算法的研究與改進

◆胡朝舉 石 倩

（華北電力大學（保定）控制與計算機工程學院 河北 071000）

Snort是基于規則匹配的入侵檢測系統，提高規則匹配的速度至關重要。本文通過對Snort下基于后綴搜索的入侵檢測算法BM算法、WM算法的研究，對WM算法進行了改進，將模式集合根據長度分為兩部分，每個模式串建立子移動表。試驗結果表明，改進的算法提高了Snort的入侵檢測效率。

入侵檢測；模式匹配；WM算法

0 引言

Snort入侵檢測系統是目前使用最廣的開源入侵檢測系統之一，具有良好的跨平臺性，并提供豐富的報警機制。Snort 的檢測采用的是模式匹配策略。模式匹配過程是系統運行的主要過程，是系統主要的性能瓶頸。針對此問題已有很多學者做了大量研究，文獻[3]對BM算法做了改進，去除了傳統的好后綴規則，改進了壞字符規則。文獻[4]提出一種基于隨機指紋模型的多模式匹配方法。文獻[5]基于BM算法的優點改進AC算法，提出了多目標AC-BM算法，大大降低重復搜索文本串的次數。文獻[6]把AC算法和BMH算法結合，只保留壞字符規則，最大移動距離為最短模式串長度。文獻[7]提出了一種改進的WM算法，減少了重復比較次數。本文通過對后綴搜索算法的研究，對WM算法進行改進，提高了Snort的入侵檢測的效率。

1 模式字符串匹配算法

多模式匹配問題可表示為求解集合：

后綴搜索是在搜索窗口內，模式匹配的是從右向左的搜索最長公共后綴。基于后綴搜索的算法經典的有BM算法、WM算法。

2 Boyer-Moore 算法

BM 算法中匹配失敗時，用兩種機制來確定模式串向右移動的距離：壞字符機制和好后綴機制。

2.1 壞字符機制

（1）導致不匹配的字符不在模式串P中，模式串向右取得最大移動距離m。

（2）導致不匹配的字符在模式串P中，則移動模式串最短距離使可匹配字符與相應文本T字符對應。

2.2 好后綴機制

（1）好后綴在模式串中存在，那么好后綴和T中已匹配對齊匹配。

（2）好后綴的最大子串在模式串中存在，那么好后綴最大子串和T對應子串對齊匹配。

（3）好后綴在模式串中并不存在，則移動距離為m。

BM算法的移動距離為好后綴機制和壞字符機制的最大值。

3 Wu-Manber（WM）算法及改進

WM算法繼承了 BM 算法中的壞字符機制，但是WM算法依據長度為 B的字符塊進行跳躍。

3.1 預處理過程

預處理階段建立三張表移動表（Shift Table）、哈希表（Hash Table）和前綴表（Prefix Table）來移動搜索窗口。

（1）建立移動表（Shift Table）

記最小模式串長度m，只考慮每個模式串的前m個字符。對m個字符中后B個字符創建一個移動表。

（2）建立哈希表（Hash Table）

發生匹配時，為了確定匹配的字符串，避免和模式字符串全部比較，使用哈希技術減少比較的次數。計算B個字符的哈希值用作為哈希表的索引，哈希表的值就是該B個字符所在模式字符串的索引。

（3）建立前綴表（Prefix Table）

所有的有相同后綴的模式字符串在哈希表中有相同的入口值。當文本中這樣一個后綴時，當發現Shift值為0，不得不單獨檢查所有帶有這個后綴的模式字符串看它是否和T匹配，因此需要建立前綴表。匹配完所有模式串的B個字符和前綴表中的前B’個字符，如果匹配成功，則讓整個模式串去和文本進行逐字符匹配。

3.2 搜索階段掃描過程

（3）計算文本當前位置前m位與前m-1位前綴的哈希值，記為text_prefix。

圖1 WM算法搜索示意圖

分析WM算法發現，存在缺點：（1）如果最短模式串非常短，那么m的值就會非常小，算法最多只能跳躍m，此時算法的效率就變得非常低。（2）Shift表為0時，需要進行精確匹配，而在WM算法中使用的精確匹配算法是效率較低的蠻力算法。

3.3 改進

對于這兩個缺點，可以改進：（1）將特征集合分為長短兩個特征集合來處理。通過分析發現，找到合適的分割長度，從而可以取得較好的匹配性能。（2）為每個模式串建立一個sub-shift表，其大小與模式串相同。相應的sub-shift表項中存放當與本模式串匹配失敗時，搜索窗口向右移動字符數。搜索過程中在精確匹配全部完成時，我們根據各字符串sub-shift表值的綜合情況，找到文本可以安全地向右跳躍的字符數。

4 實驗

4.1 數據源

數據源采用的是國際認可的麻省理工學院林肯實驗室提供的DARPA2000[8]入侵檢測數據集。該數據集包括DoS、R2L、U2R、Probe和Data5大類58種攻擊方式。

4.2 實驗環境

實驗環境為win7操作系統、2G內存、snort-2.9.1、Cygwin、WinPcap_4_1_2、snortrules-snapshot-2.9.1.tar.gz。

Cygwin提供編譯Snort所需要的應用程序bison、flex、sed。WinPcap是數據包捕獲器，為Snort捕獲數據包。

4.3 實驗方法

以補丁的形式將算法加入到Snort中，在配置文件中將匹配方法設置為WM算法、改進算法WM-NEW及默認算法AC-SPLIT算法。Snort掃描入侵檢測數據集，比較WM算法、改進算法、AC-SPLIT算法在規則數目不同時的時間，以及在規則數目不同的占用內存。規則數目為2800，模式串最小長度不同下，算法的運行時間對比。規則數目是除去對數據集的解碼規則和預處理規則后的數目。

4.4 實驗結果

在規則數目不同情況下，各算法匹配時間，以1000ms為單位。

表1 算法匹配時間（×1000ms）

表示在折線圖中，如下圖2所示。

圖2 各算法規則數目下時間對比

規則數目不同情況下，各算法占用內存測試結果，以MB為單位。

表2 算法占用內存（MB）

表示在折線圖中，如下圖3所示。

圖3 各算法內存對比

規則數目為2800，模式串最小長度不同下，算法的運行時間如下圖4所示。

圖4 算法最短模式串長度下時間對比

通過實驗結果可以看出，改進后的算法匹配效率能有了很大提高，規則數目越多，優勢越明顯。且算法平穩增長時間性能受影響較小。模式串長度增大時，新算法匹配效率提高較大。新算法的內存占用量雖然比WM算法大，但仍小于AC算法，在可接受范圍，模式串越多約明顯。

5 結束語

本文研究了Snort中兩個經典后綴搜索算法，并對WM算法進行了改進，并將其AC-SPLIT算法、WM算法進行了對比，結果表明改進后的算法檢測效率提高。同時，改進后的算法在內存占用方面仍有改進的空間，更加有效地為Snort所使用。

[1]劉積芬.網絡入侵檢測關鍵技術研究[D].上海：東華大學，2013.

[2]劉鑫.網絡入侵檢測系統中模式匹配算法的應用研究[D].大連海事大學，2013.

[3]王友釗，黃冬.一種提高系統搜索效率的BM改進算法[J].計算機工程，2014．

[4]張宏莉，徐東亮，梁敏，劉宇峰.海量模式高效匹配方法研究[J].電子學報，2014.

[5]王正才，許道云，王曉峰.基于自動機并操作的多目標AC-BM算法[J].計算機科學，2013.

[6]陸琳琳，田野.基于確定有限狀態自動機的改進多模式匹配算法研究[J].計算機應用與軟件，2013.

[7]蔣曉鴿，武小年，張昭.基于后綴WM匹配算法的改進算法[J].計算機與數字工程，2013.

[8]Laboratory Lincoln.MIT Lincoln Laboratory Inf-ormati on Systems Technology[EB/OL].http：//www.ll.mit.edu/ideval /data/2000data.html.