（计算机应用技术专业论文）新型否定选择算法的研究与应用.pdf

江苏大学硕士研究生毕业论文 摘要 人工免疫算法模拟生物免疫系统抵抗病毒和细菌等病原体的机制，具有耐 受性、分布性、鲁棒性、适应性、多样性、免疫反馈和自组织等一系列特性， 否定选择算法是实现人工免疫系统的主要算法，通过模拟t 细胞的成熟机制生 成成熟检测器，用于区分自体和非自体。现有否定选择算法存检测器冗余较大、 易产生漏洞和缺乏自适应机制等问题，造成人工免疫系统对非自体的检测率和 检测效率较低。 本文详细分析了影响否定选择算法检测效率和对非自体检测率的因素，提 出基于切割的否定选择算法。使用切割空间的方法生成检测器，依据各区域的 非自体分布特点设置阈值，消除冗余的检测器，减少了检测漏洞，提高了检测 效率和准确性；引入分层思想，设计了层次型的检测器管理机制，提高了检测 器查找、更新效率，增强了自适应性。最后针对安全磁盘需保持较高i o 性能 的特点，使用新型否定选择算法实现轻量级的访问控制系统，构成安全磁盘原 型系统，测试表明新型否定算法具有更高的检测效率和准确性。本文的主要工 作如下： 1 1 从元素描述形式、匹配规则、检测器生成和管理方式等几个方面，详细分 析了影响否定选择算法效率和对非自体检测准确性的因素。 劲提出了基于切割的否定选择算法，根据自体在空间的分布，切割空间生成 检测器，有效的减少了检测漏洞，消除了冗余的检测器，使系统只需使用 少量的检测器即可检测出较多的非自体抗原。 3 ) 设计了动态区域阈值更新算法，根据检测器所处区域的特点，优化和调节 否定选择算法的检测效率和检查非自体的准确性。 4 ) 设计层次型的检测器组织策略、基于优先级的检测器管理机制和快速检测 器更新机制，提高了否定选择算法的检测效率，减少自体变化带来的大量 开销或漏洞，增强了否定选择算法的自适应性。 5 ) 在智能磁盘系统中，使用新型否定选择算法实现访问控制功能，构建基于 免疫的安全磁盘原型系统，通过i ，o 性能的测试与比较，表明了新型否定选 择算法在保证安全性的同时，具有明显的效率优势，能有效的提高现有算 江苏大学硕士研究生毕业论文 法的检测效率和检查非自体的准确性。 关键词：人工免疫算法、否定选择算法、匹配规则、成熟检测器、切割、安全 磁盘 江苏大学硕士研究生毕业论文 a 砌c i a l 抽如嚏u n ea l g o r i t l l m 如曲窿l t l 踏b i o l o 舀c a li m i n 岫es y s t e m si l lp r o t c c 血培 a n i m a l s 缸脚v i m ，b a 咖r i a ，p 嬲毽i t ea n dd 姐g e r o u sf o r e i 弘p a m o g e n ，砌c hh 弱a 1 0 to fa d v 雏t a g e si i l d u d i n g ，d i 鼬r i b u t e d ，r o b u s 缸l e s s ，t o l e 舢c e ，a d 印t a 【b n i t y d i v e r s i 嘎 i n m l u n ef e 吠i b a c i ka i l ds e m o 唱卸娩a t i o n ，e t c m f i c i a lh 加1 l cs y s t c mg e i l c r a l l y c 0 璐t n l c t sb 撇d0 nn e g a t i v es e l e c d o na l g o r i t l l m ，w t l ic ：hg e n e m t e st h em a t i l r c d e t c c t o rd i 娟n 鲥s hb 舭ns e l fa n dn o n - s e l fs 锄p l e sv i ai i n 眦吨m et 础 d i v e l o p m e mp r o c c s si n t h em y m 璐h o w e v e r ，t r a d i t i o n a ln e g a t i v es e l 硎o n a l g o 删【l mh 弱al o to fr c d 岫d a i l td e t c c t o 瑙a n dh o l e s 0 fd e t e c t i o n ，锄dl a c k s e l f a d 印t a t i o n ，w t l i c hm a y c a u s e p o o re f f i c i e n c ya n da c c i l r a c y0 fd e t e c t i o n 1 1 1 i sp a p c ra l l a l y s e s l cf a c t o r 砌u e n 曲喀a c c i l r a c yo fd c t e c t i o na n de f f i c i e n c y i 1 1d e t a i l s ，a n dp r e s e n t sac l l 缸培b 弱c dn e g a l i v es e l e c t i o na l g o r i m mi i lo r d e rt 0 砌u c ed e d _ i l n d a l l td e t e c c o 瑙锄dh o l e so fd c t e c t i o n ，t l et l l f e s h o l dv a l u eb yt l l e c h a r a c t e r so fd 堪e r c mr e 酉o n s ，锄di i n p r o v ee f f i c i e n c ya n da c 叫a c yo fd e t e c t o r ；i l l a d d i t i o n ，w ea l s od e s i j 驴m em u l t i l a y e r sm 趾a g e m e n tm e c h 雒i s m so fd e t e c t o rt 0 i i n p r o v e st h e m a d a p t a t i o nb yo p t i i n 娩i n gm ee f i c i c n c yo fs e a 础n g 锄du p d a l i n g d e t e c t o 瑙a tl 嬲tw er e a l 娩el i 曲t 、e i g h ta c c e s sc 0 m r o ls y s t e mu s i i l gb y 廿l en e w a l g o f i t l l m sa n de s t a _ b l i s ht l l e c u r i 哆d i s kp r o t o t y p es y s t e mt 0p r o v i d e s1 1 i g l li 徊 p e r f b 衄a n c e e y a l u a t i i l gi op e r f b r i n a n c e ，l cr e s u l tp r 0 v e st h i sn o v e la l g o r i t h mh 习略 h i 曲e re f f i c i e n c y 锄da c c i l r a l c yo fd e t e c t i o n ，1 1 l em a i n c o n t e n t so ft l l i sp a p e ra r e 嬲 f o u 0 w s ： 1 ) t 缸sp 印e r 肌a 1 ) ，z e st h ef a c t 0 瑙i i ld e t c 加rg e n e r a t i i 培，d e t e c t o rm 觚a g e m e n ta n d m a t ( h i n gm l e s ，w l l i c h 砌u e n c em ee f f i d e n c y 觚da c c u r a c yo fd e t e 嘶o na b o u t n e g a 曲es e l e 嘶o na l g o r i m m 2 ) w r ep r e s e n t st h ec u t t i n gb a s e dn e g a t i v e l e c t i o na l g o r i t l l i nw h i e hc u t j ss p a c e0 f d o m a i l lb ys p a t i a ll o c a o no fs e l ft og e n e r a t ed e t e c t o r ，t l l e n 卸r o v e se f f i d e n c y o fd e t e c t o rg e n e r a t i n g ，e l h i n a t e s 川眦d 觚td e t e c t o r ，r e d u c c sh o l eo fd e t c c t i o n ， 觚d 明s u r e s1 1 i g l le f f i c i e n c ya n da c c u f a c yo fd e t e 丽o n 3 )d e s i 印i l l gt h ed y n 锄i c h e s h o l dv a l u ca l g o r i t l 吼b yt h cc h a f a c t e r so fd i f 6 e r e n t t t t 江苏大学硕士研究生毕业论文 r e g i o 娜t 00 p t i m i z e st h ee f f i c i e n c y 柚da c c u r a c yo fd e t e 嘶o n 4 )d e s i 毋m g 龇m l l l t i l a y e r s d e t e 咖fs t o f a g cs t m 咖r e ，m ep f i o r i t y b 弱e d m 猢g 锄c n tm e c h a i l i 锄o fd e t e c t o r s 觚dm e 凤t d c t c 咖ru p d a 曲ga l g o r i t l l i n ， w h i c hi l n p r o v e 1 ee i j e i d e n c y 锄d 虻峪a d a p t a t i o n0 fn e g 栅es e l e 嘶o n a l g o r i t l l m 5 ) i l lm ei i i t e l l i g e n td i s ks y s t e mw er e a l 娩et h ef i 】i i c t i o no fa c c e 豁咖o l1 1 s i n g b y m e 珊啊a l g o r i t l m 媳a n de s t ：a b l i s ht h es c c i l r i 够d i s kp r o t o t y p es y s t e m b y c o m p a 血gm e 徊p e 哟咖觚c e m er e s l l l tp r o v e st l l i sn o v c la 1 9 0 r i t l l mh 弱h i g h e r e f f i c i e n c y 锄da c c i l r a c yo fd e t e c t i o na tt h es a m et i i n e t h a ti tc 觚e n s u r em e s e c i l r i 何0 fs y s t e m k e yw o r d s ：a n i 丘d a li i 姗城ea l g o 瑚m ，n e g a 曲es e l e 硝o na l g o d t t l m ，m a t c h i i 培“e ， m a t u r ed e t e c t o r c i 眦i i l 岛c i l r i t yd i s k 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密 。 学位论文作者签名：仲巍 2 0 0 8 年6 月5 日 指导教师签名：鞠时光 2 0 0 8 年6 月5 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究工作所取得的成果。除文中已经注明引用的 内容以外，本论文不包含任何其他个人或集体已经发表或撰写 过的作品成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结果 由本人承担。 学位论文作者签名：仲巍 日期：2 0 0 8 年6 月5 日 江苏大学硕士研究生毕业论文 1 1 引言 第一章绪论 自古以来，人们就对生物界有着浓厚的兴趣，并不断地从生物系统的结构功 能及其调节机制中获得灵感。从2 0 世纪中叶开始，研究热点也正是围绕着生物 系统尤其是人类自身功能及结构的模仿，例如，神经网络是对人脑结构的模拟， 模糊控制与类模糊思维有着相似之处，而进化算法则将生物的生存演化进行了模 仿。近年来，生物免疫系统( i 咖u n es y s t e m ) 又成为一个新兴的生物信息研究课 题。免疫系统是由器官、细胞和分子组成的一个复杂系统，它是除神经系统外， 机体能特异地识别“自己非己刺激，对之做出精确应答，并保留记忆的功能 系统。研究表明，免疫系统具有多种功能：如模式识别、学习、记忆获取、多样 性、容错及分布式检测等【1 1 。免疫系统的这些诱人特性，正逐渐引起工程研究人 员的关注，基于免疫学原理已提出了不少新的算法和技术，在众多的工程研究中 引入免疫概念后取得了满意的效果：自律机器人的研究、计算机网络安全、智能 控制、模式识别及新的免疫计算方法等。这些研究与应用不仅能帮助我们更好地 理解免疫系统本身，而且也从生物免疫系统信息处理的角度重新审视和解决实际 的工程问题。 1 2 生物免疫机制 在自然界中，免疫是指机体对感染具有抵抗能力从而不患疾病或传染病。免 疫系统是由免疫活性因子、免疫细胞、免疫组织和器官组成的复杂系统，具有识 别机制，能够从人体自体细胞或自体分子和外因感染的微组织中检测并消除病毒 等病原体本身以及因感染而引起的机能不良、功能紊乱、功能障碍等症状。免疫 系统和其他几个系统及器官的相互作用调节着身体状态，保障身体处于稳定、正 常的功能状态【2 】。 免疫系统的结构是多层次的，由分布在几个层次的防御系统组成。生物免疫 系统的保护层可以划分为四层( 如图1 1 ) ： 第一层是皮肤、阻止多数的病原体，用叉表示清除病毒体；第二层是物理的， 江苏大学硕士研究生毕业论文 即温度、酸性之类的条件；第三层是固有免疫( 血ei 皿a t ei i n m 吼e ) 系统，由游 荡的细胞组成( 噬菌体) ；最后一层是自适应免疫系统( t l l ea d a p t i v ei i 姗城e ) 系 统，由淋巴细胞组成，适应性病原体结构，对其进行有效清除。 图1 1 生物免疫防御体系层次图 固有免疫系统不随特异病原体的变化而变化，它与生俱来就有辨别一定微生 物和细菌并消灭它们的能力。而自适应性免疫系统则主要是通过b 细胞( 骨髓 中产生) 和t 细胞( 胸腺中产生) 对入侵抗原进行响应。 一旦病原体( 病毒、细菌或寄生虫等) 通过了免疫系统的前两层防御入侵机 体时，免疫系统开始响应的活动。免疫系统能够识别自体( s e l f ) 和非自体 ( n o n s c l f ) ，并消除非自体。自体指生物自身的细胞和分子，非自体指病原体。 有机体内的免疫系统能够识别自体和非自体，并是自身分化激活并最终消除外部 抗原( 病原体) 的过程叫做免疫应答( i m i n u n er e s p o n ) 。在免疫系统中t 细胞 和b 淋巴细胞起着十分重要的作用，这些具有免疫功能的t 淋巴细胞，必须是 经过审查( 否定选择) 的成熟淋巴细胞。t 细胞表面的受体或b 细胞表面的抗体 被称为免疫系统的检测器。如果检测器与病原体( 如细菌、病毒和寄生虫等) 结 合，则检测器检测到有外来入侵。检测器检测到入侵后，将调用吞噬细胞，如巨 噬细胞，对其进行清除。b 细胞、t 细胞从未成熟到成熟期间，将经历自体耐受， 在识别非自体抗原后产生自体应答，杀死非自体抗原并形成免疫记忆，进行免疫 反馈。免疫系统具有高度分布、并行和自适应性等显著特性。在免疫系统中，检 测器的产生、异物的识别和清除，以及对感染模式的记忆等过程都是并行进行的， 并且是高度分布的。这些特性使得免疫系统具有良好的健壮性，同时也导致了免 2 江苏大学硕士研究生毕业论文 疫系统的复杂性。 生物免疫系统的最大特点是免疫记忆、抗体的自我识别能力和免疫多样性。 免疫系统分析和学习进入人体内的外在物质，并且同时产生抗体来消灭入侵的抗 原，具有良好的多样性、耐受性，免疫记忆，分布式处理、自组织、自学习、自 适应性和鲁棒性等特点。将免疫概念引进工程应用领域具有重要的现实意义，人 工免疫学也因此日益受到关注。 1 3 人工免疫学的当前研究现状 人工免疫是生命科学和计算机科学互相交叉而产生的又一个研究热点，具有 非常广阔的应用前景。由于其自身的功能特征，以及它所蕴涵的丰富的信息处理 机制，吸引了大批研究人员、专家学者对其进行建模、算法设计及应用研究。 1 9 7 4 年j e m e 提出了免疫系统的第一个数学模型【3 l ，奠定了免疫计算的基础， 并于1 9 8 4 年获得诺贝尔奖。1 9 8 6 年f f 锄e rjd 等人首次用数学方式描述了免疫网 络【4 】。a d e l m 锄在1 9 8 7 年讨论了计算机安全问题与生物过程之间的联系，提出了 计算机病毒的概念【5 】。s p a 肋r d 进一步将计算机病毒描述成一种人工生命体【6 1 。 f 0 盯e s t 在1 9 9 7 年提出了计算机免疫学，比较了生物免疫与计算机安全之间的 关系，得出可根据生物免疫系统的组织特点改进计算机安全系统的结论，给出了 否定选择算法、贪心检测器生成算法、r 连续位匹配规则等一系列计算机免疫的 基本算法；f 0 盯e s t 也分析了计算机免疫系统的局限性，与传统计算机安全系统要 求的机密性、完整性、可用性、可跟踪性和正确性五个特性相比，计算机免疫系 统是通过提高系统的生存性实现安全，主要涉及了完整性和可用性两方面，无法 很好的保证系统的机密性和可跟踪性；同时由于当前匹配算法的局限性，必然导 致检测漏洞与误判的存在，不能完全保证每次检测的正确性，只能保证统计上的 正确性【7 8 9 l 。d a s g u p t a 于1 9 9 9 年建立了一套计算机免疫系统，实现了计算机系统 对外来入侵的防御【1 0 1 。 在国内，2 0 0 2 年肖人彬等人归纳了人工免疫系统的仿生机理，介绍了典型 算法和应用情况，分析了人工免疫系统的特性和存在问题，指出了发展方向。2 0 0 3 年李涛提出了基于免疫的大规模网络入侵动态取证，以及网络安全风险检测与控 制技术，较好的实现了网络入侵的检测与取证【l l 】。2 0 0 5 年莫宏伟等人讨论了否 定选择算法在信息恢复中的应用，利用免疫算法生成检测器对信息恢复系统中的 3 江苏大学硕士研究生毕业论文 文本特征向量进行分类，比传统分类器更精确【1 2 l 。 人工免疫学包括所有使用免疫概念的技术研究，也是对生物免疫系统从结 构、功能及演化等全方位的模拟研究。虽然人工免疫学是新兴的领域，但免疫概 念已经渗透到众多工程领域：人工智能、计算机及其网络安全、控制等【1 3 以9 1 。 a ) 人工智能 学习是人工智能研究的一个重要方面，如果一个系统的行为是由自身的当前 输入和过去的经验而不是设计者输入和经验来决定，并且具有从经验中获得知识 并利用知识来解决新的未曾遇见难题的能力，则认为该系统具有学习能力。免疫 化过程是一种免疫学习典型的例子，另外免疫系统的分布式特性，特别适用动态 环境中的信息处理过程，这为人工智能研究注入了新的生命力。 协计算机安全领域 随着计算机系统及其互联网的高速发展，计算机网络安全成为日益突出的问 题，而防御异常入侵、防范病毒等可以从生物免疫机制中获得不少启发。 当前有人将人工免疫网络的分布性、鲁棒性、动态性、多样性和自适应性应 用到计算机网络的安全领域，采用否定选择算法进行计算机网络入侵检测，提出 人工免疫网络模型，由三个独特的进化阶段组成，否定选择、克隆选择和基因库 进化。一旦表示“非己”的检测器与新的“自己 模式的相似度达到所设定的阈 值，系统将发出报警信号，并进行基于a g 明t 的计算机网络入侵检测，基于免疫 的a g e n t 随机地分布在路由器周围，监视网络的状态，这一方法的最大优点是可 移动性、自适应性和合作性。 西智能控制 实际的工业控制对象具有非线性、不确定性、参数分布性和时变性等复杂特 性，传统的控制方法无法获得更好的控制效果。而将免疫机制引入控制领域，对 解决复杂的动态自适应控制难题提供了崭新的思路。 美国s 锄t a f c 研究院研究论坛的一个重要论题就是“自然和人工免疫系统的 反馈和控制”。他们研究认为反馈机制改进了免疫系统的性能，提出了“散布反 馈”( d 湎l s ef b e d b a c k ) 和“散布信息网络”( d i f f l 珊i i 响册a t i o n a ln e 俩o r k ) 的概念， 不仅在免疫系统的运行机制中有重要作用，而且可用于其他分布自律系统中。 借鉴免疫系统具有的双时间尺度进化结构，提出了一种免疫化计算系统 4 江苏大学硕士研究生毕业论文 血咖l l n i z e dc 0 m p u 切缸o n a ls y s 钯m ，i c s ) ，使用免疫系统模拟计算技术来重构生物 免疫系统的鲁棒性和自适应性。该系统的主要特点是，系统的鲁棒性是在慢速学 习阶段实现的，保证在外来干扰大范围内获得满意的性能；免疫系统的自适应性 是在快速学习阶段实现的，保证系统的动态响应特性。该方法成功地应用在一个 不确定模型u h1 经度直升机悬停模型上。 1 4 人工免疫算法结构 免疫算法大多将t 细胞、b 细胞、抗体等功能合而为一，统一抽象出检测器 概念，主要模拟生物免疫系统中有关抗原处理的核心思想，包括抗体的产生、自 体耐受、克隆扩增、免疫记忆等【2 0 】。 在用免疫算法解决具体问题时，首先需要将问题的有关描述与免疫系统的有 关概念及免疫原理对应起来，定义免疫元素的数学表达，然后再设计相应的免疫 算法。一般地，免疫算法大致有几个步骤组成。如图1 2 ： 5 江苏大学硕士研究生毕业论文 抗原识别 ， 初始抗体群体产生 ， 亲和力计算 ， 克隆选择 孽 群体更新 一 念 是 图1 2 免疫算法的基本架构 ( 1 ) 定义抗原：将需要解决的问题抽象成符合免疫系统处理的抗原形式，抗 原识别则对应为问题的求解。 ( 2 ) 产生初始抗体群体：将抗体的群体定义为问题的解，抗体与抗原之间的 亲和力对应问题解的评估：亲和力越高，说明问题的解越好。 ( 3 ) 亲和力计算：计算抗体和抗原之间的亲和力。 ( 克隆选择：与抗原有较大亲和力的抗体优先得到繁殖，淘汰亲和力较低 的抗体。为了获得多样性，抗体在克隆时经历变异。 6 江苏大学硕士研究生毕业论文 ( 5 ) 评估新的抗体群落：如果不能满足终止条件，则重新计算亲和力；若条 件满足则当前的抗体群落为该问题的最佳解。 计算机免疫系统中的部分功能实体和生物免疫学中的对照关系，如表1 1 ： 表1 1 计算机免疫系统和生物免疫系统对照关系 生物免抗原抗体自体耐受抗原检测应答 疫系统 计算机计算机病使用二进制或否定选择算法对非自体信息 免疫系毒、网络实值向量描述的识别、应答。 统 入侵的检测器 计算机免疫算法主要包括了两个阶段：耐受和检测。耐受阶段主要负 责成熟检测器的产生。检测阶段，检测器检测受保护的系统以发现变化。 算法的目的是找出一个检测器集合，在其不与自体集合中元素匹配的前 提下，能尽可能多的匹配识别出待检测集合中的非法元素。 成熟检测器选择算法的目的就是负责根据自体集，从初始检测器集中 挑选合适的检测器，构建能识别非自体的成熟检测器集。挑选出的成熟检 测器用于检查输入信息的合法性，识别非法访问信息，因此所构建成熟检 测器集的好坏直接关系到人工免疫系统的检测效率和准确性。下面简单介 绍现有的几类成熟检测器选择算法。 1 1 否定选择算法 否定选择算法口1 2 2 2 7 1m g a t i v es e l e 嘶o n ) 的目的是找出一个检测器集合r ( 从 候选检测器中选出的检测集合) ，它在不与集合s ( 自体集合) 中元素匹配的前 提下，尽可能多的匹配集合n ( 非自体集合) 中的元素。传统否定选择算法步 骤如下： 定义自体集合s 从检测器空间ud 中随机选择生成一个候选检测器集合 把每个检测器与自体集合中的元素匹配比较。匹配成功则放弃该检测去： 不匹配则把它放入合格的检测器集合当中。 应用否定选择原理生成检测器算法，如图1 3 ： 7 江苏大学硕士研究生毕业论文 否 合格检测器 集合 图1 3 否定选择算法 肯定选择算法 肯定选择算法f l ，2 7 1 和否定选择算法非常类似，但是其作用恰恰相反，肯定选 择算法中与自体匹配的免疫细胞被保留下来，如图1 4 。 肯定选择算法步骤如下： 初始化：产生一个候选集合p 。假设所有的都用长度为l 的二进制串来 表示，则可能产生2 1 个不同的二进制串。 亲和力计算：通过集合s ，就算p 中所有元素与自体s 的亲和力。 可用集合的产生：如果p 中的某个元素与s 中的某个元素的亲和力大于 或等于一个设定的阈值6 ，则被系统选定放入集合a ：否则删除它。 否抛弃 图1 4 肯定选择算法 3 ) 克隆选择算法 克隆选择原理描述了免疫应答的基本特征【1 2 1 1 。算法中，只有能够识别抗原 8 江苏大学硕士研究生毕业论文 的细胞才能分裂扩增。本文的模型中借鉴了这种思想，通过低频变异器部分实现 了克隆选择。 标准克隆选择算法：克隆选择原理是免疫系统用来说明对抗原刺激所产生的 免疫应答基本特征的算法，只有识别抗原的细胞才能进行克隆扩增。克隆选择算 法分为6 个步骤，每执行完6 步，生成新一代的免疫细胞。 生成一个候选方案集合( p ) 。 选择具有较高亲和力的n 个个体。 克隆这n 个最好的个体，组成一个临时的克隆群体( c ) 。与抗原亲和力 越高，个体在克隆时的规模也就越大。 把克隆群体提交给变异，根据亲和力的大小决定变异，产生一个成熟的 抗体群体( c 宰) 对c 奎进行再选择，组成记忆细胞集合m 。p 中的一些成员可以被c 中 的其他一些改进的成员替换掉。 生成d 个新的抗体取代p 中d 个低亲和力的抗体，保持多样性 1 5 研究背景 人工免疫系统是在仿生生物免疫系统工作机制的基础上快速发展起来的，由 于借鉴了人体免疫系统的自治性、多样性、自适应性、耐受性和分布性等特点， 使得系统能很好的适应动态变化的环境，自动优化始终能保持很小的开销。但现 有的人工免疫算法，如否定选择算法中还存在一系列的问题，如检测器生成的开 销较大、检查器识别非自体的能力较低、以及存在检测漏洞和误检等。因此研究 一种高效的新型否定选择算法可以有效的改善人工免疫系统的性能。 当前国外对存储安全系统的研究处于快速发展的阶段，主要的安全技术包括 加密、认证、访问控制、审计和可信通信模型等，分别从增强文件系统的安全性、 新型磁盘结构、数据的可恢复性、高效的密钥管理机制、安全中间件、分区与掩 码等六个方面展开研究【2 3 】。 智能磁盘是新型磁盘结构中的一种，它在磁盘系统中集成处理器，完成数据 的加解密、数据迁移、存储虚拟化和存储q o s 等处理任务，能极大的提高了存 储系统的性能，但其安全问题一直未得到很好的解决。智能磁盘以及所服务的存 储系统本身是系统保存数据的中心，因此安全问题非常的重要。现有的安全系统 9 江苏大学硕士研究生毕业论文 都建立在所保存的基本数据安全的基础之上，没有底层存储系统的安全性，任何 安全系统都将是空中楼阁。以智能磁盘为代表的存储系统面对的是高速、海量数 据的访问请求，使得现有的加密认证、访问控制和完整性检查等安全技术无法满 足存储系统的安全需求，容易造成安全开销过大，严重降低了系统性能。因此研 究高效的安全系统是保护智能磁盘安全的重要手段【2 4 乃】。 在此背景下，我们考虑通过改善传统否定选择算法，并将其应用于智能磁盘 的安全系统中，构建高效的智能磁盘安全系统，保护存储系统中的数据安全。 1 6 本文的研究工作 本文首先综合介绍生物免疫学和人工免疫学的基本概念和发展概况，详细阐 述了人工免疫算法的研究现状，指出改善否定选择算法的迫切性。在此背景下提 出一种基于切割的新型否定选择算法，并对其进行性能分析和评价，然后针对其 特点设计了一套检测器管理策略，最后在智能磁盘系统上搭建免疫系统模块，构 建基于免疫的安全磁盘原型系统。本文的主要工作包括： 1 1 设计了基于切割的否定选择算法 首先定义了人工免疫系统的相关元素，并制定出与其相适应的匹配规则， 利用自体元素的空间特性和多级检测器思想，设计基于切割的检测器生成算 法。同时为了进一步增强否定选择算法的自适应性，设计了一种动态区域阈 值更新算法，使得基于切割的否定选择算法可根据系统运行环境的改变，自 适应性的调节系统检测器状态。最后建立算法的原型系统，并与各类相关算 法进行分析比较，从检测效率和检测率等不同角度证明了该算法的优越性。 劲分层存储的检测器管理策略 由于人工免疫系统中缺乏对检测器的管理手段，容易导致安全系统性能 开销过大等问题，因此在基于切割的检测器生成的基础上设计出一类层次型 检测器存储结构，并针对这种结构制定各类检测器管理策略，在增加否定选 择算法的自适应性的基础上有效的提高了系统的检测效率。 3 ) 基于免疫的安全磁盘原型系统的实现 首先总结分析了当前网络存储安全系统的实现机制及其优缺点，并指出 了网络存储安全系统实现的主要关键技术。然后在网络存储系统使用基于切 割的否定选择算法实现访问控制机制，建立一种基于免疫的安全磁盘原型系 1 0 江苏大学硕士研究生毕业论文 统。最后搭建一个基于开放源码的i 鹏仃e 对象存储文件系统的实验平台，在 对i 棚仃e 的源代码进行详细分析的基础上，设计并简化实现基于免疫的安全 磁盘的原型系统。 1 7 本文的章节安排 本文的结构如下： 第一章首先概述人工免疫系统发展的现况以及未来发展的趋势，介绍人工 免疫算法研究的重要意义，最后提出本文研究的内容。 第二章首先指出了否定选择算法的特点，介绍了否定选择算法的研究现状， 并总结了实现否定选择算法所涉及的关键技术，最后展望了新型否定选择算法的 研究方向。 第三章针对传统否定选择算法的缺陷，提出多种新型算法，对否定选择算 法中的各个模块进行修改；通过与相关工作的比较，说明了该算法具有较强的安 全性和高效性。 第四章设计检测器管理策略，有效的改善了否定选择算法的自适应性，提 高了系统的性能。 第五章介绍h s 仃e 对象存储文件系统概况，在分析了网络存储安全和否定 选择算法的基础上，给出了原型系统的设计原理，最后在实验室环境中实现了基 于免疫的安全磁盘原型系统，并对其相关性能进行了测试和比较分析。 第六章对全文进行总结，并提出进一步需要开展的工作。 1 1 江苏大学硕士研究生毕业论文 第二章否定选择算法的研究现状和综合分析 免疫系统扮演的主要角色就是保护组织免受传染疾病( 如病毒、细菌等) ， 并且消除细胞残骸和发生功能异样的细胞。为了达到这些功能，作为一个免疫系 统，首先要解决的事情就是如何对自身( 自体) 和那些不属于自身的元素( 非自 体) 进行区分。在人工免疫系统中，通过否定选择算法去除那些对自体产生应答 的免疫细胞，从而实现对自体的耐受。否定选择算法是对免疫细胞的成熟过程的 模拟，经历耐受的检测器模拟成熟的免疫细胞，算法主要包括了两个阶段：耐受 和检测。耐受阶段主要负责成熟检测器的产生。在检测阶段，检测器检测受保护 的系统以发现变化。 2 1 否定选择算法中的元素描述形式 当前否定选择算法已经成为人工免疫算法中使用最为广泛的一类算法模型， 在此基础上可衍变出各类改进型的否定选择算法以适应不同的应用环境。抗原 抗体间的匹配过程为否定选择算法中的最主要的一个方面，可用来识别并有选择 性的消除外界入侵的有害元素。 一般情况下，否定选择算法中常使用字符串来描述抗原和抗体【2 让7 1 ，并构造 各类匹配规则来计算两个字符串间的亲和度以判定其是否匹配。使用二进制字符 串的描述方式一般足够代替其余的各种描述方式，毕竟任何数据元素在计算机存 储系统中都可以使用一串位序列来表示。更重要的是，目前一些使用二进制字符 串描述的匹配规则已被成功的开发和广泛应用，在此基础上可研究出更加简便的 二进制字符串描述方式和与其对应的匹配规则。 2 0 0 3 年g o n z a l e z 和d a s g u p t a 又提出使用实向量( r c a lv e c t o r ) 来描述抗原和抗 体【2 8 捌，这种方式更加适合于应用环境下的学习和数据分析，而且一些应用环境 很难直接使用二进制对其进行描述。虽然r e a l v a l u e d 的描述方式非常的困难，但 在处理高维事件时，此种描述方式使得否定选择算法显示出更好的检测效果。下 面将简单介绍各种描述方式下的常用匹配算法。 江苏大学硕士研究生毕业论文 2 2 常用匹配规则 2 2 1 基于二进制描述的匹配规则 卜c o n t i g u o u s 匹配规则 f o r r e s t 和她的小组在1 9 9 4 年提出了r c o n t i g u o u s 匹配规则【1 5 3 0 1 ，定义抗 原z = 勋勋石，阮以口) ，检测器d = 西如函似i 以口) ，抗原x 与检测器d 匹 配的定义如下： dm 口氏沈钌x 三j z z 一厂+ 1s 比如砌口f z ，= d ，扣厂j = ，f + 厂1 表示当二进制串x 和d 存在不少于，个相同连续对应位时，抗原x 与检测 器d 匹配；厂仃 ，对) 为静态匹配阈值。 f c o n t i g u o u s 匹配规则能较好的保证检测准确性，但制约了检测器识别 非自体的能力。每个长度为z 的检测器包含z r + j 个用于检测非自体的特征 子串，每个特征子串最多能识别2 厶7 种非自体，因此每个检测器最多能识 别“一，+ d 2 卜7 种非自体。 卜c h u n k 匹配规则 b a l t h r o p 为提高r c o n t i g u o u s 匹配规则的检测准确性，与2 0 0 2 年提出了 卜c h u n k 匹配规则【3 1 1 ，定义抗原z = 勋砣柳似以j ，) ，检测器d = 似西如引 f ，也以j ”，设r z 且f z r + 1 ，抗原x 与检测器d 匹配的定义如下： dm ( i t c h e sx 兰x ? = d | 加r j = i ，i + r 一1 表示当检测器d 与抗原x 的从第i 位开始存在不少于，个连续相同的对应 位时，两者匹配；，仃 ，对夕为静态匹配阈值。 r c h u n k 匹配规则实际是在卜c o n t i g u o u s 匹配规则的基础上增加了限制 条件，提高了检测的准确性。检测器中保存开始检查抗原的起始位f ，只检 查抗原x 的后j f 位，限定了抗原x 中的有效区域，提高了检测的准确性。这 时每个检测器包含z ，f + j 个特征子串，最多能识别( 厶卜f + 1 1 2 卜。种非自体， 与r c o n t i g u o u s 匹配规则相比降低了单个检测器能识别的非自体数。 h a m m i n g 距离匹配规则 f a r m e r 与1 9 8 6 年提出了h a m m i n g 距离匹配规则【3 2 1 ，定义抗原 z = z j 砣x f 伍f 以口，检测器d = 西如西似以口，j ，抗原z 与检测器d 匹配 的定义如下： 江苏大学硕士研究生毕业论文 d ，竹口改唬嚣 x 三x ，od ，r 表示当抗原x 和检测器d 中相同对应位的个数大于等于r 时，两者匹配。 ，仃 ，固) 同样为静态匹配阈值。 h a m m i n g 距离匹配规则中，每个检测器最多能识别( z r + 1 ) 2 卜7 种非 自体；但仅仅统计对应位相同的个数，不考虑相同位之间的关系，存在较 大的检测误差。 r & t 匹配规则 r o g e r s 和t a n i m o t o 在2 0 0 2 年改进了h a m m i n g 距离匹配规则，提出了 r t 匹配规则3 1 1 ，定义抗原工= z j 耽劫似以彤，检测器d = 西比d z 似 以口) ，抗原z 与检测器d 匹配的定义如下： 鼍。盔 dm 口砌卵石兰 x ，od ，+ 2 to d ， f ，r 国 ，l 夕为静态匹配阈值。 r t 匹配规则与h a m m i n g 距离匹配规则相比提高了检测的准确性，但 检测效率仍然较低。 2 2 1 基于向量描述的匹配规则 欧几里德匹配规则 r e a l - v a l u e d 的描述方式主要使用了欧几里德匹配规则，抗原和检测器均使用 实向量来表示【2 8 ，2 9 1 ，根据传统的欧氏距离公式来计算两者间的空间距离，定义 抗原g2 “，而，为，毛，厂) ，检测器d = ( d t ，矗z ，4 ，吒，r ) ，抗原x 与检测器 d 匹配的定义如下： d 聊舭胁胙1 ( t t ) 2 ( ，+ 尺) y l 欧几里德匹配规则有效的判断高维空间中超球体之间是否发生匹配， 但计算过程较为复杂，且难以判断其他类型的高维元素之间的匹配关系。 2 3 检测器生成算法 否定选择算法在试验中被证明是一个很耗时的算法，其原因是检测器的生成 需要一定的时间，这与候选检测器集合的大小、自体集合的大小以及所选择的匹 配算法有很大关系。在选择某类匹配算法的基础上如何改进检测器的生成算法将 1 4 江苏大学硕士研究生毕业论文 在很大程度上影响否定选择算法的性能。 2 3 1 基于二进制描述的检测器生成算法 f 0 玎e s t 等人最早提出的否定选择算法所使用的穷举检测器生成算法中已经 证实，候选检测器集合的大小与需要保护的自体集合是指数关系，为了克服这个 问题，f 0 玎e s t 等人提出了线性检测器生成算法【3 0 1 和贪心检测器生成算法【3 3 1 。 在穷举生成算法中，大多数候选检测器都被抛弃，所以效率并不高，但是它 适合于任意一种匹配规则。对于某些匹配规则，可以采用更加有效的生成算法。 线形检测器生成算法正是针对r c o n t i g u o u s 匹配规则，它能在参数( 字符串 长度l 和连续位长度r ) 一定的前提下，使运行时间与系统输入成线性关系。 线性检测器生成算法分为两个阶段。 第一阶段：进行一个有限的递归运算以得到一定数量的不与自体匹配 的字符串。 第二阶段：用枚举法从候选检测器中随机选出检测器。 线性检测器生成算法运行时间与自体和检测器集合的大小成线性关 系，但是其运行时间和r 及l 的关系仍然是指数关系。 贪心检测器生成算法通过消除冗余的检测器改进了线性检测器生成 算法的效率，同时它保证生成的检测器能够尽可能多的覆盖非自体空间。 算法分为两个阶段，第一个阶段是取自于线性算法中的处理阶段，第二个 阶段是检测器生成阶段。该算法可消除部分冗余，但不能使检测器生成时间 最小化。 2 3 2 基于m a l _ v a l u e d 描述的检测器生成算法 g o n z a l e z 和d 哟g u p t a 提出f e a l v a l u e d 否定选择算法【2 8 ，2 9 ，3 4 1 ，使用n 维空间 向量描述自体和检测器，并根据个体所在的空间位置计算其欧氏距离进行匹配判 断。此方法可视化地描述了抗原抗体间的匹配过程，更加方便对检测器进行管 理。该算法的检测器生成流程如下： p r o d u c e rf e a l - v a l u e dn e g a t i v es e l e c t i o n p o ，s e l d b i 鸣i i l 清空成熟检测器集合； w h i l e ( 1 ) 江苏大学硕士研究生毕业论文 b e g i i l 随机生成一个使用空间向量描述的超球体型候选检测器： 使用欧氏匹配规则计算该检测器和自体集合中元素的空间距离d ； 岬 d ) b e g i i l 使用欧氏匹配规则计算该检测器和自体集合中元素的空间距离d ； 岬- d 自体半径r ) d 等于d r ； 减小d r 的大小； e l 配 1 6 江苏大学硕士研究生毕业论文 d 等于d f ； 增大d r 的大小； e n d 将该检测器存入成熟检测器集合d 中； i f ( 成熟检测器数量达到最大值) b r e a l 【； e 】【1 d e n d 此算法中候补检测器的空间生成位置存在不确定性，相同检测器可检测出部 分相同的异常数据，动态调节检测器的大小同样会使得某些检测器成为冗余检测 器。因为需采用一种自适应的成熟检测器生成算法，在动态调整检测器检测范围 的同时防止冗余的产生。 2 4 综合分析 根据上述中对否定选择算法的详细分析可以看出，传统否定选择算法明显存 在以下几个缺陷： 1 当问题空间过大时算法时空复杂度成指数级递增，可行性不高【3 引。论阈空间 的增加导致成熟检测器需求量的增加，传统的匹配方式和检测器生成算法严 重影响到否定选择算法的生成效率和检测效率，使得算法可行性大幅度降低。 2 检测效率较低，容易产生漏洞【8 ，9 ，3 6 1 。即使使用上述各类算法产生一个完全的 成熟检测器集合，也不意味着建立一个能匹配所有非自体串的检