（计算机软件与理论专业论文）蚁群分类算法的改进及在入侵检测中的应用.pdf

中山大学硕士学位论文 蚁群分类算法的改进及在入侵检测中应用 蚁群分类算法的改进及在入侵检测中的应用 专业：计算机软件与理论 硕士生：何俊兵 指导教师：龙冬阳教授 摘要 入侵检测中需要对大量的审计数据进行分析，基于数据挖掘的入侵检测是以 数据为中心的思想，在大量审计数据中发现用以区分正常入侵行为的模式。提高 基于数据挖掘的入侵检测性能，很重要的一点就是使用高性能的挖掘算法，算法 的智能化是一个主要的研究方向。本文的研究将一种新颖的高效智能分类算法首 次应用到了入侵检测中。本文的工作主要集中在下面两点： 其一是蚁群分类算法的改进。基于规则的分类算法的一个重要问题是如何以 较短的规则获取较高的分类准确率，而规则长度和分类准确率是一对矛盾，不可 能同时达到最优。本文构造了一个新的规则质量函数，提供了两个参数实现预测 准确度和规则长度权值的在大的范围内可调整，试验证明这一改动是成功的。另 外还在蚁群分类中引入了多蚁群并行工作的思想，加上其他些零星的改动，算 法在多数数据集上能以较短的规则获得较高的的准确率。相比原算法性能有大幅 度的提高，并通过大量实验证明了其分类性能。 其二就是把蚁群算法用在了入侵网络误用检测中。现有的很多软计算方法都 已用被用在了入侵检测中，但是基于蚁群算法的入侵检测目前尚未有人研究。由 于蚁群分类算法的计算复杂度和启发式贪婪搜索算法r i p p e r 相同，而r i p p e r 因算 法复杂度和训练实例数无关而被认为是最适合入侵建模的算法，再加上改进之后 的算法引入了弹性机制，因此改进后的蚁群分类是很适合异常检测的。本文使用 改进后的算法网络入侵数据集k d dc u p 9 9 上进行了检测实验，在经过数据清理， 经属性约简和离散化等预处理后，对其进行了挖掘实验，对实验结果进行了相关 分柝，证明了蚁群分类算法在入侵检测中表现出优异的检测性能。 关铡! 词：数据挖掘：入侵检测；蚁群算法；分类算法 中山大学硕士学位论文蚁群分类算法的改进及存入侵检测巾应用 t h ei m p r o v e m e n to f a n tb a s e dc l a s s i f i e ra n di t sa p p l i c a t i o n i ni n t r u s i o nd e t e c t i o n m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：h e j u n b i n g s u p e r v i s o r ：p r o f l o n gd o n g y a n g a b s t r a c t d a t a m i n i n gm e t h o d sa r ed e s i g n e d f o re x t r a c t i n g p r e v i o u s l yu n k n o w ns i g n i f i c a n t r e g u l a r i t i e si nl a r g ed a t ac o l l e c t i o n s ，a n dh a v eb e e ns u c c e s s f u l l yu s e df o rd i f f e r e n t a p p l i c a t i o n sw i t hl a r g ea m o n g o fd a t as u c ha si n t r u s i o nd e t e c t i o n r u l ei n d u c t i o ni sa n i m p o r t a n tt a s k o fd a t am i n i n g ，w h i c hd i s c o v e r sa c c u r a t ea n dc o m p r e h e n s 洳l e k n o w l e d g e t h ed i s c o v e r e dk n o w l e d g ei su s u a l l yr e p r e s e n t e di nt h ef o r mo fi f - t h e n w a y s , w h i c hh a v e t h e a d v a n t a g eo fb e i n g ah i g h l e v e l , s y m b o l i ck n o w l e d g e r e p r e s e n t a t i o n ，c o n t r i b u t i n gt ot h ec o m p r e h e n s i b i l i t yo ft h ed i s c o v e r e dk n o w l e d g e a n tb a s e dc l a s s i f i e rh a sb e e np r o p o s e dt oe x t r a c tc l a s s i f i c a t i o nr u l e st h a tc a np r e d i c t t h ec l a s s l a b e lo fa nu n l a b e l e di n s t a n c e i nt h i sp a p e rw ed e s c r i b eav a r i e t yo f m o d i f i c a t i o n st h a tw eh a v em a d et ot h ed a t am i n i n ga l g o r i t h m si no r d e rt oi m p r o v e a c c u r a c ya n de f f i c i e n c y w ea l s oi m p l e m e n tt h em o d i f i e da l g o r i t h mo ni n t r u s i o n d e t e c t i o n t h ea n tc o l o n ya l g o r i t h mi se m p l o y e dt od e r i v eas e to fc l a s s i f i c a t i o nr u l e s f r o mn e t w o r ka u d i td a t a , a n dan o v e lf r a m e w o r ki su t i l i z e da sf i t n e s sf u n c t i o nt oj u d g c t h eq u a l i t yo fe a c hr u l e u n l i k em o s te x i s t i n gc l a s s i f i c a t i o na l g o r i t h m ，t h ep r o p o s e d m e t h o dp r o v i d et h ef l e x m i l i t yt og e n e r a t ee i t h e rm o r ea c c u r a t eb u tl e s ss i m p l eo rl e s s a c c u r a t eb u ts i m p l e rr u l es e t a n dt h el e n g t ho ft h er u l e si sa d j u s t a b l e t h ee x p e r i m e n t a l r e s u l t ss h o wt h a to u ra p p r o a c hi se f f e c t i v e k e yw o r d s ：d a t am i n i n g ；a c o ；i n t r u s i o nd e t e c t i o n ；c l a s s i f i c a t i o n i i 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 1 1 研究的背景及意义 第一章绪论 入侵检测技术是继防火墙、数据加密等传统信息安全保护措施后的新一代安 全保障技术，已经成为现代安全保护体系结构的一个重要组成部分。它的主要目 的是在于检测未授权用户、误用系统以及网络的内部和外部用户的超权行为( 也 就是我们通常所说的攻击行为) 。入侵检测通常对用户正常行为和入侵行为进行建 模，通过分析两者间的差异来检测攻击者的入侵 1 ，2 。 入侵检测分三个阶段：第一个阶段是从主机系统或者网络数据中获得数据来 源，即信息收集阶段：第二个阶段对收集到的进行分析信息分析，利用系统中已 有的检测模型检测系统是否受到非法入侵：第三个阶段按照分析的结果对信息和 计算机系统进行相关的处理 2 。本文的工作集中在检测模型的构建，把检测模型 的构建看作是一个数据分析的过程。 传统的入侵检测技术有：模式匹配、异常检测和完整性分析 3 ，4 ，这些检 测方法的共同特点是漏报和误报率偏高，对网络结构和攻击手段改进的适应能力 不强，同时建模或检测过程需要较多的人为分析。随着网络技术的进步和网络流 量的增大，海量的审计数据以及网络环境和网络攻击的复杂性，使传统的检测技 术越来越难以满足要求。为此，哥伦比亚大学l e e 等人最早于1 9 9 9 年提出以数据 为中心的思想，利用数据挖掘在有效利用信息方面的优势，将入侵检测视为一类 数据分析过程，研究审计数据建模的可行性和有效性，并构造出检测模型 5 ，6 。 这一研究有效地提高了入侵检测系统的可用性和适应性，并且很大的扩展了入侵 检测的研究领域，此后的研究中，数据挖掘在入侵检测上的应用成为了该领域主 要的研究方向之一。 数据挖掘是指在在大量的数据中识别出最有效的、新颖的、具有潜在效用乃 至最终可以理解的模式的过程 7 。在入侵检测中，数据挖掘的任务就是要在大量 的主机和网络审计数据中发现用以区分正常行为和入侵行为的模式，通过分析历 j 史数据可以提取出用户的行为特征、总结入侵行为的规律，从而建立起比较完备 的规则库来进行入侵检测 6 。数据挖掘包括关联规则发现、分类分析、聚类分析、 中山大学硕士学位论文 蚁群分类算法的改进及在入侵检测l _ | j 应j ；l ；l 时间序列分析等不同的方法，这些方法在入侵检测中都得到了不同层次的应用， 很多时候为了发现一个有用的模式需要组合利用不同的方法。 分类在数据挖掘中是一项非常重要的任务。分类的目的是学会一个分类器或 分类模型( 也常常称作为分类器) ，该模型能把数据库中的数据项映射到给定类别 的某一个。分类可用于预测。预测的目的是从利用历史数据记录中自动推导出对 给定数据的推广描述，从而能对未来数据进行预测。入侵检测中，分类的主要应 用是在预先做了入侵标识的数据集上挖掘出分类模型 1 0 ，1 1 ，用以预测新数据是 否属于入侵。若用于分类的数据集是人为获取的真实的入侵数据( 使用蜜罐或在 实验环境中获取，如k d dc u p 9 9 1 2 ) ，那么分类的结果属于误用检测模型，若数 据集是对计算机审计数据聚类分析的结果，则分类的结果属于异常检测模型。本 文的研究重点是分类算法在网络误用检测中的应用。 目前基于数据挖掘的入侵检测研究主要集中在两个方向上 1 3 ：1 、分布式入 侵检测中的数据挖掘与数据融合；2 、智能化的数据挖掘算法在入侵检测中的应用 1 1 ，1 5 。本文的研究目的，就是引入一种较为新颖的智能算法，把相应的数据挖 掘技术用于入侵检测系统中。文中对基于蚁群优化的智能分类算法 1 6 提出了一 系列的改进，提出一种新的算法框架，在大量实验的基础上较大幅度的提高了原 算法的性能，并且首次把蚁群分类应用在网络误用检测中。本文使用检测入侵检 测的通用数据集k d dc u p 9 9 对算法进行了验证性的实验，仿真结果证明该算法是 高效可行的。 1 2 国内外研究概况 在数据挖掘的研究中，预测模型的研究是一个很重要的问题。而分类是预测 的手段之一，因此分类方法的研究又是至关重要的。韩国汉城中央大学的a j i t h a b r a h a m 的研究团队 4 9 在把智能分类算法应用到入侵检测中做了大量的工作， 研究了主要的几种高性能智能分类算法用于入侵建模 5 0 5 7 并比较了其中分类 效果 1 3 ，提出新颖的数据挖掘框架提升了模型的监测性能，为这个领域的研究 做出了很好的总结与扩展。他们的若干工作是本文的主要参考文献之一。 分类器的构造方法主要有 7 统计方法、机器学习方法、神经网络方法等。统 计方法包括贝叶斯法和非参数法( 近邻学习或者基于事例的学习) ，对应的知识表 2 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 示则为判别函数和原型事例。机器学习方法包括决策树和规则归纳法，前者对应 的表示为决策树或判别树，后者则一般为产生式规则。神经网络方法主要是b p 算 法，它的模型表示是前向反馈神经网络模型( 由代表神经元的节点和代表连接权值 的边组成的一种体系结构) ，b p 算法本质上是一种非线性判别函数。另外还有粗 糙集( r o u g hs e t ) ，其知识表示是产生式规则 1 7 。 国内外许多学者对遗传算法进行分类规则发现进行了大量的研究 1 8 。遗传 算法是一种基于生物进化论和分子遗传学的全局随机搜索算法。其基本思想是将 问题的可能解按某种形式进行编码，形成染色体。随机选取n 个染色体构成初始 种群，再根据预定的评价函数对每个染色体计算适应值。选择适应值高的染色体 进行复制，通过遗传操作( 选择、交叉、变异) 来产生一群新的更适应环境的染色 体，形成新的种群。这样一代一代不断繁殖进化，最后收敛到一批最适应环境的 个体上，从而求得问题的最优解。遗传算法有应用广泛、使用简单、鲁棒性强等 特点。 同时有些学者对蚁群算法进行分类规则发现进行了一些研究。a l e x a f r e i t a s 在这方面进行了大量的相关研究 1 6 ，他的相关研究成果也是本文的 主要参考文献。蚁群算法主要是利用了蚂蚁的一些特性，即它们可以不用可视信 息来找到从源点到目标点的最短路径。蚁群算法用于分类规则发现是一个值得研 究的领域，因为蚁群算法包含简单的代理( 蚂蚁) ，它们之间相互合作来完成一个 对整个系统来说是自然发生的、统一的行为，产生一个可以在大搜索范围上高质 量的问题解决方案。但是他们研究出的蚁群分类算法的分类性能并不高，总的预 测准确率甚至不如c 4 5 ，尚存改进余地。 另一方面，传统的网络入侵检测系统中，入侵规则库一般是通过手工定制的 方式建立起来的，尤其是用于识别判断入侵行为的检测知识，都是由安全领域专 家自己总结提供，并将其编写到网络入侵检测系统中，因此不能发现潜在的攻击 入侵模式。基于数据挖掘的网络入侵模型可以进行机器学习和模式扩充，入侵检 测效率和可靠性明显得到提高。实验表明，将数据挖掘技术应用到入侵检测系统 中具有很强的理论基础，在技术上具有可行性。其技术难题主要在于如何根据具 体应用的要求，从关于安全的先验知识出发，提取出可以有效地反映系统特性的 特征属性，应用合适的算法进行数据挖掘。 3 中山大学硕士学位论文 蚁群分类算法的改进及在入侵榆测中应用 总之，入侵检测技术虽然己获得了长足发展，但随着网络入侵技术的不断发 展，入侵的行为表现出不确定性、复杂性、多样性等特点，入侵检测面临许多有 待解决的关键问题，如高效率的检测算法、入侵模式确认、入侵实时监测、入侵 描述语言、检测数据标准化、高速网络中的入侵检测、i d s 评估、i d s 与其他系 统的协同工作等一系列问题都有待进一步研究和实现。这将不断地推动入侵检测 技术得到更深入的发展和更广泛的应用，创造出更多的使用价值。 1 3 本文的研究工作及主要成果 本文在比较现有的一些分类规则发现方法的基础上，重点研究了蚁群分类算 法，并在其于算法上提出了一系列的改进。通过大量的实验表明改进后的算法较 原算法的性能有了很大程度的提高，在基于规则的分类算法中有着较高的分类性 能。最后将改进后的算法应用在了入侵数据集的分类规则提取中，验证了该算法 在应用在入侵检测中的有效性。 本文的研究工作主要解决以下问题： 1 引入了多蚁群并行搜索的思想，为蚁群算法在分类规则提取中的应用建立 了一个新的框架，使得搜索蚂蚁原本模糊的搜索目标变得清晰，有效地提高了算 法搜索单条规则的能力。 2 改进了规则质量函数，通过引入参数调节预测精确度和规则覆盖率对规则 质量的影响度，使得分类算法的输出具有了可控的特性。通过对参数进行不同设 置，使用者可以人为决定分类准确率和规则长度之间的折中，也就是说，规则长 度在很大程度上是可控的，对属性和所属类之间有线形关系的数据集来说，规则 越多，分类准确率越高。文中通过试验分析了参数选择和规则长度之间的关系。 3 设计并实现了蚁群分类系统，并且对网络入侵数据集进行属性约简和离散 化处理后，对其进行了挖掘实验，对实验结果进行了相关分析。 1 4 论文结构 本文分为七章，第五章和第六章是本文重点，相关描述如下： 第一章，绪论，阐明本文的研究背景、研究意义以及研究目标，指出智能挖 掘算法应用在入侵检测中的发展前景。 4 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 第二章至第三章，综述入侵的任务、相关研究进展及数据挖掘在入侵检测中 的应用框架，第三章重点讨论了分类挖掘在入侵检测中的应用，对现有的研究中 用于入侵检测的分类算法作出总结对比，讨论入侵检测中确定性算法和软计算方 法的发展趋势。 第四章至第五章，研究分析了基于蚁群优化的分类算法，总结了该算法的框 架及进展，并提出一系列改进，第五章通过设计大量实验验证改进后算法的性能。 实验证明蚁群分类算法的分类效果要优于常用的规则提取算法，在某些类型的数 据上的分类准确率远高于其他基于规则的分类算法，甚至是所有分类算法中最高。 第六章，使用入侵检测通用数据集进行网络误用检测实验，对实验数据进行 相关的预处理后，使用蚁群分类算法在大量的网络审计数据进行分类规则提取。 使用测试数据集检验其提取得分类规则，验证了蚁群分类算法良好的检测性能。 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 第二章数据挖掘在入侵检测中的应用 2 1 入侵检测的主要任务 入侵检测已经具有2 0 多年的发展历史，a 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 y t 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 被公认为有关入侵检测的最早论述。 d e n n i n g 在1 9 8 6 年发表的论文“入侵检测模型( a ni n t r u s i o nd e t e c t i o nm o d e l ) ” 2 被公认是入侵检测领域的另一篇开山之作。1 9 8 4 年1 9 8 6 年，d o r o t h y 和 p e t e rn e u m a n n 研究和发展了一种命名为入侵检测专家系统( i n t r u s i o n d e t e c t i o ne x p e r ts y s t e m ，简称i d e s ) 2 实时模式的入侵检测系统，该原型系 统被称为里程碑性的i d s ，并且在1 9 8 6 年1 9 9 2 年之间在s r i 国际组织得以 发展。 入侵是指有关试图破坏资源的完整性、机密性及可用性的活动集合 1 。入侵 检测( i n t r u s i o nd e t e c t i o n ) 是指发现非授权使用计算机的个体或计算机的合法 用户滥用其访问系统的权利以及企图实施上述行为的个体 2 。如：非法取得超级 用户的特权：攻击系统使其无法响应服务( d o s ) 。其特点在于检测而非禁止，这主 要是因为系统不可能避过所有的入侵行为。一个入侵检测系统应有以下功能 1 9 ： ( 1 ) 监视分析用户和系统的行为； ( 2 ) 审计系统配置和漏洞： ( 3 ) 评估敏感系统和数据的完整性； ( 4 ) 识别攻击行为； ( 5 ) 对异常行为进行统计： ( 6 ) 进行审计跟踪，识别违反安全法规的行为； ( 7 ) 自动地收集和系统相关的补丁； ( 8 ) 安装诱骗服务器，记录黑客的行为； 下图是d e n n i n g 在1 9 8 6 年提出的入侵检测通用模型。这个通用的入侵检测模 型是由事件产生器、行为特征模块、规则模块组成。 6 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应j ；i ；i 审计记录或网络数据包 特征表更新 规则更新 o 0 变化阀值 图2 1 入侵检测通用模型 事件产生器事件产生器的目的是从整个计算环境中获得事件，并向系统的其 他部分提供此事件。根据具体应用环境而有所不同，事件一般来自审计记录、网 络数据包以及其他可视行为，这些事件构成了检测的基础。 行为特征模块它是整个检测系统的核心，它包含了用户行为特征的所有变量， 这些变量是根据所采用的统计方法以及事件记录中的具体动作模式而定义的，并 且根据匹配的记录数据更新变量值。如果有统计变量的值达到了定义的阈值，则 行为特征表产生异常记录，并采取一定的措施。 规则模块由系统安全策略，入侵模式等部分组成。它一方面为判断是否入侵 提供参考机制，另一方面根据事件记录、异常记录以及有效日期等信息控制并更 新其它模块的状态。在具体实现上，规则的选择与更新可能不尽相同。但一般来 说，行为特征模块基于行为的检测( 即异常检测) ，而规则模块进行基于知识的检 测( 即误用检测) 。由于这两种方法具有一定的互补性，实际系统中经常将两者结 合起来在一起使用。 2 2 入侵检测的数据来源 入侵检测通用模型中的事件产生器为分析部件提供待分析的数据，这些数据 来自主机审计记录或者网络连接记录。因此，根据数据来源不同，入侵检测的体 系结构可分为如下几种：基于主机的入侵检测系统( h i d s ) 、基于网络的入侵检测 系统( n i d s ) 和混合分布式的入侵检测系统( d i d s ) 2 0 。 ， 7 中山大学硕士学位论文 蚁群分类算法的改进及在入侵检测。f i 应用 2 2 1 基于主机的入侵检测系统 基于主机的入侵检测系统历史最久。最早用于审计用户的活动，比如用户登 陆、命令操作、应用程序使用资源情况等。此类系统一般主要使用操作系统的审 计跟踪同志作为输入，某些也会主动与主机系统进行交互以获得不存在于系统日 志的信息。它所收集的信息集中在系统调用和应用层审计上，试图从日志寻找滥 用和入侵事件的线索。 基于主机的入侵检测依赖于特定的操作系统和审计跟踪曰志获取信息，此类 系统的原始数据来源受到所依附具体操作系统平台的限制，系统的实现主要针对 某特定的系统平台，在环境适应性、可移植性方面问题较多。所以现在的商用入 侵检测产品几乎没有一种是单纯基于主机类型的。但是在获取高层信息以及实现 一些特殊功能( 如针对系统资源情况的审计) 方面具有无法替代的作用。 2 2 2 基于网络的入侵检测系统 由于来自网络的攻击事件逐渐成为信息系统的最大威胁，因而基于网络的入 侵检测系统具有更重要的价值。基于网络的入侵检测系统是在网络中的某一点被 动地监听网络上传输的原始流量，通过线路窃听的手段对截获的网络分组进行处 理，从中提取有用的信息。基于网络的入侵检测系统通过对流量分析提取特征模 式，再与已知攻击特征相匹配或与正常网络行为原型相比较来识别攻击事件。与 基于主机的入侵检测不同，基于网络的入侵检测非常适用于检测系统应用层以下 的底层攻击事件。基于网络监听方式实现的入侵检测系统同基于主机的系统相比， 在实时性、适应性、可扩展性方面具有其独特的优势，但此类系统也存在一些固 有的弱点，比如更容易受到基于网络的拒绝服务等恶意攻击，在高层信息的获取 上更为困难，在实现技术上更为复杂等，但是也只有此类系统可以检测某些种类 的攻击，如远程缓冲区溢出、网络碎片攻击等大量针对协议栈或特定网络服务的 攻击手段。 可以这样认为，基于主机的系统一般是根据攻击对系统的影响来判断攻击事 件，比如用户是否多次使用错误口令，文件状态是否非法改变等，时间上滞后于 攻击本身，而基于网络的系统强调通过网络行为过程进行分析，不是依靠审计攻 8 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 击事件对目标系统带来的实际影响，而通过行为特征来发现攻击事件。比如网络 上一旦发生了针对w i n d o w sn t 系统的攻击行为，即使其保护网络中没有n t 系 统，基于网络的入侵检测系统一样可以检测到该攻击。此类系统侧重于网络活动 进行检测因而得以实时地发现攻击企图，许多情况下可以防范于未然。 由于基于网络监听方式的入侵检测系统直接从数据链路层获取信息，因而从 理论上它可以获取所有的网络信息，原始数据来源丰富，只要传输数据不是底层 加密的，就可检测到一切通过网络发动的攻击事件，包括一些高层应用的信息。 如：目前已经可以完全通过网络监听的方式对通过网络登陆到特定系统的用户名 和口令进行审计，故也可以分析其他系统相关的高层事件。 2 2 3 混合分布式入侵检测系统 混合分布式入侵检测可以从不同的主机系统、网络部件和通过网络监听方式 收集数据，这些系统可以利用网络数据，也可收集并分析来自系统高层事件，发 现可疑行为。 虽然基于网络的入侵检测系统实现的功能可以很强大，如要适应现代千兆比 特的高速网络和交换式网络方面也有许多难以克服的困难。而且基于主机的入侵 检测系统也有其独特功能，所以未来的入侵检测系统要想取得成功必须将基于主 机和基于网络的两种入侵检测系统无缝的结合起来，这就是混合分布式入侵检测 系统。在基于主机和基于网络的两种入侵检测系统都发展到一定程度后，混合分 布式系统也就自然出现了，它兼有两种入侵检测系统各自的优点，但是实现复杂 度要更高。 2 3 入侵检测常用技术 2 3 1 异常检测常用技术 顾名思义，异常入侵是相对正常情况下来说的。理想情况下异常活动集与入 侵性活动集相同，所以，若能检测所有的异常活动，则就能检测所有的入侵性活 动 2 1 ，2 2 。入侵性活动并不总是与异常活动相符合。活动存在的可能行为：入侵 性而非异常、非入侵性而是异常的、非入侵性且非异常和入侵且异常。 9 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测l = i = l 应j ； ； 异常入侵要解决的问题就是构造异常活动集，并从中发现入侵性活动子集。 通常情况下，通过构造不同的异常模型来构成不同的检测方法，异常检测通过观 测到的一组测量值偏离度来预测用户行为的变化，然后做出决策判断的技术。 目前，基于异常的入侵检测系统主要采用的技术有统计异常、神经网络、数据挖 掘和贝叶斯推理异常等方法 2 3 。 1 统计异常检测 统计异常检测方法根据异常检测观察器观察主体的活动，然后产生刻画这些 活动的行为的轮廓。每一个轮廓保存记录主体当前行为，并定时地将当前的轮廓 与存储的轮廓合并。通过比较当前的轮廓与己存储的轮廓来判断异常行为，从而 检测出异常入侵。 2 贝叶斯推理异常检测 基于贝叶斯推理异常检测方法是通过在任一给定的时刻，测量a l ，a 2 ，a n 变量值推理判断是否有入侵事件发生。其中每个a i 变量表示系统不同的方面特 征( 如磁盘i o 的活动数量，或系统中页面出错的数) 。 根据各种异常测量的值，入侵的先验概率及入侵发生时每种测量到的异常概 率，从而能够检测判断入侵的概率。但是为了检测的准确性，还要必须考虑各测 量a i 间的独立性。一种方法是通过相关性分析，确定各异常变量同入侵的关系。 3 神经网络异常检测 神经网络具有自学习、自适应的能力，只要提供系统的审计数据，神经网络 就可以通过自学习从中提取正常的用户或系统活动的特征模式：而不需要获取描 述用户行为特征的特征集以及用户行为特征测度的统计分布。因此，避开了选择 统计特征的困难问题，使如何选择一个好的主体属性子集的问题成了一个不相关 的事，从而使其在入侵检测中也得到了很好的应用。 4 数据挖掘异常检测 计算机互联网导致大量审计纪录，而且审计记录大多是文件形式存放( 如 u n i x 系统s y s l o g ) 。若单独依靠手工方法去发现纪录中异常现象是不够的，往往 操作不变，不容易找出审计记录间相互关系。将数据挖掘技术应用到入侵检测研 究领域中，就是从审计数据或数据流中提取感兴趣的知识，这些知识是隐含的、 实现未知的潜在有用信息，提取的知识表示为概念、规则、规律、模式等形式， i o 中山大学硕士学位论文 蚁群分类算法的改进及在入侵检测巾应用 并用这些知识去检测异常入侵和已知的入侵。 2 3 2 误用检测常用技术 误用检测和异常入侵检测技术在处理数据的方式上是互补的。误用检测方法 ( m i s u s ed e t e c t i o n ) ，主要利用收集到的入侵或攻击的相关知识( 特征、模式等) 来检查系统中是否出现了这些已知入侵攻击的特征或模式，并据此判断系统是否 遭受到攻击。 基于误用检测的入侵检测技术通过收集入侵攻击和系统缺陷的相关知识来构 成入侵检测系统中的知识库，然后利用这些知识寻找那些企图利用这些系统缺陷 的攻击行为 2 4 。也就是说，这类入侵检测方案通过检测那些与已知的入侵行为 模式类似的行为或间接地违背系统安全规则的行为，来识别系统中的入侵活动。 系统中任何不能明确地认为是攻击的行为，都可认为是系统的正常行为。因此， 基于入侵知识的入侵检测系统具有很好的检测精确度，至少在理论上具有非常低 的虚警率，但是其检测完备性则依赖于对入侵攻击和系统缺陷的相关知识的不断 更新、补充。 使用这类入侵检测系统，可避免系统以后再遭受同样的入侵攻击而且系统安 全管理员能够很容易地知道系统遭受到那种攻击并采取相应的行动。但是，知识 库的维护需要对系统中的每一个缺陷都要进行详细的分析，这不仅是一个耗费时 间的工作，而且关于攻击的知识，依赖于操作系统、软件的版本、硬件平台以及 系统中运行的应用程序。这种入侵检测技术的主要局限在于： ( 1 ) 它只能根据己知的入侵序列和系统缺陷的模式来检测系统中的可疑行为，而 面对新的入侵攻击行为以及那些利用系统中未知或潜在缺陷的越权行为则无能为 力。 ( 2 ) 检测系统知识库中的入侵攻击知识与系统的运行环境有关。 ( 3 ) 对于系统内部攻击者的越权行为，由于他们没有利用系统的缺陷，因而很难 检测出来。 在实现上，基于误用检测的入侵检测系统只是在表示入侵模式( 知识) 的方式 以及在系统的审计迹中检查入侵模式的机制上有所区别。主要实现技术可分成以 下几类 2 5 ：专家系统、入侵签名分析、状态迁移分析或模式匹配等。 1 1 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应h ；i 2 4 入侵检测中的数据挖掘框架 随着计算机网络的不断深入发展，网络的各种数据和攻击模式层出不穷，并 以惊人的速度增长。使用一般的方法难以对海量的审计数据进行数据的分析。数 据挖掘技术应用到入侵检测上来有着非常强的适应性。 哥伦比亚大学l e e 等人最早提出以数据为中心的思想，利用数据挖掘在有效 利用信息方面的优势，将入侵检测视为一类数据分析过程，研究审计数据建模的 可行性和有效性，并构造出检测模型 5 ，6 。 将数据挖掘方法进行入侵检测，可以构建一个如图2 3 所示的入侵检测模型。 首先对用户的历史行为数据，进行数据采集、集成、提取到学习得到异常正常模 式。这个数据也是主机或者网络审计数据，其中数据的采集和集成是数据预处理 过程，可以作为数据挖掘的第一步。新的主机或者网络审计数据经过数据预处理 之后得到当前用户行为特征，入侵检测器从知识库里的规则，推理、分析判断当 前用户行为特征是否是入侵，如果是，则对该行为做出响应，否则继续监测下一 个主机或者网络审计数据。 图2 2 以数据为中心的入侵检测框架 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 下面以基于网络连接记录的检测为例，进一步说明不同的数据挖掘模式如何 应用在入侵检测中： 网络入侵检测领域的一个研究重点是在收集到网络的原始数据后，如何从大 量的原始数据属性中有效地区分正常行为和异常行为，以及如何自动有效地生成 入侵规则。关联分析数据挖掘算法可用于发现网络连接记录各属性之间的关系， 序列分析数据挖掘算法能发现网络连接记录间的时序关系。使用关联分析数据挖 掘和序列分析数据挖掘算法可以得到正常行为的模式，用于异常入侵检测。分类 分析数据挖掘算法可以从训练数据中挖掘出识别正常行为和入侵行为的规则。 图2 3 数据挖掘模式在入侵检测中的应用 侦听到的原始数据首先被采集并被预处理成包含特定属性的网络连接数据， 这些数据一般涉及到某些重要的属性，例如，协议类型、目的端i p 地址和标志位 ( 根据具体的协议类型、持续时间、源端i p 地址对连接加以判断的参数) 等。接着， 使用关联分析数据挖掘和序列分析数据挖掘算法处理这些连接数据，得到关联规 则和序列规则，从而得到可用于异常入侵检测的正常行为模式。由于分类数据挖 掘算法生成入侵检测规则对训练数据有比较严格的要求，一般的网络连接记录中 入侵数据的比例是很小的，因此不能直接用来训练生成规则，必须进行一些处理， 由于前面已经用关联分析数据挖掘和序列分析数据挖掘算法得到了正常行为模 式，可以用正常行为模式去过滤网络连接数据，从而得到纯度比较高的入侵数据， 并重新建立训练数据集，最后使用分类算法做规则挖掘，生成基于误用检测的规 则，以用于误用检测。 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应j ：i j 从前文的分析中可以知道，对应不同来源的数据，可以用不同的数据挖掘算 法来提取规则。数据挖掘技术都可称为是数据驱动的，而不是用户驱动的，也就 是说用户在使用这些算法时，只要给出数据，不用告诉算法程序怎么做和期待得 到什么结果，一切都是算法自身从给定的数据中找出来。 2 5 主要的数据挖掘模式及在入侵检测中的应用 2 5 1 基于聚类分析的入侵检测 基于聚类分析的入侵检测算法基本思想主要源于入侵与正常模式上的不同及 正常行为数目应远大于入侵行为数目的条件，因此能够将数据集划分为不同的类 别，由此分辨出正常和异常行为来检测入侵。基于聚类的入侵检测是一种无监督的 异常检测算法，通过对未标识数据进行训练来检测入侵，该方法不需要手工或其它 的分类，也不需要进行训练，因此能发现新型的和未知的入侵类型。p o r t n o y 2 6 首先提出了基于聚类分析的入侵检测技术，使用改进的单链法聚类，经过标识数据 实例，通过分类来检测入侵行为，后来有人对该技术提出过改进，如利用遗传聚类 进行入侵检测 2 7 。 数据挖掘中常用的聚类算法有k 2 m e a n s 、模糊聚类、遗传聚类 2 8 等。最近也 有人尝试把蚁群聚类用到入侵检测 2 9 中，取得了很好的效果。 2 5 2 基于关联规则分析的入侵检测 关联规则挖掘是数据挖掘最为广泛应用的技术之一，也是最早用于入侵检测 的技术。现在已有多种关联规则算法如a p r i o r i 算法等用于入侵检测。关联规则最 早被用于分析网络流数据，随后也将关联规则的挖掘结果作为后挖掘的输入数据， 以便能挖掘出更优的结果。乔治梅森大学的研发人员发展了关联挖掘在入侵检测 方面的重要的应用，并提出了一种新型的应用于异常检测的多重检测方法。他们的 研究成果主要在a d a m ( a u d i td a t aa n a l y s i sa n dm i n i n g ) 系统中得到应用，初步的 实验结果非常理想。a d a m 系统在1 9 9 9 年d a r p a 入侵检测系统评估中在整体方面名列 第三，在攻击检测精确性方面位于第二位。基于关联规则挖掘的入侵检测被广泛研 究，取得许多研究成果 6 ，3 0 3 。 1 4 巾山大学硕士学位论文 蚁群分类算法的改进及在入侵检测中应用 2 5 3 基于分类分析的入侵检测 入侵检测可以看作是一种数据分类问题，进行分类挖掘的入侵检测应首先选 择一个训练数据集，对该训练集标记出正常或异常的数据，使用分类规则、决策树 等方法从该数据集中提取出分类规则并构造出适合的分类器，然后用构造出的分 类器对收集的网络实时数据流进行分类，将数据分为正常行为或某种入侵行为， 以此判断出是否存在入侵行为。这一分类过程应该不断反复和评估，以期望能够得 到最优化的分类器。后续章节中将继续介绍关于分类算法在入侵检测中的应用的 进一步研究。 2 5 4 基于序列模式分析的入侵检测 序列模式分析主要用于发现形如在某段时间内，有数据特征a 出现，然后出现 了特征b ，而后特征c 又出现了，它主要挖掘安全事件之间先后关系，运用序列分析 发现入侵行为的序列关系，从中提取出入侵行为之间的时间序列特征。序列模式 分析一般不单独使用，它可用于入侵检测过程的某一步骤，从数据中挖掘用户序列 模式，提取出可用于入侵检测的知识和模式 2 8 ，如对网络连接数据进行序列分析， 正确提取出一些基于时间的统计属性，以便能构造出分类模型。序列模式分析与 关联规则有相似之处，它对反复出现的序列检测率较高。 2 5 5 数据挖掘算法之间的融合用于入侵检测 入侵检测是一个复杂的知识挖掘过程，因此可以在检测过程中结合这些数据 挖掘技术各自的特点，将它们应用到适合它们的步骤中，使之互相配合，利用各自 的优点在各自适合的环境下发挥自身的作用，例如可用序列分析发现频繁出现的 入侵序列，提取分类规则，用聚类分析对安全事件进行聚类，分类出正常行为和 异常行为等。由于攻击方法的多样性及检测环境的多变性，使得用单一的方法进 行入侵检测受到一定的局限，或者不能检测未知入侵或者检测率不高，达不到有效 检测的目标，因此，使用多种检测技术来检测入侵受到研究人员的关注，目前已提 出多种混合检测方法 3 0 ，如基于数据挖掘的免疫检测 3 1 ，基于遗传聚类检测 3 2 等算法。 巾山大学硕士学位论文蚁群分类算法的改进及在入侵检测巾应用 第三章入侵检测中的分类算法 3 1 数据分类的任务与步骤 3 1 1 分类和分类规则 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的 目的是学会一个分类器或分类模型( 也常常称作为分类器) ，该模型能把数据库中 的数据项映射到给定类别的某一个。分类可用于预测。预测的目的是从利用历史 数据记录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。例 如：可以建立一个分类模型，对银行贷款的安全或风险进行分类。 分类规则的构造需要一个任务相关的训练样本数据集作为输入，该数据集可 以用关系模式r ( a 。，a 。，a | 1 ) 表示，其中a ；( i = 1 ，2 ，n ) 为属性。在分 类问题中，将所有属性分为两组，即特征属性( 或称条件属性) 与类别属性( 或称决 策属性) ，分别以c 。，c 。，c 。和d ，d ：，d 。表示，则分类规则的一般形 式如下： i f ( c l = i 。) a n d ( c 2 = 1 2 ) a n d a n d ( c 。= i 。) t h e n ( d 】_ j ) a n d a n d ( d m - l ) 其中，i 。，j j ( i = 1 ，n ：j = 1 ，m ) 表示集合，“c 。= i 。”表示第n 个属性上取值为i 。规则中属性的个数为规则的长度，这里是m + n 。最简单 也是最常见的情况，进行分类的类属性只有一个，这种情况下分类模型可以表示 为： i f ( c j = i 。) a n d ( e 2 = i2 ) a n d a n d ( c 。= i 。) t h e nd = j 分类规则的长度为规则中特征属性的个数，这里是n 。表2 1 是一个关于职 称评定的训练例子，训练集中有三个特征属性和一个类别属性，特征属性分别为： 姓名、职称、工龄；类别属性为是否可以继任，集合中的每个记录表示一个员工 信息。下表描述了某校的助力教授以上职称教职工的相关情况，第二列表示职称， 第三列表示评为该职称的年数，第四列表示是否延聘。 1 6 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 对于训练集，分类的目的是为了建立一个能表明是否延聘的模式( 规则) ，如： i f ( r a n k = p r o f e s s o r ) a n d ( y e a r s 5 ) t h e nt e n u r e d = y e s 这样，一条分类规则的左部可以看作是由合取范式构成的逻辑公式，公式中 每个合取项对应一个特征属性的取值集合：规则的右部可以看作是由类别属性取 值构成的合取范式。一旦分类规则建立后，它就能用来预测未来的未分类的记录。 3 1 2 数据分类的步骤 数据分类过程主要包含两个步骤 7 ： 第一步，建立一个描述己知数据集类别或概念的模型。如图2 2 所示，该模 型是通过对数据库中各数据行内容的分析而获得的。每个数据行都可认为是属于 一个确定的数据类别，其类别值是由一个属性描述( c a 称为类别属性) 。分类学习 方法所使用的数据集称为训练样本集合，因此分类学习又可以称为监督学习 ( 1 e a r n i n gb ye x a m p l e ) 。它是在已知训练样本类别情况下，通过学习建立相应模 型；而无监督学习则是在训练样本的类别与类别个数均未知的情况下进行的。通 常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学公式形式 等。例如，给定一个顾客信用信息数据库，通过学习所获得的分类规则可用于识 别顾客是否是具有良好的信用等级或一般的信用等级。分类规则也可用于对今后 未知所属类别的数据进行识别判断，同时也可以帮助用户更好的了解数据库中的 内容。 1 7 中山大学硕士学位论文蚁群分类算法的改进及在入侵检测中应用 只二”掣 l m er 腿y e 懈n 翻u 娜 胁 g 赶m