计算机免疫学.ppt

1、计算机免疫学,哈尔滨理工大学 姚 亮 2007.6.13,Good Evening,主要内容,概述 生物学免疫系统机理 计算机免疫学基本原理 计算机免疫学的应用 结束与展望,第 1 页,计算机免疫学产生的背景自古以来，人们就对生物界有着浓厚的兴趣。生物成为许多发明家创新的灵感源泉，他们从生物现象中得到启示，制造出了从机翼到防弹衣等许多产品，从20世纪中叶开始，人们就已经开始注意对生物系统尤其是人类自身功能及结构的模仿，由此产生了许多研究领域。例如，人工神经网络是对人脑结构的模拟，模糊控制与人类模糊思维有着相似之处，而进化算法则是对生物的生存演化进行了描述。生物免疫系统是一种具有高度分布性的自适

2、应学习系统，具有完善的机制来抵御外来病源的入侵，计算机的安全问题与生物免疫系统遇到的问题惊人的相似，于是就有人提出来：是不是可以把生物免疫系统的这些特性用于计算机领域呢？,第 2 页,概 述,计算机免疫学的研究概况1974年，丹麦学者 Jerne 提出了免疫系统的第一个数学模型,奠定的免疫计算的基础。1984年，由于在免疫学上的杰出贡献， Jerne 因此获得诺贝尔奖。1994年，美国学者Forrest ,Perelson 等人提出了否定选择算法，用来生成检测器，完成了检测器的耐受过程，提出了计算机免疫系统的概念。在国内，有关计算机免疫的相关研究刚起步不久，2002年，武汉大学的梁意文教授利用

3、免疫原理对大规模网络入侵检测和预警技术进行了研究。,第 3 页,计算机免疫学的研究概况（续）2002年6月，IEEE Transaction on Evolutionary Computation 出专刊报道了有关人工免疫系统（Artificial Immune System, AIS）的研究进展，2002-2004年，国际上举办有关人工免疫的学术会议达20多次。2003年，中国科学技术大学研制了一个“基于人工免疫的入侵预警系统”，该系统具有较好的未知入侵检测能力。2004年，四川大学计算机网络安全与研究所提出了基于免疫的大规模网络入侵动态取证，以及网络安全风险检测与控制技术。,第 4 页,计

4、算机免疫学的定义计算机免疫学（Computer Immunology）一词最早由Forrest等人提出，他认为计算机免疫学是一门基于生物免疫学、人工免疫、以及计算机科学等的交叉学科，主要利用最新计算机科学技术，研究有关人工免疫的理论、规则、算法、模型等，并将这些理论应用于具体的应用系统中，解决实际的应用课题。目前国内还没有统一说法。现在，计算机免疫学的同义词有很多。例如，计算机免疫系统、免疫计算、免疫计算机、人工免疫、基于免疫的系统等。总之，计算机免疫学是一门多学科领域的、边缘交叉学科。,第 5 页,生物免疫学机理,免疫学中一些基本概念 免疫（Immunity）指机体识别和排除抗原异物，维持机

5、体生理平衡和稳定的功能。 免疫学（Immunology)研究机体免疫系统的组成（免疫器官、免疫细胞和免疫分子），识别（自己、异己）并消除（异己）有害生物（体外入侵，体内产生）及其成分的应答过程及机制的科学。,第 6 页,抗原（Antigen）抗原（antigen，Ag）是一类能刺激机体免疫系统使之产生特异性免疫应答、并能与相应免疫应答产物（抗体和致敏淋巴细胞）在体内外发生特异性结合的物质。 抗体（Antibody, Ab）能与抗原进行特异性结合的免疫细胞称为抗体。 自我和非我(Self and Non-self)自我对应于机体自身的组织，非我对应于外来有害病原或者体内病变组织。,第 7 页,人

6、体天然防线 第一道防线主要是皮肤和黏膜。它是机体防御体系中很重要的部分。失去这一屏障，如大面积烧伤，人将由于失液缺失、严重感染使机体面临极大威胁。 第二道防线指吞噬细胞和巨噬细胞。 特异性免疫一旦病原体突破了前两道防线进入人体，并繁殖，机体就经历了一次与病原体斗争的过程，这种对某一种病原体的识别和杀灭作用称特异性免疫。能进行免疫应答的免疫细胞有很多种，最重要的是淋巴细胞，一种是在骨髓（bone marrow）内发育成熟的细胞，叫B细胞；另一种是在胸腺内发育成熟，称为T淋巴细胞.,第 8 页,人体免疫系统三大功能功能 正常表现免疫防御 抗感染(immunologic defense)免疫稳定 消

7、除炎症或衰老细胞(immunologic homeostasis)免疫监视 控制癌变细胞(immunologic surveillance),第 9 页,人体的免疫机制人体的免疫机制中有三个阶段：自体耐受、免疫应答、免疫反馈。 自体耐受（self tolerance ）是对自体抗原不应答的一种免疫耐受，如图是免疫系统区分自体/非自体抗原时的反应状态。非自体抗原自体抗原克隆扩增克隆忽视 否定选择克隆删除 克隆无能未受影响细胞克隆效应,第 10 页,免疫应答抗原进入机体后，免疫细胞对抗原分子的识别和效应过程，称为免疫应答（immume response ）。可分为三个阶段。抗原提呈抗原提呈是指能免

8、疫细胞能捕获、加工、处理抗原,并将抗原提呈给抗原特异性淋巴细胞。人体内的B细胞可以利用其表面的免疫球蛋白分子（抗体）直接与抗原结合，诱导产生免疫应答。免疫系统特异识别抗原被提呈后，将发生免疫系统特异识别。免疫细胞表面的受体和抗原表面的抗原决定基产生化学结合。受体和抗原决定基都是复杂的含有电荷的三维结构，二者的结构和电荷越互补，就越有可能结合，结合的强度称为亲和力（affinity）下图为B细胞的模式识别。,第 11 页,BCR或抗体 B细胞受体抗原决定基B细胞的模式识别,第 12 页,体细胞高频变异和免疫记忆人体是部最精密、最复杂的机器，人体内的免疫细胞是怎样繁殖的呢？其核心是克隆选择原理克隆

9、选择原理主要思想：1.免疫系统要产生数十亿种类的有抗体受体的B细胞；2. 抗原提呈导致能与抗原结合的抗体克隆扩增和分化；B细胞活化后，可在淋巴结内，也可在骨髓内以极高的频率分裂，同时产生克隆选择，其中一部分分化为浆细胞，它不能继续增殖，其寿命仅为数日，但是浆细胞产生抗体的能力特别强，高峰期一个浆细胞每分钟可分泌数千个抗体分子，另一部分变成记忆细胞，形成免疫记忆，能存活数年，再被激活时，可重复以前的变化，一部分化为效应细胞，一部分仍为记忆细胞。,第 13 页,克隆删除（否定选择）克隆扩增选择 记忆细胞分化浆细胞克隆删除（否定选择）克隆选择原理,第 14 页,形态空间的提出为了定量的描述免疫系统，

10、Perelson和 Oster 提出所有的免疫事件都在形态空间（shape-space）S中发生，这是一个多维空间，每个轴表示一个物理化学的测量方法，用该方法可以描述一个分子形态。分子结构表示成一个点 sS,因而在L维空间（形态空间）中，可将一个点定为决定抗体-抗原相互作用的特征集。数学上，这种形态被描述成L维字符串或向量。,计算机免疫学基本原理,第 15 页,形态空间模型 形态空间形态空间的基本模型如图所示，形态空间含有抗体结合簇( 表示) 和抗原决定基( 表示)，其中是免疫交叉反应阐值，并且假设一个抗体能够识别周围体积 V范围内的抗原决定基。抗体识别抗原过程就是与抗原匹配的过程，抗原和抗体

11、分子之间的亲和力大于或者等于交叉反应阐值时，分子间的识别事件就会发生，即分子之间存在不完全匹配性。,第 16 页,自体/非自体不同的领域内自体/非自体有着不同形式的定义对于问题域X 0,1(L空间) ，包括两个子集，自体集合S和非自体集合N，自体集合和非自体集合之间的关系有:SN=X, SN=。对于计算机病毒检测而言，非自体代表病毒代码，自体为计算机系统内正常的应用程序;对于入侵检测系统，非自体代表来自网络攻击的IP数据包，而自体为正常的网络数据事务。抗体/抗原目前抗体/抗原的编码方式主要有二进制编码、实数编码、字符编码和灰度编码等。将抗体 /抗原模拟成长度为L的二进制字符串，例如病毒和抗体间

12、匹配时考虑了互补位， 抗体可表示成字符串00010101 (L=8)，抗原(病毒)表示成11101010，则触发应答的可能性很高。只要抗体/抗原的字符串互补匹配，抗体就能够识别抗原。,第 17 页,亲和力计算抗原和抗体之间的亲和力计算基于抗原和抗体之间结构的相似性。常见计算方法包括抗体抗原之间的距离、匹配度等。下面我们介绍一种计算亲和力的方法-匹配度方法两个等长字符串之间每一个位置上的字符都相同，这种匹配叫完整匹配。1994年Forrest提出了r-连续位匹配规则，即对于两个字符串x和y，如果至少存在连续r位相同， 那么它们就是r-连续位匹配的。若r=4，那么对于至少连续4位相同的两个字符串，

13、它们是匹配的，否则就不匹配。0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1匹配 不匹配,第 18 页,免疫细胞模型 基本原理免疫细胞主要在骨髓和胸腺中形成，从产生到成熟并进入免疫循环，需要经历一系列复杂的变化。基于生物免疫系统构建的人工免疫细胞模型，主要包括自体耐受、克隆、变异、记忆和死亡的过程。免疫细胞的生命周期如图所示。骨髓模型骨髓模型主要模拟免疫细胞的生成过程。免疫细胞是由基因库中随机选出的不同基因成分串联而成的，这里的免疫细胞被抽象为一个简单的字符串，如图是一个利用基因库产生

14、新的免疫细胞的过程。否定选择1994年，Forrest, Perelson 等人提出的否定选择算法成功的模拟了免疫细胞的耐受过程，目前细胞的自体耐受主要由否定选择算法来实现，如图。,第 19 页,克隆选择克隆选择原理是免疫系统用来说明对抗原刺激所产生的免疫应答基本特征的算法。只有识别抗原的细胞才能进行繁殖（分裂）。 克隆选择用来解释当B细胞识别自体抗原模式时，免疫应答是怎样形成的，以及描述该免疫应答的基本特征。 免疫记忆免疫系统必须可识别出许多以前没有遇见过的细胞和抗原分子，并决定如何应答。而且其中有些抗原不能被攻击，例如自体抗原，免疫系统能够记住遭遇过的抗原、再次遇到知道如何在发病前消除它，

15、免疫应答和免疫记忆至今科学界解释的还不是很清楚。,第 20 页,计算机免疫系统设计 基本思想建立计算机免疫系统的基本问题是确立生物免疫系统和计算机免疫系统之间的基本元素的对应关系，主要模拟生物免疫系统中有关抗原处理的核心思想。包括抗体的产生、自体耐受、克隆的扩增、免疫记忆等。生物免疫系统与计算机免疫系统的映射关系如表,第 21 页,免疫系统和计算机免疫系统的映射关系免疫系统 计算机免疫系统（CIS）计算机病毒 抗原 网络入侵其他待检测的目标 抗体和抗原的绑定 模式匹配 自体耐受 否定选择算法 记忆细胞 记忆检测器 细胞克隆 复制检测器 抗原检测/应答 对非自体位串的识别/应答,第 22 页,免

16、疫算法的基本构架用免疫算法解决具体问题时，首先需要将问题的有关描述与免疫系统的有关概念及免疫原理对应起来，定义免疫系统中元素的数学表达方法，然后根据实际问题的应用再设计相应的免疫算法。如图所示，免疫算法由以下几个步骤组成: 开始 定义抗原:将需要解决的问题抽象成符合免疫系统处理的抗原形式，抗原识别则对应为问题的求解。 抗原识别产生初始抗体群体:将抗体的群体定义为问题的解，抗体与抗原之间的亲和力对应为问题的评估:类似遗传算 初始抗体群体产生法，首先产生初始抗体群体，对应问题的一个随机解。计算亲和力:计算抗原和抗体之间的亲和力。 亲和力计算克隆选择:与抗原有较大亲和力的抗体优先得到复制，同时抑制浓

17、度过高的抗体，淘汰亲和力低的抗体，为 克隆选择获得多样性，抗体在克隆过程中发生变异，克隆选择中抗体促进和克隆删除对应优化解的促进与非优化解 群体更新的删除等。评估新的抗体群体:若不能满足终止条件，则转向 否 第步，重新开始;如果满足 终止条件，则当前的 满足终止条件抗体群体为问题的最佳的求解。 是结束,第 23 页,计算机免疫学的应用专题,网络安全 病毒检测人工免疫理论的在病毒检测中的基本原则是，把计算机系统（网络系统）看做“自体”，把病毒（或入侵）看做“非自体”或者“抗原”，与已知病毒相应的可以生成“抗体”，该抗体能够识别“抗原”，“抗体”按照一定的算法进行变异和进化，可以实现免疫应答（即一

18、次应答识别新“抗原”，二次应答识别“旧抗原”），并保持自适应性和自稳定性的特征。所以说，基于人工免疫理论的反病毒方法能够自适应识别新病毒。 国外应用美国公司IBM是较早地把人工免疫理论应用到防治病毒的研究单位，他 们提出的反病毒综合方案KEPH97A，KEPH97B取得了巨大的成功。 国内应用四川大学建立了人工免疫病毒检测模型AISVDM，对算法进行了实现，并且做了仿真实验，取得了较好的效果。,第 24 页,入侵检测入侵检测（Intrusion Detection），顾名思义，便是对入侵行为的发觉。它通过对计算机网络或计算机系统中的若干关键点收集信息并对其进行分析，从中发现网络或系统中是否有违

19、反安全策略的行为和被攻击的迹象。从总体上来说，现有入侵检测方法在下列特性上存在明显的不足: 可扩展性像基于神经网络等方法的检测系统，要么依赖于特定类型操作系统，要么依赖与特定的网络结构。 检测效率异常检测的计算代价非常大，因为系统维护的活动记录要随着每个事件更新。基于计算机免疫学的IDS在系统可扩展性与可移植性方面具有先天的优势，检测效率较高，可维护性好。因此，基于免疫学的IDS具有广阔的发展前景。,第 25 页,入侵检测（续）国外研究概况：主要有三个小组致力于基于免疫原理的入侵检测系统的研究:美国University of New Mexico的Forrest小组;美国University

20、of Memphis的Dasgupta小组;英国University College London的 Kim&Bentley小组。国内研究概况：主要工作有中国科学院的信息安全国家重点实验室、武汉大学软件工程国家重点实验室等。中国科学院信息安全国家重点实验室主要工作是将基因规划引入了基于系统调用序列的免疫模型中，通过基因规划来建立正常行为模式，并且取得了较好的效率。,第 26 页,计算机取证传统的取证手段是一种静态方法，在事件发生后对数据进行提取、分析、抽取有效证据，这种方法费时且对取证人员有很高的要求，且不能应付高明的黑客攻击，这些黑客在完成攻击后会全面彻底销毁证据或者窜改证据，事后即便使用最

21、好的数据分析工具也无能为力，从面造成的恶果是：知道入侵者有罪，却缺乏证据起诉，无法定罪。利用免疫系统的自适应性、分布性、实时性和可靠性，可以设计较好的动态计算机取证方案。,第 27 页,风险检测传统的网络安全技术（如防火墙）主要基于被动防御，对系统正在遭受的攻击缺乏实时的网络安全风险检测，更不能有针对性主动调整自己的防御策略。实时的网络安全风险检测对积极的网络安全技术的研究具有重要意义，是目前的研究热点之一。,第 28 页,垃圾邮件处理如何有效识别和及时拦截垃圾邮件成为当今网络安全技术领域的研究热点。传统的反垃圾邮件(Anti-spam)技术大多采用基于统计学习原理的Bayes方法。Bayes

22、 模型充分发掘了已知样本所包含的统计信息，因此其可信度得到了保证。但是对于未知样本，特别是已有样本的变异样本的分类问题，基于Bayes 模型的分类系统的执行效果往往不尽人意，因此，如同对计算机病毒所采取的防范措施一样，对于垃圾邮件这种隐蔽性强、变异能力突出的网络非法信息，必须采用具有自适应和自学习能力的分类系统。而生物免疫原理则恰好为此提供了丰富的启示。,第 29 页,数据挖掘与分析数据挖掘从狭义上讲就是信息处理问题,很多都属于模式识别所研究的范畴。模式的分类和识别可以由分类器来实现。为了设计分类器必须首先对分类器进行训练, 而人工免疫系统在训练学习等方面具有其它系统无可比拟的优点,于是人们便

23、开展了人工免疫系统应用于数据挖掘的研究。人工免疫系统作为一种新兴智能系统,在数据挖掘中的应用刚刚起步,可以作为一种新的数据挖掘方法,来对数据库、数据仓库、文本、Web 页等进行数据挖掘,发现有用的知识。目前，AIS在机器学习与数据挖掘等领域潜在的应用前景，AIS的研究得到了许多大学、研究机构和工业界的重视。英国Kent大学的 Timmis 对基于AIS的机器学习和数据挖掘技术进行了系统性的理论研究，并开展了基于AIS的大规模数据挖掘应用研究。作为计算智能的一个崭新分支，AIS已成为许多国际期刊的重要议题。,第 30 页,机器学习学习一般被认为是一个从经验中获取知识并把知识抽象化来解决新问题的过

24、程。为了能够学习，系统必须通过与外界环境的交互来调整自己，并且必须能够维持（记忆）这种调整一段时间。机器学习是研究如何创造能够从经验中学习、通过学习改变自己行为和记住已学东西的系统。2001年，Watkins提出了有限资源人工免疫分类器模型，称作（ Artifical Immune Recognition System）,AIRS属于有监督学习算法。,第 31 页,计算机免疫学的应用专题,其他应用领域组合优化典型的组合优化问题如背包问题，它的限制是背包的容积，寻求优化的是物品的全部价值和，可用免疫计算来解。美国的两位学者 Keiichi ogawa和 Takamasa Akiyamn于1999

25、年利用免疫算法解决了30个城市的TSP(旅行商问题)问题。我们知道旅行商问题属于NP类问题，目前还没有算法能有效的解决。,第 32 页,知道了什么是计算机免疫学； 了解了一些网络安全方面的一些领域； 看了一些相关的论文； 最后，最近天气炎热,希望大家注意身体,谢谢大家！,结束与展望,第 33 页,产生免疫细胞 基因库N变异 耐受成功 死亡Y克隆 成熟细胞N亲和力成熟 死亡Y激活记忆细胞 返回,免疫细胞的生成基因库1 基因库2 基因库3 基因库4 A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 D1 D2 D3 D4A3 B2 C1 D4A3 B2 C1 D4 =4个16比特段A3 B2 C1 D4 =64比特串,自体耐受自体集合S未成熟的免疫细胞集合R 匹配 成熟的免疫细胞集合RNY删除与自体匹配的细胞,冠状病毒模型,