融合特征降維和密度峰值的二進制協議數據幀聚類算法

閆小勇,李 青

(信息工程大學 信息系統工程學院,鄭州 450000)

1 引 言

二進制協議區別于文本類協議[1],面向比特定義字段、數據幀結構緊湊、控制開銷小、傳輸效率高,因此在物聯網、數據鏈等場合中應用廣泛.尤其是用戶自定義的二進制協議,出于各種原因不公開協議規范,在網絡中占有相當的比例[1].二進制協議大多通過UDP協議承載傳輸,不形成會話流,傳統的面向流的分類識別算法無法有效解決這一問題.自定義字符集的使用,導致很難利用定界符等先驗信息[1],進行頻繁模式提取.同時,靈活的字段長度定義[1],要求統計分析需要以比特為單位,這在一定程度上縮小了協議數據幀之間的差異.這些特點都使得二進制協議分類識別相比于文本類協議更加困難.

劉興彬[2]等基于Apriori算法提取特征字符串和包長特征用于協議識別,但因Apriori算法需要多次掃描數據庫,并且會產生大量的候選項,導致算法整體的計算效率和可擴展性較差.Wang[3]等采用X-means方法對會話流聚類,然后對每個簇的主導應用建立分類模型.黃笑言[4]等基于字節熵矢量加權指紋實現二進制協議識別,以不同字節對協議識別的貢獻不同進行加權并完成聚類.Luo[5]等提出基于粗糙集的協議識別方法,利用最小描述準則實現聚類簇數的自適應確定.Yue[6]等利用AC算法提取頻繁項,使用Apriori算法挖掘關聯規則,最后采用改進的K-means算法實現二進制數據幀聚類,但因頻繁特征挖掘范圍不易確定,導致聚類的粒度很難掌控.

上述網絡協議識別方法大多面向會話流、以字節寬度對協議數據做統計分析[2-5],雖然對二進制協議識別有一定效果,但更偏向于文本類協議.本文面向二進制私有協議數據幀,提出了一種融合特征降維和密度峰值的二進制協議數據幀聚類算法(Feature Dimensionality Reduction based on Frequent Items-Density Peaks Clustering based on Distance Index Weighting,FIFDR-DIWDPC).主要貢獻有:

1)提出基于頻繁項的特征降維算法(Feature Dimensionality Reduction based on Frequent Items,FIFDR),在降維的同時保留了能夠區分不同協議數據的信息;

2)提出基于距離指數加權的密度峰值聚類算法(Density Peaks Clustering based on Distance Index Weighting,DIWDPC)自動選取聚類中心,有效提高了聚類中心和其它數據幀的區分度.

本文剩余部分組織如下:第二節建立了問題模型;第三節詳細闡述了算法細節;第四節對算法本身進行仿真與實驗分析,并與經典算法進行對比;第五節結論.

2 問題模型

二進制協議根據設計目標和應用背景的不同,其所定義數據幀長度存在很大差異.就同一協議而言,由于幀用途不同,會有多種幀長.即使同一類數據幀,仍會存在可擴展字段,導致幀長可變.

對于變長幀,以比特為處理單位計為一維特征,則數據幀的維數通常會從上百維到上千維,其中包含大量冗余信息[7,8].為提高聚類的性能,需要進行特征選擇.

對于接收到的數據集,可能是不同協議數據幀的混合,也可能是同一協議下不同幀格式數據幀的混合.由于先驗信息缺失,數據集的真實類別數目和類別中心很難確定[9].

因此,實現二進制私有協議數據幀的聚類需要解決數據幀預處理、冗余信息去除和無監督條件下聚類中心、聚類簇數的自動確定等關鍵問題,如圖1所示.

圖1 FIFDR-DIWDPC算法流程圖Fig.1 Workflow for FIFDR-DIWDPC

3 FIFDR-DIWDPC算法

3.1 數據幀預處理

由于3.2節中利用滑動窗提取頻繁項的過程中,當協議數據幀長度不是滑動窗長度的整數倍時,協議數據幀末尾的若干比特信息將會丟失.為了避免信息損失,采用給長度非滑動窗長整數倍的協議數據幀末尾補0的方式,使得協議數據幀的長度為滑動窗長整數倍,如式(1)所示.szeroi表示第i條協議數據幀末尾補0的個數,|xi|表示數據幀xi的比特長度,win_size是滑動窗長,mod為數學中取余運算.

szeroi=win_size-(|xi|modwin_size)

(1)

3.2 基于頻繁項的特征降維算法

絕大部分協議報文中存在關鍵詞,關鍵詞能夠用于區分不同的協議報文[10-12].關鍵詞通常在協議報文中頻繁出現,提取頻繁項,構造特征矢量用來表示協議數據幀能夠實現協議數據幀降維.基于頻繁項的特征降維算法主要包含兩個步驟:

1)利用滑動窗實現不同偏移位置處的頻繁項統計,構造攜帶偏移位置信息的頻繁項集合;

2)對照頻繁項集合將協議數據幀轉化為特征矢量,實現協議數據幀降維.

步驟1中頻繁項的提取涉及到支持度,用bstring(j)表示攜帶偏移位置信息的比特串,bstring為比特串,長度與滑動窗長win_size相同,j為bstring的起始比特相對于協議數據幀首部的偏移位置,則支持度的定義如下:

設置最小支持度閾值minsupport,當sup(bstring(j))>minsupport時,bstring(j)為頻繁項.由于本文面向混合二進制私有協議,協議的種類和數量未知,為了盡可能的識別混合數據集中的協議,通常minsupport取值較小.

如圖2所示,設滑動窗的長度為4比特,滑動窗w1,w2,w3,…,wk-1,wk的起始位置對應于協議數據幀首部的偏移量分別為0,4,8,…,(k-2)×4,(k-1)×4.假設由支持度定義獲取的頻繁項共有四個,分別為0001(0),0001(8),0101(8),0110((k-2)×4).由圖可以看出,同一個滑動窗可能產生多個不同的頻繁項,相同的比特串在不同的滑動窗中代表不同的頻繁項.將得到的頻繁項按照位置先后進行排序,得到頻繁項集合F_item={f_item1,f_item2,…,f_items}.將原始數據幀對照頻繁項集合,若頻繁項存在于數據幀中,即xi(bstring(j))=1,則將bstring(j)在頻繁項集合F_item中的對應序號(若f_item2=bstring(j),則對應序號為2)添加到數據幀的特征矢量.圖2中,第1幀、第i幀和第m幀的特征矢量分別為:(1,2),(1,4),(1,3).

圖2 特征降維Fig.2 Feature dimensionality reduction

基于頻繁項的特征降維算法,利用數據幀中包含的頻繁項來表示原有的協議數據幀,達到協議數據幀降維的目的.因為協議關鍵詞通常在協議報文中頻繁出現,通過頻繁項構建特征矢量降維原始高維數據幀,能夠保留用于區分不同協議數據幀的信息,從而實現后續混合協議數據幀的聚類.

3.3 基于距離指數加權的密度峰值聚類算法

鑒于大部分聚類方法存在聚類中心和聚類簇數無法自動確定的問題,本文改進密度峰值聚類算法(Density Peaks Clustering,DPC)[13],提出基于距離指數加權的密度峰值聚類算法DIWDPC,利用最長公共子序列距離度量數據幀之間的相似性,重新設計了γ,并采用統計學中識別異常值的方法選取聚類中心.

3.3.1 相似性度量

不同協議數據幀中包含的頻繁項數量可能不同,因此3.2節得到的降維后的數據幀維度不同.對于不等長的降維數據幀之間的距離不能使用歐氏、馬氏距離計算,本文采用最長公共子序列距離衡量降維數據幀之間的距離.距離公式如式(2)所示.dij表示數據幀yi和數據幀yj之間的距離,LCSS(yi,yj)表示數據幀yi和數據幀yj的最長公共子序列.

(2)

最長公共子序列通常使用動態規劃的方法求解.由于降維后的數據幀用頻繁項在頻繁項集合中的序號來表示,因此數據幀中不包含重復的元素.最長公共子序列LCSS(yi,yj)等價于yi和yj的交集,式(2)可以簡化為式(3).

(3)

3.3.2 密度、距離計算及參數確定

DPC算法的基礎是對聚類中心的兩點假設:

1)聚類中心被密度均不超過它的鄰居包圍;

2)聚類中心與其它密度更大點之間的距離較大.

為此,算法給每個點定義了兩個屬性:密度ρ和距離δ,ρ值和δ值都大的點才有可能成為聚類中心.

關于密度ρ,文獻[13]給出了Cut-off kernel和Gaussian kernel兩種形式.Gaussian kernel考慮了數據點之間距離對密度ρ的影響,本文選擇Gaussian kernel作為密度計算公式,如式(4).其中dij是數據幀yi和數據幀yj之間的距離,dc為距離閾值.

距離δ表示數據點與密度更大數據點的最小距離,如式(5).

(4)

(5)

距離閾值dc是DPC算法的一個重要參數,該參數直接影響密度ρ的計算,如式(4).協議數據中存在完全相等的數據幀,導致不同數據幀之間距離為0的情況較為普遍.dc的確定依賴于幀間距離,為了使dc大于0,本文確定dc的方法與文獻[13]有所不同.首先過濾掉距離為0的數據,再通過文獻[13]的經驗估計方法選取dc,具體過程如式(6)-式(9).

A={dij|j>i,dij≠0}

(6)

A′=sort(A)

(7)

p=[perc×|A′|]

(8)

(9)

A是幀間距離的集合,A′是A的升序排列,p是A′的索引,0.05

3.3.3 基于距離指數加權的聚類中心選取算法

由3.3.2節所述,ρ值與δ值均大的數據幀有可能是聚類中心.因此,文獻[13]定義γ=ρ×δ,γ值大的數據幀為聚類中心.

本文認為δ值大的數據幀要比ρ值大的數據幀更可能成為聚類中心.因為通常數據幀的分布密度多樣,ρ值大于聚類中心ρ值的數據幀較多,而δ值大于聚類中心δ值的數據幀較少.圖3是數據集2的ρ-δ分布圖(數據集2在第4小節中詳細介紹),五角星標注的點為可能的聚類中心.可以發現,δ值大的點只有幾個聚類中心,而ρ值大的點有很多,因此δ值在聚類中心選取過程中比ρ值具有更好的區分性,δ值大的點更可能成為聚類中心.為了更好的選取聚類中心,本文重新設計了γ,如式(10).γi表示第i條數據幀的γ值.

(10)

圖3 ρ-δ圖Fig.3 ρ-δ graph

新設計的γ考慮到ρ值和δ值可能處于不同的數量級,在計算γ的過程中對兩者進行了歸一化處理,即每條數據幀的ρ值和δ值分別除以ρ和δ的最大值.γ中對δ進行了q次方的處理,且要求q>1,體現了δ值的重要性,使聚類中心能夠更好的區別于其它數據幀.

由于聚類中心的γ值相對于非聚類中心點的γ值屬于過大值,因此可以使用統計學中檢測異常值的方法提取聚類中心,如式(11).

N={yi|γi-μ>σ}

(11)

N為聚類中心集合,μ為γ的均值,σ為γ的標準差.統計學方法中認為檢測值和均值的差值超過兩倍標準差時為異常值,超過三倍標準差時為高度異常值.為盡可能提取聚類中心,本文通過不同數據集上多次試驗驗證認為γ值和均值μ的差值超過一倍標準差時即可作為聚類中心.

3.3.4 聚類

確定聚類中心之后,數據幀被分配給比它密度高并且距離它最近的數據幀所屬的類,如式(12)所示.

(12)

(13)

Cc和Hc分別表示第c個簇的核心點與邊界點集合.最終的聚類結果如式(16)所示,li表示聚類之后第i條數據幀的類標簽.li為0時,表示該點沒有被分配類標簽,視為噪聲數據.

(14)

(15)

(16)

4 仿真與實驗分析

為了驗證FIFDR-DIWDPC對不同協議數據幀的區分能力, 構造數據集1,如表1所示，由五種不同協議的單種幀格式數據幀構成.為了驗證FIFDR-DIWDPC對同一協議下不同

表1 數據集1
Table 1 Data set 1

協議數據幀格式數量(幀) AISType4200 ARPRequest200 DNSRequest200 ICMPType11200 SMB200

幀格式數據幀的區分能力,構造數據集2,如表2所示，由AIS協議的五種不同幀格式數據幀構成.為了更貼近實際,構造數

表2 數據集2
Table 2 Data set 2

協議數據幀格式數量(幀)Type1200Type3200AISType4200Type6200Type18200

據集3,如表3所示，由AIS協議的五種不同幀格式數據幀和其余四種協議的單種幀格式數據幀共同構成.

表3 數據集3
Table 3 Data set 3

協議數據幀格式數量(幀)Type1200Type3200 AISType4200Type6200Type18200 ARPRequest200 DNSRequest200 ICMPType11200 SMB200

實驗過程中主要涉及四個參數win_size、minsupport、perc和q,設置如式(17)～式(20).

win_size=4

(17)

minsupport=0.1

(18)

perc=0.06

(19)

q=3

(20)

本文采用兩種常用的評價指標:純度purity和F值,如式(21)和式(24)所示.

純度purity:

(21)

F值:

(22)

recall和precision分別表示召回率和準確率,nt表述數據幀中屬于第t個類別的幀個數,nc表示數據幀中屬于第c個簇的幀個數.

(23)

F(t,c)表示第t個類別和第c個簇之間的F值,總的F值為:

(24)

4.1 FIFDR-DIWDPC算法參數及性能分析

4.1.1 FIFDR算法參數分析

圖4是FIFDR-DIWDPC在數據集3上的運行結果,圖4(a)和圖4(b)中五角星標注的點為選取的聚類中心.圖4(a)是在沒有降維的條件下,對預處理后的數據幀直接應用DIWDPC得到的γ分布圖.圖4(b)是采用特征降維后再使用DIWDPC得到的γ分布圖.對比圖4(a)和圖4(b)發現降維對聚類中心的選取影響較大,數據幀降維后再做聚類,冗余信息得到有效去除,聚類中心與其它數據幀區分性增強.

圖4 降維對聚類的影響Fig.4 Influence of dimensionality reduction on clustering

1)滑動窗長win_size分析

圖5為FIFDR-DIWDPC在數據集3上,win_size不同取值下的purity和F值統計.可以發現,4≤win_size≤8時,purity和F值穩定且相對較大.win_size>8以后,purity和F值整體成下降趨勢.這與二進制協議數據幀的特點密切相關,二進制協議數據幀以比特定義字段,數據統計和分析的最小單元為比特,不受字節長度限制,因此在win_size小于8時,算法性能良好.當win_size大于8以后,隨著win_size不斷增長,能夠提取的頻繁項數量逐漸減少,算法整體性能開始下降.本文在大部分情況下,win_size設置為4.

2)支持度閾值minsupport分析

圖6是FIFDR-DIWDPC在數據集3上,不同minsupport取值下的purity和F值統計.minsupport的取值與原始數據集中包含的協議種類數有關.minsupport取值較小,降維效果將不明顯;minsupport取值較大,數據集中占比較小的協議數據幀的頻繁項將無法通過minsupport獲取,從而對聚類結果產生影響.從圖6中可以看出,參數minsupport具有較強的魯棒性,0.06≤minsupport≤0.30時,purity和F值均較大且穩定.minsupport>0.30以后,隨著部分協議數據的頻繁項無法被提取,由特征矢量表示的協議數據幀開始丟失可區分不同協議數據幀的信息,表現為purity和F值開始下降.

圖5 不同win_size下的purity和FFig.5 Purity and F under different win_size

圖6 不同minsupport下的purity和FFig.6 Purity and F under different minsupport

4.1.2 DIWDPC算法參數分析

1)參數perc分析

圖7是在數據集3上,win_size取值為4,minsupport取值為0.1,q取值為3,不同perc取值對應的純度purity和F值.可以看出perc取值在0.05到0.07之間時,純度purity和F值均較大,本文設置perc為0.06.

圖7 參數perc對聚類的影響Fig.7 Influence of perc on clustering

2)距離指數q分析

圖8(a)至圖8(d)是在數據集2上,win_size取值為4,minsupport取值為0.1,perc為0.06,q分別取1,3,5,7時的γ分布圖.圖8(e)是相應的純度purity和F值.可以看出,q取值為1時,通過本文算法提取的聚類中心較多,與實際偏差較大.q取值為3時,聚類中心由原來的多個變為了4個,與真實情況接近.q取值為5和7時,圖中最左邊的聚類中心點隨著q的增加逐漸消失,通過本文算法最終只能得到三個聚類中心點.由圖8(e)可以看出q取值為2和3時,純度purity和F值均取得最大值,而后隨著q值的增加,兩者均開始下降,最終保持平穩,本文設置q為3.

圖8 參數q對聚類的影響Fig.8 Influence of q on clustering

4.1.3 FIFDR-DIWDPC算法整體性能分析

圖9是在三個數據集上,FIFDR-DIWDPC算法的純度purity和F值.數據集1是不同協議單種格式數據幀的混合,差異性較大,FIFDR-DIWDPC不僅能夠準確識別協議的種類,同時能夠將各數據幀正確劃分到所屬的類,純度purity和F值均達到100%.數據集2由AIS協議的5種不同幀格式數據幀混合而成,同種協議不同幀格式數據幀差異性較小,較難區分,純度purity和F值有所下降.數據集3既包含不同協議的數據幀,同時包含同種協議不同幀格式數據幀.FIFDR-DIWDPC算法能夠識別不同協議的數據幀,但對于同種協議不同幀格式數據幀識別性能稍差.因為純度purity和F值是整體性能的衡量指標,所以算法在數據集3上的整體性能優于在數據集2上的性能.

圖9 FIFDR-DIWDPC算法整體性能Fig.9 Overall performance of FIFDR-DIWDPC

4.2 與經典算法的性能對比

圖10 purity統計圖Fig.10 Purity graph of different algorithms

圖11 F值統計圖Fig.11 F graph of different algorithms

FIFDR-DIWDPC算法在不同協議數據幀聚類中性能良好,而在同一協議不同幀格式數據幀聚類中與經典算法相比優勢明顯.該算法能夠克服冗余信息對二進制協議數據幀聚類的影響,保留能夠區分不同協議數據的信息,并且實現了聚類中心和聚類簇數的自動確定,達到了二進制協議分類識別的目標.

4.3 算法時間復雜度分析

假設待聚類的數據集有n條二進制數據幀,數據幀維度為m.DPC算法時間復雜度依賴于三部分,分別是數據幀與數據幀之間的距離計算時間(時間復雜度為O(mn2/2));數據幀的局部密度ρ計算時間(時間復雜度為O(n2));數據幀的距離δ計算時間(時間復雜度為O(n2)).所以DPC算法的整體時間復雜度近似為O((m/2+2)n2).FIFDR-DIWDPC算法時間復雜度主要由FIFDR時間復雜度和DIWDPC時間復雜度兩部分構成.FIFDR的時間復雜度近似為O(n×「m/win_size?).DIWDPC時間復雜度由三部分構成,數據幀與數據幀之間的距離計算時間(時間復雜度為O(n2/2));數據幀的局部密度ρ計算時間(時間復雜度為O(n2));數據幀的距離δ計算時間(時間復雜度為O(n2)).因此FIFDR-DIWDPC算法的時間復雜度近似為O(n2).K-means算法的時間復雜度近似為O(n),DBSCAN算法的時間復雜度近似為O(n2).

5 結 論

本文提出的融合特征降維和密度峰值的二進制協議數據幀聚類算法FIFDR-DIWDPC,能夠在無監督條件下實現二進制協議數據幀的分類識別.通過在AIS、ARP、DNS、ICMP和SMB五種協議數據構成的三個數據集上測試,具有不錯的效果.該算法的局限性在于對數據集中不同類型協議數據的頻繁項提取還不夠準確.因為本文面向混合二進制私有協議,數據集中協議的種類和數量未知,若存在小類樣本,而通過設定的支持度閾值無法提取該小類樣本的頻繁項,那么最終的聚類結果中將不包含該小類樣本協議.如何克服小類樣本對聚類的影響是未來需要研究的課題.