崔 振 ，陳柏生

(1.華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 廈門(mén)361021；2.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京100190)

將所有的網(wǎng)絡(luò)行為分成正常行為和異常行為兩類(lèi)，這樣入侵檢測(cè)問(wèn)題就可以轉(zhuǎn)化成模式分類(lèi)問(wèn)題。入侵檢測(cè)的關(guān)鍵是正常和異常行為模式庫(kù)的建立。目前常用的入侵檢測(cè)方法有基于貝葉斯推理的入侵檢測(cè)[1]、基于模式匹配的入侵檢測(cè)[2]、基于神經(jīng)網(wǎng)絡(luò)的入侵檢測(cè)[3]和基于數(shù)據(jù)挖掘的入侵檢測(cè)[4]，以上方法對(duì)數(shù)據(jù)的要求較高或需要的數(shù)據(jù)量較大。支持向量機(jī)是建立在統(tǒng)計(jì)學(xué)習(xí)理論上的一種新的機(jī)器學(xué)習(xí)方法，由于其在小樣本、高維、非線(xiàn)性等方面的優(yōu)勢(shì)和較好的推廣能力，已經(jīng)在入侵檢測(cè)中得到應(yīng)用[5]?？傮w上，支持向量機(jī)可分為誤用檢測(cè)和異常檢測(cè)兩大類(lèi)，誤用檢測(cè)準(zhǔn)確度高，但難以應(yīng)對(duì)未知攻擊；異常檢測(cè)則常常面臨誤報(bào)率過(guò)高的問(wèn)題。另外，如何應(yīng)對(duì)大規(guī)模的高速數(shù)據(jù)流檢測(cè)、如何實(shí)現(xiàn)在線(xiàn)學(xué)習(xí)、如何減少或消除噪聲數(shù)據(jù)的影響，是入侵檢測(cè)系統(tǒng)面臨的主要挑戰(zhàn)。

近年來(lái)，稀疏表示相關(guān)理論已成為研究的熱點(diǎn)。常用的信號(hào)分解方式通常是非冗余的正交變換，如離散余弦變換、小波變換等。這類(lèi)方式缺乏靈活性，并且許多混合信號(hào)在單一的正交基變換中無(wú)法得到有效的稀疏表示。基于超完備字典的信號(hào)稀疏分解是一種新的信號(hào)表示理論，它采用冗余原子來(lái)構(gòu)造字典，而不是采用傳統(tǒng)的正交基，這樣使字典更富有表現(xiàn)力，同時(shí)為信號(hào)自適應(yīng)的稀疏擴(kuò)展提供了空間。通過(guò)這種超完備字典把數(shù)據(jù)變換到另一空間，即進(jìn)行稀疏編碼，會(huì)帶來(lái)更好的分類(lèi)效果[6]，原因是稀疏表示系數(shù)從某種意義上帶有一定的判別信息[7]。稀疏表示已應(yīng)用于一些具體的領(lǐng)域:學(xué)習(xí)非參數(shù)化字典來(lái)進(jìn)行圖像超分辨率或圖像重建[8]；利用稀疏表示系數(shù)重構(gòu)圖像，用重構(gòu)誤差進(jìn)行(遮擋)人臉識(shí)別[7]等。這些應(yīng)用領(lǐng)域主要集中在圖像處理和壓縮感知中。

本文將稀疏編碼方法應(yīng)用于入侵檢測(cè)。在過(guò)完備詞典學(xué)習(xí)和編碼的過(guò)程中加入l1范數(shù)約束，同時(shí)最小化重構(gòu)殘差和非零個(gè)數(shù)，在去除一定噪聲的同時(shí)也促使映射的特征本身具有稀疏性。這種稀疏性使得學(xué)習(xí)到的系數(shù)特征擁有更好的判別性，即學(xué)習(xí)后的特征在分類(lèi)空間更易于劃分，同時(shí)后端結(jié)合強(qiáng)大的分類(lèi)器——支持向量機(jī)來(lái)進(jìn)行入侵檢測(cè)。實(shí)驗(yàn)中，本文所提的方法與直接用SVM的方法進(jìn)行了比較，顯示了稀疏映射的特征更富有表示力和判別力，驗(yàn)證了所提方法的有效性。

1 稀疏表示理論

1.1 詞典學(xué)習(xí)

構(gòu)建字典歸納起來(lái)有兩種方法[9]：(1)基于數(shù)據(jù)模型建立稀疏字典，如一些小波函數(shù)；(2)從訓(xùn)練集中學(xué)習(xí)一個(gè)字典。本文采用后一種方法構(gòu)建字典。由于數(shù)據(jù)的規(guī)模很大，采用較流行的字典訓(xùn)練方法——SVD分解來(lái)迭代構(gòu)建詞典，即 K-SVD[10]方法。

K-SVD算法由K-均值聚類(lèi)算法推廣而來(lái)，是一種迭代方法，一方面用當(dāng)前字典對(duì)訓(xùn)練集信號(hào)進(jìn)行稀疏編碼，另一方面更新字典的原子以期使得字典更好地表示信號(hào)。這種聯(lián)合的更新加速了算法的收斂。K-SVD算法是靈活的，可以和任何一種追蹤算法一起工作。K-SVD的目標(biāo)函數(shù)：

其中，Y=(y1，y2， …，yN)，yi∈Rn是第 i個(gè)樣本，D=[d1，d2，…，dk]∈Rn×K是詞典，K 是原子數(shù)量，X 是稀疏系數(shù)，||·||0是l0范數(shù)。

K-SVD算法分為兩步:

(1)固定D，更新稀疏系數(shù)X?？梢酝ㄟ^(guò)任何稀疏編碼算法求解，如 LARS、OMP、BP等。

(2)同時(shí)更新D和X。采用SVD分解用最大奇異值對(duì)應(yīng)的特征向量來(lái)更新字典。記字典D第k列為dk，對(duì)應(yīng)的稀疏系數(shù)為xiR(X的第 i行)，式(1)可表示為：

然后對(duì) Ek應(yīng)用 SVD 分解：Ek=U△V。 令 dk=U(：，1)，=△(1，1)×V(：，1)T。

重復(fù)上述兩步到規(guī)定的迭代次數(shù)為止。

1.2 稀疏求解

給定超完備字典 D∈Rn×K，其中 n＜K。 測(cè)試樣本 y∈Rn，把測(cè)試樣本 y表示成字典原子項(xiàng){di}(i=1，…，m)的稀疏線(xiàn)性組合，將目標(biāo)形式化為如下的目標(biāo)函數(shù)：

式(3)可在多項(xiàng)式時(shí)間內(nèi)求解。

目前，求解超完備稀疏表示最優(yōu)化問(wèn)題的稀疏優(yōu)化方法主要有貪婪算法、全局優(yōu)化算法以及其他算法[11]。貪婪算法通過(guò)選取字典中與信號(hào)最匹配的項(xiàng)，迭代地構(gòu)造出信號(hào)的逼近。全局優(yōu)化方法是指在滿(mǎn)足一定的優(yōu)化條件下，使得某個(gè)特殊的目標(biāo)函數(shù)最小，典型的目標(biāo)函數(shù)是凸函數(shù)，并且任何局部最小值也是全局最小值。

本文使用的是Efron等提出的LARS變量選取方法[12]。算法大致描述如下：

首先稀疏系數(shù)設(shè)置為0。然后在詞典里查找與響應(yīng)變量相關(guān)最大的輸入變量，在響應(yīng)變量的投影方向選取最大的步長(zhǎng)，使得其余的某一個(gè)輸入變量與當(dāng)前的輸入變量有同樣的相關(guān)性（在當(dāng)前的重構(gòu)殘差情況下）。這時(shí)候選取了兩個(gè)變量，由這兩個(gè)變量組成一個(gè)子空間，重構(gòu)殘差在子空間上的投影方向繼續(xù)前進(jìn)直到第三個(gè)變量進(jìn)入最相關(guān)的集合。這樣持續(xù)下去直到設(shè)定的閾值為止。

LARS計(jì)算的好處是LARS路徑逐點(diǎn)線(xiàn)性，LARS的目標(biāo)函數(shù)值是逐步下降的。

2 算法流程

至此，給出基于稀疏編碼和SVM(簡(jiǎn)記為SR_SVM)的入侵檢測(cè)算法流程：

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

首先把符號(hào)類(lèi)型數(shù)值化，然后用下式標(biāo)準(zhǔn)化：Zji=(xji-m(xi))/σ(xi)。 其 中 ，m(xi)表 示 第 i個(gè) 屬 性 的 平 均值，σ(xi)為第 i個(gè)屬性的標(biāo)準(zhǔn)差，xji表示第 j條記錄的第i個(gè)屬性，Zji為標(biāo)準(zhǔn)化后的屬性值。然后計(jì)算標(biāo)準(zhǔn)化度量值，最后把每條記錄對(duì)應(yīng)向量單位化，以便于訓(xùn)練字典。

(2)訓(xùn)練字典

設(shè)訓(xùn)練集為 Train，對(duì) Train用 K-SVD算法[10]訓(xùn)練，超完備字典為 D，D∈Rn×K，m為數(shù)據(jù)記錄維數(shù)，n為詞典原子項(xiàng)數(shù)。

(3)對(duì)訓(xùn)練集求解稀疏表示

對(duì)集合 Train中每個(gè)輸入的訓(xùn)練樣本 y，y∈Rn使用LARS算法[12]最小化 l1范數(shù)，求解 y相應(yīng)于 D的稀疏表示x∈RK，并加入到集合 Train_SR。

(4)構(gòu)建支持向量機(jī)模型

使用集合Train_SR的數(shù)據(jù)訓(xùn)練，構(gòu)建支持向量機(jī)模型用于分類(lèi)檢測(cè)。

(5)決策分類(lèi)

設(shè)測(cè)試集為T(mén)est，對(duì)每個(gè)測(cè)試樣本y∈Rn使用式(3)最小化l1范數(shù)，求解y相應(yīng)于D的稀疏表示x∈RK。使用多類(lèi)支持向量機(jī)對(duì)x決策類(lèi)別作為測(cè)試樣本y的類(lèi)別。

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

實(shí)驗(yàn)采用入侵檢測(cè)領(lǐng)域共同認(rèn)可及廣泛使用的基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集——KDD Cup 1999進(jìn)行測(cè)試。

3.1 實(shí)驗(yàn)數(shù)據(jù)及預(yù)處理

實(shí)驗(yàn)中使用的訓(xùn)練集和測(cè)試集分別從KDD99數(shù)據(jù)集10%的訓(xùn)練子集和測(cè)試子集中抽取。為了檢驗(yàn)分類(lèi)器模型的泛化能力，訓(xùn)練集包含22種攻擊，測(cè)試集包含39種攻擊，訓(xùn)練集中未出現(xiàn)的17種攻擊占到整個(gè)測(cè)試集的10%左右。

KDD Cup 1999中涉及3種協(xié)議的數(shù)據(jù)，分別是TCP、UDP和ICMP。為了更精確地構(gòu)建冗余字典，加快訓(xùn)練速度，實(shí)現(xiàn)并行檢測(cè)，構(gòu)建3個(gè)檢測(cè)代理，分別是TCP檢測(cè)代理、UDP檢測(cè)代理和ICMP檢測(cè)代理(在實(shí)際應(yīng)用中可能擁有更多種類(lèi)的數(shù)據(jù)流，可以進(jìn)行擴(kuò)展)。根據(jù)網(wǎng)絡(luò)數(shù)據(jù)流的特點(diǎn)，可以把待檢測(cè)數(shù)據(jù)流進(jìn)行分類(lèi)(下面分為 3類(lèi)：TCP、UDP和 ICMP，在實(shí)際應(yīng)用中可以擴(kuò)展)，這樣做的前提是假設(shè)一次入侵行為不會(huì)使用多種網(wǎng)絡(luò)協(xié)議進(jìn)行通信[13]。針對(duì)不同的網(wǎng)絡(luò)協(xié)議，經(jīng)數(shù)據(jù)預(yù)處理后，就可以去掉一些冗余的屬性（在某協(xié)議下有些屬性的取值是完全相同的）。最后TCP選取了37個(gè)屬性，UDP選取了20個(gè)，ICMP選取了16個(gè)。

3.2 對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)參數(shù)設(shè)置：TCP、UDP和ICMP字典的原子項(xiàng)數(shù)分別為60、40和 40；K-SVD算法迭代20次，稀疏比率約為10%；SVM采用RBF核函數(shù)。

3.2.1協(xié)同檢測(cè)實(shí)驗(yàn)

訓(xùn)練集和測(cè)試集抽取情況如表1所示。

表1 數(shù)據(jù)集抽取情況

為了說(shuō)明算法的有效性，將SR_SVM與SVM進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果如表2所示，可以看到，基于稀疏表示的入侵檢測(cè)對(duì)三種代理都有較高的檢測(cè)率和較低的誤報(bào)率。

表2 協(xié)同檢測(cè)實(shí)驗(yàn)結(jié)果

另外一個(gè)值得注意的現(xiàn)象是UDP數(shù)據(jù)集和ICMP數(shù)據(jù)集屬于嚴(yán)重不平衡數(shù)據(jù)集。對(duì)于支持向量機(jī)來(lái)說(shuō)，這種情況會(huì)影響支持向量機(jī)超平面的建立。而SR_SVM對(duì)于不平衡數(shù)據(jù)集有較好的魯棒性。

3.2.2 不平衡數(shù)據(jù)實(shí)驗(yàn)

為了進(jìn)一步測(cè)試SR_SVM的魯棒性，在TCP數(shù)據(jù)集上進(jìn)行不平衡數(shù)據(jù)集的測(cè)驗(yàn)。

測(cè)試集不變，繼續(xù)使用表1中對(duì)于TCP抽取的數(shù)據(jù)集，訓(xùn)練集分6種情況隨機(jī)抽取，如表3所示。實(shí)驗(yàn)結(jié)果見(jiàn)表4。從表4可以看到，當(dāng)數(shù)據(jù)失衡后，相比于數(shù)據(jù)平衡的情況，檢測(cè)率有了較大程度的下降，但誤報(bào)率波動(dòng)很小，這可能是因?yàn)椴黄胶鈹?shù)據(jù)集影響了支持向量機(jī)超平面的建立。從結(jié)果可以看出，SR_SVM方法減弱了不平衡數(shù)據(jù)集對(duì)SVM的影響，SR_SVM的檢測(cè)率較SVM有較大程度的提高，誤報(bào)率基本上與SVM持平。無(wú)論是正常記錄多于攻擊記錄還是相反情況，SR_SVM在檢測(cè)率上基本平穩(wěn)，而SVM的表現(xiàn)則明顯差了很多。

表3 TCP不平衡記錄抽取情況

表4 不平衡數(shù)據(jù)實(shí)驗(yàn)結(jié)果

3.3 討論

在分類(lèi)前，用稀疏編碼方法自動(dòng)提取稀疏特征，而稀疏性符合人類(lèi)的視覺(jué)機(jī)理[7]。稀疏性帶來(lái)好的性能，這在許多文獻(xiàn)中已有所體現(xiàn)[7，8]。分析原因主要有兩點(diǎn)：

(1)從重構(gòu)的角度來(lái)看，目標(biāo)函數(shù)的第一項(xiàng)是重構(gòu)殘差，最小化重構(gòu)殘差使得系數(shù)幾乎與原來(lái)的樣本具有相同的表示能力。

(2)從稀疏的角度來(lái)看，使得在保證重構(gòu)能力的條件下編碼稀疏盡量稀疏，即對(duì)一些原子具有敏感性，這符合人類(lèi)的視覺(jué)機(jī)理[7]。另外，稀疏性起到部分去噪作用，這在大量的圖像修復(fù)文獻(xiàn)中已得到證實(shí)[8，14]。因此，稀疏性促使很強(qiáng)的判別力。

本文將稀疏編碼與多類(lèi)支持向量機(jī)結(jié)合應(yīng)用到網(wǎng)絡(luò)入侵中的數(shù)據(jù)分類(lèi)，初步的實(shí)驗(yàn)結(jié)果已顯示稀疏性所帶來(lái)的好處。學(xué)習(xí)得到的過(guò)完備詞典可以豐富地表示所有的樣本，在詞典上稀疏編碼也可以有效地學(xué)習(xí)到樣本的判別力特征。在接下來(lái)的實(shí)驗(yàn)中,會(huì)加入更多的實(shí)時(shí)數(shù)據(jù)來(lái)完善系統(tǒng),構(gòu)建可以應(yīng)用到實(shí)際的實(shí)時(shí)高效的入侵檢測(cè)系統(tǒng)。

[1]焦從信，王崇駿，陳世福.基于完全無(wú)向圖的貝葉斯分類(lèi)器在入侵檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)科學(xué)，2008，35(9)：83-86.

[2]姜慶民，吳寧，劉偉華.面向入侵檢測(cè)系統(tǒng)的模式匹配算法研究[J].西安交通大學(xué)學(xué)報(bào)，2009，43(2)：58-62.

[3]劉衍珩,田大新,余雪崗，等.基于分布式學(xué)習(xí)的大規(guī)模網(wǎng)絡(luò)入侵檢測(cè)算法[J].軟件學(xué)報(bào)，2008，19(4)：993-1003.

[4]劉在強(qiáng)，林東岱，馮登國(guó).一種用于網(wǎng)絡(luò)取證分析的模糊決策樹(shù)推理方法[J].軟件學(xué)報(bào)，2007，18(10)：2635-2644.

[5]CHEN R C，CHEN S P.An intrusion detection based on support vector machines with a voting weight schema[J].IEA/AIE 2007：1148-1157.

[6]YANG J，YU K，HUANG T.Efficient highly over-complete sparse coding using a mixture model[C].The 11th European Conference on Computer Vision(ECCV)，Crete，2010.

[7]WRIGHT J，YANG A，GANESH A，et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI)，2009，31(2)：210-227.

[8]YANG J，YU K，HUANG T，et al.Image super-resolution as sparse representation of raw image patches[C].In：IEEE Conference on Computer Vision and Pattern Recognition，(2008)，Anchorage，AK.

[9]RUBINSTEIN R，BRUCKSTEIN A M，ELAD M.Dictionaries for dparse tepresentation modeling[C].Proceedings of the IEEE，2010，98(6).

[10]Aharon M，ELAD M，BRUCKSTEIN A M.The K-SVD：an algorithm for fesigning of overcomplete dictionaries for sparse representation[J].IEEE Trans.on Signal Processing，2006，54(11)：4311-4322.

[11]ZIBULEVSKY M，ELAD M.L1-L2 optimization in signal and image processing[J].IEEE Signal Processing Magazine，2010，27(3)：78-88.

[12]EFRON B，JOHNSTONE I，HASTIE T，et al.Least angle regression[J].Ann.Statist，2004，32(2)：407-499.

[13]TENG S H，DU H L，WU N Q，et al.A cooperative network intrusion detection based on fuzzy SVMs[J].Journal of Network，2010，5(4)：475-483.

[14]MAIRAL J，BACH F，PONCE J，et al.Non-local sparse models for image restoration[C].International Conference on Computer Vision，Tokyo，Japan，2009.