融合特征降維和密度峰值的二進(jìn)制協(xié)議數(shù)據(jù)幀聚類算法

閆小勇,李 青

(信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,鄭州 450000)

1 引 言

二進(jìn)制協(xié)議區(qū)別于文本類協(xié)議[1],面向比特定義字段、數(shù)據(jù)幀結(jié)構(gòu)緊湊、控制開銷小、傳輸效率高,因此在物聯(lián)網(wǎng)、數(shù)據(jù)鏈等場(chǎng)合中應(yīng)用廣泛.尤其是用戶自定義的二進(jìn)制協(xié)議,出于各種原因不公開協(xié)議規(guī)范,在網(wǎng)絡(luò)中占有相當(dāng)?shù)谋壤齕1].二進(jìn)制協(xié)議大多通過UDP協(xié)議承載傳輸,不形成會(huì)話流,傳統(tǒng)的面向流的分類識(shí)別算法無法有效解決這一問題.自定義字符集的使用,導(dǎo)致很難利用定界符等先驗(yàn)信息[1],進(jìn)行頻繁模式提取.同時(shí),靈活的字段長度定義[1],要求統(tǒng)計(jì)分析需要以比特為單位,這在一定程度上縮小了協(xié)議數(shù)據(jù)幀之間的差異.這些特點(diǎn)都使得二進(jìn)制協(xié)議分類識(shí)別相比于文本類協(xié)議更加困難.

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

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

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

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

本文剩余部分組織如下:第二節(jié)建立了問題模型;第三節(jié)詳細(xì)闡述了算法細(xì)節(jié);第四節(jié)對(duì)算法本身進(jìn)行仿真與實(shí)驗(yàn)分析,并與經(jīng)典算法進(jìn)行對(duì)比;第五節(jié)結(jié)論.

2 問題模型

二進(jìn)制協(xié)議根據(jù)設(shè)計(jì)目標(biāo)和應(yīng)用背景的不同,其所定義數(shù)據(jù)幀長度存在很大差異.就同一協(xié)議而言,由于幀用途不同,會(huì)有多種幀長.即使同一類數(shù)據(jù)幀,仍會(huì)存在可擴(kuò)展字段,導(dǎo)致幀長可變.

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

對(duì)于接收到的數(shù)據(jù)集,可能是不同協(xié)議數(shù)據(jù)幀的混合,也可能是同一協(xié)議下不同幀格式數(shù)據(jù)幀的混合.由于先驗(yàn)信息缺失,數(shù)據(jù)集的真實(shí)類別數(shù)目和類別中心很難確定[9].

因此,實(shí)現(xiàn)二進(jìn)制私有協(xié)議數(shù)據(jù)幀的聚類需要解決數(shù)據(jù)幀預(yù)處理、冗余信息去除和無監(jiān)督條件下聚類中心、聚類簇?cái)?shù)的自動(dòng)確定等關(guān)鍵問題,如圖1所示.

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

3 FIFDR-DIWDPC算法

3.1 數(shù)據(jù)幀預(yù)處理

由于3.2節(jié)中利用滑動(dòng)窗提取頻繁項(xiàng)的過程中,當(dāng)協(xié)議數(shù)據(jù)幀長度不是滑動(dòng)窗長度的整數(shù)倍時(shí),協(xié)議數(shù)據(jù)幀末尾的若干比特信息將會(huì)丟失.為了避免信息損失,采用給長度非滑動(dòng)窗長整數(shù)倍的協(xié)議數(shù)據(jù)幀末尾補(bǔ)0的方式,使得協(xié)議數(shù)據(jù)幀的長度為滑動(dòng)窗長整數(shù)倍,如式(1)所示.szeroi表示第i條協(xié)議數(shù)據(jù)幀末尾補(bǔ)0的個(gè)數(shù),|xi|表示數(shù)據(jù)幀xi的比特長度,win_size是滑動(dòng)窗長,mod為數(shù)學(xué)中取余運(yùn)算.

szeroi=win_size-(|xi|modwin_size)

(1)

3.2 基于頻繁項(xiàng)的特征降維算法

絕大部分協(xié)議報(bào)文中存在關(guān)鍵詞,關(guān)鍵詞能夠用于區(qū)分不同的協(xié)議報(bào)文[10-12].關(guān)鍵詞通常在協(xié)議報(bào)文中頻繁出現(xiàn),提取頻繁項(xiàng),構(gòu)造特征矢量用來表示協(xié)議數(shù)據(jù)幀能夠?qū)崿F(xiàn)協(xié)議數(shù)據(jù)幀降維.基于頻繁項(xiàng)的特征降維算法主要包含兩個(gè)步驟:

1)利用滑動(dòng)窗實(shí)現(xiàn)不同偏移位置處的頻繁項(xiàng)統(tǒng)計(jì),構(gòu)造攜帶偏移位置信息的頻繁項(xiàng)集合;

2)對(duì)照頻繁項(xiàng)集合將協(xié)議數(shù)據(jù)幀轉(zhuǎn)化為特征矢量,實(shí)現(xiàn)協(xié)議數(shù)據(jù)幀降維.

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

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

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

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

基于頻繁項(xiàng)的特征降維算法,利用數(shù)據(jù)幀中包含的頻繁項(xiàng)來表示原有的協(xié)議數(shù)據(jù)幀,達(dá)到協(xié)議數(shù)據(jù)幀降維的目的.因?yàn)閰f(xié)議關(guān)鍵詞通常在協(xié)議報(bào)文中頻繁出現(xiàn),通過頻繁項(xiàng)構(gòu)建特征矢量降維原始高維數(shù)據(jù)幀,能夠保留用于區(qū)分不同協(xié)議數(shù)據(jù)幀的信息,從而實(shí)現(xiàn)后續(xù)混合協(xié)議數(shù)據(jù)幀的聚類.

3.3 基于距離指數(shù)加權(quán)的密度峰值聚類算法

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

3.3.1 相似性度量

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

(2)

最長公共子序列通常使用動(dòng)態(tài)規(guī)劃的方法求解.由于降維后的數(shù)據(jù)幀用頻繁項(xiàng)在頻繁項(xiàng)集合中的序號(hào)來表示,因此數(shù)據(jù)幀中不包含重復(fù)的元素.最長公共子序列LCSS(yi,yj)等價(jià)于yi和yj的交集,式(2)可以簡(jiǎn)化為式(3).

(3)

3.3.2 密度、距離計(jì)算及參數(shù)確定

DPC算法的基礎(chǔ)是對(duì)聚類中心的兩點(diǎn)假設(shè):

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

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

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

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

距離δ表示數(shù)據(jù)點(diǎn)與密度更大數(shù)據(jù)點(diǎn)的最小距離,如式(5).

(4)

(5)

距離閾值dc是DPC算法的一個(gè)重要參數(shù),該參數(shù)直接影響密度ρ的計(jì)算,如式(4).協(xié)議數(shù)據(jù)中存在完全相等的數(shù)據(jù)幀,導(dǎo)致不同數(shù)據(jù)幀之間距離為0的情況較為普遍.dc的確定依賴于幀間距離,為了使dc大于0,本文確定dc的方法與文獻(xiàn)[13]有所不同.首先過濾掉距離為0的數(shù)據(jù),再通過文獻(xiàn)[13]的經(jīng)驗(yàn)估計(jì)方法選取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 基于距離指數(shù)加權(quán)的聚類中心選取算法

由3.3.2節(jié)所述,ρ值與δ值均大的數(shù)據(jù)幀有可能是聚類中心.因此,文獻(xiàn)[13]定義γ=ρ×δ,γ值大的數(shù)據(jù)幀為聚類中心.

本文認(rèn)為δ值大的數(shù)據(jù)幀要比ρ值大的數(shù)據(jù)幀更可能成為聚類中心.因?yàn)橥ǔ?shù)據(jù)幀的分布密度多樣,ρ值大于聚類中心ρ值的數(shù)據(jù)幀較多,而δ值大于聚類中心δ值的數(shù)據(jù)幀較少.圖3是數(shù)據(jù)集2的ρ-δ分布圖(數(shù)據(jù)集2在第4小節(jié)中詳細(xì)介紹),五角星標(biāo)注的點(diǎn)為可能的聚類中心.可以發(fā)現(xiàn),δ值大的點(diǎn)只有幾個(gè)聚類中心,而ρ值大的點(diǎn)有很多,因此δ值在聚類中心選取過程中比ρ值具有更好的區(qū)分性,δ值大的點(diǎn)更可能成為聚類中心.為了更好的選取聚類中心,本文重新設(shè)計(jì)了γ,如式(10).γi表示第i條數(shù)據(jù)幀的γ值.

(10)

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

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

由于聚類中心的γ值相對(duì)于非聚類中心點(diǎn)的γ值屬于過大值,因此可以使用統(tǒng)計(jì)學(xué)中檢測(cè)異常值的方法提取聚類中心,如式(11).

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

(11)

N為聚類中心集合,μ為γ的均值,σ為γ的標(biāo)準(zhǔn)差.統(tǒng)計(jì)學(xué)方法中認(rèn)為檢測(cè)值和均值的差值超過兩倍標(biāo)準(zhǔn)差時(shí)為異常值,超過三倍標(biāo)準(zhǔn)差時(shí)為高度異常值.為盡可能提取聚類中心,本文通過不同數(shù)據(jù)集上多次試驗(yàn)驗(yàn)證認(rèn)為γ值和均值μ的差值超過一倍標(biāo)準(zhǔn)差時(shí)即可作為聚類中心.

3.3.4 聚類

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

(12)

(13)

Cc和Hc分別表示第c個(gè)簇的核心點(diǎn)與邊界點(diǎn)集合.最終的聚類結(jié)果如式(16)所示,li表示聚類之后第i條數(shù)據(jù)幀的類標(biāo)簽.li為0時(shí),表示該點(diǎn)沒有被分配類標(biāo)簽,視為噪聲數(shù)據(jù).

(14)

(15)

(16)

4 仿真與實(shí)驗(yàn)分析

為了驗(yàn)證FIFDR-DIWDPC對(duì)不同協(xié)議數(shù)據(jù)幀的區(qū)分能力, 構(gòu)造數(shù)據(jù)集1,如表1所示，由五種不同協(xié)議的單種幀格式數(shù)據(jù)幀構(gòu)成.為了驗(yàn)證FIFDR-DIWDPC對(duì)同一協(xié)議下不同

表1 數(shù)據(jù)集1
Table 1 Data set 1

協(xié)議數(shù)據(jù)幀格式數(shù)量(幀) AISType4200 ARPRequest200 DNSRequest200 ICMPType11200 SMB200

幀格式數(shù)據(jù)幀的區(qū)分能力,構(gòu)造數(shù)據(jù)集2,如表2所示，由AIS協(xié)議的五種不同幀格式數(shù)據(jù)幀構(gòu)成.為了更貼近實(shí)際,構(gòu)造數(shù)

表2 數(shù)據(jù)集2
Table 2 Data set 2

協(xié)議數(shù)據(jù)幀格式數(shù)量(幀)Type1200Type3200AISType4200Type6200Type18200

據(jù)集3,如表3所示，由AIS協(xié)議的五種不同幀格式數(shù)據(jù)幀和其余四種協(xié)議的單種幀格式數(shù)據(jù)幀共同構(gòu)成.

表3 數(shù)據(jù)集3
Table 3 Data set 3

協(xié)議數(shù)據(jù)幀格式數(shù)量(幀)Type1200Type3200 AISType4200Type6200Type18200 ARPRequest200 DNSRequest200 ICMPType11200 SMB200

實(shí)驗(yàn)過程中主要涉及四個(gè)參數(shù)win_size、minsupport、perc和q,設(shè)置如式(17)～式(20).

win_size=4

(17)

minsupport=0.1

(18)

perc=0.06

(19)

q=3

(20)

本文采用兩種常用的評(píng)價(jià)指標(biāo):純度purity和F值,如式(21)和式(24)所示.

純度purity:

(21)

F值:

(22)

recall和precision分別表示召回率和準(zhǔn)確率,nt表述數(shù)據(jù)幀中屬于第t個(gè)類別的幀個(gè)數(shù),nc表示數(shù)據(jù)幀中屬于第c個(gè)簇的幀個(gè)數(shù).

(23)

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

(24)

4.1 FIFDR-DIWDPC算法參數(shù)及性能分析

4.1.1 FIFDR算法參數(shù)分析

圖4是FIFDR-DIWDPC在數(shù)據(jù)集3上的運(yùn)行結(jié)果,圖4(a)和圖4(b)中五角星標(biāo)注的點(diǎn)為選取的聚類中心.圖4(a)是在沒有降維的條件下,對(duì)預(yù)處理后的數(shù)據(jù)幀直接應(yīng)用DIWDPC得到的γ分布圖.圖4(b)是采用特征降維后再使用DIWDPC得到的γ分布圖.對(duì)比圖4(a)和圖4(b)發(fā)現(xiàn)降維對(duì)聚類中心的選取影響較大,數(shù)據(jù)幀降維后再做聚類,冗余信息得到有效去除,聚類中心與其它數(shù)據(jù)幀區(qū)分性增強(qiáng).

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

1)滑動(dòng)窗長win_size分析

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

2)支持度閾值minsupport分析

圖6是FIFDR-DIWDPC在數(shù)據(jù)集3上,不同minsupport取值下的purity和F值統(tǒng)計(jì).minsupport的取值與原始數(shù)據(jù)集中包含的協(xié)議種類數(shù)有關(guān).minsupport取值較小,降維效果將不明顯;minsupport取值較大,數(shù)據(jù)集中占比較小的協(xié)議數(shù)據(jù)幀的頻繁項(xiàng)將無法通過minsupport獲取,從而對(duì)聚類結(jié)果產(chǎn)生影響.從圖6中可以看出,參數(shù)minsupport具有較強(qiáng)的魯棒性,0.06≤minsupport≤0.30時(shí),purity和F值均較大且穩(wěn)定.minsupport>0.30以后,隨著部分協(xié)議數(shù)據(jù)的頻繁項(xiàng)無法被提取,由特征矢量表示的協(xié)議數(shù)據(jù)幀開始丟失可區(qū)分不同協(xié)議數(shù)據(jù)幀的信息,表現(xiàn)為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算法參數(shù)分析

1)參數(shù)perc分析

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

圖7 參數(shù)perc對(duì)聚類的影響Fig.7 Influence of perc on clustering

2)距離指數(shù)q分析

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

圖8 參數(shù)q對(duì)聚類的影響Fig.8 Influence of q on clustering

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

圖9是在三個(gè)數(shù)據(jù)集上,FIFDR-DIWDPC算法的純度purity和F值.數(shù)據(jù)集1是不同協(xié)議單種格式數(shù)據(jù)幀的混合,差異性較大,FIFDR-DIWDPC不僅能夠準(zhǔn)確識(shí)別協(xié)議的種類,同時(shí)能夠?qū)⒏鲾?shù)據(jù)幀正確劃分到所屬的類,純度purity和F值均達(dá)到100%.數(shù)據(jù)集2由AIS協(xié)議的5種不同幀格式數(shù)據(jù)幀混合而成,同種協(xié)議不同幀格式數(shù)據(jù)幀差異性較小,較難區(qū)分,純度purity和F值有所下降.數(shù)據(jù)集3既包含不同協(xié)議的數(shù)據(jù)幀,同時(shí)包含同種協(xié)議不同幀格式數(shù)據(jù)幀.FIFDR-DIWDPC算法能夠識(shí)別不同協(xié)議的數(shù)據(jù)幀,但對(duì)于同種協(xié)議不同幀格式數(shù)據(jù)幀識(shí)別性能稍差.因?yàn)榧兌萷urity和F值是整體性能的衡量指標(biāo),所以算法在數(shù)據(jù)集3上的整體性能優(yōu)于在數(shù)據(jù)集2上的性能.

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

4.2 與經(jīng)典算法的性能對(duì)比

圖10 purity統(tǒng)計(jì)圖Fig.10 Purity graph of different algorithms

圖11 F值統(tǒng)計(jì)圖Fig.11 F graph of different algorithms

FIFDR-DIWDPC算法在不同協(xié)議數(shù)據(jù)幀聚類中性能良好,而在同一協(xié)議不同幀格式數(shù)據(jù)幀聚類中與經(jīng)典算法相比優(yōu)勢(shì)明顯.該算法能夠克服冗余信息對(duì)二進(jìn)制協(xié)議數(shù)據(jù)幀聚類的影響,保留能夠區(qū)分不同協(xié)議數(shù)據(jù)的信息,并且實(shí)現(xiàn)了聚類中心和聚類簇?cái)?shù)的自動(dòng)確定,達(dá)到了二進(jìn)制協(xié)議分類識(shí)別的目標(biāo).

4.3 算法時(shí)間復(fù)雜度分析

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

5 結(jié) 論

本文提出的融合特征降維和密度峰值的二進(jìn)制協(xié)議數(shù)據(jù)幀聚類算法FIFDR-DIWDPC,能夠在無監(jiān)督條件下實(shí)現(xiàn)二進(jìn)制協(xié)議數(shù)據(jù)幀的分類識(shí)別.通過在AIS、ARP、DNS、ICMP和SMB五種協(xié)議數(shù)據(jù)構(gòu)成的三個(gè)數(shù)據(jù)集上測(cè)試,具有不錯(cuò)的效果.該算法的局限性在于對(duì)數(shù)據(jù)集中不同類型協(xié)議數(shù)據(jù)的頻繁項(xiàng)提取還不夠準(zhǔn)確.因?yàn)楸疚拿嫦蚧旌隙M(jìn)制私有協(xié)議,數(shù)據(jù)集中協(xié)議的種類和數(shù)量未知,若存在小類樣本,而通過設(shè)定的支持度閾值無法提取該小類樣本的頻繁項(xiàng),那么最終的聚類結(jié)果中將不包含該小類樣本協(xié)議.如何克服小類樣本對(duì)聚類的影響是未來需要研究的課題.