陳天宇，吳 凡，馬世杰，李 雷

(南京郵電大學(xué)，江蘇 南京 210023)

基于CS和LS-SVM的入侵檢測(cè)算法

陳天宇，吳 凡，馬世杰，李 雷

(南京郵電大學(xué)，江蘇 南京 210023)

由于入侵檢測(cè)中具有原始數(shù)據(jù)量大、維度較高、冗余度較大等特點(diǎn),導(dǎo)致傳統(tǒng)的入侵檢測(cè)算法面對(duì)海量數(shù)據(jù)時(shí)檢測(cè)識(shí)別度低，運(yùn)行時(shí)間長，性能較差。為此，文中提出了一種將壓縮感知和最小二乘支持向量機(jī)應(yīng)用于入侵檢測(cè)系統(tǒng)的方法。其創(chuàng)新點(diǎn)主要在于：引入壓縮采樣技術(shù)提取原始數(shù)據(jù)特征，在保留原數(shù)據(jù)主要特征的前提下，將高維數(shù)據(jù)轉(zhuǎn)化為低維數(shù)據(jù)；利用最小二乘支持向量機(jī)直接在觀測(cè)域中訓(xùn)練和分類數(shù)據(jù)，且核函數(shù)通過組合核函數(shù)構(gòu)建。仿真結(jié)果表明，運(yùn)用壓縮感知進(jìn)行特征提取能夠極大保留原始特征，而最小二乘支持向量機(jī)能夠在不損失精度的前提下加速分類。該方法能夠較大地減少訓(xùn)練時(shí)間，并可以有效提高檢測(cè)精度。

壓縮感知；最小二乘法；支持向量機(jī)；入侵檢測(cè)

1 概 述

隨著經(jīng)濟(jì)社會(huì)的發(fā)展，互聯(lián)網(wǎng)被廣泛應(yīng)用于社會(huì)的各行各業(yè)。然而，人們?cè)谙硎芑ヂ?lián)網(wǎng)帶來的便利和高效的同時(shí)，其本身卻充斥著安全隱患，對(duì)財(cái)產(chǎn)安全和隱私造成了巨大威脅。在這樣的社會(huì)大環(huán)境下，入侵檢測(cè)系統(tǒng)(IntrusionDetectionSystem，IDS)成為當(dāng)下的熱門研究領(lǐng)域[1],其本質(zhì)上是個(gè)分類問題[2]。目前，入侵檢測(cè)主要通過機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)等方式完成[3-8]，其一般流程為提取入侵行為或正常行為的數(shù)據(jù)特征，構(gòu)建出一個(gè)特征數(shù)據(jù)庫，從中進(jìn)行模式匹配，從而完成入侵檢測(cè)。然而，一方面，隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，寬帶不斷提高，受限于奈奎斯特采樣定理，實(shí)時(shí)采樣對(duì)軟硬件的要求不斷提高；另一方面，采用機(jī)器學(xué)習(xí)的方法進(jìn)行入侵檢測(cè)時(shí)，必然會(huì)面對(duì)樣本數(shù)據(jù)相關(guān)性大、維數(shù)高，訓(xùn)練重復(fù)樣本多，訓(xùn)練時(shí)間過長并且入侵樣本標(biāo)記困難等問題[2]。

近年來，由D.Donoho等在矩陣分析、統(tǒng)計(jì)理論、優(yōu)化理論等研究的基礎(chǔ)上，提出了一種新的信息采樣理論—壓縮感知理論(CompressedSensing,CS)[9-12]。該理論指出，若信號(hào)在某個(gè)變換域內(nèi)是稀疏的，則該信號(hào)就可以用一個(gè)與變換基不相關(guān)的觀測(cè)矩陣實(shí)現(xiàn)從高維到低維的映射，并可以將低維信號(hào)重構(gòu)，從而恢復(fù)出完整的信息。

在壓縮感知理論中，基于l0范數(shù)最小化的重構(gòu)算法是NP-hard問題，即使將問題轉(zhuǎn)化為l1范數(shù)最小化問題，計(jì)算復(fù)雜度仍為O(N3)[13]，其中N為信號(hào)長度。

上述算法都無法避免對(duì)信號(hào)進(jìn)行重構(gòu)，同時(shí)傳統(tǒng)的基于壓縮感知的入侵檢測(cè)在低信噪比下檢測(cè)效果不佳。

支持向量機(jī)[14](SupportVectorMachine,SVM)以統(tǒng)計(jì)學(xué)為基礎(chǔ)，通過尋求結(jié)構(gòu)風(fēng)險(xiǎn)最小化來實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍的最小化，廣泛應(yīng)用于統(tǒng)計(jì)分類中，適用于線性可分以及線性不可分的問題，在較小的訓(xùn)練樣本時(shí)也能獲得良好的分類效果。

基于以上原因，文中將原始入侵檢測(cè)數(shù)據(jù)進(jìn)行預(yù)處理后，選取合適的觀測(cè)矩陣和稀疏基進(jìn)行壓縮采樣并歸一化，進(jìn)而將觀測(cè)域下的低維數(shù)據(jù)通過最小二乘支持向量機(jī)建立檢測(cè)分類器，完成入侵檢測(cè)。在最小二乘支持向量機(jī)中，采用組合核函數(shù)的形式，尋求獲得最近似實(shí)際的分類模型。仿真結(jié)果表明，與經(jīng)典的機(jī)器學(xué)習(xí)方法和壓縮感知算法相比，文中提出的算法可以有效改善支持向量的稀疏性，提高系統(tǒng)的魯棒性，檢測(cè)性能大幅提高，且利用組合核函數(shù)實(shí)現(xiàn)的分類結(jié)果較一般核函數(shù)的分類結(jié)果更精確。

2 壓縮感知和支持向量機(jī)理論

2.1 壓縮感知

(1)

式(1)表明，S,X其實(shí)表示的是同一個(gè)信號(hào)，只不過S為信號(hào)在Φ域中的表現(xiàn)形式，X為其在時(shí)域中的表現(xiàn)形式。在Φ域中，假設(shè)X的加權(quán)系數(shù)列S中有K個(gè)非零系數(shù)，則X可以用這K個(gè)非零系數(shù)來表示，稱信號(hào)X的稀疏度為K。當(dāng)K?N時(shí)，就稱信號(hào)X具有稀疏性。

y=ψX=ψΦS=ΘS

(2)

其中：ψ為觀測(cè)矩陣；Θ=ψΦ是一個(gè)M×N維的壓縮傳感矩陣。

由于ψ是事先選定的確定矩陣，不隨信號(hào)X變化，因此該測(cè)量過程具有非自適應(yīng)性。

綜上所述，壓縮感知理論共包括如下三方面：

第一，對(duì)于信號(hào)X，找到其稀疏正交基Φ，使得該信號(hào)在Φ上稀疏表示。

第二，找到一個(gè)M×N的測(cè)量矩陣ψ，使其與Φ滿足非相關(guān)性，即在對(duì)信號(hào)X進(jìn)行壓縮和降維的過程中，基本不損失原信號(hào)X中的重要信息，該概念等價(jià)于Θ滿足約束等距條件[15](RestrictedIsometryProperty,RIP)，也就是說,對(duì)?s∈RN,有

(3)

其中，ε為失真因子。

第三，提取原信號(hào)X中的特征信息后，采取適當(dāng)?shù)闹貥?gòu)算法和分類算法，恢復(fù)數(shù)據(jù)信息并進(jìn)行檢測(cè)。

2.2 支持向量機(jī)

支持向量機(jī)是一種強(qiáng)大的機(jī)器學(xué)習(xí)工具，已經(jīng)在模式識(shí)別、數(shù)據(jù)挖掘等方面廣泛應(yīng)用。由于壓縮感知技術(shù)在重構(gòu)時(shí)采用的算法復(fù)雜度較高，而Calderbank等證明了利用SVM將觀測(cè)域上的壓縮信號(hào)直接分類，其性能與對(duì)原信號(hào)直接使用SVM的精度類似[16]，故文中采用將觀測(cè)域下的信號(hào)直接利用SVM對(duì)數(shù)據(jù)進(jìn)行訓(xùn)練和分類。

假設(shè)樣本集為:(xi,yi),i=1,2,…,n,x∈Rd,y∈{-1,1}是類別標(biāo)號(hào)。在一個(gè)d維的空間中，在處理非線性問題時(shí)，先尋找某個(gè)非線性映射Π:Rd→H,x→π(x)，將原空間Rd中的數(shù)據(jù)x映射到一個(gè)高維特征空間中，接著通過引入某種符合Mercer條件的核函數(shù)K(xi,xj)，使支持向量機(jī)可以在高維核空間中直接利用線性函數(shù)進(jìn)行線性分類。那么在高維空間中所用的分類函數(shù)如下所示：

(4)

其中：ai>0是Lagrange因子；b是域值。

目前使用率最高的核函數(shù)有如下三種：

(1)多項(xiàng)式核函數(shù)(Poly)。

K(x,xi)=[(x·xi)+l]q

(5)

(2)Gauss徑向基核函數(shù)(RBF)。

K(x,xi)=exp(-‖x-xi‖2/σ2)

(6)

(3)Sigmoid核函數(shù)(Sigmoid)。

K(x,xi)=tanh[v(x×xi)+c]

(7)

其中，v>0,c<0。

為使分類性能最佳，文中采用改進(jìn)交叉驗(yàn)證[17]的方法尋找最優(yōu)參數(shù)。

3 基于壓縮感知和支持向量機(jī)的入侵檢測(cè)算法

3.1 稀疏基和隨機(jī)觀測(cè)矩陣的選取

基于對(duì)入侵檢測(cè)數(shù)據(jù)的認(rèn)識(shí)，文中的稀疏基采用Gabor緊框架字典[18]，其概念為：設(shè)a和b是給定的正數(shù)，對(duì)于?g∈L2:L2(R)，稱函數(shù)族。

ψj,k(x):=ei2πkbxg(x-ja),j,k∈Z

(8)

為經(jīng)過函數(shù)g得到的Gabor函數(shù)系。

若存在常數(shù)A和B(0

(9)

則稱函數(shù)族(見式(8))是L2的一個(gè)Gabor框架，并且稱A和B為框架界。而‖·‖和<·>表示L2的范數(shù)和內(nèi)積，當(dāng)式(9)中A和B相等時(shí)稱對(duì)應(yīng)的框架為緊框架。

文中采用的觀測(cè)矩陣為伯努利隨機(jī)矩陣，其定義為：

對(duì)于矩陣Φ∈RM×N，矩陣中每個(gè)獨(dú)立且同分布的元素都服從伯努利分布，即：

(10)

伯努利矩陣具有較強(qiáng)的隨機(jī)性，因此符合RIP要求。

3.2 支持向量機(jī)的選取

文中采用最小二乘支持向量機(jī)(LS-SVM)的方法。LS-SVM是普通支持向量機(jī)的一種擴(kuò)展，將最小二乘線性誤差的平方和取作損失函數(shù)，從而求解一系列方程組。LS-SVM收斂速度快，計(jì)算速度得到提升，因而在非線性分類和模式識(shí)別中得到廣泛應(yīng)用。

Π為非線性映射，則最小二乘支持向量機(jī)的優(yōu)化問題可以描述為：

(11)

其中：w為權(quán)值向量；γ為正則化系數(shù)；ek為實(shí)際值與真實(shí)值的誤差。

約束條件為：

yk[ωTp(xk)+b]=1-ekk=1,2,…,N

另一方面，文中選用Poly+RBF構(gòu)成組合核函數(shù)，其形式為：

K(x,xi)=α[(x·xi)+l]q+(1-α)× exp(-‖x-xi‖2/σ2)

(12)

式中，權(quán)系數(shù)α(0≤α≤1)作用是調(diào)節(jié)兩種核函數(shù)在作用時(shí)的權(quán)重。

當(dāng)求出優(yōu)化問題的解ai之后，組合核函數(shù)LS-SVM模型的決策超平面可表示為：

(13)

3.3 系統(tǒng)建立及算法描述

文中的入侵檢測(cè)系統(tǒng)共包含5個(gè)模塊，具體如圖1所示。

圖1 入侵檢測(cè)系統(tǒng)模塊

具體實(shí)現(xiàn)步驟表述為：

Step1：數(shù)據(jù)預(yù)處理。將原始數(shù)據(jù)向量化表示。

Step2:文中采用隨機(jī)伯努利矩陣作為測(cè)量矩陣，采用Gabor緊框架字典作為稀疏正交基。此時(shí)測(cè)量矩陣和稀疏基滿足RIP條件，且利用它們構(gòu)成的壓縮傳感矩陣能夠有效地完成對(duì)原始數(shù)據(jù)的特征提取，得到低維向量。

Step3：將得到的特征數(shù)據(jù)歸一化到[0,1]的區(qū)間內(nèi)，避免特別大的數(shù)據(jù)在數(shù)據(jù)集中起主導(dǎo)作用，提高計(jì)算精度。歸一化操作如下式：

yi'=(yi-min)/(max-min)

(14)

Step4：使用最小二乘支持向量機(jī)分類。作為對(duì)照，并分別選取RBF核函數(shù)和POLY+RBF組合核函數(shù)。

Step5：運(yùn)用K折交叉驗(yàn)證(K-CV)的方法選擇最優(yōu)參數(shù)。將數(shù)據(jù)集平均分成10組，接著輪流將當(dāng)中9組作為訓(xùn)練集，其中1組作為驗(yàn)證集(或叫測(cè)試集)，進(jìn)行10次實(shí)驗(yàn)。依據(jù)每次實(shí)驗(yàn)的分類精度，來確定針對(duì)該數(shù)據(jù)集的最優(yōu)參數(shù)。

Step6：利用最優(yōu)參數(shù)對(duì)數(shù)據(jù)進(jìn)行訓(xùn)練和預(yù)測(cè)，得出最優(yōu)分類器和分類結(jié)果。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)所用平臺(tái)為：IntelCorei5，CPU2.4GHz，4GBRAM,Windows8.1操作系統(tǒng),Matlab2014a。

4.2 數(shù)據(jù)來源

為分析比較實(shí)驗(yàn)結(jié)果，文中采用KDDCUP99入侵檢測(cè)數(shù)據(jù)集，對(duì)分別采用不同的特征提取策略，不同的支持向量機(jī)，以及不同核函數(shù)的情況下得到的入侵檢測(cè)算法效率進(jìn)行比較分析。KDD99數(shù)據(jù)集總共由500萬條記錄組成，文中攻擊數(shù)據(jù)采用KDDCUP99中特征比較顯著的四大類網(wǎng)絡(luò)攻擊：

(1)DenialOfService(DOS)；

(2)RemotetoLocal(R2L)；

(3)UsertoRoot(U2R);

(4)Surveillanceorprobe(Pride)。

由于數(shù)據(jù)量過大，文中只采用部分?jǐn)?shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，如表1所示。

表1 仿真實(shí)驗(yàn)用的樣本數(shù)據(jù)

4.3 對(duì)比算法和性能指標(biāo)

為使文中的CS-LSSVM算法檢測(cè)結(jié)果更具說服力，引入KPCA-LSSVM,CS-SVM,LSSVM進(jìn)行對(duì)比試驗(yàn)，并引入如下四個(gè)檢測(cè)性能指標(biāo)：

運(yùn)行時(shí)間t。

4.4 結(jié)果與分析

圖2～4展示了以KDDCPU99為實(shí)驗(yàn)數(shù)據(jù)，在五種算法中進(jìn)行入侵檢測(cè)的DR、FDR和LDR。通過對(duì)比，進(jìn)一步研究了基于壓縮感知的入侵檢測(cè)下具備的優(yōu)勢(shì)和不足。

圖2 不同算法的檢測(cè)率

圖3 不同算法的漏報(bào)率

圖4 不同算法的誤報(bào)率

對(duì)圖2～圖4進(jìn)行分析，可得到如下結(jié)論：

(1)在CS-SVM算法中，使用POLY+RBF構(gòu)成的組合核的性能指標(biāo)明顯優(yōu)于單一核，可見組合核更能充分劃分出數(shù)據(jù)的特性。

(2)CS-LSSVM的性能指標(biāo)明顯優(yōu)于KPCA-LSSVM。這表明就特征提取的策略而言，在本問題中，運(yùn)用CS的效果優(yōu)于KPCA。

(3)CS-LSSVM的性能指標(biāo)稍遜色于CS-SVM。這是運(yùn)用了最小二乘理論，犧牲分類精度換取收斂速度所導(dǎo)致的必然結(jié)果；然而，CS-LSSVM的精確度足以滿足一般要求。

(4)CS-LSSVM的性能指標(biāo)與采用普通LSSVM的性能指標(biāo)相接近。這說明文中采用的稀疏基和觀測(cè)矩陣是合適的，能夠充分提取原始數(shù)據(jù)的特征。

五種算法的運(yùn)行時(shí)間如圖5所示。

圖5 訓(xùn)練與檢測(cè)時(shí)間

由圖5可知，采用CS-LSSVM算法，運(yùn)行時(shí)間比KPCA-LSSVM更快，且遠(yuǎn)少于其他算法。這是由于運(yùn)用壓縮采樣進(jìn)行特征提取，極大地降低了數(shù)據(jù)維度，提高了數(shù)據(jù)稀疏性導(dǎo)致支持向量維度降低，樣本的訓(xùn)練和分類速度快。結(jié)果表明了文中CS-LSSVM的巨大優(yōu)勢(shì)和運(yùn)用價(jià)值。

5 結(jié)束語

文中提出了一種基于壓縮感知并結(jié)合運(yùn)用最小二乘支持向量機(jī)的入侵檢測(cè)算法。該方法的創(chuàng)新點(diǎn)在于：通過選擇恰當(dāng)?shù)南∈杌陀^測(cè)矩陣，有效對(duì)網(wǎng)絡(luò)數(shù)據(jù)壓縮采樣。特別在網(wǎng)絡(luò)數(shù)據(jù)獲取階段，直接使用特征提取后的數(shù)據(jù)，用組合核LSSVM構(gòu)建的分類器進(jìn)行訓(xùn)練和入侵檢測(cè)。仿真實(shí)驗(yàn)的結(jié)果表明，該方法與傳統(tǒng)方法在DR、FDR和LDR上較為接近，但運(yùn)行時(shí)間遠(yuǎn)優(yōu)于傳統(tǒng)的非壓縮方法。另一方面，采用組合核函數(shù)構(gòu)建的LSSVM在分類精度上明顯優(yōu)于單一的核函數(shù)。未來，還將進(jìn)一步研究如何提高檢測(cè)精度，以及在已經(jīng)正確分類的前提下如何對(duì)壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)等問題。

[1]PerezFM,Mora-GimenoF,Marcos-JorqueraD,etal.Networkintrusiondetectionsystemembeddedonasmartsensor[J].IEEETransactionsonIndustrialElectronics,2011,58(3):722-732.

[2]HofmannA,SickB.Onlineintrusionalertaggregationwithgenerativedatastreammodeling[J].IEEETransactionsonDependableandSecureComputing,2011,8(2):282-294.

[3]PandaM，AbrahamA，PatraMR.Ahybridintelligentapproachfornetworkintrusiondetection[J].ProcediaEngineering,2012,30:1-9.

[4]YusufovnaSF.Integratingintrusiondetectionsystemanddatamining[C]//Procof2008internationalsymposiumonubiquitousmultimediacomputing.[s.l.]:[s.n.],2008:256-259.

[5]YiYang,WuJiansheng,XuWei.IncrementalSVMbasedonreservedsetfornetworkintrusiondetection[J].ExpertSystemswithApplications,2011,38(6):7698-7707.

[6] 陳桂林，王生光，徐靜妹，等.基于GA和組合核的SVM入侵檢測(cè)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(2):148-151.

[7] 張 拓，王建平.基于CQPSO-LSSVM的網(wǎng)絡(luò)入侵檢測(cè)模型[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(2):113-116.

[8] 黃 亮，吳 帥，譚國律，等.基于EPSO-RVM的網(wǎng)絡(luò)入侵檢測(cè)模型[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(3):85-88.

[9]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.

[10]CandesEJ,RombergJ,TaoT.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.

[11] 戴瓊海，付長軍，季向陽.壓縮感知研究[J].計(jì)算機(jī)學(xué)報(bào),2011,34(3):425-434.

[12] 焦李成，楊淑媛，劉 芳，等.壓縮感知回顧與展望[J].電子學(xué)報(bào),2011,39(7):1651-1662.

[13]DonohoD,TannerJ.Observeduniversalityofphasetransitionsinhigh-dimensionalgeometry,withimplicationsformoderndataanalysisandsignalprocessing[J].PhilosophicalTransactionsofTheRoyalSocietyAMathematicalPhysicalandEngineeringSciences,2009,367(1906):4273-4293.

[14] 郭麗娟，孫世宇，段修生.支持向量機(jī)及核函數(shù)研究[J].科學(xué)技術(shù)與工程,2008,8(2):487-490.

[15]ZhangT.SparserecoverywithorthogonalmatchingpursuitunderRIP[J].IEEETransactionsonInformationTheory,2011,57(9):6215-6221.

[16]TyS,AllenJD,LiuX.Detectionofmodifiedmatrixencodingusingmachinelearningandcompressedsensing[J].ProcofSPIE,2011,8063(13):1216-1217.

[17] 鄧 蕊，馬永軍，劉堯猛.基于改進(jìn)交叉驗(yàn)證算法的支持向量機(jī)多類識(shí)別[J].天津科技大學(xué)學(xué)報(bào),2007,22(2):58-61.

[18]YangMeng,ZhangLei,ShiuSCK,etal.GaborfeaturebasedrobustrepresentationandclassificationforfacerecognitionwithGaborocclusiondictionary[J].PatternRecognition,2013,46(7):1865-1878.

IntrusionDetectionAlgorithmBasedonCompressedSensingandLeastSquareSupportVectorMachine

CHENTian-yu，WUFan，MAShi-jie，LILei

(NanjingUniversityofPostsandTelecommunications，Nanjing210023，China)

Duetoalargeamountofrawdata,andhighdimensionandredundancyinintrusiondetection,resultingintheproblemoflowrecognition,longoperationandbadperformancefortraditionalintrusiondetectionalgorithminthefaceofmassivedatadetection,amethodofcombiningcompressedsensingandleastsquaresupportvectormachinetoapplytointrusiondetectionsystemisputforward.Innovationasfollows:Introducingcompressivesamplingtoextractthefeaturefromtheoriginaldata,thehighdimensionaldataistransformedintoalowoneonthepremiseofretainingthemainfeaturefororiginaldata;Usingleastsquaresupportvectormachinetodirectlytrainandclassifydataintheobservationdomain,andthekernelfunctionisconstructedbythecombinationofkernelfunction.Simulationshowthatusingcompressedsensingtoextractthefeaturecansignificantlyreservetheoriginalfeature.Moreover,leastsquaresupportvectormachinecanacceleratethespeedofclassifyingwithoutlosingaccuracy.Thismethodcangreatlyreducethetrainingtime,andeffectivelyimprovetheaccuracyofdetection.

compressedsensing;leastsquaremethod;supportvectormachine;intrusiondetection

2015-04-21

2015-07-23

時(shí)間：2016-05-05

國家自然科學(xué)基金資助項(xiàng)目(61070234，61071167，61373137)；國家大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201410293021Z)

陳天宇(1994-)，男，研究方向?yàn)闄C(jī)器學(xué)習(xí)；李 雷，教授，博士生導(dǎo)師，研究方向?yàn)楹朔椒?、機(jī)器學(xué)習(xí)、模糊數(shù)理論和智能控制等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0814.024.html

TP

A

1673-629X(2016)05-0099-05

10.3969/j.issn.1673-629X.2016.05.021