面向私有二進制協議的報文聚類方法

徐旭東，張志祥，張 獻

海軍工程大學 電子工程學院，武漢430033

1 引言

協議逆向工程[1]是對未知協議的報文數據或處理這些報文的指令序列進行分析，以獲取該協議的格式規范、報文語義或行為規范。協議逆向工程在漏洞挖掘[2]、入侵檢測[3]等領域有重要作用。

在網絡環境下，通常存在多種協議所生成的報文數據，而不僅僅是單一的報文數據，而協議逆向工程在如此多種的協議報文數據下是不利于開展的，因此在進行協議逆向工作之前需要對報文數據進行聚類，以便對同一類的報文數據進行處理。報文聚類算法針對的協議主要有文本類協議[4]和二進制協議[5]，文本類協議目前有比較成熟的解決方案，如PI[6]和Discover[7]以及之后的改進方案。

對于二進制協議，從數據預處理和聚類方法兩方面分析。黃笑言等[8]基于字節熵矢量加權指紋的二進制協議識別，在數據預處理階段，通過不同字節對協議識別的貢獻不同，設定權值并加權構造字節熵矢量；在聚類階段，使用基于局部加權K-means 算法進行聚類。岳旸等[9]在數據預處理階段使用AC 算法挖掘出頻繁序列特征，使用Apriori 算法搜索頻繁序列的關聯關系；在聚類階段，通過改進的K-means算法進行聚類。Tao 等[10]在數據預處理階段，直接將原始二進制報文作為初始報文向量；在聚類階段，使用了引入輪廓系數（silhouette coefficient）的K-means算法進行二進制報文聚類。閆小勇[11]在數據預處理階段，對二進制報文進行截取或補0 的預處理方式，將不等長的二進制報文變為等長的；在聚類階段，使用距離指數加權的方法自動選取聚類中心，使用密度峰值聚類算法進行聚類。

上述方法大部分針對文本類協議，部分支持二進制協議的聚類方法在數據預處理階段會存在特征提取不純，聚類階段存在簇數不確定等問題。主要原因有兩點：（1）二進制協議報文根據使用的場景及目的，會設計出各種不同長度的二進制報文格式，甚至存在同一報文根據不同場景設計不同的變長域，導致同一類型的二進制報文也會存在不同長度的情況；（2）二進制報文是由0 和1 組成的，字段劃分以比特為單位，并非傳統以字節為劃分的文本類協議。這對于二進制報文的聚類是一個很大的挑戰。

通過對文獻[11]中使用的聚類方法進行分析，發現文中在進行二進制報文的向量化過程中，針對不同長度的二進制報文進行預處理，會采用截斷末尾序列，或是對末尾序列補0 的方式，使處理后的二進制報文達到等長的效果，進而進行向量化映射，進行報文聚類。但是其在對二進制報文進行預處理的過程中，會引入一些無關緊要的噪音，這些噪音本文將其定義為序列噪音。這些序列噪音不僅會干擾報文聚類的效果，而且在報文聚類過程中會引起計算量增加，效率降低的結果。

同時，傳統的聚類方法在聚類的過程中會存在聚類中心不確定，聚類簇數不確定的問題。本文針對上述問題，（1）提出一種序列項-位置矩陣的頻繁項生成方法，根據設置的頻繁項支持度閾值挖掘出頻繁項；（2）根據生成的頻繁項，將二進制報文序列進行向量化的表示；（3）為避免聚類簇數和聚類中心的設定，使用層次聚類[12]中的分拆式層次聚類，對報文的特征向量進行聚類操作，同時使用輪廓系數指導聚類劃分，設定輪廓系數閾值，以達到更好的聚類效果。

2 方法概述

二進制報文序列在聚類之前首先要將序列進行特征向量化表示，在進行特征的向量化表示時，首先要進行頻繁項的提取，因此本文的工作流程如圖1所示。

Fig.1 Method step diagram圖1 方法步驟圖

根據以上思想，主要將工作任務劃分為三個階段：

（1）進行頻繁項的構造時，根據n-gram[13]序列化的思想，逐一地對樣本集S中所有的二進制報文序列進行遍歷，記錄每個n-gram 出現的次數C及位置P。為了在頻繁項提取時能夠盡可能地將存在的頻繁項挖掘出，本文引入人工先驗知識，參考已有公開的二進制協議的字段長度劃分，對n-gram 序列化時的n值進行確定。設置n的取值范圍[minN,maxN]，逐一地更改n的大小，重復此步驟，直至記錄下所有的n-gram 信息。將記錄下的n-gram 信息納入到序列項-位置矩陣中，完成矩陣構造。

（2）設置支持度閾值threshold1，當某個n-gram的支持度大于閾值threshold1 時，將其納入到頻繁項集中，根據頻繁項集中的頻繁項，逐一地遍歷每條序列，若存在此頻繁項，則將此序列對應特征向量的位置置為1，否則置為0。

（3）根據特征化表示后得到的序列特征向量，使用分拆式層次聚類的方法進行聚類，以輪廓系數作為指導，設置輪廓系數閾值threshold2，指導聚類劃分，當所有簇的輪廓系數大于threshold2 時，結束劃分，完成聚類。

3 基于序列項-位置矩陣的分拆式層次聚類算法

3.1 序列項-位置矩陣的構造方法

本文根據n-gram 序列化的思想，逐一地遍歷每條二進制報文序列，摘取片段序列并記錄每個片段序列出現的次數C=(c1,c2,…,ci,…,ck)及位置P=(p1,p2,…,pj,…,py)（pj表示對應序列的第一個比特相對于整個序列的偏移位置），由于不同位置的片段可能是相同的，因此對于得到的總的序列片段數目k≤|se|-n+1（|se|表示序列se包含的比特數量），位置數目y=|se|-n+1。

例1 對于序列se=“010001101”，進行n-gram 序列化，當n取6 時，序列化得到的序列為“010001”“100011”“000110”“001101”。并記錄次數C及位置P，由于是針對一條序列，因此次數C=(1,1,1,1)，P=(1,2,3,4)，得到的總的序列片段數目y=4。

由于二進制報文字段通常不是等長劃分的，如二進制報文序列se={b1,b2,…,bi,bj,…,bn-1,bn}（bi、bj代表字段），|bi|≠|bj|，因此需要盡可能地將完整的頻繁項取出，設置n-gram 中n的取值范圍[minN,maxN]，本文中minN和maxN的確定需要根據目前已知的、公開的私有二進制協議中的字段長度來設置。設置完畢后，使n由minN逐一遞增至maxN。對于每個n，都需要對樣本集S中所有的二進制報文序列進行序列化，并記錄次數C及位置P。

將序列化后的序列片段納入到序列項-位置矩陣Mn中，每一個n、C、P對應著一個Mn，根據例1，當n=6 時，矩陣M6如表1 所示。

Table 1 Matrix M6表1 矩陣M6

3.2 報文序列特征向量生成方法

為從序列項-位置矩陣中挖掘出頻繁項，本文設置閾值threshold1，表示最小支持度，遍歷每一個序列項-位置矩陣Mn中的值，即次數cij，當cij/|S|≥threshold1時（|S|為樣本中報文的總數），將此次數cij對應的序列片段fi及位置pj作為一個頻繁項，加入到頻繁項集Fr中，Fr={f1,f2,…,fi,…,fz}，其中fi包含著每個頻繁項的比特內容及位置信息，這里將頻繁項的位置信息表示為position，以區別于片段序列的位置。

根據頻繁項集Fr，生成每一個二進制報文的特征向量FV=(v1,v2,…,vi,…,vz)，其中z=|Fr|，vi=0 or 1。將頻繁項集Fr中的每一個頻繁項fi與樣本集S中的每一個二進制報文序列進行遍歷匹配，當二進制報文序列存在所匹配的頻繁項fi時，將此二進制報文序列對應的特征向量FV中的vi置為1，反之為0。但二進制報文序列中的字段可能存在些許的位置偏移，導致在進行頻繁項fi匹配的過程中，fi.position未必完全匹配，因此本文設置一個容錯值allowance。當頻繁項fi在fi.position±allowance的范圍之內找到了對應的匹配序列，本文同樣將fi對應的特征向量FV中的vi置為1；若不在范圍內，則依然置為0，最后得到的序列特征向量形如FV=(0,1,1,0…)。

3.3 基于輪廓系數的分拆式層次聚類

3.3.1 t-SNE 的特征向量降維方法

特征向量的維數依賴于所生成的頻繁項的多少。

例2 當數據集中的報文序列包含7 類，每一類擁有200 條報文，進行序列化時，取n=5，threshold1=0.143。實驗中，產生的頻繁項高達498 個，即特征向量為498 維。

如此高的維數，在進行聚類時，運算量巨大，因此在進行特征向量聚類之前，需要對特征向量進行降維操作。

傳統的主成分分析法（principal components analysis，PCA）[14]降維是一種線性算法，在將高維數據中不相似的點降低到低維上時，存在相距較遠的問題。為了便于在低維空間上用非線性流形表示高維數據，相似數據點必須表示為非常靠近，因此本文選用t-SNE（t-distributed stochastic neighbor embedding）[15]的降維方法。關于t-SNE 的原理不是本文的研究重點，因此不再過多描述。

3.3.2 分拆式層次聚類

分拆式層次聚類是一種自上而下的聚類方式，主要思想是首先將樣本集看作是一個整體的簇，再遞歸地將現有的簇分拆為兩個子簇，在分拆的過程中，使用啟發式方法進行分拆。

開始的簇包含了所有的樣本，S={se1,se2,…,sei,…,sen}，計算樣本sei(sei∈S) 對于所有其他樣本sei′(sei′∈S)的平均距離，如式（1）所示，距離度量準則可以選擇歐式距離或其他度量準則。

選擇樣本空間S中平均距離最大的樣本sei*，如式（2）所示，將它歸入新簇N，如式（3）和式（4）所示。

根據此規則，持續地從樣本集合S中移除樣本，選取的樣本sei*滿足sei*到S的距離與sei*到N的距離差值最大，如式（5）所示。

在從樣本集S中移除樣本的過程中，不能無限制地移除，因此要設置終止條件。首先每次在移除樣本sei*時，都將重新計算每個樣本的平均距離并更新，當所移除的樣本sei*不滿足式（5），且滿足式（6）時，將停止本次移除。接下來，將分別對S和N進行同樣的拆分。

分拆式層次聚類沒有一個明確的全局目標函數來實現聚類，因此需要設置一個目標，當滿足這個目標時，便不再對子簇進行進一步的拆分，本文提出使用輪廓系數來指導劃分的方法。

3.3.3 輪廓系數指導聚類劃分

輪廓系數表示各簇內部的緊密程度，對于每個報文序列sei，定義其輪廓系數如式（7）所示。

其中，αsei如式（8）所示，表示報文序列sei與其所在簇的其他報文間的平均距離，βsei如式（9）所示，表示報文序列sei與其他簇的報文序列間的平均距離。同樣此處的距離度量可以選擇歐式距離或其他度量準則。根據公式可以看出，每個報文序列的輪廓系數取值范圍為(-1,1)，為了表達簇內部的緊密程度，將輪廓系數進行求和平均，取平均輪廓系數。如式（10）所示，代表該簇的聚類程度好壞，其中Sk表示報文序列sei所在簇。

為能夠達到預期的聚類效果，本文引入閾值threshold2，約束聚類是否要繼續進行。當平均輪廓系數SilSk＞threshold2 時，表示該簇不再需要進行拆分；當平均輪廓系數SilSk≤threshold2 時，表示該簇仍然需要繼續劃分，重復3.3.2 小節中的簇拆分步驟，直至所有簇的平均輪廓系數都滿足要求，即完成聚類。

4 實驗分析

4.1 數據集構造及參數設置

AIS（automatic identification system）協議是船舶自動識別系統的通信協議，是一種二進制協議，DNS（domain name system）、ICMP（Internet control message protocol）及ARP（address resolution protocol）是網絡通信中常用的3 種協議。本文通過AIS 采集的真實航行報文數據，以及Wireshark 捕獲的DNS、ICMP、ARP報文數據作為原始數據，對原始數據進行逆向處理，獲得0、1 組成的二進制報文數據，模擬真實情況下的私有二進制報文數據，作為數據集構造的基礎。

為了驗證本文方法對于同一協議下，不同報文格式的聚類效果，構造了數據集1，如表2 所示，包含AIS 協議4 類報文格式。其中AIS_1、AIS_4 與AIS_18 的報文數據等長，且與AIS_5 報文數據長度不同；在一定時間內，AIS_1、AIS_5 與AIS_18 報文內容變化較大，而AIS_4 報文內容變化較小。

Table 2 Data set 1表2 數據集1

為了驗證本文方法對于不同協議的報文格式的聚類效果，構造數據集2，如表3 所示，包含4 類報文格式。

Table 3 Data set 2表3 數據集2

為了驗證本文方法在實際情況下的聚類效果，構造數據集3，如表4 所示，包含同一協議下的不同報文格式，以及不同協議的報文格式，共7 類報文格式。

Table 4 Data set 3表4 數據集3

實驗過程中，需要對主要的參數進行設置，其中n為n-gram 序列化時的參數，threshold1 為頻繁項選取時的支持度閾值，threshold2 為輪廓系數指導劃分時的閾值。

本文采用兩種經典的評價指標，F1 值和純凈度Pu，如式（14）和式（16）所示。

式（14）中max(wi)表示簇i中報文數量最多的種類對應的報文數量；w表示樣本數據集中所有的報文數量；z表示聚類簇數。式（16）中F1(t,i)表示在第i個簇，第t類報文的F1 值，F1 值是在F值中的α=1 時所得，F值如式（15）所示，其中R為召回率，如式（17）所示，P為準確率，如式（18）所示。

為了說明總體的聚類效果，樣本集總體的F1 值如式（19）所示，其中wt表示樣本中t類報文的數量。

4.2 報文特征向量化效果分析與對比

為了直觀地觀察在報文向量化過程中，所生成的特征向量是否具有代表性的效果，本文使用t-SNE 降維，在二維平面上展示報文向量的分布效果。圖2 是在采用頻繁項對報文序列進行特征向量化，所得到的特征向量的分布圖，其中n=5，threshold1=0.143。

同等條件下，若采用文獻[11]中使用的截斷報文的方法，截取至報文數據部分的前50 比特，所得到的特征向量分布如圖3 所示。

對比圖2 與圖3 可以發現，文獻[11]中的方法無法很好地區分AIS_1 和AIS_5，且與AIS_18 分布較近，這是由于在一定時間段內，AIS_1、AIS_5 和AIS_18 報文數據的內容變化較大，截斷的方式無法有很好的特征表達。而經過特征向量化表示的報文序列具有更好的分布效果，特別對于長度較短的報文，特征向量化表示報文具有更加明顯的優勢。

Fig.2 t-SNE vector distribution圖2 t-SNE 向量分布圖

Fig.3 Message distribution圖3 報文分布圖

4.3 聚類方法參數及效果分析

4.3.1 序列化中參數n 的分析

在數據集3 的實驗上進行分析，將支持度閾值、輪廓系數閾值調整至最佳狀態，調整序列化參數n，觀察n對于聚類結果度量的純凈度和F1 值的影響，實驗結果如圖4 所示。

實驗發現當5 ≤n≤7 時，純凈度和F1 值處于相對較高的水平，能夠達到較好的聚類效果，這反映了以5 比特到7 比特進行頻繁項挖掘時，所構造的特征向量最具代表性；當n≤4 時，純凈度和F1 值急劇下降，說明此時的n構造的特征向量不具有代表性；當n≥8 時，純凈度和F1 值緩慢下降，說明聚類效果在緩慢變差，此時n構造的特征向量逐漸不具有代表性。

4.3.2 支持度閾值threshold1 分析

Fig.4 Purity and F1 value corresponding to different n values圖4 不同n 值對應的純凈度與F1 值

在數據集3 的實驗上進行分析，將序列化參數n、輪廓系數閾值調整至最佳狀態，調整支持度閾值threshold1，觀察threshold1 對于聚類結果度量的純凈度和F1 值的影響，實驗結果如圖5 所示。

Fig.5 Purity and F1 value corresponding to different threshold1 values圖5 不同threshold1 值對應的純凈度與F1 值

支持度閾值的選擇與樣本集中存在的報文種類有關，可以觀察當threshold1=0.143 時，純凈度與F1值相對較高；當threshold1 ≤0.143 時，純凈度會更高，但F1 值會下降較多，說明許多并非頻繁項的序列項被選入作為頻繁項，導致同一類型的報文被劃分成不同的報文而導致F1 值下降；當threshold1 ≥0.143 時，純凈度和F1 值都會明顯下降，說明選取的頻繁項構成的特征區分度下降，導致聚類過程中將不同類型的報文聚類成同一簇。

4.3.3 輪廓系數閾值threshold2 分析

在數據集3 的實驗上進行分析，將序列化參數n、支持度閾值調整至最佳狀態，調整輪廓系數閾值threshold2，觀察threshold2 對于聚類結果度量的純凈度和F1 值的影響，實驗結果如圖6 所示。

Fig.6 Purity and F1 value corresponding to different threshold2 values圖6 不同threshold2 值對應的純凈度與F1 值

輪廓系數閾值與最終聚類結果直接相關，輪廓系數越接近于1，說明聚類效果越好。但設置輪廓系數閾值時，若設置過高，會導致過分類的結果，從而導致純凈度很高而F1 值很低。從圖6 中觀察到，當0.63 ≤threshold2 ≤0.67 時，純凈度和F1 值相對較高，說明此時輪廓系數閾值能夠較好地將不同類的報文區分開，同時不會造成過分類的情況。

4.4 聚類方法對比分析

本文選用傳統的兩種聚類算法進行對比實驗，基于劃分的K-means[16]算法和基于密度的DBSCAN[17]（density-based spatial clustering of applications with noise）算法，兩種對比方法的參數在多次實驗過程中選擇最優參數設置。在K-means 算法聚類過程中，選擇其聚類簇數K=8，在DBSCAN 聚類算法中，參數MinPts=20，Eps 參數通過K-距離曲線確定。在數據集3 的實驗上進行分析，3 種聚類方法所得到的純凈度和F1 值如圖7 所示。

通過實驗結果發現，K-means 聚類算法所得到的純凈度相比DBSCAN 算法稍低，但F1 值卻明顯高于DBSCAN 算法。而DBSCAN 算法的純凈度比本文方法的98.71%稍高，達到了98.86%，但其F1 值卻是3 種方法中最低的。本文方法的純凈度雖然相比DBSCAN 算法低0.15 個百分點，幾乎可以認為純凈度水平相當，但本文方法的F1 值相比DBSCAN 提高了6.03 個百分點，相比K-means 方法也提高了2.16 個百分點，因此本文方法能夠提高聚類的純凈度與F1值，有效實現了二進制報文數據的自動聚類。

Fig.7 Purity and F1 value corresponding to different methods圖7 不同方法對應的純凈度與F1 值

5 結束語

本文所提出的報文特征向量化方法和基于輪廓系數的分拆式層次聚類方法，能夠有效地自動實現二進制報文的聚類。通過實驗測試發現，報文特征向量化方法相比于傳統的截取報文或對報文末端補0 的方法所生成的特征向量更具有報文代表性，更加有助于報文聚類；基于輪廓系數的分拆式層次聚類相比于傳統的K-means 算法和DBSCAN 算法，純凈度與F1 值具有更好的綜合效果。同時，在下一步工作中，將應用本文聚類方法進行私有二進制協議測試、協議逆向等任務。