采用壓縮近鄰法的高效入侵檢測模型
2010-01-01 00:00:00賈偉峰杜保建童彬張鳳荔
計算機應用研究 2010年6期
摘 要:針對入侵檢測中的實時性問題，提出了一種采用壓縮近鄰法的高效入侵檢測模型。該模型能夠用于精簡訓練集，從而加快入侵檢測系統的訓練及檢測速度，提高了系統的實時性。為了對該模型的訓練集精簡效果和檢測性能進行驗證，采用著名的KDD CUP99公用數據集進行實驗，并對比了該方法和其他入侵檢測方法的檢測效果和檢測時間。結果表明，該模型能夠在大幅降低訓練集大小的情況下，提升入侵檢測的實時性，并保持較好的檢測效果，是一種高效的入侵檢測模型。
關鍵詞:壓縮近鄰法; 重復剪輯近鄰法; 入侵檢測; 訓練集精簡; 實時性
中圖分類號:TP309文獻標志碼:A
文章編號:1001-3695(2010)06-2341-03
doi:10.3969/j.issn.1001-3695.2010.06.099
Highly effective intrusion detection model adopting condensed nearest neighbor rules
JIA Wei-feng1， DU Bao-jian1， TONG Bin2， ZHANG Feng-li2
(1.Anyang Normal University， Anyang Henan 455000， China; 2.School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)
Abstract:Aiming at the realtime problem for intrusion detection， this paper proposed a highly effective intrusion detection model adopting condensed nearest neighbor rules， named IDMCNN. IDMCNN could be used for training set reduction， which speeded up the training and detecting function for IDS and improved the realtime ability. To verify the performance of IDMCNN on the reduced training set and intrusion detection， performed experiments on famous public dataset KDD CUP99， performance and time consuming of intrusion detection between model proposed and compared other existing approaches among each other. Demonstrated IDMCNN is a highly effective intrusion detection model that keeps performance on detection with high realtime in such a case that the size of training set have been reduced in substantially great extent.
Key words:condensed nearest neighbor rule; multiedit nearest neighbors; intrusion detection; reduction for training set; realtime
0 引言
入侵檢測是網絡安全領域內的研究熱點和難點，其本質是分類問題。目前國內外大多數文獻將入侵檢測分為異常檢測和誤用檢測兩種類型[1，2]。異常檢測即離群點檢測，通常情況下訓練數據只包含正常樣本，然后在此基礎上對被測數據進行檢測，判斷網絡是否存在異常。誤用檢測要求檢測前建立有標定的正常數據和攻擊數據特征庫，檢測時通過匹配被檢測數據的特征與標定數據的符合程度判定入侵是否發生，這是一種有指導的基于正常、攻擊樣本庫的入侵檢測方法。相對于異常檢測技術來說，這種檢測技術由于有攻擊樣本庫的支持，具有誤報率低、檢測率高的特點，從而得到了廣泛的研究與應用。有指導入侵檢測中，關鍵環節是入侵檢測訓練樣本庫的建立，樣本過多會消耗大量的系統資源，降低訓練過程的實時性，從而不便于實際系統中訓練庫的及時更新。為了能夠提出一種高實時性的入侵檢測模型，本文采用壓縮近鄰法[3]，去掉訓練樣本庫中不利于分類的冗余樣本，在大幅減少訓練樣本數量的情況下，保持檢測效果，從而提高入侵檢測模型的實時性。相對于其他方法，本文提出的入侵檢測模型只需使用極少的訓練樣本，具有系統資源消耗低、檢測實時性高等特點。
1 研究現狀及存在的問題
由于有指導入侵檢測系統具有檢測準確性高、誤報率低的特點，近年來取得了很快的發展。就近兩年的發展情況來看，2008年，Orfila等人[4]提出了一種基于多重代理和自動化決策的入侵檢測系統，融合了多種技術，取得了較好的檢測效果，但也需要大量訓練樣本進行訓練;2009年Aydin等人[5]提出了一種混合誤用檢測和異常檢測的入侵檢測系統，有機結合了兩種檢測方式的優點，但入侵檢測系統中的誤用入侵檢測也需要大樣本庫的支持;此外，Sandhya等人[6]采用決策樹結合支持向量機構建了智能的入侵檢測模型;Simon等人[7]提出了一種基于混合人工免疫系統、SOM神經網絡的網絡入侵檢測機制，取得了較好的檢測效果。新的方法不斷被提出，但是都面臨基于大量訓練樣本進行學習的過程。而訓練樣本量過多造成了學習效率的下降，從而降低了檢測模型的實時性。入侵檢測中，實時性是一個非常重要的問題。本文以此為出發點，采用壓縮近鄰法去除訓練樣本中的冗余數據，大幅降低樣本數量，提升了訓練過程的實時性，并在這個過程中，保持模型的檢測率，控制誤報率。
2 基于壓縮近鄰法的高效入侵檢測模型
為了對本文所提出的基于壓縮近鄰法的入侵檢測模型(intrusion detection model adopting condensed nearest neighbor rules， IDMCNN)進行詳細的說明，本章采用圖1所示的數據流圖解釋該模型的數據流向。圖1中，數據流D1表示按一定格式存取的原始訓練數據。在實際的工程應用中，訓練庫使用專家系統生成，并且隨著網絡狀況的不斷變化進行更新，以便入侵檢測系統具有自適應性。本文模型將原始數據輸入訓練集精簡單元，目的是去除冗余的、不必要的訓練數據，從而提高后續模塊的運行效率。圖1中虛線框里面是模型的訓練和檢測單元，可采用目前的各種機器學習方法，如神經網絡、支持向量機(SVM)或者近鄰法等，本文采用近鄰法。實際的檢測數據D4來自被保護的網絡所采集的信息，這些信息可以是協議類型、端口號、單位時間進出流量等。為了使得本文模型具有自適應性，需要不斷更新訓練庫。D6根據檢測結果和被測數據信息，按照指定格式處理成系統能識別的更新數據信息，定期增量更新訓練庫。
2.1 壓縮近鄰法介紹
在圖1中，精簡訓練集單元采用壓縮近鄰法去除正常數據、攻擊數據分類超平面附近的交叉混淆數據和遠離分類面的冗余數據，從而達到精簡數據的目的[3]。為了對該方法有一個清楚的認識，本節對壓縮近鄰法作理論上的介紹。壓縮近鄰法實施之前，需要采用重復剪輯近鄰法去除分類超平面附近的交叉混淆數據，因此先介紹重復剪輯近鄰法。
1)重復剪輯近鄰法
該方法是對剪輯近鄰法的改進，可以用于去除分類超平面附近的混淆數據，得到精簡訓練(參考)集，具體步驟如下:
a)將訓練樣本集合χN隨機劃分為S個子集，S≥3。χN={χ1，χ2，…，χS}。
b)用χ2為參考集，對χ1進行1近鄰或k近鄰分類;用χ3為參考集，對χ2進行1近鄰或k近鄰分類，等等。依此類推至用χ1為參考集，對χS進行k近鄰分類。
c)步驟b)完成后，統一刪除被錯誤分類的樣本。
d)用留下來的樣本集χE1，χE2，…，χES的合集χN′，作為剪輯后的訓練(參考)集。
重復剪輯近鄰法的目的是為了刪除分類超平面附近交叉混淆的正常數據和攻擊數據。然而對于有些分類方法來說，如本文實驗采用的近鄰法，遠離分類面的數據對于分類來說也是無用的、冗余的。為了去除這些數據，可采用壓縮近鄰法。
2)壓縮近鄰法
a)對剪輯后的訓練樣本集χN′設置兩個存儲器store和grabbag。
b)將χN′的所有樣本放入grabbag中。
c)從grabbag中隨機取兩個樣本x1∈ω1，x2∈ω2，放入store中;ω1、ω2分別代表正常和攻擊兩個類別。
d)從grabbag中取出一個樣本xk，用store中的樣本做參考集，采用近鄰法對xk分類。若分類正確，刪除xk; 否則，xk放入store中。
e)對grabbag中所有樣本進行步驟d)的操作，直到grabbag為空。
f)對x1、x2進行步驟d)的操作。
最后，store中存放的就是壓縮精簡后的訓練樣本集χN″，χN″中已經去除了遠離分類面的冗余數據。
2.2 高效性分析
本文入侵檢測模型中的檢測單元，采用K近鄰法進行入侵和攻擊的分類，因此性能提升主要體現在K近鄰分類算法的性能提升上。由于K近鄰法中存在著大量的歐氏距離計算，計算次數與訓練參考集中的樣本數量緊密相關。若能大幅減少訓練樣本，K近鄰分類法中的歐氏距離計算量將會大幅降低，其性能必定會明顯提高。
3 實驗
為了驗證基于壓縮近鄰法的入侵檢測模型的檢測性能，本章提出并實現了一種網絡入侵檢測實驗仿真方案，驗證了模型的有效性。
3.1 實驗方案
本文實驗數據采用美國國防部高級計劃研究局(DARPA)1999年用于入侵檢測系統評估的KDD CUP99數據集[8]，該數據集分為訓練集和測試集兩大部分，每種數據集各包含normal、DoS、Probe、R2L、U2R五類數據。本文從kddcup.data_10_percent_corrected訓練集中，隨機抽取了正常數據9 728條，攻擊數據6 584條(其中DoS攻擊3 915條，Probe攻擊2 054條，R2L攻擊563條和U2R攻擊52條)，然后將正常數據與攻擊數據混合組成訓練集。從correct數據集中抽取了6 060條正常數據和5 669條攻擊數據(DoS攻擊2 299條，Probe攻擊2 083條，R2L攻擊1 059條和U2R攻擊228條)，組成測試集。采用MATLAB 6.1 for Windows XP作為訓練和測試的仿真工具平臺。具體的實驗步驟如下:
a)首先分別對原始訓練集χN中的正常數據和攻擊數據隨機分成10個子集，按照重復剪輯近鄰法對原始數據集進行精簡，得到一個新的訓練集χN′。
b)利用壓縮近鄰法，對步驟a)中的χN′進一步精簡，壓縮刪減冗余樣本，得到χN″。
c)利用K近鄰法，使用χN″作為參考集，對測試數據集χT進行入侵檢測的識別，得到檢測率、誤報率兩個代表入侵檢測算法性能的指標。
3.2 實驗結果與對比
由3.1節中的實驗步驟得知，采用壓縮近鄰法精簡訓練集之前，需采用重復剪輯近鄰法對訓練樣本進行處理，用于去除正常數據、攻擊數據分類超平面間的混淆數據。經過實驗得到如表1所示的結果。
表1 重復剪輯近鄰法剪輯結果
子集
正常數據
剪輯前剪輯后
攻擊數據
剪輯前剪輯后
1936932671563
2905903664655
3927922659648
4919889649616
5958954640624
6941940673620
7916911661608
8963958626567
91 0461 044668664
101 2171 193673602
合計9 7289 6466 5846 167
從表1的實驗結果可以看出，重復剪輯近鄰法應用到本文的訓練集上，并沒有大幅減少樣本數量。這說明本文的訓練集，處于正常、攻擊兩類數據分類超平面附近的混淆區數據比較少，大部分數據都處于分類超平面兩端，冗余性較高。為了去除這些冗余的數據，采用壓縮近鄰法進一步精簡訓練集，得到如表2所示的結果。
表2 壓縮近鄰法精簡訓練集效果
子集
正常數據
壓縮前壓縮后
攻擊數據
壓縮前壓縮后
1936932671563
193255636
290336555
392226486
4889461610
595436246
694056208
791126089
895835676
9104416643
10119316027
合計964629616766
從表2可以看出，壓縮近鄰法可以大幅減少訓練樣本數量:正常樣本數量從9 646降低為29，攻擊樣本數量從6 167降低為66。精簡后的訓練集，是對入侵檢測分類來說有用的訓練集，為了驗證精簡后的訓練集在K近鄰法入侵檢測中的性能。本節根據3.1節中提到的測試方案，用測試數據集驗證入侵檢測模型的檢測性能。評價標準采用國際上通用的檢測率(true positive rate， TP)和誤報率(1 positive rate， FP)，其定義如式(1)(2):
檢測率(TP)=被發現的攻擊樣本數攻擊樣本的總數(1)
誤報率(FP)=被誤判的正確樣本數正確樣本的總數(2)
為了驗證本文方案的實驗結果的有效性，針對同樣的數據集，本文分別采用BP神經網絡、SOM神經網絡、支持向量機(SVM)以及無參數的分類方法1近鄰法(NN)、K近鄰法(KNN)、剪輯近鄰法(edit KNN)進行檢測效果的對比。對每一種方法，根據具體參數或k的取值的不同，基于同一數據集，進行九組實驗，取平均數據，得到檢測率、誤報率兩個指標結果，如圖2所示。
由圖2可以看出，本文方法相對于其他方法來說，檢測率并沒有降低，只是誤報率稍高，考慮到訓練集的大幅精簡，這也在可接受的合理范圍之內。精簡訓練集是為了提高實時性，為了對精簡后的訓練集對入侵檢測模型實時性提高有一個量化的認識，本文對比了壓縮近鄰法和K近鄰法以及剪輯近鄰法在測試集上進行入侵檢測試驗的時間消耗，得到如圖3所示的結果。
圖3表明，精簡后的訓練集可以大幅降低近鄰分類法的檢測時間消耗，這是因為去除了冗余的樣本，減少了大量的歐氏距離計算。綜上所述，本文模型能夠在保持檢測效果的情況下，大幅精簡樣本數量，提升模型的實時性，因此本文提出的入侵檢測模型是一種具有實際工程應用價值的、高效的入侵檢測方法。
4 結束語
本文針對有監督入侵檢測領域中的訓練集冗余問題和檢測模型運算的實時性問題，提出了基于壓縮近鄰法的入侵檢測模型。實驗證明，該模型能夠在保證檢測效果的情況下，大幅減少用于訓練的正常和攻擊樣本數量，從而提高訓練速度和入侵檢測模型的實時性，是一種計算上高效的有指導入侵檢測模型，適合于部署在計算資源不夠充足的系統中。但是，本文方法較其他方法誤報率稍高，因此不適合部署于對誤報較為敏感的系統中。此時應考慮和其他方法組成混合檢測模型，降低誤報率，以對檢測模型作進一步的改進和提升。
參考文獻:
[1]BACE R G. Intrusion detection[M].[S.l.]: Macmillan Technical Publishing， 2000.
[2]李輝， 管曉宏， 昝鑫，等. 基于支持向量機的網絡入侵檢測[J]. 計算機研究與發展，2003(6):799-807.
[3]GUSTAVO E A， BATISTA P A， RONALDO C， et al. A study of the behavior of several methods for balancing machine learning training data[J]. ACM SIGKDD Explorations， 2004， 6(1):20-19.
[4]ORFILA A， CARBO J， RIBAGORDA A. Autonomous decision on intrusion detection with trained BDI agents， ButterworthHeinemann[J]. Computer Communications， 2008， 31(9): 1803-1813.
[5]AYDIN M A， ZAIM A H， CEYLAN K G. A hybrid intrusion detection system design for computer network security[J]. Computer and Electrical Engineering， 2009， 35(3): 517-526.
[6]SANDHYA P， AJITH A， GROSAN C， et al. Modeling intrusion detection system using hybrid intelligent systems[J].Journal of Network and Computer Applications， 2007， 30(1): 114-132.
[7]SIMON T P， JUN H. A hybrid artificial immune system and self organising map for network intrusion detection[J].Information Sciences， 2008， 178(15): 3024-3042.
[8]http://kdd.ics.uci.edu/databases/kddcup99/kddcup99. html[EB/OL].
