Ｒｏｕｇｈ集在基于異常的入侵檢測系統(tǒng)中的應(yīng)用研究

張寧丹　曾曉華

[摘要]針對入侵檢測系統(tǒng)中安全規(guī)則提取的困難，提出利用粗集方法從系統(tǒng)日志信息中挖掘安全規(guī)則，并給出規(guī)則挖掘算法。通過KDDCup99入侵?jǐn)?shù)據(jù)測試集中的數(shù)據(jù)驗證該方法的有效性和可行性，為入侵檢測中安全規(guī)則的提取提供一種新方法。

[關(guān)鍵詞]網(wǎng)絡(luò)安全 入侵檢測 粗集方法 數(shù)據(jù)挖掘

中圖分類號：TP3文獻標(biāo)識碼：A文章編號：1671－7597（2009）0310044－02

一、引言

將數(shù)據(jù)挖掘技術(shù)應(yīng)用于入侵檢測中，構(gòu)建基于數(shù)據(jù)挖掘技術(shù)的入侵檢測系統(tǒng)，就可以自動地從大量的審計數(shù)據(jù)中發(fā)現(xiàn)新的模型或安全規(guī)則，消除入侵檢測系統(tǒng)中規(guī)則提取和編碼的困難，建立一個準(zhǔn)確性高的智能入侵檢測系統(tǒng)。

二、有關(guān)概念與理論

1．粗集理論是波蘭數(shù)學(xué)家Z.Pawlak在1982年提出的一種數(shù)據(jù)分析的方法。在分類的意義下，粗集理論定義了模糊性與不確定性的概念，其特點是不需要預(yù)先給定某些特征或?qū)傩缘臄?shù)量描述，而是直接從給定問題的描述集合出發(fā)，找出該問題中的內(nèi)在規(guī)律。目前已被廣泛應(yīng)用于人工智能、模式識別、知識數(shù)據(jù)庫挖掘、決策支持、機器學(xué)習(xí)、智能控制等領(lǐng)域。粗集理論中的核心問題是屬性約簡，即從決策表中去除不必要的屬性。屬性約簡的目標(biāo)就是要從條件屬性集合中發(fā)現(xiàn)部分必要的條件屬性，使得這部分條件屬性形成的相對于決策屬性的分類和所有條件屬性所形成的相對于決策屬性的分類一致，即與所有條件屬性相對于決策屬性有相同的分類能力。入侵檢測可以看作是一種分類問題，即將每一條審計記錄分為正常的或是某一種特定的入侵。

2．入侵檢測：顧名思義，是指對入侵行為的發(fā)現(xiàn)，它通過在計算機網(wǎng)絡(luò)或計算機系統(tǒng)中的若干關(guān)鍵點收集信息并對收集到的信息進行分析，從而判斷網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象。入侵檢測是指識別惡意破壞計算機或網(wǎng)絡(luò)系統(tǒng)安全的過程，通過對計算機或網(wǎng)絡(luò)系統(tǒng)中的若干關(guān)鍵信息進行收集、分析，從中發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和被攻擊的跡象。完成入侵檢測功能的軟件和硬件組合便是入侵檢測系統(tǒng)。

三、系統(tǒng)原型設(shè)計

（一）設(shè)計原理與方法

基于入侵檢測系統(tǒng)與Rough集理論的特點，且考慮到本文主要討論Rough集理論在基于異常的入侵檢測上的應(yīng)用，本文將主要關(guān)注Rough集理論在檢測時的應(yīng)用細節(jié)，以此證明Rough集理論在異常入侵檢測上的應(yīng)用可能性、優(yōu)越點、不足以及應(yīng)用時所需要考慮的問題。在進行系統(tǒng)設(shè)計時，將遵循以下原則進行系統(tǒng)設(shè)計：

1．多層抽象化：即系統(tǒng)以分層形式實現(xiàn)，并在各層間抽象化，以減少算法本身對外部數(shù)據(jù)形式及模塊的依賴。

2．架構(gòu)參考一些當(dāng)前學(xué)術(shù)界和行業(yè)領(lǐng)域里的IDS框架模型，以此作為系統(tǒng)架構(gòu)的模板，這樣可以避免在設(shè)計架構(gòu)時出現(xiàn)重大缺陷，同時也有利于兼容性。

（二）模型中Rough集的核心算法

使用Rough Set理論分析決策系統(tǒng)的一般過程是先對決策表的屬性進行約簡然后由屬性約簡得到?jīng)Q策規(guī)則具體步驟如下：

1．?dāng)?shù)據(jù)采集建立樣本集；

2．對連續(xù)屬性進行離散化；

3．用離散化后的條件屬性和決策屬性建立決策表；

4．用Rough Set 理論對條件屬性化簡得到最小決策表即決策規(guī)則；

5．用決策規(guī)則對經(jīng)屬性處理后的待識樣本進行決策。

其中使用到關(guān)于Rough集理論的主要算法有下列幾種：離散化算法、屬性約簡算法、規(guī)則生成算法、分類算法，以及在處理數(shù)據(jù)集規(guī)模比較大時所用到的分解算法。有些算法也可以把屬性約簡和規(guī)則生成合并在一起，然而功能依然是相似的。而這些算法之間的彼此關(guān)系，可以用下面的圖1表示。

（三）數(shù)據(jù)離散化

一般在進行屬性約簡和規(guī)則生成之前，都需要進行離散化。離散化過程是對屬性值屬于連續(xù)空間的屬性進行處理，使得該屬性值的值域可以由若干個區(qū)間來表示，每個區(qū)間作為一個離散子，原來該屬性里的各記錄中，該屬性的值將根據(jù)它所屬的離散子，轉(zhuǎn)化成該離散子所對應(yīng)的新值。從而使得所有連續(xù)空間可以由若干個離散區(qū)間表示，從而在規(guī)則算法處理時，能產(chǎn)生更加符合需要的規(guī)則集。在對入侵檢測數(shù)據(jù)集的處理中，我們采用算法1所示的離散化過程。

Algorithm 1：離散化過程

Input:The consistent decision table A

Output:The semi-minimal set of cuts P consistent with A

Data Structure: D-the semi-minimal set of cuts; L=PART(D)-the partition of U defined by D;CA-the set of all possible cuts on A

（四）Decomposition Tree算法

標(biāo)準(zhǔn)的RSKDD處理過程對于大數(shù)據(jù)集的分析效率較低，在做規(guī)則生成之前，應(yīng)對數(shù)據(jù)表進行分解。分解過程是KDD在處理數(shù)據(jù)規(guī)模非常大的數(shù)據(jù)集時常常使用的方法。分解過程是一個比較通用的方法，其主要目的是通過在數(shù)據(jù)集的屬性中通過尋找出某些分類標(biāo)記或分類界限，然后以這些分類標(biāo)記或界限作為分解因子，把數(shù)據(jù)集分解成數(shù)個子集，然后再對這些子集使用相同的分解方法，直到所有分解出來的子集所包含的數(shù)據(jù)元素個數(shù)均符合規(guī)定的大小，然后再對每個數(shù)據(jù)子集使用數(shù)據(jù)挖掘算法。樹狀結(jié)構(gòu)通常是表示這種分解結(jié)果的一個比較好的形式，我們稱它為分解樹。在分解樹中，每個分支的集合，在該分支所表示的屬性上，有著相同的屬性特點，如左分支的所有集合該屬性都小于等于這個分支節(jié)點的節(jié)點值，而右分支的所有集合該屬性都大于這個分支節(jié)點的節(jié)點值。分解樹算法過程大致如下，它首先去找到表A的最佳模板，然后根據(jù)模板將A分成兩個子集，再對兩個子集判斷，若未達到符合的大小，則遞歸進行分解直到完成。

Algorithm2: Decomposition by template tree

Step1Find the best template T in A.

Step2Divide A onto two subtables:A1 containing all objects satisfying

T and A2=A- A1

Step3If obtained subtables are of acceptable size(in the sense of rough set methods)

then stop

else repeat from step 1 to 3 for all"too large"subtables.

該算法生成一個二叉樹，葉子節(jié)點是從原表中分解出來的子表，這些子表再通過規(guī)則生成算法生成各自的規(guī)則集保存在葉節(jié)點里，則該生成樹可用于接下來的分類操作中。假設(shè)u為一個待分類對象且A(T)是一個包含所有符合模板T的對象的子表，通過算法3從根開始搜索直到將該對象的類別分類出來。

Algorithm3: Classification by template tree

Step 1 If u matches template T found for A

then: go to subtree related to A(T)

else :go to subtree related to A(〕.

Step2 If u is at the leaf of the tree then go to 3

else: repeat 1-2 substituting A(T)(or A()for A .

四、實驗結(jié)果

實驗中使用了KDDCup99的數(shù)據(jù)作為訓(xùn)練和檢測數(shù)據(jù)。

（一）實驗選取的數(shù)據(jù)介紹

在實驗中，我們選取KDDCup99數(shù)據(jù)集中的一部分?jǐn)?shù)據(jù)作為我們實驗的訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)。

（二）屬性集約簡

實驗中我們對離散化后的訓(xùn)練數(shù)據(jù)用粗糙集進行屬性約簡，在具有41個屬性的訓(xùn)練數(shù)據(jù)上，我們共生成了4個屬性集約簡，屬性集約簡的表示形式如下：

(duration,service,src_bytes,dst_bytes)

(duration,service,src_bytes,dst_host_count)

(service,src_bytes,dst_bytes,logged_in,dst_host_count,

dst_host_same_src_port_rate)

(protocol_type,src_bytes,dst_bytes,is_guest_login,dst_host_count,

dst_host_srv_count,dst_host_same_src_port_rate)

（三）實驗結(jié)果和分析

經(jīng)過對大量訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的反復(fù)訓(xùn)練及測試，得到比較理想的效果。從表2可以看出，本文提出的Rough集在基于異常的入侵檢測方法具有高檢測率、低誤檢率。

五、總結(jié)

本文通過實驗驗證了基于Rough集理論的異常入侵檢測模型的有效性，測試了系統(tǒng)的性能。實驗結(jié)果表明，該方法對DoS和Probe攻擊具有很高的檢測率，具有較低的誤檢率，并且對U2R和R2L攻擊也具有較好的檢測率，這進一步說明了將Rough集應(yīng)用于基于異常的入侵檢測模型的可行性。

基金項目：湖南省教育廳科學(xué)研究資助項目(07c720)

參考文獻：

[1]E著、李逢天等譯，Carter,Cisco，安全入侵檢測系統(tǒng)，北京：人民郵電出版社，2003.

[2]羅守山，入侵檢測，北京郵電大學(xué)出版社，2004.4.

[3]韓東海、王超、李群，入侵檢測系統(tǒng)及實例剖析，北京：清華大學(xué)出版社，2002.5.