以LOF為基礎的叢集分析及演進最佳化之不當使用和異常行為入侵偵測系統

Evolutionary Optimization on Misuse and Anomaly IDS Using LOF-based Clustering

陳俊豪(Chun-Hao Chen)

指導教授 ： 李秀惠

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.01236

摘要

隨著網際網路的廣泛應用，各類型的網路攻擊技術也相繼出現，對許多電子化的企業、機關的威脅也愈來愈大。舊有的被動防禦措施，如：防火牆、密碼保護，在攻擊技術的精進下便顯得不足。因此入侵偵測系統這個主動偵測攻擊的系統便發展了起來。以資料探勘來發展入侵偵測系統自動且有效，因而取代了傳統的特徵比對的入侵偵測系統。入侵偵測系統可分為不當行為偵測和異常偵測。不當行為偵測是使用已知攻擊的特徵來偵測攻擊，而異常偵測則建立正常使用行為模型來判斷入侵。

本論文提出了一個可同時使用於不當行為偵測和異常偵測上的入侵偵測系統。我們將孤立點偵測演算法LOF擴充為一個叢集演算法。LOF能夠偵測出一些其它演算法無法找出的孤立點。孤立點偵測和叢集分析有許多概念是相通的，但LOF不能明確的形成叢集，我們對此修改並將之應用於入侵偵測。叢集的部分可用來建立訓練資料的資訊，用來判斷測試資料與訓練資料的關聯；而孤立點偵測的特性則可用來偵測違反訓練資料分佈的未知攻擊。除此之外，我們使用基因演算法來賦予每個資料屬性一個重要性（權重），並根據不同種類攻擊的特性來產生數組權重，以此來提高入侵偵測系統的準確度。在論文最後，使用KDD Cup 1999的資料來評估我們的系統，其結果在不當行為偵測和異常偵測上都相當不錯。

關鍵字

入侵偵測系統 ； 叢集分析 ； 孤立點偵測 ； 基因演算法 ； 資料探勘

並列摘要

With wide application of internet, various attack techniques have been developed and threaten the e-society. Old passive safeguard, e.g. firewall, and password, is insufficient when the attack techniques progress continuously. Hence, intrusion detection system (IDS) is developed for active protection. Using data mining technique to develop IDS is automatic and effective; therefore it can replace traditional signature-based IDS. IDS can be classified into misuse detection and anomaly detection. Misuse detection uses those patterns of known attacks to match and identify intrusions. Anomaly detection constructs normal behavior profiles to detect attacks.

This thesis proposes an IDS both for misuse detection and anomaly detection. We extend an excellent outlier detection algorithm LOF to a clustering algorithm. LOF can detect some outliers that other algorithms can not detect. Though there are several common concepts between outlier detection and clustering, the original LOF algorithm can not explicitly form clusters. We make extension to it and apply to IDS. The part of clustering can build the information of training data and find the association between training data and testing data; and the part of outlier detection can detect the unseen attacks if the data deviate from the distribution of training data. Besides, a genetic algorithm is used to assign each feature of data an importance (weight), and generate several sets of weights in terms of characteristics of each attack type. This is adopted to raise the accuracy of IDS. In experiments, the KDD Cup 1999 data is used to evaluate our system. We get good results both for misuse detection and anomaly detection.

並列關鍵字

IDS ； clustering ； outlier detection ； GA ； data mining

參考文獻

[CANCS 2005] W. Chimphlee, A. H. Abdullah, M. Noor Md Sap, S. Chimphlee, and S. Srinoy, “Integrating Genetic Algorithms and Fuzzy c-Means for Anomaly Detection,” IEEE Annual INDICON, 2005, Page(s): 575-579.

[GGB 2003] Y. Guan, A. A. Ghorbani, and N. Belacel, “Y-means: A Clustering Method for Intrusion Detection,” IEEE CCECE Canadian Conference on Electrical and Computer Engineering, May 2003, Vol. 2, Page(s): 1083-1086.

[IKP 1995] K. Ilgun, R. A. Kemmerer, and P. A. Porras. “State transition analysis: A rule-based intrusion detection approach,” IEEE Transactions on Software Engineering, March 1995, Page(s): 181–199.

[KD 1991] J. D. Kelly, and L. Davis, “A Hybrid Genetic Algorithm for Classification,” International Joint Conference on Artificial Intelligence, Aug 1991.

[LBM 2005] C. T. Lu, A. P. Boedihardjo, and P. Manalwar, “Exploiting Efficient Data Mining Techniques to Enhance Intrusion Detection Systems,” IEEE International Conference on Information Reuse and Integration, Aug 2005, Page(s): 512-517.