（电路与系统专业论文）入侵检测引擎的设计研究.pdf

摘要 入侵检测系统( i n t m s i o nd e t e c t i o ns y s t e m ，简称i d s ) ，是防火墙后保护网络 安全的第二道防线，作为一种功能强大的动态实时安全防御技术，f 受到越来越 多的关注。而模式匹配则是入侵检测系统中最基本也是最关键的技术，匹配的速 度直接影响到系统的处理性能。 本文在分析了入侵检测系统结构，及各种模式匹配软硬件实现方法的基础 上，提出了两种基于g m 和t c a m 的模式匹配引擎实现方式：( 1 ) 基于c 舢讧 分组的模式匹配引擎；( 2 ) 基于流水线结构的模式匹配引擎。 基于c a m 分组的模式匹配引擎有较强的通用性，除了适用于i d s 规则库， 也适用于各种病毒库的检测匹配。它支持“? ”通配符和大小写不敏感匹配，同时 对长模式串进行了压缩处理。为进一步提高系统的输出性能，待测串切换隐藏二 级匹配开销和多模块并行处理技术也被引入到引擎结构中。 基于流水线结构的模式匹配引擎，具有更高的处理性能，设计中提出的存储 单元共用的方法减少了5 0 以上对c a m 资源的需求，解决了c a m 面积和功耗 大的问题。这两种实现方式都达到了m u l t i 西g a b i t 的输出性能，能满足目前及今 后1 0 g 网络带宽内的高速入侵检测处理要求。在此基础上，本文给出了以上述引 擎为核心的模式匹配系统，介绍了系统框架、总线结构和数据接口等内容。 本文还对目前使用最为广泛的s o r t 规则库进彳亍- 了分析，并针对上述引擎提 出了s n o n 规则库中的模式匹配硬件实现的方法。此外，根据s n o n 规则库的特性， 引入了协议分析和规则头分类技术，进一步减少系统功耗，提高系统输出性能。 关键词：入侵检测，模式匹配，c a m 厂r c a m ，流水线，s n o n a b s t r a c t h l t n l s i o nd e t e c t i o ns y s t e m ( i d s ) a c t sa st h es e o o n dl i n eo fd e f e n c ea f t e rt h e t r a d i t i o n a lf i r e w a l l a sap o w e f f u l ，d y n 锄i ca n dr e a l - t i i n ed e t e c t i o ns y s t c m ，i ti s d f a w i i l gm o r ea n dm o r ea n e m i o nt l l e s ed a y s p a t t e m m a t c l l i n gi st h eb a s i ca n dp i v o t a l t e c h i i i q u ei ni d s ，a n dp m c c s s i n gs p e e do fp a n e m m a t c h j n ge n 酉n e ( p m e ) m a i l l l y d e d d e st h ep e - 0 m 趾c eo ft h cw h o l ei n t m s i o nd e t e c t i o ns y s t e m a f t e ra n a l y z i n gt h es t m c t u r eo fi d s ，a sw e ua sa l lk i n d so fs o f t w a 觥i a r d w a r e s o l u t i o n sf o rf a s tp a t t e m - m a t c h i n g ，m op m e s ，w h i c ha r eb a s e do nc a ma n dt c a m ， a r c p r o p o s e d ( 1 ) p a t t 锄一m a t c h i n ge n 舀n cu s i n gg m u p j n go 蝴；( 2 ) p i p e l j n e d p a t t e r n m a t c h i n ge n g i n e 1 n l e6 r s tp m e ，p a t t e m - m a t c h i n ge n 舀n cu s j n gg r o u p i n gc a m ，i sau n i v e r s a lo n e b e s i d c st t l e1 d sr u l e s ，i ta l s of i t sp a t t e m m a t c h i n gf o rm 柚yv i m sl i b m r i e s n i s e n 舀n es u p p o n s “? ”w i l d c 盯d ，“n oc 雒e ”k e y w o r d ( m e a n se “h c fa nu p p c rc a s eo ra l o w e rc a s ei sc o n s i d e r e dv a l i d ) ，a i i dl o n g p a t t e m m p r c s s i o n p a y l o a d - s w “曲i l l g 锄d m o d e l - l e v e lp a f a l l e lt e c h n i q u e sa r ca l s oi n t r o d u c e di n t ot t l i se 舀et oi m p m v et h e t l i m u g h p u t t h ep i p e l i n e d p a t t e m m a i c h i n ge n 酉n e h a se v e nb e t t c r p e d o 珊眦e t 1 l e m e m o f y c e ns h a r em e t h o df e d u c e sm o r et h a n5 0 c a mc o s t ，w h i c hf i x e dt h e p m b l e mt h a ta r e aa n dp o w e rc 0 s u m p t i o o f ( a ma r cu 蛐a l l yt o oh i 班 t 1 l e s et w op m e sc 柚b o t hr e a c hm u l t i g i g a b i t t h r o u 曲p u t ，w h i c hc a nm e e tt h e r e q u i r e m e n to fh i g l i s p e e di n n l l s i o nd c t e c t i o ni nt h cn e 柳o r kb e l o w1 0 g b j 怕t 1 1 e e s s a yp m p o s e d ，i l lm ef o l l o w i n gs e c t i o n ，ap a t t e m m a t c h i n gs y s t e mb a s e do nt h e s e p m e s ，a n dj t m d u c e dt t l es y s t e ma r c h i t e c t u r e ，b u ss t n l d u r c ，d a t ai n t e d - a c e ，a l l de t c n em o s tw i d e l y u s e ds n o nm l e sa r ea n a l y z e di nt h i se s s a y i m p l e m e n t a t i o no f s n o nu s i n gt h ep m p o s e dp m e si sa l s od i s c i i s s e d m o r e o v e r p r o t o la 腿l y s i s 柚d p a c k e t h e a dc l a s s i f i c a t i o nt c c h n i q u e sa r eb r o u g l l ti l la c c o r d i n gt ot h ef b a t u r eo fs n o n f l l l e s ，w h i c hc a nf u n h e rr e d u c et h cp o w e rc 0 s u m p t i o n ，a n di m p r o v et h es y s t e m t h r o u g h p u t k e yw o r d s ：m t m s i 咖d e t e c t i o n ，p a l t c m m a t c h i n 岛c a m 厂r c a m ，p i p e l i n e ，s n o n 浙江大学硕士学位论文 图表索引 图2 1c l d f 基本模型6 图2 2 h i d si 网络7 图2 3n l d s 网络7 图2 4 模式树( t r i e ) 1 2 图2 5 硬件逻辑结构图( a ) 单个字符，或运算，( c ) 与运算，( d ) 通配符 1 4 图2 6b l o o mf i l t e r 原理1 6 图2 7c a m 结构及时钟波形1 7 图2 8 特征串“l “”匹配过程1 8 图2 9 特征串在t c a m 中的存储方式及搜索过程示例1 8 图3 1t ( 认m 的一个存储结构示例2 1 图3 2 基本引擎结构2 2 图3 3 字节内8 1 压缩2 4 图3 4 字节间1 6 8 压缩一2 5 图3 5 通过影子积存器减小负载2 5 图3 6 隐藏了二级匹配开销的系统结构2 6 图3 7 用四个并行的处理模块，输出为原来的4 倍2 7 图3 8 模式串“a b c d e ”在基于c a m 分组引擎中的匹配2 8 图3 9x c 4 v l x l 0 0 1 2 上相同人小，不同设置的t c a m 性能2 8 图3 1 0x c 4 v l x l 0 0 1 2 上相同d a t aw i d t h ，不同d e p t h 的t c a m 性能2 9 图3 1 1 分字节匹配模式串原理。3 0 图3 1 2 基本流水线结构的模式匹配引擎3 l 图3 1 3 不同长度的模式串同时进行比较3 2 图3 1 4 用影子寄存器解决f a n o u t 较大的问题3 3 图3 1 5 模式串在引擎中的普通存储方式3 3 图3 1 6 存储单元共用的存储方式3 3 图3 1 7 模式串“a b c d e ”在基于流水线结构引擎中的匹配3 4 图3 1 8 不同规则数下的引擎性能3 5 图3 1 9 包头和载荷并行处理的n i d s 系统框架图3 6 图3 2 0p m b 通过i oq u e u e 与主系统连接一3 6 图3 2 1 系统数据通路图3 7 图3 2 2 对a 耶s l a v e 接口写数据波形图3 7 图3 2 3s d r a m l 0 酉c 模块读取s d r a m 数据3 8 图4 1s n o f t 检测引擎的工作流程4 0 i h 浙江大学硕士学位论文 图4 2 网络协议树4 4 图4 3 赢接进行模式匹配的系统示意图4 4 图4 4 引入了协议分析后的系统示意图4 4 图4 5 引入规则头匹配后的系统结构示意图。 表3 1a s i c 工艺下引擎的输出性能( c m o s0 1 8 ) 2 8 表3 2x n i n xf p g a 实现下引擎的输出性能( x c 4 v l x 2 0 0 。1 1 ) 2 9 表4 1s n o n2 0 规则库统计数据4 1 表4 2s n o r t2 4 规则库统计数据4 2 表4 3 “n o c a s e ”和“r e g e x ”统计数据4 2 表4 4 s n o r t2 o 中模式串的分组方式4 3 表4 5s n o r t 2 o 中包含丁不同协议的模式数目。 l v 浙江大学硕士学位论文 1 1 研究背景 第1 章绪论 随着i n t e m e t 的不断发展，社会生活对计算机网络的依赖也日益增强，网络 在带给人们迅捷、便利、高效的同时，随之而来的安全问题也在不断影响着人们 的生活。信息安全逐渐成为i m e m e t 及各项网络服务和应用进一步发展所需解决 的关键问题。美国商业杂志信息周于0 公布的调查报告显示，全球范围内每隔 数秒就发生一起网络攻击事件，黑客攻击和病毒等安全问题仅在2 0 0 0 年就造成 了上万亿美元的经济损失【1 1 。 而传统的防火墙只能做到允许或者阻止某地址访问某地址的特定端口，它不 是动态的安全防御系统，对于“数据驱动”的攻击行为一般无能为力。此外，防 火墙属于边界防护设备的范畴，不能阻止来自内部的攻，而调查发现，5 0 的攻 击【2 1 和8 0 的成功攻击【3 1 均来自内部。因此，随着网络技术的发展，单一依靠防 火墙的防护手段已不能确保网络的安全。 作为深度防御信息安全策略的关键性组件，入侵检测系统( h l t r u s j o nd e t e c t i o n s y s t e m ，简称i d s ) ，是防火墙后保护网络安全的第二道防线。与传统的防火墙隔 离技术以及操作系统加固技术相比，它是一种功能强大的动态实时安全防御技 术。通过从计算机网络或计算机系统的若干关键点收集信息并对其进行分析，与 基于入侵行为的过程和特征研究得出的数据库相比较，在不影响网络性能的情况 下对网络进行动态监控，提供对内部攻击、外部攻击和误操作的实时保护。作为 构建立体网络主动安全防御体系的重要组成部分，入侵检测系统越来越受到人们 的关注。 1 2 研究现状 在入侵检测系统中，模式匹配是最基本也是最关键的技术，它通过对比一系 列攻击特征发现入侵行为，匹配的速度直接影响到系统的丢包率和漏警率，对i d s 的整体性能起了决定性的作用。 浙江文学硕士学位论文 常用的基于软件的模式匹配算法包括：k m p 、b m 、a c 、a c b m 等。k m p 和b m 算法主要针对单模式匹配，对一个m 字节的模式串和一个n 字节的数据包 来说，搜索时间是d ( n + m ) 。如果有k 个模式串，搜索时间则线性增长为d ( 1 【( n + m ) ) 。 a c 算法用有限状态自动机的方法实现多模式匹配，处理时间为研n ) 。a cb m 算 法结合了b m 和a c 两种算法，提高了模式匹配的性能。 然而，随着网络带宽达到m u l t j 舀g a b i t ，以及特征模式库的不断增大，模式 匹配越来越成为制约i d s 性能的瓶颈。f i s k 和、h r 曲e s e 的分析显示，在s n o n 中， 模式匹配占用了3 0 到8 0 的c p u 时间【4 l o 在一个满负荷的1 0 0 m 以太网上，将 不得不丢掉3 0 7 5 的网络数据包l ”。传统的基于软件的模式匹配方法已经难 以实现实时线速度的匹配处理，以它为核心的入侵检测系统也无法满足实时的入 侵行为检测要求。 目前硬件实现i d s 中模式匹配的方法主要包括：( 1 ) 非确定有限自动机( n f a ) 和确定有限自动机( d f a ) ；( 2 ) b l o o mf i l t c r 结构；( 3 ) 基于c a m 厂r c a m 。采 用非确定有限自动机( n e a ) 执行正则表达式匹配【6 l 和确定有限自动机( d f a ) 执行正则表达式匹配【7 l 是硬件实现中研究较多的两种方法。这两种方法在处理能 力上比基于软件的方法提高了很多，也支持各种正则表达式。但无论是n f a 还是 d e a ，都存在着硬件资源消耗过多、更新不方便的问题，性能上也较难达到目前 网络g i g a b i t 带宽的要求。 d h a m a p u d k a r 等人提出了一种用b 1 0 0 mf i n e r 在f p g a 上实现高速串匹配的 硬件结构嘲【9 l 【1 0 1 。s o g 和b c k w o o d 采用e x t e n d e db 1 0 0 mf i l t e r ( e b f ) 对该结构做 了改进，减少了b 1 0 0 mf i l t e t 的数目，并提高了二级匹配的效率【1 1 1 。相对于 n 】1 a d e 气而言，b l o o mf i l t e r 结构具有了m u l t i 一百g a b i t 的处理速度，特征串的更 新也较前者方便。但即使是改进的结构依然存在几点不足：( 1 ) 需要大量的 m u l t i - p o n m e m o r y ；( 2 ) 具体搜索中串数目的不确定性使得性能上存在起伏；( 3 ) 划 分长串的实现方法引入过多额外控制逻辑；( 4 ) 不同b l o m nf i l t e r 中的模式串数目 无法平均分配。 g o k h a l e 等人介绍了一种利用c a m ( c o n t e n t a d d f e s s a b l e m e m o r y ) 的可编程模 式匹配系统【1 2 】。通过引入串结尾标记的方法，c a m 可以匹配不同长度的模式串 1 1 ”。这类方法大都只能处理较少数量的模式串，或较短的模式串。基于t c a m ( t c m a r yc a m ) 的搜索引擎n s e 有较高的输出性能【1 4 1 ，但在特征库较大的情 2 浙江大学硕士学位论文 况下，由于滑过的窗口交小，处理性能也会明显的下降。其它一些基于c a m 的 相关研究( 如p r e d e c o d e dc a m 【1 5 1 ) 也都有各自的特点和不足。虽然c a m 和t i a m 存在着面积和功耗较大的问题，但作为一种可每时钟周期完成一次并行大量搜索 的专用存储器件，c a m 和t c a m 是理想的高效模式匹配单元。此外，它支持灵 活更新的特性也非常适合特征库不断增加、更改的要求。 从目前的发展趋势来看，基于c a m 或t c a m 并与其它优化处理技术相结合 的方法，将是今后研究的一个重点，也非常具有实际运用的价值。 1 3 本文主要研究工作 本文在分析了入侵检测系统结构，以及目前已有的软硬件模式匹配实现方法 的基础上，提出了两种基于c a m 和t c a m 的模式匹配引擎实现方式：( 1 ) 基于 c a m 分组的模式匹配引擎；( 2 ) 基于流水线结构的模式匹配引擎。基于c a m 分 组的模式匹配引擎有较强的通用性，除了适用于i d s 规则库，也适用于各种病毒 库的检测匹配。它支持? 通配符和大小写不敏感匹配，同时对长模式串进行了压 缩处理。为进一步提高系统的输出性能，待测串切换隐藏二级匹配开销和多模块 并行处理技术也被引入到引擎结构中。基于流水线结构的模式匹配引擎，具有更 高的处理性能，设计中提出的存储单元共用的方法减少了5 0 以上对c a m 资源 的需求，解决了c a m 面积和功耗大的问题。这两种实现方式都达到了m u l t i 西g a b i t 的输出性能，能满足目前及今后1 0 g 网络带宽内的高速入侵检测处理要求。本文 同时给出了引擎在整个入侵检测系统中的连接方式、总线结构、数据接口等内容。 本文还对目前使用最为广泛的s n o n 规则库进行了分析，并用上述引擎对 s n o n 规则库的模式匹配进行了实现。同时，针对s i l 硼规则库的特性，采用协议 分析和规则头分类的方法，在按协议分类后，将规则划分为规则头处理和特征匹 配处理两部分，以规则头处理作为一次过滤，减少了系统功耗，提高了系统的处 理能力。 1 4 论文结构 本文的结构划分为：第二章介绍了入侵检测的概念，及目前常用的基于软件 和硬件的模式匹配算法和实现方式；第三章提出并详细分析了两种基于o w 和 3 浙江大学硕士学位论文 t c a m 的模式匹配引擎，以及它们在整个入侵检测系统中的应用；第四章对s n o n 规则库进行了分析，并在此基础上用上述引擎对s n o r t 规则库进行了实现，并引 入协议分析和规则头分类的方法对系统性能做了进一步优化；第五章介绍了其它 研究方法和i d s 的发展趋势。 4 渐江大学硕士学位论文 第2 章入侵检测技术及模式匹配算法 本章第一部分介绍了入侵检测技术的基本概念、c i d f 模型、i d s 分类、检测 方式及存在的问题等内容。第二部分着重分析了目前常用的各种基于软件和硬件 的模式匹配算法以及实现方式。 2 1 入侵检测技术 入侵检测系统是一种积极主动的安全防护工具，它从计算机系统或网络环境 中采集数据，分析数据，发现可疑攻击行为或者异常事件，并采取一定的响应措 施拦截攻击行为，降低可能的损失。提供了对内部攻击、外部攻击和误操作的实 时防护，在计算机网络和系统受到危害之前进行报警、拦截和响应。它具有以下 主要作用【2 】： 1 ) 监视、分析用户及系统活动； 2 ) 系统构造和弱点的审计； 3 ) 识别已知进攻的活动模式，并产生告警； 4 ) 异常行为的统计分析； 5 ) 评估重要系统和数据文件的完整性； 6 ) 操作系统的审计跟踪管理，并识别用户违反安全策略的行为。 2 1 1c i d f 模型 为了提高i d s 产品、组件及与其它安全产品之间的互操作性，美国国防高级 研究计划署( d 舢r p a ) 提出了公共入侵检测框架( c o m m o ni l l t m s i o nd e t e c t i o n h 咖e w o r k ，c i d f ) ，它是目前应用较多的结构模型【1 6 l 。 c f 将入侵检测系统分为四个基本组件：事件产生器( e v e n tb o x ) 、事件分 析器( a m l y s i sb o x ) 、响应单元( r e s p o n s eb o x ) 和事件数据库( d a t a b a s eb o x ) 。 它基本模型架构如图2 1 所示。 在c i d f 模型中，事件产生器、事件分析器和响应单元通常以应用程序的形 式出现，而事件数据库往往采用文件或数据流形式。f 模型将i d s 需要分析 淅江大学硕士学位论文 图2 1 f 基本模型 的数据缆称为事件 琶c n t ) ，它既可以是网络中的数据包，也可以是从系统同志 或其它途裰得到的信息。以上c l d f 模型中的四个组件代表的都是逻辑实体，其 孛饪舞麴一个缝终霉笺楚菜台诗雾筑瓣一令遴程黎歪楚线程，魄霹戆是多令计算 机上的多个进程，它们之间采用g l d o ( g e n e r a ji l l t n l s i 衄d e t e c t i o no b j e c t ，统一 入侵检测对象) 格式进行数据交换。 2 1 2 主机、网络和分布式检测 从数擐来源看，入侵检测系统可以分为：基予主枧的入侵检测系统( 硝d s ) 、 基于网络豹入侵检测系统( n l d ；) 謦疆分布式入侵狻灏系统( d 獭s ) 。 h m s 的数据来源于主机系统，通常是系统目恚和审计记录。h d s 通过对系 统f ；l 志和审计记录的不灏监控积分褥来发现攻击嚣操作。它的优点是针对不阀蛇 操作系统特点藏获应羯鼷入侵，误旅少；缺点楚依籁于主辊及箕审计子系统，实 时性差。图2 2 是安装了h i d s 的网络【2 】o n l d s 的数据来源予网络上的数攥流。它能够截获网络中数据包，提取其串摹 征并与将徽库中已知的模式串籀沈较，铁两达至g 检测的目的。箕优点是检测速度 快、隐蔽性好，不容易受到攻击，对主机资源消耗少；缺点是材然攻击是由服务 器的键盘发瞧的，不经过网络，因两光法识别，误掇察较裹。圉2 。3 是安装了獬d s 的网络。 分布式入侵检测系统检测的数据也是来源于网络中的数据戗。不同的是。它 采用分布式检测、集中镂理螅方法。鼯在每个网段安装一个黑夔予，该黑匿予镖 当予基予瞬络豹入授检测系统，拜j 来簸测其所在潮段上的数据流。它根据集中安 6 浙江大学硕士学位论文 全管理中心制定的安全策略、响应规则等来分析检测网络数据，同时向集中安全 管理中心发回安全事件信息。d i d s 的特点是对数据保护的范围比较大，但对网 络流量有一定的影响。 图2 2 瑚d s 网络 图2 3n l d s 网络 2 1 3 特征检测、异常检测和完整性检测 从数据分析手段看，入侵检测通常可以分为：特征检测、异常检测和完整性 7 浙江大学硕士学位论文 检测。它们分别适用于监控不同类型的入侵。 特征检测是将收集到的信息与已知的网络入侵和系统误用模式数据库进行 比较，从而发现违背安全策略的行为。该方法的优点是只需收集相关的数据集合， 显著减少系统负担。该方法的弱点是需要不断的升级以对付不断出现的黑客攻击 手法，不能检测到从未出现过的黑客手段。虽然特征检测存在上述缺点，但是目 前市场上，采用特征检测的i d s 还是性能最突出、最可靠的。 异常检测首先给系统对象( 如用户、文件、目录和设备等) 创建一个统计描 述、统计正常使用时的一些测量属性( 如访问次数、操作失败次数和延时等) 。 测量属性的平均值将被用来与网络、系统的行为进行比较，任何观察值在正常值 范围之外时，就认为有入侵发生。其优点是可检测到未知的入侵和更为复杂的入 侵，缺点是误报，漏报率高，且不适应用户正常行为的突然改变。 完整性分析主要关注某个文件或对象是否被更改，这经常包括文件和目录的 内容及属性，它在发现被更改的、被特洛伊化的应用程序方面特别有效。其优点 只要是成功的攻击导致了文件或其它对象的任何改变，它都能够发现。缺点是一 般以批处理方式实现，不用于实时响应。 2 1 4 存在问题 入侵检测虽然对网络安全的防护作用意义重大，但由于它是一门比较新的技 术，还存在一些技术上的困难。 2 1 4 1 误报和漏报 入侵检测系统对网络上所有的数据进行分析，如果攻击者对系统进行攻击尝 试，而系统相应服务开放，只是漏洞已经修补。那么这一次攻击是否需要报警， 这就是一个需要管理员判断的问题，因为这也代表了一种攻击的企图。但大量的 报警事件会分散管理员的精力，反而无法对真正的攻击作出反映。 和误报相对应的是漏报，随着攻击的方法不断更新，入侵检测系统是否能报 出网络中所有的攻击也是一个问题。除非将误报和漏报控制在一个极低的水平， 否则i d s 的长久发展会受到限制。 浙江大学硕士学位论文 2 1 4 2 隐私和安全 入侵检测系统可以收到网路的所有数据，同时可以对其进行分析和记录。这 对网络安全极其重要，但难免对用户的隐私构成一定风险，这就要看具体的入侵 检测系统是否能提供相应功能以供管理员进行取舍。 2 1 4 3 分析处理能力 随着网路数据流量的不断增长，尤其是网络带宽超过了g i 跏i t ，各种待分析 网络数据的产生速度已经远远超过入侵检测软件的处理能力，如何采用硬件或软 硬件相结合的方法高效处理网路中的数据实现入侵检测的功能，是需要面对的主 要问题。 在入侵检测系统的各种技术中，模式匹配是最基本也是最关键的技术，匹配 效率的高低直接制约着i d s 的性能，对模式匹配的高速硬件实现也就变的尤为重 要。正因为如此，本文将研究重点放在对入侵检测系统中高速模式匹配的研究上。 2 2 入侵检测系统中的模式匹配算法 串的模式匹配【1 7 】是一种重要的串运算。对两个串t 和w ，在主串t 中找到 等于子串w ( 也称为模式) 的过程称为模式匹配，如果在t 中找到了等于w 的 子串，则称匹配成功，否则匹配失败。 在n i d s 中，模式匹配就是将接收到的数据包或会话中的数据与特征库中的 每一条攻击特征进行匹配，在特征库中查找与接收到的数据特征相同的数据段， 若匹配成功，则表明存在入侵行为，否则，认为该数据是无害的【。多模式匹配 指的是给定包含k 个特征模式的攻击特征库p p 1 ，尸2 、 ，在数据包中找到等于 k 个特征模式中的任何一个或多个的过程。 2 2 1 基于软件的实现方法 在入侵检测系统中典型的算法包括：蛮力( b m t e f o r c e ) 算法、k m p ( k n u t l i m o r r i s - p r a t t ) 算法f 1 9 1 、b m ( b o y e r - m o o r e ) 算法【2 0 】、a c ( a j l o c o r 雒i c k ) 算法1 2 1 】及a t b m 算法【2 2 】等。 9 浙江大学硕士学位论文 2 2 1 1 1b r u t e f o r c e 算法 b m t e f o r c e 算法( 直接匹配算法) 是模式匹配中最早出现的算法之一。它将 主串t ( 串长为n ) 依次分成n m + 1 个长度为m 的子串，检查每个这样的子串是 否与攻击特征串w ( 串长为m ) 匹配。该算法的匹配过程易于理解，最坏时间复 杂度是o ( m n ) 。但当第一次匹配成功时，仅需比较m 次；而当w 中第一个字符 不同于中任意一个字符时，只需比较n 次。b n i t e f 0 r c e 算法的一个缺点是对数据 串的扫描常常需要回溯，因此匹配的效率较低，不适合用于实时的网络入侵检测。 2 2 1 2k m p 算法 k m p 算法的思想是假设在模式匹配的进程中，执行t 【i 】和w j 】的匹配检查， 若t 【i 】= w 脚，则继续检查t 【i + 1 和w 叶1 】是否匹配。若t 【i 】一w 啪，则分成两 种情况：若j = 1 ，则模式串右移一位，检查t 【i + 1 】和w 【1 】是否匹配，其中，t 【i 】 表示在主串t 中的第i 个字符，w u 】表示在模式w 中的第j 个字符。若l j s m ， 则模式串右移j - n e x t 0 ) 位，检查t 【i 】和w l n c x t ( j ) 】是否匹配。重复此过程直到j = m 或i = n 结束。其中n e x t 定义如下： fo ，j = 1 n e x t m a ) ( 删1 k j ，使得w 【l ，k - l 】_ w 【j 一( k 1 ) ，j 1 【l ，对所有k1 k n ) ，初始化时向量的每一个元素的值为o 。对每一个给定的元素置， b l o o mf i l t c r 使用k 个相互独立，且具有在值域f o ，1 ，m l 上均匀分布特性的哈 希函数对该元素进行h a s h 运算。得到的k 个值在mb i t s 向量的相应位置1 。对集 合s 中的n 个元素进行相同h 船h 求值操作，这一过程称为“对b 1 0 0 m f i l t e r 编程”。 图2 6 ( a ) 用毛，j ：两个元素，k = 4 个h a s h 函数来表明编程的过程( m = 1 3 ) 。注意到不 同元素可以被编程到m b i t s 向量中相同的位置。 查询过程和编程过程类似，b l o o mf i l t e r 用相同的k 个h a s h 函数产生k 个值， 在mb i t 的向量中相应的位置查询置位情况，如果mb i t s 向量中有至少一位没有 被置位，则说明不匹配。如果所有相应的位都置位，则被认为可能匹配：包括t 兀i e p o s i t i v e ( 图2 6 ( b ) ) 和蜘s ep o s i t j v e ( 图2 6 ( c ) ) 两种情况。在硬件实现中，每一 类长度的特征串都需要一个相应b l o o mf i l t c r ，系统以每周期1 个字节的线速度并 行的检测所有可能的匹配情况。如果系统工作频率为2 0 0 m ，则匹配的速度为 2 0 0 f 勖打s 一1 6 g 6 打5 。 b l o o mf i l t e r 算法的特点保证了不会出现漏报( f a l s en e g a t i v e ) 的情况。但是 这种实现方法存在着一些不足：( 1 1 每一种不同长度的串都需要一个独立的 b 1 0 0 mf i l t e f ；( 2 ) 对可能的匹配都需要2 次比较，在h a s h 表里的搜索及h a s h 碰 撞可能成为系统的瓶颈；( 3 ) 需要大量的多端口m e m o r y ，尽管目前的技术已经可 以提供多读写口的m e m o r y ，但硬件资源的开销和速度的影响仍然较大，尤其是 当k 值较大时。另外这种实现方法对m 锄o r y 的搜索时间也比较长。 辩糕大学磁士学证论文 s l 罅鼍，筏被编翟弱撒毯担舞量孛，逮垂k 2 4 ，m 2 1 3 x 圆) x 凌询b l o o m 鞠l # “函鸯援应位垒舔嚣位，蹶以蕊酝纛曼楚湘。筘s i l 孵，x = 是) y ( c ) y 在诲b l o o m 蝴1 因为相虑像垒部置位，掰以匹配( 但却鼹f a l s ep o s i l i v 。) 圈2 6 b mf i i t e f 灏理 2 0 2 3c a 凇c a 蠢蓬缝耨 目前，高速模式腻配硬件实现的一个研究热点是c a m ( c o t c n ta d d r e 8 s a b l e m e m o f “矬。c a m 怒一秘能够并行进行大量搜絮的专用存储器传，每时钟瘸蠲完 残一次搜索，可作为搿效豹模式嚣聚单元。c a m 包括普通c a m ( b i n a f ye a m ) 和他m ( t c m 盯vc a m ) 。普通c ：a m 中存储的是1 或0 ，进行的怒精确 的匹配。丽t c a m 瞳l 予每个存储单元可以存储l ，o 竣x f 无关项) ，可 鞋对不糊长度韵模式串进幸亍同时嚣酝攫索。图2 7 分爨为( 漶m 的结构示意图和 读操作的波形图。 l o n 冀踟于髓年w c m 发表盼论文上介缨了一种爰c 枷实现高速模式匹 配的方法。基本愚憋惩以字节毙较为单诬( 8 b i t ) ，每个字符占疆一个c a m 行， 1 6 浙江大学硕士学位论文 ( a ) c a m 结构示意图 c l k 厂八厂n ，、，厂、 e n 厂一 o l n = 3 口) c 翌) = = 二= 敷二 m 再f c h 厂1：厂一 瓣= 二笼窑c = ) 仁= 柚trk日-幽曲-州-一 m a t c h 厂_ 、，厂一 黼苌銎二= 芰互疋3 = # 赫0 0 d 0 啪- - ，o n - ，l * x _ w ：一 ( e a 麓读( 匿配) 掇撵瓣锋波形 图2 7c a m 结构及时钟波形 所有特征字符串按字符在c a m 中连续存储。为了区分每个特征串的结尾，在每 一个字符稀引入了l - b j t 的结尾标记t 。当t = o 时，表示该字符不是特征串的结 尾，当t = l 时，袭示这楚某一特德串的结尾字德。赝霉的c a m 资源是9 柚i l s 其中n 为所有特征串的字符总数。同时一个”1 的m a t c ha r r a v 与每一次跹配过 程翊瓣应，当串鼷字符黢嚣上且之蓠夔字餐都甄醒上霹，表示一次特镊事懿 m a t c h 。通过这种方法使得特征串聊以紧密排列而鼠可以同时匹配不同长度的特 薤率。图2 溜鞋1 4 4 这一褥薤事蓬怒匏过程示绸。 这种实现方式的缺点怒只能处理较少量的特征串，面鼠所用c a m 的d e d t i l 过大使匹配豹效率受蓟较大的限制。 1 7 星星里星重量富富星 嚣嚣蕊茹 图2 8 特征串“1 4 4 ”匹配过程 基于t c a m 的模式搜索引擎f 1 s e 有较高的输出性能【1 4 】，它的基本原理是： 如果待测串t 从某一位置s 起的1 w 字节与特征串的前缀都不匹配，那么待测 串新的一次匹配就可以滑过这w 字节，从而大大提高匹配的效率。 用数学语言表达为：设输入待测串为z = 气，特征串集合为 p = 促，最，p ，其中只= n ：，n ? ，4 ：。1 sj sr 。如过从待测串t 的第s 字节起， 有f 。，。* 口：，口：+ 。，f o ，1 ，w 一1 ，则比较中可以滑过这w 字节。如果w 字节匹配上了，则继续匹配剩下的字节。 特征串在t c a m 中的存储方式及搜索过程示例如图2 9 所示。 f t s et c a m c o n t e n t g o 55 5 6 7 8 8 8 8 g + 5556 7 8 8 8 g 255 5678 8 g 3555 6 7 8 g d55 5 6 7 o s555 6 g 645 55 g 1 十55 g 05 p 佗f i ) 【s l i d n gw i i i d o w ( p s w ) 匦受圈川5 432 4555678888 ll 0 0 k u p i n t c a ma n d 锄 e n 廿y i n0 6 m m c h e s s h m 、 p s wb y6b ”m c n tts 匦垂圃z n ssss ，s i l 0 0 k u p i n t c a m d ” e n 时m m c h e s s h m p s w b y9 b y t e s t l l e n tss s ss ，es 。，匝歪盈ss ll k u p j n t c a m d ” e n 时i ng 3 m 8 i c h e s - s h i n 、p s w 姆5b y t e s t h e n 。sssss ，ss z ，巨重囹 f i n da m a t c h 甜e n 酊i ng 0 图2 9 特征串在t ( ：a m 中的存储方式及搜索过程示例 1 8 洲黜 ，回0回。曰p回罐。罐 回p 回田p 回团p 回田p 固田p 回田p 回田p 回星田p 回 罐。罐 浙江大学硕士学位论文 f r s e 引擎通过滑过尽可能多的字符的方法提高了模式串搜索的性能，但在 特征库较大的情况下，由于滑行的窗口变小，处理性能也会明显下降。而且这种 方法消耗大量的t c a m ，成本和功耗都过大。还用其它一些基于c a m 的研究 【2 6 1 ，也都有各自的特点和不足。 虽然基于c a m 的方法存在面积和功耗较大的问题，但作为一种每时钟周期 完成一次并行大量搜索存储器件，c a m 仍是理想的模式匹配单元。目前的工艺 已经在c a m 的容量、面积和功耗上有了很大的改进。此外，c a m 对特征串更新 方便，用于特征库不断增加、更改的入侵检测系统中是非常合适的。 本文的研究也主要是基于c a m 和t c a m 的方法，并与其它优化处理技术相 结合，提出了两种m u l t i g i g a b i t 速率，低硬件开销的模式匹配引擎，从第三章开 始将对这两种引擎的结构，优化方法，性能及针对实际规则库的应用等内容进行 详细的分析。 1 9 浙璩大学硕士学位论文 第3 章两种基于( a m t c a m 的 模式匹配引擎设计及分析 在分析了已肖模式暇配实现方法的基础上，本章蘸点提出了两种基于 c a t n a m 的模式匹配引擎设计方法及性能分拼a 在m u l t i - g i g a b j t 网络带宽下， 这两； 申弓l 擎均能溃足n l d s 对包线速度、深检测的震求，易予舞级维护，闲时保 证了较低的面积、功耗，投较高的存储有效性。3 _ 3 节为引颦在n l d s 系统中的应 慰，按系绞结穆、麓裁模块、数据绩日分别终了食缀。 3 。- l 基于e a 嘲分组豹模式匹配萼l 擎设计 本节提