（计算机软件与理论专业论文）基于改进遗传算法的网络入侵检测的研究.pdf

哈尔滨理工大学工学硕士学位论文 基于改进遗传算法的网络入侵检测的研究 摘要 上世纪九十年代以来，i n t e r n e t 持续高速的发展，极大地加快了社会信 息化的步伐。随着计算机技术和通信技术在金融、政府、医疗、制造业、商 业、教育各界的广泛应用，网络安全问题已经越来越受人们重视。为了保护 网络和系统的安全，人们针对信息的存储、处理和传输的各个环节使用了各 种安全技术。但是人们发现使用单一的安全技术是不可靠的，只有将多种安 全技术综合地使用在一个整体的安全方案中，才可以尽可能地保护信息和系 统的安全。 当前网络入侵检测系统主要采用误用入侵检测技术和异常入侵检测技 术。误用检测技术是基于入侵检测特征库模式的匹配。由于入侵检测特征库 具有滞后性，因而入侵漏报率比较高。异常入侵检测系统通过检测系统的活 动与正常活动的偏差来判断是否存在入侵行为。但异常入侵检测系统在建立 正常模式过程中有可能受到入侵行为的干扰。从而，系统把某些入侵行为作 为正常模式对待，且不能区分用户的随机性行为，误报率较高。这就要求有 一种新的入侵检测系统的出现。 针对目前入侵检测系统的一系列问题，本论文对遗传算法在入侵检测中 的应用进行研究，首先分析标准遗传算法存在搜索时间长和易出现“早熟 收敛等不足，然后指出造成以上不足的原因是标准遗传算法在运行的过程中 出现了重要基因位丢失。本文把绝对海明距离应用到初始种群的产生过程 中，以改善初始种群的个体分布情况；应用“精英”保护策略以加快算法的 运行速度；提出了检测基因识别以及补救的策略；对交叉、变异算子做了改 进，提出了自适应的交叉率和变异率。在此基础上提出了一种改进的遗传算 法一一带基因丢失识别及补救策略的自适应遗传算法，并通过函数试验，验 证了自适应遗传算法比标准遗传算法有更快的搜索速度和更高的得到全局最 优解的概率。 最后，本文将改进的遗传算法应用到网络入侵检测系统中，提出了一个 基于改进的遗传算法的网络入侵检测的模型。然后通过实验验证了基于改进 遗传算法的网络入侵检测系统的可行性。当进化代数一定时，规则库规模相 同的情况下，基于改进后的遗传算法的入侵检测系统比基于标准的遗传算法 哈尔滨理工大学工学硕士学位论文 的入侵检测系统生成规则库所花费的时间少，随着规则库规模的增大，两种 系统生成规则库所花费的时间都在增大：同时基于改进遗传算法的入侵检测 系统大大降低了系统的误报率，检测所消耗的时间明显缩短，检测速率也有 明显的提高。证明基于改进遗传算法的网络入侵检测系统是行之有效的。 关键词网络安全；入侵检测系统；遗传算法：交叉算子；变异算子 哈尔滨理工大学工学硕士学位论文 i n t r u s i o nd e t e c t i o ns y s t e mb a s e do ni m p r o v e d g e n e t i ca l g o r i t h m a b s t r a c t w i t ht h eg r e a td e v e l o p m e n to fi n t e r n e tf r o m19 9 0 si nt h e2 0 t hc e n t u r y ，t h e p a c e o fi n f o r m a t i o n i z a t i o n o ft h e s o c i e t y h a sb e e n g r e a t l yi m p r o v e d t e c h n o l o g i e so fc o m p u t e ra n dc o m m u n i c a t i o nh a v eb e e nw i d e l yu s e di nd i f f e r e n t f i e l d s ，s u c h a s f i n a n c e ，g o v e r n m e n ts e r v i c e s ，m e d i c a lc a r e ，m a n u f a c t u r e ， c o m m e r c i a lc o n t r a c t ，e d u c a t i o na n ds oo n t h e r e f o r e ，p e o p l eh a v ep a i dm o r ea n d m o r ea t t e n t i o nt ot h ep r o b l e m sc a u s e db yi n t e r n e ts a f e t y i no r d e rt op r o t e c tt h e s a f e t yo ft h ei n t e r n e ta n ds y s t e m ，v a r i o u st e c h n o l o g i e sc o n c e r n i n gs a f e t yh a v e b e e na p p l i e dt od i f f e r e n tc o n n e c t i o no fi n f o r m a t i o n s t o r a g e ，s e t t l e m e n ta n d t r a n s p o r t a t i o n b u ti ti s n tr e l i a b l et ou s et h eo n l ys a f e t yt e c h n o l o g y t h eg o o d w a yo fs o l v i n gt h ep r o b l e mi st oc o m b i n es e v e r a lk i n d so fs u c ht e c h n o l o g i e s t o g e t h e r a n du s et h e mi nt h ew h o l ep l a nf o r p r o t e c t i n g t h e s a f e t y o ft h e i n f o r m a t i o na n ds y s t e m t h ei n t r u s i o nd e t e c t i o ns y s t e mm a i n l yu s e st h ea n o m a l yi n t r u s i o nd e t e c t i o n t e c h n o l o g ya n dt h em i s u s ei n t r u s i o nd e t e c t i o nt e c h n o l o g y t h em i s u s ed e t e c t i o n t e c h n o l o g yi sb a s e do nt h em a t c hp a t t e r n so fi n t r u s i o nd e t e c t i o nf e a t u r el i b r a r y ， b e c a u s eo ft h e h y s t e r e s i s o fi n t r u s i o nd e t e c t i o f if e a t u r e l i b r a r y ，t h e r a t eo f m i s s i n gr e p o r ti sa l w a y sh i g h b yc o n t e s t i n gt h ed i f f e r e n c e sb e t w e e ns y s t e m a c t i v i t ya n dn o r m a la c t i v i t y ，t h ea n o m a l yi n t r u s i o nd e t e c t i o ns y s t e mc a nt e l lt h e e x i s t e n c eo fi n t r u s i o nb e h a v i o r ；b u ti nt h ep r o c e s so fc r e a t i n gt h en o r m a lp a t t e r n s ， t h ea n o m a l yi n t r u s i o nd e t e c t i o n s y s t e mw i l lb ei n t e r f e r e db yt h ei n t r u s i o n b e h a v i o r t h e r e f o r e ，t h es y s t e m sn o to n l yt r e a ts o m eo ft h o s ei n t r u s i o nb e h a v i o r s a st h en o r m a lp a t t e r n s ，b u ta l s oc a nn o tt e l lt h er a n d o mb e h a v i o ro ft h eu s e ra n d g i v eaw r o n gr e s u l t s oi ti sr e q u i r e dt h a tt h e r es h o u l db ean e wi n t r u s i o n d e t e c t i o ns y s t e mt oc h a n g et h es i t u a t i o n a i m e da ts o l v i n gas e r i e so fp r o b l e m so ft h ec u r r e n ti n t r u s i o nd e t e c t i o n s y s t e m s ，ar e s e a r c hi sm a d ef o rt h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mi nt h e i i i i n t r u s i o nd e t e c t i o n s y s t e m i nt h i st h e s i s i ta n a l y z e st h es t a n d a r dg e n e t i c a l g o r i t h mh a v i n gt h ed i s a d v a n t a g e s o fs e a r c h i n gf o ral o n gt i m ea n dt h e p r e c o c i o u s ”c o n v e r g e n c e ，t h e nf o u n d i n g o u tt h ec a u s ei st h a tt h es t a n d a r d g e n e t i ca l g o r i t h md i s p l a ye f f e c t i v eg e n e sl o s t i n t h ep r o c e s so fr u n n i n g t h e a u t h o ra p p l i e sa b s o l u t eh a m m i n gd i s t a n c et ot h ep r o c e s so ft h ei n i t i a lp o p u l a t i o n ； w h i c hi m p r o v e si n i t i a lp o p u l a t i o nd i s t r i b u t i o no ft h ei n d i v i d u a l sa n dp r o p o s e s m i s s i n gg e n e t i ct e s t i n ga n dr e p a i rs t r a t e g y f o rc r b s s o v e ra n dm u t a t i o no p e r a t o r i m p r o v e s ，i tp u t sf o r w a r ds e l f - r e p a r a t i v ec r o s s o v e ra n dm u t a t i o nr a t e i ta p p l i e s ”e l i t e ”p r o t e c t i o ns t r a t e g yt os p e e du pt h er u n n i n gs p e e do fa l g o r i t h m s o nt h i s b a s i s t h ea u t h o rp u t sf o r w a r da ni m p r o v e dg e n e t i ca l g o r i t h m ，s e l f - r e p a r a t i v e & a d a p t i v eg e n e t i ca l g o r i t h mw h i c hi tb r i n g sm i s s i n gg e n e t i ct e s t i n ga n dr e p a i r s t r a t e g y a n dt h r o u g h f u n c t i o nt e s t ，i tv e r i f i e st h a tt h ea d a p t i v e g e n e t i c a l g o r i t h mw h i c hs p e e d s e a r c ha n dg e th i g h e rp r o b a b i l i t yo fg l o b a lo p t i m a l s o l u t i o nf a s t e rt h a nt h es t a n d a r dg e n e t i ca l g o r i t h m f i n a l l y , i ta p p l i e s t h ei m p r o v e dg e n e t i ca l g o r i t h mi nn e t w o r ki n t r u s i o n d e t e c t i o n ；a n dp r o p o s e san e t w o r ki n t r u s i o n d e t e c t i o ns y s t e mb a s e do nt h e i m p r o v e dg e n e t i ca l g o r i t h m u n d e rt h ec i r c u m s t a n c e so ft h es a m ee v o l u t i o n a r y g e n e r a t i o n sa n ds c a l e o fr u l eb a s e ，t h en e t w o r ki n t r u s i o nd e t e c t i o ns y s t e m b a s e do ni m p r o v e dg e n e t i ca l g o r i t h mg e n e r a t e sr u l e sq u i c k e rt h a nt h en e t w o r k i n t r u s i o nd e t e c t i o ns y s t e mb a s e do ns t a n d a r dg e n e t i ca l g o r i t h m w i t ht h es c a l eo f t h er u l eb a s ei n c r e a s i n g ，t h ec o s to fg e n e r a t i n gr u l e si n c r e a s e sf o rb o t ho ft h e s y s t e m s b u tt h e i n t r u s i o nd e t e c t i o ns y s t e mb a s e d o nt h ei m p r o v e dg e n e t i c a l g o r i t h ms i g n i f i c a n t l y r e d u c e st h er a t eo ff a l s ea l a r m ，s h o r t e n st h et i m e o f d e t e c t i o no b v i o u s l y , a n di m p r o v e st h ed e t e c t i o nr a t e sa p p a r e n t l y s o ，l t i s i m p r o v e dt h a tt h en e t w o r ki n t r u s i o nd e t e c t i o ns y s t e mb a s e do nt h ei m p r o v e d g e n e t i ca l g o r i t h mi se f f e c t i v e k e y w o r d s n e t w o r k s e c u r i t y ，i n t r u s i o n d e t e c t i o n s y s t e m ，g e n e t i ca l g o r i t h m ， c r o s s o v e ro p e r a t o r ，m u t a t i o no p e r a t o r i v 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于改进遗传算法的网络入 侵检测的研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名： 眺吁月届 哈尔滨理工大学硕士学位论文使用授权书 基于改进遗传算法的网络入侵检测的研究系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密厂 ，在年解密后适用授权书。 不保密孵。 ( 请在以上相应方框内打) 作者签名： 隰峰弓月俘日 导师签名雾阔司胁砌7 夥月尹 哈尔滨理工大学工学硕士学位论文 1 1引言 第1 章绪论 上世纪九十年代以来，i n t e r n e t 持续高速的发展，极大地加快了社会信 息化的步伐。随着计算机技术和通信技术在金融、政府、医疗、制造业、商 业、教育各界的广泛应用，网络安全问题已经越来越受人们重视。借助于计 算机网络环境实现了跨地区的电子银行、电子商务、电子政务、金融网络制 造资源管理和网络虚拟社区等多种应用。但是，网络的开放性也为信息的窃 取、盗用、非法修改以及各种扰乱破坏提供了可乘之机，使得信息在存储、 处理和传输等各个环节，都有可能遭到入侵者的攻击或病毒的危害，造成系 统的瘫痪或重要数据的丢失。为了保护网络和系统的安全，人们针对信息 的存储、处理和传输的各个环节使用了各种安全技术。但是人们发现使用单 一的安全技术是不可靠的，只有将多种安全技术综合地使用在一个整体的安 全方案中，才可以尽可能地保护信息和系统的安全。 入侵检测系统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 ) 正是在这种背景下，经过 了近几十年的发展成为安全领域内的重要技术和研究方向。 1 2 网络安全的基本概念 网络安全从其本质上来讲就是网络上的信息安全。凡涉及到网络上信息 的保密性、完整性、可用性、真实性等相关的问题，都属于网络安全研究的 领域。通常指网络系统的软硬件及其系统中的数据受到保护，不受偶然的或 者恶意的原因而遭到破坏、更改、泄漏、使系统连续可靠地运行，保证网络 服务不中断。网络安全包括物理安全和逻辑安全两个方面，其中物理安全指 系统设备及相关设施的物理保护以免于被破坏和丢失，逻辑安全是指信息的 可用性、完整性和保密性三要素。信息安全的隐患存在于信息的共享和传递 过程中，而如果信息不能进行交换将失去其价值。 1 2 1 网络安全现状及主要威胁 2 0 世纪互联网的出现改变了人类的沟通和信息传递的方式，随着网络 哈尔滨理工大学 _ 学硕士学位论文 经济时代的到来，网络将会成为一个无处不有、无所不用的工具。然而，伴 随着网络规模的日益发展，网络安全令人关注。据公安部统计，2 0 0 4 年在 对7 0 7 2 家重要信息网络、信息系统使用单位中，发生网络安全事件的比例 为5 8 。其中，发生1 次的占总数的2 2 ，2 次的占13 ，3 次以上的占 2 3 。发生的网络安全事件中，计算机病毒、蠕虫和木马程序造成的安全事 件占发生安全事件单位总数的7 9 ，拒绝服务、端口扫描和篡改网页等网 络攻击事件占4 3 ，大规模垃圾邮件传播造成的安全事件占3 6 ，5 4 的被 调查单位网络安全事件造成的损失比较轻微，损失严重和非常严重的占发生 安全事件单位总数的1 0 “1 。 网络安全的主要威胁来自如下几个方面： 1 网络缺陷i n t e r n e t 由于它的开放性，迅速在全球范围内普及，但也正 是因为它的开放性使其在保护信息安全方面存在不足。i n t e r n e t 最初的设计 主要是基于资源共享，而没有过多的考虑安全问题，缺乏相应的安全监督机 制。 2 病毒病毒时刻威胁着整个互联网的安全。像2 0 0 7 年“熊猫烧香”的 爆发就造成了极大的破坏，促使人们不得不在网络的各个环节考虑对于各种 病毒的检测防治，对病毒彻底防御的重要性毋庸置疑。 3 管理不足和资源滥用很多联网的企业缺乏对于网络安全的足够认 识，管理上存在很多漏洞，有的只是提供了接入i n t e r n e t 的通道，对于网络 上黑客的攻击缺乏基本的应对措施，同时企业内部存在资源滥用现象，这是 造成网络安全问题的根本原因。 4 黑客攻击随着网络的扩大，网上的黑客也越来越多，也越来越猖 獗；与此同时黑客技术逐渐被越来越多的人掌握。现在还缺乏针对网络犯罪 卓有成效的反击和跟踪手段，并且黑客攻击的隐蔽性好，“杀伤力”强。 5 软件漏洞和后门随着c p u 的频率越来越高，软件的规模越来越大， 软件系统中的漏洞也不可避免的存在。例如微软开发的w i n d o w s 系列的操 作系统也存在各种各样的安全漏洞和“后门”。 6 网络资源滥用网络有了安全保证和带宽管理，依然不能防止员工对 网络资源的滥用。在美国，9 7 的公司发现员工有滥用互联网的行为。网上 聊天，游戏，炒股等行为极大地降低了员工的工作效率。管理层希望员工更 加有效地使用互联网，尽量避免网络对工作带来负面影响。这时信息审计系 统应运而生，帮助企业提升互联网生产率。多数对工作效率敏感的企业已经 开始部署信息审计系统。 哈尔滨理工大学工学硕士学位论文 7 网络内部用户的误操作和恶意行为对于来自网络内部的攻击，主流 的网络安全产品防火墙基本无能为力，这类攻击及误操作行为需要网络信息 审计、i d s 等主要针对内部网络安全的安全产品来抵御。 8 信息泄漏恶意、过失的不合理信息上传和发布，可能会造成敏感信 息泄漏、有害信息扩散，危及社会、国家、团体和个人利益。更甚有基于竞 争需要，利用技术手段对目标机信息资源进行窃取。 网络安全的威胁种类随着网络的越来越广泛的应用会逐渐增多，在此基 础上，我们应该针对现有的网络威胁和预防以后的网络安全问题做出准备， 那就是网络安全技术的发展。 1 2 2 网络安全相关技术 目前的网络安全技术主要使用一下几种安全机制： 1 加密机制加密是一种最基本的安全机制，它能防止信息被非法读 取。加密是一种在网络环境中对抗被动攻击的行之有效的安全机制。数据加 密是保护数据最基本的方法。但是，这种方法只能防止第三者获得真实数 据，仅解决了安全问题的一个方面。而且，加密机制并不是牢不可破的。 2 数据签名机制签名与加密很相似，一般是签名者利用秘密密钥( 私钥) 对需要签名的额数据进行加密，验证方利用签名者的公开密钥( 公钥) 对签名 数据做解密运算。如图1 1 所示，签名可以实施在一个完整的数据包上，也 可以实施在某条信息( 或某块数据) 的校验和上，这可以根据不同的应用需求 来确定。如果能保证一个签名者的签名只能唯一地从他自己产生，那么当收 发双方发生争议的时候( 例如接收方收到了某条消息，而发送方却否认曾经 发过这个消息) ，仲裁机构就能根据消息上的数字签名来裁定这个消息是否 确实是由发送方发出的。 3 系统脆弱性检测目前已知的大多数网络安全漏洞都是针对特定操作 系统的，所以识别远程主机操作系统对于实现攻击非常重要。扫描器是一种 自动检测远程主机或本地主机安全脆弱点的程序，通过使用扫描器可以不留 痕迹的发现本地或远程服务器的各种t c p 端口的分配及提供的服务和他们 的软件版本。一个好的扫描器能对它得到的数据进行分析，帮助管理员查找 目标主机的漏洞。 4 访问控制机制访问控制是根据网络中主体和客体之间的访问授权关 系，对访问过程做出限制，可分为自主访问控制和强制访问控制。自主访问 哈尔滨理工大学工学硕士学位论文 控制主要基于主体及其身份来控制主体的活动，能够实施用户权限管理、访 问属性( 读、写、执行) 管理等。强制访问控制则强调对每一主、客体进行密 级划分，并根据主体和客体的分类之间的关系来控制访问。访问控制一般以 这些机制为基础：( 1 ) 口令，( 2 ) 安全标记，( 3 ) 访问控制数据库，( 4 ) 能力表 ( 决定主体对客体访问的权利的凭证) 。 明文p签名文s 发 入 签名 送 入 签名解释 入 接 收 方 v s 2 f ，k d ) v p = f ( s ，k e ) v 方 图i 1 数据签名原理图 f i g 1 - 1d i g i t a ls i g n a t u r ep r i n c i p l e 注：密钥k e ，k d 由发送方编制，k e 可以公开，k d 必须由发送方保管 5 认证机制认证是以交换信息的方式来确认实体身份的机制，是进行 存取控制所不可缺少的条件，因为不知道用户是谁，就无法判断其存取行为 合法性，用于认证的技术主要有：( 1 ) 口令机制，( 2 ) 安全协议机制，( 3 ) 使用 密码机制，( 4 ) 使用实体的特征或实体所用的物件。 6 防火墙防火墙实现将定义好安全策略转换成具体的安全控制操作， 它使得内部网络与因特网之间或者与其它外部网络相互隔离、限制网络互 访。防火墙对流经它的网络通信进行扫描，这样能够过滤掉一些攻击，以免 其在目标计算机上被执行。防火墙还可以关闭不使用的端口。而且它还能禁 止特定端口的流出通信，封锁特洛伊木马。最后，它可以禁止来自特殊站点 的访问，从而防止来自不明入侵者的所有通信。防火墙的实现从层次上大概 分为两种：报文过滤和应用层网关。 7 入侵检测系统( 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 ，简 4 哈尔滨理工大学工学硕士学位论文 称i d s ) 是入侵检测的软件和硬件的组合。与其他安全产品不同的是，入侵 检测系统要求更加智能化，它要能够将得到的数据进行分析，并得出有用的 结果，然后做出相应的反应。一个好的入侵检测系统能大大的缩减网络管理 员的工作量，保证网络安全的运行口1 。 1 3 课题来源、研究背景和现状 1 3 1 课题来源 本课题来源于黑龙江省自然基金项目：基于漏洞库的智能入侵防御系 统，兹在建立一套既能有效检测攻击，又能及时阻断攻击的智能入侵防御系 统。 1 3 2 研究的目的与意义 随着i n t e r n e t 的飞速发展，信息时代向人们展现出了巨大的魅力。 我们的社会生产和日常生活无一不从i n t e r n e t 的开放式结构中受益匪 浅。小小的一台计算机把我们连向了世界，也把世界连向了我们， i n t e r n e t 逐渐成为整个社会基础设施中最重要的部分之一。但就是我们 愈来愈深的感受到开放所带来的巨大便利，并由此产生对计算机网络越来越 强的依赖性时，却不得不面对信息安全问题日益严峻的考验。网络本身是不 安全的，随着网络互联的进一步发展，这种不安全性日益加剧，对社会的影 响也愈来愈大。随着网络互联的范围越来越广，社会对网络的依赖性也越来 越强，与此同时安全隐患对社会的影响也越来越大。随着电子政务、电子商 务、网上娱乐等一系列网络应用的蓬勃发展，网络越来越深地渗透到金融、 商务、国防等许多关键领域，网络与信息安全已上升为一个事关国家政治稳 定、社会安定、经济有序运行和社会主义精神文明建设的全局性问题。黑客 攻击技术的隐蔽性、攻击的智能化、攻击的手段和范围、攻击知识的复杂性 都在动态的变化中。仅仅依靠现有的安全防御技术，像防火墙、数据加密以 及传统的i d s 等，由于缺乏主动的技术适应网络攻击，在时效性方面存在 延迟。 遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变 异、等一系列遗传操，从而产生出新一代的群体，并逐步使群体进化到包含 哈尔滨理工大学工学硕士学位论文 或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优 点而被众多的应用领域所接受，并在自适应控制、组合优化、模式识别、机 器学习等领域得到了广泛的应用”1 。本文将遗传算法应用在入侵检测系统 中，在历史数据的基础上，通过遗传算法，自动形成新的入侵检测规则。在 这个实现中，同时考虑网络连接的时间和空间的因素，将这两个因素都编码 到入侵检测的规则中。这有利于判断复杂的异常行为。本文提出的实现都是 针对t c p i p 协议的。由于入侵检测系统的特殊性，属于多目标问题，要求 遗传算法能够同时找到多个局部最优解，而传统的遗传算法是用于寻找单个 全局最优解的。本文提出了一种新的结合了种群多样性概念的遗传算法，希 望建立一套高效的入侵检测系统。 1 3 3 国内外在该方向的研究现状及分析 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生 物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法， 它是有美国m i c h i g a n 大学j o h nh o l l a n d 教授于1 9 7 5 年首先提出来的，并出 版了颇有影响的专著( ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) ，g a 这 个名称才逐渐为人所知，j o h nh o l l a n d 教授所提出的g a 通常为简单遗传算 法( s g a ) 。遗传算法是从代表问题可能潜在的解集的一个种群( p o p u l a t i o n ) 开 始的，而一个种群则由经过基因( g e n e ) 编码的一定数目的个体( i n d i v i d u a l ) 组 成。每个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗 传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某种基因 组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制 这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因 型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简 化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理， 逐代( g e n e r a t i o n ) 演化产生出越来越好的近似解，在每一代，根据问题域中个 体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借助于自然遗传学的遗传算 子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ，产生出代表 新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代 更加适应于环境，末代种群中的最优个体经过解码( d e c o d i n g ) ，可以作为问 题近似最优解”。 进入9 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应 哈尔滨理工大学工学硕士学位论文 用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃， 不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显 著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法 在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活 力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工 程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注 目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法 从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭 新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识 优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推 理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓2 1 世纪中 新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分 活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体 系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新 研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生 命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对 象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划 ( e v o l m i o np r o g r a m m i n g ，e p ) 以及进化策略( e v o l u t i o ns t r a t e g y ，e s ) 等进化计算 理论日益结合。e p 和e s 几乎是和遗传算法同时独立发展起来的，同遗传 算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算 法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结 合的探讨正形成热点。 1 9 9 1 年d w h i t e y 在他的论文中提出了基于领域交叉的交叉算子 ( a a j a c e n c yb a s e dc r o s s o v e r ) ，这个算子是特别针对用序号表示基因的个体的 交叉，并将其应用到了t s p 问题中，通过实验对其进行了验证。 d h a c k l e y 等提出了随即迭代遗传爬山法( s t o c h a s t i ci t e r a t e d g e n e t i ch i l l c l i m b i n g ，s i g h ) 采用了一种复杂的概率选举机制，此机制中由m 个“投票 者”来共同决定新个体的值( m 表示群体的大小) 。实验结果表明，s i g h 与 单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现 出更好的性能，而且总体来讲，s i g h 比现存的许多算法在求解速度方面更 有竞争力。h b e r s i n i 和g s e r o n t 将遗传算法与单一方法( s i m p l e xm e t h o d ) 结 合起来，形成了一种叫单一操作的多亲交叉算子( s i m p l e xc r o s s o v e r ) ，该算子 在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对 哈尔滨理工大学工学硕士学位论文 三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交 叉、均匀交叉做了比较，结果表明，三这交叉算子比其余两个有更好的性 能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2 0 0 2 年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传 策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移 算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题。 2 0 0 4 年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率 不高的现象，提出了一种用基因块编码的并行遗传算法( b u i l d i n g b l o c k c o d e dp a r a l l e lg a ，b c p g a ) 。该方法以粗粒度并行遗传算法为基本框架，在 染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色 体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一 轮以相同方式演化的初始群体。2 0 0 5 年，江雷等针对并行遗传算法求解 t s p 问题，探讨了使用弹性策略来维持群体的多样性，使得算法跨过局部收敛 的障碍，向全局最优解方向进化。 本文在遗传算法的基础上对其进行了改进，然后把改进的遗传算法应用 与入侵检测，兹在建立一套高效快速的入侵检测系统。 1 4 本论文的工作 本论文将要进行的工作： ( 1 ) 对于目前的网络安全状况进行分析总结。研究入侵的种类及入侵的 过程。对于入侵的概念有较清晰的理解。 ( 2 ) 研究入侵检测系统的起源、分类( 基于不同原理的分类) 、系统的功 能。详细描述基于误用检测的和基于异常检测的入侵检测技术和目前比较流 行的入侵检测的研究方向。 ( 3 ) 分析遗传算法应用于入侵检测系统的不足，在此基础上对遗传算法 提出改进，并提出一种基于改进的遗传算法的网络入侵检测系统。 本文的重点在于改进遗传算法与入侵检测系统的有机结合，提高入侵检 测系统性能。作者将本文的内容安排如下：第一章是绪论，简单介绍网络安 全及网络安全技术的情况，分析入侵的种类及其特征。第二章是入侵检测系 统的描述，介绍入侵检测系统的定义、分类和目前主要的入侵检测技术，阐 述了本文的主要目的。第三章描述遗传算法的基本原理、特点其的一些应用 领域；然后分析遗传算法所存在的不足，然后对标准的遗传算法做相应的改 哈尔滨理工大学工学硕士学位论文 进，提出一种改进的遗传算法一带基因丢失识别及补救策略的自适应遗传 算法，并通过函数试验，验证自适应遗传算法比标准遗传算法有更快的搜索 速度和更高的得到全局最优解的概率。第四章讨论如何实现改进的遗传算法 在网络入侵检测中的应用，提出一个基于改进的遗传算法的入侵检测系统模 型。第五章通过实验验证它的可行性。最后是本文的结论。 哈尔滨理工大学工学硕士学位论文 第2 章入侵检测概述 2 1 入侵检测的产生与发展 2 0 世纪7 0 年代，随着计算机的速度、数量的增长以及体积的减小，对 计算机安全的要求显著增加。面对这样的形势，在1 9 7 7 年和1 9 7 8 年，美国 国家标准局召开了有政府和商业组织代表参加的会议，就当时的安全、审计 和控制状况提出报告。 1 9 8 0 年4 月，j a m e sp a n d e r s o n 为美国空军做了一份题为c o m p u t e r s e c u r i t yt h r e a tm o n i t o r i n ga n ds u r v e i l l a n c e ) ) ( 计算机安全威胁监控与监视) 的 技术报告，第一次详细阐述了入侵检测的概念。他提出了一种对计算机系统 风险和威胁的分类方法，并将威胁分为外部渗透、内部渗透和不法行为三 种，还提出了利用审计跟踪数据监视入侵活动的思想。这份报告被公认为是 入侵检测的开山之作”。 从1 9 8 4 年到1 9 8 6 年，乔治敦大学的d o r o t h yd e n n i n g 和s r i c s l ( s r i 公司计算机科学实验室) 的p e t e rn e u m a n n 研究出了一个实时入侵检测系统 模型，取名为i d e s ( 入侵检测专家系统) 。该模型由六个部分组成：主体、 对象、审计记录、轮廓特征、异常记录、活动规则。它独立于特定的系统平 台、应用环境、系统弱点以及入侵类型，为构建入侵检测系统提供了一个通 用的框架。 19 8 8 年，s r i c s l 的t e r e s al u n t 等人改进了d e n n i n g 的入侵检测模 型，并开发出了一个i d e s 。该系统包括一个异常检测器和一个专家系统， 分别用于统计异常模型的建立和基于规则的特征分析检测( 如图2 1 所示) 。 1 9 9 0 年是入侵检测系统发展史上的一个分水岭。这一年，加州大学戴 维斯分校的l - t h e b e r l e i n 等人开发出了n s m ( n e t w o r ks e c u r i t ym o n i t o r ) 。 该系统第一次直接将网络流作为审计数据来源，因而可以在不将审计数据转 换成统一格式的情况下监控异种主机。从此之后，入侵检测系统发展史翻开 了新的一页，两大阵营正式形成：基于网络的i d s 和基于主机的i d s 。 n s m 是u c d 设计的面向局域网的i d s ，n s m 被设计用来分析来自以太局 域网的数据及连接到该网的数据。这个系统重要贡献是首次使用网络数据包 作为审计数据源，提出基于网络的i d s 的概念。 哈尔滨理工大学工学硕士学位论文 1 9 9 1 年2 月在美国空军、国家安全局和能源部共同资助空军密码支持 中心、劳伦斯利弗摩尔国家实验室、加州大学戴维斯分校、h a y s t a c k 实验 室，开展对分布式入侵检测系统( d i d s ) 的研究，将基于主