（计算机软件与理论专业论文）网络入侵检测中模式匹配算法的研究.pdf

山东大学硕士学位论文 中文摘要 入侵检测系统是在传统的安全策略无法满足日益苛刻的安全需求的情形下 产生的，它的出现给计算机安全领域的研究带来了新的活力随着网络技术以令 人难以置信的速度向前发展，大型网络以及千兆以太网的出现，使目前的网络入 侵检测系统很难跟上网络快速发展的步伐，传统的入侵检测方法面临严峻挑战 入侵检测技术是一种主动保护自己免受攻击的网络安全技术，是继防火墙、 数据加密等传统安全保护措施后新一代的安全保障技术，作为防火墙的合理补充， 入侵检测技术能够帮助系统对付网络攻击，扩展系统管理员的安全管理能力，提 高信息安全基础结构的完整性 模式匹配算法是基于特征匹配的入侵检测系统中的核心算法，是当前入侵检 测设备中普遍应用的算法模式匹配的效率决定了入侵检测系统的性能 本文对入侵检测系统中的模式匹配算法进行了研究，包括朴素的模式匹配算 法、脚p 算法、蹦算法等单模式匹配算法以及a c 算法、a c b m 算法等多模式匹 配，并对各种算法的性能进行了分析，提出了对a c - b m 算法的改进算法，并通过实 验证明了改进算法的优越性 最后，本文分析了入侵检测面临的问题，展望了入侵检测系统的发展远景 关键词：网络安全：网络入侵检测系：模式匹配：b m 算法；a c b m 算法， 山东大学硕士学位论文 a b s t r a c t 砀et e c h n o l o g yo fi n t r u s i o nd e t e c t i o ni s p r e s e n t e du n d e rt h es i t u a t i o nt h a t t r a d i t i o n a l s e c u r i t ys t r a t e g i e sa r ed e m a n d b e c a u s en e t w o r k i si n c a p a b l eo f s a t i s f y i n g e v e ri n c r e a s i n g l yr i g o r o u sd e v e l o p i n gw i t l lu n b e l i e v a b l er a t ea n dn e t w o r kt e c h n o l o g y c h a n g e sq u i c k l y , l a r g e s c a l en e t w o r ka n d10 0 0 m b p se t h e m e ta p p e a r c u r r e n tn i d s ( n e t w o r ki n t r u s i o nd e t e c t i o ns y s t e m ) c a nh a r d l yc a t c hu p 、析t l lt h e s p e e do fn e t w o r k s ot h a tc o n v e n t i o n a ld e t e c t i o nm e t h o df a c et os e r i o u sc h a l l e n g e i n t r u s i o nd e t e c t i o nt e c h n o l o g yi st h a to n ek i n dp r o t e c t so n e s e l ff o r mak i n do f n e t w o r ks a f ep r a c t i c ea t t a c k e dv o l u n t a r i l y , c o n t i n u et h es e c u r i t yt e c h n o l o g yo fn e w g e n e r a t i o na f t e rt h et r a d i t i o n a ls a f ep r o t e c t i v em e a s u r e ，s u c h 嬲f i r ew a l l ，t h ed a t a e n c r y p t e de t c a sr a t i o n a ls u p p l e m e n to ff i r ew a l l ，i n v a d ed e t e c t i o nt e c h n i q u ec a nh e l p t h es y s t e mt od e a lw i t ha t t a c ko fn e t w o r k , e x p a n ds e c u r i t ym a n a g e r i a la b i l i t yo f s y s t e mm a n a g e r , r a i s et h ei n t e g r a l i t yo ft h es a f ei n f r a s t r u c t u r eo ft h ei n f o r m a t i o n p a t t e mm a t c h i n ga l g o r i t h mi sc e n t r a la l g o r i t h mi n s i g n a t u r eb a s e di n t r u s i o n d e t e c t i o ns y s t e m p e r f o r m a n c eo ft h i si n t r u s i o nd e t e e t i ns y s t e mi sd o m i n a t e db y p a t t e mm a t c h i n ga l g o r i t h mu s e d t l l i sd i s s e r t a t i o n s u r v e yt h ep a t t e r nm a t c h i n ga l g o r i t h ms u c ha st h es i m p l e a l g o r i t h m ，k m pa l g o r i t h m ，b ma l g o r i t h ms i n g l ea l g o r i t h m ，a ca l g o r i t h m ，a c - b m a l g o r i t h mm u l t i p a t t e r nm a t c h i n ga l g o r i t h ma n da n a l y s et h ep e r f o r m a n c eo f t h e m a t l a s t ，w ep r o v i d es o m ei m p r o v e m e n tf o rt h e s ea l g o r i t h m s a tl a s t ，t h i sd i s s e r t a t i o na n a l y s e ss o m ep r o b l e m si n t r u s i o nd e t e c t i o nt e c h n i c a l m u s tf a c ea n dd i s c u s s e se x p e c t a t i o no f n i d si nf u t u r e u k e y w o r d s ：n e t w o r ks e c u r i t y ；n e t w o r ki n t r u s i o nd e t e c t i o n s y s t e m ( n i d s ) ；p a t t e r n m a t c h i n g ；b ma l g o r i t h m ；a c b ma l g o r i t h m 山东大学硕士学位论文 i i 符号说明 v p n ：v i r t u a l ：p r i v a t en e t w o r k虚拟专用网 d a r p a ：t h eu sd e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y 美国国防部高级研究计划局 i d s ：i n t r u s i o 撵d e t e c t i o ns y s t e入侵检测系统 n i d s ：n e ti n t r u s i o nd e t e c t i o ns y s t e m 网络入侵检测系统 d d o s ：d i s t r i b u t e dd e n i a lo fs e r v i c e分布式拒绝服务 b p ：b a c kp r o p a g a t i o n神经网络 k d d ：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 数据库中的知识发现数据挖掘 d f a ：d e t e r m i n i s mf i n i t ea u t o m a t e确定型有穷自动机 i i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：f 銎丝兰垒 日期：竺至：兰：坚 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件 和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：2 至丝垫导师签名： 山东大学硕士学位论文 研究背景及现状 t 研究背景 第一章引言 随着计算机、网络和通信技术的发展，人类社会进入了信息时代政府、企业 和个人既是网络资源的提供者也是网络资源的消费者人们在享受网络提供的巨 大便利的同时，也承受着由网络安全问题带来的新的威胁 网络系统的安全威胁主要表现在主机可能会受到非法入侵者的攻击，网络中 的敏感数据有可能泄露或被修改，从内部网向公共网传送的信息可能被窃听或篡 改等等 于企业内部网来说，入侵的来源可能是多种多样的，它可以是企业内部心怀不 满的员工、网络黑客，甚至是竞争对手攻击者可能窃听敏感信息，窃取用户的口 令、数据库的信息，篡改数据库的内容，伪造用户身份，否认自己的签名，甚至删除 数据库的内容，破坏网络的节点，释放计算机病毒，导致整个企业网络陷入瘫痪 因此，能否成功阻止网络黑客的入侵、保证计算机和网络系统的安全和正常运行 便成为网络安全领域所面临的一个重要问题 面对如此严峻的网络安全形势，对网络、系统的安全保护却越来越困难，这是 因为：一、网络的结构随着网络的迅速发展而变得越来越复杂：二、网络中众多的 “黑客 站点不仅提供了大量的系统缺陷信息及攻击方法，而且还提供了大量易 于使用的系统漏洞扫描和攻击工具，攻击者不需要具备大量的专业系统知识就可 以利用相应的入侵工具攻入具有安全缺陷的系统：三、目前的系统攻击不仅是年 轻的。“黑客 们由于好奇而侵入系统的玩笑性游戏，入侵者的背后甚至得到一些 拥有足够系统资源、专业知识和入侵经验的犯罪组织、竞争对手甚至是敌对国家 的支持 1 9 7 2 年a n d e r s o n 提出了计算机安全模型，该模型的实现通常采用访问控制机 制来保证系统安全访问控制机制是计算机系统首先识别与认证主体身份，然后 根据授权数据库的记录判断是否允许主体访问对象但通过访问控制机制来实现 山东大学硕士学位论文 安全目标最终仍依赖于主体，这就无法防止由系统所认定的授权用户由于非法操 作而引起的破坏安全的行为的发生，对于合法用户的滥用特权、口令或密钥的泄 漏、系统自身漏洞、应用软件的缺陷以及拒绝服务攻击更是无能为力 加密技术的运用在一定程度上为安全提供了一定的保障，但是，一旦该技术 被突破，安全也就无从谈起 随后发展起来的防火墙技术通常采用的是包过滤技术、应用层网关、安全 i p 通道或虚拟专用网( v p n ) 中种或几种这些技术的运用防止了许多常见的协 议实现漏洞、源路由、地址欺骗等多种攻击手段以及提供了安全的数据通道，但 它不能解决层出不穷的应用层后门、应用程序设计缺陷、通过加密通道的攻击等 问题而且，不是所有的对i n t e r n e t 的访问都要经过防火墙，而防火墙本身也易 受攻击 上述安全技术都属于静态的安全防御技术，其技术运用都集中在系统自身的 加固和防护上，而对于网络环境下日新月异的攻击手段缺乏主动的反应针对日 益严重的网络安全问题和越来越突出的安全需求，动态安全模型n 1 应运而生 入侵检测n 瞄钉作为动态安全技术的最核心技术之一，是防火墙的合理补充， 帮助系统对付网络攻击，扩展系统管理员的安全管理能力( 包括安全审计、监视、 进攻识别和响应) ，提高信息安全基础结构的完整性，是安全防御体系的一个重要 组成部分 入侵检测系统是一个典型的数据处理系统它通过对大量的系统审计数据进 行分析，来判断被监控的系统是否遭受到了入侵行为的攻击具体到系统的检测 机制，其实就是一个系统丰体行为( 或事件) 的分类系统，它需要把对系统具有恶 意的行为从大量的系统行为中区分出来而解决这样的问题，就必须依靠高效的 入侵检测算法 1 1 2 研究现状 入侵检测的研究最早可追溯到j a m e sp a n d e r s o n 在1 9 8 0 年4 月为美国空 军做的一份题为“计算机安全威胁监控与监视 ( c o m p u t e rs e c u r i t yt h r e a t m o n i t o r i n ga n ds u r v e i l l a n c e ) 的技术报告，这份报告被公认为是入侵检测的 开山之作在报告中，他首次提出了入侵检测的概念，将入侵尝试( i n t r u s i o n 2 山东大学硕士学位论文 a t t e m p t ) 或威胁( t h r e a t ) 定义为：潜在的有预谋未经授权访问信息、操作信息、 致使系统不可靠或无法使用的企图最早资助入侵检测研究的是美国国防部高级 研究计划局( d a r p a ) 早期的研究只是一种试验阶段，产品的针对性强，即为了保 护专门的网络而进行研究设计的而且系统大多以基于主机的入侵检测系统为主 进入九十年代，随着基于网络盼入侵检测系统的阎世，给入侵检测研究注入了新 的活力很多的网络公司开始开发商业化的产品对于入侵检瓣的研究已经进入 高涨阶段，其它领域的一些算法，如：人工智能、数据挖掘、免疫学、信息论测度 等逐渐被引入入侵检测领域 实现网络与信息的安全是一项系统工程，不是哪一种单独的安全部件就可以 完成的只有在不同的安全部件之间实现互联互动，才能够更好地发挥它们各自 的作用，才可以比较好地保证网络与信息的安全随着防火墙、入侵检测等技术的 不断发展，实现它们之间的互动显得越来越重要应该考虑不同厂家的入侵检测 系统之间，入侵检测系统和防火墙之间，入侵检测系统与响应部件之间的互动在 这方面，需要解决的问题是入侵检测系统的标准化工作 标准化工作对于一项技术的发展至关重要在某一个技术领域，如果没有相 应的标准，那么该领域的发展将会是无序的令人遗憾的是，尽管入侵检测系统经 历了2 0 多年的发展，近几年又成为网络与信息安全领域的一个研究热点，但到目 前为止，尚没有一个相关的国际标准出现，国内也没有入侵检测系统方面的标准 因此，入侵检测系统的标准化工作应引起业界的广泛重视目前，国际上有两个组 织在做这方面的工作，它们是公共入侵检测框架工作组( c i d f ) 和入侵检测工作小 组( i d w g ) c i d f 早期由美国国防部高级研究计划局( d a r p a ) 赞助研究，现在由 c i d f 工作组负责，这是一个开放组织i d w g 是互联网工程任务组( i e t f ) 下的一个 工作小组，专门研究制定入侵检测领域的草案( 标准) ，它的工作目标是定义入侵 检测系统中的数据格式、信息交换过程和交换协议i d w g 在不断修改其提出的草 案，力争使其成为入侵检测系统的国际标准 在入侵检测系统中，应该进行标准化的工作主要包括：大规模分布式入侵检 测系统的体系结构、入侵特征等数据的描述( 格式) 、入侵检测系统内部的通信协 议和数据交换协议、安全部件间的互动协议和接口标准等 目前，国外比较流行的入侵检测系统有：美国c i s c o 公司的 n e t r a n g e r ，n e t w o r ks e c u r i t yw i z a r d s ( n s w 公司的d r a g o n ，s o u r c e f i r e 的s n o r t ， 山东大学硕士学位论文 n a i 公司的c y b e r c o pn e t w o r k ，a x e n t 公司的i t a 和n e t p r o w l e r ，n f r 公司的 i n t r u si o nd e t e c ti o n a p p ll a n c e 4 0 ，c e n t r a x 2 2 等 在国内，随着计算机网络及相关产业的高速发展，对入侵检测的研究也受到 各方面的关注，一些网络安全公司也相继推出自己的入侵检测产品，安氏领信的 l i n k t r u s t 系列入侵检测系统采用了专用硬件承载平台设计、复杂协议分析和模 式匹配的融合技术、多层分布式体系结构设计、完全远程升级技术、数据相关性 分析技术等技术和设计启明星辰公司的天闻系列入侵检测系统能够实时监控网 络传输，自动检测可疑行为，及时发现来自网络外部或内部的攻击，并可以实时响 应，切断攻击方的连接中联绿盟信息技术有限公司的冰之眼系列入侵检测产品 覆盖广泛的攻击特征库，具有i p 碎片重组与t c p 流汇聚、协议分析，协议识别、 攻击结果判定等功能国家对入侵检测系统研究的投入也在加大，早在“九五 末期就紧急启动了“8 6 3 计划信息安全应急计划，“十五 期间科技部又在 “9 7 3 计划”、“8 6 3 计划 、“国家科技攻关计划和“国家科技创新基金计 划 中对信息安全的技术研究和开发进行了全面部署 1 2 传统计算机安全 1 2 1 传统计算机安全的技术 传统的计算机安全技术包括漏洞扫描系统、数据加密技术、访问控制技术和 识别验证技术、日志审计、防火墙技术等嫡1 1 2 1 1 漏洞扫描系统 由于计算机系统开发过程中存在的错误、缺陷和遗漏，用户和系统管理的工 作参数设置不当。系统始终存在脆弱性系统中脆弱性的存在是系统受到各种安 全威胁的根源系统管理员的主要工作之一就是找出系统的安全漏洞，如果人工 测试安全漏洞要不断的开发、编译、运行测试程序，既慢又易出错而使用安全漏 洞扫描程序就可以解决上述问题，减少管理员的工作强度扫描程序实际上是利 用已知攻击方法对目标主机进行攻击，从而判断目标主机是否存在相应的安全漏 洞扫描器也可能被黑客利用，用来做攻击前的准备，检查目标系统是否含有己知 4 山东大学硕士学位论文 的漏洞 1 2 1 2 数据加密技术 数据加密技术的作用丰要是提高了网络系统环境中数据存储和传输过程中 的安全保密性通过对数据进行加密，可以防止重要数据被外部人员窃取和破坏 根据密钥可以将数据加密技术分为两类：对称钥加密和非对称钥加密对称钥加 密又称为秘密钥加密，加密和解密过程使用相同的密钥非对称钥加密也可以称 为公开钥加密，它一般有两个密钥，一个用于加密而另一个用于解密数据加密技 术的安全性是基于算法和密钥的嘲 1 2 1 3 访问控制技术 在计算机系统中，安全机制的核心是访问控制访问控制技术按照事先确定 的规则决定主体对客体的访问是否合法它要确定合法用户对哪些系统资源享有 何种权限、可进行什么类型的访问操作，防止非法用户进入计算机系统和合法用 户非法使用系统资源当一个主体试图非法使用一个未经授权使用的客体时，访 问控制将拒绝这一企图，并向审计跟踪系统报告若系统具有安全控制策略和保 护机制，便可将非法入侵者拒之门外：否则，非法入侵者便可攻破设防获取资源 访问控制是维护系统运行安全、保护系统资源的重要技术手段访问控制技术的 实现一般有4 种策略：程序权限限制、用户权限限制、文件属性限制和留痕技术 1 2 1 4 认证技术 认证就是将特定实体从任意实体的集合中识别出来的行为它以交换信息的 方式来确认实体的身份它是进行存取控制必不可少的条件，如果不知道用户的 身份，就无法判断用户的存取是否合法用于认证的技术：生物特征技术、口令技 术、安全协议技术和密码技术等 1 2 1 5 日志审计 系统管理员可以通过查看、分析系统日志信息可以发现入侵行为即使再高 明的黑客入侵后也会留下一些蛛丝马迹因此，日志审计是很好的离线安全分析 山东大学硕士学位论文 工具 1 2 1 6 防火墙技术 防火墙是指安装在内部网络与外部网络之间或者网络与网络之间的可以限 制相互访问的一种安全保护措施来自i n t e r n e t 和发往i n t e r n e t 的所有信息都 必须经由防火墙，而防火墙只允许被授权的信息通过防火墙技术的核心思想是 在不安全的网络环境下构造一种相对安全的内部网络环境也就是说，防火墙技 术用以在开放的网络环境中构造一个相对封闭的逻辑网络环境来满足人们对内 部网络的安全要求防火墙的实现技术主要有：数据包过滤、应用网关和代理服务 等防火墙技术比较适合于内部网络相对独立，且与外部网络的互联途径有限、网 络服务种类相对比较集中的网络防火墙是一种比较被动的网络安全技术，对于 内部未受权的访问难以有效的进行控制 6 1 1 2 2 传统安全模型的局限性 a n d e r s o n 在1 9 7 2 年提出了计算机安全模型( 图1 1 ) ，该模型的实现通常采用 访问控制机制来保证系统安全访问控制机制识别与认证主体身份，根据授权数 据库的记录决定是否可以允许主体访问对象这些方法为保证机密性与一致性对 系统的限制太死，系统很复杂、效率极低、灵活性差，没有太大的实用价值口1 图1 1 传统安全参考模型 1 9 8 5 年美国国防部( d o d ) 国家计算机安全中心( n c s c ) 发布的可信计算机安全 评估准则( i c s e c ) 是信息安全发展史上的一个里程碑这个准则的发布对操作系 统、数据库等方面的安全发展起到了很大的推动作用阳1 但是随着网络的深入发展，主要基于主机环境的静态安全模型和标准i c s e c 6 山东大学硕士学位论文 己经不能完全适应当前的技术需要，无法完全反应分布式、动态变化、发展迅速 的i n t e r n e t 安全问题 传统的信息安全技术都集中在系统自身的加固和防护上比如，采用b 级操 作系统和数据库、在网络出口配置防火墙、在信息传输和存储中采用加密技术、 使用集中的身份认证产品等然丽，单纯的防护技术存在许多不足 首先，单纯的防护技术容易导致系统的盲目建设，这种盲目包括两方面： 一方面是不了解安全威胁的严峻和当前的安全现状：另一方面是安全投入过 大而又没有真正抓住安全的关键环节，导致不必要的浪费： 其次，防火墙策略对于防范黑客攻击有其明显的局限性防火墙技术是内部 网络最重要的安全技术之一，其主要功能就是控制对受保护网络的非法访问，它 通过监视、限制、更改通过网络的数据流，一方面尽可能屏蔽内部网络的拓扑结 构，另一方面对内屏蔽外部危险站点，用以防范外对内、内对外的非法访问但也 有其明显的局限性嘲 防火墙难于防范内部网络防火墙的安全控制只能作用于外对内或内对外， 即对外可屏蔽内部网络的拓扑结构，封锁外部网络上的用户连接内部网络上的重 要站点或某些端口，对内可屏蔽外部危险站点，但它很难解决内部网络控制内部 人员的安全问题 防火墙难于管理和配置，易造成安全漏洞防火墙的管理及配置相当复杂，要 想成功的维护防火墙，要求防火墙管理员对网络安全攻击的手段及其与系统配置 的关系有相当深入的了解防火墙的安全策略无法进行集中管理一般来说，由多 个系统( 路由器、过滤器、代理服务器、网关) 组成的防火墙，管理上有所疏忽是 在所难免的根据美国财经杂志统计资料表明，3 0 的入侵发生在有防火墙的情况 下 防火墙的安全控制主要是基于i p 地址的，难于为用户在防火墙内外提供一 致的安全策略许多防火墙对用户的安全控制主要是基于甩户所用机器的i p 地 址而不是用户身份，这样就很难为同用户在防火墙内外提供一致的安全控制策 略，限制了企业网络的物理范压 防火墙只实现了较粗的访问控制且不能与企业内部使用的其它安全机制( 如 访问控制) 集成使用，这样，企业就必须为内部的身份验证和访问控制管理维护单 独的数据库 7 山东大学硕士学位论文 曼皇量皇皇曼曼量曼鼍量喜皇量曼皇曼曼曼量鼍曼置量量曼曼皇曼鲁曼量曼量皇鼍曼皇曼皇曼曼曼暑曼曼曼鼍曼量皇鼍量皇量舅舅暮d 一 i 鼍 再次，保证信息系统安全的经典手段是存取控制或访问控制，这种手段在经 典的以及现代的安全理论中都是实行系统安全策略的最重要的手段但迄今为止， 软件工程技术还没有达到a 2 级所要求的形式生成或证明一个系统的安全体系的 程度，所以不可能百分之百地保证任何一个系统( 尤其是底层系统) 中不存在安全 漏洞而且，无论在理论上还是在实践中，试图彻底填补一个系统的安全漏洞都是 不可能的，也还没有一种切实可行的办法解决合法用户在通过身份鉴别或身份认 证后滥用特权的问题另外访问控制机制的最终安全依赖于实体，也就是最终用 户需要保证它所访问对象的安全它无法防止隐蔽信息的产生以及系统所认定的 授权用户非法操作对于来自内部的非法操作、口令的泄露，软件中的缺陷以及拒 绝服务攻击更是无能为力n 町 1 3 本文内容简介 基于网络的入侵检测系统：n i d s ( 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 n s y s t e m ) 作为入侵检测系统的一种，正成为网络安全解决方案中的一个重要组成 部分，发挥着越来越大的作用目前的网络入侵检测产品大多采用单数据包模式 匹配检测方法，如何提高这种方法在处理大规模模式集时的检测效率和整体性能 已经成为研究的焦点为此，需要对现有的网络入侵检测产品和技术进行深入分 析与改进，尤其是对模式匹配算法进行深入分析和改进，设计出高效、安全的入侵 检测系统模型，进一步提高网络入侵检测的应用价值，为入侵检测领域的研究开 辟广阔的发展空间本文正是围绕这一目的展开研究的 具体工作如下： ( 1 ) 对网络安全技术的背景进行了研究和总结 ( 2 ) 研究了入侵检测技术的发展历史，对该领域国内外的研究现状进行了总 结 ( 3 ) 研究了入侵检测的定义、入侵检测系统的体系结构、分类模型等方面的 内容 ( 4 ) 本文重点研究了目前大多数i d s 所采用的模式匹配检测方法深入分析了 经典的模式匹配算法以及模式匹配在网络入侵检测系统中的运用，包括单模式的 阴算法和多模式的a c 算法和a c b m 算法 8 山东大学硕士掌位论文 ( 5 ) 结合单模式的蹦算法在匹配中的跳跃原理，以及a c 算法的匹配自动机原 理，提出了一种改进的a c 一酬模式匹配算法该算法一次可以匹配多个模式，并且 在匹配过程产生较大的跳跃，可以很快地进行模式匹配 ( 6 ) 从时间复杂度和空间复杂度讨论了b m 算法、a c 算法、a c 一8 m 算法和改进 的a c 一蹦算法这四种算法的性能在实时的网络入侵检测中，检测时间是主要考 虑因素，而改进的a c 一酬算法有较好的时间复杂度，字符平均比较次数较少，有一 定的实用价值 9 山东大学硕士学位论文 第二章入侵检测系统概述 2 1 入侵检测系统概念 入侵( i n t r u s i o n ) n 1 1 ，是指任何试图危及计算机资源的完整性、机密性或可用 性的行为s m a h a 从策略角度将入侵分为尝试性闯入( a t t e m p t e db r e a k - i n ) 、伪 装攻击( m a s q u e r a d ea t t a c k ) 、安全控制系统渗透( p e n e t r a ti o no ft h es e c u r it y c o n t r o ls y s t e m ) 、泄漏( l e a k a g e ) 、拒绝服务( d e n i a lo fs e r v i c e ) 和恶意使用 ( m a li c i o u su s e ) 等6 种类型n 船 入侵检测( i n t r u s i o nd e t e c t i o n ) l i f t ) 是对入侵行为的发觉，它通过从计算机 网络或系统中的若干关键点收集信息，并对这些信息进行分析，从而发现网络或 系统中是否有违反安全策略的行为和遭到攻击的迹象实现入侵检测功能的软件 与硬件的组合就是入侵检测系统( 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 ) 入侵检测作为传统计算机安全机制的补充，它的开发与应用扩大了网络与系 统安全的保护纵深，成为目前动态安全工具的主要研究和开发的方向随着系统 漏洞不断被发现，攻击不断发生，入侵检测系统在整个安全系统中的地位不断提 高，所发挥的作用也越来越大 2 2 入侵的常见方式 入侵攻击的常见方式有： ( 1 ) 利用系统的内部缺陷在网络运行的许多协议中，有一些协议存在着安全 漏洞如i c m p ( i n t e r n e tc o n t r o lm e s s a g ep r o t o c 0 1 ) ，这种协议很容易被拒绝 服务攻击所利用i m a p ( i n t e r n e tm e s s a g ea c c e s sp r o t o c 0 1 ) 是网络上的另一种 常见协议，攻击者能够通过i m a p 和p o p 3 取得u n i x 系统下的根目录权限，攻击者 就可操纵系统在根目录下执行各种命令，获取敏感信息和超级用户的权限t c pl i p 协议也可以被拒绝服务攻击所利用典型的d d o s 攻击主要是消耗系统的一种 或多项资源，如c p u 、内存或磁盘空间等其中最出名的是s y nf l o o d 服务，攻击 者发出大量非法请求要求建立连接，建成大量空连接，系统处于长久的等待状态， l o 山东大学硕士学位论文 占羼系统大量资源，合法的服务请求因超时而断开连接，使系统不能晦应合法的 服务请袭 ( 2 ) 缓冲区溢出这是对系统安全危害较大的攻毒手段在许多系统中，应用 程序和缓冲区都不检查数据的特性，它允许接收任意长度的数据，这可能造成系 统的堆栈或缓冲区溢出，造成系统的状态不稳定，攻击者可以通过合适的配置，取 得系统的权限 ( 3 ) 利用系统管理工具和系统配置的漏洞尤其是u n i x 系统，它的配置比较 复杂，漏洞也容易产生，如目录t 文件的访问权限设置不严格，有可能引起用户或 黑客的非法访问，而黑客有时以合法用户的名义访问系统 ( 4 ) 利用无效的体系设计和检测能力网络体系结构的安全漏洞有时是致命 的，内部网络通过路由器，防火墙与外部i n t e r n e t 相连，路由器，防火墙的精心配 置可以有效地控制内外网络的相互访问然而网络设备连接上的漏洞有可能使有 关过滤规则等访问控制被屏蔽许多系统中没有对安全管理和安全措施提出明确 的要求，这使管理员无法利用系统设备对安全进行维护有效的管理应该扩充到 系统代码的设计与实现上，一些系统的c g i 程序有安全漏洞，这可导致系统会受 到d d o s 攻击或非授权访问敏感信息n 羽 2 3 入侵检测分类 入侵检测系统根据不同的分类标准可以分为不同的类型常见的分类形式主 要有以下几种： ( 1 ) 从入侵检测的分析方法上分，通常可分为误用检测( m i s u s ed e t e c t i o n ) 和异常检测( a n o m a l yd e t e c t i o n ) 两种当然，现在也出现了一些既不属于误用检 测也不属于异常检测范围的新方法，如分类检测、免疫系统方法、遗传算法和数 据挖掘等 误用检测是先定义违背安全策略的事件的特征，再根据攻击特征建立规则库， 将待检测数据与攻击规则匹配，如果与规则符合则认为是入侵行为这种检测方 法因只能检测已知攻击，对未知攻击无法检测自然查全率比较低，但查准率就相 对高常用的误用检测技术有专家系统、条件概率、状态转移分析和有色p e t r i 网 1 4 1 等 山东大学硕士学位论文 异常检测是先假设入侵活动异常于正常的主体活动n 州蚓，建立主体正常活动 的“行为模型”，通过识别任何违反“行为模型 的活动检测入侵这种检测方法 必须对用户的正常行为模型建立一系列阀值，阀值集的完备程度决定着异常行为 的范围，故可检测未知攻击，查全率高，但查准率较低，误报率较高常用的异常检 测技术有统计分析、量化分析、神经网络、模式预测等 当前，出现了很多将其他科学理论成果运用到入侵检测领域的新型检测技术 比较受关泣的有基于免疫系统n 力( i m m u n es y s t e m ) 和遗传算法n 羽( g e n e t i c a l g o r i t h m ) 的检测技术此外，数据挖掘n 钔( d a t am i n i n g ) 和数据融合( d a t a f u s i o n ) 也在入侵检测领域得到了广泛研究 ( 2 ) 从入侵检测的数据来源上分，通常可分为基于主机( h o s t b a s e d ) 的入侵 检测和基于网络( n e t w o r k b a s e d ) 的入侵检测两类晗当然，也出现了把主机数据 源和网络数据包结合起来的系统，有人根据此种数据来源混合的方式，称此类系 统为“混合型 ( h y b r i d ) 入侵检测陇1 基于主机的入侵检测的数据源来自主机的审计数据和系统日志，其目标是保 护主机系统和系统本地用户不受入侵攻击这种i d s 通常运行在被保护的主机或 服务器上，实时检测主机诸如操作系统日志文件、审计日志文件、应用程序日志 文件等方面的安全情况，其效果依赖于审计数据、系统日志的准确性、完整性以 及安全事件的定义 基于主机的入侵检测具有检测效率高、分析代价小、分析速度较快、配置灵 活等特点，能够较准确地判断攻击，并定位入侵者，还可以结合操作系统和应用程 序的行为特征对入侵进行分析、响应，也不受加密和交换环境的影响早期的入侵 检测系统大多采用这种体系结构，如图2 1 所示 1 2 图2 1 基于主机的入侵检测系统结构 山东大学硕士学位论文 但这种检测系统存在明显的不足首先，它在一定程度上依赖于系统的可靠 性，它要求i d s 本身应该具备基本的安全功能并具有合理的设置，然后才能检测 到入侵信息其次，即使有了正确的安全配置，对操作系统熟悉的攻击者仍然有可 能在入侵行为完成后及时修改系统日志而躲过检测第三，通过主机的系统日志 能够提供的信息有限，有的入侵于段和方法不会在日志中反映出来，尤其是通过 网络协议发起的入侵行为系统日志更是无能为力此外，基于主机的入侵检测往 往依赖主机操作系统，可移植性差，对主机的运行性能也有一定影响 基于网络的入侵检测的数据源来自网络上的数据包，它通常能够实时监控网 络中的数据流量，通过协议分析、特征匹配和统计分析等手段发现潜在的或正在 发生的攻击行为基于网络的入侵检测通常安装在被保护的网络区域中的重要网 段内，采用嗅包技术从网络接口中获取数据信息，有较强的数据获取、分析能力， 在实时性、可靠性方面优于基于主机的入侵检测系统其体系结构如图2 2 所示 磁 图2 2 基于网络的入侵检测系统结构 基于网络的入侵检测重在网络数据分析，往往采用单独主机或被动监听工作 模式，对网络中的主机或服务器影响不大，也不依赖于操作系统，可移植性较好 而网络数据的获取是基于网络的入侵检测的基础，这种截获技术有两种方法实现 传统的方法是利用网络的广播特性，将网卡的工作模式设为混杂( p r o m i s c u o u s ) 模式，以便能够接收目标主机非本主机的所有数据包，可以直接访问数据链路层， 这样就能获取流经网卡的所有数据但在实际的交换网络环境下，常用的方法是 利用交换机或路由器上的监听端口或镜像端口来获取数据，也可直接选择流量最 大的上下行端口来获取数据但是，不论哪种方法都存在如果监视的数据量过于 庞大时就会出现漏包的问题，而且如果网络数据被加密时，这种检测系统就不能 山东大学硕士学位论文 扫描到协议内容 另外，网络入侵检测还有一种比较特殊的情况，那就是基于网络结点的入侵 检测这种方式的检测数据来源于被检测主机的网络流量，优点在于可以减轻系 统因处理大量网络数据产生的压力，而将待检测的数据量分散在网络中的多个结 点上 混合型入侵检测此处是指的是被检测的数据源既包括主机信息又有来自网 络的数据包，甚至还可以考虑其他安全产品如防火墙等的数据信息或人工方式提 供的各类外来数据信息这类系统可以控制整个目标网络的总体安全状况，一方 面通过主机信息能够了解主机系统的活动情况，监控对文件系统的操作、系统调 用情况、用户命令、用户登录注销及应用程序的运行情况等：另一方面，检测来 自网络的数据信息可以发现通过网络协议发动的入侵行为，如碎片攻击、s y n f l o o d 拒绝服务攻击等其结构如图2 3 所示 图2 3 混合型入侵检测系统结构 混合型入侵检测的优点在于可以满足被检测目标的多种需求，有利于提高被 检测目标的安全性能从混合型入侵检测的技术思想看，这种方法丰要体现了分 布式检测的思路，可以同时发挥基于主机和基于网络的两种检测技术的优势对 包括主机信息、网络数据包以及其他安全产品数据等多种数据源进行综合处理， 能更好地提高入侵检测的准确性，改善入侵检测系统性能 ( 3 ) 从入侵检测的响应方式上分，通常可分为主动响应的入侵检测和被动响 1 4 山东大学硕士学位论文 应的入侵检测两类 被动响应的入侵检测系统在检测到入侵行为时，只发出报警，通知系统管理 员有不正常的情况出现，引起注意，并产生告警报告，但本身不会主动地对攻击者 采取任何行动，也不会试图降低所造成的危害 主动响应的入侵检测系统则在遭受入侵行为时，采取一定的行为手段来反击， 以尽量减少被造成的破坏这种响应方式又可分为对被攻击系统实施控制的系统 和对攻击系统实施控制的系统两种对被攻击系统实施控制主要是通过调整被攻 击系统的状态，达到阻止或减轻攻击影响危害的目的，如断开网络连接、增加安全 日志和杀死可疑进程等而实现对攻击系统的控制相对困难，目前比较流行的是 网络诱骗技术即通过消耗攻击者自身资源，增加攻击者的工作量和迷惑攻击者， 使之对错误的蜜罐主机展开攻击等方法实现对攻击系统进行控制，造成威胁和损 害的目的 ( 4 ) 从入侵检测的运行方式上分，通常可分为集中式、等级式和协作式三类 集中式入侵检测是最早出现的入侵检测系统，它只有一个中央检测服务器， 但可以有多个分布于不同主机上的审计程序，审计程序把收集到的数据信息发送 到中央服务器进行分析处理这种结构系统设计相对简单，但可伸缩性、可配置性 方面存在缺点特别是随着网络规模的增加，主机审计程序和服务器之间传送的 数据量骤增，导致网络性能大大降低，一旦中央服务器出现故障或受到攻击，整个 系统就会陷入瘫痪并且，这类系统需要根据各个不同的主机需求配置服务器，非 常复杂 等级式入侵检测也叫部分分布式入侵检测，它定义了若干个分等级的监控区 域，每个入侵检测引擎负责一个区域，每一级检测只负责所在监控区的数据分析， 然后将本地的分析结果传送给上一级检测系统这种入侵检测结构也存在一些问 题，如当网络拓扑结构发生变化时，区域分析结果的汇总机制就需要做相应的调 整：而且，这种结构的系统最终还是要把各个区域收集到的结果传送到最高级的 检测服务器进行全局分析，容易导致时效性不高，系统的安全性也没有实质性的 改进 协作式入侵检测也叫完全分布式入侵检测，它是将中央检测服务器的任务分 配给多个基于主机的入侵检测引擎，这些检测引擎不分等级，各司其职，负责本地 主机的某些活动这种结构的检测系统可伸缩性强，安全性也得到了显著提高这 山东大学硕士学位论文 种系统存在的问题是维护相对困难，设计成本也高了许多，而且增加了所监控主 机的工作负荷 ( 5 ) 从入侵检测的同步技术上分，通常可分为实时连续性入侵检测和间隔时 延入侵检测两类这是根据系统监控到事件和对事件进行分析处理之间的时间间 隔进行划分的，实时连续性入侵检测系统是以实时或接近实时的方式持续地监控 从信息源检测的信息：而间隔时延入侵检测系统则是在收集到信息之后要隔一定 的时间间隔才对数据进行批处理 ( 6 ) 从入侵检测的时效性上分，通常可分为脱机分析的入侵检测和联机分析 的入侵检测两类脱机分析是指入侵行为发生后：才对产生的数据进行分析，而联 机分析则是指在数据产生的同时或发生入侵行为时即对数据进行分析检测 2 4 入侵检测算法 目前，入侵检测系统采用的算法有： 2 4 1 模式匹配 模式匹配检查对照一系列己有的攻击，比较用户活动，将收集到的信息与己 知的网络入侵和系统特征库进行比较，从而发现违背安全策略的入侵行为目前， 模式匹配已经成为入侵检测领域中使用最广泛的检测手段和机制之一，这种想法 的先进之处在于定义己知的问题模式，然后观察能与模式匹配的事件数据独立 的模式可以有独立事件、事件序列、事件临界值或者允许与、或操作的通用规则 表达式组成 基于模式匹配的入侵检测系统是由入侵检测领域的大师k u m a r 提出的晗副，首 先k u m a r 提出了入侵信号的层次性概念根据底层的审计事件，可以从中提取出 高层的事件或活动