李 蓉， 周維柏

(華南師范大學(xué)增城學(xué)院，廣東廣州 511363)

0 引言

現(xiàn)在網(wǎng)絡(luò)攻擊手段不斷變化，導(dǎo)致網(wǎng)絡(luò)入侵檢測(cè)與防御機(jī)制需不斷更新。由于正常流量與入侵流量常常容易混淆，致使入侵檢測(cè)系統(tǒng)常發(fā)出大量的虛警，因此提升網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的報(bào)警正確率是網(wǎng)絡(luò)安全管理的一個(gè)非常重要的課題。

基于流量異常的檢測(cè)的常用方法有:基于域值的檢測(cè)方法、基于小波的檢測(cè)方法、基于統(tǒng)計(jì)的檢測(cè)方法、基于馬爾可夫等隨機(jī)過(guò)程模型的方法和一些基于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和神經(jīng)網(wǎng)絡(luò)等檢測(cè)方法［1-6］，但這些方法主要存在報(bào)警意義不明確、可擴(kuò)展性較差、協(xié)同運(yùn)行差。

分類(lèi)法主要是將網(wǎng)絡(luò)流量分類(lèi)，根據(jù)群聚特性，將發(fā)生頻率稀少的流量類(lèi)型定義為異常，分類(lèi)技術(shù)有SVM、決策樹(shù)、貝氏分類(lèi)器等。但由于分群復(fù)雜度高，常造成難以在合理時(shí)間內(nèi)得出最佳分群解，K-Means算法是一種最普遍也最廣泛應(yīng)用的分群技術(shù)［7-11］，但由于K-Means的目標(biāo)函數(shù)不是凸面(Convex)函數(shù)，故可能包含許多區(qū)域最小值。近年來(lái)不少學(xué)者應(yīng)用各種人工智能算法來(lái)求近似解，主要有基因算法、粒子分群算法及差分算法，三者都是以族群為基礎(chǔ)的演變算法，比較不會(huì)受到初始解的選擇而陷入?yún)^(qū)域最佳解的情況。但差分算法仍會(huì)因初始解的選擇不好而造成執(zhí)行時(shí)間過(guò)長(zhǎng)的情況，依然有可能陷入?yún)^(qū)域最佳解。為解決此問(wèn)題，本文算法結(jié)合K-Means算法和差分算法來(lái)找出最佳分群解;由K-Means快速分群求得局部最佳解，再利用差分算法求得全域最佳解，找出樣本分群最佳群數(shù)，正確識(shí)別出正常行為和異常行為，實(shí)驗(yàn)表明此算法能快速有效地進(jìn)行入侵檢測(cè)。

1 K-Means算法

K-Means分群算法屬于分割式算法。具體步驟如下:

Step1:隨機(jī)選擇k個(gè)樣本作為初始聚類(lèi)中心。

Step2:計(jì)算每個(gè)樣本與各群群中心的距離。

Step3:根據(jù)Step2的結(jié)果將各樣本分派給距離最近的群。

Step4:重新計(jì)算各群的群中心。

Step5:重復(fù)Step2至Step4，直到各群的群中心不再變動(dòng)為止。

K-Means算法的優(yōu)點(diǎn)是方法簡(jiǎn)單，可以快速獲得解，但利用隨機(jī)方式選取群組中心將影響算法的魯棒性和正確性，而且必須預(yù)先要知道聚類(lèi)個(gè)數(shù)k，各群的樣本分布必須呈圓形分布，必須要有類(lèi)似的大小時(shí)才可能得到最佳解，無(wú)法識(shí)別孤立樣本。

因此本文結(jié)合密度、網(wǎng)格［12］和統(tǒng)計(jì)方法的概念，將初始群組中心這步驟獨(dú)立出來(lái)，把算法規(guī)劃為兩個(gè)階段來(lái)執(zhí)行:①選取初始群組中心、識(shí)別孤立樣本;②根據(jù)第一階段的結(jié)果執(zhí)行原始K-Means算法。具體步驟如下:

(1)階段一。選取初始群組中心、識(shí)別孤立樣本。

Step1:量化樣本空間成為多個(gè)網(wǎng)格，并分配樣本到所屬的網(wǎng)格，同時(shí)計(jì)算各網(wǎng)格內(nèi)樣本的平均值。

Step2:計(jì)算所有網(wǎng)格樣本量的平均值與標(biāo)準(zhǔn)差。

Step3:根據(jù)平均值與標(biāo)準(zhǔn)差標(biāo)記出核心網(wǎng)格與孤立網(wǎng)格。

Step4:連結(jié)相鄰的核心網(wǎng)格。

Step5:計(jì)算相連核心網(wǎng)格內(nèi)樣本的平均值，并將此平均值視為初始群組中心。

(2)階段二。以第一階段所選取的初始群組中心執(zhí)行K-Means算法，孤立網(wǎng)格內(nèi)的樣本不納入運(yùn)算。

Step1:計(jì)算所有樣本到各群組中心的距離。

Step2:分配各樣本到距離最近(相似度最高)的群組。

Step3:計(jì)算各群組內(nèi)樣本的平均值，以決定新的群組中心。

Step4:重復(fù)以上3個(gè)步驟，直到各群的群中心不再變動(dòng)為止。

2 差分算法

差分算法是一種以群體為基礎(chǔ)來(lái)進(jìn)行空間隨機(jī)搜尋的最優(yōu)化方法。算法過(guò)程如下:

(1)突變。隨機(jī)選取 3 個(gè)向量 Xr1，G、Xr2，G、Xr3，G，通過(guò)突變因子F取得合成向量Vi，G+1。運(yùn)算公式:

(2)重組。將合成向量與群體中所挑選出來(lái)的目標(biāo)向量Xi，G，通過(guò)交配率CR的選擇進(jìn)行交配并產(chǎn)生試驗(yàn)向量。

(3)選擇。通過(guò)適應(yīng)值函數(shù)來(lái)評(píng)估目標(biāo)向量和試驗(yàn)向量的適應(yīng)值。選擇適應(yīng)值最好的一方進(jìn)入下一世代，成為下一世代的目標(biāo)向量。

3 本文算法

本研究主要是結(jié)合K-Means分群算法和差分算法，應(yīng)用于網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)，使用分群技術(shù)將異常樣本進(jìn)行區(qū)分找出入侵行為。在算法開(kāi)始前必須先將數(shù)據(jù)樣本做前期處理，再運(yùn)用K-Means分群算法調(diào)整群中心位置以尋找較佳群中心，接著執(zhí)行差分算法，尋找出最適當(dāng)?shù)姆秩航M數(shù)與分群結(jié)果。檢測(cè)時(shí)利用樣本與各群組間的距離來(lái)識(shí)別是屬于異?；蛘Ｈ航M。算法流程圖如圖1所示。

圖1 本算法流程圖

3.1 樣本前期處理

本研究使用KDD CUP99數(shù)據(jù)集來(lái)評(píng)估此算法的識(shí)別效果。KDD CUP99數(shù)據(jù)集是由哥倫比亞大學(xué)IDS實(shí)驗(yàn)室整理形成的安全審計(jì)數(shù)據(jù)集［13-15］。數(shù)據(jù)類(lèi)型分為連續(xù)和離散。將離散類(lèi)型依其應(yīng)用如ftp、http等按英文字母順序的代號(hào)進(jìn)行編號(hào)處理，轉(zhuǎn)化為數(shù)字?jǐn)?shù)據(jù)，連續(xù)屬性的數(shù)字落差太大需采用正規(guī)化處理。本算法采用min-max正規(guī)化處理，公式如下:

其中:xi為第i個(gè)數(shù)據(jù)中連續(xù)的屬性值;xmin為屬性的最小值;xmax為屬性的最大值為修正后的屬性值。

3.2 利用K-Means算法作初始分群

大部分的分群技術(shù)都是計(jì)算連續(xù)數(shù)據(jù)，但K-Means算法也可以處理離散數(shù)據(jù)。系統(tǒng)一開(kāi)始先調(diào)整離散數(shù)據(jù)和連續(xù)數(shù)據(jù)的數(shù)值范圍，接著用K-Means算法調(diào)整群中心的位置尋找較佳群中心位置，讓封包的樣本更適合初始分群。

(1)進(jìn)行分群。將所有樣本分別指派到與群中心最近的位置。

先對(duì)每一筆樣本，計(jì)算其歸屬于那一個(gè)群中心。連續(xù)數(shù)據(jù)的距離計(jì)算是由對(duì)每個(gè)樣本到每個(gè)群中心的連續(xù)數(shù)據(jù)計(jì)算得到。而離散數(shù)據(jù)的每一樣本到每個(gè)群心位置之間的距離的計(jì)算方式是離散數(shù)據(jù)在分群中出現(xiàn)的次數(shù)(最小的為1)，再除以分群樣本總數(shù)。連續(xù)數(shù)據(jù)距離是運(yùn)用歐幾里德距離計(jì)算各樣本點(diǎn)到群中心距離，并將其歸類(lèi)到最近距離的群。

(2)重新計(jì)算新的群中心位置。重新計(jì)算連續(xù)數(shù)據(jù)、離散數(shù)據(jù)的群中心位置。

根據(jù)上一步分群結(jié)果，重新計(jì)算各群的群中心位置，其中計(jì)算連續(xù)數(shù)據(jù)群中心位置，計(jì)算方式是求出每一個(gè)群各屬性的平均值。而離散數(shù)據(jù)的群中心位置是重新計(jì)算各數(shù)據(jù)的支持度。計(jì)算方式是先計(jì)算子群的離散數(shù)據(jù)，和子群樣本個(gè)數(shù)，統(tǒng)計(jì)出現(xiàn)次數(shù)最多的離散數(shù)據(jù)的出現(xiàn)次數(shù)，出現(xiàn)次數(shù)最多的離散數(shù)據(jù)值為數(shù)據(jù)的群中心位置。

3.3 結(jié)合DK算法找出分群結(jié)果

若未經(jīng)K-Means算法作初始分群，會(huì)造成差分算法分群效果不佳。差分算法中，每個(gè)向量都是經(jīng)由目標(biāo)函數(shù)值評(píng)估后才得到保留適應(yīng)值，封包信息所構(gòu)成的每個(gè)向量都經(jīng)由突變、交配及選擇等運(yùn)算，最后用選擇評(píng)估適應(yīng)值保留最佳的向量，再由循環(huán)執(zhí)行的方式，來(lái)更新群中心位置，尋找出最佳的分群結(jié)果。

使用差分初始化分群的結(jié)果做突變機(jī)制，突變機(jī)制是在差分階段找到的解向量中隨機(jī)選取三個(gè)不同的解向量，彼此之間互相交叉運(yùn)算，創(chuàng)造出一個(gè)新的向量，在此新的向量又稱(chēng)為差分向量，利用突變來(lái)調(diào)整初始群中心的位置，使用下式創(chuàng)造出差分向量;)其中為差分階段找到的解向量中隨機(jī)選取 3個(gè)不同的解向量;F為比例系數(shù)，介于0～1之間的數(shù)。若選取的向量比原來(lái)向量的適應(yīng)度還差，經(jīng)突變和交配，有機(jī)會(huì)尋找出更好的解。

接著進(jìn)行交配，產(chǎn)生不同的群中心的子代，使用下式產(chǎn)生新的子代解向量

再利用目標(biāo)函數(shù)值計(jì)算交配后基因的適應(yīng)度，去進(jìn)行選擇動(dòng)作，使用下式做選擇動(dòng)作。

其中:為由突變、交配之后產(chǎn)生新的子代解向量為父代解向量;g為世代數(shù)。如此反復(fù)重新交配，更新最好的群中心位置，計(jì)算出差分算法后適應(yīng)度最好的分群結(jié)果，而群內(nèi)相異度低，表示分群的結(jié)果越好。

3.4 識(shí)別正常與異常群組

分群結(jié)果用來(lái)計(jì)算異常因子，計(jì)算群組之間的距離，來(lái)識(shí)別是屬于異常或正常群組。使用組內(nèi)平均距離的計(jì)算方式，計(jì)算方式主要是所有群組內(nèi)資料與群中心的位置相加，之后除以分群組數(shù)，最后輸出每群異常因子的結(jié)果，對(duì)群組的距離作排序，距離越大者為異常群組。

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)使用的 KDD CUP99數(shù)據(jù)集分為 Normal、PROBE、DoS、U2R、R2L共5類(lèi)網(wǎng)絡(luò)攻擊類(lèi)型，訓(xùn)練和測(cè)試樣本統(tǒng)計(jì)表如表1所示。

表1 訓(xùn)練和測(cè)試樣本統(tǒng)計(jì)表

為了判斷入侵檢測(cè)的效果，采取兩個(gè)重要的評(píng)估方法:檢測(cè)正確率(DR)/誤判率(FR)，

本算法不管初始解的好壞都可找到全域最佳解，因此本實(shí)驗(yàn)將群數(shù)值設(shè)定為30，比例系數(shù)設(shè)定為0.5，突變系數(shù)設(shè)為0.8，世代數(shù)設(shè)為2，解向量數(shù)設(shè)為5，并執(zhí)行10次，去平均數(shù)。對(duì)比實(shí)驗(yàn)中K-Means算法的群數(shù)設(shè)為30，世代數(shù)設(shè)為500。

DoS攻擊檢測(cè)結(jié)果如表2所示，U2R攻擊檢測(cè)結(jié)果如表3，R2L攻擊檢測(cè)結(jié)果如表4，PROBE攻擊檢測(cè)結(jié)果如表5。誤報(bào)率的統(tǒng)計(jì)結(jié)果如表6。各種網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的檢測(cè)率比較如表7。

表2 DoS攻擊檢測(cè)結(jié)果

由表2可看出，在DoS攻擊中，本算法對(duì) back、smurf和 teardrop這三種攻擊檢測(cè)率為 100%，對(duì)apache2攻擊本算法的檢測(cè)率比K-Means高0.16%，對(duì)land攻擊本算法的檢測(cè)率比K-Means高11%，對(duì)smurf攻擊本算法的檢測(cè)率比K-Means高0.05%.

表3 U2R攻擊檢測(cè)結(jié)果

由表3可看出，在U2R攻擊中，對(duì)buffer_overflow、httptunnel、ps、sqlattack、xterm 這 5 種攻擊本算法的檢測(cè)率比K-Means都要好。

表4 R2L攻擊檢測(cè)結(jié)果

由表4可看出，在R2L攻擊中，對(duì)ftp_write、guess_passwd、imap、multihop、warezmaster這 5 種攻擊本算法的檢測(cè)率比K-Means基本都一樣。但對(duì)phf攻擊本算法的檢測(cè)率比K-Means要高50%。由表5可看出，在PROBE攻擊中，各種攻擊本算法的檢測(cè)率比K-Means都要好。由表2～6可看出，本算法在DoS、U2R、R2L、Probe各種攻擊類(lèi)型的檢測(cè)能力比K-Means算法要好，提高了分群的準(zhǔn)確率，改善K-Means算法的誤判率，達(dá)到降低誤判率的效果。

表5 Probe攻擊檢測(cè)結(jié)果

表6 誤報(bào)率的統(tǒng)計(jì)結(jié)果

表7 各種網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的檢測(cè)率比較

5 結(jié)語(yǔ)

隨著互聯(lián)網(wǎng)的迅速發(fā)現(xiàn)，各種應(yīng)用程序的蓬勃發(fā)展伴隨著更多的安全漏洞，以及網(wǎng)絡(luò)惡意行為已發(fā)展為龐大的地下經(jīng)濟(jì)行為，現(xiàn)在攻擊手段更新快，這就要求檢測(cè)技術(shù)也需不斷更新。本文結(jié)合多種分類(lèi)算法的方式進(jìn)行分類(lèi)，由K-Means快速分群求得局部最佳解，再利用差分算法求得全域最佳解。實(shí)驗(yàn)結(jié)果顯示此改進(jìn)方法對(duì)入侵檢測(cè)有較好的效果。

［1］毛伊敏，楊路明，陳志剛，等.基于數(shù)據(jù)流挖掘技術(shù)的入侵檢測(cè)模型與算法［J］.中南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，42(9):2720-2728.

MAO Yi-min，YANG Lu-ming，CHEN Zhi-gang，et al.An intrusion detection model based on data mining over data［J］.Journal of Central South University(Science and Technology)，2011，42(9):2720-2728.

［2］劉衍珩，田大新，余雪崗，等.基于分布式學(xué)習(xí)的大規(guī)模網(wǎng)絡(luò)入侵檢測(cè)算法［J］.軟件學(xué)報(bào)，2008，19(4):993-1003.

LIU Yan-Heng，TIAN Da-Xin，YU Xue-Gang，et al.Large-Scale Network Intrusion Detection Algorithm Based on Distributed Learning［J］.Journal of Software，2008，19(4):993-1003.

［3］易曉梅，陳波，蔡家楣.入侵檢測(cè)的進(jìn)化神經(jīng)網(wǎng)絡(luò)研究［J］.計(jì)算機(jī)工程，2009，35(2):208-209，213.

YI Xiao-mei，CHEN Bo，CAI Jia-mei.Research on Evolutionary Neural Network of Intrusion Detection［J］.Computer Engineering，2009，35(2):208-209，213.

［4］努爾布力，柴勝，李紅煒，等.一種基于Choquet模糊積分的入侵檢測(cè)警報(bào)關(guān)聯(lián)方法［J］.電子學(xué)報(bào)，2011，39(12):2741-2747.

Nurbol，CHAI Sheng，LI Hong-wei，et al.Intrusion Detection Alert Correlation Based on Choquet Fuzzy Integral［J］.Acta Electronica Sinica，2011，39(12):2741-2747.

［5］楊雅輝，杜克明.全網(wǎng)異常流量簇的檢測(cè)與確定機(jī)制［J］.計(jì)算機(jī)研究與發(fā)展，2009，64(11):1847-1853.

YANG Ya-hui，DU Ke-ming.Identification of Anomalous Traffic Clusters for Network-Wide Anomaly Analysis［J］.Journal of Computer Research and Development，2009，64(11):1847-1853.

［6］程國(guó)振，程?hào)|年，俞定玖.基于多尺度低秩模型的網(wǎng)絡(luò)異常流量檢測(cè)方法［J］.通信學(xué)報(bào)，2012，33(1):182-190.

CHENG Guo-zhen，CHENG Dong-nian，YU Ding-jiu.Network traffic detection based on multi-resolution low rank model［J］.Journal on Communications，2012，33(1):182-190.

［7］馮 波，郝文寧，陳剛占，等.K-Means算法初始聚類(lèi)中心選擇的優(yōu)化［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49(14):182-192.

FENG Bo，HAO Wen-ning，CHEN Gang，et al.Optimization to K-means initial cluster centers［J］. Computer Engineering and Applications，2013，49(14):182-185.

［8］於躍成，王建東，鄭關(guān)勝，等.基于約束信息的并行K-Means算法［J］.東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，41(3):505-508.

YU Yue-cheng，WANG Jian-dong， ZHENG Guan-sheng，et al.Parallel K-Means Algorithm based on constrained information［J］.Journal of Southeast University(Natural Science Edition)，2011，41(3):505-508.

［9］李大字，錢(qián)麗，靳其兵，等.改進(jìn)的全局K'-Mmeans算法及其在數(shù)據(jù)分類(lèi)中的應(yīng)用［J］.信息與控制2011，40(1):100-104.

LI Da-zi，QIAN Li，JIN Qi-bing，et al.Modified Global K'-Means Algorithm and Its Application to Data Clustering［J］.Information and Control，2011，40(1):100-104.

［10］黎銀環(huán)，張 劍.改進(jìn)的 K-Means算法在入侵檢測(cè)中的應(yīng)用［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013，23(1):165-168.

LI Yin-huan， ZHANG Jian.Application of Improved K-Means Clustering Algorithm in Intrusion Detection［J］. Computer Technology and Development，2013，23(1):165-168.

［11］傅 濤，孫亞民.基于PSO的K-Means算法及其在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用［J］.計(jì)算機(jī)科學(xué)，2011，38(5):54-55.

FU Tao，SUN Ya-min.PSO-based K-Means Algorithm and its Application in Network Intrusion Detection System［J］.Computer Science，2011，38(5):54-55.

［12］任家東，孟麗麗，張冬梅.一種基于網(wǎng)格的改進(jìn)的K-Means聚類(lèi)算法［J］.計(jì)算機(jī)研究與發(fā)展，2009，46(l):453-458.

REN Jia-dong，MENG Li-li，ZHANG Dong-mei.An Improved KMeans Clustering Algorithm Based on Grid［J］.Journal of Computer Research and Development，2009，46(l):453-458.

［13］Hettich S，Bay S D.KDD cup 1999 data［EB/OL］.http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html，1999.

［14］張新有，曾華燊，賈 磊.入侵檢測(cè)數(shù)據(jù)集KDD CUP99研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(22):4809-4816.

ZHANG Xin-you，ZENG Hua-shen，JIA Lei.Research of intrusion detection system dataset-KDD CUP99［J］.Computer Engineering and Design，2010，31(22):4809-4816.

［15］谷保平，許孝元，郭紅艷.基于粒子群優(yōu)化的k均值算法在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2007，27(6):1368-1370.

GU Bao-ping，XU Xiao-yuan，GUO Hong-yan.Research of K-Means algorithm based on particle swarm optimization in network intrusion detection［J］.Computer Applications，2007，27(6):1368-1370.