基于多级贪婪的人侵检测分类算法研究
|
摘要
入侵检测是通过对系统审计数据进行检测分析来发现入侵企图并采取相应保护措施的一种技术，是保护计算机和网络安全的重要防线。
当前在入侵检测系统模型构造中采用的技术有很多种，其中，将数据挖掘(DM)技术应用到入侵检测系统模型构造中是实现模型构造的系统化、自动化，克服手工编码或过多依赖专家经验的一种有效方法。
但是，目前通用的数据挖掘算法在应用到入侵检测领域时，会存在不适合入侵检测的特殊环境的问题。
本文研究了在入侵检测领域广泛应用的挖掘算法——规则归纳分类算法。在大量的入侵检测环境下的数据上应用RIPPER分类算法的结果显示，这一传统分类算法强大的归纳能力对于入侵检测环境下反例缺乏(我们提供的审计数据不可能函概所有的入侵类型)的数据集不能很好地适应。本文在RIPPER算法的基础上，进行了适
太原理工大学硕士研究生毕业论文
应入侵检测环境的改造，提出了多级贪婪祸合规则归纳
算法。
通过在多组人造及实际数据集上同RIPPER算法的对
比实验，证明该算法对于反例缺乏的数据集，在没有明
显影响算法的速度的前提下，仍然具有较强的归纳能力。
Intrusion Detection, which tries to detect attempts to penetrate into a system is now an important fort to protect computer systems.
There are many techniques applied in the construction of intrusion detection systems. Of them, data mining is an efficient one to construct an intrusion detection system systematically and automatically, avoiding of manual and ad hoc means.
However, current data mining algorithm can't completely adapt to the particular requirements in intrusion detection fields.
Rule induction algorithm, a mining algorithm widely used in intrusion detection fields, is researched in this thesis. By applying RIPPER algorithm to a great lot data sets in intrusion detection fields, we found that the inductive ability of this traditional classification algorithm could be greatly damaged by the lack of negative examples in training data sets. Given the prevalence of lack of negative examples (which cover some intrusion types) in the audit
data we can offer, this limitation was almost lethal. Based on RIPPER, some modification was proposed to adapt the intrusion detection environment, resulting in the multi-greedy and coupling (MGC) rule induction learning algorithm.
Tests on a few man-made and real data sets showed that, without greatly affecting its computational efficiency, the new algorithm have better generalization performance over RIPPER algorithm on data sets lack of negative examples.
当前在入侵检测系统模型构造中采用的技术有很多种，其中，将数据挖掘(DM)技术应用到入侵检测系统模型构造中是实现模型构造的系统化、自动化，克服手工编码或过多依赖专家经验的一种有效方法。
但是，目前通用的数据挖掘算法在应用到入侵检测领域时，会存在不适合入侵检测的特殊环境的问题。
本文研究了在入侵检测领域广泛应用的挖掘算法——规则归纳分类算法。在大量的入侵检测环境下的数据上应用RIPPER分类算法的结果显示，这一传统分类算法强大的归纳能力对于入侵检测环境下反例缺乏(我们提供的审计数据不可能函概所有的入侵类型)的数据集不能很好地适应。本文在RIPPER算法的基础上，进行了适
太原理工大学硕士研究生毕业论文
应入侵检测环境的改造，提出了多级贪婪祸合规则归纳
算法。
通过在多组人造及实际数据集上同RIPPER算法的对
比实验，证明该算法对于反例缺乏的数据集，在没有明
显影响算法的速度的前提下，仍然具有较强的归纳能力。
Intrusion Detection, which tries to detect attempts to penetrate into a system is now an important fort to protect computer systems.
There are many techniques applied in the construction of intrusion detection systems. Of them, data mining is an efficient one to construct an intrusion detection system systematically and automatically, avoiding of manual and ad hoc means.
However, current data mining algorithm can't completely adapt to the particular requirements in intrusion detection fields.
Rule induction algorithm, a mining algorithm widely used in intrusion detection fields, is researched in this thesis. By applying RIPPER algorithm to a great lot data sets in intrusion detection fields, we found that the inductive ability of this traditional classification algorithm could be greatly damaged by the lack of negative examples in training data sets. Given the prevalence of lack of negative examples (which cover some intrusion types) in the audit
data we can offer, this limitation was almost lethal. Based on RIPPER, some modification was proposed to adapt the intrusion detection environment, resulting in the multi-greedy and coupling (MGC) rule induction learning algorithm.
Tests on a few man-made and real data sets showed that, without greatly affecting its computational efficiency, the new algorithm have better generalization performance over RIPPER algorithm on data sets lack of negative examples.
引文
[1] Wenke Lee and Salvatore J. Stolfo, Data Mining Approaches for Intrusion Detection, www.cs.columbia.edu/-wenke/papers/usenix.ps, 2001
[2] Wenke Lee and Salvatore J. Stolfo , A Data Mining Framework for Building Intrusion Detection Models, www.cs.umbc.edu/cadip/docs/NetworkIntrusion/ieee_sp99_lee.ps 1999
[3] Christina Warrender, Stephanie Forrest and Barak Pearlmutter, Detecting Intrusion Using System Calls:Alternative Data Models, IEEE Computer Society, 1999, 133-145 www.cs.unm.edu/-immsec/publications/oakland-with-submit-info.ps. gz
[4] Andreas L. Prodromidis and Salvatore J. Stolfo, Meta-learning in distributed data mining systems: Issues and approaches, www.cs.fit.edu/-pkc/papers/ddmbook.ps, 1999
[5] Wenke Lee , A Data Mining Framework for Constructing Features and Models for Intrusion Detection Systems, www.csc.ncsu.edu/faculty/lee/papers/thesis.ps.g, 1999
[6] Wenke Lee and Salvatore J. Stolfo, Mining Audit Data to Build Intrusion Detection Models, www.csc.ncsu.edu/faculty/lee/papers/kdd98． ps, 1998
[7] Wenke Lee and Rahul, A Data Mining and CIDF Based Approach for Detecting Novel and, www.csc.ncsu.edu/faculty/lee/papers/lee raid 00． ps, 2000
[8] Wenke Lee , Toward Cost-Sensitive Modeling for Intrusion Detection and Response, www.csc.ncsu.edu/facultv/lee/papers/jcs lee.ps, 2000
[9] Ke Wang, Yu He and Jiawei Han, Mining Frequent Itemsets Using Support Constraints, www.cs.sfu.ca/-wangk/pub/Asial25． ps , 2000
[10] Wei Fan and Wenke Lee , A Multiple Model Cost-Sensitive Approach for Intrusion Detection, www.cs.columbia.edu/-wfan/papers/ecm100． ps.gz, 2000
[11] Wenke Lee and Salvatore J. Stolfo, A Data Mining Framework for Adaptive Intrusion Detection, www.cs.columbia.edu/-sal/hpapers/framework.ps.gz, 1998
[12] Eleazar Eskin and Matthew Miller, Adaptive Model Generation for Intrusion Detection Systems, www.cs.columbia.edu/ids/publications/adaptive-ccsids00． pdf, 2000
[13] Steven A. Hofmeyr and Stephanie Forrest, Architecture for an Artificial Immune System, www.cs.unm.edu/-steveah/ecs.ps, 2000
[14] Steven A. Hofmeyr and Stephanie Forrest, Immunity by Design: An Artificial Immune System, ftp.cs.unm.edu/pub/forrest/gecco-steve..ps, 1999
[15] Dipankar Dasgupta, Artificial Neural Networks and Artificial Immune Systems: Similarities and Differences, IEEE International Conference on Systems, Man, and Cybernetics, Orlando, October 12-15, ftp.msci.memphis.edu/comp/ dasgupta/papers/smc97-pap2． ps.Z
[16] Eric Bloedorn Alan, Data Mining for Network Intrusion Detection: How to Get Started, www.mitre.org/support/papers/tech papers 01/bloedorn datamining/ bloedorn datamining.pdf, 2000
[17] Chua Boon Lay, Marzuki Khalid and Rubiyah, Intelligent Database by Neural Network and Data Mining, www.cairo.utm.my/publications/blchua_datamining.pdf , 2000
[18] A. Prodromidis and S. Stolfo., Effective and Efficient Pruning of Meta-Classifiers In Distributed Data, www.cs.columbia.edu/-andreas/publications/SPDDM98． ps.gz, 1996
[19] Dit-Yan Yeung Calvin, Parzen-Window Network Intrusion Detectors, www.cs.ust.hk/-dyyeung/paper/pdf/yeung.icpr2002． pdf,
2002
[20] Wenke Lee and Salvatore J. Stolfo, Real Time Data Mining-based Intrusion Detection, www. cs.columbia.edu/ids/publications/dmids-discex01.ps, 2001
[21] Eleazar Eskin, Modeling System Calls for Intrusion Detection with Dynamic Window Sizes,www. cs.columbia.edu/ids/publications/smt-syscall-discex01.ps, 2001
[22] Andreas Prodromidis, Cost Complexity-based Pruning of Ensemble Classifiers,www. cs.columbia.edu/～andreas/publications/KDD99.ps.gz, 1999
[23] Eckmann, Vigna and Kemmerer, STATL: An Attack Language for State-based Intrusion Detection, www. cs.ucsb.edu/～vigna/pub/eckmann vigna kemmerer statl.ps.gz,2000
[24] Khaled EI Emam, Saida Benlarbi, Nishith Goel and Shesh N. Rai, Comparing case-based reasoning classifiers for predicting high risk software components, The Journal of Systems and Software, Vol.55, 301～320, 2001
[25] Daniel J. Ragsdale, Adaptation Techniques for Intrusion Detection and Intrusion Response Systems
[26] Peng Xinguang, Liu Yushu, Wu Yushu, Yu Xueli, A New Accuracy Evaluation Criterion for Binary Classifiers, IEEE Region 10 Technical Conference on Computers and Communication, October 2002, To be appered
[27] 连一峰，戴英狭，王航，基于模式挖掘的用户行为异常检测，计算机学报，第25卷第3期，325～330，2002年3月
[28] 刘红岩，陆宏钧，陈剑，利用数据库技术实现的可扩展的分类算法，软件学报，第13卷第6期，1075～1081，2002年6月
[29] 季文斌，周傲英，张亮，金文，一种基于遗传算法的优化分类器的方法，软件学报，第13卷第2期，245～249，2002年2月
[30] 闫巧，谢维信，免疫思想在计算机安全系统中的应用，计算机科学，第29卷第2期，98～99，2002年2月
[31] 董晓梅，王丽娜，于戈，王国仁，分布式入侵检测系统综述，计算机科学，第29卷第2期，16～19，2002年3月
[32] 曾昭苏，王锋波，基于数据开采技术的入侵检测系统，自动化博览，29-31，2000．2
[33] 蒋建春，马恒太，任党恩，卿斯汉，网络安全入侵检测：研究综述，软件学报，2000．11，1460～1466
[34] 夏春和，张欣，网络入侵检测系统RIDS的研究，系统仿真学报，2000．7，375～379
[35] 马恒太，蒋建春，陈伟锋，卿斯汉，基于Agent的分布式入侵检测系统模型，软件学报，2000．11，1312～1319
[36] Dorothy E. Denning, An Intrusion Detection Model, IEEE transactions on software engineering, Vol. 13, No. 2 February 1987, 222～232
[37] Guy G. Helmer, Johnny S. K. Wong, Vasant Honavar and Les Miller, Intelligent Agents for Intrusion Detection,www. cs.iastate.edu/～honavar/Papers/it98-helmer, ps, 1998
[38] Dipankar Dasgupta and Fabio A. Gonzalez, An Immunogenetic Approach to Intrusion Detection,issrl.cs.memphis.edu/Tech-Report-01.pdf, 2001.5
[39] Chris Sinclair, Lyn Pierce and Sara Matzner, An Application of Machine Learning to Network Intrusion Detection, www. acsac.org/1999/papers/fri-b-1030-sinclair. pdf
[40] Richard P. Lippmann and Robert K.Cunningham, Improving intrusion detection performance using keyword selection and neural networks, Computer Network, 34(2000), 597～603
[41] 戴英狭，连一峰，王航，系统安全与入侵检测，清华大学出版社，2002年3月
[42] 陆汝钤，世纪之交的知识工程与知识科学，清华大学出版社，2001年9月
[43] 史忠植，知识发现，清华大学出版社，2002年1月
[44] Jiawei Han and Micheline, Data Mining Concepts and Techniques , Morgan Kaufman Publishers , 2001 . 8
[45] 刘同明，数据挖掘技术及其应用，国防工业出版社，2001年9月
[46] Eleazar Eskin, Matthew, Zhi-Da Zhong, George Yi, Wei-Ang Lee, Salvatore Stolfo, Adaptive Model Generation for Intrusion Detection Systems, philby.ucsd.edu/-cse291_IDVA/papers/eskin,miller,zhong,yi,lee,stolf o . adaptive_model_generation_for_intrusion_detection_sy stems .pdf
[47] Dipankar Dasgupta, Stephanie Forrest, Novelty Detection in Time Series Data using Ideas from Immunology, 16th world computer congress , Beijing, China, 2000
[48] Alexandr Seleznyov, Temporal-Probabilistic Networks in Intrusion Detection: Detecting Abnormal Learning, 16th world computer congress , Beijing, China, 2000
[49] Luo Mingyu,Lu Xicheng, Han yaxin,Su Jinshu, A Fuzzy Pattern Matching Method In Intrusion Detection for Network Security, 16th world computer congress , Beijing, China, 2000
[50] Brian D.Davison and Haym Hirsh, Predicting Sequences of User Actions , AAA/ICML ,1998, www.cs.rutgers.edu/-davison/pubs/aaai98ws.html
[51] Richard P. Lippmann, David J. Fried, Isaac Graf and Joshua W. Haines, Evaluation Intrusion Detection System: The 1999 DARPA Off-line Intrusion Detection Evaluation http://citeseer.nj .nec.com/cs
[52] William W. Cohen, Fast Effective Rule Induction, Machine Learning : Proceedings of the Twelfth International Conference (ML95)
[53] Buchanan, B. G.., Smith, D. H. White, W. C., Gritter, R., Feigen., (1976) . Applications of artificial intelligence for chemical ingerence, XXXII: Automatic rule formation in mass spectrometry by means of
the meta-DENDRAL PROGRAM. Journal of the American Chemical Society, 98, 6168．
[2] Wenke Lee and Salvatore J. Stolfo , A Data Mining Framework for Building Intrusion Detection Models, www.cs.umbc.edu/cadip/docs/NetworkIntrusion/ieee_sp99_lee.ps 1999
[3] Christina Warrender, Stephanie Forrest and Barak Pearlmutter, Detecting Intrusion Using System Calls:Alternative Data Models, IEEE Computer Society, 1999, 133-145 www.cs.unm.edu/-immsec/publications/oakland-with-submit-info.ps. gz
[4] Andreas L. Prodromidis and Salvatore J. Stolfo, Meta-learning in distributed data mining systems: Issues and approaches, www.cs.fit.edu/-pkc/papers/ddmbook.ps, 1999
[5] Wenke Lee , A Data Mining Framework for Constructing Features and Models for Intrusion Detection Systems, www.csc.ncsu.edu/faculty/lee/papers/thesis.ps.g, 1999
[6] Wenke Lee and Salvatore J. Stolfo, Mining Audit Data to Build Intrusion Detection Models, www.csc.ncsu.edu/faculty/lee/papers/kdd98． ps, 1998
[7] Wenke Lee and Rahul, A Data Mining and CIDF Based Approach for Detecting Novel and, www.csc.ncsu.edu/faculty/lee/papers/lee raid 00． ps, 2000
[8] Wenke Lee , Toward Cost-Sensitive Modeling for Intrusion Detection and Response, www.csc.ncsu.edu/facultv/lee/papers/jcs lee.ps, 2000
[9] Ke Wang, Yu He and Jiawei Han, Mining Frequent Itemsets Using Support Constraints, www.cs.sfu.ca/-wangk/pub/Asial25． ps , 2000
[10] Wei Fan and Wenke Lee , A Multiple Model Cost-Sensitive Approach for Intrusion Detection, www.cs.columbia.edu/-wfan/papers/ecm100． ps.gz, 2000
[11] Wenke Lee and Salvatore J. Stolfo, A Data Mining Framework for Adaptive Intrusion Detection, www.cs.columbia.edu/-sal/hpapers/framework.ps.gz, 1998
[12] Eleazar Eskin and Matthew Miller, Adaptive Model Generation for Intrusion Detection Systems, www.cs.columbia.edu/ids/publications/adaptive-ccsids00． pdf, 2000
[13] Steven A. Hofmeyr and Stephanie Forrest, Architecture for an Artificial Immune System, www.cs.unm.edu/-steveah/ecs.ps, 2000
[14] Steven A. Hofmeyr and Stephanie Forrest, Immunity by Design: An Artificial Immune System, ftp.cs.unm.edu/pub/forrest/gecco-steve..ps, 1999
[15] Dipankar Dasgupta, Artificial Neural Networks and Artificial Immune Systems: Similarities and Differences, IEEE International Conference on Systems, Man, and Cybernetics, Orlando, October 12-15, ftp.msci.memphis.edu/comp/ dasgupta/papers/smc97-pap2． ps.Z
[16] Eric Bloedorn Alan, Data Mining for Network Intrusion Detection: How to Get Started, www.mitre.org/support/papers/tech papers 01/bloedorn datamining/ bloedorn datamining.pdf, 2000
[17] Chua Boon Lay, Marzuki Khalid and Rubiyah, Intelligent Database by Neural Network and Data Mining, www.cairo.utm.my/publications/blchua_datamining.pdf , 2000
[18] A. Prodromidis and S. Stolfo., Effective and Efficient Pruning of Meta-Classifiers In Distributed Data, www.cs.columbia.edu/-andreas/publications/SPDDM98． ps.gz, 1996
[19] Dit-Yan Yeung Calvin, Parzen-Window Network Intrusion Detectors, www.cs.ust.hk/-dyyeung/paper/pdf/yeung.icpr2002． pdf,
2002
[20] Wenke Lee and Salvatore J. Stolfo, Real Time Data Mining-based Intrusion Detection, www. cs.columbia.edu/ids/publications/dmids-discex01.ps, 2001
[21] Eleazar Eskin, Modeling System Calls for Intrusion Detection with Dynamic Window Sizes,www. cs.columbia.edu/ids/publications/smt-syscall-discex01.ps, 2001
[22] Andreas Prodromidis, Cost Complexity-based Pruning of Ensemble Classifiers,www. cs.columbia.edu/～andreas/publications/KDD99.ps.gz, 1999
[23] Eckmann, Vigna and Kemmerer, STATL: An Attack Language for State-based Intrusion Detection, www. cs.ucsb.edu/～vigna/pub/eckmann vigna kemmerer statl.ps.gz,2000
[24] Khaled EI Emam, Saida Benlarbi, Nishith Goel and Shesh N. Rai, Comparing case-based reasoning classifiers for predicting high risk software components, The Journal of Systems and Software, Vol.55, 301～320, 2001
[25] Daniel J. Ragsdale, Adaptation Techniques for Intrusion Detection and Intrusion Response Systems
[26] Peng Xinguang, Liu Yushu, Wu Yushu, Yu Xueli, A New Accuracy Evaluation Criterion for Binary Classifiers, IEEE Region 10 Technical Conference on Computers and Communication, October 2002, To be appered
[27] 连一峰，戴英狭，王航，基于模式挖掘的用户行为异常检测，计算机学报，第25卷第3期，325～330，2002年3月
[28] 刘红岩，陆宏钧，陈剑，利用数据库技术实现的可扩展的分类算法，软件学报，第13卷第6期，1075～1081，2002年6月
[29] 季文斌，周傲英，张亮，金文，一种基于遗传算法的优化分类器的方法，软件学报，第13卷第2期，245～249，2002年2月
[30] 闫巧，谢维信，免疫思想在计算机安全系统中的应用，计算机科学，第29卷第2期，98～99，2002年2月
[31] 董晓梅，王丽娜，于戈，王国仁，分布式入侵检测系统综述，计算机科学，第29卷第2期，16～19，2002年3月
[32] 曾昭苏，王锋波，基于数据开采技术的入侵检测系统，自动化博览，29-31，2000．2
[33] 蒋建春，马恒太，任党恩，卿斯汉，网络安全入侵检测：研究综述，软件学报，2000．11，1460～1466
[34] 夏春和，张欣，网络入侵检测系统RIDS的研究，系统仿真学报，2000．7，375～379
[35] 马恒太，蒋建春，陈伟锋，卿斯汉，基于Agent的分布式入侵检测系统模型，软件学报，2000．11，1312～1319
[36] Dorothy E. Denning, An Intrusion Detection Model, IEEE transactions on software engineering, Vol. 13, No. 2 February 1987, 222～232
[37] Guy G. Helmer, Johnny S. K. Wong, Vasant Honavar and Les Miller, Intelligent Agents for Intrusion Detection,www. cs.iastate.edu/～honavar/Papers/it98-helmer, ps, 1998
[38] Dipankar Dasgupta and Fabio A. Gonzalez, An Immunogenetic Approach to Intrusion Detection,issrl.cs.memphis.edu/Tech-Report-01.pdf, 2001.5
[39] Chris Sinclair, Lyn Pierce and Sara Matzner, An Application of Machine Learning to Network Intrusion Detection, www. acsac.org/1999/papers/fri-b-1030-sinclair. pdf
[40] Richard P. Lippmann and Robert K.Cunningham, Improving intrusion detection performance using keyword selection and neural networks, Computer Network, 34(2000), 597～603
[41] 戴英狭，连一峰，王航，系统安全与入侵检测，清华大学出版社，2002年3月
[42] 陆汝钤，世纪之交的知识工程与知识科学，清华大学出版社，2001年9月
[43] 史忠植，知识发现，清华大学出版社，2002年1月
[44] Jiawei Han and Micheline, Data Mining Concepts and Techniques , Morgan Kaufman Publishers , 2001 . 8
[45] 刘同明，数据挖掘技术及其应用，国防工业出版社，2001年9月
[46] Eleazar Eskin, Matthew, Zhi-Da Zhong, George Yi, Wei-Ang Lee, Salvatore Stolfo, Adaptive Model Generation for Intrusion Detection Systems, philby.ucsd.edu/-cse291_IDVA/papers/eskin,miller,zhong,yi,lee,stolf o . adaptive_model_generation_for_intrusion_detection_sy stems .pdf
[47] Dipankar Dasgupta, Stephanie Forrest, Novelty Detection in Time Series Data using Ideas from Immunology, 16th world computer congress , Beijing, China, 2000
[48] Alexandr Seleznyov, Temporal-Probabilistic Networks in Intrusion Detection: Detecting Abnormal Learning, 16th world computer congress , Beijing, China, 2000
[49] Luo Mingyu,Lu Xicheng, Han yaxin,Su Jinshu, A Fuzzy Pattern Matching Method In Intrusion Detection for Network Security, 16th world computer congress , Beijing, China, 2000
[50] Brian D.Davison and Haym Hirsh, Predicting Sequences of User Actions , AAA/ICML ,1998, www.cs.rutgers.edu/-davison/pubs/aaai98ws.html
[51] Richard P. Lippmann, David J. Fried, Isaac Graf and Joshua W. Haines, Evaluation Intrusion Detection System: The 1999 DARPA Off-line Intrusion Detection Evaluation http://citeseer.nj .nec.com/cs
[52] William W. Cohen, Fast Effective Rule Induction, Machine Learning : Proceedings of the Twelfth International Conference (ML95)
[53] Buchanan, B. G.., Smith, D. H. White, W. C., Gritter, R., Feigen., (1976) . Applications of artificial intelligence for chemical ingerence, XXXII: Automatic rule formation in mass spectrometry by means of
the meta-DENDRAL PROGRAM. Journal of the American Chemical Society, 98, 6168．