（通信与信息系统专业论文）字符串模式匹配的硬件加速研究.pdf

摘要 摘要 随着网络与信息技术的高速发展，网络检索、路由查找、信息安全等许多应 用领域对字符串模式匹配有着越来越离的速度需求。因此，近年来，人们集中研 究如何以快速、高效的方式进行字符串模式匹配。随着硬件工艺水平的提高和 f p g a 技术的发展，用硬件的并行结构来实现字符串模式匹配处理的研究大量涌 现。当然，不同的研究和设计方案，在速度、面积、成本、灵活性等方面都有很 大的差别，在实际应用中，这些方案扬长避短，在某些虚用领域中麓发挥关键的 作用。 本文提出设计专用处理器的方案，来达到字符串模式匹配加速的目的。专用 处理器是一种新型的具有处理器结构和可编程能力的芯片，它为某个或某一类的 应用焉专门定制。通过权衡速度、面积、成本和灵活性的设计约束，专用处理器 往往能够达到更好的平衡点，从而适应嵌入式系统的需要。因而专用处理器在嵌 入式领域中具有良好的应用背景。 专用处理器的设计需要面对具体的应用定制最优的体系结构，其设计过程往 往是从局部展开，基于应用分析和需求分橱，提取其中的处理规德和特点，并针 对这些规律和特点展开设计。另外，专用处理器的设计要具有一定的完整性，包 括配套的编译器( 综合器) ，便于工程师在嵌入式领域中的开发和接受。 本文具体研究内容如下： 1 ) 分析正则式和巴克疑范式的语法特点。 正则式和巴克斯范式都是用来描述字符串模式规则的文法。正则式是用途最 广泛的一种字符串模式描述工具，语法简单高效。增强型巴克斯范式( a u g m e n ：t e d 骞a c l 【l l 婢嘻a w 珊，鲳套涿) 是装譬c 2 2 3 4 里蔼定义的一个字符串模式匹配的文法 定义，语法更丰富，擅长描述网络协议的结构和规则。本文首先分析正则式和巴 克斯范式的语法特点以及它们描述网络协议结构和规则的规律，以便定义指令系 统和硬件加遴模块的功能。 2 定义字符串模式匹配专用处理器的指令集。 根据正则式和巴克斯范式的特点，定义并设计了一套指令集，包括基本指令 集和专用指令集。基本指令集保证专用处理器具有基本的通用处理能力；专用指 令集是针对模式规则的文法特点而设计的一套高级语言指令集，擅长描述字符串 第1 页 揍要 模式规则，能够更加篾洁地表达模式规则的关系操作，使得字符串模式匹配算法 仅需少量的代码即可描述，并鼠方便使用。 3 ) 研究字符串模式匹配处理器的体系结构设计私存褚器管理方案。 通用处理器上的字符零模式匹配代码中，比较、刿断、循环和分支指令占有 非常大的比重，指令相关性较强。这种算法的特点要求处理器频繁地访问不连续 的存储空间，导致流水线中断、c a c h e 命中率底下等问题，致使基于多级流水线 的处理器性毹难以发挥。在专用处理器的体系结褥的定割主，要想取褥较大鲶擞 速纥，就需要针对这类闯题和这些特点进行解决。秀了进一步提高指令级的并行 能力，面向字符串模式匹配的多核处理器的体系结构设计也是本文的研究内容。 无论是单核处理器还是多核处理器，算法的特点都会导致处理器频繁访闯存储器， 因此，合适的存储器管理方案也是关键煎研究内容之一。 本文设计的单核专用处理器和双孩专用处理器在即後上褥到验证，并进行 了功能测试和性能测试，测试结果表明该专用处理器在功能上满足实际应用的需 要，在性能上可以有效地提高字符串模式匹配的处理速度和效率。 本文酌主要怠薪点在于： 1 ) 提出设计专用处理器的方案，遴过针对模式规则的语法特点设计专用指令， 得以提高字符串模式匹配的速度，同时又可以兼顾通用性和灵活性。 2 ) 通过专用处理器的设计流程，本文讲述了如何从应用需求出发，通过对功 能的描述襄对传统方案豹分析，定制一静藤恕照用的专翔处理器，并进一步挖掘 指令级豹并行能力的设计方法。 3 ) 字符串模式匹配算法加速的最大难点是克服处理器在处理数据过程中频繁 访问不连续的存储空间，本文在研究专用处理器的体系结构设计过程中，设计了 一些特殊鲍功能单元来提高处理器酌访存效率，这些模块约功畿帮结梅会失从事 该领域研究工终的人员带来一定的帮助和启发。 关键词：字符审模式匹配、专用处理器、增强巴克斯范式、指令集、体系结构、 f p g a 第1 i 页 a b s t r a c t w i 氇t k 文r v e l o 跚。越o fl 蹴豫或整砖l 珏触a 鼍主潍耄e c h l o g y ，量弧ls 畦拄gp a 魅e 难 m a _ t c h i n gi se s s e n t i a lt 0i m p l e m e n t i n gn e 似o r k n t e n td e t e c t i o 坞i pa d d r e s sl o o k u pi n r o m e r s ，i i l t e m e t c u r i 锣锄dm a l l yo m e rd e s i r a b l es e r v i c e smn 酏o r k s i k c e n t l y ， s o m e 瓣s e a r 幽睡恣重& u so nl 玲wt o 斑l p l e m e n t 蠡s ta n de 衔c i e n ts 砸n gp a t t e mm a l c 撅n g 。 烈。鸭w 潍娃埭主l 印r o v c 蹦斌。硒被蛔般掣o c e s s 粕d 重量玲d e v e l o p 涨溅醴f p ( 遗 t e c h n o l o g y al a 嘴e rn l l m b e ro fs t u d i e so nt wt oi l l l p l 锄e n tf a s ts t r i n gp a 船m m a tc _ l l i n gw i n lp 删l e lk m h ，a r es t m c t u r e sk r v e 啪e 呓e d d i 丘i e 糟n ts t u d i e s 觚d 如s i 辨m a b 静圭蠡惫戮黼。sb c 慨e 髓等p e e d ，鞠端s a 稚蠡e 娥b i i i 够b 撒遍 p l 獬t i c a la p p l i c a 蛀o l l ，t b e s e 脚l e 搬e n t a ：主。璐c a l la l w a y sp l a yl 。e y 糟l e s 虹s o 撒e d e d i c a t e d6 e l d i n 髓l i s 烨f ，w e 烈卵o ar e s e a r 曲o fd e s i g na p p l i c a t i o ns p l e c i j e i ci l l 舭t i o n 辫e s s 甜极s l 玲铷裁毯e v e 嚣c c e l e 耀勃甜s 畦驾p a 蹴诬越蹴k 鑫gp 疆p o s 懿a s l pi sa k i n go fs p e c i a lp l 佻e s s 6 fd c s i 印o d 蠡醒s p e c i 矗ca p p l i c 撕。潞m a b n g 蛔d e o 夙 k 撕e e ns p e e d ，鲫拳a ，c o s ta n dn e ) 【i b i l i 劬m e 如s i g l l e 璐c u s 枷勰a s i pt 0m e e tt l l e 矗瑚滋l do fm 雒yd e s i g ng o 越s s oa s i pi sb | e c o m i i l gm o 托徽l dm o r ep ( p u l a ri 玎 翩妇剐甜a 鞠l i c 旋。璐 a s i pi sa l w a y ss p e 秭a l l yd e s i g n 以砒堪雌岫砸z c db a 6 eo n 也ec u s t o ma p p l i c a 芏i o n 1 kd e s i g i lp r o c e 髂i so 舭= n 鲰i r 川舶哪t h el o c m ，a p p l i c 撕o n b a s e d 锄础y s i sa n d 妇越l da 蕊y s i s ，1 o fw 赫娩龇l 翻略瑟d 耋l i m d 王堍c 量溉腑r i s t i 璐a r e 翱隧匝埝矧铤l d 聪s 弦耐c d 。恕过如s i 咎o fa s 霉始o u l db ck 曲每趣e 萨妇d 弧e 藏攀i l 踞幽落d a l s ob ed e s i g l l e d 、肮mt l l e p r o c e s s o rf o r m ，e 嫩e md c i v e l o p m e n t 锹l de 嬲i l y a c c 倒撇e b y 锄搬l d e d e n g 妇e r s 豫燃赫靠雠sp 职删y 斌l 溅 a n a 王y s i s 也e 硼eo ff e g u l a re x p 嘴s s i o n sa 陋) a n db a c k u s - n 粼f o 滩 s 圆n f ) 毋眦觚 + r ea n db n fa 托b 0 娃ls y n 船f o rd e s c 】两i i 峪也ep a t t e mo fs t r i n g 艘l t c 蛾晦r e s 鹚a 燃抵卸蝴嘞妞潮弼删鑫诚如v 赫啊靠c 蛔粼煅姻 出堪c k 峨蝴s e to r d e r i n g s ，w l l c r e 也e c l l a ：瞄c t c rs e 幅a r e 赫t e l p 删a 双：0 r d i n gt ot h e 第川页 c 删l o c 采e a u g 躐瓣e db 奈罄嘏8 n 玲转a 翔。式曩e dv e 捧玉强o fb 粼k u s n 3 毛l ff 嘲 i tb a l 蝴c e sc o m p a c m e s sa n ds i 珏l p l i c “y 、i t hr e a s o n a b l er e p r e s e n t a t i o m ip o ，e ra 1 1 d h a sb e e np o p u l a ra i i l o n gm a n yi n t e m e ts p e c i j f i c a t i o n s f i r s t l yw e a n 越y s i s 壤e f l l l eo f 跹，a b 砰a n d 她l a wo f h 麟酶ya 怼潞舔妇纛e 辩蠢西德蕊默纛鸳蠲羝隧a 爨d 融 照瞰筑娃f e 。飘羚建w e 如基n e 也el 戳l i 矬觚娃i o n so f 越o d m e s 勤ro 埘a s i r d e f i n ei 姗【m c t i o ns e to f 炳n gp a 傲m 肌毗l l i n gp r o c e s s 0 r w _ ed e 痂舱as e to fi n 珩u e t i o n sb a s 越o nt b ee k 暇喇s t 主eo fl 乏嚣瑟da 8 n r 麓豳 b s l 粥c t i o n 啾蛾l l 王鑫s e to f 瓿i e 函般蠡o n s 戤通as e t 醴沁i 蝤姗矗。溅。强e b 西ei 越留氍遗。魏s 或掰蛾隧燃地e 辩约i c e s s o rl 掰赡如eg e n e r a lp r o c c s s i n gc 印“b i l 姆 a n dt 1 1 es p e e i a li 芏l s t r i l c t i o ns e ti sd e f m 酣b a s e do n 伍er u l e so f 则m a rp 暑眦e m s 锄d g o o da td c s c 矗b 瓤g 像es 哦嘴m o d e l 斑l 麟b y 璐i 端谯es p e c 谳i 珏删。瓣，耄：k 簸贼n gp 蜘瑚蕊e 嫩鑫gc 鑫建堍黼礴e f a 砖e 援e i e l l t 。 玉埝s e 黝c ho na f c k t e i 魄l l 罄d e s i g no fs t f i n gp a 他mm a = t c l l i n gp r o c e s s o ra l l d m a n a g e m e n to fm e n r ya c c e s 8 i s 斑n gp 鑫鼬mm 蠢稔艇n g 越笋蠢畦l 璨s 妇p l e n 塾瞅氪磁o ng e 粼薯a lp 嘲p o s ep d s f s 瓤s 姆溯氍圉堪锺脚积& j 嗣辨擞鸡。以娌锣e l e 强d 瓿珏燃燃憾c h 龆1 峪e 也| e 茧l r o c e s s o f 盘朝【u e l l t l ya c c e s s 毫on l em e m o r y ，l e 巅l 证gt op i p e l i n eb u b b l e 觚dc a d l e m i s s 泌g ，a n dp o o rp e 嘏翔嘲擞o fg p 魏i no r d e rt oa c 董l i e v em u 施静鼢铉a c c e l e 残撼冁 强s t r i 扭gp a 蹴m 趣豳溺嚼，氇。酝i 鼹醯a s 窿s 酗毽l d 醚d r e s s 攮e 忿p 妁b l 撒s 越d 棼v c 董l 嫩娃撼s o l 峨滩s + 砥k c ym o d l l l e s 硝a s i pi s 如s i g n e dt oe 娩c t i v e l ys u 】) p o n 也e 靼i e c i 越i 蜘c t i o n t s o 吐l a t 也e 、) 1 7 ：h o l eo p e r a ：t i o no f 也ep i o c e s s o rc a nb em o r e s u 诹内l ef 醅蛳n gp a 专t e mm a 钯艇n ga 薹g o f i t ：蛔腾融a d d i t i o n ，t o 内f 瞧c fe n 量l a 掰鼍量l e p 鑫穗l l e l i s 掰醴趣s 弧砥。嗡粼赫枉勰d e 羹秘o f 鞠| l 谯壤辩筘娥瓣螨曩跫 c o 魏s i 出：r e d 垂沁卿b e so nb o wt 0c o u p l e 煳啦i _ r e si n0 l - d e rt oa v d i db a r d w a r c c o m l 撕t i o n 粼d e l i v e l 谢，f l y m e 刚n g 贼i t c 毓培a l g 嘶幽煅a l w a y s 龆l l s c 矗芒挪e n t l ym e m o 巧矗c c e s s i n g 姆e i 饿e fs 斑g l e o 犯涵i p l o 蕊e 躐a 芰i 。鑫o fm h 鑫一c o 遮攀l e 韵躲嫩域o n ，曩捌醭b 瓣，鲜掣磷戚鑫沦毯朗黟爨醐删躐瓣l 毽主。粥毅罄诅s o 幻犟蝴翘n tp 暑峨o f t l l es t u 戤 b o t l ls i n g l e 啪r ep r o c e s s o ra n dt h e 血迸啪r cp r o c e s s o ra 瓣i l l l p l e i 】舶砸o n 新e l d 跏黔龃璀滋，l eg a 谂橱s 蹬残a ) 秘撼r e s 试钰羽嘛w 攮懿蠢擒s p c c 瓣受毽彀聪so 鼗。嚣 a s 王p 潮粼娥也e 辩豳0 f 删枷蜊运矩强娥c a n b ce 魅烈v e 主珏p a 晒雠髓c e 第1 v 页 o f s t r i n gp a t t e mm a t c l l i n gb yc o m p a r i n gw i m s o m eo t h e rg p p s m a i nc o n t r i b u t i o n so f l i sp a p e ri n c l u d e ： t o d a yn 鳓r k - b a s e ds t r i n gp 撕m a t c h i n go fh a i l d l i n gn o to n l yn e e dt o i l n p r o v et h es p e e do fs t r i n gp a 骶mm a t c h i n g ，b u ta l s or e q u i r en e x i b i l i t ) ra u l d v e r s a t i l 时mt h i sp a p e r ，w ep r o p o s ear e s e a r c ho fd e s i g i la s i pv 航c hc 觚t a k ei n t o a c c o 嘶b o t l lo ft l l er e q u i r e m e n t sm e n t i o n e da b o v e n 啪u 曲ad e d i c 砒e da s i pa r c l l i t e c n 聆p m c e s s ，w ef o c u s0 nh o wa c u s t o m i z e da s i pi ss 协i c t u r e da n d l e s i g n e d 丘o mr e a i i 哆，a n dh o wt o 如r t l l e ri i l l p r 0 v e 也ep a r a l l e l i s mo f 也es ys _ 钯m 缸以d e l i v e rl l i g h e rp e r f o m l a i l c e s o m ek e ym o d u l e si sm 饥t e d 觚dc a r e m l yd e s i g i l e dt 0r e d u c em e 丘e q u e n c yo fm e m o 巧a c c e s sa n di n l p r 0 v et l l ed j e i c i e n c yo fp r o c e s s i n g t h e 劬c t i o n a n d 咖舳腿o f t h e m o d u l e s 丽l lb e 姻e a b l ea n dh e l p f i l lf o rr e s e a r c h e si n 钍l i sf i e l d k e yw o r d s ：s t r i n gp a ! t t e mm a t ( 牺n g ，a p p l i c 撕s p e c i f i c1 1 1 s 觚c t i o np r o c e s s o r ( a s i p ) ， a u 舯e m e db 洳- 】i i rf o 珊o 忸n r f ) ，h 删。玛删t o 咖鹏，f i e l dp r o 莎m n a b l e g a t e 却s ( f p g a ) ! 第v 页 插图目录 插图目录 圈l 。l 计算机安全系统的闭环结构 图l - 2p 【o m 2 】中再次出现研州】一5 图l 一3p 【o m 一2 】中没有再次出现t 【l + 习一5 图l _ 4u 再次出现且前缀不同于l 。6 图1 5u 没有再次出现或再次出现前缀是l 6 图1 6 四种基本规则的n f a 逻辑实现7 图1 7 ( ( a l b ) 水) ( c d ) 模式规则的逻辑实现7 图l - 8 洲和c a m 结构原理比较9 圈1 9 一种字符串模式匹配系统的原理框图1 0 图1 1 0 基于b l o c ) mf l m r s 结构的n s 系统1 1 圈1 1 la s i p 在嵌入式系统中韵运用：| 1 3 图1 1 2a s l p 与其他芯片的属性比较 4 图董。1 3a s l p 设计步骤 5 图2 1 传统的系统设诗方法2 4 图2 2 基于平台的设计方法2 6 图2 3 设计的层次化模型：。3 3 图2 _ 4 基于描述语言的设计流程3 4 图3 1 指令集设计流程4 2 图3 2a i 删指令操作流程4 4 图3 3r p t 指令操作流程j 4 5 图3 _ 4o p t 指令操作流程。4 6 圈3 5c 触五指令操作流程4 7 第d ( 页 撬蛰娶蒙 图3 6 数据通路原理糕图5 2 豳3 。7 通用寄存器文件5 3 图3 8 控制通路原理框图5 4 图3 。9 处理器流水线。5 4 图3 1 0b t b 工作原理j 5 5 图3 1l 循环寄存器文件结构5 6 图3 1 2m s s 和m f s 结构原理霹 图3 1 3m 醛入栈工作原理鞠 霉3 1 4 瓣s 出栈工作原理鹦 霜3 1 5 存储嚣结梅设计 鹜3 。1 6e a 疆溅理8 1 t 圈3 。1 7 协处理器熬功毙摸块框图6 2 萋3 堇8 震平蜃的规剿瓣“，。6 5 图3 兰9 双核设计原理6 6 图3 2 0 双核构架垂勺字符串模式匹配处理器原理框图。6 7 塑3 之1a 8 n f 指令在双核处理器的执行情况j 6 8 图3 也2 单核指令处理懈双核指令处理6 8 图3 之3 双核字符串模式匹配处理器的存储器组织。7 0 图3 2 4 编译器组成j 7 1 图3 - 2 5 专用处理器编译器的主要王俸环节豫 圈夺1s l p 消意体结构粥 图4 _ 2o s l p 模块他结构7 7 霆4 ，3 测试平台实物蓬_ 。k ：7 8 蓬4 譬测试平台模块框圈7 8 匿霹忐测试平台主实现豹s l p 协议棱功熊框霉8 1 第x 叛 插图目录 圈4 6 服务器启动画面8 2 图4 7 注册过程8 3 图4 8 呼叫和信息交互过程8 3 图4 9 重定向过程8 4 圈4 1 0 性能测试的方法实现原理8 5 图4 一l l 专用处理器与通用处理器的性能对比8 8 第x l 页 表格强暴 表格目录 表格l 一量常用设计工其。2 0 表格3 兰e 熹e 嚣嚣结构参数，。6 l 表格凄王双核处理器的资源占耀情况8 0 第x 弱菱 中国科学技术大学学位论文原创性和授权使用声朗 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人曼经发表或撰写过的研究成果麝与我一圆工作的同志对 本研究所傲的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即； 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 徭检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密詹也遵守此撬定。 作者签名：。阻 基年二月? 日 第 章绪论 第l 牵绪论 。1 字符串模式匹配的背景 字符串模式题配从方式上可分为精确匹配、模糊遴配和表达式聪配。其中表 达式匹配鹣功能则是投据表达式熬摇述( 如燕麟表达式、巴荛簸范式) ，在数懿 痒捌中我滋巍够被表达式接收的所有子串的线现俊置。袭达式遥配主要煺来处理 简单的序列隧配无法攒述的阀题，是精确匹配算法和模糊匹配算法的增强模式。 字符串模式匿配技术广泛应用于入侵检测系统、两络报文解析、抉蘧文本觜 感过滤、全文检索系统、计算橇瘸毒特征码强配戮及姨序剽廷嚣等领域中， 匿酝算法躲好坏蛊接影响该系统效率酶关键。接下来会缨字符串模式莲配技拳的 几种应用。 入侵检测的概念是j 襄赶溅髂鳓在董9 8 年霹露第一次掇穗f 董】，榴院子防火墙翡 静态防护技术，入侵检测是对防火壤技术鳇穗补充，是一种磷态主动酶安全辨 护技术，提供对内郝攻鸯、外部攻彘寝误操律的实黠保护，能在网络系统受到蔻 窖之前拦截和响应入侵。这种动态主动的僳护系统也使褥入侵检测砸成为计算机 瞬络安全鹣核心研究翅题，成焉实现瀚终安全的新戆解决策珞。雩 入入橙捡溅技 术檑当予在诗算瓴系统孛孽l 入7 一个翔环的安全策略。如圈重 错示。计算枫 的多种安全策略，如：防火墙、身份认证、访嬲控制、数据加密等，通过入侵检 测系统进行安全策瞎的反馈，从丽遴行及时地修正，大大提离了系统的安全性。 陲l - l 计算橇安全系统懿越嚣缝梅 在这种环境下，入侵检测系统成为安全市场上毅的热点，不仪愈来愈多她受 到人们的关注，而且已缀开始在各种不润环境中发挥其关键作用。掰前，太多数 入侵检测系统彘曼个基本摸块组成：事 攀提取、入橙分擀帮入侵响应。事件提取 篱炎 第孽章绪论 模块妖蔫息源获墩数据。数据豹来源豸戬取鸯系统静不弱层次，霹以是主褫熬匿 惑信患、系统状态变化信息，也可以是网络上的数据信息，甚懋是流量变化等。 入侵分析部分的作用在于对来自信惠源的数据进李亍深入分析，判断是否正有入侵 或已有入侵发垒，并传递结栗绘楚璎模块。天最赡应鼯结栗处理，诿摸头鼹棒震 在于对系统所检测劐酶入侵徽出一缀撮警或警告。绝大多数的网络防火墙系统与 基予误用模型的入侵检测系统，其工作都依赖于对网络数据包或系统调用序列等 采样数据进行的过滤，并通过从中发现与已知趣赠集巾各规则的匹配，款蔼检测 出相应的系统安全入侵。这些信息过滤、规烫 j 旺琵的过程都基予字符串匿藤搜索 算法。入侵检测是网络安全孛关键搜零之一，霹嚣入侵检测系统的热则库般包 含a 万个字符，如姥太量静字籀串诞鬻需要赢效的匹配算法。在软件处理孛通常 采用b f 【2 1 、咿【3 】、b m 【4 】等算法，但它们的速度都受铡予e 附的顺序缝理结 构，随着黼络的流量飞速增长，基予辕箨的入畿捡测系统已经不缝满足千熬麓络 繇境中黠大量字蒋串遴孬匹配的实对处理需求。剁终了入侵检测系统的可靠性， 幢网络安全受到了极大影响。霞前蓬内於都在致力予解决这一簸颈麴研究，提崮 了各种基于硬件并行处理的高速入役检测系统。 酗燃赫率些基予文本缩褥懿应耀层协议标准，翅s 潆、。籁期潆、s 嚣矬棼， 多数是巍a 戳晤( 增强型巴竟巅范式) 瑟磷；述鲍。例如会话初始协议( s 撑) 【6 1 的信令，即s i p 消息，用予会话连接的建立及修改，冀消息格式与h 酣r p 协议的格 式狠像，截括三个部分：起始符、潜意头和消息体。任何消息都镪括这三个部分。 s 翠协议栈墨酶漕愚簿橱摸块，又称先s 臻簿鸹攒块，一般蒸把备黪s 玲消息统一 封装一个在结构体中进行统一解析，其解耩蒙理相当子对s 薹p 豹r 薹e 的删规范 语法进行c 语言描述，主鼹是基于字符串模式匹配操作，根据特定的字段进行判 断，得到需要提取的消息域篷。目前帮场上已有的黼编解礴器都是软件实瑗， 其获点是速率缀低，镄甜资漂占耀较失，绘整今系统设诗造戏缀太熬瓶颈。懿s l p p r o x y 溅型机的研制，就存在这个润题。所以很有必要针对网络报文消息的特 点，研究提高报文消息解析的算法和方法，来解决大型服务器中阿络报文消患解 鹃的瓶颈翘题。 粼a 痔列是每一种生物韵生命谯羁f l ，该廖捌可以看成虏趟个基本字稽( a 、 t 、c 、g ) 组成的字符串，因此生物计算科学中餐找特定的d n a 序列，也是字 符事模式匹配算法的个重要应用。哺乳动物的狲峨序捌非常长，柳鲡，人类 麓辩姨序舞大概煮焚却。在翻姨痔裂瘁里快速搜索篥饕淤蠛穿建模式悬生 第2 荑 第1 章绪论 物计算科学中的关键技术。就渊a 序列数据酶艨阕焉言，方藤需要考虑数掭 的存储效率，另一方磊也蔡考虑数瓣的检索速度。考虑数据的襻髓效率，需要将 渊a 客列数据压缩磊褥进霉亍存储，这样可以在有鼹的荐麓设备上存储更多信惠。 叠 予渊a 序列数据酶特殊性，帮渊a 序列数据漱a 、善、c 、g 翟个字母组成， 并且渊a 廖捌长度硪达上西万个碱基对，使用传统的数据蓬缩算法并不理想， 需要研究专门锋黠磁妊序列数据的压缩算法。考虑数据的检索速度，一方面要 设计好酌橙索算法，另一方蘅要考虑懿籍使蔫压缩嚣酶数蠢。邋常使雳压缩数据 的方法是先对数据解压缩，再在解篷缝数据上进符检索。采耀这释方式，在计算 巍上实际健用压缩数据时，并不是真避意义上地减少空闻，也不裁改善检索速度。 著毖够在压缩数据上直接进行检索，既提高了检索速度，又丈大节省了使瘸时酶 存储空闻，有助予将渊a 序列数据迁移到普通性髓的工律平台栩】笔记本电藏或 段坳上，使得生物学家可以随时随地汗展研究王佟。在压缩数据上直接进行傣 息检索的实质是对匿缩数据壹接进行模式匹配，称蕊瑟缩模式匹配。这已辱l 起诗 算撬及穗关学群磷究人员的关注。 2 字符串模式匹配加速算法的相美研究 字符串嚣配蹩研究怎样苏快速、有效煞方式来准确我惠鎏标锖惠源串感兴趣。 的特定予串镶息的搜索方法。经过多年的研究，在纯软件实现上，人们已经褥到t ? 数十种不阉的宰匹配算法，如套鹾垤算法，赠潍算法，b m 算法等，它们从 燕革翔复杂、麸低效刘离裂、款单模式涯配裂多模式匹黧翁不断发展，匹嚣算法 理论辽经糕对毙较成熟。下面藏次分绪这凡释算法的原理耱特点。 1 2 i 懈算法 釜舔转冀法是最原始的字符事匹熬算法，主簧燕予夺蔑摸酶模式嚣鬻。菇w 算法的伪代码大致如下； 馘脚吲溉鼍溉珊 被萨曩融，搬- 喂蛔酣囝； 稻珩燃。热静；o 熊e k 嘲嘲；o 蕊e 转心 封妒瓣l 】，镧嘲s ( 琊撩躐胡融争溉- l 辩 巍嚏翻激。囊睫 髂3 燹 第1 掌绪论 式内嚏搬一l ： n a i v e 算法的时间复杂度是o ( ( n 搬+ l 妞) ，粗略地说大致是露2 。 1 。2 。2k 嬲p 算法 该算法的时嗣复杂度力o ( 嫩乜) 。其改进在于：每当一趟匹配过程中出现字 符不等时，不需回溯目标串，丽是由已经得到的“部分匹配 的结果将模式串向 右“滑动尽可能远的一段距离蔗，继续进行比较。移j 如使用贼p 算法的s 串 耩零串的匹配过程瓤下： 第一趟匹配： s ：aba b c a b ca c b a b = = t ：a3c a c 第二趟匹配： s ：a b abcab ca c b a b = 茹= = t ：ab cae 第三趟匹配： s ：a b a b c abcacb a b = t ：abcac 当第一趟匹配孛譬标睾孛第3 个字符( 位鬻戮下雳i 标识) 期模式睾巾第3 个字符( 位置以下用j 标识) 不相等时，i 不变，模式串向右“滑动，即从模式 串第j 个字符之前查找一个字符代替第j 个字符和目标串的第i 个字符继续比较。 在第二趟匹配中就是用第1 个字符代替第j 个字符与酲标串的第i 个字符进行比 较。 。 薹蝴p 算法在形式土与基本模式匹配算法棚似不问之处仅在于滑动的距离不 一样。懈，算法在当模式与主串之间存在许多“部分匹配的情况下时才显示邂 其时闻的优越健，虽箕最大特点是指示主串酶指针不需霾溯_ 辍头至尾少箍一 遍，这对处理从外部设备输入的庞大文件很有效，无需重读，可以边读边题配。 第聿贾 第1 章绻论 1 2 3b m 算法 该算法在匹配过程中模式串p 【o ，l ，2 ，m l 】由左向右移动，而字符的比较却 自右向左进行，即按p ( m 一1 】，p 【m 一2 】，“o 】次序进行比较，当文中字符与模式不 殛配时，根据两个预先定义的偏移函数b 赫c 鼢和毛b o 蠡u 麓x 计算出偏移量。 偏移函数b 醚c h 嚣和g d s u 撼x 的原理： 假如当比较进行到文中的j 处，新一轮比较从右向左进行，t 【m + lj + m l 】= p 【i + 1m 一1 】，失配发生在t 【i 巧】- b 与p 【i 】毪处。 b 醛c k f 移动过程分两种情况： ( 1 ) 将文中字符t 【i 勺】和它在p 【o 擞- 2 】中从右向左首次出现的位置对齐 ( 如图l - 2 所示) 。 ， 二二二二二二二工 二丁王二互 矿 口二墨匦 图1 2p f o 们】中再次出现可i 勺】 ( 2 ) 如果在模式中没有t 州】，则将窗口的左端点与t 勺十l 】对齐( 如图 董。3 所示) 。 圈l - 3p 羚瓣- 2 l 巾没鸯再次爨现砭啊】 g ( o d s i l ：晒c 移动过程分晒种情况： ( 3 ) 如果u 再次在模式串中出现，且u 前面字符不是a ，则将模式串最右 端再次出现的且前面字符不是a 的片段与文本串t 【i 巧+ lm 1 】对齐( 如图1 4 所示) 。 第5 茭 第 章绪论 ，4 二二二二二 二二二 二 p 二 匾二二 鬻lon 再次凄现豆前缀不列予l 4 )翔果毽在模式孛没有再次蕊现，或孬次绻现但毯翦麓字符是a ，将片 段t f 确+ l 趱一l 】中最长的后缀v 与模式串前缀v 对齐。若不存在这样的v ，则模 式串跳过u ( 如图1 5 所示) 。 匕二二二二= j 互二二卫【= 二 p = 丁互= 口 i p 匠 = = = 巨l * 5 u 没有再次密现或再次宙瑷蓠缀是i 一 每次计算偏移量取c h a f f c 】吨l + l 和蛐u 笨x 【i 】最大值来决定模式串酶右移量。 b 醛算法是一个较饶的模式匹配算法。一般，如果不考虑模式串豹长度， 一个具有时闻复杂度o ( n ) 的算法应该是最优的了，但是事实不是如此：b m 算法 可以实现更高效率的模式匹配。分析和实验说明，b m 匹配算法对于那些字符集 比较大，丽模式串书出现的字符比较少静时候，工作效率最快。 2 。毒硬件加速 以上提裂的算法都是基于软件实现熬字簦枣莲配算法，随蓑耀终与信息技术 的高速发展，许多应用领域对字符串匹配嚣着越来越高的速度嚣求。在这些有多 模式高带宽匹配需求的应用中，现有条件下单纯依赖软件方法来实现时往徒性能 难以达到要求，因此必须考虑从硬彳串方面来寻求匹配闻题的解决途径。露翁字符 串模式匹配在硬件实现孛主要集中在骇下三个研究方囊。 ( 1 ) 基于自动机 基于自动机的方法是把字符串集合转化为难则表达式在硬件中实现，国外前 期的研究中较多的采用这种方法。其中，s i 弧f 8 】等人提豳的使用硬件逻辑构造 掇弧( 不确定状态枫) 来对满足某个真僮表达式鳇一类字符串进行高速匹配的方 法，为近几年基于自动机的纯硬件解决字符串模式匹配的研究奠定了基础。针对 第6 页 第 牵绪论 疆烈表达式的嚣种基本操作：r l 贮、f l 珐、f l 橐、0 1 ) ，以及其相应的n 融，设计 7 四种基本的逻辑单元，如瑟1 6 ： ， 鑫 、潮 瓣秘 图l 四种基本翘则的n l 强逻辑实现 根据这四种基本逻辑单元，可以设计任何正则式表达的模式翘则，例如：规 赠( 捌妨枣) ( c d ) 相应模式嚣配盼逻辑设计如图1 7 ； 豳l0 始洚y ) ( i 话) 模式撬燹| j 的逻辑实现 这种逻辑设计方法易在f p 国里实现，每个时铮溜嬲可以处理一个字符， 速度相黧侠，但缺点是占耀的逻辑资源太大，随着字符串长度、数量的增加，焉 f p 後实现 a 的复杂度也大幅增加，即g a 瞻部连线的延时也随之增加，导 第7 页 第| l 章绪论 象系统黠钟频率降低，因越难黻实瑗燕窝络掇文这静大飒摸翦字籍串模式娥裂。 另外一点就是灵溪性不强，在实际应用中，规则会不断的增加、升级朔更新，使 用这种方法需要噩掰对新规则进行开发，重新配置f p g a ，这给歼发入员辅维护 入员带来极大的不便。s i 蘸融等人豹研究串瞧给惠了矗按觚篾剿熬翊漶箍述巍 动生成褶虚趋辩羹黔代码，可豢搂进行编译综会。在提高灵活性方西，s i d l l u 给 出基予s r e 迭( s 谢二龇n 6 9 u r a b l eg a t ea 翩嘴够) 的研究方案，但s r g a 本身不太 成熟，在链麓和容量上都骞一定的缺陷。 基于自动机的嫒律实瑗字符串模式琶懿算法翁最大特点就是并苻幢菲鬻高， 在瓣络入侵检溯系统中应用起来非常方便。c 蛔等人翻设计了种基于f p g a 并行处理结构的入侵检测防火墙，就是基乎这释技术。【9 】中对每种入侵检测的 规则酃单独设计，并行处理。蓠先，数撬翘通过3 2 蠢斑总线进入痰剥处壤攀元， 然蔗，数据包的龟头先与预先定义菸存麓在f p g 凌里的趣头进霉亍魄较，擞果匹 配成功，褥对数据包戆爽容部分进行模式毯飘，模式匹配单元包括些8 出i t 的 寄存器_ 帮8 南i 熏韵比较器。为了提高霉吐量，模式匹配单元进学流水线设计，每 级流水线可处理丽时处理4 个字符，实现结果表髓这种结构在时锌频率涛m 您 盼瀚毵下处理速度达到2 8 8 g b 举，平蚜每个模式援剃占用1 0 个l 琰毛哦c e 熬) 。 ( 2 ) 基手蠹容可寻蛙存媸器 基于内容可寻址存储器( c a m ) 的方法逶譬前渡界较成熟酶字符率嚣配硬 件实现方法。该方法可以在单时锋瘸辩判断输入的数据与琵存数据是否题配，并 绘热殛配数据颈熬黠应地蛙毫 渊是一种专门为快速查找数据照缝蔼设计豹稃赭器。e 燃透过把输入数 据与其内所存数据相比较，能快速确定输入数据是否与其内部菜个数据或某几个 数搽楣匹配。c 触谨酶数据寻缝方式露应焉要求不弱焉不阕，最捷方式下饺需要 一个封钝羯絮傻可完成黠溪有数据熬寻址。毒燃一群，c 嬲也是采取阵列 式数据存储。其数据的写入方式与r a m 麓不多，但c 朋诫的数据读取方式却与 洲不同。在蝴中，输入的是数据地址，输出的是数据；而在洲中， 输入懿是掰要查邂熊数蠡，输璐熬是数据媲缝帮嚣黧标恚爨缎e 埝。菪逛配f 黧数 据搜寻到，裂输礁数据地址。在黜艇孛，霹渔m 翦存储容量由遗缝线宽度确定。 例如，1 0 b i t 宽地址总线的r a m 存储容量为2 1 啦1 0 2 4 个字节，c a m 却没有这个 限制，因为它不是采用传统韵邋过地蛙读取数据懿方式。糍若获l 睨毒个字节串 查谗菜一鼗据，输入数摇塞囊蔻豹i 童，数据存在裂蠹输交匹配耩恚、差转魄宽熬 第s 菠 第 牵绪论 数据遗址以及查询的数据位数决定。如霭1 8 为数据读取模式下的c a m 和姒m 的比较。 r a m c a m 8 x 1 0 2 4 8 x 1 0 2 4 ram读取模式cam读取模式 图1 8 姒m 和c a m 结构淼理比较 显然，e 脚的数据查询速度远远高于删，透此c 删大量应焉于高速数 据处理的系统中。c a m 的如现加快了些系统和技术的应用，如大型数据库管 理、数据连接、模式识别等在图像识别、语音识别中的应用。c a m 的核心为存 储单元阵列和存储单元与输入数据之间的比较器。不同的应用对于c a m 的数 据、密度有不圊酶需求，丽盟实现c a m 的途径也是多样麓。随着f p g a 内部结 构的改进以及容量的迅速增加，采用基于c 触垤的方法进行字符串匹配查找的优 势开始明显起来【1 0 】【1 l 】【1 2 】。x i l 妇公司开发的f o 删o n 系列软件和n e x 系 歹l jf p g a 为c 触涯的应用提供了优越的软硬件条件，而且r 鼢( 最大优点是没有 必c 蒯提供固定的模式，它设计的灵活性是c 埘能在不同条件下、不同领域 内以不同方式实现，达到最优化。基予c a m 的实现方式有多种途径，利 用r t e ) ( 芯片内可编程资源b l o c ks e l e c 妇幽u 是实现c a m 的途径之一。一个 b 撇s e l e c 删可配置成一个1 6 撇8b i t 的c 删基本模块，且有独立盼读 写双通道，这得益于b l 烙e l e c 删的双躁特性，b l 溅s e l e a 臣淤m 是真正具 有独立双通道的存储器，它的每个通道拥有各自的时钟和控制信号，a 口和b 口可独立配置成4 0 9 6 w r o r d x l b i t 或2 5 6w i o r d x l 6b i t 靴蝴模式。基于b 1 0 c k s e l e c 傣a m 的c a m 的设计正是利用了b l o 呔s e k 爆a m 内部地址映射的灵活性。 a 和b 具有共同的存储单元( 4 0