摘 要：
互聯(lián)網(wǎng)的不斷發(fā)展和廣泛使用給網(wǎng)絡用戶帶來了極大的方便，但同時也使得網(wǎng)絡安全形勢變得越來越嚴峻。針對網(wǎng)絡異常檢測方法檢測精度不高，網(wǎng)絡環(huán)境動態(tài)不穩(wěn)定的問題，提出了基于K-最近鄰算法(K-Nearest Neighbor,KNN)的網(wǎng)絡流量異常檢測算法。算法基于屬性加權與距離加權組合加權的方法進行異常檢測，其中使用隨機森林算法進行特征選擇并為特征賦予權重，樣本距離采用高斯函數(shù)加權。最后采用KNN算法檢測異常，經(jīng)實驗驗證，本算法具有較好的檢測效果和時效性。
內(nèi)容目錄：
1 網(wǎng)絡流量異常檢測相關算法
1.1 KNN算法
1.2 隨機森林特征選擇算法
1.3 改進的KNN算法思想
2 異常檢測算法設計及數(shù)據(jù)預處理
2.1 算法設計
2.2 數(shù)據(jù)集以及預處理
3 算法實驗與結果分析
3.1 實驗設計
3.2 實驗評估指標
3.3 實驗分析
4 結 語
00 引 言
隨著互聯(lián)網(wǎng)和移動設備的廣泛使用，網(wǎng)絡安全問題也越來越突出。要解決網(wǎng)絡安全問題，需要準確地檢測到惡意網(wǎng)絡行為。近年來異常檢測在網(wǎng)絡監(jiān)控、捕獲特征和流量分布等方面發(fā)揮越來越重要的作用。異常檢測本質是一種數(shù)據(jù)的分類任務，對于分類任務來說，機器學習算法在這一領域已經(jīng)取得了很明顯的效果。機器學習廣泛用于網(wǎng)絡異常檢測中，例如，支持向量機(Support Vector Machine，SVM)、隨機森林(Random Forest，RF)、K-均值聚類(K-means)、K-最近鄰算法(K-Nearest Neighbor，KNN)等。其中KNN算法簡單易于實現(xiàn)，并且支持特征的高維度計算，能在異常檢測中展現(xiàn)較好的效果。但傳統(tǒng)KNN算法在計算樣本之間的距離時將屬性的貢獻看作是相同的，計算樣本距離時權重是固定的，但在實際情況下，每個樣本的屬性貢獻程度不同，這就會造成實際結果與預測結果嚴重偏離的問題。其次，當數(shù)據(jù)分布不均勻時，樣本數(shù)多的類別可能會有分類優(yōu)勢，這就會導致此類別中包含的屬性參數(shù)頻率相應的提高，從而當不同類別的近鄰樣本數(shù)相等時，很有可能因k的取值范圍不同而錯誤分類。所以及時有效地檢測到網(wǎng)絡異常在網(wǎng)絡安全領域具有重大意義。
01 網(wǎng)絡流量異常檢測相關算法
1.1 KNN算法
K-最近鄰算法，是著名的模式識別統(tǒng)計學方法，在機器學習分類算法中占有重要地位。KNN算法的步驟是：首先計算給定測試對象與訓練集中每個對象的距離，然后選定距離最近的k個訓練對象作為測試對象的近鄰，最后根據(jù)這k個近鄰歸屬的主要類別來對測試對象分類，通常，KNN在分類任務中使用“投票法”，即選擇k個實例中出現(xiàn)次數(shù)最多的標記類別作為預測結果。在衡量樣本距離時使用歐氏距離計算相似度。
設樣本的類別由n個屬性決定，即待測樣本是n維向量，假設樣本i的表示方法為
。
表示樣本i的第j個屬性，因此可得到任意兩個樣本之間的歐氏距離：
(1)
1.2 隨機森林特征選擇算法
隨機森林是集成學習bagging類方法的一種，也是最早的集成學習算法之一，隨機森林算法(Random Forest，RF)是利用多棵決策樹對樣本進行訓練并集成預測的一種分類器。它采用bootstrap重抽樣技術從原始樣本中隨機抽取數(shù)據(jù)構造多個樣本，然后對每個重抽樣本采用節(jié)點的隨機分裂技術來構造多棵決策樹，最后將多棵決策樹組合，并通過投票得出最終預測結果。
使用隨機森林選擇特征的算法，利用特征重要性度量值作為特征排序的重要依據(jù)，特征重要性度量是基于袋外樣本(Out-of-bag，OOB)的。通過分別在每個特征上添加噪聲對比分類正確率的方式，來衡量特征的重要程度，當一個特征很重要時，添加噪聲后，預測正確率會明顯下降，若此特征是不重要特征，則添加噪聲后對預測的準確率影響微小。在選擇特征方面隨機森林法已具有較好的效果，也有研究使用卷積自動編碼器來進行特征降維，通過無監(jiān)督學習剔除不重要特征，但無法得到屬性的重要程度。本文希望根據(jù)網(wǎng)絡流量特征對于異常分類的貢獻程度，賦予特征適當?shù)臋嘀亍Ｒ虼?，計算特征的重要性度量和權重大小是一個關鍵的問題。為了消除數(shù)據(jù)不均衡帶來的大偏差影響，
設原始數(shù)據(jù)集為D，特征個數(shù)為N，使用隨機森林Bagging方法對原始數(shù)據(jù)集進行Boot-Strap取樣，對原始數(shù)據(jù)集取樣M次生成M個子數(shù)據(jù)集，在M個數(shù)據(jù)集上構造M棵決策樹，則將數(shù)據(jù)集D劃分為
，根據(jù)劃分后的數(shù)據(jù)集構造M棵決策樹
。在每一棵決策樹上，通過給特征添加噪聲對比分類正確率，得到一個特征的重要性度量。
設第j個屬性的特征的重要性度量為
，即對特征添加噪聲前分類正確的個數(shù)
與添加噪聲后分類正確的個數(shù)
之差，把每個子數(shù)據(jù)集再分別劃分為五份，采用五折交叉驗證計算特征的重要性度量。第 j 個特征的重要性度量
是由5次產(chǎn)生的平均差值來決定。
(2)
其中
代表第i個子數(shù)據(jù)集第j個屬性在添加噪聲前分類正確的個數(shù)，
代表第i個子數(shù)據(jù)集第j個屬性在添加噪聲后分類正確的個數(shù)。
假設測試數(shù)據(jù)集有Q個樣本，分成M個子數(shù)據(jù)集構造M棵決策樹，每個決策樹生成一個預測結果，M棵決策樹的預測結果綜合投票得到對于樣本的集成結果。第i棵決策樹的權重可由下面公式得到：
(3)
代表第i棵決策樹對第j個樣本的預測結果，
代表所有決策樹對第i個樣本的集成預測結果，
代表集成預測的準確率。所以第j個屬性的重要性度量值計算方法為：
(4)
1.3 改進的KNN算法思想
使用高斯函數(shù)對KNN算法自適應的取K值，可以解決樣本空間分布不均問題。傳統(tǒng)KNN算法在分類時給予每個屬性的權重是一樣的，為區(qū)分屬性重要性，本文用隨機森林的算法判斷屬性重要程度并根據(jù)重要程度賦予其權重，隨機森林算法在計算屬性重要度時，它利用隨機重采樣技術bootstrap和節(jié)點隨機分裂技術構建多棵決策樹，通過投票得到最終分類結果。算法采用屬性與樣本距離組合加權(Combined weighted)的思想，提出了基于KNN的組合加權算法(CW-KNN)，提高了異常檢測率，在對樣本距離加權時采用Gaussian函數(shù)進行不同距離的樣本權重優(yōu)化，如果訓練樣本與測試樣本的距離較遠，該距離值權重就較小。也就是給更近的鄰居分配更大的權重，而較遠的鄰居的權重相應地減少。
異常檢測流程圖如圖1所示。
算法使用隨機森林特征加權，那么計算距離公式為：
(5)
獲得經(jīng)過屬性加權后的距離值，取距離最近的前k個元素，使用高斯函數(shù)對樣本距離加權，在處理離散型數(shù)據(jù)時，將k個數(shù)據(jù)用權重區(qū)別對待，預測結果為與第n個數(shù)據(jù)的標簽相同的概率。即：
(6)
在處理數(shù)值型數(shù)據(jù)時，對k個數(shù)據(jù)取加權平均，將每一項的距離乘對應的權重，然后將結果累加，求得總和后，再對其除以所有權重之和。即：
圖1 基于KNN的網(wǎng)絡異常檢測流程
(7)
高斯函數(shù)在距離為0時，權重為1，隨著距離增大，權重減小，但不會變?yōu)?，符合本算法對距離加權時的需求。高斯函數(shù)為：
(8)
02 異常檢測算法設計及數(shù)據(jù)預處理
異常流量檢測是網(wǎng)絡異常檢測的重要研究內(nèi)容，異常流量是在網(wǎng)絡中與正常流量偏移較大的情形，正常流量會隨著網(wǎng)絡環(huán)境和用戶的行為發(fā)生變化。因此，異常流量需要與運行在相同網(wǎng)絡狀態(tài)下的正常流量進行比對，才能判斷出不正常的預期行為。在流量檢測的過程中，DOS攻擊的Bwd Packet Length Std特征與其他類型的流量有較大的差異。正常流量與其他類型的攻擊流量(除DOS)該特征值大部分為0，而DOS攻擊流量具有較大的數(shù)值。因此，通過學習流量的特征，就能正確識別正常流量與異常流量。
2.1 算法設計
網(wǎng)絡異常檢測模型由數(shù)據(jù)收集及預處理模塊，特征選擇模塊，流量分類模塊組成。數(shù)據(jù)收集及預處理模塊將KDD Cup99數(shù)據(jù)集進行預處理，包括將字符型特征轉化成數(shù)值型特征、數(shù)值標準化、數(shù)值歸一化。特征選擇模塊使用隨機森林算法判斷屬性重要程度并根據(jù)重要程度去除無關特征，按照屬性重要程度進行加權。流量異常檢測模塊根據(jù)待測樣本與訓練樣本加權距離，通過改進KNN算法進行分類，以確定是否為攻擊流量以及攻擊類型。
2.2 數(shù)據(jù)集以及預處理
本實驗使用KDD Cup99數(shù)據(jù)集，共有311 029條數(shù)據(jù)，實驗訓練集與測試集比例為2：8。
KDD Cup99數(shù)據(jù)集是從一個模擬的美國空軍局域網(wǎng)上采集來的9個星期的網(wǎng)絡連接數(shù)據(jù)，分成具有標識的訓練數(shù)據(jù)和未加標識的測試數(shù)據(jù)。在訓練數(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)絡流量統(tǒng)計特征和基于主機的網(wǎng)絡流量統(tǒng)計特征。數(shù)據(jù)集中異常數(shù)據(jù)類型分為4類：DOS、PROBE、U2R、R2L。
03 算法實驗與結果分析
3.1 實驗設計
本節(jié)評估本文提出的算法的性能，所有的實驗均在windos10操作系統(tǒng)中實現(xiàn)，選用KDD Cup99數(shù)據(jù)集，利用python3編譯環(huán)境，結合Pycharm編輯器實現(xiàn)對CW-KNN異常檢測算法的仿真。
3.2 實驗評估指標
檢測率(DR)和誤報率(FAR)是決定異常檢測算法檢測精度的重要指標。檢測率是指正確檢測的異常數(shù)目占實際異常數(shù)目的百分比。誤報率是指錯誤檢測的異常數(shù)目占檢測異常數(shù)目的百分比?；诨煜仃嚩攘糠匠倘缦拢渲蠺P是數(shù)據(jù)為異常且預測為異常的數(shù)量，TN是數(shù)據(jù)為正常且預測為正常的數(shù)量，F(xiàn)P是數(shù)據(jù)為正常但預測為異常的數(shù)量，F(xiàn)N是數(shù)據(jù)為異常但預測為正常的數(shù)量，本文利用以上指標對本文提出的異常檢測方法進行驗證。
檢測率和誤報率定義如下：
3.3 實驗分析
本節(jié)重點評估結合KNN算法，使用隨機森林降維并為特征加權的方法進行異常檢測所獲得的結果。為了展示所建模型的有效性，我們使用KDD Cup99數(shù)據(jù)集進行了大量實驗。實驗效果與原始KNN和基于距離加權的KNN(DIS-KNN)算法進行對比，驗證CW-KNN算法的實驗有效性。從原始數(shù)據(jù)集中選取訓練數(shù)據(jù)和測試數(shù)據(jù)的樣本，為了表明提出的方法的有效性，我們進行了廣泛的實驗，將K的參數(shù)取值范圍確定為1，3，5，7，9，11這在一定程度上改變了最近鄰居的數(shù)量，能有效地對比實驗效果。結果如表1所示。
表1 不同K值下檢測算法的檢測率對比
由表1可以看出隨著K的取值變化，三種異常檢測模型的檢測準確率也隨之波動，與KNN與DIS-KNN(基于距離加權的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)絡數(shù)據(jù)流異常檢測中的準確性，與原始KNN算法和單一的距離加權的方法(DIS-KNN)相比，組合加權的KNN方法具有較高的檢測率。對于四種攻擊類型的檢測率效果也比較理想，由于U2r攻擊類型在測試集中占比重較小，因此檢測率較低，對Dos攻擊的檢測率能達到100%，因此可以證明算法的有效性。
表2 CM-KNN算法對于各攻擊類型檢測結果
表3 各算法的檢測率和誤報率對比
04 結 語
針對現(xiàn)在的網(wǎng)絡異常檢測方法檢測精度不高，網(wǎng)絡環(huán)境動態(tài)不穩(wěn)定的問題，本文提出基于KNN的網(wǎng)絡流量異常檢測模型。使用基于KNN的屬性加權與距離加權相結合的方法進行流量異常檢測，屬性加權使用隨機森林算法對屬性重要性排序并對其加權，距離加權使用高斯距離加權。本文方法較好地優(yōu)化了算法性能，提高了檢測率，能有效檢測各類攻擊行為。由于KNN算法對于高維數(shù)據(jù)計算量大，檢測效率有待提高，下一步的研究重點是將無監(jiān)督學習應用于異常檢測，提高算法的健壯性和效率。
引用本文：張凡,高仲合,牛琨.基于KNN的網(wǎng)絡流量異常檢測研究[J].通信技術,2021,54(5):1235-1239.
作者簡介 >>>張 凡，碩士，主要研究方向為網(wǎng)絡信息安全;高仲合，男，碩士，教授，主要研究方向為計算機網(wǎng)絡與通信;?！＄?，碩士，主要研究方向為物聯(lián)網(wǎng)無線射頻識別?；痦椖浚簢易匀豢茖W基金青年項目(No.61601261);山東省自然科學基金博士基金(No.ZR2016FB20);山東省高等學校科技計劃(No.J17KA062);教育部產(chǎn)學合作協(xié)同育人項目(No.201602028014)。選自《通信技術》2021年第5期(為便于排版，已省去原文參考文獻)
原文來源：信息安全與通信保密雜志社
