基于新型否定选择算法的计算机病毒检测技术研究
|
摘要
计算机病毒检测系统是一种防护网络安全的系统,是被用来检测威胁或危害主机和计算机网络的代码。生物免疫系统是保护生物机体免受外部病原体危害的一种机制,其具有分布式并行处理、自组织、免疫记忆和鲁棒性等特性。传统的计算机病毒检测技术是一种被动防御技术,借鉴生物免疫系统与计算机病毒检测系统相似性,来提高病毒检测系统的性能。
本文详细的分析了传统否定选择算法所存在的问题,并介绍了学者们在这些方面所作的改进和努力。根据切割空间生成检测器的算法原理,提出一种针对二进制串的新型的切割否定选择算法,此算法不仅可消除冗余的检测器,并可减少检测器的漏洞,还在一定程度上防止黑洞形成；引入树状层次管理机制和禁忌搜索策略思想,在基于新型否定选择算法生成庞大的检测器的基础上,提出了一种将禁忌搜索算法与人工免疫算法相结合的新型禁忌人工免疫网络算法,在很大的程度上提高了检测器的搜索效率,更新效率,节省了内存占用率,此算法全局收敛性可以达到最优；最后本文针对所选用的数据集数据,通过分析数据进行试验和测试,测试表明新型否定选择算法具有更高的检测效率,准确性和搜索速率。本文的主要工作如下：
1)分析传统否定选择算法和计算机病毒检测技术所存在的问题,总结诸多学者在这方面的改进方案和实施方法。
2)根据切割空间的否定选择算法,提出一种应用于二进制生成串检测器的新型的切割否定选择算法(Cutting Negative Selection Algorithm, CNSA),此算法生成的检测器有效的减少了检测漏洞,消除冗余的检测器,并通过递增阈值减少检测器存在的黑洞,使系统只需少量的检测器即可检测出较全面的非自体检测器。
3)结合树状层次模型和禁忌搜索算法,提出一种新型的禁忌人工免疫网络算法,通过设置匹配迭代次数T的阈值,对检测器施行禁忌表、记忆表和进化方向表之间的调度,通过对各个表里的检测器进行亲和力大小的排序,抑制检测器的个数,提高检测器的有效利用率和减少内存占用率。
4)选取数据集,对数据进行实验和分析,来对算法进行验证,最后建立基于新型否定选择算法的计算机病毒检测系统,并进行性能分析。
Computer virus detection system is a network security system to be used to detect threats or hazards to the host and the computer network code, Biological immune system is a mechanism to protect living organisms from harmful external pathogens, which has distributed parallel processing, self-organization, immune memory and robustness properties, Traditional computer virus detection technology is a passive defense technology, based on the immune system and computer virus detection system similarity, So we learn from the immune system theory to improve virus detection performance.
This paper analyses the problems of the traditional negative selection algorithm, and introduced improvement and effort in these areas, Based on a cutting space negative selection algorithm, proposes a kind of a new cut negative selection algorithm which is used to detecting the binary string, this algorithm can eliminate redundant detectors, reduce the detector vulnerability, but also to some extent prevent the black hole; we also introduce the principles of the tree-level management system and tabu search strategy, this paper presents a new taboo artificial immune network algorithm which combinations of the tabu search algorithm and the artificial immune algorithm combines, to improve the detection search speed, update efficiency, saving the memory, this algorithm can achieve optimal global convergence; Finally, we analyses the selected data sets which selected from KDDCUP99 and tests show that the new negative selection algorithm has a higher detection efficiency, accuracy of detection and search speed, The main work of this paper is as follows,
1) This paper analyzes the problems of the traditional negative selection and the computer virus detection technology, and concluded the improvements and implementation methods in the areas.
2) According to the cutting space negative selection algorithm, we presents a new cutting negative selection algorithm (CNSA) which is applied to the binary string detector generates, this algorithm improves detector effectively reduce the detection loopholes, and eliminate the redundant detectors, reduce the existence of black holes detector, the system only a small number of selfsets can detect a more comprehensive non-self-detector.
3) Based on the combination of the tree-level model and the tabu search algorithm, we design a new kind of taboo artificial immune network algorithm, By setting the threshold T, the detectors can transform between tables which are the taboo table, the memory table and the evolutionary table, According to the sort of the detector affinity, which can inhibit the number of detectors to improve the detector efficiency and reduce the effective memory utilization.
4) Screening the data sets, analyzing data, we can select data to validate the algorithm, and finally the paper design a new computer virus detection system based on the cutting negative selection algorithm, and analyzes the performance of the model.
本文详细的分析了传统否定选择算法所存在的问题,并介绍了学者们在这些方面所作的改进和努力。根据切割空间生成检测器的算法原理,提出一种针对二进制串的新型的切割否定选择算法,此算法不仅可消除冗余的检测器,并可减少检测器的漏洞,还在一定程度上防止黑洞形成；引入树状层次管理机制和禁忌搜索策略思想,在基于新型否定选择算法生成庞大的检测器的基础上,提出了一种将禁忌搜索算法与人工免疫算法相结合的新型禁忌人工免疫网络算法,在很大的程度上提高了检测器的搜索效率,更新效率,节省了内存占用率,此算法全局收敛性可以达到最优；最后本文针对所选用的数据集数据,通过分析数据进行试验和测试,测试表明新型否定选择算法具有更高的检测效率,准确性和搜索速率。本文的主要工作如下：
1)分析传统否定选择算法和计算机病毒检测技术所存在的问题,总结诸多学者在这方面的改进方案和实施方法。
2)根据切割空间的否定选择算法,提出一种应用于二进制生成串检测器的新型的切割否定选择算法(Cutting Negative Selection Algorithm, CNSA),此算法生成的检测器有效的减少了检测漏洞,消除冗余的检测器,并通过递增阈值减少检测器存在的黑洞,使系统只需少量的检测器即可检测出较全面的非自体检测器。
3)结合树状层次模型和禁忌搜索算法,提出一种新型的禁忌人工免疫网络算法,通过设置匹配迭代次数T的阈值,对检测器施行禁忌表、记忆表和进化方向表之间的调度,通过对各个表里的检测器进行亲和力大小的排序,抑制检测器的个数,提高检测器的有效利用率和减少内存占用率。
4)选取数据集,对数据进行实验和分析,来对算法进行验证,最后建立基于新型否定选择算法的计算机病毒检测系统,并进行性能分析。
Computer virus detection system is a network security system to be used to detect threats or hazards to the host and the computer network code, Biological immune system is a mechanism to protect living organisms from harmful external pathogens, which has distributed parallel processing, self-organization, immune memory and robustness properties, Traditional computer virus detection technology is a passive defense technology, based on the immune system and computer virus detection system similarity, So we learn from the immune system theory to improve virus detection performance.
This paper analyses the problems of the traditional negative selection algorithm, and introduced improvement and effort in these areas, Based on a cutting space negative selection algorithm, proposes a kind of a new cut negative selection algorithm which is used to detecting the binary string, this algorithm can eliminate redundant detectors, reduce the detector vulnerability, but also to some extent prevent the black hole; we also introduce the principles of the tree-level management system and tabu search strategy, this paper presents a new taboo artificial immune network algorithm which combinations of the tabu search algorithm and the artificial immune algorithm combines, to improve the detection search speed, update efficiency, saving the memory, this algorithm can achieve optimal global convergence; Finally, we analyses the selected data sets which selected from KDDCUP99 and tests show that the new negative selection algorithm has a higher detection efficiency, accuracy of detection and search speed, The main work of this paper is as follows,
1) This paper analyzes the problems of the traditional negative selection and the computer virus detection technology, and concluded the improvements and implementation methods in the areas.
2) According to the cutting space negative selection algorithm, we presents a new cutting negative selection algorithm (CNSA) which is applied to the binary string detector generates, this algorithm improves detector effectively reduce the detection loopholes, and eliminate the redundant detectors, reduce the existence of black holes detector, the system only a small number of selfsets can detect a more comprehensive non-self-detector.
3) Based on the combination of the tree-level model and the tabu search algorithm, we design a new kind of taboo artificial immune network algorithm, By setting the threshold T, the detectors can transform between tables which are the taboo table, the memory table and the evolutionary table, According to the sort of the detector affinity, which can inhibit the number of detectors to improve the detector efficiency and reduce the effective memory utilization.
4) Screening the data sets, analyzing data, we can select data to validate the algorithm, and finally the paper design a new computer virus detection system based on the cutting negative selection algorithm, and analyzes the performance of the model.
引文
[1]莫宏伟,左兴权,毕晓君,人工免疫系统研究进展,智能系统学报,2009,4(1),22-29
[2]赵云丰,付冬梅,一种改进的人工免疫网络优化算法及其性能分析,自然科学进展,2009,19(4),434-445
[3]孙勇智,人工免疫系统模型、算法及其应用研究,[博士论文],浙江大学,2004,3-20
[4]姜恩龙,张凤斌,杨洋,刘悦,基于海明匹配的r连续位匹配规则的研究,哈尔滨理工大学学报,2007,12(5),91-93
[5]李江涛,基于行为的病毒检测系统,北京交通大学(硕士学位论文),2008年,
[6]Bingje Zhao, Fuxiong Sun, Wei Xie, The Research of Generation Algorithm of Detectors in Immune-based Detection Model, International Symposium on Knowledge Acquisition and Modeling,2008 IEEE, pp,693-697
[7]Jinquan Zeng, Tao Li, Xiaojie Liu, A Feedback Negative Selection Algorithm to Anomaly Detection, Third International Conference on Natural Computation(ICNC 2007),2007 IEEE, pp,575-579
[8]张波云,殷建平,张鼎兴等,基于集成神经网络的计算机病毒检测方法,计算机工程与应用,2007,43(13),26-29
[9]赖英旭,刘增辉,基于关联规则的未知病毒检测方法研究,计算机工程与应用,2008,44(7),33-35
[10]Uwe Aickelin, Steve Cayzer, The Danger Theory and Its Application to Artificial Immune Systems, Proceedings of the 1st Internat Conference on ARtificial Immune Systems,2002,pp,141-148
[11]Tom Morrison, Uwe Aickelin, An Artificial Immune System as a Recommender for Web Sites, Proceedings of the 1st Internal Conference on ARtificial Immune Systems, 2002,pp,161-169
[12]张宇,人工免疫系统中阴性选择算法的研究,浙江大学(硕士学位论文),2007年5月
[13]罗一丹,蔡自兴,王勇,江中央,基于免疫重构的阴性选择算法,计算机科学,2008,35(3),149-151
[14]X,Z,Gao,S,J,Ovaska,and X,Wang,"Genetic Algorithms-based Detector Generation in Negative Selection Algorithm, "Adaptive and Learning Systems,2006 IEEE Mountain Workshop on, pp,133-137,2006
[15]郭振河,谭营,刘政凯,基于阴性选择原则的non-self探测器生成算法,小型微型计算机系统,2005,26(6),959-964
[16]Renchao Qin, Tao Li, Yu Zhang, An Immunity based Computer Virus Detection Method with GA-RVNS, Second International Symposium on Intelligent Information Technology Application,2008 IEEE,pp,864-868
[17]张清华,钱宇,胥布工,高廷玉等,采用在自己空间变异搜索来训练检测器的阴性选择算法,计算机应用,2007年第3期
[18]张清华,钱宇,胥布工,高廷玉等,一种采用非己空间变异搜索的故障检测算法,计算机工程与应用,2007年43卷(28期)
[19]Qian Wang,Xiao-kai Feng, A Detector Generation Algorithm Based on Negative Selection,Fourth International Conference on National Computation,2008 IEEE,pp,605-611
[20]Yufeng Zhao,Dongmei Fu, An improved artificial immune network optimization algorithm and its performance analysis,2009,19(4),434-445
[21]仲巍,新型否定选择算法的研究,江苏大学(硕士学位论文),2008年6月
[22]B,Sankalp,"Multi-shaped Detector generation usingReal-valued representation for Anomaly Detection,"Masters Thesis,Univ,Memphis,2005
[23]Andrew Watkins, Jon Timmis, Exploiting Parallelism Inherent in AIRS, an Artificial Immune Classifier, ICARIS 2004,LNCS 3239,pp,427-438
[24]叶尔骅,张德平,概率论与随机过程,北京,科学出版社,2005,78-103
[25]黄席樾,张著洪,何传江,等,现代智能算法理论及应用,北京,科学出版社,2005,125-153
[26]Zhang Qing-hua, Shao Long-qiu, Zhang Ya-she, Design of Unit Fault Diagnosis System Software Based on Artificial Immune System,2008 International Conference on Computer Science and Software Engineering,2008 IEEE, pp,431-435
[27]Zhang Qing-Hua,Qian Yu,Xu Bu-Gong et al,Application study of non-dimension-parameter to fault diagnosis technology in artificial immune system[J],Noise and Vibration Control,2008(01)
[28]姜恩龙,基于否定选择的检测器生成算法研究,哈尔滨理工大学(硕士学位论文),2007年,
[29]王占锋,基于动态克隆选择的入侵检测研究,哈尔滨工业大学(硕士学位论文),2006年,
[30]罗印升,李人厚,张维玺,基于免疫机理的多峰值函数并行优化算法,系统仿真学报,2005,17(2),319-322
[31]庄健,王娜,杜海峰,等,一种模糊人工免疫网络故障诊断策略,自然科学进展,2007,17(11),1544-1553
[32]罗一丹,蔡自兴,王勇,江中央,基于免疫重构的阴性选择算法,计算机科学,2008,35(3),149-151
[33]付玉珍,自适应免疫网络入侵检测模型的应用与研究,太原理工大学(硕士学位论文),2008年
[34]秦晓倩,基于蜜罐的免疫病毒检测模型的设计,计算机工程与设计,2008,29(20),5184-5189
[35]程永新,基于免疫原理的新型入侵检测模型及算法研究,电子科技大学(硕士学位论文),2006
[36]刘辉,张凤斌,一种改进的基于否定选择的检测器生成算法,哈尔滨理工大学学报,2008年8月
[37]KDD Cup 1999 Data. Irvine,CA 92697-3425, Information and Computer Science,University of California(USA),Irivine,http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
[38]焦李成等,免疫优化计算,学习与识别[M],北京,科学出版社,2006,96-101
[39]李涛,计算机免疫学[M],北京,电子工业出版社,2004 59-62
[40]莫宏伟,人工免疫系统原理与应用,哈尔滨,哈尔滨工业大学出版社,2002
[2]赵云丰,付冬梅,一种改进的人工免疫网络优化算法及其性能分析,自然科学进展,2009,19(4),434-445
[3]孙勇智,人工免疫系统模型、算法及其应用研究,[博士论文],浙江大学,2004,3-20
[4]姜恩龙,张凤斌,杨洋,刘悦,基于海明匹配的r连续位匹配规则的研究,哈尔滨理工大学学报,2007,12(5),91-93
[5]李江涛,基于行为的病毒检测系统,北京交通大学(硕士学位论文),2008年,
[6]Bingje Zhao, Fuxiong Sun, Wei Xie, The Research of Generation Algorithm of Detectors in Immune-based Detection Model, International Symposium on Knowledge Acquisition and Modeling,2008 IEEE, pp,693-697
[7]Jinquan Zeng, Tao Li, Xiaojie Liu, A Feedback Negative Selection Algorithm to Anomaly Detection, Third International Conference on Natural Computation(ICNC 2007),2007 IEEE, pp,575-579
[8]张波云,殷建平,张鼎兴等,基于集成神经网络的计算机病毒检测方法,计算机工程与应用,2007,43(13),26-29
[9]赖英旭,刘增辉,基于关联规则的未知病毒检测方法研究,计算机工程与应用,2008,44(7),33-35
[10]Uwe Aickelin, Steve Cayzer, The Danger Theory and Its Application to Artificial Immune Systems, Proceedings of the 1st Internat Conference on ARtificial Immune Systems,2002,pp,141-148
[11]Tom Morrison, Uwe Aickelin, An Artificial Immune System as a Recommender for Web Sites, Proceedings of the 1st Internal Conference on ARtificial Immune Systems, 2002,pp,161-169
[12]张宇,人工免疫系统中阴性选择算法的研究,浙江大学(硕士学位论文),2007年5月
[13]罗一丹,蔡自兴,王勇,江中央,基于免疫重构的阴性选择算法,计算机科学,2008,35(3),149-151
[14]X,Z,Gao,S,J,Ovaska,and X,Wang,"Genetic Algorithms-based Detector Generation in Negative Selection Algorithm, "Adaptive and Learning Systems,2006 IEEE Mountain Workshop on, pp,133-137,2006
[15]郭振河,谭营,刘政凯,基于阴性选择原则的non-self探测器生成算法,小型微型计算机系统,2005,26(6),959-964
[16]Renchao Qin, Tao Li, Yu Zhang, An Immunity based Computer Virus Detection Method with GA-RVNS, Second International Symposium on Intelligent Information Technology Application,2008 IEEE,pp,864-868
[17]张清华,钱宇,胥布工,高廷玉等,采用在自己空间变异搜索来训练检测器的阴性选择算法,计算机应用,2007年第3期
[18]张清华,钱宇,胥布工,高廷玉等,一种采用非己空间变异搜索的故障检测算法,计算机工程与应用,2007年43卷(28期)
[19]Qian Wang,Xiao-kai Feng, A Detector Generation Algorithm Based on Negative Selection,Fourth International Conference on National Computation,2008 IEEE,pp,605-611
[20]Yufeng Zhao,Dongmei Fu, An improved artificial immune network optimization algorithm and its performance analysis,2009,19(4),434-445
[21]仲巍,新型否定选择算法的研究,江苏大学(硕士学位论文),2008年6月
[22]B,Sankalp,"Multi-shaped Detector generation usingReal-valued representation for Anomaly Detection,"Masters Thesis,Univ,Memphis,2005
[23]Andrew Watkins, Jon Timmis, Exploiting Parallelism Inherent in AIRS, an Artificial Immune Classifier, ICARIS 2004,LNCS 3239,pp,427-438
[24]叶尔骅,张德平,概率论与随机过程,北京,科学出版社,2005,78-103
[25]黄席樾,张著洪,何传江,等,现代智能算法理论及应用,北京,科学出版社,2005,125-153
[26]Zhang Qing-hua, Shao Long-qiu, Zhang Ya-she, Design of Unit Fault Diagnosis System Software Based on Artificial Immune System,2008 International Conference on Computer Science and Software Engineering,2008 IEEE, pp,431-435
[27]Zhang Qing-Hua,Qian Yu,Xu Bu-Gong et al,Application study of non-dimension-parameter to fault diagnosis technology in artificial immune system[J],Noise and Vibration Control,2008(01)
[28]姜恩龙,基于否定选择的检测器生成算法研究,哈尔滨理工大学(硕士学位论文),2007年,
[29]王占锋,基于动态克隆选择的入侵检测研究,哈尔滨工业大学(硕士学位论文),2006年,
[30]罗印升,李人厚,张维玺,基于免疫机理的多峰值函数并行优化算法,系统仿真学报,2005,17(2),319-322
[31]庄健,王娜,杜海峰,等,一种模糊人工免疫网络故障诊断策略,自然科学进展,2007,17(11),1544-1553
[32]罗一丹,蔡自兴,王勇,江中央,基于免疫重构的阴性选择算法,计算机科学,2008,35(3),149-151
[33]付玉珍,自适应免疫网络入侵检测模型的应用与研究,太原理工大学(硕士学位论文),2008年
[34]秦晓倩,基于蜜罐的免疫病毒检测模型的设计,计算机工程与设计,2008,29(20),5184-5189
[35]程永新,基于免疫原理的新型入侵检测模型及算法研究,电子科技大学(硕士学位论文),2006
[36]刘辉,张凤斌,一种改进的基于否定选择的检测器生成算法,哈尔滨理工大学学报,2008年8月
[37]KDD Cup 1999 Data. Irvine,CA 92697-3425, Information and Computer Science,University of California(USA),Irivine,http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
[38]焦李成等,免疫优化计算,学习与识别[M],北京,科学出版社,2006,96-101
[39]李涛,计算机免疫学[M],北京,电子工业出版社,2004 59-62
[40]莫宏伟,人工免疫系统原理与应用,哈尔滨,哈尔滨工业大学出版社,2002