（应用数学专业论文）基于fpga的入侵检测系统的网络包分类技术研究.pdf

摘要 摘要 基于f p g a 技术的网络入侵检测是未来的发展方向，而网络包头的分类是入 侵检测系统的关键。 文章首先介绍了f p g a 技术的基本原理以及其在信息安全方面的应用，接着 介绍入侵检测系统以及f p g a 技术在入侵检测系统中的应用。 分析了几种比较出名的网络包分类算法，包括软件分类方法、t c a m 分类算 法、b v 算法、t r e eb i t m a p 算法以及端口范围分类算法。 在此基础上，文章设计了一个基于f p g a 技术的入侵检测系统包分类的基本 框架图，实现框架图中的各个基本功能模块。在实现过程中，提出了一类结合三 态内容可寻址内存( t c 埘) 和普通存储器( r 删) 的网络包包头分类方案。我们 将检测规则编号并位图化，使用r a m 存储与包头结构相关的规则位图，通过t c 棚 上的数据匹配操作，快速关联待分析的网络数据包与入侵检测规则。文章还讨论 了网包头分类方法的优化算法，将优化算法与未优化算法在速度和空间上进行比 较。此外，还讨论了对s n o r t 的规则库进行整理和规则化的问题。 最后，对所设计的包头分类匹配模块在o u a r t u si i 进行仿真评估，将实验 结果与已有的一些分类算法进行了比较。结果说明，本设计在匹配速度和更新速 度上有优势，但消耗了较多的存储空间 关键词：入侵检测系统；s n o r t ；f p g a 技术；包分类；t c 瑚 a b s t r a c t t h ef u t u r ed i r e c t i o nf o ri d s ( i n t r u s i o nd e t e c t i o ns y s t e m ) i sf p g a - b a s e d n e t w o r kp a c k e tc l a s s i f i c a t i o np a y sa l li m p o r t a n tr o l ei ni d s i nt h i sp a p e r , w ef i r s ti n t r o d u c et h ef p g at e c h n o l o g ya n di t sa p p f i c a f i o ni n i n f o r m a t i o ns e c u r i t y , n e x tw ei n t r o d u c ei d sa n df p g a t e c h n o l o g yu s e di ni d s w ea n a l y z es e v e r a lf a m o u sn e t w o r kp a c k e tc l a s s i f i c a t i o na l g o r i t h m , i n c l u d i n g s o f t w a r ep a c k e tc l a s s i f i c a t i o n 、b va l g o d t h m 、t r e eb i t m a pa l g o r i t h ma n dp o r tr a n g e a l g o r i t h m w e l a yaf a m ew o r ko fn e t w o r kp a c k e tc l a s s i f i c a t i o nb a s e do nf p g at c c i m o l o g y a n dr e a l i z et h ef r a m ew o r k d u r i n gt h ei m p l e m e n t a t i o n ，w ei n t r o d u c ea na l g o r i t h mf o r p a c k e tc l a s s i f i c a t i o nc o m b i n i n gt c a ma n dn o r m a lr a m w e u s er a mt os t o r et h e m a p p i n g o ft h er u l es e t , t h r o u g ht c a m m a t c h i n ga n dr u l es e tm a p p i n g , w ec a ne a s i l y g e tt h em a t c h i n gr e s u l t w ea l s od i s c u s sh o w t oo p t i m i z et h er u l es e t i na d d i t i o n ，w e a l s od i s c u s sh o wt oa b s t r a c tr u l ef r o mt h es n o r tr u l es e ta n dn o r m a l i z et h e m f i n a l l y , w es t i m u l a t et h ep a c k e tc l a s s i f i c a t i o nc o m p o n e n t so nq u a r t u sn a n d c o m p a r et h ee x p e r i m e n t a lr e s u hw i t ho t h e rf a m o u sc l a s s i f i c a t i o na l g o r i t h m r e s u l t s h o w st h a to u rd e s i g ni sb e t t e rt h a no t h e ra l g o r i t h mo nm a t c h i n gs p e e da n du p d a t e s p e e d b u ti ta l s oh a v ed i s a d v a n t a g eo ns p a c eu s e da n dc o s t k e yw o r d ：i d s ；s n o r t ；f p g a t e c h n o l o g y ；p a c k e tc l a s s i f i c a t i o n ；t c a m 广州大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 后果由本人承担。 学位论文作者签名：硼寸庆玩日期：伽f 年占月妇 广州大学学位论文版权使用授权书 本人授权广州大学有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 广州大学可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。( 保密的学位论文在解密后适用本授权书) l 叫 r月月 ，b r b 年年 1，=f 叫研 期期 第一章绪论 1 1 本课题的研究意义 第一章绪论 本文涉及f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ，现场可编程门阵列) 技 术的入侵检测系统的网络包分类技术的研究。 入侵检测是最近二十年发展起来的一种动态监控、预防或抵御系统入侵行为 的安全机制，是网络安全体系的重要组成部分。网络入侵检测系统，通过收集和 分析网络数据包信息，依据预先设定的检测规则，判断网络中是否有违反安全策 略的行为和遭到袭击的迹象。一个成功的入侵检测系统可以使系统管理员时刻了 解网络系统( 如程序、文件和硬件设备等) 的任何变更，为安全策略的制定提供 重要信息。入侵检测是对传统安全产品的合理补充，它帮助系统对付网络攻击， 扩展了系统管理员的安全响应能力，提高了信息安全基础结构的完整性，其开发 和应用增大了网络与系统安全的保护纵深。 目前，大多数的入侵检测系统都是由软件实现的，这给这类系统的应用带来 一些局限性。软件实现的网络入侵检测系统，都要占用一定的计算资源，在一个 大型的或拥挤的网络中，这类系统可能来不及处理过量数据或丢失网络数据包， 从而无法识别网络流量较大时发起的攻击；软件实现的网络入侵检测系统的灵活 性是有限的，系统往往与操作系统有关，且当升级或重新配置时，需要重新启动； 与其他软件系统类似，软件实现的入侵检测系统也存在安全漏洞，容易被第三方 攻击，缺乏对入侵检测关键组件的保护，若攻击成功，则直接导致报警失灵，使 攻击者的攻击行为无法被记录。因此，软件实现的入侵检测系统尽管存在开发便 捷的特点，但在系统的有效性、灵活性、安全性等方面存在局限。 在软件实现的系统中，处理器可以动态地调用当前所需的程序段，具有相当 的灵活性却损失了一定的性能；在硬件实现的系统中，算法被固化成电路，性能 优越但却几乎完全丧失了灵活性。 实时电路重构，就是在电子系统的工作状态下，动态改变电路的结构。这主 要是通过对系统中的可编程器件进行重配置或部分重配置来实现的。利用这一技 术设计的可重构系统，就能在只增加少量硬件资源的情况下，轻而易举地将软件 实现和硬件实现的优点合二为一。 在可重构系统中，硬件信息( 可编程器件的配置信息) 也可以像软件程序一样 被动态调用或修改。这样既保留了硬件计算的性能，又兼具软件的灵活性。换句 话说，可重构系统把硬件软件化，使硬件可以像软件一样被使用。 采用硬件实现的入侵检测系统是解决上述问题的一种有效的方法。 f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ，现场可编程门阵列) 是p a l ，g a l 、 1 第一章绪论 e p l d 等可编程器件的发展，其具有的静态可重复编程和动态在系统重构的特性， 使得硬件的功能可以像软件一样通过编程来修改，极大地提高了电子系统设计的 灵活性和通用性，降低了电子系统的开发成本。 本项目的研究涉及入侵检测网络包头的分类，我们将研究基于f p g a 的网络入 侵检测系统的可行的、可灵活配置的、高速的入侵检测系统的包头分类的结构网 络包头的方法，使得入侵检测系统能够更好地适应高速网络的环境，克服软件实 现的入侵检测系统所具有的局限性，更加及时地发现入侵者和入侵行为。 1 2 本课题国内外研究现状及发展趋势 入侵检测系统及相关技术的研究，是网络安全研究中的一个热点，尽管人们 对入侵检测已有近二十年的研究，且对入侵检测的整体框架有总体上的认识，但 其实现技术和实现结构仍远未达到成熟的阶段，还有很大的发展空间。 已有的入侵检测系统的研究主要有两大方面，一是入侵检测技术和算法的研 究，提出了数据挖掘、人工免疫、神经网络、机器学习等不同的数据分析模型， 为降低系统的误报率和漏报率，又提出了许多的方法进行数据融合和报警关联； 二是体系结构方面，从原来的单机、单个网络的检测研究，发展到分布式的入侵 检测系统的研究以及基于a g e n t 的入侵检测系统的研究等等。值得注意的是，上 述的研究都假定所有的网络攻击数据包都是可收集的，而具体的实现包括许多商 业化的入侵检测产品大都基于软件。 随着网络规模的扩大，传输速率的提高，软件实现的入侵检测系统很难检测 所有的网络数据包，使得系统的漏报率上升，达不到安全需求，需要通过硬件实 现入侵检测系统，有效且快速地收集和分析网络数据。 在寻求硬件实现的研究过程中，一种可行的方法是采用f p g a 芯片来辅助完成 入侵检测系统的硬件实现。2 0 0 2 年，美国b r i g h a my o u n g 大学的h u t c h i n g s 1 0 等设计了一个串的正则表达式至o f p g a 电路的映射模块，用于在f p ( i a 中实现入侵检 测规则中内容串的快速匹配，这是比较早期的讨论f p g a 芯片应用到入侵检测系统 的实现。随后，在与f p g a 开发和应用相关的重要的国际会议上，如i e e es y m p o s i u m o nf i e l dp r o g r a m m a b l ec u s t o mc o m p u t i n gm a c h i n e s ( f c c m ) 、i n t e r n a t i o n a l s y m p o s i u mo nf i e l dp r o g r a m m a b l eg a t ea r r a y s( f p g a ) 、 i n t e r n a t i o n a l c o n f e r e n c eo nf i e l dp r o g r a m m a b l el o g i ca n da p p l i c a t i o n ( f p l ) 等，都出现 了一系列利用f p g a 芯片的快速数据处理能力 1 0 - 1 4 ，来提高入侵检测系统对网 络数据包的分析和处理性能。 1 0 中提出了将可重配置电子应用于网络入侵检测 系统， 1 3 中提出了将f p f g a 技术应用于处理快速路由表中， 1 4 中提出一种将 f p g a 技术应用于防火墙上。f p g a 芯片对数据流的高速处理能力，使得即使在比较 2 第一章绪论 高速网络上也能完成数据包的收集和分析，这在基于软件的入侵检测系统中是难 以完成的。目前在基于f p g a 的入侵检测系统的实现中，f p g a 芯片主要用于网络包 的分类和模式串的匹配处理上，数据融合和报警关联方面，仍由软件实现。而且， 现有的实现主要集中在i p v 4 网络上，没有考虑到i p v 6 数据包的收集与分析。 国内方面，f p g a 技术在信息安全方面的应用主要集中在密码算法的实现中， 包括d e s 、a e s 等分组密码算法和r s a 、b c c 等公钥密码算法的实现中 2 2 3 5 ， 就我们所了解，在入侵检测系统的f p g a 实现方面，国内目前还没有看到公开发 表的技术文章。 从现有的资料来看，无论国内还是国际，利用f p g a 来实现入侵检测，都处于 起步的状态。入侵检测系统的检测过程一般是首先进行包头分类匹配，然后进行 包负载匹配。包头分类匹配和包负载匹配都可以用硬件实现。本文仅考虑包分类 部分。 1 3 论文的主要内容及章节安排 论文概述了f p g a 技术在信息安全，特别是入侵检测系统中的应用。分析了 网络包的几种分类方法，如软件的包分类方法、t c a m 、b v 算法、t r e eb i t m a p 算法等，在此基础上，设计了一个基于f p g a 的网络入侵检测系统包分类的框架 图，实现在框架图中的各个模块，在设计过程中，引入了用r a m 存储比特位串以 及用r a m 和t c a m 结合来完成匹配。最后，从各个指标上对各种包分类算法进行 比较。 论文的全文章节安排如下： 第一章介绍f p g a 网络入侵检测系统的国内外的研究情况。 第二章介绍了f p g a 技术及网络入侵检测系统的检测原则。 第三章研究了各种网络包分类的算法，包括最有代表性的s n o r t 的快速检 测引擎f p d e ，以及基于硬件的t c a m 、b y 、t r e eb i t m a p 等算法。 第四章提出一个用f p g a 实现网络包头分类的框架图，并且实现各个设计模 块。 第五章对第四章所设计的网络包分类模块进行仿真，并且从各个指标对各 种算法进行对比分析。 1 4 本章小节 本章介绍了研究的课题的内容即：关于f p ( ；a ( f i e l dp r o g r a 珊n a b l eg a t ea r r a y ， 现场可编程门阵列) 技术的入侵检测系统的网络包分类技术，课题的意义以及课 题的国内外研究现状及发展趋势。 3 第二章入侵检测系统和f p 卧技术概述 第二章入侵检测系统和f p g a 技术概述 2 1 入侵检测系统概述 2 1 1 什么是入侵检测? 入侵是所有试图破坏网络信息的完整性、保密性、可用性、可信任性的行为。 入侵是一个广义的概念，不仅包括发起攻击的人取得超出合法范围的系统控制 权，也包括收集漏洞信息，造成拒绝服务等危害计算机和网络的行为。入侵行为 主要有以下几种： 外部渗透指既未被授权使用计算机，又未被授权使用数据或程序资源的渗 透； 内部渗透指虽被授权使用计算机，但是未被授权使用数据或程序资源的渗 透； 不法使用指利用授权使用计算机、数据和程序资源的合法用户身份的渗 透。这几种入侵行为是可以相互转变，互为因果的。例如，入侵者通过外部渗透 获取了某用户的账号和密码，然后利用该用户的账号进行内部渗透；最后，内部 渗透也可以转变为不法使用。 入侵检测是指通过对行为、安全日志或审计数据或其他网络上可以获得的信 息进行操作，检测到对系统的闯入或闯入的企图。 2 1 2 入侵检测系统的分类 根据检测技术的分类，入侵检测系统分为基于误用的入侵检测系统和基于异 常的入侵检测系统。 ( 1 ) 误用( m i s u s e ) 检测原理 基于误用的i d s 又被称为基于滥用的i d s ，该技术的研究主要是从2 0 世纪 9 0 年代中期开始，当时主要的研究组织有s r i ，p u r d u e 大学和c a l i f o r n i a 大学 的d a v i s 分校。误用检测技术主要通过某种方式预先定义入侵规则，然后监视系 统的运行，从中找到符合预先定义的入侵行为。显然，误用入侵检测依赖于模式 库，如果没有构造好模式库，则i d s 就不能检测到入侵者。如著名的开源软件 s n o r t 就是基于误用的入侵检测系统。该系统预先定义好入侵规则库，对捕捉到 的数据包，根据s n o r t 规则的需要，提取其特征值，如果特征值与s n o r t 规则库 的某条规则相匹配，就意味着该数据包是个入侵的数据包，s n o r t 就采取相应的 动作。 5 第二章入侵检测系统和f p “技术概述 图1 误用入侵检测模型 f i g 1m i s u s e di n t r u s i o nd e t e c tm o d e l 目前这类入侵检测系统主要有专家系统、模型推理系统、误用预测系统和模 式匹配系统。其中，模式匹配是应用最为广泛的检测手段。 ( 2 ) 异常( a a o m a l y ) 检测原理 基于异常的i d s 假设任何人的正常行为都是有一定的规律的，并且可以通过 分析这些行为产生的日志信息总结出这些规律。i d s 检测与可接受行为之间的偏 差。如果可以定义每项可接受的行为，那么每项不可接受的行为就应该是入侵。 首先总结正常操作应该具有的特征( 用户轮廓) ，当用户活动与正常行为有重大 偏离时即被认为是入侵。这种入侵行为可能是已知的，也有可能是未知的。 假设某个用户帐号平时访问服务器的时间是：9 ：0 0 t 目的地址：h o m e i。规则头 目的端口：2 3 l根结点 立兰 f l o w ：t os e r v e r 。、 e s t a b l i s h e d c o n t e n t ：i a 02 3 a 0 1 0 a e s o l 。 移_ 嚣鬻 ( o t n ) 图3s n o r t l x 的规则树 选项结点匹配。f i g3 s n o r t1 x sr u l et r e e 弱点分析：采用这种方式进行数据包匹配工作是费时的：每个数据包到达时， 都必须找到相应的规则头结点。由于规则头结点在内存中以链表形式保存，查询 的代价相对较大。s n o r t2 3 2 约有1 8 0 个规则头根结点，若采用该算法，最好 的情况只要用1 次查询就能得到规则头根结点，最坏的情况是需要1 8 0 个查询， 平均的情况下，每个数据包需要查询大约9 0 次才能找到所属的规则头。 3 3 2 s n o r t2 j 的快速检测引擎f p d e 针对上述缺点，s n o r t2 0 构造了全新的快速检测引擎( f a s tp a c k e t d e t e c t i o ne n g i n e ，f p d e ) 和全新的规则分类管理模块( p a c k e t c l a s s i f i c a t i o n - r u l em a n a g e r ，p c 删) ，重新设计了包分类检测机制。 p c 跳针对不同目的端口和源端口的规则划分类别，并将这些信息以数组的 形式保存。对每种不同的协议，p c 蹦都为它们建立“端口一规则”映射 p o r t _ r u l em a p ，p o r t _ r u l e _ m a p 中保存了每个端口对应的规则集p o r t _ g r o u p ， 第三章入侵检测系统的网络包分类算法 p o r t _ g r o u p 中保存了不同类别的规则链表。 p o r tg r o u p 中包含了名为p r m s r c p o r t 、p r m d s t p o r t 和p r m g e n e r i c 的数组， 分别用于存放源端口、目标端口与通用规则集。图l 中构造的规则树被重新分类 并加入规则集合中，分类方法如下： 如果源端口值为特定值f ，目的端口为a n y ，则将该规则加入源端口集 p r m s r c p o r t 力中；如果目的端口值为特定值j ，源端口为a n y ，则将该规则加入 到目的端口集p r m d s t p o r t 刃中。 如果源端口值为特定值1 ，目的端口值为特定值则将该规则同时加入 源端口集p r m s r c p o r t 力和目的端口集p r m d s t p o r t l 中。 如果目的端口和源端口均为a n y ，则该规则加入通用集( p r m g e n e r i c ) 中。然后将它们同时加入所有含有内容的源端口集合和目的端口集中。 如果规则中出现端口值求反或指定范围的情况，视其端口值为a n y 。 将所有通用集合中的规则加入每个非空的p r m d s t p o r t 刃和 p r m s r c p o r t j 中，其中i o ，6 5 5 3 5 。今后通用集合( p r m g e n e r i c ) 不再参与 匹配工作。 p o r t r u l e m a p p r m s r c p o n 6 5 5 3 6 】：p o r t _ g r o u p p r m d s t p o r t 6 5 5 3 6 】：p o r t _ g r o u p 4 d r i l l g c n c r i c ：p o r tg r o u p p o r tg r o u p p g h e a d ：r u l en o d e 。p g h e a d n c ：r u l en o d e p g u r i h e a d ：r u l en o d e p g p a t d a t a ：r u l en o d e * d p a t d a l a u r i ：r u l en o d e r u l en o d e - - - - - - - - - - - - - - - - - - ：- - - - - - - - - - - - - - 一 m r u l e d a t a ：v o i d i r u l e n o d e l d 4 m n e x t ：r u l en o d e 图4m o r t 2 x 使用的规则映射 f i g 4s n o r t 2 x sr u l em a p p i n g p c i i m 模块最大的改进是采用“端 口一规则”映射代替原有的规则头链 表。每一个端口在p o r t _ i 雌p 中都有 对应的组规则。当数据包到达时， 其源端口j 和目的端口对应的规则 集分别是p r m s r c p o r t 力和 p r m d s t p o r t j 。这样，无需进行包 头与规则头的比较，完全解决了1 中 提及的弱点。 尽管由端口找到相应的规则，大 大提高了查找速度，但是，对于该端 口相应的一大串规则，不能实现并行 匹配，这也就大大限制了扫描匹配的 速度。 簟三章入侵检翻系统的圈络包分赛算法 3 4 基于硬件技术的包分类 3 4 1 基于t c 枷包分类方法 1 内容可寻址存储器c 埘 内容可寻址存储器c a m ( c o n t e n t a d d r e s s a b l em e m o r y ) 又称为关联存储 器，是一种新型存储器技术，它的高速、并行和易扩展的特性及实现的灵活性使 它一出现就得到人们的重视。c a m 基于内容寻址，通过硬件电路实现快速匹配， c a m 的并行处理特性使得它在数据分选领域倍受青睐，被广泛应用于以太网网 址搜寻、数据压缩、模式识别、高速缓存、高速数据处理、数据安全和数据加密 等等。另外，c a m 的出现也为军用信号处理( 尤其是雷达截获系统信号处理) 领 域提供了新的思路。但是，由于c a i v l 的实现是以牺牲硬件资源为代价的，常规 的f p g a 器件只能实现很小规模的c a m ，因此，以前的c a v l 都是专用器件。 且规模较小，使用灵活性较低。随着f p g a 器件门数的增加和结构的改进，以及 p 库的不断丰富，基于f p g a 的c a v l 实现已成为可能。尤其是1 9 9 9 年底和 2 0 0 0 年初a l t e r a 公司和x i l i n x 公司相继推出a p e x 和v i g t e x 系列超大规模 f p g a ，使得利用f p g a 实现大规模c a m 的时机趋于成熟。 c a m 是一种专门为快速查找数据地址而设计的存储器。c a m 通过把输入数据 与其内部所存储的数据同时相比较，能快速确定输入数据是否与其内部某个数 据或几个数据相匹配。c a m 的数据寻址方式因要求不同而不同，最快方式下仅需 要一个时钟周期便可完成对所有数据的寻址。与r a m 一样，c a m 也是采取阵列式 数据存储，其数据单元的写入方式与r a m 是差不多的，但c a m 的数据读取方式 却不同于r a l 。c a m 可以看作是逆r 删，在r a m 中，输入的是数据地址，输出的是 数据，而在c 心中输入的是所要查询的数据，输出的是数据地址和匹配标志 ( m a t c h ) ，若匹配( 即数据搜寻到) ，则输出数据地址。在r a m 中，r 栅的存储 容量由地址线宽度所确定。例如，l o b i t 宽地址总线的r a m 存储容量为1 0 2 4 个 单元，c 黼却没有这个限制，因为它不是采用传统的通过地址读取数据的方式。 如要从1 0 2 4 个字节中查询某一数据，输入数据宽度为8 b i t ，若数据存在，则 输出匹配标志和l o b i t 宽的数据地址。因为c a m 不是采用传统的地址线模式读取 数据，存储空间可以很容易地扩展，输入数据线宽度只由需查询的数据位数决 定。图5 为数据读取模式下的r a m 和c 删的比较。 第三章入侵检测系统的同络包分类算法 图5r a m 与c a h i 读取模式比较 f i g 5r e a dm o d ec o m p a r a s i o no i lr a ma n dc a m c a m 的数据查询速度远远高于r a m ，因此c a m 大量应用于需要高速数据处理 的系统之中。c a m 的出现也加快了一些系统和技术的应用，如大型数据库管理， 数据链接、模式识别等在图像识别、语音识别中的应用。c a m 的核心为存储单元 阵列和存储单元与输入数据之问的比较器。具体不同的应用对c a m 的速度、密度 有不同的要求，c a m 实现途径也是多样的。 2c a m 的读写 以a l t e r a 生产的a p e x 系列芯片为例，介绍c a m 的读写原理。 ( 1 ) 数据写入： 由a p e x 的e s b 构成的c a m ，其数据写入有两种方法：一是在初始化时写入， 另外也可在系统工作过程中写入。在大多数情况下，每个字节只需两个时钟周期 就可写入。在本论文的设计中，数据的写入基本是在初始化时就写入，即使用m i f 文件对c a m 进行内存初始化，其具体的实现在4 2 中有详细的介绍。 ( 2 ) 数据输出： c a m 的数据输出只能是三种的其中一种：单匹配模式( s i n g l e m a t c hm o d e ) 、 多匹配模式( n 砌l t i p l e - m a t c hm o d e ) 以及快速匹配模式( f a s t - m a t c hm o d e ) 。单 匹配只用于无重复数据在匹配，其它两种模式主要用于有重复数据的匹配。 ( 3 ) 多匹配模式和快速匹配模式的区别： c a m 中的每个e s b 中，是3 2 字( w o r d ) x 3 2b i t s ，e s b 分为两个模块，每个模块 1 6 字。e s b 在每个周期中只能输出1 6 字。多匹配模式中，e s b 用两个时期输出3 2 字。但是在快速匹配模块中，e s b 只利用其前1 6 字，后1 6 字丢弃不用，因此，每 次只要用一个周期就能输出e s b 中的数据。不过，在快速匹配模式中，e s b 的利用 率只有原来e s b 的一半。 下表是三种匹配模式的单个e s b ( 3 2 字x 3 2 ) 各种情况的对比。 蕈三章入侵检一系统的胃络包分娄算法 匹配模式e s b 使用个数l e 使用个数 m ( m h z ) e s b 使用率( ) 单匹配模式 1 3 51 9 8 8 9 1 0 0 多匹配模式 l 9 89 4 4 5 9 9 快速匹配模式 lt 9 1 9 0 9 1 5 0 表1 三种匹配方式在资源使用和速度的比较 t a b 1c o m p a r i n gt h r e em a t c hm o d eo nr e s o u r c eu s e da n ds p e e d 在每一种模式中，数据所在的c a m 的地址输出分为编码输出和非编码输出。 编码输出时，e s b 输出数据所在地址的二进制编码，例如，将数据存储于地址1 2 ， 那么e s b 输出为1 2 。当非编码输出时，在两个以上的时间周期内，e s b 使用其1 6 个输出显示数据的位置。在这种情况下，如果数据存放在地址1 2 ，则第1 2 根输出 线变高。当使用非编码输出时，需要两个时问周期读取输出，因为要用1 6 位的输 出总线显示3 2 个字的状态。编码输出更适合于写入c a m 存储空间中无重复数据。 如果同一数据写入两个地址，那么c a m 的输出将不正确。如果c a m 可能包含重复数 据，那么非编码输出将是一个更好的解决办法。在非编码输出当中，为了得到数 据的地址，a 1 t e r a 的a p e x 2 0 k c 系列芯片都设计有一个编码器( p r i o r i t y ) ，该编码 器用于将非编码的输出信号进行编码，将数据的地址将储于m a d d r e s s 【 中。因此， 当在c a m 里有重复数据时，也能够得到数据所在内存的编码地址。 从以上分析知道，无论是哪种匹配模块，其匹配速度都是比较快的，最快的 只需要1 个时钟周期就能得到一个匹配，最慢的也只需要2 个时钟周期，正是因 为c a m 有这种特征，所以，在速度要求比较高的的应用上，都使用c a m 来作为匹 配器。在分类当中，也用c a m 来进行分类。如高速网络的路由器的路由表转发。 3 三态内容可寻址寄存器t c a m t c a m 是在c a m 的原有的功能上，加上了一个不关注( d o n tc a r e ) 项，用 x 表示。在t c a m 中，如果模式串中有个比特是x ，则无论其所要匹配的 比特串中，无论该位置上的比特是0 还是。1 ，该位置上的比特都和模式 串上相应位置上的比特是匹配的。该功能最主要是用于前缀的匹配上，也用于模 式串是a n y 的匹配上。 使用t c 斓作为组件，可以对表示为精确值以及前缀字段进行分类。如s n o r t 规则中的协议号就属于比较精切的字段，源i p 地址、目标i p 地址是用前缀表示 的，也可以用t c a m 来检测。 无论是t c a m ，还是c a m ，都有一个缺点，那就是不支持范围的匹配，如7 9 - 8 0 这样的模式串，t c a m 就不能直接匹配，而是要将范围化为前缀才能匹配。 t c a m 的这种缺点，决定了它在模式串为范围的情况下，需要寻找另外的方 1 ， 簟三章入侵检测系统的同络包分类算法 法来实现。 3 4 2b y ( b i tv e c t o r ) 算法 t c a i i 算法在非范围字段的匹配能取得较高的速度，在i d s 头部的匹配中， 有端口范围的匹配，这就不能单单用t c a m 进行匹配，文献 8 都指出的解决办法， 算法比较好的有t c a m + b v 及其改进算法t c a m + b i t m a p ，即：对利用t c a m 对精确 字段和前缀字段进行匹配，对有范围的字段则使用b v 算法或t r e eb i t m a p 进行 匹配。b v 算法和t r e eb i t m a p 算法是基于比特操作的硬件技术。以表1 为例， 讨论b v 算法原理。 li | )s o u r c el p 1 ) l i n a t i o nl pp n 谴is o u r v ep o r ti ) t i n a t i o ap o r t il i w1 9 21 6 80 0 ，1 6 t o p 1 0 2 ；l2 5 s 9 2a n v1 9 2 1 l j # j f ，1 6 t o p 1 0 1 0 1a l i v 3r1 9 2 j 6 s 5 ( i 2 ，j ? t c p a l n 4 ，1 3 毒1 9 2 1 6 8 ，0 o ，1 6 a n yu d p ，i 蚴粥f i ) 删 5 a n y a n y t o p i 哇l v1 1 0 6 钏吣 a i 拶 t c p 1 + 1 6i x 鼢：1 3 0 0 表26 个规则首部的集合 t a b 2s i xr u l eh e a d e rs e t ( 1 ) 首先将端口范围表示转化为前缀表示。 如规则中的端口范围 = 1 0 2 4 ，其转化后的