曾傳璜，黃侃

江西理工大學(xué)信息工程學(xué)院，江西贛州 341000

提高Snort規(guī)則匹配速度新方法的研究與實(shí)現(xiàn)

曾傳璜，黃侃

江西理工大學(xué)信息工程學(xué)院，江西贛州 341000

ZENG Chuanhuang,HUANG Kan.Research and implementation of new method on increasing speed of rule-matching in Snort.Computer Engineering and Applications,2014,50（22）：102-105.

1 引言

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)安全問(wèn)題在互聯(lián)網(wǎng)中越來(lái)越嚴(yán)峻，入侵檢測(cè)系統(tǒng)（Network Intrusion Detection System，NIDS）在網(wǎng)絡(luò)安全扮演著越來(lái)越重要的角色，并且已經(jīng)被廣泛應(yīng)用于各種網(wǎng)絡(luò)環(huán)境中。Snort[1]是一個(gè)開(kāi)源的、具有高匹配精確度的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)。對(duì)于每一種入侵行為，Snort系統(tǒng)按照檢測(cè)規(guī)則[2]，將捕獲的數(shù)據(jù)包與檢測(cè)規(guī)則進(jìn)行匹配，若匹配成功，則認(rèn)為構(gòu)成入侵行為，將數(shù)據(jù)包信息反饋出來(lái)。

2 提高Snort規(guī)則匹配速度

改進(jìn)Snort系統(tǒng)使用的BM[3]算法（或BM改進(jìn)算法），能夠有效提高Snort規(guī)則匹配速度，下面介紹BM及BM改進(jìn)算法。

2.1 BM算法

1977年，Boyer和Moore提出了BM算法（Boyer-Moore）。BM算法的基本思想：采用兩種啟發(fā)式方法：壞字符啟發(fā)式方法（Badchar）好后綴啟發(fā)式方法（Goodsuffix）。

壞字符啟發(fā)式方法（Badchar）：算法在匹配過(guò)程中，若某個(gè)字符x不匹配：（1）如果字符x在模式串P中沒(méi)有出現(xiàn)，那么移動(dòng)至x字符之后。（2）如果x在模式串P中出現(xiàn)，則移動(dòng)至與x字符對(duì)齊進(jìn)行再匹配。

好后綴啟發(fā)式方法（Goodsuffix）：若發(fā)現(xiàn)某個(gè)字符不匹配的同時(shí)，但有部份字符匹配，利用已經(jīng)匹配成功的部份最長(zhǎng)子串，將模式串中的匹配最長(zhǎng)前綴或后綴字符串的相應(yīng)位置對(duì)齊。

兩種方法都產(chǎn)生了一個(gè)移動(dòng)距離，BM算法取較大的一個(gè)作為移動(dòng)距離。BM算法是繼BF算法和KMP算法之后提出的，相比BF算法和KMP算法，是一種具有較高匹配效率的算法，可以達(dá)到接近線性的時(shí)間復(fù)雜度。但是在實(shí)際應(yīng)用中，badchar函數(shù)應(yīng)用次數(shù)遠(yuǎn)遠(yuǎn)超過(guò)goodsuffix函數(shù)，goodsuffix函數(shù)將會(huì)制約BM算法的效率。

2.2 BMH算法

1980年，Horspool提出改進(jìn)的BM算法，即BMH算法[4]。Horspool指出，在實(shí)際應(yīng)用中，badchar函數(shù)應(yīng)用的次數(shù)遠(yuǎn)遠(yuǎn)超過(guò)goodsuffix函數(shù)，因此badchar函數(shù)起主導(dǎo)作用；BMH算法只考慮badchar函數(shù)，在實(shí)際應(yīng)用中也取得顯著效果。BMH算法舍棄了難以理解又較難實(shí)現(xiàn)的goodsuffix函數(shù)，只考慮badchar函數(shù)，有效提高了算法的效率，而且理論上能夠達(dá)到與BM算法相同的時(shí)間復(fù)雜度。

2.3 BMHS算法

1990年，在BMH算法的基礎(chǔ)上，Sunday提出了改進(jìn)的BMHS算法[5]（Boyer-Moore-Horspool-Sunday），其主要改進(jìn)思想是：計(jì)算badchar函數(shù)時(shí)，考慮模式串最后一位字符對(duì)應(yīng)的文本串字符在模式串中出現(xiàn)的情況，即利用下一個(gè)字符來(lái)決定移動(dòng)距離。具體匹配過(guò)程如圖1和圖2所示。表1演示了BMHS算法的移動(dòng)過(guò)程。BMHS算法是在BM算法和BMH算法的基礎(chǔ)上改進(jìn)的，通常情況下，BMHS算法效率是最高的，匹配速度是最快的，只有當(dāng)T[k+1]字符出現(xiàn)在模式串P中時(shí)，算法效率不如BMH算法。

圖1 T[k+1]出現(xiàn)在P中時(shí)移動(dòng)情況

圖2 T[k+1]不出現(xiàn)在P中時(shí)移動(dòng)情況

3 改進(jìn)的BM算法

3.1 算法改進(jìn)的思路

改進(jìn)BM算法，可以從以下三個(gè)方面思考：

（1）增大窗口移動(dòng)的最大距離。BM算法、BMH算法、BMHS算法及其他一些改進(jìn)算法，當(dāng)首次匹配失敗時(shí)，窗口即要移動(dòng)一個(gè)最大距離；按照字符等概率原則，在實(shí)際情況下，移動(dòng)一個(gè)最大距離的概率是比較高的，因此，增大窗口移動(dòng)的最大距離，能夠有效提高算法的效率。

（2）保證移動(dòng)最大的安全距離。當(dāng)匹配失敗時(shí)，模式串能否移動(dòng)一個(gè)最大的安全距離是算法改進(jìn)成功與否的關(guān)鍵因素。提高算法性能，盡可能地保證匹配失敗時(shí)每一次都能夠移動(dòng)最大安全距離，就能夠有效減少字符比較次數(shù)，提高模式匹配的效率。本方法綜合考慮多種情況，盡量保證算法在匹配過(guò)程中能夠移動(dòng)一個(gè)最大的安全距離。

（3）BMN[6]算法思想的啟發(fā)。BMN算法是在匹配失敗時(shí)，考慮模式串P最右端字符對(duì)應(yīng)文本串T中的字符，將此字符與文本串T中的前一字字符和后一個(gè)字符組合，分析雙字符組合在P中的出現(xiàn)情況來(lái)決定右移距離。本文受BMN算法啟發(fā)，采用雙字符序列檢測(cè)方法，并結(jié)合BMH算法，提出了一種改進(jìn)的BM算法。雙字符[7]序列檢測(cè)法，即在匹配過(guò)程中，將兩個(gè)字符結(jié)合為一個(gè)整體，與模式串先匹配，以減少模式串與字符串的比較次數(shù)，增大窗口移動(dòng)的最大距離的一種方法。在本方法中，窗口向右移動(dòng)的最大距離將達(dá)到m+2。

3.2 改進(jìn)算法的基本思想

綜合考慮以上三個(gè)方面，提出一種改進(jìn)的BM算法。該算法采用雙字符序列檢測(cè)法。首先利用BMH算法確定出一個(gè)位移量skip1，繼而將T[k+1]T[k+2]組合，分為兩種情況討論，計(jì)算出另一個(gè)位移量skip2，再與skip1相比，最后確定移動(dòng)距離，算法實(shí)現(xiàn)過(guò)程中，盡量確保匹配窗口移動(dòng)最大的安全距離。實(shí)驗(yàn)驗(yàn)證，模式匹配過(guò)程中，出現(xiàn)此方法最大位移的概率較高，且此方法能夠提高算法效率。該算法的最大的移動(dòng)距離可以達(dá)到m+2。

首先設(shè)立一個(gè)數(shù)組G[8]，數(shù)組G用來(lái)標(biāo)記模式串中

表1 BMHS算法移動(dòng)過(guò)程

該算法的核心思想描述如下：當(dāng)T[i+j]≠P[i]時(shí)，表示這一輪匹配失敗，首先利用模式串P中最右端字符所對(duì)應(yīng)該的文本串字符T[k]在P中的出現(xiàn)情況，根據(jù)BMH算法，記錄下此時(shí)應(yīng)該移動(dòng)的距離，倘若T[k]字符未出現(xiàn)在模式串P中，則可移動(dòng)距離為skip1=m，若T[k]出現(xiàn)在模式串P中，則計(jì)算出可移動(dòng)新的移動(dòng)距離skip1，可以肯定此時(shí)skip1≤m；繼而將T[k+1]T[k+2]結(jié)合為一個(gè)組合，記為H(y)，將H(y)與模式串P進(jìn)行匹配，分為以下幾種情況討論：

（1）若P中沒(méi)有與字符組合H(y)匹配的字符組合時(shí)，將H(y)與模式串P的首字符P[1]進(jìn)行比對(duì)，若H(y)中不含P[1]，可以確定，將模式串移動(dòng)什么位置與H(y)對(duì)齊，都不會(huì)匹配，skip2的值為m+2；若H(y)含有P[1]，需分兩種情況討論：T[k+1]=P[1]，skip2的值為m+2，T[k+2]=P[1]，skip2的值為m+1。

（2）若P中有與H(y)匹配的字符組合時(shí)，分為以下兩種情況討論：

①H(y)不含模式串P的首字符P[1]，考慮已匹配字符T[k]的G(x)值，若G(x)=1，說(shuō)明字符T[k]只在模式串P最后出現(xiàn)一次且只一次，不管將模式串移動(dòng)多少位置與H(y)對(duì)齊，也不會(huì)匹配，skip2為m+2。

②考慮T[k]字符的G(x)值，若G(x)=0，則需要根據(jù)H(y)計(jì)算出應(yīng)該移動(dòng)的距離，產(chǎn)生一個(gè)新的skip2值，與skip1進(jìn)行對(duì)比，若skip1＞skip2，則移動(dòng)skip1；若skip1＜skip2，則移動(dòng)skip2；若skip1=skip2，則移動(dòng)skip1。

算法在實(shí)現(xiàn)過(guò)程中需構(gòu)造一個(gè)單字符檢測(cè)表skip1和一個(gè)雙字符序列檢測(cè)表skip2，skip1主要用于算法的第一步，利用BMH算法思想計(jì)算出的位移值skip1，skip2為|Σ|×|Σ|的二維表結(jié)構(gòu)，用于與模式串P進(jìn)行匹配對(duì)比，具體公式如下：每個(gè)字符出現(xiàn)的次數(shù)，數(shù)組G有利于算法的實(shí)現(xiàn)，在匹配過(guò)程中減少不必要的匹配，增大最大距離出現(xiàn)的概率。如下所示：

雙字符序列檢測(cè)表skip2記錄文本串字符T[k+1]T[k+2]在模式串中的存在情況，若在模式串中存在，skip2的值為1；若不存在，skip2的值為0。

算法偽代碼如下：

3.3 BM改進(jìn)算法實(shí)例

以2.3節(jié)中的BMHS算法實(shí)例中的文本串T和模式串P進(jìn)行匹配：

（1）第一次比較：P[6]=h與T[6]=h匹配，P[5]=c與T[5]=a不匹配，此時(shí)T[6]=h，G（h）=1，skip1=6；組合字符H（y）=”wh”，模式串P中沒(méi)有與H（y）中相匹配的字符，且不含首字符”s”，skip2=8。skip2＞skip1，移動(dòng)距離為8。

（2）第二次比較：P[6]=h與T[6]=h匹配，P[5]=c與T[5]=r不匹配，此時(shí)T[6]=h，G（h）=1，skip1=6；組合字符H（y）=”ch”，與模式串P有相匹配字符已匹配字符”h”的G（h）=1，且不含首字符”s”，skip2=8。skip2＞skip1，移動(dòng)距離為8。

（3）第三次比較：P[6]=h與T[6]=d不匹配，字符”d”未出現(xiàn)模式串中，skip1=6；組合字符H（y）=”er”，在模式串沒(méi)有匹配字符，且不含首字符”s”，skip2=8。skip2＞skip1，移動(dòng)距離為8。

表2 改進(jìn)的BM算法移動(dòng)過(guò)程

（4）第四次比較：匹配按照P[6]，T[6]，P[5]，T[5]，P[4]，T[4]，P[3]，T[3]，P[2]，T[2]，P[1]，T[1]順序進(jìn)行，匹配成功。

在上述比較過(guò)程中，窗口移動(dòng)次數(shù)為4次，匹配次數(shù)也有所減少，該算法效率較BMHS算法有所增加。

4 算法的性能測(cè)試及結(jié)果分析

構(gòu)造雙字符序檢測(cè)跳躍表skip2將產(chǎn)生的二維空間，使算法的時(shí)間復(fù)雜度為平方階層O(Σ2)，算法的預(yù)處理時(shí)間復(fù)雜度為O(Σ2)，空間復(fù)雜度為O(Σ)?？紤]窗口移動(dòng)最大距離和移動(dòng)較大距離的概率對(duì)算法的影響，最好情況下的時(shí)間復(fù)雜度能夠接近亞線性階層，最壞情況下時(shí)間復(fù)雜度為O(m(n-m))。在模式匹配中，有這樣的定理：沒(méi)有算法的計(jì)算復(fù)雜度比BM算法更優(yōu)[9]。根據(jù)以上綜合分析，改進(jìn)的算法并不希望比BM算法復(fù)雜更低，相比BM算法，該算法的平均時(shí)間復(fù)雜度并不是很高，平均性能優(yōu)于BM算法及BMH算法、BMHS算法。

綜合比較匹配過(guò)程中的字符比較次數(shù)、窗口比較次數(shù)和匹配所花費(fèi)時(shí)間，對(duì)BM、BMH、BMHS和改進(jìn)的BM算法進(jìn)行測(cè)試。

實(shí)驗(yàn)首先使用隨機(jī)的100個(gè)字符kajfieanygjbhawio gjeaengeagjwgqhklaiweakjgoawotoasgjadkjafieakdfifueikv jaisdifasqieanpaetnvjeaechlda，分別用BM、BMH、BMHS和改進(jìn)的BM算法測(cè)試，統(tǒng)計(jì)模式串se，sea，sear，searc，search，searchi，searchin，searching用不同算法匹配時(shí)字符比較次數(shù)和窗口移動(dòng)次數(shù)，結(jié)果如圖3和圖4所示。

圖3 四種算法字符比較次數(shù)對(duì)比

圖4 四種算法窗口移動(dòng)次數(shù)對(duì)比

另測(cè)試不同算法模式匹配時(shí)所花費(fèi)時(shí)間對(duì)比，在下列的實(shí)驗(yàn)環(huán)境下進(jìn)行。內(nèi)存：2 GB；主頻：Intel雙核；操作系統(tǒng)：Windows XP；Snort版本：2.9.1；程序?qū)崿F(xiàn)使用C++語(yǔ)言，Visual C++6.0編譯軟件；結(jié)果察看使用Kiwi日志文件工具。實(shí)驗(yàn)分別用四種算法BM、BMH、BMHS和改進(jìn)的BM算法，對(duì)服務(wù)器上隨機(jī)的同樣數(shù)量的數(shù)據(jù)包[10]進(jìn)行測(cè)試，所花費(fèi)的時(shí)間如圖5所示。

圖5 四種算法消耗時(shí)間對(duì)比

通過(guò)觀察可知，改進(jìn)的BM算法比BM、BMH、BMHS在窗口移動(dòng)次數(shù)上有所減少，時(shí)間花費(fèi)上也更少，由此可知，BM改進(jìn)算法更優(yōu)越。BM改進(jìn)算法能夠增大最大的移動(dòng)距離，減少移動(dòng)次數(shù)以及增大最大距離出現(xiàn)的概率。改進(jìn)后的Snort規(guī)則匹配速度較以前有一定的提高，說(shuō)明算法的改進(jìn)是成功的，會(huì)對(duì)Snort系統(tǒng)今后的發(fā)展有所幫助。

5 小結(jié)

Snort系統(tǒng)憑借其自身的優(yōu)勢(shì)，在現(xiàn)代網(wǎng)絡(luò)安全中得到越來(lái)越廣泛的應(yīng)用，提高其規(guī)則匹配的速度是研究的熱點(diǎn)。本文提出的改進(jìn)算法，應(yīng)用于Snort系統(tǒng)中，能夠提高Snort系統(tǒng)的效率，對(duì)于Snort系統(tǒng)及其他入侵檢測(cè)系統(tǒng)都有可操作之處。

[1]Koziol J.Intrusion detection with Snort[M].吳溥峰，孫默，許誠(chéng)，譯.北京：機(jī)械工業(yè)出版社，2005：31-35.

[2]任曉峰，董占球.提高Snort規(guī)則匹配速度方法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2003，23（4）：59-61.

[3]Boyer R S，Moore J S.A fast string searching algorithm[J]. Communications of the ACM，1977，20：762-772.

[4]Horspool R N.Practical fast searching in strings[J].Software Practice&Experience，1980，10（6）：501-506.

[5]Sunday D M.A Very fast substring search algorithm[J]. Communication of the ACM，1990，33（8）：132-142.

[6]何畏，汪榮貴，查全民.一種新的快速移動(dòng)單模式匹配算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（5）：665-669.

[7]王浩，張霖，張慶.基于雙字符序檢測(cè)的BM模式匹配改進(jìn)算法[J].計(jì)算機(jī)工程與科學(xué)，2012，34（3）：113-117.

[8]張娜，張劍.一個(gè)快速的字符串模式匹配改進(jìn)算法[J].微電子學(xué)與計(jì)算機(jī)，2007，24（4）：102-105.

[9]李雪寶，劉寶旭.字符串匹配技術(shù)研究[J].計(jì)算機(jī)工程，2004，30（22）：24-26.

[10]王杰，王同軍，孫珂珂.提高Snort規(guī)則匹配速度的新方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（28）：109-111.

ZENG Chuanhuang,HUANG Kan

IDS plays an increasingly important role in network security sector,Snort is one of IDS with open source,the theme we continuously researching improves the efficiency of the matching algorithm,so that IDS can reduce running time.The key to improve the efficiency of the matching algorithm is to increase the maximum distance and ensure moving the biggest safe distance.The improved algorithm is based on the BM algorithm and adopted the double characters sequence detection method.It results the maximum distance add tom+2and can move the biggest safe distance each time.Finally, through the experiment,when this algorithm applied to Snort,it can reduce times of comparing character and mobile windows. At the same time,it can improve the efficiency of Snort.

system of Snort;improved BM algorithm;maximum distance

入侵檢測(cè)系統(tǒng)在網(wǎng)絡(luò)安全中扮演著越來(lái)越重要的角色，Snort作為一個(gè)開(kāi)源的入侵檢測(cè)系統(tǒng)，改進(jìn)其使用的匹配算法，使其能夠減少運(yùn)行時(shí)間，提高效率是不斷研究的主題。對(duì)于模式匹配算法，增大其最大移動(dòng)距離和保證其能夠移動(dòng)最大的安全距離是提高算法效率的關(guān)鍵。改進(jìn)算法在BM算法的基礎(chǔ)上，采用雙字符序列檢測(cè)方法，增大匹配過(guò)程中最大移動(dòng)距離至m+2，并保證匹配失敗時(shí)，每一次都能夠移動(dòng)最大的安全距離。將該改進(jìn)算法應(yīng)用于Snort系統(tǒng)中。實(shí)驗(yàn)驗(yàn)證，該算法能夠減少字符比較次數(shù)和窗口移動(dòng)次數(shù)，同時(shí)提高Snort系統(tǒng)的效率。

Snort系統(tǒng)；改進(jìn)的BM算法；最大移動(dòng)距離

A

TP309

10.3778/j.issn.1002-8331.1211-0322

School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou,Jiangxi 341000,China

曾傳璜（1964—），男，副教授，碩士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全，數(shù)據(jù)庫(kù)應(yīng)用技術(shù)。E-mail：huangkan0918@163.com

2012-11-26

2013-01-23

1002-8331（2014）22-0102-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-02-28,http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.020.html