（计算机科学与技术专业论文）面向网络预警的并行模式匹配方法研究.pdf

国防科学技术大学研究生院硕十学位论文 摘要 网络预警系统是实现网络安全主动防护的重要工具。网络预警系统基于网络 安全态势感知信息，其中入侵检测系统是网络安全态势感知信息的重要来源，但 现有入侵检测系统的性能难以满足现实要求。模式匹配是入侵检测系统的性能瓶 颈所在。为提高入侵检测中模式匹配的速度，人们从不同角度开展了大量研究工 作，但是仍有许多问题没有得到解决。本文综合考虑了性能与成本的因素，深入 研究了入侵检测系统中的模式匹配问题，工作的主要内容和创新点包括： l 、研究了当前针对入侵检测系统进行模式匹配加速的四种基本方法，并对这 些方法的优缺点和适用范围进行了评价与比较。 2 、从课题的背景出发，对s n o r t 进行了性能瓶颈分析。首先利用工具g p r o f 获取了s n o r c 运行过程中各函数消耗的时间以及函数间的调用关系等信息；同时设 计实现了一个对源码结构自适应的性能分析辅助工具和一个以图形化方式展现特 定函数调用关系的工具。分析结果证实，在s n o r t 中，模式匹配消耗的时间占总处 理时间的一半以上，是系统性能瓶颈所在。 3 、提出了一种基于g p u 的并行模式匹配方法。该方法将模式集划分与文本 划分结合起来，采用更为有效的数据访问和数据管理方式，同时探讨了其中的负 载均衡问题，以实现快速的模式匹配。实验表明，该方法相比c p u 上的实现有较 大的提高，加速比约为7 。与另一种在g p u 上的实现g n o r t 相比，在模式集合更 大的情况下也有一定优势。 4 、提出了一种基于缩减模式集的预过滤方法。根据统计分析的结论，使用长 度为2 字节的模式子串做为过滤模式的候选集合。然后给出缩减候选集合问题的 o 1 整数线性规划形式，再利用l i n g o 软件来求解。在s n o r t 的模式集合上进行的 实验表明，通过优化，过滤模式集合大大缩减，同时提高了过滤率。 5 从网络预警系统的需要出发，构建了网络安全态势信息收集平台。首先探 讨了平台的总体架构，给出了现有原型系统的基本情况。然后分别描述了平台中 入侵检测预处理模块和基于入侵检测的态势信息收集模块的实现。 主题词：网络预警，模式匹配，性能瓶颈分析，图形处理单元，预过滤，安 全态势信息收集 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t n e t w o r ke a r l yw a r n i n gs y s t e m ( n e w s ) i sa l li m p o r t a n tt o o lf o ra c t i v ed e f e n c eo f n e t w o r ks e c u r i t y n e w si sb a s e do nn e t w o r ks e c u r i t ys i t u a t i o na w a r e n e s s ( n s s a ) ， a n di n t r u s i o nd e t e c t i o ns y s t e m ( i d s ) i st h em o s ti m p o r t a n ts o u r c eo f n s s ai n f o r m a t i o n h o w e v e r t h ep e r f o r m a n c eo fc u r r e n ti d s si sn o ta sg o o da sr e q u i r e d t h eb o t t l e n e c k l i e s i np a t t e r nm a t c h i n g al o to fw o r kh a sb e e nd o n eo nt h ep r o b l e mo fp a t t e r n m a t c h i n gf o ri n t r u s i o nd e t e c t i o n y e tt h e r ei ss t i l lal o to fs p a c el e f tf o ri m p r o v e m e n t i n t h i sp a p e r , w ef o c u so nt h e p r o b l e mo fp a t t e r nm a t c h i n g f o ri d s s t h em a i n a c h i e v e m e n t sc a l lb el i s t e da sf o l l o w s 1 f o u rd i f f e r e n tw a y st oa c c e l e r a t ep a t t e mm a t c h i n ga r es u r v e y e d a n dt h e i r a d v a n t a g e sa n dd i s a d v a n t a g e sa r ea n a l y z e da n dc o m p a r e di nd e t a i l 2 a na n a l y s i so fs n o r t sp e r f o r m a n c eb o t t l e n e c ki sc a r r i e do u t t h et o o lg p r o fw a s u s e dt op r o f i l et h er u n n i n gt i m eo fe a c hf u n c t i o na n dt or e c o r dt h er e l a t i o n s h i po f f u n c t i o nc a l l sd i s c o v e r e da tr u n t i m e m e a n w h i l e ，a l la s s i s t a n tt o o lf o rp e r f o r m a n c e p r o f i l i n gw a sd e s i g n e da n di m p l e m e n t e d ，a n da ng r a p h i c a ld e s c r i p t i o nt o o lf o rt h e r e l a t i o n s h i po ff u n c t i o nc a l i sw a sp u tf o r w a r d t h ee x p e r i m e n tr e s u l t ss h o wt h a ti ns n o r t m o r et h a nh a l fo ft h ep r o c e s s i n gt i m ew a sc o n s u m e db yp a t t e r nm a t c h i n g ，w h i c hi st h e p e r f o r m a n c eb o t t l e n e c k 3 ag p ub a s e dm e t h o df o rp a r a l l e lp a t t e r nm a t c h i n gi sp r o p o s e d t 1 1 i sm e t h o d c o m b i n e sp a t t e ms e tp a r t i t i o na n dt e x tp a r t i t i o nt o g e t h e r ，e m p l o y sam o r ee f f e c t i v ew a y o fd a t aa c c e s sa n dd a t am a n a g e m e n t a tt h es a n l et i m e t h ei s s u eo fl o a db a l a n c i n gi s d i s c u s s e dt o o t h ee x p e r i m e n tr e s u l t si n d i c a t e sa7t i m ea c c e l e r a t i o nc o m p a r e dt ot h e c p ui m p l e m e n t a t i o n u n d e rt h ec o n d i t i o nw i t hal a r g ep a t t e ms e t o u rm e t h o di sb e a e r t h a na n o t h e rg p ub a s e dm e t h o do n o r t 4 ap r e - f i l t e r i n gm e c h a n i s mb a s e do nt h er e d u c t i o no ff i l t e r i n gp a t t e r ns e ti s p r o p o s e d a c c o r d i n gt oo u rs t a t i s t i c a la n a l y s i s ，2b y t es u b - p a t t e r na r eu s e da sp r e - f i l t e r k e y w o r dc a n d i d a t e s t h e nt h eb i n a r yi n t e g e rl i n e a rp r o g r a m m i n gf o r m a t i o no ft h e k e y w o r dr e d u c t i o np r o b l e mi sg i v e n t h eo p t i m i z a t i o nl c a d st oad e c r e a s e ds i z eo f f i l t e r i n gp a t t e r ns e t ，a n dt h ef i l t e rr a t i oi si n c r e a s e d 5 t h ep l a t f o r n lo fi n f o r m a t i o nc o l l e c t i o nf o rn e t w o r ks e c u r i t ys i t u a t i o n a w a r e n e s si sd e s i g n e da c c o r d i n gt ot h er e q u i r e m e n t so f n e w s s t h ea r c h i t e c t u r eo ft h e p l a t f o r mi sp r e s e n t e df i r s t ，t h e ns o m ed e t a i l sa b o u tt h ep r o t o t y p es y s t e mi sr e v e a l e d t h e p r e p r o c e s s i n gm o d u l ef o ri n t r u s i o nd e t e c t i o na n dt l l ec o l l e c t i o nm o d u l eo fs i t u a t i o n a w a r e n e s si n f o r m a t i o nf o ri n t r u s i o nd e t e c t i o nb a s e da r ed e m o n s t r a t e dt o o k e yw o r d s ：n e t w o r ke a r l yw a r n i n g ，p a t t e r nm a t c h i n g ，p e r f o r m a n c e b o t t l e n e c ka n a l y s i s ，g p u ，p r e - f i l t e r i n g ，s e c u r i t ys i t u a t i o ni n f o r m a t i o nc o l l e c t i o n 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1 基于不同平台的方案的比较7 表2 1 f l a tp r o f i l e 信息的组成字段1 3 表2 2 在i n s i d e t c p d u m p 上的评测1 4 表2 3 在o u t s i d e t c p d u m p 上的评测1 4 表2 4g p r o f 产生的c a l lg r a p h 形式1 7 表2 5 调用图中节点的定义1 7 表2 6 调用关系图缩减算法。1 8 表2 7d o t 图生成算法19 表3 1 b p s p m l e n g t h 算法3 0 表3 2 吞吐率的比较3 3 表4 1二字节a s c i i 字符串出现概率统计：3 6 表4 2 不同过滤模式的数目3 9 表4 3 预过滤效果3 9 表5 1过滤模式对应的t i l e 的构造方法4 6 表5 2 针对预过滤优化的匹配方法4 7 第1 v 页 国防科学技术大学研究生院硕士学位论文 图 图 图 1 2 3 图2 1 图2 2 图2 - 3 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图4 1 图5 1 图5 2 图5 4 图5 5 图5 6 图5 7 图目录 n v i d i ag e f o r c e6 8 0 0 g t 结构示意图3 p i x e l s n o r t d e 的1 6 路并行匹配4 g 8 0g p u 的结构示意图5 g p r o f 产生的f i a tp r o f i l e 信息1 3 k p r o f 产生的调用图1 3 m a k e f i l em o d i f i e r 11 ； s n o r t m a i n 相关的调用函数图1 9 c p u 与g p u 峰值浮点运算能力的比较2 2 c p u 与g p u 存储器带宽比较2 2 c p u 与g p u 的结构差异2 3 g 8 0g p u 的硬件模型2 3 h p s m m 方法2 6 四个g p u 的情况2 7 s n o r t 和c l a m a v 模式长度分布情况统计3 2 在s n o r t 模式集上进行的实验3 2 在c l a m a v 模式集上进行的实验一3 2 负载均衡实验的效果比较3 3 基于子串的预过滤器框架3 7 态势感知信息来源4 1 面向预警的信息收集平台总体架构4 2 平台中网络信息的配置4 4 平台中主机信息的维护一4 4 平台中n s s a s 服务器的配置维护4 4 平台中态势感知探测器的配置维护。4 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同- - r - 作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者张羁远壅日期砷年，z 月力日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 乒 莎 叼 刀 沙 选蹲酶 国防科学技术大学研究生院硕士学位论文 第一章绪论 随着i n t e m e t 应用的急剧增长，网络的安全形势日趋严峻和复杂，网络预警系 统是实现主动防范的重要工具【1 1 。网络预警系统是基于网络安全态势信息感知的， 入侵检测系统是网络安全态势信息的重要来源【2 1 ，然而现有入侵检测系统的性能难 以满足现实要求。当前实用的入侵检测系统主要采用模式匹配技术，模式匹配技 术往往成为入侵检测系统的性能瓶颈。因此，快速模式匹配技术的是当前的研究 热点【3 捌。 1 1 1 网络预警的意义 1 1 研究背景 网络技术的迅猛发展，尤其是i n t e m e t 的广泛应用，深刻地改变了人们工作、 学习和生活的方式。计算机网络已经成为人类社会的基础设施。网络新应用不断 涌现，网络的规模不断扩大、速度不断提高，在极大的方便人们获取和共享信息 的同时，也使网络安全面临着更大的挑战。 根据 2 0 0 8 年中国互联网网络安全报告 1 0 】所做的调查，大陆地区外有多达 9 8 2 3 0 个主机地址参与控制我国大陆被木马植入的计算机，与上年同期相比增长 2 6 4 。其中中国台湾( 6 5 ) 、美国( 8 ) 的木马控制端数量位居前两位。网络安全 已不再是单纯的网络所面临的问题，而是关系到国家安全和社会稳定的重要因素。 它涉及到政治、经济、文化等社会生活的各个方面。 然而，传统的计算机网络安全工具，如单纯的入侵检测系统、防火墙、防病 毒软件已经不能满足新形势下网络安全的需求。网络预警技术旨在能够根据当前 网络的运行状态及时预警可能发生的网络攻击行为，对网络攻击行为的危害程度 进行判断，并提供相应的应对建议【1 1 1 ，从而为实现主动防御、最大限度地减少网 络攻击造成的危害提供重要依据。 1 1 2 网络预警需要高速入侵检测 网络预警是基于网络安全态势信息感知的，而网络入侵检测系统( n i d s ) 产 生的告警事件是一类最为重要的网络安全态势信息【1 2 】。n i d s 通过实时地抓取网络 中的所有报文，对报文进行分析，判断出网络或主机是否受到某些特定攻击，并 能识别相应的攻击类型，发出告警信息、记录相关证据。 网络预警系统一般要求在全网范围内部署大量的安全态势信息探测器，然后 第1 页 国防科学技术大学研究生院硕七学位论文 对不同探测器获得的数据进行关联、融合，进而进行全局性的分析、评估，以获 得网络安全态势的全网视图。探测器的性能高低直接影响到态势视图的完整性和 准确性。因此，作为一类重要的安全态势信息探测器，n i d s 的性能必须能跟上网 络预警的要求。 1 1 3 高速入侵检测需要快速模式匹配 随着网络技术的不断发展，网络的速度越来越快，这对n i d s 的性能提出了很 高的要求【1 3 1 。目前实用的绝大多数n i d s 是基于模式匹配技术的，模式匹配的性 能直接影响着n i d s 的性能和效率。以s n o r t 1 4 1 为例，模式匹配占用的时间约为 4 0 7 0 t 1 5 】，可以说模式匹配部分是n i d s 的性能瓶颈所在。因此提高模式匹配 的速度对改进n i d s 的性能有重要意义。 1 2 研究现状 当前，有许多工作围绕如何加快模式匹配的速度以提高n i d s 的性能展开研 究。根据技术路线的不同，大致可分为四类：基于专有硬件技术的快速模式匹配 技术、基于网络处理器的快速模式匹配技术、基于g p u 的快速模式匹配技术和基 于预过滤的快速模式匹配技术。 1 2 1 基于专有硬件技术的快速模式匹配技术 加速模式匹配的早期研究致力于设计更高性能的软件算法【1 6 。2 6 1 ，然而基于软 件的方法在通用处理器上最快只能达到1 0 0 k b p s 左右暖7 1 ，不能满足现实需求。为 了达到更快的速度，一些研究者基于f p g a t 2 ”0 1 、t c a m t 3 1 。3 3 】等专有硬件设计解决 方案，使吞吐率能达到g b p s 的水平。 一些基于f p g a 的技术将模式集合编译成自动机后存放于片上【2 8 瑚j ，以进行 匹配，但在n i d s 中模式数量很多，由此产生的自动机占用空间很大，无法在片上 存储，因此还需要额外的存储器，然而对片外存储器的访问具有很高的延迟。为 解决这一问题，相关工作提出使用b l o o mf i l t e r t 3 4 弓6 1 ，基本思路是先利用片上的 b l o o mf i l t e r 判断是否可能产生匹配，若确有可能匹配才去访问外部存储，从而提 高处理效率，此类方法适用于匹配发生的概率较低的情况。其缺点是b l o o mf i l t e r 的引入可能使得产生误报。 另一类技术是使用三相内容寻址存储器( t c a m ) 。t c a m 是一种能够进行并行 查找的高速存储器，它包含多个表项，每个表项可存储一个模式串，允许匹配、 不匹配、未知三种状态【3 3 1 。输入的每个字符串都可并行地与t c a m 中每个表项存 第2 页 国防科学技术大学研究生院硕士学位论文 储的模式进行比较。相关工作讨论了模式长度不一以及模式长度超过t c a m 字长 时如何进行处理。基于t c a m 的方法的主要缺点是其功耗大、代价昂贵。 1 2 2 基于网络处理器的快速模式匹配技术 网络处理器由若干微处理单元和一些硬件协处理单元组成，通过软件控制处 理流程，不同处理单元并行工作。网络处理器具有处理速度快、可编程、可扩展 等特点，被认为是推动下一代网络发展的核心技术【37 。在i n t e l 等厂商的支持下【3 8 】， 一些大学和研究机构以多核网络处理器为平台，对高速模式匹配技术及其在深度 检测中的应用进行了深入研刭3 9 - 4 3 1 。 网络处理器是专为网络应用而设计的处理器，它将c p u 的廉价、灵活和专有 硬件的高速结合在一起 4 4 1 。有关在网络处理器上实现快速模式匹配的研究，主要 从三个方面进行：一是从模式匹配算法的角度出发，结合网络处理器的结构特性 进行优化【4 5 4 。7 】二是从网络处理器提供的硬件多线程机制出发，分析最大限度利 用多线程的方式【3 9 ，4 8 ，4 9 ；三是从网络处理器内多个微引擎m e ( m i c r oe n g i n e ) 并行 的角度出发，进一步提高性能 4 6 ，5 0 , 5 1 】。 1 2 3 基于g p u 的快速模式匹配技术 g p u 是近几年学术界和工业界研究和讨论的热点。自1 9 9 9 年n v i d i a 公司提 出g p u 的概念以来【52 。，g p u 的发展速度要远远高于c p u 。g p u 一般由多个流处 理器构成，具有很强的浮点运算能力和很高的存储带宽以及高度的并行性【5 3 1 ，可 用于处理大流量的网络数据。 早期g p u 的结构是专为图形处理应用设计的，主要由顶点处理器v p ( v e a e x p r o c e s s o r ) 和分片处理器f p ( f r a g m e n tp r o c e s s o r ) 等构成【5 训。用此类g p u 进行模式匹 配，需要将模式匹配中的算法和数据结构进行为对图形的操作和各种图元，使之 能在g p u 上运行。此过程十分复杂，往往以算法过程和数据结构相对简单的k m p 算法【2 4 】、w u - m a n b e r 2 0 j 算法等为基础进行算法的设计。 一输入数据 图1 1 n v i d i ag e f o r c e6 8 0 0 g t 结构示意图 第3 页 国防科学技术大学研究生院硕士学位论文 j a c o b 等提出p i x e l s n o r t p 川，他们使用的g p u 为n v i d i ag e f o r c e6 8 0 0 g t ，该 g p u 的结构如图1 1 所示。初始化阶段，p i x e l s n o r t 将所有模式字符串编码，然后 写入一个规则纹理，使得纹理的每一行对应一条规则，然后将生成的纹理传送至 g p u 。匹配阶段，假设有n 个规则串，则对每个输入报文编码并生成n 个拷贝写 入报文纹理。6 8 0 0 g t 同时运行1 6 个f s ( f m g m e n ts h a d e r ，是指在f p 上运行的程 序) 对数据进行并行的处理，每个f s 都运行k m p 算法，实现1 6 路的并行匹配， 如图1 2 所示。匹配结果由f p 写入到帧缓存并传回c p u 。最好情况下p i x e l s n o r t 的模式匹配部分的性能比s n o r t 要高8 5 t 5 5 】。 报文纹理 2 5 4 7 7 4 9 2 4 2 5 4 7 7 4 9 2 4 2 5 4 7 7 4 9 2 4 2 5 4 7 7 4 9 2 4 分片处理器规则纹理 口 口陌霄萌丽丽 ! 卜一2 5 4 9 5 8 6 9 5 口 卜l 萌秆硒诬 9 5 6 9 6 8 3 21 图1 2p i x e l s n o r t d e 的1 6 路并行匹配 h u a n g 等一些研究者借鉴w u - m a n b e r 算法【2 0 l 的思想，结合g p u 的特性，实现 了基于g p u 的多模式匹配算法 5 6 j 。h u a n g 使用的g p u 结构与图1 1 所示类似，用 到的数据结构主要为：哈希过滤纹理h t ( h a s ht e x t u r e ) 、模式纹理p t ( p a t t e m t e x t u r e ) 、报文纹理p k t ( p a c k e t t e x t u r e ) 。h t 的主要作用是利用类似于哈希的方法， 快速过滤不可能的匹配，加快匹配过程。p t 以纹理元素的形式存放模式的i d 、长 度和模式内容。p k t 存储报文内容，大小固定为1 5 1 8 字节，大于最长报文的长度。 在匹配时，每个f s 每次读入报文的3 个字节x y z ，如果x y z 是某个模式的前 缀，那么通过h t 可以得到所有前缀为x y z 的模式在p t 中的位置，再逐个字符进 行精确匹配；如果只剩下两个字节x y ，那么直接利用h t 和x y 的哈希值得到对应 模式的i d 或不存在对应模式的信息。c p u 和g p u 之间的数据交互是通过o p e n g l 来实现的。h u a n g 方法获得的最高吞吐率为2 8 0 m b p s 5 6 】，是当时的s n o r t 版本中采 用的m w m 方法的3 倍。 新一代g p u 如n v i d i a 的g 8 0 系列包含多个多处理器m p ( m u l t i p r o c e s s o r ) ， 每个多处理器又包含多个流处理器s p ( s t r e a mp r o c e s s o r ) ，每个流处理器可支持多 个线程并发执行【5 。新的体系结构能更好地支持通用计算，再加上g p u 通用编程 模型c u d a 5 3 】等的出现，使得g p u 上的编程更加灵活，从而能够以结构和操作更 复杂的算法如a h o c o r a s i c k 算法【2 6 】为基础进行模式匹配。这类g p u 的结构简单示 意图可如图1 3 所示。 第4 页 国防科学技术大学研究生院硕士学位论文 v a s i l i a d i s 等对s n o r t 进行修改，提出g n o r t ，在g p u ( n v i d i ag 8 0 ) 上实现基 于a h o c o r a s i c k 算法的多模式匹配【5 8 l 。g n o r t 将a h o c o r a s i c k 算法中的有限状态自 动机( f s a ) 以二维阵列( 两个维数分别为状态数和字母表大小) 的形式存放。f s a 驻留在g p u 的纹理存储器上，利用其c a c h e 的特性减少访存时间。在搜索阶段， g n o r t 提出两种并行方案：一是用一个m p 搜索一个报文，每个报文被3 2 等分， 每个线程处理一个部分。为防止遗漏可能的匹配，在划分处多往后检查m 个字节， 其中m 为最长模式的长度；二是每个线程搜索一个报文。实验结果表明，这两种 方案的性能差别不大。在模式数目为1 0 0 0 ，报文大小为1 5 0 0 字节时，g n o r t 能达 到2 3 g b p s 的吞吐率【5 引。 图1 3g 8 0 g p u 的结构示意图 1 2 4 基于预过滤的快速模式匹配技术 在入侵检测的问题中，网络流量中攻击流量的比例往往很小。因此，有相关 研究者根据这一点提出基于预过滤的快速模式匹配技术，即分步进行模式匹配， 先快速地过滤一些正常流量，然后对剩余的可疑流量再进行进一步的检查。 m a r k a t o s 使用一个两步的方法【5 9 】：该方法先检查输入流是否包含了模式中所 含有的所有字符，如是则进行完全匹配，由于每个字符的出现概率都不低，因此 这种方法的过滤效果很不理想；后来他们又对此进行改进，提出了p i r a n h a t 6 0 】：从 每个模式中抽取出最不常出现的4 字节子串，形成过滤模式集合，并将匹配分两 步进行，首先将输入文本与过滤模式集合进行匹配，如果不能匹配上的话，则无 第5 页 国防科学技术大学研究生院硕士学位论文 需进行下一步；若发生了匹配，则要进一步检查是否与某些特定的模式相匹配。 此方法的主要缺陷是产生的过滤模式集合相对较大，从而导致预过滤的效率远没 有预期的理想。 中南大学的彭诗力等提出字符串特征值的概念，希望利用字符串特征值来进 行预过滤恂。他们使用字符串的异或值来表征其特征值，其基本思想是把正文中 字符串的特征值与等长模式字符串的特征值相比较，若不相等则两个字符串肯定 不匹配，从而实现了预过滤。该方法的主要问题是特征值的计算代价过大，在模 式集合很大时，预过滤的开销超出可承受的范围。 s o u r d i s 等提出预过滤的过程中应将报文头部信息考虑进去，即预过滤过程应 同时包含对报文头部和报文负载的过滤，从而使得能和一个报文匹配上的模式数 目大大减小阻，6 3 1 。对报文头部，该方法使用了源地址、目的地址和协议类型作为 过滤字段；对报文负载，该方法使用模式的前缀作为过滤字段。通过预过滤，使 得每个报文只需要与少数规则进行匹配。该方法的有效性严重依赖于硬件能否快 速确定要进行匹配的规则，也是一种开销比较大的方法。 1 2 5 评价与比较 基于专有硬件技术的方法具有最高的性能，但是其适应性和可扩展性差，更 重要的是其代价昂贵，而在面向预警的应用中，需要大量部署探测器结点，性价 比是必须要考虑的因素。 多核技术的兴起带来了新思路，尤其是多核的网络处理器n p ( n e t w o r k p r o c e s s o r ) 和图形处理器g p u ( g r a p h i c sp r o c e s s i n gu n i t ) 的快速发展使得性价比高、 通用性强、扩展性好的解决方案成为可能。基于网络处理器和基于g p u 的方法都 有较好的适应性和可扩展性，价格也比基于专有硬件技术的方法低。 为了有效对比不同方案的性能和技术优势，本文提出吞吐率价格比的指标【1 3 】。 吞吐率价格比定义为：吞吐率价格比= 吞吐率峰值平台价格。 从上式可知，若平台价格一定，吞吐率价格比越大则所能获得的吞吐率峰值 越大；若吞吐率峰值一定，吞吐率价格比越大则平台价格越低。因此，吞吐率价 格比大的实现方案更适合大规模应用。 表1 1 对比了吞吐率峰值表现较好的几种实现方案的吞吐率价格比【l 引，可以看 出基于g p u 的实现方案具有更高的吞吐率价格比。面向预警的应用需要在网络中 大量部署n i d s 作为探测节点，同时对单个节点的处理能力要求并不特别高，因此 这时选择吞吐率价格比高的g p u 是更合适的选择。 除了在吞吐率价格比方面的优势，在实际部署的时候，g p u 也有其特别的优 点。g p u 即通常我们所说的显卡，现在一般的p c 机都配有显卡，因此对部署无 第6 页 国防科学技术大学研究生院硕士学位论文 特别要求，可以使用普通的p c 机接入网络的冲突域作为探测器节点。网络处理器 一般以专有设备的形式出现，不但价格高，而且还面临着复杂的管理问题。 表1 1 基于不同平台的方案的比较 方法吞吐率峰值平台价格吞吐率价格比 a cm t t 4 驯 6 7 g b p s $ 5 0 0 1 3 4 m b p s $ p m c t 1 j 4 - 1 2 g b p s $ 5 0 0 8 - 2 4 m b p s $ g n o r t t 5 硼 2 3 g b p s $ 8 0 2 8 7 5 m b p s $ 基于上述原因，本文选用g p u 作为研究并行模式匹配方法的平台。 预过滤方法的基本思路是将模式匹配分两个阶段进行：在第一阶段，快速过 滤掉肯定不匹配的内容；剩余内容在第二阶段中进行完全的模式匹配。预过滤方 法的有效性依赖于两个方面的因素：一是被过滤的网络流量的比例，二是预过滤 引入的开销大小。现有的预过滤方法要么是过滤效果不理想，要么是预过滤的开 销太大。本文以有较好的过滤效果和较低的开销为目标对预过滤问题进行研究。 1 3 研究内容 本文着重研究了面向预警的并行模式匹配方法：首先对著名的开源入侵检测 系统s n o r t 进行了性能分析，用实际数字证明模式匹配是入侵检测系统的性能瓶颈； 然后基于支持c u d a 的g p u 设计了一种并行模式匹配方法，该方法结合文本划分 和模式集划分的策略，并对相应的负载均衡问题进行了讨论；利用0 1 整数线性规 划设计了基于缩减模式集的预过滤方法以进一步提高模式匹配的效率。还讨论了 网络预警系统的子系统面向预警的网络安全态势信息收集平台的构建。 1 3 1 入侵检测性能瓶颈分析 n i d s 的基本工作机制是通过接入网络的探针获取网络报文，并对报文进行分 析和处理。为确定n i d s 的性能瓶颈所在，采用m i t 林肯实验室入侵检测数据集， 利用工具g p r o f 对著名的开源入侵检测系统s n o r t 进行性能分析。 工具g p r o f 的主要功能是：打印出程序运行中各个函数消耗的时间，帮助程序 员找出最耗时的函数；产生程序运行时的函数调用关系，帮助程序员分析程序的 运行流程。基本使用方法是使用p g 选项编译和链接要分析的程序，然后运行程序 产生相应的p r o f i l i n g 信息。现实中遇到的问题是，s n o r t 由许多模块组成，而不同 模块被组织在不同的子目录下，手动修改编译和链接选项将是一项浩大、繁琐的 工程。论文设计并实现了一种自适应的性能瓶颈分析辅助工具，实现对源码目录 第7 页 国防科学技术大学研究生院硕士学位论文 结构复杂的程序的编译和链接选项的自动修改。为了形成性能瓶颈的完整视图， 不但要找出最耗时的函数，还需弄清与该函数相关的函数调用关系，g p r o f 产生的 信息中已经包含有对函数调用关系的记录，但是是以文本方式给出的，不易于分 析和理解。论文设计并实现了一种图形化的调用关系描述工具，实现对g p r o f 产生 的函数调用关系信息的图形化显示。 1 3 2 基于g p u 的并行模式匹配方法研究 通过性能瓶颈分析证实了模式匹配是n i d s 的性能瓶颈所在，并明确了相关细 节。新一代的g p u 是一种性价比很高、能力较强的并行处理平台。利用g p u 实 现快速并行模式匹配，可以满足预警中高速、廉价的要求。由于n i d s 具有模式数 目较多、长度不一的特点，如果利用a c 算法等基于自动机的匹配方法，编译模式 后产生的自动机占用的空间是g p u 难以承受的。自动机的大小与其包含的状态数 成指数关系，将对应于一个大自动机的模式集合划分为若干个小模式集合有利用 降低空间消耗，同时可以在并行处理的情况下增加数据访问的局部性，从而提高 处理性能。 论文考虑综合使用模式集划分和文本划分的方法来利用g p u 提供的并行性， 提出了一种基于g p u 的并行模式匹配方法，同时讨论了使用该方法时的负载均衡 问题。 1 3 3 基于缩减模式集的预过滤方法研究 通常情况下，网络中的流量大部分都是正常流量，采用预过滤的方法可以快 速过滤掉相当部分的正常流量，从而减轻进行完全模式匹配的压力。常见的预过 滤方法是利用模式的一部分即模式子串来是实现快速过滤。现有的方法包括利用 前缀、后缀等作为过滤子串。 论文针对现有方法中过滤子串过多的特点，提出缩减过滤模式集合，给出了 模式集缩减问题的0 1 整数线性规划形式，希望找出一个尽可能小的过滤模式集 合：该集合能够覆盖所有的模式，同时其中所有模式的平均出现概率尽可能低。 实验表明，本方法能够有效地缩减过滤模式集合，并提高预过滤处理的效果。 1 3 4 面向预警的网络安全态势信息收集平台的构建 网络预警系统是基于网络安全态势信息的，网络安全态势信息可分为静态信息 和动态信息。静态信息包括网络拓扑、主机运行的服务、主机漏洞信息等。动态 信息可来自n i d s 、流量分析系统。论文面向预警的主要需求，设计了网络安全态 第8 页 国防科学技术大学研究生院硕士学位论文 势信息收集平台，讨论了该平台中的入侵检测预处理模块和基于入侵检测的态势 信息收集模块的实现细节。 1 4 研究成果 论文围绕面向预警的并行模式匹配方法进行了相关研究，主要创新点包括： ( 1 ) 提出了一种基于g p u 的并行模式匹配方法。 给出基于g p u 的并行模式匹配框架，在m p 的层次上引入模式集合划分，提 高在m p 内进行匹配时数据访问的局部性，在每个m p 的s p 内部引入文本划分， 通过每个s p 同时处理文本的某一段来开发并行性。通过两个不同层次上使用不同 的方法，充分利用了g p u 的并行性，同时部分解决了现实中模式集合过大带来的 效率降低的问题。 ( 2 ) 提出了一种经济的g p u 上负载均衡方法 g p u 不善于处理分支和控制程序，因此其上的负载均衡策略应尽可能简单， 否则将会大大影响处理性能。对于一个m p 内的s p 而言，其负载均衡问题可直接 由文本的平均划分解决，而文本的平均划分可通过合理计算访问下标实现；对于 一个g p u 内的m p 来讲，其负载均衡问题可以归结为模式子集合之间的相似性问 题，为了使问题尽可能简单，采用静态的负载均衡方法，先对模式集合按长度排 序，然后再按r o u n d r o b i n 的方式分派模式集合。在匹配过程中，模式子集不发 生任何变化。 ( 3 ) 提出了一种基于缩减模式集的预过滤方法。 基于预过滤的思想，提出使用模式子串进行预过滤。与基于前缀和后缀的方 法相比，基于子串的方法有更多的优化空间。利用不同模式可能共享子串这一点 进行过滤模式集合的缩减。给出了模式子串集缩减问题的0 - 1 整数线性规划形式， 大大减小了过滤模式集合规模。 ( 4 ) 设计了面向预警的网络安全态势信息收集平台。 提出了面向预警的网络安全态势信息收集平台的总体架构，给出实现情况。 将基于缩减模式集的方法应用于入侵检测预处理模块，并讨论了入侵检测信息收 集模块的实现。 1 5 论文结构 本文的研究始终围绕面向预警的并行模式匹配方法，论文共分为6 章。 第一章为绪论，介绍了课题研究的意义和背景。概述了基于不同技术路线的 快速模式匹配技术的研究现状，并进行了评价与比较。提出了论文的研究内容， 第9 页 国防科学技术大学研究生院硕士学位论文 并总结了本文的贡献。 第二章讨论了入侵检测性能瓶颈分析及相关辅助工具的研制。选定g p r o f 作为 性能瓶颈分析的主要工具，分析了对s n o r t 进行性能瓶颈分析需要解决的问题。针 对s n o r t 源码目录结构复杂的问题，设计并实现了一个根据源码目录结构自适应修 改编译和链接选项的辅助工具；针对g p r o f 产生结果不直观的问题，设计并实现了 一个图形化的调用关系描述工具。 第三章研究了基于g p u 的并行模式匹配方法。分析了模式匹配问题本身存在 的并行性和g p u 从结构上提供的并行性，同时针对基于自动机的模式匹配算法在 处理大模式集合时存在的问题，提出在m p 的层次引入模式集划分、在s p 的层次 引人文本划分，从而最大限度地利用各种并行性。分析了在利用并行性的过程中 的负载均衡问题，分别针对模式集划分和文本划分提出了相应的负载均衡策略， 并通过实验验证了方法的有效性。 第四章提出了基于缩减模式集的预过滤方法。通过分析指出，要实现高效地