臺灣博碩士論文加值系統

入侵偵測在現今是一個非常重要的網路安全議題，目前已經有釵h使用資料探勘技術達到入侵偵測目的的研究，但是如何增加其入侵偵測之效率仍為一相當重要之議題；在資料探勘技術應用於入侵偵測的研究中，初期有些研究使用單一資料探勘技術進行入侵偵測，爾後有研究使用混合(hybrid)或是整合(ensemble)方式結合二種以上資料探勘技術以進行入侵偵測，研究也證實結合兩種以上資料探勘技術效能的確優於單一技術使用。本篇論文提出Triangle Area based Nearest Neighbors(TANN)方法，此方法以三角型面積相似測量加上混合的方法結合了k-means以及k-NN兩種技術來做入侵偵測，期能比以往方法更有效率；在這種方法中，首先以k-means先取出五個中點值，再利用三角型面積相似測量轉換資料後以k-NN取得類別值，判斷是否為入侵攻擊。最後，我們使用公開下載之KDDCup 99’資料庫測試並以十摺驗證法近一步驗證實驗之準確性，實驗結果顯示本論文提出的方法與支援向量機(SVM), k-NN,及整合k-means以及k-NN之混合式模型進行比較, TANN可以有效偵測入侵攻擊並且達到非常高的準確率以及低錯誤率。

Intrusion detection is a very important research issue in network security nowadays. Intrusion detection can be approached by data mining and machine learning techniques. In literature, advanced techniques by hybrid learning or ensemble methods have been considered, and they are superior to the models using single machine learning techniques. This thesis proposes a triangle area similarity measure combining the hybrid method, namely Triangle Area based Nearest Neighbors (TANN), in order to detect attacks more effectively. In TANN, we use k-means to obtain five cluster centers and transform data for k-NN classification by triangle area similarity measurement. By using KDDCup 99’ as the dataset and considering 10-fold cross validation, the experimental results show that TANN can effectively detect intrusion attacks and achieve higher detection and lower error rates than three baseline models based on support vector machines, k-NN, and the hybrid model combining k-means and k-NN.

Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 2
1.3 Research Objectives 3
1.4 Structures of This Thesis 4
Chapter 2 Literature Review 5
2.1 Intrusion Detection Systems 5
2.2 Machine Learning 6
2.2.1 Supervised learning 6
2.2.2 Unsupervised learning 8
2.3 Intrusion Detection Approach 9
2.3.1 Hybrid Approach 10
2.3.2 Ensemble Approach 11
2.4 Related Work in Data Mining for Intrusion Detection 12
2.5 Summary of related works 22
Chapter 3 System Architecture 26
3.1 Cluster Centers Extraction 28
3.2 Triangle Area based Nearest Neighbors (TANN) 28
3.2.1 Perimeter of the Triangle - Euclidean Distance 29
3.2.2 Forming the Triangle Area - Heron’s Formula 30
3.2.3 Forming New Training Data 30
3.3 Training and Testing k-NN 31
Chapter 4 Experimental Methodology 32
4.1 KDD-Cup 99 dataset 32
4.2 Dimensionality Reduction 34
4.3 10-fold Cross-validation 34
4.4 Model Validation 36
4.5 Baseline 36
4.6 Evaluation Methods 37



Chapter 5 Experiment Result 39
5.1 k-NN 39
5.2 SVM 40
5.3 Combining k-means and k-NN 40
5.4 TANN 41
5.5 Comparisons and discussions 42
5.5.1 Comparisons among TANN, SVM, k-NN, and the hybrid method 42
5.5.2 t test 44
Chapter 6 Conclusion and Future Work 46
6.1 Summary of this research 46
6.2 Contribution 46
6.3 Future work 47
6.3.1 Techniques used 47
6.3.2 Datasets used 47
6.3.3 Domain problems 47
References 49
Appendix A Data of ROC Curves 54
Appendix B Original Data of t-test 55

Abadeh, M. S. and Habibi, J, Habibi, J., Barzegar, Z. and Sergi, M. 2007. A parallel genetic local search algorithm for intrusion detection in computer networks. Engineering Applications of Artificial Intelligence.
Abadeh, M. S. and Habibi, J. and Lucas, C. 2007. Intrusion detection using a fuzzy genetics-based learning algorithm. Journal of Network and Computer Applications, 30, 414-428.
Agarwal, R. and Joshi, M.V. 2000. PNrule: A New Framework for Learning Classifier Models in Data Mining. Department of Computer Science, University of Minnesota, Report No. RC-21719.
Anderson, J. 1995 . An introduction to neural networks. Cambridge: MIT Press, USA.
Balajinath, B. and Raghavan, S. V. 2000. Intrusion detection through behavior model. Computer Communication,.24, 1202-1212.
Bishop, C, M. 2007. Pattern Recognition and Machine Learning., Springer, USA.
Bishop, C. M. 1995. Neural Networks for Pattern Recognition. Oxford, England: Oxford University Press.
Bouzida,Y., Cuppens, F., Cuppens-Boulahia, N., and Gombault, S. 2004. Efficient intrusion detection using principal component analysis. Proceedings of the 3eme Conference surla Securite et Architectures Reseaux (SAR), Orlando, FL, USA.
Bridges, S. M., Vaughn, R. B. 2000. Intrusion Detection Via Fuzzy Data Mining. The Twelfth Annual Canadian Information Technology Security Symposium, Ottawa, USA, June 19-23.
Chavan, S. Shah, K. Dave, N. and Mukherjee, S. 2004. Adaptive Neuro-Fuzzy Intrusion Detection Systems.” In Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04), 2, 70-74.
Chen, Y. Abraham, A. and Yang, B. 2007. Hybrid Flexible Neural-Tree-Based Intrusion Detection Systems.” International Journal of Intelligent Systems, 22, 337-352.
Chen, W.-H., Hsu, S.-H. and Shen, H.-P. 2005. Application of SVM and ANN for intrusion detection.” Computer and Operations Research, 32, 2617-2634.
Chimphlee, W., Addullah, A. H., Sap, M. N. M., Srinoy, S. and Chimphlee, S. 2006. Anomaly-Based Intrusion Detection using Fuzzy Rough Clustering. International Conference on Hybrid Information Technology (ICHIT’06), November.
Cover, T. M. and Hart, P. E. 1967. Nearest neighbor pattern classification. IEEE T Inform Theory.
Dasarathy, B.V. 1991. Nearest Neighbor (NN) Norms: NNPattern Classification Techniques, IEEE Computer Society, Washington.
Depren, O., Topallar, M., Anarim, E. and Ciliz, M. K. 2005. An intelligent intrusion detection system (IDS) for anomaly and misuse detection in computer networks. Expert Systems with Applications, 29, 713–722.
Dokas, P., Ertoz, L., Kumar, V., Lazarevic, A., Srivastava, J. and Tan, P.-N. 2002. Data Mining for Network Intrusion Detection. Proceeding NSF Workshop on Next Generation Data Mining, Baltimore, MD.
Duda, R.O., Hart, P. E. and Stork, D.G. 2000. “Pattern Classification.” second edition., Wiley-Interscience.
Elkan, C. 1999. Results of the KDD’99 Classifier Learning Contest. URL: http://www.cs.ucsd.edu/users/elkan/clresults.html.
Ertoz, L., Eilertson, E., Lazarevic, A., Tan, P.-N., Dokas, P., Kumar, V. and Srivastava, J. 2003. Detection and Summarization of Novel Network Attacks Using Data Mining. AHPCRC Technical Report, no. 2003-108.
Eskin, E., Arnold, A., Prerau, M., Portnoy, L., and Stolfo, S. 2002. A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data. Data Mining for Security Applications, Kluwer.
Eskin, E. 2000. Anomaly Detection over Noisy Data using Learned Probability Distributions. Proceedings of the Seventeenth International Conference on Machine Learning (ICML-2000), Palo Alto, CA, July.
Fan, W., Lee, W., Miller, M., Stolfo, S. J., and Chan, P. K. 2001. Using artificial anomalies to detect unknown and known network intrusions. Proceedings of the first IEEE International Conference on Data Mining.
Fawcett, T. (2005) “An introduction to ROC analysis” Pattern Recognition Letter 27, pp861-874.
Florez, G., Bridges, S. M., and Vaughn, R. B. 2002. An Improved Algorithm for Fuzzy Data Mining for Intrusion Detection. Proceedings of the North American Fuzzy Information Processing Society Conference (NAFIPS 2002), New Orleans, LA, June 27-29.
Friedman, M. and Kandel, A. 1999. Intrusion to Pattern Recognition – statistical, structural, neural and fuzzy logic approaches. World Scientific Publishing, USA.
Giacinto, G., Perdisci, R., Rio, M. D. and Roli, F. 2006. Intrusion detection in computer networks by a modular ensemble of one-class classifier. Information Fusion.
Giacinto, G. and Roli, F. 2003. Intrusion Detection in Computer Networks by Multiple Classifier Systems. Proceeding of ICPR 2002, 16th International Conference on Pattern Recognition, Quebec City, Canada, Aug 11 - 15, IEEE press, 2, 390-393.
Gomez, J. and Dasgupta, D. 2001. Evolving fuzzy classifiers for intrusion detection. Proceedings of the 2002 IEEE Workshop on Information Assurance, United States Military Academy, West Point, NY, June, 2001.
Han, S.-J. and Cho, S.-B. 2003. Detecting intrusion with ruled-based integration of multiple models.” Computers and Security, vol. 22, no. 7, pp 613-623.
Heller, K. A., Svore, K. M., Keromytis, A. D., and Stolfo, S. J. 2003. One Class Support Vector Machines for Detecting Anomalous Window Registry Accesses. 3rd IEEE Conference Data Mining Workshop on Data Mining for Computer Security, Florida, November 19.
Hinton, G. and Sejnowski, T. J. 1999. Unsupervised Learning and Map Formation: Foundations of Neural Computation. ISBN 0-262-58168-X, MIT Press, USA.
Hopfield, J. J. 1987. “Learning algorithms and probability distributions in feed-forward and feed-back networks.” In Proceedings of the National Academy of Sciences of the USA, vol. 84, pp 8429 - 8433.
Hotelling, H. 1993. Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24, 498-520.
Ishibuchi, H. and Nakashima, T. 1999. Improving the performance of fuzzy classifier systems for pattern classification problems with continuous attributes. IEEE Trans. Ind. Electron, 46, no. 6, DECEMBER 1999.
Jiang, S. Y., Song, X., Wang, H., Han, J.-J. and Li, Q.-H. 2006. A clustering-based method for unsupervised intrusion detections.” Pattern Recognition Letters, 27, 802–810.
Joo, D. Hong, T. and Han, I. 2003. The neural network models for IDS based on the asymmetric costs of false negative errors and false positive errors. Expert System with Applications, 25, 69-75.
Kang, D. K., Fuller, D. and Honavar, V. 2005. Learning Classifiers for Misuse and Anomaly Detection Using a Bag of System Calls Representation. Proceeding of the 2005 IEEE, 118-125.
Kayacik, H. G., Nur, Z.-H. and Heywood, M. I. 2007. A hierarchical SOM-based intrusion detection system. Engineering Applications of Artificial Intelligence, 20, 439-451.
Khan, L., Awad, M. and Thuraisingham, B. 2007. A new intrusion detection system using support vector machines and hierarchical clustering. The VLDB Journal, 16, 507-521.
Kim, K.-J. and Ahn, H. 2008. A recommender system using GA K-means clustering in an online shopping market. Expert System with Application, 34, 1200-1209.
Lazarevic, A., Ertoz, L., Kumar, V., Ozgur, A., and Srivastava, J. 2003. A comparative study of anomaly detection schemes in network intrusion detection. Proceedings of the Third SIAM Conference on Data Mining, San Francisco, CA.
Lee, W., and Stolfo, S. 2000. A framework for constructing features and models for intrusion detection systems. ACM Transactions on Information and System Security (TISSEC), 3, Issue 4 (November 2000), 227 – 261.
Lee, W., and Stolfo, S. 1998. Data Mining Approaches for Intrusion Detection. Proceedings of the Seventh USENIX Security Symposium (SECURITY '98), San Antonio, TX, January.
Lee , W., Stolfo, S. J., Chan_ , P. K., Eskin, E. , Fan , W., Miller, M., Hershkop, S., and Zhang, J. 2001. Real Time Data Mining-based Intrusion Detection. Proceedings of DISCEX II.
Levin, I. 2000. KDD-99 classifier learning contest LLSoft’s results verview. SIGKDD explorations, ACM SIGKDD 1 (2) 67–75.
Leon, E., Nasraoui, O., and Gomez, J. 2004. Anomaly detection based on unsupervised niche clustering with application to network intrusion detection. Evolutionary Computation.
Liao, Y. and Vemuri, V. R. 2002. Use of K-Nearest Neighbor classifier for intrusion detection. Computer and Security, 21, 5, 439-448.
Liu, G., Yi, Z. and Yang, S. 2007. A hierarchical intrusion detection model based on the PCA neural networks. Neurocomputing, 70, 1561-1568.
Liu, G. and Yi, Z. 2006. Intrusion Detection Using PCASOM Neural Networks. Proceeding of ISNN2006, Lecture Notes in Computer Science, 3973, Springer, Berlin, Heidelberg, 240-245.
Liu, Y., Chen, K., Liao, X., and Zhang, W. 2004. A genetic clustering method for intrusion detection. Pattern Recognition, 37, 927-942.
Li, Y. and Guo, L. 2007.An Active Learning Based TCM-KNN Algorithm for Supervised Network Intrusion Detection. Computer and Security, 26, 459-467..
Luo, J. and Bridgest, S. M. 2000. Mining Fuzzy Association Rules and Fuzzy Frequency Episodes for Intrusion Detection. International Journal of Intelligent System, 15, 687-703.
MacQueen, J. B. 1967. Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 281-297.
Mitra, S. and Acharya, T. 2003. DATA MINING Multimedia, Soft Computing, and Bioinformatics. Wiley Inter-Science, USA.
Moradi, M. and Zulkernine, M. 2004. A Neural Network Based System for Intrusion Detection and Classification of Attacks. Proceeding of the 2004 IEEE International Conference on Advances in Intelligent Systems - Theory and Applications, pp 148: 1-6, Luxembourg, November.
Mukkamala, S., Sung, A. H., and Abraham, A. 2005. Intrusion detection using an ensemble of intelligent paradigms. Network and Computer Applications, 28, 167-182.
Mukkamala, S., Sung, A. H., and Abraham, A. 2004. Modeling Intrusion Detection Systems Using Linear Genetic Programming Approach. Proceedings of Innovations in Applied Artificial Intelligence, 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE), Lecture Notes in Computer Science 3029 Springer 2004, 633-642.
Nisson, N. J. 1996. Introduction to Machine Learning. MIT Press, USA.
Ozyer, T., Alhajj, R. and Barker, K. 2007. Intrusion detection by integrating boosting genetic fuzzy classifier and data mining criteria for rule pre-screening. Journal of Network and Computer Applications, 30, 99–113.
Patcha, A. and Park, J.-M. 2007. An overview of anomaly detection techniques: Existing solution and latest technological trends. Computer Networks, 51, 3448-3470.
Peddabachigari, S., Abraham, A., Grosan, C. and Thomas, J. 2007. Modeling intrusion detection system using hybrid intelligent systems. Journal of Network and Computer Applications, 30, 114-132.
Peddabachigari, S., Abraham, A., and Thomas J. 2004. Intrusion Detection Systems Using Decision Trees and Support Vector Machines. International Journal of Applied Science and Computations, USA.
Pfahringer, B. 2000. Winning the KDD99 classification cup: bagged boosting, SIGKDD Explorations 1, 2, 65–66.
Portnoy, L., Eskin, E., and Stolfo, S. J. 2001. Intrusion detection with unlabeled data using clustering. Proceedings of ACM CSS Workshop on Data Mining Applied to Security (DMSA-2001), Philadelphia, PA, November 5-8.
Ramos,V. and Abraham, A. 2005. ANTIDS: self organized ant based clustering model for intrusion detection system. Proceedings of The Fourth IEEE International Workshop on Soft Computing as Transdisciplinary Science and Technology (WSTST'05), 977-986, Springer-Verlag, Berlin.
Rhodes, B., Mahaffey, J., and Cannady, J. 2000. Multiple self-organizing maps for intrusion detection. Proceedings of the 23rd national information systems security conference, Baltimore, MD.
Sabhnani,M.R., and Serpen, G. 2003. Application of machine learning algorithms to KDD intrusion detection dataset within misuse detection context. Proceedings of International Conference on Machine Learning: Models, Technologies, and Applications, 23–26 June, Las Vegas, Nevada, USA, 209–215.
Schultz, M. G., Eskin, E., Zadok, E., and Stolfo, S. J. 2001. Data Mining Methods for Detection of New Malicious Executables. Proceedings of the 2001 IEEE Symposium on Security and Privacy (SP '01), 178–184.
Scott, S. L. 2004. A Bayesian paradigm for designing intrusion detection systems. Computational Statistics and Data Analysis, 45, 69-83.
Shon, T. and Moon, J. 2007. A hybrid machine learning approach to network anomaly detection. Information Sciences, 177, 3799-3821.
Shon, T., Kovah, X. and Moon, J. 2006. Applying genetic algorithm for classifying anomalous TCP/IP packets. Neurocomputing, 69, 2429-2433.
Shyu, M. Chen, S. Sarinnapakorn, K. and Chang, L. 2003. A Novel Anomaly Detection Scheme Based on Principal Component Classifier. Proceedings of ICDM’03, 172-179.
Song, D., Heywood, M. I. and Zincir-Heywood, A.N. 2005. Training genetic programming on half a million patterns: an example from anomaly detection.” IEEE Transactions on Evolutionary Computation, 9(3), 225–239.
Stallings, W. 2006. Cryptography and Network Security Principles and Practices. Pearson Prentice Hall, USA.
Stein, G. Chen, B. Wu, A. S. and Hua, K. A. 2005. Decision tree classifier for network intrusion detection with GA-based feature selection. Proceedings of the 43rd annual Southeast regional conference, March 18-20, Kennesaw, Georgia.
Tan, P.-N., Steinbach, M., and Kumar, V. 2006. Introduction to data mining. Addition-Wisley, USA.
Theodoridis, S. and Koutroumbas, K. 2006. Pattern Recognition 3 edition. ACADEMIC PRESS, USA.
Thomassey, S and Fiordaliso, A. 2006. A hybrid sales forecasting system based on clustering and decision tree. Decision Support Systems, 24, 408-421.
Tian, M., Chen, S.-C., Zhuang, Y. and Liu, J. 2004. Using statistical analysis and support vector machine classification to detect complicated attacks. Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, 26-29 August.
Toosi, A. N. and Kahani, M. 2007. A new approach to intrusion detection based on an evolutionary soft computing model using neuro-fuzzy classifiers. Computer Communication, 30, 2201-2212.
Tsang, C.-H., Kwong, S. and Wang, H. 2007. Genetic-fuzzy rule mining approach and evaluation of feature selection techniques for anomaly intrusion detection. Pattern Recognition, 40, 2373-2391.
Wang, W.; Battiti, R 2006. Identifying intrusions in computer networks with principal component analysis. Proceedings of the First International Conference on Availability, Reliability and Security (ARES'06), 270-279.
Wang, W., Guan, X., Zhang, X. 2004. A novel intrusion detection method based on principle component analysis in computer security. Proceedings of the International Symposium on Neural Networks, Dalian, China, 2004, 657–662.
Wang, K., Stolfo, S. J. 2004. Anomalous Payload-based Network Intrusion Detection. Proceedings of Recent Advance in Intrusion Detection (RAID), Sophia Antipolis, France, Sept.
Wang, Y., Kim, I., Mbateng, G. and Ho, S.-Y. 2006. A latent class modeling approach to detect network intrusion. Computer Communications, 30, 93-100.
Witten, I. H. and Frank, E. 2005. Data Mining Practical Machine Learning Tools and Techniques. Morgan Kaufmann, USA.
Xiang, C. Lim and S. M. 2005. Design of multiple-level hybrid classifier for intrusion detection system. Proceeding of the IEEE Workshop Machine Learning for Signal Processing, September 2005, 117-122.
Yamanishi, K., Takeuchi, J.-I. and Williams, G. 2000. On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms. Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 320–324.
Yeung, D.Y. and Chow, C. 2002. Parzen-Window network intrusion detectors. Proceeding of 16th International Conference on Pattern Recognition, 11–15 August, IEEE Computer Society, 4, 385–388.
Zhang, C., Jiang, J., and Kamel, M. 2005. Intrusion detection using hierarchical neural network. Pattern Recognition Letters, 26, 779-791.
Zhang, L.-H., Zhang, G.-H., Yu, L., Zhang, J., and Bai, Y.-C. 2004. Intrusion detection using rough set classification. Journal of Zhejiang University SCIENCE, 5(9), 1076-1086.
Zhang, Z. and Shen, H. 2005. Application of online-training SVMs for real-time intrusion detection with different considerations. Computer Communications, 28, 1428-1442.