基于模糊ID3算法的IDS規(guī)則生成技術(shù)

劉咸通++申培培++辛?xí)赠i++蔡碩

摘 要：本文針對(duì)計(jì)算機(jī)免疫系統(tǒng)模型GECISM中的類MC Agent，基于fuzzy-ID3算法構(gòu)造決策樹，模糊決策樹使用系統(tǒng)調(diào)用作為數(shù)據(jù)集生成入侵檢測(cè)規(guī)則，與C4.5算法生成規(guī)則的對(duì)比。Fuzzy-id3算法生成的規(guī)則具有較低的誤報(bào)率和漏報(bào)率。

關(guān)鍵詞：入侵檢測(cè)；系統(tǒng)調(diào)用；規(guī)則

中圖分類號(hào)：TP393.08 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2017）19-0035-03

隨著網(wǎng)絡(luò)技術(shù)的日益發(fā)展，網(wǎng)絡(luò)安全問題日益顯現(xiàn)出來，網(wǎng)絡(luò)入侵和攻擊的現(xiàn)象屢見不鮮、目前，解決網(wǎng)絡(luò)安全問題的主要技術(shù)有：數(shù)字加密技術(shù)、訪問控制、虛擬專用網(wǎng)、大數(shù)據(jù)安全等。訪問控制技術(shù)、虛擬專用網(wǎng)技術(shù)可以控制已知的網(wǎng)絡(luò)非法訪問，對(duì)于一些未知的訪問只能用籠統(tǒng)的規(guī)則來處理，無法細(xì)化未知訪問的合法性，已無法完全解決網(wǎng)絡(luò)安全的問題.近幾年來，利用生物個(gè)體的細(xì)胞免疫原理，使用系統(tǒng)中進(jìn)程的系統(tǒng)調(diào)用作為判斷計(jì)算機(jī)系統(tǒng)中正常和異常的程序的依據(jù)，也就是所謂的自我和非我.這一應(yīng)用克服了傳統(tǒng)安全技術(shù)非智能化以及粒度粗化的缺點(diǎn).根據(jù)自適應(yīng)、自主學(xué)習(xí)的原則設(shè)計(jì)安全系統(tǒng)模型，使用模糊決策樹區(qū)分計(jì)算機(jī)系統(tǒng)中的”正?！暗南到y(tǒng)調(diào)用和”異常“的異常系統(tǒng)調(diào)用，并刪除各類的”異?！?。

進(jìn)程作為系統(tǒng)中運(yùn)行的最小代碼單位，也是判斷是”正常“訪問還是”異?！俺绦虻闹饕罁?jù)，在操作系統(tǒng)中有應(yīng)用系統(tǒng)日志以及系統(tǒng)審計(jì)日志等數(shù)據(jù)可以用來對(duì)進(jìn)程進(jìn)行分類，這些數(shù)據(jù)一般有具體的系統(tǒng)工具收集，收集起來非常方便，可移植性也較好，但是對(duì)于單個(gè)系統(tǒng)而言數(shù)據(jù)信息量較小，且分析粒度也非常大，并不能完全反應(yīng)系統(tǒng)進(jìn)程的特征.進(jìn)程都是通過其占用的系統(tǒng)調(diào)用來完成工作，就像生物細(xì)胞中的DNA圖譜一樣，不同的進(jìn)程占用的不同的系統(tǒng)調(diào)用不同，因此可以根據(jù)進(jìn)程占用的系統(tǒng)調(diào)用來對(duì)進(jìn)程進(jìn)行分類。美國(guó)新墨西哥州大學(xué)Stephanie Forrest教授提出了這一觀點(diǎn)，其領(lǐng)導(dǎo)的研究小組實(shí)驗(yàn)表明，以等長(zhǎng)劃分而成的所有程序運(yùn)行時(shí)產(chǎn)生的系統(tǒng)短調(diào)用序列有明顯的穩(wěn)定性和連續(xù)性，因此可以通過基于定長(zhǎng)的系統(tǒng)調(diào)用序列來構(gòu)造樣本特征庫來區(qū)分”正常“進(jìn)程和”異常“進(jìn)程稱為自我合肥我.根據(jù)已得到的系統(tǒng)短調(diào)用”正?！?、”異常“的生成判斷”正常“和”異?！暗囊?guī)則庫，規(guī)則庫中無法判斷的短調(diào)用稱為漏點(diǎn)，如果在某個(gè)時(shí)間周期T內(nèi)，漏點(diǎn)的個(gè)數(shù)達(dá)到的限值L，規(guī)則庫則進(jìn)行規(guī)則更新；否則到T時(shí)進(jìn)行規(guī)則更新。

決策樹規(guī)則生成使用C4.5算法，該算法使用信息的熵作為啟發(fā)式，并且假設(shè)樣本的屬性值和分類值是確定的這一前提下建立一棵清晰的決策樹，然后根據(jù)決策樹產(chǎn)生規(guī)則.在保證數(shù)量一定且分布合理的訓(xùn)練集的情況下使用該方法訓(xùn)練出的規(guī)則對(duì)未知樣本進(jìn)行分類預(yù)測(cè)，此時(shí)得到自我和非我的結(jié)果準(zhǔn)確率較高.但是由于在對(duì)未知樣本進(jìn)行匹配時(shí)，若無法和已知規(guī)則匹配即可判斷為異常即非我，所以使用此方法是無法判斷漏點(diǎn)的，在規(guī)則庫中，不是正常即是異常，因此誤報(bào)率較高，所以為提高準(zhǔn)確率，訓(xùn)練集數(shù)據(jù)應(yīng)盡量分布合理。

本文介紹了利用模糊決策樹fuzyy-id3算法構(gòu)造模糊決策樹規(guī)則庫，對(duì)樣本使用規(guī)則進(jìn)行模糊匹配，根據(jù)相應(yīng)的隸屬度（匹配度）來對(duì)結(jié)果分類，可以達(dá)到較好判別自我和非我的效果，此方法應(yīng)用于移動(dòng)互聯(lián)，對(duì)于移動(dòng)PDA訪問的判別也有良好的效果。

1 fuzzy-id3算法

1.1 模糊決策樹

1965年L.A.Zadeh在數(shù)學(xué)上創(chuàng)立了一種描述模糊現(xiàn)象的方法稱為模糊集合論。這種方法把待考察的對(duì)象及反映它的模糊概念作為一定的模糊集合，建立適當(dāng)?shù)碾`屬函數(shù)，通過模糊集合的有關(guān)運(yùn)算和變換，對(duì)模糊對(duì)象進(jìn)行分析.模糊集合論以模糊數(shù)學(xué)為基礎(chǔ)，研究有關(guān)非精確的現(xiàn)象?？陀^世界中，大量存在著許多亦此亦彼的模糊現(xiàn)象即不確定性?，F(xiàn)實(shí)中人類的思想與感知也是模糊的，無法用精確的確定的量來描述.事物本身具有的不確定性以及現(xiàn)實(shí)生活中技術(shù)條件所限造成了計(jì)算機(jī)在在知識(shí)表達(dá)及推理過程產(chǎn)生不確定性即所謂的模糊性.模糊集理論定義了多個(gè)不同的模糊算子以反應(yīng)映現(xiàn)實(shí)中不確定性傳播規(guī)律。模糊集合論是以模糊數(shù)學(xué)為其理論基礎(chǔ)，運(yùn)算靈活性強(qiáng)且富于針對(duì)性，時(shí)間復(fù)雜度也較低。

模糊集合論中的模糊分類可以有如下描述：一個(gè)模糊化后的樣本集合D={d1，d2，…，dn}，其中每個(gè)di由n個(gè)模糊特征屬性A1，A2，…，An和一個(gè)模糊類屬性C={C1，C2，…，Cm}來描述，每個(gè)Ai又由模糊語言變量，即屬性值組成，表示為Ai={Ai1，Ai2，Aik}（i=1，2，…，n）.即每個(gè)示例uj可以用一個(gè)維向量表示，形如：

則示例集D關(guān)于類別C的信息熵為：

，

而用特征屬性劃分的D后的模糊熵為：

則屬性A相對(duì)于數(shù)據(jù)集D的信息增益為：

。

模糊決策樹算法是傳統(tǒng)決策樹算法的一個(gè)擴(kuò)充和完善，使得決策樹學(xué)習(xí)的應(yīng)用范圍擴(kuò)大從而能夠處理不確定性。它合理的處理了學(xué)習(xí)和推理過程中的不精確信息，具有更強(qiáng)的分類能力及穩(wěn)健性.由于能生成不同水平和不同置信度的規(guī)則，為決策者提供豐富的決策信息。

1.2 FUZZY—ID3算法

模糊決策樹歸納的啟發(fā)式算法有多種，比如FUZZY—ID3、Min—Ambiguity等，其中FUZZY—ID3算法是使用最多的一種.下面給出詳細(xì)的FUZZY—ID3算法：

（1）初始化：F←“所有屬性”，D←“所有訓(xùn)練示例”；

（2）選取所有屬性中模糊信息熵最小的屬性作為根節(jié)點(diǎn)；

（3）如果當(dāng)前節(jié)點(diǎn)滿足以下條件，該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，計(jì)算各類的置信度CF的值，選取最大的作為節(jié)點(diǎn)的類別標(biāo)記并記錄，返回；

條件：a.屬性已經(jīng)全部使用

b.

c.

（4）否則，對(duì)該節(jié)點(diǎn)進(jìn)行模糊分割，分割步驟如下：endprint

①對(duì)F中的所有屬性Ai，計(jì)算啟發(fā)式I（C；Ai）的值，選取使之最大的屬性A作為該節(jié)點(diǎn)的測(cè)試屬性；

②F←F＼{A}；

③依次用

（5）將生的樹轉(zhuǎn)換成模糊產(chǎn)生式規(guī)則。

2 計(jì)算機(jī)免疫系統(tǒng)

在計(jì)算機(jī)免疫系統(tǒng)中，將檢測(cè)有害成分稱為免疫檢測(cè)，將消除有害成分稱為免疫應(yīng)答，而對(duì)免疫應(yīng)答激烈程度的調(diào)整稱為免疫調(diào)整。

計(jì)算機(jī)中”正?！芭c”異常“的定義。正常操作不會(huì)對(duì)計(jì)算機(jī)系統(tǒng)造成破壞，只有非法操作產(chǎn)生的異常行為才會(huì)造成對(duì)系統(tǒng)的破壞，保護(hù)正常行為的同時(shí)檢測(cè)并消除異常行為才能保證系統(tǒng)的安全。我們知道程序（進(jìn)程）是通過調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用函數(shù)服務(wù)來實(shí)現(xiàn)的，一個(gè)有害程序只有被調(diào)入內(nèi)存中執(zhí)行異常操作時(shí)才能對(duì)系統(tǒng)造成破壞，因此，程序的行為是正常的還是異常的可以通過執(zhí)行的系統(tǒng)調(diào)用反映出來，但是該調(diào)用與操作系統(tǒng)的版本、系統(tǒng)服務(wù)的類型和危害發(fā)生的位置有關(guān)，所以計(jì)算機(jī)免疫系統(tǒng)使用程序運(yùn)行所形成的系統(tǒng)調(diào)用序列串、操作系統(tǒng)版本、服務(wù)的類型和危害發(fā)生的位置等四個(gè)屬性來表征一個(gè)進(jìn)程是正常的還是異常的。

系統(tǒng)中”正?！笆侵刚Ｓ脩粜袨樵斐傻挠?jì)算機(jī)系統(tǒng)中的系統(tǒng)調(diào)用函數(shù)序列串、操作系統(tǒng)版本、系統(tǒng)服務(wù)的類型和危害發(fā)生的位置的序列。”異?！笆侵福寒惓Ｐ袨樵斐傻挠?jì)算機(jī)系統(tǒng)中的系統(tǒng)調(diào)用序列串、操作系統(tǒng)版本、服務(wù)的類型和危害發(fā)生的位置的序列。由此，計(jì)算機(jī)免疫系統(tǒng)的功能就可以概括為：保護(hù)”正常“程序進(jìn)程；檢測(cè)并消除含有”異?！暗倪M(jìn)程。

3 數(shù)據(jù)預(yù)處理

系統(tǒng)調(diào)用是操作系統(tǒng)提供給用戶程序調(diào)用的一組“特殊”接口。用戶程序可以通過這組“特殊”接口來獲得操作系統(tǒng)內(nèi)核提供的服務(wù)，linux系統(tǒng)調(diào)用主要分為硬件控制、系統(tǒng)狀態(tài)設(shè)置以及內(nèi)存管理、進(jìn)程管理等，考慮到計(jì)算成本，實(shí)驗(yàn)中用定長(zhǎng)滑動(dòng)窗口系統(tǒng)調(diào)用系列，生成長(zhǎng)度為8的系統(tǒng)短調(diào)用（S0，S1，S2，S3，S4，S5，Class1，Class2），其中Class1，Class2為屬性類別，Class1標(biāo)識(shí)為“1”，Class2標(biāo)識(shí)為“0”，放入Normal庫中.同樣對(duì)每個(gè)”異常“系統(tǒng)調(diào)用系列，生成長(zhǎng)度為8的樣本點(diǎn)，Class1標(biāo)識(shí)為“0”，Class2標(biāo)識(shí)為“1”，放入Abnormal庫中.刪除Normal、Abnormal庫中重復(fù)出現(xiàn)的系統(tǒng)斷掉用，刪除Abnormal庫中每條在Normal庫中出現(xiàn)的系統(tǒng)短調(diào)用。

3.1 決策樹規(guī)則生成及匹配

合并Normal、Abnormal庫到訓(xùn)練樣本庫D，每個(gè)樣本有6個(gè)屬性，S0，S1，S2，S3，S4，S5，和類屬性C={CLASS1、CLASS2}來描述，其中，各特征屬性是由一些相同的屬性值，這是因?yàn)槊總€(gè)Linux操作系統(tǒng)的系統(tǒng)調(diào)用，例如固定體積，標(biāo)準(zhǔn)Linux 2.4.18內(nèi)核有237個(gè)系統(tǒng)調(diào)用，即在這個(gè)系統(tǒng)中，每個(gè)屬性有237個(gè)屬性值。每個(gè)樣本庫中的一個(gè)記錄，每個(gè)數(shù)字代表相應(yīng)屬性的匹配度跟這個(gè)樣品（如果樣品的S0是讀取，然后讀取相應(yīng)的屬性值是1，其他是0），使用ID3算法建立D進(jìn)行模糊決策樹學(xué)習(xí)訓(xùn)練，生成模糊決策樹，然后生成規(guī)則。

3.2 使用以下步驟對(duì)規(guī)則進(jìn)行匹配

步驟1：計(jì)算未知的短周期系統(tǒng)調(diào)用序列與特征屬性匹配后的匹配度，把它作為確定分類結(jié)果的結(jié)論匹配度；

步驟：2：取將某個(gè)短調(diào)序列分為同一類結(jié)果的多個(gè)規(guī)則產(chǎn)生的不同的匹配度中最高匹配度的作為分類結(jié)果；

步驟3：對(duì)于某短調(diào)序列以不同的匹配度分到不同類結(jié)果，分別取class1、class2中的最高匹配度，并規(guī)定一個(gè)閾值，如果兩個(gè)匹配度相差超過這個(gè)閾值，則取較大者所在類別，否則認(rèn)為此短調(diào)序列為未知序列。

4 實(shí)驗(yàn)結(jié)果及其分析

實(shí)驗(yàn)使用Linux系統(tǒng)中的rlogin程序，針對(duì)rlogin特洛伊代碼允許入侵通過“后門”登陸系統(tǒng)，系統(tǒng)短調(diào)用序列數(shù)據(jù)集來自墨西哥州大學(xué)計(jì)算機(jī)免疫系統(tǒng)網(wǎng)站.原始數(shù)據(jù)集中的數(shù)據(jù)由兩列構(gòu)成，分別是進(jìn)程標(biāo)識(shí)符和系統(tǒng)調(diào)用.正常運(yùn)行的rlogin程序中有11個(gè)進(jìn)程，植入特洛伊代碼的rlogin程序有9個(gè)進(jìn)程異常，對(duì)這兩個(gè)程序的系統(tǒng)調(diào)用序列長(zhǎng)度為8的窗口采集后，共得到樣本點(diǎn)5981個(gè).按照前所描述方法進(jìn)行數(shù)據(jù)整理，最后Normal庫中為835個(gè)樣本點(diǎn)，Abnormal庫中為216個(gè)，生成訓(xùn)練集D共1051個(gè)示例，其中來自Normal庫中的數(shù)據(jù)，Class1置為1，Class2置為0，來自Abnormal庫中的則正好相反。利用C4.5算法生成規(guī)則，結(jié)果如表1。

利用上述介紹的Fuzzy-ID3算法生成的規(guī)則，其中參數(shù)θ=0.1、β=0.8（置信度）、λ1=0.3，結(jié)果如表2。

在實(shí)驗(yàn)中，提取隨機(jī)70%個(gè)數(shù)據(jù)集作為訓(xùn)練集，30%作為測(cè)試集.如表1所示，規(guī)則數(shù)（置信因子≥0.8），通過C4.5算法生成的，是56。其中22為判斷的”正?！?、”異常“的38個(gè)判斷.然后對(duì)規(guī)則所設(shè)定的短信進(jìn)行分類，誤碼率為4.3%。如表2所示，規(guī)則數(shù)（置信因子≥0.8），通過模糊ID3算法產(chǎn)生，56.其中，21為判斷的”正常“、”異常“的35個(gè)判斷.然后對(duì)所規(guī)定的短信組進(jìn)行分類，錯(cuò)誤率為2.2%，同時(shí)，由于無法判斷4發(fā)短信的分類樣本點(diǎn)，失敗報(bào)告率為1.3%。由于訓(xùn)練集所作的關(guān)于分類確定（或”正?！昂汀碑惓！埃拔粗獦颖军c(diǎn)“空相應(yīng)項(xiàng)目的識(shí)別，和“未知樣本點(diǎn)”不會(huì)產(chǎn)生規(guī)則，相應(yīng)的項(xiàng)目是零和。

為什么高錯(cuò)誤率增加的C4.5算法生成的規(guī)則的理由是，如果某些樣本點(diǎn)從所有不同的規(guī)則，那么它將被視為正常的系統(tǒng)條件的違反，所以系統(tǒng)會(huì)判斷該點(diǎn)為“異常”，顯然，如果我們選擇了過度訓(xùn)練組，錯(cuò)誤率將上升.同時(shí)，把”正?！昂汀碑惓！暗碾`屬度的樣本點(diǎn)的匹配準(zhǔn)則2.4中描述與ID3算法，然后判斷其分類閾值的λ1，漏報(bào)率將跳下。盡管ID3算法產(chǎn)生的漏報(bào)率，這并不說明這種方法不能與C4.5算法相比，由于漏報(bào)率是不可避免的，C4.5算法只是考慮它的錯(cuò)誤率。

在實(shí)驗(yàn)中，如果訓(xùn)練集少，錯(cuò)誤率不會(huì)上升，但是，其漏報(bào)率會(huì)上升，會(huì)產(chǎn)生更多的“未知序列”，這是產(chǎn)生的規(guī)則不全面導(dǎo)致的，需要選擇訓(xùn)練集或移動(dòng)程序TC代理.閾值的影響λ1漏報(bào)率的選擇，所以我們需要在大量的實(shí)驗(yàn)值。

5 結(jié)語

采用Fuzzy-ID3算法構(gòu)造的規(guī)則，可以依據(jù)系統(tǒng)短調(diào)用序列對(duì)進(jìn)程進(jìn)行合理的判斷，得到”正?！?、”異?！盎颉拔粗比N分類，且不會(huì)因?yàn)橛?xùn)練集分布的不合理而升高誤報(bào)率。此方法應(yīng)用于移動(dòng)通訊領(lǐng)域，對(duì)于移動(dòng)終端訪問服務(wù)器時(shí)對(duì)異常訪問的甄別是可行的。

參考文獻(xiàn)

[1]王煜，王正歐，等.基于模糊決策樹的文本分類規(guī)則抽取[J].計(jì)算機(jī)應(yīng)用，2005，（7）：04.

[2]Somayaji A，Hofmeyr SA， Forrest S.Principles of Computer Immune System[z].New Security.Paradigms workshop，ACM， Charlottesville， Virginia， September 22 - 25 1998.

[3]王鳳先，張巖，劉振鵬，等.基于系統(tǒng)調(diào)用的入侵檢測(cè)規(guī)則的生成[J].計(jì)算機(jī)工程與應(yīng)用，2003，（21）.

[4]QUINLAN JR.Induction of decision trees[J].Mach Learning，1986，1（1）：81-106.

[5]朱參世，李響.自適應(yīng)模糊決策樹算法在數(shù)據(jù)流挖掘中的應(yīng)用[J].現(xiàn)代電子技術(shù)，2010，（10）：63.

[6]王熙照，孫娟，楊宏偉，等.模糊決策樹算法與清晰決策樹算法的比較研究[J].計(jì)算機(jī)工程與用，2003，（21）：72.

[7]李川，張永輝，譯.Ian H.Witten Eibe Frank Mark A.Hall著.數(shù)據(jù)挖掘?qū)嵱脵C(jī)器學(xué)習(xí)工具與技術(shù).機(jī)械工業(yè)出版社，2014，（5）.endprint