K-近鄰算法在入侵檢測系統中的應用研究

張昊

（沈陽理工大學信息科學與工程學院，遼寧 沈陽 100159）

0 引言

計算機網絡已經深入到工業、商業和人類生活的各個領域，隨著世界向云計算，移動應用和無線網絡發展，網絡安全比以往任何時候都更加重要。網絡中的攻擊行為種類繁多，網絡攻擊事件也屢屢發生。計算機安全協會的一份調查報告發現，45.6%的受訪者表示他們在過去一年中至少遭受過一次有針對性的攻擊，數據泄露通常也會導致公司損失數十億美元資產[1]。因此，構建可靠的網絡對IT管理員來說是一項非常重要的任務。同時，信息技術的快速發展也為建立可靠網絡帶來了若干挑戰，建立一個易于實現的網絡安全體系已經成為一項非常艱巨的任務。針對上述問題，入侵檢測系統（IDS）應運而生，它是指被設計用來發掘那些對網絡安全可能產生威脅的行為的軟件或硬件系統，入侵檢測系統不僅易于實現并且切實可靠，是構建網絡安全體系的重要措施。入侵檢測系統的主要任務是通過檢測網絡系統或主機設備上的惡意攻擊來保護計算機系統或計算機網絡，監視計算機系統或網絡中發生的事件并挖掘他們入侵的跡象[2]。IDS能夠對網絡安全事件進行發現、記載并產生安全報告，一般放在內聯交換機的生成端口或集線器上，用來取代交換機。

1 常見的入侵檢測系統

常見的入侵檢測系統主要有：基于主機的IDS（HIDS）、基于網絡的IDS（NIDS）以及基于簽名的IDS，其具體介紹如下：

基于主機的IDS是一種通常在計算機、節點或設備中運行的IDS，現如今已經開發了許多可用于監視網絡的HIDS變種。它的主要功能是內部監控，首先，它監視和分析計算機、節點或設備的內部[3]。然后，HIDS確定系統是否已被入侵并警告管理員。例如，它可以檢測到一個流氓程序，以可疑的方式訪問系統資源，或者發現程序以有害的方式修改注冊表。

基于網絡的IDS與HIDS的不同之處在于它通常沿著LAN線放置。它試圖通過分析遍歷到多個主機的線路的流量來發現對LAN的未授權和惡意訪問。目前已經有許多用于檢測惡意流量的算法，它們通常讀取入站和出站數據包并搜索任何可疑模式[4]。NIDS生成的任何警報都允許它通知管理員或采取主動操作，例如阻止源IP地址。NIDS最常見的位置是使用網絡分路器直接連接到交換機跨接端口，并且在內部連接[5]。

在基于簽名的IDS中，IDS查找數據包并將其與預定義的規則或模式（稱為數據庫中定義的簽名）進行比較[6]。該技術的主要優點是簡單有效地處理審計數據?；诤灻姆椒ǖ膬烖c是具有低得多的誤報率。但是基于簽名的檢測這種方法對未知攻擊是無效，隨著每小時新攻擊和惡意活動的更新速度的加快，基于簽名的IDS僅能檢測到與其簽名數據庫和規則集的貼近度一樣的攻擊方式。

2 KNN算法在入侵檢測中的適用性

面對肆意發生的網絡攻擊，入侵檢測系統需要通過對網絡攻擊行為有更高檢測率的檢測算法來維護網絡安全。在本節首先介紹樸素貝葉斯、C4.5決策樹和KNN算法的原理，然后比較分析KNN算法相比于樸素貝葉斯和C4.5決策樹算法在入侵檢測系統中有更好的適用性。

2.1 樸素貝葉斯

根據貝葉斯定理有，給定樣本特征B,樣本屬于類別A的概率為：

樸素貝葉斯是基于貝葉斯定理和特征條件獨立假設的分類方法，則有：

在上式中，分母對于所有類別來說都相等，因此只需將分子最大化，所以有：

對于一個新的測試樣本X,對各個類別計算P( X | yi) P( yi)概率，如果某個類標yi使該概率最大化，則該測試樣本的類標則為yi[7]。

2.2 C4.5決策樹算法

C4.5決策樹是一種用于分類和回歸的有監督學習方法，C4.5決策樹的本質是構建一個樹，其中每個分支顯示多個可能性之間的概率，每個葉子用來顯示決策[8]。C4.5決策樹算法收集信息并將其用于決策，在C4.5決策樹中，每個類別根據不同的屬性劃分數據，目標是以最少的決策數量實現完美的分類。

2.3 K-近鄰算法（KNN）

K近鄰算法(k-nearest neighbor, KNN)是一種基于實例的學習方法，也可以稱為懶惰學習，它是用于分類或回歸的非參數方法[9]。KNN的分類原理為對于訓練集中待分類的對象，每個對象的分類由最近的K個數據投票確定，即對象被分配給最近的K個對象中最多的類，并由訓練集中K個最近鄰居的多數標簽表示。每個對象的特征由位置矢量描述，并且特征之間的距離由歐幾里德或曼哈頓距離測量。

2.4 比較分析

從上述對算法原理的分析我們可以得出，樸素貝葉斯算法對輸入數據的要求較為嚴格，若某個屬性值在訓練集中沒有與某個類同時出現過，則直接基于條件概率與先驗概率的計算公式進行計算，將出現不論其它屬性如何，該類的判別概率都為0的問題，導致分類質量大大降低，這在我們入侵檢測系統中將會產生嚴重的漏判問題，導致大部分網絡攻擊行為無法檢測出來，給計算機網絡安全帶來嚴重問題。而C4.5決策樹算法相比于樸素貝葉斯來說，雖然在輸入數據要求上并不嚴格，可以處理具有不相關特征的數據，但同時由于其分類原理是選擇最佳特征進行分類，很容易造成過度匹配的問題，在入侵檢測系統中往往會產生對某種攻擊行為檢測率較高，而對其他攻擊行為檢測率很低的問題，對于入侵檢測系統來說，這都不是我們希望看到的。

入侵檢測系統需要的是算法易于實現，對數據結構并不敏感，且檢測精度較高的檢測技術。KNN算法是基于不同數據特征值之間的距離進行分類的，采用計算不同數據之間的歐幾里德或曼哈頓距離來判別待測數據的類別，通過這種精確的數學計算，在入侵檢測系統中，會對網絡攻擊行為產生較好的檢測效果。

3 實驗結果分析

為了分析上述入侵檢測技術的性能，本節采用應用廣泛的樸素貝葉斯、KNN和C4.5決策樹算法在KDD Cup99 數據集[10]上進行仿真實驗。并給出評價指標準確率和召回率。準確率指正確檢測到入侵記錄數與記錄總數的比例，召回率指正確檢測到入侵記錄數與入侵記錄總數的比例。

表1給出了樸素貝葉斯、K-NN和C4.5決策樹檢測算法對攻擊行為檢測的準確率和召回率。

表1 不同算法對攻擊行為的檢測效果Tab.1 Detection effect of different algorithms on attack behavior

圖1給出了樸素貝葉斯、KNN和C4.5決策樹檢測算法對攻擊行為檢測準確率和召回率的柱狀圖。

圖1 不同算法對攻擊行為的檢測效果Fig.1 Detection effect of different algorithms on attack behavior

由上述實驗結果可以看到，樸素貝葉斯和C4.5決策樹檢測算法對網絡攻擊行為檢測都有一定的效果，但KNN算法的檢測效果最好，樸素貝葉斯檢測算法的準確率和召回率明顯低于K-NN和C4.5決策樹檢測算法，檢測效果較差。而KNN和C4.5決策樹檢測算法雖然在準確率上相差不多，但KNN的召回率要明顯高于C4.5決策樹檢測算法，說明KNN相比C4.5決策樹檢測算法對網絡中的攻擊行為有更好的檢測效果。由此可見，KNN算法相比于樸素貝葉斯和C4.5決策樹檢測算法在入侵檢測系統中有更好的檢測效果，非常適合應用到入侵檢測系統當中。

4 結論

本文介紹了IDS在網絡安全的重要性，以及不同類型的入侵檢測系統、方法和技術。每種技術和IDS都有其優越性和局限性，因此在選擇最佳方法時應注意。本文通過算法原理和在KDD Cup99數據集上的實驗分析發現，樸素貝葉斯、K-NN和C4.5決策樹檢測算法都可以用于入侵檢測系統中對網絡攻擊行為的檢測，但K-NN算法在入侵檢測系統中有更好的檢測效果，非常適合應用于入侵檢測系統對網絡攻擊行為的檢測。在今后會將研究重點放在常見的入侵檢測模型上，同時也會對KNN算法的計算復雜度進行進一步的研究。