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

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

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

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

DOI： 10.15938/j.jhust.2015.02.012

中圖分類號：TM391.1

文獻標志碼：A

文章編號：1007-2683（2015）02-0063-06

0 引 言

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

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

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

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

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

1.1 子空間聚類算法

子空間聚類問題描述：

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

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

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

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

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

該算法的相關定義如下：

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

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

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

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

該算法的基本步驟如下：

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

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

3）查找每個基本聚類的κ個最相似聚類，當作該基本聚類的合并候選；

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

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

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

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

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

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

2.2

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

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

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

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

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

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

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

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

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

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

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

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

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

如果IRI=0，則將該待分類流標記為label=Unknown，因為沒有分類器標記這個流；

如果|R|=1，R={k}則將此流標記為M（k），因為只有一個二分類器標記了這個流如果|R|>1，且Vi. ER，|si|<|Sk|，則將此流標記為M（k）.即如果多個分類器同時標記此流，則選擇簽名維度更高的分類器做標記，因為維度越高，特性越明顯.

2 實驗結果和分析

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

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

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

2.2特征

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

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

2.3 實驗理論和評估指標

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

本文使用覆蓋率（Coverage）、覆蓋集識別準確率（aCcuracy）以及新應用檢測率（newApp）等評價方法來評價SCM分類器的分類性能.

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

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

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

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

新應用的檢測率：

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

2.4實驗結果及分析

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

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

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

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

3 結 語

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