基于改進屬性加權的樸素貝葉斯入侵取證研究

賈 嫻，劉培玉，公 偉

JIA Xian1，2,LIU Peiyu1，2,GONG Wei1，2

1.山東師范大學 信息科學與工程學院，濟南 250014

2.山東省分布式計算機軟件新技術重點實驗室，濟南 250014

基于改進屬性加權的樸素貝葉斯入侵取證研究

賈 嫻1，2，劉培玉1，2，公 偉1，2

JIA Xian1，2,LIU Peiyu1，2,GONG Wei1，2

1.山東師范大學 信息科學與工程學院，濟南 250014

2.山東省分布式計算機軟件新技術重點實驗室，濟南 250014

針對傳統樸素貝葉斯分類模型在入侵取證中存在的特征項冗余問題，以及沒有考慮入侵行為所涉及的數據屬性間的差別問題，提出一種基于改進的屬性加權樸素貝葉斯分類方法。用一種改進的基于特征冗余度的信息增益算法對特征項集進行優化，并在此優化結果的基礎上，提取出其中的特征冗余度判別函數作為權值引入貝葉斯分類算法中，對不同的條件屬性賦予不同的權值。經實驗驗證，該算法能有效地選擇特征向量，降低分類干擾，提高檢測精度。

入侵取證；樸素貝葉斯；加權樸素貝葉斯；信息增益；特征冗余度；屬性加權

1 引言

入侵取證是近年來網絡安全研究上的一個熱點，很多用于入侵檢測的技術都可用于動態取證分析，有效打擊網絡犯罪。常用于入侵檢測的分類算法有貝葉斯算法、C4.5算法、支持向量機等。其中樸素貝葉斯分類算法在入侵取證中是一種有效的證據檢測算法，具有很強的概率推理能力，可用來檢測已知的和未知的入侵，或已知的入侵變種，通過對檢測出來的入侵或不良攻擊行為的實時動態分析，可使整個取證過程更加具有智能性和實時性，并且還能迅速做出響應，通過報警提示或是采取切斷當前異常TCP連接等措施以減少危害性后果的發生。

針對樸素貝葉斯對冗余特征敏感的問題，本文首先提出一種改進的信息增益特征選擇算法（Improved Information Gain，IIG）來刪除無關的和冗余的特征，得到最優特征子集。另外一個問題就是樸素貝葉斯入侵檢測在對樣本分類時，沒有考慮到入侵行為所涉及的數據屬性不同對分類所起作用也不同，加權樸素貝葉斯是對它的一種擴展。文獻[1]提出了根據屬性的重要性給不同屬性賦不同權值的加權樸素貝葉斯（Weighted Naive Bayes，WNB）模型，并通過實驗發現它們能改進樸素貝葉斯的分類效果[1]，文獻[2-3]分別提出用互信息相對可信度R和信息增益進行特征選擇，并且將R和信息增益作為權值對NB模型進行改進。但是這些權值計算方法沒有考慮屬性之間的相關性對分類的影響，而IIG算法很好地兼顧了二者。因此本文提出一種改進的屬性加權樸素貝葉斯分類方法（Improved Attribute Weighted Naive Baye，IWNB），用改進的信息增益作為一種新的屬性權值計算方法，提高了樸素貝葉斯的分類性能。

2 樸素貝葉斯分類的相關模型

2.1 樸素貝葉斯模型貝葉斯法則是貝葉斯學習方法的基礎，根據貝葉斯公式：

為敘述方便，對符號作如下約定：用大寫字母表示變量，C表示類別變量，A表示屬性變量，假定共有m個屬性變量，A=＜A1，A2，…，Am＞；用小寫字母表示變量取值，分別表示類別變量和屬性變量的值域；用X表示待分樣本集，x=＜a1，a2，…，am＞表示待分類樣本；用T表示訓練樣本集，ti=＜a1，a2，…，am，cl＞表示訓練實例[4]。樸素貝葉斯分類器基于一個簡單的假定：各屬性相對于類別條件獨立。則有：

從而后驗概率公式為：

測試樣本（E）被分在后驗概率最大的類中，由于P() x為一常數，則樸素貝葉斯分類模型為：

2.2 加權樸素貝葉斯模型

樸素貝葉斯條件獨立性的假設在實際應用中很難滿足，條件屬性對決策屬性的分類重要性是不一致的。因此，可根據各個屬性對分類的重要程度賦不同的權值將其擴展為加權樸素貝葉斯，加權樸素貝葉斯模型為[1]：

其中，wi代表屬性Ai的權值，屬性的權值越大，該屬性對分類的影響就越大。加權樸素貝葉斯的關鍵問題就在于如何確定不同屬性的權值[4]。

3 信息增益算法及其改進

3.1 信息增益算法

信息增益（Information Gain，IG）是信息論中一個重要的概念。在IG中，重要性的度量標準就是看屬性能夠為分類系統帶來的信息量的大小，值越大，說明其包含的信息量也越大。屬性 A的信息增益[5]定義為：Gain(A)=其中：在式（1）中，I(s1，s2，…，sm)由樣本的熵來確定，其中，m是樣本類別數；P(Ci)是任意樣本中屬于類Ci的概率，其值等于si/s；si是屬于類 Ci的樣本數；s是總的樣本數。

式（2）計算的是由屬性A劃分成子集的熵，設屬性A具有v個不同的取值{a1，a2，…，av}，用屬性A可以將s劃分為v個子集是子集A=aj中的樣本個數除以s中總的樣本數，表示是第 j個子集的權值，sij是子集 sj中屬于類 Ci的樣本數；且中樣本屬于類Ci的概率。

Gain(A)就是從特征A上獲得該劃分的IG，它越大，表示該特征在給定記錄集中具有的區分度越大，對分類越重要。

3.2 基于特征冗余度的信息增益算法改進

IG算法是一種有效的特征選擇算法，能夠較好地解決入侵取證中存在的數據高維海量問題，保證檢測精度，提高檢測速度。但由于其在特征選擇時只是考慮了選擇每個屬性所得到的信息量的大小，并沒有考慮屬性之間的冗余性，即當一個屬性被選擇之后，如果另一個屬性與之有很大的相關性，那么該屬性往往一般沒有再被選擇的必要。所以該算法對無關特征過濾效果理想，但對于冗余特征的過濾則效果很差，這就導致了特征子集中存在著大量的冗余特征，從而影響了分類器的性能。而基于屬性相關性的特征選擇（Correlation-based Feature Selection，CFS）[6]算法能夠識別冗余屬性，因此結合這兩種算法各自的特點，將CFS算法中用于度量特征冗余度的函數 Merits=引入到IG算法中，通過對其進行改進形成特征冗余度判別函數Rmerit來刪除冗余特征，形成IIG特征選擇算法，其中，表示類與特征之間的平均相關度，表示特征與特征之間的平均相關度。

IIG算法獲取最優特征子集過程如下：

輸入：訓練數據集Tain，測試數據集Test，IG過濾閾值θ和初始特征集S

（1）計算 I(s1，s2，…，sm)

（2）For i=1 to n do

計算E(Ai)

（3）Gain(Ai)=I(s1，s2，…，sm)-E(Ai)//得到每個屬性特征 A的信息增益，Gain(A)越大，表示該特征A與類的相關性越高，說明對類的貢獻度越大，視為重要特征

（4）IFGain(Ai)＞θ

Rmerit(Ai)其中，p為S′中特征的個數；為第Ai個特征和其余特征的相關度的平均值。對于特征之間的相關性通過熵計算方式來進行評價

每次從剩余屬性中選擇一個加入到當前子集中，使得產生的新子集的評價值最高，搜索得到的較優特征子集作為最后的特征選擇結果

（5）Return Rmerit

輸出：特征子集Rmerit

特征子集Rmerit是最佳特征子集，其中，各個特征應和類別標記具有較高的相關性，同時這些特征之間應盡量互不相關。

由此可以發現在最終的特征子集中，不一定是單個最好的特征，但是最好的特征子集是不需要包含最好的單個特征的。另外在最初的時候設定一個閾值θ為0.2，只有Gain(Ai)大于0.2的時候才進行第（4）步的操作（其中0.2是經驗值），否則將其刪除，不再進行特征之間的判斷，使該算法有較高的效率。IIG算法在沒有增加IG算法時間復雜度的基礎上，兼顧了無關特征和冗余特征的過濾，在特征選擇上得到了較好的效果。

4 改進屬性加權的樸素貝葉斯分類算法

常見的權值計算方法都是通過嘗試對屬性與類別之間的相關關系進行量化，以此值作為加權系數，對該屬性項的屬性取值進行加權，關聯程度較大的屬性值將獲得較大的加權系數，反之，將獲得較小的加權系數[7]。但是在最佳特征子集中，單個特征不一定是與類別的關聯程度最大的，所以特征屬性與類別之間的相關度并不能全面衡量各個特征屬性對分類意義的大小，還應該考慮屬性之間的關聯性對分類的影響。因此本文提取出IIG算法中的特征冗余度判別函數作為屬性權值變量來判斷該屬性在決策中的作用，在此函數中，加入一個屬性特征之后，如果該特征與類之間的關聯度越大，同時與其他屬性特征之間的關聯度越小，那么該函數值就越大，表明該特征對分類是起著積極的作用。此函數值更能全面地體現出該屬性特征對分類的貢獻，同時使得到的特征子集也越來越趨向于最優。

改進的屬性加權樸素貝葉斯算法，利用訓練數據信息，對屬性進行加權，分類器的實現步驟如下：

步驟1對數據進行預處理：將訓練樣本和待分類樣本進行補齊和離散化。

步驟2判斷：如果是分類任務，則轉步驟6，如果是訓練任務則轉步驟3。

步驟3屬性值約簡及權值參數的學習：

步驟3.1計算每個屬性的信息增益，對不滿足預定閾值的屬性刪除，選擇那些滿足預定閾值的信息增益的屬性；

步驟3.3按照本章中的權值定義計算約簡后的每個屬性Ai的權值wi。

步驟4概率表的學習：根據約簡后的訓練樣本集，針對每個屬性Ai的屬性值aik，每個類別cl，計算所有的先驗概率，即在類別cl下屬性值aik出現的概率，以及，即類別cl出現的概率。

步驟5生成加權樸素貝葉斯概率表及屬性權值列表，即所需的加權樸素貝葉斯分類器。

步驟6分類：調用概率表及屬性權值列表，得出分類結果。

5 實驗與分析

5.1 實驗數據集

實驗數據選用KDD Cup99數據集[8]。該數據集包含了在網絡環境中仿真的各種入侵，共Dos、U2R、R2L和Probe共4類攻擊類型，每條攻擊記錄都有42個屬性，其中34個連續屬性，7個離散屬性，1個類別屬性。

由于整個數據集太大，通常使用一個10%的子集來測試算法的性能。由于數據集中的攻擊記錄的比例大大超過了真實環境中入侵數據應占的比例，并且KDD-99數據集中攻擊數據分布不均勻，如果隨意地選取數據，那么就有可能出現選取的某組數據集里只包含一種類型攻擊數據的情況，這對于反映整個網絡真實環境是不利的[9]。所以以隨機方式重新建立兩個數據集，一個作為訓練數據集，包括10 490條記錄，另一個作為測試數據集，含有20 000條記錄，其中異常連接的種類盡可能平均。

5.2 實驗設計及結果

為降低分類干擾，提高入侵取證的精度，首先通過特征選擇對屬性約簡，進行降維處理是非常有必要的，同時也滿足了取證及時性的原則。IG改進前后的特征選擇結果如表1所示，其中數字代表特征編號。

表1 特征選擇結果比較

經過IG算法之后，特征子集中的特征個數由41變為22，約簡掉了原始特征集中約47%的特征，而IIG算法在此基礎上又約簡掉了原始特征集中約24%的特征（約10個）。IIG算法在IG算法去除無關特征的基礎上去除冗余特征，提取出了12個比較重要的屬性特征，得出代表問題空間的最優特征子集，同時計算出各特征項的權重作為加權樸素貝葉斯的加權系數，從檢測率和誤報率兩方面驗證IWNB算法的有效性。實驗結果如圖1、圖2所示。

圖1 檢測率比較圖

圖2 誤報率比較圖

由圖1、圖2可知，用改進屬性加權方法實現的IWNB性能顯然是最好的。傳統NB算法對于Normal、Dos、Probe攻擊的檢測率也較高，IG方法改進前后的檢測率差別并不大，且基于改進信息增益的樸素貝葉斯算法（NB-IIG）比基于信息增益的樸素貝葉斯算法（NB-IG）略高，這是因為，IIG算法去除了影響樸素貝葉斯分類性能的冗余特征。基于信息增益的加權樸素貝葉斯算法（WNB-IG）比基于信息增益的樸素貝葉斯算法（NB-IG）要高，這是因為WNB-IG算法考慮了屬性重要性不同對分類的影響。

為了體現IWNB算法的全面性，更好地說明各個類別的檢測情況，利用上述的訓練集和測試集，在得出的最優特征子集上又分別與基于神經網絡（NN）和支持向量機算法（SVM）的檢測性能進行了比較，如圖3、圖4所示。

圖3 檢測率比較圖

圖4 誤報率比較圖

總體上不論哪一種檢測算法對于U2R和R2L攻擊的檢測率都要低于另外三種攻擊，這是由于這兩種攻擊在數據集中占的比例很小，一般又是偽裝成合法用戶的身份進行攻擊，這樣就使其特征與正常數據包比較相似，給算法的檢測帶來了一定的困難。盡管如此，IWNB算法對U2R 和R2L攻擊還是有著較高的檢測率的。鑒于這兩種攻擊雖然所占的比例較小，但攻擊的危害性仍然較大，因此如果能夠有效檢測出這兩種攻擊，對提高入侵取證的性能還是非常明顯的。

另外，誤報率也得到有效控制和降低，這將更有助于發現系統中的異常情況，避免真正的攻擊就夾雜在數不清的虛假告警中蒙混過關。IWNB算法對可能帶來后續危害性的Probe攻擊的誤報率達到了0。

6 結束語

本文提出了一種改進屬性加權的樸素貝葉斯分類算法用于入侵取證的證據檢測中。首先用一種改進的基于特征冗余度的信息增益算法得到優化的特征子集，在去除無關特征的同時也過濾了冗余特征。然后在此基礎上，采用其中的特征冗余度判別函數作為加權樸素貝葉斯模型中新的權重計算公式，提高了樸素貝葉斯的分類精度，使獲得的證據信息更加真實和有效，從而證明了本文方法在入侵取證中的有效性和可行性。

[1]Harry Z，Sheng S L.Learning Weighted Naive Bayes with accurate ranking[C]//Proceedings of the 4th IEEE International Conference on Data Mining（ICDM 04），Brighton，UK，2004：567-570.

[2]令狐紅英，陳梅，王翰虎，等.基于互信息可信度的貝葉斯網絡入侵檢測研究[J].計算機工程與設計，2009，30（14）：38-40.

[3]何慧，蘇一丹，覃華.基于信息增益的貝葉斯入侵檢測模型優化的研究[J].計算機工程與科學，2006，28（6）：3288-3290.

[4]鄧維斌，王國胤，王燕.基于Rough Set的加權樸素貝葉斯分類算法[J].計算機科學，2007，34（2）：204-206.

[5]Bagliomi M，Furletti B，Turini F.DrC4.5：improving C4.5 by means ofpriorknowledge[C]//Proceedings ofthe ACM Symposium on Applied Computing.Santa Fe：ACM Press，2005：474-481.

[6]HallM A.Correlation-based feature selection fordiscrete and numericclassmachinelearning[C]//Proceedingsofthe 17th InternationalConference on Machine Learning.San Francisco：Morgan Kaufmann Publishers，2000：359-366.

[7]秦鋒，任詩流，程澤凱，等.基于屬性加權的樸素貝葉斯分類算法[J].計算機工程與應用，2008，44（6）：107-109.

[8]Information and Computer Science University of California. Irving KDD cup 1999 data[EB/OL].[2010-09-20].http：//kdd. ics.uci.edu/databases/kddcup99/kddcup99.html.

[9]肖立中，劉云翔.適合入侵檢測的分步特征選擇算法[J].計算機工程與應用，2010，46（11）：81-84.

1.School of Information Science and Engineering,Shandong Normal University,Ji'nan 250014,China

2.Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology,Ji'nan 250014,China

Traditional Naive Bayes classification exists the issues of feature redundancy in intrusion forensics and neglects the difference between data attributes in different intrusion actions.For these issues,an improved Weighted Naive Bayes classification method by setting attribute weights is proposed.A new Information Gain algorithm based on feature redundancy is used to optimize the set of feature,then the discriminant of feature redundancy extracted as weights is introduced to Bayes classification algorithm based on this optimization results.The different condition attributes are weighted differently.The experimental results show that the new algorithm can effectively select features,reduce classification interference and improve detection accuracy.

intrusion forensics;Naive Bayes;Weighted Naive Baye;Information Gain;feature redundancy;attribute weighted

A

TP393

10.3778/j.issn.1002-8331.1108-0191

JIA Xian,LIU Peiyu,GONG Wei.Research of intrusion forensics based on improved attribute Weighted Naive Bayes. Computer Engineering and Applications,2013,49（7）：81-84.

國家自然科學基金（No.60873247）；山東省自然科學基金（No.ZR2009GZ007）；山東省高新技術自主創新工程（No.2008ZZ28）；山東省教育廳科技計劃項目（No.J09LG52）。

賈嫻（1984—），女，碩士生，研究方向為網絡信息安全，網絡安全審計等；劉培玉（1960—），男，教授，博士生導師，主要研究方向為計算機網絡信息安全，網絡系統規劃，網絡信息資源開發和軟件開發技術；公偉（1987—），男，碩士研究生，研究方向為網絡信息安全，網絡安全審計等。E-mail：spring2019@126.com

2011-08-15

2011-12-07

1002-8331（2013）07-0081-04