（信号与信息处理专业论文）基于遗传算法的入侵检测研究.pdf

浙江工业大学硕士学位论文 基于遗传算法的入侵检测研究 摘要 随着计算机网络技术的发展和网络系统的膨胀，敏感数据正面临 着被黑客攻击的威胁。对于网络来说入侵是很常见的威胁，而且攻击 者的创造力不断提高，开发个有效的入侵检测系统( i d s ，i n t r u s i o n d e t e c t i o ns y s t e m ) 正成为巨大挑战。解决该问题的常用方法是开发一 个基于规则库的专家系统，但需要付出高昂的维护费用。由此导致了 下一代入侵检测系统的发展，即使用人工智能技术来检测入侵，如人 工神经网络、逻辑树、遗传算法、模糊逻辑和数据挖掘。事实表明基 于这些技术的攻击类型知识库减少了i d s 的计算成本。在这些方法中， 进化搜索技术如遗传算法，有能力区分网络流量中的异常模式。本论 文描述了用微遗传算法( m g a ，m i c r og e n e t i ca l g o r i t h m ) 构建的一个 入侵过滤器，该过滤器用多重故障诊断的办法检测入侵攻击的子集。 从我们的初步分析结果来看，该过滤器对拒绝服务类( d o s ， d e n i a l o f - s e r v i c e ) 攻击的子集检测是非常成功的。该过滤器是我们正 在研究的智能入侵检测系统的重要组成部分。 当然，遗传算法等相关学科应用到入侵检测系统中，使其具有智 能性，这些还处于研究阶段，入侵检测系统还有更多的方面需要人们 去做更多的努力。作者相信，在大家的努力下，入侵检测系统定会 像现在的防火墙，走进千家万户。 浙江工业大学硕士学位论文 关键字：网络安全，入侵检测，过滤器，遗传算法( g a ) 浙江工业大学硕士学位论文 ag ab a s e di n t r u s i o nd e t e c t i o nr e s e a r c h a b s t r a c t w i t ht h ed e v e l o p m e n to f n e w t e c h n o l o g i e sa n dt h ee x p a n s i o no f n e t w o r k e dc o m p u t e rs y s t e m s ，s e n s i t i v ed a t aa r eu n d e rc o n s t a n tt h r e a to f a t t a c kf r o mh a c k e r s i n t r u s i o ni sav e r yc o m m o nt h r e a tt oan e t w o r ka n d w i t ht h ei n c r e a s i n gc r e a t i v i t yo fa t t a c k e r s ，t h ed e v e l o p m e n to fa ne f f e c t i v e 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 ) i sb e c o m i n gag r e a t e rc h a l l e n g e ap r i o r a p p r o a c ht ot h i sp r o b l e mh a sb e e nt od e v e l o pa r u l eb a s e d s y s t e m ，b u ti t h a s p r o v e nt ob eu n s a t i s f a c t o r yo w i n gt oi t sh i g hm a i n t e n a n c ec o s t t h i s h a sr e s u l t e di nt h ed e v e l o p m e n to f n e x tg e n e r a t i o ni n t r u s i o nd e t e c t i o n s y s t e m s ，w h i c hu s eo t h e ra r t i f i c i a li n t e l l i g e n c et e c h n i q u e ss u c ha s a r t i f i c i a ln e u r a ln e t w o r k s ，l o g i ct r e e s ，g e n e t i c a l g o r i t h m s ，f u z z yl o g i c a n dd a t am i n i n gt od e t e c ti n t r u s i o n s i th a sb e e ns h o w nt h a tk n o w l e d g eo f t h et y p eo f a t t a c kr e d u c e st h ec o m p u t a t i o n a lo v e r h e a do f t h ei d s a m o n g o t h e rm e t h o d s ，t h ee v o l u t i o n a r ys e a r c ht e c h n i q u e ss u c ha sg e n e t i c a l g o r i t h m sh a v et h ec a p a c i t yt od i s t i n g u i s ha n o m a l o u sp a t t e r n si nn e t w o r k t r a f f i c t h i sp a p e rd e s c r i b e san e t w o r kf i l t e ru s i n gad i s t r i b u t e dt y p e m i c r o - - g e n e t i ca l g o r i t h mm o d e l e da f t e rt h em u l t i p l e - - f a u l td i a g n o s i s 浙江工业大学硕士学位论文 a p p r o a c ht od e t e c ts u b c l a s s e so f i n t r u s i o na t t a c k s t h er e s u l t sf r o mo u r p r e l i m i n a r ya n a l y s i si n d i c a t es u c c e s s f u ld e t e c t i o no fs u b c l a s s e so f d e n i a l - o f - s e r v i c ea t t a c k s t h i sf i l t e ri sap r i m a r yc o m p o n e n ti nt h e i n t e l l i g e n ti n t r u s i o nd e t e c t i o ns y s t e mw e a r ed e v e l o p i n g a l t h o u g h ，i nf a c t ，t h ea p p l i c a t i o no fg ai nt h ei d st h a tm a k e st h e i d sh a si n t e l l i g e n c ei ss t i l li ne x p e r i m e n t a lp h a s e ，t h e r ea r em a n ya s p e c t s t ob es t u d i e do nt h ei d si nt h ef u t u r e t h ea u t h o rb e l i e v e st h a tt h ei d sw i l l c o m ei n t oc o m m o nu s e1 i k et h ef i r e w a l lw i t ho u rh a r dw o r ko ni t k e yw o r d s ：n e t w o r ks e c u r i t y , i n t r u s i o nd e t e c t i o n ，f i l t e r , g e n e t i c a l g o r i t h m 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研 究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不 包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工 业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重 要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法 律责任。 作者签名：日期：o 许 f，月上7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 日期：0 7 年乡月节日 日期。0 年 月彳日 浙江工业大学硕士学位论文 1 1计算机网络安全现状 第一章绪论 从2 0 世纪9 0 年代末期开始，随着因特网的成熟和广泛应用，引发了一场全 球范围内的信息革命，全球信息化的步伐不断加快，信息型社会正在形成并走向 成熟。信息，逐渐被作为一种重要的社会战略资源而与物质、能源、人才一起被 列为现代社会生产力要素中的重要因素。 信息化社会中，信息安全必然重要。然而信息安全所面l i 缶的威胁也由来已久。 自世界上出现病毒理论后，对计算机系统的攻击就引起了一些人的兴趣。至今， 这种攻击已经由学术上的讨论，计算机操作系统的漏洞发现与弥补演变成了对信 息系统的破坏和对涉及国家利益信息、商业信息及个人隐私信息的窃取和破坏。 随着因特网的迅猛发展，更进一步暴露出了这种自由网络空间具有的无中心、无 管理、不可控、可信等不安全的特征，且形成了对现存社会秩序的威胁。 据调查显示，2 0 0 6 年我国网络信息安全形势非常严峻，病毒危害正在不断加 剧，同时，隐藏和逃避技术更加高级、金钱利益成为更大的驱动力、隐私和机密 数据面临风险提高。尤其需要强调的是僵尸网络，因为这已经成为散布垃圾邮件 和钓鱼信息、传播间谍软件和广告软件、集体攻击组织团体、窃取机密信怠的重 要手段。 1 2 计算机网络安全威胁 从一个网络系统的角度出发，可以简单地将相关人群分为两类：授权用户与 非法用户。它们作为主体，具备了实施攻击的条件，而攻击的目标则是网络的三 个基本要素数据、关系与能力。 如果对主体的权力进行一定的量化，并将非法用户的权力设置为零，那么可 以简单地将攻击定义为权力的越级实施，包括越级获取数据、获得不应该具有的 信任关系以及对系统能力的滥用( 包括非法访问服务与干扰服务) 。 攻击方法可以是技术性的，也可以是非技术性的。就技术性手段而言，在网 络内部发动攻击更加容易。因此，在制定安全策略的时候，最好将内部网划分为 不同的安全域，引入安全级别的概念，以防止权力的滥用。 以下对各种攻击进行分类说明。攻击分类并没有一个通用的标准，在这里将其 浙江工业大学硕士学位论文 大概分为以下六类： 1 ) 人因攻击。这种类型的攻击方法与人类社会其他领域的偷窃、欺骗行为并 无分别，大多是采用如下两中手段： 社会工程( s o c i a le n g i n e e r i n g ) ：通过一些日常的交际手段来获取些 本来应该保密的信息，一个电话、一段闲聊、一封邮件都能完成一次 攻击。这种攻击手法要利用网络用户安全意识薄弱的弱点，例如冒充 网络管理员打电话给用户，说由于系统维护的需要，要求用户提供自 己的密码，非常简单但是在某些情况下却能轻易得逞。 盗窃行为：通过一些物理( 与电子信息的窃取相对而言) 的手段来偷 窃保密信息，例如在合法用户登录时偷看密码等。 2 ) 物理攻击。这种攻击一般来说都是由内部人员发动，危害是最直接的，而 且往往能够造成最大的破坏，因为攻击者获得了保护系统的完全控制权。 可以简单地将物理攻击分为两类： 物理破坏：对于计算机系统，一杯水可能就足够了。 物理访问：如果某个入侵者能够直接接触计算机设备，则基本上可以 认为该设备的安全性已经丧失。例如直接用光盘软盘启动系统，或者 c i s c o 的路由器都可以通过一定的操作系列来修改e n a b l e 口令。这种攻 击方式与前一种的区别在于攻击的意图是获取信息或者控制系统。当 然，如果这种企图失败，恼羞成怒之下，有可能导致“物理破坏”攻 击。 以上两中攻击方法能够造成非常大的危害，但它们基本上不是技术性的或者 说通过技术手段无法防范。针对这二者，主要的措施是加强内部用户的安全教育 以及采取各种物理安全措施，例如严密看管机房、增加各种物理访问口令( 如微 机的c m o s 口令、s u n 的p r o m 口令等，虽然不是百分之百有效，但终归能够 起到一定的作用) 等，都能或多或少地防范这些攻击手法。 其余几种攻击方法都是技术性的，它们分别针对网络的三个要素发动，下面分 别介绍。 3 ) 数据攻击。这种攻击针对数据而来，主要有： 信息获取：严格地说这种行为不算是攻击，主要是利用诸如地址扫描、 端口扫描等技术获取网络的一些信息，或者利用某些网络服务来获取 网络和用户信息，例如f i n g e r 服务、w h o i s 服务( w h o i s 服务是一种公 共服务，由一些公共的w h o i s 服务器来提供服务，主要提供一些网络注 册信息。在u n i x 系统中可以参考w h o i s 命令，通过w h o i s 获取信息作 为社会工程攻击的基础) 和s m b 服务等。 非法获取数据：超越主体所具有的权限来获取数据，包括主机数据的 获取与网络传输数据的获取。这方面的例子如搭线监听来获取某些数 2 浙江工业大学硕士学位论文 据，窃取主机上或者传输网络上的密文数据；然后再用工具进行破解， 例如使用c r a c k 来破解密码。 篡改数据：修改主机上或者网络上传输的数据。前者一般需要与对能 力的攻击结合进行，即首先获取非法的权限，然后修改某些数据来表 达到隐藏痕迹和保证再次侵入的效果t 后者一般是利用路由或者电子 的手段来截取数据，篡改之后再进行发送。需要注意的是这里的数据 是广义的，如果网络上传输的是某种类型的命令，那么对这种数据的 篡改实际上达到了能力获取的目的。 4 ) 身份冒充。这种攻击的着眼点在于网络中的信任关系，主要有： 地址伪装：由于现有网络大多数都是i p 网络，因此这种攻击的主要形 式是i p 伪装( i ps p o o f i n g ) ，由于一些比较老的服务是根据m 地址来 建立信任关系，它就通过修改i p 来进行冒充活动。这种攻击一般需要 与拒绝服务攻击结合进行，即首先对真正被信任的主机进行拒绝服务 攻击，保证它没有处于活动状态，再实施冒充行为。 会话重放( r e p l a y ) ：记录有效会话的全过程，在需要时重新发送，以 达到攻击的且的。 特洛伊木马：在合法的程序中加入恶意代码，通过合法程序的执行来 运行恶意代码，以达到攻击的目的。当前这种攻击方法有与病毒相结 合的趋势，即特洛伊木马利用病毒来进行传播。 陷进门：在系统的合法程序中加入的后门代码，它利用了用户对于系 统程序的信任，一般是在攻击成功之后为了进行进一步的攻击而引入 的，例如在成功地入侵系统之后，对系统l o g i n 程序进行替换，保证攻 击者能够绕过系统的鉴别过程随时进入系统。这方面一个著名的例子 是k e nt h o m p s o n ，在早期的u n i x 系统中通过修改c 语言的编译器加 入的后门。 5 ) 非法使用服务。这种攻击的目的在于非法利用网络的能力，主要有： 主机缓冲区溢出：本地的非特权用户利用系统的漏洞成为特权用户， 这种攻击主要利用了系统堆栈具有可执行权限的漏洞，近几年来这种 类型的漏洞可以说是层出不穷。 远程缓冲区溢出：利用网络服务的漏洞来远程获取特权用户的权力， 例如s e n d m a i l 和i i s 的漏洞等。 利用系统朋艮务漏洞的攻击：利用系统正常服务的各种漏洞，来获取正 常情况下无法获取的数据，例如早期通过c g i 获得p a s s w d 文件的漏洞、 近期的u n i c o d e 漏洞等方法。 6 ) 拒绝服务。这种攻击的目的是干扰网络的正常运行，它针对全部三个要素， 既干扰用户合法获取数据，又妨碍合法的信任关系的建立，还要阻止系统 。3 。 浙江工业大学硕士学位论文 提供服务，主要有： 占用网络宽带：妨碍正常的网络流量，干扰正常工作，甚至占用全部 网络带宽，例如锄u r f 攻击等。 干扰服务：干扰系统提供的各种网络服务，降低服务性能，例如 s y n f l o o d 等。 本地关机：在n t 和各种u n i x 、l i n u x 主机上，非特权用户是不能关机 的( 不是按开关) ，但是系统的缺陷可能会使他们也能够非法关机( d o w n 掉) ，例如x 8 6 指令集的缺陷。 远程关机：远程使主机d o w n 机，例如早期的w i n n u k e 攻击。 1 3 计算机网络安全策略 网络的安全策略( s e c u r i t yp o l i c y ) 是计划的需求，在现实社会安全中有时是 一个神奇的概念，最初的安全定义是指建立一个理想的系统，安全地实现这些计 划。或者说安全策略将安全的抽象概念映射到真实世界中。在最初定义安全的时 候，我们指出它基于一些想法，即由什么构成一个系统的预期行为。安全策略将 这些预期用文字记载下来。安全策略有两个定义：1 ) 正式的安全策略，通常由一 个数学模型所构成，这个数学模型收集了系统所有可能的状态和操作，并伴随着 状态操作存在的可能时间和方式的约束；2 ) 管理上的安全策略，它概述了安全目 标并提交管理资源以达到目标。下面概述已有的安全组件。 1 ) 访问控制：访问控制防止对资源的未授权使用，包括防止以未授权方式使 用某一资源。访问控制需采取两种措施：一种是识别与确证访问系统的用 户，即身份证；另一种是决定该用户对某一系统资源可进行何种类型的访 问( 读、写、运行等等) 。 2 ) 鉴别与认证：在可信的计算机信息系统初始运作时，首先要求用户标识自 己的身份，并使用保护机制( 如口令、证书等) 来鉴别用户的身份；阻止 非授权用户访问用户身份鉴别数据。通过为用户提供惟一标识，计算机可 信信息系统能够使用户对自己的行为负责。计算机可信信息系统还具备身 份标识与该用户所有可审计行为相关联的能力。 3 ) 加密：通过执行多种功能来保护信息，可以有效地隐藏数据文件和所传输 的内容，消除未授权者监视的可能性，还可以检测到数据的意外更改或有 意的篡改。加密还可以为文档的作者提供验证。加密技术是保障信息安全 的核心技术，它可以在计算机和网络通信中用来解决身份鉴别、访问控制 以及信息的保密性、完整性、不可否认性。 下面概述已有的网络安全产品。 1 ) 防火墙。防火墙出现得很早，最初可能是作为路由器的一个附加功能来实 4 。 浙江工业大学硕士学位论文 现的。实现防火墙的主要技术有数据包过滤、应用网关和代理服务等。若 将应用网关技术和包过滤技术结合起来，将保证应用层的安全性、同一支 持处理所有协议、审计和预警等，其运转对于用户和建立系统都是透明的， 并且包括了面向所有的图形用户接口，便于配置和管理。 2 ) v p n 。v p n 是英文v i r t u a lp r i v a t en e t w o r k i n g 的缩写，中文一般译作虚拟 专用网，或虚拟子网。简单地说，一个v p n 就是利用基于公共基础设施 建设起来的公开网络的数据传输能力，借助相关安全技术和手段实现的， 能够提供安全、可靠、可控的保密数据通信的一条安全通道。 3 ) 扫描器。扫描器是一种自动检测远程或本地主机安全性弱点的程序，通过 使用扫描器，你可以发现远程服务器的各种t c p 端口的分配、它们提供 的服务以及它们的软件版本，直观或间接地了解到远程主机所存在的安全 问题。 4 ) 入侵检测系统。入侵检测系统是一种主动的网络安全防护措施，它从系统 内部和各种网络资源中主动采集信息，从中分析可能的网络入侵或攻击。 入侵检测是对企图入侵、正在进行的入侵或者已经发生的入侵进行识别的 过程。所有能够执行入侵检测任务和功能的系统，都可称为入侵检测系统。 以上几种网络安全技术在计算机的不同领域都有不同程度的应用，在网络安 全中都起到了一定作用，但在某些方面也存在一定的缺陷。 1 - 4 本论文的研究工作 1 4 1 选题的意义 根据2 0 0 6 年出版的最新 2 0 0 5f b ic o m p u t e rc r i m es u r v e y ( 美国最大范围 的计算机犯罪调查) 调查显示：在对全美约2 0 0 0 家组织和机构的计算机与网络安 全的调查中，2 0 0 5 年由安全问题带来的全部损失约为3 2 亿美元；来自企业网内 部的攻击和来自外部的攻击同样多，约占4 4 。对入侵攻击的检测与防范、保障 计算机系统、网络系统及整个信息基础设施的安全已经成为刻不容缓的重要课题。 入侵检测的目的是监控网络活动，及时识别可疑的行为，以及明显的攻击行为。 高效、准确的入侵检测系统能够保障计算机系统、网络系统甚至整个信息基础设 施的安全，避免发生巨大的经济损失。 入侵检测系统对计算机系统至关重要，它解决了安全防护系统中来访者被允 许访问后对其所作所为无法控制的难题。学术界对i d s 的研究已经有2 0 年了，也 出现了许多i d s 产品，然而i d s 仍然是一种相对年轻的技术，同时，随着i d s 的 发展，i d s 所保护的对象：系统和网络本身也在迅速地发展。这给i d s 提出了许 s 浙江工业大学硕士学位论文 多新的要求，如可扩展性、监测器的管理、对深入调查的支持、系统负荷、漏报 和误报、用户的参与程度、易用性。 i d s 对系统资源的占用程度是评价i d s 的一个重要指标”o l ，如果i d s 占用了 系统3 0 0 , 4 以上的资源，或者造成网络性能的明显下降，用户可能认为是不可接受 的。对于网络i d s 来说，资源主要消耗在对每个数据包的分析和匹配上，在一个 高速网络中，这种检测的开销很大。而降低系统开销的措施有时候是与提高检测 准确率相矛盾的，这就存在一个权衡的问题，很难有一个两全其美的解决办法。 为了解决这个问题，目前一种比较流行的方法是用一台专门的机器来运行i d s ， 在这台机器上没有运行其它的应用，这样，i d s 就可以做成一个黑盒子的形式。 但是该办法需要增加额外的硬件成本，对于一些小型的计算机系统来说难于接受。 入侵过滤器能够减少i d s 的计算成本。微遗传算法在保证入侵过滤器的准确 性的前提下降低了入侵过滤器的计算成本。所以将一个基于微遗传算法的入侵过 滤器加入到i d s 是符合入侵检测系统发展方向的。 1 4 2 本文的研究工作 本文在查阅了大量国内外文献的基础上，在对入侵检测方法的研究中做了以 下几个方面的工作： 1 ) 分析了目前的入侵检测技术的优缺点，提出了本论文研究的对象和意义。 2 ) 分析了遗传算法的原理及应用方法。 3 ) 进行了将微遗传算法用于入侵过滤器的理论研究，并提出了加入了入侵 过滤器的i d s 模型。 4 ) 编写了基于微遗传算法的入侵过滤器的相关源代码，并测试了过滤器的 功能和性能。从理论和实验结果上验证了本文提出的入侵过滤器的优越 性。 6 浙江工业大学硕士学位论文 第二章入侵检测的理论研究 2 1入侵检测的产生与发展 2 0 世纪7 0 年代，随着计算机的速度、数量的增长以及体积的减小，对计算 机安全的要求显著增加。面对这样的形势，在1 9 7 7 年和1 9 7 8 年，美国国家标准 局召开了有政府和商业组织代表参加的会议，就当时的安全、审计和控制状况提 出报告。 1 9 8 0 年，j a m e sa n d e r s o n 在写给一个保密客户的技术报告中指出，审计记录 可以用于识别计算机误用。他提出了入侵尝试或威胁的概念，并将其定义为：潜 在、有预谋、且未经授权而访问信息、操作信息、致使系统不可靠或无法使用的 企图。同时，他给威胁进行了分类，并对审计子系统提出了改进意见，以使该系 统可以检测误用。他认为审计记录分析可以监视入侵行为，并对入侵进行分类， 还提出对不同用户的不同渗透方法。 1 9 8 6 年，s r i 的d o r o t h ye d e n n i n g 发表了一篇论文( a n i n t r u s i o n - - d e t e c t i o n m o d e l ) ) ，该文深入讨论了入侵检测技术，探索了行为分析的基本机制，首次将入 侵检测的概念作为一种计算机系统安全防御措施而提出，并且建立了一个独立于 系统、程序应用环境和系统脆弱性的通用入侵检测系统模型。 1 9 8 8 年，s r i 开始开发1 d e s ( i n t r u s i o nd e t e c t i o ne x p e r ts y s t e m ) 原型系统， 它是一个实时入侵检测系统。它采用了统计技术来进行异常检测，用专家系统的 规则进行误用检测。i d e s 在实现双重分析( 分析和异常检测) 和实时分析两方面 迈出了关键的一步。该系统被认为是入侵检测研究中最有影响的一个系统，也是 第一个在一个应用中运用了统计和基于规则两种技术的系统。 1 9 9 0 年出现的网络安全监视器( n e t w o r ks e c u r i t ym o n i t o r ，n s m ) ，是u c d 设计的面向局域网的i d s ，n s m 被设计用来分析来自以太局域网的数据及连接到 该网的数据。这个系统重要贡献是首次使用网络数据包作为审计数据源，提出基 于网络的i d s 的概念。 1 9 9 6 年u c d 的计算机安全实验室，以开发广域网上的入侵检测系统为目的， 开发了g r i d s 。目标是使受保护的网络规模达到成千上万，甚至上百万，并且还 保护路由器、域名服务器等。1 9 9 7 年，c i s c o 公司开始将网络入侵检测整合到c i s c o 路由器中。同时，i n t e r n e t 安全系统公司( i s s ) 发布了r e a l s e e u r e ，这是个被广泛 使用的，用于w i n d o w sn t 的网络入侵检测系统，从此，网络入侵检测革命的序 幕被拉开了。 7 。 浙江工业大学硕士学位论文 从1 9 9 6 年到1 9 9 9 年。s r i 开始e m e r a l d 的研究，它是n i d e s i l 2 1 的后继者， 具有分布式可升级的特点，用于在大型网络中探测恶意入侵活动( 包括对网站的 入侵) ，高度分析，自动相应。并在以下几个方面进行了扩展：可以进行基于网络 的分析：增强互操作性；使分布式计算环境的集成更容易。 2 2 入侵检测的基本概念 2 2 ，1 入侵检测的溉念 入侵，是指任何试图危及计算机资源的完整性、机密性或可用性的行为【”】。 而入侵检测是对入侵行为的发觉。它通过从计算机网络或系统中的若干关键点收 集信息，并对这些信息进行分析，从而发现网络或系统中是否有违反安全策略的 行为和遭受攻击的迹象。进行入侵检测的软件与硬件的组合便是入侵检测系统( 简 称i d s ) 。入侵检测是防火墙的合理补充，帮助系统对付网络攻击，它扩展了系统 管理员的安全管理能力( 包括安全审计、监视、进攻识别和响应) ，提高了信息安 全基础结构的完整性。入侵检测被认为是防火墙之后的第二道安全闸门，在不影 响网络性能的情况下能对网络进行检测，从而提供对内部攻击、外部攻击和误操 作的实时保护。 入侵的主体是入侵者，也称为黑客。入侵者可分为两类： 1 ) 外部入侵者：网络外面的侵入者，或者可能攻击你的外部存在( 乱改的w e b 服务器，通过e - m a i l 服务器转来的垃圾邮件) 。外部的侵入者可能来自 i n t e r n e t ，拨号线，物理介入，或者从同你网络连接的伙伴网络( 卖主、客 户、中间商等) 。 内部入侵者：合法使用你的互连网络的侵入者。包括滥用权力的人( 比如 社会安全雇员因为不喜欢某人就将其标志为死亡) 和模仿更改权力的人 ( 比如使用别人的终端) 。个常被引用的统计就是8 0 的安全问题同内 部人有关。 入侵者进入系统的三种主要途径： 1 ) 物理侵入；如果一个侵入者对主机有物理进入权限 o , c - ，( 刁卸( 3 - 2 - 6 ) 这种方法与第二种方法类似，f 为目标函数界限的保守估计值。 常用的尺度变换方法有以下几种： 1 、线性变换法 浙江工业大学硕士学位论文 假设原适应度函数为，变换后的适应度函数为厂，则线性变换可用下式表 示： f 。= o r 厂+ ( 3 2 7 ) 上式中的系统确定方法有多种，但要满足以下条件： 原适应度的平均值要等于定标后的适应度平均值，以保证适应度为平均值 的个体在下一代的期望复制数为1 ，即： 丘。= 厶 ( 3 2 8 ) 变换后的适应度最大值应等于原适应度平均值的指定倍数，以控制适应度 最大的个体在下一代中的复制数。实验表明，指定倍数c 。可在1 o 2 0 范围内。 即根据上述条件可确定线性比例的系数丘= 丘 ( 3 2 9 ) 口：生型：! ! 垒口：! 鱼二堑盘选 舭了等肛瓦了i _ 如图3 - 2 所示，线性变换法变换了适应度之间的差距，保持了种群内的多样 性，并且计算简便，易于实现。如果种群内某些个体适应度远远低于平均值时， 有可能出现变换后适应度值为负的情况，为此，考虑到保证最小适应度值非负的 条件，进行如下的变换： 舻妄，夕= 瓦- f m f 2 4 浙江工业大学硕士学位论文 ( c ) 1 图3 2 适应度函数的线性调整 c a ) 正常情况；( b ) 适应度出现负值；( c ) 适应度出现负值时的变换 2 、幂函数变换法 变换公式为：= f ( 3 2 1 2 ) 上式中的幂指数k 与所求的最优化问题有关，结合一些实验进行一定程度的 精细变换才能获得较好的结果。 3 、指数变换法 变换公式为： f - - - - e 一矿 这种变换方法的基本思想来源于模拟退火过程( s i m u l a t e da n n 锄- g ，s a ) ， 其中的系数a 决定了复制的强制性，其值越小，复制的强制就越趋向于那些具有 最大适应度的个体。 3 2 3 遗传操作 遗传算法包括三个基本操作：选择、交叉和变异。这些基本操作又有许多不 同的方法，下面我们逐一进行介绍。 2 5 浙江工业大学硕士学位论文 1 、选择 选择是用来确定重组或交叉个体，以及被选个体将产生多少子代个体。按照 适应度进行父代个体的选择，可以挑选以下的算法： 轮盘赌选择这是最简单的一种选择方法。为了选择交配个体，需要进行多 轮选择，每一轮产生一个【o ，l 】均匀随机数，将该随机数作为选择指针来确定被选 个体。 随机遍历抽样随机遍历抽样法提供了零偏差和最小个体扩展。设定 n p o i n t e r 为需要选择的个体数目，等距离选择个体，选择指针的距离为1 n p o i n t e r ， 第一个指针的位置由f o ，1 n p o i n t e r l 又间的均匀随机数决定。 局部选择在局部选择法中，每个个体处于一个约束环境中，称为局部邻集 ( 而其他选择方法中视整个种群为个体之邻集) ，个体仅与其邻近个体产生交互， 该邻集的定义由种群的分布结构给出，邻集可被当作潜在的交配伙伴。 截断选择与前面几种自然方式的选择方法比较，截断选择法是一种人工选 择方法。它适合于大种群。在截断选择法中，个体按适应度排序。只有最优秀的 个体能够被选作父个体，截断选择的参数叫做截断域值t r u n c 。它定义为被选做父 个体的百分比，取值范围为5 0 - - - 1 0 。在域值之下的个体不能产生子个体。 选择强度； s e l i n t r , 一( t r u n c ) = 元赢厕1 多样化损失；l o s s d i v r , 一( t r u n c ) = l t r u n c 选择方差：s e l p 奶 l 。( t r u n c ) = l 一& z 砌n 。( 乃狮顿s 跣砌( z 勉加) 一工) ( 3 2 1 6 ) 上式中z 为下列高斯分布的积分下限： 砌脚= f 煮尹善矽 锦标赛选择在锦标赛选择法中，随机地从种群中挑选一定数目( t o u r ) 个 体，然后将最好的个体选做父个体。这个过程重复进行完成个体的选择。锦标赛 选择的参数为竞赛规模t o u r ，其取值范围为【2 ，n i n d 。 选择强度：s e l i n t r , 一( t r u n c ) = 2 ( 1 0 9 ( t o u r ) 一l o g x 4 z 4 1 0 9 ( t o u r ) ) 一上 婴 多样化损失：l o s s d i v r o 。, ( t o u r ) = t o u rt o u r - 1 - t o u r ”1 当t o u r = 5 时多样化损失大约为5 0 。 选择方差：s e l p 奶泔( t o u r ) = 1 - 0 0 9 6 l o g ( 1 + 7 1 l ( t o u r 1 ) ) 1 s e l 玩e ( 2 ) = l 一二 2 6 浙江工业大学硕士学位论文 2 、交叉，基因重组 基因重组是把两个父个体的部分结构加以替换重组而生成新个体的操作，也 称为交叉。重组的目的是为了能够在下一代产生新的个体，就像人类社会的婚姻 过程，通过重组交叉操作，遗传算法的搜索能力得以飞跃地提高。这里主要介绍 二进制交叉。 二进制交叉又分为单点交叉和多点交叉。单点交叉中，交叉点k 的范围为 1 ， n v a r - 1 ，n v a r 为个体变量数目，在该点为分晃相互变换变量。 对于多点交叉，m 个交叉位置k ，可无重复随机地选择，在交叉点之间的变 量问续地相互交换，产生两个新的后代，但在第一位变量与第一个交叉点之间的 一段不做变换。 多点交叉的思想源于控制个体特定行为的染色体表示信息的部分无须包含于 邻近的子串中，多点交叉的破坏性可以促进解空间的搜索，而不是促进过早地收 敛。因此搜索更加健壮。 3 、变异 重组之后是子代的变异，子个体变量以很小的概率或步长产生转变，变量转 变的概率或步长与维数( 即变量的个数) 成反比，与种群的大小无关。对于实值 变异来说，变异步长的选择比较困难，最优的步长视具体情况而定，甚至在优化 过程中可以改变。通常较小的步长会比较成功，但有时大步长比较快些。建议采 用如下的变异算子。 工= x 0 5 上 上式中，= 霎等，口( f ) 以概率l m i r 直1 ，以1 - l ，m 取值。，通常m ；2 。； l 为变量的取值范围；x 为变异前变量取值；x 为变异后变量取值。 对于二进制编码的个体而言，变异意味着变量的翻转。对于每个个体，变量值的 改变是随机的。 3 2 4 算法设计 基本遗传算法( s i m p l eg e n e t i ca l g o d t h r a ，s g a ) 可定义为一个8 元组： s g a = ( c ，e ，e o ，m ，西，f ，甲，t ) 式中，c 一个体的编码方法，s g a 使用固定长度二进制符号串的编码方法； b 个体的适应度评价函数； 岛一初始群体； m 一群体大小，一般取2 0 - - 1 0 0 ； 2 7o 浙江工业大学硕士学位论文 弧选择算子，s g a 适应比例选择算子； r 一交叉算子，s g a 使用单点交叉算子； 甲一- 交异算子，s g a 使用基本位变异算子； t - - 一算法终止条件，一般终止进化代数为1 0 0 5 0 0 ； 对于一个实际的待优化闯题，首先需要将其表示为适合于遗传算法操作的形 式。这里以二进制编码为例，它包括以下几个步骤： 根据具体问题确定待寻优的参数。 对每个参数确定它的变化范围，并用一个二进制数来表示。例如，若参数口 的变化范围为 口。，窿一 ，用n l 为二进制数b 来表示，则二者之问满足： 口= 口。+ j 巧b ( t t f t n 。- - l z m l n ) 口2 口m + 石( 二一l 这时参数范围的确定应覆盖全部的寻忧空间，字长m 的确定应在满足精度要求情 况下尽量取小的m ，以尽量减小遗传算法计算的复杂性。 将所有表示参数的二进制数串接起来组成一个长的二进制字串。该字串的 每一位只有0 或l 两种取值。该字串即为遗传算法的操作对象。 基本遗传算法运行参数包括：种群大小，染色体长度，进化最大代数，总运 行次数，交叉率，变异率等。这些参数在运行开始时由使用者输入。 3 3 改进的遗传算法 自从j h h o l l a n d 系统地提出遗传算法的完整结构和理论以来，众多学者一 直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和交叉 机理等进行了深入的探索，引入了动态策略来改善遗传算法的性能，提出了各种 变形的遗传算法。 3 3 1 分层遗传算法 对于一个问题，首先随机地生成n * n 个样本( n 2 , n 2 ) ，然后将它们分成 n 个子种群，每个子种群包含n 个样本，对每个子种群独立地运行各自的遗传算 法，记它们为g a 。( i = 1 ，2 n ) 。这n 个遗传算法最好在设置特性上有较大 的差异，这样就可以为将来的高层遗传算法产生更多种类的优良模式。 在每个子种群的遗传算法运行到一定代数后，将n 个遗传算法的结果种群记 录到二维数组r 1 n 1 m 】中，则r 【i ，j 】( i - 1 n j = i n ) 表示g a ，的结果种 群的第j 个个体。同时，将n 个结果种群的平均适应度值记录到叔祖a l l n 】中， 2 9 浙江工业大学硕士学位论文 a “】表示g a 的结果种群平均适应度值。高层遗传算法与普通遗传算法的操作相类 似，也可以分成如下三个步骤： l 、选择 基于数组a 1 n 】，即n 个遗传算法的平均适应度值，对数组r 代表的结果 种群进行选择操作，一些结果种群由于它们的平均适应度值高而被复制，甚至复 制多次；另一些结果种群由于它们的种群平均适应度值低而被淘汰。 2 、交叉 如果r 0 ，1 n 】和r 0 ，1 n 】放随机地匹配到一起，而且从位置x 进行交 叉( 1 i ；j n ；l x n 1 ) ，则r e i ，x + l n 】相互交换相应的部分。这步 骤相当于交换g a ；和g a 。中结果种群的n x 个个体。 3 、变异 以很小的概率将少量的随机生成的新个体替换r 1 n 1 n 】中随机抽取的 个体。至此，高层遗传算法的第一轮运行结束。n 个遗传算法g a ；( # l ，2 ，n ) 可以从相应于新的r i ，1 h i 和r j ，1 n 】种群继续各自的操作。在n 个g a 。再 次各自运行到一定代数后，再次更新数组r 1 n ，1 m 】和a 0 n 】，并开始高 层遗传算法的第二轮运行。如果继续循环操作，直至得到满意的结果。 3 3 ，20 h 0 算法 c h c ( c r o s sg e n e r a t i o ne l i t i s ts e l e c t i o n , h e t e r o g e n e o u sr e c o m b i n a t i o n , c a t a c l y s m i c m u t a t i o n ，跨世代精英选拔、异物种重组、灾变变异) 算法与典型的遗传算法c g a 不同点在于：c g a 的遗传操作比较单纯，简单地实行并行处理：而c l t c 算法牺牲 这种单纯性，换取遗传操作的较好效果，并强调优良个体的保留。下面介绍其遗 传操作的改进之处： l 、选择 通常遗传算法是依据个体的适应度复制个体完成选择操作的，而在c h c 算法 中，上世代种群与通过新的交叉方法产生的个体混合起来，从中按一定概率选择 较优的个体。这一策略称为跨世代精英选择。 2 、交叉 c h c 算法使用的重组操作是对均匀交叉的一种改进。均匀交叉对父个体位值的 各位位置以相同的概率实行交叉操作，这里的改进之处是：当两个父个体位值相 异的位数为r i 时，从中随机选取m 2 个位置，实行父个体位值的互换。不过要确 定一阀值，当个体问的海明距离低于该f 囝值时，不进行交叉操作。并且与种群进 化收敛的同时，逐渐地减少该阀值。 2 9 浙江工业大学硕士学位论文 3 、变异 c h c 算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀 个体中选择一部分个体进行初始化。初始化的方法是选择一定比例的基因座，随 机地决定它们的位值。这个比例值称为扩散率，一般取0 3 5 。 3 3 3 自适应遗传算法 遗传算法的参数中交叉概率p 。和变异概率p i i l 的选择是影响遗传算法行为和性 能的关键所在，直接影响算法的收敛性，p c 越大新个体产生的速度就越快。针对 不嗣的优化问题，需要反复试验来确定p c 和p m ，这是件繁琐的工作，而且很难找 到适应于每个问题的最佳值。s r i n v i v a s 等提出一种自适应遗传算法，p c 和p i n 能 够随适应度自动改变，如图3 - 3 所示。表示了遗传算法韵过程。当种群个体适应度