程愛輝 高茂庭

上海海事大學(xué)信息工程學(xué)院 上海 200135

0 引言

對入侵檢測的研究早在20世紀(jì)80年代就開始了，但真正受到重視是隨著Internet興起之后。1980年，James Aderson提出了入侵檢測的概念。入侵檢測系統(tǒng)(Intrusion Detection System,IDS)通過監(jiān)測和分析網(wǎng)絡(luò)流量、系統(tǒng)審計記錄等，來發(fā)現(xiàn)和判斷入侵行為和正常行為，并發(fā)出入侵報警，提醒系統(tǒng)管理員采取相應(yīng)的措施。

入侵檢測技術(shù)主要分為兩大類型：異常入侵檢測和誤用入侵檢測。異常入侵檢測試圖用定量方式描述可接受的行為特征，用來區(qū)分非正常的或者潛在的入侵行為；誤用入侵檢測能直接檢查不利的或不可接受的行為。也就是說，誤用檢測要建立的是入侵的行為模式，誤用檢測利用了已知的攻擊模式，這樣對已知的入侵模式識別率高，但其無法檢測新的攻擊行為；而異常檢測建立的是正常行為模式；但正常模式定義十分復(fù)雜，導(dǎo)致誤報率偏高。而目前來說，由于異常檢測能夠檢測出未知的攻擊，現(xiàn)在成為研究的熱點。

入侵檢測的技術(shù)已經(jīng)在很多方面得到應(yīng)用，支持向量機、神經(jīng)網(wǎng)絡(luò)、模糊集理論、遺傳算法和免疫理論等都已經(jīng)在入侵檢測技術(shù)中應(yīng)用。而本文采用了將聚類算法與最小二乘法支持向量機相結(jié)合的方法，利用聚類算法對入侵檢測樣本進行修剪，將靠近聚類中心的數(shù)據(jù)集合作為訓(xùn)練與測試的樣本集，以減少算法的運行時間，提高算法效率。

1 LS-SVM

支持向量機(Support Vector Machine,SVM)是由Vapnik等人提出的一種基于結(jié)構(gòu)風(fēng)險最小化原則和樣本本身的統(tǒng)計學(xué)習(xí)算法。它的學(xué)習(xí)策略是保持經(jīng)驗風(fēng)險值固定而最小化置信范圍。其原理是利用非線性函數(shù)把輸入數(shù)據(jù)空間映射到高維特征空間，然后在此空間中構(gòu)造分類間隔最大的最優(yōu)分類超平面。

最小二乘法支持向量機(Least Squares Support Vector Machine,LS-SVM)是在標(biāo)準(zhǔn)支持向量機上的一種擴展，由J.A.K SuyKens和J. Vandewalle提出。它采用最小二乘線性系統(tǒng)誤差平方和作為損失函數(shù)，將求解過程變成一組等式方程，加快了求解速度。

設(shè)訓(xùn)練樣本 D = {(xk, yk)|k = 1 ,2,… ,N },其中，xk∈Rn為輸入數(shù)據(jù)，yk∈R是輸出類別。在ω空間(原始空間)中的最小二乘支持向量機分類問題可以描述為：

約束條件：

其中， w ,b,ek與SVM含義相同，γ表示懲罰參數(shù)。

定義拉格朗日函數(shù)：

其中，拉格朗日乘子kRα∈。對上式進行優(yōu)化，并使用KKT條件：

上式可以化為矩陣方程：

其中

同時將Mercer條件帶入到

因此，式(1)的分類問題通過式(5)和式(6)的線性問題得到最終解，而不是解二次規(guī)劃問題。而核函數(shù)可以有多種，如高斯徑向基核函數(shù)、多項式核函數(shù)、多層感知器核函數(shù)和線性核函數(shù)等。

2 選取有效的聚類中心集合

支持向量機具有完備的理論基礎(chǔ)和較好的學(xué)習(xí)機能，但存在對噪聲敏感問題，雖然模糊支持向量機的提出解決了這些問題，但是支持向量機是在大量的樣本中進行尋找，支持向量機分類器會受到樣本數(shù)量，維度等因素的影響。

聚類分析主要功能是挖掘空間中相近的數(shù)據(jù)。利用 K-最鄰近法對數(shù)據(jù)集合進行有效剪枝，其聚類中心集合的選取算法原理如圖1所示。

圖1 聚類中心集合的原理圖

如果兩個類分別記為1p和2p，兩個聚類中心集合分別表示為：

選取兩類數(shù)據(jù)中距離 ( C1i, C1j)最近的兩個聚類中心：

分別作為有效聚類中心集合1PC和2PC的第一個元素，如果一個聚類中心到1PC中的每個元素的距離平均值大于到2PC中每個元素的距離的平均值，則選取該聚類中心加入

如果 d ≥ 0 則 k = 1 ,將 Ckl加入到 P C2中，如果 d ＜ 0 則k= 2 ，將 Ckl加入到 P C1中。重復(fù)上面的過程，根據(jù)有效聚類中心的條件，直到所有聚類中心處理完畢，此時， P C1和PC2中的元素就是靠近邊界的有效聚類中心集。把選擇出來的數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集。

3 基于聚類的LS-SVM的入侵檢測模型

基于LS-SVM的入侵檢測模型如圖2所示，其中包括了數(shù)據(jù)采集，數(shù)據(jù)預(yù)處理，SVM訓(xùn)練，SVM檢測，SVM支持向量庫。

圖2 基于LS-SVM的入侵檢測模型圖

模型的處理流程為：首先由網(wǎng)絡(luò)數(shù)據(jù)捕獲網(wǎng)絡(luò)應(yīng)用層中的數(shù)據(jù)流，通過分析網(wǎng)絡(luò)應(yīng)用層記錄，提取出每條網(wǎng)絡(luò)連接的特征信息(可以直接使用KDD數(shù)據(jù)集)，將數(shù)據(jù)信息提交給數(shù)據(jù)庫預(yù)處理模塊進行處理，得到 SVM的輸入向量；如果出于訓(xùn)練狀態(tài)，則訓(xùn)練SVM，否則出于測試狀態(tài)，這兩個的結(jié)果存入到數(shù)據(jù)庫中，并根據(jù)設(shè)置執(zhí)行相應(yīng)的響應(yīng)操作，如向用戶發(fā)出警報等。

為了提高支持向量機的學(xué)習(xí)速度，將支持向量機與聚類算法相結(jié)合，用K-means聚類算法對訓(xùn)練數(shù)據(jù)進行聚類，獲得每個聚類的聚類中心集合，然后將聚類中心集合作為 LS-SVM的訓(xùn)練樣本進行訓(xùn)練與測試。其算法流程圖如圖3所示。

圖3 算法流程圖

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

本文選用的樣本數(shù)據(jù)時KDD CUP99數(shù)據(jù)集，該數(shù)據(jù)集可分為兩類：正常數(shù)據(jù)(normal)和入侵?jǐn)?shù)據(jù)(拒絕服務(wù)攻擊DoS，掃描與探測Probe，未經(jīng)授權(quán)的遠(yuǎn)程訪問R2L，對本地超級用戶的非法訪問U2R)。數(shù)據(jù)的記錄都是從TCP/IP連接中提取出的 41個特征。由于有些特征是字符型，首先對字符變量處理，將字符型變化為數(shù)值型。其次，需要將數(shù)據(jù)進行歸一化，而采用的歸一化函數(shù)為：

其中p為輸入的數(shù)據(jù)，maxp和minp為輸入數(shù)據(jù)的最大值和最小值，np歸一化后的數(shù)據(jù)。

訓(xùn)練數(shù)據(jù)采用kddcup.data_10_percent_corrected，這種包含了10%正常數(shù)據(jù)的數(shù)據(jù)集。

為了減少數(shù)據(jù)的計算量，采用奇異值分解(SVD)，這是一種正交矩陣分解法，將原有的數(shù)據(jù)集降低維度。由此，選取了41個特征中的18個，得到新的數(shù)據(jù)集。

利用K-最鄰近法對數(shù)據(jù)集合進行有效剪枝，用最靠近判別邊界的聚類中心結(jié)合作為有效的數(shù)據(jù)樣本集合。

5 實驗結(jié)果與分析

實驗中采用LS-SVM1.5工具箱，該工具箱包含了四種核函數(shù)。通過測試發(fā)現(xiàn)RBF核函數(shù)效果更好，采用下面三種函數(shù)來定量描述入侵檢測方法的檢查性能，有如下的定義：

準(zhǔn)確率(precision)= 分類正確的樣本數(shù)/總的樣本數(shù)；

誤報率(False alarm rate)= 正常行為被誤認(rèn)為異常行為的樣本數(shù)/正常樣本總數(shù)；

漏報率(Omission rate)= 異常行為被誤認(rèn)為正常行為的樣本數(shù)/異常樣本總數(shù)；

實驗結(jié)果如表1所示。

表1 基于聚類的LS-SVM入侵檢測算法性能

從上面的實驗結(jié)果分析來看，采用聚類方法和LS-SVM相結(jié)合的方法，訓(xùn)練效率和準(zhǔn)確率都有了提高。

6 結(jié)束語

LS-SVM具有基于結(jié)構(gòu)化風(fēng)險，克服傳統(tǒng)學(xué)習(xí)方法的過擬合、局部最小點的缺點。本文將其應(yīng)用到入侵檢測之中，同時采用到聚類方法對數(shù)據(jù)集合進行預(yù)處理，采用KDDCUP’99數(shù)據(jù)集進行實驗，發(fā)現(xiàn)LS-SVM檢測速度快，大大降低了處理時間，效果明顯。但是LS-SVM失去了SVM特有的稀疏性的優(yōu)點。如何克服LS-SVM 的缺點，提高準(zhǔn)確率，以及如何對其改進，是下一步的研究重點。

[1]Sn-Yun Wu,Ester Yen Data mining-based intrusion detectors Expert Systems with Applications.2009.

[2]Mathias M.Adankon, Mohamed Cheriet Model selection for the LS-SVM. Application to handwriting recognition Pattern Recognition.2009.

[3]Vapnik V . The nature of statistical learning theory[M].New York: Springer Verlag 1995.

[4]http://www.esat.kuleuven.be/sista/lssvmlab.

[5]J.A.K. Suykens, J. Vandewalle, Least Squares Support Vector Machines, World Scientific, Singapore.2002.

[6]http://kdd.ics.uci.edu/databases/kddcup99/kkcup99.html.

[7]邊肇祺,張學(xué)工.模式識別(第二版).清華大學(xué)出版社.2005.

[8]任勛益,王汝傳,謝永娟.基于支持向量機和最小二乘支持向量機的入侵檢測比較.計算機科學(xué).2008.

[9]韓家煒等著,范明,孟小峰譯.數(shù)據(jù)挖掘:概念與技術(shù).機械工業(yè)出版社.2008.