基于集合的划分与覆盖的计算机病毒检测研究

《基于集合的划分与覆盖的计算机病毒检测研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

分类号：密级： 分类号：密级：UDC：编号：河北工业大学硕士学位论文基于集合的划分与覆盖的计算机病毒检测研究论文作者：宋瑞平学生类别：全日制学科门类：工学学科专业：计算机应用技术指导教师：刘恩海职称：副教授 DissertationSubmittedtoHebeiUniversityofTechnologyforTheMasterDegreeofComputerAppliedTechnologyTHECOMPUTERVIRUSDETECTIONWHICHBASEDONTHECOLLECTIONRELATIONOFCLASSIFICATIONANDCOVERAGEBySongRuipingSupervisor:Prof.LiuEnhaiNovember2013 原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文不包含任何他人或集体已经发表的作品内容，也不包含本人为获得其他学位而使用过的材料。对本论文所涉及的研究工作做出贡献的其他个人或集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：日期：关于学位论文版权使用授权的说明本人完全了解河北工业大学关于收集、保存、使用学位论文的以下规定：学校有权采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供本学位论文全文或者部分内容的阅览服务；学校有权将学位论文的全部或部分内容编入有关数据库进行检索、交流；学校有权向国家有关部门或者机构送交论文的复印件和电子版。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：日期：导师签名：日期： 摘要计算机病毒检测一直是计算机安全领域的热点问题，原始的病毒防御方法早就不能达到计算机病毒实时检测的需求，鉴于计算机病毒检测与人工免疫系统的巨大相似性，模仿生物免疫系统成功护卫机体的机制，将人工免疫原理应用于计算机病毒检测，使病毒检测系统的性能得到提高。否定选择算法提出来以后，许多学者对病毒检测的原理和技术进行了深入的探寻，病毒检测领域取得了长足发展。否定选择算法的核心技术要素包括以下几个方面：数据和检测器的表示方法；字符串或向量空间的匹配规则的选择；检测器的生成机制；检测器的存储形式。而检测器的生成机制是病毒检测技术的核心问题。本文在深入分析了病毒检测技术的原理和方法后，重点对否定选择算法进行了深度剖析，从检测器的生成和漏洞检测方面进行了改进。针对现有的检测器生成机制存在大量冗余和时间损耗多的弊端，提出了一种基于集合间划分与覆盖关系的高性能检测器生成算法，提取出所有自体集合的以r为长短的段的补集合，在连接策略上进行改进，尽量达到集合的划分，产生能覆盖最大非自体空间的最小检测器集合，降低产生检测器时耗费的时间和检测器数量，扩大等量检测器的覆盖范围，提高检测效果。仿真实验验证了方法的检测效率和时间空间方面的优越性。任何一种匹配规则都不可避免的会产生检测漏洞，漏洞的存在严重影响了病毒检测算法的性能。提出了一种新的检测漏洞的方法，该方法利用改进算法的未被利用的补集和自体集的信息，此种方法能检测出全部的漏洞，漏洞集合具有完备性。创建了一个基于改进算法的计算机病毒免疫检测模型，用仿真实验对模型的性能进行了分析与对比。仿真结果表明基于改进否定选择算法算法的病毒检测模型对已知病毒，未知病毒和已知病毒的变种都具有较高的检测效果。关键字：人工免疫系统否定选择算法划分与覆盖漏洞检测病毒检测模型I ABSTRACTComputervirusdetectionhasbeenahotissueinthefieldofcomputersecurity.Traditionalvirusdetectiontechnologyhasbeenunabletomeetthedemandforreal-timedetectionofcomputerviruses.Computervirusdetectionissimilarwithartificialimmunesystem，simulatethemechanismsofthebiologicalimmunesystemwhichsuccessedinprotectthebody’ssuccess,maketheartificialimmuneprincipleappliedtocomputervirusdetection,toimprovetheperformanceofthevirusdetection.Sincethenegativeselectionalgorithmwasproposed,alargenumberofscholarshasmadedeepstudyonvirusdetectionprinciplesandtechniques，theareaofthevirusdetectionhasmadeconsiderableprogress.Thecoretechnologyelementsofthenegativeselectionalgorithmsincludethefollowingaspects:therepresentationofdataanddetector;thechoiceofmatchingrules;detectorgenerationmechanism;thestorageformofthedetector.Thegenerationmechanismofdetectoristhecoreissuetothevirusdetectiontechnology.Thispaperwasdeepanalyzedintheprinciplesandtechnologyofthevirusimmunedetection,focusingonthenegativeselectionalgorithmfordepthprofiling,improvedthemechanismofthedetectorgenerationandholedetection.Focusonthemalpracticeoftheexistingdetectionmechanisemswhichexistalotofredundantandtimeconsumingmuch,proposedahighperformancedetectorgeneratingalgorithmwhichisbasedonthecollectiondivisionandcoverage.Basedonthervaluesegmentationtoextracttheselfcollectionofcomplement,improvedtheconnectionstrategy，asfaraspossibletoachievethedivisionofthecollection，generatedtheminimumdetectorstocoverthelargestnonselfspace，decreasegenerationtimeofthedetector,reducethenumberofdetectors，expandthecoveragerangeofequalnumberofdetector，improvedthedetectionresults.Simulationresultsdemonstratetheefficiencyofdetectionandthetimeandspacesuperiority.Anykindofmatchingrulesareinevitablyproducedetectionholewhichhasseriousimpactontheperformanceofvirusdetectionalgorithm.Anewmethodsisproposedforthedetectionofhole,thismethodusedthecollectioninformationofcomplementandautologous,thismethodcandetectallthevulnerabilities，thecollectionoftheholeiscompleteness.Establishedacomputervirusdetectionmodelbasedontheimprovedvirusdetectionalgorithm,anduseexperimentstoverifiedtheperformanceofthemodel.Experimentalresultsshowthatthevirusdetectionmodelbasedonimprovedalgorithmforknownvirus，unknownandknownvirusesvariantshaveahighdetectionresults.KEYWORDS:artificialimmunesystemnegativeselectionalgorithmclassificationandcoverageholedetectionvirusdetectionmodelII 目目目目录录录录第一章绪论.................................................................................................................................11.1课题研究背景及意义..............................................................................................................11.2国内外研究状况......................................................................................................................21.3本文主要工作..........................................................................................................................41.4本文的组织与结构..................................................................................................................4第二章计算机病毒概述...............................................................................................................72.1计算机病毒知识简介..............................................................................................................72.1.1计算机病毒的定义........................................................................................................72.1.2计算机病毒的特征........................................................................................................72.1.3计算机病毒的工作原理................................................................................................82.1.4计算机病毒的分类........................................................................................................92.1.4.1按照链接方式分类...................................................................................................102.1.4.2按照传染原理进行分类...........................................................................................102.1.4.3按照病毒的破坏程度分类.......................................................................................112.2传统的病毒检测方法............................................................................................................112.3小结........................................................................................................................................13第三章人工免疫系统与计算机病毒检测研究.........................................................................153.1生物免疫系统概述................................................................................................................153.1.1生物免疫系统的功能..................................................................................................153.1.2生物免疫系统的层次结构..........................................................................................153.1.3免疫机制......................................................................................................................153.1.4生物免疫系统的特点..................................................................................................163.2人工免疫系统概述................................................................................................................173.3相关算法................................................................................................................................183.3.1否定选择算法..............................................................................................................193.3.2克隆选择算法..............................................................................................................193.3.3免疫网络算法..............................................................................................................203.4基于人工免疫的病毒检测研究............................................................................................213.5小结........................................................................................................................................22第四章基于集合的划分与覆盖的检测器生成算法研究.........................................................234.1否定选择算法综述................................................................................................................23III 4.1.1算法原理......................................................................................................................234.1.2否定选择算法的主要技术要点..................................................................................244.2基于集合的划分与覆盖的检测器生成算法研究................................................................264.2.1已有的检测器生成算法..............................................................................................264.2.2基于集合的划分与覆盖的检测器生成算法..............................................................274.2.3实验分析......................................................................................................................284.3漏洞研究................................................................................................................................304.3.1漏洞产生的原因..........................................................................................................304.3.2如何检测漏洞..............................................................................................................314.3.3一种新的检测漏洞的方法..........................................................................................324.3.3.1算法简介...................................................................................................................324.3.3.2复杂性分析...............................................................................................................344.3.3.3实验分析...................................................................................................................344.4本章小结................................................................................................................................35第五章实验与分析.....................................................................................................................375.1基于集合间关系的病毒检测模型........................................................................................375.1.1自体集、非自体集的编码方式..................................................................................375.1.2模型框架......................................................................................................................375.2实验数据来源........................................................................................................................395.3实验结果分析........................................................................................................................405.4小结........................................................................................................................................42第六章结论.................................................................................................................................436.1论文总结................................................................................................................................436.2结论展望.................................................................................................................................43参考文献.......................................................................................................................................45攻读硕士学位期间所取得的相关科研成果...............................................................................49致谢...........................................................................................................................................51IV 河北工业大学硕士学位论文第一章绪绪绪绪论论论论1.1课题研究背景及意义现今已进入高度发达的科技信息化社会，伴随着计算机网络技术的快速发展，计算机已普及到人们生活的各方面，然而，计算机中在带给人们便捷的同时，各类计算机病毒不断侵害用户的电脑，影响用户正常的使用操作，窃取用户信息，破坏计算机系统中的软硬件资源等。尤其是互联网的快速发展，网络病毒大范围发作与传播，这些病毒表现出一些以往病毒所不具备的新的特性，使大量计算机用户遭到了严重的损失，对计算机网络安全又提出了新的挑战。计算机病毒随着计算机中信息的传播进行繁殖、感染和进行破坏作用。当计算机病毒控制计算机后，它们会主动寻找宿主程序进行广泛传播。自1983年世界上第一例计算机病毒诞生以来，现在计算机病毒的种类多得难以计数。全世界每天都有大量新的病毒产生，国内外的统计数据显示，计算机病毒正在以快速方式大规模递增，每年由于计算机病毒造成的经济损失以千亿美元计算。计算机病毒通常利用操作系统的薄弱环节，稍不注意就可能对计算机用户造成严重的损失。提高计算机系统的安全性可以有效降低病毒的入侵和感染，但是并不存在完美的系统，而且提高系统的安全性必然会使系统用大量的时间进行病毒的安全性检测，降低了系统的实用性与效率。计算机病毒与计算机反病毒研究一直处于此消彼长[1][2]的竞争过程。计算机病毒检测一直是计算机安全领域的热点问题，计算机病毒猛烈的发展势头，使病毒检测变得更为困难和复杂。计算机安全技术包括加密技术、防火墙技术、认证技术以及访问控制等，这些技术对防止计算机遭受病毒的侵害起到了一定程度的保护作用，但是它们全都是侧重于防护的被动的安全技术。静态防御技术在病毒检测时永远不能处于主动的地位，而且安全策略的制定又不能过于严格，因此需要研究新的动态防御技术，能主动发现入侵的病毒并加以清除。特征码检测技术是传统病毒检测方法的核心技术，该方法是将已发现的病毒的特征数据提取出来，在检测外来抗原时与特征库中存在的特征数据进行对比，判断此抗原是否是病毒。但是该方法对未知病毒无能为力。为了克服这一缺点，各反病毒专家学者积极探索研究病毒检测的新型智能算法。生物免疫系统的运行机理和免疫过程，与计算机病毒检测所要解决的问题十分相像，都需要在持续变化的环境条件中保护自体，抵御非自体的入侵。生物免疫系统在维持机体平衡，保护机体免受入侵方面具有非常值得学习的地方，为病毒检测构建了理论前提。近年来，受生物免疫系统启发，1 基于集合的划分与覆盖的计算机病毒检测研究提出了神经网络、遗传算法、进化算法等新兴智能理论，在实践中应用广泛。人工免疫系统（AIS）是在模拟生物免疫系统的原理基础之上建立起来的免疫系统。人工免疫系统采用灵活和有效的手段使复杂问题得以有效解决，并且发展速度飞快，在许多领域都得到了广泛的应用。免疫算法即在人工免疫系统中采用的算法。目前的人工免[3,4]疫算法主要有否定选择算法、克隆选择算法和免疫网络模型。自免疫理论提出以来，[5][6][7][8]人工免疫理论在入侵检测、故障检测、在线检测、医疗诊断等领域都取得了很大的成果。大量的研究和技术应用于病毒检测，基于免疫的病毒检测技术克服了传统[9][10]病毒检测技术的弱点，应用前景十分广阔。1.2国内外研究状况在日本召开的有关免疫系统的国际专题研讨会上，首次提出了人工免疫系统这一新概念。人工免疫系统作为继神经网络、免疫遗传算法之后的一门新兴的智能理论，以其特有的优势近年来被广泛应用到计算机病毒检测和入侵检测研究中。国外将人工免疫系统的研究致力于计算机网络安全方面的典型代表有：NewMexico大学的Forrest小组；IBM实验中心的Kephart小组；伦敦大学的Kim-Bentley小组;孟菲斯大学的Dasgupta小组。美国墨西哥大学的Forrest博士在1994年，首先将人工免疫概念应用于计算机病[11]毒检测领域。他们建立了一个计算机病毒检测系统，用于检测计算机中的文件是否发生了异常。这个计算机病毒免疫系统采用否定选择算法的思想和原理，以计算机中文件的完整性作为检测的依据。经过实验验证，该系统发现未知病毒的效果很好。他们主要是为了创建一个基于网络的计算机病毒检测体系。这种病毒检测的思想是对网络中的重要的程序或文件进行特征提取，存放到正常文件的特征库中。特征库中的软件版本，结构都有特别的规定。第二个阶段是对异常行为进行检测，将可疑的程序与特征库中的信息进行比对，如果不与特征库中的文件相匹配，则认为该文件异常。Forrest博士和他的研究小组还建立了一个基于网络的入侵检测模型，模型将具有监听功能的主机分布在网络中，系统具有分布性，每台主机都能检测外来抗原，抗原由源主机IP地址，目的主机IP地址，服务器来表示，免疫系统通过检查网络中数据包的表示形式来发现异常。模型中采用的检测器是对生物免疫系统免疫细胞的模拟，产生与免疫细胞相同的功能，将自体、非自体、检测器选用相同的组织形式进行表示，采用了连续位匹配规则。[12]美国IBM公司在Kephart研究员的带领下建立了第一个商务计算机病毒检测系统，网络结构是分布式的，此病毒检测系统的中心能够处理大量用户提交的请求，快速检测出异常，对于病毒的变种以及文件被感染的问题能迅速检测到。Kephart还将神经网络应用于计算机病毒检测，对引导型病毒起到了很好的检测效果，但是当时所2 河北工业大学硕士学位论文检测的引导型病毒总数占IBM实验中心病毒总数的比例很低。[13]Kim-Bentley小组研究出了一个入侵检测模型。该模型由一级和二级两级入侵检测系统组成，根据先验知识建立未成熟检测器的基因库，接着用能检测到非法入侵的检测器来进化，再利用两级入侵检测系统之间传递的检测器来进行检测。并引入了小生境策略，将分布式、自组织和轻便性作为病毒检测系统的三个基本要素。孟菲斯大学的Dasgupta小组在病毒检测模型中使用了免疫遗传算法，模型的优越性在于生成的检测器可以衡量危险的不同级别，由于这个模型设计时特意针对突然出现的反常数据包，而这种攻击被发现的几率又是很高的，这也就限制了这个模型的价值。部分机构的研究人员将代理（agent）技术与免疫理论组织到一起，研究出新型的高性能的病毒检测技术。Okamoto和Ishida研究并设计了一种新的计算机病毒检测技术，该技术通过自治异类代理来判断并消除计算机病毒。他们建立的这套分布式系统通过计算机自身的信息与待检测样本进行匹配，以此来判断样本的合法性。尽管国内对在以人工免疫理论为基础的计算机病毒检测研究起步较晚，但发展迅速，已经取得了不少有意义的研究成果。中国科学技术大学的王煦法教授在对免疫算法进行重点研究的基础上，研制出一种入侵预警系统，该系统对未知入侵行为有良好的预警能力。武汉大学的梁意文教授和其所在的团队，深入研究和探索了基于免疫的大范围计算机病毒防御和入侵检测系统的创建技术。四川大学的李涛教授将人工免疫理论应用于网络安全领域，主要研究方向有针对大规模网络入侵的动态取证技术、计算机病毒检测技术等。李涛教授编写了《计算机免疫学》一书，在书中全面详细的介绍了生物免疫系统原理，计算机免疫学基本原理，[14]免疫算法和免疫网络模型。莫宏伟教授在Bentley-Kim小组对病毒检测系统研究的基础上进行了更深入的研究工作，将小生境阴性选择算法应用于病毒检测。他们提出的计算机病毒检测模型包括阴性选择过程、克隆选择过程和检测器进化过程，整合了人功能免疫理论的三个不同的阶段。传统的阴性选择算法检测器是随机生成的，而小生境阴性选择算法对这一传统算法进行了改进，使检测器倾向于向非自体方向进化。另外，国内的许多学者对否定选择算法的数据表示，匹配规则，检测器生成，检测器存储机制等方面也进行了[15]深入而有针对的研究。在人工免疫系统原理被提出后，产生了很多免疫算法。这些免疫算法很好的解决了病毒检测的问题，但是大部分算法都是针对专门问题，算法缺乏普适性。免疫算法以后的研究方向集中在下面几点：（1）对免疫算法性能的全面评估。现有的免疫算法的种类非常多，应用领域很3 基于集合的划分与覆盖的计算机病毒检测研究广。但是某些算法只针对特定的领域，仅与少量的不同的算法在性能上进行对比，评价标准不全面。（2）将免疫算法更好的应用到网络系统中。免疫系统原理与人工神经网络和人工智能等多方融合，使网络智能成为免疫算法发展的新方向。（3）将多种免疫算法进行融合。当今的免疫算法主要是对已有算法的改进，没有从根本上改变免疫算法的功能。（4）将免疫算法模型应用于工程领域。拓宽免疫算法的应用领域。1.3本文主要工作本文深入研究了生物免疫系统原理，计算机病毒的相关知识，人工免疫理论与计算机病毒检测的相似性。深入剖析了否定选择算法，针对已有检测器生成算法产生的检测器冗余度较高，产生速度慢的问题，提出了一种基于集合的划分与覆盖的检测器生成算法，用以提高对计算机病毒的检测效果。本文研究的主要内容及创新点：（1）检测器的生成机制是否定选择算法的核心，关系着病毒检测的性能和效率，在用层次匹配算法产生检测器的基础上，研究出了一种基于集合的划分与覆盖的检测器集生成算法，该算法能用最小的检测器集合覆盖最大的非自体空间，降低了产生检测器的时间消耗，减少了检测器的数量，提高了检测性能，并与去除冗余的检测器生成算法和层次匹配检测器生成算法进行了实验对比。（2）任何一种匹配规则都不可避免的会产生漏洞问题，漏洞的存在严重影响着病毒检测的效果，因此对漏洞的研究具有十分重要的价值。本文对病毒检测产生的漏洞进行了深入的探讨，提出了一种新的检测漏洞的算法，利用检测串链接的过程中未被利用的串集合与分段的自体串信息产生漏洞集合，该方法可以产生完整的漏洞集合，复杂度较算法EHANDP算法好。理论分析与实验结果验证了此种检测漏洞的方法的性能。（3）最后设计了一个病毒检测模型，该模型是基于集合间划分与覆盖关系的否定选择算法的。经过理论分析和用实验验证，对检测器的性能和漏洞计算的效果进行了说明。经实验证明，新建立的这个病毒检测模型对已知病毒，未知病毒和已知病毒的变种都有较好的检测效果。1.4本文的组织与结构论文一共分为六章，各章的内容与结构安排如下：第一章绪论部分。主要介绍了课题的研究背景及意义，国内外对于有关课题的研究近况。对课题的主要研究内容，以及课题的创新点进行了介绍，最后介绍了各章4 河北工业大学硕士学位论文的内容和结构安排。第二章对计算机病毒进行了详细的介绍。包括计算机病毒的概念、特点和工作原理。从连接方式、感染原理、破坏程度等方面对计算机病毒进行了分类。介绍了几种传统的病毒检测方法。第三章介绍了将人工免疫系统原理应用于计算机病毒检测的理论基础。首先从功能方面、层次结构、免疫机制、特点等方面对生物免疫系统进行了概述。介绍了人工免疫系统的相关知识，对免疫系统中的阴性选择算法、克隆选择算法和免疫网络算法进行了深入剖析。对基于人工免疫的病毒检测研究进行了简介。这为新算法的建立提供了理论前提。第四章提出了一种改进的否定选择算法。首先分析了否定选择算法的原理，介绍了否定选择算法的主要技术要点，介绍了一些改进的否定选择算法的思路。针对现有否定选择算法的弊端，基于集合间划分与覆盖关系的原理提出了一种新的检测器生成算法，该算法能用有最小的检测器集合覆盖最大的非自体空间，并通过理论分析和仿真实验验证了算法的性能。分析了漏洞产生的原因，介绍了如何判断一个字符串是否是漏洞以及计算漏洞数量的方法。在基于集合的划分与覆盖关系的检测器生成算法的基础上，设计了一种新型的计算漏洞数量的方法，利用检测器生成过程和自体集合信息查找出系统的漏洞。相比于Stibor提出的算法，该算法能检测出更多的漏洞，具有更好的检测效果。第五章使用改进的否定选择算法，开发了一种计算机病毒检测模型。首先建立模型的框架，选取实验数据，搭建实验环境，进行实验仿真，通过和原始层次匹配检测器生成算法进行对比，从对已知病毒、未知病毒和已知病毒的变种进行检测的效果上进行对比，验证病毒检测模型的性能。实验结果表明该病毒检测模型具有较高的检测效果。第六章进行了总结和展望，总结了论文的内容，并针对建立的计算机病毒检测模型的不足，提出了进一步完善的措施。5 基于集合的划分与覆盖的计算机病毒检测研究6 河北工业大学硕士学位论文第二章计算机病毒概述计算机病毒概述2.1计算机病毒知识简介本章对计算机病毒的相关概念及运行原理进行了介绍，并论述了人工免疫系统的原理和相关算法，并将病毒检测问题与免疫系统作了对比分析。2.1.12.1.1计算机病毒的定义2.1.1计算机病毒的定义FredCohen博士最先对给出了计算机病毒的定义，他指出：计算机病毒是一段特殊的指令集合，是一段能插入到计算机系统中并自我复制的代码集合。该定义具有相当的学术权威性，也因此被病毒研究者进行广泛引用。我国在1994年2月18日颁布的《中华人民共和国计算机信息系统安全保护条例》中，给出了计算机病毒的确切定义：计算机病毒，是指编制或者在计算机程序中插入的破坏计算机功能或者毁坏数据，[16]影响计算机使用，并能自我复制的一组计算机指令或者程序代码。2.1.22.1.2计算机病毒的特征2.1.2计算机病毒的特征计算机病毒具有区别于其他程序的显著特征。一、传染性计算机病毒所拥有的最基本的性质即是传染性。病毒侵入系统后，便会寻找一切满足其传染条件的宿主程序，将其自身代码代码插入其中，以达到繁殖自身的目的。如果病毒程序或文件不及时处理，就会使该病毒在本台计算机或病毒所在的网络环境中迅速传播，而新感染病毒的系统或文件又会成为新的感染源，病毒会利用可移动设备、硬盘、网络等传播媒介进行传播，最终造成网络的瘫痪。二、隐蔽性计算机病毒的编制通常需要高级的编程技巧，并且编写的程序大都精悍有效。病毒通常存储在比较隐蔽的地方，有的附着在其他正常的程序或以隐藏程序的形式存在，这样用户不会察觉到病毒的行为，只有在其被激活对系统造成影响或造成破坏时才会被用户察觉。三、潜伏性计算机病毒进入操作系统后，往往并不是立马爆发，只有在其发作的特定要求满足时，计算机病毒才会被激活并且执行破坏活动。在病毒的潜伏期内，病毒并不表现出破坏性，只是造成病毒的广泛传播，病毒潜伏的时间越长，病毒就会在越广的范围内传播，并且也就加大了被发现的难度。7 基于集合的划分与覆盖的计算机病毒检测研究一般情况下病毒的触发需要满足特定的条件，病毒的触发机制通常有三种。第一种是采用计算机系统时钟所提供的时间，精度可以达到毫秒级。第二种是利用计算机病毒自己携带的计数器，此计数器记录的可以是某次操作执行的次数、计算机病毒执行的次数等。第三种是通过执行对计算机系统的某些特定操作来触发，比如对外设的操作，读写磁盘的扇区等。四、破坏性计算机病毒进入计算机系统内，当其满足触发条件时，便会对计算机系统或者是计算机当中的应用程序及文件造成影响甚至是破坏。破坏程度较轻的计算机病毒会抢占计算机系统资源，使计算机的工作能力下降。破坏程度较重的计算机病毒会破坏计算机系统资源甚至损坏系统硬件，如CIH病毒，更有甚者会窃取用户信息，造成用户信息的泄露，进而使用户蒙受损失。五、不可预见性Cohen已经证明不存在一个病毒检测算法能够精确地检测出全部可能的计算机病[17]毒。现有的病毒检测技术只对已知病毒或者对部分未知病毒具有检测能力。计算机病毒和计算机病毒检测技术一直以来都处于一种相互促进增长的态势。2.1.32.1.3计算机病毒的工作原理2.1.3计算机病毒的工作原理病毒程序和其他程序在执行功能上基本一致。病毒程序必须依附在宿主程序上，这是病毒区别于其他程序的显著特征，当宿主程序运行时，使病毒程序激活，开始运行并进行传播和感染。分析病毒运行的原理和机制，有助于对病毒的防治和消除。[18]病毒一般经历四个不同的阶段：潜伏阶段、传染阶段、触发阶段以及发作阶段。如图2.1所示：图2.1病毒工作的四个阶段8 河北工业大学硕士学位论文首先病毒处于潜伏阶段时，病毒程序为休眠状态，病毒并不能被用户所察觉，事实上，并不是所有的病毒都会经历潜伏阶段。如果某个特定的事件或动作发生，就会激活处于休眠状态的病毒程序，使病毒从休眠状态进入传染阶段。处于传染阶段的病毒将会进行病毒的感染和传播，将自身程序拷贝到其他程序或者磁盘文件中。经过这个阶段后，当满足计算机病毒的触发要求后，则会激活病毒程序，进入发作阶段的病毒将会进行破坏数据文件、扰乱计算机的正常工作等。为了完成病毒的4个阶段的转换，病毒需要具有相对应的功能模块。病毒程序主要的组成模块有引导模块、传染模块和表现模块。如图2.2所示。病毒引导模块激活传染条件传染功能实现判断模块模块病毒传染模块触发表现条件判表现功能实现模断模块块病毒表现模块图2.2病毒程序典型模块组成计算机病毒的引导模块：负责将计算机病毒程序引入到计算机内存中，同时为了应付杀毒程序的处理，还需提供自我保护功能。计算机病毒程序被引入到内存后，引导模块设置某些特定的启动条件，为传染模块和表现模块服务。使传染模块和表现模块在合适的条件下触发。计算机病毒的传染模块：传染模块实现两个功效，一个判断在引导模块设置的传染条件是否满足，一个是在满足传染条件的情况下进行感染操作。计算机病毒表现模块：表现模块也完成两个功能，一个判断是否满足在引导模块设置的触发条件，一个是在触发条件满足的情况下启动病毒程序，进行预先设定的操作。2.1.42.1.4计算机病毒的分类2.1.4计算机病毒的分类计算机病毒的类型繁多，且具有多种多样的感染方式，按照计算机病毒的特点和9 基于集合的划分与覆盖的计算机病毒检测研究性质有不同的分类方法，相同的病毒也会具有各种各样的特点，因此相同特点的病毒[19]可能隶属不同的分类中。2.1.4.1按照链接方式分类（1）外壳型病毒外壳型病毒寄居在被侵入的程序的头部或者是尾部，并不对原来的宿主程序进行损坏，文件型病毒大都属于外壳型病毒。这种病毒会比宿主程序先执行，并且随着宿主程序的执行大范围扩散。这是最为常见的计算机病毒，制作方法简单，容易找到。（2）嵌入型病毒此类病毒不同于外壳型病毒，嵌入型病毒会将自身嵌入到被侵入程序的里面，破坏了宿主程序原有的结构，此类病毒清除起来非常困难，采用这种技术的通常是超级计算机病毒。对这类超级计算机病毒的检测对计算机安全检测提出了重大的挑战。（3）源码型病毒源码型病毒是使用C、java和其他高级语言编写的病毒程序，高级语言程序及脚本程序通常是此类病毒的攻击对象。在宿主程序编译前，这类病毒就将自身插入到源程序里，通过编译链接的方式成为宿主程序的一部分，与合法程序融为一体。（4）操作系统病毒操作系统病毒将自身代码加入到操作系统内部或者取代部分操作系统的代码，通过攻击磁盘引导扇区或者文件分配表达到攻击计算机操作系统的目的，这种病毒的破坏力很强，甚至可能造成整个系统的瘫痪。2.1.4.2按照传染原理进行分类（1）引导型病毒引导型病毒通过攻击启动扇区（Boot）或主引导记录（MBR）来进行攻击。此类病毒先于操作系统运行，病毒触发时，病毒正在进行磁盘的引导操作，驻留在内存当中的病毒可以监视计算机操作系统的运行，伺机进行传染和破坏活动。（2）文件型病毒文件型病毒通过感染计算机中的文件系统来实现对操作系统的入侵。这种病毒通常会采用一些技术手段将自身隐藏起来，随着被感染病毒的文件的运行，病毒被激活，通过对自身进行大量复制进而感染系统中其他的可执行文件。（3）混合型病毒具有文件型病毒和引导型病毒共同的特征，是混合型病毒的特点。同时感染文件和引导扇区，这种病毒较前两种病毒具有更复杂的算法，清除这类病毒的难度也更大。（4）蠕虫病毒蠕虫病毒并不是直接复制自身来进行病毒的传播，它通过拦截各地的E-mail文10 河北工业大学硕士学位论文件来将自身复制品进行传播。蠕虫病毒具有非常快的传播速度和严重的破坏性。2.1.4.3按照病毒的破坏程度分类（1）良性病毒良性病毒只是复制自身，并不会立即对计算机系统或硬件资源造成直接的破坏作用，但是良性病毒可能会大量占用系统资源，降低计算机工作效率，甚至使计算机不能正常工作。（2）恶性病毒恶性病毒对计算机系统造成的损害较良性病毒严重，随着互联网的发展恶性病毒将直接对计算机操作系统造成损坏。恶性病毒不仅可能会损毁数据或程序，甚至干扰计算机工作。恶性病毒的破坏作用通常表现在破坏硬盘信息，损毁文件分配表，删除计算机中的数据或文件甚至将硬盘格式化等。由于恶性病毒的危险性，应该更加注意对恶性病毒的防范。2.2传统的病毒检测方法自计算机病毒产生以来，大量的病毒检测研究算法被提出来，传统的病毒检测方法大都是以特征码为基础的，主要包括特征代码法、校验和法、行为监控法和一些高级反病毒技术。（1）特征代码法特征代码法是当前病毒检测领域最方便、成本最小、利用最多的病毒检测策略。特征代码法的检测程序是先搜集感染文件的病毒样本，采集到病毒的特征码，当遇到非常规文件时，将文件与病毒特征代码库的特征代码进行对比，如果匹配，则证明到有病毒入侵。特征代码法对病毒的检测快速、准确，能够检测出病毒的种类并且误报警率低。特征代码法的缺点是对于未知病毒或者已知病毒的变异体是无法准确识别的，另外，由于要收集病毒的特征代码，其花费的开销比较大，而且匹配也要花费一定的时间，这些都会使网络性能降低。尽管特征代码法存在着一定的缺陷，但是该方法的优越性还是无法替代的，此方法仍是当今乃至未来很长一段时间被广泛使用的方法。（2）校验和法所谓校验和法，就是计算操作系统中合法文件的校验和，将计算出来的校验和保存在一个单独的文件或者直接写入该文件中，当再次使用该文件时，比较现在文件算出的校验和与之前算出的文件的校验和是否相同，通过此种方式来判断是否受到了病毒的入侵。校验和法通过对比前后文件的校验和来判断是否有可能感染病毒，此种方法的优11 基于集合的划分与覆盖的计算机病毒检测研究点是不光能发现已知病毒，还能检测到部分未知病毒。但是文件内容的改变可能不单单是由病毒入侵引起的，还可能是由于文件版本的更新、运行参数的改变等其他原因，也就是说正常程序也可能会使文件的内容改变，因此校验和法可能会产生误报警。而且这种方法不能确定病毒的名称和种类。另外，此种方法对隐蔽型病毒无效，因为隐蔽型病毒在到达内存后会剥去其病毒代码，使感染病毒后的文件的校验和与系统正常文件的校验和一样。（3）行为监控法计算机病毒拥有一些正常程序没有的行为特点，而且这些特点通常是传染或损毁性的，通过检测程序运行时所表现出来的一些特殊的行为推断程序是否感染了病毒。行为监测法的误报率较高，不能判断出病毒的类别，并且实现起来不太容易。（4）其他的病的检测方法
软件模拟法软件模拟法主要针对多态性病毒，多态性病毒一旦成功破坏其他文件后都会改变病毒密码，并且使用新的密钥，因此并不能从感染文件中提取出一致的病毒特征码。软件模拟法主要通过虚拟机技术完成，通过在虚拟机上模拟病毒的运行，跟踪病毒的行为，将病毒解密，取得病毒的特征代码，获得新病毒的类型和内部结构，这样当再次遇到这种病毒的入侵时，就能通过特征代码法加以识别。在病毒检测过程中，将特征代码法与模拟软件法相结合，先采用病毒特征代码法来监测程序的运行，当遇到特征代码法无法应对的多态性病毒时，就采用软件模拟法监测该病毒，破解病毒自身的密码后，待提取出病毒的特征码后再利用特征代码法判断病毒属于何种类型。
比较法比较法的思想是利用正常程序与被检测程序在长度、内存、中断等方面进行对比。从多个角度对正常程序和被检测程序进行了比较。该方法利用常规的软件便可，并不需要专门的检测程序。长度比较法就是通过比较正常文件和待检测文件的长度是否存在差异来进行判断是否有病毒入侵。通常正常文件在感染病毒后，文件都会增长，如果记录下不同病毒使文件增长的长度，就可以据此推断出是哪种病毒感染了文件。但是由于病毒的入侵并不是造成文件长度改变的唯一原因，所以此种方法会出现一定的误报警。内存比较法是为了发现藏匿在内存中的病毒，病毒进入内存后会占用一定的内存空间，通过比较内存空间的变化情况来判断是否有病毒入侵。这种方法的缺点仍然是不能判断病毒的类型，同时也不能检测出隐蔽型病毒。中断比较法是通过比较带毒系统的中断向量和合法操作系统的中断向量来判断是否感染病毒，病毒往往是利用操作系统底层的机制和原理，通过改变中断向量或者12 河北工业大学硕士学位论文接管中断向量而转去执行病毒代码部分，来达到传播和感染的目的。比较法具有简单、方便的优点，具有无法判断病毒种类的缺点。
分析法分析法是通过分析发生异常的那部分代码判断是否感染病毒。分析法一般由反病毒技术人员完成，具有较高的技术含量。分析法分为静态分析法和动态分析法。静态分析法是利用反向汇编程序将病毒代码转为汇编代码进行分析。动态分析法是当病毒驻留在内存时，利用调试工具对病毒进行动态追踪，在工作原理上深入理解病毒的机制。分析法是病毒检测技术中一种非常重要的方法。2.3小结本章对计算机病毒进行了概述。介绍了计算机病毒的概念、特征和内部的工作机制。从三个方面对计算机病毒进行了分类。并介绍了特征代码法、校验和法、行为监控法等传统的病毒检测方法。本章对计算机病毒的介绍为后续章节的展开奠定了基础。13 基于集合的划分与覆盖的计算机病毒检测研究14 河北工业大学硕士学位论文第三章人工免疫系统与计算机病毒检测研究人工免疫系统与计算机病毒检测研究3.1生物免疫系统概述3.1.13.1.1生物免疫系统的功能3.1.1生物免疫系统的功能生物体维持自体的平衡是通过自身的免疫系统来完成的。免疫细胞、免疫分子、免疫器官等组成了生物免疫系统。生物免疫系统通过和其他系统及其器官相互配合和作用共同调节机体平衡，抵御外来抗原的入侵。生物免疫系统的功能有：（1）免疫防御：其主要功能是抵御外来病原体的入侵，同时还能抑制住病原体在生物体内传播以及扩散，清除外来微生物，保持机体正常的生命活动。免疫防御能力低下，机体的免疫能力就低，而如果免疫防御能力过高则容易出现过敏性反应。（2）免疫自稳：指生物体将体内衰老、损坏的细胞或组织删除的功能。（3）免疫监视：其功能是当变异细胞在生物体内出现时，机体就会采取相应的措施将变异细胞清除，使恶性肿瘤无法在体内长存。3.1.23.1.2生物免疫系统的层次结构3.1.2生物免疫系统的层次结构生物体保护自体免受外界的入侵包括一系列的层次结构，生物体保护自身的第一层是物理和生理屏障。皮肤表面的角化层可以阻止细菌和病原体的入侵，是人体的第一道屏障，同时皮肤还具有杀菌能力。分布在呼吸道和消化道以及胃表面的粘膜由于吞噬细胞和抗体的作用，同样能阻止病原体的入侵。第二层是固有免疫反应。固有免疫系统包括吞噬细胞和巨噬细胞，它们分布在身体各个部分的细胞中，监视着病原体的入侵，特异病原体的变化并不会引起这些细胞的变化，这种免疫是人天生的，从出生时就存在。以上两种免疫系统的作用是具有普适性的，这种抵御外来入侵的能力可以对多种病原体起到防御的能力，并不是只针对某一种特殊的病原体，正是由于这种非特异性，这种免疫反应也叫非特异性免疫。如果细菌或病原体突破了非特异性免疫系统的侵扰，侵入体内进行感染，那么特异性免疫将发生作用。特异性免疫系统也就是自适应免疫系统，主要是在T细胞和B细胞的作用下完成。对于不同病原体，T细胞和B细胞会相应的产生特定的抗体，同时对于以前出现过的入侵病原体还能产生记忆，特异性免疫反应能够完成固有免疫系统所不能完成的功能，具有更加优秀的免疫能力。3.1.33.1.3免疫机制3.1.3免疫机制15 基于集合的划分与覆盖的计算机病毒检测研究生物免疫系统的免疫机制主要包括免疫耐受阶段和免疫应答阶段。（1）免疫耐受：其定义是当免疫活性细胞接触到抗原性物质所表现出的一种特[20][21]异无应答状态。区分自体和非自体是免疫系统的一种重要功能。自体耐受就是生物体对自身抗原不反应的过程，是一种特殊的免疫耐受。当免疫耐受受到破坏，自身免疫系统极易出现病变。适应性免疫应答主要需要T细胞和B细胞的参与，T细胞和B细胞都要完成免疫耐受才能发挥其免疫作用，而且T细胞耐受的重要性高于B细胞，这是因为B细胞只有在T细胞刺激作用下，才可对大多数的抗原产生出抗体。中枢耐受和外围耐受是耐受的两种形式。中枢耐受是指在骨髓中分布的B淋巴细胞和在胸腺中存在的T淋巴细胞，这两种细胞在发育的过程中执行否定选择过程，如果未成熟淋巴细胞会引起自体免疫反应，则从自体删除，这一过程属于克隆删除。中枢耐受将对自身产生免疫反应的未成熟细胞删除，对自身免疫性疾病的预防有着重要的意义。经历外围耐受的淋巴细胞是在外围的非淋巴组织生成的。T细胞和B细胞在外围组织中经历的耐受程度是不同的，外围耐受大部分情况下是可逆的，而且具有动态性和柔韧性，因为在大多数的组织和器官中特异性抗原的浓度太低，不足以使T细胞和B细胞激活，当抗原的浓度达到一定的浓度时，自身反应性T淋巴细胞就会与MHC分子接触，产生淋巴细胞被激活的第一个信号，再在辅助性T淋巴细胞的协同刺激下，产生第二个信号，来共同完成外围组织中淋巴细胞的激活过程。（2）免疫应答：免疫系统完成免疫功能是由免疫系统各部分共同协作完成的，各部分完成各部分的生理功能，抗原入侵机体后，免疫细胞或者免疫组织对抗原会做出一系列应答过程例如提取抗原、激活淋巴细胞、识别抗原、形成抗体、免疫反应、免疫记忆等。生物体生来就具有固有免疫应答，这是第一类应答形式。其主要包括物理和生理屏障。还有一类免疫应答是适应性免疫应答，其是指在遇到抗原入侵时，能发生适应性学习来发现并识别特异性抗原，并产生记忆功能，当又一次受到这种抗原的侵扰时，能快速应答，主要是在T免疫细胞和B免疫细胞的作用下进行。适应性免疫应答按抗原的刺激顺序包括初次应答和二次应答。初次应答是指在遇到特异性抗原入侵时，在抗原的持续刺激下，淋巴细胞激活，初次应答的响应速度一般比较慢，抗体浓度低下，免疫期短。初次应答会产生一定数量的记忆细胞，记下此次免疫反应的反应过程。二次应答是指生物体再次受到同一抗原的刺激后，将会激活B免疫细胞，其将会快速地参与到免疫过程，二次应答的反应速度非常快，并且能在机体内持续很长的时间。3.1.43.1.4生物免疫系统的特点3.1.4生物免疫系统的特点生物免疫系统在对侵入生物体内的抗原进行分析和学习后，产生抗体来消灭外来入侵。免疫系统具有免疫记忆、多样性和对特异抗原具有识别能力的特点，此外还具有优良的耐受性、广泛的分布性、良好的学习和认知能力、稳定性及鲁棒性和良好的16 河北工业大学硕士学位论文[22]适应性等优良特性。耐受性是指生物体不会对自身抗原产生免疫反应。即通过上文提到的中枢耐受和外围耐受来实现。分布性是指完成免疫功能是由分布在各处的局部组织共同完成，而不是通过集中控制，也就是采用分布式检测，采用这一检测策略的原因是外来抗原是随机分布在生物体的各个细胞和组织中的。生物免疫系统的分布性特性使其自适应性更加强化。生物免疫系统具有学习能力，对首次进入体内的抗原进行识别和记忆，当同样的抗原再次出现时，能迅速做出反应。这种学习能力的获得得益于免疫系统的基因编码、克隆增长和基因的变异，而学习的关键是基因的变异。生物免疫系统的适应性是指生物免疫系统强大的学习能力，使其能适应不断变化的环境，对新出现的病毒具有较高的适应能力。通过反馈和调节功能使免疫系统对免疫反应表现的强烈程度根据自身的实际情况决定。正是由于免疫系统的容错性、多样性、动态性以及分布性，这使生物免疫系统具有极其良好的鲁棒性。3.2人工免疫系统概述免疫系统具有多样性、自适应性、鲁棒性、自组织和分布性等特点，生物免疫系统自身具有的这些特点激励着人们不断地对生物免疫系统进行深入的研究。研究人员通过借鉴生物免疫系统成功保护机体的机理，将其应用到人工免疫系统的研究及应用上。1974年美国若贝尔奖获得者免疫学家Jerne首次提出免疫网络学说。Farmer博士于1986年对免疫网络理论用数学语言进行了描述。Farmer博士发表的论文《免疫系统、适应与机器学习》为基于人工免疫原理的计算机免疫系统的研究和发展开辟了道路。免疫系统的核心机制是区分自体和非自体。基于这一机制的免疫系统模型经常用在入侵检测、计算机病毒检测、故障诊断、异常变化检测和优化问题中。人工免疫系统主要包括三个最重要的部分：否定选择算法、克隆选择算法和免疫网络模型。Forrest博士于1994年首先提出否定选择算法，并将否定选择算法应用于计算机病毒检测和入侵检测领域。克隆选择原理是由Burnet率先提出的，1999年，Hunt在克隆选择原理的基础上研究出高频变异学说。1989年，Varela提出了免疫网络学说。这些研究和学说为人工免疫的研究奠定了理论基础。借鉴生物免疫系统的免疫过程，构建的人工免疫系统模型的核心过程包括克隆选择、亲和度变异、自体耐受以及记忆和死亡。免疫模型如图3.1所示。17 基于集合的划分与覆盖的计算机病毒检测研究开始产生免疫细胞N变异耐受成功死亡Y克隆选择成熟细胞亲和力成熟Y激活记忆细胞图3.1人工免疫过程模型人工免疫系统模型是对生物体内免疫细胞过程的模拟。模型的基本步骤是：（1）初始免疫细胞产生。在骨髓中产生的免疫细胞，有一个耐受期限，如果与自体发生匹配，耐受细胞将会死亡，产生新的免疫细胞。（2）成功经历免疫耐受的细胞，将进入免疫循环，如匹配到抗原则亲和力累积。当累积到达一定阈值时，免疫细胞将会被激活转变成记忆细胞。同时大量的免疫细胞将会通过克隆过程产生出来以抵御入侵。如果在其生命周期内，成熟免疫细胞未达到激活阈值，则将该成熟细胞删除，由新的免疫成熟细胞代替。（3）记忆细胞的生命周期较成熟细胞更长，记忆细胞成功匹配抗原后，会使自己再次激活并对自身进行克隆，产生的新细胞将作为记忆细胞。对于以前识别过的抗原系统能更快的做出反应。其中一部分免疫细胞还将进行变异，加大其学习进化的功能。经过变异的免疫细胞也必须经历耐受过程。3.3相关算法[23][24]目前的人工免疫算法主要有免疫网络模型、否定选择算法和克隆选择算法。18 河北工业大学硕士学位论文3.3.13.3.1否定选择算法3.3.1否定选择算法否定选择算法是Forrest于1994年提出的，该算法借鉴了生物免疫系统原理，通过模仿自然免疫系统以区分自体和非自体，确保计算机系统的安全可以描述为检测未经授权的对计算机操作的使用，阻止计算机病毒的传播等。否定选择算法分为两个阶段：（1）随机产生一部分字符串，作为候选检测器，利用特定的匹配规则，令该字符串与自体集合中的字符串作比较，如果匹配则删除该字符串，否则将候选检测器放入检测器集合中。（2）通过对外来字符串与检测器集合中字符串的比较来监测有无入侵，如果外来字符串与检测器集合中的字符串相匹配则证明有入侵。否定选择过程如图3.2所示：图3.2否定选择算法过程3.3.23.3.2克隆选择算法3.3.2克隆选择算法最先提出克隆算法的是巴西Campians大学的De.Castro.L。Kim首先将克隆选择原理应用于病毒及异常行为的检测中，描述了免疫系统与抗原对抗的过程。当遇到病毒或者外部细菌的入侵后，机体中的B细胞大量复制以此来消灭外来入侵者。能够识别抗原的细胞根据与抗原的亲和程度进行增殖和变异，与抗原具有较高亲和力的细胞，经历的变异程度较小。亲和度越低，经历的变异程度越大，以保留优秀个体并改良较差的个体。克隆选择算法的过程如图3.3所示。19 基于集合的划分与覆盖的计算机病毒检测研究开始抗原识别初始抗体产生变异亲和力计算抗体选择抗体变异是否满足终止条件YN终止图3.3克隆选择过程3.3.33.3.3免疫网络算法3.3.3免疫网络算法基于网络的免疫算法所构建的免疫系统中，处于系统内的所有元素之间可以相互联系相互促进。Jern首先提出免疫网络理论，免疫网络理论是对生物体内免疫细胞进化、抗体的产生、耐受、识别自体和非自体、免疫记忆等活动的概括。免疫网络是由生物体内所有的免疫细胞所组建成的网络系统，其更加注重个体间的相互协调和刺激作用。典型的免疫网络模式是DeCastro等人提出的aiNet人工免疫网络系统。aiNet免疫网络研究了免疫系统的一些基本问题，主要是对数据量特别大的集合的聚类和自学习能力分析。将aiNet网络中的免疫细胞称作细胞节点，节点之间不必全部相连，连接的节点称作节点对，边界则表示为所有节点对的集合。给每对相连接的节点间分配一个连接强度的权值。aiNet网络采用进化策略，从而控制网络的动态以及网络可塑程度。免疫细胞通过连接强度矩阵对其相互间的亲和力大小进行衡量。同时免疫细胞通过对抗原的识别能力的大小展开竞争活动，优秀的细胞将进行克隆增殖，清除竞争失败的细胞。抗体与抗体之间将会产生互相识别的现象，同时识别的过20 河北工业大学硕士学位论文程还会导致网络的抑制，抑制的程度用特定的抑制阈值进行衡量。aiNet网络就是通过免疫网络中免疫细胞的相互协调作用，使机体处于一个平衡稳定的状态。aiNet免疫网络模型是影响力最大的人工免疫网络，被广泛应用到数据结构描述、减小数据冗余等领域。部分研究人员对aiNet免疫网络进行了改进，文献[25]提出了一种VD-aiNet算法，是一种基于矢量距的免疫算法。文献[26][27]将禁忌免疫算法的思想引入到aiNet网络中，加大了算法的收敛性。3.4基于人工免疫的病毒检测研究生物免疫系统是一个复杂并且高效的自然免疫系统，能对外来病毒体做出迅速的响应。计算机病毒防御问题与生物免疫系统（BIS）所遇到的问题非常相似，都需要在不断变化的环境中保持系统的稳定性和高效性。生物免疫系统的功能是保护机体免受各种侵害，也就是区分自体和非自体的能力，确保计算机系统的安全包括检测未经授权的对计算机中的数据和文件的使用，确保数据完整性以及阻止计算机病毒的传播等。保护计算机系统安全的问题可以归结为区分计算机中的自体（合法的用户，保护的数据，原始源代码，授权活动等）和非自体（未授权的用户，拒绝服务攻击，病毒，后门，特洛伊木马等）的问题。免疫系统具有高度的自适应能力和良好的动态学习能力，对以前未出现过的抗原能迅速做出反应，当前的计算机病毒检测主要是针对已知病毒的，不能很好地检测到未知病毒和已知病毒的变种。相对于计算机病毒的发展，计算机病毒检测技术往往总是滞后，同时计算机病毒的传播方式越来越多样化，感染文件的方式和对自身隐藏的手段越来越高明，这给计算机病毒检测提出了更为严峻的挑战。生物免疫系统抵御外来入侵的机理给计算机病毒检测提供了一个崭新的思路。将免疫机制引入到计算机病毒检测中，借鉴并学习免疫系统的优良特性和机制，比如否定选择、克隆选择、学习和记忆机制，使计算机病毒检测问题得到更好的解决，加强计算机病毒检测系统的自适应能力和学习能力，更好的应对复杂多变的网络环境。生物机体的免疫系统和计算机病毒的检测系统在功能上和工作原理上具有明显的相似性，如表3.1所示。表3.1生物免疫系统与计算机病毒检测系统对比生物免疫系统计算机病毒检测系统正常组织或细胞正常的程序或文件外来入侵计算机病毒抗体检测器抗体的自我耐受过程检测器的否定选择过程21 基于集合的划分与覆盖的计算机病毒检测研究3.5小结本章主要介绍了计算机病毒检测与人工免疫理论的相关知识，对计算机病毒进行了概述，主要介绍了人工免疫中的否定选择、克隆选择算法和aiNet免疫网络。文章最后对计算机病毒检测系统与人工免疫系统的相似性进行了介绍。本章的内容作为背景理论铺垫，通过对相关理论和相关算法的论述，为本文第4章的基于集合的划分与覆盖的检测器生成算法的提出提供了理论基础。22 河北工业大学硕士学位论文第四章基于集合的划分与覆盖的检测基于集合的划分与覆盖的检测器生成算法研究检测器集合的生成机制是关系否定选择算法性能的关键。将自体集合依据r值分段提取出自体集合的补集，并将这些补集连接成检测器集合的机制仍然存在大量冗余检测器，这样不但增大了时间和空间消耗，同时降低了检测器的性能和检测效率。为了生成覆盖最大非自体空间的最小检测器集合，利用集合间划分与覆盖关系的原理，改进了检测器集合的生成机制。4.1否定选择算法综述4.1.14.1.1算法原理4.1.1算法原理否定选择算法采用的是R-连续位匹配规则，两个字符串完全匹配的情况是这两个字符串所有位置的字符都匹配，但是这种完全匹配的情况非常少见，于是才有部分匹配规则，若两个字符串x和y，如果x与y匹配当且仅当它们至少有r个连续位相同，这种匹配规则可以应用于多个符号的字母表上，0、1代码组成了计算机内所有的程序，所以用二进制字符串表示非常方便。例如字符串X=101000，Y=101110，在r<=3时，X与Y匹配。用符号PM表示两个字符串在r连续位匹配规则前提下，其匹配概率的大小，l代表字符串的长度，r代表连续匹配位的大小，m代表字母表中符号的数量，则-r[()()]P»m1-rm-1/m+1（4.1）M-r当m=2时，PM≈2[（l-r）/2+1]。已有的实验结果表明在m和r不变的前提下，随着l的增长，PM线性下降；随着r的增大，PM呈指数下降趋势；m的增大，对PM有巨大的影响。否定选择算法的检测效率，通过检测失败率Pf来衡量。为了更明晰的观察否定选择算法的检测率我们定义以下符号：N代表初始检测器集的大小，即未经耐受前检测器集的大小。R0NR代表经历耐受阶段后检测器的数量。NS代表自体字符串数量。PM代表两个随机字符串匹配的概率。f代表一个随机字符串和自体中每一个字符串都不匹配的概率，有NSf=1(-P)。MPf代表非法字符串不能被检测器集中的检测器NR检测到的概率。有23 基于集合的划分与覆盖的计算机病毒检测研究NRP=1(-P)（4.2）fM经过简单的公式推导有：-lnPfN=（4.3）RPM-ln(P)fN=（4.4）R0NP*1(-P)sMM由（4.3）可知，若Pf和PM固定，则NR也即固定，也就是说检测器集的数量不因自体集的增大而增大。由（4.4）可知，当Pf和PM固定的条件下，候选检测器的大小和NS成指数关系。否定选择算法是要找到一个检测器集合，这个检测器集合需要在不与自体集合匹配的前提下，尽可能多的匹配非自体。由于候选检测器产生的随机性，每一个候选检测器都要和自体进行匹配，只有与自体集合中的所有自体都不匹配的候选检测器才被保留下来。否定选择算法的时间复杂度主要取决于两个因素：初始检测器集合的产生时间以及检测器集与自体集中每个数据匹配的时间。-ln（P）fTime：O（*N）（4.5）NsP*（1-P）smm空间复杂度取决于自体集大小。在自体集合很大时，该算法的时间复杂度和空间复杂度都很高，检测效率不高。Space：O（l*Ns）（4.6）否定选择算法的优点是不需要先验知识，候选检测器是随机生成的，同时也由于候选检测器产生的随机性，会使产生的大量检测器被丢弃，容易产生交叉漏洞和限长漏洞，因此检测效率不高。4.1.24.1.24.1.2否定选择算法的主要技术要点否定选择算法的主要技术要点[28][29]否定选择算法的主要技术要点包括：问题空间和检测器的表示形式；选择何[30][31][32][33][34][35][36]种匹配规则；检测器生成机制；检测器存储形式。而如何快速有效的生成检测器是否定选择算法的关键。问题空间和检测器的表示形式：传统的否定选择算法对检测器及抗原采用的表示方式是使用字符串，由于计算机中所有的数据文件都是由0、1代码组成的，因此最普遍的表示方法是使用二进制字符串。针对用字符串表示问题空间的局限性，有关专家和学者又提出了用实值向量和矩阵的表示形式，这种表示形式对问题空间的表示更加形象。匹配规则：针对二进制字符串表示的匹配规则，主要有海明距离匹配规则、r连续位匹配规则、r块匹配规则。24 河北工业大学硕士学位论文r-contiguous(rcb)匹配规则：Forrest博士1994年将r连续位匹配规则应用于NS算法。该匹配规则通过判断两字符串在连续r个位置上的相同性，如果在连续r个位置上相同，则认为这两个字符串匹配，r为匹配阈值大小。假设抗原的表示形式为X=x1x2…xl,检测器的表示形式为D=d1d2…dl,如果X与D匹配，则当1£i£l-r+1时，有xj=dj，j=i,…,i+r-1。r-chunk(rch)匹配规则:rch匹配规则对rcb匹配规则进行了限制，即要求两个字符串匹配必须在相同位置的连续r个位串匹配，才能判定两个字符串匹配。例如X：101010，Y：100110，在r=4时，在rcb匹配规则下，X与Y匹配，但是在rch匹配规则下，两者不匹配。海明距离匹配规则：海明距离匹配是计算两个字符串对应位相同的字符串的个数，计算方法是统计各个位置上不同元素的个数，再取异或值就得到两个串的相似度量值。检测器生成算法：自否定选择算法提出以来，对检测器生成算法进行了大量的研究，D’haeseleer于1996年提出了线性时间检测器生成算法和贪心检测器生成算法。线性时间检测器生成算法分为两个阶段，首先通过递归运算从而得到特定数量的并且不与自体相匹配的候选检测器集合，第二个阶段是随机从候选检测器集中选出若干个作为检测器用以检测异常。线性时间检测器生成算法改变了传统否定选择算法随机生成检测器的盲目性，时间复杂度和自体集大小呈指数关系，但是该算法的时间和空间复杂度仍与r呈指数关系，当l和r很大时，仍将影响检测效果。贪心检测器生成算法使产生的检测器分散到更大的空间，尽可能地用最少的检测器集合以涵盖最大的非我空间。但同时这两种算法都不可避免的会产生漏洞和冗余现象。张衡，吴礼发等人研究出了一种r可变阴性选择算法，通过调整匹配阈值大幅度降低黑洞数量。何申等人提出了一种新型的否定选择算法，这种算法的检测器长度是可变的，其覆盖范围通[37]过检测器长度的变化得以提高，杨铭魁对该算法进行了改进。LiskiewiczM等针对[38]穷举法存在的问题，提出了非穷举法。ElberfeldM提出了压缩法，对检测器集进行[39]压缩将时间复杂度由指数级降低到多项式级，减少了检测器数量。柴争义，张雄美[40][41]等将检测器的表示形式从字符串空间转到向量空间和矩阵空间。王辉，敖民等采[42][43]用可变模糊匹配阴性选择算法，提出了具有一定连续相似度的模糊匹配。大多数文献是探讨匹配阈值的变化，检测器长度的变化和检测器形状的改变来生成检测器。基于随机搜索的策略，所产生的的检测器具有非常大的检测漏洞，会造成时间和空间[44]的巨大消耗。杨宁将小生境策略用于否定选择算法以提高效率。张清华等人提出了[45]一种新型的针对二进制串的切割否点选择算法。为了提高检测器检测非自体的效[46]率，蔡涛等人提出了一种基于红黑树的快速否定选择算法。刘星宝提出了一个检测器快速生成策略，该算法充分利用自体信息，根据r值大小，将自体集分段，得到自25 基于集合的划分与覆盖的计算机病毒检测研究[47]体集合相应段的补集，通过二叉树连接得到检测器集合。该算法能保证所产生的检测器不与自体匹配，加快检测器生成的速度，但是该算法会产生大量的冗余，现有的去除冗余检测器的办法是：当一个检测器新生成时，让该检测器与检测器集合中的检测器进行匹配，如果匹配，即此检测器能由已有检测器集合中的检测器代替，则舍弃此检测器，但是该方法会产生二次冗余的问题，因为检测器是顺序产生的，先放入检测器集合中的检测器会与后放入检测器集合中的检测器的覆盖范围出现相交的情况，所以经过一次去除冗余后并不能保证检测器集合中的检测器不存在冗余。好的检测集集合应该保证：不与自体空间匹配；用最小的检测器集合几乎完全覆盖所有的非自体空间。本文在层次匹配算法的基础上，提取出所有自体集合的以r为大小的段的补集合，在连接策略上进行改进，尽量达到集合的划分，产生能覆盖最大非己空间的最小检测器集合，降低检测器生成时间，减少检测器的个数，提高等量检测器相应的覆盖范围，从而提高检测的效果。4.2基于集合的划分与覆盖的检测器生成算法研究4.2.14.2.14.2.1已有的检测器生成算法已有的检测器生成算法由于r连续位匹配规则的特殊性，传统的免疫算法在产生候选检测器的时候，需要和自体进行连续r位匹配，如果匹配则删除或者进行位变异等方法；在检测器抗原的时候，也是利用抗原与检测器进行连续r位匹配，不同的检测器有可能包含同样的检测因子，使得在匹配的时候存在重复提取相同检测器子串造成重复匹配，将耗费大量的时间，使检测效率降低。如果使不同的检测器尽量包含不同的检测因子，这将大大提高检测器的性能。传统的算法没有充分利用自体集的模式信息，本文提出的检测器的生成算法，第一部分采用文献[47]中提取自体集每个分段补集的方法，即对长度为L的字符串集合，匹配位长度为r，其每个自体有L-r+1个分段，依次提取自体集r中每段r位字符串，由于包含这些段信息的字符串会与自体匹配，所以根据与2所产生的全局空间比较得到所有自体段中每段r位字符串的补集，这些补集都不能与自体匹配，因此将作为检测器的组成部分。例1自体集合为{100000,101101,111001}。在r=3时，产生的关于自体集的补集为：C1~3=[000，001，010，011，110]；C2~4=[001，010，100，101，111]；C3~5=[001，010，011，101，111]；C4~6=[010，011，100，110，111].上述各个补集的意义为，合格的检测器的1~3位应该为C1~3[]中的字符串；第26 河北工业大学硕士学位论文2~4位应该为C2~4[]中的字符串；第3~5位应该为C3~5[]中的字符串，第4~6位应该为C4~6[]中的字符串，也就是说若C1~3[]中某个字符串的2，3位与C2~4[]中某个字符串的1,2位相同，则可将C2~4[]中字符串的第3位链接到C1~3[]中对应字符串的第4位，因为C1~3[]中串的第4位只有0或1两种形式，因此可以将串链接的过程表示为二叉树链接的方式，以此类推，直到得到达到固定检测率的检测器集合，但上述做法，势必会造成大量的冗余，因为每个补集段中的字符串只充当一个检测因子的作用，但是其会被多次链接为检测器，这样会造成大量的检测器存在重复检测因子，不但加大了工作量而且降低了检测效率。4.2.24.2.2基于集合的划分与覆盖的检测器生成算法4.2.2基于集合的划分与覆盖的检测器生成算法定义111设1A是任意集合，p是由A的若干子集组成的集合。如果下列3个条件成立：（1）对于任意AiÎp，均有Ai¹F；（2）任意Ai，AjÎp,i¹j,有AiÇAj=F；（3）UAi=A。AiÎp则称p是集合A的一种划分。定义222设2A是集合，如果这些非空子集的并集等于A，则由A的若干非空子集[48]构成的集合称为A的覆盖。集合A的覆盖不必要求两个不同的子集不相交。L算法如下：设字符串长度为L，匹配位长为r，将自体集分段，在全局空间U对应产生自体集合的补集为C1[],C2[]…Cs[]。C1[],C2[]…Cs[]中各个补串的长度为r。根据集合的覆盖与划分的定义，所产生的检测器集合最理想的情况是链接上补集中所有的串，这样就能产生覆盖所有的非自体空间，同时使补集中的串链接且只链接一次，这样就能保证所产生的检测器集合最小，也就是产生补集的划分，然而在真实的网络检测环境中，所产生的自体集的补集并不能保证都能链接成检测器，有的补集中的串要被链接多次，有的补集中的串一次都不会被链接到。在这种情况下，就要尽可能地产生补集的覆盖，尽可能多的链接上补集中的串，同时使补集中的串重复链接次数最小。具体实现步骤如下：（1）从C1[]中的第一个串开始与C2[]中的串进行比较，C1[]中每个串的第2…r位与C2[]中的1…r-1位进行比较，这可能会出现三种情况，C1[]中的串的2…r位与多个C2[]中的串的1…r-1位匹配；C1[]中的串的2…r位与只与一个C2[]中的串的1…r-1位匹配；C1[]中的串的2…r位与C2[]中的串的1…r-1位无匹配。首先链接C1[]中的那些2…r位只与一个C2[]中的串的1…r-1位匹配的串，将C2[]27 基于集合的划分与覆盖的计算机病毒检测研究中对应串的第r位添加到C1[]中对应串的后面，这样就能尽可能的向集合的划分靠拢，接着依此规则链接C2[]与C3[]中的串，直到Cs-1[]与Cs[]中的串链接完毕。（2）对C1[]中每个串的第2…r位与多个C2[]中的1…r-1位串匹配的串，从C2[]中未被链接的串中任选一个进行链接，每次链接都依此规则，形成新的检测器。（3）经过前面两部骤，补集中会剩下两类串，一类是和本数组内的串有前r-1位匹配，为了保证最大的非自体空间覆盖率，对这类串进行回溯，与前面的补集段中的串进行链接，再向后递归，链接成检测器；还有一类串是不管回溯和递归都不能链接成检测串，对这些串就进行放弃。依据此算法，对例1中的补集链接成检测器恰巧能构成补集的一个划分。如图4.1所示。图4.1检测器链接过程产生的检测器集合为{000100；001010；010011；011111；110110}。这个检测器集合把自体补集中的所有检测因子都包含在此检测器集中，因此这个检测器集合能覆盖所有的非自体空间，同时由于每个补集中的串链接且只连接了一次，因此这个检测器集合所包含的检测器个数是最少的，比经过去除冗余之后产生的检测器还要少。这将大大降低空间复杂度。复杂性分析：本算法的时间复杂度为产生自体集合相应段的补集的时间和链接成检测器的时间，对于Ns个自体集合依据r连续位匹配，每个自体产生L-r+1个分段，因此算法第一步的时间复杂度为Ns*（L-r+1）*r，链接成检测器这一步骤为取到每个补集段中的串按照划分与覆盖的原则进行链接，其时间复杂度为Ns*（L-r+1）*（r-1），所以总的时间复杂度为Ns*（L-r+1）*（2r-1）。空间复杂度为链接成的检测器集合的大小为：2r-Ns。4.2.34.2.3实验分析4.2.3实验分析28 河北工业大学硕士学位论文为了验证本文提出的算法的性能和检测效果，本文在Windows7平台下进行了仿真实验。实验环境为：CPU为intel双核酷睿2P7450，内存2G，运行环境为Matlab7.10。为了与已有检测器的生成算法相对比以及简便起见，在这部分的试验中，暂时不考虑检测器的生命周期问题。实验分为两组，第一组测试在同样的检测失败率条件Pf下，去除冗余后的线性时间检测器生成算法，层次匹配检测器生成算法，本文算法，产生的检测器个数比较以及所耗费的时间比较。第二组实验验证在相同数量的检测器个数下，三种算法能成功检测非法集合的概率。实验参数设置及实验过程如下：（1）L=8,生成256个8位的二进制串，依次随机选取8，16，32，64，128个二进制字符串作为自体，其余的二进制串作为抗原，位串间采用的匹配位长度r为6。Pf设为0.1，重复随机产生自体个数的步骤50次，统计在不同的自体个数下，三种算法在确定的匹配概率下，需要的平均检测器个数和消耗的平均时间比较。如表4.1和表4.2所示。表4.1三种算法在固定的检测失败率Pf下所需检测器个数NS去除冗余后的线性检测器生成算法层次匹配检测器生成算法本文算法8941303216761172432561001964409715128369412表4.2三种算法在固定的检测失败率Pf下消耗的平均时间NS去除冗余后的线性检测器生成算法层次匹配检测器生成算法本文算法82012101633251432654020649060301281157050（2）采用（1）中产生的检测器，对应相同数量的自体，将剩下的检测器作为抗29 基于集合的划分与覆盖的计算机病毒检测研究原，统计在相同数量的检测器个数下，三种算法成功检测到非自体的平均值。如表4.3所示。表4.3三种算法在相同数量的检测器集合下检测成功率NS去除冗余后的线性检测器生成算法层次匹配检测器生成算法本文算法80.900.750.96160.860.790.93320.810.800.92640.850.830.941280.920.850.98由表4.1和表4.2可以看出，本文算法相比于前两种算法，在同样的检测失败率下，产生的检测器数量大大减小，同时耗费的时间也明显降低。由表4.3可知，在同样的检测器数量下，本文算法的检测效率最优，检测效果最好。4.3漏洞研究即使一个检测器生成算法能够构造出一个完全的检测器指令系统，这也不一定意味着这个检测器系统能够覆盖所有的非自体空间，也就是说，在特定的匹配规则下，在自体集中的某些字符串是非法的，不能产生有效的检测器来发现它，这些字符串成为“黑洞”。生物免疫系统中也存在着同样的问题，即有些病原体不能被免疫系统检测到，黑洞的存在严重影响着检测系统的性能。若外来抗原不能别检测器识别，将被当作自体加入到自体集合中，使受保护的数据发生了改变，所以非常有必要分析检测系统中存在的漏洞。4.3.14.3.1漏洞产生的原因4.3.1漏洞产生的原因所谓黑洞就是一个非我模式串aÎN，对于属于自体集中的任意一个字符串s，有Match（s，a）=True，那么a就为一个检测漏洞。黑洞是不能通过产生相应的检测器检测出来的。黑洞的直观示意图如图4.2所示。30 河北工业大学硕士学位论文4.2黑洞直观示意图黑洞存在于任何匹配规则中。模式集的结构和所采用的匹配规则是黑洞产生的原因。自体集中的模式串与非自体集中的模式串越接近，黑洞的数量就越多。自我模式集的相似程度越高，产生的黑洞就越少。随着匹配位长度R的减少，漏洞数量将会增加。极端情况下，当R=0时，所有的非自体都是一个检测漏洞，当R=L（字符串本身长度）时，不存在不被检测到的漏洞。比如自体集S包含两个字符串s1和s2:s1：a1…akbk+1…bk+r-1ck+r…cl’’’’s2：a…ab…bc…c1kk+1k+r-1k+rl由s1和s2生成个体h1和h2:’’h1：a…ab…bc…c1kk+1k+r-1k+rl’’h2：a1…akbk+1…bk+r-1ck+r…cl组成h1和h2的任意r位长度的子串都不能被检测到，因为h1和h2都与s1和s2匹配。而h1和h2又不属于自体集，所以h1和h2就成为系统的检测漏洞。4.3.24.3.2如何检测漏洞4.3.2如何检测漏洞漏洞的存在严重影响检测器的性能，在生物免疫系统中同样存在着漏洞，并且病原体总是趋于漏洞方向进化，增加了被检测到的难度。在目前的阴性选择算法中，大都存在着检测漏洞，降低了检测器集的性能。D’haesseleer提出了一个在连续位匹配规则下，计算漏洞的算法。张衡等提出了一种r可变阴性选择算法，降低了黑洞的数31 基于集合的划分与覆盖的计算机病毒检测研究量，但是无法确定漏洞数量减少的程度大小，而且匹配阈值的变化使系统性能发生变化。在生物免疫系统中是利用MHC机制来应对黑洞问题的，借鉴这一免疫机制提出在同一种匹配规则下，使用多种模式表示法来降低黑洞数量，该方法同样会影响系统性能。还有一种思路是判断一个字符串是否是漏洞，魏春英、吴开兴等给出了这种方[49][50][51]法。Stibor利用自体模式间的相关信息提出了探测漏洞的一种方法。Stibor方法的思想是：（1）将自体集中的自体Si分为l-r+1个长度为r的子串，即：Sij：=Si[j,…,r-1+j]，j=1,…,l-r+1，i=1,…n。（2）将子串Sij与子串Sk,j+1进行链接，判断Si，j的后r-1位串值与串Sk,j+1的前r-1位串值是否相同，i=1,…,n，k=1,…,n，j=1,…,n-1。（3）遍历每一个子串，Si,1，…,Si,l-r+1，按此方法进行链接以此来得到不能被检测到的漏洞集合H。例2S={01001，00001，10100，11101}，l=5，r=3，利用Stibor方法产生漏洞的过程为：首先将自体集合S中的每一个字符串拆分为3个长度为3的子串，去掉相同的子串，然后进行子串的重新链接过程。如图4.3所示：图4.3Stibor漏洞产生过程图示产生的字符串集合为{01001，00001，10100，10101，11100，11101}，去除与自体匹配的字符串，得到的漏洞集合H为{10101，11100}。Stibor方法产生的漏洞不会被相应的检测器检测到，但是Stibor法计算出的漏洞不具备完备性。比如字符串00000，01000，因为这两个字符串最后三位的特殊性，导致这两个字符串不能被检测器检测到，因此是检测系统中存在的漏洞。4.3.34.3.3一种新的检测漏洞的方法4.3.3一种新的检测漏洞的方法4.3.3.1算法简介32 河北工业大学硕士学位论文本文提出了一种基于集合间划分与覆盖关系的检测器生成算法，在自体集的补集串的链接过程中，存在三种情况：（1）所有的补集串链接且只被链接一次，达到集合的划分的效果。（2）有的补集串被多次链接到，最终达到集合的覆盖的情况。（3）有的补集串一次都没有链接到。针对检测器产生过程中的这三种情况，提出一种新型的计算漏洞的方法。对于第三种情况，没有被链接到的补集串，说明没有被作为检测器的一部分，也就是说含有这部分集合的抗原是不会被检测到的，也就会有漏洞的情况发生。针对例2中的自体集合，介绍新算法计算漏洞的过程。针对例2中的自体集合，首先按照基于集合间划分与覆盖关系的否定选择算法产生检测器集合，过程如图4.4所示：图4.4检测器产生过程由图4.4可以看出，C3~5中的补集串000没有被链接到，含有这个串的抗原可能会成为漏洞，因为找不到有效的检测器发现它。本文提出的检测漏洞的方法需要结合自体集的分段信息和检测器产生过程中的补集串信息，过程如下：（1）将自体集合中的每个元素分为l-r+1个长度为r的子串，去除相同的子串，减少不必要的操作；（2）将检测器生成阶段没有被链接到的串添加到上述集合中；（3）将子串Sij与子串Sk,j+1进行链接，判断Si，j的后r-1串值与串Sk,j+1的前r-1个串是否相同，i=1,…,n,k=1,…,n,j=1,…,n-1。如果相同则将Sk,j+1的末位添加到Sij串的后面；（4）依此类推，得到全部漏洞串集合，并去除与自体集合中串相同的元素。依据此算法，对例2中的串产生漏洞集合的过程如图4.5所示：33 基于集合的划分与覆盖的计算机病毒检测研究图4.5漏洞产生过程产生的漏洞集合为{01000，01001，00000，00001，10100，10101，11100，11101}，去除与自体集合相同的串，则产生的漏洞集合为{00000，01000，10101，11100}。Stibor方法没有检测出来的漏洞{00000,01000}被本文算法检测出来了。可以看出本算法产生的漏洞数量较Stibor算法产生的漏洞数量多。能够产生全部的不可被检测到的漏洞集合。4.3.3.2复杂性分析因为本文提出的新的检测漏洞的方法需要的未被链接到的补集串集合可以根据检测器产生过程直接取得，所以本算法具有与Stibor算法相似的复杂度。都取决于每一层匹配的成功的个体数。最坏情况下的复杂度为从第二层到第L-r+1层得到的个体L-r数为2到2，设第一层个体数为Ns，算法的复杂度为：L-rL-r2Ns/2*（1+2+…+2）*Ns=2*Ns。（4.6）4.3.3.3实验分析为了对比本文提出的漏洞检测算法的性能，对Stibor提出的漏洞检测算法和本文的算法进行了实验仿真。实验环境为第三章中采用的实验环境,测试在自体集分别为8,16,32,64,128的条件下，两者检测出的漏洞数量的平均值。运行环境为Matlab7.10。实验步骤如下：（1）随机产生8，16，32，64，128个L长度的自体集；（2）根据产生的自体集，利用改进的否定选择算法产生检测器集合；（3）产生用Stibor提出的方法产生的漏洞集合H1；（4）根据本文提出的方法，产生漏洞集合H2；（5）运行本次实验50次，计算出H1和H2产生的漏洞集合的平均数。34 河北工业大学硕士学位论文实验结果如表4.4所示：表4.4算法产生漏洞数量对比NSStibor算法本文算法822216432327486497012815133由表4.4可以看出，在相同的复杂度情况下，本文提出的算法探测漏洞的效果更好，探测出的漏洞数量远远多于stibor算法。4.4本章小结本章深入分析了否定选择算法的原理和性能，针对层次匹配检测器生成算法的不足，提出了一种基于集合间划分与覆盖的检测器生成算法，理论分析和实验结果表明，改进后的算法时间消耗和空间消耗将会大大降低，从而检测效率将会提高。在基于集合的划分与覆盖的检测器生成算法的基础上，提出了一种新的计算漏洞的方法。该方法利用检测器生成过程中未被利用的补集串，再利用自体集分段的信息进行链接，产生漏洞的集合，经理论分析与实验结果表明该方法产生的检测器集合多于Stibor计算漏洞的方法产生的漏洞数量，具有更好的完备性。35 基于集合的划分与覆盖的计算机病毒检测研究36 河北工业大学硕士学位论文第五章实验与分析实验与分析5.1基于集合间关系的病毒检测模型本章基于集合间的划分与覆盖原理的检测器生成算法，建立一个计算机病毒检测模型，验证新的算法在检测抗原方面的性能。5.1.15.1.1自体集5.1.1自体集、、、非自体集的编码方式、非自体集的编码方式在计算机当中，自体指正常的数据文件和程序等，非自体指外来入侵包括恶意攻击、病毒等。在构造自体集、非自体集和检测器集合前，需要先定义元素的编码方式，同样在免疫系统中，抗体和抗原的表示方式也具有举足轻重的作用。本文建立的病毒检测模型采用的免疫算法是对生物免疫系统中抗体对抗原检测过程的模拟。目前常用的免疫算法的编码方式有字符编码、实值编码和灰度编码等[52]。由于在网络环境中，捕获到的数据包都是由0、1代码组成的二进制序列，计算机当中的数据都是以二进制方式保存的，二进制编码相比其他表示方法更加简洁，尽管用这种方式构造的模式集会破坏某些原始数据信息的完整性，但是这种表示方法使整个模型更具有普适性，同时对匹配算法的要求也随之降低。所以本模型采用二进制编码方式。5.1.25.1.2模型框架5.1.2模型框架模型中核心的部分是检测器的产生和进化过程。初始检测器是用二进制字符串表示的，长度为L，该字符串是系统随机产生的，使用改进后的算法产生候选检测器集合，如果候选字符串在生成期内没有检测到外来入侵，就会从候选检测器集合中清除。候选检测器集合如果检测到抗原，则将其放到成熟检测器集合中，当成熟检测器集合中的检测器检测到的抗原入侵到达设定的激活阈值，就放入记忆检测器集合中。在检测外来抗原的入侵时，首先将抗原与记忆检测器集合中的检测器进行比对，如果匹配，则检测到异常，清除抗原。抗体抗原间采用r连续位匹配规则。本文建立的病毒检测模型包括数据处理模块，检测器生成模块和病毒检测模块。模型的框架图如图5.1所示：37 基于集合的划分与覆盖的计算机病毒检测研究图5.1病毒检测模型模型分为训练阶段和检测阶段。训练阶段是建立自体集和生成成熟检测器的过程。在构造自体的过程中，需要保证系统的运行状态是安全的，没有受到非法入侵。对正常的网络模式进行特征提取，放入到自体集合中，这个过程只是提取过程并不进行合法性的检测。每提取一个新的字符串，将该字符串与自体集合中的自体进行比较，如果已有相同模式的自体，则将该字符串删除，防止自体集合出现冗余。自体集合的构造过程具有非常重要的意义，影响着病毒检测的效果。训练期一般比较长，是为了保证自体集合的准确性和整体性。当自体集合中自体的数量达到要求时，将进入产生检测器的阶段。检测器的产生38 河北工业大学硕士学位论文不是随机的，根据集合间划分与覆盖关系的原理产生成熟检测器集合，用以检测异常。此时训练期结束。训练期产生了大量不与自体匹配的成熟检测器集合，对网络中的活动进行检测。提取网络活动的模式串与记忆检测器集合中的检测器进行匹配，匹配不成功后再与成熟检测器集合中的检测器匹配，如果匹配成功则证明检测到入侵，向控制中心发送报警信号。为了使生成的成熟检测器集合中的检测器更具有适应性，需要对其进行变异。通过统计每个检测器与抗原之间的海明距离来作为抗体与抗原的亲和力，对亲和力低的检测器进行高频变异，对亲和力较高的检测器进行低频变异。本模型使用离散变异的方法，应用的是matlab工具箱中的mut函数。公式为：yi=mut（xi,Pm）（5.1）xi为需要进行变异的检测器，yi为变异后的检测器，Pm代表对xi哪个位置发生了变异，PmÎ(0,1]5.2实验数据来源选取KDPCUP99作为本次仿真实验的数据集。这个数据集来源于模拟的美国空军军事网络上的9个礼拜的网络数据流，总共七百多万条网络连接记录，五百多万条训练数据和二百多万条测试数据。这个数据集主要分为以下四类：（1）拒绝服务攻击（DenialofService，Dos）此类攻击是指向目标服务器发送大量请求，导致服务器无法提供其他服务，甚至瘫痪。此数据集中一种出现了11种具体的Dos攻击。（2）未授权的远程访问攻击（RemotetoLocal，R2L）指的是没有目标主机账号的入侵者，利用发送数据包的方式，得到目标主机的本地访问权限的一种攻击方式。此数据集中一种出现了14种具体的R2L攻击。（3）未授权获取权限的攻击（UsertoRoot，U2R）这种攻击方式指的是黑客通过一些技术手段获得某台主机系统管理员权限的攻击。此数据集中一种出现了7种具体的U2R攻击。（4）探测与扫描攻击（Probing）此种攻击是指通过扫描DNS服务器，以获得有效IP地址、操作系统类型等新兴的攻击方式。此数据集中一种出现了6种具体的Probing攻击。KDDCUP数据集的任意一条数据记录都是由42个属性组成的，第42个属性表示数据的行为状态，包括“normal”和“abnormal”这两种类型。用normal属性建立自体集合，非常便捷。前41个属性可以归纳为四类，如表5.1所示：39 基于集合的划分与覆盖的计算机病毒检测研究表5.1KDDCUP数据记录属性分类包含的属性duration,protocol_type,service,falg,src_bytes,dst_bytes,基于单一网络连接功能的特征信息wrong_fragment,urgent.hot,num_failed_logins,logged_in,num_compromised,root_shell,su_attempted,num_root,num_file_creations,nu基于单个服务的特征信息m_access_files,num_outbound_cmds,is_hot_login,is_guest_login.dst_host_count,dst_host_srv_count,dst_host_name_srv_rate,dst_host_diff_srv_rate,land,dst_host_name_src_port基于主机的特征信息_rate,dst_host_srv_diff_host_rate,dst_host_serror_rate,dst_host_srv_serror_rate,dst_host_rerror_rate,dst_host_srv_rerror_rate.count,srv_count,serror_rate,srv_serror_rate,rerror_rate,s基于时间的特征信息rv_rerror_rate,diff_srv_rate,srv_diff_host_rate.5.3实验结果分析KDDCUP数据集包括七百多万条数据，数据量特别大，为了方便实验，从中选择了部分数据当作实验用的数据。利用数据集中的正常数据作为自体数据，共选取了300条。从数据集中的测试数据集中随机选取5000条作为测试数据。实验分为两组，第一组测试数据中包括正常数据3000条，异常数据2000条。异常数据的2000条记录全部为已知入侵。第二组测试数据包括正常数据3000条，异常数据2000条。异常数据的2000条记录其中1000条为未知的入侵，1000条为已知入侵的变异。从自体集、训练集和测试集中的数据选取具有代表性的11个属性，进行预处理，得到32位长度的二进制字符串，匹配阈值r=13。这11个属性如表5.2所示。40 河北工业大学硕士学位论文表5.2选取的11个属性位置属性名称代表的意义类型2protocol_type协议类型离散3service目标主机的网络服务类型离散4flag连接正常或错误的状态离散5src_bytes从源主机发往目的主机的数据连续6dst_bytes从目的主机发往源主机的数据连续10hot访问系统敏感文件和目录的次数连续17num_file_creations文件创建操作的次数连续23count在当前两秒内，连接到同一台主机的次数连续24srv_count过去两秒内，与当前连接具有相同服务的连接数连续32dst_hot_count过去两秒对同一主机发出的连接数连续33dst_host_srv_count两秒内当前连接服务相同的连接数连续本文进行了两次实验，实验1验证新建立的算法和原始层次匹配检测器生成算法建立的病毒检测模型对已知入侵的检测效果。实验2验证改进后的算法和原始层次匹配检测器生成算法建立的病毒检测模型对未知入侵以及已知入侵变异的检测率。图5.2本文算法与原有算法对已知入侵的检测率41 基于集合的划分与覆盖的计算机病毒检测研究图5.3本文算法与改进算法对已知入侵和未知入侵的检测效果由图5.2可知，本文算法相对于原始层次匹配检测器生成算法检测率略有提高。由图5.3可知，本文算法相对于原始层次匹配检测器生成算法对未知病毒入侵和已知病毒入侵的变异的检测效果都要好。5.4小结本章在改进的否定选择算法的基础上，建立了一个病毒检测模型。选用KDDCUP99数据集进行了仿真实验，对比本算法和原始层次匹配检测器生成算法在检测未知病毒、已知病毒及其变种方面的效果。42 河北工业大学硕士学位论文第六章结论结论6.1论文总结本课题通过大量参阅国内外文献，首先介绍了病毒检测算法的课题背景和国内外相关研究现状。接着介绍了计算机病毒检测和人工免疫的相关理论，介绍了计算机病毒的相关知识，概述了人工免疫的相关算法，对基于人工免疫的计算机病毒检测研究的进展情况进行了介绍。分析了病毒检测的核心算法，对否定选择算法进行了分析，在层次匹配算法的基础上，提出了一种基于集合间划分与覆盖关系的新的检测器的生成算法。该算法用最小的检测器集合覆盖最大的非自体空间，大大减少了检测器的数量，提高了检测效率。针对否定选择算法不可避免的存在漏洞问题，在改进的否定选择算法的基础上，提出了一种新的检测漏洞的方法，经理论分析与实验验证，该方法能计算出比传统漏洞探测方法更多的漏洞。最后根据改进的否定选择算法，建立了基于改进算法的一种病毒检测的新模型，并验证了模型在检测已知入侵、未知入侵和已知入侵变异的检测效果。6.2结论展望病毒检测算法研究一直是病毒检测方面研究的核心。本文在深入研究人工免疫系统原理的基础上提出了一种改进的检测器生成算法，提高了检测已知病毒和未知病毒的效果。建立了一种基于改进算法的一种病毒检测新模型，该模型在某些方面还需要进一步改进：（1）模型的自我更新能力有待提高。生物免疫系统中是一个不断更新的系统，具有自适应性，需要更进一步加深对否定选择算法免疫机理的研究。对免疫机理的深入认识，能够为算法构建提供强大的理论支撑和保障，并且发现新机理将有助于发现新算法。（2）对匹配规则的改进。现有的匹配规则不可避免的导致大量漏洞的产生，而且缺乏自适应性。无论是基于字符串还是基于实值向量的匹配规则都具有局限性。研究新的匹配规则或对现有匹配规则进行改进，将在很大程度上提高算法的性能。（3）加强对否定选择算法的数学理论分析。数学理论的支撑将会对算法改进开辟新的思路，为进一步提高算法的性能提供理论依据。43 基于集合的划分与覆盖的计算机病毒检测研究44 河北工业大学硕士学位论文参考文献[1]张明杰.计算机病毒发展的新趋势研究[J].计算机工程应用技术,2009,5(24):6896-6897.[2]肖英,邹福泰.计算机病毒及其发展趋势[J].计算机工程,2011,37(11):149-151.[3]DasguptaaD,YuaS,NinoF.Recentadvancesinartificalimmunesystems:modelsandapplications[J].AppliedSoftComputing,2011,11:1574-1587.[4]ZhouJ,DasguptaD.Revisitingnegativeselectionalgorithms[J].EvolutComput,2007,15(2):223-251.[5]GongMG,JiaoLC,ZhangK.DynamicV-detectornegativeselectionalgorithmforintrusiondetection[A].ProceedingsoftheFourthInternationalConferenceonHumanizedSystems,ICHS’08[C].Beijing,China,2008.[6]岑建,胥布工,张清华.免疫检测器证据理论集成的机组复合故障诊断[J].控制与决策,2011,26(8):1248-1259.[7]刘占生,窦唯,王晓伟.基于人工免疫的直升机传动系统在线异常检测方法[J].航空学报,2007,28(8):739-744.[8]ChenLF.Animprovednegativeselectionapproachforanomalydetection:withapplicationsinmedicaldiagnosisandqualityinspect[J].NeuralComputing&Applications,2011,20:1-10.[9]EmmaHart,JonTimmis.ApplicationareasofAIS:Thepast,thepresentandthefuture[J].AppliedSoftComputing,8(2008):191-201.[10]AliRizaYildiz.Anovelhybridimmunealgorithmforglobaloptimizationindesignandmanufacturing[J].RoboticsandComputer-IntegratedManufacturing,25(2009):261-270.[11]ForrestS,PerelsonAS,AllenL,etal.Self-nonselfdiscriminationinacomputer[C].Proceedingsof1994IEEESymposiumonResearchinSecurityandPrivacy.Los,CA:IEEEComputerSocietyPress,1994.[12]TesaurlG,KephartJ,SorkinG.Neuralnetworksforcomputervirusrecognition[C].IEEEExpert,1996(11):5-6.[13]KimJ,BentleyPJ.TowardsAnArtificialImmuneSyetemforNetworkIntrusionDetection:AnInvestigationofDynamicClonalSelection[A].TheCongressonEvolutionaryComputation(CEC-2002)[C].WashingtonD.C.:IEEEPress,2000,1015-1020.[14]李涛.计算机免疫学[M].北京:电子工业出版社,2004.7-52.[15]金章赞,廖明宏,肖刚.否定选择算法综述[J].通信学报,2013,34(1):159-170.[16]中华人民共和国公安部公共信息网络安全监察局.2006年全国信息网络安全状况与计算机病毒疫情调查分析报告,2006.http://www.antivirus-china.org.cn/content/report2006.doc.[17]李晓勇,周丽涛,石勇等.虚拟行为机制下恶意代码检测与预防[J].国防科技大学学报,2010,32(1):101-106.[18]秦志光,张凤荔.计算机病毒原理与防治[M].人民邮电出版社,2007.20-30.[19]刘晋辉.计算机病毒技术分析[J].兵工自动化,2012,31(1):93-96.[20]张红梅.基于人工免疫系统的未知木马检测系统研究与实现[D].成都:电子科技大学,2009.[21]陈保军.基于人工免疫的未知网络蠕虫检测系统的研究[D].济南:山东大学,2009.45 基于集合的划分与覆盖的计算机病毒检测研究[22]范晓峰.基于免疫系统的计算机病毒检测模型研究[D].桂林:桂林电子科技大学,2008.[23]张文杰.基于混沌免疫算法的计算机病毒检测方法研究[D].太原:太原理工大学,2011.[24]柴倩.基于人工免疫的病毒检测技术研究[D].南京:南京邮电大学,2012.[25]Yanghaidong,Guojianhua,DengFeiqi.ArtificialImmuneSystemIntegrationandApplication[M].Beijing:SciencePress,2010(9):61-70.[26]赵云丰,尹怡欣,付冬梅等.禁忌免疫网络算法及其在函数优化中的应用[J].智能系统学报,2008,3(5):393-400.[27]赵红霞.基于新型否定选择算法的计算机病毒检测技术研究[D].太原:太原理工大学,2010.[28]BalachandranS,DasguptaD,NinoF.Aframeworkforevolvingmultishapeddetectorsinnegativeselection.ProceedingsofIEEESymposiumSeriesonComputationalIntelligence[C].HonoIulu,2007,401-408.[29]YiZX,MuXD,ZhangL.Amatrixnegativeselectionalgorithmforanomalydetection.2008IEEECongressonEvolutionaryCompution(CEC2008)[C].2008,978-983.[30]韩亮,李成云.免疫网络入侵检测中的r连续位匹配算法研究[J].软件导刊,2012,11(11):60-62[31]高苗粉,秦勇,李勇等.网络入侵检测系统自体集检测中的概率匹配高效寻优机制[J].计算机应用,2013,33(1):156-159.[32]肖赤心,蔡自兴,王勇等.进化策略用于阴性选择算法[J].小型微型计算机系统,2008,11:2091-2094.[33]王辉,于立君,毕晓君.具有疫苗算子的可变模糊匹配阴性选择算法[J].哈尔滨工业大学学报,2011,43(6):141-144.[34]ChmielewskiA,WierzchonSTV-detectoralgorithmwithtree-basedstructures[A].ProceedingsoftheInternationalMulticonferenceonComputerScienceandInformationTechnology.2006,9-14.[35]蔡涛,鞠时光,牛德姣.快速否定选择算法的研究与分析[J].小型微型计算机系统,2009,6:1171-1174.[36]孙秋丽,韩芳溪,王晓琳.基于检测树的抗原合法性快速检测方法[J].山东大学学报,2010,40(5):8-11.[37]杨铭魁.改进的变长检测器产生算法[J].计算机工程,2010,36(15):174-175.[38]LisjuewiczM,TextorJ.Negativeselectionalgorithmswithoutgeneratingdetectors.GECCO2010ACM[C].Porland,Oregon,USA,2010:1047-1054.[39]ElderfeldM,TextorJ.Efficientalgorithmsforstring_basednegativeselection[A].ProcofICARIS2009,volume5666ofLNCS[C].Springer,2009:109-121.[40]柴争义,吴慧欣,吴勇.用于异常检测的免疫实值检测器优化生成算法[J].吉林大学学报,2012,42(5):1251-1256.[41]张雄美,易昭湘,宋建社等.基于矩阵形式的否定选择算法研究[J].电子与信息学报,2010,32(11):2701-2706.[42]王辉,于立君,王科俊等.一种可变模糊匹配阴性选择算法[J].智能系统学报,2011,6(2):178-184.[43]敖民.基于阴性选择的检测器生成算法研究[D].重庆:重庆大学计算机学院,2010.[44]杨宁,王茜.一种基于小生境策略的阴性选择算法[J].计算机科学,2011,38(10A):181-184.[45]张清华,赵红霞,朱月君等.一种新型的否定选择算法生成检测器的研究[J].电子设计工程,2010,18(11):8-11.46 河北工业大学硕士学位论文[46]蔡涛,鞠时光,牛德娇.快速否定选择算法的研究与分析[J].小型微型计算机系统,2009,30(6):1171-1174.[47]刘星宝,蔡自兴.负选择算法中的检测器快速生成策略[J].小型微型计算机系统,2009,7(7):1263-1267.[48]邓辉文.离散数学[M].清华大学出版社,2010:29-32.[49]魏春英.基于免疫原理的入侵检测中的漏洞研究[J].计算机工程,2009,35(11):146-147.[50]吴开兴,王立功,郑凤.免疫机制入侵检测技术中检测器漏洞的研究[J].计算机与现代化,2005,4:50-53.[51]StiborT,MohrP,TimmisJ.Isnegativeselectionappropriateforanomalydetection.GECCO’05,Washington,DC,USA.2005,321-328.[52]姜恩龙.基于否定选择的检测器生成算法研究[D].哈尔滨：哈尔滨理工大学,2007.47 基于集合的划分与覆盖的计算机病毒检测研究48 河北工业大学硕士学位论文攻读硕士学位期间所取得的相关科研成果[1]刘恩海,宋瑞平.否定选择算法中高性能检测器生成研究[J].《计算机工程与设计》已录用.49 基于集合的划分与覆盖的计算机病毒检测研究50 河北工业大学硕士学位论文致谢时光飞逝，岁月如梭，转眼间，又到了一年毕业时，即将在这美好的季节里告别我的学生生涯。在河北工业大学的两年半的硕士学习生活中，我收获了很多，成长了很多。经历过快乐，感受过迷茫，这段短暂而美好的时光将会永远的刻印在我记忆中。感谢我的导师刘恩海教授。在刘老师的悉心指导下，从论文的选题到课题进展中的每一个环节，刘老师都给了我方向上的指引，思想上的启发。刘老师一丝不苟的学术作风，使我对课题研究认真严谨，使我积累了大量的知识，刘老师更教会了我谦和真诚的处世态度。他在学术上对我孜孜不倦的教诲，在生活上细心的关心与照顾，成为我前进道路上的思想明灯，在此向关心教育我的刘老师致以最真诚的感谢。感谢计算机学院的每一位老师，他们在学术研究上的兢兢业业，开阔了我的眼界，使我接触到更广范围内的前沿知识。感谢小组的耿恒山老师，对我课题研究进展给予的针对性和建设性的意见，使得我在困惑面前茅塞顿开。感谢帮助过我的各位同学，你们的鼓励和陪伴成为前进的不懈动力，和大家一起走过的日子我非常幸福，这段日子是我一生的财富。特别感谢参考文献的作者，你们的研究工作和学术成果，使我的论文有了参考的资料，给了我巨大的启发。感谢我的父母，是你们默默的支持和信任给了我前进的动力，感谢你们对我的包容，你们的爱是那么无私，那么浓烈。此外，还要感谢我所有亲朋好友，正是你们的关心鼓励使得我不断的进步。感谢河北工业大学，给我了一个成长的环境，学习的平台，促使我成长，促使我进步。51