基于KNN 的網(wǎng)絡(luò)流量異常檢測研究*

張 凡，高仲合，牛 琨

（曲阜師范大學，山東 曲阜 273165）

0 引言

隨著互聯(lián)網(wǎng)和移動設(shè)備的廣泛使用，網(wǎng)絡(luò)安全問題也越來越突出。要解決網(wǎng)絡(luò)安全問題，需要準確地檢測到惡意網(wǎng)絡(luò)行為[1]。近年來異常檢測在網(wǎng)絡(luò)監(jiān)控、捕獲特征和流量分布等方面發(fā)揮越來越重要的作用。異常檢測本質(zhì)是一種數(shù)據(jù)的分類任務(wù)，對于分類任務(wù)來說，機器學習算法在這一領(lǐng)域已經(jīng)取得了很明顯的效果[2]。機器學習廣泛用于網(wǎng)絡(luò)異常檢測中，例如，支持向量機（Support Vector Machine，SVM）、隨機森 林（Random Forest，RF）、K-均值聚類（K-means）、K-最近鄰算法（K-Nearest Neighbor，KNN）等。其中KNN 算法簡單易于實現(xiàn)，并且支持特征的高維度計算，能在異常檢測中展現(xiàn)較好的效果[3]。但傳統(tǒng)KNN 算法在計算樣本之間的距離時將屬性的貢獻看作是相同的，計算樣本距離時權(quán)重是固定的，但在實際情況下，每個樣本的屬性貢獻程度不同，這就會造成實際結(jié)果與預(yù)測結(jié)果嚴重偏離的問題。當數(shù)據(jù)分布不均勻時，樣本數(shù)多的類別可能會有分類優(yōu)勢，這就會導致此類別中包含的屬性參數(shù)頻率相應(yīng)的提高，從而當不同類別的近鄰樣本數(shù)相等時，很有可能因k的取值范圍不同而錯誤分類。所以及時有效地檢測到網(wǎng)絡(luò)異常在網(wǎng)絡(luò)安全領(lǐng)域具有重大意義[4]。

1 網(wǎng)絡(luò)流量異常檢測相關(guān)算法

1.1 KNN 算法

K-最近鄰算法是著名的模式識別統(tǒng)計學方法，在機器學習分類算法中占有重要地位。KNN 算法中，首先計算給定測試對象與訓練集中每個對象的距離，其次選定距離最近的k個訓練對象作為測試對象的近鄰，最后根據(jù)這k個近鄰歸屬的主要類別來對測試對象分類。通常，KNN 在分類任務(wù)中使用“投票法”，即選擇k個實例中出現(xiàn)次數(shù)最多的標記類別作為預(yù)測結(jié)果。在衡量樣本距離時使用歐氏距離計算相似度。

設(shè)樣本的類別由n個屬性決定，即待測樣本是n維向量，假設(shè)樣本i的表示方法為表示樣本i的第j個屬性，因此可得到任意兩個樣本之間的歐氏距離：

1.2 隨機森林特征選擇算法

隨機森林是集成學習Bagging 類方法的一種，也是最早的集成學習算法之一。隨機森林算法（Random Forest，RF）是利用多棵決策樹對樣本進行訓練并集成預(yù)測的一種分類器[5]。它采用Boot-Strap 重抽樣技術(shù)從原始樣本中隨機抽取數(shù)據(jù)構(gòu)造多個樣本，然后對每個重抽樣本采用節(jié)點的隨機分裂技術(shù)來構(gòu)造多棵決策樹，最后將多棵決策樹組合，并通過投票得出最終預(yù)測結(jié)果。

使用隨機森林選擇特征的算法，利用特征重要性度量值作為特征排序的重要依據(jù)，特征重要性度量是基于袋外樣本（Out-Of-Bag，OOB）的。通過分別在每個特征上添加噪聲對比分類正確率的方式，來衡量特征的重要程度，當一個特征很重要時，添加噪聲后，預(yù)測正確率會明顯下降，若此特征是不重要特征，則添加噪聲后對預(yù)測的準確率影響微小。在選擇特征方面隨機森林法已具有較好的效果，也有研究使用卷積自動編碼器來進行特征降維，通過無監(jiān)督學習剔除不重要特征，但無法得到屬性的重要程度[6]。本文希望根據(jù)網(wǎng)絡(luò)流量特征對于異常分類的貢獻程度，賦予特征適當?shù)臋?quán)重。因此，計算特征的重要性度量和權(quán)重大小是一個關(guān)鍵的問題。為了消除數(shù)據(jù)不均衡帶來的大偏差影響。

設(shè)原始數(shù)據(jù)集為D，特征個數(shù)為N，使用隨機森林Bagging 方法對原始數(shù)據(jù)集進行Boot-Strap 取樣，對原始數(shù)據(jù)集取樣M次生成M個子數(shù)據(jù)集，在M個數(shù)據(jù)集上構(gòu)造M棵決策樹，則將數(shù)據(jù)集D劃分為{D1,D2,…,DM}，根據(jù)劃分后的數(shù)據(jù)集構(gòu)造M棵決策樹{T1,T2,…,TM}。在每一棵決策樹上，通過給特征添加噪聲對比分類正確率，得到一個特征的重要性度量。

設(shè)第j個屬性的特征的重要性度量為θj，即對特征添加噪聲前分類正確的個數(shù)RjF與添加噪聲后分類正確的個數(shù)RjB之差，把每個子數(shù)據(jù)集再分別劃分為五份，采用五折交叉驗證計算特征的重要性度量。第j個特征的重要性度量IMij是由5 次產(chǎn)生的平均差值來決定。

式中，RijF代表第i個子數(shù)據(jù)集第j個屬性在添加噪聲前分類正確的個數(shù)，RijB代表第i個子數(shù)據(jù)集第j個屬性在添加噪聲后分類正確的個數(shù)。

假設(shè)測試數(shù)據(jù)集有Q個樣本，分成M個子數(shù)據(jù)集構(gòu)造M棵決策樹，每個決策樹生成一個預(yù)測結(jié)果，M棵決策樹的預(yù)測結(jié)果綜合投票得到對于樣本的集成結(jié)果。第i棵決策樹的權(quán)重可由式（3）獲得：

式中，Tij代表第i棵決策樹對第j個樣本的預(yù)測結(jié)果，Ej代表所有決策樹對第i個樣本的集成預(yù)測結(jié)果，ACCensemble代表集成預(yù)測的準確率。所以第j個屬性的重要性度量值計算方法為：

1.3 改進的KNN 算法思想

使用高斯函數(shù)對KNN 算法自適應(yīng)地取K值，可以解決樣本空間分布不均問題[7]。傳統(tǒng)KNN 算法在分類時給予每個屬性的權(quán)重是一樣的。為區(qū)分屬性重要性，本文用隨機森林的算法判斷屬性重要程度并根據(jù)重要程度賦予其權(quán)重。在計算屬性重要度時，它利用隨機重采樣技術(shù)Boot-Strap 和節(jié)點隨機分裂技術(shù)構(gòu)建多棵決策樹，通過投票得到最終分類結(jié)果。算法采用屬性與樣本距離組合加權(quán)（Combined Weighted）的思想，提出了基于KNN的組合加權(quán)算法（CW-KNN），提高了異常檢測率。在對樣本距離加權(quán)時采用Gaussian 函數(shù)進行不同距離的樣本權(quán)重優(yōu)化，如果訓練樣本與測試樣本的距離較遠，該距離值權(quán)重就較小。也就是給更近的鄰居分配更大的權(quán)重，而較遠的鄰居的權(quán)重相應(yīng)地減少。

異常檢測流程圖如圖1 所示。算法使用隨機森林特征加權(quán)，那么計算距離公式為：

獲得經(jīng)過屬性加權(quán)后的距離值，取距離最近的前k個元素，使用高斯函數(shù)對樣本距離加權(quán)，在處理離散型數(shù)據(jù)時，將k個數(shù)據(jù)用權(quán)重區(qū)別對待，預(yù)測結(jié)果為與第n個數(shù)據(jù)的標簽相同的概率：

在處理數(shù)值型數(shù)據(jù)時，對k個數(shù)據(jù)取加權(quán)平均，將每一項的距離乘對應(yīng)的權(quán)重，然后將結(jié)果累加，求得總和后，再對其除以所有權(quán)重之和：

圖1 基于KNN 的網(wǎng)絡(luò)異常檢測流程

高斯函數(shù)在距離為0 時，權(quán)重為1，隨著距離增大，權(quán)重減小，但不會變?yōu)?，符合本算法對距離加權(quán)時的需求。高斯函數(shù)為：

2 異常檢測算法設(shè)計及數(shù)據(jù)預(yù)處理

異常流量檢測是網(wǎng)絡(luò)異常檢測的重要研究內(nèi)容，異常流量是在網(wǎng)絡(luò)中與正常流量偏移較大的情形，正常流量會隨著網(wǎng)絡(luò)環(huán)境和用戶的行為發(fā)生變化。因此，異常流量需要與運行在相同網(wǎng)絡(luò)狀態(tài)下的正常流量進行比對，才能判斷出不正常的預(yù)期行為[8]。在流量檢測的過程中，DoS 攻擊的Bwd Packet Length Std 特征與其他類型的流量有較大的差異。正常流量與其他類型的攻擊流量（除DoS）該特征值大部分為0，而DoS 攻擊流量具有較大的數(shù)值。因此，通過學習流量的特征，就能正確識別正常流量與異常流量[9]。

2.1 算法設(shè)計

網(wǎng)絡(luò)異常檢測模型由數(shù)據(jù)收集及預(yù)處理模塊，特征選擇模塊，流量分類模塊組成。數(shù)據(jù)收集及預(yù)處理模塊將KDD Cup99 數(shù)據(jù)集進行預(yù)處理，包括將字符型特征轉(zhuǎn)化成數(shù)值型特征、數(shù)值標準化、數(shù)值歸一化。特征選擇模塊使用隨機森林算法判斷屬性重要程度并根據(jù)重要程度去除無關(guān)特征，按照屬性重要程度進行加權(quán)。流量異常檢測模塊根據(jù)待測樣本與訓練樣本加權(quán)距離，通過改進KNN 算法進行分類，以確定是否為攻擊流量以及攻擊類型。

2.2 數(shù)據(jù)集以及預(yù)處理

本實驗使用KDD Cup99 數(shù)據(jù)集，共有311 029條數(shù)據(jù)，實驗訓練集與測試集比例為2:8。

KDD Cup99 數(shù)據(jù)集是從一個模擬的美國空軍局域網(wǎng)上采集來的9 個星期的網(wǎng)絡(luò)連接數(shù)據(jù)，分成具有標識的訓練數(shù)據(jù)和未加標識的測試數(shù)據(jù)[10]。在訓練數(shù)據(jù)集中包含了1 種正常的標識類型normal 和22種訓練攻擊類型，另外有14 種攻擊僅出現(xiàn)在測試數(shù)據(jù)集中。KDD Cup99 訓練數(shù)據(jù)集中每個連接記錄包含了41 個固定的特征屬性和1 個類標識，標識用來表示該條連接記錄是正常的，或是某個具體的攻擊類型。在41 個固定的特征屬性中，9 個特征屬性為離散（Symbolic）型，其他均為連續(xù)（Continuous）型。這41 個屬性可以分為4類：TCP 連接基本特征、TCP 連接內(nèi)容特征、基于時間的網(wǎng)絡(luò)流量統(tǒng)計特征和基于主機的網(wǎng)絡(luò)流量統(tǒng)計特征。數(shù)據(jù)集中異常數(shù)據(jù)類型分為DoS、PROBE、U2R 和R2L 共4 類。

3 算法實驗與結(jié)果分析

3.1 實驗設(shè)計

本節(jié)評估本文提出的算法的性能，所有的實驗均在Windos10 操作系統(tǒng)中實現(xiàn)，選用KDD Cup99數(shù)據(jù)集，利用Python3 編譯環(huán)境，結(jié)合Pycharm 編輯器實現(xiàn)對CW-KNN 異常檢測算法的仿真。

3.2 實驗評估指標

檢測率（Detection Rate，DR）和誤報率（False Alarm Rate，F(xiàn)AR）是決定異常檢測算法檢測精度的重要指標。檢測率是指正確檢測的異常數(shù)目占實際異常數(shù)目的百分比。誤報率是指錯誤檢測的異常數(shù)目占檢測異常數(shù)目的百分比?；诨煜仃嚩攘糠匠倘缦?，其中TP是數(shù)據(jù)為異常且預(yù)測為異常的數(shù)量，TN是數(shù)據(jù)為正常且預(yù)測為正常的數(shù)量，F(xiàn)P是數(shù)據(jù)為正常但預(yù)測為異常的數(shù)量，F(xiàn)N是數(shù)據(jù)為異常但預(yù)測為正常的數(shù)量。本文利用以上指標對本文提出的異常檢測方法進行驗證。

檢測率和誤報率定義如下：

3.3 實驗分析

本節(jié)重點評估結(jié)合KNN 算法，使用隨機森林降維并為特征加權(quán)的方法進行異常檢測所獲得的結(jié)果。為了展示所建模型的有效性，使用KDD Cup99數(shù)據(jù)集進行了大量實驗。實驗效果與原始KNN 和基于距離加權(quán)的KNN（DIS-KNN）算法進行對比，驗證CW-KNN 算法的實驗有效性。從原始數(shù)據(jù)集中選取訓練數(shù)據(jù)和測試數(shù)據(jù)的樣本，為了表明提出的方法的有效性進行了廣泛的實驗，將K的參數(shù)取值范圍確定為1、3、5、7、9、11，在一定程度上改變了最近鄰居的數(shù)量，能有效地對比實驗效果。結(jié)果如表1 所示。

表1 不同K 值下檢測算法的檢測率對比

由表1 可以看出隨著K的取值變化，3 種異常檢測模型的檢測準確率也隨之波動，與KNN 與DISKNN（基于距離加權(quán)的KNN 算法）相比。CW-KNN算法的異常檢測模型檢測率較高，并能有效降低誤報率和漏報率?？梢钥闯?，CW-KNN 取得了較好的檢測率并相比較其他兩種方法也更穩(wěn)定。

由此可以分析：參數(shù)K取值在3～5 時，檢測率有大幅度提升；當K＞9 時，各算法檢測率逐漸降低；當參數(shù)K=5 時，CW-KNN 能取得最高檢測率。整體來看，CW-KNN 能取得較高的檢測率。

表2 和表3 驗證了攻擊類別的高發(fā)現(xiàn)率，對DoS 攻擊的檢測率可達到100%。與KNN 算法相比，在檢測率方面CW-KNN 算法具有明顯優(yōu)勢，由此可以驗證CW-KNN 算法在網(wǎng)絡(luò)數(shù)據(jù)流異常檢測中的準確性。與原始KNN 算法和單一的距離加權(quán)的方法（DIS-KNN）相比，組合加權(quán)的KNN 方法具有較高的檢測率。對于4 種攻擊類型的檢測率效果也比較理想，由于U2R 攻擊類型在測試集中占比重較小，因此檢測率較低，對DoS 攻擊的檢測率能達到100%，因此可以證明算法的有效性。

表2 CM-KNN 算法對于各攻擊類型檢測結(jié)果

表3 各算法的檢測率和誤報率對比

4 結(jié)語

針對現(xiàn)在的網(wǎng)絡(luò)異常檢測方法檢測精度不高，網(wǎng)絡(luò)環(huán)境動態(tài)不穩(wěn)定的問題，本文提出基于KNN的網(wǎng)絡(luò)流量異常檢測模型。使用基于KNN 的屬性加權(quán)與距離加權(quán)相結(jié)合的方法進行流量異常檢測，屬性加權(quán)使用隨機森林算法對屬性重要性排序并對其加權(quán)，距離加權(quán)使用高斯距離加權(quán)。本文方法較好地優(yōu)化了算法性能，提高了檢測率，能有效檢測各類攻擊行為。由于KNN 算法對于高維數(shù)據(jù)計算量大，檢測效率有待提高，下一步的研究重點是將無監(jiān)督學習應(yīng)用于異常檢測，提高算法的健壯性和效率。