高速网络入侵检测系统模式匹配算法研究与实现.pdf

国防科学技术大学 硕士学位论文 高速网络入侵检测系统模式匹配算法的研究与实现 姓名：鲍震 申请学位级别：硕士 专业：计算机技术 指导教师：孙志刚;胡晓峰 20070401 国防科学技术大学研究生院工程硕士学位论文 摘要 随着计算机和网络技术的快速发展以及应用程度的不断提高，计算机网络安 全已成为国家经济发展的关键，同时也是国家与国防安全的重要组成部分。对入 侵和攻击行为的检测与防范，保障计算机系统、网络系统及整个信息基础设施的 安全是一项重要课题。网络入侵检测作为一种积极主动的安全防护技术目前正成 为网络安全领域中研究的热点。由于近年来网络规模以令人难以置信的速度扩张， 网络技术日新月异，特别是随着连接速度的不断提高，目前网络入侵检测系统的 性能很难跟上网络快速发展的步伐，传统入侵检测方法面临严峻挑战。 本论文在对网络安全和入侵检测技术进行深入分析的基础上，指出现有入侵 检测系统存在的主要问题和提高入侵检测性能的重要意义。然后系统介绍和分析 了目前使用最广泛的模式匹配检测方法，对几种典型的单模式和多模式匹配算法 进行了对比分析，针对a cb m 算法存在的不足，提出了新的有更好搜索步长的 多模式匹配算法_ ia cb m 算法，给出了算法执行的伪代码，并对新算法的效 率进行了分析。最后给出新算法在s n o r t 中的实现方案。论文最后对入侵检测系统 的发展趋势进行了分析。 论文的主要工作和贡献包括： 对入侵检测中的模式匹配算法进行详细的分析，指出a cb m 算法的两处 不足。 针对a cb m 算法的不足，提出新的ia cb m 算法，分析证明该算法具 有更好的搜索步长、更好的检测效率。 结合s n o r t 的系统结构，将ia cb m 算法应用于入侵检测系统中，提出设 计方案，给出算法的实现机制。 本文的工作对提高基于模式匹配的入侵检测系统的检测效率、减少误报漏报 和拒绝服务攻击的发生具有重要意义。 主题词：入侵检测，模式匹配，s n o r t 第i 页 国防科学技术大学研究生院工程硕士学位论文 a b s t r a c t w i t l lt h e r a p i dd e v e l o p m e n t o f c o m p u t e r a n dn e t w o r k t e c h n i q u e s ， c o m p u t e r & n e t w o r ks e c u r i t yh a sb e e nt h ek e yt ot h en a t i o n a le c o n o m i cd e v e l o p m e n ta n d a l s oa ni m p o r t a n tp a r to ft h en a t i o n a ld e f e n s es e c u r i t y i ti sa nu r g e n tt a s kt od e t e c ta n d p r e v e n ti n t r u s i o ne v e n t s ，s e c u r et h ec o m p u t e rs y s t e ma n dt h e w h o l ei n f o r m a t i o n i n f r a s t r u c t u r e n e t w o r ki n t r u s i o nd e t e c t i o nh a sb e e nb e c o m i n gt h em s e a l c hh o t s p o ti n t h ef i e l do fn e t w o r ks e c u r i t ya sa na c t i v es e c u r i t yd e f e n d i n gt e c h n i q u e b e c a u s en e t w o r k s c a l ei se x p a n d i n gw i t hu 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 yd e v e l o p sq u i c k l y ， e s p e c i a lt h ec o n n e c t i o nr a t ee n h a n c e sc o n t i n u o u s l y c u r r e n tt h ep e r f o r m a n c eo fn i d s c a nh a r d l yc a t c hu pw i t ht h es p e e do fn e t w o r ks ot h a tc o n v e m i o n a ld e t e c t i o nm e t h o d f a c et os e r i o u sc h a l l e n g e f i r s to ft h i st h e s i s ，o nt h e b a s i so ft h o r o u g ha n a l y s i so fn e t w o r ks e c u r i t ya n d i n t r u s i o nd e t e c t i o nt e c h n i q u e s ，t h es h o r t a g eo ft h ei d sa n dt h ev i t a ls i g n i f i c a n c eo f i m p r o v i n gt h ei d sp e r f o r m a n c ea l ep o i n t e do u t a n dp a t t e r nm a t c hw h i c hi sa p p l i e d w i d e l yi si n t r o d u c e da n da n a l y z e ds y s t e m a t i c a l l y s e v e r a lr e p r e s e n t a t i v es i n g l ep a t t e r n m a t c h i n ga n dm u l t i n a t i o np a t t e r nm a t c h i n ga l g o r i t h m sa 陀e o n t r a s t i v e l ya n a l y s e d i n l i g h to ft h ep r o b l e ma n db o t t l e n e c ko fa c b ma l g o r i t h m ，an e wa l g o r i t h m i - a c b m a l g o r i t h m w h i c hh a sl o n g e r s t e p st h a t c a nm e n dt h ep r o b l e mi sp r e s e n t e d a n d p s e u d o - c o d e o ft h i s a l g o r i t h m s i s b m u g h tf o r w a r d i t s h o w sa n a l y t i c a l l ya n d e x p e r i m e n t a l l yt h a tt h en e wi m p r o v e da l g o r i t h mi sf a s t e ri nt h es e a r c h i n gl a r g e rs e t so f p a t t e r n sw i t hl i v i n ge x a m p l e a n da f t e r w a r d sic h o o s et h i sn e wa l g o r i t h mt oi m p r o v e t h es n o r t sd e t e c t i o ne n g i n e ，a n da ni m p r o v e ds c h e m ei sp r e s e n t e d i nt h ee n dt h e d e v e l o p m e n t 臼n do fi n t r u s i o nd e t e c t i o na r ep u tf o r w a r d t h em a i n w o r ka n dc o n t r i b u t i o no ft h i st h e s i s ： t h ep a t t e mm a t c h i n g a l g o r i t h m s o ft h e i n t r u s i o nd e t e c t i o na r ea n a l y z e d d e t a i l e d l y t w ol a c k so fa c _ b ma l g o r i t h ma l ep o i n t e do u t i nl i g h to ft h el a c k so fa c b ma l g o r i t h m , an e wa l g o r i t h m - i - a c - j m a l g o r i t h mi sp r e s e n t e d a n dw et e s t i f i e dw h i c hh a sl o n g e rs t e p sa n db e t t e re f f i c i e n c y t h a tc a nm e n dt h ep r o b l e m c o m b i n i n gt h es y s t e ms t r u c t u r eo fs n o r t , i a c b ma l g o r i t h mi sa p p l i e dt o i n t r u s i o nd e t e c t i o ns y s t e m ai m p r o v e ds c h e m ea n dr e a l i z a t i o nm e c h a n i s mo ft h i s a l g o r i t h ma l ep r e s e n t e d t h ev i t a ls i g n i f i c a n c eo ft h i st h e s i sl i e si nw h i c hi n c r e a s e dt h ee x a m i n a t i o n e f f i c i e n c ，d e c r e a s e dt h eo c c u r r e n c eo fm i s s i n g - r e p o r t , o m i t t i n g - r e p o r ta n dd o s a t t a c k k e yw o r d s ：i n t r u s i o nd e t e c t i o n ，p a t t e r nm a t c h ，s n o r t 第i i 页 国防科学技术大学研究生院工程硕士学位论文 表目录 表1 1 误用检测与异常检测的对比7 第1 i i 页 国防科学技术大学研究生院工程硕士学位论文 图1 1 图1 2 图1 3 图1 4 图2 1 图2 2 图2 3 图3 1 图3 2 图3 3 图3 4 图3 图3 图3 图3 5 6 7 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图3 1 6 图3 1 7 图3 1 8 图3 1 9 图3 2 0 图3 2 l 图3 2 2 图3 2 3 图4 1 图目录 i d e s 结构框架图4 异常检测模型6 误用检测模型6 i d s 配置示意图9 转向函数18 失效函数l8 输出函数18 模式构成的规则树2 l a cb m 算法第一次匹配2 2 a cb m 算法第二次匹配2 3 a cb m 算法第三次匹配2 3 a cb m 算法第四次匹配2 4 a cb m 算法第五次匹配2 4 a cb m 算法问题匹配示例图l 2 5 a cb m 算法问题匹配示例图2 2 5 a cb m 算法问题匹配示例图3 2 6 a cb m 算法问题匹配示例图4 2 6 a cb m 算法问题匹配错误移动示例图2 7 s u n d a y 算法不匹配的情况2 8 s u n d a y 算法移动的第一种的情况2 8 s u n d a y 算法移动的第二种的情况2 8 模式树中不含t ( i ) 的移动情况。3 0 模式树中不含t ( i x ) t ( i ) 的移动情况3 0 模式树中含t o ) 的移动情况3 0 ia cb m 算法第一次匹配3 2 ia cb m 算法第二次匹配3 2 ia cb m 算法第三次匹配3 3 ia cb m 算法第四次匹配3 3 ia cb m 算法改进匹配示例图1 3 4 ia cb m 算法改进匹配示例图2 3 4 s n o r t 体系结构3 6 第1 v 页 国防科学技术大学研究生院工程硕士学位论文 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图4 1 2 图4 1 3 图4 1 4 图4 1 5 s n o r t 部件流程3 6 s n o r t 的数据包嗅探功能。3 7 s n o r t 的预处理器3 7 s n o r t 的检测引擎模块3 8 s n o r t 的报警模块。3 9 s n o r t 规则头。4 0 s n o r t 规则树。4 1 规则解析工作流程图4 2 快速规则匹配引擎构建4 4 s n o r t m a i n 函数工作流程图4 6 o t n 节点的链表结构图4 7 构建多模式前缀规则树4 8 改进后的检测引擎工作流程图4 8 模式匹配算法流程图。5 2 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：直速圆缝厶堡拴型丕统搓盛堕配簋洼鳗丑究生塞理 学位论文作者签名：复轧翼日期：a l ，0 7 年多月，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书一 学位论文题目：高速圈缝堡拴型丞统搓盛堕螫篡洼盟珏究生塞趣 学位论文作者签名： 麴整 储舯蝴擗：早麴# 日期：p i 9 7 年二月，日 日期：参刁年f 月7 目 嚣防科学技术大学研究生院工程硕士学位论文 第一章绪论 1 1 研究背景 1 1 1 网络安全问题的严重性 计算机网络己经渗透到社会的各个领域，对社会的进步和发展起着越来越重 要的作用。随着电子商务、电子政务的迅猛发展，越来越多的公司开始在互联网 上开展其核心业务，人们也愈来愈依赖于网络所提供的服务。但是，由于早期网 络在设计上对安全的不重视以及一些人为因素使得网络安全十分脆弱，黑客的入 侵对国家安全、企业安全和个人安全造成的损失日益严重。 据统计，美雷微软公司每天大约受到2 5 3 0 0 0 次攻击，每舞累计超过l o 万 次。2 0 0 0 年微软公司即遭黑客攻击，黑客进入公司电脑系统访问核心机密长达十 几天时间。2 0 0 0 年2 月黑客袭击了美国8 大超级网站，据统计显示，这场由黑客 发起的电子攻击事件已给美国信息产业造成约1 2 亿美元的巨额损失，美国国际互 联网络的使用量在随后的两天下降了3 0 左右。2 0 0 1 年的“红色代码病毒在全 球因特网大爆发，在爆发最初的9 小对内就攻击了2 5 万个计算机系统，给全球因 特网及相关产业造成的损失超过1 0 亿美元。 我国互联网建设发展迅速，实现了国蠹凿际的高速互联，网络规模不断扩大、 带宽逐渐提高、应用范围日渐扩展；同时政府上网工程、电子政务等也不断深入。 据中国互联网信息中心提供的中国互联网络发展状况【l 】统计显示，截至2 0 0 6 年6 月3 0 日，我国共有上网用户1 2 3 0 0 万人，上网计算机5 4 5 0 万台，域名总数约为 2 9 5 0 5 0 0 个，w w w 站点总数7 8 8 4 0 0 个。网络安全已成为涉及政治、经济、军事 等各个领域甚至关系到匡家安危的追在眉睫的任务，然两形势却不容乐观。 据c n c e r t c c 2 0 0 5 年网络安全工作报告【2 】，2 0 0 5 年全年收到漏洞报告 5 9 9 0 个，平均每天超过1 5 个。微软2 0 0 4 年芷式公布了3 4 个安全漏洞，2 0 0 5 年 则公布了4 8 个安全漏洞，是2 0 0 4 年的1 4 倍，自1 9 9 5 年以来共计收到漏洞报告 总数2 2 7 1 6 个。从2 0 0 5 年1 月1 日到2 0 0 5 年1 2 月3 1 日，接收到不同渠道的蠕 虫、木马、闻谍软件等恶意代码样本上报2 7 8 6 9 7 次，较前一年网期增长2 2 倍， 入库有效样本1 5 0 9 0 2 个，较前一年增长1 8 倍。同时发现我国大陆地区2 万2 千 5 百多个臻地址的主杌被植入木马；至少有7 0 万念主枫被植入某种类型的 s p y w a r e ；境外2 2 万台主机曾对我国发起攻击。因此国内网络信息安全所面临的 形势异常严峻。 第1 页 国防科学技术大学研究生院工程硕士学位论文 1 1 2 传统安全技术简介 1 、加密技术【3 】 加密是一种最基本的安全机制，它能防止信息被非法读取。加密是一种在网 络环境中对抗被动攻击行之有效的安全机制。数据加密是保护数据最基本的方法， 但是这种方法只能防止第三者获取真实数据，仅仅解决了安全问题的一个方面， 而且加密技术也并不是牢不可破的。 2 、数据签名技术 数据签名与加密有点相似，一般是签名者利用私钥对需要签名的数据进行加 密，验证方利用签名者的公钥对签名数据进行解密运算。此法对于密钥的设计和 j i 解密算法的要求极高。 3 、访问控制技术 访问控制技术就是按照事先确定的规则决定主体对客体的访问是否合法。访 问控制一般以下面的机制为基础： ( 1 ) 访问控制数据库； ( 2 ) 口令机制： ( 3 ) 安全标志：当它与实体( 程序、数据等) 有关时，可用来允许或拒绝与 安全有关的访问； ( 4 ) 能力表：决定主体对客体访问的权利的凭证。 4 、数据完整性控制技术 数据完整性控制技术可以发现网络上传输的数据是否已被非法修改，从而使 用户不会被非法数据所欺骗。数据完整性控制包括文件系统完整性控制和网络传 输信息完整性控制。 5 、认证机制技术 认证是以交换信息的方式来确定实体身份的一种机制，是进行存取控制必不 可少的条件，因为不知道用户是谁，就无法判断其存取是否合法。用于认证机制 的技术如下： ( 1 ) 口令机制：口令一般由发送方实体提供，由接收方实体检验； ( 2 ) 安全协议机制：收发双方事先经过约定，按照约定的协议进行鉴定交换； ( 3 ) 使用密码技术：将交换的数据进行加密，只有合法用户方能解密，得到 有意义的明文( 数据) 。 ( 4 ) 使用实体的特征或实体所有的物件：这时常采用的技术就是指纹识别技 术、视角膜识别技术和d n a 识别技术等。 6 、系统漏洞扫描技术 第2 页 国防科学技术大学研究生院工程硕士学位论文 系统中漏洞的大量存在是网络安全问题总体形势趋于严峻的重要原因。外部 黑客对系统的攻击主要利用了系统提供的网络服务中的漏洞；内部人员作案则也 是利用了系统内部服务及其资源配置中所存在的漏洞。如“拒绝服务攻击 主要 就是利用了系统中资源分配上的漏洞，长期占用有限的资源不释放，使得其它用 户褥不虱系统应该提供的服务；或者利用服务处理上酌弱点使该缀务器麓溃。因 此，要保护系统的安全，就非常有必要消除系统中所存在的各种安全漏洞，而消 除系统中安全漏洞的第一步就是应该检测出系统中是否存在各种安全漏洞，在此 基础上才能进一步考虑怎样消除和修补存在的漏洞。 7 、防火墙技术 防火墙是指安装在内部阚络与外部霹络之闻或者网络与鼹络之间的可以限制 相互访问的一种安全保护措施。防火墙是在被保护网周边建立的，分割被保护网 络与井部阕络的系统，宅在内部网络与终都网络之闻形成一道安全保护屏障。 防火墙技术是通过对网络做拓扑结构和服务类型上的隔离来加强网络安全的 一种手段，它应该是不同网络之间的唯一出入墨。其露的是保护一个网络不受来 自另一个网络的攻击。英特征是通过在网络边界上建立相应的网络通信监控系统， 根据制定的安全策略，进行监测、限制或更改跨越防火墙的数据流，尽可能地对 外部鼷络屏蔽有关被保护鼷络的信息和结构，实现对穗络的安全保护，降低网络 安全的风险。当前比较成熟的防火墙实现技术从层次上主要分为包过滤技术和应 用层鼹关。 8 、入侵检测技术 入侵检测技术【4 】是在8 0 年代提出来的，是一神非常重要的动态安全技术，被 认为是解决网络安全行之有效的方法。入侵检测( i n t r u s i o nd e t e c t i o n ) 瞄】是指对入 侵行为的发现，它通过在计算机网络或计算机系统中的若干关键点收集信息并对 收集到的信息进行分析，从丽判断蹭络或系统孛是否有违反安全策略的行为和被 攻击的迹象j 。 入侵检测技术可以检测、识别和隔离“入侵 企图或对计算机的不恰当的未 授权使用。主要作用如下： ( 1 ) 监测并分析用户和系统的活动； ( 2 ) 核查系统配置和漏洞； ( 3 ) 评估系统关键资源和数据文件的完整性； ( 4 ) 识别己知的攻击行为； ( 5 ) 统计分析异常行为； ( 6 ) 对操作系统进行圈志管理，并识别违反安全策略的用户活动； ( 7 ) 针对已发现的攻击行为作出适当的反应，如告警，中止进程等。 第3 页 国防科学技术大学研究生院工程硕士学位论文 入侵检测作为传统计算机安全机制的补充，它的开发与应用扩大了网络与系 统安全的保护纵深，成为目前动态安全工具的主要研究和开发的方向。随着系统 漏洞不断被发现和攻击不断发生，入侵检测系统在整个安全系统中的地位不断提 高，所发挥的作用也越来越大。 如前文所述，为了保障计算机和网络系统的安全，人们提出并采用了多种安 全技术，很显然，没有一种技术是万能的，需要多种技术手段多个措施来分工合 作，共同构建安全的计算机网络系统。i d s 帮助管理员对付网络攻击，扩展了系 统管理员的安全管理能力( 包括安全审计、监视、攻击识别和响应) ，提高了信 息安全基础结构的完整性。入侵检测被认为是防火墙之后的第二道安全闸门，在 不影响网络性能的情况下能对网络进行监测，从而提供对内部攻击、外部攻击和 误操作的实时保护。 1 2 入侵检测技术概述 1 2 1 入侵检测发展历史及研究现状 1 9 8 0 年4 月，j a m e sp a n d e r s o n 为美国空军做了一份题为( ( 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 ) ) 【5 】的技术报告，第一次详细阐述了入侵检测的 概念。并将入侵划分为外部闯入、内部授权用户的越权使用和滥用三种类型，并 提出用审计追踪来监视入侵威胁。 1 9 8 7 年，d o r o t h yd e n n i n g 的论文 a ni n t r u s i o nd e t e c t i o nm o d e l ) ) 1 6 j 提出的理 论架构奠定了入侵检测系统商业产品的理论基础。d o r o t h yd e n n i n g 给出了一种不 依赖于特殊系统、应用环境、系统缺陷和入侵类型的通用入侵检测专家系统框架， 简称i d e s 模型，如图1 1 所示。 图1 1i d e s 结构框架图 i d e s 原型系统【7 1 使用一种混合机构，包括一个异常检测器和一个专家系统。 这种异常检测器使用统计学技术来描述反常行为，而专家系统使用基于规则的方 第4 页 国防科学技术大学研究生院工程硕士学位论文 法来保护己知的安全入侵。i d e s 原型系统在2 0 世纪是最先进的系统。 19 9 0 年，h e b e d e i n 等人开发出了基于网络的入侵检测n s m ( n e t w o r ks e c u r i t y m o n i t o r ) ，该系统第一次直接将网络中的数据流作为入侵检测的数据来源，因而 可以在不将审计数据转换成统一格式的情况下监控网络中的不同计算机，这就是 n i d s 的思想。这样i d s 有了基于网络和基于主机两种主流形态。 1 9 9 6 年，g r i d s ( g r a p h - b a s e di n t r u s i o nd e t e c t i o ns y s t e m ) 的设计与实现使得 对大规模自动协同攻击的检测更为便利。 1 9 9 8 年，r o s sa n d e r s o n 和a b i d ak h a t t a k 将信息检索技术引进了入侵检测领 域。 随着人工智能、分布式技术等等的引入，特别是i n t e r a c t 的日益膨胀，入侵、 攻击事件频频发生，网络用户迫切需要实时的、智能的入侵检测系统及其他安全 保障措施的出现。这些需求都进一步推动了入侵检测技术的发展。 近几年，入侵检测产品发展很快。国外比较流行的入侵检测系统也比较多， 如美国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 s i o nd e t e c t i o na p p i i a n c e 4 0 、c e n t r a x 2 2 等。 1 - 2 2 入侵检测技术简介 虽然存在着种类繁多的入侵检测系统，但i d s 通常使用两种基本的分析方法 来分析数据、检测入侵行为。这两种分析方法【3 0 琅口异常检测( 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 ) 。 1 、异常入侵检测( a n o m a l yd e t e c t i o n ) 异常检测技术，又称基于行为( b e h a v i o r - b a s e d ) 的入侵检测技术，是对正常 行为建模，所有不符合这个模型的事件就被怀疑为攻击。异常检测首先收集一段 时期正常操作活动的历史数据，再建立代表用户、主机或网络连接的正常行为轮 廓，然后收集事件数据并使用各种方法来决定所检测到的事件活动是否偏离了正 常行为模式，来判定用户和计算机的行为是否属于入侵行为。异常检测模型如图 1 2 所示。 异常检测常用的方法和技术包括：统计异常检测方法、基于特征选择异常检 测方法、基于贝叶斯推理异常检测方法、基于贝叶斯网络异常检测方法、基于模 式预测异常检测方法、基于神经网络异常检测方法、基于机器学习异常检测方法、 基于数据采掘异常检测方法等。 异常检测技术的优点在于可以实现对未知入侵行为的预警能力，但它存在较 高的误报率。异常检测技术的关键在于用户行为的建模、阀值的选取及其系统特 第5 页 国防科学技术大学研究生院工程硕士学位论文 征量的选择，这些都与检测的准确性有很大关系。 图1 2 异常检测模型 2 、误用入侵检测( m i s u s ed e t e c t i o n ) 误用检测技术，又称基于知识( k n o w l e d g e b a s e d ) 的入侵检测技术，它通过 攻击模式、攻击签名的形式表达入侵行为，其中应用最广的是模式匹配技术。模 式匹配对己知的入侵行为进行分析，提取检测特征，构建攻击模式或攻击签名。 检测时，通过系统当前状态与攻击模式或攻击签名的匹配，判断是否为入侵行为。 目前，误用检测系统通常将每一个攻击事件的模式定为一个独立的特征，独立的 模式可以有独立事件、事件序列、事件临界值或者允许与、或操作的通用规则表 达式组成。这种专家特征库存在的主要问题是攻击特征库的维护和攻击特征匹配 搜索问题，本文将在第二章对模式匹配算法进行详细介绍。误用检测模型如图1 3 所示。 图1 3 误用检测模型 误用检测型i d s 的优点：能够十分有效地检测到攻击，而不会产生惊人的误 警信息；能够迅速可靠地诊断特定攻击工具和技术的应用，这能够帮助管理人员 优先考虑对策，容易让普通的网络管理人员而非网络安全专家来操作。 误用检测型i d s 的不足：只能检测出那些己知的攻击，因此，需要不断地更 新攻击特征库来检测新的攻击；对变形的攻击的检测无能为力。 第6 页 国防科学技术大学研究生院工程硕士学位论文 3 、误用检测与异常检测的对比【9 】 这两种法虽然都能检测到入侵行为，但是还是有明显的区别，具体比较如表 1 1 所示。 表1 1 误用检测与异常检测的对比 误用检测异常检测 入侵行为的检测只能发现已知行为可以发现未知行为 对具体行为的依赖依赖不依赖 对具体系统的依赖依赖不依赖 误检率低高 由上面的对比可以看出： ( 1 ) 检测攻击方面：基于模式匹配的n i d s 对简单的底层( 网络层和传输层) 攻击检测率高，对已知攻击检测准确率高，对未知攻击往往无能为力。 ( 2 ) 扩展性方面：基于模式匹配的n i d s 扩展性好，发现新的攻击后只需在 特征库里增添新的规则即可，并且有许许多多组织和个人在研究攻击，这些组织 和个人都可以协助发现新的攻击，因此添加新规则相对来说更加容易。 ( 3 ) 开发难度方面：基于模式匹配的n i d s 开发难度不大。据统计，目前市 场中充斥的各种n i d s 中9 5 都属于模式匹配，也说明其开发难度不大。 ( 4 ) 攻击种类方面：基于模式匹配的n i d s 发现攻击行为后可以用比较明确 的语言提示攻击的种类，管理人员不需要很精通入侵检测知识。 由此可见，运用最多也是目前最为成熟的检测方法还是基于模式匹配的误用 检测方法。同时，随着入侵技术的更新和自动入侵工具的出现及发展，网络流量 的急剧增大，特别是网络规模和复杂程度的不断增长，入侵检测系统仍然存在着 许多问题。 1 2 _ 3 现有入侵检测系统存在的主要问题 虽然存在着大量比较成熟的入侵检测系统，但在目前的入侵检测系统中，普 遍存在以下主要问题： 1 、不断增大的网络流量使计算速度不能满足计算量的需求 以模式匹配方法为例，支撑这一方法所需要的计算量是非常惊人的。对一个 满负荷的1 0 0 m 以太网而言，所需要的计算量将是一个庞大的数字。在以太网中， 计算次数的公式如下： 计算次数= 信号大小包大小信号数量奎传输率 假设有3 0 0 0 个信号，每个信号大小为3 0 字节，平均每个包大小为3 0 0 字节， 传输率为3 0 0 0 0 包秒。 第7 页 国防科学技术大学研究生院工程硕士学位论文 计算次数= 3 0 0 0 * 3 0 0 * 3 0 * 3 0 0 0 0 = 8 1 幸1 0 1 1 通过上面的计算我们看到每秒需要计算8 1 0 亿次，这一计算速度要求己经大 大超过现有的计算条件。现有的网络入侵检测系统经常会出现丢包的现象，这也 是处理庞大计算量的结果。 同时，模式匹配算法计算所耗费的时间所占比重也相当大。根据数据统计， 在入侵检测系统s n o r t 中处理2 0 万个w e b 访问数据包时，模式串匹配时间占到了 s n o r t 全部运行时间的4 7 7 。 庞大的计算负荷，使得当今市场上没有基于模式匹配的网络入侵检测系统可 以跟进到百兆以太网领域。基于模式匹配的网络入侵检测系统在一个满负荷的 1 0 0 m 以太网上，将不得不丢弃3 0 0 o - 7 5 的数据。某些系统即使在利用率只有2 0 的以太网上也会漏掉某些攻击。黑客了解这一弱点并利用它，在目标网络上产生 大量数据，使被攻击的以太网被数据所淹没，以此来使自己的攻击被遗漏，躲过 n i d s 的检测。 可以想见，随着网络带宽的增加，对入侵检测系统将提出更大的挑战。因此， 必须对入侵检测系统各部分的性能尤其是检测引擎进行改进或者采用硬件方式实 现。 2 、误报和漏报 误报和漏报产生的原因主要有以下几点： ( 1 ) 基于特征匹配的检测方式随着规则增多性能下降。目前实际应用的入侵 检测系统通常是基于特征逐条匹配的检测方式，即通过已知攻击方式预先设定入 侵规则，已构建规则特征库。基本流程是捕获数据包、数据包解析、入侵特征匹 配，然而随着数据流量的增大、攻击方式的复杂多样化，不得不增加入侵规则条 目而使系统的处理负荷线性增加，结果是对一些攻击行为不能及时识别做出响应， 漏报问题显著。 ( 2 ) 随着网络规模的扩大以及异构平台和不同技术的采用，尤其是网络带宽 的迅速增长，i d s 的分析处理速度越来越难跟得上网络流量，从而造成数据包丢失。 ( 3 ) 网络攻击方法越来越多，攻击技术及其技巧性日趋复杂，也加重了i d s 的误报、漏报现象。 3 、拒绝服务攻击 i d s 是失效开放( f a i lo p e n ) 的系统，一旦系统停止作用，整个网络或主机就 变成开放的。因此，当i d s 遭受拒绝服务攻击时，这种失效开放的特性就会导致 黑客可以实施攻击而不被发现。下面的一些典型攻击很容易使i d s 被拒绝服务。 常见的拒绝服务攻击有：大流量攻击、m 碎片攻击、t c p 连接供给、报警攻击和 日志攻击等。 第8 页 国防科学技术大学研究生院工程硕士学位论文 1 2 4 提高入侵检测性能的意义 随着现代网络技术的飞速发展和核心交换技术的不断提高，局域千兆网解决 方案已经成为一种潮流。如图1 4 所示，i d s 可以部署在骨干网络的各个关键节点。 图1 4i d s 配置不意图 比如i d s l 部署在防火墙的前面可以侦探各种入侵的企图，但这样将产生许多 不必要的报警。i d s 2 部署在防火墙的d m z ( d e m i l i t a f i z e dz o n e ) 区，d m z 区是 内部网络对外提供各种服务的区域，比如w e b 服务、邮件服务、f t p 服务等。由 于d m z 区往往是遭受攻击最多的区域，在此部署是非常必要的。i d s 3 部署在防 火墙与路由器之间，这是检测的最关键位置，实时监测进入到内部网的数据包。 i d s 4 5 部署在内部各个网段，监测来自内部违反安全规则的行为。 然而用户的网络环境以及对入侵检测的安全需求发生了很大的变化：用户的 网络设备向高速化方向发展，如千兆网络交换设备、千兆网络服务器等等，传统 的网络入侵检测产品无法适应现有的网络结构；用户希望对入侵事件的发现越早 越好，因此需要在主干网络上布置入侵检测系统。在网络主干的高速流量环境下， 现有的入侵检测系统对网络信息包捕获能力成为一个瓶颈；在高速的流量环境下， 用户对网络入侵识别的确定性提出了更高的要求，既不能漏过重要的攻击事件， 也不能出现大量纷繁复杂的报警而使管理员要花费大量时间来从中寻找与重点防 护资产有关的问题。因此对入侵检测系统的信息分析能力和策略控制能力又是一 个重要的挑战；近年来入侵技术无论从规模与方法上都发生了变化，入侵的手段 与技术也有了“进步与发展 。只有提供高性能的入侵检测系统，才能有效降低 系统的漏报率和误报率，同时提高入侵检测系统自身的抗攻击能力。 因此，人们迫切需要速度更快、功能更好、性能更强的入侵检测系统，来适 第9 页 国防科学技术大学研究生院工程硕士学位论文 应在高速环境下网络安全防护。如何既为用户提供高性能的网络入侵检测和响应， 同时又保证系统的可扩展性、可升级性、可维护性和低成本，是长期以来安全界 面临的一个主要的课题和发展方向。因此，研究更好的模式匹配算法来提高d s 的检测性能仍然是目前i d s 研究的重点和热点。本文的研究重点就是通过改进模 式匹配算法的搜索速度从而使入侵检测系统更好的适应高速网络环境。 1 3 研究内容及创新点 入侵检测作为网络安全解决方案的一个重要组成部分，正发挥着越来越重要 的作用。目前的网络入侵检测系统绝大多数采用模式匹配的检测方法，如何提高 这种方法在处理高速网络大规模实时的检测效率和整体性能已经成为研究的焦 点。为此，需要对现有的模式匹配算法进行深入分析和改进，设计出效率更高的 算法，进一步提高网络入侵检测的应用价值。本文的主要工作如下： 1 、对网络安全的现状、传统安全技术尤其是入侵检测技术作了概要性介绍和 分析；对两类基本检测方法作了介绍与比较；指出了目前存在的主要问题及提高 入侵检测性能的意义。 2 、对模式匹配理论作了简要概述，对几种典型的单模式匹配算法和多模式匹 配算法进行了研究、分析与比较。 3 、对多模式匹配算法一a cb m 算法作了系统的分析，指出了该算法存在 的问题。针对存在的不足，运用新的匹配搜索思想，提出了一种改进的有更好搜 索步长的多模式匹配算法； 4 、在对s n o r t 检测引擎分析的基础上，运用改进算法提出实现方案。 1 4 论文的组织结构 第1 章绪论。介绍了论文的背景、意义和论文的主要内容及组织结构。 第2 章模式匹配算法研究现状。对入侵检测中的模式匹配进行了系统的介绍， 对几种典型的单模式和多模式匹配算法对行了对比分析。 第3 章一种新型的多模式匹配算法_ ia cb m 算法。本章首先对a cb m 算法的缺陷进行了分析，针对存在的不足，提出了一种新的有更好搜索步长的多 模式匹配算法叫a cb m 算法。 第4 章i - a c b m 算法入侵检测中的应用。本章结合s n o r t 系统构架，将 i a c b m 算法应用于入侵检测系统中，给出算法的实现机制，提出设计方案。 第5 章发展趋势及下一步工作。本章提出入侵检测的发展趋势及本论文下一 步要完善的工作。 第l o 页 国防科学技术大学研究生院工程硕士学位论文 第二章模式匹配算法研究现状 2 1 基于模式匹配的检测方法 目前的入侵检测系统中存在着多种检测技术，面模式匹配的理论和技术已经 是非常成熟的了。模式匹配就是将收集到的数据和信息与已知的网络入侵和系统 误用数据库进行比较，从而发现违背安全策略的行为。该过程可以是简单的通过 字符串匹配以寻找一个简单的条目或指令，也可以是利用复杂的数学方法来表示 安全状态的变化。 基于模式匹配检测方法【l o 】【1 1 钧入侵检测系统是由k u m a r 在1 9 9 5 年提出的。 目前，模式匹配己经成为入侵检测领域中最广泛的检测手段和机制之一，本文将 在本章的第2 节和第3 节对几种典型的单模式匹配算法和多模式匹配算瑟i 3 2 1 1 3 3 1 进 行介绍。下面将从原理、特点和实现及数据包特征四个方面对基于模式匹配的入 侵检测系统进行介缨。 2 1 1 模式匹配算法的背景及原理 根据底层的审计事件可以从中提取出高层的事件或活动，由高层的事件构成 入侵信号并依照高层事件之间的结构关系划分入侵信号的抽象层次并对其分类。 如果对构成信号的事件按照底层的审计进行精确的定