入侵檢測系統，就是按照一定的安全策略對網絡、系統的運行狀況進行監視，盡可能地發現各種攻擊企圖、行為或者結果，以保證網絡系統資源的機密性、完整性和可用性。入侵檢測系統根據分析對象的不同，可以分為基于主機的和基于網絡數據包的入侵檢測系統。模式匹配方法[1-2] 入侵檢測系統中應用廣泛，該方法根據預先制定的模式檢測攻擊，可以有效地發現已知模式的攻擊，但是不能發現未知模式的攻擊。
　數據挖掘，就是從大量數據中獲取有效、潛在、有用、新穎的模式的非平凡過程。將數據挖掘方法應用在入侵檢測系統中[3],可以有效地挖掘出新的模式，發現新的攻擊。在基于主機的入侵檢測系統中已有很多研究，也取得了不錯的成果。常用的方法有支持向量機[4] 、隱馬爾科夫模型[5]、KNN[6]等。
　基于網絡數據包的入侵檢測系統是將網絡數據包作為分析的對象，有數據量大、數據變換快等特點，而傳統的數據挖掘方法在應用中往往出現運算時間復雜度過高,不能在有限時間內處理完大量數據包的難題。
　從IEEE802.11協議[7] 中可以發現：在不同的階段，網絡數據包的類型是完全不同的，如認證階段只有認證報文，認證階段結束后進入連接階段，只會出現連接報文，在認證階段后的任何階段都可以發生斷開認證階段等,不同的階段是相繼發生但是階段間是相互獨立的。傳統的數據挖掘方法會將不同階段的數據包統一分析，不僅會產生極大且無謂的計算量，而且不能體現出階段性的特點。本文提出了一種分階段K鄰居數據挖掘方法，可以有效地解決上述問題。

    該函數與節點本身的屬性和節點的內部鄰居集有關，而且不同屬性的內部鄰居集對節點的內部評價值的影響力不一樣。
    (2) 階段評價函數:評價節點和該節點階段鄰居特征的函數。
　
　該函數與節點的內部評價值和節點的階段鄰居有關，而且不同的階段鄰居對節點的外部評價值的影響力不一樣。
2 KNS算法
　應用KNS方法的前提：對象可分為一定的階段，階段之間相對獨立并且有序，同一階段中不同節點的內部行為和階段行為應該相似。
　在KNS算法開始之前，需要對節點的各個屬性進行篩選，選擇能夠將數據集分割成n個連續的階段的屬性作為階段屬性，如果有幾個屬性都可以作為階段屬性，則選擇其中分割的最均勻的屬性作為階段屬性。
　KNS方法可分為學習算法和測試算法兩部分。
    
    首先通過對樣本數據集的學習，調整內部影響權值w[k]和階段影響權值sc[n,n]。調整算法可以用自適應濾波LMS(Least-Mean-Square)學習算法等，由此得到階段對照評價集U[n]。然后輸入待測數據集，計算每個節點s的內部評價值W(s)并最終得到階段評價值Sc(s)。將Sc(s)與該階段的對照評價集U[j]比較，并將Sc(s)偏離U[j]的程度作為判斷結果的依據輸出。
　KNS學習算法是先通過樣本數據集中的每個節點找到內部鄰居集和階段鄰居集，然后計算所有節點的內部評價值W和階段評價值Sc并將Sc加入到評分集U[j]中,通過調整w[k]和sc[n,n]的值，逐步縮小U[j]的范圍，最終輸出U[j]作為KNS測試算法的對照評價集。
   (2)KNS測試算法
   Input w[k], sc[n][n]; U[n];
   Input  target data set S；
   foreach s in S
           Switch(s(y))
                  Set s in section Mj ;
           searchNeighbor(s, Mj);
           for Mk before and after Mj
                  searchNeighbor(s, Mk);
        compute W(s) Sc(s)
        get distance(Sc(s) U[j] );
        answer(s)=tooFar(Sc(s),U[j]);
        output answer;
    KNS測試算法比學習算法簡單很多，只需在每個節點進入時，設置為相應的階段并為它找到內部鄰居和階段鄰居，然后計算出內部評價值W和階段評價值Sc，最后將Sc與該階段對照評價集U[j]比較，輸出比較結果。
   綜上所述，KNS方法整個流程如圖1所示。

3 基于WLAN網絡數據包的入侵檢測
    無線局域網(WLAN)使用過程如圖2所示。

    每個終端(STA)在連接并使用WLAN的過程都可以按照圖2流程分為5個階段，不同階段中所涉及的數據包的類型也是完全不同的，并且每個階段內的數據包類型都是有限的，如網絡發現階段數據包的類型有Beacon、Probe Request和Probe Response三種，認證階段只有Authentication一種等。這是滿足分階段K鄰居方法應用的前提。
    在實驗中，每個獨立的包作為一個節點，數據包里的各個項的值作為該節點的屬性。將上述階段再次按照不同的數據包類型分成更小的階段，每個階段中只包含一種類型的數據包，同時將源地址和目的地址作為判斷是否階段鄰居的屬性依據。同類數據包中的其他屬性作為該階段的內部屬性。
    實驗中，先收集一定量的安全環境下的數據包，作為樣本集合進行KNS學習，然后再將結果用于入侵檢測，并將階段評價函數的偏離程度作為判斷是否有入侵的依據。
    實驗使用的評價函數有：
 
4 實驗結果及分析
　在實驗室環境下進行攻擊和檢測。實驗分別用KNS方法和HMM方法進行。
    (1) KNS方法
    KNS方法檢測結果如表1所示。

    由表1可以發現，KNS方法可以在較高檢測率的情況下保持較低的誤報率。但是對于Probe Request 類型的攻擊，由于STA Probe的比較沒有規律，STA可以在任何時候發出Probe Request并可以持續任意長的時間,然后在任何時間結束Probe,即開始認證或離開WLAN(Probe Response也是類似)。對于這種類型的攻擊，階段K方法盡管可以有著很高的檢測率,但是也有著較高的誤報率。而對于Beacon Flood、Spoof Authentication和Spoof Association這幾種攻擊，不但有很高的檢測率同時也有較低的誤報率。
    (2) HMM方法
    實驗采用滑動窗口HMM模型，將WLAN數據包MAC頭部的二進制碼作為分析對象，取窗口大小為7，得到結果如表2所示。

    對比表1和表2可以發現，對于不同的攻擊類型，兩種方法的誤報率有高有低。但是總體而言，KNS方法的檢測率基本都高于HMM方法
    (3) 運算效率
    采用KNS方法和HMM方法處理2 000個~20 000個數據包所用的時間如圖3所示。由圖可知，KNS方法處理包的平均速度是HMM方法的2.5倍，說明KNS方法有著快速處理大量實時網絡數據包的能力。

    本文提出了一種可以體現對象階段性特點的數據挖掘KNS模型。該方法將待測對象按照階段不同分為若干階段，然后分別對階段內部鄰居和階段鄰居的相關屬性進行統計挖掘。如果待測對象滿足兩個條件：(1)可分為互相獨立且有序的階段； (2)同一階段中不同節點的內部行為和階段行為是相似的,則可以應用該模型。此外，還實驗了KNS方法在基于WLAN網絡數據包的入侵檢測系統中的應用，并將結果與HMM方法的結果進行了對比，可以發現在檢測率和誤報率相當的情況下，KNS方法運算效率高,可以在實時檢測中很好地應用。
    在研究過程中發現，目前的KNS方法還存在許多不足，如階段內部評價函數以及階段評價函數的設定還有有待改進，當前的函數略顯復雜，后續工作只需要找到可以反映階段特點的更簡單的函數，就可以進一步改進KNS算法的計算速度。
參考文獻
[1]    THOMPSON H H, WHITTAKER J,ANDREWS A M. Intrusion detection: perspectives on the insider threat[C].Computer Fraud & Security, 2004:13-15.
[2]    HAN S J, CHO S B. Detecting intrusion with rule-based integration of multiple models[J]. Computer & Security, 2003, 22:613-623.
[3]    PIETRASZEK T, TANNER A. Data mining and machine learning-toward reducing false positives in intrusion detection[J]. Information Security Technical Report,2005,10:169-183.
[4]     ZHANG Z, SHEN H. Application of online-training SVMs     for real-time intrusion detection with different considerations[J]. Computer Communications, 2005, 28:1428-1442.
[5]    QIAO Y, XIN X. Anomaly intrusion detection method based on HMM[J]. Electonics Letters,2002,38(13):663-664.
[6]    LIAO Y, VEMURI V R. Use of K-nearest neighbor classifier for intrusion detection[J]. Computer & Security, 2002, 21:439-448.
[7]    IEEE802.11 Working Group.IEEE standard for information     technology—telecommunications and information exchange between systems—local and metropolitan area networks—specific requirements Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications.2007[EB/OL]. http://standards.ieee.org/getieee802/download/802.11-2007.pdf