使用機器學習算法分類Ｐ２Ｐ流量的方法

摘 要:P2P應用的快速增長，帶來網絡擁塞等諸多問題，而傳統的基于端口與有效載荷的P2P流量分類方法存在著很多缺陷。以抽取獨立于端口、協議和有效載荷的P2P流的信息作為特征，用提出的基于ReliefF-CFS的方法選擇流的特征子集，研究使用機器學習算法對P2P流量進行分類的方法，也研究了利用流的前向N個報文的統計信息作為特征，分類P2P流量的方法。實驗結果顯示提出的方法取得了較好的分類準確率。

關鍵詞:對等網; 流量分類; 特征選擇; 機器學習

中圖分類號:TP18;TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3468-04

doi:10.3969/j.issn.1001-3695.2009.09.075

Method of P2P traffic classification using machine learning algorithms

LIU Yong-ding1， YANG Ai-min1，2， ZHOU Xu-sheng1， ZOU Hao-jie1

(1. College of Computation Communication， Hunan Industry University， Zhuzhou Hunan 412000， China; 2. School of Informatics， Guangdong University of Foreign Studies， Guangzhou 510006， China)

Abstract:As the rapid increase of P2P application， many network problems occur， while the traditional P2P traffic classification methods based on port， protocol and payload have many objections. Extract the attributes irrelevant to port， protocol and payload and use the methods of feature selection based on ReliefF-CFS to choose feature subset， this paper could classify P2P application flows with machine learning algorithms. At the same time， researched the P2P traffic classification with the statistical features of its N-forward information. The experiment shows that the method has good classification accuracy.

Key words:P2P(peer-to-peer); traffic classification; feature selection; machine learning

快速增長的P2P應用帶來網絡擁塞、帶寬資源濫用、版權保護等諸多問題，已經受到各個網絡運營商和網絡管理者的高度重視。P2P流量的識別已成為網絡研究者的熱點問題，對P2P流量和P2P行為進行深入的了解和分析，為監控與管理P2P提供技術支持。

傳統的基于靜態端口、協議和有效載荷的P2P流量的分類方法取得了較好的分類效果[1～3]，但這些方法對于采用動態端口和經過加密的P2P協議流無法正確分類。如Kazza、Gnutella等協議一方面使用Web的80端口號傳輸其流量;另一方面，其報文格式也模仿HTTP流量的格式[3]。而基于有效載荷的P2P流分類方法中，協議解碼需要協議知識和較完整的報文數據，且很難處理協議加密的網絡流量分類問題。

本文研究基于P2P流的應用類型的流量分類方法，以抽取獨立于端口、協議和有效載荷的P2P流的信息作為特征，用兩種特征選擇算法相結合來優選特征子集，研究使用機器學習算法對P2P流量進行分類的方法。這種分類方式可以避免使用端口、協議和有效載荷信息。

1 P2P流的定義及特征產生

1.1 流的定義及表示

本文把互聯網絡上P2P通信節點之間產生的流量，依據TCP/IP協議通信的五元組，即源IP、源Prot、目的IP、目的Prot及IP協議，定義成流，以超時120 s或雙向TCP報文標志位(FIN)為1作為流的結束，可以將P2P報文產生的流分成TCP(或UDP)流。用F={F1，F2，…，Fi，…，FM }表示流的集合，Fi={fi1，fi2，…，fij，…，fiN}表示第i條P2P流。其中M表示流的個數，N表示特征的個數，fij表示第i條流的第j個特征。設C={C1，C2，…， Ck，…，CK}表示流所屬的類別標簽集合。其中K表示類別的數量，Ck表示第k類流，如BT、Thunder等。

1.2 流特征的產生

本文研究的重要目標之一就是要產生獨立于端口、協議和有效載荷的流特征，以便于基于機器學習算法的流量分類器的構建、學習及其應用。依據1.1節流的五元組的定義，對P2P流的報文長度、到達時間等基本信息進行統計計算，產生流的特征。在本文的研究中，流的特征分為前向和后向雙向特征，把一條流的第一個報文中的源IP和源Port看做源節點，把報文中的目的IP和目的Port看做目的節點，前后向流的定義如下:

前向流:源節點→目的節點;后向流:目的節點→源節點

研究中，分別對雙向流的報文長度、到達時間進行統計分析，通過計算其均方差等方法，產生獨立于端口、協議和有效載荷的流特征。其中，均方差的計算如式(1)。

Fij=∑Pnuml=1a2l-∑Pnuml=1al2/Pnum/Pnum(1)

其中:al表示流中一個報文的長度或到達時間;Pnum表示一條流所包含的報文個數。

統計計算雙向報文的個數、長度等形成36個候選特征，如表1所示。流候選特征的詳細含義可參考文獻[4]。

表1 流的候選特征

P2P流的候選特征含義個數序號

packets(forward，backward)雙向報文個數21～2

Bytes(forward，backward)雙向報文的總字節數23～4

pakcetsLen(min，max，mean，avg)(forward，backward)雙向報文長度的統計特征量85～89～12

arriveTime(mean)(forward，backward)雙向報文到達時間213～14

less(〈100，500，1000，〉1000) (forward，backward)雙向報文長度的范圍區間815～1819～22

duration持續時間123

avgPktSecond平均包/s124

framFlag(forward，backward)雙向分片標志225～26

TCPFla(Urg、Ack、Psh、Rst、Syn)(forward，backward)雙向報文的TCP標志位1027～3132～36

2 基于ReliefF-CFS方法的特征選擇

在基于機器學習算法的P2P流量分類研究中，特征選擇也是本文研究的一個重要內容。特征選擇是指在不降低或能夠保證分類準確率的情況下，從候選特征集中去掉不相關或冗余特征，選擇出一個最優特征子集。根據評估函數與分類器的關系，特征選擇方法分成過濾器(filter)模式[5，6]和封裝器(wrapper)模式[7，8]兩種。其中，filter的評估函數與分類器無關;而wrapper采用分類器的分類錯誤率或正確率作為評價函數，選擇速度慢，需要交叉認證和大量的計算資源，選擇結果依賴于采用的分類算法。本文的研究采用filter模式，用基于ReliefF[9]和基于相關性的兩種相結合的方法來選擇特征子集。 其基本思想是:先用ReliefF方法對P2P流的候選特征進行初步選擇，然后對初步選擇的P2P流用基于相關的特征選擇(correlation-based feature selection，CFS)方法[10]進一步選擇，稱這種方法為ReliefF-CFS方法。

2.1 用基于ReliefF對P2P流特征進行初步選擇的方法

ReliefF是一種有監督特征選擇算法，是對Relief算法的一種改進，可用于多類分類。其基本思想是從每個不同類別的流樣本集合中選擇G個最近鄰樣本流，計算每一個樣本流特征的權重，從而得到各個特征與類別的相關性，選擇相關性大的特征作為流量分類的特征。

符號約定:Ft(∈F)表示一個訓練樣本流， Cl=class(Ft)表示流Ft所屬的類別。其中，Cl∈C。Ht表示由G個與流Ft具有相同類別，且與流Ft最近鄰的流構成的集合，Mi(k)表示由G個Ck類流(l≠k，k=1，2，…，K)，即與流Fi具有不相同類別，且與流Fi最近鄰的流構成的集合。用diff_hit(j)表示同類樣本流之間第j個屬性的差異，用diff_miss(j)表示異類流之間第j個屬性的差異。

基于ReliefF方法的P2P流量選擇算法如下:

輸入:已標注類別的訓練樣本流集合F，訓練樣本數目為Tr_num，迭代次數T

輸出:權值向量W=w1，w2…，wj，…，wN(j=1，2，…，N)。其中，N表示候選特個數

a) 初始化W置0，wj=0(1≤j≤N);

b)for t=1 to T， 計算同類屬性之間和異類之間屬性差異:

(a)隨機從F中選擇一實例流Ft;

(b)計算和找出Ht，Mt (k)集合;(k≠l=class(Ft)， Mt (k)的個數為K-1);

(c)for j=1 to N，按式(2)和(3)分別計算diff_hit(j)和diff_miss(j);

diff_hit(j)=∑Gg=1diff(j，ftj，hgj)/(T*G)

(2)

其中:hgj∈Ht，diff(j，fti，hgi)=0 if ftj=fgj1others

diff_miss(j)=∑Kk≠j=class(Ft)P(k)/1-P(class(Ft))

∑Gg=1diff(j，ftj，mkgj)/(T*G)(3)

其中:mkgj∈Mt(k)，P(k)表示第k類的分布概率。

diff(j，ftj，mkgj)=0 if ftj=mkgj1 others

(d)for j=1 to N，按式(4)進行權值W的更新:

wj=wj-diff_hit(j)+diff_miss(j)(4)

c)輸出W，算法結束。

通過ReliefF特征選擇算法得到按權值由大到小排序的權值向量W，設定一個閾值，大于閾值的特征被選為基于相關性的特征選擇方法的初始特征集。

2.2 用CFS方法選擇特征

由于ReliefF算法只考慮特征與類別的相關性，而沒有考慮特征之間的相關性。經ReliefF算法處理后，得到了初步的流的特征子集，在此基礎上通過基于相關性特征選擇方法[11]繼續選擇特征。相關性計算式如式(5)。

Rs=q*rcf/q+q*(q-1)*r-ff(5)

其中:s表示是含有 q個特征的特征子集，Rs是對特征子集s相關度的一個評估結果;rcf是類與特征之間的平均相關度;rff是特征與特征之間的平均相關度。當類與特征之間相關度越高、特征與特征之間的相關度越小時，特征子集s分類效果越好。在本文的研究中，采用BestFirst搜索策略結合正向搜索方向，搜索得到的較優的特征子集作為最后的特征選擇結果。

3 基于機器學習算法的P2P流量分類器

機器學習[11]是人工智能技術中的一個重要研究內容和方向。其主要研究是從樣本出發尋找規律，并利用規律對未知數據進行預測。機器學習的過程通常由兩部分組成，即分類模型的建立和分類。首先利用訓練數據建立分類模型;然后基于該模型產生一個分類器對未知數據集進行分類。本文介紹基于支持向量機(support vector machine，SVM)、C4.5決策樹以及K-最鄰近(K nearest neighbors，KNN)三種機器學習算法的P2P網絡流量分類器。

3.1 基于支持向量機(SVM)的P2P網絡流量分類器

支持向量機(SVM)[12]是由Boser等人[12]根據統計學習理論導出的結構風險最小化原則基礎上的機器學習算法。SVM是針對兩類分類問題而提出的，原理是用分類超平面將空間中兩類樣本點正確分隔，并使兩類樣本的間隔最大。假設樣本線性可分，設訓練樣本為

T=x1，y1，…，xi，yi，…，xn，yn∈X，YM (6)

其中:xi∈X=Rn，yi∈Y=+1，-1，i=1，…，M。問題線性可分，表明存在著超平面(w#8226;x)+b=0使得訓練點中的正類輸入和負類輸入分別位于該超平面的兩側，構造并求解變量a和b的最優化問題:

minw，b 1/2w 2

s.t. yi[(w#8226;xi)+b]≥1 (7)

求得最優解w，b;構造分劃超平面(w#8226;x)+b=0，由此構造決策函數

f(x)=sgn((w#8226;x)+b)(8)

對于線性不可分的情形，通過選擇好的非線性映射函數(核函數)將訓練樣本流映射到一個高維特征空間中，在高維特征空間中構造線性判別函數，來實現原空間中的非線性判別函數，保證機器有較好的推廣能力，同時使用核函數巧妙地解決了維數災難問題，其算法的復雜度與樣本維數無關。在原來的研究中[14]采用SVM算法對四種網絡流量進行分類，取得了較好的分類效果。本文仍使用SVM中一對一的多類分類方法，共構造K*(K-1)/2個二類分類器，結合SVM的C-SVC類型和徑向基核函數(RBF)，并搜索C-SVC的最優分類參數C和RBF的最優分類參數γ。

3.2 基于C4.5決策樹的P2P網絡流量分類器

決策樹模型(decision tree)是一種從無序、無規則的訓練樣本流中推出決策樹表示形式的分類方法，其每個分支代表一個測試輸出，而每個葉節點代表類別，C4.5算法[13]是Quinlan對ID3算法[14]的擴展，利用C4.5的算法來構建P2P網絡流量分類器，決策樹的構造步驟如下:

a)計算訓練樣本集F的總信息熵。樣本集F的總信息熵的計算式為

entropy(F)=-∑Mi=1pk logpk2(9)

其中:pk是F中屬于類別Ck的比例。

b)計算每個屬性的信息熵。假設屬性fj上共有v個不同的取值，通過屬性fj可將樣本集F劃分為v個子集，如果fj被選為決策屬性，則這些子集將對應該節點的不同分支。則根據fj劃分樣本的信息熵為

entropy(fj)=∑V∈values(fj)Fv/Fentropy(Fv)(10)

其中:values(fj)是屬性fj所有可能值的集合;Fv是F中屬性fj的值為v的子集。

c)計算該屬性的信息增益率。用屬性fj劃分樣本集F后所得的信息增益值為

gain(fj)=entropy(F)-entropy(fj) (11)

信息增益率為

gainRatio(fj)=gain(fj)/splitInfo(fj)(12)

其中:splitInfo(fj)=-∑V∈values(fj)Fv/Flog2Fv/F。

d)依據計算的每個屬性的信息增益率，把信息增益率最大的屬性作為分支節點，節點的每個可能取值對應一個子集，對樣本子集遞歸地執行b)c)，直到生成決策樹。

在生成決策樹后，采取剪枝技術來糾正過度擬合問題，即剪去樹中不能提高預測準確率的分支。通過設置每個葉節點的最少實例數(MNI)來適當控制樹的規模，設置置信因子(CF)確定樹的修剪程序。

3.3 基于KNN的P2P流量分類器

KNN算法是計算待分類流到每個樣本流的距離，得到與待分類流最近的k個樣本流，然后，尋找k個樣本流中占多數樣本流的類別，則待分類流就屬于該類別。在本文研究中，采用歐幾里德距離計算流Fi和Fl之間的距離dis(Fi，Fj)，計算式如式(13) 所示。

dis(Fi，Fl)=∑Nj=1(fij-flj)2 (13)

當給定一個類別未知的待分類的流Fx，基于KNN的P2P流量分類器搜索訓練樣本流空間，計算各訓練樣本流與Fx流的之間距離，找出最接近Fx流的k個訓練樣本流。這k個訓練樣本就是流Fx的最近鄰;然后，對k個訓練樣本流的類別進行投票，獲得占多數訓練樣本流的類別，即Fx流的類別。

4 實驗結果與分析

4.1 實驗數據的獲取與處理

在局域網內使用多臺PC機，每臺PC機運行單獨的P2P應用程序，通過路由器的端口鏡像獲取數據，獲取了八種P2P應用類型的原始數據，只獲取每個數據報文的前128 Byte，如表2所示。把獲取的原始網絡報文數據保存為DMP文件，合成流時依據報文的IP地址直接標注流的P2P應用類型。

表2 獲取的P2P數據集

應用類型數據集/GB應用類型數據集/GB

BT10.29100Bao3.12

Fasttrack5.83Poco2.30

eDonkey9.28Thunder4.31

Gnutella2.44FlashGet3.73

4.2 特征選擇實驗

從4.1節的數據中，抽取各類流共計2 000條流，作為特征選擇實驗，再用基于ReliefF算法的特征選擇實驗，得到流的各屬性(前20個)權值W如表3所示。

表3 基于ReliefF算法得到的屬性權值W

權值特征序號權值特征序號權值特征序號

0.058 72160.011 074320.001 2171

0.057 323100.009 77190.000 93130

0.048 699120.006 54550.000 85815

0.036 896110.005 292210.000 80627

0.034 58580.005 158310.000 7913

0.024 58670.004 265330.000 73929

0.018 377340.001 91522

在研究中，屬性wj(j=1，2，…，N)的閾值設置為0.001，則得到初步的特征子集的編號集為{6，10，12，11，8，7，34，32，9，5，21，31，33，22，1}。這些將作為基于CFS方法的初始特征子集。

在基于CFS方法的特征選擇實驗中，采用BestFirst搜索策略結合正向搜索方向，搜索得到的較優特征子集作為最后的特征選擇結果。最優特征子集的編號集合為{1，3， 5，6，7，8，9，10，11，12，21，22，31，32，33，34}。

4.3 分類實驗結果

在實驗中，從八種P2P協議中各抽取2 000條流形成樣本流集合F，使用SVM、C4.5和KNN三種機器學習算法，各分類器的參數分別如下:

a)基于SVM的P2P流量分類器參數:核函數是RBF函數，優化學習得到C=512，γ=2.0。

b)基于C4.5的P2P流量分類器參數:MNI=4，CF=0.2。

c)基于KNN的P2P流量分類器參數:k=5。

實驗中，使用5折交叉驗證方式進行分類器構建與測試。

首先對未進行特征選擇和已進行特征選擇的樣本集進行分類器的構建與測試，并用準確率、訓練與測試時間兩個標準進行評估，結果如表4所示。

表4 特征選擇與否的性能評估

學習算法

評估標準

準確率

未選擇已選擇

訓練與測試時間/s

未選擇已選擇

SVM88.672 387.857 4308176

C4.592.965 591.860 512963

KNN86.999 687.143 4415264

同時，研究了統計流的所有報文的特征形成的樣本集與只統計流的前50、100、150、200(指在進行流的特征統計時，只統計其中最先到達的個數，而不統計后續到達的報文)個報文的特征形成的樣本集，在未進行特征選擇和已進行特征選擇的情形下分類，結果如圖1和2所示。

從實驗結果可以看出:a)對三種機器學習算法的性能評估，C4.5算法的性能是最好的;b)結合兩種特征選擇方法選擇出的特征子集較好地保持分類準確率的同時，在很大程度上降低了分類器的訓練與測試時間;c)只統計流的前部分報文形成的樣本能夠達到很好的分類準確率，說明這些分類器可以用于在線流的實時分類。

5 結束語

本文研究了產生抽取獨立于端口、協議和有效載荷的P2P流的特征的方法，提出了基于ReliefF-CFS的特征選擇方法，研究了幾種基于機器學習算法的P2P流量分類分類器，實驗表明，分類器具有較好的分類效果。對統計流的前部分報文的情況下，分類器的準確率，這表明分類器可以用在實時流的分類應用中。

參考文獻:

[1]SEN S， WANG Jia. Analyzing peer-to-peer traffic across large networks[J].IEEE/ACM Trans on Networking，2004，12(2):219-232.

[2]GERBERAND A， HOULE J， NGUYEN H，et al. P2P the gorilla in the cable[C]//Proc of National Cable and Telecommunications Association(NCTA)， National Show.2003.

[3]SEN S， SPATSCKECK O，WANG D. Accurate， scalable in-network identification of P2P traffic using application signatures[C]//Proc of the 13th International World Wide Web Conference.2004: 512-521.

[4]鄧河， 陽愛民， 劉永定.一種基于SVM的P2P網絡流量分類方法[J].計算機工程與應用， 2008，44(14):122-126.

[5]LIU H， SETIONO R. A probabilistic approach to feature selection[C]//Proc of International Conference on Machine Learning.1996: 319-327.

[6]DAS S. Filters， wrappers and a boosting based hybrid for feature selection[C]//Proc of the 8th International Conference on Machine Learning.2001:74-81.

[7]YUAN Huang， TSENG S S， WU Gang-shan， et al.A two-phase feature selection met hod using both filter and wrapper[C]//Proc of IEEE International Conference on Systems，Man，and Cybernetics. 1999:132-136.

[8]KOHAVI R， JOHN G H. Wrappers for feature subset selection [J]. Artificial Intelligence Journal，1997，97(1-2):273-324.

[9]KONONENKO I.Estimation attributes: analysis and extensions of RELIEF[C]//Proc of European Conference on Machine Learning. 1994:171-182.

[10]HALL M A. Correlation-based feature selection for discrete and numeric class machine learning[C]//Proc of the 17th International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers， 2000:359-366.

[11]MITCHELL T M. 機器學習[M]. 曾華軍，張銀奎， 等譯.北京:機械工業出版社，2003.

[12]BOSER B E， GUYON I， VAPNIK V. A training algorithm for optimal margin classifiers[C]//Proc of the 5th Annual Workshop on Computa-tional Learning Theory. [S.l.]:ACM Press，1992:144-152.

[13]QUINLAN J R. C4.5: Programs for machine learning[M]. San Mateo， Calif:Morgan Kaufmann， 1993:17-42.

[14]QUINLANJ R. Induction of decision tree[J]. Machine Learning， 1986(1):81-106.