楊哲，李領(lǐng)治，紀(jì)其進(jìn)，朱艷琴

（1. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 江蘇 蘇州 215006; 2. 江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室, 江蘇 蘇州 215006）

1 引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，出現(xiàn)了文件共享、VoIP和流媒體等各種不同類型的應(yīng)用流量，它們對(duì) QoS的要求各不相同。為了實(shí)施有效的 QoS保障，網(wǎng)絡(luò)管理者需要了解網(wǎng)絡(luò)中各種類型的流量狀況，關(guān)注其流量特征，或者分析相應(yīng)的用戶行為和應(yīng)用發(fā)展趨勢(shì)，從而對(duì)網(wǎng)絡(luò)進(jìn)行擴(kuò)容改造。這些都必須對(duì)各種應(yīng)用流量進(jìn)行準(zhǔn)確的分類。此外，準(zhǔn)確的流量分類在網(wǎng)絡(luò)安全、流量計(jì)費(fèi)等領(lǐng)域，也具有極其重要的意義，一直是網(wǎng)絡(luò)測(cè)量領(lǐng)域的研究熱點(diǎn)。

最初的流量分類是根據(jù)IANA端口映射表，將符合某個(gè)特定端口號(hào)的流量識(shí)別為相應(yīng)的網(wǎng)絡(luò)應(yīng)用。其針對(duì)傳統(tǒng) Internet應(yīng)用和早期采用固定端口傳輸?shù)腜2P應(yīng)用，分類準(zhǔn)確性較高。隨著新型應(yīng)用采用隨機(jī)端口、端口跳變或端口偽裝等技術(shù)，該方法的分類準(zhǔn)確性已大大下降[1]。隨后Moore[1]、Sen[2]和Karagiannis[3]等分別提出載荷分析法，通過(guò)檢查數(shù)據(jù)分組的應(yīng)用層載荷，進(jìn)行應(yīng)用協(xié)議的特征串匹配。這些特征串稱為應(yīng)用層簽名（application signature）。該方法分類準(zhǔn)確性最高，為當(dāng)今大多數(shù)商用系統(tǒng)所采用。但是其必須針對(duì)每一種應(yīng)用構(gòu)建應(yīng)用層簽名，且需經(jīng)常更新以適應(yīng)應(yīng)用的不斷發(fā)展。雖然 Haffner[4]和 Ma[5]等提出了自動(dòng)構(gòu)建應(yīng)用層簽名的方法，但只能針對(duì)傳統(tǒng) Internet應(yīng)用。隨著應(yīng)用載荷加密和混淆技術(shù)的不斷發(fā)展，該方法的有效性正逐步下降。此外，也有研究者從其他的角度提出了不同的流量分類模型。Karagiannis等[6]提出基于傳輸層行為的盲分類器BLINC，通過(guò)主機(jī)在社會(huì)層、網(wǎng)絡(luò)層和應(yīng)用層3個(gè)層次的內(nèi)在行為特性，先識(shí)別主機(jī)參與的應(yīng)用，然后對(duì)其產(chǎn)生的流量進(jìn)行分類。Xu等[7]也采用這種辦法進(jìn)行流量分類，但其使用信息論和數(shù)據(jù)挖掘工具。這些方法不依賴于分組載荷，擴(kuò)展性好，但模型較為復(fù)雜。Dahmouni等[8]認(rèn)為不同應(yīng)用的 TCP控制分組也是統(tǒng)計(jì)可分的，并提出建立TCP標(biāo)記序列的馬爾可夫鏈作為分類器，該方法的有效性有待進(jìn)一步驗(yàn)證。

為了克服上述方法的不足，研究者開(kāi)始尋求新的方向。一般來(lái)說(shuō)，不同應(yīng)用產(chǎn)生的流量往往具有不同的統(tǒng)計(jì)特征，反映著各個(gè)應(yīng)用的內(nèi)在特性。例如，F(xiàn)TP流量的分組長(zhǎng)度較大且分組間隔時(shí)間較小。但是，網(wǎng)絡(luò)流量具有數(shù)據(jù)龐大、應(yīng)用特性高度動(dòng)態(tài)的特點(diǎn)。因此，利用機(jī)器學(xué)習(xí)方法，構(gòu)造基于流統(tǒng)計(jì)特征的網(wǎng)絡(luò)流量分類模型，是目前流量分類的研究熱點(diǎn)。

2 基于流統(tǒng)計(jì)特征的網(wǎng)絡(luò)流量分類

一般來(lái)說(shuō)，流量分類的基本處理單元，通常是一組具有相同五元組＜源IP、目的IP、源端口、目的端口、傳輸層協(xié)議＞的分組序列，即網(wǎng)絡(luò)流（flow）。在實(shí)際處理中，又進(jìn)一步劃分為單向流和雙向流。單向流是指嚴(yán)格按照五元組規(guī)則劃分的分組序列，雙向流是指同一網(wǎng)絡(luò)連接之內(nèi)的雙向分組序列，其包括正向流（client to server）和反向流（server to client）。通過(guò)提取單向流或雙向流的特征集合，將流抽象為由一組特征屬性構(gòu)成的特征向量，實(shí)現(xiàn)從網(wǎng)絡(luò)流量分類問(wèn)題到機(jī)器學(xué)習(xí)問(wèn)題的過(guò)渡。因此，利用機(jī)器學(xué)習(xí)方法處理流量分類問(wèn)題，需要解決的關(guān)鍵問(wèn)題，主要包括 3個(gè)方面：① 選擇合適的特征屬性構(gòu)建特征向量；② 選擇適當(dāng)?shù)臋C(jī)器學(xué)習(xí)算法構(gòu)建分類模型；③ 利用真實(shí)流量數(shù)據(jù)，對(duì)分類模型進(jìn)行評(píng)價(jià)。

目前，主要使用的特征屬性分為以下3類。

1) 數(shù)量相關(guān)特征，例如雙向分組/字節(jié)總數(shù)、正向分組/字節(jié)總數(shù)和反向分組/字節(jié)總數(shù)等。

2) 長(zhǎng)度相關(guān)特征，例如正向（反向）分組的平均長(zhǎng)度、方差和極值等。

3) 時(shí)間相關(guān)特征，例如流持續(xù)時(shí)間、正（反）向分組的平均到達(dá)間隔、方差和極值等。

不同網(wǎng)絡(luò)應(yīng)用在這些特征屬性上，一般存在較大差異。如P2P是雙向數(shù)據(jù)傳輸，而被動(dòng)FTP是單向數(shù)據(jù)傳輸。因此利用正（反）向分組數(shù)量的差異，可以有效區(qū)分這兩者[9]。選取最能夠反應(yīng)網(wǎng)絡(luò)應(yīng)用本質(zhì)區(qū)別的特征屬性，對(duì)于網(wǎng)絡(luò)流量分類非常重要。但特征屬性之間存在相關(guān)性和冗余性，不僅增加計(jì)算復(fù)雜度，并且會(huì)降低分類準(zhǔn)確性。Moore等[10]提出的一個(gè)248項(xiàng)特征屬性的集合，其中有100多項(xiàng)是通過(guò)傅里葉變換得來(lái)的。如果對(duì)每條網(wǎng)絡(luò)流都進(jìn)行傅里葉變換，則計(jì)算負(fù)擔(dān)過(guò)于沉重。較少的特征屬性可以有效降低分類模型的計(jì)算開(kāi)銷。Kim等[11]經(jīng)過(guò)對(duì)幾種常用的機(jī)器學(xué)習(xí)算法分析后認(rèn)為，使用5～10個(gè)特征屬性進(jìn)行流量分類較為合適。有些特征屬性值，必須等待流結(jié)束后才能獲得，例如流持續(xù)時(shí)間、分組總數(shù)等。這一限制會(huì)影響分類模型的實(shí)時(shí)性。Nguyen等[12]提出的多子流模型，擺脫了這一限制。但子流持續(xù)時(shí)間相對(duì)較短，其特征屬性容易受到網(wǎng)絡(luò)運(yùn)行狀態(tài)的影響而發(fā)生變化。此外，Bernaille[13,14]、Li[15]、Huang[16]等都是根據(jù)流最初幾個(gè)分組的大小和方向進(jìn)行分類。這些方法具備了一定的實(shí)時(shí)檢測(cè)能力，但其過(guò)分依賴于數(shù)據(jù)分組的到達(dá)順序。在實(shí)際網(wǎng)絡(luò)環(huán)境中由于非對(duì)稱路由、網(wǎng)絡(luò)擁塞等原因，分組通常無(wú)法保證順序到達(dá)。因此，其穩(wěn)定性得不到保證。

在獲取合適的流特征屬性集合之后，需要利用機(jī)器學(xué)習(xí)方法來(lái)構(gòu)建流量分類模型，并以此模型對(duì)未知類型的網(wǎng)絡(luò)流進(jìn)行分類。

Roughan等[17]用k-NN和線性判別式分析方法來(lái)處理流量分類問(wèn)題。Moore等[18]采用基于概率模型的樸素貝葉斯方法，雖然該方法的整體準(zhǔn)確率只有 65%左右，但采用基于關(guān)聯(lián)的快速過(guò)濾機(jī)制FCBF和核估計(jì)方法，對(duì)特征集進(jìn)行篩選之后，能將準(zhǔn)確率提高到90%以上。其他研究者還使用了貝葉斯人工神經(jīng)網(wǎng)絡(luò)[19]、支持向量機(jī)[20,21]、決策樹(shù)[22,23]等有監(jiān)督的機(jī)器學(xué)習(xí)方法，都取得了較好的分類準(zhǔn)確率。Williams等[24]分析了包括樸素貝葉斯、決策樹(shù)、貝葉斯網(wǎng)絡(luò)和樸素貝葉斯樹(shù)在內(nèi)的幾種有監(jiān)督的機(jī)器學(xué)習(xí)方法后發(fā)現(xiàn)，它們分類的精度大致相當(dāng)，但計(jì)算開(kāi)銷卻差別很大。之后Kim等人[11]綜合比較了7種常用的機(jī)器學(xué)習(xí)方法（樸素貝葉斯、帶核估計(jì)的樸素貝葉斯、貝葉斯網(wǎng)絡(luò)、C4.5決策樹(shù)、k-NN、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)）后發(fā)現(xiàn)，它們都能取得80%以上的分類準(zhǔn)確性。2009年，Li等人[39]分別用2003年、2004年和2006年的網(wǎng)絡(luò)流量數(shù)據(jù)，對(duì) C4.5決策樹(shù)和帶核估計(jì)的樸素貝葉斯的分類準(zhǔn)確性進(jìn)行了分析。結(jié)果表明，經(jīng) 2003年的流量數(shù)據(jù)訓(xùn)練得到的分類模型，在對(duì)2004年和2006年的流量數(shù)據(jù)進(jìn)行分類時(shí)，準(zhǔn)確率會(huì)從96%下降至88%。這表明由機(jī)器學(xué)習(xí)得到的分類模型具有時(shí)效性。2010年，Callado等[40]進(jìn)一步分析了載荷分析法和6種機(jī)器學(xué)習(xí)方法（NBTree、PART、J48、貝葉斯網(wǎng)絡(luò)、帶核估計(jì)的樸素貝葉斯和支持向量機(jī)），在校園網(wǎng)及商用網(wǎng)絡(luò)中對(duì)流量分類的準(zhǔn)確性。其結(jié)果表明在校園網(wǎng)環(huán)境的網(wǎng)絡(luò)條件比較均衡，應(yīng)用種類較少，機(jī)器學(xué)習(xí)算法能夠取得95%的準(zhǔn)確性。而在商用網(wǎng)絡(luò)中，網(wǎng)絡(luò)環(huán)境較為復(fù)雜，應(yīng)用種類較多，且存在一定的未知應(yīng)用，導(dǎo)致機(jī)器學(xué)習(xí)算法的分類準(zhǔn)確性均低于77%，貝葉斯網(wǎng)絡(luò)方法的準(zhǔn)確性甚至只有10%左右。

但是，有監(jiān)督的機(jī)器學(xué)習(xí)方法，都需要用預(yù)先分類好的樣本集來(lái)訓(xùn)練分類器。如果分類樣本較少，會(huì)出現(xiàn)過(guò)度擬合（overfitting），導(dǎo)致分類器的泛化能力弱。因此，有些研究者用無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法進(jìn)行流量分類。McGregor等[25]最早使用EM算法對(duì)網(wǎng)絡(luò)流量進(jìn)行聚類分析。Erman等[26,27]采用了K-Mean、DBSCAN和AutoClass算法來(lái)進(jìn)行流量聚類，其精度明顯優(yōu)于樸素貝葉斯。Yuan等[28]分析了端口、IP地址、字節(jié)數(shù)等特征的熵，用聚類方法進(jìn)行流量分類。之后Erman等[29]又提出了半監(jiān)督的學(xué)習(xí)方法，有效減少了預(yù)處理時(shí)間，并且能夠達(dá)到較高的分類精度。此類方法在聚類過(guò)程中無(wú)須使用訓(xùn)練樣本的類型，因而能夠識(shí)別部分類型尚未定義的新型網(wǎng)絡(luò)流量。然而在聚類結(jié)束后必須進(jìn)行手工標(biāo)記以實(shí)現(xiàn)網(wǎng)絡(luò)流量的分類，效率偏低。

從目前的研究成果來(lái)看，多數(shù)分類模型所采用的特征屬性，必須等待流結(jié)束后才能獲取。這大大影響了分類的實(shí)時(shí)性和實(shí)用性。雖然也有研究者僅僅根據(jù)流最初幾個(gè)分組的大小和方向進(jìn)行分類，使得對(duì)流量的分類有可能在流剛開(kāi)始的一段時(shí)間內(nèi)實(shí)現(xiàn)，但其過(guò)分依賴于數(shù)據(jù)分組的到達(dá)順序，穩(wěn)定性得不到保證。因此，本文對(duì)不同類別的應(yīng)用數(shù)據(jù)流，根據(jù)其在最初若干分組中進(jìn)行握手和參數(shù)協(xié)商的差異性，通過(guò)通信模式、載荷長(zhǎng)度以及信息熵等特征，采用基于最短劃分距離的方法構(gòu)建決策樹(shù)模型，對(duì)其進(jìn)行流量分類。通過(guò)在4個(gè)不同類型的網(wǎng)絡(luò)數(shù)據(jù)集上的離線分類實(shí)驗(yàn)，以及在校園網(wǎng)環(huán)境中在線流量分類實(shí)驗(yàn)，結(jié)果表明本方法對(duì)8種常見(jiàn)的網(wǎng)絡(luò)應(yīng)用，能夠在分類準(zhǔn)確性和系統(tǒng)開(kāi)銷上取得較好的綜合效果。

3 雙向流特征屬性

本文進(jìn)行分類處理的對(duì)象是雙向流，因其不僅包含通信雙方在2個(gè)方向上獨(dú)立的網(wǎng)絡(luò)流特征，還包含2個(gè)單向流之間的關(guān)聯(lián)特征，具有更強(qiáng)的特征描述能力。由于 UDP協(xié)議是面向無(wú)連接的，與大多數(shù)分類模型一樣，本文暫不考慮。對(duì)于TCP協(xié)議，由于雙向TCP流是一個(gè)雙向有序的分組序列，為統(tǒng)一對(duì)方向問(wèn)題的討論，本文以雙向TCP流的SYN分組的方向?yàn)樵摿鞯恼较?。在?jì)算流特征屬性時(shí)，忽略狀態(tài)控制分組（如SYN、RST和FIN等）。因?yàn)檫@些分組的應(yīng)用層載荷長(zhǎng)度一般為零，對(duì)流量分類的作用不大。

在流量分類問(wèn)題研究中，分類的類別可以有不同的定義。如將一組功能相似的應(yīng)用定義為同一類，也可深入識(shí)別確切的應(yīng)用甚至軟件版本。本文將分類的類別定義為具體的應(yīng)用協(xié)議，具體包括 HTTP、HTTPS、FTP、SMTP、POP3、IMAP、BitTorrent、eDonkey在內(nèi)的 8個(gè)典型 Internet應(yīng)用協(xié)議。

對(duì)于任何一種網(wǎng)絡(luò)應(yīng)用，通信雙方會(huì)按協(xié)議狀態(tài)機(jī)，在某個(gè)時(shí)刻i發(fā)出包含不同載荷數(shù)據(jù)的分組Xi。隨著時(shí)間的推移，通信雙方之間一次完整的流會(huì)話過(guò)程，可以視為一個(gè)離散平穩(wěn)信源，用隨機(jī)變量序列 X＝X1X2X3X4…Xi…表示。待分類的網(wǎng)絡(luò)流對(duì)象X可以由若干特征屬性描述，設(shè)計(jì)通用的分類模型時(shí)應(yīng)避免選擇基于特定協(xié)議的特征。對(duì)于不同的應(yīng)用，2個(gè)方向上的流特性迥異，還應(yīng)考慮分別選取2個(gè)方向上的特征屬性。出于實(shí)時(shí)性方面的考慮，所選取的特征屬性，應(yīng)該能通過(guò)流早期的若干分組計(jì)算得出。

一般來(lái)說(shuō)，在消息序列X的前N個(gè)消息中，通信雙方需要進(jìn)行應(yīng)用層握手，并協(xié)商各種參數(shù)。根據(jù)不同應(yīng)用協(xié)議的約定，需要協(xié)商和傳遞的參數(shù)個(gè)數(shù)和類型不同，會(huì)導(dǎo)致其最初若干消息分組的方向、載荷長(zhǎng)度以及載荷中每個(gè)字節(jié)取值的不確定性和差異性，其最能反映出應(yīng)用協(xié)議的本質(zhì)特征。因此本文使用以下特征，用于刻畫(huà)前N個(gè)消息分組的這種差異性。

3.1 通信模式

通信模式（pattern），用于描述雙向流中前 N個(gè)分組的方向，用形如b1b2b3…bN形式的二進(jìn)制整數(shù)表示，其中，bi（i≤N）用于表示第i個(gè)分組的方向。本文規(guī)定如果第i個(gè)分組的方向與流量的正向同向，則bi取值為1，否則為0。例如N＝4時(shí)，則Pattern的取值為0000～1111。

如圖1所示的FTP應(yīng)用，在TCP握手之后登錄過(guò)程中，第1個(gè)分組方向是由服務(wù)器端發(fā)往客戶端的“220”消息(b1=0)，之后3個(gè)分組的方向交替出現(xiàn)。因此，F(xiàn)TP應(yīng)用的通信模式一般為0101。而HTTP的第一個(gè)分組是由客戶端發(fā)往服務(wù)器端的Get請(qǐng)求(b1=1)，之后3個(gè)分組的方向受請(qǐng)求和響應(yīng)報(bào)文的長(zhǎng)度影響，沒(méi)有固定的模式，因此HTTP的通信模式可能為1000～1111。

一般來(lái)說(shuō)，不同應(yīng)用協(xié)議的通信模式是統(tǒng)計(jì)可分的。本文對(duì)WIDE數(shù)據(jù)集（詳見(jiàn)5.1節(jié)）中的FTP、HTTP、BitTorrent和eDonkey應(yīng)用的通信模式進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)其通信模式有明顯的差異，如表1所示（單位為%）。FTP和HTTP是典型的C/S應(yīng)用，有92.84%的FTP流的通信模式為0101，有74.39%的HTTP流，其通信模式為 1000。而 BitTorrent和eDonkey這2種典型的P2P應(yīng)用，其通信模式主要為1010和1001。

3.2 載荷長(zhǎng)度

雙向流消息序列中，任一時(shí)刻發(fā)出的消息Xi，其載荷長(zhǎng)度（payload size）因協(xié)議和傳輸?shù)膮?shù)而異。因此，本文用Si表示消息分組Xi的應(yīng)用層載荷大小。與其他研究者使用分組大小[12,13,15～18,22]特征不同的是，本文使用的是以字節(jié)為單位的應(yīng)用層載荷大小。因?yàn)榉纸M中可能含有IP或TCP的可選數(shù)據(jù)，使用分組大小不能準(zhǔn)確描述各種應(yīng)用協(xié)議的應(yīng)用層握手或信令長(zhǎng)度的特征。

3.3 分組信息熵

對(duì)任一消息Xi，其載荷內(nèi)容受協(xié)議和傳輸參數(shù)而異，其每個(gè)字節(jié)都取且可取遍字符集K＝{k, 0≤k≤255}。本文將分組Xi載荷數(shù)據(jù)中每個(gè)字節(jié)的取值當(dāng)作一組隨機(jī)事件，即Xi＝{xk, 0≤k≤255}，用xk表示在分組Xi的載荷數(shù)據(jù)中，值為k的字節(jié)出現(xiàn)的次數(shù)，則Xi的信息熵為

其中，

對(duì)于一個(gè)完整的雙向流消息序列X，其前N個(gè)分組的信息熵構(gòu)成了一個(gè)熵序列H（ X1）,H（ X2）, …, H（ XN），反映了每個(gè)分組Xi各自所含信息量的多少。但雙向流是一個(gè)雙向有序的分組序列，而由于H（ Xi）的非負(fù)性（H（ Xi）≥0），分組信息熵只能刻畫(huà)信息量的多少，不能描述分組的方向。因此→本文定義分組Xi的有向熵（directed entropy）（ Xi），用于增強(qiáng)對(duì)方向性的描述， （ Xi）可定義為

其中，sgn(x)為符號(hào)函數(shù)，bi為Pattern值，表示分組Xi的方向，其取值為1或0。若Xi與流的正向同向，則bi=1，sgn（bi-0.5）=1， （ Xi）=H（ Xi）≥0，表示此時(shí)雙向流按正向傳遞了大小為H（ Xi）的信息。若→Xi與流的正向相反，則bi=0，sgn（bi-0.5）=-1，H（ Xi）=-H（ Xi）≤0，表示雙向流按負(fù)向傳遞了大小為H（ Xi）的信息?！藭r(shí)，雙向流前N個(gè)分組的有向熵構(gòu)成的熵序列（ X1）, （ X2）,…,（ XN），從微觀上能有效刻畫(huà)雙向流的信息傳遞大小和方向。此外，為了從整體上描述雙向流的信→息流動(dòng)情況，本文定義了雙向流X的有向信息熵H（ X）：

3.4 雙向流特征屬性集

因此本文使用表2所示的特征屬性作為雙向流的分類依據(jù)。雖然端口號(hào)已經(jīng)不能作為主要的分類特征，但它仍是一個(gè)重要特征，尤其是對(duì)一些傳統(tǒng)的Internet應(yīng)用進(jìn)行分類時(shí)[2]。因此，本文仍使用端口號(hào)（port）作為描述雙向流的特征之一。

表2 雙向流的特征屬性

4 基于最短劃分距離的決策樹(shù)

本文上述特征屬性，采用決策樹(shù)算法對(duì)真實(shí)網(wǎng)絡(luò)流量進(jìn)行分類。決策樹(shù)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，能從一組無(wú)序的已知樣本中，歸納出以倒掛的樹(shù)狀結(jié)構(gòu)表示的分類知識(shí)。決策樹(shù)的每個(gè)內(nèi)部節(jié)點(diǎn)，代表對(duì)一個(gè)或多個(gè)特征屬性的取值進(jìn)行測(cè)試比較，并根據(jù)比較結(jié)果確定該節(jié)點(diǎn)的分枝，每個(gè)葉節(jié)點(diǎn)就代表一個(gè)類別。決策樹(shù)算法應(yīng)用簡(jiǎn)便，只要訓(xùn)練樣本集能夠用屬性向量和類別表示，就能使用該算法。在使用決策樹(shù)模型對(duì)類型未知的樣本進(jìn)行分類時(shí)，只需從根節(jié)點(diǎn)開(kāi)始逐步對(duì)該樣本的特征屬性進(jìn)行測(cè)試，并沿著相應(yīng)的分支直到某個(gè)葉節(jié)點(diǎn)為止，此時(shí)葉節(jié)點(diǎn)所代表的類型即為該樣本的類型。與其他機(jī)器學(xué)習(xí)算法相比，決策樹(shù)算法相對(duì)簡(jiǎn)單，具有較高的數(shù)據(jù)處理效率，適合進(jìn)行流量的實(shí)時(shí)分類[22,23]。

4.1 基于信息熵的決策樹(shù)

在決策樹(shù)創(chuàng)建過(guò)程中，如何確定內(nèi)部節(jié)點(diǎn)的分枝是最為關(guān)鍵的問(wèn)題。對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行分枝，對(duì)應(yīng)著當(dāng)前樣本集的一個(gè)劃分。采用不同的劃分標(biāo)準(zhǔn)得到的決策樹(shù)各不相同。在網(wǎng)絡(luò)流量分類問(wèn)題中，T為已知類別的流量樣本數(shù)據(jù)集，包含m種類別{c1, c2,…,cm}，每個(gè)流樣本的特征屬性集為A={a1,a2,…,ak}。根據(jù)樣本類別可得T的一個(gè)理想劃分T={t1, t2,…,tm}，其中，樣本子集ti中的樣本都屬于類別ci，則該理想劃分的信息熵為

如果以選擇特征屬性ai（1≤i≤k）作為測(cè)試條件α，根據(jù)該屬性的不同取值，可得T的另一個(gè)劃分T′=｛t1′, t2′,…,tr′｝ ，則該劃分的信息熵為

其中，

式(9)表示劃分T′中屬于子集t′i的樣本，在理想劃分中屬于子集tj的概率。因此，選擇ai對(duì)T進(jìn)行劃分所獲得的信息熵增益為

ID3算法中[30]，根據(jù)每個(gè)測(cè)試條件的信息熵增益，選擇增益最大的測(cè)試來(lái)確定當(dāng)前節(jié)點(diǎn)的分枝。對(duì)大多數(shù)應(yīng)用，信息熵增益法都能取得較好的結(jié)果。但是其最大的缺陷是偏愛(ài)輸出分枝較多的測(cè)試條件，導(dǎo)致決策樹(shù)規(guī)模過(guò)大，泛化能力弱。隨后在改進(jìn)的C4.5算法中[31]，引入測(cè)試條件α帶來(lái)的分割信息熵。

用信息增益與分割信息熵的比值，即信息增益率作為選擇測(cè)試條件的依據(jù)。

但是采用增益率標(biāo)準(zhǔn)，當(dāng)劃分產(chǎn)生的分割信息量很小時(shí)，增益率的值不穩(wěn)定。一種情況是，如果劃分后只有一個(gè)子集中有樣本，會(huì)導(dǎo)致分母——分割信息熵為零。另一種情況是，對(duì)于某些劃分，雖然產(chǎn)生的信息熵增益很小，但由于分割信息熵也很小，其信息增益率很大。

4.2 基于劃分距離的決策樹(shù)

為克服C4.5算法存在的上述2個(gè)缺點(diǎn)，本文用Mantaras范式距離來(lái)定義2個(gè)劃分間的距離[32]。在各屬性中選擇與理想劃分距離最近的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試條件，用最短距離劃分的辦法來(lái)構(gòu)建決策樹(shù)。

根據(jù)樣本集T的理想劃分T={t1,t2,…,tm}和以屬性ai作為測(cè)試條件α所得的劃分T′=｛t1′, t2′,…,tr′ ｝ ，則劃分T′對(duì)于理想劃分T的條件熵為

其中，

式(14)表示一個(gè)樣本在劃分T′中屬于子集t′i，而在理想劃分T中屬于子集tj的概率。同理，理想劃分T對(duì)于劃分T′的條件熵為

劃分T′與理想劃分T的聯(lián)合熵為

因此，劃分T′與理想劃分T的Mantaras范式距離為

按照最短距離標(biāo)準(zhǔn)，首先計(jì)算每個(gè)可能的特征屬性所對(duì)應(yīng)的劃分與理想劃分之間的距離，然后選擇距離最小的劃分所對(duì)應(yīng)的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性。最短距離法能有效克服信息增益率方法的缺陷，算法的穩(wěn)定性好，其構(gòu)建的決策樹(shù)規(guī)模更小，分類速度更快。

4.3 屬性離散化和剪枝

如表2所示，本文使用的流特征中，除端口和通信模式為離散屬性外，其余均為連續(xù)屬性。如果直接處理連續(xù)屬性，一旦被選為決策樹(shù)內(nèi)部節(jié)點(diǎn)的測(cè)試條件，則會(huì)產(chǎn)生很多分枝，造成決策樹(shù)結(jié)構(gòu)龐大。因此，必須對(duì)連續(xù)屬性進(jìn)行離散化。本文采用劃分距離評(píng)估連續(xù)區(qū)間的分割點(diǎn)，即選擇劃分后的2個(gè)樣本子集間Mantaras距離最小的分割點(diǎn)作為最佳分割點(diǎn)[32]，以最短描述長(zhǎng)度準(zhǔn)則（MDLP，minimum description length principle）作為離散化過(guò)程的結(jié)束條件。

在無(wú)沖突的情況下，算法生成的決策樹(shù)將與訓(xùn)練集完全一致。但由于訓(xùn)練集里的實(shí)例可能包含了噪聲點(diǎn)和孤立點(diǎn)，訓(xùn)練中生成的樹(shù)會(huì)嘗試擬合每一個(gè)異常的細(xì)節(jié)。這種過(guò)度擬合的結(jié)果，是對(duì)訓(xùn)練集分類的效果很好，但用它來(lái)對(duì)新的數(shù)據(jù)集進(jìn)行分類時(shí)可能并不理想。因此有必要對(duì)生成的初始決策樹(shù)進(jìn)行剪枝，以得到更一般的分類規(guī)則。因此，本文使用PEP（pessimistic error pruning）算法[31]對(duì)生成的初始決策樹(shù)進(jìn)行剪枝，進(jìn)而得到最終的決策樹(shù)。由于PEP算法在剪枝過(guò)程中，對(duì)每棵子樹(shù)最多只檢查一次，且不需要額外的剪枝數(shù)據(jù)集，因此其速度較快，適用于樣本數(shù)較多的數(shù)據(jù)集。

此外，在初始特征屬性集中，屬性之間存在的相關(guān)性和冗余性，不僅增加計(jì)算復(fù)雜度，并且很可能會(huì)降低分類的準(zhǔn)確性。一般可以利用特征過(guò)濾算法，發(fā)現(xiàn)屬性之間的關(guān)聯(lián)性，從而濾除冗余屬性。但是特征過(guò)濾算法可能會(huì)利用局部信息過(guò)濾特征屬性，造成局部最優(yōu)性問(wèn)題。而且在決策樹(shù)本身的構(gòu)造中，實(shí)際上已經(jīng)包含了屬性選擇過(guò)程，所以本文沒(méi)有采用特征過(guò)濾算法。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文方法在分類準(zhǔn)確性和實(shí)時(shí)性方面的性能，實(shí)現(xiàn)了一個(gè)原型系統(tǒng)，并部署在蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院局域網(wǎng)邊緣的路由交換機(jī)上，其拓?fù)浣Y(jié)構(gòu)如圖2所示。

圖2 實(shí)驗(yàn)環(huán)境拓?fù)浣Y(jié)構(gòu)

該網(wǎng)絡(luò)擁有約1 200臺(tái)主機(jī)，其邊緣為Cisco 4507路由交換機(jī)，通過(guò)吉比特每秒鏈路與蘇州大學(xué)網(wǎng)絡(luò)中心核心路由器相連。在該邊緣路由交換機(jī)上通過(guò)端口鏡像，將其出口的全部流量鏡像到本文實(shí)驗(yàn)用的Dell PowerEdge 1950服務(wù)器上。服務(wù)器配置為1路4核至強(qiáng)CPU，8GB內(nèi)存，146GB硬盤(pán)，運(yùn)行Windows 7操作系統(tǒng)。該服務(wù)器主要用于：①用真實(shí)網(wǎng)絡(luò)的離線流量數(shù)據(jù)，訓(xùn)練基于最短劃分距離的決策樹(shù)模型，并與其他分類算法的準(zhǔn)確性進(jìn)行對(duì)比；② 將經(jīng)過(guò)訓(xùn)練得到的分類模型，用于在線流量分類，以驗(yàn)證其實(shí)時(shí)分類的能力。

5.2 網(wǎng)絡(luò)流量數(shù)據(jù)與工具

本文首先使用4個(gè)真實(shí)網(wǎng)絡(luò)流量數(shù)據(jù)，對(duì)決策樹(shù)分類模型進(jìn)行離線訓(xùn)練和驗(yàn)證。數(shù)據(jù)的采集點(diǎn)包括局域網(wǎng)和廣域網(wǎng)，時(shí)間跨度從2003年到2011年，分別是 LBNL[33]、UNIBS[34]、WIDE[35]和 SUDA 數(shù)據(jù)集。

LBNL數(shù)據(jù)集來(lái)自勞倫斯伯克利國(guó)家實(shí)驗(yàn)室（lawrence Berkeley national laboratory）局域網(wǎng)出口的Trace數(shù)據(jù)集，本文選用2003年1月12日的數(shù)據(jù)。UNIBS數(shù)據(jù)集來(lái)自University of Brescia辦公網(wǎng)，約有1 000個(gè)左右的用戶，通過(guò)吉比特以太網(wǎng)鏈路接入Internet。采集時(shí)間為 2007年某一周的白天。WIDE數(shù)據(jù)集來(lái)自 WIDE互聯(lián)網(wǎng)測(cè)量與分析項(xiàng)目采集的骨干網(wǎng)鏈路的 Trace數(shù)據(jù)。本文采用的是 F點(diǎn)獲取的2009年10月1日20:00～21:00的數(shù)據(jù)。其中，LBNL和UNIBS原始Trace中包含全部分組載荷，WIDE原始Trace中，每個(gè)分組包含40byte的載荷內(nèi)容，三者對(duì)涉及用戶隱私的信息經(jīng)過(guò)匿名處理。最后的SUDA數(shù)據(jù)集，采集自5.1節(jié)所述的蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院的局域網(wǎng)出口，采集時(shí)間為2011年4月13日至15日，數(shù)據(jù)集中每個(gè)分組包含40byte的載荷。

對(duì)上述4個(gè)離線數(shù)據(jù)集，首先使用Tcptrace軟件[36]提取出雙向均發(fā)送一個(gè)以上分組的雙向 TCP流，并計(jì)算表2所述雙向流的特征屬性。本文分類的對(duì)象為HTTP、HTTPS、FTP、SMTP、POP3、IMAP、BitTorrent、eDonkey等 8種應(yīng)用協(xié)議。首先使用Analyzer載荷分析軟件[38]，對(duì)離線數(shù)據(jù)集中這8種應(yīng)用的雙向TCP流，通過(guò)其應(yīng)用層簽名進(jìn)行標(biāo)記。經(jīng)過(guò)流特征屬性提取和標(biāo)記后的數(shù)據(jù)集中，各種應(yīng)用協(xié)議雙向流的數(shù)量如表3所示。其中，LBNL數(shù)據(jù)集中沒(méi)有BitTorrent和eDonkey的流量，UNIBS數(shù)據(jù)集中沒(méi)有IMAP4的流量。

表3 數(shù)據(jù)集中各種協(xié)議的樣本數(shù)

本文的決策樹(shù)分類模型及其剪枝算法，是基于Weka平臺(tái)[37]實(shí)現(xiàn)的。用于與本文方法進(jìn)行對(duì)比的常用分類算法有k-NN（k-nearest neighbors）、SVM（support vector machines）、NBK（na?ve bayes kernel estimation）和 C4.5決策樹(shù)算法，這些算法也都基于Weka平臺(tái)實(shí)現(xiàn)。

5.3 評(píng)價(jià)指標(biāo)

本文采用如下準(zhǔn)確性指標(biāo)對(duì)分類模型的分類能力進(jìn)行評(píng)估。在訓(xùn)練數(shù)據(jù)集中的流樣本，分別屬于m種類別。對(duì)類別i，令TPi表示其全部樣本中被正確分類的樣本數(shù)，F(xiàn)Ni表示被誤判為其他類別的樣本數(shù)，F(xiàn)Pi表示其他類別的樣本中被誤判為類別i的樣本數(shù)，則定義如下分類準(zhǔn)確性指標(biāo)。

1) 類別i的召回率（recall）

2) 類別i的準(zhǔn)確率（precision）

3) 類別i的F值（F-measure）

4) 整體準(zhǔn)確率（overall accuracy）

上述準(zhǔn)確性指標(biāo)中，單個(gè)類別的召回率和準(zhǔn)確率能夠反映分類模型針對(duì)某個(gè)類型的分類能力，而F值對(duì)模型分類能力的綜合評(píng)價(jià)能力更好，因?yàn)镕值是召回率和準(zhǔn)確率的調(diào)和平均值。此外，分類模型的整體準(zhǔn)確率，能從整體上反映正確分類的樣本數(shù)占總樣本數(shù)的比例。因此它和F值指標(biāo)的應(yīng)用最廣，幾乎為所有研究所采納[2]。另外，本文還使用訓(xùn)練時(shí)間、分類時(shí)間、吞吐率等指標(biāo)來(lái)評(píng)估分類模型的開(kāi)銷。

本文使用每個(gè)流的機(jī)器處理時(shí)間來(lái)評(píng)價(jià)分類模型的實(shí)時(shí)分類性能。流處理時(shí)間是指從每個(gè)流的第一個(gè)分組進(jìn)入機(jī)器開(kāi)始，然后計(jì)算流特征屬性，最后由分類模型對(duì)流所屬應(yīng)用類型進(jìn)行標(biāo)記的全部時(shí)間，其包括3個(gè)部分。

1) 流緩存時(shí)間tcache。由于本文用表2所定義的流特征屬性，需要處理每個(gè)TCP流中前N個(gè)載荷長(zhǎng)度不為零的分組。因此tcache時(shí)間是指每個(gè)流的第一個(gè)分組進(jìn)入機(jī)器開(kāi)始，到前N個(gè)載荷長(zhǎng)度不為零的分組全部到達(dá)的時(shí)間。

2) 屬性計(jì)算時(shí)間tattributes，是指按表2的定義計(jì)算TCP流的特征屬性的時(shí)間。

3) 分類時(shí)間 tclassification，是指分類模型依據(jù)每個(gè)流的特征屬性，對(duì)流所屬應(yīng)用類型進(jìn)行標(biāo)記的時(shí)間。

這3部分機(jī)器處理時(shí)間，都與分類模型需要對(duì)每個(gè)流進(jìn)行處理的分組個(gè)數(shù)N有關(guān)。N越大，則3部分時(shí)間都會(huì)延長(zhǎng)，導(dǎo)致分類模型對(duì)流所屬應(yīng)用類型進(jìn)行標(biāo)記的時(shí)機(jī)越遲，其實(shí)時(shí)性變差；而N越小，雖然有利于提高分類實(shí)時(shí)性，但會(huì)導(dǎo)致分類的準(zhǔn)確性降低。因此，本文用這3個(gè)指標(biāo)來(lái)評(píng)價(jià)模型的實(shí)時(shí)分類能力，同時(shí)考慮準(zhǔn)確性指標(biāo)，以獲得最佳的分類效果。

5.4 離線訓(xùn)練和驗(yàn)證

本文首先在4個(gè)離線數(shù)據(jù)集上，進(jìn)行了3個(gè)實(shí)驗(yàn)，主要對(duì)本文提出的基于最短劃分距離的決策樹(shù)模型的分類準(zhǔn)確性進(jìn)行評(píng)價(jià)。其中，第1個(gè)實(shí)驗(yàn)用于確定本文模型中的待定參數(shù) N，即每個(gè)流需要分析的分組數(shù)量。第2個(gè)實(shí)驗(yàn)在確定N取值的條件下，對(duì)比各種機(jī)器學(xué)習(xí)方法的分類整體準(zhǔn)確性。第3個(gè)實(shí)驗(yàn)用于分析抽樣率對(duì)單個(gè)類別分類準(zhǔn)確性的影響。

實(shí)驗(yàn)1 確定待定參數(shù)N。

為了確定每個(gè)流需要分析的分組個(gè)數(shù)N，首先將4個(gè)離線數(shù)據(jù)集，用隨機(jī)抽樣的方法分別分成相同大小的A、B 2個(gè)子集，子集中每類應(yīng)用協(xié)議的流樣本的比例與原數(shù)據(jù)集保持一致，然后分別用不同的N取值，在子集A上進(jìn)行訓(xùn)練以獲得決策樹(shù)分類模型，在子集B上對(duì)模型進(jìn)行驗(yàn)證。重復(fù)實(shí)驗(yàn)10次，每次重新對(duì)離線數(shù)據(jù)集進(jìn)行隨機(jī)抽樣，獲得10組不同的A、B子集。綜合考慮10次實(shí)驗(yàn)中分類模型的平均整體準(zhǔn)確率和系統(tǒng)開(kāi)銷等指標(biāo)后，確定最佳的N取值。

圖3 不同N取值下的整體準(zhǔn)確率

圖3給出了不同N取值（N＝2, 4, 6, 8, 10）條件下，分類模型在4個(gè)離線數(shù)據(jù)集上的整體準(zhǔn)確率指標(biāo)?？梢钥闯?，每個(gè)流如果只分析2個(gè)分組的信息，因?yàn)楂@取的信息不充分，導(dǎo)致整體準(zhǔn)確率較低。分類模型的整體準(zhǔn)確率隨著N值的增加而提高。當(dāng)N取6時(shí)，即每個(gè)流分析的分組數(shù)量為6個(gè)時(shí)，分類模型的整體準(zhǔn)確率達(dá)到最大值，之后則略有下降。因?yàn)榇蠖鄶?shù)協(xié)議的應(yīng)用層握手過(guò)程，一般都在4～6個(gè)分組中完成，少數(shù)會(huì)持續(xù)6～8個(gè)分組，之后便開(kāi)始傳輸數(shù)據(jù)。進(jìn)行數(shù)據(jù)傳輸時(shí)，受數(shù)據(jù)內(nèi)容和長(zhǎng)度的影響，其分組的方向、長(zhǎng)度和信息熵等特征不穩(wěn)定，導(dǎo)致分類器的整體準(zhǔn)確率有所下降。

表4給出了不同N取值條件下，分類模型在4個(gè)數(shù)據(jù)集上的訓(xùn)練和分類時(shí)間，以及吞吐率指標(biāo)。決策樹(shù)分類模型的建模過(guò)程相對(duì)復(fù)雜，因此導(dǎo)致其訓(xùn)練時(shí)間較長(zhǎng)。但分類時(shí)只需根據(jù)流的特征屬性在樹(shù)狀模型中，自上而下的進(jìn)行簡(jiǎn)單比較，因此分類時(shí)間要明顯少于訓(xùn)練時(shí)間，適合于實(shí)時(shí)的流量分類問(wèn)題。但是隨著N的增加，需要計(jì)算和進(jìn)行測(cè)試的特征屬性較多，訓(xùn)練和分類時(shí)間都大大增加，吞吐率也逐漸下降。

因此，從分類的整體準(zhǔn)確率考慮，N＝6是最佳的取值。此時(shí)在4個(gè)數(shù)據(jù)集上的分類準(zhǔn)確性分別為94.0%（LBNL），96.7%（UNIBS），92.6%（WIDE）和95.8%（SUDA），平均吞吐率保持在5.1×104流/秒。

實(shí)驗(yàn)2 不同分類算法的準(zhǔn)確性對(duì)比。

在第1個(gè)實(shí)驗(yàn)得到的10組A、B子集上，實(shí)驗(yàn)2分別用不同的機(jī)器學(xué)習(xí)算法，用本文使用的特征集進(jìn)行訓(xùn)練和分類，以對(duì)比本文的基于最短劃分距離的決策樹(shù)（DBDT, distance based decision tree）算法和其他機(jī)器學(xué)習(xí)算法，在分類準(zhǔn)確性和分類性能的差異。

圖4給出了在4個(gè)離線數(shù)據(jù)集上，每種算法的分類整體準(zhǔn)確率指標(biāo)?？梢钥吹剑琸-NN和NBK算法的準(zhǔn)確率較低，本文的DBDT算法和SVM、C4.5算法的整體準(zhǔn)確率大致相當(dāng)，在樣本數(shù)量較少的 UNIBS數(shù)據(jù)集上，略低于SVM算法。這是因?yàn)镾VM算法是專門(mén)針對(duì)小樣本情況下的機(jī)器學(xué)習(xí)算法，而決策樹(shù)算法無(wú)論樣本規(guī)模如何，都能取得較好的分類準(zhǔn)確性。

圖4 5種算法的分類整體準(zhǔn)確率比較

表5給出了在N＝6的條件下，5種分類算法在4個(gè)數(shù)據(jù)集上訓(xùn)練和分類時(shí)間以及吞吐率指標(biāo)。

表4 不同N取值下的算法開(kāi)銷

表5 5種算法的性能對(duì)比

從訓(xùn)練時(shí)間來(lái)看，決策樹(shù)算法（DBDT和C4.5）并不是最優(yōu)的。但是在分類時(shí)間和吞吐率上，決策樹(shù)算法僅需根據(jù)樣本的特征屬性，在決策樹(shù)上自上而下的依次比較，處理相對(duì)簡(jiǎn)單，因此具有較高的數(shù)據(jù)處理效率。與 C4.5決策樹(shù)算法相比，DBDT采用最短劃分距離構(gòu)建決策樹(shù)，其克服了C4.5算法的缺陷，構(gòu)建的決策樹(shù)規(guī)模更小，因此其訓(xùn)練和分類速度更快。

實(shí)驗(yàn)3 抽樣率對(duì)準(zhǔn)確率的影響。

在第一個(gè)實(shí)驗(yàn)得到的10組A、B子集上，實(shí)驗(yàn)3主要分析不同抽樣率對(duì)每個(gè)類別的分類準(zhǔn)確率的影響。首先隨機(jī)抽取A子集中每類應(yīng)用協(xié)議10%的流樣本，進(jìn)行訓(xùn)練以獲得分類模型，然后在子集B上對(duì)模型進(jìn)行驗(yàn)證。隨后抽樣率按 10%遞增直至100%，重復(fù)實(shí)驗(yàn)10次，以獲得不同抽樣率下單個(gè)類別的平均分類準(zhǔn)確性指標(biāo)。圖5～圖8分別給出了在LBNL、UNIBS、WIDE和SUDA數(shù)據(jù)集的A子集上，用不同抽樣率進(jìn)行訓(xùn)練后，用B子集進(jìn)行驗(yàn)證得到F值的10次實(shí)驗(yàn)平均值。

如圖5所示，在LBNL數(shù)據(jù)集上，每個(gè)類別的F值隨著抽樣率的遞增而增加。但在原始數(shù)據(jù)集中，由于POP3和IMAP4協(xié)議樣本數(shù)量較少，分別為1 172和7 677個(gè)流。在對(duì)A子集進(jìn)行小樣本抽樣（10%～50%）后，樣本數(shù)量嚴(yán)重不足，導(dǎo)致分類器訓(xùn)練不充分，對(duì)某些特殊樣本過(guò)度訓(xùn)練。因此F值較低，且波動(dòng)較大。而HTTP、SMTP和FTP的樣本數(shù)量相對(duì)較多，雖然在小樣本抽樣條件下的F值較低，但仍高于POP3和IMAP4。

圖5 LBNL數(shù)據(jù)集上的F值

如圖6所示，在UNIBS數(shù)據(jù)集上，每個(gè)類別的F值隨著抽樣率變化的趨勢(shì)與LBNL相似，即對(duì)eDonkey協(xié)議流的分類F值較低，HTTPS、SMTP和POP3的分類F值較高。

圖6 UNIBS數(shù)據(jù)集上的F值

如圖7所示，在WIDE數(shù)據(jù)集上，每個(gè)類別的F值的變化趨勢(shì)與前兩者相似，但整體的波動(dòng)性要小。這是由于WIDE數(shù)據(jù)集中，每個(gè)類別的樣本絕對(duì)數(shù)量要大于前兩者，小樣本抽樣后得到的樣本數(shù)量仍然較多。雖然對(duì)分類器的訓(xùn)練仍然不充分，導(dǎo)致F值較低，但在特殊樣本上進(jìn)行過(guò)度訓(xùn)練的概率較低，因此F值的波動(dòng)比較平穩(wěn)。

圖7 WIDE數(shù)據(jù)集上的F值

如圖8所示，在SUDA數(shù)據(jù)集上，除IMAP4和FTP外，其他類別的F值變化趨勢(shì)與WIDE相似。這是由于SUDA數(shù)據(jù)集中，IMAP4和FTP類別的樣本較少，而其他類別的樣本較多。

圖8 SUDA數(shù)據(jù)集上的F值

因此，針對(duì)單個(gè)類別的應(yīng)用流量，為了取得較好的分類準(zhǔn)確性，其用于訓(xùn)練的流樣本的絕對(duì)數(shù)量必須保持一定的規(guī)模，才能避免分類模型對(duì)噪聲點(diǎn)和孤立點(diǎn)的過(guò)度擬合，導(dǎo)致分類準(zhǔn)確性的波動(dòng)較大。

5.5 在線流量分類

除驗(yàn)證本文模型的準(zhǔn)確性指標(biāo)外，在5.1節(jié)所述的環(huán)境中，還進(jìn)行了流量的在線分類實(shí)驗(yàn)，以驗(yàn)證其實(shí)時(shí)分類能力。首先在實(shí)驗(yàn)服務(wù)器上，用Tcptrace[36]捕獲鏡像流量中的TCP流，然后計(jì)算表2所定義的流特征屬性。利用離線實(shí)驗(yàn)中，經(jīng)由SUDA離線流量數(shù)據(jù)訓(xùn)練得到的分類模型進(jìn)行流量的在線分類，用流處理時(shí)間指標(biāo)來(lái)評(píng)價(jià)其實(shí)時(shí)分類的性能。同時(shí)在實(shí)驗(yàn)服務(wù)器上，還部署了Analyzer軟件，用于事后檢驗(yàn)分類的準(zhǔn)確性。

考慮到內(nèi)存開(kāi)銷和計(jì)算復(fù)雜度問(wèn)題，實(shí)驗(yàn)中沒(méi)有捕獲每個(gè)流的所有分組。根據(jù)圖3和表4所示的離線實(shí)驗(yàn)結(jié)果，從準(zhǔn)確性角度考慮，N＝6時(shí)是最佳結(jié)果。但是，在線流量分類對(duì)時(shí)間的要求更為關(guān)鍵。根據(jù)5.2節(jié)對(duì)機(jī)器處理時(shí)間與N取值的關(guān)系分析，在同時(shí)保持較高準(zhǔn)確性和分類性能的前提下，N＝4也是較好的結(jié)果。因此，在線分類實(shí)驗(yàn)一共持續(xù) 6天時(shí)間，從2011年4月17日到22日。其中前3天的實(shí)驗(yàn)，N的取值為6，即捕獲了每個(gè)雙向TCP流的前6個(gè)載荷不為零的分組；后3天的實(shí)驗(yàn)中，N取4，用于驗(yàn)證N取值與模型實(shí)時(shí)分類能力的影響。另外，考慮到實(shí)際網(wǎng)絡(luò)中存在一定比例的短流（有效分組數(shù)少于N個(gè)）以及其他TCP錯(cuò)誤，因此實(shí)驗(yàn)中對(duì)每個(gè)流的處理設(shè)置一個(gè)超時(shí)時(shí)間ttimeout＝10s。如果在 ttimeout時(shí)間內(nèi)，一個(gè) TCP流的有效分組數(shù)量少于 N，則不進(jìn)行處理，以節(jié)約內(nèi)存的開(kāi)銷。

本文首先分析了不同的N取值，對(duì)在線分類的整體準(zhǔn)確性的影響，如圖9所示。實(shí)驗(yàn)每6個(gè)小時(shí)統(tǒng)計(jì)一次在線分類的整體準(zhǔn)確率指標(biāo)，在N分別取6和4的各自3天實(shí)驗(yàn)中，一共取得12組數(shù)據(jù)。通過(guò)對(duì)比可以看到 N＝6的 3天實(shí)驗(yàn)中，分類的整體準(zhǔn)確率平均為 93%。而 N＝4時(shí)，分類的整體準(zhǔn)確率會(huì)有所降低，但仍能取得平均90%的整體準(zhǔn)確率。

然后本文分析了在不同N取值條件下，機(jī)器的處理時(shí)間和內(nèi)存消耗的情況，如圖10～圖13所示。圖10所示為在不同N取值條件下，流緩存時(shí)間tcache的累計(jì)分布情況。當(dāng)N＝6時(shí)，有52%的流緩存時(shí)間小于100ms，99%的流緩存時(shí)間小于1 000ms。而當(dāng)N＝4時(shí)，則74%的流緩存時(shí)間小于100ms，99%的流緩存時(shí)間小于500ms。這說(shuō)明較小的N取值，可以大大減少流緩存的時(shí)間。

圖9 不同N取值下的在線分類整體準(zhǔn)確率

圖10 不同N取值下的tcache累計(jì)分布

圖11所示為在不同N取值條件下，屬性計(jì)算時(shí)間tattributes的累計(jì)分布情況。當(dāng)N＝6時(shí)，有57%的流屬性計(jì)算時(shí)間小于 100μs，99%的流屬性計(jì)算時(shí)間小于700μs。而當(dāng)N＝4時(shí)，則83%的流屬性計(jì)算時(shí)間小于100μs，99%的流屬性計(jì)算時(shí)間小于300μs。較小的N取值也可以有效減少流緩存的時(shí)間。

圖11 不同N取值下的tattributes累計(jì)分布

圖12所示為在不同N取值條件下，流分類時(shí)間tclassification的累計(jì)分布情況。當(dāng)N＝6時(shí)，有83%的流分類時(shí)間小于 10μs，99%的流分類時(shí)間小于50μs。而當(dāng)N＝4時(shí)，則89%的流分類時(shí)間小于10μs，99%的流分類時(shí)間小于30μs。較小的N取值，雖然可以減少流分類時(shí)間，但程度不如對(duì)流緩存時(shí)間和屬性計(jì)算時(shí)間提高的那樣明顯。

圖12 不同N取值下的tclassification累計(jì)分布

圖13所示為在不同N取值下，系統(tǒng)的內(nèi)存開(kāi)銷情況。實(shí)驗(yàn)每6個(gè)小時(shí)統(tǒng)計(jì)一次內(nèi)存的平均利用率指標(biāo)，在N分別取6和4的3天實(shí)驗(yàn)中，一共取得12組數(shù)據(jù)?？梢钥吹絅＝6的3天實(shí)驗(yàn)中，實(shí)驗(yàn)服務(wù)器的內(nèi)存利用率平均為71%。而N＝4時(shí)，內(nèi)存利用率平均為32%。這主要是由于較小的N取值可以大大降低流緩存的時(shí)間，使得每個(gè)流得以盡快的處理，釋放大量的內(nèi)存空間。

圖13 不同N取值下的內(nèi)存開(kāi)銷

對(duì)流量進(jìn)行在線分類時(shí)，實(shí)時(shí)性是最主要的要求。因此，綜合考慮準(zhǔn)確性、處理時(shí)間和內(nèi)存開(kāi)銷等因素，N取4是比較理想的結(jié)果。此時(shí)本文提出的基于最短劃分距離的決策樹(shù)分類方法，可以取得90%的分類準(zhǔn)確性，99%的流處理時(shí)間小于 500ms（流緩存時(shí)間）+300μs（屬性計(jì)算時(shí)間）+30μs（分類時(shí)間），內(nèi)存利用率平均為32%。

6 結(jié)束語(yǔ)

利用機(jī)器學(xué)習(xí)方法，構(gòu)造基于流統(tǒng)計(jì)特征的網(wǎng)絡(luò)流量分類模型，是流量分類問(wèn)題的研究熱點(diǎn)。目前大多數(shù)的分類模型必須等待流結(jié)束后，才能對(duì)其進(jìn)行分類，實(shí)時(shí)性較差。一些模型從實(shí)時(shí)性的角度出發(fā)，僅僅根據(jù)流最初若干分組的方向和大小進(jìn)行分類，導(dǎo)致其過(guò)度依賴分組的到達(dá)順序，穩(wěn)定性較差。本文除了考慮流最初幾個(gè)分組的方向、載荷大小特征，主要根據(jù)分組的信息熵等特征，采用最短劃分距離的方法構(gòu)建決策樹(shù)分類模型，對(duì)其進(jìn)行分類。根據(jù)在真實(shí)網(wǎng)絡(luò) Trace數(shù)據(jù)集上，以及在線流量分類的實(shí)驗(yàn)結(jié)果表明，本文方法對(duì)8種常見(jiàn)的網(wǎng)絡(luò)應(yīng)用能夠取得較好的分類準(zhǔn)確性和綜合分類性能。

[1] MOORE A W, PAPAGIANNAKI K. Toward the accurate identification of network applications[A]. Proc of PAM’05[C]. Boston, USA,2005.41-54.

[2] SEN S, SPATSCHECK O, WANG D. Accurate, scalable in-network identification of P2P traffic using application signatures[A]. Proc of WWW’04[C]. New York, USA, 2004.512-521.

[3] KARAGIANNIS T, BROIDO A, BROWNLEE N, et al. Is P2P dying or just hiding[A]. Proc. of GLOBECOM’04[C]. Dallas, USA, 2004.

[4] HAFFNER P, SEN S, SPATSCHECK O, et al. ACAS: automated construction of application signatures[A]. Proc of SIGCOMM Mine-Net’05[C]. New York, USA, 2005. 197-202.

[5] MA J, LEVCHENKO K, KREBICH C, et al. Unexpected means of protocol inference[A]. Proc of IMC’06[C]. Rio de Janeiro, Brazil,2006.313-326.

[6] KARAGIANNIS T, PAPAGIANNAKI K, FALOUTSOS M. BLINC:multilevel traffic classification in the dark[J]. SIGCOMM Computer Communication Review, 2005, 35(4): 229-240.

[7] XU K, ZHANG Z, BHATTACHARYYA S. Profiling Internet backbone traffic: behavior models and applications[A]. Proc of SIGCOMM’05[C]. Philadelphia, USA, 2005.

[8] DAHMOUNI H, VATON S, ROSSE D. A markovian signature-based approach to IP traffic classification[A]. Proc of SIGCOMM Mine-Net’07[C]. New York, USA, 2007.29-34.

[9] ERMAN J, ARLITT M, MAHANTI A. Traffic classification using clustering algorithms[A]. Proc of SIGCOMM MineNet’06[C]. New York, USA, 2006. 281-286.

[10] MOORE A W, ZUEV D, CROGAN M. Discriminators for use in flow-based classification[R]. RR-05-13, Queen Mary University of London, 2005.

[11] KIM H, CLAFFY K, FOMENKOV M, et al. Internet traffic classification demystified: myths, caveats, and the best practices[A]. Proc of ACM CoNEXT’08[C]. New York, USA, 2008.1-12.

[12] NGUYEN T, ARMITAGE G. Training on multiple sub-flows to optimize the use of Machine Learning classifiers in real-world IP networks[A]. Proc of IEEE LCN’06[C]. Tampa, 2006.

[13] BERNAILLE L, TEIXEIRA R., AKODKENOU I. Traffic classification on the fly[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(2): 23-26.

[14] BERNAILLE L, TEIXEIRA R, SALAMATIAN K. Early application identification[A]. Proc of CoNEXT’06[C]. Lisboa, Portugal, 2006. 1-12.

[15] LI J, ZHANG S, LU Y, et al. Real-time P2P traffic identification[A].Proc of GLOBECOM’08[C]. Dallas, USA, 2008. 1-5.

[16] HUANG N, JAI G, CHAO H. Early identification traffic with application characteristics[A]. Proc of ICC’08[C]. Beijing, China, 2008.5788-5792.

[17] ROUGHAN M, SEN S, SPATSCHECK O, et al. Class-of-service mapping for QoS: a statistical signature-based approach to ip traffic classification[A]. Proc of IMC’04[C]. New York, USA, 2004. 135-148.

[18] MOORE A W, ZUEV D. Internet traffic classification using bayesian techniques[A]. Proc of SIGMETRICS’05[C]. Alberta, Canada, 2005.50-60.

[19] AULD T, MOORE A, GULL S F. Bayesian neural networks for Internet traffic classification[J]. IEEE Transactions on Neural Networks,2007, 18(1): 223-239.

[20] 徐鵬, 劉瓊, 林森. 基于支持向量機(jī)的Internet流量分類研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(3): 407-414.XU P, LIU Q, LIN S. Internet traffic classification using support vector machine[J].Journal of Computer Research and Development, 2009,46(3): 407-414.

[21] WANG R, LIU Y, YANG Y. A new method for P2P traffic identification based on support vector machine[A]. Proc of AIML’06[C]. Sharm El Sheikh, Egypt, 2006. 967-974.

[22] 徐鵬, 林森. 基于C4.5決策樹(shù)的流量分類方法[J]. 軟件學(xué)報(bào), 2009,20(10): 2692-2704.XU P, LIN S. Internet traffic classification using C4.5 decision tree[J].Journal of Software, 2009, 20(10): 2692-2704.

[23] 王宇, 余順爭(zhēng). 網(wǎng)絡(luò)流量的決策樹(shù)分類[J]. 小型微型計(jì)算機(jī)系統(tǒng),2009, 30(11): 2150-2156.WANG Y, YU S Z. Internet traffic classification based on decision tree[J]. Journal of Chinese Computer Systems, 2009, 30(11): 2150-2156.

[24] WILLIAMS N, ZANDER S, ARMITAGES G. A preliminary performance comparison of five machine learning algorithms for practical IP traffic flow classification[J]. SIGCOMM Computer Communication Review, 2006, 36(5): 5-16.

[25] MCGREGOR A, HALL M, LORIER P, et al. Flow clustering using machine learning techniques[A]. Proc of PAM’04[C]. Antibes Juanles- Pins, France, 2004. 205-214.

[26] ERMAN J, ARLITT M, MAHANTI A. Traffic classification using clustering algorithms[A]. Proc of SIGCOMM MineNet’06[C]. Pisa,Italy, 2006. 281-286.

[27] ERMAN J., ARLITT M., MAHANTI A. Internet traffic identification using machine learning[A]. Proc of GLOBECOM’06[C]. San Francisco, USA, 2006.

[28] YUAN J, LI Z, YUAN R. Information entropy based clustering method for unsupervised Internet traffic classification[A]. Proc of ICC’08[C]. Beijing, China, 2008. 1588-1592.

[29] ERMAN J, ARLITT M, MAHANTI A. Offline/real-time traffic classification using semi-supervised learning[J]. Performance Evaluation.2007, 64(9-12): 1194-1213.

[30] QUINLAN R. Discovering Rules from Large Collections of Examples:a Case Study[M]. Expert Edinburgh University Press, 1979.

[31] QUINLAN R. C4.5: Programs for Machine Learning[M]. San Francisco, USA. Morgan Kaufmann Publishers Inc, 1993.

[32] LOPEZ R, MANTARAS D. A Distance-based attribute selection measure for decision tree induction[J]. Machine Learning, 1991, 6(1):81-92.

[33] LBNL traces[EB/OL].http://ee.lbl.gov/anonymized-traces.html.

[34] CROTTI M, DUSI M, GRINGOLI F, et al. Traffic classification through simple statistical fingerprinting[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(1):5-16.

[35] WIDE Project[EB/OL]. http://mawi.wide.ad.jp/mawi/.

[36] Tcptrace official homepage[EB/OL]. http://www.tcptrace.org.

[37] Weka 3: Data mining software in Java[EB/OL]. http://www.cs. waikato. ac.nz/ml/weak.

[38] Analyzer: a public domain protocol analyzer[EB/OL]. http://analyzer.polito.it/.

[39] LI W, CANINI M, MOORE A. Efficient application identification and the temporal and spatial stability of classification schema[J]. Computer Networks, 2009, 53(6): 790-809.

[40] CALLADO A, KELNER J, SADOK D, et al. Better network traffic identification through the independent combination of techniques[J].Journal of Network and Computer Applications, 2010, 33(10):433-446.