（模式识别与智能系统专业论文）基于prefixspan算法的计算机入侵检测研究.pdf

摘 要 计算机入侵检测技术是近年来计算机网络安全领域的重要方向。本文首先介 绍了防火墙和入侵检测系统的技术发展。入侵检测是计算机内部网中位于防火墙 之后的安全防护工具，是一种积极主动检测攻击的方法。由于入侵检钡4 系统是网 络安全防护中的最后一道屏障，其在系统安全方面的作用和重要性也就显得格外 重要。入侵检测按检测方式可以分为误用检测和异常检测。目前的异常检测方法 有统计方法、神经网络、数据挖掘等。数据挖掘是近年来兴起的一种数据库中知 识发现的技术( k d d ，k n o w l e d g ed i s c o v e r i nd a t a b a s e ) ，在挖掘海量数据中的 有用知识中性能强大。本文介绍了上述几种异常检测算法，并对他们的优缺点进 行了比较论述。详细介绍了数据挖掘技术在入侵检测系统中的应用，并将其中的 序列模式分析算法应用在异常检测技术之中。文中对目前主要的三种序列模式分 析方法进行了比较分析。改进了其中性能晟好的p r e f i x s p a n 算法，提高了其挖掘 速度，降低了算法运行的内存损耗，将改进后的算法应用到入侵检测中的异常检 测技术中，并采用网络连接审计记录进行了实验数据仿真，给出了结果分析和未 来技术发展的展望。 关键词数据挖掘：入侵检测；异常检测；误用检测： 频繁序列 a b s t r a c t i n t r u s i o nd e t e c t i o ni sai m p o r t a n ti s s u ei nc o m p u t e r n e t w o r k s e c u r i t y t h i sp a p e r i n t r o d u c e dt h ed e v e l o p m e n ti nf i r e w a l la n di n t r u s i o nd e t e c t i o nf i r s t i n t r u s i o nd e t e c t i o ni saf a c i l i t yw h i c hi se q u i p p e dh i d d e nb e h i n df i r e w a l l i tw o r k s a c t i v et od e t e c t p o s s i b l ei n t r u s i o n i n t r u s i o nd e t e c t i o n i sv e r yi m p o r t a n tb e c a u s ei t st h ef i n a ls h i e l d t ot h ei n t r u d e r f r o mt h ep o i n to f v i e w o f t e c h n i q u e ，i n t r u s i o nd e t e c t i o n c o n s i s t so f m i s u s ed e t e c t i o na n da n o m a l yd e t e c t i o n t h e r eh a sb e e ns o m ea n o m a l yd e t e c t i o n a l g o r i t h m ，s u c h a ss t a t i s t i cm e t h o d ，a r t i f i c i a ln e u r a ln e t w o r k m e t h o d ，e x p e r ts y s t e m s a n dd a t am i n i n ga l g o r i t h m s d a t am i n i n gi sar e c e n t l yd e v e l o p e dm e t h o du s e dt o d i s c o v e rk n o w l e d g ei nd a t a b a s e i t ss t r o n gt od i s c o v e rk n o w l e d g ei nh u g ed a t a b a s e s t h i sp a p e rl i s t sa l lt h em e t h o d sm e n t i o n e da b o v e ，a n dc o m p a r e dt h e s em e t h o d s b ya n a l y z i n g e a c h ss t r o n g p o i n t sa n d d i s a d v a n t a g e s a n dt h e nd e m o n s t r a t e dt h ea p p - l i a n c eo f d a t a m i n i n gm e t h o di ni n t r u s i o nd e t e c t i o ni nd e t a i l i nt h i sp a p e rw ea p p l i e d t h es e q u e n t i a lp a t t e r n sm i n i n gm e t h o dt oa n o m a l yd e t e c t i o n w ec o m p a r e dt h et h r e e m a i n s e q u e n t i a lp a t t e r n sm i n i n ga l g o r i t h m s ，a n dm o d i f i e dt h eb e s ta l g o r i t h mi n p e r f o r m a n c e _ p r e f i x s p a nt og e tf a s t e rm i n i n gs p e e da n dl e s sm e m o r y c o n s u m p t i o n w e a p p l i e dt h i sd e v e l o p e da l g o r i t h mt oa n o m a l yd e t e c t i o n w ed oe x p e r i m e n t su s i n ga p i e c eo f n e t w o r kc o n n e c t i o na u d i td a t a f i n a l l y ，w eg a v et h er e s u l ta n a l y s i sa n dc o n c l u s i o n k e y w o r d sd a t am i n i n g ；i n t r u s i o nd e t e c t i o n ；a n o m a l yd e t e c t i o n ；m i s u s e d e t e c t i o n ： f r e q u e n te p i s o d e s 致谢 时间犹如白驹过隙，三年的功夫一眨眼就过去了。本科毕业的时候宛 若近在眼前。毕业在即，回想三年的学习生活，有很多感触在心中。太多 的人对我的关心和帮助让我难以割舍这片土地。 首先，感谢我的导师奚宏生教授。奚老师不仅学术水平高，而且对工 作认真负责，经常工作到晚上7 、8 点钟，双休日也能在实验室看到奚老 师忙碌的身影。读研的三年中，奚老师不仅指导我的研究工作，还教会我 好多做人的道理。奚老师的治学态度、对学生的精心培育，都足以作为我 一世的楷模。在此祝奚老师身体健康、工作顺利，在事业上取得更大的进 展。 其次，感谢班主任周荷琴周老师，周老师的工作很忙，还要管理我们 这个班级的一些琐碎的事情，跟周老师接触得越多，就越能感受到她的慈 祥。祝周老师身体健康，工作不要太过于操劳。 感谢系里的其他老师，这三年之间，他们或多或少都在无私的给予着 我帮助，才会使我顺利的度过研究生这一段紧张的学习生涯。祝你们身体 健康，事业上取得更大的成功。 感谢实验室的成员：谭晓彬，高荣，吴峰光，黄林华，赵宇，杨坚， 候继周，高绪东和低年级的师弟们。你们在这三年给了我很多的帮助。祝 你们身体健康，将来事业有成，拥有美满的家庭。 最后，谨以此文，作别我学习、生活了八年的中国科学技术大学，我 将努力为你争光! 张胜斌 2 0 0 3 5 9 茎至! 竺! ! ! ! 竺苎望塑生篓塑尘生堕塑塑翌王 第一章计算机入侵检测 1 1 计算机安全问题 随着计算机和网络技术的发展，计算机系统已经从独立的主机发展到复杂 的，开放式互联的网络系统随着网络规模的不断扩大，网络使用者的增多，计算 机的入侵成为一个严峻的问题黑客已经成为一个广泛的话题，其入侵行为时常 可以见之报端，即便是大公司和政府要害部门的计算机系统也不能幸免于黑客的 攻击。1 9 9 9 年】o 月7 日美国政府官员称，来自俄罗斯的黑客们已经系统性的入侵 了美国国防部的电脑系统，并窃取了数量巨大的敏感信息；1 9 9 9 年4 月6 1 3 ，美国 三个核武器实验室被迫关闭他们的机密计算机系统一个星期以上，以加强计算机 的安全防护：1 9 9 8 年9 月，美国海军的一个网络安全小组称，全球各地的黑客们 联合起来实行难以发现的攻击，以图骗过安全专家和入侵检测软件的侦察，据称 检测到从分布在几个大陆的1 5 个地点同时发起的攻击，专家认为攻击者储存 并 共享了入侵海军站点得来的信息。( 文献1 ) 1 2 防火墙 因特网的安全防护主要依赖于防火墙和入侵检测系统。防火墙是一种计算机 软件和硬件的组合，在因特网和内部互联网之间建立一个安全网关，从而保护内 部网免受非法用户的侵入。防火墙的基本思想是：让外界因特网对内部网的访问 都通过这一点，通过这一点对网络访问的控制来隔绝外界入侵者对内部网络的访 问。防火墙可以从通信协议的各个层次以及应用中获取、存取并管理相关的信息， 以便实施系统的访问安全决策控制。防火墙技术已经历了三个发展阶段，即包过 滤技术、代理技术和状态监视技术。包过滤防火墙的安全性是基于对包的i p 地址 的校验。它将所有通过的包中发送方和接收方的i p 地址和t c p 端口以及t c p 链路状 态等信息读出，并按照预先设定的规则过滤信息包。这是一种基于网络层的安全 技术，对于应用层的黑客行为无能为力。代理服务器接受客户请求之后会检查验 证其合法性，如合法，则代理服务器取回所需信息再转发给客户。它将系统内部 署u # l - 界隔离开来，从外部网络只能看到代理服务器而看不到任何内部资源。服务 器只允许有代理的服务通过，另外代理服务器还可以过滤协议，如可以过滤f t p 连接，拒绝使用f t p 的上载命令，以保证用户不能写文件到匿名服务器。代理服 务具有信息隐蔽、保证有效的认证和登录、简化了过滤规则等优点。网络地址转 苎王! 竺! ! ! ! 竺苎鲨堕生兰! 坠垒堡丝型! 壅一 换月臣务( n a t n e t w o r k a d d r e s st r a n s l a t i o n ) 可以屏蔽内部网络的i p 地址，使网 络结构对外部来说是不可见的。自适应代理技术可根据用户定义的安全规则，动 态“适应，传送中的数据流量。当安全要求较高时，安全检查仍在应用层中进行， 保证实现传统防火墙的最大安全性：而一旦可信任身份得到确认，数据便可直接 快速通过网络层。状态监视技术是第三代网络安全技术。状态监视服务的监视模 块在不影响网络安全正常工作的前提下，采用抽耿相关数据的方法对网络通信的 各个层次实行监测，并作安全决策的依据。监视模块支持多种网络协议和应用协 议，可以方便地实现应用和服务的扩充。状态监视服务可以监视r p c ( 远程过程调 用) 和u d p 端口信息，而包过滤和代理服务则都无法做到。 使用防火墙的益处： 保护脆弱的服务：通过过滤不安全的服务，防火墙可以极大地提高网络安全 和减少子网中主机的风险。例如，防火墙可以禁止n f s 、n r s 服务通过，同时可以 拒绝源路由和i c m p 重定向封包。 控制对系统的访问：防火墙可以提供对系统的访问控制。如允许外部访问某 些主机，同时禁止访问另外的主机。 集中的安全管理：防火墙对企业内部网络实现集中的安全管理，在防火墙定 义的安全规则可以运行于整个内部网络，而无需在内部网每台主机上分别设立安 全策略。防火墙可以定义不同的认证方法，而不需要在每台机器上分别安装特定 的认证软件。外部用户也只需要经过一次认证就可以访问内部网。 进行地址变换：防火墙的n a t 功能使整个内部网在外部看来就是一个地址， 从而隐藏了内部网络结构。另外，它可以缓解地址空间短缺的问题。 防止内部信息的外泄：使用防火墙可以阻止攻击者获取攻击网络系统的有用 信息，如f i g e r 和d n s 。 对网络存取和访问进行监控审计：防火墙是审计和记录i n t e r n e t 使用量的一 个最佳地方。防火墙可以记录和统计通过它的网络通讯，提供关于网络使用的统 计数据。并且，防火墙可以提供统计数据，来判断可能的攻击和探测。 安全策略执行：防火墙提供了制定和执行网络安全策略的手段。未设置防火 墙时，网络安全取决于每台主机的用户。 防火墙的局限性： 2 苎王堕! ! ! ! ! ! 苎鲨盟生簦! ! 仝堡丝型型l 一 防火墙是内部网络的第一道防线，用以防止非法数据的进入和内部数据的泄 漏。但防火墙不是万能的，它只能被动地防止外部网络对内部网络地破坏，只能 按照预先地设定成不变地过滤网络数据传送。并且由于性能的限制，防火墙 通常不提供有效的安全保护能力。防火墙不能防范不经过防火墙的攻击。例如， 如果允许从受保护的网络内部向外拨号，一些用户就可能形成与i n t e r n e t 的直 接连接。另外，防火墙完全不能阻止来自内部的袭击，对于企业内部心怀不满的 员工来说，防火墙形同虚设。防火墙只允许来自外部网络的一些规则允许的服务 通过，并且往往无法做到完全的用户透明性，这样反而会给网络用户增添很多的 不便，抑制一些正常的信息通信，从某种意义上说大大削弱了i n t e r n e t 应有的功 能。并且防火墙提供的是粗粒度的访问控制，且不能同企业内部所使用的其他安 全机制( 如访问控制) 集成使用，这样，企业必须为内部的身份验证和访问控制管 理维护单独的数据库防火墙主要是采取基于i p 地址的安全策略，难于为用户在 防火墙内外提供一致的安全策略，限制了企业网的物理范围防火墙的另一个缺 点在于其难于管理和配置，易造成安全漏洞，防火墙的管理和配置相当复杂，要想 成功地维护防火墙，要求防火墙管理员对网络安全攻击的手段及其与系统配置的 关系有相当深刻的了解 1 3 入侵检测系统 当黑客采取种种手段通过了防火墙的检验和认证，最后剩下的屏障就是入侵 检测系统。入侵检测是一种积极主动的安全防护技术，提供了对内部攻击，外部 攻击和误操作的实时保护。它具有以下主要作用： a 监测并分析用户和系统的活动： b 核查系统配置和漏洞 c 评估系统关键资源和数据文件的完整性 d 识别已知的攻击行为 e 统计分析异常行为 董王! 竖! ! ! 竺竺鎏堕苎苎塑尘堡丝型竺妻一 f 操作系统日志管理，并识别违反安全策略的用户活动。 它能动态适应系统的复杂情况，在网络系统受到危害之前拦截和相应入侵。 它从网络系统中的若干关键点收集信息并加以分析，以确定网络之中是否有违反 安全策略的行为和遭到攻击的迹象。一般将审计跟踪，攻击检测系统作为信息系 统的最后一道安全防线。 计算机入侵检测系统按照数据源可分为基于主机的入侵检测系统和基于网 络的入侵检测系统 基于主机的入侵检测系统 基于主机的入侵检测系统出现在8 0 年代初期，那时网络还没有今天这样普 遍、复杂，且网络之间也没有完全连通。在这一较为简单的环境罩，检查可疑行 为的检验已录是很常见的操作。由于入侵在当时是相当少见的，在对攻击的事后 分析就可以防止今后的攻击。现在的基于主机的入侵检测系统保留了这样的方 法，以理解以前的攻击形式，并选择合适的方法去抵御未来的攻击。基于主机的 i d s 仍使用验证记录，但自动化程度大大提高，并通过对用户行为和程序系统调 用序列等的分析，可迅速做出响应。 基于主机的i d s 在发展过程中融入了其它技术。对关键系统文件和可执行文 件的入侵检测的一个常用方法，是通过定期检查校验和来进行的，以便发现意外 的变化。反应的快慢与轮询间隔的频率有直接的关系。最后，许多产品都是监听 端口的活动，并在特定端口被访问时向管理员报警。这类检测方法将基于网络的 入侵检测的基本方法融入到基于主机的检测环境中。 尽管基于主机的入侵检查系统不如基于网络的入侵检查系统快捷，但它确实 具有基于网络的系统无法比拟的优点。这些优点包括： 性能价格比高在主机数量较少的情况下，这种方法的性能价格比可能更 高。尽管基于网络的入侵检测系统能很容易地提供广泛覆盖，但其价格 通常是昂贵的。配置一个入侵监测系统要花费$ 1 0 ，0 0 0 以上，而基于主 机的入侵检测系统对于单独一代理标价仅几百美元，并且客户只需很少 的费用用于最初的安装。 更加细腻这种方法可以很容易地监测一些活动，如对敏感文件、目录、 程序或端口的存取，而这些活动很难在基于网络的系统中被发现。基于 茎王! ! ! ! ! 1 2 竺蔓鎏堕旦兰垫垒垦丝塑翌茎- 一 主机的i d s 监视用户和文件访问活动，包括文件访问、改变文件权限、 试图建立新的可执行文件并且或者试图访问特许服务。例如，基于主 机的i d s 可以监督所有用户登录及退出登录的情况，以及每位用户在联 接到网络以后的行为。基于网络的系统要做到这个程度是非常困难的。 基于主机技术还可监视通常只有管理员才能实施的非萨常行为。操作系 统记录了任何有关用户帐号的添加、删除、更改的情况。一旦发生了更 改，基于主机的i d s 就能检测到这种不适当的更改。基于主机的i d s 还 可审计能影响系统记录的校验措施的改变。最后，基于主机的系统可以 监视关键系统文件和可执行文件的更改。系统能够检测到那些欲重写关 键系统文件或者安装特洛伊木马或后门的尝试并将它们中断。而基于网 络的系统有时会检测不到这些行为。 视野集中一旦入侵者得到了一个主机的用户名和口令，基于主机的代理 是最有可能区分正常的活动和非法的活动的。 易于用户剪裁每一个主机有其自己的代理，当然用户剪裁更方便了。 较少的主机基于主机的方法有时不需要增加专门的硬件平台。基于主机 的入侵检测系统存在于现有的网络结构之中，包括文件服务器、w e b 服 务器及其它共享资源。这些使得基于主机的系统效率很高。因为它们不 需要在网络上另外安装登记、维护及管理的硬件设备。 对网络流量不敏感用代理的方式一般不会因为网络流量的增加而丢掉 对网络行为的监视。 适用于被加密的以及切换的环境由于基于主机的系统安装在遍布企业 的各种主机上，它们比基于网络的入侵检测系统更加适于交换的以及加 密的环境。交换设备可将大型网络分成许多的小型网络段加以管理。所 以从覆盖足够大的网络范围的角度出发，很难确定配置基于网络的i d s 的最佳位置。业务镜像和交换机上的管理端口对此有帮助，但这些技术 有时并不适用。基于主机的入侵检测系统可安装在所需的重要主机上， 在交换的环境中具有更高的能见度。某些加密方式也向基于网络的入侵 检测发出了挑战a 根据加密方式在协议堆栈中的位置的不同，基于网络 的系统可能对某些攻击没有反应。基于主机的i d s 没有这方面的限制。 薹兰! ! 生：! 竺蔓婆盟生簦垫垒堡丝塑坚壅一 当操作系统及基于主机的系统发现即将到来的业务时，数据流已经被解 密了 确定攻击是否成功由于基于主机的i d s 使用含有已发生事件信息，它们 可以比基于网络的i d s 更加准确地判断攻击是否成功。在这方面，基于 主机的i d s 是基于网络的i d s 完美补充，网络部分可以尽早提供警告， 主机部分可以确定攻击成功与否 基于网络的入侵检测系统 基于网络的入侵检测系统使用原始网络包作为数据源。基于网络的i d s 通常 利用一个运行在随机模式下网络的适配器来实时监视并分析通过网络的所有通 信业务。它的攻击辩识模块通常使用四种常用技术来识别攻击标志： 模式、表达式或字节匹配 频率或穿越阀值 次要事件的相关性 统计学意义上的非常规现象检测 一旦检测到了攻击行为，i d s 的响应模块就提供多种选项以通知、报警并对 攻击采取相应的反应。反应因产品而异，但通常都包括通知管理员、中断连接并 且或为法庭分析和证据收集而做的会话记录。 基于网络的i d s 有许多仅靠基于主机的入侵检测法无法提供的功能。实际上， 许多客户在最初使用i d s 时，都配置了基于网络的入侵检测。基于网络的检测有 以下优点： 侦测速度快基于网络的监测器通常能在微秒或秒级发现问题。而大多数 基于主机的产品则要依靠对最近几分钟内审计记录的分析。 隐蔽性好一个网络上的监测器不像一个主机那样显眼和易被存取，因而 也不那么容易遭受攻击。基于网络的监视器不运行其他的应用程序，不 提供网络服务，可以不响应其他计算机。因此可以做得比较安全。 视野更宽基于网络的入侵检测甚至可以在网络的边缘上，即攻击者还没 能接入网络时就被发现并制止。 较少的监测器由于使用个监测器就可以保护一个共享的网段，所以你 茎王! ! ! ! ：! ! ! 苎垄塑生篓塑尘生生塑塑堕壅一 不需要很多的监测器。相反地，如果基于主机，则在每个主机上都需要 一个代理，这样的话，花费昂贵，而且难于管理。但是，如果在一个交 换环境下，就需要特殊的配置。 攻击者不易转移证据基于网络的i d s 使用正在发生的网络通讯进行实 时攻击的检测。所以攻击者无法转移证据。被捕获的数据不仅包括的攻 击的方法，而且还包括可识别黑客身份和对其进行起诉的信息。许多黑 客都熟知审记记录，他们知道如何操纵这些文件掩盖他们的作案痕迹， 如何阻止需要这些信息的基于主机的系统去检测入侵。 操作系统无关性基于网络的i d s 作为安全监测资源，与主机的操作系统 无关。与之相比，基于主机的系统必须在特定的、没有遭到破坏的操作 系统中才能正常工作，生成有用的结果。 占资源少在被保护的设备上不用占用任何资源。 基于网络和基于主机的入侵检测系统都有各自的优势，两者相互补充。这两 种方式都能发现对方无法检测到的些入侵行为。从某个重要服务器的键盘发出 的本地攻击并不经过网络，因此就无法通过基于网络的入侵检测系统检测到，只 能通过使用基于主机的入侵检测系统来检测。基于网络的入侵检测系统通过检查 所有的数据包的包头( h e a d e r ) 来进行检测，而基于主机的入侵检测系统并不查 看包酋标。许多基于i p 的拒绝服务攻击和碎片攻击，只能通过查看它们通过网 络传输时的包首标才能识别。基于网络的入侵检测系统可以研究负载的内容，查 找特定攻击中使用的命令或语法，这类攻击可以被实时检查包序列的入侵检测系 统迅速识别。而基于主机的系统无法看到负载，因此也无法识别嵌入式的负载攻 击。联合使用基于主机和基于网络这两种方式能够达到更好的检测效果。比如基 于主机的入侵检测系统使用系统同志作为检测依据，因此它们在确定攻击是否已 经取得成功时与基于网络的检测系统相比具有更大的准确性。在这方面，基于主 机的入侵检测系统对基于网络的入侵检测系统是一个很好的补充，人们完全可以 使用基于网络的入侵检测系统提供早期报警，而使用基于主机的入侵检测系统来 验证攻击是否取得成功。 入侵检测系统模型 c i d f ( c o m m o n i n t r u s i o nd e t e c t i o nf r a m e w o r k ) 阐述了一个入侵检测系统 叁王罂! ! 1 2 竺苎鲨堕兰苎塑垒堡丝型竺垄一 ( i d s ，i n t r u s i o nd e t e c t i o ns y s t e m ) 的通用模型它将一个入侵检测系统分为以 下组件： 事件产生器( e v e n tg e n e r a t o r s ) 事件分析器( e v e n ta n a ly z e r s ) 响应单元( r e s p o n s eu n it s ) 事件数据库( e v e n td a t a b a s e s ) c i d f 将i d s 需要分析的数据统称为事件( e v e n t ) ，它可以是网络中的数据包， 也可以是从系统日志等其他途径得到的信息事件产生器负责从整个环境中获得 事件，并向系统的其他部分提供此事件事件分析器分析得到的数据，并产生分析 结果响应单元则是对分析结果作出反应的功能单元，它可以作出切断连接、改变 文件属性等强烈反应，也可以只是简单地报警。事件数据库是存放各种中间和最 终数据的地方的统称，它可以是复杂的数据库，也可以是简单的文本文件。入侵 检测系统中的数据流模型如下图所示： 图l 保护内部网的入侵检测系统往往采取分布式的结构，其功能部件分布于不同 的主机上，这是由系统特征和处理机性能决定的。比如基于主机和基于网络相结 合的系统，在需要保护的主机上安装主机i d s ，监控网络数据包的检测子系统一般 安装运行于空闲的主机上，为提高性能，事件产生器、事件分析器和响应单元一 般放置于不同的机器上。由此必须对i d s 模块之问的通信制定相应的标准和协议。 薹量! 墅! 1 2 翌兰堕堕兰垫垒堡笪型堡壅一 i e t f 目前有一个专门的小组i n t r u s i o nd e t e c t i 。n w o r k i n gg r o u p ( i d w g ) 负责制 定这样的通信格式，称作i n t r u s i o nd e t e c t i o ne x c h a n g ef o r m a t ，目前只有相关 的草案，并未形成正式的r f c 文档。 一个分布式入侵检测系统的框架如下图所示： 图2 9 墨王! 竺! ! ! 竺苎莲堕兰兰塑垒堡笪型堡茎一 第二章 入侵检测算法概论 2 1 概述 入侵检测方法可分为异常检测( m i s u s ed e t e c t i o n ) 和误用检测( a n o m a l y d e t e c t i o n ) ，误用检测抽取曾发生过的攻击的特征模式，记录于数据库中，进行 检测时匹配攻击的特征和行为特征，若相同则判为入侵，其实现方式类似于杀毒 软件；异常检测的主要思想是建立正常行为的特征库，然后比较行为的特征和特 征库的相似程度，据此判断是否为入侵行为。误用检测的优点在于匹配到攻击模 式就可以报警，只要尽可能完善攻击模式库就可以基本出检测出己有的攻击，缺 点是不能对未知的攻击进行检测异常检测的优点在于其灵活性，即不受对攻击 行为认识的有限性的限制，只要充分进行正常行为建模，提高建模和检测算法， 理论上可发现所有的攻击，无论这攻击是否曾发生过，其缺点是相对于误用检测， 其误检率和误报率均偏高。 异常检测的算法主要分为统计方法( 文献2 0 ，2 2 ) ，神经网络( 文献1 7 ，1 8 ，1 9 ) 和数据挖掘( 文献1 2 ，1 3 ，1 4 ) 等等方法。 2 2 统计方法 基于统计的方法，其主要思路是对正常的用户或者网络行为进行统计学建 模，形成行为的统计特征库和或行为序列的概率转移库。 统计特征库的算法可描述如下：系统生成原始的行为特征文件，异常检测系 统定期从原始来的特征文件生成新的特征文件。特征文件包括许多衡量特征，例 如：活动频率及分布情况、c p u 的使用时间、一段时问内的网络连接数、审计记 录的分布情况等等。特征文件只占用很小的空间来存储，并且能够高效更新。随 着系统定期更新过期的数据，当对输入的审计记录进行处理时，系统生成一个新 的值来表示其异常性。该值是通过一个函数计算出来的，函数的输入是组成特征 文件每种衡量特征的异常度的值。例如，一个用户的特征文件有n 个衡量特征 m ，一 毛，每一种所对应的异常度为s ，氐，s 越大表明异常度越高，这样 ，用户总的异常度可以表达为s = a , s , 2 + q g + ，+ 吼鄙，q o ，- l 。其 中d ，可以是各个衡量特征的权重，通常m ，并不是完全独立的，这将导致更复杂 1 0 苎王! 曼! ! ! ! 竺苎垦笪型! 醴坠兰堡丝塑塑婴l 一 的算法。( 文献2 3 ) 用随机过程中的m a r k o v 系列模型可以对用户行为序列、网络连接序列和系统 调用序列等进行学习，建立他们的序列转移模型，以概率转移的方式描述行为状 态的转换。这类方法有m a r k o v 过程、隐马氏模型( h j d d e nm a r k o v m o d e l ) 等。像 所有的异常检测算法一样，m a r k o v 系列模型的建立需要大量的难常状态下所要学 习序列的数据，因为小样本训练出来的概率是没有意义的。用户、网络连接、程 序的系统调用决不会是错乱而毫无章法地胡乱跳变的，它们总是遵循着一定的规 律。m a r k o v 算法的根本在于准确计算行为从一个状态变换到下个或下几个状态 的可能性，以近似概率的方式表达并储存起来。实际进行异常检测的时候，当状 态的转换发生了异常( 小概率转移的发生，甚至是多次的发生) ，我们可以据此认 为行为的状态异常，有可能是入侵者在攻击系统。m a r k o v 链和隐马氏模型的不同 在于，m a r k o v 链的状态是行为序列的一个节点，状态的变化即行为的转移，事实 上，系统中用户所能执行的命令、网络连接的种类、系统调用的数目都是较多的。 l i n u x 下的系统调用就有2 0 0 多个。这样，即使只计算一步的概率转移，所得出的 也是维数很大的矩阵。这么大的矩阵训练起来所耗费的计算量是非常大的。隐马 氏模型是m a r k o v 模型的演化。隐马氏模型呈两层结构，顾名思义，底下隐藏的是 状态转移链，上层可观测到的是行为链。隐马氏模型定义了行为可能停留的n 种 状态。通过训练学习出下层状态转移和上层行为链的概率关系。检测时根据行为 链判断出概率最大的状态链，根据这条状态链在对正常行为的训练结果中出现的 概率大小判断异常状况出现的可能。隐马氏模型自定义状念的数量一般都小于单 个行为的数量。这样可以减少模型训练的运算量。同时隐马氏模型的状念划分融 入了人类专家对行为的先验认识，其有效性和准确性与专家的判断有较大关系。 ( 文献2 0 中给出了基于隐马氏模型的异常检测的例子) 统计方法的好处在于可以自适应地学习用户的行为，因而可能比人类的专家 更为敏感。这种方法同时也存在着问题：系统可能被入侵者逐渐训练，到最后入 侵事件也会被认为是正常事件。统计方法的关键问题，也是异常检测系统的共同 问题，即如何选择要监视的衡量特征，如何在所有可能的衡量特征中选择合适的 特征子集，以及如何选择合适的异常阈值，才能够准确地检测入侵行为。 堇王! 兰! ! ! 竺兰鲨塑盐兰塑垒堡丝型里壅一 2 3 神经网络方法 如上所述，基于审计统计数据的攻击检测系统，具有一些天生的弱点，因 为用户的行为可以是非常复杂的，所以想要准确匹配一个用户的历史行为和当前 的行为是相当困难的。错发的警报往往来自于对审计数据的统计算法所基于的不 准确或不贴切的假设。s r i 的研究小组利用和发展神经网络技术来进行攻击检测。 神经网络可能用于解决传统的统计分析技术所面临的以下几个问题： 难于建立确切的统计分布 难于实现方法的普适性 算法实现比较昂贵 系统臃肿难于剪裁 目前，神经网络技术提出了对基于传统统计技术的攻击检测方法的改进方向，但 尚不十分成熟。 2 4 数据挖掘方法 数据挖掘( d a t am i n i n g ) ，或称之为数据库中的知识发现( k d d ，k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) ，是从数据库数据仓库中对数据进行一定的处理， 挖掘出有用的、潜在的、能够被人理解的模式。所谓模式，可以看作是我们所 说的知识，它给出了数据的特性或数据之间的联系，是对数据所包含的信息更加 抽象的描述。这些知识和信息通常以知识概念( c o n c e p t s ) 、规律( r e g u l a t i o n s ) 、 规则( r u l e s ) 、限制( 1 i m i t a t i o n s ) 、模式( p a t t e r n ) 、约束( c o n s t r a i n t s ) 、可视 化( v i s u l i z a i t i o n ) 等形式来表现。 数据挖掘的技术基础是人工智能，它利用了人工智能的一些已经成熟的技术 和算法。例如人工神经网络、遗传算法、决策树、邻近搜索算法、规则推理、模 糊逻辑等。数据挖掘利用的技术越多，得出的结果精确性就越高。这主要取决于 问题的类型以及数据的类型和规模。无论使用何种技术来完成数据挖掘的工作， 从功能上可以把数据挖掘分为以下几种： 关联分析方法( a s s o c i a t i o n s ) 序列模式分析( s e q u e n t i a lp a t t e r n s ) 分类分析( c l a s s i f i e r s ) 聚类分析( c l u s t e r i n g ) 董王! ! ! ! ! 1 2 1 1 整堡塑生竺巡堕型! ! 壅一 关联分析目的是挖掘出隐藏在数据项( i t e m ) 之间的相互关系。给定一组 i t e m 和一个记录集合，通过分析记录集合，得出i t e m 之间的相关性。 序列模式分析与关联分析类似，序列分析方法的目的也是挖掘数据之间的 相关性，与之不同的是，给定组i t e m 和一个记录集合，序列模式分析方法的任 务是挖掘记录之间前后相继的相关程度。形象地说，关联分析是“横向”的，挖 掘记录内部各i t e m 之间的关系；序列模式分析是“纵向”的它挖掘记录之间的 关系。不论入侵者如何刻意遮掩，其先后行为之间肯定是具有一定规律的，不然 入侵检测算法根本就无从谈起。比如黑客入侵的时候，一般都会对系统进行端口 扫描等等。 分类分析假定记录集合和一组标记。标记是指一组具有不周特征的类别。 分类分析时首先为每一个记录赋予一个标汜，即按标记分类记录，然后检测这些 标记的记录，描述出这些记录的特征。例如对黑客入侵行为，可按照危害性将其 分为致命入侵、一般入侵、弱入侵。当然还可根据其他标准来进行分类。分类分 析检查以前的黑客入侵行为，根据分类标准对每一个危害等级进行分类，然后给 出每个等级的描述。 聚类分析聚类分析的输入集是一组未标定的记录，也就是说在分析之前记 录未被进行任何的分类。聚类分析的目的就是根据一定的规则，合理地划分记录 集合，并用显示或者隐式的方法标定不同的类别。所依据的规则是由聚类分析的 工具定义的。由于聚类分析可以采用不同的分类规则，所以对相同的记录集合可 以有不同的划分。 数据挖掘的这四种方法具有不同的适用范围。关联分析可以用来提取行为各 特征之间的关联度。举个例子，用关联分析可以得出从某个固定i p 地址发起大量 网络连接中使用各种服务( 女【 h t t p ，f t p ) 的比例，由此推断出正常情况下这个地 址所请求的服务是哪些类型，它们的置信度又各是多少。序列模式分析方法是异 常检测的有力工具。从黑客入侵行为开端开始，任何一个孤立的举动都是不能达 到入侵的目的的。黑客必须执行一连串的操作，才能成功的登入系统进行破坏。 在这一过程中，尽管黑客刻意地用一些没有意义的命令、连接和系统调用进行修 饰，妄图掩盖其入侵系统的真实目的，但具有攻击危险的行为序列总是有迹可寻。 序列模式分析方法可以用来提取行为的时间序列特征，应用于误用检测时，提取 苎王! 鬯! ! 苎! 墨鎏塑生竺塑垒堡垫型堑壅一 攻击行为的特征，检测时检查所监控的行为的序列特征是否与已有攻击的特征相 匹配，若匹配则判为攻击：应用于异常检测时，用大量的正常行为序列来训练序 列模式分析算法，并使之生成正常行为的序列特征库，并存储相应的支持度与置 信度等信息，检测时监控行为序列是否在库中，若是，提取其支持度与置信度数 据，根据一定的判别规则判断是否异常，若否，则判为异常。分类分析方法可以 用于入侵行为分类问题。利用关联分析和序列模式分析的结果，定义入侵行为的 分类标准，并进行描述。此外，可以应用聚类分析方法，以前面所得的描述为基 础，根据一定的规则，抛弃原有的分类结果，对行为数据重新进行划分并用显式 的或隐式的方法对不同划分进行描述，以此获得更好的结果。( 文献l o ) 数据挖掘方法的分析过程一般要经过以下几个步骤： ( 1 ) 数据准备：这个阶段，从操作环境中提取数据。 ( 2 ) 数据预处理：将得到的原始数据集成，从中选择需要进行挖掘的数据， 并对之进行平滑，去噪，删除冗余数据，消除不一致数据等数据清理操 作，最后将数据变换成统一的适合挖掘的形式。 ( 3 ) 数据挖掘：基本步骤，利用以上提及的某种或某几种数据挖掘方法挖掘 预处理后的数据，提取相应的规则和特征。 ( 4 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式，即 感兴趣的、有用的知识。 ( 5 ) 知识表示：数据挖掘将所得到的知识以便于理解和观察的方式提供给系 统和管理员。在入侵检测系统中，通过数据挖掘，发现了有关的规则和 特征之后，再根据这些特征和规则将用户的异常模式和f 常模式定义出 来，然后存储在知识库中。 ( 6 ) 评价：可以对数据挖掘后所提取的网络安全异常模式或f 常模式进行评 价，如果能够有效地检测出入侵行为，就说明它是成功的。否则，可修 订挖掘规则，重复进行挖掘直至成功。 数据挖掘技术作为一种已经比较成熟智能化的知识发现工具，内含的算法可 以丰富地挖掘数据中的横向、纵向关系，挖掘数据中频繁出现的特征。其应用在 入侵检测方面，可以在以下几点作出贡献：( 文献1 1 ) ( a ) 从引发警报的数据段中删除正常数据，以便集中精力研究真实的攻击行 苎王! 些! ：! 竺蔓鲨竺生兰塑垒堡堕型塑垄一 为： ( b ) 识别虚假警报发生器和“坏的”传感器信号； ( c ) 找出揭露真实攻击的异常行为： ( d ) 识别很长的、持续的序列( 例如不同i p 源地址进行相同的操作) 以下先简单介绍数据挖掘几种方法的具体实现： 根据统计学的观点，事物的性质由经常出现的特征刻画。因此数据挖掘中的 关联分析，序列模式分析均围绕数据中的频繁项而展开。数据挖掘在异常检测方 面主要的算法应用还是关联分析和序列模式分析。因此后面详细介绍这两类方法 的现状和性能改进，对分类和聚类均简单介绍而不涉及具体应用。 2 4 1 关联分析： 基本概念： 设i = ，岛，) 为数据项集合；设d 为与任务相关的数据集合，也就是个 交易数据库；其中的每个交易t 是一个数据项子集，即r i ；每个交易均包含一 个识别编号t i 。设a 为一个数据项集合，当且仅当a t 时就称交易t 包含a 。一 个关联规则就是具有“a j 口”形式的蕴含式；其中有a c ，b c i 且a n 口= 。 规则a 号b 在交易数据集d e e 成立，且具有s 支持度和c 信任度。这也就意味着交 易数据集d 中有s 比例的交易t 包含数据项：且交易数据集d 中有c 比例的交易t 满足 “若包含a 就包含b 条件”。具体描述就是： s u p p o r t ( a 二= b ) = p t a ub ) c o n f i d e n c e ( aj 口) = p ( b 爿) 满足最小支持度阈值和最小信任度阈值的关联规则就称为强规则( s t r o n g ) ( 频 繁规则) 。( 文献7 ) 最著名的关联规则挖掘算法是a p r i o r i 算法。其算法的核心思想是“个频 繁项集，它的任意子集必定也是频繁的”。据此，a p r i o r i 算法首先挖掘出长度为 一的( 仅包含一个字段) 的频繁项集l l ，根据l 1 的元素两两组合生成候选的长度 为2 的候选频繁集合c 2 继而从c 2 里面遴选出长度为2 的频繁项集l 2 ，再由l 2 基于p r e f i x s p a n 算法的汁算机入侵榆测研究 自连接得到c 3 ，再从c 3 中遴选l 3 ，继续这个过程一直挖掘到规定长度的频繁集。 文献9 中给出了a p r i o r i 算法伪代码： 丛岱亟： 嘞：c a n d i d a t e it e m s e to fs i z ek c 黔j 2 c a n d i d a t e sg e n e r a t e df r o m l k ； m rc n c 1t r a n s a c t i o n ri nd a t a b a s ed o 1 n c r e m e n t h e c o u n to fa l l c a n d i d a t e s i n 嘞手 t h a ta r ec o n t a i n e di n t l k + l 5 c a n d i d a t e si n c k 十，w i t hm i n s u p p o r t u r i t j r c tu ir 1 u 丘l k ； a p r i o r i 的瓶颈：一 巨大的候选集： 1 0 4 个频繁l 一项集要生成1 0 7 个候选2 一项集 要找尺寸为1 0 0 的频繁模式，如 a 1 ，8 2 ，8 l o o ，你必 须先产生2 1 0 0m1 0 3 0 个候选集 多次扫描数据库： 如果最长的模式是n 的话，则需要( n + ，) 次数据库扫描 基于上述的这些缺点，文献9 中介绍了改进的f t t r e e 算法。 用f l e q u e n t - p ；t tt e r n tr e e (