（计算机软件与理论专业论文）现代体系结构上的网络入侵检测系统：基于多核和simd的方法.pdf

摘要 摘要 随着互联网的快速发展，越来越多的政府机构、企q p 和个人将自己的计算机 连接到互联网上，电子政务，电子商务正成为。个潮流，网络安全系统成了网络 体系结构中不可或缺的重要部分，网络入侵检测系统作为网络安全系统的基础设 施，已经成为维护网络安全的重要工具之一。传统的网络入侵榆测系统由于性能 方面的限制无法应用到高速网络中。本文的主要目的就是要利用现代计算机体系 结构的一些新特征来加速网络入侵检测系统中的检测引擎，使得在高速网络中， 网络入侵检测系统也能够很好地工作。 本文首先考察了网络入侵检测系统的基本结构，详细讨论了检测引擎所使用 的两大类型算法的特点，然后深入研究了现代体系结构的两个重要特征：多核和 单指令多数据流，结合检测引擎算法的特点，考察了利用这两个特征来加速检测 引擎的可行性。接下来从下列三个方面进行展开。 第一，在多核平台上，使用规则集分解的方法，实现检测引擎多核化，提 出了使得每个核上的负载均衡化的规则集分割算法，然后讨论了检测引擎算法内 存访问的特点，提出了基于单指令多数据流指令集而实现的高速缓存替换算法， 并且使用双缓存方法来重叠检测计算和内存访问，降低检测引擎的内存访问开 销，最大化检测引擎的并行度。 第二，在算法控制流并行的基础上，使用单指令多数据流指令集对入侵检 测引擎进行指令集级的并行化，针对单指令多数据流指令的向晕寄存器和对齐内 存访问两个特性，设计了新的模式串集合数据结构重排算法，这种重排的结构大 幅度地降低了向量化的检测引擎的内存访问开销。 最后，针对网络中的一类特殊的流量：压缩流量的检测，提出了不对流量进 行完全解压缩，直接在压缩流量中进行搜索匹配的新算法，新算法利用压缩过程 中的已经产生的编码信息来减少检测匹配过程中的重复搜索，同时针对该算法实 现中的散列数据结构访问提出了基于单指令多数据流指令集的高速散列查找算 法。 关键词： 入侵检测；多核；s i m d a b s t r a c t a b s t r a c t a sm o r ea n dm o r eg o v e r n m e n t sa n di n d i v i d u a l sc o n n e c t e dt h e i rc o m p u t e rt o i n t e r a c t e - g o v e r n m e n ta n de - b u s i n e s sh a db e e nb e c o m i n gm o r ea n dm o r ep r e v a l e n t w i t hd e v e l o p m e n to fi n t e r a c t ；n e t w o r ks e c u r i t ys y s t e mh a db e c o m ei n d i s p e n s a b l e c o m p o n e n to fn e t w o r ka r c h i t e c t u r e n i d s 州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 ) b e c o m e st h ec o r ei n f r a s t r u c t u r eo fc o r p o r a t ei n f o r m a t i o ns e c u r i t y , i tb e c o m eak e y t o o l o fn e t w o r ks e c u r i t y h o w e v e r , t r a d i t i o n a ln i d sc a n n o ta p p l yt oh i g hw i r es p e e d n e t w o r kb e c a u s eo ft e c h n i c a lr e s t r i c t i o n s t h ee s s a ya i m sa ta c c e l e r a t i n gt h ed e t e c t i o n e n g i n eo fn i d st h r o u g hm a k i n gu s eo fm o d e ma r c h i t e c t u r ec o m p u t e r ss o m en e w f e a t u r e s i tm a k e sn i d sc a nw o r kw e l la th i g hw i r es p e e dn e t w o r k s t h ee s s a yr e v i e w e dt h ef u n d a m e n t a ls t r u c t u r e so fn i d sf i r s t l y ；d i s c u s s e dt w o t y p e so fa l g o r i t h m su s e di nd e t e c t i o ne n g i n e ；t h e ns t u d i e dt w oi m p o r t a n tn e wf e a t u r e ， m u l t i c o r ea n ds i m d o fm o d e ma r c h i t c c t i l r ec o m p u t e r c o m b i n e dw i t ht h ef e a t u r e s o fd e t e c t i o ne n g i n e s ；w es t u d i e dt h ef e a s i b i l i t yo fa c c e l e r a t i n gt h r o u g ht h et w o a r c h i t e c t u r e sf e a t u r e s t h e nw ec i r c u m s t a n t i a t e dt h eb o d yo ft h ee s s a yi nt h r e e a s p e c t s f i r s t l yw ed i v i d e dt h er u l e ss e to fn i d sw h i c hm a d et h ed e t e c t i o ne n g i n ec o u l d w o r ko nm u l t i p l ec o r e sp l a t f o r m t h er u l e ss e tp a r t i t i o na l g o r i t h mf o rb a l a n c i n gt h e o v e r l o a do f e a c hc o r ew r i t sp r o p o s e d t h e nw es t u d i e dt h ef e a t u r eo fm e m o r ya c c e s so f d e t e c t i o ne n g i n e ，i n v e n t e dal o c a lc a c h es u b s t i t u t i o na l g o r i t h mb a s e do ns i m d i n s t r u c t i o n ss e t , o v e r l a p p e dt h ed e t e c t i o nc o m p u t i n ga n dm e m o r ya c c e s sv i ad o u b l e b u 疵r a l lt h e s ee n h a n c e m e n t sd e c r e a s e do v e r l o a do fm e m o r ya c c e s sa n dm a x i m i z e d t h ep a r a l l e l i s mo f d e t e c t i o ne n g i n e s e c o n d l yw ep a r a l l e l e dt h ed e t e c t i o ne n g i n ea ti n s t r u c t i o n s s e tl e v e lt h r o u g h s i m da f t e rt h ep a r a l l e la l g o r i t h mc o n t r o lf l o w n e wd a t as t r u c t u r e so fp a t t e r n ss e t r e a r r a n g e m e n ta l g o r i t h mw a sp r o p o s e dt h r o u g hd e e p l ys t u d y i n gs i m di n s t r u c t i o n s a n dm e m o r ya l i g n m e n ta c c e s sf e a t u r e t h er e a r r a n g e m e n to fp a t t e m ss t r u c t u r e d r a m a t i c a l l yr e d u c e dt h eo v e r l o a do fm e m o r y a c c e s so fd e t e c t i o ne n g i n e f i n a l l yan o v e lc o m p r e s s i o n f o r m a tb a s e dp a t t e r nm a t c h i n ga l g o r i t h m i s p r o p o s e d i tc o u l dd e t e c tt h ec o m p r e s s e dd a t as t r e a mw i t h o u tt h en e e do fd e c o m p r e s s t h ed a t as t r e a mc o m p l e t e l y t h ea l g o r i t h md e c r e a s e dt h er e p e t i t i o ns e a r c ho fd e t e c t i o n m a t c h i n gw i t hu t i l i z i n gd i s t a n c ec o d ei n f o r m a t i o nw h i c hg e n e r a t e di nc o m p r e s s i o n i n a b s t r a c t t h i sa l g o r i t h m si m p l e m e n t a t i o nw ep r o p o s e da ns i m db a s e dh i g hs p e e dh a s hs e a r c h a l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mr e d u c e dt h e c o m p u t i n go v e r l o a da n dt h e ni m p r o v e dt h r o u g h p u td r a m a t i c a ll y k e yw o r d s ：i n t r u s i o nd e t e c t i o n ；m u l t i - c o r e ；s i m d 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人 在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标 明。本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) ：攻_ 降 i 妒j 年j 月胡同 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 1 保密( ) ，在( ) 年解密后适用本授权书。 2 不保密( ) ( 请在以上相应括号内打“ ) 作者签名：砭卅降日期：知玩年卜月硼日 导师卿昧日期少万年r 月坫日 m t 镕镕构1 h 镕 惶幢w 幕统，盱多# 目s i m d 自 第一章绪论 1 1 网络入侵检测系统与现代体系结构概述 随着电子商务的发展，越来越多的商业组织将其核心业务转移至忸联网上， 网络入侵事件、计算# 哺毒每年都给这些组织带来了巨额损失网络安全已 经成为一个无法回避的问题被提到人们面的。网络入侵检测作为网络安争系统 的核心近年来已经成为工、界_ 手口学术界研究的热话题。 图l 入侵检测的工作原理 1 i 1 网络入侵检测系统的工作原理 网络入侵检测系统( n c 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 ) ，简称n i d s 。如 图l 所示，n i d s 的基本j ：作原理是嗅探，在关键的嘲段或交换部位侦听，将 网卡设置为混杂模式，使得嘲卡可以接收网络接口上的所有数据，它是一种旁 路监听网络数据的技术。在实际的部署中，n i d s 是升联在网络中。通过旁路 监听的方式实时地监视网络中的流量，l 可时判断其中是否含有攻击的企圈，通 过并种手段向管理员报警，不但可以发现从外部的攻击，也可以发现内部的恶 意行为，其中攻击意酬通过规则集来表达。实际r 嗅探就是从网络的数据流中 查找匹配规则集中任何规则的流量当检测到匹配时印是检洲到威胁时，大多 一彦 、塞一f 参 第一章绪论 数入侵检测系统会采取，系列的措施。这些描施可以是自动或于工进行，包括 本地的、远程的操作及通告。 概要地讲，一个嘲络入侵检测系统主要组件模块包括：抓取数据分组模块、 多模式匹配模块、规则集合、报警模块。抓取数据分组模块负责从网络中获取 数据分组，在可能的情况下，把数据分组组合成为数据流：多模式匹配模块负 责匹配规则集和数据流，检测流量中是否存在威胁；规则集合是预先定义好的， 根据各种威胁的特征构建的一个数据库；报警模块是当匹配模块发现威胁时调 用用来向片j 户报告威胁的存在。 1 1 2 现代体系结构的主要特征及其对n i d s 影响 近年来，处理器的时钟频率一再提高，甚至英特尔公司宣称可以达到1 0 g h z 或更高，但是在这种情况下，功耗大的问题4 直没有好的解决方案，芯片制造 商被迫停止兆赫兹方面的竞赛，而纷纷开始转向多核处理器技术。由于其在功 效、成本及其他方面的优势，多核正在从早期的接纳阶段慢慢成为主流技术， 甚至普通的个人计算机也配备了多核处理器。另一方面，单指令多数据流的向 量处理单元这种以前只有在高性能计算机上才有的特性，现在就连最普通的微 机也具备了诸如m m x 2 1 ，s s e2 3 2 1 ，a l t i v e c 【3 】这些向量操作指令集。 传统的入侵检测系统由于无法利用或者没有利用现代体系结构的这些新特 点，而使得其性能较差，无法适应实际高速网络应用的需求。因此充分利用现 代体系结构的新特点来提高入侵检测系统的性能是一个急需解决的问题。 1 2 网络入侵检测系统的主要技术难点 入侵检测就是通过捕获网络上传输的数据进行实时分析来检测是否存在入 侵行为的，这种做法对系统的开销极大。因此，入侵柃测系统对硬件性能要求 极高。很多商业产品的推荐配置都是当前最好的硬件环境。尽管如此，入侵检 测系统在处理高速网络数据时仍然非常困难。 当前网络入侵检测系统正面临着一些严重的挑战，其中主要的挑战包括在 高速网络上由于检测引擎的计算能力相对低下i n j 丢失待检测的数据分组，数据 分组经过了加密或者压缩，检测引擎无法直接对分组进行检测等问题。采h j 新 现代体系结构上的嘲络入侵检测系统：基于多核和s i m d 的方法 的方法提高入侵检测引擎的速度是解决这些问题的。种重要的方法，这将直接 关系着入侵检测系统的发展前景。 1 2 1i n t e r n e t 链路速度的急速增长 当网络速度【4 】增加时，数据分组会丢失。在一个1 0 m b p s 的网络上可能不会 出现任何问题，但是当网络速度达到1 0 0 m b p s ，甚至i g b p s ，这时可能会丢失 许多需要检测的数据分组。数据分组的丢失能掩盖外部人员的入侵行为。例如 入侵者可以发送大= 阜= 的分组，超过了入侵检测系统的处理能力，从而使得被监 听的端口流量总和超过临听端口的上限，会发生分组丢失，这就口j 能导致入侵 行为漏报。 1 2 2 规则集合越来越大 据文献1 5 j ，在2 0 0 0 年到2 0 0 6 年期间有超过2 6 0 0 0 个不同的系统脆弱性被 报道。这些脆弱性都是系统安全的隐患，都是任何一个安全系统需要关心的。 s n o r t 6 j 作为最有名的一个基于规则的网络入侵检测系统，其规则集合在2 0 0 3 年6 月只包含1 5 0 0 条规则，而到了2 0 0 6 年6 月则包含5 0 0 0 条以上的规则。更 重要的是，各种新的系统漏洞还在不停地涌现，攻击方法不断地推陈出新，所 以网络入侵检测系统使用的规则集合将会变得越来越大，而更为糟糕的是，这 种趋势未来的一段时间内还没有什么好的解决办法使之得以扭转。 1 2 3 加密和压缩在实际网络中的广泛应用 入侵检测系统所使用的基本方法是搜索网络分组载荷，在其中查找规则集 中的模式是否出现。如果有效载荷被加密过了，那就无法检测出任何模式。而 加密在网络的各层都很常见，例如s s l t l s e7 】传输层安全协议，网络层的虚拟 专用网络v p n ，甚至某些应用层也进行加密。这些都给网络入侵柃测带来严重 的影响，当前的大多数网络入侵检测系统对加密的数据流来说几乎毫无价值。 对于压缩9 1 的流黄也有类似的问题，入侵检测系统如果要对压缩流晕进行 检测，就需要首先对流最解压缩，然后才能进行检测。而解压缩操作需要大量 的运算，是一种计算和输入输出都十分密集的操作，对系统资源的占用很大， 1 第一章绪论 这样使得入侵检测系统的性能问题更加突出。 1 3 论文的主要内容及结构 本论文的各章节内容安排如下： 第一章为绪论，高度概要地介绍了入侵检测系统的基本结构，现代体系结 构对入侵检测带米的影响以及入侵检测系统当前亟待解决的问题。 第j ：章介绍了网络入侵检测系统的核心算法多模式匹配算法的调研综 述。文中分别调研了两种典型多模式匹配核心算法，并对两类算法做出了仔细 的分析和比较。然后对现代计算机体系结构中的一些新特点进行了综述。最后 为了伞面地测量入侵检测系统的件能，文巾也调研了两种入侵检测的基准测试 程序并简要地分析了其特点与使用方法。 第三章阐述了对模式集合进行划分，利用多线程技术来提升入侵检测系统 在多核体系结构上的性能。提出了自己的模工弋集合划分方法，并从负载均衡角 度对该划分方法和普通的随机划分方法进行了对比测量。 第四章提出了入侵检测引擎针对s i m d 向量化指令集进行优化的算法，同 时由于s i m d 的优化方法又会对模式集合的划分产生影响，所以提出了针对 s i m d 优化的模式集合划分方法，本章最后对几种情况进行了性能测罱比较。 第五章对于压缩流晕的匹配提出了自己的新算法，充分利用压缩过程中的 行程编码结果来最大限度地减少重复计算匹配的开销，为了验证算法的有效性， 文巾以l i n u x 内核代码中的几个长度不同的关键字为例进行了性能测量。 第八章对本文的工作进行了总结，并对进步的工作提出了建议和设想。 现代体系结构上的网络入侵检测系统：苯于多核和s 1 m d 的方法 2 1 入侵检测系统 第二章相关工作与文献调研 入侵检测系统，顾名思义，就是用于检测可能存在的入侵行为。它通过对计 算机网络或计算机系统中若干关键点收集信息并对其进行分析，从中发现网络或 系统中是否有违反安全策略的行为和被攻击的迹象。更重要的是，入侵检测系统 检测并发现存在的网络攻击以及网络错误。安装在网络中的入侵检测系统就如同 一个房间中安装的用于防止盗贼的防盗报警器。能发现网络中的非法入侵行为， 并根据相应的情况发出警告或者报警。 入侵榆测系统监视、检测并对网络中未经授权的活动和外部入侵行为进行响 应。入侵检测系统通过策略来确定事件的性质，一旦发现有与预先定义的策略相 一致的行为，入侵检测系统就会报警。换句话说，如果一个行为与入侵检测系统 定制的策略是一致的，那么这个行为就会被入侵检测系统检测到，并作为一个安 伞事件进行响应。入侵检测系统响应的方式是向管理员发送警告，当入侵行为发 生时，入侵检测系统的管理员就会收到町能发生了入侵事件的一个页面通知、电 子邮件或s n m p 消息通知。某些入侵检测系统不仅能检测入侵事件，也能自动响 应事件，针对特定的入侵事件执行一系列的操作。这些操作包括将事件涉及的用 户帐号从网络中注销，禁用该帐号或者执行一个脚本程序，避免入侵对服务器造 成危害。 入侵检测系统分为如下几类【川： 1 网络入侵检测系统，这是通过分析网络主机之问网线上传输的信息 来工作的。 2 基于主机的入侵检测系统，这种系统是被设计用于监视、检测对于 主机的攻击行为，通知用户并进行响应，这种入侵检测系统通常部 署在被检测的主机上。 3 混合的入侵检测系统，这是上述两种系统的结合，能实现对入侵行 为的全方位检测。 近年来由于入侵检测系统市场的飞速发展，许多公司和研究机构都投入到这 气 第二章相关工作j 文献调研 ，领域中来，虽然出现了- 些较好的入侵检测系统产品，但是入侵检测目前还缺 乏国际标准，试图对入侵检测系统进行标准化j l ：作的有两个组织：i e t f 的 i n t r u s i o nd e t e c t i o nw o r k i n gg r o u p ( i d w g ) s t l c o m m o ni n t r u s i o nd e t e c t i o n f r a m e w o r k ( c i d f ) ，但是进展十分缓慢，尚没有正式标准出台。 典型的网络入侵检测系统的体系结构由数据包嗅探器，预处理器，检测引擎 和报警输出模块组成。如图2 所示： 图2 典型的入侵检测系统结构图 数据包嗅探器是一个并联在网络中的设备，它的工作原理与电话窃听类似， 它是整个入侵检测系统的数据入口；预处理器是通过分析数据包，从中发现这 些数据的“行为”，原始数据包的应用层表现是什么，数据包经过预处理后才发 送给检测引擎；检测引擎根据预先设定好的规则检测数据包，一旦发现数据包 中的内容和某条规则相匹配，就通知报警模块；报警模块产生报警信息，这些 信息会通过网络、u n i xd o m a i ns o c k e t 、w i n d o w sp o p u p ( s m b ) 或s n m p 协 议的t r a p 命令送给日志文件，报警信息也可存入s q l 数据库中。 2 2 多模式匹配算法【”i 经过性能测量发现检测引擎在整个代码执行路径中占用了7 0 至8 0 的处 理时间，而检测引擎的核心就是一个多模式匹配算法，检测引擎通常提供用户配 置文件，可以对使用哪种多模式匹配算法进行配置。多模式匹配算法的性能关系 到整个入侵检测系统的性能，本节考查了几种在现代入侵检测系统中常用的多模 式匹配算法。 通常多模式匹西己算法是对相应的单模式匹配算法进行扩展而得到的，它对一 6 现代体系结构上的嘲络入侵检测系统：摹于多核和s i m d 的方法 组字符串p = p 1 ，p 2 ，p 3 ，p r ) 在待匹配数据流中进行搜索，其中p 。是定义在有限 字母表上的字符串，p 中的- 些宁符串可能是集合中其他字符串的子串、前缀、 后缀，或者完全相等，记l p l 为p 中所有宁符串的长度之和，记i m i n , 币l j i m a x 分别为p 中最短模式串的长度和最长模式串的长度，搜索在文本t = t l t 2 t 3 t n 上进行，多模 式匹配就是找出所有满足下列条件的所有二元组( i ，j ) ： t j i p l i + i t j = p 1 如图3 所示，这是一个在数据流中同时搜索三个字符串“a n n o u n c e ”，“a n n u a l ” 和“a n n u a l l y ”的例子： 待匹配数据： 模式串集合： 图3 多模式匹配实例：在数据流中同时搜索三个字符串 2 2 1 基于自动机的多模式匹配 自动机是计算机科学中一个常用的概念，a h o c o r a s i c k 算法就是利用自动 机来进行多模式匹配的，它是k m p 算法向多模式串情形的扩展，著名的u n i x 应 用程序g r e p 就是使用该算法的，a h o c o r a s i c k 算法使用模式串集合p 来生成自动 机，称为a h o c o r a s i c k 自动机。下面简要描述这种算法的匹配过程。 假设已经读入文本的前缀t l t 2 t i ，而既是t l t 2 t i 的后缀，同时也是某个模式 串的前缀的最长字符串对应于a h o c o r a s i c k 自动机的c u r r e n t 状态，记这个最长字 符串为v = l ( c u r r e n t ) 。当读入一个新字符t i + 1 并计算t l t 2 t i t i + 1 的新的最长后缀u 时，可能出现如下两种情况： 1 如果状态c u r r e n t 存在标号为t i + l 的转移，目的状态为c 那么粥成为 新的c u r r e n t 状态。并且，u = l ( f ) = u t i + l 是t i t 2 t i t 的最长前缀， ，f。j。l 第一：章相关工作j 文献调研 机。 同时也是某个模式串的前缀。 2 如果状态c u r r e n t 不存在标号为t 的转移，即无法在t r i e 树上继续识 别字符t l + l ，那么就沿着c u r r e n t 的路径回溯，直到： a ) 找到一个状态q ，它存在标号为t i + l 的转移。那么q 的t i + l 转移的目的 状态戚为新的c u r r e n t 状态，并且u = l ( f ) 。 b ) 如果到达空状态，那么说明要查找的最长后缀u 是空字符窜o o ，于是 从c u r r e n t 跳转到初始状态。 图4 是对应于模式串集合p = a b ，b a ，b a b b ，b b 而构造的a h o c o r a s i c k 自动 图4a h o c o r a s i c k 自动机 在开始时，按照上述规则，从图中的初始状态开始移动，只需要对待匹配的 字符串进行一次扫描即可完成匹配算法，找出所有的匹配。 a h o c o r a s i c k 算法有一个严重的缺点，当模式串数量越来越多时，达到儿千 个时，这在一般的检测引擎中是非常常见的，a h o c o r a s i c k 自动机需要巨人的存 储空间。它的空间复杂度是o ( i ixl p l ) ，而且该复杂度与转移的实现方式无关。 虽然现代的计算机都配备了很大容量的内存储器，但是当模式串数量达到一万以 上时，模式串平均长度为1 6 m ，需要4 g 以上的内存，这就已经达到一般低端服 现代体系结构上的网络入侵检测系统：基于多核和s i m d 的方法 务器的上限了，即使对于拥有人内存的服务器，由于内存访问体系结构方面的问 题，也会使得大量内存需求程序的内存访问速度较慢。a h o c o r a s i c k 算法的这个 缺点制约了它的应用范同，它只能用于模式串集合较小的情况下并且字母表也较 小的情况，当然有一个折中的处理方式可以部分地解决这个问题，先不构造这些 新的转移，而是在匹配过程中，发现还有足够的存储空问时构造这种新的转移， 这种以时间换空间的做法在一个实时性要求很高的入侵检测引擎中并不实用。 2 2 2 基于散列分类的多模式匹配 多模式匹配的模式串集合中包含许多不同的模式串，使用散列函数对模式串 集合进行分类是一种很自然的方法，虽然这样会引入散列函数计算的开销，但是 只要保证散列函数的计算开销比较小就不会对性能产生影响，因为通过这种分 类，在匹配到数据流中某处时，需要查找的模式串只局限在模式串集合的某子集 当中，极大地缩小了需要查找的范罔，使得计算开销大幅度地减少。这种基于散 列的算法中设计一个好的散列函数就至关重要，对模式串进行分类的散列函数好 坏的评价标准和其他处使用的散列函数标准也一样，首先必须比较均匀，碰撞尽 可能小，其次散列函数本身的计算开销不能太大，否则会抵消散列分类带来的性 能增益。 w u m a n b e r 算澍”i 是一种典型的基于散列的多模式匹配算法，该算法是在 b o y e r - m o o r e t l 4 】单模式匹配后缀搜索算法基础上加上散列方法而派生的多模式 匹配算法，文献【1 3 】中对原始算法的描述相当模糊，既没有说明如何计算算法 中需要的几个表格，也没有说明如何选择合适的散列函数，在实际应用中，只 要参数选择得当，这个算法的速度是相当快的。下文中对该算法的详细描述是 基于s n o r t 系统中的w u m a n b e r 算法的实现，该实现的主要数据结构如图5 所 示，由一个对各个模式串进行描述的结构数组、一个散列表和一个字符移动距 离数组所组成。 算法开始运行前，需要把所有的模式组织到一个称为m w m 数据结构中， 根据每个模式的前两个字节构建一个散列表，散列表中的每项指向模式数组中 的索引，这样在查找时，就可以根据散列值找到需要开始匹配的模式，然后对 具有相同散列值的模式串逐个模式进行比较。 第二章棚荚工作j 文献调研 在匹配时，首先根据待处理的字符串前两个字节计算出散列值，根据此散 列值在散列表中查找，如果对应项为0 ，说明没有模式串能够匹配当前的字符 串，如果彳i 为零就顺着该索引一直比较。该算法主要优点是事先经过散列，使 得匹配入口点较少，减少了比较的次数，同时引入了b o y e r m o o r e 单模式匹配 算法中的坏字符规则，使得匹配过程中可以根据字符移动距离数组跳过不需要 进行比较的字符，进一步减少了比较的次数。 图5 一种散列分类算法的典型数据结构 作为一种基于散列的算法，其性能十分依赖于散列函数的设计，当散列函数 让所有的模式串都产生碰撞时，w u m a n b e r 算法就退化成为对模式串集合中的每 个模式运行单模式匹配算法，性能增益为零。在实际应用中这种情况并不多见， 所以w u m a n b e r 算法由于其平均速度快而得到广泛的应用。在s n o r t 的实现中是把 待匹配的字节和下一个宁节拼接起来，作为一个1 6 位的整形数，这个整形数直接 作为一个6 5 5 3 6 项数组的索引，这个数组实际上存储了一个指针，指向同样散列 值的模式串予集合。显而易见w u m a n b e r 算法所需要的额外存储空问也并不大， 除了存储各模式串本身的信息外只需要一个的散列表来保存模式串集合的分组 信息，并且散列表大小并不会随着模式串集合的增大而增大。 2 2 3 压缩格式数据中的模式匹配【1 5 】 压缩格式数据上的搜索问题是指在不解压缩或者不完全解压缩的基础上找 现代体系结构上的嘲络入侵检测系统：摹于多核和s i m d 的方! ：主= 出模式串在压缩数据中的匹配位置。在数据压缩算法中，有两人类，其+ 是使用 数宁信号处理技术实现的有损压缩，多用于图像，音频和视频等的压缩；另一类 是无损压缩，主要用于那些小能容忍信息丢失的领域，例如可执行二进制文件， 程序或其他文本文件。这些无损压缩算法中最流行的有：h u f f m a n 1 6 】( 文本中的 每个符号被变长的编码取代，出现频率越高的符号编码长度越短) 、z i v l e m p e l ( 对丁文本中当前位置的字符串，编码器使用指向前面已经出现的该字符串的指 针来代替) 。l z 7 7 _ 算 去1 1 7 是z i v l e m p e l g 法t 1 8 1 的一个重要的变体，和z i v l e m p e l 算法相比它不对重复字符串在前面出现的位置加以限制。l z 7 7 用途极其广泛， u n i x 下的g z i p i 具就是使用该算法，遵循r f c1 9 5 2 中阐述的压缩算法压缩的网 络流量也是使用该算法，因此使得入侵检测引擎能够对经过l z 7 7 算法压缩的数 据进行匹配检测具有重要的实际应用意义。 压缩匹配问题是f 1 3 a m i r 着l ：i b e n s o n 在文献【1 9 】中首次提出的，目的是直接在压 缩文本中进行字符串匹配而不需要解压缩。给定文本t = t l t 2 t t i ，相应的压缩字 符串为z = z l z 2 z 。，模式串为p = p l p 2 p m ，压缩匹配问题就是只使用p 和z ，找 出p 在t 中的出现的所有位置。一种很明显的算法就是首先对z 进行解压缩，然后 使用经典的模式匹配算法，然而这种算法由于需要解压缩，一方而需要占用大量 的内存或外存空间，另一方面解压缩是一种运算量非常大的操作，这两方面决定 了这种显而易见的算法的存储和计算开销都十分巨大的，在实际系统中是难以应 用的。 已有许多的研究工作是在z i v l e m p e l 的基础上进行的，这种压缩算法具有很 好的压缩率，第，。个基于z i v l e m p e l 压缩上进行精确模式匹配的算法在文献 2 0 中提到，它可以在o ( m 2 + n ) 的时间和空间内对l z 7 8 的压缩文本进行匹配。但是在 l z 7 7 压缩文本上的工作较少，其中一个是在文献【2 l 】中所提到的。对于h u f f m a l l 压缩算法，文献 2 2 】使用了基于词的h u f f m a n 编码( 编码中的单位是文本中的词 和分隔词，而不是字符) 压缩文本，并且支持其上的单模式串的精确和近似匹配。 2 3 现代体系结构的特征 入侵检测引擎总是运行在一定的系统的硬件平台之上的，为了提高检测引擎 的性能，所以不得不考察几种现代体系结构平台的特征，在其巾寻找可以用来提 第二章相芙工作j 文献调研 高检测引擎性能的平台相关的特性。 2 3 1 多处理机系统 用户一直在追求速度更快、史经济的计算机系统。设计人员能够满足这种需 求的一种方法是，通过制造速度更快的单c p u ，从而提高单位时间内能够完成的 处理量。这种方法的缺点是，一旦突破了c p u 性能上的某个阈值，硬件和开发成 本的增长速度就会大大超过由此在c p u 速度卜带来的提高。 多核或称多处理机是由两个或者两个以上的c p u 组合成的单个计算机系统 所构成。采用多处理机的方法后，设计人员代之以采用多个c p u 来缓解制造更高 速度c p u 的需要，于是就可以把工作量分布到所有的c p u 上。在执行任何单一任 务时，多处理机，般不会比单处理机速度更快，因为c p u 的速度是相同的，但是 它可以在单位时间内并行执行更多的任务。简言之，使用多处理器的好处就是提 高性能，缩短解题时间。 从体系结构角度来看，多核结构分为两种：s m p ( 对称的多处理器) 和a s m p ( 非对称的多处理器) ；从内存访问速度一致性角度米看可分为：u m a ( 一致的 内存访问) 和n u m a ( 非均匀的内存访问) 。在对称的多处理器器上，这些处理 器中没有主处理器，操作系统和用户线程可以被调度到任何一个处理器 二运行， 而且所有的处理器共享唯一的内存空间。这种模犁与非对称的多处理器不同，在 一个典型的非对称的多处理器系统中，操作系统选择其中的一个或几个处理器来 执行操作系统内核代码，而其他的处理器只运行用户代码。这两种多处理器模型 的区别如图6 所示。 体镕# t 目镕 系统# f 多棱s i m d0 勺女 非对梅 圈6 对称的多处理器和非对称的多处理器 超线程( h y p c r t h r e a d ) 也是一种多核技术它是i n t e l 日l 入的一项技术，它 可以在一个物理处理器上提供多个逻辑处理器。每个逻辑处理器都有它自己的寄 存器堆有它自己的c p u 状态但是执行引擎和芯片上的高速缓存则是共享的。 这使得一个逻辑c p u 可以在其他逻辑c p u 正忙着的时候继续执行。 下面从内存访问速度一致性来考察体系结构的内存访问特性，一致的内存访 问u m a 是一种较简单的结构在这种结构中每个处理器都可以访问的所有的 内存，并且访问速度都一致；在非致的内存结构n u m a 系统中处理器被组织 成为更小的单元，称为节点。每个节点有它自己的处理器和内存，并且通过一个 缓存一致性的互连总线连接到更大的系统中然而在常见的n u m a 类型系统中。 所有的处理器还是可以访问所有的内存，h 是节点本地的内存访问起来比其他节 点的内存更快一些。如果用户空间的程序需要利用这种特性来提高程序的性能， 那么就必须保证在某个处理器节点上运行的线程的内存分配必须被分配刊节点 内的内存空间中去这在l i n t r 磺操作系统中都有系统调用可以用来完成这个任 务。 2 3 1 单指令多数据渲 为了满足计算密集型的应用，尤其是大规模向量和矩阵的运算在处理器市 第二章相关工作j 文献调研 场上出现了人量的专用的向量处理器，这些处理器通常采用。类特殊的指令，他 们能够把完整的物理寄存器划分为多个子寄存器，并在这几个子寄存器上并行执 行相同的操作。这些类型的指令通常称为单指令多数据流( s i m d ) 指令集，简 单米讲，单指令多数据流是指单一指令部件同时控制多个重复设置的处理单元， 执行同一指令下不i 司数据的操作。基于i n t e l 处理器的m m x ，s s e 2 3 ，基于p o w e r p c 平台的a l t i v e c 羊 i 基于c e l l 2 4 】甲台的v m x 都是一种s i m d 指令集。 - “一r ， 厂 b l o | h 以b 1b 2| ) 0叫b s1 3 6b 7b 8h q l ； 图7 典型的s i m d 操作 如图7 所示，是一种典型的s i m d 指令的操作，s i m d 指令的操作数通常是一 个向量，长度为6 4 位或1 2 8 位，甚至吏长，上图所示的操作数向量是由4 个3 2 位的 整型数组成，操作数和结果都保存在向量寄存器中，只需要在一条指令中，就可 以完成4 对整数的操作。一个向量不仅可以由整型数组成，也可以由8 位字节组成， 1 6 a 立双字节，3 2 位字，6 4 位双字组成，这些组成成分可以是位、字符、整型数或 者浮点数。例如1 2 8 位的向量可以由两个6 4 位的高精度浮点数组成，或者1 6 个字 符串所组成。这样使用1 2 8 位的存储单元，对于3 2 位的浮点数来讲，s i m d 指令的 操作是一次针对4 个浮点数来完成的，这种批处理当然就会带来性能上的提升。 南于s i m d 指令的操作数都是向量，输出结果也是向量，但是检测引擎中算 法操作的基本单元是字符，所以在使用s i m d 来优化检测引擎时，传统的多模式 匹配算法及其数据结构就必须针对s i m d 指令集进行相应的调整。同时s i m d 指令 一般都要求操作数是内存边界对齐的并且是连续的，某些体系结构的s i m d 操作 一 rliliif_li 现代体系结构上的网络入侵检测系统：摹于多核和s i m d 的方法 虽不要求操作数是内存边界对齐的，但是这些指令在操作数是内存对齐的情况下 速度要快得多，这种特性也会对检测引擎的算法产牛重要的影响。 在实际的编程中，程序员一般都彳i 需要直接调用汇编指令，各种s i m d 处理 器的对应编泽器及程序库含有扩展的i n t r i n s i c 支持1 2 5 1 ，程序员可以在代码中显式 地使用s i m d 指令的包装函数和s l m d 数据结构，米指导编译器进行代码优化。当 前某些研究性质的编译器通过编译选项就能够为应用程序进行一定程度的自动 优化，但是这些自动优化目前只能从语言层面，例如循环结构等，来进行程序优 化，对于算法层面上的目前还没有合适的自动优化方法。 2 4 入侵检测引擎的基准测试【2 6 】 基准测试是衡量系统能力和阈值的基本方法。入侵检测系统由于其特殊性， 很难在实际运行的牛产系统上来运行测试。为了对入侵检测的性能进行测量，需 要好的t 具进行基准测试。在当前的市场上能够为入侵检测系统做基准测试的工 具非常的少。这里简要介绍一下本文所用到的两种系统测试工具。 2 4 1i d si n f o r m e r b l a d e 软件公司的i d si n f o r m e r 软件是目前测试入侵检测系统特性和实现的 事实卜的业界标准。它的图形化界面和可配置特色远远优于其他的入侵检测系统 测试工具。 图形化的用户界面为配置i d si n f o r m e r 提供了易于理解的和使用的界面，如 图8 所示，用户可以很容易地配置i p 地址，m a c 地址等选项，还可以配置攻击 的传输速率以及生存时间。 囤8b l a d ei d si n f o r m e r 的配置 配置i d si n f o r m e r 的好处就是用户能够创建町管理的攻击分组，如图9 所示 创建群组使得用户可以预先定义小而易于管理的攻击子集。 2 4 2s