基于樹加權樸素貝葉斯算法的入侵檢測技術研究

王　輝　陳泓予　楊姍姍

(河南理工大學計算機科學與技術學院　河南 焦作 454000)

?

基于樹加權樸素貝葉斯算法的入侵檢測技術研究

王輝陳泓予楊姍姍

(河南理工大學計算機科學與技術學院河南 焦作 454000)

摘要針對樸素貝葉斯(NB)算法在現實情況中所存在的缺陷，提出一種改進后的樸素貝葉斯算法——樹加權樸素貝葉斯(TW-NB)算法。該算法通過引入決策樹歸納法(DTI)在屬性之間條件獨立的集合中選擇出相對更為重要的子屬性集，并利用權重參數弱化了NB算法的條件獨立假設性，從而降低了分類數據的維度，提高了算法的分類準確率。結合實驗結果證明，在使用有限的計算資源下，基于TW-NB算法的入侵檢測技術對于不同的網絡入侵類型皆能表現出較高的檢測率(DR)和較低的誤檢率(FR)。

關鍵詞樸素貝葉斯決策樹歸納法入侵檢測準確率

INTRUSION DETECTION TECHNOLOGY BASED ON TREE-WEIGHTING NAIVE BAYESIAN ALGORITHM

Wang HuiChen HongyuYang Shanshan

(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,Henan,China)

AbstractAiming at the deficiency of naive Bayesian (NB) algorithm in the reality, this paper proposes an improved NB algorithm which is called tree-weighting naive Bayesian (TW-NB) algorithm. This algorithm, by introducing the decision tree induction (DTI), selects a comparatively more important subset of attributes from the set of conditional independence assumption, and uses weighting parameter to weaken the conditional independence assumption of naive Bayesian and thus reduces the dimensionality of the classification data, as well as improves the classification accuracy of the algorithm. It is verified by combining the experimental results that the intrusion detection technology based on the TW-NB algorithm can achieve higher detection rates (DR) and lower false rates (FR) for different network intrusion types when the computational resources used are limited.

KeywordsNaive BayesianDTIIntrusion detectionAccuracy

0引言

隨著網絡信息量的不斷增大以及網絡服務規模的日益擴大，保障網絡數據安全性的網絡信息安全技術開始受到各界領域的關注與重視。入侵檢測技術(IDT)在網絡環境中作為防火墻技術(FT)的有效補充可被分為異常檢測(AD)和誤用檢測(MD)兩大類，它能夠通過審計、檢測、識別和響應的方式實時地對網絡行為進行監控并過濾信息數據，形成一種內外呼應的智能保護體系[1]。

由于網絡技術的不斷更新，網絡入侵行為也演變的更加復雜多變，海量數據情況下的網絡環境也使得入侵檢測技術不斷面臨著巨大的挑戰。因此，將針對大數據環境的數據挖掘(DM)算法如：KNN[2]、樸素貝葉斯(NB)[3]、支持向量機(SVM)[4]、K-means[5]等應用在入侵檢測技術當中逐漸成為研究熱點。其中，樸素貝葉斯(NB)算法作為最優秀的分類模型之一被廣泛應用于各信息領域。但由于NB的“獨立性假設”要求，這樣會忽略屬性與屬性之間的依賴關系，使得屬性所具有的關系性得不到體現，這與網絡環境中數據之間的復雜聯系情況相違背，對于入侵檢測技術中的網絡行為分類就會表現出較低的準確率。因此，針對這一算法缺陷，研究人員運用各種方法技術對樸素貝葉斯(NB)算法進行改進，以提升其分類的性能。

文獻[6]中首次引入了隱樸素貝葉斯(HNB)模型的概念，該算法在NB模型的基礎上通過為每個屬性節點增加一個隱藏父節點來記錄該節點與其他節點間的依賴關系，弱化了屬性間的獨立性條件，從而提高了分類精度，但該模型對于多重屬性的關系網絡卻顯得效率較低。在文獻[7]中，針對HNB算法改進的雙隱樸素貝葉斯(DHNB)模型被提出。該模型通過再度為每個屬性節點增加一個新的隱藏父節點，該節點用來記錄每個屬性依賴關系的加權總和，從而更加充分地表示每個節點之間的關系情況，通過權重(Weight)屬性進一步提升了NB算法的性能。文獻[8]介紹了一種隨機選擇樸素貝葉斯(RSNB)，該算法是在包裝器(Wrapper)屬性特征子集選擇方法(FSS)的基礎之上，在整個屬性空間中裝載隨機搜索，使得NB算法的預測性和分辨性增強，但在一定程度上也增加了算法本身的時間和空間復雜度O(n)。Flores等人[9]采用了在連續和離散域AODE (Aggregating One-dependence Estimators)模型中自動建立基于復雜屬性值的半樸素貝葉斯(SNB)，該算法能夠將依賴性較強的基本屬性特征組合成集合，因此SNB在某種程度上簡化了屬性集的復雜度，去除冗余屬性，從而避免了分類干擾因素。在文獻[10]中，一種動態完全樸素貝葉斯(DCNB)分類模型被建立，該算法通過使用多元高斯核函數估計屬性條件聯合密度與平滑參數優化的方法，有效地利用了屬性之間的條件依賴信息，從而提升了NB算法的分類準確性，但該改進算法針對大數據環境卻顯得效率有所降低。文獻[11,12]分別引入屬性加權的思想對NB算法進行了改進，通過對不同的條件屬性賦予不同的權值來降低分類干擾，提高檢測精度。

本文在前人的研究基礎之上，針對上述改進方法的優缺點，提出了一種改進的NB算法——樹加權樸素貝葉斯(TW-NB)算法，并將該算法引入到入侵檢測技術當中。該算法通過使用決策樹歸納法(DTI)過濾出重要的屬性子集，首先通過決策樹估計出被選擇的屬性權重，然后只有這些由決策樹根據它們相關權重所選擇出的最重要的屬性才能被用于“類條件獨立性假設”的計算。本文將結合使用KDD’99入侵檢測數據集測試并驗證TW-NB算法在入侵檢測技術中的性能，并與NB算法進行分類準確度的比較。實驗結果證明，TW-NB算法在網絡入侵行為的檢測率與誤檢率方面較NB算法都有顯著的改善，針對復雜多級的集合環境也能表現出較高的分類效率。

1改進算法相關研究

1.1NB分類算法

給定一個N維訓練樣本集T={D1,D2,…,Dn}，其中Di={d1,d2,…,dn}表示集合中每個數據記錄。訓練集T包含屬性集合A={A1,A2,…,An}，而每個屬性Ai擁有屬性值集合{a1,a2,…,an}，屬性值可以是離散值或者連續值。訓練數據集T還包含類集合C={C1,C2,…,Cm|(m≤n)}，每個訓練樣本實例D(D∈T)均擁有一個特定的類別標記Cj。對于一個測試樣本集E={e1,e2,…,en}，測試實例ei可根據貝葉斯定理計算的后驗概率P(Cj|Ai)得出其所屬類別。先驗概率P(Cj)可由拉普拉斯校正方程統計每個類別Cj(j≤m)在訓練集T中所出現的頻率估算所得，條件概率P(Ai|Cj)可相應地根據屬性值ai(i≤n)在訓練集T中對應的所屬類別Cj中出現的頻率計算得出。因此，樸素貝葉斯(NB)算法可通過先驗概率和條件概率進行預測，從而得出待分類樣本實例的所屬類別，達到不同數據歸類的目的。

(1)

根據式(1)可分別計算出測試樣本屬性ei所屬類別的后驗概率，NB分類算法找出最大后驗概率MAP最終劃分屬性的歸屬類別，根據式(2)計算所得，即在訓練集中僅當P(Ci|ei)>P(Cj|ei)(i≠j,1≤j≤m)，則ei的類別標簽為Ci，概率P(Ci|ei)即為最大后驗假設。

(2)

樸素貝葉斯分類器(NBC)是一個基于概率的算法，可以預測樣本所屬類成員的概率。該算法有以下優點：(1) 算法構造簡單，時間復雜度低；(2) 概率生成僅需單次遍歷訓練集合；(3) 模型結構清晰嚴謹，具備較好的魯棒性和可擴展性。NBC需要條件獨立性假設的前提，即屬性在給定類的影響獨立于其他屬性。

1.2決策樹歸納法

決策樹歸納法(DTI)是一組規則集合，使用遞歸的方式將訓練樣本集(TS)劃分成更小的子集合(Sub-TS)，直到每一個子集合擁有獨有的所屬類別標簽。DTI算法通常采用信息論(IT)作為屬性選擇方法，根節點TS的選擇是基于計算出的所具有最高信息增益的屬性。給定一個N維訓練樣本集T={t1,t2,…,tn}，pj表示樣本實例ti(i≤n)屬于類別Cj(j≤m)的先驗概率，可根據式(3)得出對給定的樣本實例進行分類所需要的期望信息Info(T)。

(3)

相應地，訓練樣本集T根據屬性A={a1,a2,…,an}迭代地被劃分成N個不同的子集合{T1,T2,…,Tn}，其中Ti為樣本集合T中屬性A=ai時的樣本子集合。可根據權重值|Ti|/|T|計算出屬性A劃分T的期望信息，從而根據原始信息要求Info(T)和新的信息要求的偏移量計算得出信息增益InfoGain(A)。根據樣本集T中的屬性值，逐一地計算出每個屬性值對T進行劃分的信息增益，從中選擇出具有最高信息增益的屬性Am作為最佳屬性來劃分子集合，遞歸整個過程直到所有集合都被正確歸類。

(4)

DTI用于分析構建模型的可行性與可信度，相應地根據觀察推出其邏輯表達式及結構，通過其簡單清晰的邏輯推理和分割信息值，能夠快捷地對大數據集進行高效的數據劃分。但針對連續型數據和多類別集合，劃分效率就會隨復雜度的升高而降低。

1.3TW-NB算法

樹加權樸素貝葉斯(TW-NB)算法是通過引入決策樹歸納法(DTI)來增強樸素貝葉斯(NB)算法的預測性與可行性，增加權重參數使樣本屬性之間的獨立性得到弱化，運用信息增益比迭代地將集合逐步精確細分，從而使得每個樣本實例都能正確的被歸類。

在一個給定的N維訓練樣本集合U中，其每一個訓練樣本實例Si(Si∈U)都擁有一組屬性{A1,A2,…,An}，且每個屬性都有不同的取值{a1,a2,…,an}。同時，樣本集中的類集合C={C1,C2,…,Cm}用于標記樣本實例Si(i≤n)。首先，根據決策樹歸納法則，將訓練集U構建成未修剪的決策樹Tr，集合中每個樣本擁有屬性值，Tr作為屬性選擇及計算影響樣本屬性Ai歸類的權重值φ的決策方法。構建完Tr后，使用決策樹分類器從集合U(U≠?)中分出最影響分類的子集合Us(Us?U)，為訓練集U中每一個屬性Ai初始化權重值φ(i≤n,φ≥0)。如果Ai∈U但Ai?Tr，則設初值φ=0。計算出Tr中測試屬性Ai∈Tr的最小深度D，并將屬性的權重值初始化為1/D。根據式(5)，將選擇屬性的權重值設為樸素貝葉斯(NB)后驗概率計算定理的指數時，能夠影響分類的條件概率估算。最終，通過Laplace定理估計出Tr中類先驗概率P(Cj)(j≤m)和屬性條件概率P(Ai|Cj)，屬性通過φ≠0而被選擇出作為影響樣本的最終歸類，從而計算出后驗概率而得出正確分類，而φ=0的屬性樣本將不會出現在分類集合中。

(5)

其中，權重值φ是屬性值類條件概率計算及樣本之間關系的影響因子，得出樣本屬性的所屬類別需要根據決策樹Tr確定其影響最終分類的屬性關系。并根據先驗概率和條件概率估計出最大后驗概率MAP，通過遞歸的原則逐步重復劃分子集合的過程，將錯分的子集合再次重組繼續劃分歸類，最終確定每個樣本的分類集合。TW-NB算法的具體實現過程如下：

輸入訓練樣本集U={S1,S2,…,Sn}。

1) 在集合U中去除冗余樣本數據，選擇出最佳分裂屬性并逐步地建立未修剪的決策樹Tr。

2) for (確定Tr中的每個節點Ni和分割路徑Path)。

3) if (該條Path終止)，將該子集合Ue確定為葉節點Ne并將其合理的分類。

4) else 將子集合Us≠?根據Path繼續劃分，建立決策子樹Tr-s并為每個節點添加標記Li(i≤n))。

5) for (遍歷每個屬性Ai(Ai∈U))。

6) if (Ai∈U但Ai?Tr)，設初權重值φ=0。

7) else 作為Tr中屬性Ai(i≤n)的最小深度D，初始化權重值φ=1/D。

8) for (分別遍歷U中的類別標記Cj(j≤m)和屬性Ai(φ≠0))。

10) for (遍歷每一個求出的后驗概率P(Cj|Ai))。

11) 訓練集U中比較每一個后驗概率的值，當且僅當P(Cx|Ai)>P(Cj|Ai)(x≠j≤m)，即P(Cx|Ai)為最大后驗概率MAP，選取Cx作為Ai的所屬類別，直到所有的子集合Us分類完畢。

輸出訓練集中所有樣本均正確歸類的分類集合UC，其中映射函數f:Cj→Ai(j≤i≤n)。

2入侵檢測實驗與分析

2.1KDD’99入侵檢測數據集

入侵檢測技術即為一種概率性預測及網絡數據分類技術，將TW-NB分類器運用在該技術中來檢測網絡異常行為及事件數據歸類達到預警功能是合理有效的。

本文實驗使用KDD Cup 1999 (KDD’99)入侵檢測數據集，通過實驗數據來驗證基于TW-NB算法的入侵檢測技術的檢測效率。在KDD’99數據集中，每個樣本表示網絡數據流中類Class的屬性值A:{A1A2,…,An}，每個類Class都被標記著正常Normal或攻擊Attack。這些類在數據集中可被分為{Normal,DOS,U2R,R2L,Probe}五大類，其中四大入侵類又可被細分成22種攻擊類型如表1所示。

表1　KDD’99數據集中的入侵類型

KDD’99數據集是由DARPA98數據集轉化來的，它是對DARPA98數據進一步過濾處理后產生的。由于原始數據集的龐大以及包含過多的冗余和缺失數據，因此KDD’99數據集提供了一個500萬條數據記錄其中的10%的樣本數據作為子集來方便數據的實驗。通過實驗數據的需求，本文選取了這個10% KDD’99數據子集中的樣本分別作訓練集Train和測試集Test數據如表2所示，同時數據集中為每次的網絡連接使用的41種輸入屬性特征如表3所示。

表2　KDD’99數據集中訓練及測試樣本的數量(10%)

表3　KDD’99數據集中41種屬性

2.2影響因素的分析與預處理

在實際的網絡環境中，海量的網絡訪問數據由于類型和結構的不同會造成普遍的數據冗余以及一定程度的數據缺失，這些現實因素會直接影響到TW-NB算法的分類性能和預測效果。因此，數據的預處理為解決干擾問題對于驗證算法的性能和健壯性是非常必要的。所關注并處理的實際影響因素主要有以下幾項：

(1) 冗余數據

實際環境中數據的冗余現象是必然存在的，它直接影響著數據的質量。因此，增加數據的獨立性和剔除冗余數據是測試大規模數據系統成功的前提條件。

(2) 缺失數據

數據的缺失造成了系統丟失了大量的有用信息，使系統表現出更加顯著的不確定性，包含空值的數據會使分類過程陷入混亂并導致不可靠地輸出。

處理以上影響TW-NB算法的分類預測因素，本文采用基于特征相似度的屬性選擇方法。主要步驟如下：

1) 根據式(6)，在數據集合U中計算與屬性Aj之間的相似度ρij。其中1≤j≤n，且Aj∈U。

2) 選擇相似度ρij最大的完整屬性Ai(1≤i≤n)作為缺失數據的彌補對象，用于填補數據的完整性。

3) 計算數據集合U中屬性之間的方差值COV(i,j)，選擇方差小的屬性值，方差相同的屬性任選其一，從而剔除了不必要的冗余數據，提高了數據質量。

4) 輸出一個完整的、低冗余度的屬性集合D。

(6)

2.3實驗結果分析

實驗仿真環境采用Windows 7操作系統、2.8 GHz雙核CPU、4 GB DDR3內存以及Weka智能分析環境，實驗數據使用KDD’99入侵檢測數據集中10%訓練及測試樣本數據。根據入侵檢測仿真實驗結果，基于TW-NB算法的入侵檢測技術的檢測效率分析以及改進前后算法性能的比較結果分別如圖1所示。

圖1　改進前后算法的入侵檢測率(DR)比較

從圖1和圖2中的實驗結果可以看出，TW-NB算法在檢測不同入侵數據時較NB算法在DR和FR方面都有了明顯的性能提升，尤其對于DOS攻擊和R2L攻擊在檢測率和誤檢率上分別有大幅度改善。由圖3所示，在設置了閾值(θ=98.5%)的情況下，TW-NB算法對入侵檢測數據集中的攻擊數據的檢測準確度Accuracy的連續值較NB算法有了普遍的提高，整體連續屬性取值均高于閾值θ，最高準確值Am可達99.76%。而NB算法的檢測準確度值趨于或低于閾值，最低取值降到98.12%，遠遠低于閾值。當準確度取值A<θ時，則值A為不期望值。

圖2　改進前后算法的入侵誤檢率(FR)比較

圖3　算法在入侵檢測數據集中的準確度

結合實驗結果與數據分析，本文將TW-NB算法分別與網絡入侵檢測領域中的其他流行的數據挖掘算法(C4.5、SVM、K-means)以及改進的NB算法(HNB、RSNB、AODE)進行檢測性能的比較，比較結果分別如表4和表5所示。

表4　TW-NB算法與相關算法檢測率(DR)的比較

表5　相關算法入侵檢測準確度(Accuracy)的比較

根據表4、表5的數據比較結果，本文的改進算法TW-NB在檢測率(DR)和分類準確度(Accuracy)方面較其他流行的數據挖掘算法以及改進算法均有明顯的提升和改善。從其他實驗結果可分析，TW-NB算法的平均入侵檢測率可達99.49%，平均準確度較其他算法可提升到99.162%，平均錯誤分類率較其他算法可降到0.838%，檢測性能具有比較顯著的改進。

3結語

針對現代網絡環境中復雜多變的網絡入侵行為，本文借鑒樸素貝葉斯理論，提出了改進的NB算法——TW-NB算法，并運用在入侵檢測技術當中，將攻擊數據從海量數據中劃分出來并進行攻擊預測。TW-NB算法通過引入決策歸納法(DTI)，設計權重參數φ以及決策準則來進一步控制樸素貝葉斯(NB)的分類，從而更加提高了NB算法的分類準確度。實驗中，首先運用Weka智能分析環境和KDD’99入侵檢測數據集中的大量數據驗證了算法的可行性，并分析實驗結果得到不同效果的實驗圖和表。在今后的研究工作中，將進一步深入優化并提升TW-NB算法的分類性能。由于該算法對冗余數據復雜度及計算資源狀況較為敏感，因此在下一步的計劃當中，將引入數據預處理的相關方法再度提高TW-NB算法的魯棒性和適用性。

參考文獻

[1] 史志才,夏永祥.高速網絡環境下的入侵檢測技術研究綜述[J].計算機應用研究,2010,27(5):1606-1610.

[2] Yang Li,Li Guo.An active learning based TCM-KNN algorithm for supervised network intrusion detection[J].Computers & Security,2007,26(7):459-467.

[3] Levent Koc,Thomas A Mazzuchi,Shahram Sarkani.A network intrusion detection system based on a Hidden Na?ve Bayes multiclass classifier[J].Expert Systems with Applications,2012,39(18):13492-13500.

[4] 譚愛平,陳浩,吳伯橋.基于SVM的網絡入侵檢測集成學習算法[J].計算機科學,2014,41(2):197-200.

[5] Reda M Elbasiony,Elsayed A Sallam.A hybrid network intrusion detection framework based on random forests and weighted k-means[J].Ain Shams Engineering Journal,2013,4(4):753-762.

[6] Jiang Liangxiao,Zhang H,Cai Zhihua.A novel Bayes model: hidden naive Bayes[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1361-1371.

[7] 李晶輝,張小剛.一種改進隱樸素貝葉斯算法的研究[J].小型微型計算機系統,2013,34(7):1654-1658.

[8] Liangxiao Jiang,Zhihua Cai,Harry Zhang.Not so greedy:Randomly Selected Naive Bayes[J].Expert Systems with Applications,2012,39(12):11022-11028.

[9] M Julia Flores,José A Gámez,Ana M Martínez.Domains of competence of the semi-naive Bayesian network classifiers[J].2014,260(1):120-148.

[10] 王雙成,杜瑞杰,劉穎.連續屬性完全貝葉斯分類器的學習與優化[J].計算機學報,2012,35(10):2129-2138.

[11] 李方,劉瓊蓀.基于改進屬性加權的樸素貝葉斯分類模型[J].計算機工程與應用,2010,46(4):132-141.

[12] 賈嫻,劉培玉,公偉.基于改進屬性加權的樸素貝葉斯入侵取證研究[J].計算機工程與應用,2013,49(7):81-84.

中圖分類號TP311

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.068

收稿日期：2014-06-20。國家自然科學基金項目(51174263)；教育部博士點基金項目(20124116120004)；河南省教育廳科學技術研究重點項目(13A510325)。王輝，副教授，主研領域：計算機網絡及網絡安全，無線傳感器網絡。陳泓予，碩士生。楊姍姍，碩士生。