網(wǎng)絡(luò)入侵檢測(cè)算法研究

劉海濤

摘要：網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)通過(guò)對(duì)網(wǎng)絡(luò)中傳輸數(shù)據(jù)包的檢測(cè)來(lái)判別網(wǎng)絡(luò)中的異樣數(shù)據(jù)包，是目前應(yīng)用最為廣泛的網(wǎng)絡(luò)安全防范工具之一。網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)效率很大程度上取決于網(wǎng)絡(luò)入侵檢測(cè)算法效率。其中在Wu-Manber（WM）入侵檢測(cè)算法中，設(shè)置了SHIFT、PREFIX和HASH三個(gè)表來(lái)實(shí)現(xiàn)多模式匹配，但是PREFIX和HASH表的功能類似，因此可以通過(guò)HASH表的改進(jìn)，實(shí)現(xiàn)PREFIX和HASH表的融合，來(lái)減少算法空間復(fù)雜度和減少匹配比對(duì)次數(shù)，從容提高網(wǎng)絡(luò)入侵檢測(cè)算法效率。

關(guān)鍵詞：網(wǎng)絡(luò)安全；入侵檢測(cè)；模式匹配

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）05-0042-02

隨著信息技術(shù)的發(fā)展，人們通過(guò)網(wǎng)絡(luò)獲得極大便利的同時(shí)，網(wǎng)絡(luò)安全由于涉及個(gè)人、企業(yè)和國(guó)家的隱私和安全，因此也受到人們極大的關(guān)注。入侵檢測(cè)系統(tǒng)（Intrusion Detection System，IDS ）是網(wǎng)絡(luò)安全的重要組成部分，通過(guò)對(duì)網(wǎng)路中傳輸?shù)臄?shù)據(jù)包進(jìn)行檢測(cè)，辨別出網(wǎng)絡(luò)中的異樣數(shù)據(jù)包，從而實(shí)現(xiàn)網(wǎng)絡(luò)安全防范。入侵檢測(cè)算法是入侵檢測(cè)系統(tǒng)的核心，如何快速、準(zhǔn)確的檢測(cè)出網(wǎng)絡(luò)中的異常數(shù)據(jù)報(bào)是入侵檢測(cè)算法研究的重點(diǎn)。本文主要對(duì)源碼開放的Snort入侵檢測(cè)系統(tǒng)的Wu-Manber（WM）入侵檢測(cè)模式匹配算法進(jìn)行分析，并針對(duì)WM算法所存在的不足，對(duì)其進(jìn)行改進(jìn)研究。

1 模式匹配算法概述

模式匹配算法先定義一個(gè)長(zhǎng)度為n的文本串T，然后定義一個(gè)長(zhǎng)度為m的模式串P，如果在T中能夠完全找到模式串P，則匹配成功，否則匹配失敗。模式匹配算法的改進(jìn)的主要方向就是減少算法的時(shí)間、空間需求。

在入侵檢測(cè)系統(tǒng)中，隨著網(wǎng)絡(luò)帶寬的不斷增加，網(wǎng)絡(luò)中數(shù)據(jù)傳輸速率越來(lái)越快，因此對(duì)用于檢測(cè)網(wǎng)絡(luò)傳輸數(shù)中異常數(shù)據(jù)包的模式匹配算法效率提出了更高的要求。如果模式匹配算法的檢測(cè)速率跟不上網(wǎng)絡(luò)傳輸速度，那么在進(jìn)行入侵檢測(cè)時(shí)會(huì)漏檢大量的數(shù)據(jù)包，從而影響入侵檢測(cè)算法的高效性和準(zhǔn)確性，因此如何選擇合適的模式匹配算法，對(duì)于提高入侵檢測(cè)算法的檢測(cè)效率和檢測(cè)準(zhǔn)確性具有非常重要的影響。

2 WM入侵檢測(cè)算法簡(jiǎn)介

WM是一個(gè)典型的多模式匹配算法，是借鑒BM單模式串算法構(gòu)造出來(lái)的。WM通過(guò)采用長(zhǎng)度為B的字符塊，來(lái)擴(kuò)展壞字符移動(dòng)規(guī)則，同時(shí)采用HASH表來(lái)BM算法匹配階段的匹配運(yùn)算模式，從而提高了匹配效率。

WM具有較高的匹配效率，非常適用于入侵檢測(cè)系統(tǒng)中。WM算法采用哈希散列和跳躍不可能匹配的方法，來(lái)實(shí)現(xiàn)匹配。在WM算法中需要使用SHIFT、PREFIX和HASH三個(gè)表，并且需要對(duì)所有模式進(jìn)行預(yù)處理。其中，讀入字符串根據(jù)SHIFT表來(lái)決定跳躍距離，如果通過(guò)SHIFT表判斷跳躍距離為0時(shí)，就需要進(jìn)一步基于PREFIX表和HASH表來(lái)進(jìn)行判斷；PREFIX表用于存儲(chǔ)塊尾字符相同的模式傳中的手快字符散列值；HASH表用于存儲(chǔ)塊尾字符散列值相同的模式串值。WM算法執(zhí)行過(guò)程中，通過(guò)利用SHIFT、PREFIX和HASH表來(lái)完成字符的尋找和掃描。

在WM算法中，如果模式串?dāng)?shù)量越多，那么模式串后端相同的概率也會(huì)越大，根據(jù)WM的SHIFT表設(shè)計(jì)規(guī)則，此時(shí)模式串的移動(dòng)距離也會(huì)越小，增加比較次數(shù)，降低匹配效率。

在WM執(zhí)行過(guò)程中需要遵循如下的原則：

（1）如果在任何模式串中都不包括字符塊B，則SHIFT[h]=m-B+1，其中m為模式串的長(zhǎng)度，h為B的哈希值。字符串B通常取值2或者3，通過(guò)上述公式，可以計(jì)算每個(gè)塊字符與匹配窗口模式串串尾的距離。

（2）如果在某些模式串中能夠找到字符塊B，而且字符塊在模式傳中出現(xiàn)的位置為1，則SHIFT[h]=m-1。

WM算法流程如下所示：

①將最短的模式串長(zhǎng)度記為m；

②構(gòu)建HASH表、PREFIX表和SHIFT表，分別表示為HASH[h]、PREFIX[h]和SHIFT[h]；

③如果SHIFT[h]>0，則將窗口跳躍SHIFT[h]的位置；否則，執(zhí)行下一步；

④如果存在p滿足： HASH[h]≤p

3 WM算法存在的不足

WM是一個(gè)效率較高的模式匹配算法，但是在入侵檢測(cè)算法中，WM算法仍然存在如下的不足：

（1）當(dāng)模式串?dāng)?shù)量不斷增加時(shí)，那么擁有相同后綴的模式傳輸量也會(huì)響應(yīng)增加，那么具有相同哈希值的模式串?dāng)?shù)量也會(huì)增加，從而導(dǎo)致同一個(gè)哈希值表項(xiàng)內(nèi)的串聯(lián)長(zhǎng)度增加，即當(dāng)確定模式串的后綴的哈希值之后，還需要通過(guò)更多次的對(duì)比。

（2）如果所有模式串中最短模式串的長(zhǎng)度m較小，那么每次跳躍的距離會(huì)很小，影響模式串的匹配效率，對(duì)算法性能造成較大的影響。

4 WM算法的改進(jìn)

通過(guò)對(duì)WM算法的分析，在WM算法中，HASH表存儲(chǔ)了模式串后綴模式串的哈希值，而在PREFIX表中存儲(chǔ)了模式串前綴的哈希值，從而可以看出WM算法中的HASH表和PREFIX表的功能類似，因此可以通過(guò)HASH表的改造，將其分成兩個(gè)區(qū)來(lái)分別表示原HASH表和PREFIX表中的內(nèi)容，取消PREFIX表。

構(gòu)建改進(jìn)WM算法步驟如下所示：

①記錄所有模式串中最小模式串的長(zhǎng)度為m；

②確定字符塊B的大小，一般B取值為2或者3；

③構(gòu)建SHIFT 表；

④構(gòu)建HASH表的左右半?yún)^(qū)，其中左半?yún)^(qū)存儲(chǔ)原WM算法的HASH表內(nèi)容，右半?yún)^(qū)存儲(chǔ)原WM算法中PREFIX表的值；

在構(gòu)建好改進(jìn)的WM算法之后，使用WM算法來(lái)進(jìn)行入侵檢測(cè)的匹配流程如下所示：

①計(jì)算模式串的SHIFT表；

②計(jì)算當(dāng)前匹配模式串文本的前綴和后綴，并將前綴和后綴的哈希表值分別存儲(chǔ)到HASH表中的左右半?yún)^(qū)中；

③基于SHIFT表對(duì)文本串進(jìn)行掃描，從文本串左端第m個(gè)字符開始，整體從模式串的左匹配到右，每次掃描B個(gè)字符，如果跳躍距離大于0，則根據(jù)SHIFT表中的值后移；

④如果后綴的哈希值在HASH表的作伴去，則尋找HASH表的右半?yún)^(qū)中是否有與其完全匹配的字符串，如果有則表示模式串完全匹配文本串，如果沒(méi)有則返回第③步，直到所有的文本串匹配完畢。

從改進(jìn)WM算法中可以看出，改進(jìn)WM算法通過(guò)將HASH表劃分為左右搬去，節(jié)省了PREFIX表的構(gòu)建空間，減少了算法匹配時(shí)的對(duì)比次數(shù)，有效提高了算法效率。

下面以一個(gè)具體的實(shí)例來(lái)對(duì)改進(jìn)WM算法的具體應(yīng)用進(jìn)行介紹：

文本串：”Each of us will have a better tomorrow”，匹配字符串為hava，算法中B取值為2。改進(jìn)WM算法的步驟如下所示：

①計(jì)算SHIFT表

計(jì)算文本串中每個(gè)字符塊與匹配窗口內(nèi)模式串串尾的距離，并且將所得到的距離作為文本中出現(xiàn)時(shí)的跳躍距離，SHIFT表中未出現(xiàn)在匹配窗口內(nèi)的塊字符值均為m-B+1=4-2+1=3，最終得到SHIFT表如表1所示：

表1 SHIFT表

[ha＼&av＼&ve＼&其他＼&2＼&1＼&0＼&3＼&]

②計(jì)算HASH表

在改進(jìn)HASH表中的作伴去存儲(chǔ)原算法HASH表中的值，有半?yún)^(qū)存儲(chǔ)原算法PREFIX表中的值，最終得到HASH表如表2所示。

表2 HASH表

[ve＼&ha＼&have＼&have＼&]

③匹配過(guò)程

取B值為2，從右向左掃描文本串前端的4個(gè)字符，并且根據(jù)這4個(gè)字符的后兩位來(lái)查找SHIFT表，其中ch在表1中的跳躍距離為3，則向后移動(dòng)3個(gè)距離，后移距離3后的字符串為of，of在表1中的跳躍距離同樣為3，依次匹配下去，知道發(fā)現(xiàn)ve在表1中的移動(dòng)距離為0，則轉(zhuǎn)入表2的左半?yún)^(qū)，查找到have，然后計(jì)算have在表2右半去的哈希值，同樣也有have，則匹配串have完全匹配文本串。

5 總結(jié)

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)入侵檢測(cè)已經(jīng)成為了捍衛(wèi)網(wǎng)絡(luò)安全的有力武器，而網(wǎng)絡(luò)入侵檢測(cè)的效率很大程度上取決于模式匹配算法的效率。在本文的研究中主要針對(duì)Snort開源入侵檢測(cè)系統(tǒng)中的WM多模式匹配算法所存在的問(wèn)題，進(jìn)行改進(jìn)WM多模式匹配算法的設(shè)計(jì)。

參考文獻(xiàn)：

[1] 蘭景英，王永恒.snort研究及BM算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì).2008，29（9）：2199-2202.

[2] 張?chǎng)危?譚建龍， 程旗. 一種改進(jìn)的Wu-Manber 多關(guān)鍵詞算法[J]. 計(jì)算機(jī)應(yīng)用， 2003，23 （7）：29-31.

[3] 唐謙，張大方. 基于snort的入侵檢測(cè)引擎比較分析[J].計(jì)算機(jī)工程與設(shè)計(jì)2005，26（11）：2884-2886.

[4] 王猛，王小雙.snort規(guī)則匹配算法改進(jìn)[J].浙江海洋學(xué)院學(xué)報(bào)：自然科學(xué)版，2007，26（2）：215-218.

[5] 馬偉華，劉玉梅 ，葉飛 ，楊旭東 .一種改進(jìn)的Wu-Manber多模式串匹配算法[J]. 應(yīng)用科技，2007，34（10）：32-34.

[6] 崔瑋， 劉建偉， 張其善. 基于snort和改進(jìn)BM算法的入侵檢測(cè)系統(tǒng)的研究與實(shí)現(xiàn)[J]. 2006，29（6）：144-146.