（计算机系统结构专业论文）基于网络处理器的多模式串匹配算法研究.pdf

摘要 摘要 随着计算机网络的迅速普及以及人们对网络越来越强的的依赖性，网络安全 问题尽益突出并引起广泛关注。入侵检测是网络安全系统的一个重要组成部分， 其目的是通过监视和分析网络流量来发现可疑的攻击行为，进而采取有效的防护 措施。目前入侵检测最常采用的方法是先根据各种入侵行为的特点建立一个入侵 行为特征( 数据流中出现的特征字符率) 痒，并为每一种入侵行为关联一个安全 措施，运行时通过在收到的数据包中检查是否存在这些特征字符串来判断是否存 在入馒行势。在数据包中查找入侵特征串使用瓣是模式率匹配技术，研究表瞬模 式串匹配是入侵检测系统中耗时最多的操作。随着网络速度及网络流量的激增， 模式串匹既已成为决定入侵检测系统性能的主要因素。 模式串匹配是一个已经研究了很久的的问题，其应用十分广泛，也已经有很 多算法被提出。根据应用的特点选择合适的模式串匹配算法、进行适应性改造并 在特定平台上高效实现是模式串匹配应用研究的一个重要方面。随着网络速度及 流量的增长，入侵检测面临的压力越来越大。网前基于通用处理器实现的模式串 匹配只能达到l o o m b p s 左右的速度，距离l o g b p s 的鼷络速度还很远，如何提高 模式串匹配的速度是目前亟待解决的难题。网络处理器的出现为以较低的代价实 现高速模式串匹配带来了新的解决方案，僵虽翦基于网络处理器的模式睾匹配研 究开展得还不多。 本文研究适合于入侵检测的模式串匹配算法以及算法在网络处理器上的高 效实现癌对目前使用最广泛的s n o r t 入侵特镬库的统计特性进行分析的基础上， 本文选择f n p 算法作为主要的模式串匹配算法并做了适应性改变，在具有相同 前缀的模式串数量超过一定阙值时将f n p 算法和a c 算法褶结合以改善f n p 算 法在最坏情况下的性能。本文选择i n t e li x p 2 8 0 0 网络处理器作为算法实现的平 台，仔缨磷究了i x p 2 8 0 0 的软硬件体系结构，充分利用其多核多线程的特点对 算法进行了并行化。在i n t e ld e v w o r k b e n c h 仿真平台上对f n p - a c 算法的测试表 明，算法具有很好的扩放性，在l o k 规模的模式串集合上可达到6 g b p s 的吞吐 量，且具有近乎线性的加速比。 关键词：入侵检测，模式串匹配，网络处理器，并行算法 a b s t l a c t a b s t r a c t a l o n gw i t ht h er a p i dp o p u l a r i z a t i o no fc o m p u t e rn e t w o r k ，a n dp e o p l e + sg r o w i n g d e p e n d e n c eo ni t ，n e t w o r ks e c u r i t yb e c o m e sam o r ea n dm o r ec o n s p i c u o u sp r o b l e m a n da t r r a c t se v e ri n c r e a s i n ga t t e n t i o n i n t r u s i o nd e t e c t i o ni sa v e r yi m p o r t a n ta s p e c ti n n e t w o r ks e c u r i t ys y s t e m ，w h o s ea i mi st od e c t e c t s u s p i c i o u sa t t a c kt h r o u g h m o n i t o r i n g a n d a n a l y z i n g n e t w o r kd a t a f l o w , t h e nt a k ee f f e c t i v ed e f e n d i n g m e a s u r e m e n t s c u r r e n t l y , t h em o s tc o m m o n l ye m p l o y e dm e t h o df o ri n t r u s i o n d e m c t i o ni st os e tu pa ni n t r u s i o nr u l el i b r a r y , a s s o c i a t ee v e r yk i n do fi n t r u s i o na c t i o n w i t has a f e t yp r e c a u s i o na n dj u d g et h ee x i s t e n c eo fa ni n t r u s i o nb yc h e c k i n gw h e t h e r t h er e c e i v e dp a c k a g eh a st h ef e a t u r e ds t r i n g 。p a t t e r n m a t c h i n gi st h ew a yt of i n d s t r i n g so fi n s t u s i o nr u l e si nt h ep a c k e t s ，a n dt h er e s e a r c hh a sr e v e a l e dt h a tp a n e r n m a t c h i n gi st h ea c t i o nt h a tc o n s u m e st h em o s tt i m ei ni n t r u s i nd e t e c t i o ns y s t e m w i t h t h es h a r pi n c r e a s eo fb o t hs p e e da n dt h et h r o u g h p u to fn e t w o r k ，p a t t e r nm a t c h i n gh a s b e c o m eac r i t i c a le l e m e n tt oi n f l u e n c et h ep e r f o r m a n c eo ft h ei n t r u s i o nd e t e c t i o n s y s t e m d u et oi t sw i d ea p p l i c a b i l i t y , p a t t e r nm a t c h i n gi sn o tn e wi nt h er e s e a r c hf i e l d ， a n db a t c h e so fa l g o r i t h m sh a v ea l r e a d yb e e np r o p o s e do n i t a m o n gt h e s ea l g o r i t h m s ， o n eo ft h em o s ti m p o r t a n tp r o b l e mi st os e l e c tt h em o s ta p p r o p r i a t e m a t c h i n g a l g o r i t h ma c c o r d i n gt ot h ea p p l i c a t i o nr e q u i r e m e n t s ，t h e nt oa p p l yi to nt h es p e c i f i c p l a t f o r ma f t e rb e i n gm o d i f i e da d a p t i v e l y t h eg r o w t ho fn e t w o r ks p e e da n d t h r o u g h p u th a sa g g r a v a t e dt h ep r e s s u r eo fi n t r u s i o nd e t e c t i o n u pt i l ln o w , t h e s p e e do fp a t t e r nm a t c h i n gb a s e do nt h eg e n e r a lp r o c e s s o rc a no n l yr e a c h10 0 m b p s ， l y i n gf a rb e h i n dt h e10 g b p sn e t w o r ks p e e d t h e r e f o r e ，t h eu r g e n tn e c e s s i t yi st o i m p r o v e t h es p e e do fp a t t e mm a t c h i n g t h ea p p e a r a n c eo fn e t w o r kp r o c e s s o rm a y b eab r e a k t h r o u g hf o rh i g hs p e e do f s t r i n gs e a r c h i n ga tal o wp r i c e ，h o w e v e r ，o n l ya f e wr e s e a r c hh a sb e e nc a r r i e do u tb a s e do nn e t w d r k p r o c e s s o r w es t u d i e dp a t t e r nm a t c h i n ga g o r i t h m sw h i c hi ss u i t a b l ef o ri n t r u s i o nd e t e c t i o n s y s t e m ，a sw e l la sh i g h l ye f f e c t i v er e a l i z a t i o no ft h e mo nn e t w o r kp r o c e s s o r b a s e do n s t a t i s t i c a l a n a l y s i so fi n t r u s i o nr u l si nw i d e s p r e a d l yu s e ds n o r ts y s t e m ，w et a k e o p t i m i z e df n pa l g o r i t h ma st h em a i nm a t c h i n ga l g o r i t h m ，a n dt a k ea ca l g o r i t h m w h e ns t r i n g sw i t hs a m ep r e f i xs u s p a s sc e r t a i nt h r e s h o l dt oi m p r o v et h ep e r f o r m e n c e o ff n pi nt h i sw o r s tc a s e 。t h i sp a p e rc h o o s e si n t e li x p 2 8 0 0n e t w o r kp r o c e s s o ra st h e n a b s t r a c t e x p e r i m e n tp l a t f o r m 。a f t e ri n v e s t i g a t i n g t h ea r c h i t e c t u r eo fl x p 2 8 0 0i nb o t hs o f t w a r e a n dh a r d w a r ea s p e c t s ，t h ep r o p o s e da l g o r i t h r ni sp a r a l l e l e d ，t a k i n gf u l la d v a n t a g eo f i t sc h a r a c t e r i s t i co fm u l t i c o r ea n dm u l t i t h r e a d t h et e s to ff n p a co nt h e s i m u l m i o np l a t f o r md e v w o r k b e n c hs h o w s 饿a t 也ea l g o r i t h mi ss c a l a b l e i ta l s o s h o w st h a tt h ea l g o r i t h m st h r o u g h p u ta c h i e v e s6 g b p sw h e nt h es i z eo fp a r e r ns e t c o m e s u pt o10 k w i t ht h ea l m o s tl i n e a rs p e e d u p 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 r e mm a t c h i n g ，n e t w o r kp r o c e s s o ru n i t s ，p a r a l l e l a l g o r i t h m s i i i 论文原刨性和授权使用声明 本人声明所里交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别力奠以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明簪 本入授权中国科学技术大学拥有学位论文的部分使用权，即；学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： d 鼍年 绪论 1 1 模式串匹配问题 第1 章绪论 模式串匹配是计算机科学中最古老、研究最广泛的问题之一，模式串匹配的 应用也随处可见。自上个世纪七十年代开始对模式串匹配进行深入研究以来，学 术界对串匹配的研究兴趣与日俱增，特别是发展迅速的信息检索和计算生物学领 域。模式串匹配是指在一个已知的有限长度的文本串上，寻找与已知的模式串完 全相等的所有文本串，它的严格定义是： 已知：有限字符集：模式串集合p ：( v 。尸) ( p + ) ；文本t ：，+ 。 求解：o c c u r ( p ，) = ( p ，ixi ) j ( 3 x ) o y ) ( t = x p y ) ，p p ) ，即模式串集合中的模式 串在文本中出现的所有位置。 模式串匹配的应用范围十分广泛，主要应用领域包括入侵检测、病毒检测、 信息过滤、信息检索、生物信息学等。模式串匹配的研究和发展与应用息息相关， 近年来新的应用和需求对串匹配提出了新的要求和挑战。 1 1 1 模式串匹配在安全领域中的应用 随着网络的普及和高速发展，计算机用户遭受恶意攻击的威胁也越来越大。 如何保户用户信息不被窃取、计算机系统不被破坏、网络不被蓄意破坏堵塞，已 经成为个人、公司、政府和研究机构日益重视的问题。 入侵检测是网络安全的一个重要研究方向，其目的是建立一个计算机系统安 全防护机制，防止对计算机系统和数据进行非授权访问。入侵检测最常采用的技 术是活动监视，通过监听和分析用户的活动( 即发送的数据包) 来判断用户的行 为是否合法，并进而采取相应的措施。入侵检测系统预先根据各种入侵行为的特 点建立了一组入侵行为特征模式集合，并为每种入侵行为关联了应对措施，构成 系统的入侵规则集；运行时将收到的数据包与入侵规则集进行匹配，根据匹配的 结果采取相应的措施。将数据包与入侵规则集进行匹配时使用了模式串匹配技 术。随着网络速度及网络流量的激增，模式串匹配速度成为影响系统性能的决定 性因素。据统计，在目前使用最广泛的开放源码的入侵检测系统s n o r t 中，串匹 配时间占去了整个检测时间的7 0 矛d 实时跟踪计算指令的8 0 ( n a l ：h a nt u c k ， 2 0 0 4 ) 。 病毒检测也是模式串匹配的重要应用领域之一。每个病毒检测系统都有一个 绪论 庞大的病毒特征库，病毒检测就是在每一个文件中搜索可疑的病毒特征的过程。 据统计，2 0 0 5 年网络病毒已接近1 0 万种，在裔用的病毒软件系统中病毒库每天 都要更新。面对如此庞大的瘸毒库，串匹配算法的性能成为整个系统性能的关键 和瓶颈。 1 。1 。2 模式串匹配在生物信息学中的应用 目前，人类基因组序列的绘制工作已经完成，国内外均建立了大型蛋自质重 要样本数据库，且这些数据十分庞大。人们不褥不利用计算机技术来存储和辅助 分析这些数据，从而产生了生物学与计算机科学的交叉学科，即生物信息学。 模式警匹配技术在生物信息学中的典型应用是，寻找个或一组基因片段在 个基因序列中的出现位置，以比较基因的相似性和遗传关系；或者根据已知的 蛋白质样本去匹配来知的蛋白质序列，以确定这种未知的蛋白质序歹| j 所属的蛋囱 康幂申类和功能。由于蛋囱质和基因都可以建立在一定字符集上的符合序列来表 示，所以可以借助传统的模式串匹配技术来解决该领域内的匹配问题。 生物学家们在利用这些序列数据的时候，已经不满足予单纯地确定一个给定 的特征串是否出现在数据库中，面是要求在一定的相似性范围内找出特征串在数 据库中的礤现位置。这是因为这些序列数据代表了生命物质的微观结构，是人们 通过试验测量得到的，这就不可避免会引入实验误差和错误。同时，遗传过程中 发生的突变和进化等微小的改变，使得嚣个描述网一物质的正确的序列数据也可 能含有微小的差异。这里，传统的精确模式串匹配已经不能满足应用的要求，生 物学家们需要种具有定容错能力的近似模式串题配技术。 1 t 3 模式串匹配在信息检索中的应用 信息检索是计算机科学的一个应用领域，它是指将信息按定的方式组织和 存储起来，并根据用户的需要我出相关信息的过程。相关性是信息检索的核心， 面对不断积累的海量知识，如何高效地查找所需的信息是人们在学习和工作中无 法回避的润题。 信息检索最早起源于图书馆的参考咨询工俸和书冒工作，詹来随着嚣领域内 信息的急剧增加，信息检索也逐渐普及开来。w e b 搜索弓 擎也是一种索引信息查 询系统，它根据用户提供的关键词快速从数据库中涯配相关的信息并显示给用 户。 1 2 模式审匹配研究现状 2 绪论 模式搴匹配算法按照功辘可以分为三类：精确匹配算法，近似匹配算法和正 则表达式匹配算法。精确匹配算法是在数据序列中找出与一个或一组特定模式串 完全相同的字串的邀现位置；近似匹配算法是按照算法定义的相似度度量标准， 在数据序列中找出所有与一个或者一组特定模式串的相似程度在一定范围内的 所有字串的出现位鼹：而正则表达式匹配算法是根据正则表达式的描述，在数据 序列中找出能够被正则表达式接受的所有字串的出现位置。这三类算法的产生都 与具体应用领域的需求相关，精确匹配算法主要应用在文本检索和入侵监测领 域，近似隆配算法主要应焉在生物信息学领域，正则表达式匹配主要用来处理简 单的序列匹配无法描述的问题，是精确匹配算法或者近似匹配算法的增强模式。 模式毒匹配算法还可以按照次匹配的模式串个数分为单模式串匹配积多 模式串匹配。单模式串匹配每扫描遍文本只搜索一个模式串，而多模式串匹配 算法扫描一遍文本就可以找出摸式串集合中所有模式串的出现位置。许多单模式 匹配算法可以扩展成多模式匹配算法。 已经出现了大量的模式串匹配算法，这些算法各有所长，在处理不同类型的 模式串时性能各有不同。影响模式串匹配算法性能的因素有很多，包括模式串集 合的规模、符号集合的规模、模式串最小长度、符号的分布规律等，通常必须根 据特定应耀领域的模式串特点选择合适的串隧配算法。 1 2 。1 模式串精确匹配算法( g o n z a l 0n a v a r o ，2 0 0 4 ) 目前酲经提出的各种精确模式串匹配算法，按照检索符号序列的方式可以分 为前缀模式、羞缀模式和子串模式三种匹配模式。这三种模式的匹配算法都可以 看做是使用一个固定长度的窗口来搜索文本的过程，在窗口内检验文本是否匹 配，然后从左到右不断地移动窗口，检索整个文本。 前缀模式匹配是在搜索窗口内从前向后( 沿着文本的正向) ，逐个读入文本字 符，搜索窗口中文本串和模式串的最长公共前缀。假设已经读入直到文本位置i 的所有字符，并且邑知既是融读入文本的后缀也是模式串p 的前缀的最长字符串 长度，当该长度等于lpi 时，就产生了一个成功匹配。算法要解决的主要问题是， 豢读入下一个文本字符的时候，如何快速计算该长度。( g o n z a l on a v a r o ，2 0 0 4 ) 中总结了两个经典的实现途径：一种是找到一种有效的机制来计算既是已读入文 本的后缀也是模式睾p 的前缀的最长字符串，并且对于每个字符丽言，最好是常 数的均摊时间。例如单模式匹配算法中的k m p 算法( d e k n u t h ，1 9 7 7 ) ，以及多 模式匹配算法中的h h oc o r a s i c k 算法( a h o ，c o r a s i c k ，1 9 7 7 ) ；另一种途径维护 一个集合，它包含了所有既是己读入文本韵后缀也是模式串p 的前缀的字符串， 并且每读入一个文本字符时就更新该集合。当模式串的长度足够短时，位并行方 绪论 法可以有效地维护这个集合。例如使用使并行机制的s h i f t - a n d s h i f t - o r 算法 ( 群us ，1 9 9 2 ) 。 后缀模式蹑配主要通过计算和当前模式串的焉缀相鼷的最大长度，进而计算 出题配窟嗣的安全转移距离。它的特点是在窗黼肉的莲配过程是驮右割左的。主 要的算法有单模式匹配算法b o y e r - m o o r e ( b o y e r ，m o o r e ，1 9 7 7 ) 算法和多模式串 匹配的经典算法w u - m a n b e r 算法( w u ，m a n b e r ，1 9 9 4 ) 。 予模式串可以看做是屠缀模式翻前缀模式豹结合，它溺厝缀模式样在窗嗣 内从右到左匹配，同时又和前缀模式匹配致，通过识别在窗嗣孛的模式宰最长 前缀来确定当前的最大安全移动鼹离来向后滑动窗嗣。主要算法宥单模式串的 b d m ( b a c kd a w gm a t h i n g ) 算法( 麓c r o c h e m o r e ，1 9 9 4 ) 和8 鳓( b a c k w a r do r a c l e m a t c h i n g ) 算法( c a l l a u z e n ，2 0 0 1 ) ，相应的多模式宰甄配算法s b d m ( s e t b a c k w a r dd a w gm a t c h i n g ) 算法( a 。b l u m e r ，1 9 8 7 ) 和s b o m ( s e tb a c k w a r do r a l e m a t c h i n g ) 算法( n a t h a nt u c k ，1 9 8 7 ) 。 2 。2 模式串近似匹配算法 近似模式帛殛配算法也称为允许错误的模式窜逛麟算法，器的是找到文本串 和模式串的差异程度在定范豳肉的所有予帛的擞现位嚣。所以近似模式串琏醌 算法的结果与预先定义的嚣个符号近似度的计算方式有关。近似摸式串蹊配算法 的求解主要有四种途径：动态规划法、基予自动机的方法、继并行方法和过滤筛 选法。 动态规划的搜索算法中以1 9 8 0 年出现的s e l l e r s 算法( p 。 。s e l l e r s ，1 9 8 0 ) 最为经典。它使用矩阵来记录编辑距离，并将复杂度控制在o ( m ) 上( m 为模式串 长度) 。基于囱动机的算法是以确定他的形式在( e 。u k k o e n ，1 9 8 5 ) 中提磁，它使 用经典的n f a 到d f a 麴转换算法，将原来可以容错若于个字符的n f a 确定化， 通过这种转换，搜索时闻在最坏情况下为o ( n ) ，n 文本串长度。也可以利用d f a ， 将d f a 的每个状态视为动态规划矩阵的某- n ，在预处理阶段就就能计算出动态 瓶划矩阵中各列之间对于每一个可能的输入字符所进行的状态转移。德并行算法 被大量使用，并且整体效果最好；它采用了s h i f t - a n d 方法模拟实现自动枧算法 率的n f a ，并且可以采用备种并行方式，如行式健并行，列式位并露，对角式位 并行，瞧可以将动态规划中的编辑距离矩阵并行化。通过这这些经典算法的模拟 和位并行化，取得了良好的效暴。 1 。2 。3 正则表达式匹配算法 毒 绪论 正则表达式( r e g u l a re x p r e s s i o n ) 匹配描述了一种字符串匹配的模式，可以 用来检查一个串是否含有某一类子串。正则表达式作为一个模板，将某个字符模 式与所搜索的字符串进行匹配。 在匹配操作中，正则表达式匹配解析成表达式树，可以使用t h o m p o n 构造法 ( k t h o m p s o n ，1 9 6 8 ) 或者g l u s h k o v ( v - m g l u s k o v , 1 9 6 1 ) 构造法，将表达式树转换成 非确定有限自动机n f a ，然后直接利用那个n f a 进行搜索，目前，已经提出了多 种方法束完成此搜索工作。另外一种策略是将n f a 转换成有限自动机d f a ，在每 个文本字符到来时可以直接进行转换，从而得到了线性复杂度的搜索时间。还有 第三种策略，就是先使用多模式匹配或者其他相关方法对文本进行过滤，当发现 一个锚时就预示着附近区域中可能存在成功匹配。这时，可以选择前两种策略中 的一种对这个区域进行仔细验证。这三种策略其实是可以组合起来使用的，并且 可以使用位并行的方法来加速搜索过程。 1 2 4 单模式串匹配算法 单模式串匹配算法可以归结为三种基本的方法。 第一种方法是从文本中逐个读入字符，每读入一个字符就更新相应的变量， 检查是否存在一个可能的匹配，k l d p 算法就属于这种方法，此外，效率更高的 s h i f t 一0 r 算法也是这类算法。 第二种方法是基于滑动窗口。滑动窗1 = 1 沿着文本滑动，对于任意位置上的窗 口，在窗口中从后向前搜索窗口中的文本和模式串p 的公共后缀。b m 算法就是 利用这种方法。但是在一般情况下，b m 算法比它的简化版本h o r s p o o l 算法 ( r n h o r s p o o l ，1 9 8 0 ) 要慢。 第三种方法也是使用滑动窗口，并在其中从后向前搜索，不同的是，它搜索 的是窗口中文本的最长后缀，并且这个最长后缀同时也是模式串p 的一个因子。 最早使用这种方法的算法是b d m 算法( m c r o c h e m o r e ，1 9 9 4 ) 。 目前，最有效的匹配算法都是属于其中的某一类。另外也存在一些利用哈希 函数的散列匹配算法。 1 2 5 多模式串匹配算法 多模式匹配算法是在只搜索一遍文本串的情况下，搜索出模式串集合p 中的 所有模式串的所有出现位置。许多单模式串匹配算法可以扩展成多模式串匹配算 法。 ， 1 2 4 节叙述的三种单模式串匹配算法能扩展成多模式串的情况，基于第一 绪论 种方法是的算法包括经典的a h o - c o r a s i c k 算法。如果用lp 表示所有的模式串的 长度之和，那么当lp | 很小的时候，可以使用m u l t i p l es h i f t - a n d 算法。 基予第二种方法的算法有著名的c o m m e n t z - w a l t e r 算法( b c o n m e n t z - w a l t e r ，1 9 7 9 ) ，但是其实际运行的效率不是很高。h o r s p o o l 算法的扩展是s e t h o r s p o o l 算法，当搜索一个很大字母表的一个较小的模式串集合时，其效率很 高。嘲算法( w u ，m a n b e r ，1 9 9 4 ) 结合了蘑缀搜索算法和散列算法，在实际应用 中效率很高。 基予第三种方法的算法中，由b o m 算法派生出了s b o m 算法( n a t h a nt u c k ， 1 9 8 7 ) ，当模式审集合中的最小模式串长度较大时，s b o m 算法的效率很离，与 s h i f t - o r 算法相似，当| p i 很小时候，b n d m 算法派生出了m u l t i p l eb n d m 算法。 。3 模式串匹配藏临的困难 实际应用中，模式串匹配算法要面对的模式串集合往往很大。比如，由于 凝的入侵手段不断出现，入侵检测系统中的入侵规则集每年都在迅速扩大，如图 1 1 ，知名的入侵检测组织s n o r t o r g 和b l e e d i n g t h r e a d n e t 公布的入侵规则每 年都在递增。规则集中包含的相异模式串( u n i q u es t r i n g s ) 数量也在增加。在 2 0 0 0 年到2 0 0 3 年间，s n o r t 的相异模式串数量增长了2 7 5 倍( n a t h a nt u c k ， 2 0 0 4 ) ，如图l 。2 ，2 0 0 5 年底从s n o 娃规则集中提取出的楣异模式串为2 7 3 3 条， 2 0 0 6 年底这个数字为3 3 7 3 条，这种增长的势头还在继续。此外，病毒库的规模 已经达到了约l o 万条，基因库的规模达到5 0 多万。 、 6 图l + ls n o r t 中入侵规爱| j 增长趋势示意圈 罅审l逛葛-名毒z 绪论 图1 2 相异模式串在2 0 0 0 - 2 0 0 3 年间增长示意图 由于给定的字符序列必须与模式串集合中的每一个模式串进行匹配，因而模 式串集合的规模对模式串匹配算法的速度影响很大，传统的基于通用处理器的算 法实现往往不能满足应用的要求。比如，在通用处理器上用软件实现的串匹配算 法一般只能达到l o o m b p s 左右的吞吐量( l iw e i - n a n ，2 0 0 6 ) ，远远不能达到现在 吉比特的网络速度。 近些年来，网络处理器的出现为以较低的代价实现高速模式串匹配带来了新 的解决方案。网络处理器( n e t w o r kp r o c e s s o ru n i t ，n p u ) 是一种专门针对网 络应用而设计的可编程处理器，它结合了通用处理器和应用特定集成电路a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ，a s i c ) 的优点，既有通用处理 器的灵活性又有a s i c 的高速度。网络处理器一般都有多个执行核和多个可并行 执行的关键功能单元，主要利用并行体系结构来获得高的处理速度。目前已有多 家芯片制造公司推出了自己的网络处理器产品，包括i n t e l ( i n t e l ，2 0 0 8 ) 、 f r e e s c l e ( f r e e s c a l e ，2 0 0 8 ) 和a m c c ( a m c c ，2 0 0 8 ) 等。 目前，已有一些研究工作利用网络处理器的多核多线程特点对模式串匹配算 法进行并行化，以期获得较高的速度。比如，( j i a m i n gy u ，2 0 0 5 ) 在i n t e li x p 2 8 5 0 网络处理器上实现了a c 算法，它将i x p 2 8 5 0 的1 6 个微引擎( 执行核) 当作一个对 称多处理器使用，获得了1 3 3 4 5 3 4 8 倍的加速比。h e r b e r tb o s k a i m i n g 在 ( h e r b e r tb o s ，2 0 0 4 ) 中介绍了基于i x p l 2 0 0 的一个入侵检测系统n i d s ，也是将 a c 算法并行化匹配 获得了2 0 0 m b p s 的检测匹配吞吐量。( r o n g t a il i u ，2 0 0 4 ) 中基于1 0 2 0 0 0 实现了f n p 算法，充分利用了网络处理器的并行处理能力和入侵 7 1 0 0 0 n o z e2j)笛de3z u i o协可口j。c一 绪论 规则集中包含大量短规爱| l 串的特点，获得了较好的访存效果。( p i t ip i y a c h o n ， 2 0 0 6 ) 改进了a c 算法的内存存储横型鞠并行院较方法，提擞了位并行和多字节并 行榴结合的b i t - b y t ea c 算法，第一次将睾匹配速度提高到吉比特麴匹配吞吐量。 ( j i an i ，2 0 0 7 ) 提趱了一种快速多模式匹配算法h a s hb o y e r m a n b e r ( h b m ) ，使 蕉嗡希函数和一个额外的扁发表减少了躐算法中对扇发表的访溺，在i n t e l i x p 2 4 0 0 网络处瑗器上的模拟试验表髓，该算法能达到1 g b p s 的吞吐量。( h e r b e r t b o s ，2 0 0 4 ) 蓠次将网络处理器用在了生物信息学中，在i n t ei x p l 2 0 0 网路处理 嚣鲍土使用用经典的a e 算法实现d n a 和蛋鑫质序列托对，菲常具蠢创造性。 以上基于网络处理器豹模式帛匹配研究大多选择筋算法，剥孀髓络处理嚣 本身的并行处理能力来提离吞睦量。焱c 算法蛉缺点是必须逐个字符进行匹配， 访存次数与文本长度成芷毙。幽予近年来处理器速度与存储器访闯速度的差距一 袁在增大，大量的访存操作无疑将成为制约算法性能进步提高翡重要因素。一 些一次可以遥配多个字符的多模式宰题配算法，如姚，m a n b e r ，熏9 罐) ， ( b c o m m e n t z - w a l t e r ，1 9 7 9 ) 簿，避配速度受到最短模式牢长度( l e n g t ho f s h o r t e s tp a t t e r n ，l s p ) 的豢l 约，即窗团一次滑动的距离不能超过最短模式拳 的长度。对真实豹入侵翘则集中模式枣( 也称入侵特征弗) 长度分布麴研究发瑷， 模式串集合中存在许多长度缀短( 1 - 3 ) 赫串，显然受l s p 限制麴串题配算法不 适合用予入侵特征宰的匹配。f n p 算法一次可以匹配多个字符藕叉不受l s p 的限 制，但是( r o n g - t a il i u ，2 0 0 4 ) 中给出的f n p 算法一旦找到个糕配的前缀薏， 就用线性查找的方法从具有相同前缀的模式零集中荐进步查找。对真实麴入侵 特征串长度分布的研究发现，具有相同蘸缀的模式窜数量可能很多，最坏情况下 可能达到几百个，采用线性查找的方法无疑会影响算法在最坏情况下的性能。 ( j i an i ，2 0 0 7 ) 中对黼算法改进盾，基于i x p 2 4 0 0 的测试表明可以达到i g b p s 的眷吐量，但是它在模式串集合规摸较大的情况下，性能下降厉害。2 0 0 8 年s 月发表的( 余建明，2 0 0 8 ) 用种薪的确定性有限状态鸯动机以及状态转移袭静态 c a c h e 策路，基予i x p 2 8 0 0 获得了6 4 g b p s 的处理能力。 1 + 4 本文贡献和内容结构安排 本文研究适用于入侵检测的多模式串匹就算法以及算法在潮络处理器上的 离效实现。本文根据实际的入侵特征串的分布特点选择f n p 作为主要的模式窜韪 配算法并徽了适应性改变，研究了算法在i n t e li x p 2 8 0 0 鼹络处理器上的并行实 现方法，并在i n t e ld e v w o r k b e n c h 仿真平台上对算法性能进行了测试。 本文的主要贡献如下；( 1 ) 分析了嚣前使用最广泛的s n o r t 入授规则集中 寒 绪论 入侵特征串的符号及长度分布特点，为选择适含入侵检测的模式睾匹配算法以及 对算法进行改进提供了依据；( 2 ) 根据入侵特征串的分布特点改进tf n p 葬法， 并在最坏情况下与矗e 算法捆结合汉进步提离f n p 的性能：( 3 ) 研究了f n p - a c 算法在i n t e li x p 2 8 0 0 网络处理器上的尚效实现方法，在l o k 规模的模式串集会 上达到了6 g b p s 的番吐量，且其有遥乎线性的加速比。 本文剩余内容安排如下：第二章介绍与本文相关的凡个多模式串匹配算法； 第三章以i n t e li x p 2 8 0 0 为铡，简要介缀了i n t e l 网络处理器的体系结构特点及 软件框架；第四章详细介绍了f n p - a c 算法的设计与优化实现；第五章介缨了仿 真实验结聚和分橱；第六章总结全文，并指潞下一步的工作。 夸 第2 章相关多模式串霾配算法研究 第2 章相关多模式串匹配算法研究 多模式涎配算法是提对予单模式匹配两言的，旨在同时查找多个模式串。设 集合p = a ，魏，。，魏 是缀模式串集合，每个模式串魏国来源于字符集合的 字符序列组成，绘定长度为n 的文本串t - t e l n 3 ，文本串的每个字符也来源予 字符集，多模式匹配就是在文本彳中找出模式集合p 中的每个模式的所有出现。 a h o 和c o r a s i c k 予1 9 7 5 年最早提出了基予自动机的多模式匹配算法，随后，围 绕这算法，一些改进的算法被提了出来，比如压缩存储空间基予位图的a c 算法、 路径压缩鹃a e 算法，反囱构建自动机弓| 入跳跃的启发式方法等。舔详u 和m a n b e r 予1 9 9 4 年提出了采用h a s h 方法的基于艨缀匹配方法，同时采用移位来加速比较。 这两零孛方法是当前主流的软件实现的多模式匹配算法( l iw e i n a n ，2 0 0 6 ) 。 随着基于网路处理器的入侵检测体系的研究，结合网络处理器特点的多模式 匹配算法研究也逐渐出现，避几年的文献主要有( r o n g t a il i u ，2 0 0 4 ) ，( p i t i p i y a c h o n ，2 0 0 6 ) ，( j i a m i n gy u ，2 0 0 5 ) ，( h e r b e r tb o s ，2 0 0 4 ) ，( j i an i ，2 0 0 7 ) 。 文献( l iw e i - n a n ，2 0 0 6 ) 对部分多模式匹配算法做了总结和分析。本章介缀几种 典型的多模式匹配算法，并分析它们的性能。 2 | la h o - c o r a s i c k 算法( l iw e i - n a n ，2 0 0 6 ) a h o - c o r a s i s k 算法是基于有穷状态自动枫的，在进行匹配之前，先对模式串集 合进行预处理，构建树型有限状态自动机鹬a ( f i n i t es t a t ea u t o m a t a ) ，然恁，依 据该f s a ，只需对文本睾稠擒次就可以找如与其逛配的所有模式串。颈处理生 成3 个函数：g o t o ( 转移) 函数、f a i l u r e ( 失效) 函数和o u t p u t ( 输出) 函数。转移函数 g o t o 表明，在当前状态下读入下个待比较文本的字符后到达的下一个状态失 效函数f a i l u r e , n 来指明在莱个状态下，当读入的字符不殛配时应转移到的下一 个状态。输出函数o u t p u t 的作用是，在匹配过程中，当蹬现匹配时输出匹配到的模 式 。 a h o c o r a s i c k 算法的艇配过程是：从初始状态0 潞发，每次取出文本串中的一 个字符，根据当前麴状态和扫描到的字符，利用g o t o 或f a i l u r e 溺数进入下一状态。 当巢个状态的o u t p u t 函数不为空时，表明达到该状态时找到了匹配的模式，于是 输澎其值。 下面首先介绍3 个预处理函数的构建。力了构造g o t o 函数，首先要根据模式构 建g o t o 图，设置一个初始状态0 ，然后依次扫描各个模式，根据模式逐步为这个髓 篥2 章糯关多模式串匹配算法研究 添加新的边和顶点，构造盘囱动机：从状态0 出发，由当前状态和读到的下一个字 符决定下一状态。如果有从当前状态出发并标注该字符的矢线，则将矢线所指的 状态赋为当前状态：否则，添加一个标号比已有状态标号大i 的新状态，并用一条 矢线从当前状态指向新加入的状态，并将新加入的状态赋为当前状态：所有模式 串处理完毕后，再灏一条0 状态的鱼返矢线，标注豹字符为不能从0 开始的字符集 这样，每个模式都可以由一条从初始状态出发的路径标识出来。对模式串集会 s h e ，h e ，h e r s ，h i s 构建的g o t o 图如图2 1 所示。 图2 1 依据焱c 算法构建的状态g o t o 状态自动机 失效函数f 是逐层构造的，设某个状态的层深度为扔始状态到该状态的最短路 径长度令第l 层状态的f a i l u r e 瞒数值为0 ，如双1 ) = 烈3 ) = o ：对予菲第l 层状态s 若其父状态为器p 存在字符旅乎( 五a ) = 5 ( 这里，s 的层深度比砂1 ) ，则 双曲= g ( 八姆) ，萄，其中，状态胖为追溯s 的祖先状态得到的第1 个便g ( “抟) ，茹存 在的状态，如“4 ) = 移( 以3 ) ，妨= g ( o ，妨= l ，“5 ) = 譬( 双4 ) ，= g ( 1 ，彩= 2 。 输出函数o u t p u t 的作用是在匹配过程中输出匹配到的模式串。o u t p u t 的构造 分两步：第l 步是在构造转移函数尉，每处理完一个模式串，涮将该模式串加入到 当前状态s 的输穗函数中，安i o u t p u t ( 2 ) = h e ，o u t p u t ( 5 ) = s h