（电路与系统专业论文）基于人工免疫的入侵检测的硬件实现研究[电路与系统专业优秀论文].pdf

浙江大学硕士学位论文 摘要 随着计算机互连网络的发展和广泛应用，网络安全特别是网络入侵检测 ( i n t r u s i o nd 咖c 如ns y s t e m , i d s ) n 题变得越来越严重。对于入侵检测系统来说， 入侵的检测和分析模块是系统的核心。由于传统的入侵检测系统大多是静态的， 很难与动态环境协调一致，造成分布性差，适应性差，健壮性不好等种种缺陷； 而生物免疫系统可以保护人类机体不受诸如病毒，病菌等各种病原体的侵害，且 表现出了分布式保护，多样性，自组织性，动态性等良好特性，且这种与入侵检 测系统在功能和特性上的惊人相似，引起人们的高度重视和兴趣，使得借鉴生物 免疫系统的机理开发研究入侵检测系统成为网络安全的研究热点和重点。 本论文研究的入侵检测是以人工免疫的阴性选择算法为基础的一种分布式 检测，属于网络型的基于异常的检测，检测方法采用监视数据包的方式。检测系 统分为两个阶段：一，产生成熟检测器，二，用成熟检测器检测异常。 文章首先对人工( 生物) 免疫系统和入侵检测的一些基本概念和原理等进行 了较为详细的介绍；然后在原有阴性选择算法的基础上进行了略微改进，提高了 检测器的检测能力，并重点对阴性选择模块用硬件实现之：分别对三种阴性选择 算法中涉及的常见的匹配算法( r c h , r c b , h a m m i n g ) 进行优化实现，r c h ， h a m m i n g 算法模块用流水线且并行实现，对r c b 匹配算法的实现时提出了一个 通用序列检测器的思想；用并列l f s r 组成伪随机数发生器( 周期非常大) 实现 随机字符串( 4 9 位) 的生成；为了高效和准确的进行匹配，设计了占空比为5 0 的通用奇偶分频器( g l i t c h - f r e e ) ，其设计思想简单实用高效稳定；所有硬件实现 都是面向速度优化为主，面积优化为辅的宗旨。最后细化总体硬件实现框架并对 改进的阴性选择算法模块与原算法模块进行了大量的样本( 数据通路三元组，4 9 位) 验证，证实了改进模块确实提高了检测器的检测能力。 i 关键字】： 人工免疫入侵检测阴性选择检测器r c br c hh a m m i n g 浙江大学硕士学位论文 a b s t r a c t 、 j t ht h er a p i de x t e n s i o na n dw i d e l ya p p l i c a t i o no ft h ei n t e m e t 。n e t w o r k s e c u r i t y 。e s p e c i a l l yn e t w o r ki n t r u s i o n ，h a sb e c o m e e v e rs e r i o u s t h ed e t e c t i o n a n da n a l y s i sp a r t sa r et h em o s ti m p o r t a n tf o rt h ei n t r u s i o nd e t e c t i o ns y s t e m a st h em o s to ft r a d i t i o n a ii n t r u s i o nd e t e c t i o ns y s t e m sa r es t a t i ca n dh a v e d i f f i c u 时i nc o o r d i n a t i n gw i t ht h eo u t e rd y n a m i cs i t u a t i o n ，c o n s e q u e n t l y , l e a d i n g t oas e r i a lo fd e f i c i e n c ys u c ha sl i m i t e dd i s t r i b u t i o n 1 i m i t e da c c o m m o d a t i o na n d l i m i t e dr o b u s te t c f o r t u n a t e l y , t h eh u m a ni m m u n es y s t e mc a np r o t e c t t h e m s e l v e sf r o mt h ei n v a s i o no ft h ev i r u s ，g e r m i n aa n da l ls u c hs o r to ft h i n g s m e a n w h i l e ，t h e yh a sal o to fe x c e l l e n tf e a t u r e ss u c ha sg o o dd i s t r i b u t i o n ， s e l f - o r g a n i z a t i o n ，d y n a m i ca n ds oo na n dt h e s ef e a t u r e sp e r f o r mf a b u l o u s s i m i l a r i t yo nt h ef u n c t i o na n dc h a r a c t e r i s t i cw i t h t h ei n t r u s i o nd e t e c t i o n s y s t e m ，w h i c ha r o u s i n gp e o p l e sh i g h l ya t t e n t i o na n di n t e r e s t i n ga n dm a k et h e r e s e a r c h i n ga n dd e v e l o p m e n to ft h ei n t r u s i o nd e t e c t i o ns y s t e mb a s e dh u m a n i m m u n es y s t e mb e c o m i n go n eo ft h eh o ta n dt h ek e yo ft h en e t w o r ks e c u r i t y r e s e a r c h t h ei n t r u s i o nd e t e c t i o ns y s t e mt h i sp a p e rp a ya t t e n t i o nt oi sak i n do f d i s t r i b u t i o nd e t e c t i o nw h i c hb a s e do nn e g a t i v es e l e c t i o na l g o r i t h mo ft h e a r t i f i c i a li m m u n es y s t e m i ti so n eo ft h en e t w o r ke x c e p t i o nd e t e c t i o na n dw i t h t h ew a t c h i n gd a t ap a c k a g em e t h o d t h ed e t e c t i o ns y s t e mi so r g a n i z e db yt w o p a r t s ：g e n e r a t i n gt h em a t u r ed e t e c t o r sa n dd e t e c t i n gt h ee x c e p t i o nw i t ht h e s e d e t e c t o r s f o rt h ef i r s t p a r t ，t h i sp a p e rg i v ead e t a i li n t r o d u c t i o na b o u tt h eb a s i c c o n c e p ta n dt h e o r yo ft h eh u m a ni m m u n es y s t e ma n di n t r u s i o nd e t e c t i o n s y s t e m t h e nm a k i n gal i t t l ei m p r o v e m e n ta c c o r d i n gt ot h eo r i g i n a ln e g a t i v e s e l e c t i o na l g o r i t h m ，w h i c hi n c r e a s i n gt h ea b i l i t yo fd e t e c t i o n a n dp a y i n g a t t e n t i o nt ot h eh a r d w a r ei m p l e m e n t a t i o no ft h en e g a t i v es e l e c t i o na l g o r i t h m m o d u l e ：i m p l e m e n tt h em o s tc o m m o nt h r e em a t c ha l g o r i t h m s ( r c b ，h a m m i n g r c h ，) o ft h en e g a t i v es e l e c t i o na l g o r i t h ma n d w i t ht h ep i p e l i n em e t h o df o rr c h a n dh a m m i n ga l g o r i t h ma n dp u tf o r w a r dau n i v e r s a ls e d a ld e t e c t i o nm e t h o d w h e nd e a l i n gw i t ht h er c ba l g o r i t h m ；g e n e r a t et h er a n d o mc h a r a c t e rs t d n g s w i t ht h ep h o n yr a n d o mg e n e r a t o rw h i c hi sc o m p o s e db yl f s rp a r a l l e l l y t o m a t c hm o r ee f f e c t i v ea n dc o r r e c t l y , d e s i g nao d d a n de v e nc l o c kd i v i d e r ( g l i t c h 浙江大学硕士学位论文 - f r e e ) w i t ht h ed u t yc y c l eo f5 0 a l lt h eh a r d w a r ei m p l e m e n t a t i o na r e o r i e n t a t e dw i t ht h es p e e dr e d u c t i o ni n s t e a do fa r e ar e d u c t i o n f i n a l l y , t h i sp a p e r g i v ead e t a i l e df r a m eo ft h eh a r d w a r ei m p l e m e n t a t i o na n dd oa sm u c ha s s a m p l ev e r i f i c a t i o nf o rt h ei m p r o v e dn e g a t i v es e l e c t i o na l g o r i t h mm o d u l e c o m p a r e dw i t ht h eo r i g i n a l ，a n dm a k es u r et h ei m p r o v e m e n td o e sw o r k s k e y w o r d ： a r t i f i c i a l i m m u n e 。i n t r u s i o nd e t e c t i o n ，n e g a t i v es e l e c t i o n ， d e t e c t o r , r c h r c b ，h a m m i n g i 浙江大学硕士学位论文 第一章绪论 1 1 人工免疫系统概述 1 1 1 什么是人工免疫系统 什么是人工免疫系统? 一般认为，人工免疫系统是一类基于生物免疫系统的 功能。原理，基本特征以及相关理论免疫学说而建立的用于解决各种复杂闽题的 计算系统。 生物免疫系统的基本功能是识别自我和非我，并将非我部分分类清除。生物 免疫系统具有免疫识别，免疫记忆，免疫调节和免疫宽容等功能特征，能有效识 别外来侵入者，维持机体本身的平衡，保证生物体自身的生存和发展。生物免疫 学的发展，特别是从2 0 世纪后半期以来的现代免疫学的迅速发展，为人工免疫 系统的研究提供了相应的理论基础。 很多计算机学家和免疫学家，特别是人工智能专家，已经逐渐认识到生物免 疫系统是一个自适应，自学习，自组织的并行处理和分布协调复杂系统，其中蕴 涵了丰富且有效的信息处理机制。因此，抽取生物免疫系统独有的计算机制，建 立人工免疫模型和系统，己成为当前生命科学和计算机科学交叉学科的研究热点 之一。它对解决各类关系到国民经济和社会发展的复杂问题，包括机器人控制， 模式识别，调度和规划，网络入侵检测，病毒免疫识别和复杂优化问题求解等， 具有十分引人注目的现实和发展前景。 1 1 2 人工免疫系统的生物学基础 免疫系统的组成主要有免疫器官和免疫细胞。免疫器官有胸腺，骨髓，淋巴 结，脾脏等。免疫细胞有淋巴细胞，单核吞噬细胞，粒细胞等。 生物保护自身免受外来病菌的侵害是通过其免疫系统完成的。免疫系统的物 质基础是淋巴细胞，它们由骨髓产生，分布于全身，种类繁多，各自起着不同的 作用。 淋巴细胞中重要的有t 细胞和b 细胞。在骨髓中产生的未成熟t 细胞进入 另一个中枢免疫器官胸腺，在其中分化发育为两大类t 细胞，不合格的t 细 胞( 会产生自体免疫) 被消灭，而成熟的t 细胞分布在脾和淋巴结中以等待外 来入侵。从所有未成熟t 细胞中选择符合条件的成熟t 细胞的过程称为“阴性 浙江大学硬士学位论文 选择”。每个b 细胞产生一种依附于其表面的抗体，用以探测相应的抗原b 细 胞可以产生数百万不同种类的抗体，每个抗体只对一种抗原有效，这就是免疫系 统的多样性和特定性。当b 细胞探测到抗原，并收到辅助t 细胞发来的信号时， 便产生免疫应答。其中一部分b 细胞转化为浆细胞，产生与抗原相应的抗体， 并与抗原结合使之失去活性，从而达到清除抗原的目的，这个过程就是先天免疫。 没有转化为浆细胞的b 细胞则变为记忆细胞，记录下该抗原的特征，以提高将 来对同一抗原的反应速度。这一反应是后天形成的，称为后天免疫。我们要借鉴 的就是生物的后天免疫机制。 免疫应答有几个重要的特征：1 ) 特异性。免疫活性细胞仅能与相应的抗原 起反应，而与无关的抗原不发生反应；2 ) 排它性。免疫系统能识别“自己”和 “非己”抗原，对。非已”的外来抗原产生免疫应答，对“自己”抗原一般没有 反应；3 ) 多样性。免疫系统具有庞大的t 细胞和b 细胞库，可与几乎所有的 外界抗原发生应答；4 ) 记忆性。初次接触的抗原被排除后，机体可长期保留这 种抗原信息，形成特异性记忆免疫活性细胞，当再次接触同一抗原时，就会产生 迅速而更强的免疫应答；5 ) 分布性。成熟的免疫活性细胞分布于全身的淋巴， 各自完成检测异己抗原的功能，不需要集中控制。 生物免疫系统具有的分布式、自适应和平衡动态能力，正是现有网络系统所 不具备的，我们可以应用生物系统的免疫原理，构造用于进行网络入侵检测的人 工免疫，解决现有入侵检测系统的不足，改进其性能。 1 2 入侵检测系统概述 1 2 1 什么是入侵检测 入侵检测：顾名思义，便是对入侵行为的发觉。它通过对计算机网络或计算 机系统中得若干关键点收集信息并对其进行分析，从中发现网络或系统中是否有 违反安全策略的行为和被攻击的迹象。进行入侵检测的软件与硬件的组合便是入 侵检测系统( i n t r u s i o nd e t e c t i o ns y s t e m ，简称i d s ) 。与其他安全产品不同的是， 入侵检测系统需要更多的智能，它必须可以将得到的数据进行分析，并得出有用 的结果。一个合格的入侵检测系统能大大的简化管理员的工作，保证网络安全的 运行。 网络中的安全威胁主要有： 1 ) 身份窃取，指用户的身份在通信时被非法窃取； 2 ) 假冒，指非法用户假冒合法用户获取敏感信息的行为； 3 ) 数据窃取，指非法用户截获通信网络的数据； 2 浙江大学硕士学位论文 4 ) 否认，指通信方事后否认曾经参与某次活动的行为； 5 ) 非授权访问； 6 ) 拒绝服务，指合法用户的正当申请被拒绝，延迟，更改等； 7 ) 错误路由； 1 2 2 入侵检测的分类 1 ) 根据检测对象的不同，入侵检测系统可分为主机型和网络型： 基于主机的监测。主机型入侵检测系统就是以系统日志、应用程序日志等作 为数据源，当然也可以通过其他手段( 如监督系统调用) 从所在的主机收集信息 进行分析主机型入侵检测系统保护的一般是所在的系统。这种系统经常运行在 被监测的系统之上，用以监测系统上正在运行的进程是否合法。最近出现的一种 i d ( i n t r u s i o nd e t e c t i o n ) 位于操作系统的内核之中并监测系统的最底层行为。 所有这些系统最近已经可以被用于多种平台。 网络型入侵检测。它的数据源是网络上的数据包。往往将一台机子的网卡设 于混杂模式，对所有本网段内的数据包并进行信息收集，并进行判断。一般网络 型入侵检测系统担负着保护整个网段的任务。本文研究的是这类入侵检测。 不难看出，网络型i d s 的优点主要是简便：一个网段上只需安装一个或几 个这样的系统，便可以监测整个网段的情况。且由于往往分出单独的计算机做这 种应用，不会给运行关键业务的主机带来负载上的增加。但由于现在网络的日趋 复杂和高速网络的普及，这种结构正受到越来越大的挑战。一个典型的例子便是 交换式以太网。 而尽管主机型i d s 的缺点显而易见：必须为不同平台开发不同的程序、增 加系统负荷、所需安装数量众多等，但是内在结构却没有任何束缚，同时可以利 用操作系统本身提供的功能、并结合异常分析，更准确的报告攻击行为。 2 ) 从技术上，入侵检测也可分为两类：一种基于标志( s i g n a t u r e - b a s e d ) ， 另一种基于异常情况( a n o m a l y - b a s e d ) ： 对于基于标志的检测技术来说，首先要定义违背安全策略的事件的特征，如 网络数据包的某些头信息。检测主要判别这类特征是否在所收集到的数据中出 现。此方法非常类似杀毒软件。 而基于异常的检测技术则是先定义一组系统。正常情况的数值，如c p u 利 用率、内存利用率、文件校验和等( 这类数据可以人为定义，也可以通过观察系 统、并用统计的办法得出) ，然后将系统运行时的数值与所定义的。正常“情况比 较，得出是否有被攻击的迹象。这种检测方式的核心在于如何定义所谓的。正常” 情况。本文研究的正是基于异常的检测技术。 浙江大学硕士学位论文 两种检测技术的方法、所得出的结论有非常大的差异。基于标志的检测技术 的核心是维护一个知识库。对于已知的攻击，它可以详细、准确的报告出攻击类 型，但是对未知攻击却效果有限，而且知识库必须不断更新。基于异常的检测技 术则无法准确判别出攻击的手法，但它可以( 至少在理论上可以) 判别更广泛、 甚至未发觉的攻击。 1 3 基于人工免疫的入侵检测进展 1 3 1 入侵免疫系统中应用的免疫机制的分类 1 ) 以氨基酸短序列为基础的免疫识别机制。 2 ) 以受体编码基因库为基础的免疫多样性机制。 3 ) 以阴性选择为基础的免疫耐受机制和分布式检测机制。本文研究的是此类 免疫机制。 4 ) 以记忆b 细胞为基础的免疫记忆机制。 1 3 2 入侵检测研究现状 基于人工免疫的入侵检测研究这几年也刚刚起步。由于生物免疫系统的自我 保护机制给解决当前入侵检测系统面临的难题带来了新的灵感和希望，自然而然 地它就成为网络安全和人工免疫系统研究领域中最弓f 入注目的研究热点之一。 目前相关研究工作主要体现在以下几个方面： 1 ) f a b r i c i os p a u l a 等人提出的基于生物免疫机制的混合型入侵检测模型。 他们借鉴生物免疫系统的先天免疫和自适应免疫，设计了一个包含异常检测和误 用检测模块在内的入侵检测模型，但目前还是仅仅停留在模型设计上，没有在具 体算法和系统的设计实现方面开展实际工作。 2 ) s f o r r e s t 和s a h o f m e y r 等人对阴性选择算法用于入侵检测时面临的 问题进行了分析和相关实验，偏重于基本检测原理和理论。 3 ) j k i m 等人基于阴性选择算法，基因库进化，静态克隆选择算法，动 态克隆选择算法的入侵检测算法和模型研究，其工作则主要从克隆选择的角度对 阴性选择算法进一步改进，也还没有在具体的系统设计与实现方面开展实际工 作。 4 ) 美国m e m p h i s 大学数学系d a s g u p t a 博士领导的智能安全系统实验室 主要基于免疫a g e n t 的角度对入侵检测进行相关研究。与此同时，该研究还从 人工免疫系统与模糊，进化等方法相结合的角度来研究入侵检测系统。 4 浙江大学硕士学位论文 5 ) 中国科技大学王煦法教授所领导的项目组则从免疫功能特征，免疫学习 原理，免疫理论学说等多个角度针对入侵检测系统进行了相关算法，模型和系统 设计，其研究成果已通过省部级鉴定。 等等 目前国内外影响较大的几个算法研究成果为：( 1 ) 阴性选择算法，如前所述， 阴性选择算法是s f o r r e s t 等人基于t 细胞的产生过程而提出的一种异常检测算 法。( 2 ) 克隆选择算法，克隆选择算法是d e c a s t r o 等人基于克隆选择学说提出 的一种免疫学习算法。( 3 ) 免疫网络算法，免疫网络算法是j 1 1 m m i s 等人基于 免疫网络调节理论提出的一种学习算法。 总的来说，目前基于人工免疫的入侵检测研究还处于起步阶段，均为一些基 本的模型或算法研究，缺乏系统性的研究，更缺少具体的硬件实现，也尚未建立 一个实际的基于人工免疫的网络入侵检测系统。 1 4 入侵检测研究意义 面对日益加剧的网络安全威胁，传统的静态安全技术如认证机制、加密和防 火墙等已经难以胜任。入侵检测作为一种重要的动态安全技术，能够提供对计算 机系统和网络的外部攻击、内部攻击及误操作的全面检测，其主要功能是监视并 分析用户和系统的行为、审计系统构造和弱点、评估重要系统和数据文件的完整 性、识别已知攻击的行为模式、异常行为模式的统计分析、操作系统的审计跟踪 管理和识别用户违反安全策略的行为。作为防火墙之后的第2 道安全防线，入 侵检测已成为网络安全领域重要而迫切的课题。 为此，近几年人们把入侵检测技术与生物免疫系统相结合，通过对自然免疫 系统的模拟研究，力图使计算机网络系统获得更多理想的安全特性( 动态适应性， 针对行为的异常检测，分布式处理和多样性，鲁棒性，可以与其他技术融合的多 层机制) ，这就导致了一种新型、智能化的入侵检测系统网络入侵免疫系统 的诞生，并成为当今的研究热点之一 1 5 本论文的研究内容与组织安排 本论文主要研究内容是基于人工免疫的入侵检测系统中的阴性选择算法部 分，在算法改进的基础上进行优化的硬件实现。并最后进行验证与评估。 本论文共分为五章，第一章绪论，总体上介绍下人工免疫和入侵检测的概 念；第二章基础理论，介绍涉及到人工免疫和入侵检测方面一些基础并重要的原 理：第三章架构实现，提出了一种新的阴性选择算法和架构并用硬件实现和仿真； 浙江大学硕士学位论文 第四章细化阴性选择算法系统架构并测试评估：第五章是总结与展望。 6 浙江大学硕士学位论文 第二章基础理论 2 1 生物免疫系统的特点 生物免疫系统是一个高度分布，并行和自适应的系统，它的如下特点为构建 健壮的计算机安全系统提供了重要线索： 多层性：生物免疫系统对外来侵害提供多层保护。例如，皮肤为第一道屏 障，阻止病菌进入生物体内；第二道屏障是生理上的，通过免疫细胞识别和消灭 侵入的病菌。这一特征在有些计算机安全中已经得到应用，例如防火墙的过滤功 能，代理功能以及主机自身的安全系统构成了对网络的多层保护。这一特性应得 到进一步加强。 不完全匹配性：免疫响应是特异性的，每种抗体或受体只能识别和结合特 定的抗原。同时人们又发现，体内的约| 0 6 种不同的淋巴细胞能识别约1 0 1 6 种不 同的外来抗原模式。因此，抗原和抗体的匹配是不完全的，即不是一一对应的。 一个淋巴细胞可以对应几种或几十种不同的，结构相近的抗原作出反应。借鉴这 一特性，解决某些计算机安全方面的问题，将会十分有效。例如在病毒检测中， 使用有限的检测器可以检测出较多的计算机病毒。 自学习功能：如果免疫系统检测到以前从未遇到过的病菌，它将经历初次 免疫系统响应，并“学习”该特定病菌的结构，之后当遇到相同的病菌模式时， 免疫系统将快速做出响应。免疫系统检测新病菌，并通过免疫记亿保存该病菌的 特征。这一特征对计算机安全十分重要，例如，目前各种计算机病毒产品都面临 着一个难题：他们只能识别出已知病毒，而识别不出新病毒。利用免疫系统的“学 习”特性，可以迅速对付各种新病毒的产生和传播。 多样性：由于胚胎期的遗传和免疫细胞在增殖中发生的基因突变，形成了 免疫细胞的多样性。首先，有机体内免疫细胞的多样性保证：当每一种抗原侵入 机体时，都能在机体内选择出可识别和消灭相应抗原的免疫细胞，并使之激活， 分化和增殖，进行免疫响应，最终清除抗原。其次，每个个体都有一个都一无二 的免疫系统，存在着群体免疫系统的多样性。这种多样性保证：当有个体对某病 菌呈现脆弱性时，不会出现所有个性都对同一病菌呈现脆弱性的情况。因此，免 疫系统的多样性可大大增强个体与群体的健壮性。借鉴这一特性，可以使不同的 站点或网络具有不同的安全系统，保证一个站点或网络受到攻击破坏时，其他站 点或网络极少受到同样的攻击或破坏。 分布性：免疫系统是一个包括免疫器官，免疫细胞和免疫分子的庞杂系统， 其各组成部分分布于生物体全身，免疫应答是无集中控制的，它通过分布在全身 7 浙江大学硕士学位论文 众多的局部免疫部件之间的相互作用，来实现对整个集体的保护。在计算机网络 安全的体系结构中，有人提出了分布的，移动的安全代理结构，以实现这一特性 的应用。 动态性：淋巴细胞在体内不断地循环和更新，使免疫保护呈现动态特性。 通常，免疫细胞的生存期短( 仅几天) ，它们不断地被新产生的淋巴细胞所替代， 使得免疫细胞多样化。这种多样化扩大了免疫系统的免疫范围。在计算机安全领 域，无法预先定义所有攻击模式，使用这一动态特性，可以扩大检测入侵的范围。 2 2 人工免疫模型( a r t i s ) h o f m e y r 引进了一种融合多种免疫系统性能的人工免疫模型( a r t i s ， a r t i f i c i a li m m u n es y s t e m ) ，包括多样性，分布式计算，错误耐受，动态学习和适 应性与自我监测( s e l f - m o n i t o r i n g ) ，a r t i s 是分布式自适应系统的一般框架，该 系统基于免疫系统检测抗原原理应用在网络环境，构成计算机安全系统。 2 2 1 基本定义 在免疫系统中，基于在蛋白质链之间形成的化学结合区分为自体和非自体。 为保持一般性，用固定长度为l 的二进制字符模拟蛋白质链。免疫系统基于蛋 白质区分自体和非自体。 a r ：n s 模型解决类似问题，定义如下： 所有长度为l 的字符串集合形成一个空间u 。分为两个子集：自体s ，非自 体n ( u = su n ，st 3 n = a ) a r t i s 模型实现区分或分类任务：给定u 中一个 任意二进制字符串，按正常( 自体) 或异常( 非自体) 分类。该定义可以推广到 在多种类种分类，不仅是自体和非自体两类。 a r n s 能区分两种错误：当一个自体字符串分类为异常时，发生错误肯定， 而当一个非自体字符串分类为正常时，发生错误否定。免疫系统也进行类似错误 区分：当免疫系统袭击身体时( 自体免疫应答) ，发生错误否定；免疫系统检测 和抗击病原体失败时，发生错误否定。在人体中两种错误都是有害的；所以，免 疫系统已经进化到可以避免发生错误。类似地，a r t i s 也使这两种错误最小化。 如图2 1 所示： 浙江大学硕士学位论文 图2 1 一个字符串结构的二维表示 每一个字符串属于两个集合中的一个：自体和非自体。在图2 1 中，平面中 每一个点表示一个字符串，如果该点在阴影面积中则是自体，否则是非自体。免 疫检测系统在两个集合之问通过对字符串进行正常( 对应自体) 或异常( 对应非 自体) 分类来给边界编码。 当实际问题抽象化时，自体和非自体可能是相交的，因为一些字符串既有自 体又有非自体的特征。在这种情况下，字符串分为一类或是另一类则会导致不可 避免的错误。所以我们应该回避这种情况。 2 2 2 检测器及其生命周期 自然免疫系统有许多不同种类细胞和分子组成。该系统只简单介绍一种基本 类型的检铡器，模拟淋巴细胞这样的免疫细胞。检测器融合了b 细胞、t 细胞和 抗体的性质。a r t i s 具有类似免疫系统的特征，即它有许多流动的检测集组成， 这些流动的检测集在分布式环境中不断循环，用以监控是否有异常出现。 在淋巴细胞表面有成百上千种同样的抗体，这些抗体结合在病原体上的区 域，结合取决于化学结构和电荷，一个抗体可能结合几个类似的抗原决定基。在 a r t i s 中，抗原决定基和抗体被模拟成固定长度为l 的二进制字符串，产生的 检测集中每一个字符串与自体s 中的任何字符串当且仅当至少r 个连续位上一样 时才称这两个字符串是匹配的。r 为匹配阈值，这种匹配规则我们称之为r 连续 位部分匹配规则，如图2 2 所示： r = 4 0 1 j q j 0 0 10 l 0 l0 q j 】0 10 0 9 浙江大学硕士学位论文 11 1 q j 11101 匹配 111 鱼j j ，1101 无匹配 图2 2 连续位规则下的匹配 产生检测集r 算法如图2 3 所示： 图2 3 产生检测器集合的阴性选择算法示意图 如果检测器无限期存活下去，只在接受协同刺激失败时死亡，则多数检测器 会只成熟一次。任何发生在这些检测器未成熟期间的非自体字符串不会在未来被 检测到，因为所有检测器会被耐受并保持耐受。然而在生物免疫系统中不会存在 这个问题，因为淋巴细胞是典型的短命细胞( 才几天时间) ，所以总是出现新的 未成熟淋巴细胞，也就是淋巴细胞群体的动态性。枷s 模型引入类似的测量方 法：每一个检测器一旦成熟就具有死亡概率p d 曲。死亡后，由新的随机产生的 未成熟检测器取代。最终，每一个检测器都死亡，除非它是记忆检测器。 每个检测器要经过以下几个状态： ( 1 ) 随机产生态随机产生字符串集合，构成最初始的检测器，进入未成熟 状态。 ( 2 ) 未成熟状态进入未成熟状态的检测器经过耐受期，采用反面选择算法 的步骤2 检查检测器是否与“自身”集合s 匹配。如果发生匹配，检则器被清 除，否则进入成熟且未激活状态。 ( 3 ) 成熟且未激活状态该阶段的检测器都有一定的存在时间，在存在期限 内，如果检测器与被检测集合s 发生匹配，则进入激活状态；如果存在期限已到 1 0 浙江大学硕士学位论文 而尚未被激活，该检测器被清除。 ( 4 ) 激活状态检测器被激活意味着系统可能发生了异常情况，但仍然需要 确认。确认过程可以由系统管理员来完成。如果确定是异常情况。检测器进入记 忆状态；否则，该检测器被清除。 ( 5 ) 记忆状态进入记忆状态的检测器具有长期的存在时间，并且具有比较 低的激活阈值，一旦发生匹配贝立刻进入激活状态。 动态检测器的循环周期如图2 4 所示： 图2 a 检测器的生命周期 2 2 3 阴性选择算法 阴性选择算法基于免疫系统的自体非白体识别原理，其核心思想是定义一 个自我集作为训练集来产生不与自我集模式匹配的检测元素，使用这些检测元素 进行入侵检测。基本步骤如下： 1 ) 依照特定的算法，从需要保护的正常数据集合种产生一组长度为l 的有 限字符串集合s ，构成“自身”。若从网络安全考虑，这里的正常数据集合，可 浙江大学硕士学位论文 能是来自被保护的文档，也可能是来自系统的呼叫进程调用。 2 ) 根据集合s 产生检测器集合r ，r 中的每个检测器也是长度为l 的字符 串，它与s 中的每个字符串都不匹配。 3 ) 不断地将集合r 中的检测器与被检测集合s 进行比较，监控s 中的 改变。如果某个检测器与s 中的字符串产生了匹配现象，则意味着s 中可能 发生了异变( 非法入侵、病毒或异常错误等) 。 符号字符串中的部分匹配有许多定义方法，比如海明距离或者编辑距离，这 里采用r 连续位匹配规则。用等长的两个字符串之间r 连续位规则测量其相似性。 例如： x ：b c a b c b a d y ：d c a b d c b a x 和y 是定义超过四个字母的字符串，x 和y 在三个连续位匹配，这样匹 配对于r 3 是对的，r 3 是错的。 根据匹配阈值r 检测样本字符串，匹配规则提供严格检测器，如图2 5 所示： 表明定义长度的字符串的覆盖指数随r 的减少而增加。r ：l 得到最大覆盖，但是 产生的检测器可能与许多自体字符串在错误检测中匹配。理想匹配表示在两个字 符串上的每个位置符号都一样，因此需要大量的检测器检测非自体模式。要用该 方法成功估计合理模块的检测器集合，则需优化r 值。 以上算法主要依赖于以下三个重要原理：( 1 ) 检测算法的每个拷贝是唯一的； ( 2 ) 检测是概率的；( 3 ) 它是概率地检测任何异常活动，而不是寻找特定已知 改变模式的鲁棒系统。 阴性选择算法的性质：首先极易分布，每个检测器都能独立地行使功能，无 需在检测器之间交流或协调，因为每一个检测器只覆盖非自体的一部分，组检 测器可以分布在多个位置。第二个性质：如果假设一个封闭世界和自体完整规定， 就不会有错误肯定，这取决于如何选择检测器，无论如何有错误否定的机会；所 以算法更适应动态或者干扰数据。 该算法已广泛用于信息处理，免疫自适应系统研究和解决计算机科学中未解 决的一些重要问题中。 浙江大学硕士学位论文 形 状 空 间 由 的 匹 配 1 0 0 0 1 0 0 1 0 l234 567891 01 1 1 21 31 4 1 51 6 匹配阈值( r ) 图2 5 每个二进制字符串能覆盖多少点随不同匹配阈值变化 2 2 4 黑洞问题 利用阴性选择方法生成检测器集合，会出现如下问题：存在某些非我字符串， 找不到有效的检测器发现它。这个非我字符串称为一个检测“黑洞”。采用形式 化的语言进行描述：某个字符串a nf n o 赋l f ) ，如果任意给定一个字符串s o ( u 为字符串整个空间) , m a t c h ( s ，a ) = t r u e ，其中s s ( s e l f ) ，则a 就是一个检测 “黑洞”。 例如，s i = 0 0 1 1 0 1 ，s 2 = 1 1 1 1 1 1 ，$ 3 = 0 0 1 1 1 1 ，r 连续位匹配函数中的参数r = 3 ，那么 与s 3 匹配的检测器集为：d 3 = s 0 0 1 3 3 3 u $ 3 0 1 1 3 3 u $ 3 3 1 1 1 3 u $ 3 3 3 i l l ，这里 s 0 0 1 3 3 3 是由模板0 0 1 3 3 3 产生的一个6 位的字符串子集( “3 ”表示该字符可以 是任意的0 或1 ) 。d 3 中所有的检测器都与s 1 或s 2 匹配。如果s l 和s 2 都是s e l f 集里的，即s 1 ，s 2 s ，并且s 3 是属于n o n s e l f 集合里的，即s 3 n ，那么任何与s 3 匹 浙扛大学硕士学位论文 配的字符串都至少与s e l f 集合里的一个字符串相匹配，因此s 3 就是个检测黑 洞。 黑洞的存在取决于模式集的结构和模式匹配所基于的匹配规则。如果自我模 式集中的自我模式串和非我模式集中的非我模式串越相似，黑洞的数量也就越 多。同时，所有具有恒定匹配概率的匹配规则，随着匹配粒度的增加，黑洞的数目相 应地减少。由于黑洞不可能被任何检测器所检测到，所以应该尽可能减少黑洞的 数量及其出现的概率。 2 2 5 应答 免疫系统有两种免疫应答类型：一种是遇病原体后，首先并迅速地起防卫作 用地称为固有性免疫应答( i n n a mi n a n l l l n er e s p o n s e ) ；另一种是适应性免疫应答 ( a d a p 6 v ei i l i i n u o er e s p o n s e ) 固有免疫应答中，执行固有免疫功能的有皮肤和黏膜的物理阻挡作用及局部 细胞分泌的抑菌，杀菌物质的化学作用等。固有免疫的感染早期执行防卫功能。 适应性免疫应答的执行者是t 及b 淋巴细胞。其又分为两种类型：初次应 答及二次应答。 1 ) 初次免疫应答( i n i t i a li m r n u n er e s p o n s e ) 初次免疫应答发生在免疫系统遭遇某种病原体第一次入侵时。此时免疫系统 对感染产生大量抗体，帮助清除体内抗体。下图2 6 表明当一种抗原侵入免疫系 统后，系统有一个产生抗击抗原感染的抗体的初始化过程。但是，几天以后，抗 体的浓度水平开始下降，直到再次遇到抗原。自适应免疫系统能够学习和记忆特 异种类的病原体。初次应答是对以前没见过的病原的应答过程。初次应答学习过 程缓慢，发生在初次感染的前几天，要用几周的时间清除感染。 1 4 浙江大学硕士学位论文 抗体 一户 图2 6 免疫应答过程 图2 6 是抗体的浓度水平对一个抗原的免疫应答时间反应周期。对初次遇到 的抗原应答时间可长达几周，而二次应答则对遇到的同样抗原的反应时间非常迅 速。y 轴是免疫应答的强度测量，由抗体浓度表示。 2 ) 二次免疫应答( s e c o n d a r yi m m t m er e s p o n s e ) 在初次免疫应答后，免疫系统首次遭遇异体物质并将其清除体外，但免疫系 统中仍然保留一定数量的b 细胞作为免疫记忆细胞，这使得免疫系统能够在再 次遭遇异体后仍能快速反应并反击抗原，这个过程称为二次免疫应答。二次应答 更迅速，无须重新学习。 在a r t i s 中，免疫的合适形式取决于应用领域。在抽象模型效应器选择中， 假设要求几种不同应答，每一个与不同种类效应器关联。每一个效应器能随一个 确定区域扩大。检测器激活后复制，它们经历一个类似同型特异性转换的过程。 迁移检测器不仅会负载关于异常模式的信息，也负载关于那些异常如何被消除的 特异性信息，这会保持一个类似层次的鲁棒性和灵活性。 2 2 6 记亿性 在免疫系统中基于记忆的检测有一个重要特征一联想性。记忆检测允许免疫 系统检测新病原体，结构上与以前遇到的有关联。这个概念具有免疫化含义，即 用无害形式病原体接种。a 诱导初次应答，产生记忆细胞群体，与有害种类病原 l s 浙江大学硕士学位论文 体b 交叉反应，该记忆细胞群体确保免疫系统对任何b 感染产生再次应答。 a r t i s 模型使用类似的记忆检测形式。当在一个节点的多个检测器被同样非 自体字符串s 激活时，它们进入竞争状态成为记忆检测器。那些与s 具有最近匹 配( 在r 连续位下) 的检测器会被选择成为记忆检测器( 因为匹配是大致的，激 活阂值t 比l 大，有可能最终激活一个检测器的字符串的s 。不同于来自s 1 & i 的某个以前匹配的字符串，因此对激活有作用。假设最终字符串s t 是对激活起 作用的所有字符串的合适表示法) ，该系统以最简单的方式处理这个问题。这些 记忆检测器复制自己，然后散布到临近节点。结果，字符串s 表示法是在整个空 间分散的。在任何节点会迅速地检测到未来s 的出现，因为能匹配s 的检测器存 在于每一个节点。另外，记忆检测器低于激活阕值( 例如，t = 1 ) ，所以它们在未 来比以前遇到的重新出现的非自体字符串能更迅速地被激活，即它们对那些字符 串更敏感，在模拟免疫系统中再次应答。 2 2 7 协同刺激 免疫系统中耐受不是前面描述的那么直接，一个t 细胞必须被第二信号协 同刺激。 不能推测在a r t i s 中一个检测器在其耐受期间内会遇到每一个字符串s e s 。 要粗略实现一种协同刺激形式，理想情况下，第二信号应该由系统的其他元素提 供，但是最接近的是用人工操作提供第二信号当一个检测器d 被字符串s 激活 时，它发送一个信号给操作员( 给定时间周期l 成为协作蒯激延迟) ，在期间决 定s 是否为真非自体。如果操作员决定s 确实是非自体，返回一个第二信号给d ； 如果操作员决定s 是自体，不发信号给d ，d 死亡并被新的未成熟检测器所取代。 结果，一个操作员需要产生不应答以防止错误肯定；系统会自动校正自己，防止 在未来发生类似错误肯定。 2 3 入侵检测系统 2 3 1 基本结构 一个典型的入侵检测系统一般都是由数据采集，数据分析和事件响应三个部 分组成，其基本结构如下图2 7 所示； 1 6 浙江大学硕士学位论文 卜 数 卜 数 卜 事 l 数据 据 数据 据 事件 件 i 。 分 v响y 采 集析 应 图2 7 入侵检测系统的基本结构 入侵检测系统( i d s ) 首先采集来自网络系统不同节点( 不同子网和不同主 机) 中隐藏了网络入侵的数据，例如系统日志，网络数据包，文件与用户活动的 状态和行为。然后，通过模式匹配，异常检测和完整性分析等技术，i d s 对数据 进行分析以寻找出入侵行为。一旦发现入侵，i d s 就进入响应过程，并在日志， 告警和安全控制等方面做出反应。 2