序列比較算法在入侵檢測系統(tǒng)的研究與應(yīng)用

摘要：該文從闡述序列比較入手，分析了序列比較算法。通過對序列比較與入侵檢測行為比較的相似性研究，采用了一種序列比較算法應(yīng)用于入侵檢測中。按照入侵檢測的特點(diǎn)采用了一種序列比較算法，使用標(biāo)準(zhǔn)數(shù)據(jù)和收集數(shù)據(jù)對其進(jìn)行測試，取得了較好的實(shí)驗(yàn)結(jié)果。

關(guān)鍵詞：入侵檢測；序列比較算法；相似性

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2009)04-0871-02

Research on Application on the Sequence Compare Algorithm in the Intrusion Detection System

LIU Peng1，LONG Hai2

(1.Department of Production，Shanxi TV，Xi'an 710061，China;2.Department of Computer， Hunan Institute of Humanities， Science and Technology， Loudi 417000，China)

Abstract: This paper introduces the sequence compare for analysing the sequence compare algorithm. We compare thecomparability between the sequence compare and intrusion detection toemployee a sequence compare algorithm based on the feature of the intrusion detection. Also ， the word employees the standard data and collection data to test the algorithm to abtain the better experiment result.

Key words: intrusion detection;sequence compare algorithm;comparability

1 引言

入侵檢測的研究是當(dāng)前的研究熱點(diǎn)[1-4]，最早可追溯到James Anderson在1980年的工作，他首先提出了入侵檢測的概念，將入侵嘗試（Intrusion attempt）或威脅（Threat）定義為：潛在的有預(yù)謀未經(jīng)授權(quán)訪問信息、操作信息、致使系統(tǒng)不可靠或無法使用的企圖。入侵檢測是識(shí)別網(wǎng)絡(luò)攻擊的主要手段。

序列比較分析與入侵檢測具有著很大的相似性：從目的上看，序列分析其目的即尋找一個(gè)最大可能長度的序列，而且此序列同時(shí)被二個(gè)序列所擁有。即尋找序列直接的相似性。入侵檢測分析即分析監(jiān)測行為與用戶過去行為，找出這兩種行為之間的差別和相同點(diǎn)。從實(shí)現(xiàn)手段上看，序列分析其無非是尋找到序列之間最大可能的匹配段，很可能就是一條最佳匹配序列。入侵檢測分析則是尋找監(jiān)測行為與用戶過去行為的異同，通過偏差度來做為手段分析異同。從結(jié)果顯示上看，序列分析會(huì)由得分函數(shù)得到相似度數(shù)值，由數(shù)值的大小表征序列之間的相似情況。入侵檢測分析則是通過判斷監(jiān)測行為與用戶過去行為相似與否，作出正?；蛘弋惓５呐袛?。本文將試圖把這種技術(shù)應(yīng)用于專用網(wǎng)的拒絕服務(wù)攻擊的入侵檢測中去。

由于大多數(shù)的入侵檢測都會(huì)以用戶命令序列的分析作為開始。這種分析與序列比對分析有著很大的相似性。對于全局聯(lián)配和局部聯(lián)配技術(shù)，事實(shí)上單獨(dú)地將任意的一種用于入侵檢測都是不合適的。在全局聯(lián)配中，兩條序列要么匹配，要么需要加入空格，在入侵檢測中有可能只有一小部分是不匹配的，而序列的大多數(shù)部分是匹配的，從而掩蓋住了相似性部分大于不匹配部分這一事實(shí)。而局部聯(lián)配會(huì)忽略掉大多數(shù)的數(shù)據(jù)，盡管匹配部分匹配值很高，但是實(shí)際上這沒有任何的意義。本文采用了一種Smith Waterman序列比較算法[2]，有效地提高檢測效率。

2 相關(guān)設(shè)置

2.1 得分函數(shù)的特殊設(shè)置

得分函數(shù)是用來評定序列相似性的方法，主要包括對匹配以及不匹配的得分。匹配記為正分，不匹配或者加入了編輯操作的情況記為負(fù)分。這種記分函數(shù)的選取方法對于入侵檢測是不合適的。由于入侵檢測一部分高度相似，其余部分相似。對應(yīng)的在測試序列中出現(xiàn)空位，在正常序列中有空位的影響小的多。而當(dāng)出現(xiàn)完全不匹配的情況，此時(shí)兩條序列相似度是及其低的。因此對得分函數(shù)進(jìn)行特殊設(shè)置：＋1，兩個(gè)序列是匹配的；－1，正常序列中有空位；－2，測試序列中有空位；0，完全不匹配的情況。這種設(shè)置有利用入侵檢測行為的比對，使匹配得分值能更好的反映監(jiān)測行為與用戶行為的差異。

2.2 比對數(shù)據(jù)的選取設(shè)置

序列的比對對所有的數(shù)據(jù)如果采用所有數(shù)據(jù)都進(jìn)行比較的方法，對應(yīng)的整體數(shù)值就會(huì)偏低，從而不能反映某一個(gè)區(qū)域相似性非常的高這一特性。所以選取設(shè)置可以將數(shù)據(jù)中的一部分給予剔除，由于這一部分的不匹配將會(huì)帶來過多的負(fù)分，從而影響總體的得分。選取設(shè)置只截取頭部或者尾部的數(shù)據(jù)進(jìn)行去除處理。選取美國蘭德公司提供的入侵檢測數(shù)據(jù)SEA Data，對采集的數(shù)據(jù)進(jìn)行測試并分析。

3 算法測試分析

算法衡量的主要標(biāo)準(zhǔn)有：False PostiveRate（錯(cuò)報(bào)率），即將非入侵?jǐn)?shù)據(jù)檢測為入侵?jǐn)?shù)據(jù)的百分率；FalseNegativeRate （漏報(bào)率），即將入侵的數(shù)據(jù)檢測成為非入侵?jǐn)?shù)據(jù)的百分率；HiteRate（命中率），即將入侵的數(shù)據(jù)檢測為入侵?jǐn)?shù)據(jù)的百分率。首先將要從數(shù)據(jù)的角度闡述測試的步驟，然后從閾值選取、記分函數(shù)選取和實(shí)驗(yàn)結(jié)果參數(shù)分析三個(gè)方面對測試結(jié)果進(jìn)行分析。

本文使用的測試數(shù)據(jù)包含著50個(gè)文件。每一個(gè)文件包含有著15，000個(gè)命令，最開始的5000個(gè)數(shù)據(jù)是不包含任何入侵?jǐn)?shù)據(jù)的，在實(shí)際測試中將會(huì)把這5000個(gè)數(shù)據(jù)作為正常數(shù)據(jù)看待。接下來10000個(gè)數(shù)據(jù)將其分為100個(gè)塊，每一個(gè)塊中包含有100個(gè)命令，在這些塊中散布著入侵者的數(shù)據(jù)。在測試數(shù)據(jù)的入侵?jǐn)?shù)據(jù)是人為制造的。50個(gè)文件的數(shù)據(jù)，來源于兩個(gè)組用戶（50和20個(gè)）。人為地將前50個(gè)用戶的命令序列認(rèn)為是正常用戶的命令。若出現(xiàn)后20個(gè)用戶的命令序列，視為入侵者的序列數(shù)據(jù)。在這些數(shù)據(jù)中，如果當(dāng)前的塊不包含入侵，接下來的塊中包含入侵?jǐn)?shù)據(jù)的可能性為1%；如果當(dāng)前塊包含入侵，接下來的塊中包含入侵的可能性為80%。

SEA數(shù)據(jù)中入侵的位置分布包含有100行與50縱對，每一個(gè)縱對對應(yīng)于50個(gè)SEA數(shù)據(jù)文件中的一個(gè)，每一行對應(yīng)于一個(gè)數(shù)據(jù)塊。開始于數(shù)據(jù)的第5001個(gè)位置截止到15000個(gè)位置（由于前5000個(gè)作為正常數(shù)據(jù)）。分布圖中包含著0或者1，0意味著對應(yīng)的這個(gè)數(shù)據(jù)塊是不包含入侵的，1則代表著這個(gè)數(shù)據(jù)塊中包含著入侵。

3.1 檢測步驟介紹

SEA標(biāo)準(zhǔn)數(shù)據(jù)測試實(shí)驗(yàn)用到的數(shù)據(jù)是比較龐大的，將所有的750，0000個(gè)數(shù)據(jù)進(jìn)行測試總共要進(jìn)行50×100×4901＝24，505，000次。通過編程和檢測步驟的優(yōu)化，可以將檢測次數(shù)下降到5000次左右，總共使用二個(gè)月左右的時(shí)間完成數(shù)據(jù)的測試。并將所有數(shù)據(jù)結(jié)果取平均得到測試實(shí)驗(yàn)結(jié)果。

為了方便步驟的解釋，這里只拿50個(gè)數(shù)據(jù)文件中的第一個(gè)數(shù)據(jù)文件，而且選取這一數(shù)據(jù)文件中第一塊數(shù)據(jù)作為例子。實(shí)際上每個(gè)數(shù)據(jù)文件的每塊數(shù)據(jù)都是使用相同的方法（以下簡稱Data1，Block1）。SEA標(biāo)準(zhǔn)數(shù)據(jù)測試實(shí)驗(yàn)步驟主要包括以下幾個(gè)步驟：

1）將Data1加載于程序，將Data1的前5000個(gè)數(shù)據(jù)提取作為正常測試數(shù)據(jù)，將其他的10000個(gè)看作是100個(gè)塊，每個(gè)塊包含100個(gè)數(shù)據(jù)，測試中塊是最為基本的單元。

2）Data1閾值的選取，將Data1數(shù)據(jù)做20次隨機(jī)實(shí)驗(yàn)，每次實(shí)驗(yàn)抽取100個(gè)數(shù)據(jù)與隨機(jī)抽取的1000個(gè)數(shù)據(jù)進(jìn)行匹配，將20次隨機(jī)實(shí)驗(yàn)的平均值看出為Data1的閾值。

3）記分函數(shù)的選取，在實(shí)驗(yàn)中一律選取匹配計(jì)為＋1分；若在正常數(shù)據(jù)中出現(xiàn)空位，計(jì)為－1分；若在測試數(shù)據(jù)中出現(xiàn)空位，計(jì)為－2分；完全不匹配計(jì)為0分。

4）將Block1分別與Data1的正常數(shù)據(jù)做4901次匹配，匹配中用的是序列比較算法。匹配后得到的最佳匹配序列按記分函數(shù)打分，記錄4901次的最高得分。

5）將Data1的100個(gè)數(shù)據(jù)塊按步驟4）處理，記錄測試結(jié)果。按照2）的閾值判斷入侵與否。

6）將Data1到Data50重復(fù)以上實(shí)驗(yàn)步驟，得到測試算法判斷入侵分布圖，將該圖與標(biāo)準(zhǔn)入侵分布圖相比較，由參數(shù)定義求得本次實(shí)驗(yàn)最終測試結(jié)果。

另外可以改變步驟3）的記分函數(shù)選取測試記分函數(shù)不同對實(shí)驗(yàn)最終結(jié)果的影響。

3.2 數(shù)據(jù)測試實(shí)現(xiàn)分析

實(shí)驗(yàn)選取VC作為編程語言和平臺(tái)，以下將首先就測試的流程加以說明，然后為幾個(gè)主要測試塊運(yùn)行步驟和結(jié)果進(jìn)行了截圖。

執(zhí)行步驟如下：首先通過算法的初始化定義和矩陣推導(dǎo)可以得到一個(gè)得分矩陣，然后由得分矩陣得到最佳匹配序列，最后根據(jù)設(shè)計(jì)的得分情況給出序列匹配得分，根據(jù)這個(gè)匹配得分的高低，與閾值大小判斷入侵與否。整個(gè)流程包括：1）對用戶的操作提取特征行為數(shù)據(jù)；2）對提取的數(shù)據(jù)進(jìn)行預(yù)處理；3）利用了序列比較算法，對用戶數(shù)據(jù)序列與正常的數(shù)據(jù)進(jìn)行算法匹配，通過得分函數(shù)得到匹配得分；4）與閾值比較，若判斷為入侵，則進(jìn)入系統(tǒng)報(bào)警處理環(huán)節(jié)。若正常，則返回開始界面，重新開始新一輪檢測。

4 系統(tǒng)性能分析

4.1 攻擊路徑長短對錯(cuò)誤判斷率的比較

下面通過模擬實(shí)驗(yàn)分析和評估的性能。以某個(gè)ISP服務(wù)商的實(shí)際運(yùn)行的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)，取其中的50個(gè)主要路由器。在該網(wǎng)絡(luò)中隨機(jī)的選擇一個(gè)攻擊源和被攻擊主機(jī)，從攻擊源以自適應(yīng)的概率發(fā)出1000個(gè)攻擊數(shù)據(jù)包。每個(gè)數(shù)據(jù)包在攻擊被攻擊主機(jī)的路徑中，通過路由器（已經(jīng)安裝了SHTE引擎的路由器）時(shí)都以自適應(yīng)概率的方式進(jìn)行標(biāo)記。追蹤過程從模擬的被攻擊路由器開始，直到攻擊源為止。均勻的通信量以最大錯(cuò)誤概率P來模擬每個(gè)路由器之間的通信。雖然真實(shí)的情況并不是相同的通信量，由于錯(cuò)誤判斷對通信量是否相同起的作用很少，因此認(rèn)為這種表示攻擊的起點(diǎn)是正確的。為了精確模擬網(wǎng)絡(luò)中的真實(shí)通信負(fù)荷，有效的錯(cuò)誤判斷率要根據(jù)不同路由器進(jìn)行調(diào)節(jié)的。

明顯地，沒有被標(biāo)記的數(shù)據(jù)包只包含一個(gè)源地址和目的地址。有多個(gè)攻擊源的初步實(shí)驗(yàn)顯示了錯(cuò)誤判斷率隨著攻擊路徑的增長而成直線上升。圖1顯示了以標(biāo)記概率0.125的情況下，攻擊路徑長短對錯(cuò)誤判斷率的影響的比較圖。直線代表分析的錯(cuò)誤判斷率，曲線代表實(shí)際錯(cuò)誤判斷率。圖中曲線表示的非線性表明網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對錯(cuò)誤率的影響。很明顯，如果一個(gè)路由器周圍有很多路由器相連，那么它就是處于中心地帶，相反，如果周圍相鄰的路由器比較少，就處于網(wǎng)絡(luò)拓?fù)涞倪吘?。由于處于邊緣的路由器相比中心路由器通過的數(shù)據(jù)包少，那么錯(cuò)誤判斷率也將有所增加。

系統(tǒng)追蹤關(guān)鍵是SHTE引擎查詢是否成功。SHTE引擎資源的請求由數(shù)據(jù)包摘要通過光暈濾波的數(shù)量和存儲(chǔ)摘要表的存儲(chǔ)量決定。利用SHTE引擎追蹤的特性也有2方面：第一，數(shù)據(jù)包摘要保存的時(shí)間。只有查詢中心在數(shù)據(jù)還沒有為存儲(chǔ)更新數(shù)據(jù)包摘要信息前查詢該摘要信息，才能查到正確的數(shù)據(jù)；第二，保證在錯(cuò)誤判斷的情況下SHTE引擎的正確性。

4.2 閾值對實(shí)驗(yàn)結(jié)果影響及分析

在提供檢測數(shù)據(jù)的網(wǎng)站中，提供了研究成熟的6種算法的閾值，而對于本文研究的算法，圖2是閾值的選取對實(shí)驗(yàn)結(jié)果的影響圖。（深色線為漏報(bào)率，淺色線為錯(cuò)報(bào)率）從圖上可以清晰的看到閾值選取對錯(cuò)報(bào)率和漏報(bào)率的影響情況。

通過對圖2的分析，可以看到閾值選取對實(shí)驗(yàn)參數(shù)有著很重要的影響。閾值取的過于低，則幾乎所有的數(shù)據(jù)塊都會(huì)被測試為不包含入侵，這樣會(huì)帶來很高的漏報(bào)率，同時(shí)錯(cuò)報(bào)率是低的。當(dāng)閾值的選取比例為0％時(shí)，所以的數(shù)據(jù)都被認(rèn)為是正常的數(shù)據(jù)，此時(shí)錯(cuò)報(bào)率為0％，漏報(bào)率也達(dá)到最高值。而閾值選取過于高，則很多數(shù)據(jù)塊都會(huì)被認(rèn)為含有入侵，此時(shí)錯(cuò)報(bào)率較高，同樣對實(shí)驗(yàn)結(jié)果不利。

4.3 記分函數(shù)對實(shí)驗(yàn)結(jié)果影響及分析

在入侵檢測序列匹配記分過程中，記分函數(shù)也會(huì)對實(shí)驗(yàn)結(jié)果有著影響，下表描述了記分函數(shù)對實(shí)驗(yàn)影響。下表的數(shù)據(jù)來自于對一個(gè)數(shù)據(jù)塊變換得分函數(shù)值后測試結(jié)果?？梢钥吹接浄趾瘮?shù)值對實(shí)驗(yàn)結(jié)果有著影響，但是不是非常的大。增加序列匹配得分值，一方面會(huì)提高實(shí)驗(yàn)的命中率，但是實(shí)驗(yàn)的錯(cuò)報(bào)率也相應(yīng)的增加；增加置空位的負(fù)分值，則命中率和錯(cuò)報(bào)率均會(huì)有一定的提高。

4.4 實(shí)驗(yàn)結(jié)果參數(shù)分析

數(shù)據(jù)提供的網(wǎng)站介紹了六種算法的實(shí)驗(yàn)結(jié)果（如表2）。

采用的算法，經(jīng)過多次的重復(fù)性實(shí)驗(yàn)取得平均值，通過實(shí)驗(yàn)其命中率可以達(dá)到接近70.1％，錯(cuò)報(bào)率為2.1％。

5 結(jié)論

該文從闡述序列比較入手，分析了序列比較算法。通過對序列比較與入侵檢測行為比較的相似性研究，采用了一種序列比較算法應(yīng)用于專用網(wǎng)的拒絕服務(wù)攻擊的入侵檢測中。使用標(biāo)準(zhǔn)數(shù)據(jù)和收集數(shù)據(jù)對其進(jìn)行測試，從閾值選取、記分函數(shù)選取和實(shí)驗(yàn)結(jié)果參數(shù)分析三個(gè)方面對算法進(jìn)行了分析，取得了較好的實(shí)驗(yàn)結(jié)果。

參考文獻(xiàn)：

[1] Elliott J..Distributed Denial of Service Attack and the Zombie Ant Effect [J].IP Professional，March/April 2000，55-57

[2] 蔣建春，馮登國.網(wǎng)絡(luò)入侵檢測原理與技術(shù)[M].北京:國防工業(yè)出版社，2001.

[3] Chang H Y，Narayan R，Sargor C，et al.Decentralized Source Idetification for Network-Based Intrusions[C].Proceeding of 6th IFIP/IEEE International

[4] 邵先供，石鵬，王育民.入侵檢測響應(yīng)系統(tǒng)的分析與研究[J].研究－網(wǎng)絡(luò)技術(shù)安全與應(yīng)用，2003(9):40-43.