（计算机软件与理论专业论文）基于免疫机制的快速异常检测算法.pdf

中国科学技术大学硕士学位论文 摘要 随着计算机网络的飞速发展，网络安全问题已经越来越严重，引起人们的高 度重视。近年来新兴的人工免疫系统己迅速成为智能计算领域的个研究热点。 由于生物免疫系统具有很强的自我保护功能，因此，基于生物免疫机制的人工免 疫网络安全新机制研究备受瞩目。 免疫网络和非选择机制是生物免疫中非常重要的两个方面。免疫网络具有免 疫调节、记忆等功能，相关的j e r n e 免疫网络学说在理论免疫学中具有很大影响； 非我选择是生物免疫系统抵御外界病毒的基本机帛8 之一。本论文旨在深入探索免 疫网络机制与非我选择机制，在现有人工免疫网络模型以及非选择算法的基础 上，设计出更高效快速的实用性算法，并应用于实际的异常检测。 具体丽言，本文的研究内容主要包括以下两个方萄： ( 1 ) 提出了一种融合免疫网络与非我选择机制的异常检测算法。该算法首先 借鉴免疫网络理论对非我选择后的成熟检测器进行聚类。异常检测时，从全部予 类中选择最佳的部分子类进行检测；同时，利用免疫网络的动态生成和记忆机制 来实现二次应答。文中将算法应用于基于系统调用序列的入侵检测。实验结果表 明，本算法不仅能保证检测效果，还能有效地提高检测速度，并比较好地解决检 测器集不完备的问题。 ( 2 ) 针对非选择算法匹配次数较多的问题，根据匹配规则的特殊性，提出了 基于k 均值聚类的改进非选择算法、基于自适应检测器集k 均值聚类的异常检 钡i 算法、基于多层次聚类的异常检测算法；这些算法都在很大程度上减少了匹配 次数，提高了检测速率。与此同时，提出了基于自我集聚类的检测器自我过滤算 法。应用于摸拟数据和入侵检测的实验结果都表明这些新提出的算法快速有效。 本论文通过分析j 选择算法在实际网络安全应用中的问题。结合免疫网络机 制以及传统的k - 均值聚类方法，从减少检测器与待检测数据之间的匹配次数的 角度提出了新的更加快速的异常检测算法。与此同时，提出了基于自我集聚类的 检测器自我过滤算法。本文的工作不仅使得面向网络安全的人工免疫算法更加实 用，而且对人工免疫系统本身的研究也具有促进作用。 摘要中国科学技术大学硕士学位论文 关键词：人工免疫；非选择：免疫网络：聚类；异常检测 h a b s t r a c t中国科学技术大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y , p r o b l e m sa b o u t n e t w o r ks e c u r i t yh a v eb e c o m em o r ea n dm o r es e v e r e ，a n db e e ne m p h a s i z e dw i d e l y a r t i f i c i a li m m u n es y s t e mh a sb e c o m eah o t s p o ti nt h ea r e ao fi n t e l l i g e n tc o m p u t i n g r e s e a r c hf i e l d b i o l o g i c a li m m u n es y s t e mh a sas t r o n gs e l f - p r o t e c t i o nf u n c t i o n s o r e s e a r c ho nn 州a r t i f i c i a li m m u n en e t w o r ks e c u r i t ym e c h a n i s m s i n s p i r e db y b i o l o g i c a li m m u n es y s t e mh a sb e e naf o c u so f r e s e a r c ho nc o m p u t e rn e t w o r ks e c u r i t y i m m u n en e t w o r ka n dn o n - s e l fs e l e c t i o na r et w ov e r yv a l u e dm e c h a n i s m si n b i o l o g i c a li m m u n es y s t e mi m m u n en e t w o r kh a si m m u n ea d j u s t m e n ta n dm e m o r y f u n c t i o n se t c , a n di m m u n en e t w o r kt h e o r yp r o p o s e db yj e r n eh a si m p o r t a n ti n f l u e n c e o ni m m u n o l o g y n o n s e l fs e l e c t i o ni so n eo fb a s i cv i r u sd e f e n s i v em e c h a n i s mo f b i o l o g i c a li m m u n es y s t e mt h ea i mo ft h i st h e s i si st oe x p l o r ea n dr e s e a r c hi n t o i m m u n en e t w o r ka n dn o n - s e l fm e c h a n i s m s ，b a s e do na r t i f i c i a li m m u n en e t w o r k m o d e l sa n dn e g a t i v es e l e c t i o na l g o r i t h mp r o p o s e db e f o r e ，d e s i g nf a s ta n de f f i c i e n t m o d e l sa n da l g o r i t h m sa n da p p l yt h e mt oa n o m a l yd e t e c t i o n t h em a i nw o r ko ft h i st h e s i sc a nb es u m m a r i z e di n t ot w om a j o ra s p e c t sa s f o l l o w s ： 1 ) an o v e la n o m a l yd e t e c t i o na t g o d t h mi sp r o p o s e di nt h i st h e s i s ，w h i c hm i x e s i m m u n en e t w o r ka n dn e g a t i v es e l e c t i o nm e c h a n i s m s t h em a i ni d e ao ft h i s a l g o r i t h ml i e so nt w oa s p e c t s f i r s t l y , aw a yi n s p i r e db yi m m u n en e t w o r kt h e o r y i sa d o p t e dt oc l u s t e rm a t u r ed e t e c t o r sa f t e ra n e g a t i v es e l e c t i o np r o c e s s s e c o n d l y , s e v e r a lb e s ts u b s e t so fd e t e c t o r sa r es e l e c t e dt od e t e c tt h ed a t ap r a c t i c a l l y a tt h e s a m et i m e ，d y n a m i cg e n e r a t i o na n di m m u n em e m o r ym e c h a n i s m so fi m m u n e n e t w o r kc a ni m p l e m e n ts e c o n d a r yi m m u n er e s p o n s e t h i sa l g o r i t h mi sa p p l i e dt o i n t r u s i o nd e t e c t i o ne x p e r i m e n t sw h i c ha r eb a s e do ns y s t e mc a l ls e q u e n c e st h e e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ea l g o r i t h mi n c r e a s e st h ed e t e c t i o n s p e e d o b v i o u s l ya n dt h ed e t e c t o rs e ti ss e l f - a d a p t i v e 2 ) c o m b i n e dt h es p e c i a lm a t c h i n gr u l eu s e di na n o m a l yd e t e c t i o n ，a ni m p r o v e d a b s t r a c t中国科学技术大学硕士学位论文 n e g a t i v es e l e c t i o na l g o r i t h mb a s e do nk - m e a n sc l u s t e r i n g 、af a s ta n o m a l y d e t e c t i o na l g o r i t h mb a s e do nc l u s t e r i n gs e l f - a d j u s t m e n td e t e c t i o ns e ta n daf a s t a n o m a l yd e t e c t i o na l g o r i t h mb a s e do nat r e es t r u c t u r ed e t e c t o rs e ta r ep r o p o s e dt o d e c r e a s et h en u m b e ro fm a t c h i n ga n di n c r e a s et h ed e t e c t i o ns p e e d a tt h es a m e t i m e ，d e t e c t o rf i l t r a t i o na l g o r i t h m sb a s e do nc l u s t e r i n gs e l v e sa r ed e s i g nt o i n c r e a s et h ef i l t r a t i o ns p e e d t h e s ea l g o r i t h m sa r ea p p l i e dt oi n t r u s i o nd e t e c t i o n e x p e r i m e n t sa n dt e s te x p e r i m e n t s ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e s e a l g o r i t h m sa r em o r ee f f e c t i v e i n s p i r e db yi m m u n en e t w o r km e c h a n i s ma n dt r a d i t i o n a lk - m e a n sc l u s t e r i n g m e t h o d ，a n da n a l y z e dt h ea p p l i c a t i o n so f n s ai na c t u a ln e t w o r ks e c u r i ty s o m en o v e l f a s ta n o m a l yd e t e c t i o na l g o r i t h m sa r ed e s i g n e dt od e c r e a s et h en u m b e ro rm a t c h i n g b e t w e e nd e t e c t o r sa n dt h ed a t u md e t e c t e d a tt h es a m et i m e ，d e t e c t o rf i l t r a t i o n a l g o r i t h m sb a s e do nc l u s t e r i n gs d v e sa r ep r o p o s e d w o r k si nt h i st h e s i sn o to n l yc a n b o o s tu pt h ep r a c t i c a b i l i t yo fa r t i f i c i a li m m u n ea l g o r i t h m so nn e t w o r ks e c u r i t y , b u t a l s oc a nb o o s tt h er e s e a r c ho na r t i f i c i a i i m m u n es y s t e m k e yw o r d s ：a r t i f i c i a li m m u n i t y ；n e g a t i v es e l e c t i o n ；i m m u n en e t w o r k ；c l u s t e r i n g a n o m a l yd e t e c t i o n 中图科学技术大学硕士学位论文 第1 章绪论 2 0 世纪后半叶，计算机科学与生命科学的交叉、渗透和相互促进已经成了 一种趋势。人工免疫系统( a r t i f i c i a li m m u n es y s t e m ：a i s ) 是继人工神经网络、 进化计算之后新的智能计算研究领域。人工免疫系统研究是在借鉴生物免疫系统 所蕴含的信息处理机制的基础上，建立相应的工程模型和算法，开拓新型智能信 息处理系统。 生物兔疫系统是个具有很强自我保护功能的系统，铯够抵御外界入侵，有 效识别己知和未知抗原，并将抗原分类清除。以此为基础的人工免疫系统方法蕴 含着抵抗外界入侵的机制，对网络安全中设计新的异常检测技术带来了启发。生 物免疫系统的b 细胞网络是一个相互刺激、抑制的动态调节的网络，鉴于此的 人工免疫网络为网络调节以及数据分析提供了新的模型。因此，研究基于非我选 择和免疫网络的快速异常检测具有重要的意义和广泛的应用前景。 本章首先介绍了人工免疫的相关概念以及生物免疫机制，然后介绍人工免疫 网络和非选择，最后是基于人工免疫的网络安全研究现状以及本文的研究内容。 第1 节人工免疫系统概述 1 1 1 人工免疫系统 什么是人工免疫系统? 一般认为，人工免疫系统是一类基于生物免疫系统的 功能、原理、基本特征以及相关理论免疫学说而建立的用于解决各种复杂问题的 计算系统【1 】。 生物免疫系统的基本功能是识别自我和非我，并将非我分类清除。是具有免 疫识别、免疫记忆、免疫调节和免疫宽容等功能特征的系统，能有效识另i j # l - 来侵 入者，维持机体本身的平衡，保证生物体自身的生存和发展 2 1 。 很多专家、学者已经逐渐认识到生物免疫系统是一个自适应、自学习、自组 织的并行和分布协调复杂系统，其中蕴含了丰富且有效的信息处理机制【3 ，4 】。 因此，抽取生物免疫系统独有的计算机制，建立人工免疫模型和系统，已经成为 中国科学技术大学硕士学位论文 当前生命科学和计算机科学交叉学科的研究热点之一。它对解决各种关系到国民 经济和社会发展的复杂问题，包括模式识别、自动控制、网络入侵检测、病毒免 疫识别和复杂优化问题求解等，具有十分引人注目的现实意义和发展前景。 生物免疫系统的基本功能是识别自我和非我。并将非我分类清除。与神经系 统、遗传进化系统相类似，生物免疫系统也是一个自适应、自学习的系统，具有 学习和记忆等功能。 1 1 2 生物免疫机制简介 自然界生物的免疫系统是一个高度复杂的分布协调白适应系统。生物免疫系 统能够抵抗外界病菌的侵入和感染，维持机体自身生理活动的稳定与平衡。下面 简要的从信息处理系统角度对生物免疫机制进行介绍。 1 生物免疫系统的组成 免疫系统是生物体执行免疫功能的机构，是产生免疫应答的物质基础。通常 可将免疫系统分为免疫器官，免疫细胞和免疫分子三大类： 免疫器官：免疫器官包括中枢免疫器官和外周免疫器官。中枢免疫器官主要 包括骨髓和胸腺，是产生免疫细胞的场所。外周免疫器官则包括脾、淋巴结、粘 膜免疫系统等。外周免疫器官又称二级免疫器官，是t 细胞、b 细胞定居的场所， 也是它们识别外来抗原后发生免疫应答的所在位置。 免疫细胞：免疫细胞主要有淋巴细胞、单核吞噬细胞等抗原呈递细胞和粒细 胞等炎症反应细胞。最基本的两种免疫细胞为b 细胞和t 细胞，它们都是淋巴 细胞。b 细胞是由骨髓产生的淋巴球，从它表面可产生“y ”形状的蛋白质，即 抗体。t 细胞则在胸腺中发育成熟，经血液和淋巴循环周游全身，以多种形式， 直接或间接地抑制和杀伤微生物或肿瘤细胞，从而保护机体。 免疫分子：包括抗体、补体分子、细胞因子等。抗体为一类免疫球蛋白，是 最重要的免疫分子。这些免疫分析的功能各不相同，主要是溶菌、杀菌、调节多 种细胞的生理功能等。 2 生物免疫识别的过程和特点 生物免疫系统最基本的功能就是识别自我和非我，并将非我的抗原分子分类 2 中国科学技术大学硕士学位论文 清楚，以此保护生物体不受外界抗原的侵害【2 】。其中，免疫识别机制是生物免 疫系统的基础。 免疫识别的功能是由免疫细胞完成的，其基本过程是由免疫细胞表面受体 ( p a t a t o p e ) 和外来抗原表位( e p i t o p t e ) 相结合，通过受体和表位间的匹配来识 别抗原。两者吻合的越好，亲和度越高，反之越低，如图1 - l 所示【2 】。 拄靡 熊稔艨 。， 、一 辑辩郓袭中等攀和窭 嵩潦霉i 腔 图卜1 受体和表位的绑定 参与免疫识别的免疫细胞主要有b 细胞和t 细胞。它们识别不同类型的抗 原，从而引起不同类型的免疫反应，即b 细胞介导的体液免疫和t 细胞介导的 细胞免疫： 1 ) t 细胞介导的细胞免疫 凡是由免疫细胞发挥效应以清除异物的作用即称为细胞免疫，参与的细胞称 为免疫效应细胞。细胞免疫包含非特异性细胞免疫和特异性细胞免疫两种类型。 非特异性细胞免疫是指效应细胞表面没有受体，无需激活就可以识别和清除抗原 的免疫反应，如巨噬细胞m m 和杀伤细胞k 。特异性细胞免疫是指效应细胞具有 抗原识别受体，们必须经抗原激活才能活化发挥其效应细胞的作用。t 细胞介导 的细胞免疫就是特异性细胞免疫【2 】。 2 ) b 细胞介导的体液免疫 1 3 细胞上的抗原受体，有时也叫b 细胞受体，是一个细胞表面免疫球蛋白分 子。抗原入侵后。首先是巨噬细胞等抗原提呈细胞对抗原进行提呈，产生抗原识 别位与1 v i h c ：分子相结合的稳定的螺旋结构复合物( 即“i v l h c 、+ j 肽”) ：然后是t h 2 细胞被该复合物激活：最后是b 细胞被1 1 1 2 细胞激活，亲和度高的b 细胞大量 分化增殖，产生大量抗体( 具有与b 细胞同样的受体) ，进而消灭抗原。 中国科学技术大学硕士学位论文 在b 细胞介导的体液免疫中，抗原的识别与清除是通过巨噬细胞、t 细胞、 b 细胞等相互作用协同完成的。图1 - 2 简要地描述了b 细胞介导的体液免疫对t 细胞依赖抗原的识别和效应过程d s 。 抗艇八舒巨噬鞭膪 图卜2b 细胞介导的体液免疫 生物体免疫识别机制对于维持生物体的正常生命活动是极端重要的，它具有 以下特点： 免疫识别：识别自我和非我，只消灭非我而不伤害自我。病菌是非我， 所以被消灭；自身的细胞却不会受到免疫系统的攻击。做器官移植时， 外来器官是非我，所以常因自我免疫系统的排斥而移植失败。 免疫记忆：当抗原再次入侵机体时，可引起比初次免疫更强的高亲和度 的抗体产生。记忆分两种，终身记忆和临时记忆。终身记忆是指一旦对 某抗原有了免疫性，终身都有免疫性。而临时记忆则不同，以前可以免 疫的，慢慢的可以退化而不再具有免疫能力。 免疫宽容：免疫活性细胞( t 细胞、b 细胞等) 接触抗原性物质时所表 现的一种特异性的无应答状态，也称免疫耐受( i m m u n o l o g i ct o l e r a n c e ) 。 免疫调节：生物体的免疫系统是一个分布协调的系统，外周免疫器官遍 布全身，各种免疫细胞在体内不停流动，且不断有免疫细胞死亡和新的 免疫细胞产生。免疫调节机制指在免疫应答过程中免疫系统内各细胞之 间、免疫细胞与免疫分子之间、以及免疫系统与其他系统如神经系统、 内分泌系统之间的相互作用，从而形成了一个既拥瓦协调又干几瓦制约的 网络结构，使免疫应答维持合适的强度保证内环境的稳定【1 6 】。 特异性：某种抗体只对特定抗原起作用，对其他抗原不起作用。 4 中国科学技术大学硕士学位论文 第2 节免疫网络与非选择简介 人工免疫网络是在生物免疫理论学说的独特型网络调节学说和克隆选择学 说的基础上发展起来的，非我选择是生物免疫系统的识别自我和非我机制。本节 首先介绍这两种理论免疫学说，然后介绍人工免疫网络以及非选择算法。 1 2 1 理论免疫学说和模型 生物学家对免疫现象的研究早在1 9 世纪就已经开始，他们提出了若干理论 免疫学说和模型，来解释生物免疫的过程。其中最著名的也被大部分免疫学家 接受的免疫理论主要是b u r n e t 提出的克隆选择学说 1 7 1 和j e m e 提出的独特型网 络调节学说【1 8 】。 1 克隆选择学说 免疫克隆学说是澳大利亚的fm b u m e t 在1 9 5 7 年提出的。克隆选择学说认 为，免疫细胞在胚胎发育阶段先广泛地生成，再接受自身抗原的刺激，使得自身 反应性细胞克隆在早期即被淘汰杀死。所以发育成熟的免疫系统不会对自身抗原 产生应答，但却仍保留对异物抗原的应答能力。外界抗原进入后，机体根据免疫 细胞表面受体和抗原表位间耦合的紧密程度来选择出高匹配度的那部分免疫细 胞，使之激活并增殖，产生专门针对该抗原的抗体，引起适当的免疫反应，最终 将其清除。图1 - 3 是一个基于克隆选择学说的免疫抽象模型。 髦虹蛔艟 图卜3 基于免疫克隆选择学说的免疫抽象模型 中国科学技术大学硬士学位论文 2 独特型网络调节学说 在b u m e t 提出的“克隆选择学说”的基础上，n k j e m e 大约在1 9 7 4 年左右 提出了“独特型网络调节学说”，并与克隆选择学说一起成为免疫学中两个最重 要的理论学说。 独特型网络调节学说认为：任何抗体分子( 或淋巴细胞) 的抗原受体上都存 在独特型抗原决定簇，独特型抗原决定簇形成独特位，它们可被生物体内另一些 抗体识别而刺激诱发产生抗独特型。抗体除了能识别抗原外，同时具有抗原特性。 即具有独特位( i d i o t y p e ，即l d ) 。图1 - 4 是一个抗体结构示意图 1 4 。其中，对 位( p a r a t o p e ) 识别抗原的表位( e p i t o p e ) ，而独特位( i d i o t y p e ) 则将被另外一 些抗体识别。 图卜4 抗体结构 图卜5j e r n e 免疫网络模型 能识别抗体独特位( i d ) 并引起反应的抗体叫抗独特型( a i d ) 抗体，能对 a j d 进行识别和反应的抗体又叫抗抗独特型( a a i d ) 抗体。这样a i d 识别i d ， a a i d 又识别a i d ，如此类推，抗体间通过独特位连成一个网络，相互激活或抑 6 绪论中国科学技术大学碗士学位论文 制，形成独特型网络调节，如图1 5 。 j e m e 独特型网络调节学说强调免疫系统中各个细胞克隆( 抗体) 不是处于 一种孤立状态，而是通过相互刺激和抑制构成一个动态平衡的网络。构成相互刺 激和相互制约的物质基础是独特型和抗独特型【1 9 】。 j e m e 的网络学说奠定了用整体的、联系的、发展的观点解释免疫调节等免 疫现象的基本思想。以此免疫学说为基础，p - d c h e r 、h o f f m a n n 、p e r e l s o n 等人提 出了新的网络模型 2 0 ，2 1 ，2 2 ，s e g e l 等人则提出了具有很大影响的形态空间 计算模型 2 3 ，2 4 。 1 2 2 人工免疫网络 j e m e 的免疫网络理论认为在免疫系统内维持一个相互连接的b 细胞网络。 借鉴j e m e 免疫网络理论建立的人工免疫网络模型中，b 细胞群体由两个子群体 组成：初始子群体和克隆子群体。初始子群体是从原始数据的一个子集中产生的， 余下的数据被用作抗原训练集。然后用每个抗原来训练初始的b 细胞网络如 果抗原与网络的某b 细胞匹配成功，则克隆变异该b 细胞 2 5 】，变异产生一系列 能用在分类程序中的抗体，一旦一个新的b 细胞被创建，尝试将和该b 细胞非 常接近( 亲和度高) 的那些细胞结合为一个整体。如果新的b 细胞不能被结合 到一个整体( 没有与它亲和度较高的b 细胞) 则被删除。如抗原没有被网络中 任一一个b 细胞匹配成功，则用该抗原作为模板产生一新的b 细胞，将该b 细 胞加入b 细胞网络中。 借鉴生物免疫网络的信息处理机制，让人工免疫网络在分类、聚类等数据分 析方法上有了新的启示。人工免疫的数据分析方法大多由两个阶段组成：网络训 练和数据解释。下面介绍两种比较有影响力的人工免疫网络及其聚类算法。 1 a 矾 t i m m i s 等人提出了一种新的数据分析方法一a i n 2 6 】。a i n 将相互间亲和 度超过预定阈值( 或者距离小于预定的某个值) 的两个检测器连接在一起。后来 的人工免疫研究学者对a i n 有进一步的研究和发展 5 8 6 0 。下面介绍a j n 的数 据聚类算法： 7 中国科学技术大学硕士学位论文 ( a ) 第一阶段：网络训练 1 1 选择部分样本初始化b 细胞网络，把余下数据作为训练集或者抗原集 2 1 计算a n 网络中每个b 细胞与抗原集中每个抗原的亲和度( 欧氏距离) ； 3 ) 根据亲和度以及与周围b 细胞的连接状况按照式( 丰) 决定激励方式和程 度： 4 ) 根据激励水平决定该b 细胞是否克隆以及克隆的数量； 5 ) 移去群体中激励最弱的部分( 如5 ) b 细胞； 6 ) 将a i n 网络中b 细胞间亲和度大于阈值n a t 的b 细胞连接起来； 7 ) 未达到聚类标准，重复以上步骤。 拈一p d - 2 萎啦 式( ) 中，p d 是b 细胞与抗原的标准化距离( 亲和度) ，也就是0 s f o r r e s t 的非选择算法。s f o r r e s t 等人将非选择算法用在u n i x 操作系 统系统下的进程行为异常检测中，来检测网络入侵 3 3 】。其基本思想是， 对系统调用序列使用滑动窗口分片在此基础上应用非选择算法。实验 证明，该算法得到的正常模式比较稳定，并且可以对正常进程和被入侵 进程做出一定程度的区分。 j k i m 的人工免疫模型。jk i m 提出了基于非选择的人工免疫模型，并 将其应用在i d s ( 网络入侵检测系统。i n t r u s i o nd e t e c t i o ns y s t e m ) 的研 究d p 3 4 ，3 5 1 。该模型结合了非选择、基因库进化和免疫记忆。采用主 i d s 和从i d s 的结构来构成分布式的入侵检测系统 同时利用基因库进 化来自适应生成检测器，使该模型具有对未知入侵模式的识别能力。 s a h o f m e y 博士提出了一个基于非选择算法的分布式检测免疫模型 f 3 6 。其主要贡献是。对非选择检测模型进行了较为详细的分析并加以 扩展：将模型应用到网络入侵中，监视广播网上的t c p 数据包。 d d a s g u p t a 就人工免疫系统的原理和应用进行了相关的研究，提出了基 于免疫a g e n t 的入侵检测系统框架【3 7 】。其思想是通过一些基于免疫机 制的a g e n t 在计算机网络上各个机器之间流动，相互协作，监视网络的 状态并发现已知和未知的入侵。 国内的研究工作主要有中国科技大学王煦法教授领导的科研小组在人 工免疫理论及其在网络安全中的应用方面完成了的工作 5 7 ，9 1 4 ， 3 8 4 3 i 武汉大学的康立山、梁意文教授领导的科研小组通过多级演化 的遗传算法等多种方法对人工免疫中的检测器生成问题进行了很多有 益的尝试 4 4 4 6 ：西安电子科技大学的焦李成教授领导的科研小组借鉴 免疫接种机制等进行了一系列工作 4 7 5 1 1 。 以上介绍了基于人工免疫的计算机安全现状。人工免疫系统的独特机制已经 引起了计算机科学家们的高度关注，越来越多的研究者正加入其中。 第4 节本文的主要研究内容及章节安排 近年来，人工免疫系统已迅速成为计算智能领域的一个研究热点。通过研究 和借鉴生物免疫系统的信息处理机制和相关免疫学说，目前已有不少学者建立了 中国科学技术大学硬士学位论文 用于解决各神网络安全闻题的计算模型和算法。 免疫网络和非选择机制是生物免疫中非常重要的两个方面。免疫网络具有免 疫调节、记忆等功能；非我选择是生物免疫系统抵御外界病毒的基本机制之一。 本论文旨在深入探索免疫网络机制与非我选择机制，在现有人工免疫网络模型以 及非选择算法的基础上，设计出更高效快速的实用性算法，并应用于实际的异常 检测。 本文的研究内容主要在于以下两点； 1 ) 提出了一种融合免疫网络与非我选择机制的异常检测算法。该算法首先 借鉴免疫网络理论对非我选择后的成熟检澳i 器进行聚类。异常检测时， 从全部子类中选择最佳的部分子类进行检测；同时，利用免疫网络的动 态生成和记忆机制来实现二次应答。文中将算法应用于基于系统调用序 列的入侵检测。实验结果表明，本算法不仅能保证检测效果，还能有效 地提高检测速度，并比较好的解决检测器集不完备的闯题。 2 ) 针对非选择算法匹配次数较多的问题，根据匹配规则的特殊性，提出了 基于k - 均值聚类的改进非选择算法、基于自适应检测器集k 均值聚类 的异常检测算法、基于多层次聚类的异常检测算法：这些算法都在很大 程度上减少了匹配次数，提高了检测速率。与此同时，提出了基于聚类 的检测器自我过滤算法。应用于模拟数据和入侵检测的实验结果都表明 这些新提出的算法快速有效。 本论文通过分析非选择算法在实际网络安全应用中的问题，结合免疫网络机 制以及传统的k 均值聚类方法，从减少检测器与待检测数据之间的匹配次数的 角度提出了新的更加快速的异常检测算法。与此同时，提出了基于自我集聚类的 检测器自我过滤算法。本文的工作不仅使得面向网络安全的人工免疫算法更加实 用，而且对人工免疫系统本身的研究也具有促进作用。 本文后面的章节安排如下： 第2 章借鉴生物免疫系统b 细胞网络以及非我选择机制，提出了一种融合 免疫网络与非我选择机制的异常检测算法，并对基于系统调用序列的网络入侵进 行了实验检测。依次介绍t i b 选择算法的特点以及各人工免疫研究者对非选择算 法的改进工作、核心算法和算法特点、具体实验以及结果讨论。 中国科学技术大学硕士学位论文 第3 章用传统的k 均值聚类方法对检测器集聚类，提出了基于k 均值的改 进非选择算法；再通过克隆变异高亲和度的检测器实现检测器集的自适应，提出 了基于对自适应检测器集聚类的异常检测算法；最后提出了将检测器集进行多层 次聚类，将检测器构造成树型结构，很大程度上提高了检测速率，在分析算法的 空间、时间复杂度后将改基于树型结构检测器的快速异常检测算法应用到基于系 统调用序列的入侵检测中。与此同时，用k - 均值方法对自我集聚类，提出了新 的检测器自我过滤算法。 第4 章是总结与展望。 第5 节本章小结 本章首先对人工免疫系统的概况做了综述，结合生物免疫机制给出当前提出 的人工免疫理论、模型及算法。然后重点介绍了人工免疫系统中有重要影响的免 疫理论学说和非选择算法，并给出了用于数据分析的两个人工免疫网络模型a i n 和a j n e t 。接下来介绍了基于人工免疫的计算机安全研究的现状。虽然该方向研 究还处于起步阶段，但人工免疫系统的独特机制已经引起了很多关注，越来越多 的研究者正在加入到其中来。最后说明了本文的主要研究内容及章节安排。 融合免痰网络与非我选择机制的异常检测中国科学技术大学硕士学位论文 第2 章融合免疫网络与非我选择机制的异常 检测 在非选择算法中。检测器生成和实际检测过程的核心操作都是匹配。由于非 选择算法中采用的是部分匹配的方法，为保证算法的准确性，非选择算法通常将 待检测数据串与检测器集内所有检测器逐一匹配直到匹配成功，匹配时间长，难 以满足实时检测需求；丽检测器完备性问题也是目前非选择算法和人工免疫系统 研究领域中急需解决的问题。 本章提出了一种融合免疫网络与非我选择机制的异常检测算法。该算法利用 免疫网络的数据分析能力对初始检测器集聚类，再基于聚类后的检测器集进行实 际检测，减少了匹配次数；同时利用免疫网络的动态生成及记忆，实现未知抗原 的二次应答，较好的解决检测器集不完备的问题。最后将该算法应用于实际的入 侵检测，给出了实验结果及分析。 第l 节非选择算法的特点以及改进 2 1 1 非选择算法及其实际应用的特点 非选择算法( n s a ：n e g a t i v es e | e c t i o na l g o r i t h m ) 是由s f o r r e s t 等人借鉴 生物免疫系统t 细胞的成熟过程和识别抗原机制于1 9 9 4 年提出的一种变化检测 算法 8 】。从非选择算法以及实际应用中可以看出有如下特点： 1 ) 基于“自我”的非选择。检测过程中不是将待检测串与自我匹配如 果与所有的自我串匹配都不成功则报警表示异常：而是产生部分( 或全 部) 不与任一自我匹配成功的检测器，在将与检测器匹配成功的串视为 有异常发生。这种非选择方法不仅能检测出有异常发生，还能够根据匹 配成功的检测器确定是何种异常发生，以便处理。 2 ) 匹配规则的模糊性。非选择算法中采用固定长度的检测器，而实际的数 据大都为变长的，所以采取精确的匹配规则很困难，一般使用部分匹配 规则( r 连续位匹配或者海明距离等) 8 ，5 2 。 1 4 融合免疫嗣络与非我选择机制的异常检测 中国科学技术太学硕士学位论文 3 ) 检测器集生成的低效。检测器是用来检测实际数据的，每个检测器都不 能与任一自我串匹配成功，产生一定数量的检测器常常需要较大的复杂 度，不过后续有贪心法及动态规划等方法产生 5 2 。 4 ) 检测效果是可调的。选择合适的检测概率以及检测器集大小可调节检测 效果 5 2 1 。 非选择算法在计算机信息处理的实际应用中( 如入侵检测、病毒预警等) ， 又具有下面的一些特点： 1 ) 自我集的不完善。在入侵检测、病毒预警等应用中，由于面对海量的正 常程序行为，很难完整的收集自我。 2 ) 检测器集的不完善。由于检测器空间的庞大，列出所有可能办在的检测 器然后进行检测将是一件非常低效的事情；实际检测中，很可能从已有 的一些异常中抽取检测器，然后再随机产生并动态补充。 3 ) 检测方法的低效。部分匹配规则的特殊牲，使得很难找出一种像索引、 二分法查找等高效的方法，一般要么根据之前的检测过程选择检测器或 者顺序检测。 4 ) 确认异常发生的不定性。一个单独的数据串旦与原数据串不同则可认 为其发生了异常，而在入侵检测、病毒预警中，由于程序行为的多样复 杂性，很难说成功匹配一个检测器的程序有异常发生；一般分析自我数 据与已知异常数据，然后给定某个阂值( 或某个范围) ，一里程序成功 匹配的检测器数( 或成功匹配的次数) 超过该阈值，则认为该程序发生 了异常。 从非选择算法以及实际异常检测的特点中可以看出，基于人工免疫的异常检 测存在检测过程中匹配次数过多，检测速度低下的问题；还存在自我集以及检测 器集不完备的问题。针对这些问题，漫计出快速、有效、自适应的异常检测算法 是非常重要的。 2 1 2 现有的针对非选择算法的改进工作 目前，针对非选择算法的很多改进工作主要集中在检测器的生成、模式匹配 规则、表示方案( r e p r e s e n t a t i o ns c h e m e ) ，以及构建新的非选择模型。主要有 融合免疫网络与非我选择机制的异常检测 中国科学技术大学硕士学位论文 如下一些： a y a r a 等人分析比较t - - 进制串的五种检测器生成方法。这五种检测器 生成方法是穷举法( e x h a u s t i v e ) 、线性方法( 1 i n e a r ) 、贪心法( g r e e d y ) 、 进制模版( b i n a r yt e m p l a t e ) 、非选择变异( n s m u t a t i o n ) 5 3 。 g o n z a l e z 等人分析比较了不同的非选择中的二进制匹配规则。主要有， 连续位匹配( r - c o n t i g u o u sm a t c h i n g ) 、，大块匹配( r c h u n km a t c h i r i g ) 、 海明距离匹配( t l a m m i n gd i s t a n c em a t c h i n g ) 以及变种r & t 匹配( r o g e r s a n dt a n i m o t om a t c h i n g ) 5 4 。 g o n z a l e z 探索了不同的表示方案，主要研究的表示方案有超矩形 ( h y p e r r e c t a n g l e s ) 、模糊规则( f u z z yr u l e s ) 、超球体 ( h y p e r s p h e r e s ) 。不同的表示方案组合不同的检测器生成算法， g o n z a l e z 提出了n s d r 、n s f d r 、r n s 、r r n s 等 5 5 】。 k i m 提出的动态克隆选择算法( d y n a m i c s ) 该算法结合了非选择、基 因库进化和免疫记忆，适合连续变化环境的检测 2 9 ，3 2 。 将实际被检测数据与检测器进行检测时，检测方案是选择怎样的策略安排检 测器与被检测数据检测。现有的检测方案有最大安全方案( m a x i m u ms e c u r i t y ) 、 间隔检测方案( i n t e r m i t t e n tc h e c k i n g ) 、基于权值的检测方案( w e i g h t e dd e t e c t i o n ) 、 分布检测方案( d i s t r i b u t e dd e t e c t i o n ) 5 2 。最大安全方案是将所有的检测器与被 检测数据挨个匹配，匹配次数太多；间隔检测方案是随机选择部分检测器进行检 测，会出现漏检情况，需要其他的辅助手段；基于权值的检测方案是根据以前成 功匹配抗原次数多的检测器优先进行检测。 结合非选择算法的特点与本节中对非选择的改进工作一起看，匹配次数过 多、检测器集不完备仍然是亟待解决的问题。 第2 节融合免疫网络与非我选择的异常检测算法及特点 根据基于人工免疫的异常检测中需要解决的问题，本节提出了一种融合免疫 网络与非我选择的异常检测算法，比较好的解决了前面分析的非选择算法在异常 检测中存在的问题。 1 6 融含免痊网络与非我选择机制的异常检测 中国科学技术大学硬士学位论文 2 2 1 算法的核心思想 借鉴免疫网络在数据分析、动态调整方面的功能，利用数据分析、动态调整 恰好解决非选择中匹配次数过多，检测器集不完备的问题。 利用人工免疫网络的数据分析能力，可以将检测器集中相互亲和度高自啦测 器聚成一个数据簇( 检测器子类) ，这样在检测的时候，只需要每个子类选择几 个代表的检测器就能知道该数据簇与被检测数据串的亲和度大致范围，从而可以 将亲和度较小的簇省去，不用继续检测，在很大程度上减少了匹配次数。利用免 疫网络的动态调整能力动态调整检测器，动态产生新的检测器以实现对未知抗原 的识别，并用记忆机制实现对未知抗原的二次应答，也可将长时间没被激活的检 测器从检测器集中删去。具体的过程如下。 首先通过免疫网络对初始检测器集的全部检测器进行聚类：然后，在检测过 程中，将待检测数据串与每个子类的代表检测器进行匹配，选择亲和度较高的若 干个子类，并将这些子类中的全部检测器逐一与待检测数据串进行匹配，如果匹 配成功则报警；如不能匹配成功则按比例选择亲和度高的部分检测器进行克隆变 异产生新的检测器进一步对该数据串进行检测，直到匹配成功或达到预定的迭代 次数。最后将匹配成功且是新产生的新检测器加入到初始检测器集，动态调整检 测器网络将该检测器划入相应的检测器子类中。 2 2 2 算法描述 为了便于说明算法的详细步骤，首先给出需要用到的符号及其含义如下： s ：自我集 尺：成熟检测器集，简称检测器集 k ：聚类产生的子类数目 c ：被选取的具有较高亲和度的子类数目 d _ 垦 、一 否 否 一一 依次选择高亲和 度检测器克隆变 异 新的检测器集岛+ ， 是结柬 图3 - 3 基于一适应检测器集k 均值聚类的异常检测算法流程 本算法的特点与融合免疫网络、非我选择机制的异常检测算法特点基本类