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

朱 健，盧秉亮，曲超毅

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

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

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

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

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

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

1 引 言

隨著網(wǎng)絡(luò)技術(shù)的逐漸發(fā)展，不斷出現(xiàn)新的入侵和新類型的攻擊，為了解決此問(wèn)題，必須應(yīng)用智能入侵檢測(cè)技術(shù)。常見(jiàn)的入侵檢測(cè)方法主要包括統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)、模式匹配、規(guī)則推理以及人工免疫理論等方法［1-3］。為了獲得網(wǎng)絡(luò)行為模式，需要通過(guò)帶標(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)境造成的。為了提高入侵檢測(cè)效率，以聚類（Clustering）為代表的無(wú)監(jiān)督入侵檢測(cè)算法［4-6］被用來(lái)直接處理無(wú)標(biāo)簽原始網(wǎng)絡(luò)數(shù)據(jù)。

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

2 聚類分析算法

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

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

2.2 聚類分析算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

為了能夠?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ū)別開(kāi)來(lái)，因此在網(wǎng)絡(luò)入侵檢測(cè)中可以應(yīng)用聚類分析算法。聚類后的結(jié)果可以應(yīng)用簇標(biāo)記算法［11-12］判斷簇是正常網(wǎng)絡(luò)行為還是入侵網(wǎng)絡(luò)行為。

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

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

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

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

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

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

3.2.3 聚類分析

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

K-means有其缺點(diǎn)，即產(chǎn)生類的大小相差不會(huì)很大并且對(duì)于“臟”數(shù)據(jù)很敏感，因此，要對(duì)初始聚類結(jié)果進(jìn)行優(yōu)化，使各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開(kāi)。聚類結(jié)果的具體評(píng)價(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í)時(shí)檢測(cè)

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

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

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

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

表1 檢測(cè)率（%）及聚類精度（Intra-cluster distance）對(duì)比

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

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

表2 對(duì)未知類型的檢測(cè)

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

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

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

5 結(jié)束語(yǔ)

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

［1］呂志軍，鄭瑞，黃皓.高速網(wǎng)絡(luò)下的分布式實(shí)時(shí)入侵檢測(cè)系統(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ò)入侵檢測(cè)中的應(yīng)用［J］.計(jì)算機(jī)工程，2003，29（16）：48-49，185.

［6］徐菁，劉寶旭，許榕生.基于數(shù)據(jù)挖掘技術(shù)的入侵檢測(cè)系統(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)聚類分析算法的入侵檢測(cè)系統(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ì)的異常檢測(cè)方法［J］.計(jì)算機(jī)工程與應(yīng)用，2002，38（22）：48-50.

［12］蔣建春，馬恒太，任黨恩，等.網(wǎng)絡(luò)安全入侵檢測(cè)：研究綜述［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ì)算機(jī)網(wǎng)絡(luò)與數(shù)據(jù)庫(kù)。

2013-10-9