摘　要：

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

內(nèi)容目錄：

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

1.1　KNN算法

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

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

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

2.1　算法設(shè)計(jì)

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

3　算法實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)設(shè)計(jì)

3.2　實(shí)驗(yàn)評(píng)估指標(biāo)

3.3　實(shí)驗(yàn)分析

4　結(jié)　語(yǔ)

00  引　言

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

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

1.1　KNN算法

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

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

(1)

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

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

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

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

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

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

(2)

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

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

(3) 

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

(4)

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

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

異常檢測(cè)流程圖如圖1所示。

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

(5)

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

(6)

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

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

(7)

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

(8)

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

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

2.1　算法設(shè)計(jì)

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

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

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

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

03 算法實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)設(shè)計(jì)

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

3.2　實(shí)驗(yàn)評(píng)估指標(biāo)

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

檢測(cè)率和誤報(bào)率定義如下：

3.3　實(shí)驗(yàn)分析

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

表1　不同K值下檢測(cè)算法的檢測(cè)率對(duì)比

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

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

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

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

表3　各算法的檢測(cè)率和誤報(bào)率對(duì)比

04 結(jié)　語(yǔ)

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

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

作者簡(jiǎn)介 >>>張　凡，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全;高仲合，男，碩士，教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與通信;?！＄T士，主要研究方向?yàn)槲锫?lián)網(wǎng)無(wú)線射頻識(shí)別。基金項(xiàng)目：國(guó)家自然科學(xué)基金青年項(xiàng)目(No.61601261);山東省自然科學(xué)基金博士基金(No.ZR2016FB20);山東省高等學(xué)?？萍加?jì)劃(No.J17KA062);教育部產(chǎn)學(xué)合作協(xié)同育人項(xiàng)目(No.201602028014)。選自《通信技術(shù)》2021年第5期(為便于排版，已省去原文參考文獻(xiàn))

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