基于Snort入侵檢測(cè)的后綴搜索算法的研究與改進(jìn)

◆胡朝舉 石 倩

（華北電力大學(xué)（保定）控制與計(jì)算機(jī)工程學(xué)院 河北 071000）

基于Snort入侵檢測(cè)的后綴搜索算法的研究與改進(jìn)

◆胡朝舉 石 倩

（華北電力大學(xué)（保定）控制與計(jì)算機(jī)工程學(xué)院 河北 071000）

Snort是基于規(guī)則匹配的入侵檢測(cè)系統(tǒng)，提高規(guī)則匹配的速度至關(guān)重要。本文通過(guò)對(duì)Snort下基于后綴搜索的入侵檢測(cè)算法BM算法、WM算法的研究，對(duì)WM算法進(jìn)行了改進(jìn)，將模式集合根據(jù)長(zhǎng)度分為兩部分，每個(gè)模式串建立子移動(dòng)表。試驗(yàn)結(jié)果表明，改進(jìn)的算法提高了Snort的入侵檢測(cè)效率。

入侵檢測(cè)；模式匹配；WM算法

0 引言

Snort入侵檢測(cè)系統(tǒng)是目前使用最廣的開(kāi)源入侵檢測(cè)系統(tǒng)之一，具有良好的跨平臺(tái)性，并提供豐富的報(bào)警機(jī)制。Snort 的檢測(cè)采用的是模式匹配策略。模式匹配過(guò)程是系統(tǒng)運(yùn)行的主要過(guò)程，是系統(tǒng)主要的性能瓶頸。針對(duì)此問(wèn)題已有很多學(xué)者做了大量研究，文獻(xiàn)[3]對(duì)BM算法做了改進(jìn)，去除了傳統(tǒng)的好后綴規(guī)則，改進(jìn)了壞字符規(guī)則。文獻(xiàn)[4]提出一種基于隨機(jī)指紋模型的多模式匹配方法。文獻(xiàn)[5]基于BM算法的優(yōu)點(diǎn)改進(jìn)AC算法，提出了多目標(biāo)AC-BM算法，大大降低重復(fù)搜索文本串的次數(shù)。文獻(xiàn)[6]把AC算法和BMH算法結(jié)合，只保留壞字符規(guī)則，最大移動(dòng)距離為最短模式串長(zhǎng)度。文獻(xiàn)[7]提出了一種改進(jìn)的WM算法，減少了重復(fù)比較次數(shù)。本文通過(guò)對(duì)后綴搜索算法的研究，對(duì)WM算法進(jìn)行改進(jìn)，提高了Snort的入侵檢測(cè)的效率。

1 模式字符串匹配算法

多模式匹配問(wèn)題可表示為求解集合：

后綴搜索是在搜索窗口內(nèi)，模式匹配的是從右向左的搜索最長(zhǎng)公共后綴?；诤缶Y搜索的算法經(jīng)典的有BM算法、WM算法。

2 Boyer-Moore 算法

BM 算法中匹配失敗時(shí)，用兩種機(jī)制來(lái)確定模式串向右移動(dòng)的距離：壞字符機(jī)制和好后綴機(jī)制。

2.1 壞字符機(jī)制

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

（2）導(dǎo)致不匹配的字符在模式串P中，則移動(dòng)模式串最短距離使可匹配字符與相應(yīng)文本T字符對(duì)應(yīng)。

2.2 好后綴機(jī)制

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

（2）好后綴的最大子串在模式串中存在，那么好后綴最大子串和T對(duì)應(yīng)子串對(duì)齊匹配。

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

BM算法的移動(dòng)距離為好后綴機(jī)制和壞字符機(jī)制的最大值。

3 Wu-Manber（WM）算法及改進(jìn)

WM算法繼承了 BM 算法中的壞字符機(jī)制，但是WM算法依據(jù)長(zhǎng)度為 B的字符塊進(jìn)行跳躍。

3.1 預(yù)處理過(guò)程

預(yù)處理階段建立三張表移動(dòng)表（Shift Table）、哈希表（Hash Table）和前綴表（Prefix Table）來(lái)移動(dòng)搜索窗口。

（1）建立移動(dòng)表（Shift Table）

記最小模式串長(zhǎng)度m，只考慮每個(gè)模式串的前m個(gè)字符。對(duì)m個(gè)字符中后B個(gè)字符創(chuàng)建一個(gè)移動(dòng)表。

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

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

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

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

3.2 搜索階段掃描過(guò)程

（3）計(jì)算文本當(dāng)前位置前m位與前m-1位前綴的哈希值，記為text_prefix。

圖1 WM算法搜索示意圖

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

3.3 改進(jìn)

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

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)源

數(shù)據(jù)源采用的是國(guó)際認(rèn)可的麻省理工學(xué)院林肯實(shí)驗(yàn)室提供的DARPA2000[8]入侵檢測(cè)數(shù)據(jù)集。該數(shù)據(jù)集包括DoS、R2L、U2R、Probe和Data5大類(lèi)58種攻擊方式。

4.2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為win7操作系統(tǒng)、2G內(nèi)存、snort-2.9.1、Cygwin、WinPcap_4_1_2、snortrules-snapshot-2.9.1.tar.gz。

Cygwin提供編譯Snort所需要的應(yīng)用程序bison、flex、sed。WinPcap是數(shù)據(jù)包捕獲器，為Snort捕獲數(shù)據(jù)包。

4.3 實(shí)驗(yàn)方法

以補(bǔ)丁的形式將算法加入到Snort中，在配置文件中將匹配方法設(shè)置為WM算法、改進(jìn)算法WM-NEW及默認(rèn)算法AC-SPLIT算法。Snort掃描入侵檢測(cè)數(shù)據(jù)集，比較WM算法、改進(jìn)算法、AC-SPLIT算法在規(guī)則數(shù)目不同時(shí)的時(shí)間，以及在規(guī)則數(shù)目不同的占用內(nèi)存。規(guī)則數(shù)目為2800，模式串最小長(zhǎng)度不同下，算法的運(yùn)行時(shí)間對(duì)比。規(guī)則數(shù)目是除去對(duì)數(shù)據(jù)集的解碼規(guī)則和預(yù)處理規(guī)則后的數(shù)目。

4.4 實(shí)驗(yàn)結(jié)果

在規(guī)則數(shù)目不同情況下，各算法匹配時(shí)間，以1000ms為單位。

表1 算法匹配時(shí)間（×1000ms）

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

圖2 各算法規(guī)則數(shù)目下時(shí)間對(duì)比

規(guī)則數(shù)目不同情況下，各算法占用內(nèi)存測(cè)試結(jié)果，以MB為單位。

表2 算法占用內(nèi)存（MB）

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

圖3 各算法內(nèi)存對(duì)比

規(guī)則數(shù)目為2800，模式串最小長(zhǎng)度不同下，算法的運(yùn)行時(shí)間如下圖4所示。

圖4 算法最短模式串長(zhǎng)度下時(shí)間對(duì)比

通過(guò)實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)后的算法匹配效率能有了很大提高，規(guī)則數(shù)目越多，優(yōu)勢(shì)越明顯。且算法平穩(wěn)增長(zhǎng)時(shí)間性能受影響較小。模式串長(zhǎng)度增大時(shí)，新算法匹配效率提高較大。新算法的內(nèi)存占用量雖然比WM算法大，但仍小于AC算法，在可接受范圍，模式串越多約明顯。

5 結(jié)束語(yǔ)

本文研究了Snort中兩個(gè)經(jīng)典后綴搜索算法，并對(duì)WM算法進(jìn)行了改進(jìn)，并將其AC-SPLIT算法、WM算法進(jìn)行了對(duì)比，結(jié)果表明改進(jìn)后的算法檢測(cè)效率提高。同時(shí)，改進(jìn)后的算法在內(nèi)存占用方面仍有改進(jìn)的空間，更加有效地為Snort所使用。

[1]劉積芬.網(wǎng)絡(luò)入侵檢測(cè)關(guān)鍵技術(shù)研究[D].上海：東華大學(xué)，2013.

[2]劉鑫.網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中模式匹配算法的應(yīng)用研究[D].大連海事大學(xué)，2013.

[3]王友釗，黃冬.一種提高系統(tǒng)搜索效率的BM改進(jìn)算法[J].計(jì)算機(jī)工程，2014．

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

[5]王正才，許道云，王曉峰.基于自動(dòng)機(jī)并操作的多目標(biāo)AC-BM算法[J].計(jì)算機(jī)科學(xué)，2013.

[6]陸琳琳，田野.基于確定有限狀態(tài)自動(dòng)機(jī)的改進(jìn)多模式匹配算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2013.

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

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