基于变长系统调用序列入侵检测的研究与实现
|
摘要
入侵检测技术是一种主动的信息安全保障措施,已成为现代计算机系统安全技术中的研究热点。它的主要任务是按照一定的策略,对网络的运行状况进行监视,尽可能发现各种攻击行为,以保证网络系统资源的机密性、完整性和可用性。
本文首先陈述了入侵检测的研究背景和发展,以及入侵检测系统(IDS)的概念、原理和分类。其次,重点分析了基于系统调用的入侵检测方法。本文针对目前各种基于系统调用的入侵检测技术进行了研究与比较,指出现有算法的不足之处:采用固定长度的系统调用序列。为克服不足之处,本文采用变长的系统调用序列检测方法,将Teiresias组合模式发现算法,这一典型的变长模式生成算法应用到系统调用入侵检测中。
高效的模式匹配算法能够显著提高入侵检测效率。本文在分析了几个常用多模式匹配算法的基础上,根据理论[32]指导对Wu-Manber算法进行了改进,结合了Quick-Search匹配算法的思想,在预处理阶段构造了一个Head表,增加了WM算法的跳转距离,实验表明改进算法可以有效地减小匹配步数,提高匹配效率。
最后,在Unix环境中构建了一个基于变长系统调用序列模式的入侵检测模型,设计并实现了数据收集模块、正常行为模式建立模块、检测模块。在数据收集模块中,采用LKM技术收集程序执行的系统调用序列。模式抽取模块采用基于Teiresias算法的变长模式抽取方法构建程序正常行为模式库。检测模块采用改进的WM算法进行入侵判断。利用新墨西哥大学提供的仿真数据进行了实验测试,实验表明,本文提出的入侵检测模型能够有效降低模式库规模,提高入侵判断效率。
Intrusion Detection is a hot topic in network security in recent years, and is a kind of active measure of information assurance. The task of an Intrusion Detection System (IDS) is to monitor the running of the networks according to some pre-specified policy and try to find the intrusive activities.
This thesis firstly introduces the background and development of the research of Intrusion Detection, details the concept and theory of Intrusion Detection System. In this foundation, this thesis analyzes the technique of Intrusion Detection based on sequence of host system call. After research and compare these techniques of Intrusion Detection based on sequence of host system call, we point out that there biggest common shortcoming is to using fix-length system call sequence. To eliminate this drawback, we can use variable-length pattern method. In this thesis, Teiresias compound-pattern discover algorithm is used to find meaningful variable-length patterns in Intrusion Detection.
The high-performance pattern-matching algorithms can significantly improve the efficiency of intrusion detection. Based on the analysis of several more common pattern-matching algorithms, this thesis improves the multi-pattern matching algorithm of Wu-Manber (WM) using the thesis of Quick Search Algorithm (QS). In WM algorithm’s preprocess step, a Head table is newly added and this table can increase the shift distance of WM algorithm. Experiment shows that the improved WM algorithm can effectively reduce the number of matching step to improve the efficiency of pattern matching.
We design a host-based intrusion detection model under UNIX OS using variable-length system call patterns. In the model, data collection module, pattern extraction module and detection module are designed and implemented. In data collection module, the technique of LKM is used to collect the system call sequence invoked by process. A variable-length patterns extracting approach based on Teiresias algorithm is adopted to model the normal program behavior. In detection module, the improved WM algorithm is applied to implement variable-length pattern matching. In the paper, we make an experiment using the emulational data provided by the University of New Mexico. The result of the experiment indicates that the intrusion detection module can effectively reduce the size of normal program behavior patterns and improve the efficiency of the intrusion detection.
本文首先陈述了入侵检测的研究背景和发展,以及入侵检测系统(IDS)的概念、原理和分类。其次,重点分析了基于系统调用的入侵检测方法。本文针对目前各种基于系统调用的入侵检测技术进行了研究与比较,指出现有算法的不足之处:采用固定长度的系统调用序列。为克服不足之处,本文采用变长的系统调用序列检测方法,将Teiresias组合模式发现算法,这一典型的变长模式生成算法应用到系统调用入侵检测中。
高效的模式匹配算法能够显著提高入侵检测效率。本文在分析了几个常用多模式匹配算法的基础上,根据理论[32]指导对Wu-Manber算法进行了改进,结合了Quick-Search匹配算法的思想,在预处理阶段构造了一个Head表,增加了WM算法的跳转距离,实验表明改进算法可以有效地减小匹配步数,提高匹配效率。
最后,在Unix环境中构建了一个基于变长系统调用序列模式的入侵检测模型,设计并实现了数据收集模块、正常行为模式建立模块、检测模块。在数据收集模块中,采用LKM技术收集程序执行的系统调用序列。模式抽取模块采用基于Teiresias算法的变长模式抽取方法构建程序正常行为模式库。检测模块采用改进的WM算法进行入侵判断。利用新墨西哥大学提供的仿真数据进行了实验测试,实验表明,本文提出的入侵检测模型能够有效降低模式库规模,提高入侵判断效率。
Intrusion Detection is a hot topic in network security in recent years, and is a kind of active measure of information assurance. The task of an Intrusion Detection System (IDS) is to monitor the running of the networks according to some pre-specified policy and try to find the intrusive activities.
This thesis firstly introduces the background and development of the research of Intrusion Detection, details the concept and theory of Intrusion Detection System. In this foundation, this thesis analyzes the technique of Intrusion Detection based on sequence of host system call. After research and compare these techniques of Intrusion Detection based on sequence of host system call, we point out that there biggest common shortcoming is to using fix-length system call sequence. To eliminate this drawback, we can use variable-length pattern method. In this thesis, Teiresias compound-pattern discover algorithm is used to find meaningful variable-length patterns in Intrusion Detection.
The high-performance pattern-matching algorithms can significantly improve the efficiency of intrusion detection. Based on the analysis of several more common pattern-matching algorithms, this thesis improves the multi-pattern matching algorithm of Wu-Manber (WM) using the thesis of Quick Search Algorithm (QS). In WM algorithm’s preprocess step, a Head table is newly added and this table can increase the shift distance of WM algorithm. Experiment shows that the improved WM algorithm can effectively reduce the number of matching step to improve the efficiency of pattern matching.
We design a host-based intrusion detection model under UNIX OS using variable-length system call patterns. In the model, data collection module, pattern extraction module and detection module are designed and implemented. In data collection module, the technique of LKM is used to collect the system call sequence invoked by process. A variable-length patterns extracting approach based on Teiresias algorithm is adopted to model the normal program behavior. In detection module, the improved WM algorithm is applied to implement variable-length pattern matching. In the paper, we make an experiment using the emulational data provided by the University of New Mexico. The result of the experiment indicates that the intrusion detection module can effectively reduce the size of normal program behavior patterns and improve the efficiency of the intrusion detection.
引文
[1]冯登国.国内外信息安全研究现状及其发展趋势.Availabe from: http://www.netexpert.cn/2008, 2008.
[2] Garuba. M, Chunmei Liu, Fraites.D.Intrusion Techniques: Comparative Study of Network Intrusion Detection Systems.Information Technology: New Generation, ITNG 2008.Fifth International Conference,2008,592～598.
[3]罗广春,张骏等.入侵检测系统的历史、现状与研究进展.计算机应用研究,2003, No8.
[4]金波,吴咏炜,邹淳.入侵检测技术综述.计算机应用.2003.3.
[5] J.Ross Quinlan.C4.5:Programs for Machine Learning,Morgan Kaufmann, Morgan Kaufmann Publishers Inc.1993:1～302.
[6]唐正军,李建华.入侵检测技术.北京:清华大学出版社.2004:5～38.
[7] CIDF working group. The Common Intrusion Detection Framework Architecture, Availabe from:http://www.isi.edu/gost/cidf/drafts/architecture.txt.1998.
[8] Biswanath, Mukher jee, L.Todd Heberlein, and et al.Network Intrusion Detection. IEEE Network, 1994.
[9] Animesh Patcha, Jung-Min Park. An overview of anomaly detection techniques: Existing solutions and latest technological trends, Aug. 2007 Computer Networks: The International Journal of Computer and Telecommunications Networking卷次: 51刊期: 12. 2007.
[10]蒋建春,冯登国.网络入侵检测原理与技术.北京:国防工业出版社, 2007:25～27.
[11]唐正军.入侵检测技术导论.北京:机械工业出版社, 13～135, 2004.
[12]Stafford EH, Zamboni D. Intrusion Detection using Autonomous Agents. Computer Networks, 2000, 34(4):547～570.
[13]Feiertag R, Rho S, Benzinger L, et al. Intrusion Detection Inter-Component Adaptive Negotiation. Computer Networks. 2000, 34(4):605～621.
[14]Manganaris S, Christensen M, Zerkle D, et al. A Data Mining Analysis of R-TID alarms. Computer Networks. 2000, 34(4): 571～577.
[15]刘泉涌.基于系统调用的异常入侵检测系统研究,[硕士学位论文],武汉:武汉理工大学,2006.
[16]Peng Xingguang, Zhang Zhirong, Wang Zheng. Anomaly Detection of Privileged ProgramBased on Fuzzy Segments. IEEE Workshop on Cooperative Computing,Internetworking, and Assurance, IEEE Computer Society Press, 2005:580～584.
[17]Christina Warrender, Stephanie Forrest. Detecting Intrusion Using System Calls: Alternative Data Models. IEEE, 1999.
[18]Eugene H.Spafford, Diego Zamboni. Intrusion detection using autonomous agents. Computer Networks, 2000, (34):547～570.
[19]Marina Bykova, Shawn Ostermann, Brett Tjaden. Detecting Network Intrusions via a Statistical Analysis of Network Packet Characteristics. IEEE, 2001.
[20]M.Damashek. Gauging similarity with n-grams:Language-independent categorization of text. Science, 2005, 34(3):185～191.
[21]P.Helman, J.Bhangoo. A statistically based system for prioritizing information exploration under uncertainty. IEEE Transactions on Systems, 7, 1997.
[22]S.A.Hofmeyr, S.Forrest, A.Somayaji. Intrusion detection using sequences of system calls. Journal of Computer Security, 2006, 25(8):38～42.
[23]Yoshinori Okazaki, Shigeki Goto. A New Intrusion Detection Method based on Process Profiling. Applications and the Internet, 2002, (SAINT 2002), Proceedings, 2002 : 82～90.
[24]Anup K. Ghosh, Aaron Schwartzbard. Learning Program Behavior Profiles for Intrusion Detection. Proceedings of the Workshop on Intrusion Detection and Network Monitoring,1999.
[25]Daniel J. Ragsdale. Adaptation Techniques for Intrusion Detection and Intrusion Response Systems. Proceedings of the IEEE International Conference on Systems, 2000: 2344～2349.
[26]Sandeep Kumar, Eugene Spafford. A Pattern Matching Model for Misuse Intrusion Detection. Proceedings of the 17th National Computer Security Conference, 1995: 11～21.
[27]Aho AV, Corasick MJ. Efficient string matching: an aid to bibliographic search, Communications of the ACM 18,1975:330～340.
[28]Commentz-Walter B. A string matching algorithm fast on the average. Proc. 6th International Colloquium on Automata, Language, and Programming, 1979:118～32.
[29]Sun Wu, Udi Manber. A Fast Algorithm For Multi-Pattern Searching. Technical Report TR 94-17, University of Arizona at Tuscon, May 1994.
[30]Donald E. Knuth, James, H.Morris, Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal On Computing, 1997, 6(2):323～350.
[31]Boyer RS, Moore JS. A fast string searching algorithm. Communications of the ACM20, 1977, 762～772.
[32]Sunday DM. A very fast substring search algorithm. Communications of the ACM, 1990, 33(8):132-142.
[33]Yang Dong hong, Xu Ke, Cui Yong. An improved Wu-Manber multiple patterns matching algorithm. Performance, Computing, and Communications Conference, 2006. IPCCC 2006. 25th IEEE International. 10-12 Page(s):6 pp.– 680, April, 2006.
[34]Bruce W Watson. The performance of single-keyword and multiple-keyword pattern matching algorithms. Eindhoven University of Technology, Eindhoven, the Netherlands, Tech Rep: 94(19), 1994.
[35]Udi Manber. AGREP, an approximate GREP. Availabe from: http://www.tgries.de/agrep, 2005.
[36]http://www.c114.net/technic/technicread.asp?articleid=5755&boardcode=test.
[37]http://www.cs.unm.edu/~immsec/data-sets.html.
[38]Andreas Wespi, Marc Dacier, and Herve Debar. An Intrusion-Detection System Based on the Teiresias Pattern-Discovery Algorithm. EICAR Proceedings, 1999.
[39]A.P Kosoresow, S.A.Hofmeyr. Intrusion detection via system call traces. IEEE Software, 1997.
[40]Byung-joo Kim, Il-kon Kim. Kernel based intrusion detection system. Computer and Information Science, 2005. Fourth Annual ACIS International Conference on 2005,pp.13～18, 2005.
[41]John FuscoSep. Ten handy commands every Linux developer should know, 2004,125.
[42]Greg Herlein. The Linux Telephony Kernel API. Linux Journal, 2001, 25(5).
[43]Joao B. D. Cabrera, Lundy Lewis, Raman K, et al. Detection and classification of intrusions and faults using sequences of system calls. Dec. 2001 ACM SIGMOD Record, 2001,30(4).
[44]PZhuowei Li, PAmitabha Das. Analyzing and evaluating dynamics in stide performance for intrusion detection. Knowledge-Based Systems, 2006, 19(7):135～139.
[45]A.P.Kosoresow, S.A.Hofmeyr. A shape of self for unix process. IEEE Software, 1997, 14(5):35～42.
[46]Jiwei Li, Xianghua Zhang, Chun Yuan, et al. Motif Extraction with Indicative Events for System Call Sequence Classification. Fuzzy Systems and Knowledge Discovery, Fourth International Conference, 2007, 3(24):611～616.
[47]Pnevmatikatos.D,Arelakis. A. Variable-Length Hashing for Exact Pattern Matching. Field Programmable Logic and Applications, 2006. FPL '06. International Conference, 2006:1～6.
[48]Seungyong Yoon, Byoungkoo Kim, Jintae Oh. High-Performance Stateful Intrusion Detection System. Computational Intelligence and Security, 2006 International Conference, 2006, 1(12):574～579.
[49]Garuba.M, Chunmei Liu, Fraites, D. Intrusion Techniques: Comparative Study of Network Intrusion Detection Systems. Information Technology: New Generations, 2008. ITNG 2008. Fifth International Conference, 2008:592～598.
[50]Jing-Sheng Xue, Ji-Zhou Sun, Xu Zhang. Summary: Organizations require security systems that are flexible and adaptable in order to combat increasing threats from software vulnerabilities, virus attacks and other malicious code, in addition to internal attacks. Machine Learning and Cybernetics, Proceedings of 2004 International Conferencen,5,2004:2676～2679.
[51]Dash, S.K, Rawat, S, Pujari, A.K. LLE on System Calls for Host Based Intrusion Detection, Computational Intelligence and Security, 2006 International Conference on (1) , 2006:609～612.
[52]Maggi, F., Matteucci, M., Zanero, S. Detecting Intrusions through System Call Sequence and Argument Analysis, Dependable and Secure Computing, IEEE Transactions on : Accepted for future publication, 2003:505～507.
[53]Herve Debar, Marc Dacier, Andreas Wespi, and Stefan Lampart. A workbench for intrusion detection systems. Technical Report RZ 6519, IBM Zurich Research Laboratory, Saumerstrase 4, CH-8803 Ruschlikon, Switzerland, March, 111,121, 122,124, 1998.
[2] Garuba. M, Chunmei Liu, Fraites.D.Intrusion Techniques: Comparative Study of Network Intrusion Detection Systems.Information Technology: New Generation, ITNG 2008.Fifth International Conference,2008,592～598.
[3]罗广春,张骏等.入侵检测系统的历史、现状与研究进展.计算机应用研究,2003, No8.
[4]金波,吴咏炜,邹淳.入侵检测技术综述.计算机应用.2003.3.
[5] J.Ross Quinlan.C4.5:Programs for Machine Learning,Morgan Kaufmann, Morgan Kaufmann Publishers Inc.1993:1～302.
[6]唐正军,李建华.入侵检测技术.北京:清华大学出版社.2004:5～38.
[7] CIDF working group. The Common Intrusion Detection Framework Architecture, Availabe from:http://www.isi.edu/gost/cidf/drafts/architecture.txt.1998.
[8] Biswanath, Mukher jee, L.Todd Heberlein, and et al.Network Intrusion Detection. IEEE Network, 1994.
[9] Animesh Patcha, Jung-Min Park. An overview of anomaly detection techniques: Existing solutions and latest technological trends, Aug. 2007 Computer Networks: The International Journal of Computer and Telecommunications Networking卷次: 51刊期: 12. 2007.
[10]蒋建春,冯登国.网络入侵检测原理与技术.北京:国防工业出版社, 2007:25～27.
[11]唐正军.入侵检测技术导论.北京:机械工业出版社, 13～135, 2004.
[12]Stafford EH, Zamboni D. Intrusion Detection using Autonomous Agents. Computer Networks, 2000, 34(4):547～570.
[13]Feiertag R, Rho S, Benzinger L, et al. Intrusion Detection Inter-Component Adaptive Negotiation. Computer Networks. 2000, 34(4):605～621.
[14]Manganaris S, Christensen M, Zerkle D, et al. A Data Mining Analysis of R-TID alarms. Computer Networks. 2000, 34(4): 571～577.
[15]刘泉涌.基于系统调用的异常入侵检测系统研究,[硕士学位论文],武汉:武汉理工大学,2006.
[16]Peng Xingguang, Zhang Zhirong, Wang Zheng. Anomaly Detection of Privileged ProgramBased on Fuzzy Segments. IEEE Workshop on Cooperative Computing,Internetworking, and Assurance, IEEE Computer Society Press, 2005:580～584.
[17]Christina Warrender, Stephanie Forrest. Detecting Intrusion Using System Calls: Alternative Data Models. IEEE, 1999.
[18]Eugene H.Spafford, Diego Zamboni. Intrusion detection using autonomous agents. Computer Networks, 2000, (34):547～570.
[19]Marina Bykova, Shawn Ostermann, Brett Tjaden. Detecting Network Intrusions via a Statistical Analysis of Network Packet Characteristics. IEEE, 2001.
[20]M.Damashek. Gauging similarity with n-grams:Language-independent categorization of text. Science, 2005, 34(3):185～191.
[21]P.Helman, J.Bhangoo. A statistically based system for prioritizing information exploration under uncertainty. IEEE Transactions on Systems, 7, 1997.
[22]S.A.Hofmeyr, S.Forrest, A.Somayaji. Intrusion detection using sequences of system calls. Journal of Computer Security, 2006, 25(8):38～42.
[23]Yoshinori Okazaki, Shigeki Goto. A New Intrusion Detection Method based on Process Profiling. Applications and the Internet, 2002, (SAINT 2002), Proceedings, 2002 : 82～90.
[24]Anup K. Ghosh, Aaron Schwartzbard. Learning Program Behavior Profiles for Intrusion Detection. Proceedings of the Workshop on Intrusion Detection and Network Monitoring,1999.
[25]Daniel J. Ragsdale. Adaptation Techniques for Intrusion Detection and Intrusion Response Systems. Proceedings of the IEEE International Conference on Systems, 2000: 2344～2349.
[26]Sandeep Kumar, Eugene Spafford. A Pattern Matching Model for Misuse Intrusion Detection. Proceedings of the 17th National Computer Security Conference, 1995: 11～21.
[27]Aho AV, Corasick MJ. Efficient string matching: an aid to bibliographic search, Communications of the ACM 18,1975:330～340.
[28]Commentz-Walter B. A string matching algorithm fast on the average. Proc. 6th International Colloquium on Automata, Language, and Programming, 1979:118～32.
[29]Sun Wu, Udi Manber. A Fast Algorithm For Multi-Pattern Searching. Technical Report TR 94-17, University of Arizona at Tuscon, May 1994.
[30]Donald E. Knuth, James, H.Morris, Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal On Computing, 1997, 6(2):323～350.
[31]Boyer RS, Moore JS. A fast string searching algorithm. Communications of the ACM20, 1977, 762～772.
[32]Sunday DM. A very fast substring search algorithm. Communications of the ACM, 1990, 33(8):132-142.
[33]Yang Dong hong, Xu Ke, Cui Yong. An improved Wu-Manber multiple patterns matching algorithm. Performance, Computing, and Communications Conference, 2006. IPCCC 2006. 25th IEEE International. 10-12 Page(s):6 pp.– 680, April, 2006.
[34]Bruce W Watson. The performance of single-keyword and multiple-keyword pattern matching algorithms. Eindhoven University of Technology, Eindhoven, the Netherlands, Tech Rep: 94(19), 1994.
[35]Udi Manber. AGREP, an approximate GREP. Availabe from: http://www.tgries.de/agrep, 2005.
[36]http://www.c114.net/technic/technicread.asp?articleid=5755&boardcode=test.
[37]http://www.cs.unm.edu/~immsec/data-sets.html.
[38]Andreas Wespi, Marc Dacier, and Herve Debar. An Intrusion-Detection System Based on the Teiresias Pattern-Discovery Algorithm. EICAR Proceedings, 1999.
[39]A.P Kosoresow, S.A.Hofmeyr. Intrusion detection via system call traces. IEEE Software, 1997.
[40]Byung-joo Kim, Il-kon Kim. Kernel based intrusion detection system. Computer and Information Science, 2005. Fourth Annual ACIS International Conference on 2005,pp.13～18, 2005.
[41]John FuscoSep. Ten handy commands every Linux developer should know, 2004,125.
[42]Greg Herlein. The Linux Telephony Kernel API. Linux Journal, 2001, 25(5).
[43]Joao B. D. Cabrera, Lundy Lewis, Raman K, et al. Detection and classification of intrusions and faults using sequences of system calls. Dec. 2001 ACM SIGMOD Record, 2001,30(4).
[44]PZhuowei Li, PAmitabha Das. Analyzing and evaluating dynamics in stide performance for intrusion detection. Knowledge-Based Systems, 2006, 19(7):135～139.
[45]A.P.Kosoresow, S.A.Hofmeyr. A shape of self for unix process. IEEE Software, 1997, 14(5):35～42.
[46]Jiwei Li, Xianghua Zhang, Chun Yuan, et al. Motif Extraction with Indicative Events for System Call Sequence Classification. Fuzzy Systems and Knowledge Discovery, Fourth International Conference, 2007, 3(24):611～616.
[47]Pnevmatikatos.D,Arelakis. A. Variable-Length Hashing for Exact Pattern Matching. Field Programmable Logic and Applications, 2006. FPL '06. International Conference, 2006:1～6.
[48]Seungyong Yoon, Byoungkoo Kim, Jintae Oh. High-Performance Stateful Intrusion Detection System. Computational Intelligence and Security, 2006 International Conference, 2006, 1(12):574～579.
[49]Garuba.M, Chunmei Liu, Fraites, D. Intrusion Techniques: Comparative Study of Network Intrusion Detection Systems. Information Technology: New Generations, 2008. ITNG 2008. Fifth International Conference, 2008:592～598.
[50]Jing-Sheng Xue, Ji-Zhou Sun, Xu Zhang. Summary: Organizations require security systems that are flexible and adaptable in order to combat increasing threats from software vulnerabilities, virus attacks and other malicious code, in addition to internal attacks. Machine Learning and Cybernetics, Proceedings of 2004 International Conferencen,5,2004:2676～2679.
[51]Dash, S.K, Rawat, S, Pujari, A.K. LLE on System Calls for Host Based Intrusion Detection, Computational Intelligence and Security, 2006 International Conference on (1) , 2006:609～612.
[52]Maggi, F., Matteucci, M., Zanero, S. Detecting Intrusions through System Call Sequence and Argument Analysis, Dependable and Secure Computing, IEEE Transactions on : Accepted for future publication, 2003:505～507.
[53]Herve Debar, Marc Dacier, Andreas Wespi, and Stefan Lampart. A workbench for intrusion detection systems. Technical Report RZ 6519, IBM Zurich Research Laboratory, Saumerstrase 4, CH-8803 Ruschlikon, Switzerland, March, 111,121, 122,124, 1998.