臺灣博碩士論文加值系統

本篇論文提出模型化的混合網路入侵偵測系統，結合隨便森林演算法與KNN演算法。使用隨機森林在第一個階段的特徵偵測，KNN在第二階段異常偵測。透過結合不同的基於分類與基於群聚訓練方式，使得系統偵測攻擊的偵測率能最大化，且使誤報比率減到最小。
我們在KDD99數據集上進行我們的實驗。結果顯示，結合隨便森林演算法與KNN演算法的偵測模型，提供一個更穩定、更可靠的整體偵測能力。

Network malicious attacks are becoming widespread and dangerous. Furthermore, computer attacks are increasing and can easily cause amount of dollar damage to an organization.
This paper presents a hybrid approach of modeling intrusion detection system. Random Forests and K-nearest neighbor are combined as a hierarchical hybrid intrusion detection system model. The hybrid intrusion detection model used the random forests algorithm which has a superior performance in large dataset, applied in the first signature detection. And k-nearest neighbor algorithm is used in the second anomalous detection. By combining individual classification and clustering based data mining approach to maximize detection accuracy and minimize false alarm rate.
We conduct our experiment over the KDD’99 dataset. The results show that proposed approach can improve the detection performance of the intrusion detection, where only signature detection or anomaly detection approach used.

1. INTRODUCTION 1
1.1. Background 1
1.2. Motivation 3
1.3. Research Problem And Objective 5
1.4. Research Contribution 6
1.5. Thesis Organization 6
1.6. Research Process 7
2. LITERATURE REVIEW 8
2.1. Overview Of Intrusion Detection Systems 8
2.2. Data mining Approach 10
2.2.1 Classification-based Intrusion Detection 12
2.2.2 Clustering and Outlier Detection 16
2.3. Hybrid intrusion detection system 17
2.4. Random Forests 21
3. PROPOSED SYSTEM ARCHITECTURE 22
3.1. Random Forests 25
3.2. Signature Detection 29
3.3. Anomaly detection 30
4. EXPERIMENT AND PERFORMANCE EVALUATION 33
4.1. Experiment Process and Design 33
4.2. Intrusion Dataset 35
4.3. Preprocess of the Data Sets 37
4.3.1 Number of the Experiment Using Dataset 37
4.3.2 Feature Selection 38
4.3.3 Comparison Metrics 41
4.4. Experiment Methodology 42
4.4.1 Random Forests 42
4.4.2 Decision Tree 45
4.4.3 Support Vector Machine (SVM ,degree=3) 46
4.4.4 KNN (K=2) 47
4.4.5 Hybrid Random Forests-KNN 48
4.5. Experiment Analysis 49
5. CONCLUSION AND FUTURE WORK 52
5.1. Implication and Conclusion 52
5.2. Limitation and Future Work 53
APPENDIX 55
REFERENCES 57

[1]E. Byres and N. Sheble, "Making cyber security work in the refinery," in InTech. vol. 54, Oct. 2007, pp. 50-54.
[2]D. Wills, "Computer Crime," in postnote, Oct. 2006.
[3]M. Roesch, "Snort - Lightweight Intrusion Detection for Networks," in Proceedings of the 1999 USENIX LISA Systems Administration Seattle, Washington, USA, 1999, pp. 229-238.
[4]V. Paxson, "Bro: a system for detecting network intruders in real-time," in Proceedings of the 7th conference on USENIX Security Symposium, San Antonio, Texas, 1998.
[5]G. Vigna, W. Robertson, and D. Balzarotti, "Testing network-based intrusion detection signatures using mutant exploits," in Computer and Communications Security Washington DC, USA 2004, pp. 21 - 30
[6]A. Patcha and J. M. Park, "An overview of anomaly detection techniques: Existing solutions and latest technological trends," Computer Networks, vol. 51, Aug. 22 2007 pp. 3448-3470.
[7]H. e. D. Elvis Tombini, L. M´e, and M. Ducass´e, "A Serial Combination of Anomaly and Misuse IDSes Applied to HTTP Traffic," in Proceedings of the 20th Annual Computer Security Applications Conference, Tucson, AZ ,USA, 2004, pp. 428 - 437
[8]J. Zhang and M. Zulkernine, "A hybrid network intrusion detection technique using random forests," in The First International Conference on Availability, Reliability and Security, 2006 (ARES''06) Austria: IEEE, 2006.
[9]T. Shon and J. Moon, "A hybrid machine learning approach to network anomaly detection," Information Sciences, vol. 177, Sep 15 2007, pp. 3799-3821.
[10]S. Peddabachigari, A. Abraham, C. Grosan, and J. Thomas, "Modeling intrusion detection system using hybrid intelligent systems," Journal of Network and Computer Applications, vol. 30, Jan. 2007, pp. 114-132.
[11]J. Allen, A. Christie, W. Fithen, J. McHugh, J. Pickel, and E. Stoner, "state of the practice of intrusion detection technologies," Software Engineering Institute,Carnegie Mellon University, Pittsburgh, PA, TECHNICAL REPORT CMU/SEI-99-TR-028, Jan. 2000.
[12]R. R. Kompella, S. Singh, and G. Varghese, "On scalable attack detection in the network," IEEE-Acm Transactions on Networking, vol. 15, Feb 2007, pp. 14-25.
[13]C. Kruegel, F. Valeur, G. Vigna, and R. Kemmerer, "Stateful intrusion detection for high-speed network''s," in Proceedings 2002 IEEE Symposium on Security and Privacy, 2002, pp. 285 - 293
[14]S. Chebrolu, A. Abraham, and J. P. Thomas, "Feature deduction and ensemble design of intrusion detection systems," Computers & Security, vol. 24, Jun. 2005, pp. 295-307.
[15]D. E. Denning, "An Intrusion-Detection Model," IEEE Transactions on Software Engineering, vol. 13, Feb. 1987, pp. 222-232.
[16]S. Axelsson, "Intrusion Detection Systems: A Survey and Taxonomy," Department of Computer Engineering Chalmers University of Technology G¨oteborg, Sweden 14 Mar. 2000.
[17]N. Ye, S. M. Emran, Q. Chen, and S. Vilbert, "Multivariate statistical analysis of audit trails for host-based intrusion detection," IEEE Transactions on Computers, vol. 51, pp. 810-820, Jul 2002.
[18]S. Staniford, J. A. Hoagland, and J. M. McAlerney, "Practical automated detection of stealthy portscans " Journal of Computer Security, vol. 10, July 2002, pp. 105-136.
[19]S. Kumar and E. Spafford, "A Pattern Matching Model for Misuse Intrusion Detection," in Proceedings of the 17th National Computer Security Washington,D.C, 1994, pp. 11-21.
[20]K. Ilgun, R. A. Kemmerer, and P. A. Porras, "State Transition Analysis - a Rule-Based Intrusion Detection Approach," IEEE Transactions on Software Engineering, vol. 21, pp. 181-199, Mar. 1995.
[21]D. Barbard, J. Couto, S. Jajodia, and N. Wu, "ADAM : A Tested for Exploring the Use of Data Mining in Intrusion Detection," ACM SIGMOD Record, vol. 30, 2001, pp. 15-24.
[22]W. Lee and S. J. Stolfo, "Data Mining Approaches for Intrusion Detection," in IEEE Symposium on Security and Privacy, Oakland, California, May 1999, pp. 120-132.
[23]W. Lee and S. J. Stolfo, "A framework for constructing features and models for intrusion detection systems," ACM Transactions on Information and System Security (TISSEC), vol. 3, Nov. 2000, pp. 227-261.
[24]W. Lee, S. J. Stolfo, and K. W. Mok, "A data mining framework for building intrusion detection models" in IEEE Symposium on Security and Privacy, Oakland, CA, 1999, pp. 120-132.
[25]S. Kumar and S. Eugene H, "An application of pattern matching in intrusion detection " The COAST Project, Department of Computer Sciences, Purdue University, West Lafayette, IN, USA Technical Report CSD-TR-94-013, June 17 1994.
[26]S. Kumar, "Classification and Detection of Computer Intrusions." Ph D. thesis, Department of Computer Science, Purdue University, August 1995.
[27]A. Patcha and J. M. Park, "Network anomaly detection with incomplete audit data," Computer Networks, vol. 51, Sep. 12 2007, pp. 3935-3955.
[28]M. Thottan and C. Ji, "Anomaly detection in IP networks," IEEE Transactions on Signal Processing, vol. 51, Aug. 2003, pp. 2191-2204.
[29]D. MUTZ, F. VALEUR, and G. VIGNA, "Anomalous System Call Detection," ACM Transactions on Information and System Security (TISSEC), vol. 9, Feb. 2006, pp. 61-93.
[30]N. Ye, Y. B. Zhang, and C. M. Borror, "Robustness of the Markov-chain model for cyber-attack detection," IEEE Transactions on Reliability, vol. 53, Mar. 2004, pp. 116-123.
[31]F. Esponda, S. Forrest, and P. Helman, "A formal framework for positive and negative detection schemes," IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics, vol. 34, Feb 2004, pp. 357-373.
[32]I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second ed.: Academic Press 2005.
[33]W. W. Cohen, "Fast effective rule induction," in Machine Learning: Proceedings of the 12th International Conference, Tahoe City, CA, 1995, pp. 115-123.
[34]J. R. QUINLAN, Programs for Machine Learning Los Altos,CA: Morgan Kaufmann, 1993.
[35]S. M. Bridges and R. B. Vaughn, "Fuzzy data mining and genetic algorithms applied to intrusion detection " in Proceedings of the 23rd National Information Systems Security Conference, Baltimore, MD, Oct. 2000.
[36]S. M. Bridges and R. B. Vaughn, "Fuzzy data mining and genetic algorithms applied to intrusion detection " in Proceedings of the 23rd National Information Systems Security Conference, Baltimore, MD, 2000.
[37]J. E. Dickerson and J. A. Dickerson, "Fuzzy network profiling for intrusion detection," in Proceeding of the 19th International Conference of the North AmericanFuzzy Information Processing Society, ( NAFIPS) Atlanta, GA, USA, 2000, pp. 301-306.
[38]M. M. PILLAI, J. H. P. ELOFF, and H. S. VENTER, "An approach to implement a network intrusion detection system using genetic algorithms," in Proceedings of the 2004 annual research conference of the South African institute of computer scientists and information technologists on IT research in developing countries Stellenbosch, Western Cape, South Africa 2004, pp. 221-228.
[39]T. Shon, X. Kovah, and J. Moon, "Applying genetic algorithm for classifying anomalous TCP/IP packets," Neurocomputing, vol. 69, Oct. 2006 pp. 2429-2433.
[40]Z. Bankovic, D. Stepanovic, S. Bojanic, and O. Nieto-Taladriz, "Improving network security using genetic algorithm approach," Computers & Electrical Engineering, vol. 33, Sep-Nov 2007, pp. 438-451.
[41]C. H. Tsang, S. Kwong, and H. L. Wang, "Genetic-fuzzy rule mining approach and evaluation of feature selection techniques for anomaly intrusion detection," Pattern Recognition, vol. 40, Sep. 2007, pp. 2373-2391.
[42]M. Ramadas, S. Ostermann, and B. Tjaden, "Detecting Anomalous Network Traffic with Self-organizing Maps " in Proceedingsof the 6th International Synposium on Recent Advances in Intrusion Detection, RAID 2003, , Pittsburgh, PA, USA, Sep. 2003, pp. 36-54.
[43]S. Chavan, K. Shah, N. Dave, and S. Mukherjee, "Adaptive Neuro-Fuzzy Intrusion Detection Systems," in Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC’04), USA, 2004, pp. 70-74.
[44]Sridhar, Ramaswamy, R. Rastogi, and K. Shim, "Efficient algorithms for mining outliers from large data sets," in Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas, Texas, United States 2000, pp. 427 - 438.
[45]V. Hautam¨aki, I. K¨arkk¨ainen, and P. Fr¨anti, "Outlier Detection Using k-Nearest Neighbour Graph," in Proceedings of the 17th International Conference on Pattern Recognition (ICPR 2004), Los Alamitos, CA, USA, Aug. 2004, pp. 430- 433.
[46]Y. H. Liao and V. R. Vemuri, "Use of K-Nearest Neighbor classifier for intrusion detection," Computers & Security, vol. 21, pp. 439-448, 2002.
[47] D. Anderson, T. Frivold, A. Tamaru, A. Valdes, "Next Generation Intrusion Detection Expert System (NIDES)." Software Users Manual, Beta-Update release, Computer Science Laboratory, SRI International, Menlo Park, CA, USA, Technical Report SRI-CSL-95-0, May 1994.
[48]B. E. Popescu, Ensemble learning for prediction. Stanford, CA, USA Stanford University, Jan. 2004.
[49]T. F. Wu, C. J. Lin, and R. C. Weng, "Probability estimates for multi-class classification by pairwise coupling," Journal of Machine Learning Research, vol. 5, Aug. 2004, pp. 975-1005.
[50]K. Q. Shen, C. J. Ong, X. P. Li, Z. Hui, and E. P. V. Wilder-Sniith, "A feature selection method for multilevel mental fatigue EEG classification," IEEE Transactions on Biomedical Engineering, vol. 54, Jul. 2007, pp. 1231-1237.
[51]D. Meyer, F. Leisch, and K. Hornik, "The support vector machine under test," Neurocomputing, vol. 55, Sep. 2003, pp. 169-186.
[52]G. I. Webb and Z. J. Zheng, "Multistrategy ensemble learning: Reducing error by combining ensemble learning techniques," IEEE Transactions on Knowledge and Data Engineering, vol. 16, Aug. 2004, pp. 980-991.
[53]J. W. Lu, K. N. Plataniotis, A. N. Venetsanopoulos, and S. Z. Li, "Ensemble-based discriminant learning with boosting for face recognition," IEEE Transactions on Neural Networks, vol. 17, Jan. 2006, pp. 166-178.
[54]L. Breiman, "Random forests," Machine Learning, vol. 45, Oct. 2001 pp. 5-32.
[55]P. Viswanath, M. N. Murty, and S. Bhatnagar, "Partition based pattern synthesis technique with efficient algorithms for nearest neighbor classification," Pattern Recognition Letters, vol. 27, Oct. 15 2006 pp. 1714-1724.
[56]C. Domeniconi, J. Peng, and D. Gunopulos, "Locally adaptive metric nearest-neighbor classification," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, Sep. 2002, pp. 1281-1285.
[57]T. Hastie and R. Tibshirani, "Discriminant adaptive nearest neighbor classification," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, Jun. 1996, pp. 607-616.
[58] DARPA Intrusion Detection Evaluation, MIT Lincoln Laboratory, (http://www.ll.mit.edu/IST/ideval).
[59]T. U. o. Waikato, "WEKA software," Hamilton, Zew Zeland, Machine Learning.
[60]W. H. Chen, S. H. Hsu, and H. P. Shen, "Application of SVM and ANN for intrusion detection," Computers & Operations Research, vol. 32, Oct. 2005 pp. 2617-2634.
[61]L. Khan, M. Awad, and B. Thuraisingham, "A new intrusion detection system using support vector machines and hierarchical clustering," Vldb Journal, vol. 16, Oct. 2007, pp. 507-521.