基于改進密度峰值聚類的異常流量檢測

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

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

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

現今，人們生活中的各個方面都離不開互聯網，如互聯網金融、智能家居、智能醫療設備、智能網聯汽車等。這些應用網絡中存在規模巨大的數據交互信息，如果這些信息不加以保護，將會受到各種各樣的網絡攻擊，甚至會導致計算機系統破壞。異常流量檢測是網絡信息安全領域中的一項重要的主動安全檢測技術，可以檢測出網絡中的異常流量，從而保護網絡安全，因此，通過異常流量檢測發現潛在的非法的惡意行為，是解決網絡信息安全問題的關鍵所在[2]。

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

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

1 聚類算法

作為一種無監督學習的經典方法，聚類算法在當前復雜的現實網絡環境中極其重要。由于網絡環境無法高度精準并高效獲得規模較大的新收集流量的類別標記，因此聚類算法更適合作為當前異常流量檢測的技術。

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

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

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

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

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

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

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

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

N1、N2、N3、N4、N5、N6—預設數據點。圖1 具有噪聲的基于密度的聚類算法的相關定義示意圖

DBSCAN算法具體步驟如下：

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

步驟2將樣本數據集合D中所有數據點標記為未處理狀態。

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

步驟4重復步驟3，直至所有數據點都被處理。

步驟5輸出聚類結果C。

1.2 密度峰值聚類算法

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

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

(1)

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

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

(2)

即該數據點i的歐氏距離等于其他數據點與該點的最大距離。

任意數據點i的局部密度ρi定義為

其中

(3)

式中dc為截斷距離。

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

(4)

DPCA流程如圖2所示。

2 基于IDPCA的異常流量檢測

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

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

步驟1輸入數據集合D、截斷距離dc。

步驟2發現簇中心點。根據式(1)、(2)計算點距離矩陣，根據式(3)、(4)計算點的局部密度，構建決策圖并選擇簇中心點。

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

步驟4輸出聚類結果簇C。

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

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

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

(5)

δt的定義為

(6)

式中γ1、γ2均為經驗參數。

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

3 結果與分析

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

表1 KDDCup99數據集中部分實驗數據集

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

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

圖4 KDDCupp99數據集中部分數據集的決策圖

圖5 KDDCupp99數據集中部分數據集的聚類結果

將IDPCA與k均值算法、DBSCAN算法進行性能對比，分別從評測運行時間、完整性、同質性和檢測準確率4個性能指標，性能指標描述與評測結果分別見表2、3。IDPCA、k均值算法均設置聚類中心數量為25，DBSCAN算法選擇默認參數。

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

表2 聚類算法的性能指標及其描述

表3 不同聚類算法的性能指標評測結果

4 結論

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