基于子空間聚類的網(wǎng)絡(luò)流量分類方法

李丹丹++田春偉++李佰洋++孫廣路++康+健

摘要：應(yīng)用層網(wǎng)絡(luò)流量分類技術(shù)對(duì)流量控制與管理等研究具有重要意義，針對(duì)傳統(tǒng)的基于有監(jiān)督機(jī)器學(xué)習(xí)的分類方法對(duì)所有應(yīng)用程序使用相同的特征，使得某些特征對(duì)一種或幾種應(yīng)用類型有區(qū)分性，而對(duì)其他應(yīng)用類型的網(wǎng)絡(luò)流分類產(chǎn)生干擾等問題，提出基于子空間聚類方法的網(wǎng)絡(luò)流分類框架.利用子空間聚類算法，在總特征集中為每一種類型應(yīng)用進(jìn)行特征選擇，提取與之相對(duì)應(yīng)的關(guān)鍵特征，自動(dòng)消除不相關(guān)的特征，使得每種應(yīng)用類型都產(chǎn)生對(duì)應(yīng)的特征簽名集，并用這些不同的特征簽名對(duì)未知的網(wǎng)絡(luò)流進(jìn)行分類.實(shí)驗(yàn)結(jié)果表明：本文提出的方法能夠有效地提出每種應(yīng)用類型的特征簽名，并且所提出的特征簽名具有明顯的可區(qū)分性，該方法的分類準(zhǔn)確率在93%以上，并且能很好的識(shí)別新出現(xiàn)的應(yīng)用，

關(guān)鍵詞：子空間聚類；網(wǎng)絡(luò)流分類；特征簽名

DOI： 10.15938/j.jhust.2015.02.012

中圖分類號(hào)：TM391.1

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-2683（2015）02-0063-06

0 引 言

近年來，具有開放性、共享性等特點(diǎn)的互聯(lián)網(wǎng)迅速普及并發(fā)展壯大，隨著網(wǎng)絡(luò)用戶數(shù)量的飛速增多，傳統(tǒng)的互聯(lián)網(wǎng)業(yè)務(wù)已經(jīng)無法滿足人們的需求，越來越多的新型網(wǎng)絡(luò)應(yīng)用應(yīng)運(yùn)而生.對(duì)于網(wǎng)絡(luò)運(yùn)營商來說，為了有效利用帶寬，并提供更好的服務(wù)質(zhì)量（quality of service，QoS），需要網(wǎng)絡(luò)能夠針對(duì)不同應(yīng)用進(jìn)行分類.另一方面，互聯(lián)網(wǎng)的開放性特點(diǎn)允許任何符合其技術(shù)標(biāo)準(zhǔn)的設(shè)備或軟件接人互聯(lián)網(wǎng)，導(dǎo)致了各種網(wǎng)絡(luò)惡意攻擊事件層出不窮，嚴(yán)重危害網(wǎng)絡(luò)信息安全與服務(wù)，保護(hù)網(wǎng)絡(luò)安全迫在眉睫.網(wǎng)絡(luò)流量分類技術(shù)能夠增強(qiáng)網(wǎng)絡(luò)可控性，幫助研究人員掌握網(wǎng)絡(luò)上的流量分布情況，幫助網(wǎng)絡(luò)運(yùn)營商優(yōu)化服務(wù)質(zhì)量，預(yù)防并阻止各種網(wǎng)絡(luò)犯罪行為.總而言之，構(gòu)建網(wǎng)絡(luò)智能，網(wǎng)絡(luò)流分類是第一步.

在流量分類研究中，目前廣泛采用5元組{源IP、源端口、目的IP、目的端口、傳輸層協(xié)議}（SourceIP，Source PORT，Destination IP，Destination PORT，Protocol）定義數(shù)據(jù)流，迄今為止，網(wǎng)絡(luò)流量分類方法主要包括基于端口號(hào)匹配的分類方法、基于應(yīng)用層載荷特征的分類方法、基于主機(jī)行為和交互行為的分類方法，以及基于機(jī)器學(xué)習(xí)的分類方法.用于分類的特征主要有端口特征、載荷特征、網(wǎng)絡(luò)流包級(jí)和流級(jí)統(tǒng)計(jì)特征、主機(jī)行為和交互行為特征（根據(jù)IP地址、端口等衍生出來的關(guān)聯(lián)特征）.

其中，傳統(tǒng)的基于有監(jiān)督機(jī)器學(xué)習(xí)的分類方法，主要是利用網(wǎng)絡(luò)流在網(wǎng)絡(luò)層和傳輸層的統(tǒng)計(jì)特征來識(shí)別流量.這種方法使用的特征和訓(xùn)練得到的分類器對(duì)所有應(yīng)用類型的流都是相同的，沒有差異和針對(duì)性.某些特征對(duì)一種或幾種應(yīng)用類型有區(qū)分性，而對(duì)其他應(yīng)用類型的流分類產(chǎn)生干擾，導(dǎo)致整體的分類準(zhǔn)確率不高.而且，其對(duì)于網(wǎng)絡(luò)數(shù)據(jù)中新出現(xiàn)協(xié)議的識(shí)別效果不能令人滿意.

針對(duì)以上問題，依據(jù)樣本在不同的數(shù)據(jù)簇中常常與某些特定的數(shù)據(jù)特征子集相對(duì)應(yīng)的思想，本文提出了一種新的網(wǎng)絡(luò)流分類方法：基于子空間聚類的網(wǎng)絡(luò)流分類方法（subspace clustering-basedmethod，SCM）.它針對(duì)每一種應(yīng)用流獨(dú)立建立識(shí)別模型，然后將這些識(shí)別單一應(yīng)用的模型合在一起，實(shí)現(xiàn)多類別分類，而不是同時(shí)區(qū)分幾種應(yīng)用.換句話說，SCM方法學(xué)習(xí)獨(dú)立的識(shí)別類A和識(shí)別類B，而不是試著同時(shí)區(qū)分類A和類B.本文使用骨干網(wǎng)絡(luò)數(shù)據(jù)集和邊界網(wǎng)絡(luò)數(shù)據(jù)集對(duì)SCM分類方法進(jìn)行測試，識(shí)別精度達(dá)到93%，而且對(duì)新應(yīng)用的識(shí)別率可以達(dá)到90%.由于路由非對(duì)稱原因?qū)е鹿歉删W(wǎng)中雙向流中的某一個(gè)方向的流經(jīng)常丟失，本文中的分類方法使用單向流.

1 子空間聚類算法及網(wǎng)絡(luò)流分類框架

1.1 子空間聚類算法

子空間聚類問題描述：

設(shè)B=B1×B2×…×Bn，代表一個(gè)n維數(shù)據(jù)空間，其中，n為正整數(shù).F是包含m個(gè)位于n維特征空間的數(shù)據(jù)對(duì)象的集合，記為F= {Xi|i∈[1，m]，xij=Xi.Bj}，其中，點(diǎn)Xi=（xi1，xi2，…，xij，…，xin。），Xi的第j個(gè)屬性值xij，為其在哆維上的取值.設(shè)k維子空間S^CB其中，k≤n.在SK子空間中的元組集合表示為

在訓(xùn)練期間，SCM分類框架為每種應(yīng)用類型產(chǎn)生一組簽名.產(chǎn)生簽名的過程如下：

1）輸入：屬于同種應(yīng)用類型的一組流的集合F，每個(gè)流feF用n維數(shù)值向量表示.

2）輸出：流的子集合與特征子空間的對(duì)應(yīng)關(guān)系（Fi，Si）即簽名，其中F：∈F，S，CB.每一種應(yīng)用類型可能包含多個(gè)簽名iE[1，|F|].

本文使用文提出的基于K最相似聚類的子空間聚類算法，在得到所有一維空間聚類的基礎(chǔ)上，查找包含相同數(shù)據(jù)對(duì)象的相似聚類，繼而決定子空間搜索方向，然后合并不同維度中的相似聚類，最終得到子空間聚類。該方法用不同子空間中采用的不同密度閾值替代傳統(tǒng)算法中的全局密度閾值，提高了子空間聚類算法聚類結(jié)果的精度。

該算法的相關(guān)定義如下：

定義1（基本聚類） 將使用DBSCAN方法產(chǎn)生的所有一維空間的聚類的集合稱為基本聚類，記為C'.

定義2（基本聚類相似度） 給定c.，c：∈C1，其中，c，在Bi維，c：在B，維，且i≠j，其相似度定義為基本聚類c，，C2所包含的相同數(shù)據(jù)對(duì)象元素的數(shù)目，記為.sim（ ci，C2）=|C1∩C2|.

定義3（最相似聚類） 給定聚類c∈Cl，c的最相似聚類MSC（C）∈C1滿足條件：

定義4（k最相似聚類）給定聚類C∈Cl和正整

該算法的基本步驟如下：

1）對(duì)數(shù)據(jù)做預(yù)處理，產(chǎn)生每一維上的基本聚類；

2）計(jì)算所有基本聚類之間的相似度；

3）查找每個(gè)基本聚類的κ個(gè)最相似聚類，當(dāng)作該基本聚類的合并候選；

4）使用深度優(yōu)先方法搜索子空間，產(chǎn)生子空間聚類：

5）刪除剩余數(shù)據(jù)噪聲點(diǎn).

先找到基本聚類c∈C1，形成子空間S1，計(jì)算Cl中各個(gè)基本聚類問相似度，通過得到的基本聚類相似度查找每個(gè)基本聚類的k個(gè)最相似聚類，合并基本聚類相似度大于等于para（S2）的基本聚類，形成S2子空問，然后不斷的遞歸的搜索，產(chǎn)生子空問聚類.

其中para（Sm）為Sm子空間合并閾值，利用如下公式來獲得：

就是Sm子空間期望，它是由總的學(xué)習(xí)樣本數(shù)|F|比上Sm子空間投影到每一維產(chǎn)乍的不同元組的數(shù)目得到的，算法的詳細(xì)內(nèi)容參見.

所有的特征都使用標(biāo)準(zhǔn)的Z-score算法進(jìn)行標(biāo)準(zhǔn)化，該公式為其中μ和σ分別是通過訓(xùn)練數(shù)據(jù)算出來的特征的平均值和標(biāo)準(zhǔn)差.

2.2

SCM網(wǎng)絡(luò)流分類框架

基于子空間聚類算法，本文提出一種新的網(wǎng)絡(luò)流分類框架SCM.SCM執(zhí)行兩個(gè)不同的過程：（a）產(chǎn)生簽名（b）網(wǎng)絡(luò)流分類.具體的分類示意圖如圖1.

分類過程：在分類期間，一個(gè)待分類流需要和所有應(yīng)用類型各自對(duì)應(yīng)的簽名模式做匹配.實(shí)質(zhì)上每一個(gè)簽名模式都是一個(gè)二分類器，只返回是或否.F面是分類的詳細(xì)過程.

匹配一個(gè)簽名模式：當(dāng)一個(gè)待分類流匹配某個(gè)特定的簽名（Fi，Si）時(shí)，首先它投影到Si維空間中（提取對(duì)應(yīng)特征集），然后用標(biāo)準(zhǔn)“歐幾里得距離”來計(jì)算它與Fi中的模式流之問的距離.本文把待分類流到Fi中最近的流的距離作為待分類流到簽名的距離（即距離的最小值）.如果待分類流在該簽名的預(yù)定半徑r范圍內(nèi)，則匹配成功，實(shí)質(zhì)上，每一個(gè)簽名都是一個(gè)有|Si|維特征、|Fi|個(gè)點(diǎn)和同定半徑的最近鄰分類器，這個(gè)固定的半徑保證簽名只匹配屬于此應(yīng)用類型的流而不會(huì)匹配屬于其他應(yīng)用類型的流.

根據(jù)歐幾里得公式：

可以看到，即使每一維度的距離都很小，距離d還隨維度|Si|升高而遞增，而不同子空間的維度可能不相同，所以對(duì)所有的子空問都用同一個(gè)固定半徑不準(zhǔn)確，本文用基本的縮放因子/哆T來調(diào)節(jié).這樣，如果在我們的分類器中使用的一維半徑是r，那么對(duì)于簽名（Fi，Si），

在簽名的所有點(diǎn)半徑ri的覆蓋范圍內(nèi)我們都認(rèn)為是有效的，

流分類過程：本文中的SCM分類框架包括很多二分類器，每一個(gè)二分類器對(duì)應(yīng)一個(gè)應(yīng)用簽名（Fi，Si）.假設(shè)現(xiàn)在得到t個(gè)二分類器：

每一個(gè)進(jìn)入SCM分類框架的流都要被每一個(gè)二分類器處理.每一個(gè)二分類器都要返回true或false和距離d.因此，結(jié)果是兩個(gè)向量：

1） -個(gè)t維的布爾向量其中變量表示二分類器i的返回值.比如，如果X，給流標(biāo)記為真，f，=l，否則，f，=0.

2） -個(gè)n維的數(shù)值向量：其中di。表示該待分類流到簽名（Fi，Si）之問的距離，由于屬于一個(gè)應(yīng)用類型的待分類流可能和多個(gè)簽名有關(guān)，它可能被映射到多個(gè)二分類器巾，為了跟蹤二分類器和應(yīng)用類型的映射關(guān)系（在訓(xùn)練中得到），我們引進(jìn)了一個(gè)新的向量M，如果二分類器i來自應(yīng)用App，則M（i）=App，可能會(huì)有多個(gè)i對(duì)應(yīng)一個(gè)應(yīng)用App.

最后，測試流是否被標(biāo)記為App或Unknown由下面的算法決定，這個(gè)算法用到向量L、D和M：

添加所有L（i）=true的i值到結(jié)果集R中；

如果IRI=0，則將該待分類流標(biāo)記為label=Unknown，因?yàn)闆]有分類器標(biāo)記這個(gè)流；

如果|R|=1，R={k}則將此流標(biāo)記為M（k），因?yàn)橹挥幸粋€(gè)二分類器標(biāo)記了這個(gè)流如果|R|>1，且Vi. ER，|si|<|Sk|，則將此流標(biāo)記為M（k）.即如果多個(gè)分類器同時(shí)標(biāo)記此流，則選擇簽名維度更高的分類器做標(biāo)記，因?yàn)榫S度越高，特性越明顯.

2 實(shí)驗(yàn)結(jié)果和分析

2.1數(shù)據(jù)集

本文使用3份真實(shí)流量對(duì)SCM子空間聚類方法進(jìn)行實(shí)驗(yàn)驗(yàn)證，這3份數(shù)據(jù)一份是骨干網(wǎng)絡(luò)數(shù)據(jù)和兩份是不同的校園網(wǎng)數(shù)據(jù).分別收集于2010年與2012年.

本文使用基于載荷的DPl分類技術(shù)對(duì)網(wǎng)絡(luò)流進(jìn)行標(biāo)記.使用的數(shù)據(jù)集中包括如下幾種應(yīng)用：Web， Streaming， P2P，Chat， Dns， Games， Mail和其他類型，其中未標(biāo)記的流約占20%.實(shí)驗(yàn)時(shí)將這些未識(shí)別的流去除掉.圖2描述了3份網(wǎng)絡(luò)數(shù)據(jù)集中應(yīng)用層應(yīng)用類型的分布情況.

2.2特征

本文使用了網(wǎng)絡(luò)流包級(jí)、流級(jí)的主要特征，包括流的前6個(gè)包的大小、內(nèi)部時(shí)間間隔（IAT）、總字節(jié)數(shù)、總包數(shù)和IAT的最大值，最小值，平均值、標(biāo)準(zhǔn)差等等.

還包含了每個(gè)流的前16字節(jié)載荷.每個(gè)載荷字節(jié)都用{0，l，…255}之間的數(shù)值表示，據(jù)研究，應(yīng)用層協(xié)議頭在流中會(huì)重現(xiàn)，而載荷的前16字節(jié)會(huì)包括應(yīng)用層協(xié)議頭.所以載荷的前16字節(jié)也是重要的特征.每個(gè)特征用一個(gè)流的特征向量的一維來表示，使用的詳細(xì)特征見表1.

2.3 實(shí)驗(yàn)理論和評(píng)估指標(biāo)

為了評(píng)估SCM方法的性能，本文把每一個(gè)數(shù)據(jù)集分成兩部分.用其中一部分做訓(xùn)練，用另一部分做測試.訓(xùn)練分類器時(shí)，本文只考慮實(shí)際流數(shù)超過1000個(gè)的應(yīng)用類型.這個(gè)數(shù)對(duì)于收集訓(xùn)練數(shù)據(jù)不難，而且足夠用于抽取好的簽名，本文只對(duì)單向流產(chǎn)生簽名，這樣可以分別從客戶端到服務(wù)器端的交互和從服務(wù)器端到客戶端的交互中抽取不同的簽名.當(dāng)用對(duì)比基準(zhǔn)與SCM分類預(yù)測結(jié)果對(duì)照時(shí)，需要同時(shí)看流的兩個(gè)方向上所給的標(biāo)簽，如果一個(gè)方向標(biāo)記為未知流，反方向標(biāo)記為某種已知應(yīng)用類型，則用反方向標(biāo)簽標(biāo)記該流.如果兩個(gè)方向標(biāo)記的標(biāo)簽不同，則將此流標(biāo)記為未知.文中所有的實(shí)驗(yàn)結(jié)果均是對(duì)多次實(shí)驗(yàn)結(jié)果取得的平均值，

本文使用覆蓋率（Coverage）、覆蓋集識(shí)別準(zhǔn)確率（aCcuracy）以及新應(yīng)用檢測率（newApp）等評(píng)價(jià)方法來評(píng)價(jià)SCM分類器的分類性能.

覆蓋率：實(shí)際做出預(yù)測的樣本的數(shù)量（沒被標(biāo)記為未知）除以樣本總數(shù).

覆蓋集的準(zhǔn)確率是被正確分類的樣本的數(shù)量除以預(yù)測樣本總數(shù).即：其中，TP表示真正（true positive.s），F(xiàn)P表示正錯(cuò)誤（false Positives）.具體定義如下：

1）真正：指待測方法將P2P流識(shí)別為P2P流的個(gè)數(shù)；

2）正錯(cuò)誤：指待測方法將非P2P的流錯(cuò)誤識(shí)別為P2P流的個(gè)數(shù)；

新應(yīng)用的檢測率：

當(dāng)SCM分類框架對(duì)一個(gè)訓(xùn)練數(shù)據(jù)集中不存在的應(yīng)用類型的流分類時(shí)，理想的結(jié)果是這個(gè)流被標(biāo)記為未知.例如，如果訓(xùn)練得到的分類器中沒有Gaines類型的簽名，那么分類器應(yīng)該將所有測試數(shù)據(jù)中的Games流標(biāo)記為未知.由于訓(xùn)練的簽名中不存在Games類型，Games類型就代表了一種新的應(yīng)用.本文暫時(shí)刪除訓(xùn)練數(shù)據(jù)中的一種應(yīng)用類型的流，然后觀察分類器如何標(biāo)記這些“新”應(yīng)用類型的流.

2.4實(shí)驗(yàn)結(jié)果及分析

本文在不同配置參數(shù)下測試了SCM方法的性能，先用一個(gè)數(shù)據(jù)來測試不同的配置，確定參數(shù)供實(shí)驗(yàn)中其他數(shù)據(jù)使用，本文使用DBSCAN算法來產(chǎn)生基簇，DBSCAN有兩個(gè)參數(shù)，流間允許的最大距離ε和最小點(diǎn)數(shù)minPts.一維特征空間的有效區(qū)域的半徑r也設(shè)為與ε相同的值r=ε.通過刪除低維簽名可以調(diào)控分類器的準(zhǔn)確率，經(jīng)過實(shí)驗(yàn)，我們得到μ為

3，minClu為4，MSCG（c）集合大小為4時(shí)子空間聚類算法的聚類效果最好，

為了研究參數(shù)敏感性，本文大范圍的變換ε，minPts的值來觀察實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果表明，參數(shù)的變化對(duì)我們分類器的分類效果影響很大，本文中使用的默認(rèn)參數(shù)是minPts=10.這些參數(shù)值是測試清華骨十網(wǎng)數(shù)據(jù)得到的，然后對(duì)其余2個(gè)數(shù)據(jù)集用與這個(gè)分類器同樣的配置.圖3展示了SCM分類器在3個(gè)數(shù)據(jù)集上的分類表現(xiàn)，雖然使用通過edgel數(shù)據(jù)得到的分類器配置，但是在3個(gè)數(shù)據(jù)集上的分類效果都很好.Accuracy可達(dá)到93%，與樸素貝葉斯分類器的分類結(jié)果對(duì)比如圖3.在調(diào)整好參數(shù)的情況下，SCM的準(zhǔn)確率優(yōu)于樸素貝葉斯分類器.

SCM在識(shí)別新應(yīng)用方面表現(xiàn)也很好，本文對(duì)每種應(yīng)用類型都做一次新應(yīng)用測試，然后用所有應(yīng)朋類，趔各自得到的newApp求平均值.newApp的平均值可達(dá)到90%，coverage可達(dá)到75%，如圖4所示.

3 結(jié) 語

本文將子空間聚類方法應(yīng)用于應(yīng)用層流量分類中，提出SCM網(wǎng)絡(luò)流分類框架.在訓(xùn)練過程中，為每種應(yīng)用類型產(chǎn)生多個(gè)流與子特征空間的簽名對(duì)即二分類器，用于識(shí)別單一應(yīng)用類型的應(yīng)用.義將多個(gè)二分類器組合在一起實(shí)現(xiàn)多類別分類.SCM能夠有效的對(duì)每個(gè)應(yīng)用類型抽取出相應(yīng)的特征簽名，并日.所提出的特征簽名具有明顯的可區(qū)分性，該方法的分類準(zhǔn)確率能達(dá)到93%以上，超過了樸素貝葉斯分類器，并且能很好的對(duì)新出現(xiàn)的應(yīng)用進(jìn)行識(shí)別.