Length-Ware限制聚類的Markov加密流量分類研究

宮光霖，易軍凱，張雅聰

（1.北京信息科技大學 自動化學院，北京 100192；2.北京化工大學 信息科學與技術學院，北京 100015）

網絡流量是網絡中傳輸的數據［1］，為了使網絡中的數據傳輸情況可以被負責人清楚地了解，需要對網絡流量進行分析監控。除此之外，流量行為分析作為網絡安全分析的首要條件，因此又被定義為“網絡可視化”。現階段用戶隱私和傳輸保護越來越受到重視，這也導致數據包的加密比例持續顯著增長，從而使得識別和分析流量變得異常困難，只有確定網絡流量的類別才能對其進一步分析。

流量分類是一個很早就開始研究的課題，但是這些研究只是簡單地將流量劃分為SSL、VPN、encrypted P2P、VoIP、SSH等類別，沒有太多參考意義，而且隨著加密技術的興起和廣泛使用，加上流量自身的特性使得對流量分類變得更加困難。在網絡環境中，網絡流量依托的載體是數據包，然而數據包的數量十分龐大，對流量分類進行特征提取時，獲取的特征有限且不是典型的特征，對其分析難度較大。

近些年在國內對加密流量雖然有了初步的研究分析，但仍處在一個比較初級的階段，研究成果相對較少。陳貞貞［2］運用深層數據包檢測技術原理，結合深度學習，對HTTPS流量進行分類分析，提取出上下行數據包平均大小等特征實現加密流量的識別；董浩等［3］運用網絡流量與文本結構的相似的特性，將預處理后的數據構成一幅圖像，采用CNN模型實現對復雜網絡加密流量的特征提取和分類；程光等［4］采用支持向量機結合相對熵的概念，基于相對熵識別局部隨機性的特性排除流量干擾，并利用支持向量機對加密流量進行分類。這些方法大多數是通過技術方法提取網絡流量的特征并進行分析，屬于應用行為的分析。

Korczynski等［5］提出基于Markov的加密流量分類方法，在SSL/TLS中傳輸的應用流量隨機指紋基于Markov鏈，嵌入在SSL/TLS中的信息自然會形成隨時間變化的報文序列，這也是首次將通信的報文序列定義為Markov隨機過程，通過Markov鏈對給定應用從服務器端到客戶端的單向流中出現的一系列SSL/TLS報文類型進行建模，生成的模型展示了一種特定的結構，該結構允許通過將其報文序列與指紋進行比較來對加密的流量進行分類。Shen等［6］認為Korczynski等的方法有弊端，首先是SSL/TLS協議中session ID恢復的問題，避免了客戶端與服務器完整的握手過程，當要在同一客戶端和服務器之間建立新的連接時，session ID可能來自先前的連接或另一個當前已建立的連接；然后是Application Data的問題，作者認為在SSL/TLS協議中出現的第一個Application Data的規?？梢砸暈榱髁糠诸惖年P鍵功能。而Korczynski等［5］忽略了網絡傳輸中占比最大的是Application Data，僅對加密過程進行了分析?；谝陨蠁栴}，筆者進行了改進并提出了基于二階Markov鏈可感知屬性的加密流量分類方法。

通過大量的實驗研究分析出上述文獻仍存在不足之處：

①大部分應用都是按照協議進行密鑰和證書交互，特征指紋極容易出現重復，對分類有較大影響；

②提到的Certificate相比于其他報文占比很小，反而其他報文被忽略，因而眾多重要特征也沒有被提取到；

③Certificate報文在session ID復用階段出現的情況很少，通信大部分是通過TCP報文保持連接，然后發送大量應用數據。

為了解決上述問題，本文提出了Length-ware限制聚類的Markov加密流量分類（Encrypted Traffic Classification on Length-Ware Constrained Clustering，Length-ware）方法。Length-ware算法將其他相關報文長度也作為重要的特征分析，通過GMM［7］對其建立模型并對聚類加入限制條件，分析同一應用中不同長度報文的概率分布來提高分類準確率。

1 Markov過程與報文狀態轉換

網絡環境中，不同的應用轉換報文狀態的概率不同，這是一個隨機的過程，而Markov過程可以描述這個隨機過程。Markov性質是下一時刻的狀態只與當前狀態有關，與上一時刻狀態無關，用一個包含多個狀態集合的狀態矩陣去描述轉移過程就是Markov過程。

Markov過程是一個對現實高度抽象的極理想的過程，除了要滿足Markov性質外還需要包含狀態集合、轉移矩陣和初始狀態分布3部分。對該過程的概率進行計算，假設X1，X2，…，Xt是該過程的一組狀態，那么下一時刻（t+1）的概率如式（1）所示：

網絡中的數據包數量十分龐大，獲取的數據有限且沒有典型的特征，傳統的基于機器學習的分類方法無法對網絡流量實現分類，而Markov過程可以實現。

假設Markov模型t時刻狀態為Xt，（t+1）時刻狀態Xt+1的概率為：

式中：pi～j（i，j∈T）是Markov過程的轉移概率。

為了使最終的結果更加準確，這里進一步運用2階Markov模型

以QQ的通信數據舉例，＜（11∶05，11∶02）n＞、＜（11∶05，11∶02）n，11∶04，11∶02＞、＜（11∶04，11∶01，11∶01，（24∶，11∶02）n＞，這3個典型的QQ通信數據包的應用場景和出現概率都不同。

假設有一段未知的通信序列，我們將這段序列出現的概率定義為初始概率INIP（Initial Probability，INIP），如式（6）所示：

通信序列存在開始就存在結束，因此將完結的概率定義為結束概率EXTP（Exit Probability，EXTP），如式（7）所示：

假設這一段未知的通信序列為seqM=＜msg1，msg2，…，msgM＞，確定這個通信序列屬于哪一個具體應用的概率如式（8）所示：

式中：INIPmsg和EXTPmsg分別是以狀態msg1和msgM為初始狀態和結束狀態的概率。下文以3個典型的QQ通信數據包所示的通信序列模式為例對上述過程進行解釋。3個典型的QQ通信數據包共包含5種狀態：11∶01，11∶02，11∶04，11∶05，24∶。通過計算，INIP11∶05=0.96，φ11∶05=0.37，INIP11∶04=0.04，EXTP11∶02=1。狀態11∶05轉換為狀態11∶02的轉換概率方式在QQ通信中較常見，即p11∶05～11∶02=0.35。將狀態轉換概率建立成模型，如圖1所示。

圖1 狀態轉換示意圖

假設＜11∶05，11∶02，11∶05，11∶02，11∶01，24∶，11∶02＞是一段隨機抓取的通信序列，那么這個通信序列屬于QQ的概率為：P（＜11∶05，11∶02，11∶05，11∶02，11∶01，24∶，11∶02＞）=0.03。

2 Length-ware加密流量分類

加密流量是通過特殊的算法，改變了原有數據，在傳輸過程中即使被截獲也無法獲取其內容，為了獲取加密流量的數據特征提出分析應用行為的方法，在TLS/SSL中實現數據傳輸前，通信雙方需要經過密鑰和證書交換及用戶數據傳輸。這個過程比較復雜，所以實際應用時通常會簡化通信的過程來提高通信效率，經實驗將該過程分為3類：

①完整通信過程，通常發生在首次申請與服務器通信，服務器需要傳輸密鑰和證書。

②簡化通信過程，應用短時間再次與服務器端連接，不會進行完整通信過程，服務器會從保留的資源里直接獲取相關參數，并會通過一個報文ChangeCipherSpec傳送新的密鑰來確保傳輸的可靠性。

③數據傳輸過程，大部分應用僅通過傳輸控制協議（TPC）和Application Data 2種報文傳輸用戶數據，其中TPC用于保持連接。

大多數文獻通常僅考慮完整通信過程，主要研究分析報文類型，很小一部分文獻考慮到了報文長度，而本文主要將報文長度作為重要的特征分析，通過GMM對其建立模型并對聚類加入限制條件，然后通過指紋的概率分布提高分類準確率。

2.1 通信狀態轉換過程

網絡數據由于量大，屬性少，冗余多的特性，想要對這個復雜的傳輸過程進行分析一直是研究難點。Shen等［6］列舉了Application Data和Certificate 2種報文，并分析他們的報文長度來提高分類效率，并提出了Bigram聚類算法，以此為基礎，豐富原始二階Markov鏈中的狀態，圖2描述了通信狀態轉換的過程。

圖2 通信狀態轉換

其中，State X與State Y分別表示轉換到Certificate報文前和Certificate報文轉換到Application Data報文前的其他類型的報文，Application Data只有報文長度不同，在考慮Application Data的概率的同時，Bigram聚類通過這種報文長度的確定其概率分布。根據實驗分析，文獻仍存在不足之處，圖3是狀態轉換和指紋分布情況。

圖3 狀態轉換指紋分布示意圖

其中，stateα、stateβ、stateγ分別是分析的3類通信過程中的完整過程、簡化過程和數據傳送過程，stateα狀態與stateβ狀態的轉換過程一致，最終會轉換為stateγ的狀態，而Certificate只會出現在stateα狀態，該狀態在傳輸大量數據后很久不會再發生，因此，作為Bigram聚類核心的Certificate報文對stateβ狀態和stateγ狀態很難進行分析。其次，stateα、stateβ和stateγ狀態內都存在大量重復問題，而stateα狀態作為主要分析對象最為嚴重，嚴重影響分類效果的準確性。

所以為了解決報文間的重復問題，將報文長度作為重要的特征分析，建立了三類過程狀態之間的N-gram模型，并提出基于Length-ware的限制聚類報文概率分布模型，然后通過計算指紋的分布概率提高分類準確率。

2.2 Length-ware報文狀態轉換模型

加密傳輸的報文除了長度沒有典型的特征可以用作分析，而本文也正是將報文長度作為重要的特征分析N-gram模型［8］，對不同長度的報文概率分布建模，如圖4所示。

圖4 概率分布模型示意圖

如圖4所示，每個狀態中指紋的報文長度不同，而一個指紋可以定義為一個N-gram模型，不同報文長度情況的指紋就構成N-gram多元模型，假設是指紋中的一種報文長度，那么一個狀態中的一種指紋可以定義為，而一個狀態含有多個指紋，可以定義為fpα，β，γ=（fp1，fp2，fp3，…，fpi）。

fpα，β，γ狀態是其內眾多指紋及其報文長度的組合，無法確定具體的參數和分布類型，怎么去定義fpα，β，γ是模型建立的關鍵。高斯混合模型表示了觀測數據在總體中的概率分布，它是一個由多個正態分布組成的混合分布，通常來說，一個混合模型可以表示任何概率的正態分布，即用高斯混合模型表示任意一種未知的分布。假設fpα，β，γ中的其中一個特征指紋fpi滿足一種正態分布，那么就能夠用GMM描述fp：

式中：ai是各分布的混合參數a1+a2+a3+…+an=1，θi是正態分布的參數（μi，σi），式（9）可以轉化為：

所有的參數為θ=（θ1，θ2，θ3，…，θn，a1，a2，a3，…，an），用MLE的方法求參數θ，假設獲取的樣本為X=（x1，x2，x3，…，xn）：

2.3 基于限制聚類的報文N-gram模型

N-gram模型通過MLE的方法計算參數，但是式（13）所示的計算方法的計算量和計算過程都很復雜，在實際運算中很難算出參數。此外，不同應用的指紋，也可能存在相同長度的報文，算法要計算一個指紋中不同長度報文的概率，引用聚類的方法來計算N-gram模型的概率分布。

常見聚類的原理是隨機選取若干樣本，按照樣本間的距離大小，將樣本集重新劃分為n個簇。為了將相同IP地址的指紋盡量劃分成一個簇來提高分類效果，在計算參數時給與限制條件，使得同一個簇內的指紋如果相類似，盡可能來自同一應用，加快了收斂速度。此外，聚類時由于分類數量遠小于IP地址數量，獲取的數據包被劃分成Y=（y1，y2，y3，…，yn）等價集。

假設樣本X=（x1，x2，x3，…，xn）在計算參數時加入限制條件Φc，有一個簇的劃分Y=（y1，y2，y3，…，yn），（xi∈yi）。樣本X可以劃分成X=（x1，x2，x3，…，xn），其中是X的子集，加入的限制條件計算如下式：

式中：θy是樣本加入限制條件Φc后得到的參數，式（14）是參數（θ，θy）的期望函數。

然后在式（14）的基礎上采用MLE的方法對參數進行估計，得到式（15）：

式中：P（l|Xs，y∈Φc，θy）是Xs的后驗概率。

依次可以計算高斯模型的參數（μi，σi）的估計值：

根據式（19）可以很容易的計算相同指紋的概率分布：

表1是限制聚類的算法描述。

表1 Length-ware算法

通過Length-ware算法，可以將式（8）變換為式（22）：

3 實驗及結果分析

實驗測試所需的數據集是現實環境中通過Wireshark［11］抓取的網絡數據，設備是2個安卓系統的智能手機，手機安裝了包含抖音、快手等視頻類，微博、騰訊體育等新聞類，QQ、電子郵箱等通信類和美團、大眾點評等生活類的四大類常用軟件，數據集的具體值如表2所示。

表2 數據集

Background是手機在靜置狀態沒有使用任何應用的情況下抓取數據包的數量，主要是系統本身發送和一些應用的消息推送的數據，從表中可以看出，靜置15 min只獲取935個數據包，與Mix3數據集15 min獲取的179 181個數據包相比可以忽略不計，所以可以忽略這部分數據的影響；Video、News、Communication、Life是手機分別在只運行視頻類、新聞類、通信類、生活類的軟件采集的流量情況，Mix1、Mix2、Mix3是手機運行所有種類的軟件分別采集5、10、15 min的混合流量。

實驗驗證的是本文提出的Length-ware算法，第一部分驗證限制聚類對報文長度的聚類效果，運用基于Markov過程的流量分類方法，判斷標準是計算數據流每個類別的概率相差情況，如果相差較大，則說明分類效果較好，反之則較差。然后分析如何衡量按照報文長度進行限制聚類的聚類效果，需要考慮最理想和最差的2種極限情況，如果聚類時，由于一個應用的所有報文長度比較相近從而被聚類在同一個類中，在計算概率時，各個類別的概率差異明顯，再次遇到同樣長度的報文就能比較快速的確定報文的類別，這是最理想的情況；而最差的情況是聚類時由于一個應用的所有報文長度比較分散從而被聚類到不同類中，在計算概率時，各個類別的概率沒有明顯差異，所以很難確定報文的類別，因此從最理想和最差的情況分析，以同一應用的報文盡量在一個簇里，一個簇里盡量只包含1種應用作為評判標準，當然現實中這2種極限情況都不會存在，太過于理想只能存在于假設中，將這個評判標準定義為聚合系數［12］（clustering coefficient，CL_CO），如式（23）所示。

圖5 聚合系數CL_CO

在最理想和最差的情況下，CL_CO都無限趨近于0，采集流量的不同決定著最優的K值，所以K的取值對分類結果也有影響，當K的取值在31～35之間時，CL_CO達到最好。

第2部分實驗驗證的是加密流量分類的效果，與同樣基于Markov模型提出的流量分類方法——文獻［5］的MCF算法和文獻［6］的SOM算法作對比實驗，MCF算法僅僅考慮了完整通信過程的情況，并以報文類型為主要分析目標，SOM算法在其基礎上進行了改進，將Certificate的不同長度作為重要的特征分析。然后采用常見的評價指標TPR與FPR來檢驗3種算法的分類效果，TPR和FPR分別表示當前流量被分到正樣本類別中，真實的正樣本占所有正樣本的比例及當前流量被錯誤分到正樣本類別中，真實的負樣本占所有負樣本總數的比例，如式（24）（25）所示。

式中：TP為真陽性，是指屬于正樣本類別的流量被分類成正樣本類別；FN為漏報，是指屬于正樣本類別的流量而被分類成負樣本類別；FP是誤報，是指負樣本類別的流量而被分類成為正樣本類別；TN為真陰性，是指負樣本類別的流量而被分成負樣本類別。

這里同樣采用數據集Mix3作為被測試的數據集，K值選定35，CL_CO相對較好，然后分別計算3種算法對各類應用的TPR與FPR情況，如表3所示。

表3 MCF、SOM、Length-ware算法比較

從表3可以分析出，相比其他2種算法，MCF算法由于只考慮了通信建立階段而忽略維持階段的通信行為，因此分類性能明顯較差。SOM算法的分類效果相比MCF算法有一定提升，但相比Length-ware算法仍存在差距，因為SOM算法雖然考慮了通信維持階段的通信行為，但除Certificate外其他報文都被忽略，眾多重要特征也沒有被提取。從分類結果可以分析，視頻類由于只發送視頻，且格式和大小都相對穩定，所以分類效果普遍較好，而新聞類分類情況相比其他類普遍較差是由于其包含文字、圖片、視頻等多種類別數據，因此，由上述分類結果可以分析，一類應用流量行為越單一，其分類效果越好，相反則越差。

實驗選取不同的K值進行TPR和FPR，分析其對分類效果的影響，仍然以Mix3作為被測試的數據集，結果如圖6所示。

圖6 不同K值的TPR和FPR直方圖

從圖6的結果分析可知，當K=40時，TPR達到頂峰，FPR達到低谷，此時分類效果最好，而K值過大或者過小對分類結果都有較大的影響，分類效果會隨著K值的改變而改變，因此，只有選取合適的K值才能達到最優的分類效果。

4 結論

解決了原有Markov模型中沒有考慮網絡通信的狀態轉換的問題，提出基于報文長度的Length-ware算法，將報文長度作為重要的特征分析，通過GMM對其建立模型并對聚類加入限制條件，然后通過指紋的概率分布完成對相同指紋的分類。限制聚類時，盡可能將同一應用相同IP地址的指紋劃分成一個簇，提高分類效率。