人工免疫系统及其在计算机病毒特征提取中的应用

1、人工免疫系统及其在计算机病毒特征提取中的应用黄宏伟 （ 100320 ）摘要： 本报告在相关参考文献的支持下得到。 对于计算机病毒问题的日益重视， 相关的病毒 特征提取算法也一直在快速发展。 受自然免疫系统的启发， 人工免疫系统也逐渐被关注并得 以应用。这样得到一种基于人工免疫的利用计算机病毒代码相关性的计算机病毒特征提取方 法。根据文献， 这种特征提取方法在底层提取出与病毒相关的字节模式， 在相对更高的层面 上记录这些字节模式之间的共同作用信息， 之后利用阴性选择算法提取出计算机病毒检测基 因库，实现了对训练集上合法程序的完美记忆， 从而保证了该文方法的误判率处于极低的水 平。关键字：计算机

2、病毒；人工免疫；阴性选择；特征匹配；代码相关性1 引言 在自然界，生物体得以在各种病毒与细菌之间安全地生存，得益于生物体自 身的免疫系统， 有效地保护生物体不受各种有害病毒的伤害。 自然免疫系统可以 识别身体内部异己的成分，并将这些对自身有害的部分消灭清除。计算机病毒是隐藏在计算机软件中间的一些程序代码。计算机学界的科学家 们通过对自然免疫系统的模拟， 建立了人工免疫系统模型， 可以有效的将计算机 软件中的“异己”成分识别出来， 从而使得计算机能够处在一种类似 “自我保护” 的状态中。本报告根据相关的文献，对计算机病毒 4 、人工免疫系统 2 （其中的阴性选 择算法 23 ）等做出介绍，重点讲

3、述一种基于人工免疫和代码相关性的计算机 病毒特征提取方法 1。2 计算机病毒计算机病毒（Computer Virus）在中华人民共和国计算机信息系统安全保护条 例4中被明确定义，病毒指“编制者在计算机程序中插入的破坏计算机功能 或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代 码”。而在一般教科书及通用资料中被定义为：利用计算机软件与硬件的缺陷， 由被感染机的内部发出的破坏计算机数据并影响计算机正常工作的一组指令集 或程序代码。计算机病毒具有的几个特点：寄生性；传染性；潜伏性；隐蔽性；破坏性； 可触发性。由于这些特点， 计算机病毒往往会造成计算机资源的损失和破坏。 这 不

4、但会造成资源和财富的巨大浪费， 而且有可能造成社会性的灾难， 随着信息化 社会的发展， 计算机病毒的威胁日益严重， 反病毒的任务也更加艰巨了。 计算机 病毒具有很强的隐蔽性，时隐时现、变化无常，这类病毒处理起来通常很困难。 而免疫系统具有天然的病毒处理能力， 故而人们想到采用人工免疫系统来提取计 算机病毒的特征，保护计算机系统的安全。3 人工免疫系统 近年来，人们不断从生物系统获得灵感，提出了若干采用计算途径实现的学 习系统。生物免疫系统是一个高度进化的生物系统， 它旨在区分外部有害抗原和 自身组织， 从而清除病原并保持有机体的稳定。 从计算的角度来看， 生物免疫系统是一个高度并行、分布、自适

5、应和自组织的系统，具有很强的学习、识别、记 忆和特征提取能力。人们自然希望从生物免疫系统的运行机制中获取灵感，开发面向应用的免疫系统计算模型人工免疫系统(Artificial Immu ne System , AIS)用于解决工程实际问题。目前，AIS已发展成为计算智能研究的一个崭新的分支。3.1人工免疫系统(AIS)的生物原型在生物自然界中，免疫系统是一个由执行免疫功能的器官、组织、细胞和分 子等组成的复杂系统。它是生物系统保护机体，抵抗细菌、病毒和其他致病因子 入侵的基本防御系统，它能够识别自身与异已抗原，并通过免疫应答排除抗原性 异物，维持机体的生理平衡。免疫系统的主要功能是识别体内细胞

6、，将其归类为“自我”和“非我”，并引发适当的防卫机制去除“非我”。自我对应于机体自身的组织；非我对应于外 来有害病原或者体内病变组织。免疫应答主要由分布在生物体全身的免疫细胞实 现。免疫细胞泛指所有参与免疫应答过程的相关细胞，包括吞噬细胞、NK细胞、淋巴细胞等。淋巴细胞又分为 B细胞和T细胞两种。B细胞的主要功能是产生抗体，且每个B细胞只产生一种抗体。免疫系统主 要依靠抗体来对入侵抗原进行攻击以保护有机体。T细胞的主要功能是调节其它 细胞的活动或直接对抗原实施攻击。成熟的 B细胞产生于骨髓中，成熟的 T细 胞产生于胸腺之中。B细胞和T细胞成熟之后进行克隆增殖、分化并表达功能。 两种淋巴细胞共同

7、作用并相互影响和控制对方功能，形成了机体内部高度规律的反馈型免疫网络。3.2人工免疫系统(AIS)的仿生机理从信息处理的角度来看，免疫系统具备强大的识别、学习和记忆的能力及分 布式、自组织和多样性特性，这些显著的特性不断地吸引着研究人员从免疫系统 中抽取有用的隐喻机制，开发相应的 AIS模型和算法用于信息处理和问题求解。 下图给出了 AIS仿生机理的主要内容描述，然后对各种典型的AIS仿生隐喻机理及其具体实现进行讨论。丸出生机理丄自适应 I井相式 丄爹样性- 丄克a选样- 丄免疫记忆- 丄a疫学习_I免疫说别一S网貉图1:人工免疫系统的仿生机理图中前4种AIS仿生机理对应于免疫系统的应答过程。

8、 免疫应答包括初次应 答和再次应答，初次应答是指免疫系统首次遇到一种抗原， 再次应答则是对已识 别抗原产生的免疫应答。免疫应答的实质是一个识别、效应和记忆的过程。免疫识别是免疫系统的主要功能，同时也是 AIS的核心之一，而识别的本质 是区分“自我”和“非我”，通过淋巴细胞上的抗原识别受体(rece ptor)与抗原的 结合(binding)实现的，结合的强度称为亲合度(affinity)。免疫识别过程同时也是一个学习的过程， 学习的结果是免疫细胞的个体亲合 度提高、群体规模扩大， 并且最优个体以免疫记忆的形式得到保存。 免疫学习大 致可分为两种：一种发生在初次应答阶段， 即免疫系统首次识别一种

9、新的抗原时， 其应答时间相对较长； 而当机体重复遇到同一抗原时， 由于免疫记忆机制的作用， 免疫系统对该抗原的应答速度大大提高， 并且产生高亲合度的抗体去除病原， 这 个过程是一个增强式学习 （ reinforcement learning） 过程，对应于再次应答。免疫记忆对应于再次免疫应答和交叉免疫应答， 而交叉应答是免疫系统对结 构相似的抗原所产生的免疫应答。免疫记忆属于联想式记忆，是 AIS区别于其它 进化算法的重要特性之一。克隆选择原理大致内容为：当淋巴细胞实现对抗原的识别（即抗体-抗原的亲和度超过一定阈值）后， B 细胞被激活并增殖复制产生 B 细胞克隆，随后克隆 细胞经历变异过程，

10、 产生对抗原具有特异性的抗体。 主要特征是免疫细胞在抗原 刺激下产生克隆增殖，随后通过遗传变异分化为多样性效应细胞（如抗体细胞） 和记忆细胞。 克隆选择对应着一个亲合度成熟的过程， 本质上是一个达尔文式的 选择和变异的过程。免疫网络理论对免疫细胞活动、抗体生成、免疫耐受、自我与非我识别、免 疫记忆和免疫系统的进化过程等做出了系统的假设， 并且将免疫系统视为由免疫 细胞或者分子组成的调节网络， 免疫细胞以抗体间的相互反应和不同种类免疫细 胞间的相互通信为基础，抗原识别是由抗原相互作用所形成的免疫网络完成的。抗体多样性的生物机制主要包括免疫受体库的组合式重整、 体细胞高突变以 及基因转换等。 多样

11、性仿生机理可以广泛应用于优化搜索过程， 特别是组合优化 与多峰函数优化。免疫系统的分布式特性首先取决于病原的分布式特征， 即病原是分散在机体 内部的；其次免疫系统的分布式特性有利于加强系统的健壮特性， 从而使得免疫 系统不会因为局部组织损伤而使整体功能受到很大影响。3.3 阴性选择原理未成熟的 T 细胞首先要经历一个审查环节，只有那些不能与自我发生应答的 T细胞才可以离开胸腺，执行免疫应答任务，该过程称为阴性选择，它是免疫识 别的一种主要方式。T细T细胞阴性选择是T细胞在胸腺中产生、成熟过程中的一个重要阶段。未成熟 胞在胸腺中与大量的“自己”细胞进行匹配操作，与“自己”细胞匹配的 死亡，只有不

12、与任何“自己”细胞匹配的未成熟T细胞才最终生长为成熟T细胞。 在计算机免疫系统中， 探测器生成过程采用阴性选择过程的称为遵循阴性选择原 则。1994 年 Forrest 等3提出了阴性选择算法。该算法很好地体现了阴性选择原 则的思想。 算法分两个阶段， 一是探测器生成阶段， 该阶段是探测器的产生和成 熟的过程，探测器由等长的字符串表示，成熟的探测器不与“自己”集中的任何 个体匹配。 该阶段称为评价 （ Censoring ）阶段。二是探测器监控 （Monitor） 阶段，在 该阶段利用比较输入字符串和探测器集的匹配情况来保护被保护的数据集。免疫细胞对抗原的识别是通过结合（或匹配）过程实现的，相

13、应地AIS中的抗原 识别通过特征匹配来实现， 其核心是定义一个匹配阈值， 而对匹配的度量则采用 多种方法，如Hamming距离、Euclidean距离以及Forrest2所提出的R连续位匹 配方法（见下图）等。阴性选择原理对应AIS中的阴性选择算法，其核心是根据识 别的对象特征进行编码，定义一个自我集合并随机产生一系列检测器， 用于检测 自我集合的变化。根据阴性选择原理，若检测集合与自我集合匹配，则完成匹配 任务。CIO10 11Ivl 01 001111loinR = 401匹配干匹配图2:阴性选择的R位连续匹配规则基于阴性选择原理，D 'aeseleer2给出了一种阴性选择算法，用

14、于监测数据 改变。其中抗体（问题解答）与抗原（问题）的匹配采用Forrest提出的部分匹配规则。 该算法的流程如下：SteP 1:有限字符表上，定义一组长度为L的字符串集合S来代表自我，用 于检测。SteP 2：产生检测器集合R,依据阴性选择原理，对每个检测器进行审查。 审查采用部分匹配规则，即两个字符串匹配当且仅当至少有 r个连续位相同，其 中r为参数。SteP 3:通过连续地将R中的检测器与S比较来监测S的改变。如果检测器 发生匹配，则有改变发生。该算法的优点是简便、易于实现，主要问题是计算复杂度呈指数级增长，难 以处理复杂问题。4 一种基于人工免疫和代码相关性的计算机病毒特征提取方法传统

15、的计算机反病毒方法是以特征检测为基础的，这些方法利用从病毒中提 取的特定特征来检测出有相似行为的病毒程序。它们对于已知或者是出现过的病 毒有着很高的识别率，但是对于没有出现过的未知病毒或者病毒的新变种缺乏快 速而准确的识别能力。以生物体为原型的计算机系统和自然生物系统有着天然的联系，而自然免疫 系统又具有强大的区分“自体”和“异体”的能力，这种功能与计算机安全系统 的反病毒功能极为类似。因此，借助自然免疫机理，如阴性选择机理、克隆选择 机理等机理，采用人工免疫模型来识别计算机中的合法程序（称为“自体”）和病毒程序（称为“异体”）成为病毒检测的一个可行的发展方向。在病毒的实际工作机理中，一个病毒

16、的多个指令都是相关的，病毒多个关键 代码的有机结合才产生了病毒作用。基于此思想，文献1提出了一种特征提取方法，充分利用了组成病毒的相关指令的相关性， 使得病毒特征的提取在个体层 上完成，将每个病毒样本的多个指令存放在此病毒样本对应的数据库空间中，采用与其特征生成、储存对应的匹配检测模式，并由此建立了模型。4.1特征的有向导生成通过对自然免疫过程的模拟产生的人工免疫系统，移植了相关的一些概念：（1）DNA:整个程序的bit串称为程序的DNA;（2）基因：病毒的检测器，DNA的片断，病毒检测的比较单元；（3） 脱氧核苷酸：每两个字节看作是一个脱氧核苷酸，记作ODN,若干个脱氧核苷酸组成了基因。病毒

17、程序的代码对应着生物体中的 DNA。少量起着病毒作用的关键代码被认 为是病毒的基因，这些基因由病毒的 ODNs组成。多个ODN的有序连接表示程 序的一个指令或多个指令的有序集合。病毒特征的初始选择采用了有向导的方式， 利用已知浓度的信息来统计每个 ODN趋向于代表病毒的程度。ODN i的合法程序数与所有合法ODN特征库就形成了，但是其中也 需要通过进一步的筛选。以此基本模型能够统计出ODN在合法程序和病毒程序中出现的频率信息。模型要根 据其频率信息，计算出每个 ODN趋向于代表病毒的程度：ODN i被挑选进入病 毒ODN库的概率与其在病毒程序所有 ODN中出现的频率成正比，与其在合法 程序所有

18、ODN中出现的频率成反比；与训练集中包含ODN i的病毒文件数与所 有病毒文件数的比例成正比，与训练集中包含 程序数的比例成反比。通过有向导的生成后，一个基本的病毒 存在着很多非病毒基因段或疑似病毒基因段， 库为训练集进一步训练。4.2特征的存储结构凸尝 最后为基实际的病毒运行机理是：（1）特征不应该为了计算的简洁方便而采取不符合 实际的固定长度；（2）多个特征并存才可以用来标识一个病毒， 而非只采用一个 病毒特征；（3）病毒的多个特征间是有极大的相关联系的。文献1依据这些特点，提出了在个体层上检测病毒的概念， 以充分利用多个相关基因的相关性。 试将每个病毒样本的多个基因存放在此病毒样本对应的

19、一个数据库空间中， 通过空间中的所有病毒进行两两匹配， 得出病毒个体之间定义出的相似度值， 充分利用多个基因的相关性提供基础。 这种存储方式被称为个体层上的存储。于有向导的特征生成方法，可以很好控制住 ODN的个数，特征存储的空间即可 被控制住，从而控制了最终匹配检测时的计算代价， 避免了出现训练的时间过长 而致模型失去实用性的问题。病毒基因库的基本存储单位是病毒样本个体。在每个病毒样本个体中，保存 了该样本的所有基因，这样就使得同一病毒的不同基因存放在一起， 不同病毒的 基因分离保存。每个基因是不定长的，每个样本储存的基因数目也不同。样本1样*3£因2*b1霸 'b本M&#

20、187;墓與M图3:病毒基因的储存方式4.3病毒基因库有向导地生成病毒特征的ODN库后（这是组成病毒特征的最基本单元），在 此基础上与任一程序的字符串进行匹配， 形成一系列不定数目的不定长 ODN串, 属于某个程序的储存在一起，不同程序的分开储存，从而得到了病毒基因库和类 病毒基因库，在这过程中，需要运用人工免疫方法中的阴性选择算法， 对初始得 到的这种病毒候选基因进行免疫，去除其特征表示的模糊状态，进而得到用来标 示文件可以应用于特征检测的检测基因库。训缘处图4:病毒候选基因库和检测基因库的生成模型利用第一步生成的病毒 ODN库中的ODN为训练集，采用连续匹配的方 式匹配病毒DNA，从而生成

21、病毒的候选基因。所谓连续匹配方式是指从第一个发 生匹配的位置开始，采用滑动窗口的方式向后进行匹配比较， 一直匹配前进，直 到发生间断为止，此时检查从开始匹配到结束匹配共有多少个病毒ODN库中的ODN参与了匹配，如果ODN数目超过某个阈值T,则将病毒DNA的这个片段作 为病毒基因，否则认为该片段不包含足够多的信息， 不是病毒的关键代码，即不 是病毒的基因。模型将所有生成的病毒基因都保存到与其对应的病毒样本的数据库空间中， 形成了病毒候选基因库。以同样的方法，将 ODN库中的特征片段与已知的合法 程序进行连续匹配，可以得到类病毒基因库。模型将合法程序的类病毒基因看作 “自体”，将病毒的候选基因看作“异体”， 采用T连续一致匹配规则，进行阴性选择，即一旦病毒的某个基因与合法程序的 任何一个基因匹配成功，则删除病毒的该候选基因。重复这个过程，直到病毒候 选基因库中所有和合法程序类病毒基因发生匹配的基因都被删除为止。至此，病毒候选基因库升级成为病毒的检测基因库。4.4特征的多层次匹配病毒库的生成，可以开始识别测试程序。在特征的匹配问题之上，为了提高 模型的准确度，在3个逻辑层面上进行逐一匹配。在对可疑程序进行检测时，在 底层，即基因层，采用了 T连续一致匹配规则，采用模糊匹配的方式来进行容错 匹配