（计算机软件与理论专业论文）基于数据挖掘的网络入侵检测系统研究.pdf

基于数据挖掘的网络入侵检测系统研究 摘要 随着网络的不断发展，安全的重要性越来越突出，原有的防火墙已经难以 单独保障网络的安全，入侵检测系统开始发挥出不可替代的作用。然而，现有 的入侵检测系统在有效性、适应性和可扩展性等方面都存在不足，尤其是在遇 到新的入侵类型时显的无能为力，针对这些不足，本文从数据处理的角度，用 数据挖掘的方法建立了入侵检测的模型。由于入侵检测系统处理的数据含有大 量的冗余与噪音特征，使得系统耗用的计算资源大，导致系统训练时间长、实 时性差，检测效果不好。特征选择能够很好地消除冗余和噪音特征，有利于提 高入侵检测系统的检测速度和效果，因而对基于特征选择的入侵检测系统进行 研究是必要的，也符合入侵检测领域的发展趋势。 本文提出了一种基于过滤器模式特征选择的入侵检测系统模型，分别用 c h i 2 、信息增益和f c b f 三种不同的算法进行特征选择，用决策树作为分类算 法。按照d o s ，p r o b e ，r 2 l ，u 2 r 四个类别对k d dc u p 9 9 数据集进行分类， 并且在每一类上进行了大量的实验。实验结果表明，对每一类攻击，由本文提 出的特征选择算法构建的入侵检测系统在建模时间、检测时间、检测己知攻击、 检测未知攻击上，与没有运用特征选择的入侵检测系统相比具有更好的性能。 关键词：入侵检测，数据挖掘，特征选择，决策树 u i r e s e a r c ho nn e t w o r ki n t r u s i o nd e t e c t i o nb a s e do nd a t am i n i n g a b s t r a e t w i t ht h ep r o g r e s so fn e t w o r k ，t h ei m p o r t a n c eo fs e c u r i t yi sb e c o m em o r ea n d m o r eo b v i o u s ，t h et r a d i t i o n a ls e c u r i t yd e v i c ef i r e w a l lh a sd i f f i c u l ti np r o t e c t i n g n e t w o r ks e c u r i t ya l o n e h o w e v e r ，c u r r e n ti n t r u s i o nd e t e c t i o ns y s t e m sl a c k o f e f f e c t i v e n e s s ，a d a p t a b i l i t y a n d e x t e n s i b i l i t y ，a n de s p e c i a l l y , t h e y b e c o m e i n e f f e c t i v ei nt h ef a c eo fd e t e c t i n gn e wk i n do fa t t a c k s a i m e d a tt h e s e s h o r t c o m i n g s ，t h i st h e s i st a k e sad a t a c e n t r i cv i e wt oi d sa n db u i l d sa ni n t r u s i o n d e t e c t i o nm o d e lb y m i n i n ga u d i td a t a a st h ed a t ai n t r u s i o nd e t e c t i o ns y s t e m p r o c e s s e dc o n t a i n sal o to fr e d u n d a n c ya n dn o i s ec h a r a c t e r i s t i c sc a u s i n gs l o w t r a i n i n ga n dt e s t i n gp r o c e s s ，h i g hr e s o u r c ec o n s u m p t i o na sw e l la sp o o rd e t e c t i o n r a t e f e a t u r es e l e c t i o nc a ne l i m i n a t er e d u n d a n ta n dn o i s yf e a t u r e sw e l l i no r d e rt o i m p r o v ep e r f o r m a n c e so fi n t r u s i o nd e t e c t i o ns y s t e mi nt e r m so f d e t e c t i o ns p e e da n d d e t e c t i o nr a t e ，t h u sas u r v e yo fi 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 nf e a t u r e s e l e c t i o ni s n e c e s s a r y a n da l s oc o n f o r m st ot h et r e n di nt h ef i e l do fi n t r u s i o n d e t e c t i o n a ni n t r u s i o nd e t e c t i o ns y s t e mm o d e lb a s e do nf i l t e r m o d e lf e a t u r es e l e c t i o ni s i n t r o d u c e di nt h et h e s i s t h ea l g o r i t h mo fc h i s q u a r e ，i n f o r m a t i o ng a i na n df c b f a r ea d o p t e dr e s p e c t i v e l yt os e l e c tf e a t u r e s ，a n dt h ea l g o r i t h mo fd e c i s i o nt r e ei s u s e da sc l a s s i f i c a t i o na p p r o a c h t h ea u t h o rh a v ee x a m i n e dt h ef e a s i b i l i t yo ft h e f e a t u r es e l e c t i o na l g o r i t h mb yc o n d u c t i n gs e v e r a le x p e r i m e n t so nk d dc u p 9 9 i n t r u s i o nd e t e c t i o nd a t a s e tw h i c hw a sc a t e g o r i z e da sd o s ，p r o b e ，r 2 la n d u 2 r t h ee x p e r i m e n tr e s u l t ss h o wt h a tf o re a c ht y p eo fa t t a c k ，a ni n t r u s i o n d e t e c t i o ns y s t e mw i t hac o m b i n a t i o no ff e a t u r 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 e p a p e rh a sb e t t e rp e r f o r m a n c e st h a nt h a tw i t h o u tf e a t u r es e l e c t i o na l g o r i t h mi nt e r m s o fb u i l d i n gt i m e ，t e s t i n gt i m e ，d e t e c t i n gk n o w na t t a c k sa n dd e t e c t i n gu n k n o w n a t t a c k s k e y w o r d s ：i n t r u s i o nd e t e c t i o n ，d a t am i n i n g ，f e a t u r es e l e c t i o n ，d e c i s i o nt r e e i i 插图清单 图2 1 入侵检测系统的数据流图5 图3 1 典型的数据挖掘系统结构1 4 图3 2 基于数据挖掘的入侵检测系统的基本模型1 9 图5 1 系统模型结构2 9 图5 2 基于c h i 2 和i g 的特征选择流程图3 0 图5 3 基于卡方算法选出的d o s 攻击特征子集结果一3 3 图5 4 基于信息增益选出的d o s 攻击特征子集结果3 4 图5 5 基于f c b f 算法选出的d o s 攻击特征子集结果3 4 图5 6 三种系统模型对已知攻击的检测率3 6 图5 7 三种系统模型对未知攻击的检测率：3 6 图5 8 三种系统模型的误报率3 7 v i 表格清单 表5 - 1 k d d l 9 9 9 训练集与测试集的分类统计信息3 2 表5 - 2 基于c h i 2 和i g 得到的特征子集3 4 表5 3 基于f c b f 算法得到的特征子集3 5 表5 - 4 不同类别入侵检测模型在所有特征和特征子集上平均建模时间和检 测时间3 5 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得金熙王 些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字： 王彳也签字日期：州。年名月纠日 学位论文版权使用授权书 本学位论文作者完全了解金胆工些太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅或借阅。本人授权金壁王些太堂 可以将学位论文的全部 或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 五忽 期解争月辛 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字劣矿鲫瑚 电话： 邮编： 致谢 本论文是在我的导师叶震老师的悉心指导下完成的。从选题、收集 资料、撰写、修改到定稿的过程，都倾注了叶老师的心血。在此对叶老 师致以诚挚的感谢和敬意。 感谢实验室的同学在这三年里给予我的帮助。他们端正的学习态度， 积极的进取精神使我获益匪浅。与他们共度的这段学习时光充实而快乐， 是我人生中一段难忘的回忆。 在此，我还要特别感谢我的父母和前女友王莉，是他们用伟大、温 暖而无私的爱，在背后默默地支持我、关心我、鼓励我真诚面对生活， 战胜一切困难和挫折，走过一个个迷茫彷徨的日子，有勇气去迎接一切 挑战。感谢他们为我所做的一切。 最后再次衷心的感谢所有关心和帮助过我的老师和同学们! n i 作者：王旭 2 0 10 年4 月2 日 第一章绪论 1 1 课题研究的背景和意义 随着计算机网络的不断普及以及相关技术的不断发展，越来越多的企业、 政府和个人在开放的互联网上开展业务、获取信息。但是互联网在给公众带来 巨大方便的同时，其安全问题已成为其发展的一个瓶颈问题。虽然近年来网络 安全越来越得到关注，但网络入侵的种类也越来越多，技巧也越来越复杂，始 终在明处抵挡外来攻击的防火墙难以抵挡黑客针对防火墙的防不胜防的手段翻 新，以及很多来源于网络内部攻击，使得原有的防火墙难以单独保障网络的安 全，这构成了极大的安全威胁。 目前，计算机网络的安全已成为一个国际化的问题，据统计，几乎每 2 0 秒全球就有一起黑客事件发生，仅美国每年由于黑客攻击所造成的经济 损失就超过1o o 亿美元。在过去5 年中信息攻击以2 5 0 速度增长，大多数 的大公司都发生入侵事件。世界著名的商业网站，如y a h o o ，a m a z o n ， e b a y ，c n n ，b u y 都曾遭受到黑客的入侵，造成了巨大的经济损失。更 有甚者，有的专门从事网络安全防护的r s a 网站也曾遭受到黑客的攻击。 在我国，计算机网络的安全状况也不容乐观，据经济专刊华尔街日 报2 0 0 2 年3 月l8 日的报道，中国已成为世界上黑客活动最多的国家，仅 次于美国和韩国。在2 0 0 6 年我国全国信息网络安全状况调查分析报告显 示：2 0 0 5 年5 月至2 0 0 6 年5 月，在13 8 2 4 家被调查单位中，有8 5 的信息网 络已接入互联网，其中有5 4 的被调查单位遭受过网络攻击，比去年上升 了5 ；其中有2 2 的发生过3 次以上的攻击，比去年上升了7 。 然而在近年来，网络攻击产生了新的发展趋势n 1 ，主要表现在以下几个方 面： ( 1 ) 攻击速度和自动化程度不断提高； ( 2 ) 攻击工具越来越复杂； ( 3 ) 从出现安全漏洞到被利用形成攻击时间越来越短； ( 4 ) 网络攻击将攻击手段和病毒体结合在一起； ( 5 ) 攻击不断更新，导致原有的防火墙防御能力不断下降； ( 6 ) 攻击对基础设施将产生更大的威胁； ( 7 ) 攻击的动机已由过去的引起注意或名气转变为追求利益； ( 8 ) 攻击目的为窃取用户机密数据的攻击将具有更大的破坏力； ( 9 ) 连接到i n t e r n e t 上其他系统的安全状态将决定可能遭受到攻击的可能。 出现的攻击这些新特点将使借助于互联网运行业务的机构面临前所未有的 1 考验。为了保护网络免于攻击，入侵检测系统( i n t r u s i o nd e t e c t i o ns y s t e m ) 在信 息安全领域将发挥出不可替代的作用。 从技术层面来看，传统的安全技术，如加密技术、防火墙、口令认证、安 全审计等，都是属于静态的防御技术。静态防御中过于严格的安全策略以牺牲 用户操作方便为代价，与当前网络的开放性、共享性不相容，因此很难做到一 个好的利弊平衡。而且，现有的各种安全防御机制都有无法克服的局限，例如 加密技术、防火墙技术的安全系数设置的非常高，也很难防止密码失窃和来自 内部人员的攻击：一个安全的系统也很难保证内部人员的误操作，以及由于设 置错误而导致系统漏洞的产生。因此，网络安全系统不能只依靠单一的安全防 御机制和防御技术。在充分研究网络安全防御的体系和各种网络安全技术和工 具的基础上，制定详细的系统安全策略，通过设立多层安全防线、集成各种可 靠的安全机制以建立完善的多层安全防御体系乜儿3 1 才能够有效地抵抗来自系统 内部、外部的入侵攻击，从而达到有效地维护网络系统安全的目的。 入侵检测技术是信息网络安全的重要保障。然而，入侵检测技术经过了二 十多年的发展，到目前为止，其应用现状却并不乐观。网络技术在时间和空间 上的延伸，使得目前的网络环境变的越来越复杂，网络基础设施不断升级所带 来的爆炸式的网络数据流量，层出不穷与日趋多样化的攻击手段，使得传统的 仅靠单一的基于模式匹配方法的入侵检测技术难以适用于目前的网络状况。与 其他网络安全产品不同的是，入侵检测系统需要智能化j 它必须能分析得到的 数据，并给出有用的结果。一个合格的入侵检测系统能大大地简化管理员的工 作，保证网络系统安全的运行。 正是由于入侵检测对于网络安全领域具有重要意义，及其在技术上的不完 善性，所以说，对入侵检测的研究很有必要。 1 2 本文组织结构 本文按以下结构进行组织： 第一章，提出本文的研究背景和研究意义； 第二章，总结了入侵检测系统相关的研究，详细介绍了入侵检测系统 的基本原理、入侵检测方法、技术和存在的问题，以及入侵检测发展的方 向； 第三章，详细介绍数据挖掘的相关理论，包括数据挖掘的分析方法以 及入侵检测中用到的数据挖掘技术，提出了基于数据挖掘的入侵检测模 型； 第四章，简述了面向入侵检测的特征选择的研究现状，给出了特征选 择的理论依据，以及特征选择所使用的算法； 2 第五章，详细介绍了本文模型的设计与实现，给出了系统模型结构图， 实验所使用的数据集、实验的评价标准、实验的方案设计、实验的结果和 对比分析； 第六章，总结和展望。 1 3 本章小结 本章通过大量的调查数据指出了当前网络的安全状况和引入入侵检测 系统的必要性，指出了网络攻击新的发展趋势，最后给出了本论文的组织结构。 2 1 入侵与入侵检测 第二章入侵检测综述 所谓的入侵( i n t r u s i o n ) 就是未经许可便擅自进入系统，进行破坏或滥用系统 资源，其目的可能是窃取机密的资料或是盗用一些网络服务：如e m a i l 、f t p s e r v i c e 、线上游戏等。随着计算机的普及与网络的迅速发展，计算机专业人才 也随之迅速增加，网络犯罪的比例也逐年变大。人们对网络的依赖越深，引诱 骇客犯罪的动机也就越高，加上网络犯罪追查难得较大，所以能够破案的机会 也就非常渺茫。 对网络系统而言，不论是不怀好意或是无意的入侵，都是重要的资讯安全 议题。攻击者可以通过非法登入来入侵系统，而已授权的用户可能会非法取得 超出原本的权限，而摇身变成了攻击者。此外，攻击者也可能通过病毒、蠕虫 或特洛伊木马程式来达到入侵的目的。 入侵检测( i n t r u s i o nd e t e c t i o n ) 就是发现入侵的行为，并加以处理，主要为 监视、收集使用者的行为资讯，并分析其行为模式。藉由所收集到的资料，与 目前已知的入侵行为模式作比较，以检测是否有可疑的入侵、攻击的动作。入 侵检测系统是保护系统的重要的部分。如果能快速的检测出入侵行为，除了可 以确认入侵者，还可以在入侵者危害系统之前将入侵者驱出系统。而就算无法 在第一时间检测到入侵者，对非法入侵的检测越快，就系统遭受的损失也越小， 并且也能越快的恢复系统。要想把入侵检测做好，必须要收集大量与入侵相关 的资讯，而这些资讯更可以用来加强防范入侵的能力。 入侵检测的技术是以“入侵者的行为与合法用户的行为之间是不同的”为 前提，而且可以用量化的方法辨别入侵者的行为。但是，两者之间还是会有重 复的地方。因此，虽然扩大界定入侵行为，可以找到更多的入侵者，但同时却 也会导致更多的误判，即将合法用户误认为是入侵者。反之，却会让某些入侵 者成为漏网之鱼1 。 2 2 入侵检测的基本原理 为了介绍入侵检测的基本原理阳1 ，首先介绍入侵检测系统的数据流程。入 侵检测系统的数据流程图如图2 2 所示： 4 处理结束 管理员 古 管理模块 响应器 是i 一 一是。 否浍 l _ 一 、弋! ：三竺墨，l 昌理伏屎i 一、= ：= ! ：三一一：一一1 妄磊i 高至 一 撒瞀牟 一 有否 关联模块 y 的蕴含式，其中xci ，yci 并且 x o y = a 。规则x = y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数与所有交易数之比，记为s u p p o r t ( x = y ) ，即s u p p o r t ( x = y ) = l t ：x uy s t , t d ) i i d l 。规则x = y 在交易集中的置信度( c o n f i d e n c e ) 指包含x 和y 的交易数与包含x 的交易数之比，记为c o n f i d e n c e ( x = y ) ，即 c o n f i d e n c e ( x = y ) = l t ：xuy t , t d l i t ：x c t , t d i 当不考虑关联规则的支持度和置信度时，那么在事务数据库中就可以找到 无穷多的关联规则。然而事实上，人们一般只对那些满足一定的支持度和置信 度的关联规则感兴趣。因而对于给定的事务处理集合，关联规则挖掘就是产生 所有支持度与置信度大于用户给定的最小支持度( m i n s u p ) 与最小置信度 ( r a i n c o n o 的规则。一般定义强规则为满足一定要求的规则，如满足较大的支持 度和置信度的规则。关联规则的最低可靠程度表示为最小置信度。 关联规则的挖掘过程一般可分为两步n 引： 第一步：找到所有大于最小支持度项目的组合，即寻找频集或频繁模式的 集合； 第二步：在频集中产生规则。判定x = y 规则是否有效，可以令 r = s u p p o r t ( x u y ) s u p p o r t ( y ) ，当且仅当r m i n c o n f 时，规则才有意义。 1 5 识别或发现所有频繁项目集是关联规则挖掘算法的核心，也是计算量最大 的部分。常用的关联分析算法有a p r i o r i ，a i s ，s t e m ，d h p 等。 3 3 2 序列分析 序列分析( f r e q u e n te p i s o d ea n a l y s i s ) 就是在处理不同记录之间属性集的 关联关系时把时间和数据之间的关联性联系起来。想要发现序列模式，就需要 确定事件发生的具体时间。序列模式分析的重点是分析事件间的先后序列关系。 它能发现数据库中形如“在某一段时间内，顾客购买a 商品，接着购买b 商品， 而后再购买c 商品，就序列a = b = c 出现的频度较高”之类的知识。 3 3 3 分类分析 分类分析( c l a s s i f i c a t i o na n a l y s i s ) 就是通过分析示例数据库中的数据，为每 个类别做出准确的描述，或建立分析模型，或挖掘出分类规则然后用这个分类 规则对其他数据库的记录进行分类。 在构造分类模型之前，首先要为分类算法提供一个训练数据集作为它的输 入，训练数据集中每一条数据记录都标识与之相应的己知的类型，并且训练数 据集中数据记录的数据项与实际数据集中数据记录的数据项应该相同。分类算 法首先对训练数据集进行分析，提取数据记录的特征属性，给每一种类型标识 生成与之相应的精确的分类规则描述。 3 3 4 聚类分析 聚类分析和分类分析是一个互逆的过程。聚类分析的输入是一组未分类的 记录，并且这些记录要分为几个类事先也并不知道。通过分析数据库中的记录 数据，根据一定的分类规则，合理地划分记录集合，确定每个记录所在类别。 聚类分析所采用的分类规则是由聚类分析工具决定的，有多种方法，其中包括 系统聚类法、分解法、加入法、模糊聚类法、动态聚类法、运筹法等。采用不 同的聚类方法，将可能对相同的记录集合划分出不同的结果。聚类分析方法的 计算复杂度不是线性的，因此难以适用于数据库非常大的情况下姑。 3 4 入侵检测中常用的数据挖掘技术 目前网络安全领域应用数据挖掘技术的主要在以下几点：分析安全检测对 象的海量的审计数据；分析安全检测对象的行为数据；分析安全系统报警事件 1 6 的数据等。数据挖掘算法是一个定义完备的过程，它以数据作为输入，输出主 要为模型或模式的形式。下面简单介绍入侵检测中常用的数据挖掘技术： 3 4 1 关联规则分析 从数据库表中得出属性之间的关联关系是关联规则挖掘的目标。f o r r e s t 等 证明了系统调用在系统特征的取值上和用户行为表现出频繁的关联性。l e e 等 人心叫通过扩展基本的关联规则挖掘算法，以此来发现系统调用以及用户活动在 系统特征上的关联性。通过合并审计记录中挖掘的关联规则，并且添加到最终 规则集中来构建用户的正常行为模型( 要求训练的数据必须绝对纯净，不包含任 何攻击) 。合并规则有两个条件：第一个是规则的左半部分l h s ( 规则的条件) 和 右半部分r h s ( 规则的结论) 必须完全相同；第二是置信度和支持度非常接近， 或者在一个非常小的区间之内变化。分析一个使用者的登录会话，从会话过程 中所调用的命令序列中挖掘出关联模式，并且把它与正常的用户活动简档进行 比较。比较时，规则之间的相似程度应使用相似度函数来评估。例如，如果新 规则集有m 个模式，其中只有1 1 个是可以合并的，那么其相似度的值就为1 3 m 。 3 4 2 特征选择 从审计数据或捕获的数据包中挖掘的规则所涉及到的属性的“重要程度 是不同的。规则应该仅描述那些与“重要 属性相关的模式。那些“不重要 属性的规则不仅没有参考价值而且在某种程度上还会起到误导作用。为了降低 计算成本以及追求实时响应入侵，必须能够确定描述数据的最小化的属性集合。 因此确定合适的属性集将对入侵检测系统的性能产生重要的影响。 m u k k a m a l a 凹2 1 总结了三种不同的属性选择方法：重要程度测试、相互重要 程度测试和基于规则的方法。重要程度测试主要用来决定一个属性给分类系统 所带来信息量的大小，在给定的置信度下，如果某个属性的重要程度低于某个 设定的阈值，则把该属性除去；相互重要程度测试主要用来测试属性之间的依 赖关系程度，假如一个属性是重要的，那么其他依赖此属性的不重要的属性就 可以删除；基于规则的方法就是得出i f t h e n 形式的决策规则集，该规则集用 来判定用户行为是否正常，除去那些没有出现在规则集中的属性。 3 4 3 模糊挖掘技术 审计记录中包含了量化特征，置信度和支持度的阈值把量化数据分隔在两 个区间，正常行为和异常模式的临界分割线非常靠近。为了克服尖锐边界所引 发的问题，b r i d g e s 口3 使用关联规则挖掘算法和频繁情节挖掘算法与模糊逻辑相 结合的方法开发入侵检测系统。作为该方法的进一步延伸，b r i d g e s 和v a n g h n 提出了一个基于遗传算法和模糊挖掘技术的智能入侵检测系统( i n t e l l i g e n t i n t r u s i o nd e t e c t i o ns y s t e m ) 原型1 。 3 4 4 频繁情节规则 事件间的频繁模式在入侵检测中非常的重要，因为有时入侵行为所产生的 一系列事件中其中有单个事件是符合正常模式的，因此只有通过对这个系列事 件进行完整的分析后才能判定是否存在入侵行为。频繁情节描述的主要是事件 之间的频繁关系而不是它们内部属性之间的关系。频繁情节挖掘算法的实现使 用的是关联规则挖掘的数据结构，详细的算法见文献 2 5 】 3 4 5 多级挖掘技术 使用关联规则和频繁情节规则很难检测出那些发生的频率并不高的攻击行 为，原因是其支持度没有超过预定的阂值。如果在挖掘过程中采用较低的支持 度，又会得到大量与频繁度高的服务类型相关的模式。为了克服这个问题，l e e 和s t o l f o 提出了基于多级近似挖掘技术心6 2 7 3 。主要思想是首先找到那些与频率 出现高的轴属性值相关的模式，然后不断降低支持度的值，挖掘那些与频率出 现较低的轴属性值相关的模式。在这个模式的挖掘过程中，限制那些“旧”轴 属性的参与：候选项目集必须至少包括一个“新 ( 低频繁度) 的轴属性值。每 次循环计算得到的模式或者是由所有“新的轴属性构成或者是由“新 轴属 性与“旧 轴属性一起构成。 3 4 6 聚类挖掘技术 在异常检测模型中要求的训练数据集是完备并且是绝对纯净的，不包含任 何攻击。如果在训练数据中隐藏了入侵行为的数据，那么在将来的检测阶段系 统将不会识别出这个入侵，因为在训练阶段这种行为就已经被认为是合法的。 由于待处理的审计日志的数据量非常大，而且对训练数据进行手工分类标记也 是一份十分繁琐并且容易出错的工作，因此要获得带有标记而且绝对纯净的数 据非常困难。虽然可以通过模拟入侵行为来构造标记数据，但这也只能够模拟 对已知类型的攻击，而不能反映将来有可能出现的新的未知类型攻击。因此， e s k i n 等人提出了一种非监督式异常检测算法，该算法是使用一个简单的基于 距离的测度( k 中心点算法) 将数据实例聚类成簇集，一旦数据归类，就可以 1 8 把一些小类标记为异常实例。基于聚类方法的入侵检测系统的可靠性是以如下 两个假设为基础：第一个是训练数据中异常实例数据要远远小于正常实例数据； 第二个是正常行为和入侵实例在本质上是有区别的，即两种行为类型数据属性 的相似性非常低。虽然实验结果表明，该方法在降低误报率和漏报率上的表现 和那些依赖于详细标记性数据的算法相比，性能提高不是非常突出。但它的优 势在于不需要对数据进行预分类和不需要新攻击类型的先验知识。聚类算法省 略了构造训练数据集的繁重的工作量，是数据挖掘技术应用于入侵检测研究领 域的一个新的尝试。 3 5 基于数据挖掘的入侵检测模型 基于数据挖掘的入侵检测系统结构主要由数据收集、数据挖掘、模式匹配 以及决策等四个模块构成。数据收集模块主要是获得数据源，数据源可以是系 统日志、网络数据包、原始数据经过预处理过程后得到的审计数据等。把数据 收集模块得到的审计数据提交给数据挖掘模块后，数据挖掘模块对审计数据进 行整理、分析，找到可用于入侵检测的模式与知识，然后提交给模式匹配模块 进行入侵分析，做出最终判断，最后由决策模块决定应该采取哪些措施。整个 系统的基本模型如图3 2 所示。 l 训练数据l ， 数 ，l 删舛o f i i i i。 7 据 模式匹配卜一智能决策挖 i 审计数据卜_ 掘t i 隐含规则 图3 2 基于数据挖掘的入侵检测系统的基本模型 3 6 数据挖掘中应注意的问题 在数据挖掘过程中，应特别注意以下几个问题： ( 1 ) 过拟合 所谓过拟合就是指通过训练数据产生的模型不能拟合未知的数据。例如在 决策树建模过程中经常会发生过拟合的现象，处理过拟合的方法主要是通过对 树的进行修剪和对由决策树导出的规则进行修剪来处理。 ( 2 ) 噪声数据 1 9 训练数据集中存在不正确的或无效的干扰分类模型建立的属性，在数据挖 掘之前必须改正这些属性值或者去除这些干扰的属性。例如在决策树建模过程 中，经常会出现由于存在噪声属性而影响决策树的分类准确率。 ( 3 ) 不相关数据 对于某个数据挖掘任务，某些数据可能并不需要，由于不相关数据的存在， 有时也会影响挖掘出来的模型的准确率。问题是如何判断属性的重要性，一种 方法是依赖专家的建议，但那样做人为因素偏多，另一种方法就是运用机器学 习或数据挖掘的方法，从众多属性中筛选出重要属性或者是去除不相关的属性。 尤其是对分类数据挖掘，对训练集属性的进行筛选，不仅能提高分类准确性， 而且还有助于降低过拟合的程度，并使得所产生的规则数量减少，泛化能力强。 ( 4 ) 结果的可解释性 数据挖掘输出的结果需要专家给予正确的解释，否则这些结果对一般的数 据库用户来说可能是难以理解的，这样就降低了挖掘结果的可用性。一般来说， 利用决策树导出规则比较简单( i f - t h e n 形式) ，也比较容易被用户理解，这也是 本文选择决策数作为构造分类器算法的原因之一。 3 7 本章小结 本节中主要介绍数据挖掘的概念和意义，把数据挖掘技术应用于入侵检测 系统中具有的优势，目前基于数据挖掘的入侵检测系统的研究现状，罗列了常 见的数据挖掘分析方法以及在入侵检测中用到一些数据挖掘技术，最后指出数 据挖掘应注意的问题。 第四章特征选择综述 4 1 面向入侵检测系统的特征选择研究现状 随着网络速度的不断提升，入侵检测系统面临的一个主要问题是检测速度 低、负荷大、效率低，不能及时处理网络中传输的海量数据，导致丢包进而又影 响入侵检测的性能，并且这个问题也交得越来越严重。因此，检测速度已成为 当前入侵检测系统实时性要求的一个重要指标，如何在保证检测正确性的基础 上开发出一个检测速度快的轻量级的入侵检测系统心8 2 明成为了当前的研究热 点。很多研究者试图通过特征选择来解决这个问题，因为检测处理的特征数目过 多是导致速度下降的主要原因之一。然而特征数目和分类器的性能之间并不存 在线性关系，当特征数目超过了一定的限度时，反而会导致分类器性能变差。实 际上，有些特征并没有包含或者包含极少量的系统状态信息，它们对检测结果几 乎没有影响。还有一些是噪声特征，他们将会误导我们，这将会导致检测误报 率的增加。因此，运用特征选择一一去除冗余特征，保留能够反映攻击模式的重 要特征是提高检测速度的一种有效方法。在尽量保持分类精确度的前提下降低 特征空间的维数，就是特征选择，即依据一定的特征选择和评价函数从原始特征 集中选择与输出与分类有关的或重要的特征子集。 特征选择有两种基本的模式：过滤器模式( f i l t e r ) 和封装器模式 口们( w r a p p e r ) 。一般来说，过滤器模式特征选择速度比较快，所选择出的结果 与采用的学习算法没有关系，度量简单。而封装器模式的特征选择，由于封装 了学习算法，加上需要交叉认证和大量的计算资源，运行速度较慢，选择的结 果依赖于所采用的分类算法，选择效果一般较好。特征选择有两个关键的问题， 即选择合适的评估函数和与之相适应的搜索策略。 目前国内外的研究者尝试把特征选择运用到入侵检测方向的研究已取得一 些研究成果。国内的研究者主要是中国科学院计算技术研究所的李洋、陈友等。 陈友、李洋等提出基于封装器模式的特征选择算法，用改进的随机变化爬山算 法来搜索候选子集，用支持向量机迭代程序作为封装方法来获得最优特征子集 2 q 4 1 。李洋提出基于特征选择和最大熵模型的特征选择，用c h i s q u a r e 作为特征 选择的算法，用最大熵模型分类器来检测入侵别。戴宏等人提出基于c h i 。s q u a r e 和改进的c 4 5 混合的入侵检测系统酮6 1 。张吴等人提出基于k n n 算法及禁忌搜 索算法的特征选择方法阳7 1 。张宏宇、刘宝旭提出基于遗传算法的入侵检测特征 选择引。毛俐提出了集成f i l t e r 和w r a p p e r 方法的混合特征选择新方法引。采用 基于信息增益的f i l t e r 方法，删除不相关特征，采用基于改进的自适应遗传算法 和评价函数w r a p p e r 方法，获取最优特征子集。c h e ny u e h u i 等人提出混合的柔 2 1 性神经树方法来减少输入特征h 们。 国外的研究者在这方面也提出了许多新的方法，m j ：f a d a e i e s l a m 等对主 成分分析和基于决策从属关联h 的两种特征选择方法做了比较，通过实验验证 后者在去除不关联的和冗余的数据方面更有效。k h a j am o h a m m a ds h a z z a d 提出 了一个快速的混合特征选择方法羽一个基于关联的特征选择、支持向量机 和遗传算法的融合来决定最优特征子集，并验证了该方法的可行性。 4 2 特征选择的理论依据 特征选择的理论依据瞳引是：在原特征集中删除或增加相关的特征，对该特 征集的分类能力几乎不产生影响，为了证明这个结论，我们引入下面的定义和 定理： 定义4 - 1 ：设r n 为一个r l 维的特征空间，x 。是原特征空间r n 中的模式向 量； f n = x ；，h i ：l 是m 个模式类别的总样本数，且有n ，= n ，其中，n t 为第i 类模式 i = l 的样本数，定义f i s h e r 比准则为： = 筹 n t ， 定义4 - 2 ： 对于r n 空间的样本集f “= x ；) 釜。， 存在矩阵 日”= ( x ? ，x 2 ”，x 品) 7 = ( y 1 n 矽，p ) ，其中e 是样本的第i 个特征组成的n 维 的向量。若墨，掣线性相关，则称模式间的特征是相关的，若y i n 蟛，彰 线性无关则说明模式间的特征是线性无关的。 定理4 - 1 ：若在原特征空间r n 中增加一个相关特征构成了一个新的特征空 间r 。十l ，如果样本阵列h n + 1 中的列向量d 1 和特征空间r n 中的列向量是线性相 关的，则有j n ( 矿) = j n + l ( 扩州) 。 证明：由于d l 与z n ，彤是线性相关的，由矩阵的性质可知，将h n + 1 进行初等变换，使d l 变为零矢量，即存在矩阵q ( n + 1 ) 。( 。+ 1 ) 使得式( 4 2 ) 成立 h 肘1 = ( ，矽，掣，o ) q ( 4 2 ) 即( x ? + 1 ，x x 2 n + l ，x 1 ) = q r ( x ? 州，x 2 n + l ，x 妒1 ) ( 4 3 ) 式中x n + l = ( x ，n t ，u j t ，o = l ，2 ，) ，根据非负定矩阵的秩分解定理，特征空间 r n 中的霹和掣的秩可分解为： s i n ：艺 b 聊rs ：艺丸l l b ? p ? t q 式中，l = r a n k ( s ? ) ，所以，特征空间r 。+ 1 中w 卅和s ，“的秩可分解为 掣州：圭q 丁+ t 研川y q ，s ；“：圭丑q r + 历川) r q ( 4 5 ) 式中“= ( ，o ) r ， 由式( 4 1 ) ，( 4 5 ) 可得j n ( 0 玎) = j 。+ l ( 矿+ 1 ) 定理4 1 表明，若在原特征空间中增加一个相关的特征，则新旧特征空间 中的最优分类鉴别矢量的分类能力保持不变。同样，若在原特征空间中删除一 个相关的特征，两特征空间的最优分类鉴别矢量的分类能力也相等。这就是进 行特征选择的理论依据。 4 3 特征选择算法 本文将详细介绍三种不同的算法c h i 2 、i g 和f c b f ，并用这三种算法构建 两个特征选择算法流程，合并c h i 2 和i g 算法建立一个模型，而f c b f 算法单 独建立一个模型，具体算法如下文。 4 3 1c h i 2 算法 c h i 2 检验中使用特征与类别间的关联性来进行这个量化，关联性越强，特 征得分越高，该特征就越应该被保留。c h i 2 算法3 是基于z 的统计，它包含两 个阶段。在第一阶段，为了所有的数字属性离散化以一个高显著水平开始 ( s i g l e v e l ) ，例如0 5 。每一个属性根据其值排序，然后执行下面步骤：( 1 ) 用公 式( 4 6 ) 计算每对相邻间隔的z 值( 开始时，每个模式放到它自己的间隔，这些 间n - + n 性只包含个值) ；( 2 ) 以最低的z 值合并相邻间隔。合并继续进行， 直到所有对间隔的最低形值超过了以s i g l e v e l 确定的参数( 最初为0 5 ，如果自 由度是l ，其对应的z 值为0 4 5 5 ，或更低) 上述过程重复减少s i g l e v e l 直到超 过了离散数据的不一致率万。第一阶段如一个c h i 合并。没有指定z 的阈值， c h i 2 以一个循环自动递增z 2 阈值( 递减s i g l e v e l ) 封装了c h i 合并。为了生成的离 2 3 散数据集准确地反映原数据，引用一致性检查作为停止标准。带有这两个新功 能，c h i 2 自动确定一个适当的z 阈值保持原始数据的保真度。 第二阶段是第一阶段的细化过程。以第一阶段确定的s i g l e v e l 0 开始，每个 属性i 与一个s i g l e v e l i 关联，并轮流合并。每个属性的合并完后进行一致性 检查。如果不一致率没有超过，为了属性i 的下一轮合并，递减s i g l e v e l i 】， 否则属性i 不会进入进一步的合并。这个过程持续到没有属性值可以合并。在 第二阶段的结束，如果合并属性的值只有一个，则意味着该属性和原始数据集 的关键属性是不相关的。因此，当离散的结束就是特征选择的完成。 z2 ：2 壹丝兰芷 ( 4 6 ) 。2 l ，2 1 其中：k = 分类的数量； a i j = 第i 个间隔第j 个类的模式数量； r i = 第i 个间隔的模式数量= ：，以； c i _ 第j 个类的模式数量= y j ，4 ，； 。 。-一，2lv n = 总的模式数量2 ：。r ； e i j = a u 的期望频率= r i 宰c j n 如果r i 或者c j 为0 ，e i j 设置为o 1 。z 统计的 c h i 2 的算法如下： 第一阶段： s e ts i g l e v e l = 0 5 ； d ow h i l e ( i n c o n s i s t e n c y ( d a t a ) 万) f o re a c hn u m e r i ca t t r i b u t e s o r t ( a t t r i b u t e ，d a t a ) ； c h i s q - i n i t i a l i z a t i o n ( a t t r i b u t e ，d a t a ) ； d o c h i s q - c a l c u l a t i o n ( a t t r i b u t e ，d a t a ) ) w h i l e ( m e r g e ( d a t a1 ) ) ) s i g l e v e l 0 = s i g l e v e l ； s i g l e v el = d e c r e s i g l e v e l ( s i g l e v e1 ) ；