馬爾科夫模型在網(wǎng)絡(luò)流量分類中的應(yīng)用與研究

趙 英,韓春昊

(北京化工大學(xué) a.信息中心; b.信息科學(xué)與技術(shù)學(xué)院,北京 100029)

0 概述

網(wǎng)絡(luò)流量分類是網(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全的基礎(chǔ),是認(rèn)識、管理、優(yōu)化網(wǎng)絡(luò)資源的重要依據(jù)。目前的流量分類技術(shù)主要基于端口號查詢和深度包載荷檢測的分類技術(shù)。但是,隨著動態(tài)端口號和包載荷加密技術(shù)的應(yīng)用的使用,2種分類技術(shù)已經(jīng)無法滿足網(wǎng)絡(luò)管理的需求。因此,近年來關(guān)于網(wǎng)絡(luò)流量分類方法的研究主要是基于概率統(tǒng)計的機器學(xué)習(xí)算法研究。

機器學(xué)習(xí)在流量分類算法的運用中具有準(zhǔn)確高、分類快速的優(yōu)點,但其分類的好壞往往由訓(xùn)練集的選取決定。對于基于有監(jiān)督學(xué)習(xí)的分類,識別能力取決于訓(xùn)練集樣本中被標(biāo)記的類型,如果測試集中出現(xiàn)訓(xùn)練集中不包括的類型,那么會影響識別精度;而基于無監(jiān)督學(xué)習(xí)的分類器,它的分類精度完全依賴分類算法的好壞,但目前未出現(xiàn)能應(yīng)對一切情況的算法?；诎氡O(jiān)督學(xué)習(xí)的方法采用部分標(biāo)記樣本的方法構(gòu)造分類器,結(jié)合了前2種方法的優(yōu)點,提高了算法的準(zhǔn)確度。但是,半監(jiān)督算法中多數(shù)研究都采用如k均值這樣的需要多次迭代的聚類算法,這類算法往往缺乏穩(wěn)定的精度。

在網(wǎng)絡(luò)流量分類研究中,文獻[1]已經(jīng)證實,使用對流量數(shù)據(jù)構(gòu)造馬爾科夫模型輔助分類,具有良好的準(zhǔn)確性。但是怎樣選取流量數(shù)據(jù)構(gòu)建馬爾科夫模型往往決定著流量分類結(jié)果的精度。而且以往的馬爾科夫模型分類算法只能識別已知流量,當(dāng)未知流量混入測試集樣本中時,往往會嚴(yán)重影響分類的精度。

為此,本文提出一種基于網(wǎng)絡(luò)流量相關(guān)性的馬爾科夫模型,使用KL距離劃分相似度較高的樣本以形成類簇。由于以往的基于馬爾科夫模型的分類器無法識別未知的流量類型,因此引入密度計算用以估計聚類中心點。

1 網(wǎng)絡(luò)流量分類方法

1.1 流量數(shù)據(jù)采集

通常采集網(wǎng)絡(luò)流量數(shù)據(jù)通過五元組作為最基本流量的特征,即源端口、目的端口、源IP地址、目的IP地址、協(xié)議,將具有相同五元組的流量數(shù)據(jù)稱為流。具有五元組特征的流量數(shù)據(jù)通常傳輸在兩臺已接入網(wǎng)絡(luò)的主機之間,而主機之間的數(shù)據(jù)傳輸是有方向性的。因此流還具有一下特性:

特性1流是具有傳輸在主機之間的單向有序流量數(shù)據(jù)的部分集合。

特性2流量采集時,凡傳輸時間超過1 min的流應(yīng)當(dāng)以1 min為單位被劃分成不同的流。

根據(jù)馬爾科夫模型構(gòu)造的需要,通過五元組和流的特性采集流量數(shù)據(jù)樣本。

1.2 馬爾科夫模型

馬爾科夫模型是指由多條馬爾科夫鏈組成的模型,馬爾科夫鏈的定義是由若干狀態(tài)組成的隨機序列,這樣的序列中的狀態(tài)量只與其前一個狀態(tài)有關(guān),稱為無后效性,用公式表達如下:

P{Xn+1=in+1|Xn=in,Xn-1,…,X1=i1}=

P{Xn+1=in+1|Xn=in}

(1)

式(1)表示了馬爾科夫鏈的無后效性,決定第n項的只有第n-1項狀態(tài),與n-1之前的所有狀態(tài)無關(guān)。馬爾科夫模型是概率分布模型中所有可能的馬爾科夫鏈的集合。

網(wǎng)絡(luò)流量分類方法將具有相同應(yīng)用類型的數(shù)據(jù)流分為一類。按照馬爾科夫的定義和網(wǎng)絡(luò)流的特征,并根據(jù)文獻[2]中提出的前4個包已經(jīng)足夠以極高的準(zhǔn)確率分類流量的觀點,本文實驗構(gòu)造馬爾科夫模型通過提取前4個包的大小[3]。定義馬爾科夫模型中的狀態(tài)量通過定義一個連續(xù)、有向的數(shù)據(jù)包,和包的大小。在TCP流量中,MSS(最大報文長度)是經(jīng)常會發(fā)生變化的,如果直接以區(qū)間[0,MMSS]內(nèi)的每一個整數(shù)作為一種狀態(tài),會造成狀態(tài)過多而且很多狀態(tài)并未出現(xiàn),難以統(tǒng)計狀態(tài)轉(zhuǎn)移情況,因此,需要將狀態(tài)重新歸類。文獻[4]提出將包的大小歸類為4個區(qū)間,即[0,99],[100,299],[300,MMSS-1],[MMSS],因為這些區(qū)間作為特征向量可以很好的區(qū)分多類應(yīng)用。由于流的方向性,狀態(tài)還可以被分類正向的和反向的,即客戶端到服務(wù)器端流量歸為正方向,服務(wù)器端到客戶端為反方向,因此狀態(tài)可以被分為8種,前4種代表客戶端發(fā)往服務(wù)器的包,即{0,1,2,3},后4代表服務(wù)器發(fā)往客戶端的包,即{4,5,6,7}。例如0-1-2-3,是指客戶端先發(fā)送[0,99]Byte包,然后發(fā)送[100,299]Byte包,接著發(fā)送[300,MMSS]Byte包,最后發(fā)送[MMSS]包。

除了狀態(tài),通過統(tǒng)計和計算得出初始狀態(tài)概率向量π和轉(zhuǎn)換概率矩陣a:

(2)

(3)

其中,F0表示每種狀態(tài)作為初始狀態(tài)的個數(shù),F表示狀態(tài)轉(zhuǎn)換i到j(luò)的個數(shù)。

通過馬爾科夫模型轉(zhuǎn)化的網(wǎng)絡(luò)流量概率分布模型,其優(yōu)點在于通過計算每條馬爾科夫鏈在分布模型中的概率,將一維的特征值(數(shù)據(jù)包大小)轉(zhuǎn)化為多維特征參數(shù),用各種數(shù)據(jù)流在應(yīng)用類型中的分布情況來體現(xiàn)各類應(yīng)用流量數(shù)據(jù)的特性,不需要選取過多的特征類型就可以體現(xiàn)出網(wǎng)絡(luò)流量的分部特性。

1.3 流的相關(guān)性

在網(wǎng)絡(luò)中的數(shù)據(jù)傳輸是以流的形式存在的,而流之間并不是獨立存在的,是有相互關(guān)系的。根據(jù)文獻[5]提出流之間的相關(guān)性可以表明網(wǎng)絡(luò)流量的應(yīng)用類型,具有相同的{dstIP,dstPort,protoType}屬性的流屬于同一類型,并經(jīng)過試驗取得較好的分類效果。因此,本文將具有流相關(guān)性的未知網(wǎng)絡(luò)流量數(shù)據(jù)歸位同一類型,為其構(gòu)建馬爾科夫模型。

2 基于馬爾科夫模型的半監(jiān)督聚類

2.1 算法問題描述

半監(jiān)督學(xué)習(xí)流量分類方法結(jié)合了監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)流量分類方法的特點,通常是先利用聚類算法在樣本集中形成類簇,然后通過識別應(yīng)用類別類簇中部分已標(biāo)記樣本來決定類簇的應(yīng)用類型。半監(jiān)督學(xué)習(xí)分類方法中的聚類方法通常選取如K-means算法之類的需要多次迭代的方法,這些方法在樣本集較為容易劃分情況下迭代次數(shù)往往會小于分類樣本個數(shù),但是如果數(shù)據(jù)較難劃分時迭代次數(shù)往往是不可控的。因此,使用迭代聚類算法用于網(wǎng)絡(luò)流量分類往往穩(wěn)定性較差。

在以往的網(wǎng)絡(luò)流量分類研究中,馬爾科夫模型多用于監(jiān)督學(xué)習(xí)分類方法[6]。文獻[7]通過對流量數(shù)據(jù)構(gòu)造可觀測馬爾科夫模型,通過似然分類器比較模型參數(shù)與已標(biāo)記樣本進行分類,得到了95%以上的準(zhǔn)確率,因此,應(yīng)用馬爾科夫模型可以解決網(wǎng)絡(luò)流量分類問題。但是以往的研究都存在相同的問題,就是當(dāng)分類器用于實際環(huán)境流量分類時,由于網(wǎng)絡(luò)技術(shù)的進步,新型流量層出不窮,因此無法對所有流量進行標(biāo)記,基于馬爾科夫模型的分類器會將未知流量誤認(rèn)為是已標(biāo)記流量而造成錯誤分類?；谏鲜鰡栴},主要解決的問題主要有以下兩方面:

1)構(gòu)造基于馬爾科夫模型的半監(jiān)督學(xué)習(xí)分類器,解決以往基于馬爾科夫模型分類器無法識別未知流量的問題。

2)通過馬爾科夫模型輔助聚類,以解決半監(jiān)督分類中聚類算法穩(wěn)定性問題。

2.2 相對熵

KL距離(Kullback-Leibler Divergence)也叫相對熵(Relative Entropy),是評價相同事件空間中2個概率分布的差異程度的量[8]。設(shè)樣本X={x1,x2,…,xn},Y={y1,y2,…,yn},那么X相對于Y的相對熵,即KL距離為:

(4)

其中,p(xi)和q(yi)表示概率分布中樣本xi和yi發(fā)生的概率[9]。使用馬爾科夫模型進行聚類,需要將相似程度較高的樣本聚集形成類簇,這就需要對樣本相似度進行對比[10]。由于馬爾科夫模型是概率分布模型,因此使用KL距離比較相似度。

2.3 聚類算法

對一個給定的樣本集,如果其中某些樣本點分布比較集中,那么這些點最有可能屬于同一類型[11],那么這些分布集中的樣本中,處于分布最密集區(qū)域的點最能代表該類型特性[12-13],因此可以通過求樣本密度來選出這樣的樣本。設(shè)DKL(xi,xj)表示樣本i和樣本j之間的KL距離,那么樣本的密度可以定義為:

(5)

密度計算式(3)表示樣本距離周圍的m個樣本越近,則密度越大。大多數(shù)研究將m定義為所有樣本的個數(shù),這樣會使樣本密度受到較遠(yuǎn)距離樣本的影響。因此采用鄰域半徑估計m的值,鄰域半徑R的定義如下:

(6)

表示求總體樣本集中樣本i的平均距離,α是調(diào)節(jié)參數(shù)。m的值是所有KL距離小于Ri的樣本點個數(shù)。算法執(zhí)行前先對部分樣本進行標(biāo)記,算法描述如下:

1)設(shè)定聚類簇數(shù)為k,已標(biāo)記樣本類型個數(shù)為c。若k

2)初始化聚類中心點集合C={·}。

3)設(shè)在已標(biāo)記樣本集中共標(biāo)記L種應(yīng)用類型,分別將每個已標(biāo)記應(yīng)用類型子集看做獨立的的樣本集,計算L個樣本集中每個樣本的鄰域半徑Ri,根據(jù)Ri求得m,然后求出樣本密度dens(xi,xj),并從中選出密度最大的L個樣本加入中心點集合C中,并從集合S中刪除所有已標(biāo)記樣本。

4)若C中的樣本個數(shù)小于k,則從S中選出密度最大的一個樣本,加入C,并從S中將其刪除,并刪除其鄰域半徑內(nèi)的樣本。

5)迭代步驟4),直至C中的樣本個數(shù)等于k。

6)輸出集合C。

經(jīng)過上述步驟輸出的C即為類簇中心點集合,利用KL距離計算其他樣本和中心點的相似度形成類簇。

全部算法流程如下:

1)對所有樣本集中每個樣本按照流相關(guān)性劃分成為若干個子集,每個子集中包含N個流,對每個子集構(gòu)建馬爾科夫模型,將形成馬爾科夫模型的新樣本放入集合S中。

2)使用DPI工具從樣本集合S中取出部分樣本進行標(biāo)記。

3)通過密度計算獲取中心點,從樣本集合S中獲取k個中心點樣本構(gòu)成集合C,并從S中刪除C中的樣本。

4)對S中的樣本根據(jù)中心點C使用KL距離進行聚類。

5)根據(jù)部分標(biāo)記類型確定流量類型,根據(jù)分類結(jié)果構(gòu)造分類器。

2.4 評價標(biāo)準(zhǔn)

為了正確評價各個相似度測量算法的分類結(jié)果,選用Overall-accuracy和F-measure作為評價指標(biāo)[14-15]。用TP、TN、FP、FN分別表示真正例、真反例、假正例、假反例的樣本個數(shù),則上述評價標(biāo)注的描述為:

(7)

(8)

(9)

(10)

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

3.1 實驗環(huán)境及數(shù)據(jù)集

本文實驗通過TCP/IP網(wǎng)絡(luò)模型的分析對服務(wù)器端-客戶端之間的通訊產(chǎn)生的流量進行采集,采集的數(shù)據(jù)集來自于以下的真實環(huán)境下的鏈路數(shù)據(jù):BUCT數(shù)據(jù)集。BUCT數(shù)據(jù)集來自北京某大學(xué)網(wǎng)絡(luò)實驗室的節(jié)點路由上采集,可以獲得全校人員訪問網(wǎng)絡(luò)的流量數(shù)據(jù),共采集182 GB流量,約包含4 245 173個流。

為了準(zhǔn)確的評價算法的準(zhǔn)確性,本文實驗使用基于深度包載荷檢測工具(Ntop)和基于端口號采集工具(CoraReef),對數(shù)據(jù)集進行交叉驗證判斷其中的流量類型。對于DPI工具無法識別的加密流量,如https流量,使用端口號識別技術(shù)分類。使用手工檢測分類工具無法識別的流量類型(約100 000個流),而這些流量大多數(shù)是新型P2P流量。最后去除DPI和手工檢測均不能檢測的流,利用其中的約4 200 000個流用于實驗。經(jīng)過檢測這些流量中包含的的流量類型有Web、SSH、SSL、FTP、Mail、P2P、Games,共7種流量類型。每類隨機抽出10 000個流作為訓(xùn)練集樣本,訓(xùn)練集包含共70 000個流。

3.2 實驗結(jié)果

本文所提出算法中包含2個參數(shù),即聚類簇數(shù)k和用來構(gòu)建馬爾科夫模型的流數(shù)N,2個參數(shù)的取值不同會對實驗結(jié)果產(chǎn)生影響,因此,先測試在取不同k和N的情況下,分類結(jié)果的變化情況。

由圖1可知,當(dāng)N=10時,所構(gòu)建的馬爾科夫模型基本上無法體現(xiàn)各個應(yīng)用類型的特征,盡管k在增大,但是類型之間的區(qū)分度依然很差,所以準(zhǔn)確度變化很小;當(dāng)N=100時,分類的準(zhǔn)確率得到了較大提高,但是包含100個流的馬爾科夫模型依然不能完整的表現(xiàn)類型的特性,因此,k值的變化對準(zhǔn)確性的影響較小;當(dāng)N=300時,可以從圖中看出,馬爾科夫模型已經(jīng)能夠表現(xiàn)完整的類型特征,k值的變動對準(zhǔn)確性也產(chǎn)生了較大影響。

圖1 N和k參數(shù)對分類準(zhǔn)確度的影響

實驗取N={10,100,300},k={50,70,90,110,130,150,160}。圖2所示為分類的Overall-accuracy指標(biāo)。

圖2 基于馬爾科夫模型的分類器的準(zhǔn)確性測試

然后進行第2組實驗,即測試所提分類算法在測試集中存在未標(biāo)記的類型存在時的準(zhǔn)確性。選取部分Web、Mail、SSH和P2P流量進行標(biāo)記,然后將這些樣本和包含所有類型(包括FTP、SSL和Game流量)的部分未標(biāo)記樣本混合,訓(xùn)練半監(jiān)督分類器。使用剩下的流量作為測試集,測試訓(xùn)練好的分類器和文獻[2]提出的分類器的準(zhǔn)確度。設(shè)定N=300,k=160,分類結(jié)果如圖3所示。

圖3 與K-means分類算法比較結(jié)果的F-measure

對于文獻所使用方法,由于未標(biāo)記的類型的存在,且每種類型在樣本集中的含量并不均勻,因此不同類型流量收到了不同程度的干擾。而本文所提方法影響較小,每一類型的準(zhǔn)確率皆在93%以上,說明所提出的算法有識別未標(biāo)記的流量應(yīng)用類型的能力,實驗結(jié)果達到了預(yù)期目標(biāo)。

隨后,測試所提出的算法與傳統(tǒng)半監(jiān)督算法在網(wǎng)絡(luò)流量分類中的表現(xiàn)。選取基于半監(jiān)督學(xué)習(xí)的K-means聚類算法與其進行比較。選取能夠表明流之間的相關(guān)性的三元組{dstIP,dstPort,protoType}作為K-means分類所需特征值。通過密度計算選擇初始中心點,輔助K-means算法進行聚類。選取k=110和k=160作為2組被比較對象。

實驗結(jié)果表明,本文所提出的分類方法與基于K-means的半監(jiān)督分類算法相較,在準(zhǔn)確度上有很明顯的提升,使Overall-accuracy指標(biāo)達到約95%。能夠有效提高分類的準(zhǔn)確性主要由于以下因素:

1)利用馬爾科夫模型推導(dǎo)出類型的參數(shù)進行分類識別,使應(yīng)用類型的差異性得到了較好的反映。

2)通過流之間的相關(guān)性優(yōu)化了馬爾科夫模型的構(gòu)建。

3)使用半監(jiān)督學(xué)習(xí)分類方法使基于馬爾科夫模型的分類器具有了識別未知流量類型的能力,在消除了未知流量干擾的情況下,基于馬爾科夫模型的分類器的流量類型識別能力明顯優(yōu)于傳統(tǒng)的聚類分類器。

4 結(jié)束語

本文研究馬爾科夫模型在網(wǎng)絡(luò)流量分類中的應(yīng)用。使用密度計算估計聚類中心點，使馬爾科夫模型分類器具有識別未知流量的能力，解決了傳統(tǒng)基于半監(jiān)督學(xué)習(xí)的分類器依賴不穩(wěn)定聚類算法的問題。通過馬爾科夫模型提取特征值，反映類型之間的差異性，提升半監(jiān)督學(xué)習(xí)網(wǎng)絡(luò)流量分類方法的穩(wěn)定性，得到較高的精確度。實驗結(jié)果證明了該算法的有效性。

[1] MAIA J E B,HOLANDA F R.Internet traffic classification using a hidden markov model[C]//Proceedings of International Conference on Hybrid Intelligent Systems.Washington D.C.,USA:IEEE Press,2010:37-42.

[2] BERNAILLE L,TEIXEIRA R,SALAMATIAN K.Early application identification[C]//Proceedings of ACM Conference on Emerging Network Experiment and Technology.New York,USA:ACM Press,2006:1-12.

[3] FAHAD A,TARI Z,KHALIL I,et al.An optimal and stable feature selection approach for traffic classification based on multi-criterion fusion[J].Future Generation Computer Systems,2014,36(7):156-169.

[4] MüNZ G,DAI H,BRAUN L,et al.TCP traffic classification using markov models[J].Lecture Notes in Computer Science,2010,6003:127-140.

[5] 熊 剛,孟 姣,曹自剛,等.網(wǎng)絡(luò)流量分類研究進展與展望[J].集成技術(shù),2012,1(1):32-42.

[6] ZHANG Jun,XIANG Yang,WANG Yu,et al.Network traffic classification using correlation information[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(1):104-117.

[7] FINAMORE A,MELLIA M,MEO M.Mining unclassified traffic using automatic clustering Techniques[C]//Proceedings of International Conference on Traffic Monitoring and Analysis.Berlin,Germany:Springer-Verlag,2011:150-163.

[8] 畢安琪,王士同.基于Kullback-Leiber距離的遷移仿射聚類算法[J].電子與信息學(xué)報,2016,38(8):2076-2084.

[9] ZHANG Jun,XIANG Yang,WANG Yu,et al.A novel semi-supervised approach for network traffic clustering[C]//Proceedings of International Conference on Network and System Security.Washington D.C.,USA:IEEE Press,2011:169-175.

[10] FOREMSKI P.On different ways to classify internet traffic:a short review of selected publications[J].Iitis PI,2013,25(2):119-136.

[11] PALMIERI F,FIORE U,CASTIGLIONE A.A distributed approach to network anomaly detection based on independent component analysis[J].Concurrency & Computation Practice & Experience,2014,26(5):1113-1129.

[12] 周文剛,陳雷霆,Lubomir Bic,等.基于半監(jiān)督的網(wǎng)絡(luò)流量分類識別算法[J].電子測量與儀器學(xué)報,2014,28(4):381-386.

[13] DAINOTTI A,DONATO W D,Pescape A,et al.Classification of network traffic via packet-level hidden markov models[C]//Proceedings of IEEE Global Tele-communications Conference.Washington D.C.,USA:IEEE Press,1930:1-5.

[14] 王 笑,李千目,戚 湧.一種基于馬爾科夫模型的網(wǎng)絡(luò)安全風(fēng)險實時分析方法[J].計算機科學(xué),2016,43(s2):338-341.

[15] PARK J S,YOON S H,KIM M S.Performance improvement of payload signature-based traffic classification system using application traffic temporal locality[C]//Proceedings of Network Operations and Management Symposium.Washington D.C.,USA:IEEE Press,2013:1-6.