朱 健，盧秉亮，曲超毅

（1.沈陽航空職業(yè)技術(shù)學(xué)院，沈陽110034；2.沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽110136；3.中航工業(yè)沈陽飛機(jī)工業(yè)（集團(tuán)）有限公司，沈陽110034）

聚類算法在入侵檢測中的應(yīng)用研究

朱 健1，盧秉亮2，曲超毅3

（1.沈陽航空職業(yè)技術(shù)學(xué)院，沈陽110034；2.沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽110136；3.中航工業(yè)沈陽飛機(jī)工業(yè)（集團(tuán)）有限公司，沈陽110034）

應(yīng)用聚類算法對入侵檢測數(shù)據(jù)集進(jìn)行聚類，通過對其聚類結(jié)果的分析，發(fā)現(xiàn)聚類的部分簇中存在劃分不夠緊湊的問題。為此，提出應(yīng)用加權(quán)聚類算法對簇中與聚類中心距離較遠(yuǎn)的數(shù)據(jù)進(jìn)行聚類，解決了聚類結(jié)果中存在“子簇”的問題。結(jié)果表明，簇的緊湊性有較大提升，同時由于子簇?cái)?shù)量的減少使得檢測率有所提升，加快了檢測速度。

網(wǎng)絡(luò)安全；入侵檢測；聚類分析；加權(quán)聚類算法

1 引 言

隨著網(wǎng)絡(luò)技術(shù)的逐漸發(fā)展，不斷出現(xiàn)新的入侵和新類型的攻擊，為了解決此問題，必須應(yīng)用智能入侵檢測技術(shù)。常見的入侵檢測方法主要包括統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)、模式匹配、規(guī)則推理以及人工免疫理論等方法［1-3］。為了獲得網(wǎng)絡(luò)行為模式，需要通過帶標(biāo)簽數(shù)據(jù)或者完全正常的網(wǎng)絡(luò)行為數(shù)據(jù)進(jìn)行訓(xùn)練。然而，標(biāo)簽數(shù)據(jù)和完全正常的網(wǎng)絡(luò)行為數(shù)據(jù)是很難實(shí)現(xiàn)的，這是由于數(shù)據(jù)的海量性和復(fù)雜的網(wǎng)絡(luò)環(huán)境造成的。為了提高入侵檢測效率，以聚類（Clustering）為代表的無監(jiān)督入侵檢測算法［4-6］被用來直接處理無標(biāo)簽原始網(wǎng)絡(luò)數(shù)據(jù)。

通過使用應(yīng)用加權(quán)的聚類算法在局域網(wǎng)中進(jìn)行實(shí)際的入侵檢測驗(yàn)證，對DOS和Probe兩類攻擊進(jìn)行檢測，結(jié)果表明有較好的檢測性能，并對未知網(wǎng)絡(luò)入侵具有一定的自適應(yīng)性。

2 聚類分析算法

2.1 聚類算法進(jìn)行聚類的原理

聚類分析算法［7-8］可以描述為：給定m維空間R中的n個向量，把每個向量歸屬到k個聚類中的某一個，使得每一個向量與其聚類中心的距離最小。聚類可以理解為：類內(nèi)的相關(guān)性盡量大，類間相關(guān)性盡量小。在這里對鏈路流量進(jìn)行聚類，初始設(shè)定一個鏈路流量大的鏈路A作為類A和一個鏈路流量小的鏈路B作為類B。

2.2 聚類分析算法原理

聚類算法包括劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法［7］。典型的基于劃分的聚類分析算法是K-means算法：給定一個有N個元組或者紀(jì)錄的數(shù)據(jù)集構(gòu)造K個分組，每一個分組代表一個聚類，這里的K＜N。K個分組滿足下列條件：①每一個分組至少包含一個數(shù)據(jù)紀(jì)錄；②每一個數(shù)據(jù)紀(jì)錄屬于且僅屬于一個分組；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復(fù)迭代的方法改變分組，最終使得同一分組中的記錄越近，而不同分組中的紀(jì)錄越遠(yuǎn)。

K-means算法把n個向量xi（i＝1，2，…，n）分成k個類Gi（i＝1，2，…，k）并求每類的聚類中心，使得非相似性（或距離）指標(biāo)的目標(biāo)函數(shù)達(dá)到最小。當(dāng)選擇第i個類Gi中向量xl與相應(yīng)的聚類中心Ci間的度量為歐幾里德距離時，目標(biāo)函數(shù)可以定義為

這里Ji是類Gi內(nèi)的目標(biāo)函數(shù)，顯然J的大小取決于聚類中心Ci和Gi的形狀，J越小，表明聚類的效果越好。

K-means算法的基本思想是：

（1）首先從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；

（2）而對于剩下的其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；

（3）設(shè)U是一個c×n矩陣，若xj∈類i，則uij＝1，否則uij＝0，即當(dāng)‖Xj-Ci‖≤‖Xj-Ck‖（k≠j）時，uij＝1，否則uij＝0；

（4）根據(jù)uij計(jì)算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；

（5）根據(jù)uij計(jì)算標(biāo)準(zhǔn)測度函數(shù)的值，直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止，否則回到步驟（3）。

2.3 加權(quán)的聚類算法［7］

采用K-means算法也有其局限性，在聚類分析的時候，它考慮了所有因素，而且認(rèn)為這些因素對距離的影響是等同的［9］，會出現(xiàn)由不相關(guān)屬性導(dǎo)致的“維數(shù)陷阱”。要解決這一問題，需要對每一個屬性加上特征參數(shù)［10］，讓不同的屬性在聚類中起不同作用。從歐氏空間上來說就是拉長相關(guān)屬性對應(yīng)的軸，縮短無關(guān)屬性對應(yīng)的軸。為此，就要把目標(biāo)函數(shù)中的‖Xi-Ci‖2換為，這樣目標(biāo)函數(shù)J還依賴于權(quán)值Wj，權(quán)值的大小由經(jīng)驗(yàn)確定，從而解決“維數(shù)陷阱”問題。

3 聚類技術(shù)在入侵檢測中的應(yīng)用

3.1 應(yīng)用聚類分析進(jìn)行入侵檢測的基本思想

為了能夠?qū)崿F(xiàn)聚類，要求網(wǎng)絡(luò)環(huán)境中的正常網(wǎng)絡(luò)行為要遠(yuǎn)大于入侵網(wǎng)絡(luò)行為并且兩種行為必須是可以區(qū)分的，使得算法能夠?qū)⒕W(wǎng)絡(luò)行為數(shù)據(jù)集劃分為不同的類別，在實(shí)際網(wǎng)絡(luò)環(huán)境中，入侵網(wǎng)絡(luò)行為遠(yuǎn)小于正常網(wǎng)絡(luò)行為并且可以區(qū)別開來，因此在網(wǎng)絡(luò)入侵檢測中可以應(yīng)用聚類分析算法。聚類后的結(jié)果可以應(yīng)用簇標(biāo)記算法［11-12］判斷簇是正常網(wǎng)絡(luò)行為還是入侵網(wǎng)絡(luò)行為。

3.2 應(yīng)用聚類算法進(jìn)行入侵檢測主要過程

應(yīng)用聚類分析技術(shù)進(jìn)行入侵檢測主要經(jīng)過數(shù)據(jù)收集、特征向量標(biāo)準(zhǔn)化、聚類分析、標(biāo)記生成簇、實(shí)時檢測、結(jié)果驗(yàn)證等過程。

3.2.1 數(shù)據(jù)收集

將原始的網(wǎng)絡(luò)數(shù)據(jù)包恢復(fù)成TCP／IP層的連接，每個連接記錄包括網(wǎng)絡(luò)協(xié)議、起始時間、結(jié)束時間、端口號、源IP地址、目的IP地址、連接終止?fàn)顟B(tài)、TCP標(biāo)志等屬性。同時要記錄一段內(nèi)與當(dāng)前連接具有相同服務(wù)類型的連接數(shù)和錯誤的連接百分?jǐn)?shù)等。

3.2.2 特征向量標(biāo)準(zhǔn)化

聚類算法的輸入通常有 N個數(shù)據(jù)點(diǎn)的集合D＝｛x1，x2，…，xn｝，具有不同的特征向量，其單位也是不同的，如果直接進(jìn)行聚類會影響聚類結(jié)果，通過標(biāo)準(zhǔn)化處理將所有特征向量轉(zhuǎn)化為無單位，則可提高聚類結(jié)果的準(zhǔn)確性。

3.2.3 聚類分析

在這里對鏈路流量進(jìn)行聚類，初始設(shè)定兩個類，一個是類A，代表鏈路流量大的鏈路；另一個是類B，代表鏈路流量小的鏈路，然后使用加權(quán)K-means算法進(jìn)行聚類分析得到聚類結(jié)果。

K-means有其缺點(diǎn)，即產(chǎn)生類的大小相差不會很大并且對于“臟”數(shù)據(jù)很敏感，因此，要對初始聚類結(jié)果進(jìn)行優(yōu)化，使各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。聚類結(jié)果的具體評價標(biāo)準(zhǔn)［13］定義如下：

其中，δ（Ck，Cl）定義為簇間距離：

d（x，y）為記錄x與y的距離，Δ（Cm）定義為簇的直徑：

由公式2可知，簇的直徑越小，聚類結(jié)果越緊湊；簇間距離越大，各聚類之間的分割性越好，公式2的值越大表示聚類的結(jié)果越好。

3.2.4 標(biāo)記生成簇

由簇標(biāo)記算法區(qū)分正常簇還是異常簇，進(jìn)而獲得其特征模式。

3.2.5 實(shí)時檢測

對異常簇異常行為的特征模式應(yīng)用檢測器（入侵檢測系統(tǒng)的模式信息庫）對其進(jìn)行判斷，產(chǎn)生檢測結(jié)果，確定并輸出入侵和攻擊［14-16］。

4 實(shí)驗(yàn)結(jié)果及其分析

由于數(shù)據(jù)集中入侵?jǐn)?shù)據(jù)的比例遠(yuǎn)超過真實(shí)環(huán)境，不能滿足無監(jiān)督異常檢測算法中“正常數(shù)據(jù)的數(shù)量要遠(yuǎn)大于入侵?jǐn)?shù)據(jù)”的要求，而且數(shù)據(jù)集中含有大量重復(fù)數(shù)據(jù)，因此需要對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行篩選。選取的數(shù)據(jù)分為兩部分，去掉10%數(shù)據(jù)集中的重復(fù)數(shù)據(jù)。實(shí)驗(yàn)中，訓(xùn)練集A使用了24790條記錄用來生成檢測模型，其中24294條為正常網(wǎng)絡(luò)行為，496條為入侵網(wǎng)絡(luò)行為，正常網(wǎng)絡(luò)行為的數(shù)據(jù)比例約為98%，測試集B1和測試集B2用來檢測算法的性能。

表1是以B1為測試集，改進(jìn)前后的聚類精度及檢測結(jié)果對比。

表1 檢測率（%）及聚類精度（Intra-cluster distance）對比

由表1的實(shí)驗(yàn)結(jié)果可見，改進(jìn)后檢測率及Intra-cluster distance值都有進(jìn)一步的提高，已經(jīng)能夠獲得所有被不合理聚類的攻擊數(shù)據(jù)，Intra-cluster distance提升率約為7.43%，說明簇的緊湊度有較明顯的提高。同時，在聚類過程中存在將訓(xùn)練集中本應(yīng)屬于同一個簇的數(shù)據(jù)劃分為多個子簇的現(xiàn)象，影響了檢測時的速度，使得含有較少樣本的正常類型簇在簇的標(biāo)記過程中被誤判為異常簇，導(dǎo)致誤報(bào)率上升的現(xiàn)象。為解決這一問題，在聚類結(jié)束后使用簇的合并算法［3］，將含有較少樣本的子簇與其相似簇合并。

表2給出使用測試集B2對未知攻擊類型的測試結(jié)果。算法對未知攻擊類型的檢測率約為58%。說明對未知攻擊類型具有一定的檢測能力。

表2 對未知類型的檢測

表3是同其它文獻(xiàn)中方法的對比，加下劃線的數(shù)據(jù)為最優(yōu)結(jié)果。

表3 與其它文獻(xiàn)使用方法的對比

由表3的檢測結(jié)果對比表明，加權(quán)聚類算法對DOS，U2R，R2L三個攻擊類型的檢測率有所提升，但是對Probe，normal類型的檢測還存在一定的差距。

5 結(jié)束語

應(yīng)用kdd cup 99入侵檢測數(shù)據(jù)集對加權(quán)聚類算法進(jìn)行了驗(yàn)證，將數(shù)據(jù)集中的數(shù)值型屬性進(jìn)行標(biāo)準(zhǔn)化后用于聚類算法訓(xùn)練。在檢測過程中，算法分別測試了已知入侵和未知入侵兩種情況，通過對已知入侵的測試來檢測算法的檢測率和誤報(bào)率，通過對未知入侵來測試算法的適應(yīng)性。加權(quán)聚類算法的聚類精度和檢測結(jié)果都有較明顯提高。

［1］呂志軍，鄭瑞，黃皓.高速網(wǎng)絡(luò)下的分布式實(shí)時入侵檢測系統(tǒng)［J］.計(jì)算機(jī)研究與發(fā)展，2004，41（4）：667-673.

［2］Lih-Chyau Wuu，Chi-Hsiang Hung，Sout-Fong Chen.Building intrusion pattern miner for Snort network intrusion detection system［J］.The Journal of Systems and Software，2007，80（10）：1699-1715.

［3］Animesh Patcha，Jung-Min Park.An overview of anomaly detection techniques：Existing solutions and latest technological trends［J］.Computer Networks，2007，51（12）：3448-3470.

［4］Eskin E，Arnold A，Prerau M，et al.A Geometric Framework for Unsupervised Anomaly Detection：Detecting Intrusions in Unlabeled Data，2002［C］.Applications of Data Mining in Computer Security.2002：26-29.

［5］向繼，高能，荊繼武.聚類算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用［J］.計(jì)算機(jī)工程，2003，29（16）：48-49，185.

［6］徐菁，劉寶旭，許榕生.基于數(shù)據(jù)挖掘技術(shù)的入侵檢測系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程，2002，28（6）：9-10，169.

［7］閆偉，張浩，陸劍峰，等.聚類分析理論研究及在流程企業(yè)中的應(yīng)用［J］.計(jì)算機(jī)工程，2006，32（17）：19-21，27.

［8］雷小鋒，何濤，李奎儒，等.面向結(jié)構(gòu)穩(wěn)定性的分裂-合并聚類算法［J］.計(jì)算機(jī)科學(xué)，2010，37（11）：217-222.

［9］杜強(qiáng)，孫敏.基于改進(jìn)聚類分析算法的入侵檢測系統(tǒng)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（11）：106-108，181.

［10］延皓，張博，劉芳，雷振明.基于量值的頻繁閉項(xiàng)集層次聚類算法［J］.北京郵電大學(xué)學(xué)報(bào)，2011，34（6）：64-68.

［11］閻慧，曹元大.一種基于入侵統(tǒng)計(jì)的異常檢測方法［J］.計(jì)算機(jī)工程與應(yīng)用，2002，38（22）：48-50.

［12］蔣建春，馬恒太，任黨恩，等.網(wǎng)絡(luò)安全入侵檢測：研究綜述［J］.軟件學(xué)報(bào)，2000，11（11）：1460-1466.

［13］Dunn JC.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters［J］.J.Cybernetics，1973（3）：32-57.

［14］Portnoy L，Eskin E，Stolfo S J.Intrusion Detection with Unlabeled Data Using Clustering，2001［C］.Proceedings of ACM CSS Workshop on Data Mining Applied to Security（DMSA-2001），New York：ACM Press，2001：123-130.

［15］Portnoy L，Eskin E，Stolfo S J.Intrusion detection with unlabeled data using clustering，2001［C］.Proceedings of ACM CSSWorkshop on Data Mining Applied to Security（DMSA-2001）.Philadelphia，PA，2001：123-130.

［16］Mukkamala S，Janoski G，Sung A H.Intrusion Detection Using Neural Networks and Support Vector Machines，2002［C］.Proceedings of IEEE International Joint Conference on Neural Networks，2002：1702-1707.

Research of Application of Clustering Algorithm in Network Intrusion Detection

ZHU Jian1，LU Bing-liang2，QU Chao-yi3
（1.Shenyang Aeronautical Vocational College，Shenyang 110034，China；2.School of Computer Science and Engineering，Shenyang Aerospace University，Shenyang 110136，China；3.AVIC Shenyang Aircraft Corporation，Shenyang 110034，China）

The clustering algorithm is used to cluster data set for intrusion detection，the clustering results are analyzed to find the problem of uncompacted division in partof clusters.Therefore，aweighing clustering algorithm is put forward to cluster the data far from the clustering center for solving the problem that clustering results havemany sub-clusters.The results show that the clusters aremore compact and the detection accuracy and speed are increased because of sub-clusters decreased.

Network security；Intrusion detection；Cluster Analysis；Weighted clustering algorithm

10.3969／j.issn.1002-2279.2014.05.012

TP393.07

：A

：1002-2279（2014）05-0040-03

朱?。?971-），男（滿族），遼寧北鎮(zhèn)人，碩士，教授，高級工程師，主研方向：計(jì)算機(jī)網(wǎng)絡(luò)與數(shù)據(jù)庫。

2013-10-9