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

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

0 引言

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

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

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

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

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

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

2.1 實(shí)現(xiàn)方案

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

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

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

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

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

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

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

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

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

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

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

聚類過(guò)程的偽代碼：

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

2.4 確定k 值的AGNES 聚類

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

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

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

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

AGNES（AGglomerative NESting）算法輸入：樣本集D={x1，x2，…，xn}；距離度量d；聚類個(gè)數(shù)k。輸出：k 個(gè)類簇步驟：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è)置當(dāng)前簇個(gè)數(shù)q=m 10. while q＞k:11. 找到最相似的兩個(gè)簇，合并最相似的兩個(gè)簇12. 將聚類簇重新編號(hào)，刪除相對(duì)應(yīng)的距離矩陣的行和列13. q=q-1 14. end while 15. 輸出K 個(gè)類簇。

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

圖3 Calinski-Harabasz 分?jǐn)?shù)值ch 隨k 值變化情況

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

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

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

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

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

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

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

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

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

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

在聚類過(guò)程中，設(shè)定方法為中位數(shù)聚類法，度量標(biāo)準(zhǔn)采用PEARSON 相關(guān)性距離，聚類數(shù)指定為5，對(duì)750 條協(xié)議報(bào)文進(jìn)行聚類，聚類的結(jié)果如圖7所示。

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

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

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

顯效：患者的臨床癥狀和體征緩解50%以上，尿微量白蛋白下降50%以上或是恢復(fù)正常水平。有效：臨床癥狀和體征緩解30%～50%，尿微量白蛋白下降30%～50%。無(wú)效：不符合上述標(biāo)準(zhǔn)者。

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

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

在相同的k 值下通過(guò)準(zhǔn)確率、識(shí)別率、誤識(shí)別率來(lái)比較兩種方法的聚類結(jié)果。

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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