梅瑩瑩，梁月放

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

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

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

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

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

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

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

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

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

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

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

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

1.2 孤立點(diǎn)剔除算法

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

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

最近對(duì)求出后，可以用上述思想分離出孤立點(diǎn)。這樣分離孤立點(diǎn)的過(guò)程如圖3所示。

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

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

2 ASWDStream算法

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

2.1 ASWDStream算法實(shí)現(xiàn)

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

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

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

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

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

(1)

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1 驗(yàn)證數(shù)據(jù)集

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

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

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

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

3.3 聚類結(jié)果比較

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

圖5 運(yùn)行時(shí)間比較 圖6 運(yùn)行時(shí)間比較

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

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

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

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

3.4 應(yīng)用驗(yàn)證

由于KDDCUP數(shù)據(jù)集數(shù)據(jù)過(guò)多，且內(nèi)容屬性有較多類似的地方。因此只從中選取1萬(wàn)條記錄用于本試驗(yàn)，該數(shù)據(jù)由以下兩部分組成：(1)3000條測(cè)試樣本中包含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。

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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