基于網(wǎng)絡(luò)資源的kNN網(wǎng)絡(luò)流量分類模型的研究

程　珊， 鈕　焱， 李　軍

(湖北工業(yè)大學(xué)計算機學(xué)院， 湖北 武漢 430068)

?

基于網(wǎng)絡(luò)資源的kNN網(wǎng)絡(luò)流量分類模型的研究

程珊， 鈕焱， 李軍

(湖北工業(yè)大學(xué)計算機學(xué)院， 湖北 武漢 430068)

為了快速有效的識別網(wǎng)絡(luò)流量中的攻擊行為，根據(jù)同一類應(yīng)用對網(wǎng)絡(luò)資源的消耗具有相似性，不同類應(yīng)用對網(wǎng)絡(luò)資源的消耗具有差異性，提出了一種基于網(wǎng)絡(luò)資源的kNN流量分類模型。該模型可以從多種網(wǎng)絡(luò)資源中選取三種屬性作為特征，采用改進的 kNN 算法進行流量檢測，對網(wǎng)絡(luò)中的各種流量特別是攻擊類流量盡可能快速并有效的識別，給網(wǎng)絡(luò)防御的啟動提供重要依據(jù)。實驗結(jié)果表明：改進的kNN算法在保證識別率的同時有效提高分類的速度。

流量識別 ； kNN； 網(wǎng)絡(luò)資源； 網(wǎng)絡(luò)攻防

隨著網(wǎng)絡(luò)應(yīng)用不斷豐富，以及各種隱藏在網(wǎng)絡(luò)流量中的惡意威脅，網(wǎng)絡(luò)的各種資源變得緊張，導(dǎo)致網(wǎng)絡(luò)性能不斷下降甚至崩潰。由于各種網(wǎng)絡(luò)行為的表現(xiàn)形式是流量，各種網(wǎng)絡(luò)行為隱藏在流量中，因此需要對網(wǎng)絡(luò)流量進行識別：一方面，可以識別出需要占用大量資源的正常流量，調(diào)用相應(yīng)的資源提高網(wǎng)絡(luò)的服務(wù)質(zhì)量。另一方面，大部分的攻擊表現(xiàn)為對網(wǎng)絡(luò)資源的爭奪，可以通過網(wǎng)絡(luò)資源的占用情況識別出網(wǎng)絡(luò)攻擊流量，作為啟動防御措施的重要依據(jù)。因此，有必要尋求一種網(wǎng)絡(luò)流量識別模型對網(wǎng)絡(luò)中的各種流量特別是攻擊類流量盡可能快速并有效地加以識別，以便采取措施預(yù)防網(wǎng)絡(luò)崩潰。

目前國內(nèi)外提出了很多關(guān)于流量的識別與分類的方法。傳統(tǒng)的網(wǎng)絡(luò)流量識別技術(shù)主要有基于端口識別與深層數(shù)據(jù)包檢測的協(xié)議識別方法[1]。但是隨著動態(tài)端口以及協(xié)議加密技術(shù)的應(yīng)用，上述方法的應(yīng)用范圍越來越窄。近幾年機器學(xué)習(xí)方法廣泛應(yīng)用于流量分類，主要有貝葉斯[2]、k-means[3]、支持向量機SVM[3-4]、C4.5決策樹[5]、神經(jīng)網(wǎng)絡(luò)[6]、kNN[7-9]等。

相比較其他的方法，kNN算法有很多優(yōu)點：它簡單易實現(xiàn)，可以處理大量的類別，而且kNN算法還能支持流量的更多特征的高維計算，而特征的數(shù)量會直接影響分類的效果。但是kNN算法也存在不足。kNN算法在對未知樣本分類時，時間消耗很大。本文嘗試應(yīng)用改進的kNN算法與網(wǎng)絡(luò)資源結(jié)合進行流量分類，以期在保證分類效果的同時有更低的時間消耗。

1　kNN算法

k-最近鄰分類法(kNN)最初由 Cover 和 Hart提出，此后它廣泛應(yīng)用于模式識別領(lǐng)域。kNN算法是基于類比學(xué)習(xí)，即通過將給定的檢測樣本與和它相似的訓(xùn)練樣本進行比較來學(xué)習(xí)。kNN算法的基本思想是：先計算待分類樣本與已知類別的訓(xùn)練樣本之間的相似度，相似度一般使用歐氏距離測量，依據(jù)相似度找到與待分類樣本數(shù)據(jù)最相似的k個鄰居，再根據(jù)這些鄰居所屬的類別來判斷待分類樣本數(shù)據(jù)的類別，將待分類樣本指派到它的k個鄰居中權(quán)重最大的類別。

待分類樣本d(x1,x2,…,xn)和訓(xùn)練樣本di(y1,y2,…,yn)的相似度計算公式為：

(1)

待分類樣本d和每一類cj的權(quán)重的計算公式為：

y(di,cj)是類別屬性函數(shù)，如果di屬于cj，那么函數(shù)值為1，否則為0。

最后的分類決策函數(shù)

f(θ)=argmaxcj(p(d,cj))

將待分類樣本d歸屬于權(quán)重最大的那個類別。

通過上述算法介紹我們可以看出，kNN的分類思想和過程比較簡單，但是當訓(xùn)練樣本集較大時，相似度的計算量很大，算法的時間開銷過大。因此可以對其進行改進。

2　改進的kNN算法

kNN算法簡單易實現(xiàn)，支持高維計算，分類效果明顯，但是在尋找k個最近鄰樣本的時候，需要將測試樣本逐一與訓(xùn)練樣本比較相似度，因此計算量龐大，會直接影響分類的速度[10]。而網(wǎng)絡(luò)流量識別在很多應(yīng)用場合需要有較高的實時性。減少需要比較的訓(xùn)練樣本數(shù)量不失為提高分類效率的有效方法。

2.1基本思想

根據(jù)kNN算法的近鄰規(guī)則可知，測試樣本的最近鄰主要分布在靠近測試樣本的區(qū)域內(nèi)。與測試樣本距離較遠的訓(xùn)練樣本，對分類結(jié)果影響較小，基于此，可以將訓(xùn)練樣本進行適當?shù)牟眉?，只需保留位于測試樣本附近區(qū)域的訓(xùn)練樣本。但是隨意確定裁剪區(qū)域的大小是不合適的。如果裁剪區(qū)域太小，會裁減掉過多的訓(xùn)練樣本，影響分類效果。裁剪后的范圍過大，需要比較的訓(xùn)練樣本數(shù)量依然很多，不會明顯提高分類效率。

根據(jù)樣本類別的不同可分為多個樣本子集，每個樣本子集是一個聚類。對于一個聚類，它的所有樣本都圍繞著一個類中心分布。由kNN算法選取出來的k個鄰居，只會分布在靠近類中心和測試點之間的空間上， 可以根據(jù)類中心和測試樣本的位置來確定裁剪區(qū)域的位置和大小。

2.2樣本集裁剪規(guī)則

為每一個類指定一個類中心，類中心為每一個聚類的中心點。計算公式如下：

第j類樣本的類中心

且

(i=1,2,…,n;j=1,2,…,g)

(2)

Nj是第j類樣本的數(shù)量，ymi是第m個樣本的第i個屬性值。

樣本集的裁剪規(guī)則如下：為每一個聚類確定一個類中心O，利用公式(1)歐氏距離公式計算測試樣本到每一個類中心的距離r。然后確定剪裁區(qū)域的位置。將測試樣本點d(x1,x2,…,xn)作為球心，將最短距離rmin作為半徑，做球體的外接立方體。對于每一個訓(xùn)練樣本di(y1,y2,…,yn),如果位于立方體區(qū)域內(nèi)，即

則這個訓(xùn)練樣本保留。否則，予以去除，即裁減掉位于立方體區(qū)域外的訓(xùn)練樣本。可將保留的所有訓(xùn)練樣本定義為一個新的訓(xùn)練樣本集合S，用裁剪后的樣本集S代替大量的原始樣本，進行kNN分類。

為了更清楚的說明裁剪規(guī)則，下面以具有三維特征的樣本為例說明樣本裁減方法。

圖 1　樣本集裁減示意圖

設(shè)某個訓(xùn)練集的分布如圖1所示，其中有4個類別X1、X2、X3和X4，由公式(2)可計算出它們的類中心分別為O(X1)、O(X2)、O(X3)和O(X4)。A(a,b,c)是測試樣本。A到類中心點O(X1)、O(X2)、O(X3)和O(X4)的距離分別是r1、r2、r3、r4(r3

則這個訓(xùn)練樣本保留。裁減掉位于矩形區(qū)域外的訓(xùn)練樣本。通過以上方式的裁剪，得到裁剪區(qū)域S。顯然，對比分布在裁剪區(qū)域S內(nèi)部和外部的樣本與A的相似度，內(nèi)部的相似度更大。此時，分布在S中的訓(xùn)練樣本數(shù)量遠少于原始的訓(xùn)練樣本數(shù)量。只需比較A點與S中的訓(xùn)練樣本的相似度，而不是整個訓(xùn)練樣本。在S而不是整個空間中選出k個最近鄰，再根據(jù)選出的k個最近鄰所屬的類別來判斷待分類樣本數(shù)據(jù)的類別，將待分類樣本指派到它的k個最近鄰中權(quán)重最大的類別，完成A點的分類。

2.3時間復(fù)雜度分析

設(shè)訓(xùn)練樣本集為D，其中包含α個訓(xùn)練樣本，由β種類別的樣本組成。設(shè)測試樣本集為T，其中包含γ個測試樣本。每個訓(xùn)練樣本和測試樣本都是由n維特征屬性組成。傳統(tǒng)的kNN算法的時間復(fù)雜度是O(α×γ)。用改進的kNN算法，先計算β個類中心，針對每一個測試樣本都要進行一次訓(xùn)練樣本集D的裁剪，假設(shè)裁剪后的訓(xùn)練樣本集的規(guī)模的平均值為μ，μ?α。裁剪樣本的時間可以忽略不計。再將γ個測試樣本和裁剪后的μ個訓(xùn)練樣本進行比較，改進后的kNN算法時間復(fù)雜度是O(μ×γ)。由于μ?α，所以很明顯，改進后的kNN算法比傳統(tǒng)kNN算法更有效率。

3　基于改進kNN算法的網(wǎng)絡(luò)流量分類模型

3.1流量分類模型

流量分類模型由數(shù)據(jù)收集及預(yù)處理模型、特征選擇模型、流量分類模型組成(圖2)。

數(shù)據(jù)收集及預(yù)處理模塊定期向服務(wù)器發(fā)送網(wǎng)絡(luò)資源數(shù)據(jù)收集請求，服務(wù)器將回復(fù)的資源使用情況的數(shù)據(jù)傳送給數(shù)據(jù)收集節(jié)點。

特征選擇模塊負責(zé)接收數(shù)據(jù)收集模塊收集到的數(shù)據(jù)，提取出與網(wǎng)絡(luò)行為相關(guān)的3個特征組成三元組，每個三元組都以網(wǎng)絡(luò)行為作為標識。

流量分類模塊負責(zé)將收集到的三元組通過改進的kNN算法進行分類，以此來區(qū)分某時刻的流量是否是攻擊流量或者是來自于哪種應(yīng)用的流量。特征選擇和流量分類模塊是此模型尤為關(guān)鍵的部分。

圖 2　流量分類模型

3.2特征提取

網(wǎng)絡(luò)資源包含吞吐量、帶寬、時延、CPU資源、存儲資源、磁盤資源等。同一類應(yīng)用對網(wǎng)絡(luò)資源的消耗具有相似性，不同的應(yīng)用會消耗特定的網(wǎng)絡(luò)資源[11]。

表1、表2和表3中的數(shù)據(jù)采集于實驗室，分別說明了視頻播放、網(wǎng)頁瀏覽、DDOS攻擊三種行為對網(wǎng)絡(luò)資源消耗的相關(guān)性。表中分別列出了收集到的網(wǎng)絡(luò)流量的3個特征：流量、CPU和內(nèi)存的最小值和最大值，通過分析數(shù)據(jù)，發(fā)現(xiàn)這些特征值都集中在某個范圍內(nèi)。

表1　播放視頻產(chǎn)生的流量的相關(guān)性

表2　瀏覽網(wǎng)頁產(chǎn)生的流量的相關(guān)性

表3　模擬DDOS攻擊產(chǎn)生的流量的相關(guān)性

從數(shù)據(jù)集中可以觀察到：相同行為消耗的資源，有很大的相似性和相關(guān)性，特征值大部分集中在很小的范圍內(nèi)。例如，表1中流量的值的范圍是391.998到8983565.233，但是大約98.1%的樣本在[391.998,2985979.052]內(nèi)。CPU的值的范圍是0到99.999，但是大約98.5%的樣本在[0,16.797]內(nèi)。

將表1、表2中的數(shù)據(jù)進行比較，播放視頻消耗的內(nèi)存的范圍是[0,548.546]，產(chǎn)生的流量的范圍是[391.998,2985979.052]；瀏覽網(wǎng)頁消耗的內(nèi)存的范圍是[0,98.994]，產(chǎn)生的流量的范圍是[924655.872,2297410.454]。明顯地，和瀏覽網(wǎng)頁相比，播放視頻對內(nèi)存的消耗更大，同時會產(chǎn)生大量流量。不同的應(yīng)用對資源的消耗具有差異性。

對比表1、表2和表3的數(shù)據(jù)，三種網(wǎng)絡(luò)行為對CPU和內(nèi)存的消耗存在極大的不同。例如，播放視頻消耗的CPU集中范圍是[0,16.797]，消耗的內(nèi)存集中范圍是[0,548.546]；瀏覽網(wǎng)頁消耗的CPU集中范圍是[0,3.906]，消耗的內(nèi)存集中范圍是[0,98.994]；DDoS攻擊消耗的CPU集中范圍是[0.007，27.739]，消耗的內(nèi)存集中范圍是[12.976，3970.914]。對比發(fā)現(xiàn)，DDoS攻擊行為會消耗大量的CPU和內(nèi)存資源。由此可見，網(wǎng)絡(luò)行為中，CPU和內(nèi)存資源尤為重要。

針對同一類應(yīng)用對資源的消耗存在很大的相似度和相關(guān)性，不同的應(yīng)用對資源的消耗存在明顯的差異性，可以網(wǎng)絡(luò)資源的聯(lián)合分布作為特征屬性，對流量進行分類，從而在必要時調(diào)集所需的資源優(yōu)化網(wǎng)絡(luò)性能改善用戶的體驗，或者在識別出攻擊行為時，及時啟動防御措施，保護網(wǎng)絡(luò)的安全。

在眾多的網(wǎng)絡(luò)資源中，CPU與內(nèi)存尤為重要，網(wǎng)絡(luò)中的CPU資源和內(nèi)存資源是網(wǎng)絡(luò)中重要的資源，網(wǎng)絡(luò)行為基本上離不開這兩個資源的支持,很多時候交換機、路由器會因為這兩個資源的耗盡導(dǎo)致網(wǎng)絡(luò)性能下降直至崩潰，可以依據(jù)CPU與內(nèi)存的特征屬性，對網(wǎng)絡(luò)流量進行分類。網(wǎng)絡(luò)行為通常隱藏在流量中，故選擇流量、CPU和內(nèi)存作為特征屬性，反映網(wǎng)絡(luò)性能的變化。

3.3基于改進kNN算法的網(wǎng)絡(luò)流量分類

根據(jù)改進的kNN算法，按照以下步驟構(gòu)建網(wǎng)絡(luò)流量分類模型。

依次輸入不同類型的樣本流量作為訓(xùn)練樣本集合。

其中，Nj是第j類流量的樣本數(shù)目。

Step2:分別計算新流入的網(wǎng)絡(luò)流量fx到每一個類中心的距離。

Step3:將β個距離由小到大依次排列，選擇最小的距離作為半徑r。

r=min{dist(fx,oj)}

Step4:以fx所在位置為圓心，以r為半徑，作一個球體的外接立方體。確定集合D中的流量是否分布在立方體區(qū)域內(nèi)。判斷方法如下：

滿足條件即位于立方體區(qū)域內(nèi)，反之位于立方體區(qū)域外。

Step5:裁剪掉位于立方體區(qū)域外的流量樣本點，形成一個有γ個流量樣本點的新的流量集合S。

Step6:設(shè)定k值。

Step7:計算待分類的流量fx與集合S中的γ個流量樣本點的相似度。

其中，

Step8:將相似度從大到小依次排列，選出k個相似度最大的流量。

Step9:在這k個流量中，依次計算每個類別的權(quán)重。流量fx屬于Cj類的權(quán)重計算公式為：

y(fi,cj)是類別屬性函數(shù)，如果fi屬于cj，那么函數(shù)值為1，否則為0。

Step10:比較類的權(quán)重，將流量fx分到權(quán)重最大的那個類別中。

f(θ)=argmaxcj(p(fx,cj))

4　實驗及分析

先構(gòu)造一個網(wǎng)絡(luò)，通過服務(wù)器對互聯(lián)網(wǎng)分別進行網(wǎng)頁瀏覽、文件下載和視頻播放訪問，另外，可以使用LOIC進行基于HTTP的DDOS攻擊來模仿異常流量的產(chǎn)生。通過服務(wù)器性能監(jiān)視器的數(shù)據(jù)收集器，分別收集以上4種行為所消耗的流量、CPU和內(nèi)存的數(shù)據(jù)。將收集到的樣本數(shù)據(jù)分成四大類：網(wǎng)頁類、下載類、視頻類和攻擊類，按照每個類別隨機選取500個樣本點，一共2000個樣本點。因為kNN算法要求訓(xùn)練樣本集的類型分布盡可能平均，因此每個類別的訓(xùn)練樣本數(shù)目應(yīng)保持一致。四種類別的樣本數(shù)據(jù)各取前300個樣本點作為訓(xùn)練樣本集，后200個樣本點作為待分類樣本集。分別采用kNN和改進kNN對待分類流量進行分類。四種行為的訓(xùn)練樣本分布見圖3。

圖 3　四種行為的訓(xùn)練樣本分布

本文采用精確度對模型的分類能力進行評估以及使用分類時間來評估分類模型的開銷。

分類時間是指分類模型對網(wǎng)絡(luò)流量所屬類型進行判別的時間。

最終測試結(jié)果見表4和表5。

表4　kNN和改進的kNN時間比較

表5　kNN和改進的kNN精確度比較

從表4中可以看到，改進kNN的分類時間比傳統(tǒng)kNN的要短。改進kNN花費平均24.12ms進行分類，然而傳統(tǒng)的kNN需要花費平均29.19ms進行分類。從表5中可以看到，改進kNN算法的精確度和傳統(tǒng)kNN算法精確度相差不大。因此，裁剪數(shù)據(jù)集并未影響分類的精確性。實驗結(jié)果表明，改進kNN算法有效提高分類的速度。

5　結(jié)論

提出了一種基于網(wǎng)絡(luò)資源的kNN流量分類模型，該模型從多種網(wǎng)絡(luò)資源中選取流量、cpu、內(nèi)存作為特征，采用改進kNN算法進行流量檢測，對網(wǎng)絡(luò)中的各種流量特別是攻擊類流量盡可能快速并有效地識別，給網(wǎng)絡(luò)防御的啟動提供重要的依據(jù)。實驗結(jié)果表明：方法有效可行，在保證精確度的前提下提高了分類的速度。

[1]Qosmos.Deeppacketinspectionandnetworkintelligencetools[EB/OL]. [2016-01-05]http://www.qosmos.com/.

[2]AuldT,MooreAW,GullSF.BayesianneuralnetworksforInternettrafficclassification[J].IEEETransactionsonNeuralNetwork, 2007,18(1) :223-239.

[3]劉三民,孫知信,劉余霞. 基于K均值集成和SVM的P2P流量識別研究[J]. 計算機科學(xué),2012(4):46-48,74.

[4]顧成杰,張順頤. 基于改進SVM的網(wǎng)絡(luò)流量分類方法研究[J]. 儀器儀表學(xué)報,2011(7):1507-1513.

[5]周劍峰,陽愛民,劉吉財. 基于改進的C4.5算法的網(wǎng)絡(luò)流量分類方法[J]. 計算機工程與應(yīng)用,2012,48(5):71-74.

[6]譚駿. 基于自適應(yīng)BP神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)流量識別算法[J]. 電子科技大學(xué)學(xué)報, 2012, 41(4):580-585.

[7]SuM.UsingclusteringtoimprovethekNN-basedclassifiersforonlineanomalynetworktrafficidentification[J].JournalofNetworkandComputerApplications,2011,34(2): 722-730.

[8]DuM,ChenX,TanJ.AnovelP2PtrafficidentificationalgorithmbasedonBPSOandweightedkNN[J]．ChinaCommunications, 2011,8(2): 52-58.

[9]WuD,ChenX,ChenC,etal.Onaddressingtheimbalanceproblem:acorrelatedkNNapproachfornetworktrafficclassification[C]// 8thInternationalConferenceNetworkandSystemSecurity.Xi’an,China:Springer, 2014: 138-151.

[10]卜凡軍.kNN算法的改進及其在文本分類中的應(yīng)用[D].蘇州：江南大學(xué),2009.

[11]PengX,WenyuQ,HengQ,etal.DetectingDDoSattacksagainstdatacenterwithcorrelationanalysis[J].ComputerCommunications, 2015, 67: 66-74.

[責(zé)任編校： 張巖芳]

A Study on Network Traffic Classification Model of kNN Based on Network Resources

CHENG Shan，NIU Yan, LI Jun

(SchoolofComputerScience,HubeiUniversityofTechnology,Wuhan430068,China)

With the substantial growth of network users and network applications, the attack behavior which is hidden in thetraffic seriously affects the quality of network service. How to identify the networktraffic quickly and effectively is one of the keys in network security. According to similarities in the consumption of the network resources by the same sort of applications, and the differences in the consumption of the network resources by different applications, this paper proposes a networktraffic classification model of kNN based on network resources. The model can be used to select three attributes as its own feature from a variety of network resources, and it uses improved kNN algorithm to detecttraffic. It can also identify all kinds oftraffic in network as fast and effectively as possible, especially the attacktraffic. It can be used as an important basis for the enablement of network defense. The experimental results show that the improved kNN algorithm can improve the speed of the classification effectively while ensuring the recognition rate.

traffic classification；kNN；network resources；network attack and defense

2015-09-25

湖北省教育廳科學(xué)研究計劃資助項目( D2014403)

程珊(1992-)，女，湖北孝感人，湖北工業(yè)大學(xué)碩士研究生，研究方向為網(wǎng)絡(luò)安全

1003-4684(2016)04-0075-06

TP393

A