（计算机应用技术专业论文）基于量子遗传和聚类技术的入侵检测系统研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重迭由g 电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：d 阶巾 签字日期：九刃年钼2 ，日 学位论文版权使用授权书 本学位论文作者完全了解 重庆蜜电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重废自g 电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：毒扛予中 签字日期：力冲年乡月龃 导师签名： 矽舯 签字嗍沙( 年几6 日 重庆邮电大学硕士论文摘要 摘要 随着信息技术的迅猛发展和人类社会生活对i n t e m e 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 fi n f o r m a t i o nt e c h n o l o g ya n dt h eg r o w i n g d e m a n do fh u m a n1 i f ef o ri n t e r n e t ，c o m p u t e ra n di n t e m e tt e c h n 0 1 0 9 yh a sb e e n i n n o v a t e da n du p g r a d e dc o n s t a n t l y t h er i s k so fn e t w o r ki n t r u s i o nh a sb e c o m e h i g h e ra n dh i g h e r ， a n dn e t w o r ks e c u r i t yh a sb e c o m ea9 1 0 b a lp r o b l e m i n t r u s i o n d e t e c t i o nt e c h n 0 1 0 9 yc a m ei n t ob e i n g i ti sa n o t h e ri m p o r t a n t s e c u r i t yt e c h n o l o g ya f t e rt h ef i r e w a l l ，d a t ae n c r y p t i o na n do t h e rt r a d i t i o n a l s e c u r i t ym e a s u r e s a sar e a s o n a b l ec o m p l e m e n ta n de x t e n s i o no ft h ef i r e w a l l t e c h n o l o g y j i n t r u s i o nd e t e c t i o ni sa na c t i v es e c u r i t y t e c h n o l o g y a n di t p r o v i d e sar e a l - t i m ep r o t e c t i o na g a i n s ti n t e m a la t t a c k s ，e x t e r n a la t t a c k sa n d m i s s - o p e r a t i o n b a s e do na b o v er e s e a r c hb a c k g r o u n d ，t h i sp 印e rf o c u s e so n m a n yp r o b l e m s t h a te x i s ti ni n t r u s i o nd e t e c t i o n e s p e c i a l l y w i t ht h e d i s a d v a n t a g e o fa d a p t i v e c a p a c i t y ， s l o w p r o c e s s i n gs p e e d o fd e t e c t i o n a l g o r i t h m ，t h el o wd e t e c tr a t ea n dh i g hm i s t a k ed e t e c t i o nr a t e a tf i r s t ，t h i s p a p e ri n t e g r a t e d t w od e t e c t i o nt e c h n 0 1 0 9 y e x c e p t i o n a n o m a l yd e t e c t i o na n dm i s u s a g em i s u s et o b u i l dam o d e lo fi n t r u s i o n d e t e c t i o ns y s t e m t h e nf o rt h ei m p l e m e n t a t i o no ft h ec o r ek e r n e lc o m p o n e n t s o ft h em o d e l ，t h eq u a n t u mg e n e t i ca l g o r i t h mw a si n t r o d u c e di n t oi n t r u s i o n d e t e c t i o nt od e a lw i t ht h ef e a t u r e sr e d u c t i o n ，f e a t u r ee x t r a c t i o n c o m b i n gw i t h t h ec l u s t e r i n ga l g o r i t h m ，ai n t r u s i o nd e t e c t i o na l g o r i t h mb a s e do nq u a n t u m g e n e t i cc l u s t e r i n gw a sp r o p o s e df b ri n t r u s i o nd e t e c t i o n i te n h a n c e da d a p t i v e a n a l y s i sa n dd e t e c t i o nc a p a c i t yo fs y s t e m ，r e d u c e dt h ec o s to ft h es y s t e m ， i m p r o v e dt h ep e r f o r m a n c eo ft h ew h o l es y s t e ma n da l s o i n c r e a s e dt h e r e u s a b i l i t yo fm o d u l e ss i m u l t a n e o u s l y f i n a l l y t h es i m u l a t i o nt e s tr e s u l t so f v a r i o u ss t a g e ss h o wt h a tt h ea l g o r i t h mh a sm a i n t a i n e dh i g hd e t e c tr a t ea n d r e d u c e dt h ef a l s ed e t e c t i o nr a t e i ta l s oi m p r o v e dt i m ec o m p l e x i t yg r e a t l y b e c a u s et h eq u a n t u mg e n e t i ca l g o r i t h ms t i l lh a sap o w e r f u ls p a c es e a r c h c a p a b i l i t i e sw i t hs m a l ls p e c i e s k e yw 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 ，q u a n t u mg e n e t i c a l g o r i t h m ，c l u s t e r i n ga l g o r i t h m i i ，- 重庆邮电大学硕士论文目录 目录 摘要1 a b s tr a c t ii 第一章绪论1 1 1 选题背景1 1 2 国内外研究现状1 1 3 存在问题3 1 4 论文组织结构4 第二章入侵检测及相关技术概述6 2 1 入侵检测概念6 2 2 入侵检测分类6 2 2 1 根据数据源的的不同6 2 2 2 根据检测方法的不同7 2 3 遗传算法及其在入侵检测中的应用9 2 3 1 遗传算法的特点9 2 3 2 量子遗传算法1 0 2 3 3 遗传算法的应用l o 2 4 数据挖掘技术及聚类算法在入侵检测中的应用1 1 2 4 1 数据挖掘技术在入侵检测中的应用1 1 2 4 2 入侵检测中常用的数据挖掘算法1 2 2 4 3 聚类算法在入侵检测中的应用1 3 2 5 本章小结15 第三章入侵检测模型的研究与设计1 6 3 1p d r r 模型1 6 3 2c i d f 模型1 6 3 3 本文i i d s 模型的设计与建立1 7 3 3 1 基于主机的i d s 工作原理1 7 3 3 2 基于网络的i d s 工作原理18 3 3 3i i d s 模型的设计1 8 3 3 4i i d s 模型中分析检测模块的建立2 0 3 4 本章小结2 2 第四章基于量子遗传算法的预处理研究2 3 4 1i i d s 模型中的预处理过程2 3 4 2 量子遗传算法原理2 4 i i i 重庆邮电大学硕士论文目录 4 2 1 传统遗传算法与量子遗传算法比较2 5 4 2 2 量子位的表示2 6 4 2 3 量子旋转门2 7 4 3 基于q g a 算法的特征约减2 7 4 3 1 算法实现步骤2 7 4 3 2 算法描述3 2 4 4 仿真实验3 3 4 4 1k d d c u p 9 9 数据集3 3 4 4 2 算法测试3 5 4 5 本章小结3 6 第五章基于量子遗传聚类的检测分析研究3 8 5 1i i d s 模型中的检测分析过程3 8 5 2 基于c q g a 算法的检测分析3 8 5 2 1 距离度量3 9 5 2 2 算法实现步骤4 0 5 2 3 算法描述一4 2 5 3 仿真实验4 3 5 3 1 实验方案一4 3 5 3 2 实验方案二4 5 5 4 基于q g a 算法的特征提取4 8 5 4 1 算法实现步骤4 8 5 4 2 算法描述5 0 5 5 仿真实验5 1 5 6 本章小结5 3 第六章总结与展望5 4 6 1 总结5 4 6 2 展望5 4 致谢5 6 攻读硕士学位期间从事的科研工作5 7 参考文献5 8 i v 重庆邮电大学硕士论文第一章绪论 1 1 选题背景 第一章绪论 随着信息技术的迅猛发展和人类社会生活对i n t e r n e t 需求的日益增 长，计算机与互联网科技得以不断的创新与升级。截至到2 0 0 8 年6 月底， 我国网民数量达到2 5 3 亿，首次大幅度超过美国，跃居世界第一位。随 着政府信息化基础建设的推进，如何能保证信息化社会的正常安全平稳的 运转，其中信息网络的安全是最重要的环节之一，必须不断深化。由我 国国家计算机网络应急技术处理协调中心( n a t i o n a lc o m p u t e rn e t w o r k e m e r g e n c yr e s p o n s e t e c h n i c a lt e a m c 0 0 r d i n a t i o nc e n t e r o fc h i n a ， c n c e r t c c ) 提供的数据( 如图1 1 所示) 可以看出，网络仿冒、漏洞攻击、 网页恶意代码等黑客入侵手段在安全事件中仍占有较大的比例，因此入侵 检测( i n t r u s i o nd e t e c t i o n ，i d ) 【2 】技术作为信息系统安全保障防御体系中的 一个重要组成部分扮演着越来越重要的角色。 图1 12 0 0 8 年上半年度网络安全事件类型分布 1 2 国内外研究现状 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 、，e i l l a n c e ( 计算机安全威胁监控与监视) 重庆邮电大学硕士论文 第一章绪论 的技术报告，第一次详细阐述了入侵检测的概念【3 】。这份报告被公认为是 入侵检测的开山之作。 19 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 设计了一个实时入侵检测系统模型，取 名为入侵检测专家系统( 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 ) 4 1 。该模 型由六个部分组成：主体、对象、审计记录、轮廓特征、异常记录、活动 规则。它独立于特定的系统平台、应用环境、系统弱点以及入侵类型，为 构建入侵检测系统提供了一个通用的框架。 1 9 8 8 年i n t e r n e t 蠕虫事件后，网络安全引起了军方、学术界和企业界 的高度重视。19 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 ) ，该系统首次直接 将网络数据流作为审计数据来源。这一年是入侵检测系统发展史上的一个 分水岭，从此之后，入侵检测系统从单一的基于主机的入侵检测系统 ( h o s t - b a s e di n t r u s i o nd e t e c t i o ns y s t e m ，h i d s ) 向结合h i d s 和基于网络的 入侵检测系统( n e t w o r k b a s e di n t r u s i o nd e t e c t i o ns y s t e m ，n i d s ) 的转变【5 】。 1 9 9 0 年，m a c c a b e 最早把遗传算法引入入侵检测中【6 1 。他提出应用遗 传方法来搜索整个度量子空间，以寻找正确的度量子集。 1 9 9 4 年普渡大学计算机系c o a s 一7 】实验室研究了遗传算法在入侵检 测中的应用，使用遗传算法构建的智能代理程序能够识别入侵行为，而且 这些代理具有学习用户操作习惯的初步智能a 1 9 9 9 年哥伦比亚大学计算机系研究室、e n k el e e 提出了一个全新的概 念即把数据挖掘技术应用于入侵检测系统之中【8 】，此方法能够提高系统的 检测率，而不会降低目前任何一种检测模型的其他效能。 2 0 0 0 年，b r i d g e s 等人提出了一个新的方法，把模糊数据挖掘技术和 遗传算法结合起来检测网络误用和异常【9 】。 2 0 0 3 年，刘勇国等人提出了一种基于遗传聚类的入侵检测算法【i o 】。 该算法为一种混合算法，通过最近邻聚类方法和遗传算法相结合来共同检 测异常数据，但对于遗传算法只应用了一般的遗传策略，对不同的入侵行 为的检测波动性较大。 2 0 0 5 年，h a r i r i 等人提出了一种应用信息理论和遗传算法共同检测异 常行为的方法【1 1 1 。基于网络特征和网络入侵类型的共有信息，少量网络特 征和网络攻击非常一致，然后应用选择的特征和遗传算法产生线性结构的 规则。但是，此方法只考虑了不连续特征，没有考虑到连续特征的问题。 目前入侵检测系统得到了长足的进步，国内外也出现了一些技术比较 2 成熟的产品，比较有代表性的产品有i s s ( i n t e r n e ts e c u r i t ys y s t e m ) 公司的 r e a l s e c u r e ，n a i ( n e t w o r ka s s o c i a t e s ，i n c ) 公司的c y b e r c o pm o n i t o r 和c i s c o 公司的n e t r a n g e r ，国内有启明星辰公司的天阗入侵检测系统、安氏( 中国) 公司的l i n k t r u s t 入侵检测系统等。与国外相比，国内产品的差距还很大， 总体发展比较慢，检测技术单一，大多以仿国外产品为主。因此，系统地 研究入侵检测技术和方法是非常必要的。 1 3 存在问题及解决方案 目前入侵检测系统( 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 】： 1 ) 系统结构缺陷 目前几乎所有的i d s 都是在基于误用检测技术和基于异常检测技术的 基础上发展而来的，在基于误用检测技术的i d s 中存在特征知识库建立困 难的缺点，而在基于异常检测技术的i d s 中存在构建行为轮廓模型困难的 缺点，因此两种模型的融合以及寻求新的数据源来构建新型的系统模型也 逐步成为人们研究的目标； 2 ) 缺乏可扩展性和自适应性 目前i d s 的可扩展性和自适应性对于今天的网络环境来说非常重要， i d s 需要有可扩展性来与新的模块配合工作，且i d s 自身也必须能够经常 自我更新，以检测新的入侵行为。依据定期改进检测技术、裁剪入侵检测 机制，对于i d s 存在很大的困难； 3 ) 系统维护困难 对目前i d s 的维护通常需要特殊的知识和足够的努力。例如，误用检 测一般由专家系统来实现，用特征知识库来进行模式匹配，对特征知识库 的更新涉及专家系统的细节和描述知识库的语言，对于网络管理员来讲维 护是比较困难的。所以将多种技术相融合，探索新的实现方法来完善入侵 检测功能是现在和未来研究的发展方向； 4 ) 易被欺骗性 基于网络的i d s 使用一般的网络协议栈来对受保护主机的协议栈行为 进行建模和评价网络数据包，攻击眷可利用协议栈的差异，向目标主机发 送让i d s 处理困难的数据包，以达到进入目标主机的目的； 5 ) 响应能力欠缺 传统的i d s 更重视对攻击的检测而不是响应，其实使系统管理员及时 分析来自i d s 的警告并采取合适的行动是非常必要的。 综上所述，针对i d s 目前所存在诸多问题，尤其是具有自适应能力、 能自学习的i d s 还不完善等缺点，本文着重对系统的自适应性弱和系统维 护困难等问题进行解决，并提出本文的系统模型以改善以往系统模型中存 在的缺陷。 在传统的异常检测技术中，需要构造一个系统正常行为轮廓的参考模 型，然后检查系统的运行情况，若与给定参考模型存在较大的偏差，则认 为系统受到了入侵攻击【1 3 】，但是设置恰的特征轮廓和异常警报的门限值是 相当困难的。因此，本文将量子遗传算法引入入侵检测领域，并与聚类算 法相结合，提出了一种改进的检测算法，以增强系统自适应分析、检测的 能力；同时，为了完善系统的功能，还将量子遗传算法引入预处理阶段和 特征知识库建立阶段，提高了整个系统的性能和模块的复用性；最终，在 理论算法研究和功能模块实现的基础上，提出了本文的入侵检测框架模 型，对入侵检测系统的研究有着实际意义的作用。 1 4 论文组织结构 通过以上对i d s 存在问题及解决方案的论述，本文采取以下的组织结 构，其中正文共分为6 个章节： 第1 章主要分析计算机网络系统的安全性和主要面临的威胁，叙述 入检测的发展与研究现状，并对现今i d s 所存在的缺点及本文所要针对解 决的问题进行阐述，同时指出本论文的主要内容及结构； 第2 章主要介绍了入侵检测技术及其应用领域的相关理论，包括入 侵检测概念、技术以及系统的分类，同时，详细介绍了传统遗传算法、量 子遗传算法和数据挖掘中聚类算法的理论背景知识及其在入侵检测中的 应用与研究情况，为本文的研究提供了充分的理论依据； 第3 章主要介绍了本文i d s 模型的研究与设计，在详细分析c i d f 模型的基础上，综合异常与误用两种检测技术的优点，提出了本文的i d s 框架模型( i i d s ) ，并详细论述了本文重点研究与实现的三大组件，为本文 相应算法的研究提供了系统级的支持； 第4 章主要介绍了针对本文系统模型中预处理阶段特征约减组件的 研究与实现。将量子遗传算法引入入侵检测领域进行特征约减，在理论研 4 究的基础上，结合本领域的特殊性对算法中的关键步骤进行了详细研究与 设计，如适应度函数的设计与进化策略的制定等，并通过仿真实验进行了 论证，同时也为下一步聚类分析打下基础； 第5 章主要介绍了针对模型数据分析组件和特征提取组件的研究与 实现，是整个模型中最核心的部分。在对q g a 算法和聚类算法的研究基 础上，提出了一种改进的基于量子遗传聚类的算法( c q g a ) ，并详细阐述 了算法具体实现的步骤，然后对预处理阶段q g a 算法进一步研究，将其 应用于特征提取阶段，为特征知识库的建立做必要的准备，最后通过仿真 实验对两部分组件分别进行了测试，并取得良好的效果； 第6 章全文的结论部分，主要总结了本课题的研究成果，并展望了 未来研究的方向。 重庆邮电大学硕士论文 第二章入侵检测及相关技术概述 第二章入侵检测及相关技术概述 2 1 入侵检测概念 入侵检测( i n t r u s i o nd e t e c t i o n ，i d ) 是对入侵行为的检测。它通过收集 和分析网络行为、安全日志、审计数据、其它网络上可以获得的信息以及 计算机系统中若干关键点的信息，检查网络或系统中是否存在违反安全策 略的行为和被攻击的迹象。 入侵检测是一种主动安全防护技术，提供了对内部攻击、外部攻击和 误操作的实时保护，在系统受到危害之前拦截和响应入侵。并且可以在不 影响网络性能的情况下对网络进行监测，是防火墙的合理补充，因此被认 为是防火墙之后的第二道安全闸门。 2 2 入侵检测分类 目前入侵检测的分类，可以根据数据来源、检测方法、分析的实时性、 系统结构等有着不同的分类方法，但大多数是基于数据源和检测方法的不 同进行的分类【14 1 。 2 2 1 根据数据源的不同 根据数据来源的不同，入侵检测通常可以分为三类：基于主机的入侵 检测系统( h o s ti n t r u d ed e t e c ts y s t e m ，h i d s ) 、基于网络的入侵检测系统 ( n e t w o r ki n t r u d ed e t e c ts y s t e m ，n i d s ) 和采用混合数据源的分布式入侵检 测系统( d i s t r i b u t e di n t r u d ed e t e c t i o ns y s t e m ，d i d s ) 。 1 ) 基于主机的入侵检测系统 h i d s 通过对主机的系统审计日志以及网络实时连接进行智能分析和 判断，在系统审计日志文件中寻找攻击特征，然后给出统计分析报告。一 般用于保护关键应用的服务器，实时监视可疑的连接、系统日志、非法访 问等。 6 重庆邮电大学硕士论文第二章入侵检测及相关技术概述 由于h i d s 通常采用查看针对可疑行为的审计记录来进行检查，所以 它能够将最新的记录与攻击特征进行比较，并检查不应该改变的系统文件 的校验以此来分析系统是否被攻击【1 5 】，因此说实时性是h i d s 的一个显著 优点，但是h i d s 只能检测本主机上发生的入侵行为【1 6 】【17 1 ，并且能否及时 采集到系统的审计记录直接影响了检测效果，这些均是h i d s 存在的缺点； 2 ) 基于网络的入侵检测系统 n i d s 用于实时监控网络关键路径的信息【l 引，它利用工作在混杂模式 下的网卡，对共享网段上原始的数据包进行实时监视和分析来发现可疑的 行为，一旦检测到攻击，响应模块将按照配置对攻击做出反应。因此n i d s 不需要主机提供严格的审计数据，对主机资源消耗少，并且可以提供对网 络通用的保护而无需顾及异构主机的不同架构； 3 ) 采用混合数据源的分布式入侵检测系统 由于h i d s 和n i d s 各有优缺点，为了获得更好的检测效果，将两者 结合起来，进行优势互补的d i d s 逐步引起了人们的重视，成为了当前入 侵检测研究的趋势之一。d i d s 由分布在网络主机上的多个部件组成，能 够同时分析来自主机系统审计日志和网络数据流，通过数据收集和数据分 析的分布式处理，能够提高检测系统应对协作入侵攻击【1 9 】【2 0 1 和日趋分散化 的系统漏洞【2 1 】【2 2 】的能力。 2 2 2 根据检测方法的不同 根据检测方法的不同，入侵检测通常可以分为两大类：误用检测 ( m i s u s ed e t e c t i o n ) 和异常检测( s i g n a t u r e - b a s e dd e t e c t i o n ) ，这两种入侵检测 技术在处理数据的方式上是互补的【23 1 。 1 ) 误用检测 误用检测技术，又称为基于知识的入侵检测技术或特征检测。该技术 建立在对过去各种已知入侵方法和系统缺陷知识的积累之上，首先要建立 包含已知入侵特征和系统缺陷的知识库，然后再通过收集到信息与已定义 好的入侵模式进行匹配，以此来判断是否有入侵行为的发生。 由于误用检测技术依据具体特征知识库进行判断，所以检测的准确率 高，误检率低，并且能够迅速可靠地判断特定攻击工具和技术的应用，为 系统管理员做出相应措施提供了方便。但是误用检测技术仅能检测已经定 义好的入侵行为，当未定义的攻击发生时，此类i d s 只有在更新知识库后 才能检测到新的攻击行为和系统漏洞，所以实时性不高，并且这种检测技 7 重庆邮电大学硕士论文第二章入侵检测及相关技术概述 术与具体系统依赖性太强，不但系统移植性不好，维护工作量大，而且将 具体入侵手段抽象成知识也是很困难的。总体说来，基于误用检测的i d s 由于具有容易实现的特点，所以在商业上有着广泛的应用【2 引。 误用检测技术常借助的方法有专家系统、状态转移分析、p e r t 网状态 转换、模型推理等。 2 ) 异常检测 异常检测技术，又称为基于行为的检测异常检测技术。该技术是假设 攻击者活动明显异常于正常主体的活动，对攻击行为的检测可以通过观察 那些偏离正常用户行为的方式来判断。根据这一理念人们常常使用统计的 方法首先对用户的行为进行统计分析，构建出主体正常活动状态下的行为 模型并不断的更新，然后将当前主体的活动情况于已构建的正常模型相比 较，如果其间的差异程度超过一定的阈值，则认为该活动为攻击行为。 异常检测技术的优点在于其通用性强、与系统相对无关且能抽象系统 正常的行为，从而不需要定义攻击和系统漏洞即可检测到未知的攻击行 为。但是由于用户的行为的随机性，往往使得统计抽象出的行为模型并不 能完全的描述出用户的正常行为，因此这种对用户行为随机性捕捉能力的 不足的问题会导致较高的误检率【2 4 1 。 异常检测技术常借助的方法有系统分析方法、神经网络、遗传算法、 数据挖掘、免疫学方法等。 在入侵检测技术的研究中，误用检测技术和异常检测技术是最主要的 两大技术，研究它们之间存在的优缺点，使其可以优势互补，概括来说有 以下几点： 1 ) 检测原理不同 误用检测是对已知入侵行为的标识，检测的效果取决于先验知识；异 常检测则可以对未知的入侵行为进行检测，更加的智能化； 2 ) 是否依赖于具体的入侵行为 误用检测多是通过对一些具体行为的判断和推理，从而检测出入侵行 为的；异常检测则是根据用户的正常行为或资源的使用状况来判断是否有 入侵，并非依赖具体的入侵行为； 3 ) 检测方法不同 误用检测通过具体的特征知识库进行判断，准确度高、速度快，但对 未知攻击的检测能力略显不足；误用检测可以发现未知的攻击，但是由于 系统正常行为模式的建立相对比较困难，因此容易造成误检； 4 ) 对系统要求不同 重庆邮电大学硕士论文第二章入侵检测及相关技术概述 误用检测过分依赖于主体的系统结构，可移植性不强；异常检测对系 统的依赖性相对较小。 2 3 遗传算法及其在入侵检测中的应用 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 创立于2 0 世纪7 0 年代初期，美国 密执根大学的h o l l a n d 教授于1 9 7 5 年首次提出了g a 算法的思想【25 1 ，它是 模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，通过自然 选择、遗传、变异等作用机制，从而实现各个个体适应性的提高，是一种 全局搜索和优化的算法，充分体现了自然界中“物竟天择、适者生存”的 进化过程。 2 3 1 遗传算法的特点 遗传算法是一类可用于复杂系统优化的全局搜索算法，与其他传统的 优化算法相比，主要有以下优点： 1 ) g a 算法不是直接作用在所处理问题空间的参数变量集上，而是利 用参数变量的某种编码形式。因此g a 算法可以对结构对象，如集合、序 列、矩阵、树、图、链、表等多种数据结构直接进行操作，这也是g a 算 法具有广泛应用领域的重要特点之一； 2 ) g a 算法直接以适应度作为搜索信息，无需导数等其它辅助信息， 使得g a 算法容易形成通用程序； 3 ) 在优化问题中，算法并行性的研究一直是关注的重点，传统的优化 方法一般是从一个点开始搜索，逐步寻找最优解，这样就很难克服多个极 值点的问题，容易陷入局部极值。而g a 算法可同时从多个点开始搜索， 降低了陷入次优解的可能性，非常有易于大规模并行化的运算； 4 ) g a 算法采用随机概率方法进行最优解搜索，算子都是随机操作， 而非确定性规则； 5 ) 强鲁棒性是g a 算法最突出的特点，由于初始集本身就带有大量与 最优解相差甚远的信息，通过基本算子的操作能迅速排除与最优解相差较 大的多余信息，这是典型的一个并行滤波机制。因此，g a 算法具备很高 的容错能力。 重庆邮电大学硕士论文第二章入侵检测及相关技术概述 2 3 2 量子遗传算法 量子遗传算法( q u a n t u mg e n e t i ca l g o r i t h m ，q g a ) 是将量子计算和遗传 算法相结合的一种算法【26 1 。a n a r a y a n a n 和m m o o r e 于1 9 9 9 年在其发表 的论文q u a n t u m i n s p i r e dg e n e t i ca l g o r i t h m 中首次提出了量子遗传的概 念【27 1 ，随后k h h a n 、k h p a r k 和c h l e e 等人又在p a r a l l e l q u a n t u m i n s p i r e dg e n e t i ca l g o r i t h mf o rc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s 一文中将q g a 算法用于求解组合优化问题，并且取得了较好的效果【2 引。 q g a 算法是以量子计算的一些概念和理论为基础，为了便于更加深入 理解q g a 算法，在此简单介绍一下相关量子力学的理论基础。 1 ) 光和微粒的波粒二象性： 通过光的干涉和衍射现象以及光的电磁理论两方面充分证明了光的 波动性。随后，爱因斯坦提出电磁辐射不仅在被发射和吸收时以五v 微粒形 式出现，还以这种形式以速度c 在空间运动，成功的解释了光电效应，这 种微粒和波动的双重性质被称为光的波粒二象性。 1 9 2 9 年，德布罗意提出微粒也具有波粒二象性的假说，并给出关系式： e = j 1 1 ，= j i l 国 ( 2 1 ) 尸= = 办 ( 2 2 ) 其中，e 为粒子的能量，p 为动量，1 ，为波的频率，名为波长。由该关 系式可知自由粒子的动量和能量都是常量。 2 ) 态迭加原理： 根据双狭缝衍射实验可知，用表示粒子穿过上面狭缝到达屏幕的状 态，用表示粒子穿过下面狭缝到达屏幕的状态，并用缈表示粒子穿过两 个狭缝到达屏幕的状态。那么y 就可以写成和的线性迭加，可表示为： 沙= c l + c 2 ( 2 3 ) 其中，q 和乞为复数，如果和y ：是体系中的某个可能状态，那么它 们的线性迭加缈也是这个体系中的某个状态，这就是量子力学中的态迭加 原理。 3 ) 纠缠态： 若复合系统的一个纯态不能写成两个子系统纯态的直积，就称之为纠 缠态。说明一个处于纠缠态的完整量子系统的一些确定态和子系统的确定 态并不是相互对应的。 l o 重庆邮电大学硕士论文第二章入侵检测及相关技术概述 2 3 3 遗传算法的应用 遗传算法从产生至今不断扩展应用领域，如工程设计、人工智能、模 式识别、网络安全、生物工程、商业和金融等，这些在实际产业中的应用 同时也促进了g a 算法的研究和发展。 在入侵检测领域，g a 算法也同样得到了广泛的应用和发展，并取得 了较好的效果。如m a r kc r o s b i e 应用遗传规划构建自动代理来实现一个 i d s ，并用自动定义函数进化遗传程序实现自动代理的生成 29 1 ，d d a s g u p t a 通过多级别数据采集( 用户级、系统级、进程级和网络级) 使用小生境技术 构造了一个基于遗传分类器的智能入侵检测系统，但其检测率不高，平均 在8 0 以下【j 。 从本质上看，无论是误用检测还是异常检测，都是一种规则或特征的 匹配问题，因而规则或特征的质量水平直接关系着i d s 的效率和性能。g a 算法在其他领域成功解决了大量传统优化算法所不能解决的问题，而入侵 检测中检测指令的提取和优化，可以通过某种方式转化为函数的优化问 题，因此将g a 算法应用于特征的提取和优化是其应用的延伸和扩展。 量子遗传算法虽然有着传统g a 算法不具备的一些优点，并且也在某 些领域得到了应用，但在入侵检测领域，q g a 算法还未发挥它的优势。本 文将首先应用q g a 算法对初始数据集的属性集进行特征子集的提取，然 后将q g a 算法与聚类算法相结合得到一种新的方法，对数据集进行分类， 以区别正常行为和入侵行为，最后再使用q g a 算法对具体某类入侵行为 的突出特征进行提取，以便于特征知识库的建立，并且在此基础之上建立 检测模型。 2 4 数据挖掘技术及聚类算法在入侵检测中的应用 数据挖掘( d a t am i n i n g ) 【3 1 1 是从海量数据中提取隐含的、事先不知道 的、但又潜在有用的信息和知识的过程，是从大量数据中发现潜在规律、 提取有用知识的方法和技术。 2 4 1 数据挖掘技术在入侵检测中的应用 随着数据挖掘技术的快速发展，越来越多的基于该技术的智能检测方 法成为了人们研究的热点，其思想是利用数据挖掘中的一系列智能算法提 取出与安全相关的系统或网络特征属性，并根据这些特征属性生成安全事 件的分类模型，用于对安全事件的自动鉴别。在1 9 9 9 年w e n k el e e 等人 首次提出了利用数据挖掘技术构建入侵检测模型的过程( 如图2 1 所 示) 【3 2 】【3 3 】，在该模型中，原始审计数据首先被处理成a s c i i 网络数据包信 息或主机事件数据，如连接时间、服务类型等，然后利用数据挖掘应用程 序提取连接记录，通过相关算法的计算形成特征属性，再利用分类程序进 行行为的识别，如果分类模型性能不理想，还需要不断地进行模式挖掘和 特征重构工作，直至分类模型的性能达到最佳。 图2 1 入侵检测中的数据挖掘过程 在入侵检测领域中，数据挖掘技术之所以得到广泛的应用，是因为它 具有以往其它检测技术所不具备的优势。在早期的i d s 中，特征知识库的 建立都需要用手工的方式编写，这样的检测模型存在检测精度低、容易造 成对新攻击行为漏报等的缺点。数据挖掘技术的应用，大大减少了手工分 析和编码入侵模型的需要，提高了模型精确性和智能化的程度，由于拥有 良好的适应性和较强的可扩展性，更增加了模型便于分布式分析和协同工 作的能力。 2 4 2 入侵检测中常用的数据挖掘算法 数据挖掘方法有很多种，在入侵检测领域常用的有以下四种： 1 2 1 ) 分类分析( c l a s s m c a t i o na n a l y s i s ) 分类分析的思想是将特定的数据项归入预先定义好的某个类别，通过 分析示例数据库或训练集中的数据，为每个类别做出准确的描述或建立分 析模型，最终生成某种形式的“分类器 ，如决策树、分类规则等。在入 侵检测中，一种较理想的情况是，首先能够收集大量反映用户或进程活动 的“正常 和“异常状态的审计数据，然后选用某种分类算法，经过训 练学习生成一个对应的“分类器 ，最后，对于新输入的审计记录进行分 类。该“分类器 建立后就可以准确识别新的数据记录属于“正常还是 “异谍”行为。 常用的分类算法有r i p p e r 、c 4 5