梅孝輝，龍 淵，張健博

(重慶大學(xué)計算機(jī)學(xué)院，重慶 400044)

0 引言

隨著網(wǎng)絡(luò)技術(shù)和網(wǎng)絡(luò)規(guī)模的快速發(fā)展，網(wǎng)絡(luò)安全已成為一個全球性的重要問題。高速網(wǎng)絡(luò)的出現(xiàn)和攻擊模式的不斷變化使得傳統(tǒng)的通過手動方法維護(hù)和更新知識數(shù)據(jù)庫等操作變得愈發(fā)棘手。靜態(tài)安全技術(shù)無法滿足當(dāng)代網(wǎng)絡(luò)安全需求的問題日趨嚴(yán)重，因此亟需一種能夠檢測到入侵行為［1］、積極主動的安全防衛(wèi)技術(shù)，入侵檢測系統(tǒng)［2］(Intrusion Detection System，IDS)作為一種積極主動的安全防御系統(tǒng)應(yīng)運(yùn)而生。

入侵檢測技術(shù)［3］能夠迅速識別入侵行為，并能提供相應(yīng)的安全防衛(wèi)反應(yīng)機(jī)制。而數(shù)據(jù)挖掘［4］作為一種通用的知識發(fā)現(xiàn)技術(shù)，引入到入侵檢測系統(tǒng)中，將入侵檢測過程變?yōu)閿?shù)據(jù)分析過程，提高入侵檢測系統(tǒng)的效率。

作為數(shù)據(jù)挖掘的一項(xiàng)重要技術(shù)，離群數(shù)據(jù)挖掘方法目前已被許多學(xué)者應(yīng)用到入侵檢測領(lǐng)域中，其中包括:基于頻繁模式的離群點(diǎn)挖掘［5］、基于密度的離群點(diǎn)挖掘［6］和基于深度的離群點(diǎn)挖掘［7］。

文獻(xiàn)［6］中給出一種基于密度的聚類方法，首先聚類數(shù)據(jù)集，剪除掉密集的點(diǎn)，然后進(jìn)行離群挖掘操作。該方法解決了離群點(diǎn)挖掘耗時高的缺點(diǎn)，但在剪除密集點(diǎn)時，部分離群點(diǎn)也會被剪除掉，導(dǎo)致該方法檢測率不高。本文對傳統(tǒng)的基于密度聚類算法［6］(DBSCAN，Density-Based Spatial Clustering of Applications with Noise)進(jìn)行改進(jìn)，在DBSCAN 算法中引入局部離群點(diǎn)挖掘方法進(jìn)行聚類合并，提出一種新方法LDBSCAN-CM(Local-Density Based Spatial Clustering Applications with Noise and Cluster Merge)，并用實(shí)驗(yàn)證明，該方法在入侵檢測中具有良好的性能。

1 相關(guān)概念

定義1 對象p 的k 距離［8］(k_distance(p))。對于任意一個正整數(shù)k(k 即是參數(shù)Minpts(最近鄰居數(shù)))，定義對象p 的k 距離即為對象p 和數(shù)據(jù)集中的對象o 之間的距離d(p，o)，滿足條件:

1)至少存在k 個數(shù)據(jù)對象o'∈D { p}，滿足d(p，o')≤d(p，o);

2)至多存在k-1 個數(shù)據(jù)對象o'∈ D { p}，滿足d(p，o')＜d(p，o)。

定義2 數(shù)據(jù)對象p的k距離鄰域［8］(Nk_distance(p))。數(shù)據(jù)對象p 的k 距離鄰域包含所有與p 的距離小于或等于k_distance(p)的點(diǎn)的集合。

定義3 數(shù)據(jù)對象p 關(guān)于對象o(其中o 在p 的k鄰域)的可達(dá)距離［8］(reach_distk(p，o))。任意給定一個正整數(shù)k，對象p 與對象o 間的可達(dá)距離:

定義4 對象p 的局部密度可達(dá)對象q，記作(LRDk(p))［9］，定義公式為:

定義5 數(shù)據(jù)對象p 的局部離群因子記作(LOF)［8-9］，表示為p 的離群程度，其定義如下:

定義6 核心對象。如果一個對象p 的局部離群因子LOF(p)≤LOFUB，LOFUB 為局部離群度上限(用于判斷是否為核心點(diǎn))，則該對象p 為核心對象。

定義7 直接局部密度可達(dá)［9-10］，點(diǎn)p 直接局部密度可達(dá)點(diǎn)q 的條件:

其中pct 為局部離群因子，用于控制局部密度波動。

定義8 局部密度可達(dá)。若數(shù)據(jù)對象p 是從數(shù)據(jù)對象q 關(guān)于pct 和Minpts 局部密度可達(dá)的，那么存在一個對象鏈p1，p2，...，pn，p1=q，pn=p 對于pi∈D(1 ≤i ≤n)，pi+1是從pi關(guān)于pct 和Minpts 直接局部密度可達(dá)的。

2 本文算法

2.1 傳統(tǒng)的DBSCAN 算法

DBSCAN 聚類算法的處理流程［9］:1)任選一個未被訪問的點(diǎn)。2)如果選中的點(diǎn)是核心點(diǎn)，那么找出從該點(diǎn)密度可達(dá)的所有點(diǎn)，形成一個聚類簇;否則選中的點(diǎn)是非核心點(diǎn)，跳出本次循環(huán)，繼續(xù)尋找下一個核心點(diǎn)。3)迭代，直到所有的點(diǎn)都被處理，輸出聚類結(jié)果。

DBSCAN 算法具有以下缺點(diǎn):

1)DBSCAN 不能很好反映數(shù)據(jù)集局部密度的細(xì)節(jié);

2)DBSCAN 不能很好反映高尺寸數(shù)據(jù);

3)DBSCAN 算法對參數(shù)非常敏感，且參數(shù)很難確定;

4)部分聚類小簇含有超過70%正常數(shù)據(jù)［10］。

2.2 改進(jìn)的DBSCAN 算法

以傳統(tǒng)的DBSCAN 算法為基礎(chǔ)，引入局部離群因子概念，結(jié)合局部離群點(diǎn)挖掘方法，聚類出簇;再通過對離群簇進(jìn)行聚類合并，在合并過程中，通過計算2 個簇邊界點(diǎn)間的距離來代替簇之間的距離。假設(shè)2個簇Ck和Cl，邊界點(diǎn)集為εk和εl，如果dist(εk，εl)＜Dst，則合并簇Ck，Cl。本文中將改進(jìn)DBSCAN 算法命名為LDBSCAN-CM 算法。

2.3 數(shù)據(jù)預(yù)處理

2.3.1 特征選取

KDD Cup99［11］數(shù)據(jù)集中每個屬性對檢查結(jié)果貢獻(xiàn)是不相同的，通過支持向量機(jī)［12］算法選擇屬性貢獻(xiàn)較大的13 個屬性{srv_count，same_srv_rate，dst_host_count，dst_host_srv_count，dst_host_same_srv_rate，dst_host_same_src_port_rate，duration，src_bytes，dst_bytes，count，urgent，protocol_type，service}，其中既包含了連續(xù)屬性，也包含了離散屬性。本文實(shí)驗(yàn)采用該特征選取方案。

2.3.2 混合屬性處理方案

在對數(shù)據(jù)集進(jìn)行局部離群點(diǎn)挖掘和聚類合并操作之前對選出的13 個屬性進(jìn)行處理。KDD Cup99 數(shù)據(jù)集中包括數(shù)值型與符號型屬性，需要對符號型屬性進(jìn)行數(shù)值化處理;對于屬性service，字段取值有66 種情況，分別用1～66 取值代替。這樣經(jīng)過特征提取的13 個屬性全部轉(zhuǎn)化為數(shù)值型屬性，再對其進(jìn)行歸一化處理［13］。

在相似度計算之前，需對數(shù)據(jù)的屬性值進(jìn)行歸一化處理，因?yàn)閷傩蚤g值不同采用不同的度量單位差異可能很大。

為了消除這種差別，運(yùn)用標(biāo)準(zhǔn)化區(qū)間標(biāo)度變量的方法［14］。對數(shù)據(jù)歸一化處理后，采用歐氏距離［15］計算2 個對象之間的相異度，即:

其中i=(xi1，...，xin)和j=(yj1，...yjn)是2 個n 維的數(shù)據(jù)對象。

2.4 算法描述

LDBSCAN-CM 算法描述如下:

輸入:數(shù)據(jù)集Data、pct、Minpts、Dst(pct 為離群因子參數(shù)，MinPts 為對象的最近鄰居數(shù)，Dst 為簇與簇間距離)。

輸出:將聚類合并后距離大于Dst 的對象輸出。

Step1將網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行預(yù)處理。

Step2任意選取一點(diǎn)p，計算它的局部離群因子(LOF)，若點(diǎn)p 為核心點(diǎn)，則檢查其鄰域，找出所有從點(diǎn)p 局部密度可達(dá)的點(diǎn)，形成一個聚類簇。

Step3如果選取的點(diǎn)是非核心點(diǎn)，則執(zhí)行Step2。

Step4直到所有的點(diǎn)都被處理，執(zhí)行Step5。

Step5找出每個新聚類簇的k 鄰域中非核心對象，并計算這些對象間的距離D。如果D 小于Dst，則把這2 個類進(jìn)行合并，生成最終的聚類簇。

本文算法引入局部離群挖掘方法，能夠很好地反映出局部離群點(diǎn)的細(xì)節(jié);通過聚類合并的方法，避免了70%聚類中含有正常數(shù)據(jù)，提高了檢測率。下節(jié)將通過實(shí)驗(yàn)論證該算法。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)選取

在實(shí)驗(yàn)過程中，采用基于數(shù)據(jù)挖掘在入侵檢測研究中常用的實(shí)驗(yàn)數(shù)據(jù)集—KDD Cup99［11］，包含4 種攻擊類型DoS、U2R、R2L、PROBE。在數(shù)據(jù)中將攻擊數(shù)據(jù)的比例控制在1%到2%之間，正常數(shù)據(jù)控制在98%到99%之間。從KDD Cup99 提供的具有代表性的10%(共494021 條)訓(xùn)練數(shù)據(jù)集中選取5 個子集數(shù)據(jù)，每個子數(shù)據(jù)集包括10000 條正常的數(shù)據(jù)和150條入侵?jǐn)?shù)據(jù)，其中前4 個子數(shù)據(jù)集中各自只包括一種攻擊類型數(shù)據(jù)，第5 個子數(shù)據(jù)集包含4 種混合型攻擊數(shù)據(jù)，這5 組數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集來訓(xùn)練算法中局部離群因子pct 和確定聚類區(qū)域的對象個數(shù)Minpts 這2個參數(shù);訓(xùn)練出合適的pct 和Minpts 作用于測試數(shù)據(jù)集，測試集中的入侵?jǐn)?shù)據(jù)類型包含許多在訓(xùn)練集中沒有包含的新型攻擊數(shù)據(jù)，隨機(jī)選取3 組測試數(shù)據(jù)作為測試集1、2、3 來測試算法的效果。

3.2 實(shí)驗(yàn)結(jié)果與分析

入侵檢測實(shí)驗(yàn)通常是通過檢測率(Dr)和誤檢率(Fdr)來表述實(shí)驗(yàn)結(jié)果［16］。實(shí)驗(yàn)中，必須先確定算法中的3 個參數(shù):pct、Minpts、Dst。其中參數(shù)Dst 通過文獻(xiàn)［17］得出最佳參數(shù)Dst=0.02，另2 個經(jīng)過多次訓(xùn)練選取合適的值。本實(shí)驗(yàn)先訓(xùn)練參數(shù)Minpts，將pct 賦值為0.5，測試Minpts 的值，訓(xùn)練結(jié)果如表1 和表2 所示。

表1 攻擊獨(dú)立數(shù)據(jù)集訓(xùn)練Minpts 的實(shí)驗(yàn)結(jié)果

表2 攻擊混合數(shù)據(jù)集訓(xùn)練Minpts 的實(shí)驗(yàn)結(jié)果

從表1 和表2 中可以看出，不管是4 種攻擊類型獨(dú)立訓(xùn)練還是混合類型共同訓(xùn)練，當(dāng)Minpts=120時，檢測率和誤檢率的效果都是相對較好的，因此選用Minpts=120 作為輸入?yún)?shù)，輸入不同的pct 值，進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3 和表4 所示。

表3 攻擊獨(dú)立數(shù)據(jù)集訓(xùn)練pct 實(shí)驗(yàn)結(jié)果

表4 攻擊混合數(shù)據(jù)集訓(xùn)練pct 實(shí)驗(yàn)結(jié)果

從表3 和表4 中可以看出，無論4 種攻擊類型是獨(dú)立訓(xùn)練還是混合類型訓(xùn)練，當(dāng)pct=0.5 時，本文算法對4 種攻擊的檢測效果都比較好。

綜合訓(xùn)練數(shù)據(jù)集實(shí)驗(yàn)結(jié)果的檢測率和誤檢率的情況，選用Minpts=120，pct=0.5 對測試集進(jìn)行檢測，并與其他算法進(jìn)行比較。

表5 對3 種算法測試集的測試效果

從表5 中可以看出，根據(jù)訓(xùn)練數(shù)據(jù)集選出的最優(yōu)參數(shù)在測試數(shù)據(jù)集的檢測，本文LDBSCAN-CM 算法較于傳統(tǒng)的DBSCAN 算法在檢測率方面有明顯的優(yōu)勢;相較于IIDBG［10］算法有較高的檢測率和較低的誤檢率。由實(shí)驗(yàn)可知，改進(jìn)的算法具有高效性。

LDBSCAN-CM 算法進(jìn)行入侵檢測可以得到很好的檢測效果。在測試集中，包含有訓(xùn)練集中未出現(xiàn)的攻擊類型，因此，測試實(shí)驗(yàn)檢測到了新的攻擊模式，這表明LDBSCAN-CM 算法可以檢測那些未知的攻擊。

4 結(jié)束語

本文提出了一種基于傳統(tǒng)DBSCAN 算法的改進(jìn)算法LDBSCAN-CM 算法。該算法引入了局部離群點(diǎn)挖掘概念和聚類合并的思想，能夠很好地反映數(shù)據(jù)集局部密度的細(xì)節(jié)，將改進(jìn)后的方法應(yīng)用到入侵檢測中，通過在KDD Cup99 實(shí)驗(yàn)數(shù)據(jù)集中進(jìn)行仿真實(shí)驗(yàn)，表明該方法能夠取得較高的檢測率和較低的誤檢率。

但是LDBSCAN-CM 算法具有較高的時間復(fù)雜度，聚類操作消耗時間較多，在今后的研究中，需要進(jìn)一步優(yōu)化，確保檢測效果的同時降低時間復(fù)雜度，并在實(shí)際環(huán)境中應(yīng)用該算法，在真實(shí)的環(huán)境中測試其執(zhí)行效率。

［1］Heady R，Luger G，Maccabe A，et al.The Architecture of a Network Level Intrusion Detection System［R］.Mexico:University of New Mexico，1990.

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

［3］Dacier M，Jackson K.Intrusion detection［J］.Computer Networks，1999，31(23-24):2433-2434.

［4］張巍，滕少華，傅秀芬.數(shù)據(jù)融合的協(xié)同網(wǎng)絡(luò)入侵檢測［J］.計算機(jī)應(yīng)用，2009，29(1):284-287.

［5］王茜，唐銳.基于頻繁模式的離群點(diǎn)挖掘在入侵檢測中的應(yīng)用［J］.計算機(jī)應(yīng)用研究，2013，30(4):1208-1211.

［6］閆少華，張巍，滕少華.基于密度的離群點(diǎn)挖掘在入侵檢測中的應(yīng)用［J］.計算機(jī)工程，2011，37(18):240-242.

［7］van Kreveld M，Mitchell S B，Rousseeuw P，et al.Efficient algorithms for maximum regression depth［J］.Discrete ＆ Computational Geometry，2008，39(4):656-677.

［8］Breunig M M，Kriegel H P，Ng R，et a1.LOF:Identifying density based local outliers［C］// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.2000:93-104.

［9］Duan Lian，Xu Lida，Guo Feng，et al.A local-density based spatial clustering algorithm with noise［J］.Information Systems，2007，32(7):978-986.

［10］Li Xueyong，Gao Guohong，Sun Jiaxia.A new intrusion detection method based on improved DBSCAN［C］// 2010 WASE International Conference on Information Engineering(ICIE).2010，2:117-120.

［11］朱廷劭，高文.KDD:數(shù)據(jù)庫中的知識發(fā)現(xiàn)［J］.計算機(jī)科學(xué)，1997(6):5-9.

［12］祁亨年.支持向量機(jī)及其應(yīng)用研究綜述［J］.計算機(jī)工程，2004，30(10):6-9.

［13］J?rg Sander，Martin Ester，Hans-Peter Kriegel，et al.Density-based clustering in spatial databases:The algorithm GDBSCAN and its applications［J］.Data Mining and Knowledge Discovery，1998，2(2):169-194.

［14］韓家煒.數(shù)據(jù)挖掘:概念與技術(shù)(英文版)［M］.2 版.北京:機(jī)械工業(yè)出版社，2006.

［15］吳新玲.數(shù)據(jù)維數(shù)消減方法研究［J］.計算機(jī)工程與設(shè)計，2006，16(27):3000-3002.

［16］楊建華，蔣玉明，彭輪.數(shù)據(jù)挖掘在網(wǎng)絡(luò)入侵檢測中的應(yīng)用研究［J］.微計算機(jī)信息，2009，25(24):27-29.

［17］Zhang Yongli，Zhu Yanwei.Application of improved support vector machines in intrusion detection［C］// 2010 2nd International Conference on e-Business and Information System Security(EBISS).2010:1-4.

［18］Liu Qiliang，Deng Min，Shi Yan，et al.A density-based spatial clustering algorithm considering both spatial proximity and attribute similarity［J］.Computers and Geosciences，2012，46:296-309.