（计算机软件与理论专业论文）基于人工免疫系统的入侵检测技术研究.pdf

摘要 基于人工免疫的入侵检测技术是近年来入侵检测研究领域的热点 它的突出特点是 利用生物免疫系统特征 规则与机制实现对入侵行为的检测和反应 入侵检测系统与免 疫系统具有本质的相似性 免疫系统负责识别生物体的 自我 与 非我 并清除有害 细胞 入侵检测系统则区分正常与异常行为模式 对入侵行为采取措施加以阻止 本文 围绕基于免疫原理的否定选择算法在入侵检测领域的应用展开深入研究 基于否定选择算法的入侵检测与其他入侵检测技术相比虽然具备诸多优越性 但也 有其自身的缺陷 其一是系统中 自我 的描述为静态方式 一旦定义后就不再变化 然而入侵检测技术实际应用中 自我 一方面难以准确定义 另一方面它与 非我 之 间经常角色互换 随着时间的推移需要及时地修正 自我 的描述模型 否则缺乏良好 的适应能力 不能满足真实网络环境下安全监控的需求 其二是产生有效检测器的过程 中 未成熟检测器和自体集合匹配工作量巨大 大规模的数据处理导致否定选择算法时 空效率低下 难以快速发现入侵行为 严重阻碍这一技术在入侵检测中的实际应用 针 对上述问题本文提出根据自体集合动态可变思想实现带有免疫二次应答的入侵检测算 法一用规模较小的 易于程序处理的动态 自我 子集缩小原算法中庞大的自我集合 虽然动态自我集合在短时间内处理数据数量少 覆盖范围小 但可以保证数据被高速处 理 并在相对较长的检测过程中覆盖整个 自我 空间 另外 使用数据结构b l o o mf i l t e r 改变基本否定选择算法中数据的存储 查询和修改方式 缩小数据处理规模 提高查询 速度 使否定选择算法更快速地产生有效检测器 有效地增强该算法的实用性 对比实验证明 本文提出的改进否定选择算法与同类方法相比可以更快速地产生有 效检测器并准确地检测出已知和未知模式的入侵行为 关键词 入侵检测 人工免疫系统 否定选择算法 b l o o mf i l t e r a b s t r a c t i n t r u s i o nd e t e c t i o nb a s e do na r t i f i c i a li m m u n ei saf o c u si ni n t r u s i o nd e t e c t i o nr e s e a r c h f i e l dr e c e n t l y i tr e a l i z e sd e t e c t i o na n dr e a c t i o nt oi n t r u s i o nb e h a v i o r sb yp r i n c i p l e s r u l e sa n d m e c h a n i s m si nb i o l o g i c a li m m u n es y s t e m i ta l s oh a ss i m i l a r i t yw i t hi m m u n es y s t e mi n e s s e n c e i n t r u s i o nd e t e c t i o nd i s t i n g u i s h e sn o r m a la n da b n o r m a lb e h a v i o rp a t t e r n sa n dt a k e s a c t i o n st op r e v e n ti n t r u s i o nb e h a v i o r sw h i l ei m m u n es y s t e mi si nc h a r g eo f r e c o g n i z i n g s e l f a n d n o n s e l f o fo r g a n i s ma n dc l e a r sh a r m f u lc e l l s b 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 m p r o p o s e di ni m m u n o l o g y t h i st o p i cd e v e l o p sf u r t h e rr e s e a r c hi ni n t r u s i o nd e t e c t i o nr e s e a r c h f i e l d c o m p a r e dt oo t h e ri n t r u s i o nd e t e c t i o nt e c h n i q u e s a l t h o u g hn e g a t i v es e l e c t i o na l g o r i t h m h a sl o t so fa d v a n t a g e s i ta l s oh a sd e f e c t s f i r s t l y t h ed a t a b a s ea n ds c a l eo fd a t ap r o c e s s i n g u s e db yi ta r et o oh u g et oh a v eg o o ds p a c e t i m ee f f i c i e n c y s ot h i sa l g o r i t h mc a n tr a p i d l y f i n di n t r u s i o nb e h a v i o r sa n di t s p r a c t i c a la p p l i c a t i o ni ss e r i o u s l yh i n d e r e di ni n t r u s i o n d e t e c t i o nf i e l d n i sp a p e ri n t r o d u c e sad a t as t r u c t u r e b l o o mf i l t e r w h i c hc a r lc h a n g e s t o r a g e e n q u i r ea n dm o d i f i c a t i o nm o d eo fb a s i cn e g a t i v es e l e c t i o na l g o r i t h md a t a r e d u c e s c a l eo fd a t ap r o c e s s i n ga n di m p r o v ee n q u i r es p e e d t h i sd a t as t r u c t u r ee f f e c t i v e l ye n h a n c e s p r a c t i c a l i t yo fn e g a t i v es e l e c t i o na l g o r i t h m s e c o n d l y t h ed e s c r i p t i o no f s e l f a n d n o n s e l f i nt h es y s t e mi ss t a t i ca n ds e l d o mv a r i e sa f t e rd e f i n i t i o n i nc o n c r e t ea p p l i c a t i o n s o nt h eo n e h a n d s e l f a n d n o n s e l f c a n tb ee x a c t l yd e f i n e d o nt h eo t h e rh a n d t h e ya l w a y sc h a n g e r o l e sa n dn e e dt i m e l yr e v i s i o na l o n gw i t ht i m e s od e s c r i p t i o nm o d e lo fs t a t i c s e l f a n d n o n s e l f c a n tm e e tt h en e e do fn e t w o r km o n i t o ri nr e a ln e t w o r ks u r r o u n d i n ga n dl a c k sg o o d a d a p ta b i l i t y i nv i e wo ft h e s ep r o b l e m s t h i sp a p e rr e a l i z e sa ni n t r u s i o nd e t e c t i o na l g o r i t h m w i t hi m m u n es e c o n d a r yr e s p o n s ea c c o r d i n gt oa u t o l o g o u ss e td y n a m i cv a r i a b l ei d e o l o g y a d y n a m i cs e l fw h i c hh a ss m a l ls c a l ea n di se a s yt op r o g r a mp r o c e s si sp r o p o s e dt or e p l a c e h u g ee g os e ti no r i g i n a la l g o r i t h m s a l t h o u g hq u a n t i t ya n dr a n g eo fd a t ai nu n i tt i m ei ss m a l l i nd y n a m i ce g os e t t h i ss e tc a ns t i l lb er a p i d l yp r o c e s s e db yp r o g r a m sa n dc o v e rt h ew h o l e s e l fs p a c ei nar e l a t i v e l yl o n gd e t e c t i n gp r o c e d u r ei nt h ee n d c o n t r a s te x p e r i m e n t sp r o v et h a tn 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 di nt h i sp a p e rc a n r a p i d l ya n da c c u r a t e l yd e t e c tk n o w na n du n k n o w np a g e m so fi n t r u s i o nb e h a v i o r s t h i s a l g o r i t h ma c c o r d sw e l lw i t hr e q u i r e m e n to fi n t r u s i o n d e t e c t i o nt e c h n i q u e k e yw o r d s i n t r u s i o nd e t e c t i o n a r t i f i c i a li m m u n es y s t e m n e g a t i v es e l e c t i o na l g o r i t h m b l o o mf i l t e r 独创性声明 本人郑重声明 所提交的学位论文是本人在导师指导下独立进行研究工作 所取得的成果 据我所知 除了特i i i i i 以标注和致谢的地方外 论文中不包含 其他人已经发表或撰写过的研究成果 对本人的研究做出重要贡献的个人和集 体 均已在文中作了明确的说明 本声明的法律结果由本人承担 学位论文作者签名 驻堕 日期 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留 使用学位论文的规定 即 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 电子版 允许论文被查阅和借阅 本人授权东北师范大学可以将学位论文的全 部或部分内容编入有关数据库进行检索 可以采用影印 缩印或其它复制手段 保存 汇编本学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 芝垒堑q 日 期 逊 笸乡 学位论文作者毕业后去向 工作单位 通讯地址 指导教师签名 望望堕 日 期 之竺盟奎 虽 旦 电话 邮编 东北师范大学硕士学位论文 第一章引言 1 1 选题背景及意义 计算机信息系统的保密性 完整性以及可用性对用户来说是至关重要的f 业务需 求促使计算机互联网技术飞速发展 企业和政府在全球各地不断开发先进的 复杂的信 息网络 这些网络纳入了各种各样的技术 包括分布式数据存储系统 加密和认证技术 i p 上的语音和视频 远程无线接入和网络服务 以往单机为主的工作模式逐渐被多终端 网络化的协同作业模式所取代 借助计算机网络环境 实现了包括电子银行 电子商务 电子政务 企业资源管理和网络虚拟社区等多种应用 在金融 军事 教育等领域中使 用的计算机每天都要交换 处理大规模的数据 此外 由于企业网络更容易访问 如大 多数企业允许合作伙伴通过外部网络进入其内部服务网络 使客户能够通过电子商务交 易与网络互动 并且允许员工通过虚拟私人网络进入公司系统 开放的信息系统给窃取 盗用 非法修改以及各种破坏信息的方式提供了可乘之机 信息在存储 处理和传输等 各个环节 都有可能遭到入侵者的攻击 2 0 0 5 年由计算机安全学会和美国联邦调查局联合进行的计算机犯罪和安全调查表 刃 由网络攻击 入侵原告公司的计算机系统造成的损失达1 3 亿美元 2 在另一项2 0 0 3 军委托v a nd y k e 软件公司的调查中 大约6 6 的公司表示计算机系统的高度普及是对 也们企业最大的威胁 3 此外 根据最近的研究在常用的网络和计算机产品中平均每月 会友现2 0 到4 0 个安全漏洞 4 j 广泛的软件漏洞增加了计算机 网络环境的不安全性 既有的防火墙和各种计算机安全工具只能应对已知的攻击模式 也就是说只有在一种攻 击已经造成损失的前提下才能应对该攻击 这种情况在很多行业尤其是高新产业的信息 系统中是不能容忍的 信息安全技术的研究方向迫切地需要从静态到动态 从被动防范 副主动防御的转变 入侵检测技术正是顺应这样的变化而出现 入侵检测理论上能够实 时甚至提前发现已知和未知模式的攻击行为并在第一时间对攻击企图做出回应 由于入 侵检测技术所特有的前瞻性 引发了大量国内外学者投身这项研究工作 信息化社会扑 面而来 信息系统的安全问题已经被提升到战略高度 为保障祖国现代化建设避免由信 息系统遭受攻击而引发大量的 不必要的人力物力损失 自主研究开发可靠的 高效的 入侵检测产品迫在眉睫 h e a d y 将入侵检测定义为 发现未经授权蓄意尝试访问信息 篡改信息 使系统不 可靠或不能使用的企图和行为 5 1 入侵检测技术是一种动态地预防 监控 抵御对计算 机信息系统入侵行为的安全机制 入侵检测技术主要通过监控网络传输 系统状态 程 序行为等计算机系信息系统使用情况来检测系统内部用户的越权使用和系统外部的入 侵者利用系统的安全缺陷对系统进行入侵的企图 入侵检测技术和传统的计算机信息系 东北师范大学硕士学位论文 统安全机制相比具有智能监控 实时探测 动态响应 易于配置的特点 一个好的入侵 检测系统应该是鲁棒的 可配置的 可扩展和高效的 免疫系统具有的分布式 自组织 和轻量级特性满足入侵检测的要求 因此人工免疫应用于入侵检测技术有着得天独厚的 优势 1 2 入侵检测技术发展和国内外研究现状 学术界开展入侵检测技术相关研究已经有2 0 余年的历史 近年来入侵检测技术更 是从理论研究转变为一个切实可用的商业系统被计算机信息系统管理者所接受 逐渐成 为计算机安全防护体系中不可或缺的技术产品 从2 0 世纪8 0 年代开始 j a m e s a n d e r s o n 主持的一项由美国政府支持的关于计算机 信息系统安全的研究计划 6 被认为是入侵检测技术研究的开端 这项计划的研究成果包 括了 套重要的计算机安全评估标准即t c s e c 可信计算机系统评估准则 t c s e c 首 次定义了计算机信息系统安全等级评估标准 并给出了各个安全等级的计算机系统所应 该满足的各方面需求 为入侵检测技术明确了任务和目标 j a m e s a n d e r s o n 在随后的文 献中指出可以通过比较系统日志 发现偏离历史正常行为 入侵行为 的活动 这一思 路成为了以后入侵检测技术研究的指导思想用 1 9 8 7 年d o r o t h yd e n n i n g 发表了入侵检 测领域内的经典论文n 文中对入侵检测问题进行了深入探讨 建立入侵检测技术的基 本理论框架见图1 1 并提出两种基于统计方法的应用于入侵检测技术的数学模型 在 图1 1 入侵检测技术理论框架 仿真实验中验证了这些模型的有效性 以后所出现的大部分入侵检测技术都可抽象为 d e n n i n g 所提出的入侵检测系统通用模型 一段时间后s t e p h e ns m a h a 为美国空军内部 2 东北师范大学硕士学位论文 网络开发h a y s t a c k 入侵检测系统 该系统采用离线的批处理数据方式 实现d e n n i n g 提 出的两种统计分析数学模型 8 1 使入侵检测技术向实际应用又迈出了重要的一步 1 9 9 0 年t o d d 在i e e e 上发表论文 提出以网络数据包作为入侵检测技术的数据源 9 1 他的工作 为针对网络的入侵检测技术奠定了基础 1 9 9 7 年c i s c o 公司决定将入侵检测技术嵌入到 他们生产的路由器中 同年i s s 公司发布基于w i n d o w s 平台的r e a ls e c u r e 入侵检测应 用程序 从此入侵检测技术进入商用阶段 近年来国内外关于入侵检测技术的研究提出许多更为复杂同时也比前人方法更为 有效的理论模型或改进算法 现有入侵检测技术从数据分析手段看 可以分为异常入侵 检测和与之对应的误用入侵检测 1 0 因为误用检测的原理是基于攻击手段或者攻击特征 库建立攻击行为模型 只能检测已知攻击模式对未知攻击无能为力 所以相关工作比较 少 而异常入侵检测技术是建立一个关于计算机信息系统的正常行为模型并不断对其进 行更新 将计算机系统当前的活动情况与这个正常模型进行对比 如果发现当前系统特 征偏离正常特征的变量超过设定的阈值 则认为发现入侵行为 l l 异常入侵检测技术的 检测能力可以覆盖未知攻击模式 所以异常入侵检测技术相关研究最为活跃 实验也最 多 美国大学如c a r n e g i em e l l o n p u r d u e c o l u m b i a u cd a v i s g at e c h n e wm e x i c o 等都开展了异常检测技术的研究 a n i m e s hp a t c h a 4 所著入侵检测技术综述 刀中提出将现有异常检测技术分为以下三 类 基于统计的异常检测技术 这类异常检测技术基于统计方法提出 入侵检测系统观 察受保护系统活动并描述出他们的行为轮廓 行为轮廓通常包括活动强度值 审计记录 分布值 分布值 活动按类别分布 和有序值 如c p u 内存使用率等 等统计数据 入侵检测系统更新当前的行为轮廓 把当前轮廓与已存储的正常轮廓相比较 通过对比 轮廓中所有测量值的异常函数来周期性地计算异常值 表明某一具体行为的不合法程 度 如果异常值高于入侵行为判定阈值 入侵检测系统产生警报 h a y s t a c k 1 是基于统 计异常的最早的入侵检测系统之 它使用用户和基于组的异常检测策略 把系统参数 模拟成独立的高斯随机变量为每一个特性定义了一系列被认为正常的值 在某个阶段如 果某一特征值在正常范围之外 这一主体的值会上升 假设这些特性是独立的 值的概 率分布可以被计算出来 如果某个值过大就会报警 h a y s t a c k 维护一个用户组和个人轮 廓的数据库 如果一个用户以前没被检测过系统就会使用基于用户组成员的限制 创建 一个最小容量的新用户轮廓 h a y s t a c k 的缺点是它设计为离线检测 实时入侵检测系统 使用统计异常的尝试失败了 因为这要求高性能的系统 另外h a y s t a c k 依赖于维护个人 轮廓 而系统管理员常常不能确定哪些属性能更好的表征入侵行为 另一个较早的入侵 检测系统在2 0 世纪8 0 年代初由斯坦福研究所开发 称为入侵检测专家系统 i d e s 0 2 i d e s 是一种不断监视用户行为并在用户行为发生时检测可疑事件的系统 在i d e s 中 入侵可以通过检测与建立的个人用户正常行为模式的偏离度被标记出来 由于i d e s 研 究的分析方法论已经成熟 斯坦福研究所的科学家又开发了i d e s 的改进版本 被称为 下一代入侵检测专家系统 n i d e s 1 3 n i d e s 是同期入侵检测系统中能在实时系统上 1 东北师范大学硕士学位论文 操作 持续监视用户行为 或者以批处理模式进行定期分析审计数据的极少数入侵检测 系统之一 基于统计方法的异常检测技术的后续工作还有s t a n i f o r d 1 4 j 的基于网络的统计 异常检测和y e 等人 1 5 的基于主机的多元统计异常检测等等 基于统计方法的异常检测 技术优点在于它不需要事先知道安全漏洞或攻击模式 缺点在于有经验的攻击者可以训 练基于统计方法的异常检测系统 让一类攻击行为经过简单变化后长期存在于计算机 内 在一段时间后异常行为会当作正常行为被接受 入侵检测系统不再报警 这样就使 得平衡误报和漏报可能性的阈值很难确定 另外 统计方法需要精确的统计分布 但不 是所有的行为都可以使用统计方法为其构建特征模型 基于机器学习的异常检测检测技术 机器学习可以被定义为程序或系统随着时间的 推移学习和改进执行某一任务或一类任务性能的能力 机器学习的目标是回答和统计数 据一样的问题 和统计方法不同的是统计方法趋向于对数据形成过程的理解 而机器学 习技术侧重建立一个系统 在先前结果的基础上改进它的性能 换句话说 基于机器学 习模型的系统 具有根据新获得的信息改变其执行策略的能力 用于异常检测的机器学 习技术包括学习程序行为并识别严重偏离正常 入侵 的行为 在开创性的论文中f o r r e s t 等人 1 6 在生物免疫系统和入侵检测之间建立了联系 提出一个通过分析程序的系统调用 序列来创建正常信息轮廓的方法论 在他们的论文里分析了几个基于u n i x 的程序例如 s m t p l p r 等 程序被认为是攻击的受害者 如果它里面的序列与正常信息里的序列相 偏离则认为发现入侵 这个系统只能用于离线状态 使用先前收集的数据和一个相当简 单的表查找算法来获得程序的信息 f o r r e s t 等人的研究被h o f m e y r 1 7 扩展为每个程序创 建正常行为数据库 当特定环境中的某一特定程序的稳定数据库被建立之后 数据库就 用于监视程序的行为 w a r r e n d e r 等人f 1 8 提出另一种在机器学习领域内频繁使用的方法 滑动窗口应用于入侵检测 把顺序学习问题转换成经典学习问题 构建一个窗口分类k 描绘一个宽度为w 的输出窗口得到输出值y d 似 i 2 作为窗口值的一半 k 使用 阢m 黾 计 而加 黾 d x i 一预测儿 窗口分类 通过把每一个有序训练例子o 转 换成窗口值然后应用一个标准机器学习算法进行训练 通过转换成窗口值得到新的x 分 类序列 应用 预测每一个 然后串连y t 序列形成被预测的y 序列 滑动窗口方法在 很多基于机器学习的异常检测技术中成功使用 e s k i n 等人 1 9 1 改进了传统的滑动窗口方 法 他们提出一个建模方法论 使用依赖于系统调用序列上下文的滑动窗口动态长度 基于系统调用的方法对于主机入侵检测系统来说有两个缺点 第一 监视每一个系统调 用的开销很高 这种高开销导致监视系统的性能下降 第二 系统调用本身是无规则的 这种无规则使得区分正常和异常的系统调用非常困难导致较高的误报率 基于机器学习 的异常检测技术还有v a l d e s 等人 2 0 2 1 提出的基于贝叶斯网络来判断突发流量中是否包 含攻击 s h v u 瞄 2 3 1 等人提出的离群检测方案减少了审计数据的维数并得到主成分函数的 分类器 y e 等人 2 4 2 5 提出使用马尔可夫链描述系统调用序列的状态转移概率 基于数据挖掘的异常检测技术 为了在建立一个入侵检测系统的过程中消除人工干 预和自组要素 研究人员越来越多地利用数据挖掘技术进行异常检测 简单地说数据挖 掘就是把数据作为输入并从模式或偏离中分离出来的能力 这是不能通过简单的观察与 4 东北师范大学硕士学位论文 统计实现的 数据挖掘可以通过在异常检测技术中增加一层来改进入侵检测过程 帮助 计算机系统管理员从网络的普通日常流量中发现攻击行为 l e e 等人 2 6 2 7 1 提出的基于 分类的入侵检测技术根据规则集合把审计数据划分为正常和不正常 相关技术大分为四 个步骤 识别等级属性和培训数据等级 识别属性分类 使用训练数据学习一个模型 使用学习的模型为未知数据样本分类 分类方法包括归纳规则生成技术 模糊逻辑 遗 传算法和基于神经网络的技术 s e q u e i r a 等人 2 8 2 9 又将集群引入入侵检测研究 优点主 要是具有从审计数据中学习并检测入侵的能力 不需要系统管理员提供各种攻击类型的 特征描述 因此向异常检测系统提供的训练数据也减少了 集群和离群检测密切相关 从集群算法的观点来看 离群是对象没在数据集聚集的范围之内 在异常检测中他们可 能代表入侵 攻击 基于集群的异常检测方法有两种 第一种方法中 异常检测模型 使用既包括正常数据也包括异常数据的未标记数据训练 第二种方法 模型只使用正常 数据训练并建立一个正常行为的轮廓 第一种方法是源于异常数据占总数据很小的比例 的假设 如果这一假设成立 异常可根据聚簇大小来检测 大集群对应正常数据 其余 的离群数据点对应攻击数据 除上述方法外基于数据挖掘的入侵检测技术还有b a r b a r a 等人f 3 0 3 i 提出的关联规则方法 给出一个事务数据库d 其中每一个事务rd 指示数 据库里的一组条目 一个关联规则是隐含的j b 的形式 其中北d y c d 并且朋y 历 规则x jy 在事务集合d 中带有置信度c 奶r 杲x y 历埘 踟髟在 事务 励期 事是c 纸 当处理关联规则时两个很重要的概念是规则置信度和规则支持度 规则置信度的概率被 定义为条件概率尸仃 r i j v c 刀 豇噪刃乒事务自括x u y 的可能7 笙是跳 那么事务数据 库d 中规则x j 的支持是s 关联规则已经被成功用于挖掘审计数据来找到合适的异 常检测样式 它们在异常检测领域中尤其重要 因为关联规则可用于构建入侵检测系统 的异常连接概况检测 程序执行和用户活动展现出与系统特性韵频率相关 这种一贯行 为可以被关联规则捕获 基于免疫学的入侵检测技术是近几年来入侵检测领域的研究热点 目前国内外均有 大量学者针对这一领域开展了深入的 富有成效的研究工作 它的理论基础 人工免 疫系统已经发展成为应用仿生学的一个重要分支 在自动控制 机器人 优化问题等方 面取得了广泛的成果 基于免疫学的入侵检测技术突出特点是模仿生物免疫系统的工作 原理来实现对入侵行为的发现和处理 这种方法充分体现了免疫机制的学习 认知 自 适应等特性具有较高的可靠性并且可以检测未知的入侵行为 使应对入侵行为的过程变 被动为主动 具有重大理论研究意义和实际应用价值 f o r r e s t 提出的否定选择算法及相 关的后续研究包括克隆选择 3 2 和厂 连续位 3 3 垮一些检测器生成算法 试图提高有效检测 器生成效率 国内有李涛 3 4 1 提出的自体集合动态可变思想来减少有效检测器产生过程中 匹配次数 降低计算规模 何 3 5 1 提出的检测器长度可变思想从减少检测器匹配数量入 手 达到提高有效检测器产生效率的目的 其他研究 3 6 3 8 1 从减少检测器数量的角度入手 以提高系统效率 东北师范大学硕士学位论文 1 3 研究内容 本文对基于免疫学的入侵检测技术进行了深入研究分析 从改进否定选择算法的数 据存储结构和提高检测器产生效率入手 使改进后的否定选择算法在具有更快的检测速 度前提下保持较好的检测率 提高基于人工免疫系统入侵检测技术的实用性 论文共分 六章 第一章引言 介绍了本论文的选题背景和意义 国内外研究现状和进展 本文的主 要研究内容 第二章基于免疫原理的入侵检测系统 介绍了基于免疫原理的入侵检测系统实现的 基本原理 第三章自体集合可变的否定选择算法 阐述如何利用自体集合动态可变思想 实现 了带有二次应答的入侵检测算法 第四章基于b l o o mf i l t e r 的否定选择算法 在国内外相关的有效检测器生成研究基 础之上 提出了一种基于b l o o mf i l t e r 的检测器生成算法 提高数据库处理效率 在保 证检测率的前提下加快有效检测器产生速度 第五章仿真实验 对本文所提出算法的实验数据进行对比分析 证明其有效性 第六章总结与展望 在最后一章回顾本文所做的工作 并指出尚未解决的问题及今 后工作的方向 6 东北师范大学硕士学位论文 第二章基于免疫原理的入侵检测系统 由于入侵检测系统的组织结构与生物免疫系统具有高度的相似性 模拟生物学免疫 系统的免疫过程构建计算系统并将之应用于入侵检测领域的相关研究得到广泛的关注 2 1 生物免疫系统概述 2 1 1 免疫识别 在生物免疫系统中 淋巴细胞表面的抗原识别受体并绑定病原体的抗原决定基 就 会产生检测事件 受体和抗原决定基的结构是互补的 如图2 1 所示 受体和抗原决定 基之间的绑定能力称作亲和力 一般情况下受体是有针对性的 因为他们只能够绑定一 图2 1 生物免疫识别模型 结构互补 高亲和力 低亲和力 部分类似的抗原决定基 这种专用型可以推广到淋巴细胞本身 不同的淋巴细胞上的受 体可以互不相同 而在同一个淋巴细胞上的所有受体都是相同的 淋巴细胞只能对具有 类似抗原决定基结构集合起作用 病原体则可以有多个不同的抗原决定基 因此一种病 原体可以绑定多种不同的淋巴细胞 淋巴细胞表面上的受体个数可达1 0 5 数量级 所有 这些受体都能够绑定抗原决定基 淋巴细胞的行为由亲和力决定 当绑定受体超过某个 阈值时 淋巴细胞被激活 此时定义为发生了一个检测事件 这个阈值被称作亲和力阈 值 淋巴细胞只有当其受体与病原体的特殊抗原决定基具有高亲和力时才被激活 而且 要求淋巴细胞周围具有足够多的病原体 这种激活方式允许淋巴细胞作为通用检测器 单个淋巴细胞能够检测这些模式中的某个子集称作子集相似性 这就要求存在特殊的淋 巴细胞如免疫记忆细胞具有比其他淋巴细胞更低的激活阈值 只需要绑定较少的受体就 7 东北师范大学硕士学位论文 能够激活 随着亲和力阈值上升 能够激活淋巴细胞的抗原决定基减少 也就是相似性 子集变小 所以免疫系统的绑定是近似的 采用近似绑定是因为免疫系统很难为每个出 现的抗原决定基发生精确互补的受体结构 如果采用精确绑定随机淋巴细胞绑定随机抗 原决定基的机会大大减小 采用近似绑定的好处就是一个淋巴细胞能够检测抗原决定基 的一个子集 免疫系统只需要为数不多的淋巴细胞就能够检测出绝大多数可能的抗原决 定基 基于免疫学的入侵检测技术使用的检测原理 其检测器也应该采用近似的检测规 则 使用少量的检测器来确定更多具有相似性的入侵行为 2 1 2 受体多样性 免疫学中将生物体可能遇到的所有外来病原体归类为 非我 n o n s e l f 免疫系统 通过绑定非我来进行检测 为了保证每种病原体都有一定数目的淋巴细胞与之进行绑 定 免疫系统必须具备淋巴细胞受体的多样性 产生大量多样的受体库是必要的 因为 生物体所能够产生的基因远远少于病原体抗原决定基 实现受体多样性的常见方式是采 用随机过程 在不同基因库中选取d n a 进行随机组合 构成不同的淋巴细胞基因生成 不同的受体 免疫系统具有的基因序列为1 0 6 数量级 需要识别的基因模式则高达1 0 1 6 种 使用这种方法可以产生1 0 b 种不同受体 由于生物体内受体数目远远小于病原体抗 原决定基 因此淋巴细胞受体不具备足够的多样性来绑定所有可能的病原体 这将导致 某些未知的病原体不能够被检测出来 免疫系统采用 动态化 解决上述问题 也就是 保证淋巴细胞的持续更新 每天有1 0 7 个新的淋巴细胞生成并替换已有的细胞 假设生 物体内有1 0 8 种不同的淋巴细胞 每天更新1 0 7 个 只需要1 0 天就可以产生一个全新的 淋巴细胞集 在实现基于免疫学的入侵检测技术中 检测器也要定期更新 保持有效检 测器的多样性以确保覆盖整个检测范围 2 1 3 免疫耐受 由于生物免疫系统内所有受体都是随机生成的 并且在体细胞高突变过程中发生不 可预料的变化 所以受体有可能绑定自我 从而导致自体免疫 对自身构成威胁 正常 的免疫系统经过耐受过程可以识别自我 不会攻击自身 免疫耐受由一种t 细胞完成 负责辅助b 细胞完成免疫应答 t 细胞在胸腺中成熟 胸腺含有绝大多数s e l f 抗原决定 基而被激活 它就会在否定选择过程中被挑选出来 并自动死亡 最后离开胸腺的t 细 胞肯定能够耐受绝大多数s e l f 抗原决定基 不同免疫细胞的专门化使得免疫系统能够进 行快速的 高度适应性的 非自身反应的免疫应答 t 细胞负责自身耐受 使得b 细胞 能够进行突变 迅速适应特殊类型的病原体 这两种淋巴细胞都是缺一不可的 t 细胞 是通用的 非专门化的监测器 因而在检测特殊类型病原体时效率不高 相反b 细胞能 够适应病原体而变得专门化 在处理特殊类型的病原体时具有很高的效率 根据研究 b 细胞检测特殊病原体的效率比t 细胞搞1 0 到1 0 0 0 0 倍 基于免疫学的入侵检测技术 在生成未成熟检测器集合时要经受自我集合的耐受过程 检测过程中 普通检测器发现 异常行为后 有时需要得到人工操作进行确认 人工操作确认做为协同刺激 3 东北师范大学硕士学位论文 2 1 4 二次应答 病原体会以指数级速率繁殖自身 免疫系统必须尽可能快地识别出并消除它们 淋 巴细胞越具有通用性 它对特殊类别的病原体检测能力就越差 消除病原体的效率越低 下 针对上述情况免疫系统包含了一种机制 使得淋巴细胞能够学习并适应特殊外部蛋 白质 淋巴细胞能够记忆这些蛋白质结构 以加速将来的免疫反应 这种机制由b 细胞 实现 当b 细胞被激活后 通过细胞分裂不断地克隆自身 克隆的速率比正常细胞发育 速率高9 个数量级 这个过程称为体细胞高度突变 突变产生的b 细胞自身也有很高的 几率绑定病原体并克隆自身 这就行程了达尔文所说的变异和选择过程 对于已有的病 原体 b 细胞间进行竞争 具有最高亲和力的b 细胞被选中 并大规模克隆复制自身 淋巴细胞的亲和力越高 就越能有效地捕获特定病原体 感染也就越容易消除 当免疫 系统遭遇变种的病原体时 这种特性尤其有效 实质上就是病原体和b 细胞繁殖的竞争 经过一次成功的免疫反应之后 与引起免疫反应的外部病原体亲和力超过阈值的b 细胞 就会增殖 保留这些b 细胞中的排序信息就构成了免疫系统的记忆能力 如果再遭遇到 相同的病原体 已适应的b 细胞群体就能够执行高效而快速的免疫反应 其响应速度远 远超过初次免疫应答 入侵检测技术所使用检测器 也应该具有这种特性 以应对频繁 出现的变种攻击模式 在入侵检测过程中 除了间断出现新的攻击模式更多的是曾经出 现过的已知攻击模式的变种 由于入侵检测系统中的检测器需要保持一个较小规模并随 着时间推移不断更新 那些可以检测已出现攻击模式的检测器将在生命周期结束后被杀 死 当可以检测已知攻击模式的检测器生命周期结束 旧的攻击模式对于检测器频繁更 换的入侵检测系统来说仍然是新的攻击模式 这样会造成入侵检测系统效率低下不能在 最快的时间内发现攻击做出反应 因此在实现基于免疫学的入侵检测技术中也必须保留 一部分有效的检测器赋予其较长的生命周期 曾经出现过的攻击模式再次出现时快速地 报警并对其进行处理 2 2 入侵检测系统与生物免疫系统的相似性 2 2 1 生物免疫系统特征 生物免疫系统的特征是建立基于免疫原理的入侵检测系统的主要理论依据 这些 主要特征包括 1 识别能力 生物免疫系统能够正确识别和分类大量不同的基因组合方式 包 括生物体自身与外来物质 并采取响应措施 2 学习能力 生物免疫系统具有学习外部抗原的能力 通过与免疫网络的交互 作用 免疫系统可以看作一个学习机制 产生相应的抗体适应入侵抗原 并 最终清除抗原 3 记忆能力 生物免疫系统能够记忆曾经出现过的抗原 触发记忆免疫以功能 可大幅提高对某些抗原的应答速率 4 分布式检测 生物免疫系统具有内在的分布式特征 系统不需要统一的控制 9 东北师范大学硕士学位论文 结点 每个淋巴细胞被特定的抗原激活并采取反映措施 免疫系统具有较高 的容错能力 能够克服集中式与层次式系统的缺点 既系统关键结点的崩溃 会导致系统无法工作 5 自组织性 自组织是指系统根据输入动态改变内部结构的能力 在免疫系统 中 根据入侵抗原调整免疫细胞的构成 最终清除外部抗原 免疫系统的这 个特性适合于应用在无监督学习领域 解决大规模数据中的模式发现和分类 问题 2 2 2 入侵检测系统与生物免疫系统的相似性 计算机信息系统遭遇的对系统保密性 完整性和可用性的侵犯 可能由内部用户滥 用权限或由系统外部的入侵者利用系统自身的缺陷和漏洞所造成 生物体的免疫系统能 够识别并消除绝大多数的病原体 当病原体进入生物体内部后 他们就会遇到固有性免 疫系统和适应性免疫系统 固有性免疫系统主要起吞噬细胞核病原体的作用 负责清除 体内残骸和病原体 适应性免疫系统能够学习识别特殊种类的病原体 并保持记忆 从 而加速未来的免疫应答过程 适应性免疫系统包括多种类型的白细胞 称为淋巴细胞 淋巴细胞分为两类 b 细胞和t 细胞 成熟b 细胞来源于骨髓 成熟t 细胞来源于胸 腺 淋巴细胞可以看作检测装置 随着血液和淋巴系统在生物体内循环 在病原体入侵 时 进行免疫应答 免疫系统没有层次结构 众多检测器通过简单的规则相互联系 共 同检测和清除抗原 保证生物体可以存活 b r a d l e y 等人在基于免疫学的入侵检测技术 研究中 比较了入侵检测系统与生物免疫系统的相似性见表2 1 证明了模拟生物体免 疫过程可以构造出可行的入侵检测系统 3 9 1 一个好的入侵检测系统应该是具有较强的健 壮性 可配置的 可扩展和高效的 免疫系统所具有的分布式 自组织和轻量级特征正 好满足了入侵检测系统的要求 因此免疫学在入侵检测检测技术中的应用具有先天性优 势 表2 1 入侵检测系统与生物免疫系统的相似性 入侵检测系统特征生物免疫系统特征 分布式 自组织 轻量级 免疫网络 单 抗体集合 基因库进化 否定选择 克隆选择 非精确匹配 记忆细胞 基因表示 l o 东北师范大学硕士学位论文 2 2 3 基于免疫原理的入侵检测系统特征 模仿生物免疫系统构造的入侵检测系统实际上就是一种人工免疫系统 人工免疫具 有生物免疫系统的全部优良特性和许多显著的信息处理能力 包括模式识别 学习 记 忆和内在的分布式并行处理等 这说明二者之间具有本质的共性 1 分布式检测 人工免疫系统的检测器与记忆系统都是高度分布式的 没有中 心控制结点 也不具有复杂的层次结构 这样就避免了由于主控结点被入侵 而导致整个系统崩溃 入侵检测系统的结构有集中式 层次式和分布式三种 从鲁棒性角度来看 分布式结构具有最高的可靠性 2 检测器的独立性 人工免疫系统中的检测器可用不同的方式实现 其数据源 检测方法与数据结构可以互不相同 类似地计算机信息系统中各个终端的入 侵检测系统也应该是相互独立的 即使其中某些检测器失效或发生错误也不 会影响其他检测器的检测能力 3 对新模式的检测能力 对于入侵检测系统来说 新的入侵手段不断出现 必 须具有检测未知攻击模式的能力 生物体免疫系统能够检测新类型的抗原和 病毒 这样就能保证生物体可以适应新的环境存活下去 人工免疫系统也拥 有这一特性 4 非完备的检测 并不是所有的抗原都能够立即被生物体的免疫系统检测出并 消灭 免疫系统借助免疫学习来解决这个问题 借助二次免疫应答能够逐渐 学习并使检测范围趋向完备 一个入侵检测系统也不可能检测出所有的入侵 模式 人工免疫系统选择适合的学习方式 不断地根据应用环境进行动态调 整 使得使检测范围趋向完备 东北师范大学硕士学位论文 第三章自体集合可变的否定选择算法 现有免疫算法有否定选择算法 克隆选择算法 免疫网络进化算法三种 当生物体 在产生t 细胞时 首先随机的重组基因序列 生成t 细胞表面的受体 所有这些受体会 在胸腺中经历否定选择过程 能够与生物体自身配细胞对的t 细胞被清除 那些与生物 体自身细胞不能够配对的t 细胞才能够离开胸腺 循环到生物体各个部分 执行免疫过 程 模拟这一流程的免疫算法称之为否定选择算法 首先随机地产生未成熟检测器 然 后在经历否定选择后只保留了那些与 自我 特征不同的 非我 用于入侵检测 本文 主要研究基于否定选择算法的入侵检测系统 3 1 基本否定选择算法 f o r r e s t 等人的工作 1 9 最早提出将免疫学知识应用于入侵检测技术 给出了入侵检测 系统中的否定选择的基本流程 如图3 1 所示 图3 1 基本否定选择算法流程图 1 将自我个体和检测器个体的长度均设为三 首先随机生成长度为三的待确认 检测器 与自我集合内所有个体按照匹配规则进行匹配 若匹配成功 说明生 成的待确认检测器是 自我 将其删除 否则送入有效检测器集合 2 重复以上过程 直到产生一定数量的有效检测器 3 有效检测器用于匹配受保护系统中提取的待检测串 若匹配则表明发生了异 常变化 这里的匹配通常是部分匹配规则 一个检测器很可能可以匹配非我 1 2 东北师范大学硕士学位论文 空间中的多个点或区域 因此能够被检测器匹配的点或区域称为被检测器所 覆盖 3 2 算法的约束及相关定义 假设入侵检测系统定义于 个全集u 上 u 是一个有限符号表上的字符串集合 集 合有限符号表的大小为 u 集合的所有元素均是长度为 的字符串 u 被划分为 自 我 集台s 和 非我 集合 两部分 自我 集合s 代表被保护的数据或活动 非我 集合 代表异常变化 即不可接受的或非法的数据或括动 在本文算法中t 需满足以下 约束条件 约束lu 是封闭和有限的 对于给定的问题域 以定长的字符串作为问题表达的 基本单位