基于稀疏編碼和SVM的協(xié)同入侵檢測*

崔 振 ，陳柏生

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

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

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

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

1 稀疏表示理論

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

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

K-SVD算法由K-均值聚類算法推廣而來，是一種迭代方法，一方面用當(dāng)前字典對訓(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?？梢酝ㄟ^任何稀疏編碼算法求解，如 LARS、OMP、BP等。

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

然后對 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。 測試樣本 y∈Rn，把測試樣本 y表示成字典原子項(xiàng){di}(i=1，…，m)的稀疏線性組合，將目標(biāo)形式化為如下的目標(biāo)函數(shù)：

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

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

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

首先稀疏系數(shù)設(shè)置為0。然后在詞典里查找與響應(yīng)變量相關(guān)最大的輸入變量，在響應(yī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)線性，LARS的目標(biāo)函數(shù)值是逐步下降的。

2 算法流程

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

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

首先把符號(hào)類型數(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)化度量值，最后把每條記錄對應(yīng)向量單位化，以便于訓(xùn)練字典。

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

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

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

對集合 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ī)模型用于分類檢測。

(5)決策分類

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

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

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

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

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

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

3.2 對比實(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é)同檢測實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

3.3 討論

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

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

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

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

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

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

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

[4]劉在強(qiáng)，林東岱，馮登國.一種用于網(wǎng)絡(luò)取證分析的模糊決策樹推理方法[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.