一種多標(biāo)記學(xué)習(xí)入侵檢測算法

錢燕燕， 李永忠， 章 雷， 余西亞

（1.江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003；2.紫光軟件系統(tǒng)有限公司，北京 100084；3.南京郵電大學(xué)通達(dá)學(xué)院，江蘇 南京 210003）

入侵檢測技術(shù)［1］是網(wǎng)絡(luò)安全防御體系的關(guān)鍵技術(shù)之一，主要分為異常檢測和誤用檢測2類。其中異常檢測有檢測新型攻擊的能力，且不需要有入侵的先驗(yàn)知識，其關(guān)鍵是建立系統(tǒng)的正常行為模式及利用該模式去檢測和判斷系統(tǒng)的異常行為。入侵檢測方法結(jié)合一些智能技術(shù)應(yīng)用于入侵檢測系統(tǒng)中成為當(dāng)前研究的重點(diǎn)。文獻(xiàn)［2］提出了基于混合分類模型的入侵檢測技術(shù)；文獻(xiàn)［3］提出云模型半監(jiān)督聚類動(dòng)態(tài)加權(quán)的入侵方法；文獻(xiàn)［4］提出基于混合入侵檢測技術(shù)的網(wǎng)絡(luò)入侵檢測方法等。

多標(biāo)記學(xué)習(xí)（multi－label learning）是機(jī)器學(xué)習(xí)一個(gè)新的研究領(lǐng)域，已經(jīng)成功應(yīng)用在文檔分類［5］、圖像分類［6］、生物基因功能分類［7］等領(lǐng)域。本文研究了基于多標(biāo)記學(xué)習(xí)的KNN（multi－label k－nearest neighbor，ML－KNN）算法，進(jìn)行了必要的改進(jìn)，使其能對入侵檢測KDD CUP99數(shù)據(jù)集進(jìn)行分類，并建立正常行為模式，再利用該模式去檢測和判斷系統(tǒng)的異常行為，然后將結(jié)果與基于聚類的入侵檢測方法進(jìn)行比較。實(shí)驗(yàn)證明，本文方法具有高檢測率和低誤報(bào)率，在一定程度上能夠改善入侵檢測的性能。

1 多標(biāo)記學(xué)習(xí)

1.1 問題定義

假設(shè)X＝Rd代表d維的示例空間，Y＝｛y1，y2，…，yq｝表示q個(gè)類別的標(biāo)記空間。傳統(tǒng)的監(jiān)督學(xué)習(xí)框架是單示例單標(biāo)記學(xué)習(xí)［8－10］，即1個(gè)對象只用1個(gè)示例來表示，而且該示例只對應(yīng)1個(gè)類別標(biāo)記。學(xué)習(xí)的主要目標(biāo)是從數(shù)據(jù)集｛（x1，y1），（x2，y2），…，（xm，ym）｝中可得函數(shù)f：X→Y，其中，xi∈X為一個(gè)示例；yi∈Y為示例xi對應(yīng)的類別標(biāo)記。

在多標(biāo)記學(xué)習(xí)中，1個(gè)對象用1個(gè)示例表示，且該示例可以同時(shí)對應(yīng)多個(gè)類別標(biāo)記［7，10］。給定多標(biāo)記訓(xùn)練集T＝｛（x1，Y1），…，（xm，Ym）｝（xi∈X，Yi∈Y），其中，X為輸入空間；有限個(gè)標(biāo)記的集合Y＝｛1，2，…，Q｝。多標(biāo)記學(xué)習(xí)系統(tǒng)的目標(biāo)是從訓(xùn)練集T中進(jìn)行學(xué)習(xí)，輸出一個(gè)多標(biāo)記分類器h：X→2Y。一般情況下，為了得到上述的多標(biāo)記分類器Yi，學(xué)習(xí)系統(tǒng)將學(xué)習(xí)得到某個(gè)實(shí)值函數(shù)g：X×Y→R。對于訓(xùn)練樣本xi及其對應(yīng)的標(biāo)記集Yi，g（·，·）在屬于Yi的標(biāo)記上輸出較大的值，而在不屬于Yi的標(biāo)記上輸出較小的值，即y1∈Y 以及y2?Yi有g(shù)（xi，y1）＞g（xi，y2）。

多標(biāo)記學(xué)習(xí)一般采用的評價(jià)指標(biāo)［10］有漢明損失、1－錯(cuò)誤率、覆蓋率、排序損失及平均精度。

1.2 問題轉(zhuǎn)換

多標(biāo)記學(xué)習(xí)主要的解決途徑有問題轉(zhuǎn)化法和算法適應(yīng)法。

問題轉(zhuǎn)換法是通過對多標(biāo)記訓(xùn)練樣本進(jìn)行處理，將多標(biāo)記學(xué)習(xí)問題轉(zhuǎn)換為其他已知的學(xué)習(xí)問題（如傳統(tǒng)的單標(biāo)記學(xué)習(xí)問題）進(jìn)行求解。

算法適應(yīng)法是通過改進(jìn)傳統(tǒng)的監(jiān)督學(xué)習(xí)算法，使其能用于多標(biāo)記數(shù)據(jù)的學(xué)習(xí)；代表性的算法有 ML－KNN和Rank－SVM。

入侵檢測可看作二分類問題，即正常記錄和異常記錄。本文結(jié)合以上2種方法，將ML－KNN算法應(yīng)用于入侵檢測，并將入侵?jǐn)?shù)據(jù)集中記錄分為正常和異常，即多個(gè)獨(dú)立的二分類問題，以構(gòu)造多標(biāo)記學(xué)習(xí)系統(tǒng)，提高入侵檢測性能。

2 半監(jiān)督學(xué)習(xí)

半監(jiān)督學(xué)習(xí)的基本思想為：假定一個(gè)存在一個(gè)未知分布的有標(biāo)記數(shù)據(jù)集L＝｛（x1，y1），（x2，y2），…，（xl，yl）｝和一個(gè)未標(biāo)記數(shù)據(jù)集U＝｛x1′，x2′，…，xu′｝，期望通過學(xué)習(xí)函數(shù)f′：X→Y 準(zhǔn)確地對x預(yù)測標(biāo)記y。

半監(jiān)督學(xué)習(xí)［11］是機(jī)器學(xué)習(xí)的一種特殊形式。監(jiān)督學(xué)習(xí)需要對大量有標(biāo)記的數(shù)據(jù)進(jìn)行訓(xùn)練，但通常標(biāo)記數(shù)據(jù)很難獲得，而非標(biāo)記數(shù)據(jù)獲取相對容易，卻難于使用。半監(jiān)督學(xué)習(xí)通過標(biāo)記數(shù)據(jù)與非標(biāo)記數(shù)據(jù)的聯(lián)合使用來解決上述問題，并建立更好的學(xué)習(xí)方式［12］。本文結(jié)合半監(jiān)督學(xué)習(xí)，根據(jù)數(shù)據(jù)固有的性質(zhì)，既不丟失含標(biāo)簽數(shù)據(jù)的信息，又能利用非標(biāo)簽數(shù)據(jù)的信息進(jìn)行學(xué)習(xí)，結(jié)合 MLKNN算法，提高少部分標(biāo)記數(shù)據(jù)的利用效率，以提高分類的精度。

3 基于ML－KNN 的入侵檢測算法

3.1 基于多標(biāo)記學(xué)習(xí)的KNN算法

ML－KNN算法［9，13］是多標(biāo)記學(xué)習(xí)應(yīng)用于文檔和圖像領(lǐng)域中最成熟的算法之一，是對已有k近鄰算法的改進(jìn)。該算法的基本思想是采用“k近鄰”分類準(zhǔn)則，統(tǒng)計(jì)近鄰樣本的類別標(biāo)記信息，通過最大化后驗(yàn)概率（maximum a posterior，MAP）的方式推理未標(biāo)記數(shù)據(jù)的所屬集合［10］。

給定樣本x及其對應(yīng)的標(biāo)記集合y?Y，假定算法共取k個(gè)近鄰。令yx為對應(yīng)樣本x的標(biāo)記向量，對于其中分量yx（s）（x∈Y），當(dāng)x為s時(shí)，yx（s）＝1，否則yx（s）＝0。設(shè) N（x）表示樣本x在訓(xùn)練集中的k個(gè)近鄰的集合，則樣本x的近鄰中屬于每個(gè)標(biāo)記的數(shù)目組成的向量如下：

對于每個(gè)測試實(shí)例t，ML－KNN算法首先確定它在訓(xùn)練集合中的k個(gè)近鄰組成的集合N（t）。令為實(shí)例t中包含標(biāo)記s的事件，為實(shí)例t中不包含標(biāo)記s的事件，（j∈｛0，1，…，k｝）為在t的k個(gè)近鄰中有j個(gè)包含標(biāo)記s的事件?；诮彉?biāo)記計(jì)數(shù)向量Ct，測試樣本t的預(yù)測標(biāo)記向量yt的計(jì)算公式為：

根據(jù)貝葉斯規(guī)則，（2）式可以改寫為：

根據(jù)（3）式可知，可以直接通過統(tǒng)計(jì)計(jì)算的方法從訓(xùn)練集合中得到預(yù)測標(biāo)記向量yt、所需的先驗(yàn)概率和后驗(yàn)概率（j∈｛0，1，…，k｝）。算法偽代碼如下：

其中，T為訓(xùn)練數(shù)據(jù)集；k為近鄰的數(shù)目；t為一個(gè)實(shí)例；yt為輸出的預(yù)測標(biāo)記集合向量；s為一個(gè)平滑參數(shù)，本文采用Laplace平滑參數(shù)，設(shè)s＝1。rt為一個(gè)實(shí)數(shù)向量，用來對Y中的標(biāo)記進(jìn)行等級劃分，rt（l）對應(yīng)的后驗(yàn)概率為。

3.2 基于ML－KNN 的入侵檢測算法

入侵檢測可看作二分類問題，因此正常記錄標(biāo)記為（＋1，－1），入侵記錄標(biāo)記為（－1，＋1）。原有的ML－KNN算法是針對多標(biāo)記學(xué)習(xí)的，算法中包含了多標(biāo)記學(xué)習(xí)評價(jià)指標(biāo)，而本文側(cè)重于入侵檢測，因此將算法根據(jù)入侵檢測評價(jià)指標(biāo)進(jìn)行部分改進(jìn)。刪除有關(guān)多標(biāo)記學(xué)習(xí)評價(jià)指標(biāo)的代碼，修改主程序 ML－KNN－train 和 ML－KNN－test函數(shù)中的代碼，增加compare函數(shù)來驗(yàn)證入侵檢測性能。下面給出算法過程。

輸入：訓(xùn)練數(shù)據(jù)集T，T對應(yīng)的標(biāo)記集合T′，測試數(shù)據(jù)集t，t對應(yīng)的標(biāo)記集合t′，近鄰數(shù)目k，平滑參數(shù)s。

輸出：測試數(shù)據(jù)集t的預(yù)測標(biāo)記集合向量yt，后驗(yàn)概率rt（l），入侵檢測評價(jià)指標(biāo)（檢測率DR和誤報(bào)率FPR）。

（1）對于?ti∈t，計(jì)算先驗(yàn)概率P（Hlb）。

（2）對每個(gè)樣例確定k近鄰。

（3）計(jì)算后驗(yàn)概率P（Elj｜Hlb）。

（4）根據(jù)步驟（1）和步驟（3）的結(jié)果，結(jié)合（3）式得出ti屬于正常或異常的可能概率性O(shè)utputs，若 Outputs＞ 0.5，則yt（i，j）＝＋1；否則yt（i，j）＝－1。

（5）比較預(yù)測標(biāo)記集合向量yt與標(biāo)記集合t′，統(tǒng)計(jì)總的入侵?jǐn)?shù)目N1、正確檢測出的入侵?jǐn)?shù)目N2、總的正常數(shù)目M1及將正常記錄誤判斷為入侵 記 錄 數(shù) 目 （M1－M2），則 DR＝N2／N1，F(xiàn)PR＝（M1－M2）／M1。

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

為了研究多標(biāo)記學(xué)習(xí)理論對入侵檢測率性能的影響，實(shí)驗(yàn)采用了KDD CUP99中的corrected.gz數(shù)據(jù)集［14］。本實(shí)驗(yàn)采用了模式匹配的方式，過濾掉部分入侵類型的攻擊。例如，根據(jù)land屬性的值可判斷是否發(fā)生了land攻擊，land＝1時(shí)，可判斷該條記錄必定為land攻擊。但模式匹配只能檢測出已知攻擊類型，只適合對數(shù)據(jù)進(jìn)行前期處理。為了便于處理，實(shí)驗(yàn)1按corrected.gz分布比例選取大約1／31的數(shù)據(jù)，去掉匹配算法檢測出來的數(shù)據(jù)并剔除一些不常見的入侵記錄，剩余8 324條作為研究對象來檢驗(yàn)本文的入侵檢測模型。實(shí)驗(yàn)2按照實(shí)際網(wǎng)絡(luò)情況選取代表性數(shù)據(jù)進(jìn)行研究分析與對比。

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

每條數(shù)據(jù)由41個(gè)特征屬性和1個(gè)決策屬性構(gòu)成。決策屬性是每條數(shù)據(jù)的所屬類別，在測試時(shí)僅作為判斷條件。其余41個(gè)屬性可分為基本屬性集、內(nèi)容屬性集、流量屬性集和主機(jī)流量屬性集。41個(gè)屬性中有8個(gè)屬性是離散型變量，剩余為連續(xù)型變量。為了使數(shù)據(jù)符合實(shí)驗(yàn)要求，需要對數(shù)據(jù)進(jìn)行預(yù)處理。

數(shù)據(jù)的預(yù)處理包括符號型數(shù)據(jù)的數(shù)據(jù)化處理和數(shù)值數(shù)據(jù)的標(biāo)準(zhǔn)化處理2個(gè)步驟。由于每條數(shù)據(jù)含有3個(gè)符號型屬性，實(shí)驗(yàn)時(shí)應(yīng)將其轉(zhuǎn)化為數(shù)值屬性，3個(gè)符號型屬性分別為protocol－type、service、flag。protocol－type屬性含有tcp、udp、icmp 3個(gè)屬性，分別數(shù)值化為1、2、3。對于service屬性，由于其含有65種取值，若按照之前方法進(jìn)行處理，雖然解決了數(shù)據(jù)的數(shù)值化問題，但將數(shù)據(jù)擴(kuò)大到高維空間中，同時(shí)加大了計(jì)算量。通過分析，將service類型進(jìn)行約簡，并分成9種取值，分別為 http：1；private：2；urp－i：3；smtp：4；ftpdata：5；ecr－i：6；domain－u：7；other：8；others：9。flag屬性含有11種屬性，約簡成sf：1；rej：2；so：3；others：4。

原始數(shù)據(jù)記錄經(jīng)過上述處理后，所有屬性均變?yōu)閿?shù)值，但仍存在問題。對于連續(xù)型的屬性特征，不同的屬性特征有不同的度量標(biāo)準(zhǔn)，會(huì)產(chǎn)生大數(shù)吃小數(shù)的問題。數(shù)據(jù)的某些屬性特征將被掩蓋。為了解決該問題，必須將數(shù)據(jù)的特征屬性值進(jìn)行標(biāo)準(zhǔn)化，進(jìn)行如下變換［12］：

為了方便對數(shù)據(jù)進(jìn)行操作，實(shí)驗(yàn)時(shí)把所有數(shù)據(jù)放到excel表格中，使用xlsread命令導(dǎo)入Matlab中，此時(shí)數(shù)據(jù)經(jīng)過數(shù)值化并歸一化后可以直接用于測試。

4.2 檢測結(jié)果和算法比較分析

入侵記錄主要分為4種：① 掃描與探查（probe）；② 拒絕服務(wù)（dos）；③ 對本地超級用戶的非法訪問（U2R）；④ 未經(jīng)授權(quán)的遠(yuǎn)程訪問（R2L）。本文將normal標(biāo)記為（1，－1）；probe、dos、U2R和R2L標(biāo)記為（－1，1），數(shù)據(jù)的類別分布見表1所列。一個(gè)好的入侵檢測方案具有高檢測率和低誤報(bào)率的特點(diǎn)，因此，本文用檢測率（detection rate，DR）和誤報(bào)率（false positive rate，F(xiàn)PR）來衡量入侵檢測性能。

表1 數(shù)據(jù)的類別分布

利用半監(jiān)督學(xué)習(xí)需要提供少量標(biāo)記數(shù)據(jù)，實(shí)驗(yàn)1設(shè)計(jì)了3個(gè)數(shù)據(jù)集。3個(gè)數(shù)據(jù)集含有相同的數(shù)據(jù)，但是標(biāo)記數(shù)據(jù)所占的比例不同。其中，數(shù)據(jù)集1的標(biāo)記數(shù)據(jù)約占總數(shù)據(jù)的1／4；數(shù)據(jù)集2的標(biāo)記數(shù)據(jù)約占總數(shù)據(jù)的1／3；數(shù)據(jù)集3的標(biāo)記數(shù)據(jù)約占總數(shù)據(jù)的1／2。取不同K值，分別運(yùn)行10次，其檢測率均為100%，數(shù)據(jù)集1的誤報(bào)率均為0.08%，數(shù)據(jù)集2的誤報(bào)率均為0.09%；數(shù)據(jù)集3的誤報(bào)率均為0.12%。上述數(shù)據(jù)表明，ML－KNN算法在標(biāo)記數(shù)據(jù)的訓(xùn)練下建立了一個(gè)較好的模型，誤報(bào)率基本可以忽略不計(jì)。因此，本文提出的方案可以很好地改善入侵檢測性能。

在實(shí)際的網(wǎng)絡(luò)運(yùn)行中，正常數(shù)據(jù)占大多數(shù)，而攻擊是少量的，實(shí)驗(yàn)2把異常數(shù)據(jù)記錄控制在5%以內(nèi)。為了與文獻(xiàn) ［3］作比較，實(shí)驗(yàn)選取dos的攻擊為neptune、smurf；R2L的攻擊為guesspasswd；U2R 的攻擊為land－module、buffer－overflow、rootkit；probe的攻擊為portsweep，并新增portsweep、satan、back、teardrop 入 侵 記 錄。本文共做了3組實(shí)驗(yàn)測試算法的性能，3組實(shí)驗(yàn)選取了不同的數(shù)據(jù)集對算法進(jìn)行了測試，其中數(shù)據(jù)類型及分布見表2所列。

表2 實(shí)驗(yàn)測試數(shù)據(jù)比例

利用半監(jiān)督學(xué)習(xí)理論，3個(gè)測試數(shù)據(jù)集部分標(biāo)記（比例控制在30%～40%），取不同的K值，分別運(yùn)行10次，實(shí)驗(yàn)結(jié)果見表3所列。以入侵檢測的誤報(bào)率和檢測率作為衡量標(biāo)準(zhǔn)，盡量選擇高

檢測率和低誤報(bào)率下的實(shí)驗(yàn)數(shù)據(jù)。經(jīng)權(quán)衡比較，本實(shí)驗(yàn)結(jié)果見表4所列。

表3 不同K值下的實(shí)驗(yàn)2ML－KNN算法分類準(zhǔn)確率 %

表4 測試結(jié)果 %

不同方案的檢測率和誤報(bào)率見表5所列。

表5 入侵檢測性能比較 %

由表5可知，本文算法在保證檢測率的同時(shí)，有效地降低了入侵檢測系統(tǒng)的誤報(bào)率與k－means硬聚類算法、模糊C均值（fuzzy C－means，F(xiàn)CM）及文獻(xiàn) ［3］相比，本文方法的檢測率有了較大的提高，誤報(bào)率很低，基本可以忽略不計(jì)，一定程度上解決了目前入侵檢測存在的一些問題。但是該模型純粹采用KNN技術(shù)，在一些情況下是可行的，但是對于已知的標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)，沒有區(qū)別哪能個(gè)更重要。

5 結(jié)束語

實(shí)驗(yàn)證明本文提出的ML－KNN算法在入侵檢測方面是可行和有效的，優(yōu)于傳統(tǒng)的入侵檢測算法?；?ML－KNN的入侵檢測算法將KNN算法和貝葉斯理論相結(jié)合，構(gòu)造學(xué)習(xí)分類器，從而對KDD CUP99數(shù)據(jù)集進(jìn)行有效的分類。基于多標(biāo)記學(xué)習(xí)的算法有很多，將其應(yīng)用于入侵檢測系統(tǒng)中進(jìn)行性能分析以及對海量數(shù)據(jù)進(jìn)行分析等將是今后研究的重點(diǎn)。

［1］ 羅守山.入侵檢測［M］.北京：北京郵電大學(xué)出版社，2003：1－10.

［2］ 黃 越，臧 洌.基于混合分類模型的入侵檢測技術(shù)研究［D］.南京：南京航空航天大學(xué)，2012.

［3］ 張 杰，李永忠.云模型半監(jiān)督聚類動(dòng)態(tài)加權(quán)的入侵檢測方法［J］.昆明理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，38（4），44－47，59.

［4］ 尹才榮，葉 震，單國華，等.基于混合入侵檢測技術(shù)的網(wǎng)絡(luò)入侵檢測方法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，32（1）：69－72.

［5］ Schapire R E，Singer Y.Boostexter：a boosting－based system for text categorization［J］.Machine Learning，2000，39（2／3）：135－168.

［6］ 宋相法，焦李成.基于稀疏編碼和集成學(xué)習(xí)的多示例多標(biāo)記圖像分類方法［J］.電子與信息學(xué)報(bào)，2013，35（3）：622－626.

［7］ 陳曉峰，王士同，曹蘇群.半監(jiān)督多標(biāo)記學(xué)習(xí)的基因功能分析［J］.智能系統(tǒng)學(xué)報(bào)，2008，3（1）：83－90.

［8］ 周志華，張敏靈.MIML：多示例多標(biāo)記學(xué)習(xí)［J］.機(jī)器學(xué)習(xí)及其應(yīng)用，2009，3（2）：218－234.

［9］ Zhang Minling，Zhou Zhihua.A lazy learning approach to multi－label learning［J］.Pattern Recognition，2007，40（7）：2038－2048.

［10］ 周志華，楊 強(qiáng).機(jī)器學(xué)習(xí)及其應(yīng)用 ［M］.北京：清華大學(xué)出版社，2011：179－199.

［11］ Zhu Xiaojin.Semi－supervised learning literature survey［D］.Madison：University of Wisconsin，2006.

［12］ 謝中華.Matlab統(tǒng)計(jì)分析與應(yīng)用：40個(gè)案例分析［M］.北京：北京航空航天大學(xué)出版社，2010：321－326.

［13］ 郭躍健.多值屬性和多標(biāo)記數(shù)據(jù)分類［D］.長沙：中南大學(xué)，2010.

［14］ KDD Cup 1999Data［EB／OL］.（1999－10－28）［2014－05－23］.http：／／kdd.ics.uci.edu／databases／kddcup99／kddcup99.html.