基于層次聚類的多策略未知協(xié)議分類方法*

代先勇，胥 雄，鄧金祥，俞祥基，熊 竹，熊 民

（成都深思科技有限公司，四川 成都 610000）

0 引 言

隨著近些年互聯(lián)網(wǎng)的不斷發(fā)展，網(wǎng)絡(luò)應(yīng)用呈現(xiàn)爆發(fā)式增長，其中不乏大量使用自定義協(xié)議的應(yīng)用。對于網(wǎng)絡(luò)監(jiān)管部門來說，自定義協(xié)議的標(biāo)準(zhǔn)非公開，屬于未知格式的協(xié)議。未知協(xié)議無法參考標(biāo)準(zhǔn)協(xié)議的識別方法以準(zhǔn)確解析其數(shù)據(jù)結(jié)構(gòu)，使得直接通過網(wǎng)絡(luò)流量來識別所屬應(yīng)用協(xié)議存在較大的阻礙，增加了對網(wǎng)絡(luò)數(shù)據(jù)進行合法性審計監(jiān)測的難度。同時，越來越多的惡意程序使用未知協(xié)議進行通信，容易隱藏在正常通信流量中，難以與其他正常的私有協(xié)議數(shù)據(jù)進行區(qū)分，給網(wǎng)絡(luò)監(jiān)管帶來大量分析工作與難點。本文的研究重點在于把基于傳輸控制協(xié)議（Transmission Control Protocol，TCP）傳輸?shù)奈粗獏f(xié)議數(shù)據(jù)流通過分類的方法，對相似的未知協(xié)議數(shù)據(jù)流進行標(biāo)記，分類到同一集合；在后續(xù)進行流量分析時，由于集合中流量具有相似性，只針對同一集合的部分?jǐn)?shù)據(jù)進行分析，即可得知當(dāng)前集合所有數(shù)據(jù)的情況，減少分析過程數(shù)據(jù)量，提高分析效率。

1 模型與方法

本文提出的未知協(xié)議分類模型，主要基于層次聚類算法，并結(jié)合多種策略進行結(jié)果數(shù)據(jù)調(diào)整，最終實現(xiàn)數(shù)據(jù)的分類。

1.1 相關(guān)理論和方法

1.1.1 聚類算法分析

聚類是指根據(jù)數(shù)據(jù)間的相似性，將具有相同屬性的對象劃分到對應(yīng)數(shù)據(jù)集合的過程。聚類所生成的不同組稱為簇（cluster），一個簇包含一組數(shù)據(jù)對象的集合，具有簇內(nèi)對象彼此相似，簇間對象相異的特點。

常見的數(shù)據(jù)聚類方法可分為以下幾類：基于劃分的聚類算法，例如K均值聚類算法（K-means Clustering Algorithm，K-means）；基于密度的聚類算法，例如基于密度的噪聲應(yīng)用空間聚類算法（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）；基于層次的聚類算法，例如基于代表點的聚類算法（Clustering Using REpresentatives，CURE）；基于網(wǎng)格的聚類算法，例如基于網(wǎng)格的多分辨率的聚類算法（STatistical INformathon Gird，STING）；基于模型的聚類算法，例如基于高斯混合模型的算法（Gaussian Mixture Models，GMM）等。不同的聚類算法適用于不同的應(yīng)用場景。在實際網(wǎng)絡(luò)中，未知協(xié)議不能預(yù)先分析其規(guī)則信息，故無法預(yù)先提取標(biāo)簽數(shù)據(jù)進行學(xué)習(xí)。在基于層次的聚類算法中，通過計算不同類別數(shù)據(jù)點間的相似度來創(chuàng)建一棵有層次的聚類樹。在聚類樹中，以不同類別的原始數(shù)據(jù)點為樹的最底層，聚類的根節(jié)點為樹的頂層，可不直接依賴k值和初始聚類中心點的設(shè)置進行聚類，由聚類過程自動調(diào)整，最終把相似類別聚集在一起，滿足未知協(xié)議在真實網(wǎng)絡(luò)中的分類需求。

1.1.2 相關(guān)工作研究

網(wǎng)絡(luò)協(xié)議是指在特定網(wǎng)絡(luò)環(huán)境中進行通信而建立的標(biāo)準(zhǔn)或者規(guī)則，包含語義、語法、時序三要素。本文中，按協(xié)議是否公開標(biāo)準(zhǔn)格式或者開發(fā)文檔進行劃分，分為已知協(xié)議和未知協(xié)議兩類。協(xié)議分類經(jīng)過多年的發(fā)展，也探索出較多不同的識別路線，目前主要有端口匹配技術(shù)、深度包檢測（Deep Packet Inspection，DPI）/深度流檢測（Deep Flow Inspection，DFI）[1]技術(shù)、機器學(xué)習(xí)技術(shù)等。汪立東等人[2]提出基于端口的網(wǎng)絡(luò)流量分類，該方法具有識別速度快的優(yōu)點，但對沒有公開的未知協(xié)議就無法完成分類識別，并且現(xiàn)在還存在很多使用動態(tài)端口以及端口復(fù)用技術(shù)的服務(wù)，會使此方法出現(xiàn)識別錯誤的情況；鎮(zhèn)佳等人[3]提出基于DPI/DFI的協(xié)議分類識別，通過規(guī)則庫匹配應(yīng)用層數(shù)據(jù)的內(nèi)容，該方法可以對部分存在少量字節(jié)特征的未知協(xié)議進行分類識別，但其準(zhǔn)確性依賴于人工提取協(xié)議特征的準(zhǔn)確性，對于復(fù)雜的未知協(xié)議無法直接通過人工找到特征，需要借助協(xié)議逆向技術(shù)[4]來完成，無疑提高了對復(fù)雜協(xié)議識別的門檻，同時對計算機的計算能力也有一定的要求，對字節(jié)特征不明顯或幾乎不存在字節(jié)特征的加密協(xié)議無法進行識別；張鳳荔等人[5]提出了零知識下的比特流未知協(xié)議分類模型，該方法解決了K-means聚類算法的k值確定問題，對常規(guī)協(xié)議的分類正確率較高，但無法對加密流量進行分類；Singh[6]提出了基于網(wǎng)絡(luò)行為的無監(jiān)督聚類方法，使用基于關(guān)聯(lián)系數(shù)的特征選擇技術(shù)，對比K-means算法和EM算法的聚類效果，實驗結(jié)果表明K-means的聚類準(zhǔn)確度更高；Zhang等人[7]借助少量帶標(biāo)簽的數(shù)據(jù)，使用半監(jiān)督學(xué)習(xí)的未知協(xié)議分類方法，此方法的三元組關(guān)聯(lián)算法和投票算法都可以提升分類器的準(zhǔn)確率，但在真實網(wǎng)絡(luò)中，三元組關(guān)聯(lián)會受到很大限制，使得帶標(biāo)簽數(shù)據(jù)的擴展效果低于實驗室數(shù)據(jù)的測試結(jié)果，識別結(jié)果的類別也會受到標(biāo)簽數(shù)量的限制，需要標(biāo)簽足夠完備才能得到較好的結(jié)果；Ma等人[8]借助卷積網(wǎng)絡(luò)對未知協(xié)議進行識別，將網(wǎng)絡(luò)流負載當(dāng)作圖像數(shù)據(jù)進行處理，需要在訓(xùn)練階段使用帶標(biāo)簽的數(shù)據(jù)，篩選測試階段計算出的結(jié)果，將概率低于0.8的流作為未知流，該方法只能識別標(biāo)簽范圍內(nèi)的協(xié)議類型和“未知協(xié)議”類型，無法對未知協(xié)議進行更細粒度的區(qū)分。

在以上協(xié)議分類識別技術(shù)中，均存在各類不足。如對未知協(xié)議不適用，需要搜集大量未知協(xié)議（加密協(xié)議）樣本進行訓(xùn)練學(xué)習(xí)，耗費大量時間和人力，無法自動適應(yīng)新出現(xiàn)的未知協(xié)議分類需求等。故本文提出一種新的未知協(xié)議分類模型。

1.2 協(xié)議分類模型設(shè)計

在本模型中，協(xié)議在語義和時序上具有一定統(tǒng)計特征，并對所有類型的協(xié)議具有普適性，故分類算法主要提取協(xié)議的語義和時序兩個維度的統(tǒng)計特征作為數(shù)據(jù)輸入，對已知協(xié)議和未知協(xié)議（包括加密協(xié)議）均適用。同時采用無監(jiān)督的層次聚類算法進行分類，該算法可不依賴于預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實例，無須預(yù)先獲取大量的未知協(xié)議樣本數(shù)據(jù)，由聚類過程自動確定標(biāo)記，把相似的對象歸到同一個簇中[9]，符合未知協(xié)議網(wǎng)絡(luò)流量無先驗知識的實際情況。由于使用協(xié)議交互統(tǒng)計特征作為原始數(shù)據(jù)輸入，不需要搜集樣本進行標(biāo)記訓(xùn)練，所以也適用于新出現(xiàn)的未知協(xié)議。

首先對網(wǎng)絡(luò)流量進行捕獲抓取，經(jīng)過數(shù)據(jù)篩選、規(guī)范化等處理，在聚類前先根據(jù)流字節(jié)特征進行可讀性分類，針對可讀和不可讀數(shù)據(jù)使用不同的分類參數(shù)進行差異化區(qū)分。同時使用馬爾科夫鏈（Markov Chain）[10]來強化原始數(shù)據(jù)特征的表征能力，信息熵（Entropy）[11]對層次聚類（Hierarchical Clustering）過程進行優(yōu)化，并結(jié)合距離矩陣的對稱性，對層次聚類算法進行改進，降低計算距離矩陣的復(fù)雜度，減少聚類過程時間和計算設(shè)備內(nèi)存消耗。最后對分類結(jié)果進行調(diào)整與合并，提高分類結(jié)果準(zhǔn)確性和聚集度。功能模塊主要包括流量提取、特征預(yù)處理、可讀性分類和應(yīng)用層協(xié)議分類4個部分，在測試調(diào)優(yōu)的過程中還會引入結(jié)果評估模塊，如圖1所示。

流量提取支持通過網(wǎng)卡實時捕獲流量和從磁盤讀取離線數(shù)據(jù)包兩種方式，對進入系統(tǒng)的數(shù)據(jù)包進行流關(guān)聯(lián)，以TCP流為單位進行特征統(tǒng)計和預(yù)處理，然后借助預(yù)處理后的流量特征進行一次粗顆粒度的可讀性分類，得到可讀性數(shù)據(jù)流和不可讀數(shù)據(jù)流兩大類，接著對這兩類數(shù)據(jù)流分別進行應(yīng)用層協(xié)議分類。單個聚類策略的分類效果很難達到較高的水平，本方法提出類簇合并算法和類簇調(diào)整算法，極大程度地提升本方法的分類效果。應(yīng)用層協(xié)議分類通過層次聚類的多種策略得到多組結(jié)果，這些結(jié)果經(jīng)過類簇合并算法合并、類簇調(diào)整算法調(diào)整后，再借助二元組[7]（目的IP和目的端口）合并得到最后的分類結(jié)果。

1.2.1 流量采集預(yù)處理

對實時流量的采集，為了能適應(yīng)大流量的真實網(wǎng)絡(luò)環(huán)境，采集預(yù)處理中采用數(shù)據(jù)平面開發(fā)套件（Data Plane Development Kit，DPDK）[12]作為流量采集的基礎(chǔ)框架。對采集到的流量包通過五元組（源IP、目的IP、源端口、目的端口、傳輸層協(xié)議）進行關(guān)聯(lián)，將包間時間間隔較小且具有相同五元組的數(shù)據(jù)包視為一個流單元。后續(xù)所有的處理，均以一個流單元作為研究的基本單位。

針對捕獲到的每一個流單元（以下簡稱為流），進行協(xié)議識別、丟包檢測、流重組等操作，過濾能被協(xié)議識別的流、流連接初始階段存在丟包的流和攜帶載荷的包數(shù)量小于pkt_cnt_min（一條流統(tǒng)計的包個數(shù)總量最小閾值）或者載荷總字節(jié)數(shù)小于payload_total_min（一條流統(tǒng)計的載荷字節(jié)數(shù)總量最小閾值）的流。經(jīng)過上述過濾后，剩余的流具有更穩(wěn)定的網(wǎng)絡(luò)行為和字節(jié)特征，也使整個方法能適應(yīng)真實的網(wǎng)絡(luò)環(huán)境，而不僅限于實驗室數(shù)據(jù)。

每一個TCP流的前面部分都包含了流中的關(guān)鍵信息[8]，因此在對流進行特征提取時，更關(guān)注TCP流的前面部分流特征。經(jīng)過過濾后，進行流特征統(tǒng)計[8,10,13]，主要包括：

（1）前pkt_cnt_min個帶負載包的每個包最多前payload_max（一個數(shù)據(jù)包統(tǒng)計的載荷數(shù)據(jù)最大字節(jié)數(shù)）個字節(jié)的字節(jié)分布；

（2）前pkt_cnt_max（一條流統(tǒng)計的包個數(shù)總量最大閾值）個帶負載包的包大小、時間間隔及包大小的狀態(tài)轉(zhuǎn)換；

（3）單方向帶負載包的包大小及時間間隔，統(tǒng)計計算包大小的均值、標(biāo)準(zhǔn)差、最大值和最小值；

（4）雙方向帶負載包的包大小，統(tǒng)計計算包大小的均值、標(biāo)準(zhǔn)差、最大值和最小值；

（5）單方向的每秒發(fā)包量（packet per second，pps）與每秒字節(jié)數(shù)（bits per second，bps），雙向的pps與bps；

（6）TCP各標(biāo)記位次數(shù)、雙向初始窗口大小；

（7）上下行流的字節(jié)占比和包占比；

（8）單方向的帶負載包的包總大小，連接時長。

引入馬爾科夫鏈對特征進行處理。在選取的特征集合中，包大小的狀態(tài)轉(zhuǎn)換矩陣來自馬爾科夫鏈[10,14]。從TCP流第一個帶負載的數(shù)據(jù)包開始計算，每一個帶負載的數(shù)據(jù)包都具有一個狀態(tài)Si，即負載大小的變換狀態(tài)，i與數(shù)據(jù)包長度L之間的計算方法如式（1）所示：

從如上關(guān)系看出，狀態(tài)集合一共包含10個狀態(tài)元素。狀態(tài)轉(zhuǎn)換矩陣P用于記錄，TCP流在時間上相鄰的前pkt_cnt_max個帶負載包，包間狀態(tài)轉(zhuǎn)換關(guān)系計算算法如下：

Input：一條TCP流中，按包到達時間排列的數(shù)據(jù)包長度狀態(tài)序列S[0,1,…,n]

Output：狀態(tài)轉(zhuǎn)換矩陣P，具有10行10列

1 初始化矩陣P的所有項為0，初始化狀態(tài)計數(shù)器cnt[0,1,…,9]=[0,0,…,0]

2 for遍歷S中的元素，在相鄰兩個包的狀態(tài)中，前置狀態(tài)記為si，后置狀態(tài)記為sj：

2.1P[i][j]=P[i][j]+1

2.2cnt[i]=cnt[i]+1

3 for遍歷P中的所有元素，行索引記為i，列索引記為j，計算P[i][j]=P[i][j]/cnt[i]

4 輸出二維矩陣P

對于同類型的網(wǎng)絡(luò)協(xié)議來說，在通信過程中產(chǎn)生的數(shù)據(jù)包長度狀態(tài)轉(zhuǎn)換過程具有相似性，因此，在本方法中采用馬爾科夫鏈的狀態(tài)轉(zhuǎn)換矩陣作為流特征。

在預(yù)處理的最后，對數(shù)據(jù)進行去除值單一的列、標(biāo)準(zhǔn)化及去除強關(guān)聯(lián)特征等處理，形成可用于聚類算法的特征集合。

1.2.2 可讀性分類

在測試過程中發(fā)現(xiàn)，對于某些數(shù)據(jù)而言，在特征預(yù)處理階段和算法聚類階段，采用不同的參數(shù)設(shè)定比統(tǒng)一的參數(shù)設(shè)定的分類效果更好。經(jīng)深入研究，這些數(shù)據(jù)差異符合可讀性分類標(biāo)準(zhǔn)。

可讀性分類是指將TCP流分成可讀數(shù)據(jù)流和不可讀數(shù)據(jù)流兩大類?？勺x數(shù)據(jù)流是能通過肉眼分析，發(fā)現(xiàn)一些協(xié)議規(guī)律的數(shù)據(jù)流。不可讀數(shù)據(jù)流是加密程度較高或其他二進制的數(shù)據(jù)流。

可讀性分類以可打印字符占比和字節(jié)分布熵作為分類依據(jù)。當(dāng)可打印字符占比大于設(shè)定閾值，或字節(jié)分布熵小于設(shè)定閾值時，則為可讀數(shù)據(jù)流，否則為不可讀數(shù)據(jù)流。其中，字節(jié)分布熵是指在特征預(yù)處理時字節(jié)分布統(tǒng)計的基礎(chǔ)上，計算字節(jié)分布對應(yīng)的信息熵。字節(jié)分布熵值越大，代表TCP流負載越?jīng)]有規(guī)律。

可讀性分類不僅能使分類效果更好，同時能降低聚類過程的數(shù)據(jù)規(guī)模，從而提升分類過程的計算性能。

1.2.3 凝聚型層次聚類

層次聚類不直接依賴于k值的設(shè)置進行聚類，這是符合未知協(xié)議在真實網(wǎng)絡(luò)中的情況的。此外，像K-means這類算法的多次運行結(jié)果是無法保證一致的，這使聚類結(jié)果具有不確定性，從而對聚類結(jié)果的后續(xù)處理帶來一定的阻礙。此方法的層次聚類采用凝聚型層次聚類算法，并采用最近鄰鏈（Nearest Neighbor Chain，NNCHAIN）算法[15]來構(gòu)建層次樹，NN-CHAIN算法的時間復(fù)雜度和空間復(fù)雜度均優(yōu)于傳統(tǒng)的層次聚類算法。

樣本點之間的距離計算采用Bray-Curtis距離，樣本i和樣本j之間的距離dij通過式（2）進行計算，n表示樣本的特征維度總數(shù)：

類簇之間的距離計算采用簇平均（Average-Linkage）方法，其中dxz代表類簇ci與cj中兩個點的距離值，對于類簇ci與cj，通過式（3）來計算距離：

基于NN-CHAIN算法的凝聚型層次聚類過程描述如下：

Input：所有的特征化的樣本點

Output：聚類后的類簇

1 把每個樣本歸為一類，計算任意兩個類之間的距離，形成距離矩陣

2 創(chuàng)建一個棧，棧中的元素為當(dāng)前活動的類簇

3循環(huán)處理，直到最終被合并為一個類簇：

3.1 當(dāng)棧為空的時候，從當(dāng)前活動類簇集合中隨機挑選一個放入棧中

3.2 查找與棧頂元素距離最近的類簇，記為C

3.3 若C不在棧中，將C入棧

3.4 若C在棧中，則必然是原棧頂元素的前一個元素，需要將原棧頂元素和C一同出棧并合并為類簇D，將類簇D放入活動類簇集合，然后在活動類簇集合中刪除合并前的兩個元素，最后更新距離矩陣

4根據(jù)步驟3生成的層次樹，使用適當(dāng)?shù)木垲惒呗?，生成結(jié)果類簇

在整個聚類過程中，步驟1的時間復(fù)雜度為O(n2)，步驟3的時間復(fù)雜度為O(n2logn)。相對于傳統(tǒng)的凝聚型層次聚類的時間復(fù)雜度O(n3)，性能提升明顯。在聚類過程中的聚類策略，主要借助不一致系數(shù)inconsistent和類簇距離distance兩個策略。當(dāng)不一致系數(shù)或類簇距離在設(shè)定范圍內(nèi)時，允許在層次樹的相應(yīng)位置進行合并，否則不合并。這兩種策略會得到兩個相互獨立的聚類結(jié)果，需要后續(xù)進行合并處理。

1.2.4 改進的層次聚類算法

在實際的程序運行過程中，由于數(shù)據(jù)樣本的特征維度數(shù)量較大，所以層次聚類算法中的步驟1的實際耗時遠大于步驟3。因此這里考慮對步驟1進行性能優(yōu)化。步驟1的一般實現(xiàn)算法如下：

Input：所有的特征化的樣本點為p[n][m]，樣本數(shù)量為n，特征維度數(shù)量為m

Output：所有樣本點兩兩間距離矩陣為d[n][m]

1 forifrom 0 ton-1：

2 forjfrom 0 ton-1：

3d[i][j]=dist(p[i],p[j],m)

該算法中的dist函數(shù)為Bray-Curtis算法，時間復(fù)雜度為O(m)，所以計算距離矩陣的時間復(fù)雜度為O(n2×m)。由于樣本i與樣本j的距離等價于樣本j與樣本i的距離，所以通過上三角矩陣對內(nèi)存進行壓縮，并去掉主對角線，可以減少一半的內(nèi)存占用與一半的計算量。壓縮后的距離矩陣用數(shù)組a[n×(n-1)/2]表示。從矩陣d的索引（i為行索引，j為列索引）到數(shù)組a的索引k映射關(guān)系如式（4）所示：

將上式中i≤j的情況，把j假設(shè)為n-1，反解關(guān)于i的一元二次方程，得到式（5）：

借助式（5），得到從數(shù)組a的索引k到矩陣d的索引i和j的映射關(guān)系如式（6）和式（7）所示：

分析計算距離矩陣的傳統(tǒng)算法得出，計算距離矩陣中的各個元素的過程互不影響，故可將計算過程拆分為多個計算任務(wù)進行獨立處理。通過壓縮矩陣索引的正向和反向映射關(guān)系，對原算法進行多線程優(yōu)化，發(fā)揮現(xiàn)代計算機的多核優(yōu)勢。對于壓縮后的矩陣，即數(shù)組a，按block_size（分塊大?。?shù)據(jù)進行分塊，每個塊就是多線程任務(wù)隊列中的一個任務(wù)，由線程池中的多個線程對任務(wù)隊列中的計算任務(wù)進行處理，如圖2所示。

Bray-Curtis算法使用大量的數(shù)值計算指令，除循環(huán)條件判斷外，沒有其他分支語句。這樣的算法特點可以發(fā)揮出單指令流多數(shù)據(jù)流（Single Instruction Multiple Data，SIMD）系列[16]指令的性能優(yōu)勢，因此，除使用多線程對距離計算進行加速外，還能使用SIMD技術(shù)對Bray-Curtis算法加速。

1.2.5 類簇調(diào)整算法

對于TCP流量來說，相同的目的IP和目的端口，同屬相同的網(wǎng)絡(luò)服務(wù)，因此具有相同的目的IP和目的端口的TCP流，使用相同的應(yīng)用協(xié)議進行通信[10]。基于該結(jié)論對類簇進行調(diào)整。將所有樣本構(gòu)成的集合表示為A={a1,a2,…,an}。

對于具有相同二元組的（即目的IP和目的端口）TCP流，直接作為一個相同的類別。所有類別的集合表示為T={t1,t2,…,tn}。其中ti為一個獨立的類別，表示為ti={b|所有樣本b具有相同的二元組}，且ti與任意不同于ti的tj滿足ti∩tj=?,ti∈T,tj∈T,i≠j，集合T與集合A應(yīng)滿足∪ti=A,ti∈T。經(jīng)過聚類得到的類簇集合表示為C={c1,c2,…,cn}，其中ci為一個獨立的類簇，且ciA,ci∈C。

類簇調(diào)整算法（Cluster Adjustment Algorithm，CAA）具體描述如下：

Input：基于二元組的類別集合T，聚類得到類簇集合C，調(diào)整閾值h_thre和m_threOutput：調(diào)整后的類別集合R

1 forEachtiinT：

2 集合H=ti在集合C所有元素的交集中，元素最多的那個交集（記為ti與ck的交集）

3 forEachcjinC：

4 if |ti∩cj|＜|H|×h_thre，則 將ti與cj交集中的元素由集合cj移動到集合ck中

5 else if |ti∩cj|＜|ti|×m_thre，則將ti與cj交集中的元素由集合cj移動到集合ck中

6 else 不移動

7 結(jié)果類別集合R=處理后的集合C

在此算法中，調(diào)整閾值h_thre和m_thre對結(jié)果的影響較大，通過調(diào)節(jié)這兩個參數(shù)能減少最終分類結(jié)果的錯誤率。

1.2.6 類簇合并算法

聚類過程產(chǎn)生的多策略聚類結(jié)果，需要合并在一起，合并后的結(jié)果經(jīng)過CAA處理后，需要再次與二元組進行合并得到本方法的分類結(jié)果。類簇合并算法（Cluster Merging Algorithm，CMA）具體描述如下：

Input：類別集合A={a1,a2,…,an}，ai代表一個獨立的類別，為一個樣本集合；類別集合B={b1,b2,…,bn}，bj代表一個獨立的類別，為一個樣本集合

Output：合并后的類別集合D={d1,d2,…,dn}，dk代表一個獨立的類別，為一個樣本集合

1p=0

2 for 遍歷集合A中所有元素ai：

3p=p+1

4 將一個空集加入集合D中，記為dp

5 調(diào)用子算法fm(ai,A,B,D,p)，子算法定義如下：

6 初始化集合G為空集

7 for 遍歷集合ai中的所有元素air，且air不在集合D所有元素的并集集合中：

8 元素air加入集合dp中

9 在集合B中查找樣本元素air所在的集合bj，并將bj加入集合G

10 for 遍歷集合G中的元素gs：

11 遞歸調(diào)用子算法fm(gs,A,B,D,p)

12 輸出集合D

2 實驗結(jié)果分析

對本方法的結(jié)果評估主要考慮借助已知協(xié)議數(shù)據(jù)來模擬未知協(xié)議的方式。

2.1 評估方法

為了對分類結(jié)果進行合理的評估，本方法提出了準(zhǔn)確率和聚集度兩個評估維度。

2.1.1 準(zhǔn)確率

在分類結(jié)果中，結(jié)果類別沒有被標(biāo)記為特定協(xié)議的類別標(biāo)簽，因此無法使用簡單的方法直接計算分類結(jié)果的準(zhǔn)確率。這里定義一個對已知流量實驗的準(zhǔn)確率計算方法。將某一結(jié)果類別中，實際協(xié)議類別樣本數(shù)量最多的協(xié)議類別作為結(jié)果類別的協(xié)議標(biāo)記。將此結(jié)果類別中樣本實際協(xié)議與此協(xié)議標(biāo)記一致的樣本量，與此結(jié)果類別樣本總量的比值作為此結(jié)果類別的準(zhǔn)確率。如在分類后的眾多結(jié)果類別中，其中某個結(jié)果類別ci，包含m種不同實際協(xié)議的樣本，這m種不同實際協(xié)議的樣本數(shù)量分別為w1,w2,…,wm，其中的最大值為wj，wj對應(yīng)的實際協(xié)議為pj，則結(jié)果類別ci被看作實際協(xié)議pj的類別，即類別ci中實際協(xié)議為協(xié)議pj的樣本被認(rèn)為分類正確的樣本，類別ci的分類準(zhǔn)確率計算方法如式（8）所示：

分類結(jié)果的整體C={c1,c2,…,cn}的準(zhǔn)確率計算方法如式（9）所示：

經(jīng)分析可知，準(zhǔn)確率的取值范圍為[0,100%]，且越接近100%分類效果越好。

2.1.2 聚集度

僅根據(jù)上面定義的準(zhǔn)確率來評估分類結(jié)果，無法對下面的情況進行合理評估：當(dāng)實際為同類型協(xié)議pj的樣本被分到不同的n個結(jié)果類別中時，這些結(jié)果類別中的實際協(xié)議pj的樣本量分別為u1,u2,…,un，此時按準(zhǔn)確率進行評估，會發(fā)現(xiàn)當(dāng)n=1時與n=10時的分類結(jié)果的準(zhǔn)確率是相同的，但實際上，n=1時的分類效果優(yōu)于n=10時的分類效果。因此定義了聚集度來體現(xiàn)這一差異，借助信息熵來定義協(xié)議pj的聚集度，計算方法如式（10）所示：

對所有協(xié)議P={p1,p2,…,pn}，在分類結(jié)果中的聚集度計算方法如式（11）所示：

經(jīng)分析可知，聚集度的取值范圍為[0,+∞]，且越接近0分類效果越好。

準(zhǔn)確率體現(xiàn)的是被分到同一個類別中的樣本實際上也是同一個類別的程度，聚集度體現(xiàn)的是實際為同類型協(xié)議的樣本在結(jié)果類別中被聚集在一起的程度。

2.2 結(jié)果分析

本文采用的數(shù)據(jù)，在多種真實的網(wǎng)絡(luò)環(huán)境出口處抓取獲得。去掉其中占比極高的超文本傳輸協(xié)議（HyperText Transfer Protocol，HTTP）數(shù)據(jù)和傳輸層安全協(xié)議（Transport Layer Security，TLS）數(shù)據(jù)。經(jīng)過預(yù)處理后共計得到97460條TCP流，包含19種不同的應(yīng)用協(xié)議，其中包括比特流協(xié)議（BitTorrent，BT）、簡單郵件傳輸協(xié)議（Simple Mail Transfer Protocol，SMTP）、簡 單 郵 件 傳 輸加密協(xié)議（Simple Mail Transfer Protocol Transport Layer Security，SMTP_TLS）、可擴展通訊和表示協(xié) 議（Extensible Messaging and Presence Protocol，XMPP）、Telnet遠程終端協(xié)議、簡單對象訪問協(xié)議（Simple Object Access Protocol，SOAP）、郵局協(xié)議（Post Office Protocol，POP）、安全外殼協(xié)議（Secure Shell，SSH）、文件傳輸協(xié)議（File Transfer Protocol，F(xiàn)TP）、交互郵件訪問協(xié)議（Internet Message Access Protocol，IMAP）、Mysql數(shù)據(jù)庫協(xié)議、實時消息傳輸協(xié)議（Real Time Messaging Protocol，RTMP）、微信應(yīng)用協(xié)議、基于HTTP的自適應(yīng)碼率流媒體傳輸協(xié)議（HTTP Live Streaming，HLS）、WebSocket網(wǎng)絡(luò)傳輸協(xié)議、文件傳輸協(xié)議（File Transfer Protocol Data，F(xiàn)TP-DATA）、SOCKS4代理協(xié)議、SOCKS5代理協(xié)議、遠程顯示協(xié)議（Remote Display Protocol，RDP）。在這些協(xié)議中，SMTP、POP、IMAP、Telnet、XMPP、RTMP等屬于非加密協(xié)議，BT、SOCKS4/5、微信協(xié)議、RDP、FTP-DATA則屬于加密協(xié)議。不可讀數(shù)據(jù)流具有424個特征維度，可讀數(shù)據(jù)流具有416個特征維度，下面分別對不可讀數(shù)據(jù)流和可讀數(shù)據(jù)流（加密流）進行分析。

測試環(huán)境說明：Intel(R) Xeon(R) Silver 4214 CPU @ 2.20GHz，Cent OS 7.2 x64。

如表1所示，不可讀數(shù)據(jù)流（加密流）的分類準(zhǔn)確率為96.78%，聚集度為1.23，說明本模型針對加密流量具有較好的分類效果。其中總計的標(biāo)簽數(shù)量并非其他協(xié)議標(biāo)簽數(shù)量的累加，因為在分類結(jié)果中協(xié)議之間存在混合在一起的情況。在運行聚類算法、CAA和CMA的過程中，耗時24秒，其中CAA和CMA僅耗時0.5秒。在計算耗時方面，聚類算法遠大于其他算法。

表1 不可讀數(shù)據(jù)流的分類結(jié)果

如表2所示，可讀數(shù)據(jù)流的分類準(zhǔn)確率為99.81%，聚集度為0.25，說明本方法對明文流量也具有較好的分類效果。在運行聚類算法、CAA和CMA的過程中，耗時151秒。對比不可讀數(shù)據(jù)流和可讀數(shù)據(jù)流分類結(jié)果發(fā)現(xiàn)，可讀數(shù)據(jù)流的分類結(jié)果無論是準(zhǔn)確率還是聚集度，都明顯優(yōu)于不可讀數(shù)據(jù)流的分類結(jié)果。原因在于，不可讀數(shù)據(jù)流在負載方面的特征對協(xié)議的區(qū)分度遠低于可讀數(shù)據(jù)流。

表2 可讀數(shù)據(jù)流的分類結(jié)果

BT和FTP-DATA這類協(xié)議的負載與其傳輸文件有著密切的聯(lián)系，當(dāng)傳輸文件為加密文件或其他二進制文件時，會被作為不可讀數(shù)據(jù)流；當(dāng)傳輸文件為文本文件時，會被作為可讀數(shù)據(jù)流。這類協(xié)議在特征上的變化也比較多，使其分類結(jié)果的聚集度偏高。與之相反，RDP、FTP、MySQL等協(xié)議在特征的表現(xiàn)比較固定，使其分類結(jié)果的聚集度更低，效果更好。從以上結(jié)果可以看出，本模型針對已知協(xié)議和未知協(xié)議（包括加密協(xié)議）流量均具有較好的分類效果，并且過程中不需要預(yù)先確定聚類中心點，不依賴原始樣本數(shù)據(jù)進行標(biāo)記學(xué)習(xí)，也能應(yīng)對新出現(xiàn)的未知協(xié)議類型，具有普適性；同時算法經(jīng)過多種策略調(diào)整，在準(zhǔn)確率和聚集度上均能達到較好效果。

2.3 多策略效果分析

2.3.1 可讀性策略分析

如表3所示，綜合上述不可讀數(shù)據(jù)流和可讀數(shù)據(jù)流的整體分類結(jié)果：準(zhǔn)確率為98.96%，聚集度為0.53，耗時175秒。在不使用可讀性分類的整體結(jié)果：準(zhǔn)確率為98.94%，聚集度為0.88，在運行聚類算法、CAA和CMA的過程中，耗時313秒。對比可知，經(jīng)過可讀性分類，分類結(jié)果的準(zhǔn)確率和聚集度均有提升，計算性能也有較大提升。此外，可讀性分類在某些數(shù)據(jù)集中會對結(jié)果帶來更大的提升。

表3 采用與不采用可讀性分類的效果對比

2.3.2 CAA與CMA策略分析

對27392個不可讀數(shù)據(jù)流進行對比測試，如表4所示，無論單獨使用哪一種聚類策略，其分類結(jié)果的準(zhǔn)確率和聚集度都比不上采用CAA與CMA策略的準(zhǔn)確率和聚集度。CAA與CMA可以規(guī)避單一策略的缺點，充分發(fā)揮各種策略的優(yōu)勢，從而使分類結(jié)果達到更優(yōu)的效果。

表4 是否采用CAA與CMA的分類效果對比

2.3.3 計算策略性能分析

聚類算法是整個過程中最耗時的部分，在本方法中，聚類計算性能優(yōu)化通過單線程和多線程實現(xiàn)，并將其與scipy.cluster.hierarchy.linkage（Python層次聚類函數(shù)）進行對比。如圖3所示，使用單指令多數(shù)據(jù)流（Single Instruction Multiple Data，SIMD）技術(shù)優(yōu)化后的算法（對應(yīng)單線程的曲線），比Python軟件包庫中的算法實現(xiàn)速度提升了近一倍。再使用多線程對算法進行加速，速度約為scipy庫中的算法實現(xiàn)的8倍。

3 結(jié) 語

本文將層次聚類運用于未知協(xié)議的分類中，提出了一種基于層次聚類的多策略未知協(xié)議分類方法。借助馬爾科夫鏈來強化特征的表征能力。使用可讀性分類機制提升分類效果和計算性能。利用最近鄰鏈算法、SIMD技術(shù)與多核技術(shù)加速本方法的計算速度。將CAA和CMA引入到本方法中，規(guī)避了單一聚類策略帶來的弊端，發(fā)揮出了多種聚類策略的優(yōu)勢，提升了分類效果。最后提出了使用已知協(xié)議數(shù)據(jù)集合模擬未知協(xié)議數(shù)據(jù)集合的結(jié)果評估方法。實驗結(jié)果表明，與原始的層次聚類算法相比，本分類方法的分類效果更優(yōu)，且計算速度更快。

本文使用真實網(wǎng)絡(luò)數(shù)據(jù)進行測試，無須對數(shù)據(jù)進行前提假設(shè)和設(shè)置要求，此方法能適用于各種現(xiàn)實網(wǎng)絡(luò)中，較為通用，具有極強的工程應(yīng)用能力。