基于SU和AMB的網絡流量特征選擇算法①

龐玉林,李喜旺

1(中國科學院 沈陽計算技術研究所,沈陽 110168)

2(中國科學院大學,北京 100049)

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

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

1 相關工作

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

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

2 算法設計

2.1 FSSA

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

2.2 SU 算法

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

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

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

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

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

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

2.3 AMB 算法

馬爾可夫毯是進行特征冗余性分析的一種常用的工具,在一個特征空間中,目標特征的馬爾可夫毯包含了它的所有信息,所以非馬爾可夫毯就可以看成是目標特征的冗余特征.因此通過發現目標特征的馬爾可夫毯就可以精確確定目標特征的冗余特征,從而降低特征空間的維數,達到特征選擇的目的[13].

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

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

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

2.4 算法流程描述

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

算法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 實驗分析

3.1 實驗環境與數據集

本文使用Weka 平臺作為仿真環境,Weka 是基于Java 環境下開源的機器學習以及數據挖掘軟件,該軟件集合了大量能承擔數據挖掘任務的機器學習算法,包括對數據進行預處理,分類、回歸、聚類、關聯規則以及在新的交互式界面上的可視化[15,16].

本文的操作系統指紋數據集分別來自Network-Miner、 p0f、 Nmap 的指紋文件[17-19]設計的指紋特征庫,本文對這些指紋特征庫進行整理,形成本次實驗的數據集.數據集中包含的操作系統類別詳細信息如表1所示,所有類別包含的特征和特征代表的涵義如表2所示.

表1 數據集詳細信息

表2 數據集特征屬性詳細信息

3.2 實驗流程

本實驗根據操作系統的不同類別將操作系統指紋數據集分為7 個數據子集,每個子集中訓練集Training與測試集Test 的比例為7:3.

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

圖1 算法實驗流程圖

3.3 評價指標

本實驗采用整體識別精確率和召回率來衡量本文特征選擇算法對網絡設備操作系統識別的精確性.其中精確率和召回率根據表3 的定義如下:

表3 二分類矩陣

3.4 實驗結果與分析

3.4.1 算法識別精確率對比

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

表4 各特征選擇算法所選特征數目(個)

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

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

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

3.4.2 算法復雜度對比

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

表7 各算法時間復雜度

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

4 結論與展望

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