賈 嫻，劉培玉，公 偉

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

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

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

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

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

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

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

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

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

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

1 引言

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

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

2 樸素貝葉斯分類的相關(guān)模型

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

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

從而后驗概率公式為：

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

2.2 加權(quán)樸素貝葉斯模型

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

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

3 信息增益算法及其改進

3.1 信息增益算法

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

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

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

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

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

IIG算法獲取最優(yōu)特征子集過程如下：

輸入：訓練數(shù)據(jù)集Tain，測試數(shù)據(jù)集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與類的相關(guān)性越高，說明對類的貢獻度越大，視為重要特征

（4）IFGain(Ai)＞θ

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

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

（5）Return Rmerit

輸出：特征子集Rmerit

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

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

4 改進屬性加權(quán)的樸素貝葉斯分類算法

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

改進的屬性加權(quán)樸素貝葉斯算法，利用訓練數(shù)據(jù)信息，對屬性進行加權(quán)，分類器的實現(xiàn)步驟如下：

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

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

步驟3屬性值約簡及權(quán)值參數(shù)的學習：

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

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

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

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

步驟6分類：調(diào)用概率表及屬性權(quán)值列表，得出分類結(jié)果。

5 實驗與分析

5.1 實驗數(shù)據(jù)集

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

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

5.2 實驗設計及結(jié)果

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

表1 特征選擇結(jié)果比較

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

圖1 檢測率比較圖

圖2 誤報率比較圖

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

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

圖3 檢測率比較圖

圖4 誤報率比較圖

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

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

6 結(jié)束語

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

[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]令狐紅英，陳梅，王翰虎，等.基于互信息可信度的貝葉斯網(wǎng)絡入侵檢測研究[J].計算機工程與設計，2009，30（14）：38-40.

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

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

[5]Bagliomi M，F(xiàn)urletti 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]秦鋒，任詩流，程澤凱，等.基于屬性加權(quán)的樸素貝葉斯分類算法[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）；山東省高新技術(shù)自主創(chuàng)新工程（No.2008ZZ28）；山東省教育廳科技計劃項目（No.J09LG52）。

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

2011-08-15

2011-12-07

1002-8331（2013）07-0081-04