Apriori-KNN算法的警報過濾機制的入侵檢測系統(tǒng)

翟繼強,馬文亭,肖亞軍

(哈爾濱理工大學 計算機科學與技術(shù)學院,哈爾濱 150080)

1 引 言

基于特征的網(wǎng)絡入侵檢測系統(tǒng)(NIDS)在檢測過程中可能會產(chǎn)生大量誤報,增加了分析NIDS警報的難度,降低了NIDS系統(tǒng)的檢測性能[1-3].誤報源于NIDS檢測方法的固有局限性.基于特征的檢測很大程度上取決于一組檢測入侵的規(guī)則,規(guī)則越嚴格,安全級別越高[4].這種情況下,誤報的數(shù)量將會增加.放寬規(guī)則可以減少誤報的數(shù)量,但安全級別將同時下降.因此,我們必須權(quán)衡考慮低誤報率與檢測精度之間的關(guān)系.

本文提出了利用Apriori-KNN算法的警報過濾器來降低基于特征的NIDS的警報誤報率的過濾方法.主要研究在不犧牲安全性情況下基于特征的NIDS如何實現(xiàn)降低誤報率.基于特征的NIDS(如Snort)產(chǎn)生的警報,直接輸出作為警報過濾器的輸入,利用數(shù)據(jù)挖掘技術(shù)對已經(jīng)輸出的警報進行二次處理[5].利用無攻擊情況下的“正?！本瘓髮谔卣鞯腘IDS的正常警報模式進行建模,利用基于Apriori-KNN算法對警報進行過濾,誤報則直接忽略將真正的警報輸出進行處理.

2 相關(guān)工作

2.1 KNN算法

KNN算法是數(shù)據(jù)挖掘技術(shù)中的一種分類算法,其中心思想類似于“物以類聚,人以群分”[6,7].KNN依據(jù)距離度量從訓練集中找出其最近的k個數(shù)據(jù)點,將k個數(shù)據(jù)點中的主導標簽分配給新數(shù)據(jù).若k=1,則新數(shù)據(jù)點由其最近的數(shù)據(jù)點確定.由于該算法實現(xiàn)簡單和分類有效性,KNN通常被用作標準分類器[8].

2.2 Apriori算法

Apriori算法是一種可以有效地解決頻繁項集任務,挖掘關(guān)聯(lián)規(guī)則的算法[9].該算法主要利用關(guān)聯(lián)規(guī)則的方法進行分類,計算頻繁項集與規(guī)則.關(guān)聯(lián)規(guī)則可以用X→Y表示(X,Y表示相互獨立的項集,即X∩Y≠Φ),支持度(sup)和置信度(conf)用于度量其規(guī)則的關(guān)聯(lián)強度.

2.3 Apriori-KNN算法

Apriori-KNN算法將關(guān)聯(lián)規(guī)則轉(zhuǎn)化為可量化的,然后與KNN算法結(jié)合.將是否含有頻繁項集Xi(Xi=0或者Xi=1)作為一個屬性,作為KNN算法的距離計算公式的變量.bool(Xi)表示是否存在頻繁項集Xi,其對每一類的均值為conf(Xi→Yi).結(jié)合KNN的距離公式得到新的歐幾里得的距離測試樣例與訓練樣例(x,yi)的距離d如公式(1)所示:

(1)

設參數(shù)α為向量x詞頻的均值.X(1)表示為1-項集,X(2)表示2-項集,依此類推.在分類方面,項數(shù)多的項集會明顯高于項數(shù)少的項集,因此設定ki=i的參數(shù)對項集 X(k)進行修正.修改距離公式如公式(2)所示:

(2)

在上述闡述的基礎上,該Apriori-KNN算法的具體步驟如下:

1)首先對數(shù)據(jù)集進行預處理.

2)通過步驟1),得到bool模型和vsm模型.

依據(jù)信息增益方法對數(shù)據(jù)進行降維,根據(jù)其公式(3)選取前j個特征作為新的bool模型.

(3)

3)根據(jù)步驟2)的bool模型進行關(guān)聯(lián)規(guī)則挖掘,利用Apriori算法產(chǎn)生頻繁項集與規(guī)則,計算頻繁項集的置信度和其對任意分類的置信度.

4)根據(jù) tf-idf公式計算 vsm 模型關(guān)鍵字權(quán)值:

(4)

排序取前K個特征.

5)根據(jù)上述更改的KNN距離公式(2)計算測試樣例與訓練數(shù)據(jù)集的相似度.

6)通過KNN的分類規(guī)則進行分類,為了提高其分類的準確度,該算法使用距離加權(quán)表決公式:

(5)

公式(5)中wi=1/i.

KNN算法中取 k 個特征詞構(gòu)成特征詞庫,而Apriori 算法取 j 個詞構(gòu)成特征項集.根據(jù)以上的準備工作,Apriori-KNN算法的分類過程圖如圖1所示.

Apriori-KNN算法是利用Apriori算法對傳統(tǒng)的KNN算法進行優(yōu)化,解決由文章長短影響的語義關(guān)聯(lián)和詞頻等問題,從而提高KNN算法分類的準確率.相比于KNN算法,Apriori-KNN算法在分類的準確率和召回率方面均有明顯的提高.

3 基于Apriori-KNN算法的警報過濾機制

基于Apriori-KNN算法的入侵檢測系統(tǒng)警報過濾機制結(jié)構(gòu),除了通用 NIDS 結(jié)構(gòu)的部分外,還包括警報過濾模塊.如圖2所示.

圖1 Apriori-KNN算法的分類過程圖Fig.1 Classification process of Apriori-KNN algorithm

許多NIDS都是基于規(guī)則的,不僅編碼實現(xiàn)困難,而且也無法檢測到新的入侵行為[11-14].針對NIDS的弊端提出了依賴于數(shù)據(jù)挖掘的分類方法,利用基于Apriori-KNN算法的警報過濾機制降低誤報率.當網(wǎng)絡環(huán)境受到攻擊時,基于特征的NIDS會產(chǎn)生不同于正常安全情況下的警報.而且在某些攻擊情況下,可能發(fā)出正常情況下不存在的警報類型.該方法用于判斷輸入的警報序列是否偏離正常情況.如果出現(xiàn)偏離正常情況的現(xiàn)象,判斷為可能存在攻擊行為,需要做進一步調(diào)查.如果產(chǎn)生的警報與無攻擊的情況非常相似,判斷被攻擊的風險很低.

圖2 基于Apriori-KNN的算法入侵檢測系統(tǒng)結(jié)構(gòu)Fig.2 Based on Apriori-KNN algorithm intrusion detection system structure

下面將介紹如何模擬正常警報模式以及檢測偏離狀態(tài)與正常模式的偏差.在無攻擊的情況下,N是由NIDS產(chǎn)生的不同的警報類型,采用N維空間建立正常的警報模式.空間中的數(shù)據(jù)點P的屬性(A1,A2,A3,…,An)表示在時間段為T時不同類型的警報數(shù)量.將沒有經(jīng)歷任何攻擊產(chǎn)生的警報定義為“正常”點,這些警報被認為是“安全的”并被視為誤報.如圖3(a)表示數(shù)據(jù)集點表示無入侵行為情況下正常的點.用上述方法為新警報創(chuàng)建新數(shù)據(jù)點并判斷新警報是否為誤報.新點(白點)與正常點(黑點)的距離相當于該警報與正常模式的偏離.即新點接近正常點,則被認為是正常的,且認為在這段時間內(nèi)產(chǎn)生的警報是誤報.圖3(a)表示是一個正常點的模型示例.如果滿足以下任何一種情況,認為新點是異常的:遠離正常點(圖3(b))或者由正常點不存在的新警報類型組成,此時產(chǎn)生的警報是真正警報.

圖3 誤報模型中的正常點與異常點示例-標號的數(shù)據(jù)點(黑點)是離新數(shù)據(jù)點(白點)最近的5個點Fig.3 Example of normal and abnormal points in the false alarm model-Numbered points are the 5 nearest normal(black)points from the new(white)point

根據(jù)以上對于新警報的判斷原理,采用Apriori-KNN算法作為分類算法判斷新的數(shù)據(jù)點是否正常.根據(jù)Apriori-KNN算法中的距離d判斷點與點之間的相似性,距離d越小表示相似性越大.被分類的數(shù)據(jù)點的最終相似性得分是其距離最接近的k個正常點的距離的平均值.相似性數(shù)值高于閾值T,則該點被認為是異常的.反之說明屬于誤報,應該被過濾掉.

圖4 基于Apriori-KNN算法的警報過濾機制的詳細結(jié)構(gòu)Fig.4 Detailed structure of alarm filtering mechanism based on Apriori-KNN algorithm

圖4介紹基于Apriori-KNN算法的警報過濾層的內(nèi)部構(gòu)造.基于Apriori-KNN算法的警報過濾機制主要由數(shù)據(jù)標準化,警報存儲和警報過濾三部分組成.數(shù)據(jù)標準化包含兩個部分:特征選擇和格式轉(zhuǎn)換.特征選擇是對輸入警報進行預處理,格式轉(zhuǎn)換是根據(jù)預處理特征集將基于特征的NIDS警報轉(zhuǎn)換為標準警報(數(shù)據(jù)標準化的輸出警報).具體的特征選擇取決于NIDS的具體類型.以Snort為例,從Snort警報中提取8個特征,如描述,分類、優(yōu)先級、報文類型、源IP地址、源端口號、目的IP地址和目的端口號,然而對于測試Apriori-KNN算法以上特征均不適合直接使用,需將這些特征進行標準化.所有警報將使用其在數(shù)據(jù)集中發(fā)生的概率來表示.在警報存儲的組件中,所有傳入的標準警報將被存儲到數(shù)據(jù)庫中,警報過濾組件將執(zhí)行過濾誤報.為了更好的測試降低誤報率的算法,可通過對一些現(xiàn)有數(shù)據(jù)集(例如DARPA數(shù)據(jù)集)來標記標準警報,并對基于Apriori-KNN的警報過濾機制進行周期性測試.

該方法提出過濾警報的模型均獨立于網(wǎng)絡入侵檢測系統(tǒng)(如圖5),無需對現(xiàn)有檢測配置進行更改.警報數(shù)據(jù)集是利用“正?！本瘓髞順?gòu)建誤報模型.警報過濾過程是對從基于特征的NIDS連續(xù)不斷輸出的警報進行過濾,只需將過濾過程中被留下的警報進行二次檢測.整個減少誤報率的過程可看作是基于特征的NIDS的插件.簡而言之,NIDS輸出的警報流通過過濾器,將真正的警報輸出并進行處理,誤報則忽略.

圖5 NIDS與降低誤報率過程之間的關(guān)系Fig.5 Relationship between IDS and the proposed false alarm reduction processes

4 測試與分析

算法測試通過對基于特征的NIDS(即Snort)在不同情況下的性能進行比較,通過兩個不同數(shù)據(jù)集(DARPA數(shù)據(jù)集和真實數(shù)據(jù)集)在Snort進行兩次獨立實驗,并獲取和分析實驗結(jié)果.

4.1 使用DARPA數(shù)據(jù)集進行測試

DARPA是唯一經(jīng)過深入研究,具有文獻記錄和公開可用的用于測試入侵檢測系統(tǒng)的標記的數(shù)據(jù).在實驗中,使用1999年DARPA數(shù)據(jù)集來測試基于Apriori-KNN算法的警報過濾機制的性能.在DARPA 1999數(shù)據(jù)集中,誤報可以通過從第1周和第3周重播到Snort來獲得,在這兩個星期內(nèi)數(shù)據(jù)包不受任何攻擊,因此,該時間段內(nèi)的任何警報都可以被認為是誤報.利用數(shù)據(jù)包生成器(Colasoft Packet Builder)向Snort發(fā)送惡意數(shù)據(jù)包來模擬一些攻擊,從而獲得了真實警報.DARPA數(shù)據(jù)集測試產(chǎn)生的警報數(shù)如表1所示.

表1 Snort生成的警報數(shù)
Table 1 Number of alarms generated by Snort

產(chǎn)生警報第2周第4周第5周 誤報1448241057767 真正警報971723982172 警報總數(shù)2419965039939

為了測試Apriori-KNN算法的性能,利用DARPA數(shù)據(jù)集分別對本文算法的過濾機制和KNN分類器在Snort進行測試.DARPA數(shù)據(jù)集在Apriori-KNN算法和KNN算法產(chǎn)生的誤報數(shù)量如表2所示.

在第2周、第4周和第5周DARPA數(shù)據(jù)集在Apriori-KNN、KNN與Snort的識別率見表3,Apriori-KNN警報過濾機制能夠在KNN分類器的基礎上再次提高Snort的識別率,降低了誤報率.

如表1所示,由Snort在DARPA數(shù)據(jù)集上生成的標記警報(真實警報和誤報),第2周誤報數(shù)量為14482.表2、表3分別呈現(xiàn)了使用基于Apriori-KNN算法的警報過濾機制后的剩余警報(誤報)數(shù)量與識別率,識別率用來衡量識別誤報和真實警報的準確性.實驗結(jié)果表明,基于Apriori-KNN算法的警報過濾機制具有較高的識別精度,減少誤報數(shù)量.

表2 DARPA數(shù)據(jù)集在Apriori-KNN、KNN、Snort誤報數(shù)量
Table 2 Number of false alarm for DARPA datasets in Apriori-KNN,KNN,Snort

時間誤報數(shù)量Apriori-KNNKNNSnort第2周2047241214482第4周7929264105第5周115713287767

表3 DARPA數(shù)據(jù)集在Apriori-KNN算法的警報過濾器Snort降低誤報
Table 3 Snort alarms reduced by based on the Apriori-KNN false alarm filter on the DARPA data set

時間識別率(%)Apriori-KNNKNNSnort第2周91.5490.0340.15第4周87.8285.7536.88第5周88.3586.6321.85

4.2 使用真實數(shù)據(jù)集進行測試

為了進一步測試基于Apriori-KNN算法的警報過濾器Snort的性能,使用真正的網(wǎng)絡流量跟蹤產(chǎn)生的數(shù)據(jù)集對該機制進行第二次實驗.真實數(shù)據(jù)集是由部署在CSLab中具有公共IP域(這個IP地址不同于教育領(lǐng)域)的蜜罐提供.它由兩臺服務器組成:Honeywall和一臺用于模擬服務列表的虛擬機(如HTTP,FTP).外部用戶可以通過網(wǎng)絡連接訪問蜜罐,攻擊者還可以對其發(fā)起惡意攻擊或進行隨機掃描.這種情況下,蜜罐可以看作是通過記錄正常數(shù)據(jù)包和惡意數(shù)據(jù)包的所有傳入流量來收集真實網(wǎng)絡數(shù)據(jù).將真實數(shù)據(jù)集分三部分,分別表示為DAY1,DAY2和DAY3.

表4給出了使用基于Apriori-KNN算法的警報過濾器進行降低誤報率實驗結(jié)果,其中警報過濾機制可以實現(xiàn)警報大約85%的識別率(識別精度在很大程度上取決于算法的訓練.例如,通過測試更多的數(shù)據(jù)集,Apriori-KNN算法甚至可以達到90%以上的識別精度).

表4 基于Apriori-KNN算法的警報過濾器測試真實數(shù)據(jù)的性能
Table 4 Performance of the Apriori-KNN-based false alarm filter on the real data set

警報DAY1DAY2DAY3減少警報前568988297341減少警報后85410772172識別率(%)84.9987.8085.96

實驗結(jié)果顯示使用DARPA數(shù)據(jù)集測試時,識別率可以高達91.54%,相對于snort誤報率而言明顯減少.在使用收集的真實數(shù)據(jù)集進行測試時,識別率可以達到87.80%.使用基于Apriori-KNN算法的警報過濾器前后的警報差最多有7752個,明顯減少了誤報的數(shù)量,降低了誤報率.

5 結(jié) 語

本文針對于基于特征的NIDS存在的高誤報率問題,提出了一種利用Apriori-KNN算法的警報過濾機制的入侵檢測系統(tǒng).用N維空間對正常的警報模式進行建模,其中每個維度對應于一種警報類型.模型中的數(shù)據(jù)點表示某個時間段的警報分布,而其每個屬性值是該時間段內(nèi)特定類型的警報數(shù).在研究中,根據(jù)Apriori-KNN算法中改進的歐氏距離d將新數(shù)據(jù)點分類為正常或異常.通過對DARPA數(shù)據(jù)集和收集真實數(shù)據(jù)集的測試與分析,證明本方法可以在不犧牲NIDS的安全性能前提下,有效地減少NIDS誤報率,提高系統(tǒng)性能.