摘　要：

互聯(lián)網(wǎng)的不斷發(fā)展和廣泛使用給網(wǎng)絡(luò)用戶帶來了極大的方便，但同時也使得網(wǎng)絡(luò)安全形勢變得越來越嚴(yán)峻。針對網(wǎng)絡(luò)異常檢測方法檢測精度不高，網(wǎng)絡(luò)環(huán)境動態(tài)不穩(wěn)定的問題，提出了基于K-最近鄰算法(K-Nearest Neighbor,KNN)的網(wǎng)絡(luò)流量異常檢測算法。算法基于屬性加權(quán)與距離加權(quán)組合加權(quán)的方法進(jìn)行異常檢測，其中使用隨機(jī)森林算法進(jìn)行特征選擇并為特征賦予權(quán)重，樣本距離采用高斯函數(shù)加權(quán)。最后采用KNN算法檢測異常，經(jīng)實驗驗證，本算法具有較好的檢測效果和時效性。

內(nèi)容目錄：

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

1.1　KNN算法

1.2　隨機(jī)森林特征選擇算法

1.3　改進(jìn)的KNN算法思想

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

2.1　算法設(shè)計

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

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

3.1　實驗設(shè)計

3.2　實驗評估指標(biāo)

3.3　實驗分析

4　結(jié)　語

00  引　言

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

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

1.1　KNN算法

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

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

(1)

1.2　隨機(jī)森林特征選擇算法

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

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

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

設(shè)第j個屬性的特征的重要性度量為，即對特征添加噪聲前分類正確的個數(shù)與添加噪聲后分類正確的個數(shù)之差，把每個子數(shù)據(jù)集再分別劃分為五份，采用五折交叉驗證計算特征的重要性度量。第 j 個特征的重要性度量

是由5次產(chǎn)生的平均差值來決定。

(2)

其中代表第i個子數(shù)據(jù)集第j個屬性在添加噪聲前分類正確的個數(shù)，代表第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) 

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

(4)

1.3　改進(jìn)的KNN算法思想

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

異常檢測流程圖如圖1所示。

算法使用隨機(jī)森林特征加權(quán)，那么計算距離公式為：

(5)

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

(6)

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

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

(7)

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

(8)

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

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

2.1　算法設(shè)計

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

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

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

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

03 算法實驗與結(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　實驗評估指標(biāo)

檢測率(DR)和誤報率(FAR)是決定異常檢測算法檢測精度的重要指標(biāo)。檢測率是指正確檢測的異常數(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ù)量，本文利用以上指標(biāo)對本文提出的異常檢測方法進(jìn)行驗證。

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

3.3　實驗分析

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

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

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

由此可以分析，參數(shù)K取值在3到5之間，檢測率有大幅度提升，當(dāng)K大于9時，對于各算法，檢測率逐漸降低.當(dāng)參數(shù)K取5時CW-KNN能取得最高檢測率，整體來看，CW-KNN能取得較高的檢測率。

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

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

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

04 結(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é)合的方法進(jìn)行流量異常檢測，屬性加權(quán)使用隨機(jī)森林算法對屬性重要性排序并對其加權(quán)，距離加權(quán)使用高斯距離加權(quán)。本文方法較好地優(yōu)化了算法性能，提高了檢測率，能有效檢測各類攻擊行為。由于KNN算法對于高維數(shù)據(jù)計算量大，檢測效率有待提高，下一步的研究重點是將無監(jiān)督學(xué)習(xí)應(yīng)用于異常檢測，提高算法的健壯性和效率。

引用本文：張凡,高仲合,牛琨.基于KNN的網(wǎng)絡(luò)流量異常檢測研究[J].通信技術(shù),2021,54(5):1235-1239.

作者簡介 >>>張　凡，碩士，主要研究方向為網(wǎng)絡(luò)信息安全;高仲合，男，碩士，教授，主要研究方向為計算機(jī)網(wǎng)絡(luò)與通信;牛　琨，碩士，主要研究方向為物聯(lián)網(wǎng)無線射頻識別?；痦椖浚簢易匀豢茖W(xué)基金青年項目(No.61601261);山東省自然科學(xué)基金博士基金(No.ZR2016FB20);山東省高等學(xué)校科技計劃(No.J17KA062);教育部產(chǎn)學(xué)合作協(xié)同育人項目(No.201602028014)。選自《通信技術(shù)》2021年第5期(為便于排版，已省去原文參考文獻(xiàn))

原文來源：信息安全與通信保密雜志社