Apriori-KNN算法的警報過濾機制的入侵檢測系統

翟繼強,馬文亭,肖亞軍

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

1 引 言

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

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

2 相關工作

2.1 KNN算法

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

2.2 Apriori算法

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

2.3 Apriori-KNN算法

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

(1)

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

(2)

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

1)首先對數據集進行預處理.

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

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

(3)

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

4)根據 tf-idf公式計算 vsm 模型關鍵字權值:

(4)

排序取前K個特征.

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

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

(5)

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

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

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

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

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

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

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

圖2 基于Apriori-KNN的算法入侵檢測系統結構Fig.2 Based on Apriori-KNN algorithm intrusion detection system structure

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

圖3 誤報模型中的正常點與異常點示例-標號的數據點(黑點)是離新數據點(白點)最近的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

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

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

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

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

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

4 測試與分析

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

4.1 使用DARPA數據集進行測試

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

表1 Snort生成的警報數
Table 1 Number of alarms generated by Snort

產生警報第2周第4周第5周 誤報1448241057767 真正警報971723982172 警報總數2419965039939

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

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

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

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

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

表3 DARPA數據集在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 使用真實數據集進行測試

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

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

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

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

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

5 結 語

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