（计算机软件与理论专业论文）基于改进随机决策树的入侵检测方法研究.pdf

基于改进随机决策树的入侵检测方法研究摘要随着计算机和i n t e m e t 技术的迅猛发展和广泛应用，人们在受益于信息革命所带来的巨大利益的同时，也不得不面对信息安全的严峻挑战，系统安全脆弱性的客观存在，操作系统、应用软件和网络协议等自身设计存在的安全隐患，使得由黑客攻击和病毒等带来的安全问题日益突出和复杂，造成的经济损失也日剧加大。入侵检测技术作为一种网络技术对网络安全起着重要的作用，将数据挖掘引入到入侵检测中，可以提高网络安全检测的自适应和自学习能力。然而，由于数据规模的庞大而使得许多数据挖掘模型难以适用。为此，本文以随机决策树作为描述模型，开展基于数据挖掘的入侵检测研究。主要工作如下：( 1 ) 概述了入侵检测技术的相关研究内容，探讨了随机决策树分类模型在入侵检测中的应用。( 2 ) 针对随机决策树因处理连续属性的方法过于简单而导致分类准确性下降的缺陷，提出了基于密度聚类的连续属性离散化算法，改进了随机决策树处理连续属性时的分类准确率下降问题。( 3 ) 针对随机决策树建树过程中所有属性的完全随机选择，从而导致抗干扰能力降低以及分类准确率不稳定的问题，提出一种基于属性重要度的随机决策树构造算法a s r d t ，利用粗糙集理论计算属性的重要度，从而显著提高了算法的抗干扰能力，使a s r d t 在保持原有r d t 算法优点的基础上，更具有良好的分类准确率及稳定性。( 4 ) 将改进的随机决策树模型用于入侵检测方法研究，理论和实验证明，改进的随机决策树有较好的时空性能，有效降低了误报率和漏报率，具有很强的可扩展性和环境适应性。关键词：入侵检测，数据挖掘，分类，连续属性离散化，属性重要度r e s e a r c ho ni n t r u s i o nd e t e c t i o nm e t h o dw i t hi m p r o v e dr a n d o md e c i s i o nt r e ea b s t r a c tw h ht h er a p i dd e v e l o p m e n ta n de x t e n s i v ea p p l i c a t i o no fc o m p u t e ra n di n t e m a tt e c h n o l o g y , p e o p l eb e n e f i tf r o mt h e s es om u c h ，a n da tt h es a m et i m e ，t h e yh a v et of a c et h eg r i mc h a l l e n g e so ni n f o r m a t i o ns e c u r i t y t h ev u l n e r a b i l i t yo fs y s t e ms e c u r i t y , s e c u r i t yr i s k sb yt h eo w nd e s i g no fo p e r a t i n gs y s t e m ，a p p l i c a t i o ns o f t w a r e ，n e t w o r kp r o t o c o la n d5 0o n ，a l lo fw h i c hm a k et h es e c u r i t yp r o b l e m sb yh a c k e r sa n dv i r u sa t t a c k sb ei n c r e a s i n g l ys e r i o u sa n dc o m p l i c a t e & a n da l s oc a u s et h em o r ea n dm o r ee c o n o m i cl o s s e s i n t r u s i o nd e t e c t i o n ( 1 d ) ，ak i n do fn e t w o r kt e c h n o l o g y , p l a y sa ni m p o r t a n tr o l ei nn e t w o r ks e c u r i t y i n t r o d u c i n gd a t am i n i n g ( d m ) t e c h n o l o g yi ni dc a r li m p r o v ei t ss e l f - a d a p t i v ea n ds e l f - l e a r n i n ga b i l i t y h o w e v e r , t h el a r g e - s c a l eo f i dd a t a b a s em a k e sm a n yo f d mm o d e l sh a r dt ob eu s e d t h e r e f o r e ，r a n d o md e c i s i o nt r e e ( r o t ) i si n t r o d u c e dt oc a r r yo u tt h er e s e a r c ho f l db a s e do nd m t h em a i nw o r k si nt h i sd i s s e r t a t i o ni sa sf o i l o w s ：( 1 ) t h er e l a t e dr e s e a r c he o n t e n t sa b o u ti dt e c h n o l o g ya r es u m m a r i z e df i r s t l y , a n dt h e nt h ea p p l i c a t i o no f r d tc l a s s i f i c a t i o nm o d e li ni di sp r o b e di n t od e e p l y ( 2 ) a i m i n ga tt h es h o r t c o m i n go fl o wc l a s s i f i c a t i o na c c u r a c yc a u s e db yt h es i m p l em e t h o d sr d tu s e dt od e a lw i t hc o n t i n u o u sa t l d b u t e s ，d e n s i t y b a s e dc l u s t e r i n gd i s c r e t i z i n gc o n t i n u o u sf e a t u r e si si n t r o d u c e dt oi m p r o v et h ea c c u r a c yo f r d t sd e a l i n gw i t hc o n t i n u o u sa t t r i b u t e s ( 3 ) t h es e l e c t i o no fa t t r i b u t e si nb u i l d i n gt r e ei se n t i r e l yr a n d o m ，w h i c hi n e v i t a b l yr e d u c e st h ea b i l i t yo fa n t i - j a m m i n ga n di n s t a b i l i t yo fc l a s s i f i c a t i o na c c u r a c y a c c o r d i n g l y , a na t t r i b u t e ss i g n i f i c a n c e b a s e dr a n d o md e c i s i o n t r e ea l g o r i t h m ( a s r d t ) i sp r o p o s e dw h i c hc o m p u t e st h es i g n i f i c a n c eo fa t t r i b u t eb yr o u g hs e tt h e o r yt oi m p r o v ei t sa n t i - j a m m i n ga b i l i t yd i s t i n c t l y , a n dm a k e sa s r d tn o to n l yk e e pt h ea d v a n t a g e so fr d t , b u ta l s op e r f o r m a n c eb e t t e rc l a s s i f i c a t i o na c c u r a c ya n ds t a b i l i t yt h a nt h el a t t e f ( 4 ) b o t ht h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l ts h o w st h a tt h ea p p l i c a t i o no fi m p r o v e dr d tm o d e li ni dh a sp r e f e r a b l es p a c e t i m ep e r f o r m a n c e 1 0 w e rr a t eo ff a l s ea n dl o s sa l a r m ，a n das t r o n gs e n s eo f s e a l a b i l i t ya n da d a p t a b i l i t y 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 ，c l a s s i f i c a t i o n ，d i s c r e t i z a t i o no fc o n t i n u o u sf e a t u r e s ，a t t r i b u t e ss i g n i f i c a n c e i j插图清单1 1 通用入侵检测系统模型21 2 基于神经网络的入侵检测62 1k d d 的处理过程模型1 02 2 用决策树学习解决分类预测问题的两个步骤1 52 3i d 3 算法描述1 72 4c a r t 算法描述2 03 1 随机决策树深度与准确性关系一2 43 2 随机决策树的棵数与准确性关系2 53 3 当o v e r h e a d 取不同值时基于信用卡数据集的实验结果3 04 1 棵数与误报率和漏报率的关系示例3 74 2 棵数与误分类率的关系示例3 74 3 误报率比较3 84 4 漏报率比较3 8v i图图图图图图图图图图图图图表格清单表2 1 数据挖掘的任务l l表3 1k d dc u p 9 8 数据集效益矩阵2 8表3 2 信用卡欺骗数据集效益矩阵2 8表3 3 基于k d dc u p 9 8 数据集的实验结果对比2 9表3 4 基于信用卡数据集的实验结果对比3 0表3 5 基于a d u l t 数据集的实验结果对比3 0表3 6 内存消耗比较，3l表4 1 与其它算法分类正确率的比较3 8表4 2a s r d t 与r d t 的误分类率比较3 9表5 1k d dc u p 9 9 冠军、r d t 及改进的r d t 的分类准确率比较4 4独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得金胆王些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签字多套击印签字日期：多呷年，月，z 日学位论文版权使用授权书本学位论文作者完全了解金胆王些太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金世王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位做者签名甚栖签字日期：) 一7 年，月日学位论文作者毕业后去向：工作单位：通讯地址：导师签名：签字日期：书珊嚣：织严邮编谚卯矿7致谢值此论文完成之际，我谨向在读研三年的学习和生活中给予我的关心和帮助的老师、同学、亲人、朋友们表示真挚的谢意。首先，我要感谢我的导师胡学钢教授。在近三年的硕士研究生学习中，自始至终都得到了胡老师悉心的指导，所取得的点滴进步，无不浸透着胡老师的心血。胡老师治学严谨、工作踏实、知识渊博、思维开阔，学术见解新颖独到。从胡老师身上学到的不仅学术的知识，更重要的是学做人、学处事。胡老师在这三年中以他在数据挖掘领域深厚的理论基础和对研究方向前瞻的把握，指引我从事科学研究，让我的科研之旅少了很多的荆棘与曲折。没有他的指导和帮助，没有他对我论文反复修改和精心提炼，我是不可能顺利完成我的毕业论文的。此外，胡老师一直以来不断教导我们做人的真谛，要热爱生活、热心工作，并身体力行，这种耳濡目染的熏陶和教化无疑将是我一生受用无穷的宝贵财富。另外，我要十分感谢计算机与信息学院的王浩教授，在我攻读硕士期间，他了我大量的指导、关怀和帮助，并提出了许多宝贵的意见，令我在成长的路上受益匪浅。感谢吴共庆老师和王德兴老师，他们的谆谆教导和倾力相授让科研阶段的沟壑变成坦途；另外，感谢王东波同学细心的讲解聚类相关知识，使我能够顺利地完成小论文，感谢史君华、张圆圆、李洋、谢飞、刘卫同学，与他们的交流和讨论拓宽了我的视野和思路。感谢合肥工业大学人工智能与数据挖掘研究室每个成员，与他们一起学习生活的点点滴滴都是愉快而难忘的。感谢计算机与信息学院的王新生老师、徐静老师为我所付出的辛勤工作!最后，我要衷心的感谢我的家人，是他们几十年来一直默默地给与我无尽的关怀和帮助。这种支持不但使我能够顺利地完成学业，也将激励着我在今后的日子里不断的前进。1 1 1作者：李楠2 0 0 7 年5 月第一章入侵检测系统本章首先简述了入侵检测和入侵检测系统的相关概念，按照信息的来源，数据分析方法及实效性等不同的分类方法介绍了入侵检测系统的类别，然后详细介绍了现有不同种类的入侵检测技术，总结了各种检测技术的优缺点。随着计算机和i n t e r a c t 技术的迅猛发展和广泛应用，人们在受益于信息革命所带来的巨大利益的同时，也不得不面对信息安全的严峻挑战，系统安全脆弱性的客观存在，操作系统、应用软件、硬件设备和网络协议自身设计存在的安全隐患，使得由黑客攻击和病毒等带来的安全问题日益突出和复杂，造成的经济损失也日剧加大。由于各种网络攻击的多元化和复杂化，单纯依赖防火墙等静态防御难以对付层出不穷的入侵技术，入侵检测技术的出现弥补了防火墙的不足。近年来，入侵检测系统i d s ( i n t r u s i o nd e t e c t i v es y s t e m ) 作为安全防御体系的一个重要组成部分，通过将实时的捕捉和分析系统与网络监视系统相结合，对计算机和网络资源上的恶意使用行为进行识别和响应，成为了网络安全研究热点。1 1 入侵检测和入侵检测系统( i d s ) 的概念入侵检测基本框架概念由j a m e sa n d e r s o n 于1 9 8 0 年在技术报告“c o m p u t e rs 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 ”，他将入侵尝试或威胁定义为：潜在的、有预谋的、未经授权访问信息和操作信息，致使系统不可靠或无法使用的企图。入侵行为一般可以分为外部闯入、内部授权用户的越权使用和滥用三种类型1 2 jj 。1 9 8 7 年，d o r o t h yd e n n i n g 首次提出来了将入侵检测的概念作为一种计算机系统安全防御问题措施及一种通用入侵检测系统的抽象模型1 4 , 5 1 ，这个模型以主机上的审计记录文件为基础，通过采用基于规则的特征匹配的专家系统，发现主机上可能的入侵行为，为入侵检测系统研制奠定了基础。1 9 9 0 年，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 ) ，它与此前的入侵检测系统相比它不再检查主机系统的审计记录，而是通过主动的监视局域网上流量来追踪可疑的行为。入侵检测是一种用于检测任何危害或企图危害信息系统保密性( c o n f i d e n t i a l i t y ) 、完整性( i n t e g r i t y ) 和可用行( a c c o u n t a b i l i t y ) 行为的一种网络技术。通过采用异常检测( a n o m a l yd e t e c t i o n ) 或误用检测( m i s u s ed e t e c t i o n ) 的方式对计算机和网络资源上的恶意行为进行识别和相应处理，能够在网络系统受到危害之前拦截入侵。作为一种积极主动的安全防护技术，入侵检测与传统安全防御机制不同在于，它不仅可以检测外部入侵行为，也可以找出内部用户的越权使用和滥用行为，目前己经成为网络安全中的一个研究热点。入侵检测系统( i n t r u s i o nd e t e c t i o ns y s t e m ) 是执行入侵检测任务的程序。它通过检查特定的攻击模式、欺骗程序、配置问题、独立事件、存在缺陷的程序版本和其他黑客可能利用的漏洞来监控和安全有关的活动。图1 1 是美国斯坦福国际研究所( s r i ) 的d e n n i n g 于1 9 8 7 年提出的一个通用的入侵检测系统模型，该模型假设安全破坏是有异于系统正常应用模式的行为，可以通过监视系统的审计记录检测到。蹇图1 1 通用入侵检测系统模型该模型由以下六个主要部件构成：主体( s u b j e c t s ) 、对象( o b j e c t s ) 、审计记录( a u d i tr e c o r d s ) ，活动档案( a c t i v i t yp r o f i l e ) ，异常记录( a n o m a l yr e c o r d ) 。规则集( r u l es e t ) 各部分的主要功能如下：( 1 ) 主体：启动在目标系统上活动的实体，如用户或系统本身。( 2 ) 对象：系统资源，如文件、设各、命令等。( 3 ) 审计记录：入侵检测系统中使用的审计数据一般来自系统日志、防火墙或者网络通信、系统审计跟踪等应用子系统。因此这些数据一般不具有统一的格式，故审计记录可以定义为更高一级的抽象，如网络通信中的一次连接等，而不是低级抽象。，( 4 ) 活动档案：用以保存监视中主体的正常活动信息，具体实现依赖于检测方法。旦事件在审计数据中出现，活动档案就会根据检查出来的活动创建新的变量。( 5 ) 异常记录：用以表示异常事件的发生情况。( 6 ) 规则集：是一个决定入侵是否发生的处理引擎。结合活动档案用入侵检测技术分析收到的审计记录，调整内部规则或统计信息，在判断出有入侵发生时采取相应的措施。i 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 ) 与它的后继版本n i d e s ( 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 ne x p e r ts y s t e m ) 均基于d e n n i n g 的该通用模型。2d e n n i n g 模型的最大缺点在于它没有包含已知系统漏洞或攻击方法的知识而这些知识在许多情况下是非常有用的信息。1 2 入侵检测系统分类入侵检测系统可按照其采用的技术、系统所检测的对象及实时性等多种方式进行分类。1 2 1 按照信息的来源分类根据入侵检测系统的不同信息来源，通常将它们划分为三类：基于主机的入侵检测系统、基于网络的入侵检测系统和混合分布式入侵检测系统。( 1 ) 基于主机的入侵检测系统。基于主机的入侵检测系统历史悠久，是指在单个主机上运行一个或多个代理程序，该代理程序作为检测引擎，对需要检测主机上的数据进行采集、分析和判断，并对照主机行为特征库判断是否为入侵行为，如是则将警报信息发送给控制端程序，由管理员集中管理。此外，代理程序也定期向控制端发送信号，用于管理员确信代理程序是否正常工作。此类系统一般主要使用操作系统的审计跟踪日志作为输入，例如安全审计记录、系统日志、系统配置文件的完整性情况、应用服务程序产生的日志文件等。该类i d s 检测程序比较简单，针对性较强，误报率较低，可以精确地分析入侵活动提供关于入侵的更详尽的信息，这使其在获取高层信息以及实现一些特殊功能( 如针对系统资源情况的审计) 方面具有无法替代的优势。但他只能检测该主机上发生的入侵，对来自网络底层的攻击无能为力，且主要依赖于特定的操作系统和审计跟踪日志获取信息，此类系统的原始数据来源受到具体操作系统平台的限制，系统的实现有过强的针对性，在环境适应性、可移植性方面问题较多，所以基于主机的i d s 在网络系统中有很大的局限。( 2 ) 基于网络的入侵检测系统。随着网络环境的普及，来自网络的攻击事件逐渐成为信息系统的最大威胁，因而出现了大量基于网络的入侵检测系统，该类i d s 在网络中的某一点监听网络上传输的原始流量，通过线路窃听的手段对截获的网络分组进行处理，从中提取有用的信息，并通过协议分析、特征匹配、统计分析等手段提取特征模式，再与己知攻击特征或正常网络行为原型相比较识别攻击事件。基于网络的i d s 同基于主机的i d s 相比，在适应性、实时性、可扩展性方面具有所改进，并且可以检测到某些种类的攻击，如远程缓冲区溢出、网络碎片攻击等针对协议或特定网络服务的攻击手段。但此类系统也存在一些弱点，如更容易受到基于网络的拒绝服务等恶意攻击，在实现技术上更为复杂，在高层信息的获取上更为困难等。( 3 ) 混合分布式入侵检测系统。随着网络系统结构的复杂化和大型化，网络入侵手法趋向于分布式、协同式方向发展，单一的基于主机的入侵检测系统或是基于网络的入侵检测系统都会造成主动防御体系不全面。进入2 0 世纪9 0年代后，出现了把基于主机和基于。网络的入侵检测结合起来的分布式入侵检测系统。混合分布式i d s 可以从不同的主机系统、网络部件和监听方式收集数据，不同类型的l d s 之间优势共享，缺陷互补，协同检测，更加精确地识别和定位入侵行为，成为目前的研究热点和未来发展的趋势，但分布式入侵检测系统本身还很不成熟，还存在很多问题如系统资源如何有效分配，各检测实体如何通信，i d s 之间的信息交换和共享机制如何形成一个统一的标准等等。1 2 2 按照数据分析方法分类从数据分析手段看，入侵检测通常可以分为两类：异常入侵检测和滥用入侵检测6 ，7 ，3 1 。( 1 1 异常入侵检测。异常入侵检测的假设条件是检测攻击行为可以通过区分当前活动与系统历史正常活动之间的差异来实现。这种检测的特点是首先总结正常操作应该具有的特征，建立一个关于系统正常活动的状态模型，此后，对后续的操作进行监视，将用户当前的活动情况与这个正常模型进行对比，一旦发现偏离正常统计学意义的操作模式，即进行报警。这种方法的优点是可以识别出未知的入侵行为，因此成为目前i d s 的主要研究方向；它的缺点主要是：比学枚举所有的正常使用规则，否则会导致误报的产生，另外，在判断某行为是否正常时，不能做简单的匹配，而要利用统计的方法进行模糊匹配，这在实现上有一定的难度。异常检测采用的主要技术有：统计分析、神经网络、基于规则的检测等。( 2 ) 滥用入侵检测。与异常入侵检测相反，滥用入侵检测通过分析各种类型的攻击手段，建立相关的规则库，在对收集到的数据进行检测时，与特征库中的特征代码相比较，如果发现满足条件的匹配，则指示发生了一次攻击行为。这种检测的特点是收集入侵行为的特征，能很好的识别己知的入侵形式，检测的方法也比较简单，具有较高的检测率和较低的误报率，且容易实现；缺点是不能不断的更新模式库，无法相应未知的、新的攻击形式，漏报率很高。1 2 3 按照实效性分类( 1 ) 脱机分析。脱机分析指在行为发生后，对收集的审计日志文件进行离线分析处理，找出可能的攻击行为踪迹，目的是进行系统配置的修补工作，防范以后的攻击，如日志的审核、系统文件的完整性检查都属于脱机分析。( 2 ) 联机分析。联机分析通过实时监控网络流量，在数据产生或者发生改4变的同时对其进行检查，在出现异常活动时及时做出反应，这种方法一般用于网络数据的实时分析，对系统资源要求比较高。1 3 常用的入侵检测技术目前的入侵检测系统模型构造中使用的检测方法很多，常用的检测方法有：基于统计的异常检测方法，基于专家系统入侵检测方法，基于贝叶斯推理的异常检测方法等，具体介绍如下。1 3 1 基于统计的异常检测方法基于统计分析的异常检测是最早的检测方法。著名的入侵检测系统i 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 ) 以及它的后继版本n i d e s 中所包含的异常检测模块都属于此类别。统计分析方法首先给用户、文件和设备等系统对象创建一个统计描述。根据用户对象的动作为每个用户建立用户特征表，通过比较当前特征与正常活动的状态特征，判断行为是否异常。算法如下，设一个用户的特征文件有n 个特征变量m l ，m 2 ，m 。，这些变量可以是文件访问数量、网络回话时间，c p u 的使用、i 0 的使用地点及时间等等。用s i ，s 2 ，s 。分别表示变量m l ，m 2 ，m 。的异常测量值，其中s i 是越大越异常，总的异常度s = a l s ? + a 2 s ；+ + a 。s ：，其中a i 表示各个特征变量的权重且a i 0 ，将异常度s 的平均值与网络、系统的行为进行比较，如超出正常值范围则认为有入侵发生。该算法的前提是m j 必需是完全独立，然而通常情况下并不能满足。统计方法的最大优点是它可以学习用户的使用习惯，从而具有较高的检测率和可用性，但是它的学习能力也给入侵者提供机会，入侵者可以通过逐步恶意训练系统，使入侵事件符合正常操作的统计规律，使系统误认为是正常行为。另外，统计方法不能反映事件在时间顺序上的前后相关性，而许多预示着入侵行为的系统异常都依赖于事件的发生顺序，因此，使用统计方法进行异常检测有很大的局限性，此外统计分析模型所面临的另一个棘手问题时如何确定合适的阀值，如果选择的不恰当，就会导致系统误报率( f a l s ep o s i t i v e s ) 、漏报率( f a l s en e g a t i v e s )的升高。1 3 2 基于专家系统入侵检测方法专家系统是基于一套由专家经验事先定义的规则的推理系统，分为控制推理阶段和问题解决的规范化阶段，专家系统将策略声明和己知的攻击编码成一个规则集，其中规则具有i f t h e n 的格式，只有当规则的全部条件都满足的时候，规则表示式中右边的动作才会执行。根据这个规则集对入侵检测系统收集的审计日志事件信息做出结论。规则集的修改需手工完成，并有可能结合了5统计或概率的因素，建立专家系统的关键在于审计记录的完备性与实时性。这种检测方法应用的实际问题时需要处理大量的数据并且依赖于审计记录的完备性与实时性。专家系统的优点在于把系统看作一个自治的黑盒子，使推理控制过程和问题的最终解答分离。其缺点在于系统本身必须要用安全的专家知识来构造，且系统的能力受限于专家知识，很可能造成漏判，误自学习和自适应能力，同时，当对规则进行增加和删除操作时需手工完成，并有可能结合了统计或概率的因素，另外，还必须考虑规则集中不同规则之间的依赖性。1 3 3 基于贝叶斯推理的异常检测方法基于贝叶斯推理的异常检测方法是通过在任意给定的时刻，测量特征变量c l ，c 2 ，c 。，推理判断系统是否有入侵事件发生，其中c i 表示网络回话时间、i o 的使用地点及时间等系统对象。假定c i 变量有两个值，l 表示异常，0 表示正常，e 表示系统当前遭受入侵攻击。每个异常变量c i 的异常可靠性和敏感性表示p ( c i = i e ) 和p ( c i = l 、e ) ，则在给定每个c i 值的条件下，由贝叶斯定理得出i 的可信度。根据各种异常测量的值、入侵的先验概率及入侵发生时每种测量到的异常概率，能够检测判断入侵的概率。但是为了检测的准确性，还必须考虑每个测量c i 之间的独立性。通过相关性分析，确定各个异常变量与入侵的关系。1 3 4 基于神经网络的异常检测方法基于神经网络的入侵检测方法是训练神经网络连续的信息单元，其中信息单元指的是命令。网络的输入层是用户当前输入和已经执行过的命令，是神经网络用来预测用户输入下一个命令的依据，如图1 2 所示。h，朋哇v i磺下一图1 2 基于神经网络的入侵检测神经网络最终将被训练成预测用户输入命令序列集合，该结构就构成了用户的命令轮廓框架。当用这个神经网络不能正确预测出用户的后继命令时，表明用户行为在某种程度上与轮廓框架存在偏离，则认为有异常事件发生，基于神经网络的入侵检测系统就是根据这一点进行异常检测的。在图1 2 中，输入6层箭头指向用户最近输入执行的命令序列，通过将每个输入以某种方式编码，把输入命令表示成几个值或级别的形式成为命令的唯一标识，输出层由单一的多层输出构成，用于预测用户发出的下一个命令。这种方法的优点是不依赖于任何有关数据种类的统计假设，能较好的处理噪声数据，同时，也可以比较自然的说明各种影响输出结果测量的相互关系，但是网络拓扑结构和元素的权值分配较难确定。1 3 5 基于免疫系统的入侵检测方法n e wm e x i c o 大学的f o r r e s t 等人注意到在生理免疫系统和系统保护机制之间有着显著的相似性，两者正常运行的关键是执行了“自我非自我”决定能力。f o r r e s t 等通过大量实验发现；对一个特定的程序来说，其系统特权进程调用序列是相当稳定的，使用系统调用序列来识别“自我”，可以满足系统的要求。在考虑了数据量，可靠检测误用能力及以一种适合高级模式匹配技术编码的适合度等数据的大量目标的基础上，将系统调用作为一个主要信息源时，且进一步忽略传递给调用的参数，集中在短顺序的系统调用上，仅看它们的临时顺序。该系统按两个阶段进行入侵分析处理，第一阶段建立一个以系统处理为中心的正常行为特征轮廓知识库：第二阶段，将特征轮廓用于监控异常系统行为。源于调用特权程序的系统调用顺序随着时间流失被收集，系统特征轮廓由长度为l ，0 的独一无二的序列组成。系统使用成功的开拓、不成功的开拓和错误条件度量描述正常行为的偏离，取得了令人满意的结果。免疫方法主要特征在于分层保护、分布式检测、能够检测未知类型攻击行为，但是该方法对于一些包括种族条件、伪装和策略违背等不涉及到系统特权进程的使用的攻击行为，往往无能为力。1 3 6 基于数据挖掘的入侵检测方法各种检测技术在性能方面均存在差异，至今还没有一种技术能够独占鳌头。以上介绍的入侵检测系统的工作原理与病毒检测相似，自身带有一定规模和数量的入侵特征模式库，特征模式库的提取和更新依赖于手工方式，缺乏自适应了自学习的能力，更新方式不灵活，且仅对己知的攻击手段有效。虽然基于神经网络和免疫方法的入侵检测系统自适应性较好，但它们对入侵的表示不具可理解性，用户无法进一步了解入侵模式，也无法为现有系统中存在的问题提供解决方法。随着人工智能技术的不断发展，各种机器化的方法受到研究者的关注，成为近年来研究的热点。另外如何将异常检测技术和滥用检测技术相结合，采用不同的模块以达到良好的性能也是学者们的研究方向。综上所述，我们寻找的方法应当具备自学习能力，对入侵的表达直观，能够参与异常检测和滥用检测，对己有的系统具备一定的兼容性。数据挖掘程序处理收集到的审计数据，全自动的为各种入侵行为和正常操作建立精确的行为模式，不需要人工分析是一个很好的解决方案。关于数据挖掘的方法，将在后面的章节中详细的介绍。1 4 本文的研究内容与组织入侵检测技术作为一种网络技术对网络安全起着重要的作用，将数据挖掘引入到入侵检测中使其可以适应海量数据的环境，同时，提高了自适应和自学习能力，有重要的研究价值，本文在对入侵检测及数据挖掘进行概述，详细介绍了随机决策树分类模型的相关知识，客观分析现有算法的优劣性，并结合现实世界数据特性及实际应用情况，提出基于属性重要度及联系属性离散化的随机决策树模型，全文由五章组成：第一章首先简述了入侵检测和入侵检测系统的相关概念，按照信息的来源，数据分析方法及实效性等不同的分类方法介绍了入侵检测系统的类别，然后详细介绍了现有不同种类的入侵检测技术，总结了各种检测技术的优缺点。第二章首先简述数据库知识发现产生的原因以及发展前景，概述了知识发现的处理过程和特性，然后详细阐述了知识发现的核心技术，介绍了决策树分类模型，结合入侵检测数据的认真分析了各种决策树分类算法的优缺点，并对各种算法进行比较。第三章引入随机决策树分类模型，详细介绍了如何启发式选择随机决策树的深度及棵树，通过实验证明了该算法的有效性和高效性，最后对随机决策树模型进行分析，得出该模型非常适合应用于入侵检测系统中。第四章针对随机决策树抗干扰能力较低，分类准确率的不稳定的缺点，本章提出一种基于属性重要度的随机决策树构造算法即a s r d t 算法，算法利用粗糙集理论计算每个属性的属性重要度，提升重要属性的影响因子，提高了算法的抗干扰能力，使a s r d t 在保持原有r d t 算法优点的基础上，更具有良好的分类准确率及稳定性。第五章针对随机决策树在对连续属性处理时方法过于简单，降低了分类的准确性的不足，本章开展了基于密度聚类算法的连续属性离散化方法的研究，改进了随机决策树处理连续属性导致的分类准确率下降问题。第六章总结全文并对下一步工作进行展望。8第二章数据挖掘随着信息化的不断深入，人们收集、存储数据的能力远远超过了对其分析数据的能力，从大量的历史数据中提取有用的知识变得越来越困难了。k d d 就是在这种背景下产生的，并迅速得到广泛关注，成为当前人工智能领域的研究热点。本章简述数据库知识发现产生的原因以及发展前景，概述了知识发现的处理过程和特性，然后详细阐述了知识发现的核心技术，介绍了决策树分类模型，结合入侵检测数据的认真分析了各种决策树分类算法的优缺点，并对各种算法进行比较。2 1 数据挖掘概述随着计算机科学与技术的飞速发展，人类产生和收集数据的能力已经迅速提高，起作用的因素包括如：商业事务、政府事务、农业生产和科学研究过程的信息化。条形码( b a rc o d e s ) 在大部分商业产品中的广泛使用；快速、高性能和廉价的存储设备；更好的数据库管理系统和数据仓库技术等信息技术和数据存贮技术的发展。随着数据库中存储数据量急剧增大，收集和存储数据的能力已经大大超过了对其分析和综合处理的能力，迫切需要将这些数据转换成有用的信息和知识，由此数据库知识发现( 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 ) 9 - i 1 j 便酝酿而生。近年来，数据库知识发现越来越受到信息产业界的重视。关于k d d 的定义众多学者有不同的意见，其中被公认为比较完整、深刻和全面的是由f a y y a d 在1 9 9 6 年【1 3 1 的会议论文中将k d d 定义为：“t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv 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 si nd a t a ”即k d d 是从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、并能最终被人理解的模式的非平凡的处理过程。可见，k d d 是从数据库中提取有价值知识的过程i l “。k d d 的研究目的是为了将知识发现的研究成果应用于实际数据处理中，为科学的决策提供知耻。通常情况下，将从实际数据到发现潜在知识的整个k d d过程分为以下几个步骤：数据准备，数据选择，数据预处理，数据转换，确定k d d 目标，确定知识发现算法，数据挖掘，模式解释与评价，知识表示 i “。一般将k d d 中进行知识发现的阶段称为数据挖掘( d a t am i n i n g ，d m ) l iz l ，关于k d d 的研究大多着重于对数据挖掘的研究。某些应用领域已经不对数据挖掘与k d d 加以区分地使用，某种意义上二者可看作同一个概念。92 2 数据挖掘过程图2 1 描述了数据挖掘的基本过程和主要步骤，研究业务对象是整个数据挖掘的基础，它驱动了整个数据挖掘过程，也是检验最后结果和指导分析人员完成数据挖掘的依据。图2 1 各步骤按照一定顺序进行，整个过程中还会存在步骤问的反馈，各步骤的大体内容如下：卜一数据准备卅一数据挖掘l 瓷某表选和解释- 4图2 ik d d 的处理过程模型( 1 ) 确定业务对象清晰的定义业务问题，认清数据挖掘目的是挖掘过程的重要一步。挖掘的最后结果是不可预测的，但要探索的问题应该是有预见的，为了数据挖掘而数据挖掘则带有盲目性，是不会成功的。( 2 ) 数据准备数据准各又可分为三个子步骤：数据选择、数据预处理、数据转换。数据选择的目的是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除噪声、推导计算缺省数据、消除重复记录等。数据转换将数据转换成一个分析模型，该模型是针对挖掘算法建立的，建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。( 3 ) 数据挖掘阶段对所得到的经过转换的数据进行挖掘。除了完善或选择合适的挖掘算法外，其余一切工作都能自动地完成。尽管数据挖掘算法是整个挖掘过程的核心，也是目前研究人员的主要努力方向，但要获得好的挖掘结果，必须对各种挖掘算法的要求或前提假设有充分的理解。( 4 ) 结果分析及知识的同化1 0解释并评估结果，其使用的分析方法一般应视数据挖掘操作而定，通常会用到可视化技术。最后将分析所得到的知识集成到业务信息系统的组织结构中去。数据挖掘过程的分步实现过程中，不同的步骤需要有不同专长的人员，他们大体可以分为三类：精通业务的业务分析人员、精通数据分析技术的数据分析人员以及精通数据管理技术的数据管理人员。由此可见，数据挖掘是一个多个专家合作的过程，也是一个在资金和技术上高投入的过程。2 3 数据挖掘技术数据挖掘涉及的学科领域和方法很多，有多种分类法f i5 1 。其中根据开采方法可粗略地分为：统计方法、机器学习方法、神经网络方法和数据库方法。其中统计方法可再分为：回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、非参数判别、费歇尔判别等) 、聚类分析( 系统聚类、动态聚类、密度聚类等) 、探索性分析( 主元分析法、相关分析法等) 等。而机器学习中，又可细分为：归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗传算法等。神经网络方法又可分为：前向神经网络( b p 算法等) 、自组织神经网络( 自组织特征映射、竞争学习等) 等。根据开采任务的不同可分为分类、聚类、关联规则发现、序列模式发现等等。表2 1 列出了数据挖掘主要方法，概况和典型应用领域。下面将对以上开采任务进行简单的介绍。表2 1 数据挖掘的任务数据挖掘算法典型应用任务关联规则统计学集台理论购物篮分析市场分析分类决策树神经网络粗糙集产品行销保险业银行信贷聚类神经网络统计学市场分析序列模式统计学集合理论购物篮分析偏离发现统计学医疗2 3 1 分类( c 1 a s s i f i c a t i o n )分类是最基本的一种认知形式，人类认识事物从分类开始，分类能力是人类智能的基础。在从大规模数据库获得知识的过程中必然涉及到数据分类问题i i6 l 。数据分类是从一组已知的、已分类的数据中提取出一个模型( 也称作分类器) ，该模型能把数据库中的数据项映射到给定类别中的某一个，从而实现对数据的分类。分类问题作为数据挖掘的一个重要研究主题，被广泛应用于疾病诊断，银行信贷等领域。当前研究的分类模型主要有决策树( d e c i s i o nt r e e ) ，统计方法( s t a t i s t i c s ) ，神经网络( n e u r a ln e t w o r k ) ，遗传算法( e v o l u t i o n a r ya l g o r i t h m s ) 等，决策树以其准确率高、计算量相对小、易于理解等优点被广泛于各个领域。常用的决策树分类算法有：i d 3 ，c 4 5 ，c a r t ，s l i q 等。本文主要研究是一种新的决策树模型在入侵检测系统中应用，研究结果表明，与其它入侵检测技术相比该方法在占用较小时空的前提下，有很低的漏报率和误报率及很强的实用性。2 3 2 聚类( c l u s t e r i n g )“物以类聚，人以群分”，聚类就是按照事物间的相似性进行区分和分类的过程。聚类分析数据对象，不考虑已知的类标记。在人工智能和模式识别中聚类分析也被称为“无先验学习”，是机器学习中知识获取的重要环节。聚类是用数学方法研究和处理所给对象的分类以及各类之间的亲疏程度，是将物理或抽象对象的集合分组成为有类似的对象组成的多个类的过程，是在对数据不做任何假设的条件下进行分析的工具。它将物理或抽象对象的集合分为由类似的对象组成的多个簇。簇( c l u s t e r ) 是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异，聚类应该使簇内个体间的相似性最大，而簇间的相似性最小。当存在大量的聚类算法，具体使用哪种算法取决于数据的类型、聚类目的和应用，如下将讨论在数据领域中常用的一些聚类算法。( 1 ) 基于划分的方法( p a r t i t i o n i n g b a s e dm e t h o d )对于给定的包含n 个数据对象的数据集，通常基于划分的方法要求用户给定构建划分类的数目k ，每个划分表示一个聚簇，并且k v ，通