序列比較算法在入侵檢測系統的研究與應用

摘要：該文從闡述序列比較入手，分析了序列比較算法。通過對序列比較與入侵檢測行為比較的相似性研究，采用了一種序列比較算法應用于入侵檢測中。按照入侵檢測的特點采用了一種序列比較算法，使用標準數據和收集數據對其進行測試，取得了較好的實驗結果。

關鍵詞：入侵檢測；序列比較算法；相似性

中圖分類號：TP311文獻標識碼：A文章編號：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 引言

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

序列比較分析與入侵檢測具有著很大的相似性：從目的上看，序列分析其目的即尋找一個最大可能長度的序列，而且此序列同時被二個序列所擁有。即尋找序列直接的相似性。入侵檢測分析即分析監測行為與用戶過去行為，找出這兩種行為之間的差別和相同點。從實現手段上看，序列分析其無非是尋找到序列之間最大可能的匹配段，很可能就是一條最佳匹配序列。入侵檢測分析則是尋找監測行為與用戶過去行為的異同，通過偏差度來做為手段分析異同。從結果顯示上看，序列分析會由得分函數得到相似度數值，由數值的大小表征序列之間的相似情況。入侵檢測分析則是通過判斷監測行為與用戶過去行為相似與否，作出正常或者異常的判斷。本文將試圖把這種技術應用于專用網的拒絕服務攻擊的入侵檢測中去。

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

2 相關設置

2.1 得分函數的特殊設置

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

2.2 比對數據的選取設置

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

3 算法測試分析

算法衡量的主要標準有：False PostiveRate（錯報率），即將非入侵數據檢測為入侵數據的百分率；FalseNegativeRate （漏報率），即將入侵的數據檢測成為非入侵數據的百分率；HiteRate（命中率），即將入侵的數據檢測為入侵數據的百分率。首先將要從數據的角度闡述測試的步驟，然后從閾值選取、記分函數選取和實驗結果參數分析三個方面對測試結果進行分析。

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

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

3.1 檢測步驟介紹

SEA標準數據測試實驗用到的數據是比較龐大的，將所有的750，0000個數據進行測試總共要進行50×100×4901＝24，505，000次。通過編程和檢測步驟的優化，可以將檢測次數下降到5000次左右，總共使用二個月左右的時間完成數據的測試。并將所有數據結果取平均得到測試實驗結果。

為了方便步驟的解釋，這里只拿50個數據文件中的第一個數據文件，而且選取這一數據文件中第一塊數據作為例子。實際上每個數據文件的每塊數據都是使用相同的方法（以下簡稱Data1，Block1）。SEA標準數據測試實驗步驟主要包括以下幾個步驟：

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

2）Data1閾值的選取，將Data1數據做20次隨機實驗，每次實驗抽取100個數據與隨機抽取的1000個數據進行匹配，將20次隨機實驗的平均值看出為Data1的閾值。

3）記分函數的選取，在實驗中一律選取匹配計為＋1分；若在正常數據中出現空位，計為－1分；若在測試數據中出現空位，計為－2分；完全不匹配計為0分。

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

5）將Data1的100個數據塊按步驟4）處理，記錄測試結果。按照2）的閾值判斷入侵與否。

6）將Data1到Data50重復以上實驗步驟，得到測試算法判斷入侵分布圖，將該圖與標準入侵分布圖相比較，由參數定義求得本次實驗最終測試結果。

另外可以改變步驟3）的記分函數選取測試記分函數不同對實驗最終結果的影響。

3.2 數據測試實現分析

實驗選取VC作為編程語言和平臺，以下將首先就測試的流程加以說明，然后為幾個主要測試塊運行步驟和結果進行了截圖。

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

4 系統性能分析

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

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

明顯地，沒有被標記的數據包只包含一個源地址和目的地址。有多個攻擊源的初步實驗顯示了錯誤判斷率隨著攻擊路徑的增長而成直線上升。圖1顯示了以標記概率0.125的情況下，攻擊路徑長短對錯誤判斷率的影響的比較圖。直線代表分析的錯誤判斷率，曲線代表實際錯誤判斷率。圖中曲線表示的非線性表明網絡拓撲結構對錯誤率的影響。很明顯，如果一個路由器周圍有很多路由器相連，那么它就是處于中心地帶，相反，如果周圍相鄰的路由器比較少，就處于網絡拓撲的邊緣。由于處于邊緣的路由器相比中心路由器通過的數據包少，那么錯誤判斷率也將有所增加。

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

4.2 閾值對實驗結果影響及分析

在提供檢測數據的網站中，提供了研究成熟的6種算法的閾值，而對于本文研究的算法，圖2是閾值的選取對實驗結果的影響圖。（深色線為漏報率，淺色線為錯報率）從圖上可以清晰的看到閾值選取對錯報率和漏報率的影響情況。

通過對圖2的分析，可以看到閾值選取對實驗參數有著很重要的影響。閾值取的過于低，則幾乎所有的數據塊都會被測試為不包含入侵，這樣會帶來很高的漏報率，同時錯報率是低的。當閾值的選取比例為0％時，所以的數據都被認為是正常的數據，此時錯報率為0％，漏報率也達到最高值。而閾值選取過于高，則很多數據塊都會被認為含有入侵，此時錯報率較高，同樣對實驗結果不利。

4.3 記分函數對實驗結果影響及分析

在入侵檢測序列匹配記分過程中，記分函數也會對實驗結果有著影響，下表描述了記分函數對實驗影響。下表的數據來自于對一個數據塊變換得分函數值后測試結果。可以看到記分函數值對實驗結果有著影響，但是不是非常的大。增加序列匹配得分值，一方面會提高實驗的命中率，但是實驗的錯報率也相應的增加；增加置空位的負分值，則命中率和錯報率均會有一定的提高。

4.4 實驗結果參數分析

數據提供的網站介紹了六種算法的實驗結果（如表2）。

采用的算法，經過多次的重復性實驗取得平均值，通過實驗其命中率可以達到接近70.1％，錯報率為2.1％。

5 結論

該文從闡述序列比較入手，分析了序列比較算法。通過對序列比較與入侵檢測行為比較的相似性研究，采用了一種序列比較算法應用于專用網的拒絕服務攻擊的入侵檢測中。使用標準數據和收集數據對其進行測試，從閾值選取、記分函數選取和實驗結果參數分析三個方面對算法進行了分析，取得了較好的實驗結果。

參考文獻：

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

[2] 蔣建春，馮登國.網絡入侵檢測原理與技術[M].北京:國防工業出版社，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] 邵先供，石鵬，王育民.入侵檢測響應系統的分析與研究[J].研究－網絡技術安全與應用，2003(9):40-43.