采用壓縮近鄰法的高效入侵檢測(cè)模型

摘 要:針對(duì)入侵檢測(cè)中的實(shí)時(shí)性問(wèn)題，提出了一種采用壓縮近鄰法的高效入侵檢測(cè)模型。該模型能夠用于精簡(jiǎn)訓(xùn)練集，從而加快入侵檢測(cè)系統(tǒng)的訓(xùn)練及檢測(cè)速度，提高了系統(tǒng)的實(shí)時(shí)性。為了對(duì)該模型的訓(xùn)練集精簡(jiǎn)效果和檢測(cè)性能進(jìn)行驗(yàn)證，采用著名的KDD CUP99公用數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并對(duì)比了該方法和其他入侵檢測(cè)方法的檢測(cè)效果和檢測(cè)時(shí)間。結(jié)果表明，該模型能夠在大幅降低訓(xùn)練集大小的情況下，提升入侵檢測(cè)的實(shí)時(shí)性，并保持較好的檢測(cè)效果，是一種高效的入侵檢測(cè)模型。

關(guān)鍵詞:壓縮近鄰法; 重復(fù)剪輯近鄰法; 入侵檢測(cè); 訓(xùn)練集精簡(jiǎn); 實(shí)時(shí)性

中圖分類(lèi)號(hào):TP309文獻(xiàn)標(biāo)志碼:A

文章編號(hào):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 realtime 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 realtime 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 realtime in such a case that the size of training set have been reduced in substantially great extent.

Key words:condensed nearest neighbor rule; multiedit nearest neighbors; intrusion detection; reduction for training set; realtime

0 引言

入侵檢測(cè)是網(wǎng)絡(luò)安全領(lǐng)域內(nèi)的研究熱點(diǎn)和難點(diǎn)，其本質(zhì)是分類(lèi)問(wèn)題。目前國(guó)內(nèi)外大多數(shù)文獻(xiàn)將入侵檢測(cè)分為異常檢測(cè)和誤用檢測(cè)兩種類(lèi)型[1，2]。異常檢測(cè)即離群點(diǎn)檢測(cè)，通常情況下訓(xùn)練數(shù)據(jù)只包含正常樣本，然后在此基礎(chǔ)上對(duì)被測(cè)數(shù)據(jù)進(jìn)行檢測(cè)，判斷網(wǎng)絡(luò)是否存在異常。誤用檢測(cè)要求檢測(cè)前建立有標(biāo)定的正常數(shù)據(jù)和攻擊數(shù)據(jù)特征庫(kù)，檢測(cè)時(shí)通過(guò)匹配被檢測(cè)數(shù)據(jù)的特征與標(biāo)定數(shù)據(jù)的符合程度判定入侵是否發(fā)生，這是一種有指導(dǎo)的基于正常、攻擊樣本庫(kù)的入侵檢測(cè)方法。相對(duì)于異常檢測(cè)技術(shù)來(lái)說(shuō)，這種檢測(cè)技術(shù)由于有攻擊樣本庫(kù)的支持，具有誤報(bào)率低、檢測(cè)率高的特點(diǎn)，從而得到了廣泛的研究與應(yīng)用。有指導(dǎo)入侵檢測(cè)中，關(guān)鍵環(huán)節(jié)是入侵檢測(cè)訓(xùn)練樣本庫(kù)的建立，樣本過(guò)多會(huì)消耗大量的系統(tǒng)資源，降低訓(xùn)練過(guò)程的實(shí)時(shí)性，從而不便于實(shí)際系統(tǒng)中訓(xùn)練庫(kù)的及時(shí)更新。為了能夠提出一種高實(shí)時(shí)性的入侵檢測(cè)模型，本文采用壓縮近鄰法[3]，去掉訓(xùn)練樣本庫(kù)中不利于分類(lèi)的冗余樣本，在大幅減少訓(xùn)練樣本數(shù)量的情況下，保持檢測(cè)效果，從而提高入侵檢測(cè)模型的實(shí)時(shí)性。相對(duì)于其他方法，本文提出的入侵檢測(cè)模型只需使用極少的訓(xùn)練樣本，具有系統(tǒng)資源消耗低、檢測(cè)實(shí)時(shí)性高等特點(diǎn)。

1 研究現(xiàn)狀及存在的問(wèn)題

由于有指導(dǎo)入侵檢測(cè)系統(tǒng)具有檢測(cè)準(zhǔn)確性高、誤報(bào)率低的特點(diǎn)，近年來(lái)取得了很快的發(fā)展。就近兩年的發(fā)展情況來(lái)看，2008年，Orfila等人[4]提出了一種基于多重代理和自動(dòng)化決策的入侵檢測(cè)系統(tǒng)，融合了多種技術(shù)，取得了較好的檢測(cè)效果，但也需要大量訓(xùn)練樣本進(jìn)行訓(xùn)練;2009年Aydin等人[5]提出了一種混合誤用檢測(cè)和異常檢測(cè)的入侵檢測(cè)系統(tǒng)，有機(jī)結(jié)合了兩種檢測(cè)方式的優(yōu)點(diǎn)，但入侵檢測(cè)系統(tǒng)中的誤用入侵檢測(cè)也需要大樣本庫(kù)的支持;此外，Sandhya等人[6]采用決策樹(shù)結(jié)合支持向量機(jī)構(gòu)建了智能的入侵檢測(cè)模型;Simon等人[7]提出了一種基于混合人工免疫系統(tǒng)、SOM神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)入侵檢測(cè)機(jī)制，取得了較好的檢測(cè)效果。新的方法不斷被提出，但是都面臨基于大量訓(xùn)練樣本進(jìn)行學(xué)習(xí)的過(guò)程。而訓(xùn)練樣本量過(guò)多造成了學(xué)習(xí)效率的下降，從而降低了檢測(cè)模型的實(shí)時(shí)性。入侵檢測(cè)中，實(shí)時(shí)性是一個(gè)非常重要的問(wèn)題。本文以此為出發(fā)點(diǎn)，采用壓縮近鄰法去除訓(xùn)練樣本中的冗余數(shù)據(jù)，大幅降低樣本數(shù)量，提升了訓(xùn)練過(guò)程的實(shí)時(shí)性，并在這個(gè)過(guò)程中，保持模型的檢測(cè)率，控制誤報(bào)率。

2 基于壓縮近鄰法的高效入侵檢測(cè)模型

為了對(duì)本文所提出的基于壓縮近鄰法的入侵檢測(cè)模型(intrusion detection model adopting condensed nearest neighbor rules， IDMCNN)進(jìn)行詳細(xì)的說(shuō)明，本章采用圖1所示的數(shù)據(jù)流圖解釋該模型的數(shù)據(jù)流向。圖1中，數(shù)據(jù)流D1表示按一定格式存取的原始訓(xùn)練數(shù)據(jù)。在實(shí)際的工程應(yīng)用中，訓(xùn)練庫(kù)使用專(zhuān)家系統(tǒng)生成，并且隨著網(wǎng)絡(luò)狀況的不斷變化進(jìn)行更新，以便入侵檢測(cè)系統(tǒng)具有自適應(yīng)性。本文模型將原始數(shù)據(jù)輸入訓(xùn)練集精簡(jiǎn)單元，目的是去除冗余的、不必要的訓(xùn)練數(shù)據(jù)，從而提高后續(xù)模塊的運(yùn)行效率。圖1中虛線框里面是模型的訓(xùn)練和檢測(cè)單元，可采用目前的各種機(jī)器學(xué)習(xí)方法，如神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)(SVM)或者近鄰法等，本文采用近鄰法。實(shí)際的檢測(cè)數(shù)據(jù)D4來(lái)自被保護(hù)的網(wǎng)絡(luò)所采集的信息，這些信息可以是協(xié)議類(lèi)型、端口號(hào)、單位時(shí)間進(jìn)出流量等。為了使得本文模型具有自適應(yīng)性，需要不斷更新訓(xùn)練庫(kù)。D6根據(jù)檢測(cè)結(jié)果和被測(cè)數(shù)據(jù)信息，按照指定格式處理成系統(tǒng)能識(shí)別的更新數(shù)據(jù)信息，定期增量更新訓(xùn)練庫(kù)。

2.1 壓縮近鄰法介紹

在圖1中，精簡(jiǎn)訓(xùn)練集單元采用壓縮近鄰法去除正常數(shù)據(jù)、攻擊數(shù)據(jù)分類(lèi)超平面附近的交叉混淆數(shù)據(jù)和遠(yuǎn)離分類(lèi)面的冗余數(shù)據(jù)，從而達(dá)到精簡(jiǎn)數(shù)據(jù)的目的[3]。為了對(duì)該方法有一個(gè)清楚的認(rèn)識(shí)，本節(jié)對(duì)壓縮近鄰法作理論上的介紹。壓縮近鄰法實(shí)施之前，需要采用重復(fù)剪輯近鄰法去除分類(lèi)超平面附近的交叉混淆數(shù)據(jù)，因此先介紹重復(fù)剪輯近鄰法。

1)重復(fù)剪輯近鄰法

該方法是對(duì)剪輯近鄰法的改進(jìn)，可以用于去除分類(lèi)超平面附近的混淆數(shù)據(jù)，得到精簡(jiǎn)訓(xùn)練(參考)集，具體步驟如下:

a)將訓(xùn)練樣本集合χN隨機(jī)劃分為S個(gè)子集，S≥3。χN={χ1，χ2，…，χS}。

b)用χ2為參考集，對(duì)χ1進(jìn)行1近鄰或k近鄰分類(lèi);用χ3為參考集，對(duì)χ2進(jìn)行1近鄰或k近鄰分類(lèi)，等等。依此類(lèi)推至用χ1為參考集，對(duì)χS進(jìn)行k近鄰分類(lèi)。

c)步驟b)完成后，統(tǒng)一刪除被錯(cuò)誤分類(lèi)的樣本。

d)用留下來(lái)的樣本集χE1，χE2，…，χES的合集χN′，作為剪輯后的訓(xùn)練(參考)集。

重復(fù)剪輯近鄰法的目的是為了刪除分類(lèi)超平面附近交叉混淆的正常數(shù)據(jù)和攻擊數(shù)據(jù)。然而對(duì)于有些分類(lèi)方法來(lái)說(shuō)，如本文實(shí)驗(yàn)采用的近鄰法，遠(yuǎn)離分類(lèi)面的數(shù)據(jù)對(duì)于分類(lèi)來(lái)說(shuō)也是無(wú)用的、冗余的。為了去除這些數(shù)據(jù)，可采用壓縮近鄰法。

2)壓縮近鄰法

a)對(duì)剪輯后的訓(xùn)練樣本集χN′設(shè)置兩個(gè)存儲(chǔ)器store和grabbag。

b)將χN′的所有樣本放入grabbag中。

c)從grabbag中隨機(jī)取兩個(gè)樣本x1∈ω1，x2∈ω2，放入store中;ω1、ω2分別代表正常和攻擊兩個(gè)類(lèi)別。

d)從grabbag中取出一個(gè)樣本xk，用store中的樣本做參考集，采用近鄰法對(duì)xk分類(lèi)。若分類(lèi)正確，刪除xk; 否則，xk放入store中。

e)對(duì)grabbag中所有樣本進(jìn)行步驟d)的操作，直到grabbag為空。

f)對(duì)x1、x2進(jìn)行步驟d)的操作。

最后，store中存放的就是壓縮精簡(jiǎn)后的訓(xùn)練樣本集χN″，χN″中已經(jīng)去除了遠(yuǎn)離分類(lèi)面的冗余數(shù)據(jù)。

2.2 高效性分析

本文入侵檢測(cè)模型中的檢測(cè)單元，采用K近鄰法進(jìn)行入侵和攻擊的分類(lèi)，因此性能提升主要體現(xiàn)在K近鄰分類(lèi)算法的性能提升上。由于K近鄰法中存在著大量的歐氏距離計(jì)算，計(jì)算次數(shù)與訓(xùn)練參考集中的樣本數(shù)量緊密相關(guān)。若能大幅減少訓(xùn)練樣本，K近鄰分類(lèi)法中的歐氏距離計(jì)算量將會(huì)大幅降低，其性能必定會(huì)明顯提高。

3 實(shí)驗(yàn)

為了驗(yàn)證基于壓縮近鄰法的入侵檢測(cè)模型的檢測(cè)性能，本章提出并實(shí)現(xiàn)了一種網(wǎng)絡(luò)入侵檢測(cè)實(shí)驗(yàn)仿真方案，驗(yàn)證了模型的有效性。

3.1 實(shí)驗(yàn)方案

本文實(shí)驗(yàn)數(shù)據(jù)采用美國(guó)國(guó)防部高級(jí)計(jì)劃研究局(DARPA)1999年用于入侵檢測(cè)系統(tǒng)評(píng)估的KDD CUP99數(shù)據(jù)集[8]，該數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集兩大部分，每種數(shù)據(jù)集各包含normal、DoS、Probe、R2L、U2R五類(lèi)數(shù)據(jù)。本文從kddcup.data_10_percent_corrected訓(xùn)練集中，隨機(jī)抽取了正常數(shù)據(jù)9 728條，攻擊數(shù)據(jù)6 584條(其中DoS攻擊3 915條，Probe攻擊2 054條，R2L攻擊563條和U2R攻擊52條)，然后將正常數(shù)據(jù)與攻擊數(shù)據(jù)混合組成訓(xùn)練集。從correct數(shù)據(jù)集中抽取了6 060條正常數(shù)據(jù)和5 669條攻擊數(shù)據(jù)(DoS攻擊2 299條，Probe攻擊2 083條，R2L攻擊1 059條和U2R攻擊228條)，組成測(cè)試集。采用MATLAB 6.1 for Windows XP作為訓(xùn)練和測(cè)試的仿真工具平臺(tái)。具體的實(shí)驗(yàn)步驟如下:

a)首先分別對(duì)原始訓(xùn)練集χN中的正常數(shù)據(jù)和攻擊數(shù)據(jù)隨機(jī)分成10個(gè)子集，按照重復(fù)剪輯近鄰法對(duì)原始數(shù)據(jù)集進(jìn)行精簡(jiǎn)，得到一個(gè)新的訓(xùn)練集χN′。

b)利用壓縮近鄰法，對(duì)步驟a)中的χN′進(jìn)一步精簡(jiǎn)，壓縮刪減冗余樣本，得到χN″。

c)利用K近鄰法，使用χN″作為參考集，對(duì)測(cè)試數(shù)據(jù)集χT進(jìn)行入侵檢測(cè)的識(shí)別，得到檢測(cè)率、誤報(bào)率兩個(gè)代表入侵檢測(cè)算法性能的指標(biāo)。

3.2 實(shí)驗(yàn)結(jié)果與對(duì)比

由3.1節(jié)中的實(shí)驗(yàn)步驟得知，采用壓縮近鄰法精簡(jiǎn)訓(xùn)練集之前，需采用重復(fù)剪輯近鄰法對(duì)訓(xùn)練樣本進(jìn)行處理，用于去除正常數(shù)據(jù)、攻擊數(shù)據(jù)分類(lèi)超平面間的混淆數(shù)據(jù)。經(jīng)過(guò)實(shí)驗(yàn)得到如表1所示的結(jié)果。

表1 重復(fù)剪輯近鄰法剪輯結(jié)果

子集

正常數(shù)據(jù)

剪輯前剪輯后

攻擊數(shù)據(jù)

剪輯前剪輯后

1936932671563

2905903664655

3927922659648

4919889649616

5958954640624

6941940673620

7916911661608

8963958626567

91 0461 044668664

101 2171 193673602

合計(jì)9 7289 6466 5846 167

從表1的實(shí)驗(yàn)結(jié)果可以看出，重復(fù)剪輯近鄰法應(yīng)用到本文的訓(xùn)練集上，并沒(méi)有大幅減少樣本數(shù)量。這說(shuō)明本文的訓(xùn)練集，處于正常、攻擊兩類(lèi)數(shù)據(jù)分類(lèi)超平面附近的混淆區(qū)數(shù)據(jù)比較少，大部分?jǐn)?shù)據(jù)都處于分類(lèi)超平面兩端，冗余性較高。為了去除這些冗余的數(shù)據(jù)，采用壓縮近鄰法進(jìn)一步精簡(jiǎn)訓(xùn)練集，得到如表2所示的結(jié)果。

表2 壓縮近鄰法精簡(jiǎn)訓(xùn)練集效果

子集

正常數(shù)據(jù)

壓縮前壓縮后

攻擊數(shù)據(jù)

壓縮前壓縮后

1936932671563

193255636

290336555

392226486

4889461610

595436246

694056208

791126089

895835676

9104416643

10119316027

合計(jì)964629616766

從表2可以看出，壓縮近鄰法可以大幅減少訓(xùn)練樣本數(shù)量:正常樣本數(shù)量從9 646降低為29，攻擊樣本數(shù)量從6 167降低為66。精簡(jiǎn)后的訓(xùn)練集，是對(duì)入侵檢測(cè)分類(lèi)來(lái)說(shuō)有用的訓(xùn)練集，為了驗(yàn)證精簡(jiǎn)后的訓(xùn)練集在K近鄰法入侵檢測(cè)中的性能。本節(jié)根據(jù)3.1節(jié)中提到的測(cè)試方案，用測(cè)試數(shù)據(jù)集驗(yàn)證入侵檢測(cè)模型的檢測(cè)性能。評(píng)價(jià)標(biāo)準(zhǔn)采用國(guó)際上通用的檢測(cè)率(true positive rate， TP)和誤報(bào)率(1 positive rate， FP)，其定義如式(1)(2):

檢測(cè)率(TP)=被發(fā)現(xiàn)的攻擊樣本數(shù)攻擊樣本的總數(shù)(1)

誤報(bào)率(FP)=被誤判的正確樣本數(shù)正確樣本的總數(shù)(2)

為了驗(yàn)證本文方案的實(shí)驗(yàn)結(jié)果的有效性，針對(duì)同樣的數(shù)據(jù)集，本文分別采用BP神經(jīng)網(wǎng)絡(luò)、SOM神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)(SVM)以及無(wú)參數(shù)的分類(lèi)方法1近鄰法(NN)、K近鄰法(KNN)、剪輯近鄰法(edit KNN)進(jìn)行檢測(cè)效果的對(duì)比。對(duì)每一種方法，根據(jù)具體參數(shù)或k的取值的不同，基于同一數(shù)據(jù)集，進(jìn)行九組實(shí)驗(yàn)，取平均數(shù)據(jù)，得到檢測(cè)率、誤報(bào)率兩個(gè)指標(biāo)結(jié)果，如圖2所示。

由圖2可以看出，本文方法相對(duì)于其他方法來(lái)說(shuō)，檢測(cè)率并沒(méi)有降低，只是誤報(bào)率稍高，考慮到訓(xùn)練集的大幅精簡(jiǎn)，這也在可接受的合理范圍之內(nèi)。精簡(jiǎn)訓(xùn)練集是為了提高實(shí)時(shí)性，為了對(duì)精簡(jiǎn)后的訓(xùn)練集對(duì)入侵檢測(cè)模型實(shí)時(shí)性提高有一個(gè)量化的認(rèn)識(shí)，本文對(duì)比了壓縮近鄰法和K近鄰法以及剪輯近鄰法在測(cè)試集上進(jìn)行入侵檢測(cè)試驗(yàn)的時(shí)間消耗，得到如圖3所示的結(jié)果。

圖3表明，精簡(jiǎn)后的訓(xùn)練集可以大幅降低近鄰分類(lèi)法的檢測(cè)時(shí)間消耗，這是因?yàn)槿コ巳哂嗟臉颖荆瑴p少了大量的歐氏距離計(jì)算。綜上所述，本文模型能夠在保持檢測(cè)效果的情況下，大幅精簡(jiǎn)樣本數(shù)量，提升模型的實(shí)時(shí)性，因此本文提出的入侵檢測(cè)模型是一種具有實(shí)際工程應(yīng)用價(jià)值的、高效的入侵檢測(cè)方法。

4 結(jié)束語(yǔ)

本文針對(duì)有監(jiān)督入侵檢測(cè)領(lǐng)域中的訓(xùn)練集冗余問(wèn)題和檢測(cè)模型運(yùn)算的實(shí)時(shí)性問(wèn)題，提出了基于壓縮近鄰法的入侵檢測(cè)模型。實(shí)驗(yàn)證明，該模型能夠在保證檢測(cè)效果的情況下，大幅減少用于訓(xùn)練的正常和攻擊樣本數(shù)量，從而提高訓(xùn)練速度和入侵檢測(cè)模型的實(shí)時(shí)性，是一種計(jì)算上高效的有指導(dǎo)入侵檢測(cè)模型，適合于部署在計(jì)算資源不夠充足的系統(tǒng)中。但是，本文方法較其他方法誤報(bào)率稍高，因此不適合部署于對(duì)誤報(bào)較為敏感的系統(tǒng)中。此時(shí)應(yīng)考慮和其他方法組成混合檢測(cè)模型，降低誤報(bào)率，以對(duì)檢測(cè)模型作進(jìn)一步的改進(jìn)和提升。

參考文獻(xiàn):

[1]BACE R G. Intrusion detection[M].[S.l.]: Macmillan Technical Publishing， 2000.

[2]李輝， 管曉宏， 昝鑫，等. 基于支持向量機(jī)的網(wǎng)絡(luò)入侵檢測(cè)[J]. 計(jì)算機(jī)研究與發(fā)展，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， ButterworthHeinemann[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].