基于證據推理算法的入侵檢測系統

王伍柒+周立萍

摘要：數據融合算法是入侵檢測系統設計的核心內容，對于“不知道”與”不確定”信息的處理，證據推理算法具有十分突出的特點，已成為數據融合算法的熱點。為了避免焦元爆炸問題，該文采用一種可有效減少證據合成計算量又可確保合成實時性準確性數據融合算法。為了解決分布式系統中主控端與各入侵檢測終端之間的通信問題，引入分布式協同算法，并在此基礎上，設計一種分布式入侵檢測系統。

關鍵詞：數據融合；入侵檢測；證據推理；分布式協同算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2017）28-0032-03

入侵檢測系統是一種積極主動的安全防護機制，不僅能夠防御對來自外網入侵攻擊，還能有效地防止內網的攻擊和機密信息的泄漏，入侵檢測系統有效地提高網絡安全的整體水平，它已經成為網絡信息安全領域的研究熱點。

1 概述

論據推理理論是入侵檢測系統中應用最為廣泛的數據融合算法，已成為一種最適合的不確定推理方法。它不需要任何先驗的概率，直接利用區間信度刻畫證據度量和命題結果，處理“不確定”與“不知道”的信息，約束條件寬松，與經典的概率論、貝葉斯理論有著本質的區別。盡管如此，若入侵檢測技術采用傳統的證據理論進行數據融合計算，在網絡環境各種干擾和噪聲的影響下，系統中攻擊行為、入侵事件與惡意企圖等網絡入侵目標的識別能力急劇下降，漏報率和誤報率增加，因此，需要改進傳統的證據理論，使其適合網絡入侵檢測技術。

2 證據合成算法的研究與改進

在入侵檢測系統中，對于各子系統上報的可疑行為，需要對來自各個多個信息源的數據進行關聯、估計和組合等處理，從而進行識別判斷。證據理論就是用于數據融合的算法之一。

2.1 D-S證據理論

證據推理是由Dempster首先提出的，并由Shafer進一步完善發展起來的，所以又稱作Dempster-Shafer證據理論或D-S證據理論。

D-S證據推理是從經典的集合論的基礎上發展而來的。設Θ為某一的辨別框架非空的集合，且各元素之間滿足互斥條件，其所有的子集構成冪集2Θ。則基本信任指派函數可表達為[BPA：mA→0，1]，其中A為冪集2Θ中任一子集，表示證據支持命題A發生的程度[mA] 。

上式K表示兩個證據體突沖程度的度量，也是描述是否適用證據推理算法的依據。如果K=1，則證據體完全矛盾，D-S融合算法失效；如果K值較小，則證據體是一致的，可以使用歸一化處理。

實踐證明：利用傳統的證據合成規則在合成不同證據時出現的計算復雜度問題屬于NP完全問題，計算復雜度隨識別框架的基數的增加而成指數增加，極大的計算量限制了其應用。

2.2 基于D-S證據理論的算法改進

（1） 相關函數

Dubois和Prade認為證據理論中焦元的基數和焦元的基本概率賦值信息是證據的構成的重要因素，因此，改進算法選擇參與融合的焦元的標準不是焦元的基本概率賦值，而是以證據的平均能量函數作為評判的選擇標準，平均能量函數可包括證據的焦元能量函數和平均能量函數。

（2） 分類規則

如果采用焦元能量函數、證據平均能量函數作為合成過程中焦元的分類規則，則可將焦元分為兩類：

保留焦元（焦元的能量大于或等于證據的平均能量）和拋棄焦元（焦元的能量小于證據的平均能量）。

其中，[Nib，Nip，Ni]分別為證據保留焦元集中的焦元（命題）個數、拋棄焦元集中的焦元個數以及證據i所支持的焦元個數。

焦元分類規則能夠較為精確的區分識別框架Q中所有的證據體須要融合計算的焦元和對組合計算最終拋棄的焦元。即參與組合計算的焦元將精確標出，這樣就大大減小了推理合成的計算量，避免焦元爆炸的現象。

（3） 算法描述

如果被拋棄的焦元中的一些信息如果不參與證據合成計算，那么，可能會使最終決策結果產生偏差，即據證丟失可能影響最終的判決結果。因此，對于拋棄的焦元，需要對其基本概率賦值進行再分配，使拋棄焦元自身攜帶的有用信息得以有效利用，參與到決策結論的判決過程中。這樣，不會因拋棄焦元的有用信息不會損失而使判決結果有較大的偏差。

設[Pk]為[SiP]中一焦元，為與之相關的集合，[BG]為[SiB]中與[Pk]相交不為空的焦元組成的集合；如果[SiB]中與[Pk]相交不為空則可判斷所拋棄的焦元中含有用的信息理論不會影響結果，因此，只需考慮集合[BG]。對拋棄焦元[Dk]的基本概率賦值再次分配時，只要將拋棄焦元的基本概率賦值分配在有嵌套關系或相交的焦元集上。當拋棄焦元與所有保留焦元相交為空時，將其基本概率賦值分配給未知命題Q。

拋棄焦元基本概率賦值重新分配方法如下：

（1） 終端T0即主控中心對于所有的入侵檢測任務，如果有"mi?M，則查詢本體的攻擊特征入侵規則庫，獲悉該任務多個原子攻擊序列組成，A={a1，a2，…，an}，此時，主控中心向所有入侵檢測終端Tn廣播消息序列，分發入侵的檢測結果。

（2） 收到主控中心訂閱消息后，各終遄Tn向主控中心T0回復一條確認消息。

（3） 各入侵檢測終端Tn如果檢測到了入侵行為或惡意攻擊時，主動向主控中心T0發送入侵告警消息。

（4） 主控中心T0對收到來自各個入侵檢測終端的原子入侵消息（包括T0自身匯報的和從其他T匯報的）進行關聯分析，建立檢測模型，通過融合計算，判斷是否存在入侵企圖或存在的攻擊等威脅，并向網絡管理者發出報警或主動切斷網絡的連接。

各入侵檢測終端Tn所承擔的分析任務是發現網段內的協同攻擊，其分析依據是來自各自檢測信息以及從主控中心訂閱的原子入侵報警（協同其他入侵檢測終端或T0）。主控中心T0對于收集到的終端Tn上報的信息集合，進行關聯分析，試圖找出各個入侵者所有可能的關聯方式，即所有可能的入侵者組合的集合。endprint

4 改進算法的實現

入侵檢測系統將向其他終端Tn訂閱入侵消息的終端T0定義為主控端，定義T0自身檢測信息以及其他Tn的原子入侵報警信息為證據。

參與主控端T0融合的證據來源于T0自身及其他Tn，主控中心T0和其他入侵檢測終端Tn具有局部檢測分析的功能，獨立性很強，需要對對局部檢測分析報告事件或存在的攻擊可能行為進行明確的定義。各終端上報T0的事件格式需要適用入侵檢測分析環境的不同、檢測的技術方式的差異。因而需要對可疑事件的報告格式進行定義。定義格式如表1所示。

只要各終端T獲取可疑事件相應的局部決策表，利用分布式協同算法，上報主控端T0由主控端最終融合計算，得出檢測結論。

設各終端上報的可疑事件i的證據體為[Aj，miAjj=1，2，…，N]，運用改進算法進行融合的流程圖如圖2所示。

改進的證據推理算法步驟如下：

①對識別框架中的焦元安照保留下焦元和拋棄焦元進行分類，并計算焦元能量函數、證據平均能量函數；

②計算拋棄焦元的基本概率賦值，根據基本概率值實現拋棄焦元再分配，減少因拋棄焦元因攜帶有用信息而對融合結果產生的偏差；

③根據證據合成規則，融合判斷是否有入侵事件，并獲得最終融合結果。

5 小結

本文重點對D-S證據理論進行了研究，采用基于D-S證據理論的算法改進，引入分布式協同算法來解決各終端之間的協同問題，設計一種分布式入侵檢測系統。通過實踐證明改進的證據推理算法能夠有效地減少數據融合的計算量，同時還能提高系統的融合性能，達到設計的要求。

參考文獻：

[1] 靳留乾.基于確信度證據推理的不確定性多屬性決策方法研究 [D]. 西南交通大學， 2016.6.

[2] 包甜甜，謝新連，魏照坤.新的證據沖突度量方法[J]. 控制理論與應用2017，34（01）：41-48.

[3] 呂嘉祥，李益發.基于多代理技術可自檢的分布式入侵檢測系統模型[J].微計算機信息，2005，21（11）：30-32.

[4] 楊海松，李津生，洪佩琳.分布開放式的入侵檢測與響應架構—IDRA[J].計算機學報，2003，26（9）：1177-1182.

[5] 葉清，吳曉平，翟定軍，等. 基于證據推理的多agent分布式入侵檢測系統模型[J].計算機應用研究，2009，26（8）：3063-3066.endprint