（通信与信息系统专业论文）网络内容分析中基于硬件的字符串匹配算法的研究.pdf

摘要 摘要 i n t c m e t 代表的信息革命极大改变了人们的生活、生产方式，网络无处不在。 但是在巨大的信息浪潮中，内容安全问题也同样无处不在，各种令人不安的信息 如湍急暗流隐藏在互联网大潮下。一方面是人们生活越来越多地依靠网络，许多 政府业务越来越多地使用网络，而另一方面却是i n t e m d 上信息的鱼龙混杂，黑客、 病毒、网络攻击等日益盛行。保护网络空间的洁净，保护网络空间中的“国土一， 已成为未来国家发展的重要问题，也是摆在人们面前的一个巨大挑战。为了建立 起高效、绿色、安全的互联网世界，网络内容分析技术已经越来越受到人们的关 注。 论文主要针互联网中内容分析的基本问题，从算法和系统的角度研究基于硬 件实现的字符串匹配技术在网络内容分析中的应用。 论文有以下几点创新之处： 提出了硬件实现的基于a b n f 范式的字符串匹配和协议解码方法 在网络内容分析中，除了要对特定的模式串匹配，还需要对数据报文中的真 实含义进行解码检查。而在传统字符串匹配中，网络数据包被简单的看成无序字 符串，其内部结构和报文中的真实含义不被匹配算法本身关注。但是由于网络通 信是建立在一定协议之上的，通信协议是一种高度规格化、具有明确含义和取值 的数据流，为此，论文提出了一种硬件实现的基于a b n f 范式的字符串匹配和协 议解码方法，实验表明了此方法在性能上能比软件实现的匹配和协议解码有6 0 倍的提高。 提出了基于加权扩展b 1 0 0 忸f i l t e r 的字符串匹配算法 为了在对模式串进行匹配的同时得到与数据报文中的字符串相匹配的模式 串的值。论文对硬件实现的b 1 0 0 哪f i l t e r 进行扩展，使其支持域值获取；同时还对 此扩展b 1 0 0 mf i l t | e r 进行加权处理以消除扩展带来的新的性能下降，并通过理论分 析得出加权扩展b 1 0 0 m 丘l t c r ( w e i g l l t i 耐以t e n d e db 1 0 0 mf i l t e r ：、e b f ) 的最优配 置参数。为了提高匹配的性能，论文专门设计了基于a s i c 的w e b f 引擎，通过 仿真和实验表明了基于此算法的芯片匹配速度大大超过了现有的各种软件和硬 件的匹配算法。 设计了基于f p g a 协处理器的网络内容分析处理平台 论文设计和实现了一个基于嵌入式c p u 和f p ( 认协处理器的网络内容分析 处理平台用以验证文中提出的字符串匹配算法的功能和性能指标。此平台验证了 文中提出的硬件实现的串匹配算法和协议解码器的模型是可行的，其匹配速度是 第1 页 摘要 现有的各种匹配算法无法比拟的。同时此平台上运行的g n u l i n u x 操作系统具有 强大的特性和自由软件的优势，可以迅速的实现复杂的网络业务。此平台可以被 设计为硬件支持数据包分类、协议解码、字符串匹配等最基本的网络报文处理， 同时还包含高性能通用处理器内核的通用平台，它能为许多网络应用提供灵活可 变、性能优异的处理能力，方便进一步的研究。 关键词：网络内容分析，网络安全，字符串匹配，模式匹配，协议解码，a b n f 范式，b i o o m 行i t e r ，a s i c 第页 a b s t r a c t a b s t r a c t n ei n f o 咖a t i o nr e v o l u t i o nc e n t e 代通0 ni n t e m e th 嬲c h 加g e dp c o p l e sl i v e s 觚d n e t w o r ki se v e 聊h e r e h o w e v e r ，b e n e a t ht h ei n t e m 嚏c o n t e n ts e c u r i 哆h 雒a l w a y s b e 锄a p r o b i e m o n o n es i d e ，p e o p l ed e p e n do nn 前w o d ( m o r e 锄dm o 陀i i lm e i rd a i l y i i v e s ，扑dm u c hm o 陀缸孤s a c t i o n si ng o v e n l m e n t sh a v et ob ed o n ew i t hn e 呐o r k ；伽 廿i e0 t h e rs i d e ，i n t e m e ti sad o u b l e e d g e ds w o r d ，嬲h a c k e 髂，v i m s 锄dn e t w o r k 甜 a c k 撇m o r e 锄dm o r ep o p u l 筑t ok e e pc l 啪o ft l l en 朗0 r ks p a c e 卸dt 0p r o t e c tt l l e i i l t c g r 时o ft h e ”c 0 帅仃y ”h a v eb e c o m e 锄i l i l p o r t 锄tt h i n gi nt l l ed e v e l o p m e n to fo 鹏 c o u 肭嘎锄dh a v eb e c 0 m eag r e a tc h a l l e n g eo fp c o p i e n e 咐。订【c o n t e n t 觚a l y s i sh 嬲 a t _ 咖i c t e dm o 托觚dm o 陀a t t i 嘲t i o nt 0b u i l d 廿l en e 附o r k 锄v i m e n tw i 廿lh i g h e 伍e n c y 锄d 阻f c 够 t h i st l l e s i s 向c u s e s0 nt h eb 舔i cp r o b l e m mn e t w o r kc o n t e n ta n a l y s i s ，粕da i m sa t 廿l e 印p l i c a t i o n0 ft h ei l a r d h 锄陀b a s e d 鲥n g 脚妯i n ga l g o r i 廿l i i li n 跏d ( c o n t e f l t 锄a l y s i s 纳mm e 嬲p e c t so fa l g o r i t h ma n ds y s t e l n t i 屺陀a 陀s e v e m ln e w i d e 嬲i i i l i s m e s i s ： f i r 鸡i i i 廿l en c t w o r kc o n t e n t 跚a l y s i s ，m ep a y l o a d si nn i e 胁m e s 鞠g eh a v et 0 b cd c c o d c d 锄dc h e c k c db e s i d e st l l es p c c i f i cs t r i n gn 脚c h i n g h lt h e 侧i t i o n a ls t r i n g m a t c h i n g ，m en e 晰o d ( m e s 鞠g e sa r cs i m p l y 仃e a l c d 懿o r d e r l e 豁蛐r i i l g ，w m l ei t si n s i d e c o n 姗c t锄d廿l e r c a l 脒猢i n g0 f 廿l ep a y l o a d s a 他 鹏g l e c 伽 h o w e v e r c o m m u n i c a t i o n si nn e t w o r ka 陀b a 瞬翊0 n l ep r o t o c o l s ，w h i c ha 糟h i g h l ys t a n d a r d i z e d d a t as 晒mw i mc l e 盯m e 觚i n g 觚dv a i s 0 ，a 确n gm a t c h i n g 觚dp 咖l d e c o d i l l ga l g 嘶幽 i lb a d a b n fi sp r o p o s e di n l i s l e s i s i t 啪p c r f o 帅s t r i n g m a t c h i i l g 锄dd t ：c ) d et i l ep r o t o c o li i lal l a 删1 w a 他m 锄e r ，a l s 0c 觚s a t i s 矽t i l em e d so f l en 嘶i i r o 出c o l l t e n t 觚a l y s i s 锄di i i l p r o v et i l ep e 疵i m 帅c co f t h es y s t e m t 0 删一c v et l l ev a l 0 f p a t t c n ls 仃i n gw r h i c hm a t c h e dw 汕廿i ei i l p u ts t r i i l g ，t l l e 删i t i o n a lb l 嗍f i l t e ri s 懿t e n d e dt 0s u p p o r tv a i u c 胁i e v e ；m 湖w h i l e ，aw e i g h t e i a e x 咖e db 1 0 0 mf i k ri s p r o p o di n l i s 廿l e s i s t 0e i i m i n 咖l ep c 而咖册c e d e c 崩n e n ti nn l ea b o v ee x t c n d e db 1 0 0 mf i n 既t h 钮l eo p t i m lc o n f i g u m t i o no ft h e w e i g m e de x t e n d c db 1 0 0 mf i l t c r ( w e b f ) i sd c d u c e d a l s 0 ，t 0i m p r o v et l l ep e r f o n n 锄c c o fn 坞m a 钯h i n g ，aw e b f g i a s i cc h i pi sd e s i g n c da n dt i l ep e r f o r i l l 锄c ei sg i v e n 协r o u g hs h u l a t i o n 锄de x l ) e r i l i l e n t t 0v e r i 匆m em n c t i o n 锄dp e r f - 0 m 锄o fm es t r i n g m a t c h i n ga 1 9 0 r i t h n l 第页 a 8 s t r a c t p r o p o s e 蠢n 像 s 重h e s i s ，w ed e s g n 鑫l l e 辩。墩糕鼍e n t 黼a l y s sp l 醚凳鼬b a s e d 强 e m b e ( 1 e dp f o c e s s o r 韪n dw e b fe n g i n e 。l ti si n d i c a 纶dt h a t 如es l r i n gm a t c b i n g a l g o r i t h m 粕dt h ep r o t o c o ld e c o d e rm o d e ii s 佗a s i b i ew i t ht h ea d v a n t a g eo fh i 曲 e 硪c i e n c y 勰dl o w c o s t i nt h em e a n t 两e ，g n u 悲i n 娃xs y s 绝m 滩t h ep l a 南哺i s 纛糯 鞠dp o w e 惩l la n de 强i 趣纠e m e n t m p l i c a 芝e dn e w o 戒怕n s c a t i o n f r o maw i d e r2 l s p e c t ，n e m o r kc o n t e n ta n a l y s i si sas p e c i f i ca p p i i c a t i o no fd a t a 日o wm a n a g e m 锄t e 垃拯日o wm a n a g e l 稚e n t sa 耋e c h n i q u eo fm a n i p u l a i n gag 愆a 雒l o 鞋程ld 攥a _ 泓i 鹅黼d 铷d l e s s 爨。转懿鬈d 嬲 w ea l w a y sh a v cad r e 籼o fd e s i | g l l i n gan e 似o r ks o cc h i p ，w h i c hc 觚s u p p o r t s o m eb a s i cn e t 、 ，o r km e s s a _ g eo p e r a t i o n ss u c h 越p a c l ( e tc l a s s i 蠢c a t i o n ，p r o 眦o lp a s e r 锄蠢s 哦n g 菇8 玺c h i 鑫gi 糕魏a 砖斌糙a 强嚣雒d 越辩龇旺纽i 矬s 辩e 拖lg e 曩e 碟掣o c e s s 嚣 c o r e s i tc 粕s u p p i yn e x i b l ea n dp o w e r f i l la b i l 时t om a n yn c t 、0 r ka p p i i c a t i o n s w 宅 h o p et l l a ti tc 锄b e c o m eab a s i cs y s t e m a t i cc h i pt op r 0 v i d ct e c h n i c a ls u p p o r tt 0t l l e s e c u r 时鑫髓dc o m m e 弼主a ld e v e l o p m 铋lo f rc o u 茶t h i s 氇e s i sc a nb e 扫e 蹴d 鑫s 雏 躐嘲p tl om i s o r i 铋t a l i o n k 呵w - o 州s ：n 朗阳撤c o 鹏n la 麓l y s 蕊n 咖。呔s e c u r i 劬钳i n gm 鑫托h 堍，黝淝热 m a 据h i n g ，p f o 幻c o lp i l f ，a b n f ，b l o ( 腿f i l t e 霸a s l g 。 第页 插图目录 插图蟊录 图2 1b r u t e f o r c e 算法8 图2 2a h o c o r a s i c k 算法。9 图2 - 3b o 琵r m o o r e 算法。- l o 图2 0k 嘲p 算法 l 图2 5 报头和内容c a m 一1 3 图2 墙c a m 和t c a m 分组结构1 3 图2 7d c a m 结构一1 4 图2 - 8b v t c a m 结构1 4 图2 - 9 单个瓯配单元结构1 5 图2 1 0 基于规则的字符串匹配算法- 1 6 图2 - 1 基于可重新配置存储器的字符串匹配结构1 7 图2 - 1 2 基于流水线8 1 辎f l 疆睬的字符串匹配算法1 8 图孓1 基于a b n f 的字符串匹配结构2 6 图孓2 域值提取模块结构2 7 图孓3 匹配搿a b c 一的关键字匹配模块2 8 图4 种a b n f 基本操作符的n f a 表示一2 9 图3 5 匹配( ( 口1 6 ) ) ( d d 】) 的n f a 结构? 2 9 图64 种a 8 n f 基本操作符的硬件逻辑表示3 0 琶孓7 种嵩效率的比较器的实现一3 1 图8 对范式( 和| 6 ) 搴) h 棚) 匹配豹逻辑结构3 图孓95 段流水线组成方式3 3 图1 0s i p 协议解码各种实现的性能比较3 5 图禾1 一个使用4 个h a s h 函数的b l o o mf l 哦r 示例4 0 图奉2c o u n t i n gb l o o mf i l l e r 山一4 2 图4 - 3w e b f 中的误判概率5 2 第贾 播图目录 图4 0 班8 f 中的l d 号错误溉率5 2 图4 5 对网络报文进行匹配的v 讵b f 结构一s 5 翻4 6w e b f 豹滑动窗飚5 6 图4 7w e b f 引擎结构5 7 图4 8 单块存储器需要同时支持1 4 次查找5 8 图4 9w e b f 引擎芯片的版图5 8 图4 1 0 各种字符串匹配算法实现的性能比较。5 9 图5 - 1 嵌入式鼹终内容分析处理平台总体结构6 图5 - 2 嵌入式隧络内容分橱处理平台实物图。6 2 图5 3 了m s 3 2 0 d m 6 4 4 6 的结构图。6 3 图c 6 4 x + d s p 结构图6 5 图5 - 5 误判率与分组个数的关系7 2 图5 - 6 误判率与m n 的关系：j 7 2 图5 - 7i d 号错误概率与分组个数的关系7 3 图孓8l d 号错误概率与悯的关系。t i 7 3 圈5 - 9 网络内容分析平台的测试鼹络拓扑图7 s 第x 页 波格目录 表格蠢录 表1a b n f 核心规剃定义+ 2 5 表2 器段滚零线预约表豁 表孓3 各个协议硬件解鹤系统炎瓣占焉。 ，表夺- l 部分参数组合下的误判概率( l 一譬。柳鼎 ) 。3 表奉2 o k 令元素麴缭栗硒 表4 。31o o k 个元素的结果。躺 表夺4w e 8 f 弓l 擎芯片性笺参数鞠 髂x l 页 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。， 拓者签名：茎赴 沙g 年气月以日 薷 章绪论 第薹章绪论 。 嚣联露内容安全瑗裴 h 撇黼e 专代表的信息薷命裰大羧黛了入翻豹擞溉、生产方式，黼络茏处乔巍。 但是在臌犬的信息浪潮中，内容安叠黼题无处不在，各种令人不煮的信息如湍急 暗滚隐藏在耍联网大潮下。 壤多企盈戆警递者蒸发现，企监褥络瓣整鬻羧率氯下。最多樊工镬蘑金遂隧 络作自戳的“私事捧，测览网页、求黻、聊天、下裁音乐电影等瓣。据调查，中 国受王橼阕花在网上处理私人事务辩时闯离达5 6 小时，焉亚太地区整体的平均 上爨时鳓是龟2 夸嚣移璃。存赘赫中鼷警理大员壶予在办公时间虑测菱与工箨秃荚 嚣瓣站，使金踅畜更多祝会遭受到镶黉诈骧、赫漾软佟帮其它瓣童玫毒翡藏胁。 如荣上面的效率楚指员工对网终艘应用对芏绍带来的效率影焖，是一种“软” 意义上的效率的话，税p 较件影响的则是鼷终带宽徽率，是硬馋意义上的低效举。 禳多静嬲络誊瑾曼都对黔头疼不蠢。鞋髓秀代袋戆滋羁终槎挺供丰富瓣海 容熬圈辩，也谴鼹络带宽不堪重受。特掰是需要赢付丽责带宽糕爝金韵企盘，对 此更是深惩瘸绝。如辩霄效地控制樊憾雅p 网络的使用，取其测瓣去其害，魁缎 多瘸管都非常关心戆话题。 蠢蓊淹遵鬻终窃取、灌露公裁撬饕戆装象塞发尹熏，藩金鼗来说，逮释蜚舞 对其危辫最大。企业的核心竞争力埘瓣在不经意的一封邮件中就瀚漏出去，双黼 造成巨大的经济损失。同样，对于企她，如果员狂利用公司网络发布各类有密 售惑，将给金_ 遂带寒穰耩熬社塞影瞧。 翦毂对簿，在爨麓江等建开袋懿绿色免费瓣避活动蠹现了群葑不鹾痊懿祷 况。这擞校园内的免赞上网环境并没黼吸引青少筚| | i | q 嗣光，绿色湖吧门可罗雀， 经营性麟曦门庭若市。其中最大的原域裁是绿色爨吧嚣蠹担心内瓣安全的闭趱， 霞粪太多数蓑蛰，漤戏熬蓬嚣，霉致鬻多冬诀鸯漫意懋，蠡舞在遗滤琴羹蠹察懿 弱对最大限度地减少对阏络的使用影昀，是孛小学拨阕霹络非常瓣重的一点。 为了建立起高效、绿色、安全的腻联网世界，网络内容分析拽术已经越来越 受裂大稍耱关注。 1 2 网绻内容分析系统研究现状 在瓣终内容传播孛，数据并不墨瓣燕持久稳定的状态，蔗是戳大量、连缕、 羲邃、辩囊懿鼗据蔑形式戮遮。这样瓣鼗攥塞集楚盛爝萃逶室爝掩久嫠囊关系建 躲1 页 第 章绪论 模，而适宜用瞬态数据流( ( 1 a 像s 骶a m s ) 建模【l ，2 ，3 】。这些应用的实例包括金 融服务，阚络监控，安全，电信数据管理，w e b 应用，生产制造，传感检测等等。 在这种数据流模型中，单独的数据单元可熊是相关的冗组( 1 【u p l e s ) ，例如网络测 量，呼日q 记录，嗍页访问，传感读数等产生的数据。这类系统被称为数据流关系 系统( d s 醚s ：d 鑫纨嫩e 鑫m 糖鞠a g e m e 魏s y 蹴m ) 。阻子这些数据以大量、快速、对 变( 还可能是不可预知、极大的) 的数据流形式持续到达，这对其中的字符串匹 配算法提出了更高的性能要求。因此，论文以高速网络作为技术背景，选择网络 内容分桥中字符串隆配算法的硬件加速作力论文的研究方向。 由于网络内容分析系统涉及到国家机密、公民隐私等敏感问题，因而网络内 容分析系统方面的资料较少。所知的典型项目有下面这些： 斯蜒福大学受美国n s f ( 国家自然科学基金) 资助，开始了s t 跹a m 顼婆 【4 ，5 】。这是一种全面d s m s 的设计和原型实现。它是一个以关系为基础的数据流 管理系统，重点在于内存管理和近似查询。它可以用于处理快速的、易变的、大 量涌入的数据流信息，其连续查询能力非常好。s 啊强触唾的主要处理技术包括 连续的囊我监控和爵优化、适应于不网需要的近似查询、合理的资源分配和使用。 目前他们在d s m s 的体系结构、数据模型和语义、语言、资源分配和查询优化 等方面取得了部分成果。 加髑大学伯克利分校研制的t e k g 强h c q 系统【6 ，7 ，8 】是为连续的数据流构建 的连续蠢询处理系统。由于开放源代码的数据库系统p 0 s 蟾r e s q l 代码的易重甩 性和很好的扩展性【9 】，特别是载入用户代码和丰富的数据类型的能力f l o 】，因此 r l e g 胁c q 使用邂晖s q l 侔为研究的起点，其致力于多数据流上的并发连续 查询的囱适应和共享处理。它主要使用一个自适应查询引擎来处理不稳定和不可 预知的环境( 例如，i n t e m e t 上的自治数据资源或传感器网络) 。在现阶段 瓢l e g r a l l c q 支持d 观语言声明，可创建存档帮不存档的数据流f ll 】。 麻省理工学院和布朗大学共同开发的a u f o r a 【1 2 】项目建造了个专门用于流 监控的数据处理系统。a u r o 豫系统的核心是由一个大的触发器网络组成，每个触 发器是包含一个节点的数据流阌，每个数据节点是七个嵌入操作符中的一个( 按 a u 妁豫的术语是b o x c s ) 。这种数据流管理系统对基于流的应用在性能和处理方 面提出了相关需求。它支持多重并发持续查询，其所产生的每个结果都可以用于 一种或多种基于流的应用f 1 3 】。 威斯康星大学豹n 酞g a 姒项嚣【1 4 ，1 5 】也是由美国国家自然科学基金支持 的，其主要研究目标是在i i l t i 咖e t 环境下的x m l 数据检索和过滤系统。该系统 从i n t i 跚1 e t 上采集和监管信息，然后包装为) 【1 啜。数据流供检索和过滤使用。这 样利用粼l 的语义信息，可以提供更赧准确的数据流检索纛过滤。基前他们的 第2 页 第1 章绪论 研究目标主要集中在可扩展性和性能优化方面，主要技术是查询分组和增量维 护。 美国为了防范电脑犯罪，早在1 9 9 9 年就开展了“电脑信息安全行动”计划。 由于许多i s p 没有能力将某种特定的消息同其他通讯内容区分开，于是美国联邦 调查局设计和开发了一个类似于“s n i 毹r ”的特征鉴别工具c a m i v o r e 。其运行在 i s p 所在地的一台特殊的计算机上，通过这个装置对进入整栋大楼的i s p 的数据 进行监督，寻找受监督主体收发的通信，将许多内容分割成微小的数据报，自动 纪录、拦截和保存所有的通信内容。 除了上面提到的研究项目和产品外，相关的技术还有p u b l i s h s u b s c r i b es y s t e m ， m e s s a g eb r o k c rn e 铆o t k ，i i l f 0 珊a t i f i l t c r i n g ，仃i g g m a t e r i a l 娩c dv i e w ，、c bc l i c k s 仃e 锄sm i l l i n g 等。 1 3 网络内容分析中的问题 在网络内容分析模型中，需要处理的输入数据并不存放在可以随机访问的磁 盘中，而是以一个或多个“连续数据流 【l ，2 ，3 】的形式到达。因此，网络内 容分析模型不同于传统的存储处理模型，主要区别体现在如下几个方面： 1 数据流的数据元素是以线速到达的； 2 数据流的潜在大小可能是无穷无尽的； 3 一旦数据流中的某个元素经过计算机处理，要么被丢弃，要么被存储。 因此，网络内容分析系统给人们带来了新的挑战。本节将概要的介绍其中最 吸引人的一些挑战。 网络内容分析系统需要拦截用户在网络中传输的数据包，立即对数据包中的 内容进行分析，如果信息内容是不希望传输的，则终止用户这次数据传输，否则， 转发正常的数据【1 6 】。网络内容分析系统有两个最重要的特征：第一，它需要实 时处理网络数据，在高速网络环境下，对内容的分析要求有非常高的实时要求。 第二，网络内容分析系统需要尽可能早的发现匹配规则，一旦发现满足任何一条 规则，则可以立即终止内容分析，这与信息过滤( i i l f o m a t i f i l t i 喇n g ) 中需要 对整个文档全部处理后再执行判断是不同的。 这两个特征决定了高速度的字符串匹配算法在网络内容分析系统中的重要 性。 1 3 1 字符串匹配算法的速度 在安全领域【17 】，有这与一个公式：口+ 墨 ，每一个表项都包含数据比特串和掩码比特串。c a m 能够 在一个硬件时钟周期内完成模式串的精确匹配查找，只需要输入模式审的内容， c 剐订就会将此关键字于c 越涯中所有的表项同时进行匹配比较，最最返回匹配 表项在c a m 中所对应的地址，如果存在多个匹配表项则返回地址最低的表项。 g o l c h a l e 介绍了一种利用c a m 的可编程模式匹配系统。他们在s l 恕托l v 硬件 平台【2 4 】上实现了对干兆级掰络报文的过滤。此硬件平台包含了三片x i l i l l ) 酸蹴x x c v l 0 0 0f p g a ，十片2 5 6 k 3 2s 黜m 存储器和一个千兆以太网卡。数据包以 线速进入到f p g a 内的硬件逻辑，一部分逻辑将数据包的头部与已知的包含攻击 特征的模式串相比较，另一部分逻辑比较数据包抟内容部分。需要进行匹配豹模 式串在硬件平台启动时自动载入到在f p g a 内郝实现的c a m 中，而且模式串集 合可以在不用重新编译f p ( 认的同时方便的增加、删除和修改。图2 5 是这种结 构的示意图。 第控页 第2 章字符串匹配算法概述 图2 5 报头和内容c a m 何一凡等人【2 5 】采用了对模式串分组并均衡存储的方法，以多个t c a m 和 c a m 实现核心部分模式匹配，用待测串切换技术隐藏二级匹配引入的开销，同 时多处理模块并行的结构进一步提高了字符串匹配的性能。其基本系统结构如图 2 6 所示。 s o u r d i s 提出了一种预译码c a m 结构 2 6 】，并将其用在网络入侵检测的字符 串匹配中。此结构在数据包中的字符进入c a m 之前对其进行译码，对相同的字 符可以共用一个硬件比较器，这样可以提高硬件逻辑的利用率。其结构如图2 7 第1 3 页 第2 章字符串遥配算法概述 所示。 聩c o m l n i p a c k 剖咚 8 k 串 到 槲到 l l 一： 咻到 ! ll ： l 啦到 瓢纛c 瓤 “a 8 c d ” 卜一u 、 l 、 l 、! o s 裳l 童蠢 图2 - 7d ( ：街讧结构 l a l c s h m 锄提出了另一种基于c a m 的字符率匹配算法【2 7 】。它采焉了被称为 位向量( b i 、铳t i 皤) 的方法使这种算法更加便于用硬件实现。在这种算法中，多 个数据包报头匹配阀题被分解成了单个匹配问题的多个实现。其思想是找到与数 据包报头匹配的模式串并用一缀位向量表示匹配结果。每一个模式串都被表示成 位囱量中的一位，如果一个数据包报头与某个摸式串匹配，那么把相应的位置 l ，否则为o 。待所有的模式串匹配操作都完成后，只需要查询位向量，就 可以知道数据包报头与哪些模式串匹配。这种方法的简便之处在予其只需要访闯 存储器和进行“逻辑与操作。如果对于每次匹配都是二值的，那么这种方法的 时阅复杂度为d ( 1 0 9 加，其中是模式串的个数，但是其需要的存储器大小为 d ( 2 ) 。l a i ( s h m 孤在一个以3 3 瑚z 速度运行的f p g a 和五片l2 8 k b y t e s s 似 的平台上实现了此算法，它支持5 1 2 个模式串的查询，且在最差情况下霹以每秒 处理一百万个数据包。图2 3 是这种算法的结构示意图。 圈2 8b v 一亿a m 绐构 第铒页 第2 章字符串匹配算法概述 虽然c a m 使用方便、匹配迅速，但是c a m 的功能决定了其中的每。一个存 储单元除了需要贮存数据之外还要额外增加比较器的电路。一般的来说，一个典 型的c a m 单元为了存储掩码位需要比普通i 认m 增加6 个晶体管，实现一个比 较器电路需要增加4 个晶体管，因此，实现一个c a m 单元需要1 6 个晶体管， 而一个标准的洲单元只需要4 个晶体管【2 8 】。因此c a m 的价格比普通的r a m 的价格要贵的多，其价格取决于容量的大小、内部单元之间的互连结构和其额外 电路结构的多少。另外，在密度远小于普通r a m 的同时，现在主流的c a m 每 秒钟可以进行一百万次查询，导致其访问存储器的时间是普通洲的3 3 倍 【2 9 】。而且，c 舢订的功率消耗为每比特3 m w 【3 0 】。总的来说，c a m 每比特消耗 的能量是普通洲的1 5 0 倍，其每比特价格是普通黜w 的3 0 倍。这些缺陷限 制了c a m 在字符串匹配中的大规模应用。 2 2 3 基于协处理器的字符串匹配算法 y 0 嘶gh c h o 等人为网络入侵检测专门设计了一个字符串匹配协处理器 【3l 】，可以用于监视和匹配那些包含攻击特性的模式串的网络数据报文。此协处 理器包含一组可以高度并行的模式匹配单元，这些可编程的匹配单元可以匹配不 同长度的多种模式串。其基本思想是在每一个时钟周期里，输入的文本串都经过 一个h 嬲h 运算模块生成一个索引值，这个索引值作为访问存储相应模式串的存 储器的地址。从存储器中得到的模式串再与输入的文本串比较，以判断是否匹配， 如果匹配，此索引值可以作为匹配到的模式串的标志。这些单个的匹配单元可以 级联起来用于匹配长度不同的模式串。y 0 岫gh c h o 在x i l i n xs p a r t a n 3f p g a 上+ 实现了此协处理，其处理数据报文的带宽可以达到1 9 0 g b p s 。图2 9 是单个匹配 单元的结构示意图。 图2 - 9 单个匹配单元结构 y 0 u n gh c h o 又提出了一种采用并行结构的基于规则的字符串匹配算法 【3 2 】，此算法应用在深度网络报文过滤中，图2 1 0 是这种算法的基本结构。每一 条规则都是被并行处理的。首先，网络报文数据经过3 2 比特的数据总线被送到 匹配单元中。然后，每个数据包的报头信息与预先定义的报头数据相比较，如果 匹配成功，那么载荷数据被送到内容匹配单元中，此匹配单元在载荷数据中搜索 第1 5 页 第2 鬻字符硌匹配辣法概述 鞭毙定义麴模式攀。疼容题配单元是出8 比特爨存器鬻j8 比特比较器构成的。为 了增加眷蛾鼓，4 个字节的数据以流水线的方式进行同时院较，也就是谎，每个 文本率都鬣焉了辱令莽孬豹诧较器。褰验焱示魏粹结构哥辍在众l 铤终戮泛觚 擎麓杰串苏6 蛰翅 娩熬遂痰运行，器避鏊w 以达裂l 。蛇g b 辫，并且每条规则只 鬻要l o 个逻瓣单冠。出于此协处理器缩构复杂，其馘配单元黼鼹消耗很彩的硬 件逶辑资源，两基也难融达瓣鞍嵩靛王俸频率。 鬻奈l e 爨予纛辩熬警褥枣鹣聚冀羧 a 辩剐畦薮镰人戈煺终入侵梭测提趱7 一种基子可燮新酝拦夺微器的字符串题飘 协处理器。北协处理器怒一个可鬣餐网络处瑗器的部分。它包括一个双核的支 持怒长指令字( v 零黟l o 娃g 囊械糯蘸雌瑚越；、毽l w ) 鹩怒毽器，著鼠硬释支持寒 个线糕。其存臻蓑统瓴禽? 霓个多端翻r 劁镬秘一个蠹遮的d 氛缎憩线。若干个 字符出协处理器用来加速特定的网络任务，例如报文转发、流裁控制和黼络入侵 梭测莓。熊协簸瑷器镪禽两个模块：运行在。l w 肉棱上豁软荇辩蒸予蕊鹾安 瑷黪字符攀珏嚣麴蘧器。裟抟辫分生袋爹s 醚耧状态裘，戴爹s 鹾剃熙a 酌锄s i 嫩 算法进行字符串聪配。a l d w a i r i 采朋了另外种方式将a h o o r 龄i c k 数掇存储在 s r a m 率，这样w 瑷达戮更高酌褥蘸鬣，其结构示意鬣翔圈2 。l l 掰示。京雹攉 了一个寮剩型耩艇、块戳& 醚存镳状蠢豪、一个替存嚣缳存蛰嚣拔拳餮控斟凌 阏薹姨m 的逻辑电路。实验袭明，当使用8 个f s m 并行处理的适合，这种结构 可以达到2 g b p s 的吞掰：量。但是褥畦誊念隧莆模式审巾字符数潼的螬长丽下降。 这是杰予蘸簧字符鼗爨戆增长，状态蒙鞠蔽态表熬太誉帮会增赧。 篓 巷簧 第2 章字符串匹配算法概述 图2 - l l基于司重新配置存储器的字符串匹配结构 2 2 4 基于非确定有限自动机的字符串匹配算法 s i d h u 等人提出了一种基于非确定有限自动机( n o n d e t c 咖i n i s t i cf i n 硷a u t o n m ， n f a ) 的字符串匹配算法【3 3 】。此算法用于匹配采用正则表达式表示的模式串。 正则表达式是一种用以描述一个或一组字符串的表示方法，它经常被用于精确的 描述一组字符串的集合，而不用把集合中的每个字符串都列出来。非确定有限自 动机是有限状态机的一种，对于每一对状态和输入符号的组合，都会对应若干个 可能的下一个状态。它与确定有限自动机( d e t e 肌i n i s t i cf m 沁硼t o m a ，d f a ) 的 区别是，在d f a 中下一个状态是唯一确定的。一个m a 可以用一个有向图表示， 图中的每一个节点都是一个状态，每一个边都以一个字符或者空字符标识。在 s i d l l u 提出的算法中，需要根据规则库中的每一个模式串正则表达式都生成一个 m 认，用硬件逻辑实现的n f a 可以在每次对一个字节的输入字符进行匹配。这 种方法的时间复杂度是d ( 刀) ，逻辑复杂度是d ( ”2 ) 。搜索一个长度为坍的文本串 时间复杂度是：d ( 刀+ 册) ，逻辑复杂度是0 ( 拧2 ) 。实验表示这种结构可以在x i l i n x m x l o of p g a 中以9 3 5 m h z 的速度运行，其吞吐量为o 7 5 g b p s ，对每一个模 式串大约需要3 1 个逻辑单元。需要注意的是，通常有限自动机都是非常复杂的， 并难以实现，而且每当新增加一个模式串都必须对硬件进行重新编译，这种算法 的吞吐量也是比较低的。 2 2 5 基于b 1 0 0 mf i n e r 的字符串匹配算法 b 1 0 0 mf i l t c r 是b u n o nh b l 嗍于1 9 7 0 年提出的一种存储效率很高的基于概率 的数据结构【3 5 】。它可以检测一个元素是否存在于一个指定的集合中，它利用多 个哈希函数计算集合中所有成员的索引值。查询一个元素是否存在于集合中时可 能会出现误判( f a l s ep o s i t i v e ) ，但不会出现漏判( n e g a t i v ep o s i t i v e ) 。f a l s ep o s n e 是指误判一个不存在的元素在集合中；鹏g a t i v ep o s t i v c 是指没有检测出一个本来 存在于集合中的元素。匹配和查询的时间与集合中元素的个数没有关系，而且需 要的存储容量只与集合中元素的个数成线性关系。b 1 0 0 mf i l 白e r 作为一种使用很 第1 7 页 第2 章字符串匹配算法概述 少存储空闻、易于重新配嚣并且能比有限状态祝达到受高吞吐量的数据结构，在 字符串丛配中得到了j 。泛的应用。d h 绷卸u r i k a r 等人提出了一种基于并行b i m f i l t e r 的字符串匹配算法【3 4 】。在这种算法中，模式串根据它们的长度被分成了若 t 组，而且每一个b 1 0 0 mf i l t e r 查询输入的数据并与相应长度的模式串进行匹配。 如粜文本宰被任何一个b l 灌羲l t e l 匹配，那么系统可以认为此文本串可能包含 个模式串。这样的文本串又被送到分析器中，分析器采用种确定的字符串匹 配算法，可以检测文本串是与模式串匹配还是一个误判。在d h a m l a p u r i k a r 的结 构中，每一个b l 瓣曩k | 可以在每个爵钟周期中进行一拿奁询。实验表明此结 构可以达到2 。4 6 g b p s 的吞吐量。 a t t i g 等人利用b 1 0 0 mf i i t e r 为网络入侵检测系统提出了另一种字符串匹配算 法【3 6 】，霭2 1 2 是这种算法的结构示意图。报文进入系统之后就被网络协议套处 理，报文中的数据被送入输入缓冲区，然后流向内容流水线中。当报文通过流水 线时，多个b l o o mf i r 引擎根据不同模式串的长度窝口对报文进行扫描。报文 从流水线流出后进入输出缓冲区，再通过阏络协议套处理薏重新进入网络。如果 有b l o o 骥f i 融引擎检测到匹配，算法再从一个哈希表中检查此匹配是否为一个 真正的匹配，如果是的，那么报文的内容就被过滤掉并产生个报警信息。实验 表瞻这种结构可以在x i l i n xv i 瞻姬2 0 0 0f 羊，g a 上达到2 g b p s 的吞吐量。 熙2 一1 2 基予流水线b i o o mf i l 缸的字符串珏配算法 在传统的b 1 0 0 mf i l 由e r 中，算法只能得到文本串是否与规则库中的模式串匹 第铝页 第2 章字符串匹配算法概述 配，而不能知道相匹配的模式串的值，论文后面的部分将提出一种基于加权扩展 b 1 0 0 mf i l t e r 的算法支持这种域值获取。 2 3 小结 本章首先给出了字符串匹配的定义，然后分别总结了现有的用基于软件和硬 件实现的字符串匹配算法，并分析了它们的优势和不足。论文后面的论述将提出 两种字符串匹配算法能大幅提高匹配的速度和吞吐量。 第1 9 页 第3 章蒸予a b n f 的字符枣匹配莆l 协议勰码 第3 章基于a b n f 的字符串匹配和协议解码 篓赢：襄蓑统掌祷睾茳髦串，嚣绻鼗莛京被簿攀熬藿成无黪掌将宰。羹舞帮络梅鞣摄文 枣鹣羹实含义不教鞭凝算法奉身蓑注尊蓬差焱蘑周强，髑终透穰是建纛雀一寒藏惩法议； 2 上的。通信协议感一种高度规格化、具有明确含嶷和取值的数据流。因此，在网j l 爵内容分 析中，除了罴对特愆的模式串器配，还需要辩数据搬文审豹真实禽嶷进行解蠲检蠢。奉章提 籀了冀爱箨实骥戆莲予轰g 蠢泽蒸戎瓣掌煮枣器醚瓣镰设簿礤骞遘，鼗蠢法巍鐾麓童蘸毖蓑 捧燕