基于極限學習機與改進K-means算法的入侵檢測方法

王琳琳，劉敬浩，付曉梅

(1.天津大學電氣自動化與信息工程學院，天津 300072；2.天津大學海洋科學與技術學院，天津 300072)

1 引言

隨著互聯網的飛速發展，網絡的設計缺陷與安全漏洞帶來了一系列的安全問題，必須采用主動防范的入侵檢測技術來改善網絡的安全狀況。1998年哥倫比亞大學的Lee等人[1]將數據挖掘技術引入到入侵檢測系統中，他們證明了可以使用數據挖掘技術發現用戶和程序的特征模式，通過相關特征訓練分類器可以達到識別入侵的目的。

近年來，學者針對如何將數據挖掘技術應用到入侵檢測之中做了大量的研究。文獻[2-4]分別討論了支持向量機SVM(Support Vector Machine)、BP神經網絡以及樸素貝葉斯算法等數據挖掘算法在入侵檢測中的應用。但是，這些傳統的算法存在一些問題，例如需要人工調整的參數較多、檢測精度不高、容易陷入局部極小值、需要耗費大量的計算時間等。2006年Huang等人[5]提出了極限學習機ELM(Extreme Learning Machine)，ELM是一種針對單隱含層前向神經網絡的新算法。ELM算法的輸入層與隱含層間的連接權重向量以及隱含層神經元的閾值是隨機產生的，此二者在訓練過程中無需調整。ELM算法只需要設定隱含層的神經元個數，同時ELM算法不需要迭代，訓練速度非?？?。與傳統算法相比，ELM算法具有學習速度快、泛化性能好等優點，因此適用于對入侵攻擊的分類檢測。但是，ELM算法對于激活函數的選擇具有依賴性，激活函數選擇的好壞直接影響著分類效果。文獻[6]提出了一種基于核函數的ELM入侵檢測分類方法，該方法采用徑向基RBF核函數(Radial Basis Function)來代替ELM隱含層的激勵函數。但是，由于部分攻擊連接與正常網絡連接的差異較小，進而影響了ELM算法在入侵檢測中的效果。聚類分析作為一種常用的數據挖掘技術，其算法簡單、計算復雜度低，適用于入侵檢測系統。Portnoy等人[7]較早提出了基于聚類分析的入侵檢測技術，利用無標簽的數據進行訓練，從而檢測出未知攻擊。K-means算法是經典的聚類算法。文獻[8]將K-means算法應用于入侵檢測之中。但是，傳統的K-means算法的聚類結果受初始簇中心點的影響嚴重，初始簇中心點選取不當很容易造成聚類結果陷入局部最優解或導致錯誤的聚類結果，很多學者針對這個問題進行了研究。文獻[9]提出了一種改進的半監督K-means算法，利用有標簽的數據獲得初始聚類中心。文獻[10]采用加權局部方差結合最大最小法，優化K-means初始聚類中心的選取。但是，經過這些改進后的K-means算法仍然局限于人工設置初始聚類簇數目，而不是根據特征本身來確定聚類簇數目，使得聚類結果不穩定。多級分類的入侵檢測方法可以提高入侵檢測系統的準確率。文獻[11]提出了基于多級神經網絡分類的入侵檢測方法，根據攻擊類別分別訓練神經網絡，進而對不同種類的攻擊進行分類。在多級模型的基礎上結合多種數據挖掘方法，可以集成多種算法的優點。文獻[12]提出了結合了貝葉斯聚類和決策樹算法的多級混合入侵檢測分類器。文獻[13]提出了結合改進的CatSub算法、K-point算法等算法的多級混合入侵檢測方法。

為了解決傳統單一算法難以對不同攻擊進行有效檢測的問題，基于算法級聯的思想，本文提出了一種結合ELM和改進的K-means算法的混合式入侵檢測方法。仿真結果表明，本文所提出的入侵檢測方法可以提高對入侵攻擊的檢測效率，并可以降低誤報率。

2 基于PReLU激活函數的極限學習機算法

2.1 極限學習機理論

典型的單隱含層前向神經網絡SLFNs(Single-hidden Layer Feedforward Neural networks)結構如圖1所示，由輸入層、隱含層與輸出層三層組成。

Figure 1 Structure of single-hidden layer feedforward neural networks圖1 單隱含層前向神經網絡結構

給定N個任意不同的樣本xi,ti，xi=[xi1,xi2,…,xin]T∈Rn，ti=[ti1,ti2,…,tim]T∈Rm，其具有k個隱含層神經元的SLFNs輸出函數可表示為：

j=1,2,…,N

(1)

其中,g(x)為激活函數，wi=[wi1,wi2,…,win]T為輸入層與第i個隱含層神經元間的連接權重向量，βi=[βi1,βi2,…,βim]T為第i個隱含層神經元與輸出層間的連接權重向量，bi為第i個隱含層神經元的閾值，oj為第j個輸入樣本對應的輸出值。

給定k個隱含層神經元和激活函數g(x)，則存在wi,βi,bi使得SLFNs能以零誤差逼近這N個任意不同的樣本xi,ti，即:

(2)

(3)

式(3)可表示為:

Hβ=T

(4)

其中,

Hw1,…,wk,b1,…,bk,x1,…,xN=

(5)

其中，H是該神經網絡的隱含層輸出矩陣，H的第i列是第i個關于輸入x1,x2,…,xN的隱含層節點輸出。

極限學習機ELM算法是一種求解SLFNs的學習算法。由Huang等人[5]的證明可知，當激活函數g(x)無限可微時，SLFNs的參數并不需要全部進行調整，w=[w1,w2,…,wk]n×k和b=[b1,b2,…,bk]T可以隨機選擇，且在訓練的過程中保持不變，而β可以通過求解以下方程組的最小二乘解獲得:

β-T‖

(6)

其解為:

(7)

其中，H+為隱含層輸出矩陣H的Moore-Penrose廣義逆。

2.2 基于PReLU激活函數的極限學習機算法

激活函數選擇得是否合適直接影響極限學習機ELM的學習效果。傳統的ELM算法采用的激活函數是S型非線性連續光滑單調的Sigmoid函數，其函數定義為:

(8)

由Huang等人的證明可知，ELM可選擇一個任意區間無限可微的函數作為激活函數，所以激活函數的選擇并不唯一。文獻[14]提出了一種修正線性單元ReLU(Rectified Linear Units)的新型激活函數，ReLU激活函數具有稀疏激活性，在深度卷積神經網絡中的訓練時間優于傳統的Sigmoid函數[15]。ReLU激活函數的定義為:

g(x)=max(0,x)

(9)

文獻[16]在ReLU激活函數基礎上提出了參數修正的線性修正單元PReLU(Parametric Rectified Linear Unit)。PReLU作為ReLU函數的改進函數，引入了修正參數，提高了神經網絡的準確率，而所增加的計算量可以忽略不計。PReLU引入了非常少量的額外參數，額外參數的數量等于信道總數，考慮權重總數時這是可以忽略的，所以PReLU函數不會造成過度擬合以及導致額外的風險。所以，本文將PReLU函數作為激活函數以優化ELM的學習效果。PReLU函數定義為：

g(x)=max(0,x)+amin(0,x)

(10)

3 改進的K-means算法

3.1 K-means算法

1967年MacQueen[17]提出了K-means算法，該算法是一種基于劃分的經典的聚類算法，其聚類結果使相似度較高的樣本聚集到同一類簇，而不同類簇間的樣本相似度較低[18]。K-means算法的基本思想是：首先隨機選取k個點作為初始聚類中心，然后計算各個樣本到聚類中心的距離，把樣本歸到離它距離最小的聚類中心所在的簇，對調整后的新簇重新計算平均值得到新的聚類中心，以上過程不斷重復，直至相鄰兩次的聚類中心沒有任何變化，即準則函數收斂。

K-means算法在計算兩個樣本之間的距離時，考慮到入侵檢測系統對于算法復雜度的要求，一般采用算法復雜度較小的歐氏距離，計算公式如下：

d(xi,xj)=

(11)

其中,xi=[xi1,xi2,…,xip]與xj=[xj1,xj2,…,xjp]是兩個維度為p的數據對象。

K-means算法常采用誤差平方和作為準則函數，其定義如下：

(12)

其中,x是所在聚類空間的數據對象，k為聚類簇的總數，mi為聚類簇Ci的中心，即平均值。

3.2 改進的K-means算法

傳統的K-means算法隨機選擇初始聚類中心，而不同的初始中心會導致不同的聚類效果，如果初始聚類中心選擇不當，很容易陷入局部最優。同時，傳統的K-means算法需要人為事先確定聚類數目k，但是算法不能分辨出所設定的聚類數目是否合適。因此，本文提出一種通過設定距離閾值來選擇初始聚類中心，同時可以通過計算自動生成聚類數目k，最終通過比較數據點與鄰近點的距離從而進行聚類改進的K-means算法。

對訓練集中的正常網絡連接以及與正常網絡連接特征相似的攻擊，分別采用改進的K-means算法進行聚類，生成若干種類的聚類中心數據集，以聚類得到的聚類中心數據集作為新的高質量的訓練數據集。

改進的K-means算法描述如下：

算法1改進的K-means算法

輸入：數據集D,距離閾值λ。

輸出：聚成k類的聚類中心數據集D′。

步驟1隨機選擇αj∈D作為第一個聚類中心c1，令k=1；

步驟2For(?αi∈D,i≠j)

步驟3If(歐氏距離d(αi,cn)>λ,n=1,…,k)

步驟4k=k+1//αi為新的聚類中心ck

步驟5End If;

步驟6以cn為中心，計算歐氏距離d(αi,cn)，將ai劃分到dmin(αi,cn)的類cn中；

步驟8End For;

步驟9For(?αi∈D)

步驟10重復步驟6,步驟7；

步驟11If (生成的聚類中心cn保持穩定)

步驟12輸出聚成k類的聚類中心數據集D′；

步驟13End If;

步驟14End For;

將改進的K-means算法與投票策略結合進行入侵檢測。對于測試集中的每一個樣本點β，分別計算其與改進的K-means算法中得到的每一個聚類中心cn的歐氏距離。選取其中距離最小的m個點，并判斷這m個聚類中心所屬的攻擊類別，取數量最多的聚類中心的類別作為β的類別，若聚類中心類別的數目出現相等的情況，則將β歸于與其距離最近的點的類中。

4 入侵檢測數據集與檢測算法流程

4.1 NSL-KDD數據集

NSL-KDD數據集[19]一種比KDD CUP99[20]數據集更新的用于入侵檢測測試的數據集。作為KDD CUP99數據集的改進版，NSL-KDD數據集解決了KDD CUP99數據集中數據冗余的問題，避免了分類器在訓練與分類過程中偏向于頻繁出現的連接數據。NSL-KDD數據集中僅包含網絡流量數據，每一條數據網絡連接數據由41個網絡連接屬性值以及一個類別標簽構成。NSL-KDD的訓練集中有125 973條網絡連接記錄，測試集有22 544條網絡連接記錄，包含了正常數據連接Normal以及39種攻擊類型，這39種攻擊類型分屬于DOS、Probe、U2R以及R2L等四大類攻擊，其中訓練集中包含22種攻擊，而測試集中多出了17種攻擊，這些僅在測試集中出現的攻擊類型，可以評價入侵檢測算法對新型未知攻擊的檢測能力。

4.2 入侵檢測算法流程

綜合多種數據挖掘算法構建出的多級混合式入侵檢測方法，可以集成多種算法的優點。很多學者提出了結合不同分類器的級聯式入侵檢測系統。文獻[12]與文獻[13]所提出的入侵檢測模型在第一級對DOS與Probe攻擊進行分類，第二級對Normal進行分類，第三級對U2R與R2L進行分類。文獻[21]所提出的入侵檢測模型在第一級對DOS與Probe攻擊進行分類，第二級對U2R攻擊進行分類，第三級對R2L與Normal進行分類。

本文所采用的檢測模型如圖2所示。由于DOS和Probe這兩大類攻擊在短時間內會向同一目的計算機發起大量的連接請求，其網絡連接數據與Normal的網絡連接數據差別很大，所以在第一層與第二層分別采用基于PReLU激活函數的ELM算法對這兩大類攻擊進行檢測。而在U2L與R2L這兩大類攻擊中黑客需要獲得受害者計算機的非法訪問權限，所以生成的網絡連接記錄將與正常用戶的網絡連接記錄非常相似，同時這兩類攻擊的數量相對較少，因此在第三層采用改進的K-means算法結合投票策略對Normal、U2R與R2L進行分類。

Figure 2 Architecture of the intrusion detection model圖2 入侵檢測模型結構

5 實驗與結果分析

實驗的硬件環境為2.20 GHz Intel Core i5 CPU，4 GB RAM計算機，軟件環境為Matlab R2014a。本文采用NSL-KDD數據集進行仿真驗證實驗。

為了評價本文算法的檢測效果，采用精確度、召回率、準確率、F1值、檢測率與誤報率等六項指標進行衡量。首先定義如下參數：

(1)TP(True Positive)：入侵攻擊被判斷為入侵攻擊的網絡連接數。

(2)TN(True Negative)：正常連接被判斷為正常連接的網絡連接數。

(3)FP(False Positive)：非入侵攻擊被判斷為入侵攻擊的網絡連接數。

(4)FN(False Negative)：入侵攻擊被判斷為正常連接的網絡連接數。

基于以上參數，衡量指標的定義如下：

(1)精確度Precision=TP/(TP+FP);

(2)召回率Recall=TP/(TP+FN);

(3)準確率Accuracy=(TP+TN)/(TP+TN+FP+FN);

(4)F1值F1-measure=2*Precision*Recall/(Precision+Recall);

(5)檢測率Detection Rate：總體測試集中被正確分類的數據所占的比例。

(6)誤報率FalseAlarmRate=FP/(TP+FP)。

從NSL-KDD數據集的訓練集與測試集中，各抽取10 000條數據進行算法有效性驗證。實驗數據的構成如表1所示。

Table 1 Composition of training and testing data sets

在進行模型訓練之前，首先要對數據集中的數據進行預處理。對于數據的預處理可分為兩個步驟：

(1)字符型特征轉化為數值特征。

NSL-KDD數據集共有三種字符型特征，分別是協議類型(Protocol Type)、網絡服務(Service)以及連接的狀態(Flag)。將Protocol Type特征中的TCP標注為1，UDP標注為2，TCMP標注為3。將67種Service特征按名稱首字母順序分別標注為1～67，將11種Flag特征按順序分別標注為1～11。將訓練數據按照標注的攻擊類型分為Normal、DOS、Probe、U2R以及R2L五類。

(2)標準化與歸一化處理。

將由(1)得到的數據進行標準化與歸一化處理，消除由于不同特征值度量單位的差異對實驗結果產生的影響。標準化公式為：

(13)

歸一化公式為：

(14)

其中,x1min為標準化后該特征值的最小值，x1max為標準化后該特征值的最大值，x2為歸一化后的結果。

對本文所提出的入侵檢測模型進行參數設置。第一層與第二層ELM模型采用PReLU激活函數，參數a設置為0.25，隱含層神經元個數設定為200。第三層模型取每一條測試數據與經過改進的K-means算法生成的新訓練集中距離最近的3個點，進行投票策略，其中改進的K-means算法的閾值設定分別是Normal為0.6，U2R為0.4，R2L為0.4。每次實驗重復20次求平均值。將本文所提算法與BP、SVM和ELM算法進行比較。BP的隱含層神經元個數設定為30，lr為0.1，epochs為100，goal為0.001。SVM采用廣泛使用的LIBSVM[22]軟件包，SVM采用C-SVC類型，RBF核函數，gamma參數為0.11，懲罰因子C為256。ELM算法的激活函數為Sigmoid函數，隱含層神經元個數設定為200。每次實驗重復20次求平均值，實驗結果如表2和表3所示。

Table 2 Detection rate comparisonamong different algorithms

由表2的結果看來，本文所提出的檢測方法對于Normal、Probe和DOS的檢測率都有很好的效果。相比之下，U2R與R2L的檢測率相對較低，這是因為U2R與R2L攻擊在訓練集的樣本數量小于DOS與Probe攻擊的，同時測試集R2L攻擊中新出現了snmp get attack攻擊與snmp guess攻擊，這兩種攻擊的特征屬性與Normal的特征屬性高度相似，導致大多數R2L被誤判為Normal。

Table 3 Detection result comparisonamong different algorithms

對比傳統的BP、SVM和ELM三種算法，本文所提出的檢測方法對于不同種類攻擊的檢測率都有提升，尤其是對U2R、R2L這兩類攻擊的檢測效果有大幅度提升。由表3可知，本文所提出的算法具有較高的精確度、召回率以及F1值，在提高檢測準確率的同時降低了檢測的誤報率，可以說明本文所提出的檢測方法的有效性。

將本文所提出的檢測方法與同樣基于NSL-KDD數據集的其他檢測算法進行對比，其他檢測算法分別是文獻[13]提出的多層混合式MLH(Mutil Level Hybrid)入侵檢測方法、文獻[23]提出的基于最大最小法K-means的入侵檢測方法、文獻[24]提出的基于人工神經網絡ANN(Artificial Neural Network)的入侵檢測方法，以及文獻[25]提出的基于神經網絡和K-means的混合算法進行入侵檢測的FP-ANK方法，對比結果如表4所示。

Table 4 Detection rate comparison of different methods

由對比結果可知，本文提出的檢測方法與其他方法相比準確率最高，且誤報率相比其他方法最低。基于最大最小法K-means的入侵檢測方法對于各種攻擊的檢測效果較差，且誤報率較高。ANN檢測方法對于正常流量的檢測效果較好，但是對于網絡攻擊的檢測效果較差。FP-ANK檢測方法對于Normal、DOS與Probe的檢測率與本文所提出的檢測方法基本相同，但是對U2R與R2L的檢測率明顯低于本文所提出的混合式檢測方法。MLH檢測方法對于五類網絡流量的檢測效果與本文所提方法基本相同，但是準確率和誤報率低于本文所提出的方法。

6 結束語

本文采用基于ELM與改進K-means的混合式入侵檢測方法，結合了不同算法的優點，提高了對于網絡正常數據與異常數據的檢測率，同時降低了誤報率。基于PReLU激活函數的ELM算法提高了算法的分類效果，改進的K-means算法避免了初始中心選擇不當對聚類效果的影響，同時改進的K-means算法與基于距離的投票策略提高了對攻擊的分類效果。在今后的研究中，要進一步探索如何改進方法使其應用于實時網絡當中。