基于數(shù)據(jù)流聚類挖掘算法的入侵檢測系統(tǒng)研究

梅瑩瑩，梁月放

(安徽三聯(lián)學(xué)院 計算機工程學(xué)院，安徽 合肥230601)

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)流量急劇膨脹，攻擊手段和技術(shù)呈多樣化、智能化，網(wǎng)絡(luò)安全防御中的入侵檢測系統(tǒng)面臨了新的挑戰(zhàn)[1]。近年來，基于數(shù)據(jù)流挖掘的入侵檢測系統(tǒng)成為研究的熱點。但數(shù)據(jù)流是連續(xù)快速、出現(xiàn)時間短且不可逆的[2]，所以解決挖掘算法中對數(shù)據(jù)流的實時處理問題顯得尤為重要。

將數(shù)據(jù)挖掘技術(shù)應(yīng)用于入侵檢測是近幾年來網(wǎng)絡(luò)安全領(lǐng)域研究和發(fā)展的課題，國內(nèi)外學(xué)者做了許多研究[3-4]。例如：美國的哥倫比亞大學(xué)的DMFCFM IDS項目[5]基于數(shù)據(jù)挖掘技術(shù)構(gòu)造了一個入侵檢測系統(tǒng)(IDS)，較以往IDS更加自動化和系統(tǒng)化。DMFCFM IDS提出了用頻繁情節(jié)規(guī)則和關(guān)聯(lián)規(guī)則來構(gòu)造更具預(yù)測性的、額外的特征。在國內(nèi)，中科院利用數(shù)據(jù)挖掘算法，通過層次化協(xié)作模型分析和處理安全審計數(shù)據(jù)，可在系統(tǒng)中實現(xiàn)入侵檢測規(guī)則自動生成，并建立異常檢測模型。清華大學(xué)使用多種數(shù)據(jù)挖掘算法建立檢測模型，其中采用Agent/Manager/UI三層實體結(jié)構(gòu)，提出了一種基于數(shù)據(jù)挖掘算法的協(xié)同入侵檢測系統(tǒng)[6]。

基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)已經(jīng)取得了一些研究成果[7]，但也存在著許多問題。采用傳統(tǒng)的基于靜態(tài)數(shù)據(jù)庫的數(shù)據(jù)挖掘算法在高速網(wǎng)絡(luò)環(huán)境下進行有效挖掘是行不通的。本文針對實現(xiàn)高速網(wǎng)絡(luò)數(shù)據(jù)流實時檢測處理的需求，將數(shù)據(jù)流挖掘技術(shù)和入侵檢測技術(shù)相融合，研究新的入侵檢測系統(tǒng)，以解決傳統(tǒng)入侵檢測系統(tǒng)對海量、高速數(shù)據(jù)處理實時性差的問題。

1 基于數(shù)據(jù)流挖掘的入侵檢測模型

將數(shù)據(jù)挖掘技術(shù)應(yīng)用于入侵檢測能夠廣泛、有效地審計數(shù)據(jù)，得到攻擊行為的模型或特征，進而精確地分辨和捕獲實際的入侵和正常行為模式[8]。這種方法的優(yōu)點在于相同的數(shù)據(jù)挖掘工具可應(yīng)用于多個數(shù)據(jù)流，從而有利于構(gòu)建適應(yīng)性強的入侵檢測系統(tǒng)[9-10]。

1.1 基于數(shù)據(jù)流挖掘的入侵檢測模型(DSMIDS)設(shè)計

當(dāng)網(wǎng)絡(luò)外來信息流入后，采集設(shè)備負責(zé)采集，并通過數(shù)據(jù)挖掘算法程序?qū)Σ杉臄?shù)據(jù)進行挖掘，按一定的規(guī)則聚類(或分類)流入的信息特征，該特征與現(xiàn)有系統(tǒng)的入侵特征進行匹配。根據(jù)匹配成功與否，判斷流入系統(tǒng)的信息是否含有入侵信息。當(dāng)然，系統(tǒng)需經(jīng)常對匹配規(guī)則進行更新處理。圖1描述了基于數(shù)據(jù)流挖掘的入侵檢測模型(Data Stream Mining-based Intrusion Detection System，DSMIDS)。

圖1 基于數(shù)據(jù)流挖掘的入侵檢測模型

根據(jù)上述分析，基于數(shù)據(jù)流的入侵檢測系統(tǒng)模型由數(shù)據(jù)流采集模塊、數(shù)據(jù)整理模塊、數(shù)據(jù)挖掘模塊和入侵檢測模塊等組成。其模型設(shè)計如圖2所示：

圖2 入侵檢測系統(tǒng)的模型設(shè)計

數(shù)據(jù)流采集模塊的作用是捕獲無損報文以及檢查簡單的報文，如IP報文版本檢查、校驗以及協(xié)議檢查等。數(shù)據(jù)流整理模塊包括整理訓(xùn)練數(shù)據(jù)、剔除孤立點等。對于在采集時段中采集到的正常數(shù)據(jù)，將其當(dāng)作訓(xùn)練數(shù)據(jù)集來處理，以實現(xiàn)正常信息輪廓的挖掘。孤立點就是在數(shù)據(jù)集中與眾不同的數(shù)據(jù)[11]。為解決數(shù)據(jù)流挖掘中訓(xùn)練數(shù)據(jù)的可靠和匹配模型輪廓的正確，在構(gòu)造正常數(shù)據(jù)模型時必須將孤立點剔除。入侵檢測模塊是為了將待訓(xùn)練的數(shù)據(jù)進行聚類，通過對比并匹配運算實際的信息特征輪廓和獲得的信息特征輪廓，從而判斷網(wǎng)絡(luò)信息是否存在入侵行為，以便進行及時防范。實際信息的特征輪廓通過對信息流的聚類產(chǎn)生。

1.2 孤立點剔除算法

在數(shù)據(jù)流的采集和傳輸中，由于干擾等因素，會出現(xiàn)一些偏離正常模型的孤立點。這些點會影響到正常輪廓模型的生成或?qū)е抡ＤＰ筒痪_。因此，在產(chǎn)生訓(xùn)練數(shù)據(jù)樣本時，必須要對孤立點進行剔除。

這里采用分治策略，將空間域用一條x=c的垂直線遞歸的劃分為左右兩個子域，并分別求出兩個子域的最近對d1和d2，然后求出d=min(d1,d2)，這個d不一定是空間域的最近對，因為還要考慮左右之間點的距離問題。那么有沒有左右之間兩點的距離小于d？可以證明，如果存在這樣的點，該點一定在以x=c為軸，左右距離為d的空間內(nèi)，同時可以證明，這樣的點最多只有6個[12]。也就是說，經(jīng)過這樣的優(yōu)化，求最近對的問題可以歸結(jié)為：用遞歸的方法將整個空間域分為左右兩個子域，分別求出兩個子域的最近對，再從兩個最近對中找出較小的一對，然后選出以x=c為軸，以[y-d,y+d]為空間的候選點，計算它們之間的距離，經(jīng)比較得到全部空間域的最近對。

最近對求出后，可以用上述思想分離出孤立點。這樣分離孤立點的過程如圖3所示。

圖3 優(yōu)化最近對求法 圖4 ASWDStream算法流程

可以推算，該方法的時間復(fù)雜度為：T(N)∈Θ(nlogn)，和基于最近對技術(shù)的孤立點發(fā)現(xiàn)算法[13]相比，大大提高了算法的時間效率，滿足了數(shù)據(jù)流挖掘?qū)r間復(fù)雜度的要求。

2 ASWDStream算法

ASWDStream(Attenuation Sliding Window Density-based Data Stream Clustering Mining)算法的理論要點為：處理已知的臨界候選 微簇，判斷其能否作為離群 微簇或者候選 微簇。在處理數(shù)據(jù)流時，該算法依次讀入滑動 窗口中的所有 子窗口的數(shù)據(jù)。通過聚類操作將這些數(shù)據(jù)并入多個候選 微簇和臨界候選微簇，接著把臨界候選 微簇保存到另一個臨界候選 微簇集中，將候選 微簇保存到一個候選 微簇集中，等處理完所有子窗口后，再處理保存的臨界候選微簇和候選微簇。

2.1 ASWDStream算法實現(xiàn)

ASWDStream算法包括在線的微簇維護以及離線的最終聚類生成兩個步驟。和CluStream算法[14]的離線聚類生成過程大致相同，ASWDStream算法也是用相同的金字塔時間框架來存儲聚類結(jié)果(見圖4)。

2.2 數(shù)據(jù)流聚類挖掘算法

為盡快查找進化數(shù)據(jù)流中的簇，應(yīng)該對臨界候選 微簇和候選 微簇進行維護。所有的臨界候選微簇被維護在一個獨立的內(nèi)存空間內(nèi)，稱為臨界候選緩存[15]。所有的候選 微簇被維護于另外一個專門的內(nèi)存內(nèi)，稱之為候選緩存區(qū)。大部分的新數(shù)據(jù)點都可以匹配現(xiàn)有的簇，因此現(xiàn)有的臨界候選微簇和候選微簇可以吸收新數(shù)據(jù)點。當(dāng)一個新數(shù)據(jù)點p到達時，合并過程如表1所示：

表1 數(shù)據(jù)流聚類挖掘算法流程

對現(xiàn)有的每個候選微簇Cp來說，如果不吸收新的數(shù)據(jù)點，則將會不斷地衰減Cp所占的權(quán)重。一旦Cp的權(quán)值小于βu，則表明這個候選微簇Cp己經(jīng)完成向一個離群點噪聲的退化。此時該離群點噪聲將會被刪除以釋放內(nèi)存空間。因此需要對各個候選微簇的權(quán)值進行持續(xù)性檢查。首先需要確定檢查的周期，以避免太頻繁的權(quán)值檢查工作。將一個候選微簇退化成離群點需要的最小時間跨度[16]如公式(1)所示：

(1)

由式(1)可見，只需要做定期的檢查，周期為Tp。因為所有數(shù)據(jù)流的權(quán)重為w，通過采用此檢查方法后，能夠?qū)崿F(xiàn)在內(nèi)存中的最大候選微簇數(shù)量為w/βu。

若某一滑動窗口的所有子窗口均采用ASWDStream算法來實現(xiàn)對候選微簇和臨界候選微簇的挖掘，并存儲到T1(候選微簇集)和T2(臨界候選微簇集)，則算法就會合并T1和T2內(nèi)的微簇。由于新的微簇的產(chǎn)生，此時需要合并候選微簇集中的所有微簇。如果沒有候選微簇從已合并的臨界候選微簇產(chǎn)生，則其繼續(xù)保留在臨界候選微簇集中，再次對臨界候選微簇進行合并。最后，ASWDStream算法在該滑動窗口中，由聚類運算生成兩個微簇集：候選微簇集T1和臨界候選微簇集T2。

3 仿真實驗與結(jié)果分析

實驗在統(tǒng)一平臺下進行，其中：CPU為2.16 GHz的 Pentium(R)Dual T3400，內(nèi)存為2GB，操作系統(tǒng)為Windows Xp。算法采用Microsoft Visual C++編程實現(xiàn)，并通過Matlab7.0對結(jié)果進行分析和比較。

3.1 驗證數(shù)據(jù)集

實驗采用KDD CUP競賽中的數(shù)據(jù)。該數(shù)據(jù)集采自于主機上的一個模擬網(wǎng)絡(luò)，產(chǎn)生于美國國防部DARPA部門的一項入侵檢測評估系統(tǒng)，它包括了63天的TCP Dump現(xiàn)實數(shù)據(jù)，累計有500萬余次的會話內(nèi)容，攻擊方式大約有幾十種。KDD CUP數(shù)據(jù)是受認可度較高的一套數(shù)據(jù)，經(jīng)常被用于入侵檢測系統(tǒng)性能的評估，在挖掘試驗中具有廣泛應(yīng)用。數(shù)據(jù)集在正常網(wǎng)絡(luò)數(shù)據(jù)的基礎(chǔ)上，又將多種類型的入侵數(shù)據(jù)加入進去。這些入侵行為主要有以下四大類[17]：DOS、R2L、U2L和Probing。

3.2 數(shù)據(jù)集處理

本次試驗所使用的數(shù)據(jù)集實際上是靜態(tài)數(shù)據(jù)。若使用傳統(tǒng)的基于靜態(tài)數(shù)據(jù)集的數(shù)據(jù)挖掘方法對其進行挖掘和分析，可以得到令人滿意的結(jié)果。但由于我們重點關(guān)注的是數(shù)據(jù)流中的數(shù)據(jù)挖掘算法，為保證算法的有效性，首先需要對靜態(tài)數(shù)據(jù)集作動態(tài)化的處理。在試驗之前對原始數(shù)據(jù)進行了如下的處理規(guī)定：

單遍掃描是對每條TCP連接記錄的讀入、分析處理和丟棄實施一次性處理，這樣在效果上便實現(xiàn)了對數(shù)據(jù)流單遍處理的目的。實時處理是指加入一個3秒時鐘周期，每隔一個時鐘周期便將分析結(jié)果記錄歸檔，并將其與上次結(jié)果進行比較，描出二維狀態(tài)轉(zhuǎn)移圖像，這樣便可以對網(wǎng)絡(luò)數(shù)據(jù)流進行實時監(jiān)控。

3.3 聚類結(jié)果比較

算法中的參數(shù)進行如下設(shè)置：初始數(shù)據(jù)點個數(shù)N=200 k，衰減因子λ=0.25，數(shù)據(jù)流流速v=1000，u=10，ε1=ε2=16，離群點閥值β=0.2。ASWDStream算法和CluStream算法采用同樣的參數(shù)，從兩個方面對兩種算法進行聚類精度對比實驗。

圖5 運行時間比較 圖6 運行時間比較

3.3.1 算法時間效率比較 圖5描述的是兩個算法的運行時間隨自然簇個數(shù)增加而變化的情況。數(shù)據(jù)集中所使用的數(shù)據(jù)維數(shù)為20，生成的數(shù)據(jù)的個數(shù)為200 k。結(jié)果表明，在固定數(shù)據(jù)流的維數(shù)和個數(shù)的情況下，從5到25遞增自然簇的個數(shù)，兩個算法的執(zhí)行時間隨著簇個數(shù)的增多呈線性增長，ASWDStream算法的運行時間始終要快于CluStream算法。原因在于ASWDStream算法采用微簇取代單個記錄作為增量更新的粒度，從而降低了算法的處理步驟。

圖6同樣為算法運行時間的比較，在產(chǎn)生另一組數(shù)據(jù)時，由5至25數(shù)據(jù)點的維度不斷變化，此時數(shù)據(jù)點的個數(shù)和自然簇個數(shù)保持不變。由此可見，當(dāng)維度從5至25數(shù)據(jù)點變化，ASWDStream算法和CluStream算法運行的時間都呈線性增長，ASWDStream算法的運行時間始終要快于CluStream算法。

圖7 聚類質(zhì)量比較

3.3.2 聚類質(zhì)量比較 圖7顯示的是兩個算法的聚類質(zhì)量比較圖。該圖呈現(xiàn)的是在不同的時間單元下，算法計算得到的SSQ值(SSQ是一種比較聚類質(zhì)量的方法，其值越小，算法的聚類質(zhì)量越好)。由上圖表明，通過CluStream算法獲得的SSQ均值要小于通過ASWDSteam算法獲得的SSQ均值，也就是說ASWDSteam算法的聚類質(zhì)量要好于CluStream算法。

3.4 應(yīng)用驗證

由于KDDCUP數(shù)據(jù)集數(shù)據(jù)過多，且內(nèi)容屬性有較多類似的地方。因此只從中選取1萬條記錄用于本試驗，該數(shù)據(jù)由以下兩部分組成：(1)3000條測試樣本中包含9種入侵類型，分別為：

ftp_write，ipsweep，neptune，pod，spy，buff_overflow，perl，eject，nmap。(2)7000條訓(xùn)練樣本中包含7種入侵類型，分別為：ftp_write，ipsweep，neptune，pod，spy，buff_overflow，perl。

試驗數(shù)據(jù)的組成如表2和表3所示。

表2 試驗數(shù)據(jù)類型分布

表3 試驗數(shù)據(jù)入侵部分的組成

三個參數(shù)(準(zhǔn)確率、誤報率、漏報率)來衡量入侵檢測系統(tǒng)的檢測性能。表4和表5為算法分別對訓(xùn)練數(shù)據(jù)集和樣本數(shù)據(jù)集入侵檢測的實驗結(jié)果：

表4 試驗結(jié)果分析1

表5 試驗結(jié)果分析2

從表4和表5分析可知，基于ASWDStream算法的入侵檢測系統(tǒng)在應(yīng)用驗證中表現(xiàn)出了較好的檢測性能。應(yīng)對海量、高速數(shù)據(jù)流，該算法具有較高的檢測率、較低的誤報率和漏報率，且保證了處理的實時性，對特定類型，尤其是R2L和Probing兩種入侵行為，具有較高的檢測能力。另外，對于新的入侵類型，ASWDStream算法也有較好的識別能力。

4 結(jié)語

基于對傳統(tǒng)的入侵檢測系統(tǒng)進行的模型分析，嘗試將數(shù)據(jù)流聚類挖掘融合到入侵檢測中，提出了DSMIDS模型。通過一種基于分治思想的發(fā)現(xiàn)孤立點的優(yōu)化方法，研究并設(shè)計了快速剔除孤立點的算法，解決了孤立點對提取訓(xùn)練模型的影響。提出了基于時間衰減滑動窗口的數(shù)據(jù)流聚類挖掘的改進算法ASWDStream，本算法有效彌補了傳統(tǒng)數(shù)據(jù)流聚類算法的不足。仿真實驗表明，ASWDStream具有較好的聚類效果，在入侵檢測系統(tǒng)中具有較高的實時性和檢測率。在以后的研究中，可以嘗試將人工智能的最新研究領(lǐng)域成果與入侵檢測系統(tǒng)相結(jié)合，開發(fā)出對網(wǎng)絡(luò)變化適應(yīng)性更強的、檢測效率更高的網(wǎng)絡(luò)安全檢測系統(tǒng)。