一種基于粗糙集屬性約簡的入侵檢測算法

謝景偉

（湖南大眾傳媒職業(yè)技術(shù)學(xué)院，長沙 410100）

0 概述

一般情況下入侵檢測系統(tǒng)（簡稱IDS）是對入侵的方法和系統(tǒng)的脆性進(jìn)行分析的即時(shí)監(jiān)視，以及依據(jù)專業(yè)人員知識人工寫入的，且它是根據(jù)具體的系統(tǒng)環(huán)境和不同的檢測方法的，普通的IDS是由事件采集器和分析器、檢測模式數(shù)據(jù)庫、檢測模式生成器等主要部件組成。

事件采集器主要負(fù)責(zé)采集數(shù)據(jù)（包括網(wǎng)絡(luò)數(shù)據(jù)包，系統(tǒng)日志等）；

事件分析器主要負(fù)責(zé)分析檢測，并發(fā)出入侵警報(bào)；

檢測模式數(shù)據(jù)庫主要負(fù)責(zé)存放已檢測出的攻擊模式（也包括正常行為）；

檢測模式生成器主要負(fù)責(zé)生成新模式加入到檢測模式數(shù)據(jù)庫。

在現(xiàn)實(shí)的網(wǎng)絡(luò)傳輸中，平常數(shù)據(jù)量傳輸特別巨大、數(shù)據(jù)異常繁復(fù)。并且海量的數(shù)據(jù)里很多與入侵攻擊沒有關(guān)系，這些數(shù)據(jù)也許不一致、不完整，這樣就造成入侵檢測誤報(bào)、漏報(bào)。

粗糙集理論（Rough set）是一類對付不確定、不精確和知識模糊等問題的數(shù)學(xué)方面的工具。在應(yīng)對殘缺數(shù)據(jù)分析、推斷和找出數(shù)據(jù)間的聯(lián)系、攝取有效特征、簡化數(shù)據(jù)信息、模糊知識的說明、總結(jié)、歸納等地方有著無與倫比的優(yōu)勢。這些年來它獲得了學(xué)術(shù)界的矚目，并已出色地被用在機(jī)械學(xué)習(xí)、決斷分析、模式識別等方面。而將其用在入侵檢測，就可以達(dá)到自發(fā)從海量統(tǒng)計(jì)數(shù)據(jù)中找出新模型并制定新的安全規(guī)則，建立高精的智能IDS。

1 粗糙集基本概念

1.1 信息處理系統(tǒng)

信息處理系統(tǒng)可以簡稱信息系統(tǒng)，一般可以用S=（U，A）簡化替代S=（U，A，V，f）。

信息處理系統(tǒng)的信息變換為關(guān)系表格形式顯示，關(guān)系表每一行對應(yīng)需要進(jìn)行分析的一個(gè)對象，每一列對應(yīng)這個(gè)對象的一個(gè)屬性值。對象信息由各屬性值來代替，此外關(guān)系表中一個(gè)屬性就表示一個(gè)等價(jià)關(guān)系，全部的關(guān)系表也就是被定義的一系列等價(jià)關(guān)系，這就是知識庫，這么做之后，之前討論的信息約簡就能夠轉(zhuǎn)化成關(guān)系表中屬性約簡。

1.2 屬性約簡

決策表代表決策信息系統(tǒng)的簡化，其中有海量的樣本信息。而其中一個(gè)樣本代表一條決策規(guī)則，全部規(guī)則又構(gòu)成一個(gè)決策規(guī)則集。在現(xiàn)實(shí)使用里，這種決策規(guī)則集沒有實(shí)用性，因里面每個(gè)基本規(guī)則沒有適用性，僅僅是機(jī)械的記下一個(gè)樣本信息，沒法適應(yīng)別的狀況，而進(jìn)行屬性約簡后決策表的一條記錄變成了有相同規(guī)律的樣本信息，決策規(guī)則于是有了非常強(qiáng)的適用性[6]。

在信息分析中，最開始的決策表里的屬性并非相同重要，不必要關(guān)系在信息庫里是冗余的，冗余屬性不單占用資源，且會擾亂人們，不能作出正確、簡潔的決策，故決策表中屬性約簡的作用就是把冗余信息從信息庫中剔除，并且屬性約簡不影響信息庫的分類功能。籠統(tǒng)的說，決策表的條件屬性對應(yīng)決策屬性時(shí)相對屬性約簡不唯一，也就是說同一決策表可以存在多個(gè)屬性約簡，其中屬性的數(shù)量將直接決定決策規(guī)則的繁復(fù)和功能。所以，人們都希望能找到有最少屬性數(shù)量的屬性約簡，只是由于屬性組合的沖突問題又變成最小約簡問題即是NP-Hard問題。當(dāng)今應(yīng)對此問題措施是引入啟發(fā)數(shù)據(jù)到屬性約簡，之后經(jīng)由啟發(fā)數(shù)據(jù)可以縮減樣本待搜索信息量，由此達(dá)到優(yōu)化約簡效率目的。

2 基于粗糙集屬性入侵檢測系統(tǒng)(DIS)模型

2.1 DIS模型

當(dāng)前，基于粗糙集理論的DIS組成部分為事件采集器、數(shù)據(jù)挖掘器、智能決策機(jī)制以及模式匹配，主要是應(yīng)用粗糙集理論對采集過來的數(shù)據(jù)進(jìn)行分析和處理，得到用于入侵檢測的模式，也就是能夠生成有效的安全規(guī)則，然后模式匹配模塊就能夠依據(jù)這些規(guī)則來做入侵分析，得出判斷，而決策部分就依據(jù)該判斷作出相應(yīng)的改進(jìn)。

本章所討論的基于粗糙集的DIS模型就是在對粗糙集屬性頻度約簡算法進(jìn)行改進(jìn)的基礎(chǔ)上，實(shí)現(xiàn)了入侵?jǐn)?shù)據(jù)的處理分析，經(jīng)由對應(yīng)的處理剔除審計(jì)數(shù)據(jù)中冗余的信息，大大提升了數(shù)據(jù)挖掘步驟的效率，并能得到高效、簡潔的安全規(guī)則。

2.2 基于屬性頻度的啟發(fā)式約簡算法及其改進(jìn)

2.2.1 啟發(fā)式約簡算法（基于屬性頻度）

當(dāng)前，一般的屬性頻度算法以決策表相應(yīng)的差別矩陣為基本，綜合其中全體屬性集合，列出全部非核屬性在差別矩陣中的頻數(shù)，假如某非核屬性的頻數(shù)max，則表明這個(gè)非核屬性在甄別兩個(gè)不同的決策對象中起的作用最大，故應(yīng)首先把它加入到約簡集合中，并把包含該屬性的全部其他屬性組合刪除。

基于屬性頻度的啟發(fā)式算法：

將一個(gè)決策表作為算法的輸入：T=U,R,V,f,U是論域，R=C∪D中C,D分別表示條件屬性的集合和決策屬性的集合。

該決策表T的一個(gè)約簡B表示算法的輸出。

第一步：尋找核屬性即C0；開始初始化 B：C0→B

第二步：刪除M中全部和B的交集不為空集的元素，且從條件屬性集合中剔除B中所含元素。即：M-Q→M，C-B→P，Q={ | AijAij∩B≠?}。

第三步：將ck∈P帶入，算出在M中屬性頻度函數(shù)p(ck)，再從全部的 p(ck)找出有max值的cq，即 p(cq)= max{p(ck)}。

第四步：將cq歸入約簡集合中：B∪cq→B

第五步：重復(fù)第一到第四步直到M=?。

2.2.2 基于屬性頻度的啟發(fā)式約簡算法的改進(jìn)（最優(yōu)化約簡）

屬性頻度算法是根據(jù)屬性的頻度數(shù)來確定核屬性，如果某個(gè)屬性在決策表所對應(yīng)的差別矩陣中出現(xiàn)的頻數(shù)很多，那么就說這個(gè)屬性對于決策規(guī)則是很重要的，故應(yīng)首先被考慮加入核屬性集合中。然而在現(xiàn)實(shí)運(yùn)用中會出現(xiàn)達(dá)到max頻度的屬性不止一個(gè)。

對這一現(xiàn)象原算法采取從這些都達(dá)到最大頻度的屬性中隨機(jī)挑選一個(gè)加入核屬性集合中。顯然這樣得到的約簡結(jié)果很可能不是決策表最優(yōu)化約簡。

基于屬性頻度的啟發(fā)式算法的改進(jìn)（實(shí)例）：

輸入端：一個(gè)決策表T=U,R,V,f，U表示論域，R=C∪D，C,D表示條件屬性集合以及決策屬性集合。

輸出端：決策表T的約簡結(jié)果B。

第一步：尋找決策表核屬性C0，同時(shí)初始化B：C0→B

第二步：刪除M中全部和B的交集不為空集合的元素，從條件屬性集合中剔除B相應(yīng)元素。即：M-Q→M，C-B→P，Q={ | AijAij∩B≠?}。

第三步：

(1)對全部的ck∈P，算出M的屬性頻度函數(shù)p(ck)；

(2)從全部p(ck)列出具有max值的cq，如果有max頻度的屬性有且只有一個(gè)，則 p(cq)=max{p(ck)}，隨后將cq加入約簡集合：B∪cq→B，隨后跳到第四步；如果有max頻度的屬性不止一個(gè)時(shí)轉(zhuǎn)到第三步的（3）；

(3)算出屬性頻度最大的各屬性的 POSB∪{cq}(D) /IND(B,D)中所含元素?cái)?shù)目，之后將 POSB∪{cq}(D) /IND(B,D)內(nèi)元素?cái)?shù)目最多的屬性cq加入約簡集合：B∪cq→B。

第五步：重復(fù)第一到第四步直到M=?。

2.2.3 實(shí)驗(yàn)證明

為驗(yàn)證改進(jìn)后算法可靠性，本節(jié)將進(jìn)行UCI中的信息系統(tǒng)的測試分析。

仿真程序的開發(fā)環(huán)境及平臺：

（1）CPU：Intel*2 2.4G

（2）內(nèi)存： DDR400 768M

（3）操作系統(tǒng)：Windows XP sp3

（4）開發(fā)平臺：VC++6.0

程序分為三部分進(jìn)行：

第一部分：將數(shù)據(jù)集合用常用的屬性頻度算法進(jìn)行屬性約簡，即原始算法約簡對照。

第二部分：用改進(jìn)算法對同樣數(shù)據(jù)集合進(jìn)行約簡。即改進(jìn)算法推演。

表1 醫(yī)療數(shù)據(jù)屬性列表

第三部分：依據(jù)前兩部分實(shí)驗(yàn)結(jié)果比較分析，并且得出最終結(jié)論。

例證：

使用一組共有700條的醫(yī)療數(shù)據(jù)屬性列表作為數(shù)據(jù)集合。其中條件屬性和決策屬性（用class表示）如下表所示，此類屬性均為離散型數(shù)據(jù)，故能夠進(jìn)行直接屬性約簡計(jì)算。

兩部分的運(yùn)算結(jié)果如表2所示：

表2 兩種算法的約簡結(jié)果

依據(jù)約簡集合{A,C,E,F}、{C,E,F,G}約簡原始數(shù)據(jù)集，最后約簡比對情況如表3所示：

表3 約簡結(jié)果比對

顯然，約簡集合{C,E,F,G}比{A,C,E,F}約簡效率高得多。此外，根據(jù)多次實(shí)驗(yàn)在50%的情況下原算法得出的約簡集合相對較弱，這證明了改進(jìn)算法或多或少地優(yōu)化了約簡率。

3 結(jié)束語

現(xiàn)實(shí)的入侵檢測非常復(fù)雜，入侵檢測的分析數(shù)據(jù)量也越來越大，而粗糙集理論是處理這類問題的強(qiáng)有力的工具。本文在分析了粗糙集理論、約簡算法的研究基礎(chǔ)上，把粗糙集的數(shù)據(jù)約簡技術(shù)應(yīng)用到對網(wǎng)絡(luò)數(shù)據(jù)的分析處理中，對基于屬性頻度的啟發(fā)式約簡算法進(jìn)行了改進(jìn)，實(shí)驗(yàn)結(jié)果表明，這種方法具有很高的約簡性，通過粗糙集屬性約簡能夠剔除待分析數(shù)據(jù)集合里冗余信息，此外通過數(shù)據(jù)挖掘獲取安全規(guī)則。在識別未知攻擊方面具有較好的性能，對于入侵檢測技術(shù)的發(fā)展具有重要價(jià)值。

[1]王丹,吳孟達(dá),劉銀山.屬性約簡的一種簡單算法[A].第12屆全國模糊系統(tǒng)與模糊數(shù)學(xué)學(xué)術(shù)年會論文集[C].2004.

[2]武志峰.粗糙集理論及其在入侵檢測中的應(yīng)用研究[D].南京師范大學(xué)碩士論文，2005，(4).

[3]曾黃磷.粗集理論及其應(yīng)用——關(guān)于數(shù)據(jù)推理的新方法[M].重慶：重慶大學(xué)出版社,1996.

[4]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社,2001.

[5]謝旭東,梁剛,黃天云.入侵檢測系統(tǒng)技術(shù)介紹與發(fā)展趨勢[J].福建電腦，2004，（6）.

[6]常曉艷,劉振娟.基于粗糙集屬性約簡的過程控制規(guī)則提取[A].第二屆全國信息獲取與處理學(xué)術(shù)會議論文集[C].2004.

[7]唐忠，曹俊月.基于粗糙集屬性約簡的SVM異常入侵檢測方法[J].通信技術(shù),2009，（2）.