基于K-means 和AGNES 的未知二進制協(xié)議聚類*

尹世莊，王 韜，陳慶超，劉麗君，閻韶林

（1.陸軍工程大學石家莊校區(qū)，石家莊 050003；2.陸軍工程大學，南京 210000）

0 引言

網(wǎng)絡協(xié)議識別與分析的主要對象是網(wǎng)絡中傳輸?shù)谋忍亓鲾?shù)據(jù)。對于已知協(xié)議識別，通常以比特流中包含的協(xié)議類型、端口、長度、方向及特殊字段等為特征參數(shù)，基于模式匹配［1］、機器學習［2］等方法實現(xiàn)。對于未知二進制協(xié)議比特流，如何對其進行有效地區(qū)分，是網(wǎng)絡協(xié)議識別與分析中亟待解決的問題。在比特流中包含較多未知協(xié)議的情況下，單純使用已知協(xié)議識別方法對所有比特流的協(xié)議屬性進行判別，存在著執(zhí)行效率低下的問題。同文本協(xié)議相比，二進制協(xié)議在協(xié)議逆向處理上一個比較重要的特點是格式固定且多位置對齊。由于二進制協(xié)議傳輸效率高，因而在網(wǎng)絡中的應用也越來越廣泛，并且因為真實網(wǎng)絡中未知協(xié)議數(shù)據(jù)構(gòu)成非常復雜，所以對未知二進制協(xié)議進行有效地聚類，將具有相似協(xié)議屬性的二進制協(xié)議劃分到相應集合中，是提高網(wǎng)絡協(xié)議分析效率、進行未知協(xié)議格式分析的基礎。

1 國內(nèi)外研究現(xiàn)狀

比特流中已知協(xié)議的特征主要表現(xiàn)為協(xié)議類型、端口、長度、方向及特征字段等。目前大多采用基于端口，基于內(nèi)容和基于行為的協(xié)議識別技術。但是隨著網(wǎng)絡的速度加快，人們又從流量特征這一方面對協(xié)議進行分類和識別，主要適用于流量特征明顯的協(xié)議［3-4］。但是隨著大數(shù)據(jù)和深度學習的興起，基于隱馬爾可夫模型和基于正則表達式成為了新的研究方向［5］。

目前針對未知二進制協(xié)議分類的研究還比較少，大多數(shù)是面向比特流的未知協(xié)議分類。對于比特流協(xié)議數(shù)據(jù)先經(jīng)過幀切分，生成比特流協(xié)議數(shù)據(jù)幀，可采用提取前導碼與關聯(lián)規(guī)則相結(jié)合方式［6］，然后通過多協(xié)議識別模型將多協(xié)議數(shù)據(jù)幀分離成不同單協(xié)議的數(shù)據(jù)幀集合［7］。張俊嬌［8］引入特征序列位置信息作為協(xié)議特征提取的約束條件，將特征序列及其位置信息構(gòu)成二維的復合特征，解決了特征字符串重復性的問題。陽水橋［9］基于K-means 提出了受限K-means 聚類方法，采用地址和端口號進行輔助聚類，從而更加準確地分類不同類別的網(wǎng)絡流數(shù)據(jù)。陶思宇［10］在層次聚類中引入輪廓系數(shù)確定二進制幀的最優(yōu)聚類數(shù)，提出了一種改進的多序列比對算法。以上研究成果可為未知協(xié)議比特流特征參數(shù)的選擇和提取提供一定的借鑒。

二進制協(xié)議格式固定且多位置對齊。復雜度相較于其他協(xié)議來說較低，而K-means 算法雖然存在聚類參數(shù)k 選擇困難等局限性，但由于其具有較低的實現(xiàn)復雜度，被廣泛用于大型數(shù)據(jù)集的聚類。AGNES 算法在聚類過程中聚類距離可以采用漢明距離和pearson 相關性距離，能夠更好地反映二進制協(xié)議比特流之間的相關程度。在未知二進制協(xié)議聚類的過程中，將主要采用K-means 算法和AGNES 算法進行聚類。

2 未知二進制協(xié)議聚類

2.1 實現(xiàn)方案

為實現(xiàn)對未知二進制協(xié)議的高效聚類，提出一種基于K-means 聚類和AGNES 算法的未知二進制協(xié)議聚類方法。協(xié)議是否已知并不影響聚類的準確度，為了更好地檢驗聚類效果，所以采用已知二進制協(xié)議代替未知協(xié)議。并且研究對象是已經(jīng)做了初步切分，協(xié)議頭部位置確定的比特流（以下均稱為未知二進制協(xié)議比特流）。首先對數(shù)據(jù)進行預處理，針對二進制協(xié)議的特性，選取了4 bit 作為處理單位；處理數(shù)據(jù)時采用最短數(shù)據(jù)作為依據(jù)進行切割；將每一個單位作為一個特征得到一個n×m 的二維矩陣。再采用K-means 算法對其進行聚類分析，獲得聚類的評估函數(shù)值，后用來確定聚類的k 值。然后采用確定k 值的K-means 和Agnes 算法對數(shù)據(jù)進行聚類，將未知二進制協(xié)議劃分為二進制協(xié)議子集。在Agnes 算法中采用PEARSON 相關性距離作為度量，通過這些改進來提高聚類精度。

圖1 比特流聚類與篩除實現(xiàn)方案

2.2 數(shù)據(jù)預處理

數(shù)據(jù)預處理階段首先將從wireshark 中抓包得到的.Pacp 格式包另存為txt 格式，并且去除協(xié)議頭部的多余數(shù)據(jù)，然后以4 bit 為單位進行處理。比如111111110011 轉(zhuǎn)換為ff3 和15153，f、f、3 和15、15、3 為處理單元。將輸入的數(shù)據(jù)幀構(gòu)成一個n×m 的二維矩陣。n 為所輸入的數(shù)據(jù)幀的行數(shù)，m 為所截取的數(shù)據(jù)幀的前m 個處理單元［12］：

生成一個m×n 的矩陣，其中n 為協(xié)議的總條數(shù)，因為二進制協(xié)議的頭部比較短，因而太多的數(shù)據(jù)量會增加時間開銷，所以每種協(xié)議取150 條。由于協(xié)議長度未知，為了更好地保留協(xié)議信息，同時有效地去除數(shù)據(jù)部分內(nèi)容。M 值的確定以最小m 值為準，首先確定每種協(xié)議的最短比特流長度，然后以所有協(xié)議中最短協(xié)議的長度作為m 值。

數(shù)據(jù)預處理算法參數(shù)：m（指定取數(shù)據(jù)幀的前m 個處理單元）輸入：n 條數(shù)據(jù)幀輸出：n 行，m 列的二維矩陣步驟：1.針對不同的協(xié)議幀，去除其多余的頭部數(shù)據(jù)。2.計算輸入數(shù)據(jù)幀的條數(shù)，將其值賦予n；初始化n行m 列的二維數(shù)組，記為a［n］［m］；3. for 循環(huán)遍歷每條數(shù)據(jù)幀4. 將數(shù)據(jù)幀按4 個bit 分割為m 個字節(jié)5. 分別將每個字節(jié)賦給矩陣對應行的每個元素6. 輸出二維矩陣，并存儲到txt 文檔。

2.3 基于K-means 算法的比特流聚類

在數(shù)據(jù)預處理的基礎上，采用K-means 算法對實驗數(shù)據(jù)集中的比特流進行了聚類分析，對聚類參數(shù)k 分別取2～9，輸出聚類結(jié)果和對應k 值下的輪廓系數(shù)S、誤差平方和sse 和Calinski-Harabasz 分數(shù)值ch。

輪廓系數(shù)適用于實際類別信息未知的情況。對于單個樣本，設a 是它與同類別中其他樣本的平均距離，b 是與它距離最近不同類別中樣本的平均距離，則輪廓系數(shù)S 為：

Calinski-Harabasz 分數(shù)值ch 越大則聚類效果越好。設m 為訓練樣本數(shù)，k 為類別數(shù)。Bk 為類別間協(xié)方差矩陣，Wk 為類別內(nèi)部的協(xié)方差矩陣。Tr 為矩陣的秩。其公式為：

SSE（sum of the squared errors，誤差平方和）其中，Ci是第i 個簇，p 是Ci中的樣本點，mi是Ci的質(zhì)心（Ci中所有樣本的均值），SSE 是所有樣本的聚類誤差，代表了聚類效果的好壞。

聚類過程的偽代碼：

K-means 算法輸入：n 行，m 列的二維矩陣；輸出：k 個類簇，與之相對應的s、ch 和sse 的值步驟：1.從n 個樣本中隨機選擇k 個樣本作為初始聚類中心。2.for i=1 to n：3.計算樣本xi 與各聚類中心的距離D（D 為歐式距離），將數(shù)據(jù)幀xi 劃分到距離最近的類簇中。4.按公式images/BZ_130_1541_878_1830_987.png計算誤差平方和E 5.for j=1 to k:6.計算新的聚類中心7.重新計算誤差平方和E*8.比較E 和E*的差的絕對值，若小于閾值則轉(zhuǎn)到步驟9，否則轉(zhuǎn)到步驟2；9.輸出K 個類簇。10.計算與k 相對應的s 值和ch 值11.輸出K 、s、ch、sse。

2.4 確定k 值的AGNES 聚類

由輪廓系數(shù)S、Calinski-Harabasz 分數(shù)值ch 及誤差平方和sse 的公式可知，隨著聚類數(shù)k 的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那么誤差平方和SSE 自然會逐漸變小，k 值增大的前期s 值和ch 值會逐漸增大，并且當k 小于真實聚類數(shù)時，由于k 的增大會大幅增加每個簇的聚合程度，故下降和上升的幅度會很大，而當k 到達真實聚類數(shù)時，再增加k 所得到的聚合程度回報會迅速變小，所以幅度會驟減，然后隨著k 值的繼續(xù)增大而趨于平緩，而這個時候?qū)膋 值就是數(shù)據(jù)的真實聚類數(shù)。

為了更好地確定k 值，定義i 點的斜率變化率為該點的斜率值減去上一點的斜率值，同時為了方便比較將3 種不同評價參數(shù)的斜率變化值進行歸一化處理。

為了提高精度，假定當3 種參數(shù)的變化率均大于斜率變化平均值（通過實驗獲得，太小沒有區(qū)分度，太大3 種參數(shù)沒有同時符合標準的k 值）時該點作為備選點，同時由于在實驗中取了36 個特征，為了防止出現(xiàn)聚類粒度過細的現(xiàn)象，取備選點里面第一個點作為k 值。

指定聚類個數(shù)為k，進行AGNES 聚類，由于相關性距離更能反映數(shù)據(jù)幀之間的差異，所以類內(nèi)距離采用PEARSON 相關性距離。

AGNES（AGglomerative NESting）算法輸入：樣本集D={x1，x2，…，xn}；距離度量d；聚類個數(shù)k。輸出：k 個類簇步驟：1. for i=1 to n：2. Ci={xi}#初始化單樣本聚類簇3. end for 4. for i=1 to n：5. for i=1 to n：6. Mij=D（ci，cj）7. Mij=Mji 8. end for#初始化距離9. 設置當前簇個數(shù)q=m 10. while q＞k:11. 找到最相似的兩個簇，合并最相似的兩個簇12. 將聚類簇重新編號，刪除相對應的距離矩陣的行和列13. q=q-1 14. end while 15. 輸出K 個類簇。

3 實驗結(jié)果與分析

實驗數(shù)據(jù)集由真實的網(wǎng)絡環(huán)境獲取，用ARP、DNS、ICMP、TCP 和SMB 代表5 種未知二進制協(xié)議比特流子集，文中分別用P1、P2、P3、P4和P5表示。每種協(xié)議取150 條。假定所有協(xié)議做了初步切分，均從對應協(xié)議頭部開始并且包含數(shù)據(jù)部分。取所有報文中最短長度144 bit 作為m 值。

3.1 聚類個數(shù)k 提取結(jié)果與分析

對K-means 算法中的k 值進行調(diào)整，將聚類數(shù)設置為2～9，通過不同的k 值，分別記錄對應的s、ch、sse 值。得到的結(jié)果如圖2～圖4 所示。

圖2 輪廓系數(shù)s 隨k 值變化情況

輪廓系數(shù)取值范圍是［-1，1］，同類別樣本距離相近且不同類別樣本距離越遠，s 值越大。對于Calinski-Harabasz 分數(shù)值，類別內(nèi)部數(shù)據(jù)的協(xié)方差越小，類別之間的協(xié)方差越大，Calinski-Harabasz 分數(shù)越高。

圖3 Calinski-Harabasz 分數(shù)值ch 隨k 值變化情況

圖4 誤差平方和sse 隨k 值變化情況

通過對比3 種參數(shù)的變化，發(fā)現(xiàn)在k=5 和k=8的時候s 值、sse 值和ch 值均發(fā)生了較大的變化，斜率變化率均大于平均值，但由于k=5 是第一個出現(xiàn)的k 值，故對于這個數(shù)據(jù)集而言，最佳聚類數(shù)為5。同時，也將k=8 作為對比項，進行下一步實驗。

3.2 基于K-means 算法的聚類結(jié)果與分析

在確定好k 值的基礎上，采用K-means 算法對實驗數(shù)據(jù)集中的比特流進行了聚類分析，在取聚類參數(shù)k 為5 的情況下，獲得了較為準確的聚類結(jié)果，如下頁圖5 所示。為了驗證在上一步中k 取5是合理的，另取聚類參數(shù)k 為8 的情況下，得到的聚類結(jié)果如下頁表1 所示。

表1 中數(shù)據(jù)表示聚類后每一種協(xié)議所包含的報文條數(shù)，圖5 中x 軸是協(xié)議編號，y 軸是協(xié)議種類，反映的是協(xié)議種類隨編號的分布情況。在數(shù)據(jù)預處理的過程中由于是將已知二進制協(xié)議充當未知二進制協(xié)議，并且聚類中心是隨機選取的，不影響最后結(jié)果。為了統(tǒng)計方便將5 種協(xié)議按順序排列。通過圖表可以看出聚類效果較好，各類數(shù)據(jù)都能有效區(qū)分，但是在第3 類中仍有28 條協(xié)議被劃分到了第4 類。

圖5 k=5 聚類結(jié)果分布圖

表1 k=5 和k=8 聚類結(jié)果

當k=8 時結(jié)果如圖6 所示，可以看到新增加的3 類大部分分布在在第4 類協(xié)議中，也就是TCP 協(xié)議中，通過研究具體TCP 協(xié)議聚類結(jié)果，發(fā)現(xiàn)，由于tcp 協(xié)議報文內(nèi)部格式差異較大，當k 值較大時，造成了分類粒度過細。

圖6 k=8 聚類結(jié)果分布圖

3.3 基于AGNES 聚類結(jié)果與分析

在聚類過程中，設定方法為中位數(shù)聚類法，度量標準采用PEARSON 相關性距離，聚類數(shù)指定為5，對750 條協(xié)議報文進行聚類，聚類的結(jié)果如圖7所示。

圖7 AGNES 聚類結(jié)果樹狀圖

圖7 中x 軸是協(xié)議編號，y 軸是聚類距離參數(shù)，反映的是在不同距離參數(shù)情況下協(xié)議的聚類情況。

當k=5 時，聚類結(jié)果如圖8 所示，AGNES 算法將5 種協(xié)議較好地區(qū)分開，其中有10 條p3 協(xié)議被劃分到了p4 類。

顯效：患者的臨床癥狀和體征緩解50%以上，尿微量白蛋白下降50%以上或是恢復正常水平。有效：臨床癥狀和體征緩解30%～50%，尿微量白蛋白下降30%～50%。無效：不符合上述標準者。

圖8 k=5 AGNES 聚類結(jié)果分布圖

3.4 聚類結(jié)果與傳統(tǒng)K-means 對比分析

在相同的k 值下通過準確率、識別率、誤識別率來比較兩種方法的聚類結(jié)果。

準確率Acc：表示用某種算法進行聚類操作時，正確分類的協(xié)議數(shù)量占協(xié)議總數(shù)的比例，具體計算如式（5）所示。

其中，Count（Corr_frame）表示正確分類的數(shù)據(jù)幀數(shù)量，Count（total_frame）表示所有的數(shù)據(jù)幀。

識別率TP：表示用某種算法進行聚類操作時，屬于類別X 的數(shù)據(jù)幀被正確分給X 的比例，具體計算方法如式（6）所示。

其中，Count（corr_X）表示類別X 的數(shù)據(jù)幀正確分給X 的數(shù)量，Count（total_X）表示屬于類別X 中的數(shù)據(jù)幀總數(shù)。

誤識別率FP：表示用某種算法進行聚類操作時，不屬于類別X 的數(shù)據(jù)幀被分給X 的比例，具體計算方法如式（7）所示。

表2 k=5 時K-means 和AGNES 聚類結(jié)果對比

以P1～P5 這5 種協(xié)議種類為橫坐標，畫出兩種不同算法下的TP 值和FP 值折線圖。如圖9、圖10所示。

圖9 兩種算法協(xié)議聚類效果TP 比較

圖10 兩種算法協(xié)議聚類效果FP

通過對比發(fā)現(xiàn)K-means 算法比AGNES 算法運算速度快，但是聚類結(jié)果較差。從理論上分析是由于K-means 的時間復雜度小于AGNES，所以運算速度優(yōu)于AGNES；但在聚類過程中K-means 采用的是歐式距離，而AGNES 采用的是PEARSON 相關性距離，更符合二進制協(xié)議的特性，所以精確度不如AGNES。

在未知二進制協(xié)議聚類過程中，由于K-means算法時間復雜度低，首先設定不同k 值采用K-means 聚類方法對協(xié)議報文進行聚類分析，然后通過評價函數(shù)確定k 值，再指定聚類個數(shù)為k，進行AGNES 聚類。通過不同k 值的K-means 聚類可以發(fā)現(xiàn)在某種程度上k 值反映了聚類的粒度。k 值越大，聚類粒度越細。

4 結(jié)論

為解決先驗知識不足條件下的未知二進制協(xié)議聚類問題，在數(shù)據(jù)預處理的基礎上，采用能夠快速獲得聚類結(jié)果的K-means 算法對原始比特流集合進行聚類分析，通過聚類的評估函數(shù)值后用來確定聚類的k 值。然后采用確定k 值的K-means 和Agnes 算法對數(shù)據(jù)進行聚類，將未知二進制協(xié)議比特流劃分為二進制協(xié)議子集。通過最后結(jié)果比較可以確定先通過K-means 確定k 值再通過Agnes 進行最終聚類，可以在保證精度的基礎上提高運算速度，并且對數(shù)據(jù)進行預處理和改進參數(shù)可以使模型更好地適應未知二進制協(xié)議的聚類。

提出的方法在完成未知二進制協(xié)議聚類的基礎上，能夠較快地計算出聚類結(jié)果。聚類距離的選擇對二進制協(xié)議這一特殊對象有較大的影響，對K-means 算法進行改進從而使其提高其聚類精度將會是一個新的研究方向。