（计算机应用技术专业论文）决策树的一种优化方法及其在入侵检测中的应用.pdf

决策树的一种优化方法及其在入侵检测中的应用 摘要 当今社会信息安全变得越来越重要，而网络的开放性使其容易受到外界的 攻击与破坏，信息的安全保密性受到严重影响。入侵检测作为计算机及计算机网 络安全领域的一个十分重要的研究课题，其技术是对其他信息安全技术的一个 重要补充。 入侵检测所研究的核心是分类问题，即将一个事件归类为正常或异常的问 题。目前分类技术主要有粗糙集理论、神经网络、统计方法、朴素贝叶斯、支 持向量机和决策树等。决策树由于具有无参性、构造速度快、高度可解释性等 优点而成为数据挖掘领域广泛使用的模型，然而它也有其缺点：所建树可能是 局部最优的；测试和选择分裂属性时未考虑属性间的相关性；忽视了预测精度 与规则规模的平衡等。 本文针对i d 3 和c 4 5 算法进行了深入的分析，对其存在问题展开了讨论， 提出了决策树应注重分类精度与规则规模平衡问题这一观点并设计了决策树的 一种优化方法。该方法采用遗传算法进行属性组合寻优，实验表明，在不过多 损失分类精度的前提下，所构建的决策树规则规模显著减少，因此具有更强的实 用性。 最后本文在所提出的决策树优化方法的基础上，设计并实现了一个误用型 入侵检测原型系统，该系统实现了如下功能：决策树寻优；对寻优得到的决策 树进行测试评估；依据测试评估的结果构建入侵检测分类器。 关键词：入侵检测，数据挖掘，决策树，遗传算法 a no p t i m i z e dm e t h o do fd e c i s i o nt r e e a n di t sa p p l i c a t i o ni ni n t r u s i o nd e t e c t i o n a b s t r a c t t h es e c u r i t yo fi n f o r m a t i o ni sb e c o m i n gm o r ea n dm o r ec r i t i c a l h o w e v e r , n e t w o r ki sv u l n e r a b i eb yo u t s i d ea t t a c k sa n dd e s t r u c t i o nb e c a u s e o fi t so p e n n e s s t h u si ti sab i gc h a l l e n g et om a i n t a i nt h es e c r e c ya n ds e c u r i t yo fi n f o r m a t i o n i n t r u s i o nd e t e c t i o ni sav e r yi m p o r t a n tf i e l di nm a i n t a i n i n gc o m p u t e ra n dn e t w o r k s e c u r i t y a n di t s t e c h n i q u ei s a l l i m p o r t a n ts u p p l e m e n t t oo t h e rt e c h n i q u e so f i n f o r m a t i o ns e c u r i t y t h ec o r ep r o b l e mo fi n t r u s i o nd e t e c t i o ni sc l a s s i f i c a t i o n ，i e ，aq u e s t i o no f c l a s s i f y i n gac a s et on o r m a lo ra n o m a l yp 0 0 1 t h et e c h n i q u e so fc l a s s i f i c a t i o ni n c l u d e r o u g hs e t s ，n e u r a ln e t w o r k ，s t a t i s t i c s ，n a i v eb a y e s ，s u p p o r tv e c t o rm a c h i n e ( s v m ) a n d d e c i s i o nt r e e ，e t c c o m p a r e dt oo t h e rt e c h n i q u e s ，d e c i s i o nt r e eh a sm a n ya d v a n t a g e s ： n o n - p a r a m e t r i c ，f a s tc o n s t r u c t i o na n dh i g hd e g r e eo fi n t e r p r e t a b i l i t y o fc o u r s e ，t h e t e c h n i q u e so fd e c i s i o nt r e eh a v es o m ed e f e c t sa sw e l l s u c ha s ，l o c a lo p t i m a l i t y , t a k i n gn oa c c o u n to ft h e r e l a t i o na m o n ga t t r i b u t i o n so nt h ec a s eo ft e s t i n ga n d s e l e c t i n go fs p l i t - o f fp r o p e r t ya n do v e r l o o k i n gt h eb a l a n c i n gb e t w e e n t h ep r e c i s i o no f f o r e c a s ta n dt h es i z eo f r u l e s i nt h i sd i s s e r t a t i o n ，t h ea i g o r i t h m so fi d 3 ，c 4 5f o rt h ec o n s t r u c t i o no fd e c i s i o n t r e ei sd i s c u s s e d ，a n da no p t i m a lm e t h o df o rt h ec o n s t r u c t i o no fd e c i s i o nt r e eb y a p p l y i n gg e n e t i ca l g o r i t h m si sp r o p o s e db a s e do n t h eb a l a n c i n gb e t w e e nt h ep r e c i s i o n o fp r e d i c ta n dt h es i z eo fr u l e s t h ee x p e r i m e n t sd e m o n s t r a t et h a tt h em e t h o dc a n n o t a b l yc u td o w nt h es i z eo fr u l e sw i t h o u to v e rs a c r i f i c i n gt h ec l a s s i f y i n gp r e c i s i o n t h e r e f o r e ，i ti sm o r ep r a c t i c a l a tt h ee n do ft h ed i s s e r t a t i o n ，am i d s ( m i s u s ei n t r u s i o nd e t e c t i o ns y s t e m ) i s d e v i s e da n di m p l e m e n t e d t h i ss y s t e mi m p l e m e n t st h ef o l l o w i n gf u n c t i o n s ：d e c i s i o n t r e eo p t i m i z a t i o n ，t e s t i n ga n de v a l u a t i n gt h ed e c i s i o nt r e eo p t i m i z e da sa b o v e ，a n d b u i l d i n gt h e c l a s s i f i e ro fi n t r u s i o nd e t e c t i o na c c o r d i n gt ot h er e s u l t st e s t e da n d e v a l u a t e d k e yw o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，g e n e t i ca l g o r i t h m s i i 插图目录 图2 1k d d 的处理过程模型1 1 图2 2 数据挖掘模型与任务1 2 图3 1 “g 0 1 f ”分类决策树1 8 图4 1 遗传算法流程图3 3 图4 2 决策树寻优模型3 5 图5 1 通用入侵检测系统结构3 9 图5 2 误用型入侵检测系统组成结构4 0 图5 3k d d c u p 9 9 数据形式4 1 图j 4 测试集数据4 4 图5 5 属性和类别文件4 4 图5 6 初始化寻优参数4 5 图5 。7 种群个体相关数据。，。4 5 图5 8 按适应度排名4 5 图5 9 评估测试结果4 6 图5 1 0 预测结果4 6 v i 插表目录 表3 1 “g o l f ”训练集 表4 1 试验参数表 表4 2 试验结果数据 表5 1 网络连接的基本属性 表5 2 安全领域知识建议的连接类属性 表5 3 在最近两秒内的通信的统计属| 陛 表5 4 入侵种类 v i i 盟盯勰心们 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 金魍王些盍堂 或其他教百机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解盒胆王些友堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 胆王些本坐可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字日期 帆们目( 瑶 邮编们卵巧 1 d 胆日 致谢 本人在四年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得 到了我的导师胡学钢教授的悉心指导和大力支持，无论从课程学习、论文选题， 还是到收集资料、论文成稿，都倾注了胡老师的心血，由衷感谢胡老师在学业 指导及各方面所给予我的关心以及从言传身教中学到的为人品质和道德情操， 胡老师广博的学识、严谨的治学作风、诲人不倦的优秀品质，必将使我终身受 益，并激励我勇往直前。 同时，真诚感谢计算机信息学院的全体老师，特别是王浩教授，他们的教 诲为本文的研究提供了借鉴和指导；感谢研究生院和学位办公室的领导和老师 们，在我课程学习和论文撰写期间，给予我的大力支持。 感谢我的妻子，在我忙于学业、准备论文的过程中，她总能给我以力所能 及的帮助。特别当我在研究过程中遇到困难时，她给了我很多鼓励和照顾，使 我在学业和工作中更加努力，并最终完成了学位论文。 最后，感谢合肥工业大学为我提供的这次学习机会，良好的学术气氛和优 质的师资力量，激发了我的研究兴趣，坚定了我的学习信心，使我在专业上受 益匪浅。 i i i 作者；华文立 2 0 0 6 年8 月 1 1 引言 第一章入侵检测系统概述 随着i n t e m e t 高速发展，个人、企业以及政府部门越来越多地依靠网络传递 信息，然而网络的开放性与共享性容易使它受到外界的攻击与破坏，信息的安全 保密性受到严重影响。网络安全问题已成为世界各国政府、企业及广大网络用 户最关心的问题之一。而网络安全是一个系统的概念，制定有效的安全策略或 方案是网络信息安全的首要任务。现有的网络安全策略主要有数据加密、信息 隐藏、防火墙、身份识别和入侵检测等，其中入侵检测技术作为其他安全技术 的重要补充，日益受到各界的重视。 传统的信息安全方法采用严格的访问控制和数据加密策略来防护，但在复 杂系统中，这些策略是不充分的，它们是系统安全不可缺少的部分但还不能完 全保证系统的安全。例如，防火墙就是一种保证信息安全的重要手段，尽管防 火墙及其强大的身份验证功能能够保护系统不受未经授权访问的侵扰，但是它 们对专业黑客或恶意的经授权用户却无能为力。同时，防火墙是”外紧内松”的， 无法阻止内部人员所做的攻击，对信息流的控制缺乏灵活性，从外面看似非常安 全，但内部缺乏必要的安全措施。据统计，全球8 0 以上的入侵来自于内部。 由于性能的限制，防火墙通常不能提供实时的入侵检测能力，对于企业内部人 员所做的攻击，防火墙形同虚设。事实上，防火墙( f i r e w a l l ) 是设置在不同网络( 如 可信任的企业内部网和不可信任的公共网) 或网络安全域之间的一系列部件的 组合，它属于网络层安全技术，其作用是为了保护与互联网相连的企业内部网络 或单独节点。它具有简单实用的特点，并且透明度高，可以在不修改原有网络 应用系统的情况下达到一定的安全要求。但是，防火墙只是一种被动防御性的 网络安全工具，仅仅使用防火墙是不够的。首先，入侵者可以找到防火墙的漏 洞，绕过防火墙进行攻击。其次，防火墙对来自内部的攻击无能为力。它所提 供的服务方式是要么都拒绝，要么都通过，而这是远远不能满足用户复杂的应用 要求的。 入侵检测是对防火墙有益的补充，入侵检测系统能使在入侵攻击对系统发 生危害前，检测到入侵攻击，并利用报警与防护系统驱逐入侵攻击。在入侵攻 击过程中，能减少入侵攻击所造成的损失。在被入侵攻击后，收集入侵攻击的 相关信息，作为防范系统的知识，添加入知识库内，增强系统的防范能力，避 免系统再次受到入侵。入侵检测被认为是防火墙之后的第二道安全闸门，在不 影响网络性能的情况下能对网络进行监听，从而提供对内部攻击、外部攻击和 误操作的实时保护，大大提高了网络的安全性。 1 2 入侵检测的相关概念 计算机安全的3 个基本目标是：机密性、完整性和可用性。机密性要求保 证系统信息不被非授权的用户访问，完整性要求防止信息被非法修改或破坏， 而可用性则要求保证系统信息和资源等能够持续有效，并能按用户所需的时间、 地点和方式加以访问。安全的计算机系统应该实现上述3 个目标，即保护自身 的信息和资源，不被非授权访问、修改和攻击。j 。pa n d e r s o n 在其1 9 8 0 年的技 术报告中，建立了关于入侵的早期模型，并按照入侵的来源，分为3 类”1 ： f 1 ) 外部入侵者：系统的非授权用户。 ( 2 ) 内部入侵者：超越合法权限的系统授权用户。 f 3 ) 违法者：在计算机系统上执行非法活动的合法用户。 所谓入侵( i n t r u s i o n ) “1 是指任何企图危及资源的完整性、机密性和可用性的 行为和活动。入侵检测”1 ( i n t r u s i o n d e t e c t i o n ，i d ) 是指发现非授权使用计算机的 个体( 如黑客) 或计算机系统的合法用户滥用其访问系统的权力以及企图实施上 述行为的个体。把能完成入侵检测的软件和硬件组合称为入侵检测系统 ( i n t r u s i o nd e t e e f i o ns y s t e m ，m s ) 2 i o 1 。3 入侵检测研究的历史和现状 入侵检测的研究最早可以追溯到j p a n d e r s o n 在1 9 8 0 年为美国空军做的题 为计算机安全威胁监控与监视的技术报告，第一次详细阐述了入侵检测的 概念。他提出了一种对计算机系统风险和威胁的分类方法，并将威胁分为外部 渗透、内部渗透和不法行为三种，还提出了利用审计跟踪数据监视入侵活动的 思想。他的理论成为入侵检测系统设计及开发的基础，他的工作成为基于主机 的入侵检测系统和其它入侵检测系统的出发点。 1 9 8 7 年d o r o t h y e d e n n i n g ”1 提出入侵检测系统( 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 d s 是全新的计算机安全措施。 该入侵检测系统抽象模型包含3 个必要的功能组件：信息来源、分析引擎和响 应组件。这3 个功能组件的含义是： f 1 ) 信息来源( i n f o r m a t i o ns o u r c e ) ：为检测可能的恶意攻击，i d s 所检测的网 络或系统必须能提供足够的信息给i d s ，资料来源收集模组的任务就是要收集 这些信息作为i d s 分析引擎的资料输入。 ( 2 ) 分析引擎( a n a l y s i se n g i n e ) ：利用统计或规则的方式找出可能的入侵行为 并将事件提供给响应组件。 ( 3 ) 响应模块( r e s p o n s ec o m p o n e n t ) ：能够根据分析引擎的输出，采取相应的 行动。通常具有自动化机制，如主动通知系统管理员、中断入侵者的连接和收 集入侵信息等。 1 9 8 9 1 9 9 1 年，s t e p h e ns m a h a 设计开发了h a y s t a c k 入侵检测系统，该系 统用于美国空军内部网络的安全检测目的。1 9 9 0 年，加州大学d a v i s 分校的t o d d h e b e r l i e n 发表在i e e e 上的论文“an e t w o r ks e c u r i t ym o n i t o r ”，标志着入侵检 测第一次将网络数据包作为实际输入的数据源。1 9 9 2 年前后，s a j c 和h a y s t a c k l a b s 分别开发出了c m d s 系统和s t a l k e r 系统，这两个系统是首批投入商用的 主机入侵检测系统。1 9 9 7 年，c i s c o 公司开始将入侵检测技术嵌入路由器，同 时，i s s 公司发布了基于w i n d o w s 平台的r e a l s e c u r e 入侵检测系统，由此拉开 了商用网络入侵检测系统的发展序幕。1 9 9 9 年，w e n k el e e 提出了用于入侵检 测的数据挖掘技术框架。2 0 0 0 年，普渡大学的d i e g oz a m b o n i 和e s p a f f o r d 提 出了入侵检测的自治代理结构。 目前，入侵检测技术的发展日新月异，已从早期仅仅作为研究的阶段，发 展到商用的阶段。入侵检测作为一种积极主动的安全防护技术，提供了对内部 攻击、外部攻击和误操作的实时保护，在网络系统受到危害之前拦截和响应入 侵。入侵检测系统能很好的弥补防火墙的不足，从某种意义上说是防火墙的补 充。入侵检测系统正成为信息安全体系中的重要和不可缺少的一环。 1 4 入侵检测系统的分类 对入侵检测系统的分类，大都是基于信息源和分析方法进行分类。入侵检 测系统依照信息来源收集方式的不同，可以分为基于主机( h o s t b a s e di d s ) 的和 基于网络( n e t w o r k - b a s e di d s ) ；另外按其分析方法可分为异常检钡l j ( a n o m a l y d e t e c t i o n ，a d ) 和误用检测( m i s u s ed e t e c t i o n ，m d ) 。 1 4 1 根据信息源分类 1 基于主机的入侵检测系统( 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 ) 基于主机的i d s 可监测系统、事件和w i n d o w sn t 下的安全记录以及u n i x 环境下的系统记录。当有文件被修改时，i d s 将新的记录条目与已知的攻击特 征相比较，看它们是否匹配。如果匹配，就会向系统管理员报警或者作出适当 的响应。 。基于主机的i d s 在发展过程中融入了其他技术。检测对关键系统文件和可 执行文件入侵的一个常用方法是通过定期检查文件的校验和来进行的，以便发 现异常的变化，反应的快慢取决于轮讯间隔时间的长短。许多产品都是监听端 口的活动，并在特定端口被访问时向管理员报警。这类检测方法将基于网络的 入侵检测的基本方法融入到基于主机的检测环境中。 基于主机的i d s 的优点是可以利用操作系统本身提供的功能，结合异常分 析来更加准确地报告攻击行为：缺点是必须为不同的平台开发不同的程序，增 加了系统的负荷等。 2 基于网络的入侵检测系统( 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 ) 基于网络的入侵检测系统以网络包作为分析数据源。它通常利用一个工作 在混杂模式下的网卡来实时监视并分析通过网络的数据流。它的分析模块通常 使用模式匹配、统计分析等技术来识别攻击行为。一旦检测到了攻击行为，i d s 的响应模块就做出适当的响应，比如报警、切断相关用户的网络连接等。不同 入侵检测系统在实现时采用的响应方式也可能不同，但通常都包括通知管理员、 切断连接、记录相关的信息以提供必要的法律依据等。 基于网络的i d s 的优点是简便，一个网段只需要一个或者几个这样的系统； 缺点是这种结构的适用性随着日益复杂的高速网络的普及受到挑战，比如交换 式以太网中这种结构就很难有成效。 1 4 2 根据检测所用分析方法分类 根据入侵检测所用分析方法的不同，可分为误用检测和异常检测。 1 误用检n 9 ( m i s u s ed e t e c t i o n ) 误用检测也被称为基于知识的检测。其基本前提是：假定所有可能的入侵 行为都能被识别和表示。误用检测的技术基础是分析各种类型的攻击手段，并 找出可能的“攻击特征”集合。误用检测利用这些特征集合或者是对应的规则 集合，对当前的数据来源进行各种处理后，再进行特征模式或者规则匹配工作， 如果发现满足条件的匹配，则指示发生了一次攻击行为。这里所指的“特征匹 配”根据不同的具体实现手段而各不相同，从最基本的字符串匹配，到基本状 态转移的分析模型等。 2 异常检测( a n o m a l yd e t e c t i o n ) 异常检测假设入侵者活动异常于正常的活动。为实现该类检测，i d s 建立 正常活动的“规范集( n o r m a lp r o f i l e ) ”，当主体的活动违反正常规范时，认为可能 是“入侵”行为。异常检测的优点之一是具有抽象系统正常行为模式，从而能够 检测系统异常行为的能力。这种能力不受系统以前是否知道这种入侵与否的限 制，所以能够检测新的入侵行为。大多数的正常行为的模型使用一种矩阵的数 4 学模型，矩阵的数量来自于系统的各种指标。比如c p u 使用率、内存使用率、 登录的时间和次数、网络活动、文件的改动等。异常检测的缺点是：若入侵者 了解到检测规律，就可以小心的避免系统指标的突变，而使用逐渐改变系统指 标的方法逃避检测。另外检测效率也不高，检测时间较长。最重要的是，这是 一种“事后”的检测，当检测到入侵行为时，破坏早已经发生了。 常用的异常检测方法有：基于统计异常检测方法、基于特征选择异常检测 方法、基于贝叶斯推理异常检测方法、基于贝叶斯网络异常检测方法、基于模 式预测异常检测方法、基于神经网络异常检测方法、基于机器学习异常检测方 法、基于数据挖掘异常检测方法等。 比较而言，误用入侵检测比异常检测具备更好的确定解释能力，即明确指 示当前发生的攻击手段类型，因而在诸多商用系统中得到广泛的应用。另一方 面，误用入侵检测具备较高的检测率和较低的虚警率，开发规则库和特征集合 相对于建立系统正常模型而言，也要方便、简单。误用检测的主要缺点在于一 般只能检测到已知的攻击模式，模式库需要不断更新才能检测到新的攻击方式。 而异常检测的优点是可以检测到未知的入侵行为，尽管可能无法明确指示是何 种类型。但异常检测的虚警率比较高，这主要是由于正常行为的特征轮廓的确 定比较困难。 1 5 常用入侵检测技术 入侵检测系统中常用的入侵检测技术主要有：模式匹配、统计方法、专家 系统、神经网络、遗传算法、数据融合和数据挖掘等。下面将简要介绍一下常 用的入侵检测方法。 l ，模式匹配 模式匹配方法常用于误用检测。它建立一个攻击特征库，并检查发送过来 的数据是否与攻击特征相匹配，以此判断它是否为攻击。它的算法简单、准确 率高，缺点是只能检测已知攻击，模式库更新麻烦。 2 统计方法 统计方法是异常检测中最具代表性的一种入侵检测方法。它通过设置极限 阀值等方法，将待检测数据与已有的正常行为加以比较，如果超出极限值，则 认为是入侵行为。常用的入侵检测统计模型为：操作模型、方差、计算参数的 方差、多元模型、马尔柯夫过程模型和时间序列分析。统计方法的最大优点是 它可以“学习”用户的使用习惯，从而具有较高检出率与可用性。但是它的“学习” 能力也给入侵者以机会通过逐步“训练”使入侵事件符合正常操作的统计规律， 从而透过入侵检测系统。 3 专家系统 专家系统的构建依赖于专家的经验和知识库的完备性，根据所获得的事实 和已知的规则进行推导，并得出结论。专家系统的优点是用户无须了解具体系 统内部的工作原理，只需要描述问题即可。缺点是攻击特征的提取有较大难度， 速度难以满足实时性要求等。 4 神经网络 神经网络具有自适应、自组织和自学习的能力，可以处理一些环境信息复 杂、背景知识不清楚的问题。将来自审计日志或正常网络访问行为的信息，经 数据预处理后的输入向量提交给神经网络处理，从中提取用户正常行为的模式 特征，并以此创建用户的行为特征轮廓。 5 遗传算法 遗传算法能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应 地控制搜索过程，从而得到最优解或次优解。遗传算法简单、通用、鲁棒性好， 适用于并行处理。 6 数据融合 数据融合技术通过综合多个不同的传感器或数据源的数据，对有关事件、 行为以及状态进行分析和推论。在对不同渠道搜集来的信息进行分析推断和结 果融合的基础上，给出检测系统的判断结果和响应措施，对系统威胁、恶意行 为以及威胁的类型进行识别，并作出适当的响应措施。 7 数据挖掘 数据挖掘是近几年发展起来的一项知识获取新技术。将数据挖掘技术引入 入侵检测也是一种可行的方法。从根本上说，入侵检测就是将正常的用户行为 和非正常的用户行为( 包括入侵行为和可疑行为) 区分开来，因此，研究如何利用 数据挖掘技术获取入侵行为和正常行为的特征模式也是一种有意义的尝试。用 于入侵检测的常用算法有分类算法、关联分析算法、序列分析算法等，本文将 就如何应用决策树分类算法构建入侵检测系统作一研究和探讨。 1 6 数据挖掘在入侵检测中的应用可行性 随着大规模网络入侵事件的出现，入侵检测技术已经成为近年来网络安全 领域的一个研究热点。而传统建立入侵检测系统的方法，多为基于简单特征值 分析、手动发现规则方式，人工参与的工作量大，系统建立速度慢更新代价高 而且面对日益更新的网络设施和层出不穷的入侵方法，这样建立的入侵检测系 统显得缺乏有效性、适应性和可扩展性，有较高的漏报率和误报率。近年来， 将数据挖掘技术引入入侵检测领域的研究成为一个热点，具有代表性的成果就 是美国哥伦比亚大学的w e n k el e e 研究小组所创建的入侵检测系统，该系统所 用的主要技术是分类、关联规则和序列规则分析”。 数据挖掘通常应用于市场营销、金融投资、生产制造等领域。但在入侵检 测领域中运用数据挖掘技术对网络业务进行分析、发现入侵模式等方面也具有 明显优势。入侵检测也正是要从大量数据中分析提取出有用的知识( 如规则) 和模 式，并对网络业务行为的正常与否做出判断，这与数据挖掘技术的思路不谋而 合。因此将数据挖掘技术应用于入侵检测领域是完全可行的。具体来说，基于 数据挖掘的入侵检测系统具有以下优点： ( 1 1 适应能力强：应用数据挖掘方法的检测系统不是基于预定义的检测模型， 可以有效地检测新型攻击以及已知攻击的变种。 ( 2 ) 检测效率高：数据挖掘可以自动地对数据进行预处理抽取数据中的有用 部分有效地减少数据处理量。 ( 3 ) 智能性好：采用数据挖掘技术可以自动地从海量数据中提取人工难以发 现的网络行为模式，提高了检测准确性。 基于以上分析，我们认为将数据挖掘技术应用于入侵检测是可行的，因而 进行这方面的研究也是有必要的。 1 7 本文组织安排 本文主要研究数据挖掘理论中分类技术，重点研究决策树算法。在传统决 策树算法的基础上，针对c 4 5 决策树算法，研究在保持分类精确度的前提下， 控制决策树产生的规则数量、规则长度的有效方法，并将研究成果应用到误用 入侵检测系统之中。 本文的内容安排如下： 第一章系统的介绍了入侵检测系统的概念和方法，介绍了入侵检测的发展 状况，阐述了入侵检测的核心问题是入侵模式的提取。 第二章介绍了数据挖掘的发展状况，介绍了数据挖掘的模式和常用方法， 讨论了数据挖掘中应该注意的问题，阐明了将决策树引入入侵检测的可行性， 最后介绍了本文的组织安排。 第三章主要阐述决策树的基本原理，详细讨论了基于信息熵的i d 3 算法及 i d 3 的改进算法c 4 5 。在此基础上分析了c 4 5 的不足，提出了改进方案。 第四章主要介绍遗传算法的基本原理，阐明了遗传算法的三个重要的构成 要素选择算子、交叉算子、变异算子的作用原理。另外，提出了一种基于遗传 算法进行属性寻优的决策树优化模型，介绍了该模型的基本思想，设计了一个 新的适应度函数，阐明了该适应度函数的作用，并对新算法和c 4 5 算法进行了 实验比较，验证了新算法在降低误报率，控制规则数量和规则长度方面的有效 性。 第五章介绍了基于新算法的入侵检测系统的模型，阐明了该系统的构成原 理和应用过程，该入侵检测系统实现了误用检测功能，在分类精度、规则数量 上优于传统的c 4 5 。 第六章对所做工作进行了总结，并对未来的工作进行了展望。 1 8 本章小结 本章介绍了入侵检测产生的原因、发展历史和现状，阐明了入侵检测领域 的相关概念、入侵检测的分类、入侵检测的方法及常用技术，讨论了将数据挖 掘技术引入入侵检测的可行性。 2 1 引言 第二章数据挖掘概述 随着i n t e r n e t 的迅猛发展，数据容量规模已经达到万亿( t b ) 的水平。我们面 临着信息爆炸但知识贫乏的挑战，常会感到被淹没在海量数据中却无从获取所 需要知识的困惑。过量的数据被人们称为信息爆炸，带来的挑战是一方面规模 庞大的数据让使用者无从下手；另一方面在这些庞大数据的背后却隐藏着许多 有价值的信息。因此，我们所面临的主要问题就是如何快速、准确地从已有海 量数据中获得有价值的知识，并将知识用于各种决策支持。在过去十几年里出 现的数据挖掘技术正致力于解决这个问题。数据挖掘技术是在统计学、人工智 能( 特别是机器学习) 和数据库技术等多种技术的基础上发展起来的，现在已经广 泛应用到商业、金融、医疗、网络安全等诸多行业领域，数据挖掘不仅是个重 要的研究领域，而且在现实世界中具有重大的潜在应用价值。 本章首先对数据挖掘的有关概念作简要介绍，然后对数据挖掘的方法、任 务和相关技术进行说明，最后介绍本文的研究内容和组织安排。 2 2 数据挖掘综述 2 2 1 数据库知识发现与数据挖掘的定义 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 是指从数据 中发现有用的信息和模式的过程 7 1 。人们经常将数据库中的知识发现与数据挖 掘这两个概念不加区别的使用，目前比较公认、完整、深刻和全面的k d d 定义 是由德国人f a y y a d z 等人在1 9 9 6 年发表的论文f r o md a t am i n i n g t o k n o w l e d g ed i s c o v e r y ) 一文中描述的：“t h e n o n t r i v i a l p r o c e s so fi d e n t i f y l u g v a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n s i nd a t a 即 k d d 是从大量的数据中提取有效的、新颖的、有潜在价值的、可信的、并能最 终被人们理解的模式的非平凡的处理过程【8 】。数据挖掘( d a t am i n i n g ，d m ) 的技 术定义就是从大量的、不完全的、有噪声的、随机的数据中，提取隐含在其中 的、人们事先不知道的、但又是潜在有用的信息和知识( 比如分类规则等) 的过程 1 9 1 。一般认为数据挖掘是数据库中的知识发现k d d 整个过程中的一个步骤。 9 2 2 2 k d d 发展和研究现状 数据挖掘是2 0 世纪8 0 年代，人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 研究走入 低谷后，a i 转入实际应用时提出的。国际上第一次关于数据挖掘与知识发现的 研讨会于1 9 8 9 年在美国的底特律召开，在此次会议上首次提出了知识k d d 一 词。随着k d d 在学术界和工业界的影响越来越大，k d d 组委会于1 9 9 5 年把专 题会议更名为k d d 国际学术会议，并于同年在加拿大的蒙特利尔召开了第一届 k d d 国际学术会议。k d d 国际学术会议每年举行一次，由美国人工智能协会 主办，迄今为止已经举办了1 1 届，第1 2 届k d d 会议将于2 0 0 6 年8 月在美国 的费城举行“。此外，从1 9 9 7 年开始，每年由a c ms p e c i a li n t e r e s tg r o u po n k n o w l e d g e d i s c o v e r y a n d d a t a m i n i n g f s i g k d d ) 举办一次国际k d d 大赛，该项 比赛越来越得到大家的重视。其中，1 9 9 9 年举办的k d d 大赛的题目是：i n t r u s i o n d e t e c t i o na n dr e p o r t ，比赛组织者提供了比赛所用数据，本文所用数据也均来自 k d d c u p 9 9 提供的数据。 目前，在i j c a i 、恕a i 、v l d b 、a c m s i g m o d 等代表人工智能与数据库 技术研究的国际著名学术会议上对k d d 的研究也都占有很大比重。k d d 和d m 已经成为当今计算机科学与技术领域的研究热点。近几年，我国的研究人员纷 纷加入到该领域中来，国内也相继举办了多个学术会议，如数据库学术会议、 机器学习学术会议、粗糙集合会议等等，在这些会议上都将k d d 列为重要的研 究方向。特别值得一提的是，在2 0 0 4 年k d d c u p 大赛中，中国科学院计算机 研究所的付岩等获得了大赛优胜奖，他们参赛的题目是“蛋白质序列同源性分 类”问题1 ，他们采用支持向量机技术处理同源性问题，将蛋白质序列分为同 源和不同源两类，分类效果良好。 随着k d d 研究的深入进行，许多公司推出了自己的k d d 产品，如s p s s 公司的c l e m e n t i n e 、i b m 公司的i n t e l l i g e n tm i n e r 、s a s 公司的e m e r p r i s em i n e r 、 t h i n k i n gm a c h i n e s 公司的d a r w i n t m 、d a t a m i n d 公司的d a t a m i n dd a t a c r u n c h e r 、r u l e q u e s t r e s e a r c h 公司的s e e 5 、b u s i n e s s o b e c t s 公司的b u s i n e s s m i n e r 等。在已经推出的k d d 产品中，涉及到的数据挖掘技术和方法主要有决策树方 法( 如c 4 5 ，c a r t , c h a i d ) 、规则推断( 如a q ，c n 2 ) 、最近邻方法、聚类方法、关 联规则、神经网络、贝叶斯信念网络、遗传算法、支持向量机、自组织图、神 经模糊系统等。 数据挖掘从诞生到现在不过十多年的时间，在这短短的十几年里，它吸引 了各个行业的研究人员、工业界人士的兴趣。目前，它已成为最近几年对人类 生活影响最大的几项i t 技术之一，数据挖掘的应用已取得初步的成功。随着人 们对信息的重视程度不断加深，数据挖掘的前途必将是光明的。 同时，数据挖掘作为一门新兴的科学和技术，它的发展还处于幼年期，要 1 0 想使之得到广泛充分地应用，还必须面对的许多挑战： 1 建立基础的数据挖掘理论体系； 2 提高数据挖掘算法的效率，和处理能力； 3 改善数据挖掘系统的人机界面： 4 分布式挖掘和实时挖掘； 5 挖掘各种数据类型，包括半结构和无结构数据。 2 3 k d d 的处理过程模型 一般认为，数据挖掘是k d d 整个过程中的一个步骤，而k d d 的一般过程 如图2 1 所示”1 。 图2 1k d d 的处理过程模型 从上述模型可以看出，k d d 的处理过程大致分为以下五个主要步骤：数据 选择、数据预处理、数据变换、数据挖掘和结果的解释评价。 1 数据选择 数据挖掘过程所需要的数据可能从不同的异构数据源获取，因此，第一步 就是从各种数据库、文本文件和非电子数据源中获取数据。 2 数据预处理 初始数据中可能会有一些错误的或者缺失的数据，也有可能由于数据源、 数据类型以及度量的多样性，造成一些数据不规则。错误的数据可以修正或剔 除，但缺失的数据必须补充或预测。 3 数据变换 为了便于挖掘，需要将不同数据源获取的数据转换成统一的格式，一些数 据可能需要编码或变换成更容易使用的格式。 4 数据挖掘 基于所执行的数据挖掘任务，对变换后的数据应用合适的算法来产生期望 的挖掘结果。 5 结果的解释评价 数据挖掘的结果，还要通过用户、专家或自动系统的评价，去除不合理、 冗余、错误、无关的模式，并将最终的结果以良好的、容易理解和使用的形式 呈现给用户。 曰一 2 4 数据挖掘任务和常用挖掘技术 2 4 1 数据挖掘的任务 数据挖掘任务一般可以分为两大类：描述和预测。描述型挖掘任务刻画数 据的一般特性。预测型挖掘任务在当前数据上进行推断，以进行预测“。预测 型任务主要是利用从不同数据中发现的已知结果建立预测模型，并对未知数据 进行判断和预测。而描述型任务主要是对数据中的模式或关系进行辨识，而不 是预测新的性质。数据挖掘模型与任务分类情况见图2 2 ，下面依据上述分类逐 一简单介绍。 分 现 图2 2 数据挖掘模型与任务 1 分类7 1 1 9 1 分类是指将数据映射到预先定义好的类或组中。分类算法通常通过观察已 知所属类别的数据的特征来描述类别，这个过程分为两步：建立分类模型( 又称 分类器) 和分类模型的应用。由于在分析测试数据之前，类别就已经确定了，所 以分类通常被称为有指导学习。 例题2 1 信用卡公司根据使用信用卡支付的历史信息，将每一次支付划分 为如下4 类：( 1 ) 授权；( 2 ) 在授权前要求进一步确认；( 3 ) 不授权；( 4 ) 不授权且报 警。 针对上述问题的数据挖掘任务分为两步：首先需要分析过去的历史数据， 确定拟和上述4 类历史数据的模型；然后，将得到的模型应用于新的信用卡支 付。 模式识别也是一类分类问题。例如，为了识别乘客是否为潜在的恐怖分子， 机场安全部门需要将对乘客的脸部进行扫描并辨识脸部的基本模式( 例如双眼 间距、嘴的特征、头的形状等) ，然后将得到的模式与数据库中的已知恐怖分子 的模式进行比对，看看是否与其中的某一模式匹配。 2 回归 回归是指将数据项映射到一个实值预测变量。回归实际上就是学习一个可 以完成该映射的函数，首先假设一些已知类型的函数( 例如线形函数、l o g i s t i c 函数等) 可以拟和目标数据，然后利用某种误差分析确定一个与目标数据拟和程 度最好的函数。标准线形回归就是一种简单的回归实例。 3 时间序列分析 当数据的属性随着时间不断变化时，对这样的数据进行时间序列分析可以 从三个方面进行( 1 ) 确定不同时间序列的相似性；( 2 ) 检验时间序列图中线的结构 来预测序列的行为：( 3 )