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

崔 振 ，陳柏生

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

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

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

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

1 稀疏表示理論

1.1 詞典學習

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

K-SVD算法由K-均值聚類算法推廣而來，是一種迭代方法，一方面用當前字典對訓練集信號進行稀疏編碼，另一方面更新字典的原子以期使得字典更好地表示信號。這種聯合的更新加速了算法的收斂。K-SVD算法是靈活的，可以和任何一種追蹤算法一起工作。K-SVD的目標函數：

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

K-SVD算法分為兩步:

(1)固定D，更新稀疏系數X。可以通過任何稀疏編碼算法求解，如 LARS、OMP、BP等。

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

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

重復上述兩步到規定的迭代次數為止。

1.2 稀疏求解

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

式(3)可在多項式時間內求解。

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

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

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

LARS計算的好處是LARS路徑逐點線性，LARS的目標函數值是逐步下降的。

2 算法流程

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

(1)數據預處理

首先把符號類型數值化，然后用下式標準化：Zji=(xji-m(xi))/σ(xi)。 其 中 ，m(xi)表 示 第 i個 屬 性 的 平 均值，σ(xi)為第 i個屬性的標準差，xji表示第 j條記錄的第i個屬性，Zji為標準化后的屬性值。然后計算標準化度量值，最后把每條記錄對應向量單位化，以便于訓練字典。

(2)訓練字典

設訓練集為 Train，對 Train用 K-SVD算法[10]訓練，超完備字典為 D，D∈Rn×K，m為數據記錄維數，n為詞典原子項數。

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

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

(4)構建支持向量機模型

使用集合Train_SR的數據訓練，構建支持向量機模型用于分類檢測。

(5)決策分類

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

3 實驗與分析

實驗采用入侵檢測領域共同認可及廣泛使用的基準評測數據集——KDD Cup 1999進行測試。

3.1 實驗數據及預處理

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

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

3.2 對比實驗

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

3.2.1協同檢測實驗

訓練集和測試集抽取情況如表1所示。

表1 數據集抽取情況

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

表2 協同檢測實驗結果

另外一個值得注意的現象是UDP數據集和ICMP數據集屬于嚴重不平衡數據集。對于支持向量機來說，這種情況會影響支持向量機超平面的建立。而SR_SVM對于不平衡數據集有較好的魯棒性。

3.2.2 不平衡數據實驗

為了進一步測試SR_SVM的魯棒性，在TCP數據集上進行不平衡數據集的測驗。

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

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

表4 不平衡數據實驗結果

3.3 討論

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

(1)從重構的角度來看，目標函數的第一項是重構殘差，最小化重構殘差使得系數幾乎與原來的樣本具有相同的表示能力。

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

本文將稀疏編碼與多類支持向量機結合應用到網絡入侵中的數據分類，初步的實驗結果已顯示稀疏性所帶來的好處。學習得到的過完備詞典可以豐富地表示所有的樣本，在詞典上稀疏編碼也可以有效地學習到樣本的判別力特征。在接下來的實驗中,會加入更多的實時數據來完善系統,構建可以應用到實際的實時高效的入侵檢測系統。

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

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

[3]劉衍珩,田大新,余雪崗，等.基于分布式學習的大規模網絡入侵檢測算法[J].軟件學報，2008，19(4)：993-1003.

[4]劉在強，林東岱，馮登國.一種用于網絡取證分析的模糊決策樹推理方法[J].軟件學報，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.