馬爾科夫模型在網絡流量分類中的應用與研究

趙 英,韓春昊

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

0 概述

網絡流量分類是網絡管理和網絡安全的基礎,是認識、管理、優化網絡資源的重要依據。目前的流量分類技術主要基于端口號查詢和深度包載荷檢測的分類技術。但是,隨著動態端口號和包載荷加密技術的應用的使用,2種分類技術已經無法滿足網絡管理的需求。因此,近年來關于網絡流量分類方法的研究主要是基于概率統計的機器學習算法研究。

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

在網絡流量分類研究中,文獻[1]已經證實,使用對流量數據構造馬爾科夫模型輔助分類,具有良好的準確性。但是怎樣選取流量數據構建馬爾科夫模型往往決定著流量分類結果的精度。而且以往的馬爾科夫模型分類算法只能識別已知流量,當未知流量混入測試集樣本中時,往往會嚴重影響分類的精度。

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

1 網絡流量分類方法

1.1 流量數據采集

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

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

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

根據馬爾科夫模型構造的需要,通過五元組和流的特性采集流量數據樣本。

1.2 馬爾科夫模型

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

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

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

(1)

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

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

除了狀態,通過統計和計算得出初始狀態概率向量π和轉換概率矩陣a:

(2)

(3)

其中,F0表示每種狀態作為初始狀態的個數,F表示狀態轉換i到j的個數。

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

1.3 流的相關性

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

2 基于馬爾科夫模型的半監督聚類

2.1 算法問題描述

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

在以往的網絡流量分類研究中,馬爾科夫模型多用于監督學習分類方法[6]。文獻[7]通過對流量數據構造可觀測馬爾科夫模型,通過似然分類器比較模型參數與已標記樣本進行分類,得到了95%以上的準確率,因此,應用馬爾科夫模型可以解決網絡流量分類問題。但是以往的研究都存在相同的問題,就是當分類器用于實際環境流量分類時,由于網絡技術的進步,新型流量層出不窮,因此無法對所有流量進行標記,基于馬爾科夫模型的分類器會將未知流量誤認為是已標記流量而造成錯誤分類。基于上述問題,主要解決的問題主要有以下兩方面:

1)構造基于馬爾科夫模型的半監督學習分類器,解決以往基于馬爾科夫模型分類器無法識別未知流量的問題。

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

2.2 相對熵

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

(4)

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

2.3 聚類算法

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

(5)

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

(6)

表示求總體樣本集中樣本i的平均距離,α是調節參數。m的值是所有KL距離小于Ri的樣本點個數。算法執行前先對部分樣本進行標記,算法描述如下:

1)設定聚類簇數為k,已標記樣本類型個數為c。若k

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

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

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

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

6)輸出集合C。

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

全部算法流程如下:

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

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

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

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

5)根據部分標記類型確定流量類型,根據分類結果構造分類器。

2.4 評價標準

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

(7)

(8)

(9)

(10)

3 實驗結果與分析

3.1 實驗環境及數據集

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

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

3.2 實驗結果

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

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

圖1 N和k參數對分類準確度的影響

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

圖2 基于馬爾科夫模型的分類器的準確性測試

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

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

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

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

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

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

2)通過流之間的相關性優化了馬爾科夫模型的構建。

3)使用半監督學習分類方法使基于馬爾科夫模型的分類器具有了識別未知流量類型的能力,在消除了未知流量干擾的情況下,基于馬爾科夫模型的分類器的流量類型識別能力明顯優于傳統的聚類分類器。

4 結束語

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

[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] 熊 剛,孟 姣,曹自剛,等.網絡流量分類研究進展與展望[J].集成技術,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].電子與信息學報,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,等.基于半監督的網絡流量分類識別算法[J].電子測量與儀器學報,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] 王 笑,李千目,戚 湧.一種基于馬爾科夫模型的網絡安全風險實時分析方法[J].計算機科學,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.