基于SU和AMB的網(wǎng)絡(luò)流量特征選擇算法①

龐玉林,李喜旺

1(中國(guó)科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽 110168)

2(中國(guó)科學(xué)院大學(xué),北京 100049)

隨著聯(lián)網(wǎng)設(shè)備的增多,越來越多的網(wǎng)絡(luò)設(shè)備暴露在公網(wǎng)內(nèi),網(wǎng)絡(luò)空間掃描工具Shodan 甚至可以輕而易舉獲取到隱私家用攝像頭的內(nèi)容.在工業(yè)網(wǎng)絡(luò)中,原本封閉的環(huán)境變得開放,聯(lián)網(wǎng)設(shè)備版本難以升級(jí),不易管理,這使得工業(yè)網(wǎng)絡(luò)內(nèi)的專業(yè)設(shè)備有著更容易被入侵的風(fēng)險(xiǎn)[1],如果我們能夠及時(shí)獲取聯(lián)網(wǎng)設(shè)備信息,掌握網(wǎng)絡(luò)中設(shè)備之間的拓?fù)潢P(guān)系,有效的進(jìn)行資產(chǎn)管理和資產(chǎn)分析,了解設(shè)備的脆弱點(diǎn),及時(shí)將漏洞信息和設(shè)備脆弱點(diǎn)結(jié)合起來,在發(fā)生故障時(shí)能夠及時(shí)進(jìn)行故障定位和故障處置分析.目前現(xiàn)有的網(wǎng)絡(luò)設(shè)備識(shí)別研究中大多數(shù)都是通過主動(dòng)探測(cè)的技術(shù)來發(fā)現(xiàn)設(shè)備,這種方法會(huì)干擾或者中斷設(shè)備的運(yùn)行狀態(tài),但在實(shí)際環(huán)境中,大部分設(shè)備過時(shí)或計(jì)算能力較低,并不支持中斷或干擾其系統(tǒng)[2-4].基于網(wǎng)絡(luò)流量特征的被動(dòng)式識(shí)別方法具有干擾性小、自動(dòng)化高的特點(diǎn),所以其目前成為學(xué)者們的研究熱點(diǎn),也更符合未來的發(fā)展要求.

在基于網(wǎng)絡(luò)流量分析的網(wǎng)絡(luò)設(shè)備識(shí)別研究中,利用Wireshark 在特定環(huán)境中抓取的網(wǎng)絡(luò)流量數(shù)據(jù)包中的特征屬性集往往是高維的,這些屬性集中存在許多冗余或不相干的屬性,這些冗余信息不但會(huì)降低數(shù)據(jù)集的數(shù)據(jù)質(zhì)量,也會(huì)影響后續(xù)網(wǎng)絡(luò)設(shè)備識(shí)別效率和精確率,妄加無效的工作量,所以為了保證數(shù)據(jù)集的數(shù)據(jù)質(zhì)量和設(shè)備識(shí)別效率及精確率,有效地對(duì)數(shù)據(jù)包中的數(shù)據(jù)特征屬性進(jìn)行降維是一項(xiàng)非常重要的工作.

1 相關(guān)工作

目前網(wǎng)絡(luò)流量特征選擇算法在網(wǎng)絡(luò)流量分類的研究中應(yīng)用比較廣泛,大多數(shù)的文獻(xiàn)主要是針對(duì)網(wǎng)絡(luò)流量分類的效率和精確率來對(duì)網(wǎng)絡(luò)流量特征選擇算法進(jìn)行研究和改善[5].劉雪亞等人[6]、唐宏等人[7]和趙擇等人[8]的工作主要是針對(duì)網(wǎng)絡(luò)流量不均衡,面向網(wǎng)絡(luò)流量數(shù)據(jù)中單個(gè)類別的分類,劉雪亞等人[6]提出了一種基于卡方算法和SU(對(duì)稱不確定性)算法的結(jié)合來提高小類別的網(wǎng)絡(luò)流量數(shù)據(jù)的分類精確率;唐宏等人[7]提出一種基于FCBF 的特征選擇算法更容易地選擇出來與小類別流量具有強(qiáng)相關(guān)性的特征;趙擇等人[8]提出一種基于改進(jìn)一對(duì)一算法的集成學(xué)習(xí)方式把網(wǎng)絡(luò)流量分類的多分類任務(wù)拆解為多個(gè)相互獨(dú)立的二分類任務(wù),其思想的重點(diǎn)不在于特征選擇的工程如何改善,而是把重點(diǎn)放在了利用集成學(xué)習(xí)的策略上來充分挖掘每類流量的數(shù)據(jù)特征來提高分類性能;曹杰[9]在工作中提出了一種Filter-Wrapper 混合的特征選擇模型,其先利用信息增益對(duì)有分類貢獻(xiàn)的特征進(jìn)行性能評(píng)估排序,在候選子集上再利用Wrapper 方式進(jìn)行二次特征選擇.

但本文的研究目的是選擇出能夠更高效、更精確地對(duì)網(wǎng)絡(luò)設(shè)備進(jìn)行識(shí)別的網(wǎng)絡(luò)流量特征,Nguyen-An等人[10]提出了一種通過計(jì)算網(wǎng)絡(luò)流量特征的信息熵來對(duì)網(wǎng)絡(luò)設(shè)備進(jìn)行識(shí)別的方法;Jeon 等人[11]提出了把網(wǎng)絡(luò)端口和一系列TCP/IP 協(xié)議棧的相關(guān)特征字段作為設(shè)備識(shí)別的指紋特征,但是這類基于人為分析選取的網(wǎng)絡(luò)流量特征的被動(dòng)式設(shè)備識(shí)別方法在通用性,精確度方面還有待提高.

2 算法設(shè)計(jì)

2.1 FSSA

本文主要是針對(duì)網(wǎng)絡(luò)設(shè)備的操作系統(tǒng)類型進(jìn)行識(shí)別,所以針對(duì)這個(gè)問題本文提出了一種將Filter 和Wrapper 方式相結(jié)合,基于SU[12]和AMB[13]的網(wǎng)絡(luò)流量特征選擇算法FSSA(feature selection based on symmetric uncertainty and approximate Markov Blanket),該算法首先在Filter 方式中利用SU 算法選擇出對(duì)于各個(gè)類別具有分類貢獻(xiàn)的特征,去除不相關(guān)的特征屬性;然后在候選特征子集中利用馬爾可夫毯算法刪除冗余特征,最后再采用Wrapper方式,基于C4.5 決策樹分類算法選擇出使分類器效果最好的最優(yōu)特征集,這樣不僅可以對(duì)特征集進(jìn)行降維,也可以提高分類器的性能.

2.2 SU 算法

假設(shè)樣本總數(shù)為N,樣本中有j個(gè)類別的樣本,類別用C表示,特征屬性集F={f1,f2,,···,fi},SU 可以用來描述特征屬性fi和特征屬性所屬類別C之間的相關(guān)性,也可以描述特征屬性集F中特征屬性與特征屬性的相關(guān)性[12,14].

首先我們引入信息熵H(F)和條件熵H(F|C)的定義,如式(1)和式(2),其中p(fi)表示fi在特征屬性集F中出現(xiàn)的概率,p(cj)表示類別cj的出現(xiàn)概率,p(fi|cj)表示特征fi在類別cj條件下的條件概率.

由式(1)和式(2)可以得到特征屬性與類別的信息增益IG(F,C),如式(3).

由式(1)和式(2)推算式(3)可以得到如下關(guān)系,此處不再贅述.

最后,由上述4 個(gè)公式我們可以得到特征fi與類別C之間的對(duì)稱不確定性SU(fi,C),如式(5).

首先通過計(jì)算特征fi與類別C的對(duì)稱不確定性SU(fi,C),對(duì)所有結(jié)果進(jìn)行一個(gè)降序排序,排名越靠前的值其對(duì)應(yīng)的特征對(duì)類別分類的貢獻(xiàn)就越大,通過選取合適的閾值δ,對(duì)于SU 值大于閾值δ的特征,將其放入候選特征子集內(nèi).

2.3 AMB 算法

馬爾可夫毯是進(jìn)行特征冗余性分析的一種常用的工具,在一個(gè)特征空間中,目標(biāo)特征的馬爾可夫毯包含了它的所有信息,所以非馬爾可夫毯就可以看成是目標(biāo)特征的冗余特征.因此通過發(fā)現(xiàn)目標(biāo)特征的馬爾可夫毯就可以精確確定目標(biāo)特征的冗余特征,從而降低特征空間的維數(shù),達(dá)到特征選擇的目的[13].

首先引入馬爾可夫毯的概念:假設(shè)在隨機(jī)變量的全集U中,對(duì)于給定的變量X∈U和變量集MB?U且X?MB,若滿足式(6),則稱能滿足上述條件的最小變量集MB為X的馬爾可夫毯.

由式(6)我們可以給出特征的近似馬爾可夫毯:若存在特征集合F,對(duì)于給定特征fi,使得特征子集MBi?F且fi?MBi,滿足式(7)時(shí),稱MBi是特征fi的馬爾可夫毯.

由式(6)和式(7)我們可以定義冗余特征:對(duì)于上述特征集合F,如果滿足式(8),即對(duì)于給定特征fi和分類C 是弱相關(guān)的,并且可以在F內(nèi)找到它的近似馬爾可夫毯fj,那么特征fi就是冗余特征,應(yīng)該在F中移除.

2.4 算法流程描述

本文提出的算法偽代碼如算法1所示,主要分為兩大模塊,第一模塊是Filter 式特征選擇,分別利用SU(代碼1-5 行)和AMB(代碼6-16 行)進(jìn)行特征初選,第二模塊是Wrapper 式(代碼17-27 行)特征選擇,利用C4.5 分類器,在第一模塊選取出的候選特征子集種,依次選取排名靠前的特征放入最優(yōu)特征集中,并根據(jù)這個(gè)最優(yōu)特征集預(yù)處理數(shù)據(jù)集,一邊記錄分類器訓(xùn)練測(cè)試效果,一邊進(jìn)行最后的最優(yōu)特征子集搜索,最后選擇出分類器測(cè)試效果最好的特征子集作為最優(yōu)特征子集.

算法1.算法流程代碼F(f1,f2,···,fN,C),δ輸入://training set and predefined threshold Fbest輸出:,PR //the best feature set and precision rate fi∈F 1.for SU(fi,C)2.calculate SU(fi,C)≥δ 3.if fiF′4.put into SU(fi,C)F′5.sort by descending of F′≠?6.while fj=getFirstElement(F′)7.fj≠?8.while fi=getNextElement(F′,fj)9.fi≠?10.while f′i fi 11.=SU(fi,f j)≥SU(fi,C)12.if fiF′13.remove from fi=getNextElement(F′,f′i)14.fi=getNextElement(F′,fi)15.else fj=getNextElement(F′,fj)16.Ftop=F′17.F*best=?PR0 18.,=0 Ftop≠?19.while fi∈Ftop 20.for fi into F*best 21.put Ftop 22.Preprocessed training set S and testing set D using S′23.Training C4.5 model using training set D′24.Testing C4.5 model using testing set PRi 25.calculate PRi≥PRi-1 26.if Fbest=F*best 27.

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文使用Weka 平臺(tái)作為仿真環(huán)境,Weka 是基于Java 環(huán)境下開源的機(jī)器學(xué)習(xí)以及數(shù)據(jù)挖掘軟件,該軟件集合了大量能承擔(dān)數(shù)據(jù)挖掘任務(wù)的機(jī)器學(xué)習(xí)算法,包括對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,分類、回歸、聚類、關(guān)聯(lián)規(guī)則以及在新的交互式界面上的可視化[15,16].

本文的操作系統(tǒng)指紋數(shù)據(jù)集分別來自Network-Miner、 p0f、 Nmap 的指紋文件[17-19]設(shè)計(jì)的指紋特征庫(kù),本文對(duì)這些指紋特征庫(kù)進(jìn)行整理,形成本次實(shí)驗(yàn)的數(shù)據(jù)集.數(shù)據(jù)集中包含的操作系統(tǒng)類別詳細(xì)信息如表1所示,所有類別包含的特征和特征代表的涵義如表2所示.

表1 數(shù)據(jù)集詳細(xì)信息

表2 數(shù)據(jù)集特征屬性詳細(xì)信息

3.2 實(shí)驗(yàn)流程

本實(shí)驗(yàn)根據(jù)操作系統(tǒng)的不同類別將操作系統(tǒng)指紋數(shù)據(jù)集分為7 個(gè)數(shù)據(jù)子集,每個(gè)子集中訓(xùn)練集Training與測(cè)試集Test 的比例為7:3.

本文提出算法實(shí)驗(yàn)流程如圖1所示,在實(shí)驗(yàn)過程中,分別將未處理的全部特征數(shù)據(jù)集(10 維特征)、本文提出的算法FSSA、FCBF 特征提取算法[12]、基于改進(jìn)SU 的特征選擇算法[1],通過實(shí)驗(yàn)得到的特征子集數(shù)目、網(wǎng)絡(luò)設(shè)備識(shí)別精確率、網(wǎng)絡(luò)設(shè)備識(shí)別召回率、算法時(shí)間復(fù)雜度、實(shí)際算法分類消耗時(shí)間進(jìn)行對(duì)比分析,說明本文算法的優(yōu)勢(shì);此外,在實(shí)驗(yàn)的基礎(chǔ)上,將本文算法的冗余特征分析部分的近似馬爾可夫毯算法換成mRMR 算法[20](后文中稱之為FSSM),與本文提出的算法做對(duì)比實(shí)驗(yàn),驗(yàn)證馬爾可夫毯算法的冗余特征分析能力.關(guān)于SU 特征選擇算法部分對(duì)于閾值δ的設(shè)定參考了文獻(xiàn)[1]中的參數(shù)設(shè)定,本文算法閾值δ設(shè)為0.02,關(guān)于mRMR 實(shí)驗(yàn)部分實(shí)驗(yàn)參數(shù)參考文獻(xiàn)[20],此處不再贅述.

圖1 算法實(shí)驗(yàn)流程圖

3.3 評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)采用整體識(shí)別精確率和召回率來衡量本文特征選擇算法對(duì)網(wǎng)絡(luò)設(shè)備操作系統(tǒng)識(shí)別的精確性.其中精確率和召回率根據(jù)表3 的定義如下:

表3 二分類矩陣

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

3.4.1 算法識(shí)別精確率對(duì)比

按照實(shí)驗(yàn)方案進(jìn)行實(shí)驗(yàn),可以得到各特征選擇算法獲得到的最優(yōu)特征個(gè)數(shù),如表4,可以看出本文提出的算法在各類型樣本的特征屬性集上都有不錯(cuò)的降維效果,在特征選擇的數(shù)目上看,對(duì)于個(gè)別操作系統(tǒng)類型,其它3 種算法和本文提出的算法大致相同,但是本文提出的算法在各類型的數(shù)據(jù)集上得到的特征數(shù)目是基本持平的,其他3 類算法均有波動(dòng),說明對(duì)于不同類別的數(shù)據(jù)集,這3 類算法的特征選擇結(jié)果不穩(wěn)定;表5 展示了各特征選擇算法在各類操作系統(tǒng)類型上的整體識(shí)別精確率,可以明顯看出本文提出的算法在各個(gè)類型的設(shè)備識(shí)別精確率都較高,其它算法雖然在個(gè)別類別上的識(shí)別精確率也不錯(cuò),但是在小類別的數(shù)據(jù)集上,本文提出的算法明顯優(yōu)于其它3 類算法,這是由于在特征選擇的過程中,本文算法加入了Wrapper 式的特征選擇過程,直接將分類器的性能作為特征選擇的評(píng)價(jià)標(biāo)準(zhǔn),這大大提高了本文算法在設(shè)備識(shí)別上的精確率;表6 展示了各特征選擇算法在各類操作系統(tǒng)類型上的召回率,在特征選擇的過程中,本文算法能夠在小類別的數(shù)據(jù)(比如Windows XP 和Linux 2.4)的特征屬性中選擇出更具有強(qiáng)相關(guān)性的特征,能夠減少小類別數(shù)據(jù)被錯(cuò)分為其他類別的數(shù)量,所以本文算法無論是在小類別數(shù)據(jù)還是大類別數(shù)據(jù)上表現(xiàn)都優(yōu)于其他算法．

表4 各特征選擇算法所選特征數(shù)目(個(gè))

表5 各特征選擇算法的精確率(%)

表6 各特征選擇算法的召回率(%)

FSSA 算法和FSSM 算法整體來看特征選擇數(shù)目相對(duì)來說比較平均,但是在小類別數(shù)據(jù)上可以看出,FSSM 算法選擇出的特征明顯多于本文算法;在設(shè)備識(shí)別準(zhǔn)確率和召回率上看,本文算法明顯優(yōu)于FSSM,這是因?yàn)閙RMR 算法原理是用互信息來衡量特征于類別、特征與特征之間的相關(guān)性,而本文算法中的馬爾可夫毯算法部分利用的是對(duì)稱不確定性來衡量特征與類別、特征與特征之間的相關(guān)性,實(shí)驗(yàn)數(shù)據(jù)也表明,在相同的條件下進(jìn)行特征相關(guān)性分析、不同的條件下進(jìn)行特征冗余性分析,本文算法選用的馬爾可夫毯在冗余特征分析上效果更好.

3.4.2 算法復(fù)雜度對(duì)比

假定當(dāng)前特征總數(shù)為n,m是數(shù)據(jù)集的實(shí)例總數(shù).表7 定性分析了各特征選擇算法的時(shí)間復(fù)雜度[7,12,21],表8 展示了實(shí)際實(shí)驗(yàn)過程中,應(yīng)用各特征選擇算法后對(duì)數(shù)據(jù)進(jìn)行分類的時(shí)間,從表中可以看出,本算法由于加入了Wrapper 式特征選擇方法,所以在特征選擇的時(shí)間復(fù)雜度上比較大,在實(shí)際運(yùn)行的特征選擇過程中時(shí)間也較長(zhǎng),但是由于本文算法選擇出的特征相關(guān)性高,冗余小,所以在分類時(shí)運(yùn)行的時(shí)間大大縮小.本文所采用的算法和FCBF 算法均使用馬爾可夫毯算法進(jìn)行特征冗余性分析,在實(shí)際分類時(shí)間上均比使用mRMR 算法進(jìn)行冗余性分析的FSSM 要短,所以本文選用的馬爾可夫毯算法在進(jìn)行冗余性分析時(shí)效果更好.

表7 各算法時(shí)間復(fù)雜度

表8 各算法實(shí)際分類時(shí)間(s)

4 結(jié)論與展望

本文主要是在面向基于網(wǎng)絡(luò)流量分析的網(wǎng)絡(luò)設(shè)備識(shí)別應(yīng)用中,網(wǎng)絡(luò)流量特征選取的問題進(jìn)行了研究,針對(duì)這個(gè)問題提出了一種將Filter 和Wrapper 方式相結(jié)合,基于SU和AMB的網(wǎng)絡(luò)流量特征選擇算法FSSA.實(shí)驗(yàn)表明,該方法下選擇出的特征對(duì)網(wǎng)絡(luò)設(shè)備操作系統(tǒng)類型識(shí)別的精確率相較于經(jīng)典的特征選擇方法有了一定的提高,在小類別數(shù)據(jù)上的召回率也得到了提升,但是在進(jìn)行Wrapper 式特征搜索時(shí)性能代價(jià)也較高.所以針對(duì)實(shí)驗(yàn)過程中的問題,如何對(duì)網(wǎng)絡(luò)設(shè)備更多版本的操作系統(tǒng)類型進(jìn)行識(shí)別,如何更新完善目前的數(shù)據(jù)集,如何提高模型的性能,以及除了操作系統(tǒng)信息之外,如何獲取網(wǎng)絡(luò)設(shè)備其它信息是我們下一步的工作重點(diǎn)[22].