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

华北电力人学硕十学位论文摘要 摘要 随着网络技术的不断发展，网络速度越来越快，网络安全问题也随之变 的更加突出。传统的网络入侵检测技术的局限性越来越明显，已经无法适应 网络新攻击层出不穷和数据量日益增大的趋势。数据流挖掘技术是一种对高 维的、动态变化的大量流式数据进行挖掘的新方法，如何对这些数据使用有 限的空间进行快速处理以获取有用的信息称为了现在数据挖掘领域的一个研 究热点。由于高速网络的数据具备动态变化、数据量大、维度高这些特点， 所以数据流挖掘技术可以很好的完成高速网络数据分析和入侵检测的任务， 从而保证网络的入侵检测系统的实时性和正确性，以及面对未知方式入侵时 的检测能力。 关键词：数据流挖掘，入侵检测，特征选择，克隆选择 a b s t r a c t w i t l lt h ec 0 n t i n u o u sd e v e l o p m e n to ft 1 1 en e t 、o r kt a c h i l o l o 霉? y ，h i 曲s p e e dn e t w o d 【 w a sc o m e 南r t h ，t h ei s s u eo fn e 俩o r ks e c u r i t ya l s o w i l lb ec 1 1 a n g e de v e nm o f 弓 c o n s p i c u o u s t r a d i t 至o n a ln e 魄o f ki n t m s i o n k t e c t i o nt e c h n o l o 霉 l i m i t a t i o n sh a s b o c 0 m ei n c r e a s i n g l yc l e a r ，h a sb e e nu n a b l et oa d a p tt om en e wn e 附o f ke n d l e s sa t t a c k s 锄dt l l eg 阳w i n gv o l 啪eo fd a t a 锄dt 1 i e n d s d a t as t l l j 锄m i i l i n gt e c l l n o l o g yi sal 【i r l do f h i g h d i m e n s 主o n a l ，d ) ，i l a i i l i cc h a n g e si nt h ej f l o wo fal a r g en u l n b e ro fn e w d a t am i n i n g m e 血o d s ，m eu s eo fs u c hd a t at ot l i el i m i t e ds p a c et 0d e a l 、析t l lr a p i da c c e s st 0 u s e l l i i l 内珊a t i o nl c r l 0 、n 雒d a t am i n j n ga r e 丛n o waf 嚣明r c hf o c 邺a sl l i 曲s d e e dd a t a 饿粕，0 r kw i 也d y i l 跚i cc _ h a n g 嚣，al a r 萨q u 觚t i t yo fd a ：t a l l i g hd i m e m i o no ft h 骼e c h a r a c t 耐s t i c s ， d a t as t 陀锄m i n i n gt e c ：t l l l o l o g yc a l ib ev e 巧g o o dt 0 c o m p l e t c 1 1 i 曲一s p e e dn e r ki n 仃u s i o nd e t e c t i o n 觚dd a t aa n a l y s i st a s k s ，m u se n s u r i n gn e t 、 ，o r k i r 曲n 】圆i o nd e t e c t i o ns y s t e n lr e a l t i m ea n dc o n 曰c t ，a sw e l la sw a v st of i a c em eu n h l o w n t i m eo ft t l ei n v a s i o no fd e t e c t i o nc a p a b i l i t i e s q i n ，“a n g ( c o m p u t e rs o f t w a r e & t h e o r ” d i r e c t e db yp r o f 、 ，a n g ，b a o y i k e yw o r d s ：d a t as t r e a mm i n i n g ，i n t r u s i o nd e t e c t i o n ，f e a t u r es e l e c t i o n 华北电力人学硕十学位论文摘要 摘要 随着网络技术的不断发展，网络速度越来越快，网络安全问题也随之变 的更加突出。传统的网络入侵检测技术的局限性越来越明显，已经无法适应 网络新攻击层出不穷和数据量日益增大的趋势。数据流挖掘技术是一种对高 维的、动态变化的大量流式数据进行挖掘的新方法，如何对这些数据使用有 限的空间进行快速处理以获取有用的信息称为了现在数据挖掘领域的一个研 究热点。由于高速网络的数据具备动态变化、数据量大、维度高这些特点， 所以数据流挖掘技术可以很好的完成高速网络数据分析和入侵检测的任务， 从而保证网络的入侵检测系统的实时性和正确性，以及面对未知方式入侵时 的检测能力。 关键词：数据流挖掘，入侵检测，特征选择，克隆选择 a b s t r a c t w i t l lt h ec 0 n t i n u o u sd e v e l o p m e n to ft 1 1 en e t 、o r kt a c h i l o l o 霉? y ，h i 曲s p e e dn e t w o d 【 w a sc o m e 南r t h ，t h ei s s u eo fn e 俩o r ks e c u r i t ya l s o w i l lb ec 1 1 a n g e de v e nm o f 弓 c o n s p i c u o u s t r a d i t 至o n a ln e 魄o f ki n t m s i o n k t e c t i o nt e c h n o l o 霉 l i m i t a t i o n sh a s b o c 0 m ei n c r e a s i n g l yc l e a r ，h a sb e e nu n a b l et oa d a p tt om en e wn e 附o f ke n d l e s sa t t a c k s 锄dt l l eg 阳w i n gv o l 啪eo fd a t a 锄dt 1 i e n d s d a t as t l l j 锄m i i l i n gt e c l l n o l o g yi sal 【i r l do f h i g h d i m e n s 主o n a l ，d ) ，i l a i i l i cc h a n g e si nt h ej f l o wo fal a r g en u l n b e ro fn e w d a t am i n i n g m e 血o d s ，m eu s eo fs u c hd a t at ot l i el i m i t e ds p a c et 0d e a l 、析t l lr a p i da c c e s st 0 u s e l l i i l 内珊a t i o nl c r l 0 、n 雒d a t am i n j n ga r e 丛n o waf 嚣明r c hf o c 邺a sl l i 曲s d e e dd a t a 饿粕，0 r kw i 也d y i l 跚i cc _ h a n g 嚣，al a r 萨q u 觚t i t yo fd a ：t a l l i g hd i m e m i o no ft h 骼e c h a r a c t 耐s t i c s ， d a t as t 陀锄m i n i n gt e c ：t l l l o l o g yc a l ib ev e 巧g o o dt 0 c o m p l e t c 1 1 i 曲一s p e e dn e r ki n 仃u s i o nd e t e c t i o n 觚dd a t aa n a l y s i st a s k s ，m u se n s u r i n gn e t 、 ，o r k i r 曲n 】圆i o nd e t e c t i o ns y s t e n lr e a l t i m ea n dc o n 曰c t ，a sw e l la sw a v st of i a c em eu n h l o w n t i m eo ft t l ei n v a s i o no fd e t e c t i o nc a p a b i l i t i e s q i n ，“a n g ( c o m p u t e rs o f t w a r e & t h e o r ” d i r e c t e db yp r o f 、 ，a n g ，b a o y i k e yw o r d s ：d a t as t r e a mm i n i n g ，i n t r u s i o nd e t e c t i o n ，f e a t u r es e l e c t i o n 声明尸明 本人郑重声明：此处所提交的硕士学位论文 基于数据流挖掘方法的高 速网络入侵检测研究，是本人在华北电力大学攻读硕士学位期间，在导师 指导下进行的研究工作和取得的研究成果。据本人所知，除了文中特别加以 标注和致谢之处外，论文中不包含其他入已经发表或撰写过的研究成果，也 不包含为获得华北电力大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 学位论文作者签名： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学 校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用 影印、缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被 查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位论文；同意 学校可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 名：触 日期：迹：! ：，矿 导师签名： 日期：叫二侈 华北电力大学硕士学位论文 1 1 研究背景及意义 1 1 1 研究背景 第一章引言 随着网络应用的不断增加，网络技术也发生了日新月异的变化。网络基础设施 的传输和处理速度也随之迅速提高。目前，以太网带宽已经发展到了l o o o m b p s ，同 时网络用户也急剧增加，这使得主干网或大型网络的网络流量不断增大。网络已经 成为社会和经济发展的坚实基础，其地位越来越重要。然而伴随着网络速度的不断 提高，也产生了各种各样的问题。其安全问题尤为严重。根据2 0 0 3 年计算机安全 机构( c s i ) 和美国安全局( f b i ) 的报告显示，7 0 的受调查网络承认和意识到在 过去的1 2 个月里遭到不同程度的攻击，3 0 的还不知道是否遭到过攻击，另外与去 年同期相比拒绝服务攻击d o s 增加超过3 3 ，所有这些都是发生在我们现实网络 中。 入侵检测系统是近些年兴起的一种主动的网络安全技术，可以检测和监视入侵， 为对抗入侵及时提供重要的信息，阻止事件的发生和事态的扩大，有效弥补传统安 全保护措施的不足。它提供了对内部攻击、外部攻击和误操作的实时保护，在网络 系统受到危害之前拦截和响应入侵。入侵检测的核心技术就是从网络中或许信息， 对获取的这些信息进行分析来进一步判定是否发生了入侵。随着网络不断发展，原 有的入侵检测系统已经无法完全适应高速网络环境下的入侵检测任务，尤其是在高 速骨干网l g b i t s 以上的流量情况下，原来的入侵检测系统面临着以下的难题： 1 ) 网络数据处理瓶颈。随着千兆以太网，a t m 的广泛应用，现在主机对网络 数据包的处理逐渐成为了一个入侵检测系统的瓶颈，往往需要专有设备或者集群来 获取数据，但是还是会由于分析速度不够快而造成丢包的现象。 2 ) 要获取的入侵信息种类层出不穷，并不断发生着变化，虽然基于模式匹配方 式的误用入侵检测方式已经广泛应用于商用入侵检测系统，但是由于其无法发现未 知的入侵方式而无法适用于高速网络的入侵检测。如何在变化的数据中实时发现入 侵以及新的入侵类型也成为高速网络中一个非常关键的问题。 1 1 2 国内外研究现状 ( 1 ) 数据源分析 基于网络的入侵检测系统使用在共享网段上侦听采集到的网络数据包作为数据 1 华北电力大学硕士学位论文 源，目前在市场上处于主导地位。n i d s 通常由一个或一组主机组成，尤其在现在 高速网络中，集群已经成为了一种趋势。在网络中的不同部分利用一个运行在混杂 模式下的网络适配器来“侦听”或捕获网络数据包，同时向一个唯一的管理控制台 报告攻击行为。由于在n i d s 使用的主机上不提供其它的应用服务，因此能够更好 的避免受到攻击。 基于网络的入侵检测有以下优点： 隐蔽性好。一个网络上的监测器不像一个主机那样显眼，所以也不容易受到 攻击。基于网络的监视器不运行其它应用程序，不提供网络服务，所以可以不响应 任何计算机，因此可以做的相对比较安全。 更好的攻击事件检测能力。由于n i d s 可以获取流经该网段的所有数据包，对 于针对网络的攻击行为有较好的判断。 较少的监测器。由于使用一个监测器就可以保护一个共享网段，所以不需要 很多监测器。 操作系统的无关性。n i d s 与被保护的主机的操作系统无关。与之相比，h i d s 必须在特定的、没有遭受破坏的操作系统中才能正常工作。 占用资源少。由于采用侦听模式，不会影响网络的性能；且n i d s 不会占用被 保护设备上的任何资源。可以提供对网络通用的保护而无需顾及异构主机的不同架 构。 ( 2 ) 检测方法 目前常用的入侵检测方法主要分为两类：基于异常的检测( a n o m a i yd e t e c t i o n ) 和基于误用的检测( m i s u s ed e t e c t i o n ) 【i 】。 异常检测 异常入侵检测方法的主要前提条件是将入侵活动作为异常活动的子集，理想状 况是异常活动集与入侵活动集等同【列。这样，若能检测所有的异常活动，则可检测 所有的入侵活动，但是，入侵活动并不总是与异常活动相符合，这种活动存在四种 可能情况：入侵且非异常；非入侵且异常；非入侵且非异常；入侵且异常。 异常入侵检测要解决的问题是构造异常活动集并从中发现入侵性活动子集。异常入 侵检测方法依赖于异常模型的建立，不同模型构成不同的检测方法，异常检测是通 过观测的一组测量值偏离度来预测用户行为的变化，然后做出决策判断的检测技 术。如：基于特征选择的异常检测方法，基于贝叶斯推理的异常检测方法，基于贝 叶斯网络的异常检测方法，基于模式预测的异常检测方法，基于贝叶斯聚类分析的 异常检测方法，基于机器学习的异常检测方法，基于数据挖掘的异常检测方法【3 击】 2 华北电力_ 人学硕十学位论文 等等。 误用检测 误用入侵检测的主要假设是具有能够被精确地按照某种方式编码地攻击，并可 以通过捕获攻击及重新整理，确认入侵活动是基于同一弱点进行攻击地入侵方法的 变种f 7 l 。误用入侵检测指的是通过按预先定义好的入侵模式以及观察到的入侵发生 的情况进行模式匹配来检测。入侵模式说明了那些导致安全突破或其它误用事件中 的特征、条件、排列和关系，一个不完整的模式可能表面存在入侵的企图。如：基 于条件概率的误用入侵检测，基于状态迁移分析的误用入侵检测方法【7 9 1 等。 1 1 3 课题研究内容与意义 入侵检测系统( i n t n l s i o nd e t e c t i o ns y s t e m ，i d s ) 是继防火墙、数据加密等传统 安全保护措施之后的新一代网络安全技术。入侵检测系统能够帮助网络系统快速发 现网络攻击，提高信息安全基础结构的完整性。 计算机系统、网络系统的各部分随着复杂度的增加，其设计、实现和部署使用 中都会给系统带来安全漏洞。目前尚无经济可行的方法完全消除这些隐患，因此有 效的入侵检测技术成为了保证计算机网络系统安全必不可少的手段。即使一个系统 中不存在某个特定的漏洞，入侵检测系统仍然可以检测到相应的攻击事件，并调整 系统状态对未来可能发生的入侵做出警告，从而对内部攻击、外部攻击提高实时的 保护。 虽然i d s 无法完全使计算机网络系统免受攻击和破坏，但是却可以在计算机网 络系统遭受攻击时使我们能够接近实时地检测到攻击并采取相应的措施，同时还可 以防范日后进一步的攻击。这正是入侵检测系统的功能所在，是我们应付破坏企图 的一种有效方式。但是由于随着网络不断发展进步，网络流量已经达到gb i t s 级， 这对于原有的入侵检测系统提出了巨大的挑战。传统的入侵检测系统大多是采用基 于人工专家建模的模式匹配误用检测技术，依靠人工的方式对数据进行分析并建 模。人工建模虽然可以较好的检测已知模式攻击，但是在未知模式攻击以及已知攻 击的变形攻击存在着很大的困难，尤其随着网络不断升级，入侵方式也不断发展进 步，数据量也不断增大，传统的入侵检测越来越无法适应新的网络环境。 随着网络的不断进步，高速网络数据具备了以下的特点： 1 ) 实时性：数据流中的数据元素是在线到达的。但是出于入侵检测系统的特性， 要求这些数据的处理也应当是近乎实时的。 2 ) 无穷性：高速网络数据本身就意味着数据量是无限大的，而相对系统存储能 力来说这种数据量是非常巨大，无法进行保存的。 3 华北电力大学硕七学位论文 3 ) 瞬时性：高速网络的数据由于其数据量的巨大，保存时无法实现的，所以对 于这些数据的访问只有一次机会。 数据流挖掘就是在流式数据上发现提取隐含在其中的潜在有用的信息和知识的 过程。由于数据流本身的特点，许多传统的数据挖掘算法并不适合于数据流的挖掘。 因为数据是以流动的方式出现，并不像传统的数据是静态存储在磁盘中。许多数据 是无法被保存也就意味了无法重复访问的，所以数据流挖掘算法最基本要求就是一 遍扫描数据完成挖掘。而且由于数据流中的数据量非常大，内存无法存储全部数据， 也使得数据流挖掘算法只能在一定的数据子集中进行挖掘。而且数据流的高速流入 和数据量大的特点，要求算法的空间复杂度与时间复杂度必须很低，所有数据的临 时存储和计算都必须在内存中进行。综上所述，使用数据流挖掘的方法对高速网络 数据进行挖掘进行入侵检测将是非常有意义的做法。 本课题的目标是通过研究高速网络数据的特点，结合数据流挖掘技术的特点， 从系统体系结构、数据预处理、网络数据流模型、分类算法这些方面来研究一种基 于数据流挖掘方法的入侵检测系统的关键技术。这些技术为高速网络的入侵检测提 供了一种可行的解决方法，而且也为入侵检测技术的进一步研究提供了新的思路。 1 2 主要研究内容及论文安排 本文从高速网络入侵检测现有的问题中抽取了分析速度，实时入侵发现这些难 题在算法和软件体系结构上进行了研究。 第二章对入侵数据与j 下常数据进行了详细的分析，然后根据分析的结果对基于 正常模式匹配的入侵检测系统的体系结构进行研究。 由于特征选择的方法可以有效地降低需要分析数据的计算复杂度，所以本文在 第三章中对一个基于核与免疫克隆选择相结合的特征选择算法进行研究，第四章根 据网络数据的特性结合第三章的特征选择算法对代价敏感的入侵特征选择算法进 行研究。 第五章使用了网络本体对属性问的语义距离的定义，给出了一种新的基于语义 距离的k n n 入侵检测算法，并给出了测试结果。由于数据流挖掘技术可以给n i d s 带来一定的性能改善，所以我们将基于语义距离的k n n 入侵检测算法融入个多 分类器集合的数据流分类方法中，并在第六章给出了该算法及测试结果。 最后一章是全文工作的总结，这部分概述了本文的主要工作，并对今后进一步 的研究方向进行了展望。 4 华北电力大学硕士学缱论文 第二章d s n ld s 体系结构 2 1 网络发展与入侵检测系统 入侵检测是一种通过收集和分析被保护系统信息，从而发现入侵的技术。它的 主要功能是对网络和计算机系统进行实时监控，发现和识别系统中的入侵行为或企 图，给出入侵警报。可将入侵检测看作是区别系统状态是“正常”还是“异常”的二分 类问题【o l 。对入侵检测系统的要求首先是正确性，其次是实时性。只有检测速度快， 才能及时处理网络中传输的海量数据，不会因为速度慢而丢失信息、造成漏警，更 能及时采取措施，将入侵带来的损失降到最低。随着网络的高速提升，入侵检测系 统面临的一个主要问题是检测速度低、负荷大，来不及处理网络中传输的海量数据， 并且这个问题变得越来越严重。检测速度已成为入侵检测系统实时性要求的一个重 要指标，如何在保证检测正确性的前提下开发出检测速度快的轻量级入侵检测系 统，成为当前研究的热点。我们从特征选择、模式匹配的简化、数据流挖掘算法三 个方面出发，研究了如何提高检测速度这个问题。 随着网络应用的不断普及，规模不断扩大，网络带宽也在飞速发展，传统的l o m 共享局域网络已经迅速被1 0 0 m ，l o o o m 网络所代替，当前新设计的网络都普遍采 用了1 0 0 0 m 的主干网，l o o m 交换到计算机的方案；广域骨干网带宽增长也非常快， 从原来的2 m ，8 m 已迅速发展到1 5 5 m ，6 2 2 m 以及2 5 g l o g 的带宽，光纤已像人类 的毛细血管一样延伸到地球每一个角落。1 9 9 9 年世界电信论坛会议副主席提出了一 个新的摩尔定律：网络带宽每9 个月将增加一倍，这比芯片每1 8 个月翻一翻的速 度要快了一倍，更超过了当前计算机软件技术的发展速度。 在高速网络环境下，当前i d s 研究遇到的一个突出的问题是数据处理速度受到 极大的挑战。著名信息安全研究和顾问机构g a n n e r 公司提出论点，2 0 0 5 年前i d s 会逐渐消亡【，其中4 点理由中就有目前i d s 对6 0 0 m b p s 以上的传输速率无力处 理。美国能源部将高速入侵检测系统作为i d s 重点研究方向之一【1 2 1 。到目前为止， 国际上公开发表的相关成果较少，s e k a r 等人提出了个可以到5 0 0 m b p s 处理速度 的高性能i d s 【1 3 】，但是它是基于离线数据的。较实用的高速入侵检测系统体系结构 是c h r i s t o p h e rk m e g e l 等人提出的高速网络有状念入侵检测系统结构【4 】。该体系结 构有效解决了大流量环境下分流的问题，使得后端的处理系统可以按集群的形式处 理，这样比单节点处理能力将有大幅度提高，且扩展性很强。 网络入侵检测系统面临的数据处理速度的难题可以分为两个部分来考虑，首先 5 华北电力犬学硕+ 学位论文 是网络数据包的获取，然后是检测分析的效率问题。数据包的获取在很多文献中都 进行了深入的研究，也提出了用专有硬件或使用集群机制来获取数据包而保证不丢 包的方法，而本文将着重关注检测分析的效率，从几个方面入手给出了可以有效提 高检测分析效率的高速网络入侵检测体系结构。 2 2 高速网络入侵检测面临的问题及解决方法 ( 1 ) 数据特征多，分析复杂度大 入侵检测系统处理的数据含有大量的冗余与噪音特征，使得系统耗用的计算资 源很大，导致系统训练时间长、实时性差，检测效果不好。特征选择算法能够很好 的消除冗余和噪音特征，为了提高入侵检测系统的检测速度和效果，很多研究者通 过特征选择来解决这个问题，提取和处理的特征数目过多是导致速度下降的主要原 因之一。特征和分类器性能之间并不存在线性关系，当特征数量超过一定限度时， 由于计算复杂度的增加，就会导致分类器性能变差。实际上，有些特征没有包含或 包含极少的对分类有作用的信息，他们对检测结果几乎没有任何影响。所以，特征 选择去除冗余特征，保留能够反映系统状态的重要特征是提高检测速度的一种 有效方法。在尽量不降低分类精度的前提下降低特征空间的维数，根据一定的评价 函数从原始特征集中选择与输出结果有关或重要的特征子集。 ( 2 ) 在线检测的速度慢，错误率高 模式匹配方法的速度要明显高于进行在线分类的速度，所以基于模式匹配方法 的误用入侵检测已经成功地应用于商业产品中。但是模式匹配的方法也有其致命的 缺点，那就是无法检测出未知的攻击。随着攻击方式的多样化，攻击模式库的增长 速度明显加快，以s n o n 2 8 为例，其攻击模式库中有1 2 6 8 8 条规则，并且每个几天 就会更新和增加一些规则，如果以这种方式增长下去，那么模式匹配的时间就会逐 渐增长，不管模式匹配算法如何优化，进行模式匹配的时间也是无法忽略的。这将 导致检测效率的下降。 随着网络应用的不断增加，系统漏洞越来越多，入侵的方式也不断变化，各种 入侵的变种也不断演化。我们都明白，不管系统应用如何增加，系统漏洞任意发展， 我们j 下常的访问都不会去使用系统漏洞设计应用。所以我们可以认为，j 下常的访问 模式相对入侵模式更为稳定，为了验证这个问题，我们对k d d9 9 的数据集进行了 分析。我们使用c 4 5 的分类决策树算法来生成正常模式与异常模式的分类规则，结 果如表2 1 。 6 华北电力大学硕士学位论文 表2 1k d dc u p9 9 分类规则数量 正常规则数 异常规则数 k d d 9 9 部分数据伞部属性6 8 7 1 0 9 2 k d d 9 9 部分数据特征选择 1 2 01 5 0 通过表中的数据我们不难看出，正常模式产生的规则数量要远远小于异常模式 的规则。所以在本文所提出的入侵检测体系结构中，模式匹配不再使用异常模式库， 而是使用正常模式来匹配，这将减少模式匹配的时间，也可以有效避免未知入侵的 威胁。对于提高正常数据的通过速度是非常有意义的，而对于非正常数据来说就必 需经历进一步分析才能通过。 ( 3 ) 对于网络数据的分析不深入，其分类算法正确率偏高 基于异常的入侵检测方法的基础就是异常数据有着与正常数据不同的特征，所 以这种方法就是依靠分类方法来确定一个网络数据包是否是入侵，一般的分类算法 都是依靠数据本身的特点来判定两类数据，而没有考虑过数据本身隐含的领域知 识。为了提高分类算法的效率，本文加入了网络本体的领域知识，使用领域知识将 离散属性的距离理论化。从而达到更加有效检测入侵的效果。 ( 4 ) 使用对网络数据存储、分析的方法使得分析速度降低【1 4 。1 6 j 为了提高分类方法的实时性，本文将数据流挖掘的方法应用于高速网络数据流， 使用滑动数据窗口的方法来有效提高数据分析速度，使得所有需要分析的数据都可 以从内存中找到，而不需要内外存之间进行数据交换，使用k n n 的分类方法并考 虑领域知识，不仅提高了入侵检测系统的数据包分析速度而且提高了分析准确性。 7 华北电力大学硕十学位论文 2 3 体系结构图及简要描述 图2 1d sn i d s 体系结构简图 ( 1 ) 数据采集及预处理 高速网络中的数据采集已经成为了高速网络入侵检测的一个重要组成部分，如 何做到不丢失数据包成了研究的热点问题，目前已有许多可用的数据包抓取方案。 由于本文研究重点不是研究高速网络的数据包采集，所以该部分使用专门的高性能 硬件方案来实现，主要包括实时嵌入式操作系统技术和具有高层交换功能的专有 a s i c 芯片技术。通过这些硬件可以有效地高速数据流进行采集，然后发送给入侵 检测系统进行分析。 网络数据中包含许多特征，文献【1 7 】中曾经提到过，特征选择可以有效提高入侵 检测的效率，所以该部分的核心就是特征选择的方法。入侵检测系统处理的数据含 有大量的冗余与噪音特征，使得系统耗用的计算资源很大，导致系统训练时间长、 实时性差，检测效果不好。特征选择算法能够很好的消除冗余和噪音特征，为了提 高入侵检测系统的检测速度和效果，对基于特征选择的入侵检测系统进行研究是有 必要的。 ( 2 ) 正常规则库 通过上文的分析可知，j 下常规则不会经常的发生变化，而且正常规则的数量也 少于异常规则。所以对数据包进行j 下常规则匹配不仅可以加快正常数据的通过速 r 华北电力人学硕士学位论文 度，而且还可以有效降低规则匹配所需要的时间。正常访问的规则库是根据k d d c u p9 9 数据集使用c 4 5 分类决策树算法分析得到，规则的表达方式与s n o r t 采用 的表达方式类似。而正常规则库是s n o n 所没有的，本系统的正常模式是为了提高 正常数据包的通过速度而设置的，其中的规则是从正常数据的规则中进行一定程度 的范化得到的。 ( 3 ) 数据流的组织方式 在数据流模型中，几乎所有的数据都是按照顺序进行处理而无法进行类似磁盘或 内存中的随机访问。数据流与传统的数据存储的关系模型有以下差别【l8 】： 数据流中的数据都是在线到达的。 系统无法控制数据的到达时闻和处理的时间。 数据流中的数据是无限的，所以无法全部保存。 数据一旦被处理大部分就会被抛弃，所以无法重复访问。 由于数据流的这些特点，在数据流查询中，为了提供一个近似解，查询并不使用所 有的过去数据而是使用一个由最近数据组成的一个滑动窗口进行。例如，仅仅使用 过去一个星期的数据就可以产生一个查询的结果，而这之前的数据就可以全部被抛 弃。在数据流中使用滑动窗口策略是一个非常简单实用的策略。在m a i d s 【1 9 】中提 出了一种更加简单易行的滑动窗口策略，自然倾斜时闻窗口策略( n a t u f et i l t e d t i m e w i n d o w ) 并将其在数据流挖掘系统中实现，体现了该策略良好的可用性。自然倾斜 时间窗口策略是用一组循环队列来实现的，其数据组织方式如图2 2 所示。 p a s t t i m e p r e s e n t 图2 2 自然倾斜时间窗口组织策略 在图2 2 中，数据分为了5 个时间刻度，从右到左的时间跨度越来越大，其数 据的精细程度就越粗糙，自然倾斜时问窗口策略可以做到自动维护，当时间刻度到 达时候，就将该窗口中的数据进行聚合，然后提交到其上一层时间窗口，然后清空 该窗口接受下级提交的数据。这种方法在m a i d s 中取得了良好的效果。 由于本文要面对的高速网络的数据流，其特点就是数据的流量非常不稳定，那我们 如果也使用自然倾斜时问窗口策略来对数据流进行建模的话，那必然会造成时间窗 9 华北电力大学硕士学位论文 口大小的不确定性，比如在数据流量很大的几十秒中时间内，可能会达到非常多的 数据，那么就会要求时间窗的存储区域很大，那么我们就必须对该时问窗口开辟很 大的存储空间，而在数据流量很小的时候，就会造成存储空间的浪费。所以本文将 使用固定大小的滑动窗口策略，对每个窗口固定个数据量的大小。 ( 4 ) 数据流分类算法 我们可以应用很多现有的数据流分类算法来完成高速网络数据流挖掘的入侵检 测任务。比如：s p r i n t 【2 0 】，r a i n f o r e s t 【2 l 】，b o a t 【2 2 】等等。然而这些方法都将需要多 次扫描数据，由于高速网络的数据量是巨大的，我们无法对所有数据进行保存，所 以这对于高速网络数据流来说却是无法实现的。增量学习算法或者在线的数据流挖 掘算法是进行网络数据流挖掘的另一种方法，这种方法相对来说更加可行。这种方 法使用新的数据不断对模型进行修正。然而为了保证以增量方式训练出来的模型与 批处理方式训练得到的模型相同，大多数增量学习算法都依赖一个执行复杂度很高 的算法来更新这个增量模型，这将使得增量模型的训练速度明显低于批处理模型。 在文献 2 3 】中提出了一种高效的增量决策树学习算法v f d t ，当数据流中的都是离散 数据的时候，h o e f f d 泌g 边界保证了该算法的输出模型与批处理模型非常近似，但是 由于网络数据是一种混合型数据，那么必然会增加数据预处理的时间。 以上提到的这些算法，包括在线挖掘算法和增量学习算法也包括v f d t 都是从 使用数据流来构造和维护一个数据模型，这将使得在发生概念偏移的情况下预测结 果的准确性大幅降低。这是因为网络数据不是由一个平稳随机过程产生的，所以我 们所要分类的样本会和历史样本有着非常不同的分布特性。 在本文中使用了一种多k n n 分类器加权的方法来实现数据流的分类算法，经理 论和实验的证明，我们得到了该分类器在分类错误率是与单个分类器相比有了明显 的提高，而且由于多个l 心n 分类器分布在多个数据块中，所以每个数据块搜索最 近邻的时间也随之降低，比在大量数据中寻找最近邻速度快了很多，尤其在发生概 念偏移的情况下，体现了非常好的适应性。 2 4d snid s 多线程设计 为了提高系统的实时性，系统设计多线程并行执行。系统共设计了如下几个线 程： ( 1 ) 网络数据包捕获、简单协议分析线程：该线程主要负责对流经网卡每个数据 包进行捕获，进行分片重组，最后进入协议分析器，进行协议分析，分析结 束后通知主线程，并把数据包放入数据缓冲区中。此线程在程序运行时常驻 内存。 1 0 华北电力大学硕士学位论文 ( 2 ) 主线程：该线程维护用户界面，负责协调多个线程问的共同运转。 ( 3 ) 滑动窗口维护线程：该线程维护整个倾斜时间窗口，并且维护着时间窗口中 的决策树或k n n 分类模型，还维护着时间窗口中的短序列模式挖掘模型。这 样就可以在主线程将异常包进行分类时可以用最短的时间得到结果，并可以 随时得到所有窗口中的短序列模式。 ( 4 ) 规则匹配线程：将协议分析后的数据进行规则匹配，如果无法得到准确的匹 配结果则将该数据包送入缓冲区，并调用倾斜时间窗口的维护线程对该数据 包进行分类，并将结果放入日志记录中。 ( 5 ) 规则挖掘线程：由于模式匹配的速度要远远高于数据挖掘的速度，所以该线 程是在系统运行一段时间后，为了提高系统规贝i j 的可用度而设计的一个规则 模式挖掘的自适应模块，它可以从日志中挖掘出新的规则，将新规则加入规 则库中。 这两个线程只有在主线程调用的时候才可以运行，大部分时候都处在关闭状态。 这些线程调用关系如下图： 曰匡习囤圉 ： 启动 ；广一： 卜一 ： ： ： i ： i ! 竺竺! 羔 ； ； l 添如( 数据包) i； 广一i ：规则匹配( 致据包) ： ： ： l 分类( 数据也) ： ： 入侵警报r 1 一一一一一一一一 ： 图2 3d sn i d s 主要线程图 华北也力人学颂十学似论文 由于每个线程都是独立运行的所以我们就可以将每个线程部署到不同的服务 器中，从而实现并行处理或者在多c p u 的服务器中并行运算。 25d s d s 的部署 不同于防火墙，入侵检测系统的部署相对简单很多，u 以将d sn i d s 作为一个 监听设备没有跨接在任何链路上，无须网络流量经过就可以工作。因此，对 d sn i d s 的部署，唯一的要求就是：d sn j d s 应当挂接在所有关注的流量都必须 流经的链路上。在这里，“所关注的流量”指的是来自高危网络区域的访问流量和 需要进行统计、监视的网络报文。在如今的网络拓扑中，已经很难找到以前的h u b 式的共享介质冲突域的网络，绝大部分的网络区域都已经全面升级到交换式网络结 构。因此，d sn i d s 在交授式网络中的位置一般选择在： ( 1 ) 尽可能靠近攻击源；( 2 ) 尽可能靠近受保护资源 这些位置通常是： 服务器区域的交换机上 i n t e m e t 接入路出器之后的第台交换机上 重点保护网段的局域网交换机上 网络入侵检测系统经典的部署方式如下图所示： 26 本章小结 蕊 罔24d sn i d s 部署圈 心i n s 控制台 嗣 n i d s 柠剧 宰 本立从提高入侵检洲系统数据的处理速度入手，丰璺研究了入侵检测巾的特征 1 2 华北电力大学硕士学倚论文 选择算法、正常模式库的应用、入侵检测的k n n 分类算法、以及应用于网络数据 流分类的入侵检测算法。从方法上给出了一些可以提高数据处理的思路，并将这些 方法在整个体系结构中得到了整合。 1 3 华北电力大学硕士学位论文 第三章基于核与克隆选择的特征选择算法 3 1 特征选择的研究现状 随着模式识别与数据挖掘研究的深入，研究对象越来越复杂，对象的特征维数 越来越高。大量高维数据对象的特征空间中含有许多冗余特征甚至噪声特征，这些 特征一方面可能降低分类或聚类的精度，另一方面会大大增加学习及训练的时间及 空间复杂度。因此，在面对高维数据进行分类或聚类时，通常需要运用特征选择算 法找到具有较好可分性的特征子空间，从而实现降维，降低机器学习的时间及空间 复杂度【2 4 1 。 基于遗传算法( g e n e t i ca 1 9 0 r i t h ，g a ) 的特征选择算法体现了极大的潜力，并 取得了广泛的应用【z 耻6 1 。但是由于遗传算法的交叉和变异操作都是在一定概率下发 生的，是随机、没有指导性的对解空间进行搜索，从而会导致算法的收敛速度变慢， 很容易陷入局部最优，无法确保在一定代数内收敛到最优解。 免疫克隆选择算法( i m m u n ec l o n a ls e i e c t i o na i g o r i t h m ，i c s a ) f 2 5 】是模拟自然免疫 系统功能的一种新的智能方法，它继承了生物学抗体克隆选择过程所独有的学习、 记忆、抗体多样性等性能，并利用相应的算子保证算法能快速地收敛到全局最优解， 该算法已被证明了以概率l 收敛于全局最优解。文献【2 7 】中单纯使用免疫克隆选择 算法实现了特征选择算法，并取得了良好的效果，但是其算法中种群初始化过程使 用的是随机初始化，依然使得收敛的速度并不出色，本文结合了粗糙集中决策表的 核属性的理论，将其与特征选择算法相互结合，使得算法的进化代数和进化效率有 了很大的提高。所以本文在特征选择过程中使用了免疫克隆选择算法，并结合粗糙 集属性约简的理论，对高维数据进行特征选择。 3 2 问题描述 特征就是描述数据的属性，特征选择可以定义为：已知一个特征集，从中选择 一个最优的特征子集，并且该特征子集与原特征集具有相同的分类能力。以上定义 可以表达为：给定一个分类能力评价函数l ，一个信息系统s = ，【，为 论域，r = c u d ，子集c 和d 分别为条件属性集和决策属性集。y = lj 圪是属性值 的集合，厂是一个信息函数。c = k ，乞，q ) 说明该数据集是拥有力芩特征的数据 集。特征选择就是根据决策属性集得到满足( ) = ( c ) 一万( 万一o ) 的属性子集， 且j 乞j j c l 。 1 4 华北电力大学硕士学位论文 般而言，对于一个高维数据对象进行特征选择结果往往不是唯一的，人们更 希望找出具有最小属性个数的特征子集。在一个信息系统中，对于决策属性来说在 仅考虑分类准确性的情况下，如果条件属性的个数为，则其全部搜索空间大小为 2 ，显然是一个n p 问题。特征选择算法根据其是否依赖机器学习算法分为丘l t e r 和w r a p p c r 两类，f i l t e r 型算法不依赖机器学习算法，具有计算代价小，效率高的特 点，但是其降维效果一般；w r a p p e r 型算法依赖于特点的学习算法，所以其计算复 杂度非常大，但是降维效果非常好。粗糙集理论的出现给出了种属性独立约简的 方法，由此可见使用粗糙集理论进行特征选择是可行的，但是由于特征选择是一个 n p 完全问题，如何选择约简路径就成为了粗糙集理论解决属性约简的一个关键问 题，根据经验可知启发式的方法对于解决n p 问题有很好的效果，但是对于n p 问 题如果可以降低其搜索空间，那么必然可以降低其计算复杂度。根据这种思路，从 特征选择问题出发，如果知道哪些特征是必然要存在与最优结果当中的话，那么该 特征可以搜索过程当中省略，从而可以达到降低搜索空阎的目的。粗糙集理论中决 策表的核属性正是一种在属性约简结果中必然存在的属性，根据核属性的这一特 点，本文将核属性与克隆选择算法进行结合，首先通过计算核属性达到降低搜索空 间的目的，而后使用克隆选择算法在较低的特征空间中进行搜索并得到最优解。 3 2 1 克隆选择算法 1 9 5 8 年b u m e t 等人提出了著名的克隆选择学说，其中心思想是，抗体是天然产 物，以受体的形式存在于细胞表面，抗原可与之选择性的反应。抗原与相应抗体受 体的反应可导致细胞克隆增殖，该群体具有相同的抗体特异性，其中某些细胞克隆 分化为抗体生成细胞，另一些形成免疫记忆细胞，另一些形成免疫记忆细胞以参加 之后的二次免疫反应【邪j 。 由克隆选择原理可知，免疫细胞抗体在进化中体现出了优化的思想。在抗原抗 体的应答过程中，由于免疫系统内部有一种内在的分布性，没有总体上的中心控制 点，因此每个免疫细胞抗体都能接受特定刺激，并与新抗原反应，实现免疫应答。 这表明在抗体群体中，每个抗体在进化过程中都能够独立进行优化，而新生成的抗 体可以在更广泛的搜索空间中进行寻优，从而实现了多模态的优化。正是由于克隆 选择的这种多模念优化策略，因此可以有效地解决特征选择的多集合寻优。 假定数据集有个特征，用免疫克隆选择的方法解决特征选择问题就可以被描 述为以x = “，而，h ) 为变量的组合优化问题( p ) ：m a ) 【 厂( p 叫( 彳) ：彳f ) ，其中 彳= q ，口：，口是变量x 的抗体编码，记为彳= p ( x ) ；集合，就是抗体空间，为，上 的实值函数，也被称为亲合度函数。特征选择的问题就是使得厂( 幸