基于Snort的入侵檢測系統(tǒng)的研究與改進(jìn)

鄭禮良， 吳國鳳， 胡曉明， 劉慶俞， 林杰華

(合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽合肥 230009)

由于網(wǎng)絡(luò)漏洞、管理者疏忽、黑客惡意攻擊等因素，Web服務(wù)器遭受網(wǎng)絡(luò)攻擊的事件頻繁發(fā)生[1]。其中以Web應(yīng)用類型的攻擊最多，而大部分Web應(yīng)用均未采取專門有效的防護(hù)措施來應(yīng)對。入侵檢測系統(tǒng)(Intrusion Detection System，簡稱IDS)的工作主要用于檢測該字符串中的子字符串是否與已知的攻擊模式相符，并根據(jù)預(yù)定的方案采取相應(yīng)的防范措施，如報警等，以降低入侵帶來的危害。常用的Snort[2]方法在字符串檢測上花費高達(dá)70%的執(zhí)行時間和80%的指令執(zhí)行時間，效率不理想。

入侵檢測系統(tǒng)的實現(xiàn)涉及協(xié)議分析、特征匹配、專家系統(tǒng)等多個方面。其中應(yīng)用最廣泛的是特征匹配，即通過規(guī)則庫中的規(guī)則與網(wǎng)絡(luò)中的數(shù)據(jù)包進(jìn)行匹配來判斷攻擊類型。模式匹配算法(Pattern M atching A lgorithm)是實現(xiàn)IDS的核心算法，同時匹配過程也是最耗費計算資源的處理步驟。在高速網(wǎng)絡(luò)中，它一直是IDS性能提高的一個瓶頸。在實際的網(wǎng)絡(luò)應(yīng)用中，數(shù)據(jù)包的捕獲速度與解釋速度不能匹配直接影響到IDS的效率。針對Web攻擊，目前采用的主要措施是IDS盡快、盡可能可靠地檢測出各種入侵行為[3]。

1 字符串的匹配優(yōu)化

1.1 規(guī)則庫的動態(tài)優(yōu)化

在規(guī)則匹配的歷程中，現(xiàn)行設(shè)備不斷完善，漏洞在不斷增長和變化，最初制定的一些規(guī)則很少或根本不會被匹配成功。入侵檢測進(jìn)行規(guī)則匹配時要逐個進(jìn)行，這樣就占用了大部分的匹配時間，降低了匹配效率。經(jīng)分析驗證，把匹配的次數(shù)和學(xué)習(xí)得到的權(quán)值兩者進(jìn)行比較:當(dāng)高于權(quán)值，則將此規(guī)則放在規(guī)則庫的最前面，順序由高出權(quán)值的多少而定;當(dāng)?shù)陀跈?quán)值則放在后面，順序由低出權(quán)值的多少而定;當(dāng)匹配次數(shù)小于某個閥值時，則把此規(guī)則徹底地從規(guī)則庫中刪除。權(quán)值和閥值通過不同環(huán)境下的數(shù)據(jù)學(xué)習(xí)和綜合統(tǒng)計而定，可減少無用的匹配，從而動態(tài)地更新規(guī)則庫中的規(guī)則匹配順序。

權(quán)值和閾值主要是通過數(shù)據(jù)挖掘技術(shù)來進(jìn)行確定，此技術(shù)是一種從大量數(shù)據(jù)中提取人們感興趣的模式的過程。其對象可以是數(shù)據(jù)源、文件系統(tǒng)，也可以包括諸如Web資源等任何數(shù)據(jù)集合。數(shù)據(jù)挖掘通過預(yù)測未來趨勢及行為，目標(biāo)是從數(shù)據(jù)中發(fā)現(xiàn)隱含的、有意義的知識，關(guān)聯(lián)分析能尋找數(shù)據(jù)庫中數(shù)據(jù)的相關(guān)聯(lián)系。給定一個最小支持度和一個最小可信度，找出那些可信的并具有代表性的規(guī)則。其主要操作是在路由器之后，防火墻之前建立一套入侵防護(hù)機(jī)制，監(jiān)控每一個局域網(wǎng)絡(luò)的出入口，利用入侵偵測設(shè)備(Intrusion Detection Device，簡稱IDD)對每一筆進(jìn)出局域網(wǎng)絡(luò)的數(shù)據(jù)信息進(jìn)行監(jiān)控。

此外，IDD還過濾不當(dāng)來源的數(shù)據(jù)包，對一般事件網(wǎng)絡(luò)的流量做出響應(yīng)，這些信息將會匯總到系統(tǒng)控制中心[4](Center of Intrusion Detection System，簡稱CIDS)，從而完成網(wǎng)絡(luò)數(shù)據(jù)采集功能[5]，如圖1所示。

圖1 數(shù)據(jù)挖掘流程

本文的工作就是對數(shù)據(jù)進(jìn)行統(tǒng)計分析，給出所需要的閥值和權(quán)值。通過這項技術(shù)，可以把當(dāng)前最新、最常見的規(guī)則放在匹配的最前沿，并且刪除過于陳舊的規(guī)則，不僅使規(guī)則庫更加的簡潔，而且提高了匹配的效率。

1.2 2C-BM算法簡介

隨著各種攻擊手段的不斷出現(xiàn)，IDS要匹配的模式數(shù)量急劇增加，從而對匹配算法提出了更高的要求。模式匹配[6]從方式上可分為精確匹配、模糊匹配、并行匹配等。著名的匹配算法有BF算法、KMP算法、BM算法[7]、BMH算法及一些改進(jìn)算法，這些算法在不同的條件下有著不同的優(yōu)越性?，F(xiàn)在用于Snort的比較成熟而且高效的模式匹配算法多數(shù)為BM算法以及在這個算法基礎(chǔ)之上改進(jìn)的算法，比較常見的有2C-BM算法[8]、BMH算法。Snort按照深度鏈?zhǔn)剿阉魉惴▽σ?guī)則進(jìn)行逐條匹配，規(guī)則中的每一個選項對應(yīng)各自的匹配函數(shù)，以實現(xiàn)不同類型的匹配操作。這種算法程序結(jié)構(gòu)清晰，具有非常好的可擴(kuò)展性。

根據(jù)綜合考察，發(fā)現(xiàn)2C-BM算法具有簡潔、高效、擴(kuò)展性強(qiáng)等特點，可以根據(jù)自己的需求動態(tài)地改變其每次匹配的字符數(shù)，如2C-BM算法以每次比較2個字符為主，同樣可以擴(kuò)展到3個或4個，只需將函數(shù)中的參數(shù)進(jìn)行相應(yīng)的修改即可。2C-BM算法具體實施時，主要分為預(yù)處理階段和匹配階段。

(1)預(yù)處理階段。①構(gòu)造Hash(w[i])，將匹配串中任2個字符的組合映射到一個值。但若字符集為整個 0x0000—0xFFFF，則可以不用Hash，直接用Hash(w[i])=(unsignedshort) (w[i]);②構(gòu)造Shift數(shù)組，用來計算每個字失配時的偏移量是多少。

(2)匹配階段。①將被匹配串(記為B)與模式串(記為M)對齊，且它們的長度分別為n和m，指針b→textEnd指向B[m-1]，b→currentEnd指向b[m-2]，從B{m-2，m-1}與M{m-2，m-1}開始比較;②比較一個字;③2個字相等:若已經(jīng)比較到B首字符，轉(zhuǎn)④，否則指針b→currentEnd向左移動2個字節(jié)，轉(zhuǎn)②; 2個字不等:查Shift表確定偏移量 S1、S2，取Shift=max{S1，S2+1};若(b→textEnd-b→currentEnd)＜Shift，轉(zhuǎn)④;否則，b→textEnd向右滑動Shift個字符，轉(zhuǎn)②;④匹配結(jié)束。

此算法是在BM算法的基礎(chǔ)上進(jìn)行了改進(jìn):一方面把每次匹配比較的字符由1個變成了2個，另一方面遇到失配時，根據(jù)不同情況可以通過Shift和Shift+1的值進(jìn)行跳轉(zhuǎn)，增大了跳轉(zhuǎn)距離，減少了跳轉(zhuǎn)次數(shù)。

1.3 改進(jìn)的匹配算法

由于網(wǎng)絡(luò)攻擊類型增多，IDS要匹配的模式數(shù)量也在急劇增加。到2006年10月，Snort公布的ru les已經(jīng)達(dá)到8 525條，其中8 112條就用到模式匹配。規(guī)則庫的不斷增大，僅依靠單模式算法來匹配，不僅檢測效率不高，而且漏包現(xiàn)象很嚴(yán)重。本文提供的算法是在2C-BM算法的基礎(chǔ)上加入數(shù)組定位標(biāo)記功能，以加快后期模式匹配的速度。

在匹配過程中并非很快找到所需要匹配的規(guī)則和并行匹配模式，為了提高匹配速度，本文采用了數(shù)組標(biāo)記的功能，主要是對送進(jìn)來的匹配項進(jìn)行字符標(biāo)記，在匹配的最開始通過2C-BM算法進(jìn)行字符匹配，同時開啟一組數(shù)組對已經(jīng)匹配過的字符，在被匹配串中的位置進(jìn)行標(biāo)記記錄，具體方法如下。

假設(shè)要檢測的一組字符串為:Text=“abcde fgbcga”，在開始檢測的同時就會記錄下字符串中已經(jīng)匹配過的字符所在的位置。由于部分字符被比較，所以只會記錄被匹配過的字符位置。若第1條被匹配到的規(guī)則串為opq，則根據(jù)2C-BM算法，因為 Text中沒有一個與opq中的字符相同，所以每次跳轉(zhuǎn)距離都是最大的，即其本身長度加1。第1次匹配之后，被匹配記錄的字符位置有第2、3、4位置的b、c、d，6、7、8位置的 f、g、b，被記錄的字符占總字符的54%。第2條被匹配的規(guī)則串為bcg，可以用算法匹配的同時，結(jié)合數(shù)組標(biāo)記中的記錄來找要匹配的字符，同時記錄其它剛被匹配到的字符位置。

據(jù)實驗統(tǒng)計，2C-BM算法隨著規(guī)則庫中規(guī)則數(shù)目的增加，其匹配成功的時間成不均勻的遞增分布，平均時間記為T(2C-BM)，數(shù)組標(biāo)記字符達(dá)到30%，則字符串匹配成功率達(dá)到80%以上，字符記錄40%時已經(jīng)達(dá)到90%以上，它們匹配時間分別記為T(3)、T(4)，同時T(3)＜T(4)?T(2C-BM)。因此得出結(jié)論:當(dāng)使用2C-BM算法匹配時間T(2C-BM)＞T(3)或者T(2C-BM)＞T(4)時，字符匹配則通過數(shù)組標(biāo)記法已經(jīng)匹配成功。定位表中記錄的字符越完整，則匹配的準(zhǔn)確率就越高，但需要的時間也越長。

本文通過多組實驗測試選取，當(dāng)字符記錄達(dá)到45%時，則匹配時間和匹配準(zhǔn)確率達(dá)到最優(yōu)。假設(shè)上面的所有字符都已經(jīng)記下來了它們的位置，如a[1]={1，11}，a[2]={2，8}，a[3]={3，9}，a[4]={4}，a[5]={5}，a[6]={6}，a[7]= {7，10}，分別記錄了字母a到g在abcdefgbcga中的位置。下一步給出的比較串Patten=“bcg”，則只需要查找a[2]、a[3]、a[7]中記錄的值，查看是否有連續(xù)遞增的情況。如a[2]中有2、8，再觀察a[3]中有沒有3或9。如果有繼續(xù)向下查詢，沒有則宣告結(jié)束，匹配不成功。因為a[3]={3，9}，所以再觀察a[7]中記錄的值是否有4或10，若有則匹配成功，沒有則匹配失敗。由于a[7]中有10，所以匹配成功。此法不僅在比較串的長度上沒有限制，而且對于比較串較短的情況能夠很快地給出響應(yīng)，這一點打破了以往對字符串越長匹配速度越快，越短(一般情況下最短要大于7個字符)匹配速度越慢的限制。

2C-BM算法匹配過程如圖2所示，改進(jìn)匹配算法如圖3所示。

圖2 2C-BM算法匹配過程

圖3中，a[1]記錄a的位置，a[2]記錄b的位置，a[3]記錄c的位置，a[4]記錄d的位置，a[5]記錄e的位置，a[6]記錄f的位置，a[7]記錄g的位置，匹配串為bcg，查看a[2]={2，8}，a[3]= {3，9}，a[7]={7，10}，得出a[2]、a[3]、a[7]中有8、9、10這樣的加1排序，則匹配成功。

上述2C-BM算法每次進(jìn)行雙位比較，比以往的BM算法有了很大的提高。使用本文中提供的數(shù)組定位標(biāo)記法，則只需比較數(shù)組中的記錄，查看a[2]、a[3]、a[7]中記錄的數(shù)字是否有連續(xù)遞增排序，有則匹配成功，無則跳出直接進(jìn)行下一次匹配，其優(yōu)越性是顯而易見的。

2 測 試

測試環(huán)境為:Intel(R)Core(TM)2 Duo CPU，主頻1.8 GH z，內(nèi)存1G，操作系統(tǒng)為W indow s XP，編譯器為Visual C++6.0，數(shù)據(jù)庫系統(tǒng)為SQL Server2000，入侵檢測系統(tǒng)采用開源的Snort2.8.5。在這樣的環(huán)境下，針對匹配機(jī)制以及規(guī)則庫未改進(jìn)的Snort與改進(jìn)后的Snort進(jìn)行了測試比較。

在測試中，分別針對Snort日志中的部分?jǐn)?shù)據(jù)進(jìn)行了測試比較。用長度為200 k的網(wǎng)絡(luò)數(shù)據(jù)包(取自M IT Linco ln Laboratory的數(shù)據(jù)集)進(jìn)行測試，規(guī)則采用Snort的規(guī)則庫，結(jié)果見表1所列。從表1可以看出，改進(jìn)算法相比2C-BM算法在性能上有較大的提高。起初規(guī)則少時并不能體現(xiàn)出其優(yōu)越性，但是隨著規(guī)則數(shù)量的不斷增加，改進(jìn)算法的優(yōu)點越明顯。

表1 多種算法匹配用時比較 m s

實驗表明，使用2C-BM算法后的Snort系統(tǒng)在規(guī)則數(shù)目小于100條的情況下，入侵檢測的時間相對于BM算法平均縮短了59.5%左右，而通過動態(tài)改變規(guī)則庫和加入數(shù)組定位的匹配方法，則與BM算法相比在規(guī)則數(shù)目小于100條的情況下，入侵檢測的時間平均縮短了62.3%左右，而與2C-BM算法相比則縮短了9.2%。當(dāng)規(guī)則數(shù)目大于100小于2 000條的情況下，使用2C-BM算法后入侵檢測的時間相對于BM算法平均縮短了65.3%左右，本文通過改進(jìn)后的匹配方法，與BM算法相比較，入侵檢測的時間平均縮短了74.1%左右，而與2C-BM算法相比則縮短了25%，如圖4所示。

圖4 改進(jìn)算法與2C-BM算法用時比較

通過上面的實驗數(shù)據(jù)及圖3所示可以發(fā)現(xiàn)，此方法的優(yōu)點在于規(guī)則條數(shù)越多，其匹配速度相對于其它的匹配方法則更快。

3 結(jié)束語

本文結(jié)合以往改進(jìn)的算法加入了數(shù)組標(biāo)記的功能，對于龐大的規(guī)則庫匹配，為使IDS更加智能化地發(fā)展，提出了改進(jìn)方法，并且還對于不常匹配到的規(guī)則進(jìn)行了動態(tài)的排序和刪除，極大地增強(qiáng)了匹配的靈活性，提高了匹配的速度。在本文算法的基礎(chǔ)上，通過對規(guī)則庫中的規(guī)則進(jìn)行數(shù)組標(biāo)記，在匹配前期可能對匹配速度有一定的影響，但當(dāng)規(guī)則庫記錄完整時，則匹配工作變得更加快捷。

[1] Garcia A，Juan J P，Katza A，et al.Intrusion detection in W eb ap plicationsusing textm ining[J].Engineering Applications of A rtificial Intelligence，2007，20(4):555-566.

[2] Antonatos S，Anagnostakis K G.Generating realistic w orkloads for netw ork intrusion detection systems[J].ACM SIGSOFT Softw are Engineering Notes，2004，29(1): 207-215.

[3] KA IH ong-mei，ZHU H ong-bing，KEIE，et al.A novel intelligen t intrusion detection，decision，response system [J].IEICE Transactions on Fundamentals of Electronics，Communicationsand Compu ter Scien ces，2006，E89-A(6): 1630-1637.

[4] Xiao-Ling Ye，Ying-Chao Zhang，Chao-Long Zhang.A m obile agent and Snort based distributed in trusion detection sy stem[C]//World Cong ress on Softw are Engineering. Xiamen，China，2009:281-286.

[5] 劉慶喻，葉 震，尹才榮.一種基于攻擊特征描述的網(wǎng)絡(luò)入侵檢測模型[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2010，33 (2):238-241.

[6] Horspool N R.Practical fast searching in strings[J].Softw are Practice and Experience，1980，10(6):501-506.

[7] 周文秋，呂 岳.一種快速模式匹配算法及其在IDS中應(yīng)用[J].信息技術(shù)，2009，(3):30-32，36.

[8] Pulsone N B，Rader C M.The M IT Lincoln Laboratory KASSPER algo rithm testbed and baseline algorithm suit [C]//Sensor A rray and M ultichannel Signal Processing W orkshop Proceedings，2003:38-42.