基于改進(jìn)密度峰值聚類的異常流量檢測

任 艷，徐 春，張 蕾，汪曉潔, 2

(1. 新疆財經(jīng)大學(xué) 信息管理學(xué)院，新疆 烏魯木齊 830012；2. 新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046)

互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展改變了人們的辦公、生活以及娛樂模式。在我國，移動通信、電腦設(shè)備的數(shù)量都達(dá)到了數(shù)十億的規(guī)模，同時也給用戶帶來了網(wǎng)絡(luò)信息安全的威脅，人們的隱私安全隱患問題逐漸暴露，因此，互聯(lián)網(wǎng)健康發(fā)展的關(guān)鍵是解決具有挑戰(zhàn)性的網(wǎng)絡(luò)信息安全問題[1]。

現(xiàn)今，人們生活中的各個方面都離不開互聯(lián)網(wǎng)，如互聯(lián)網(wǎng)金融、智能家居、智能醫(yī)療設(shè)備、智能網(wǎng)聯(lián)汽車等。這些應(yīng)用網(wǎng)絡(luò)中存在規(guī)模巨大的數(shù)據(jù)交互信息，如果這些信息不加以保護，將會受到各種各樣的網(wǎng)絡(luò)攻擊，甚至?xí)?dǎo)致計算機系統(tǒng)破壞。異常流量檢測是網(wǎng)絡(luò)信息安全領(lǐng)域中的一項重要的主動安全檢測技術(shù)，可以檢測出網(wǎng)絡(luò)中的異常流量，從而保護網(wǎng)絡(luò)安全，因此，通過異常流量檢測發(fā)現(xiàn)潛在的非法的惡意行為，是解決網(wǎng)絡(luò)信息安全問題的關(guān)鍵所在[2]。

近年來，國內(nèi)外專家學(xué)者研究了各種網(wǎng)絡(luò)中異常流量檢測技術(shù)。Sommer等[3]提出了一種基于機器學(xué)習(xí)的網(wǎng)絡(luò)異常流量檢測技術(shù)方案，認(rèn)為異常流量的行為與其他應(yīng)用程序有著根本的不同，為后續(xù)的異常流量檢測研究提供了指導(dǎo)。Srinivasa Murthy等[4]設(shè)計了一種基于貝葉斯和遺傳算法(Bayesian and genetic algorithm, BAGA)的混合智能入侵檢測系統(tǒng)，其中的貝葉斯算法將數(shù)據(jù)集分為各種類別以識別正?；蚬魯?shù)據(jù)包，遺傳算法通過對現(xiàn)有數(shù)據(jù)集應(yīng)用變異操作來生成新數(shù)據(jù)集，根據(jù)高檢測精度識別不同類型的攻擊。胡明霞[5]提出了一種基于反向傳播(back propagation，BP)神經(jīng)網(wǎng)絡(luò)的入侵檢測算法方案，結(jié)合遺傳算法解決了訓(xùn)練樣本規(guī)模大、不易收斂的問題，提高了檢測效率和正確率。Agyemang等[6]提出了一種基于統(tǒng)計的帶參數(shù)的異常流量檢測方案，將不符合設(shè)定的概率分布范圍的流量判斷為異常流量。與之相反，Rawashdeh等[7]提出了一種基于統(tǒng)計的不帶參數(shù)的異常流量值檢測方案。上述2種方案存在的共同缺陷是無法高效解決高維數(shù)據(jù)問題。楊茂林[8]提出了一種基于近鄰的離群異常流量檢測方案，與基于統(tǒng)計的異常流量值檢測方案不同的是，它無須得知數(shù)據(jù)分布和預(yù)先標(biāo)記就可以解決高維數(shù)據(jù)問題，但是其時間復(fù)雜度較高，不易選取結(jié)構(gòu)復(fù)雜的數(shù)據(jù)的合適距離函數(shù)。Xu等[9]提出了一種無監(jiān)督的聚類方案，基于網(wǎng)絡(luò)用戶日志數(shù)據(jù)的特征使用k均值算法對網(wǎng)絡(luò)用戶進(jìn)行聚類，但是該方案的異常流量檢測準(zhǔn)確率較低，算法較為復(fù)雜。李佳瑋等[10]提出了一種基于高斯混合聚類的異常檢測方案，利用多元高斯分布混合算法對流量數(shù)據(jù)進(jìn)行處理。上述的大部分算法非常依賴標(biāo)簽的正確性，原因是標(biāo)簽可以決定建立的模型所得出的最終結(jié)果；然而，當(dāng)前復(fù)雜的網(wǎng)絡(luò)攻擊不斷更新?lián)Q代，這時標(biāo)記通常會失效從而導(dǎo)致簇的誤劃分，因此，需要實時更改數(shù)據(jù)的標(biāo)簽。聚類算法作為一種經(jīng)典且重要的無監(jiān)督學(xué)習(xí)算法，顯然更適合作為解決方案。Yang等[11]、Du等[12]提出一種自適應(yīng)確定聚類中心的密度峰值聚類算法，可以自動識別簇中心點。Wu等[13]、Kamali等[14]提出了基于對稱鄰域的密度峰值聚類方法，可以高效地發(fā)現(xiàn)聚類中心。

在各類異常流量檢測技術(shù)中，密度峰值聚類作為新型聚類方法，其優(yōu)點是不需要任何預(yù)定義的參數(shù)和任何迭代過程。為了解決網(wǎng)絡(luò)異常流量檢測技術(shù)準(zhǔn)確率較低、簇的誤劃分等問題，本文中提出一種基于改進(jìn)的密度峰值聚類算法(improved density peaks clustering algorithm, IDPCA)的網(wǎng)絡(luò)異常流量檢測方案。該方案首先對網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行預(yù)處理分組亂序，然后計算相應(yīng)屬性值并利用局部密度發(fā)現(xiàn)簇中心點，最后采用一種新的標(biāo)簽傳遞方式形成相應(yīng)的簇群直至處理完所有數(shù)據(jù)。

1 聚類算法

作為一種無監(jiān)督學(xué)習(xí)的經(jīng)典方法，聚類算法在當(dāng)前復(fù)雜的現(xiàn)實網(wǎng)絡(luò)環(huán)境中極其重要。由于網(wǎng)絡(luò)環(huán)境無法高度精準(zhǔn)并高效獲得規(guī)模較大的新收集流量的類別標(biāo)記，因此聚類算法更適合作為當(dāng)前異常流量檢測的技術(shù)。

1.1 具有噪聲的基于密度的聚類算法

與其他聚類算法相比，具有噪聲的基于密度的聚類(density-based spatial clustering of applications with noise，DBSCAN)算法從數(shù)據(jù)對象的密鑰出發(fā)，根據(jù)其密度相關(guān)性進(jìn)行聚類，可在有噪聲的空間數(shù)據(jù)中找出任意的簇，進(jìn)一步研究不同數(shù)據(jù)對象之間的可連接性并不斷擴充，最后得到聚類的結(jié)果。DBSCAN算法作為經(jīng)典的算法，與劃分聚類和層次聚類算法不同，可以找出密度較高的點，然后將該點周圍高密度區(qū)域定義成簇。DBSCAN算法的相關(guān)定義如下：

1)鄰域。以數(shù)據(jù)點為圓心、e為半徑的圓定義為鄰域，也就是該點與其他點的歐氏距離小于e的數(shù)據(jù)對象的集合，則該數(shù)據(jù)點的密度值為圈內(nèi)數(shù)據(jù)點的個數(shù)。

2)核心點。給定鄰域樣本局部密度閾值Pmin，鄰域內(nèi)數(shù)據(jù)點的個數(shù)大于Pmin的圓心稱為高密度的點或核心點，否則稱為低密度的點。

3)密度直達(dá)。如果外圍數(shù)據(jù)點m在核心數(shù)據(jù)點n的鄰域內(nèi)，則稱外圍數(shù)據(jù)點m由核心數(shù)據(jù)點n密度直達(dá)，即將高密度點的鄰域內(nèi)的高密度點連接起來，以此類推，然后將所有這樣的點都連接起來。若低密度的點在高密度點的鄰域內(nèi)，把它與最近的高密度點相連接，則稱為邊界點。

4)密度可達(dá)。在外圍數(shù)據(jù)點m與核心數(shù)據(jù)點n中，若存在相同的若干子數(shù)據(jù)點k，則稱子數(shù)據(jù)點k由核心數(shù)據(jù)點n密度可達(dá)。

5)密度相連。在外圍數(shù)據(jù)點m與核心數(shù)據(jù)點n中，如果存在外圍數(shù)據(jù)點m由子數(shù)據(jù)點k密度可達(dá)且核心數(shù)據(jù)點n也由子數(shù)據(jù)點k密度可達(dá)，則稱外圍數(shù)據(jù)點m與核心數(shù)據(jù)點n密度相連。

圖1所示為DBSCAN算法的相關(guān)定義示意圖。其中，虛線表示預(yù)設(shè)數(shù)據(jù)點N1、N2、N3、N4、N5的鄰域，圖中所設(shè)置的Pmin為3，表示在鄰域內(nèi)有3個額外的數(shù)據(jù)點，可以看出，每個圈內(nèi)都有4個數(shù)據(jù)點。數(shù)據(jù)點N2由數(shù)據(jù)點N1密度直達(dá)，數(shù)據(jù)點N3由數(shù)據(jù)點N1密度可達(dá)，數(shù)據(jù)點N6與數(shù)據(jù)點N1密度相連。

N1、N2、N3、N4、N5、N6—預(yù)設(shè)數(shù)據(jù)點。圖1 具有噪聲的基于密度的聚類算法的相關(guān)定義示意圖

DBSCAN算法具體步驟如下：

步驟1初始化。設(shè)定樣本數(shù)據(jù)集合D、鄰域半徑e、鄰域樣本局部密度閾值Pmin。

步驟2將樣本數(shù)據(jù)集合D中所有數(shù)據(jù)點標(biāo)記為未處理狀態(tài)。

步驟3隨機選擇樣本數(shù)據(jù)集合D中處于未處理狀態(tài)的數(shù)據(jù)點m且為核心點，將其標(biāo)記為已處理狀態(tài)，若在數(shù)據(jù)點m的鄰域內(nèi)，至少包含Pmin個數(shù)據(jù)點，則建立一個新的簇C，并將鄰域內(nèi)所有數(shù)據(jù)點放入簇C。若數(shù)據(jù)點m是邊緣點，則尋找下一個數(shù)據(jù)點。

步驟4重復(fù)步驟3，直至所有數(shù)據(jù)點都被處理。

步驟5輸出聚類結(jié)果C。

1.2 密度峰值聚類算法

聚類算法的主要原理是將歐氏距離較小的點分為一個類簇，而歐氏距離較大的點分為其他的類簇。盡管聚類算法有很多種，但在聚類中的簇的定義依然沒有統(tǒng)一的標(biāo)準(zhǔn)。

密度峰值聚類算法(density peaks clustering algorithm, DPCA)是一種新型的基于密度的聚類算法。該算法首先要確定簇的中心點，然后把其余的數(shù)據(jù)點加入到對應(yīng)的類簇中。DPCA選取簇中心點有2個條件：第1個條件是選取的簇中心點在局部中是鄰域內(nèi)的密度峰值點，即最大密度值；第2個條件是這個簇中心點與其他類似局部較大密度的數(shù)據(jù)點的歐氏距離都較大。DPCA首先計算所有樣本數(shù)據(jù)點的相對距離δ和局部密度ρ這2個屬性值，然后基于這2個屬性值構(gòu)建相應(yīng)的決策圖，選取相對距離δ和局部密度ρ較大的數(shù)據(jù)點作為簇中心點，其他數(shù)據(jù)點依據(jù)局部密度ρ從大到小依次加入到相對距離δ最小的數(shù)據(jù)點所在的簇中。其中，任意數(shù)據(jù)點i的相對距離δi定義為

(1)

式中dij為任意數(shù)據(jù)點i與另一任意數(shù)據(jù)點j的歐氏距離。

若該數(shù)據(jù)點i具有整個全局最大密度，則它的距離定義為

(2)

即該數(shù)據(jù)點i的歐氏距離等于其他數(shù)據(jù)點與該點的最大距離。

任意數(shù)據(jù)點i的局部密度ρi定義為

其中

(3)

式中dc為截斷距離。

式(3)的使用條件是在數(shù)據(jù)量較大時，局部密度的區(qū)分度較高。如果數(shù)據(jù)量較小，則需要采用高斯函數(shù)求出數(shù)據(jù)點i的局部密度ρi，即數(shù)據(jù)點i的鄰域內(nèi)數(shù)據(jù)點歐氏距離的加權(quán)值之和，以解決局部密度區(qū)分度低的問題。ρi的表達(dá)式為

(4)

DPCA流程如圖2所示。

2 基于IDPCA的異常流量檢測

IDPCA主要是針對網(wǎng)絡(luò)異常流量檢測中DPCA人工選擇簇中心點容易造成簇的誤劃分問題提出的。該算法包括2個主要步驟：一是識別計算數(shù)據(jù)集中各個數(shù)據(jù)點的2個屬性值；二是構(gòu)建決策圖并開始聚類。簇中心是在比相鄰數(shù)據(jù)點密度更大的數(shù)據(jù)點中確定的，為此該算法采用2種不同的度量來識別簇中心點，然后采用標(biāo)簽傳播距離算法對數(shù)據(jù)點進(jìn)行聚類。IDPCA的步驟如下：

圖2 密度峰值聚類算法流程

步驟1輸入數(shù)據(jù)集合D、截斷距離dc。

步驟2發(fā)現(xiàn)簇中心點。根據(jù)式(1)、(2)計算點距離矩陣，根據(jù)式(3)、(4)計算點的局部密度，構(gòu)建決策圖并選擇簇中心點。

步驟3形成簇群。將簇中心點的標(biāo)簽分配給最近鄰點，進(jìn)行基于鄰域距離矩陣和密度的聚類，將剩余的每個點分配到最近的聚類中心。

步驟4輸出聚類結(jié)果簇C。

在步驟2中計算相應(yīng)的數(shù)據(jù)，這與DPCA一致。不同的是，步驟2中提出了一種新的標(biāo)簽傳遞方式，最后根據(jù)處理過的簇中心點形成簇群，為每個簇中心點分配一個不同的標(biāo)簽，每個簇中心點將標(biāo)簽傳遞到其最近的鄰點。對于沒有任何標(biāo)簽或處理過的數(shù)據(jù)點i，如果其局部密度ρi小于ρj，則該數(shù)據(jù)點獲得數(shù)據(jù)點j的標(biāo)簽?？梢钥闯?，IDPCA的時間復(fù)雜度為O(N2)，其中N是數(shù)據(jù)集D中樣本數(shù)據(jù)點的個數(shù)。

基于IDPCA的異常流量檢測流程如圖3所示。

最后判斷數(shù)據(jù)集中異常流量的規(guī)則，本文中定義異常流量樣本滿足以下條件：局部密度ρi小于Pmin，相對距離δi小于相對距離閾值δt，其中Pmin定義為

(5)

δt的定義為

(6)

式中γ1、γ2均為經(jīng)驗參數(shù)。

圖3 基于改進(jìn)的密度峰值聚類算法的異常流量檢測流程

3 結(jié)果與分析

為了更好地檢驗IDPCA的有效性和網(wǎng)絡(luò)異常流量檢測性能，采用KDDCup99數(shù)據(jù)集進(jìn)行仿真。仿真硬件環(huán)境為64位Windows 10操作系統(tǒng)的筆記本電腦，中央處理器(CPU) 為Intel 7，內(nèi)存為8 GB；實驗仿真的軟件為Python 3、MATLAB R2018b。由于原始的KDDCup99數(shù)據(jù)集規(guī)模較大，因此學(xué)者們通常采用其中10%的數(shù)據(jù)作為研究對象，樣本數(shù)據(jù)個數(shù)約為494 021。本文中采用的數(shù)據(jù)樣本類型以及數(shù)據(jù)量如表1所示。

表1 KDDCup99數(shù)據(jù)集中部分實驗數(shù)據(jù)集

對實驗數(shù)據(jù)集進(jìn)行預(yù)處理，首先對其中normal、smurf和neptune的數(shù)據(jù)進(jìn)行降采樣；然后將具有協(xié)議類型(protocol_type)離散特征的數(shù)據(jù)映射成整數(shù)型變量，再進(jìn)行獨熱編碼(one-hot code)操作；最后，將預(yù)處理過的實驗數(shù)據(jù)進(jìn)行亂序，取10組不同隨機順序的數(shù)據(jù)進(jìn)行實驗。

將IDPCA在給出的數(shù)據(jù)集上進(jìn)行測試，以相對距離為y軸、局部密度為x軸構(gòu)建相應(yīng)的數(shù)據(jù)集決策圖，如圖4所示，相應(yīng)的數(shù)據(jù)集聚類結(jié)果見圖5。由實驗結(jié)果可以看出，IDPCA算法基本可以識別所有的類簇。

圖4 KDDCupp99數(shù)據(jù)集中部分?jǐn)?shù)據(jù)集的決策圖

圖5 KDDCupp99數(shù)據(jù)集中部分?jǐn)?shù)據(jù)集的聚類結(jié)果

將IDPCA與k均值算法、DBSCAN算法進(jìn)行性能對比，分別從評測運行時間、完整性、同質(zhì)性和檢測準(zhǔn)確率4個性能指標(biāo)，性能指標(biāo)描述與評測結(jié)果分別見表2、3。IDPCA、k均值算法均設(shè)置聚類中心數(shù)量為25，DBSCAN算法選擇默認(rèn)參數(shù)。

從表3中可以看出：在運行時間方面，k均值算法用時最短，僅為3.56 s，IDPCA僅次于它，而DBSCAN的運行時間較長；在完整性方面，分值越高越好，DBSCAN算法得分最高，IDPCA得分仍然居中，k均值算法得分最低；在同質(zhì)性方面，IDPCA得分最高，k均值算法居中，DBSCAN算法得分最低；在檢測準(zhǔn)確率方面，IDPCA的準(zhǔn)確率最高，k均值算法的次之，DBSCAN算法的最低。如果按照第1名的得3分、第2名得2分、第3名得1分計算，IDPCA的綜合得分為10分，k均值算法的為8分，DBSCAN算法的為6分，因此，IDPCA在綜合性能方面較有優(yōu)勢。

表2 聚類算法的性能指標(biāo)及其描述

表3 不同聚類算法的性能指標(biāo)評測結(jié)果

4 結(jié)論

在各種網(wǎng)絡(luò)異常流量檢測技術(shù)中，密度峰值聚類作為新型聚類方法，其優(yōu)點是不需要任何預(yù)定義的參數(shù)和任何迭代過程。本文中提出基于IDPCA的網(wǎng)絡(luò)異常流量檢測方案，首先對網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行預(yù)處理和分組亂序，然后計算相應(yīng)屬性值并利用局部密度發(fā)現(xiàn)簇中心點，最后采用一種新的標(biāo)簽傳遞方式形成相應(yīng)的簇群直至處理完所有數(shù)據(jù)。實驗結(jié)果表明，IDPCA提升了網(wǎng)絡(luò)異常流量的檢測準(zhǔn)確率，綜合性能優(yōu)于k均值算法和DBSCAN算法。網(wǎng)絡(luò)中的攻擊流量往往是未知的，新型攻擊流量不斷出現(xiàn)，因此，在未來工作中將繼續(xù)研究其他數(shù)據(jù)集的特征，并對相應(yīng)的異常流量檢測技術(shù)進(jìn)行改進(jìn)和完善。