基于改進FastICA算法的入侵檢測樣本數(shù)據(jù)優(yōu)化方法

杜曄，張亞丹，黎妹紅，張大偉

?

基于改進FastICA算法的入侵檢測樣本數(shù)據(jù)優(yōu)化方法

杜曄，張亞丹，黎妹紅，張大偉

（北京交通大學(xué)計算機與信息技術(shù)學(xué)院，北京 100044）

為更好實現(xiàn)對入侵檢測樣本數(shù)據(jù)的優(yōu)化處理，提出了一種改進的快速獨立成分分析(FastICA)算法，采用基于加權(quán)相關(guān)系數(shù)進行白化處理以減少信息損失，并優(yōu)化牛頓迭代法使其滿足三階收斂。對算法進行了細致描述，分析了算法的時間復(fù)雜度。實驗結(jié)果表明，該方法可有效減少數(shù)據(jù)信息損失，具有迭代次數(shù)少、收斂速度快等優(yōu)點，可有效提高入侵檢測樣本數(shù)據(jù)的優(yōu)化效率。

入侵檢測；快速獨立成分分析；數(shù)據(jù)優(yōu)化；牛頓迭代法

1 引言

隨著信息技術(shù)的發(fā)展，網(wǎng)絡(luò)已經(jīng)滲入到人們工作、生活的方方面面，帶來了巨大的便利。但隨之而來的是，針對網(wǎng)絡(luò)的攻擊也層出不窮，入侵計算機系統(tǒng)的手段方法不斷增加，已呈智能化與協(xié)同性發(fā)展。根據(jù)國家互聯(lián)網(wǎng)應(yīng)急中心（CNCERT）發(fā)布的《2013年我國互聯(lián)網(wǎng)網(wǎng)絡(luò)安全態(tài)勢綜述》[1]，2013年CNCERT監(jiān)測發(fā)現(xiàn)境內(nèi)有1.5 萬臺主機被APT木馬控制，6.1萬個網(wǎng)站被境外通過植入后門實施控制，1 090萬余臺主機被境外控制服務(wù)器控制。網(wǎng)絡(luò)攻擊事件的頻繁發(fā)生，不僅對廣大網(wǎng)民利益造成了影響，更對社會經(jīng)濟和國家安全造成威脅和挑戰(zhàn)。為了保護系統(tǒng)資源，作為一種積極、主動的動態(tài)防護技術(shù)，入侵檢測的研究與發(fā)展就愈發(fā)顯得重要。

1980年，John Anderson的報告“Computer security threats monitoring and surveillance”[2]被認(rèn)為是最早涉及到入侵檢測領(lǐng)域的文獻。他將入侵企圖定義為故意地、非授權(quán)地試圖訪問信息、修改信息、致使系統(tǒng)不可靠或不可用。由于互聯(lián)網(wǎng)的資源共享原則，很難識別非授權(quán)用戶，攻擊者可以利用大量網(wǎng)絡(luò)主機來占用網(wǎng)絡(luò)的關(guān)鍵資源使網(wǎng)絡(luò)服務(wù)質(zhì)量顯著降低，即發(fā)生入侵攻擊[3]。入侵檢測的作用就在于及時地發(fā)現(xiàn)各種攻擊以及攻擊企圖，并做出反應(yīng)[4]。入侵檢測技術(shù)可以分為誤用入侵檢測和異常入侵檢測。誤用檢測通過預(yù)先精確定義的入侵模式進行檢測，如果入侵者攻擊方式恰好匹配上檢測系統(tǒng)中的模式庫，入侵行為即被檢測到。異常檢測認(rèn)為入侵活動是未知的，是異常活動的子集。任何對正常行為模式的偏離達到一定程度時，都認(rèn)為是入侵事件的發(fā)生。

由于入侵檢測需要對大量的系統(tǒng)實時數(shù)據(jù)進行分析和處理，例如基于主機的檢測需要對CPU、內(nèi)存、進程等參數(shù)進行分析，且通常這些數(shù)據(jù)是高維的，這必將會造成維數(shù)災(zāi)難，增加入侵檢測系統(tǒng)分析的復(fù)雜度、時效性。因此，在進行入侵檢測前有必要對數(shù)據(jù)進行優(yōu)化處理。它不僅可以降低問題規(guī)模，減小問題復(fù)雜度，而且可以去除不相關(guān)和冗余的數(shù)據(jù)，從而增加檢測的準(zhǔn)確度。

本文提出了一種改進的FastICA算法，采用基于加權(quán)相關(guān)系數(shù)的白化處理過程有效減少數(shù)據(jù)精簡帶來的信息損失，通過改進牛頓迭代法實現(xiàn)3階段收斂，以減少迭代次數(shù)，提高收斂速度。

2 相關(guān)工作

入侵檢測通常需要收集大量的歷史數(shù)據(jù)，而這些數(shù)據(jù)往往是高維的且具有相關(guān)性、冗余性，這不僅會導(dǎo)致入侵檢測效率低，而且會影響檢測正確率。因此，需要對數(shù)據(jù)進行預(yù)先優(yōu)化處理。

Derek Smith[5]提出結(jié)合貝葉斯網(wǎng)絡(luò)和主成分分析（PCA）對數(shù)據(jù)進行優(yōu)化的方法，利用貝葉斯網(wǎng)絡(luò)去除和入侵檢測無關(guān)的特征屬性以及各屬性間的相關(guān)性，然后利用PCA進一步降維。文獻[6]利用互信息去除和屬性有最大相關(guān)性的屬性，利用PCA對剩余的屬性特征進行降維處理。上述2種方法都利用了PCA，而PCA只能去除各屬性間的相關(guān)性并不能保證各屬性相互獨立。文獻[7]采用基于步進指標(biāo)搜索算法和指標(biāo)空間分離技術(shù)進行云指標(biāo)提取，得到最能刻畫云行為和健康狀況的最大關(guān)聯(lián)性標(biāo)準(zhǔn)和最小冗余度標(biāo)準(zhǔn)，然后使用最小封閉球體將云指標(biāo)數(shù)據(jù)點從數(shù)據(jù)空間映射到內(nèi)核空間進行降維。Husanbir[8]提出把數(shù)據(jù)優(yōu)化分為2部分，利用MI提取出最能表示計算機行為的特征屬性，對于仍包含多個特征的集合，通過空間分離技術(shù)進一步提取特征，完成數(shù)據(jù)的優(yōu)化處理。由于以上2種方法都引入了空間分離技術(shù)，這將加大計算過程的復(fù)雜性。文獻[9]提出了一種關(guān)于特征的分層關(guān)系來表示它與異常的相關(guān)程度，并利用EdgeRank算法確定對某個特定故障起關(guān)鍵作用的特征屬性。文獻[10]提出了一種MRPC Selection算法，對每一類故障選擇最相關(guān)主成分集合，并且為了適應(yīng)動態(tài)性引入神經(jīng)網(wǎng)絡(luò)計算主成分。以上2種方法都是針對每一類故障找到最相關(guān)的主成分，但若收集的故障種類覆蓋度不全則會直接影響到主成分的完備性。文獻[11]提出一種基于因子分析的數(shù)據(jù)降維方法，從研究指標(biāo)相關(guān)矩陣內(nèi)部的依賴關(guān)系出發(fā)，把信息重疊、具有錯綜復(fù)雜關(guān)系的變量歸結(jié)為少數(shù)幾個不相關(guān)的綜合因子。但在計算因子得分時，采用的是最小二乘法，該方法對于一些情況會失效。文獻[12]介紹了非負矩陣分解降維方法，將大矩陣分解為2個小矩陣，使這2個小矩陣相乘后能還原到大矩陣，且分解后的矩陣都是非負的。但該方法計算過程存在許多局部最小點，存在陷入局部最優(yōu)的情況。

本文提出一種改進的FastICA算法并將其應(yīng)用于入侵檢測樣本數(shù)據(jù)優(yōu)化階段，不僅可以保證各屬性相互獨立且不會陷入局部最優(yōu)的情況，同時可有效減少信息損失，加快收斂速度。

3 改進的FastICA算法

3.1 FastICA簡介

獨立成分分析最早應(yīng)用于盲源信號分離（BBS），起源于“雞尾酒會問題”，近年來已應(yīng)用于多個領(lǐng)域，如自動化識別[13]、入侵檢測[14]等。目前已形成基于高階統(tǒng)計量算法、基于信息的優(yōu)化算法、快速定點算法，并從定點算法中派生出了目前廣泛使用的FastICA算法。

FastICA的求解過程主要包括數(shù)據(jù)預(yù)處理和獨立成分提取。

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

通常情況下，收集的數(shù)據(jù)具有相關(guān)性，需要對其進行白化處理以去除各觀測變量之間的相關(guān)性，以簡化后續(xù)獨立成分的提取過程。對于觀測向量，對其進行線性變化得到新的向量，使。此過程通常由主成分分析（PCA）完成。

2) 獨立成分提取

確定目標(biāo)函數(shù)后，需要選擇學(xué)習(xí)算法來求解目標(biāo)函數(shù)。FastICA采用基于固定點迭代的定點算法，定點迭代算法收斂速度更快、更可靠。FastICA利用了牛頓迭代法求解式（1）為

(2)

最后可得的迭代公式為

3.2 改進的FastICA算法描述

3.2.1 基于加權(quán)相關(guān)系數(shù)PCA算法的白化處理

獨立成分提取前要對數(shù)據(jù)進行中心化和白化處理，這樣不僅可以去除屬性間的相關(guān)關(guān)系，還可以降低數(shù)據(jù)維度，減小噪聲。傳統(tǒng)的白化處理利用了基于協(xié)方差的PCA算法，協(xié)方差是有量綱的統(tǒng)計量，它受2個相關(guān)變量量綱的影響。而本文收集的性能數(shù)據(jù)各屬性的量綱不同，所以傳統(tǒng)方法并不可行。此外，白化處理過程會降低數(shù)據(jù)維度，帶來一定的信息損失。要保證入侵檢測的正確率，信息損失一定要盡可能少?；谝陨?點，本文采用基于加權(quán)相關(guān)系數(shù)的PCA算法進行白化處理。

首先，相關(guān)系數(shù)是無量綱的統(tǒng)計量，不受屬性量綱的影響。其次，引入權(quán)值，可以將不同屬性置于不同地位。因為不同屬性對于異常檢測的貢獻率是不同的，所以需要區(qū)別對待。根據(jù)變量方差的含義，定義如下權(quán)值

由此，得到加權(quán)相關(guān)系數(shù)

(5)

3.2.2 算法描述

由于在求解目標(biāo)函數(shù)時采用了牛頓迭代法，而牛頓迭代法在單根情況下僅能達到2階收斂，導(dǎo)致迭代次數(shù)多，收斂速度慢。對此，本文提出一種改進的牛頓迭代法，如式（6）所示，實現(xiàn)3階收斂，減少迭代次數(shù)，加快收斂速度。

由文獻[15]中的引理1可以證明式(6)為3階收斂。由此來求解式(1)。

(8)

同理可得

(10)

所以，得到的迭代式如下

得到的整個迭代過程如下。

step2 進行如下計算

改進的FastICA算法流程如圖1所示。

3.3 時間復(fù)雜度分析

改進的白化處理過程引入了基于加權(quán)相關(guān)系數(shù)的PCA，需要計算每個屬性變量的方差

假設(shè)數(shù)據(jù)集有個樣本，個屬性變量，則時間復(fù)雜度增加()。

由于每次迭代的計算量可能增加，改進后的牛頓迭代法是否真正減少計算量不只取決于收斂階。牛頓迭代法的效率指數(shù)，可用來判定改進的方法是否真正減少了計算量，效率指數(shù)越高說明收斂效率越高。效率指數(shù)可做如下定義[16]。

其中，是收斂階數(shù)，是每次迭代的計算量。由式（2）和式（6）可得2種方法的效率指數(shù)如表1所示。

表1 2種方法效率指數(shù)對比

如表1所示，改進后的牛頓迭代法在提高收斂階的同時，提高了迭代序列的效率指數(shù)，可有效地提高收斂速度。

4 算法應(yīng)用與性能分析

4.1 數(shù)據(jù)特征采集

使用第三方監(jiān)測工具sysstat在3臺機器上進行數(shù)據(jù)收集，每5 min記錄一次，共79個特征指標(biāo)[17]，包括CPU使用情況、進程創(chuàng)建、任務(wù)轉(zhuǎn)換活動、內(nèi)存利用率、I/O切換、內(nèi)存和交換空間的使用、網(wǎng)絡(luò)活動等。測試數(shù)據(jù)集共采集64 MB的樣本數(shù)據(jù)，表2列舉了主要的指標(biāo)屬性。

首先，對收集的數(shù)據(jù)進行預(yù)處理。若某個時間點的數(shù)據(jù)未成功記錄，則用相鄰2個時間點的數(shù)據(jù)的平均值進行填充。對收集的數(shù)據(jù)進行觀察，若收集過程中某個屬性的值一直未發(fā)生變化，則說明對后面的異常檢測沒有貢獻，可以直接去除。經(jīng)篩檢，最終保留%user、%system、%iowait、%idle、fault/s、kbmemfree、%memused、kbbuffers、kbswpfree、kbswpused等17個屬性。

4.2 性能測試與分析

4.2.1 白化處理

對收集的數(shù)據(jù)進行中心化和白化處理。白化處理過程分別采用傳統(tǒng)的基于協(xié)方差的PCA，基于互信息的PCA[18]以及本文提出的基于加權(quán)相關(guān)系數(shù)的PCA。得到3種不同方法下變量的特征值分布分別如圖2~圖4所示，其中橫坐標(biāo)表示某個屬性，如4.1節(jié)描述，1表示%user，2表示%system，共計17個屬性，縱坐標(biāo)表示此屬性的特征值。

以上3種方法處理后得到的主成分貢獻率和累積貢獻率如表3所示?？梢姡诩訖?quán)限關(guān)系數(shù)的PCA的主成分1的貢獻率要明顯高于其他2種方法，前2維的貢獻率分別為92.65%，39.88%，96.61%，因此，維數(shù)相同的情況下，基于加權(quán)相關(guān)系數(shù)的PCA貢獻率更大。若以貢獻率95%為限選取主成分，則前2種方法分別需要3維、12維，而基于加權(quán)相關(guān)系數(shù)的PCA僅需要2維。

表2 特征屬性集

表3 3種方法得到的主成分貢獻率及累積貢獻率

綜上所述，利用基于加權(quán)相關(guān)系數(shù)的PCA進行白化處理可以在不提高維度的情況下減少信息損失，對入侵檢測正確率的影響更小。若限定信息保留率，則可以保證更低的維度，減小問題規(guī)模，可以提高入侵檢測的效率。

4.2.2 改進的FastICA方法性能

經(jīng)過白化處理后，得到2維數(shù)據(jù)，則需提取2個獨立成分。分別采用傳統(tǒng)FastICA算法和改進FastICA算法進行獨立成分提取，每組分別進行5次實驗，取平均值，如表4所示。可以看到，傳統(tǒng)FastICA在提取第一維獨立成分時平均迭代次數(shù)高達51次，而改進FastICA平均僅需要迭代3.2次，大大減少了迭代次數(shù)。

表4 2種方法迭代次數(shù)對比

由2.3節(jié)可知，改進FastICA迭代序列的效率指數(shù)較傳統(tǒng)方法有所提高，這說明改進后的方法運行效率更高，2種方法運行時間對比情況如表5所示。改進后的方法平均運行時間減少了0.25 s，從而有效提高了入侵檢測的效率。

表5 2種方法運行時間對比

2種方法得到的獨立成分比較如圖5所示，其中橫坐標(biāo)表示樣本數(shù)量，縱坐標(biāo)表示對應(yīng)獨立成分的值，F(xiàn)astICA(1)及改進FastICA(1)表示第一個獨立成分。由圖可知，2種方法得到的獨立成分差異不大，甚至有重合的區(qū)域。用歐氏距離來衡量它們的差異度，如下

其中，是傳統(tǒng)方法得到的獨立成分，是改進FastICA得到的獨立成分。

2種方法提取獨立成分后所有樣本的差異度如圖6所示，大部分樣本的差異度分布在[0,0.2]區(qū)間，最大的差異度不超過2。因此，2種方法得到的獨立成分差別不大，對后期的異常檢測工作影響甚微。

綜上所述，本文算法在不提高數(shù)據(jù)維度的同時減小了信息損失，不僅有效地減少了迭代次數(shù)，加快了收斂速度，而且得到的獨立成分與原有方法得到的獨立成分基本無差別。

5 結(jié)束語

入侵檢測樣本數(shù)據(jù)規(guī)模的大小，直接影響到檢測算法的性能和檢測率。為了更好地對樣本數(shù)據(jù)進行優(yōu)化，提出了一種改進的FastICA算法，引入基于加權(quán)相關(guān)系數(shù)的PCA用于白化處理過程，并提出一種三階收斂的牛頓迭代法用于獨立成分提取。通過對CPU使用情況、進程創(chuàng)建等計算機主要性能指標(biāo)進行收集和測試，實驗表明，與改進前及其他相關(guān)算法相比，本文算法不僅有效減小了白化處理過程帶來的信息損失，而且減少了迭代次數(shù)，有效提高了收斂速度，為后續(xù)的入侵檢測工作提供了更好的保障，有利于提高入侵檢測的正確率和效率。

[1] 國家互聯(lián)網(wǎng)應(yīng)急中心. 2013年我國互聯(lián)網(wǎng)網(wǎng)絡(luò)安全態(tài)勢綜述[J/OL]. http://www.cert. org.cn.

National Internet Emergency Center. The overview of China’s Internet network security situation in 2013[J/OL]. http://www.cert.org.cn.

[2] ANDERSO J P. Computer Security Threat Monitoring and Surveillance [P]. USA: PA 19034, 1980.4

[3] LI M. An approach to reliably identifying signs of DDOS flood attacks based on LRD traffic pattern recognition[J]. Computers & Security, 2004, 23(7):549-558.

[4] 王慧強,杜曄,龐永剛.入侵檢測技術(shù)研究[J].計算機應(yīng)用研究, 2003, 10(20):90-94. WANG H Q, DU Y, PANG Y G. Research in intrusion detection technology [J]. Application Research of Computers, 2003, 10(20):90-94.

[5] DEREK S, GUAN Q, FU S. An anomaly detection framework for autonomic management of compute cloud systems[C]//Computer Software and Applications Conference Workshops (COMPSACW).Seoul, c2010: 376-381.

[6] GUAN Q, ZHANG Z M, FU S. Ensemble of Bayesian predictors and decision trees for proactive failure management in cloud computing systems[J]. Journal of Communications, 2012, 7(1):52-61.

[7] 夏敏納,龔德良,肖娟.一種面向可靠云計算的自適應(yīng)故障檢測方法[J].計算機應(yīng)用研究, 2013, 31(2):426-430. XIA M N, GONG D L, XIAO J. An adaptive fault detection method for reliable cloud computing[J]. Application Research of Computing,2013,31(2):426-430.

[8] HUSANBIR S, LIU J G, GUAN Q. AFD: adaptive failure detection system for cloud computing infrastructures[C]//Performance Computing and Communications Conference (IPCCC). Austin, TX, c2012: 71-80.

[9] ZHU Q, TERESA T, XIE Q. Automatic fault diagnosis in cloud infrastructure[C]//Cloud Computing Technology and Science(CloudCom). Bristol, c2013: 467-474.

[10] GUAN Q, FU S. Adaptive anomaly identification by exploring metric subspace in cloud computing infrastructures[C]//Reliable Distributed Systems (SRDS). Braga, c2013: 205- 214.

[11] 李娜,趙慧潔,賈國瑞.因子分析模型的高光譜數(shù)據(jù)降維方法[J].中國圖象圖形學(xué)報,2011, 16(11):2030-2035. LI N, ZHAO H J, JIA G R. Hyperspectral data dimensionality reduction method based factor analysis model[J]. Journal Image and Graphics,2011, 16(11):2030-2035.

[12] 李樂,章毓晉.非負矩陣分解算法綜述[J].電子學(xué)報,2008, (4):737-743. LI L, ZHANG Y J. Summary of non-negative matrix factorization algorithm [J].Chinese Journal of Electronics,2008, (4): 737-743.

[13] 藍榮祎,孫懷江.基于逆運動學(xué)和重構(gòu)式ICA 的人體運動風(fēng)格分析與合成[J].自動化學(xué)報,2014,40(6):1135-1147. LAN R W, SUN H J. The style analysis and synthesis of human motion based on inverse kinematics and reconstruction type of ICA [J]. Acta Automatica Sinica,2014,40(6):1135-1147.

[14] 榮宏,王會梅,鮮明.基于快速獨立成分分析的RoQ攻擊檢測方法[J].電子與信息學(xué)報,2013,35(10):2307-2313.

RONG H, WANG H M, XIAN M. A method of RoQ attack detection based on FastICA [J]. Journal of Electronics & Information Technology,2013,35(10):2307-2313.

[15] 吳遜.基于獨立成分分析的特征提取方法研究[D]. 廈門：廈門大學(xué)，2007. WU X. The Research on Features Extraction Method Based on Independent Component Analysis [D]. Xiamen: Xiamen University, 2007.

[16] 張卷美.一種新的迭代收斂階數(shù)的證明與推廣[J].大學(xué)數(shù)學(xué)，2007,23(6):135-139. ZHANG J M. A new proof and promotion of iteration convergence order [J]. College Mathematics,2007,23(6):135-139.

[17] 于明明,張妍.牛頓迭代法與幾種改進格式的效率指數(shù)[J].數(shù)學(xué)的實踐與認(rèn)識,2008,38(18):154-159. YU M M, ZHANG Y. The efficiency index of Newton iterative method and serveral improve formats[J]. Journal of Mathematics in Practice and Theory,2008,38(18):154-159.

[18] 范雪莉,馮海泓,原猛.基于互信息的主成分分析特征選擇算法[J].控制與決策，2013,28(6):915-919. FAN X L, FENG H H, YUAN M. Principal components analysis based on mutual information for feature selection algorithm [J]. Control and Decision, 2013,28(6):915-919.

Improved FastICA algorithm for data optimization processing in intrusion detection

DU Ye, ZHANG Ya-dan, LI Mei-hong, ZHANG Da-wei

(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)

For the purpose of achieving the better data optimization processing results in intrusion detection, an improved FastICA algorithm was proposed. The weighted correlation coefficient was adopted in the phase of albinism processing to reduce information loss, and the Newton’s iterative method was improved for third-order convergence. The algorithm was introduced concretely, meanwhile the time complexity was analyzed in detail. The experiment shows that the method has the advantages of less times of iteration and fast speed of convergence, which can effectively decrease the losses of data and increase the efficiency of data optimization in intrusion detection.

intrusion detection, fast independent component analysis, data optimization, Newton’s iteration method

TP393

A

10.11959/j.issn.1000-436x.2016006

2014-12-23；

2015-03-11

北京高校青年英才計劃基金資助項目（No.YETP0548）；中央高?；究蒲袠I(yè)務(wù)費基金資助項目（No.2014JBM030）；國家自然科學(xué)基金資助項目（No.61102105）

Beijing Higher Education Young Elite Teacher Project (No.YETP0548), The Fundamental Research Funds for the Central Universities (No.2014JBM030), The National Natural Science Foundation of China (No.61102105)

杜曄（1978-），男，黑龍江哈爾濱人，博士，北京交通大學(xué)副教授，主要研究方向為網(wǎng)絡(luò)安全、形式化驗證與可靠性分析。

張亞丹（1989-），女，河北石家莊人，北京交通大學(xué)碩士生，主要研究方向為入侵檢測與響應(yīng)、安全態(tài)勢感知。

黎妹紅（1975-），男，湖北黃梅人，博士，北京交通大學(xué)講師，主要研究方向為智能卡與生物識別技術(shù)、信息保密技術(shù)。

張大偉（1974-），男，遼寧沈陽人，博士，北京交通大學(xué)講師，主要研究方向為可信計算、智能卡安全技術(shù)。