（信号与信息处理专业论文）基于fpga的正则表达式匹配技术的研究.pdf

哈尔滨理- e 大学t 学顾f j 学位论文 基于f p g a 的正则表达式匹配技术的研究 摘要 j 下则表达式，因其具有强大而灵活的表达能力，故成为近年来串匹配的 研究热点。很多基于协议识别的网络安全管理系统，如入侵检测，内容过 滤，防火墙等已经越来越多的使用f 则表达式来描述他们的规则。作为整个 系统的核心，匹配引擎的设计好坏已然成为了影响系统性能的决定性因素。 传统方式采用软件来实现正则表达式匹配，以串行的模式工作，这种方 式吞吐率低，而且占用了大量的c p u 资源，随着网络流量的同益增长，无 法满足人们对网络安全的需求。因此，本文利用硬件实现的方式解决低吞吐 率问题，结合f p g a 的特点设计实现了基于f p g a 的正则表达式匹配引 擎。 本文首先分析了币则表达式的特点及优势，然后讨论了它的两种可实现 的自动状态机，针对n f a 正则引擎详细漫计了f 则表达式各类元字符的映 射电路，并在此摹础上结合f p g a 的自身结构迸行优化设计，提出了可共 享比较器的字符匹配模式。通过这种并行性的工作方式加上资源共享的设 计，大大节约了逻辑资源，且提高了吞吐率。 整体设计采用先进的层次化设计思想，规则库更新时，只需加载对应的 上层模块即可，不用考虑底层模块的设计，考虑到f p g a 可重复编程的能 力，使得升级规则库变得简单易行。本文设计的正则引擎是一周期一匹配， 在v i r t e x 5 系列f p g a 上可达8 7 g b p s 的匹配性能。 关键词正则表达式；非确定有限状态机；协议识别；f p g a r e s e a r c ho n t e c h n i q u eo fr e g u l a re x p r e s s i o n m a r c h i n gb a s e do nf p g a a b s t r a c t i nr e c e n ty e a r sr e g u l a re x p r e s s i o ni sa h o t s p o ti nt h es t r i n gm a t c h i n gf i e l d d u et oi t ss t r o n ga n df l e x i b l ee x p r e s s i o n a b i l i t y al o to fn e t w o r ks e c u r i t ys y s t e m s b a s e do nt h ep r o t o c o li d e n t i f i c a t i o n ，s u c ha si n t r u s i o nd e t e c t i o ns y s t e m ( i d s ) ， c o n t e n tf i l t e r i n gs y s t e ma n df i r e w a l lh a v eu s e dr e g u l a re x p r e s s i o nt od e s c r i b e t h e i rr u l e s a st h ek e yo ft h ew h o l es y s t e m ，t h ed e s i g n i n go ft h em a t c h i n g e n g i n e h a sb e c o m et h ed e c i s i v ef a c t o ro f a f f e c t i n gs y s t e mp e r f o r m a n c e i nt h et r a d i t i o n a l w a y , r e g u l a re x p r e s s i o ni ss o f t w a r eb a s e d i tw o r k sa t s e r i a lm o d e l ，w h i c hh a sal o w e r t h r o u g h p u t ，a n dt a k eu pal o to fc p ur e s o u r c e s w i t ht h eg r o w i n gn e t w o r kt r a f f i c ，i ti su n a b l et o m e e tt h en e e do fn e t w o r k s e c u r i t y t h e r e f o r e ，t h et h e s i su s et h eh a r d w a r et os o l v et h i sp r o b l e mo fi t sl o w t h r o u g h p u t c o n s i d e r i n gt h ec h a r a c t e r i s t i c so ft h ef p g a ，t h et h e s i si m p l e m e n t s r e g u l a re x p r e s s i o nm a r c h i n ge n g i n eo nt h ef p g a t h i st h e s i se x p l a i n st h ec h a r a c t e r i s t i c sa n da d v a n t a g e so f r e g u l a re x p r e s s i o n a n dt h e nd i s c u s s e si t st w ok i n d so fr e a l i z e da u t o m a t i o n b a s e do nt h en f a i t g i v e st h ed e t a i l e dm a p p i n gc i r c u i t so fav a r i e t yo f m e t ac h a r a c t e r s 。a n do p t i m i z a s t h e d e s i g nb yt h ew a yo fg i v i n gas h a r i n g c o m p a r a t o r t h r o u g hp a r a l l e l p r o c e s s i n ga n dr e s o u r c es h a r i n go fd e s i g n ，i t sa b l et on o to n l yr e d u c et h el o g i c r e s o u r c e s ，b u ta l s oi n c r e a s et h et h r o u g h p u tg r e a t l y t h eo v e r a l ld e s i g na d o p t sa d v a n c e dh i e r a r c h y d e s i g ni d e at os i m p l yl o a d c o r r e s p o n d i n gt o pm o d u l e s ，n om a t t e rh o wt h eb o t t o mm o d u l e sa r ed e s i g n e d ， w h e nt h er u l el i b r a r yo fr e g u l a re x p r e s s i o nn e e d st ou p d a t e i ti se a s yt o u p g r a d e l i b r a r yd u et ot h er e p e a t a b l ep r o g r a m m i n ga b i l i t yo ff p g a t h ef i n a ld e s i g nh a s b e e nt i m i n gs i m u l a t e da n da m o u n t e dt o8 7g b p sm a t c h i n gp e r f o r m a n c eo nt h e v i r t e x - 5 ，w h i c hc o u l dm a t c ho n ec h a r a c t e ri ne a c hc y c l e k e y w o r d sr e g u l a re x p r e s s i o n ，n o n d e t e r m i n i s t i cf i n i t ea u t o m a t o n ( n f a ) ， p r o t o c o li d e n t i f i c a t i o n ，f i e l d p r o g r a m m a b l eg a t ea r r a y ( f p g a ) 哈尔滨理1 _ 大学t 学硕i j 学位论文 第1 章绪论 1 1 课题背景 根据c n n i c ( 中国互联网络信息中心) 2 0 1 0 年7 月发布的第2 6 次中国互联 网络发展状况统计报告显示： 截至2 0 1 0 年7 月，中国网民规模达到4 2 亿，突破了4 亿关口，较2 0 0 9 年底增加3 6 0 0 万人：互联网普及率攀升至3 1 8 ，较2 0 0 9 年底提高2 9 个百 分点。宽带网民规模为3 6 3 8 1 万，使用电脑上网的群体中宽带普及率已经达到 9 8 1 t 1 i 。这标志着我国已经步入互联网大国的行列，网民在网络上收听网络 音乐、阅读网络新闻、即时通信、观看视频、搜索购物、收发邮件、网络游 戏、访问博客个人空间、论坛b b s 等，这充分显示了社会生活对网络的高度 依赖性。 1 1 1 网络与信息安全的威胁 网络信息作为一种资源，它的普遍性、共享性、增值性、可处理性 和多效用性，使其对于人类具有特别重要的意义，但随之带来信息泄露、 窃听、网络诈骗、木马病毒也应被高度重视。根据c n n i c 第2 6 次中国互 联网络发展状况统计报告显示：半年内有5 9 2 的网民在使用互联网过程中遇 到过病毒或木马攻击，遇到该类不安全事件的网民规模达到2 5 亿人之多。 2 0 1 0 年上半年，有3 0 9 的网民账号或密码被盗过，网络安全的问题仍然制约 着中国网民深层次的网络应用发展。调查发现：8 9 2 的电子商务网站访问者 担心访问假冒网站；而他们如果无法获得陔网站进一步的确认信息，8 6 9 的 人会选择退出交易。互联网向商务交易型应用的发展，急需建立更加可信、可 靠的网络环境。 显然，对网络系统的安全性与可靠性问题的研究已经刻不容缓。面对网络 与信息安全的挑战，我们只能不断发展更新更有效的安全保障技术，从网络的 每个层次来对抗这一威胁，才能使网络更好的成为人类的工具，为经济发展和 社会进步服务。 哈尔滨理t 人学下学硕j j 学位论文 1 1 2 网络安全防护技术 目自 ，国内外主流的网络安全防护技术有防火墙技术和入侵检测技术。防 火墙技术是指一个由软件或和硬件设备组合而成，限制外界用户对内部网络访 问及管理内部用户访问外界网络的权限i 劲，可借由监测所有的封包并找出不符 规则的内容以拦截病毒或是木马，它能极大地提高内部网络的安全性，并通过 过滤不安全的服务而降低风险。传统的方式一般是对包头进行扫描，进而做出 允许或禁止网包是否通过的判断，但是这样的方式却无法发现隐藏在数据包载 荷中的不合法内容，对于针对应用层展丌的攻击是无能为力。因此，基于深度 包检测( d e e pp a c k e ti n s p e c t i o n ，d p i ) 的防火墙技术应运而生。它是根据需要 对包的载荷进行扫描与分析，由分析结果决定处理策略。这种做法可以发现隐 藏在网包载荷中的不合法内容，对于防范应用层级的攻击与入侵非常有效【3 l 。 另外，对于网络上的海量信息的检测、评估、管理与控制，内容过滤和入 侵检测也是一个应用广泛而又有效的监控手段。内容过滤分软件实现和硬件实 现。软件过滤主要使用关键词匹配的方式，将特定内容移除。硬件过滤方式就 是将关键词匹配功能集成在控制有大量流量的交换机或路由器中，以对网络中 的流量进行监控；入侵检测系统也有自己的舰则库，使用特征匹配的方式对网 络数据进行分析，判别其是否属于入侵事件的模式，一旦发现入侵后，会及时 作出响应，包括切断网络连接、记录事件和报警等。入侵检测与防火墙最大的 不同点是，防火墙主要分析网外数据，它限制网络之问的访问，而入侵检测系 统所关注的数据包不管来自网外还是网内都会被其系统进行检测1 4 ，一i 。 从整个互联网安全角度考虑，如果要做到全面彻底的防护工作，必须在主 干网上布置一套综合多项安全技术的监控系统，其中对流经主干节点的所有数 据进行实时监测和分析。而无论使用基于深度包检测的防火墙、还是入侵检测 系统，它们的性能很大程度都是由特征匹配的性能决定的。文献【6 】中指出，特 征匹配所需要的占用的c p u 资源高达9 0 以上。因此想法提高特征匹配的性 能，做到解放c p u 也是当今备受关注的焦点问题。 1 2 国内外研究现状 特征匹配的研究从精确字符串匹配开始，它是串匹配技术中最简单的形 式，要求文本中被匹配的字符串与某个模式串严格相等1 7 】。由于提出较早所以 关于精确串匹配的算法已相当成熟，比较具有代表性的算法有a c t 引、w m l 9 l 、 哈尔滨理丁人学t 学硕 ：学位论文 b o m i l 0 等。但随着入侵手段的多样，攻击模式的变化，这种基于字符串的特征 提取变得越来越困难，而正则表达式因其强大而灵活的表达能力可以描述复杂 的特征规则，故为近年来特征匹配的研究重点。 目前，已有相当多的网络安全类产品，如s n o r t t i ，b r o l l 2 i ，1 7 f i l t e r t l 在使 用正则表达式来描述他们的规则集。不过，大部分的系统性能都在几百兆左 右，文献f 1 4 的作者也说明，能够对5 0 0 条入侵模式进行检测的软件系统已经很 难达到1 0 0 m b p s 的数据吞吐率了。由于规则库的规模是不断增大的，而软件系 统中对于模式的检测效率又无法满足当前的需求，所以研究人员将注意力转向 了硬件模式匹配引擎的设计上，希望用硬件的工作效率来提高系统的整体性 能，加大实际吞吐率。 第一个正则表达式匹配的硬件模型是f l o y d 和u l l m a n l l 5 1 于1 9 8 2 年提出来 的，两人用可编程逻辑阵列( p l a ) 实现了一个分层n f a 模型。s i d h u 和 p r a s a n n a t l 6 l 在f p g a 上基于n f a 自动机设计了单字节比较逻辑结构和“连接 ， “或循环 操作的专用电路，并与基于软件实现的文本搜索程序g r e p 进行 了存储空间与匹配时间上的比较。在此基础上，部分研究 1 7 - 2 0 i 针对复杂正则表 达式匹配的数量限定符经行了硬件设计和实现。其中，j b i s p o l l 9 】等人在研究的 最后对s n o r t 中的5 0 0 条规则进行了实验仿真，在v e r t e x - 4 芯片上吞吐率可达 2 9 g b p s 。在基本的比较器实现上，国内的黄建、徐晶【2 i l 提出了一种使用半字 节比较的方法来实现字符串匹配，从而实现更多字节的高速模式串匹配。h s o n g t 2 2j 等人基于三态内容寻址存储器( t c a m ) 采用b v 算法实现了入侵检测 中的包分类。h u t c h i n g s l 2 3 1 用j h d l 语言在f p g a 上实现了s n o r t 中部分正则表 达式匹配。还有不少研究 2 4 - 3 0 l 是针对系统优化的，c l a r k 2 4 l 和s c h m m e l 提出一个 8 - 2 5 6 译码器作为字符的预处理模块，以优化重复的逻辑资源。而胥清化1 2 9 】采 用基于r o m 表的实现方式对字符预处理。c h o t 2 8 1 对分散的逻辑子块进行复用 达到了减小芯片面积的目的。上述的研究都是基于n f a 来完成的，而文献 3 l 一 3 4 1 的工作是以d f a 为基础。d f a 因其自身具有“空间爆炸“的威胁，所以研 究主要放在压缩算法上实现。y u t 3 3 】等提出的分组算法，将规模很大的j 下则表达 式规则集分割为若干组后再进行匹配，极大地减少了匹配过程中的内存消耗。 k u m a d ，】等人提出了d 2 f a 表示方法，通过引入默认转移来减少状态转移的数 目，从而降低自动机的存储空间，但此法会降低一定的性能。 由于国内在应用f p g a 来实现正则表达匹配这一领域还没有过比较系统的 研究，而且对于硬件的结构尚有值得优化的空间，故本人希望能通过这篇文章 给出一个全面而具体的f p g a 实现过程，为以后的研究工作打下坚实的基础。 哈尔滨理t 大学t 学硕f ? 学位论文 1 3 主要研究内容及创新点 本文设计实现了一个基于f p g a 的正则表达式匹配引擎系统，利用f p g a 高 速和并行处理能力解决了以往软件式的低吞吐率问题。本文的研究内容主要包 括以下几点： 一：研究j 下则表达式匹配的实现方法。 二：研究如何根据n f a 模式来实现f p g a 上对应元字符的映射电路。 三：优化系统方案，使有限的f p g a 资源能够支持大规模数量的正则表达 式规则。 基于f p g a 实现该引擎的过程中，本文在借鉴了前人的设计思想上，改进 了针对数量限定符的硬件结构；对于系统的优化引进了共享比较器的思想来解 决单字符重复的问题，该模块较之8 - 2 5 6 译码器更方便范围式字符匹配。然后 针对子缀共享的问题，设计并实现了多端触发器以识别发生匹配的规则。 1 4 文章组织结构 本文的章节组织如下： 第一章：介绍研究背景，分析国内外研究状况，给出主要研究内容和创新点。 第二章：给出正则表达式的相关介绍，讨论其两个可实现的状态自动机，最 后简要的介绍了一个基于协议分析的协议识别软件1 7 一f i l t e r 。 第三章：分析基于n f a 的正则表达式引擎的实现方法，提出设计方案，给出 其关键模块的设计过程。 第四章：对系统进行优化设计，进行总体系统的验证与仿真。 哈尔滨理t 大学t 学硕 ：学 证论文 第2 章正则表达式的相关研究 2 1 正则表达式 j 下则表达式的“祖先 能一直追溯到科学家对人类神经系统工作原理的早 期研究，美国新泽西的w a r r e nm c c u l l o c h 和美国底特律的w a l t e rp i t t s 这两位 神经生理学家研究出了一种用数学方式来描述神经网络的新方法【3 5 1 。之后在 1 9 5 6 年，美国数学家s t e p h e nk l e e n e 在他们两人早期工作的基础上，发表了 一篇标题为神经网事件的表示法的论文，正式引入了正则表达式的概念。 之后一段时问，人们发现可以将这一工作成果应用于其他方面。k e nt h o m p s o n 就把这一成果应用于计算搜索算法的一些早期研究，将此符号系统引入至l j q e d 编辑器罩，这也是诈则表达式的第一个实用应用程序。从那时起直到现在，讵 则表达式都是基于文本的编辑器和搜索工具中的一个重要部分。在主流的操作 系统，如l i n u x ，u n i x ，w i n d w s 和主流的丌发语言，像p h p 、p e r l 、c + + 、c 拌、 j a v a 等都能看到f 则表达式的身影。l i n u x 的数据包分类器1 7 一f i l t e r ，还有入侵检 测系统s n o r t ，b r o 等，都普遍采用正则表达式做特征匹配。 2 1 1 正则表达式规则 j 下则表达式，是用某种模式去匹配一类字符串的一个公式f 3 6 】。它是串匹配 的一种，可以描述一个有穷或者无穷的模式串集合。它由普通字符和特殊的元 字符组成。根据正则表达式解析引擎的不同，它能支持的元字符个数及种类也 都不尽相同。常用元字符，如表2 一l 所示。 哈尔滨理工大学工学硕士学位论文 表2 1 常用的正则表达式元字符 t a b l e2 - 1t h ec o m m o nr e g u l a re x p r e s s i o nm e t ac h a r a c t e r s 元字符描述 匹配任意单个字符 幸 匹配0 或多个正好在它之前的那个字符 9 匹配0 或1 个正好在它之前的那个字符 + 匹配1 个或多个正好在它之前的那个字符 a 必须以指定的字符开始 $ 必须以指定的字符结束 i将两个匹配条件进行逻辑“或”运算 n n 是一个非负整数。匹配确定的n 次。 n ，n 是一个非负整数。至少匹配n 次 n ，m )m 和n 均为非负整数，其中n _ 一c l k 匝圃圣 - e n 亘p _ 一r s t e 一i 一l n 衙d i nd o u t 吨巫卫多 图3 5 比较器模块的外部封装 f i g 3 5t h ep a c k a g eo fc o m p a r a t o rm o d u l e 按照一位热码编码的方式设计比较器模块可有两种形式，这两种形式的硬 件结构都是用到一个触发器，一个单字节比较逻辑，和一个与门。其中，触发 器起到延迟一个周期的作用，它就像一个发动机一样推动时序的发展；单字节 比较逻辑是对固定字符的判断比较，是比较器模块的核心。图3 - 6 为单字节比 较逻辑的r t l 级实现。 a n d 4 黼j a n d 4 潮j 图3 - 6 单字：肖比较逻辑 f i g 3 - 6t h ec o m p a r m i v el o g i co fs i n g l e - b y t e 由于f p g a 中最小的逻辑单元由查找表( l o o k u p t a b l e ，l u t ) 、触发器等构成， 所以实现上面r t l 级功能的实际电路结构如图3 7 所示，这罩用到了一个3 输 入l u t 和一个6 输入l u t 。 惦k 2 一 m a fll j l 哈尔滨理t 人学丁学顶i j 学化论文 图3 7 单字节比较逻辑的l u t 实现 f i g 3 7s t r u c t u r eo fc o m p a r a t i v el o g i co fs i n g l e - b y t eu s e dl u t 在给出了单字节比较逻辑的实现方法后，下面具体给出两种比较器模块的 实现方式。 方式1 ：先延迟再相与，它的结构及工作时序如图3 8 所示。使能信号e n 经过一个触发器延迟一个时钟周期，再与单字节匹配逻辑的结果做与运算。运 算结果d o u t 作为下一个这样的比较器模块的使能端，进行时序控制。比如， 要实现对字符b 的匹配，那么单字节比较逻辑罩就是对b 的比较，输入数据只 有是b 的时候，单字节匹配逻辑输出才置l ，其他时为0 。使能信号在上个周 期有效，但是经过一个时钟延迟后，在本周期内值仍为1 ，所以与运算结果 d o u t 置1 。如此，成功的实现了对字符b 的匹配。 e l k 厂 厂 厂 厂 厂 厂 l d i n 鲫厂 b厂 d o u t 厂 图3 8 方式1 的比较器结构及i ：作时序 f i g 3 8s t r u c t u r eo fc o m p a r a t o ra n dt i m i n gd i a g r a mb a s e d o np l a n1 哈尔滨理丁人学t 学硕i j 学位论文 方式2 ：先相与再延迟，它的结构及工作时序如图3 9 所示。将方式1 中的 触发器和与门调换一下位置，即得方式2 。使能信号e l l 直接与单字节比较逻辑 的结果做与运算，运算结果再经过触发器延迟一个时钟信号。从下图可以看 出，使能信号e n 与单字节比较逻辑的结果在同一个时钟罩有效，结果d o u t 在下 一个时钟里输出。 e n e l k 厂 广 厂 厂 厂 厂 l d i n e n 厂 b厂 图3 9 方式2 的比较器结构及i ：作时序 f i g 3 - 9s t r u c t u r eo f c o m p a r a t o ra n dt i m i n gd i a g r a mb a s e do np l a n2 两种形式的比较：两种形式在本质上是等价的，都是通过单字节逻辑结构 进行判断，用与门实现使能端对比较器的控制，用触发器延迟一个周期，实现 模块之l 、日j 时序关系的对齐。但是在设计上，两者又完全不同，从时序图上看， 方式1 的输出d o u t 与输入d i n 是同步的，而方式2 的输出d o u t 与输入d i n 差了 一个周期。这看似无足轻重的差别，将影响其他模块的的设计，尤其是计数 器。 3 3 2 计数器模块 j 下则表达式中有一类限定重复次数的元字符，即数量限定符。例如： a 1 0 2 4 ，a 1 0 0 ，1 0 0 0 ) 。这类元字符，是对单字节的重复匹配，如果采用将基 本的比较器模块级联，势必会占用非常多的系统资源。所以在硬件实现上，首 先排除级联模式，考虑能否用模块复用的形式来实现该类元字符。一个最直接 的想法是，用计数单元对比较器模块进行计数，计数值如果满足该类元字符的 限定次数，则输出高电平，表示匹配。 哈尔滨理t 大学t 学硕i j 学位论艾 互e 一c l k 匡亟圣 _ a n 重 一r s t f 二一二一i n p u t 一一。：d i n d o u t 咂匝耍 图3 一1 0 计数器模块的外部封装 f i g 3 10t h ep a c k a g eo f c o u n t e rm o d u l e 计数器模块的外部封装如图3 1 0 所示，它与比较器模块的封装引脚相 同。具体如何实现计数器模块的内部逻辑结构，是一个值得考究的问题，也是 本设计当中的一个难点。很多研究人员在这个地方的设计都有所不同。本文的 想法是，该模块的设计可以在比较器模块的基础上进行计数操作，这样只要把 设计好的比较器模块拿来利用就可以了，既降低了设计复杂度，还提高了模块 的规整化。本文设计的计数器模块包括两个部分，一个是比较器的部分，另一 部分是加l 计数器单元。 理论上来说，上文提到的两种形式的比较器模块都可以拿来进行计数器模 块的设计。但是，具体用哪种方法还是因人而异的。本论文设计的计数器模 块，如果采用方式1 的比较器模块，结果将无法实现匹配。比如，要匹配的规 则是a 4 b 。当输入信号为x a a a a b x ( x 作为任意字符) 时，理论上应该有匹配。 但是实际中，硬件只是匹配了a a a a ，却无法匹配b 。原因就出在这种比较器的 输出d o u t 与输入d i n 是同步的，所以d o u t 作为下一个模块的使能信号时，还 要再延迟一个周期。如图3 1 1 所示，从第二个周期丌始，因为比较器模块成 功匹配上了字符a ，所以计数器在下一个时钟上升沿到来后( 第三个周期罩) ， 计数c n t 为1 ，一直计数到4 ，计数：1 嚣输出信号d o u t e n 置l ，表示已匹配上了 4 个a 。这之日矿都没问题，问题就出在第六个周期罩，计数器的输出信号d o u t e n 作为下一个比较器模块的使能，要先做延迟再和单字节匹配逻辑的结果相 与，所以该信号没有在第六个周期罩与有效的b 信号做与运算，导致匹配失 败。 哈尔滨理丁人学下学硕i j 学位论文 批1nnnn 阿n d l n ( | | ( e c e n f 1 丁l 0 一 三。爿墓蕞裹甚 c n t ( 二 互) 0 3 ) | | d o u t - e n bii 广 _ 卜卜一卜 i d o u r 幽3 - 1i 方式1 匹配4 a 4 b ”的i ：作时序 f i g 3 11t h et i m i n gd i a g r a mo f m a t c h i n g ”a 4 b ”b a s e do np l a n1 而采用方式2 的比较器模块，虽然输出d o u t 与输入d i n 差了一个周期，但 是d o u t 作为下一个模块的使能端，是先进行与运算的，就不会出现上述的结 果，计数模块的输出将使能本周期内的匹配逻辑，不会再错过本周期内的输入 字符。基于方式2 的比较器模块实现计数功能的逻辑结构如图3 1 2 。 图3 - 1 2 计数器模块的逻辑结构 f i g 3 - 12s t r u c t u r eo fc o u n t e rm o d u l e 首先由前一模块的输出e n 使能该模块，在成功匹配的情况下，与门的输 出d 信号置1 ，该信号作为计数器单元的使能端，即只有d 信号有效，且时钟 上升沿到来时，计数器中的值才会加1 ，否则清0 。同时d 信号经过一个触发 器延迟了一个时钟周期，输出的q 信号再次作为本计数器模块的使能端，控制 其反复进行匹配。当且仅当计数器中的计数值c n t 符合限定次数时，计数器的 输出d o u t 彳。置l ，表示本模块的有效匹配。 哈尔演理t 人学t 学硕 ：学位论文 计数器模块的仿真结果如图3 1 3 所示，正则表达式为c a 4 b ，输入信号为 c a a a a b f 。 t e s t f d c f t e s t a n 秘肛s t d i n 谚t e s t u 瞳c 童i t e s t l u u t l n i t e s t l t r a t l o f t e s t u u t l c l l t e s t u u t l i i b t e 5 t f u u t a u t 3 t e s t c l o u t 瞄 黼 图3 1 3 计数器模块的仿真结果 f i g 3 - 13s i m u l a t i o nr e s u l t so fc o u n t e rm o d u l e 3 3 3 问号元字符模块 问号元字符表示对它之前的字符匹配0 次或是1 次。根据i j 面给出的改进后 的问号元字符n f a 状态转换图，空转移对应的是一条连线，也就是说前一 状态输出无需经过比较器直接连在下一状态的使能即可。下面给出问号元字符 对应的f p g a 逻辑如图3 1 4 所示。 图3 1 4 问号元字符的封装 f i g 3 - 14t h ep a c k a g eo fq u e s t i o nm a r km o d u l e 使能信号e n 通过或门直接作用到下一个模块的使能端上，也就是说，无论 匹不匹配a ，都不影响下一个模块的匹配，即实现了对字符的0 次匹配。而1 次 匹配是经过比较器单元具体过程如自订面所述。 哈尔滨理下人学t 学硕i j 学位论文 3 3 4 加号元字符模块 加号元字符是对它之前的字符匹配1 次或是多次，与构造问号的f p g a 映 射电路相似，根据图3 3 ( 4 ) 所示，f 状态无条件转移到s o 状态，形成一个不确 定次数的反复循环匹配过程，仍然需要用或门来实现空转移。加号元字符对 应的f p g a 映射逻辑如图3 1 5 所示。 图3 15 加号元字符的封装 f i g 3 - 15t h ep a c k a g eo f p l u ss i g nm o d u l e 比较器的输出信号d o u t 通过或门连在自身的使能端上，这样只要d o u r 信 号有效，即本周期内有匹配，那么下一周期内比较器模块仍可继续比较。 以q q 协议“ 7 ? x 0 2 + x 0 3 5 为例，验证加号和问号元字符逻辑的f 确 性。依照正则表达式里从左向右字符依次出现的顺序，将触发器、问号逻辑、 加号逻辑和比较器模块级联，组合成该条规则的逻辑电路。对此进行时序仿 真，如图3 1 6 所示。 m e s s a g e s t e s t _ q q l c l k 谚l t e s t _ q q l r s t i t e s t _ q q f e n f 彩，t e s t _ q q f d i n y t e s t _ q q t u u t t a z l w l t e s tq q t u u t a z w 2 7 t e s t _ q q t u u t a 2 1 w 3 t t e s t _ q q f u u t a 2 w 4 i t e s t _ q q l u u t l a 2 1 w 5 t e s t _ q q f m a l ：c ht 属灞镭 n o w 图3 1 6 问号和加号元字符模块的仿真结果 f i g 3 16s i m u l a t i o nr e s u l t so fp l u ss i g nm o d u l ea n dq u e s t i o nm a r km o d u l e 这罩输入信号为x 0 2 k x l1 ) ( 1 3 x 1 6 x 2 0 ) ( 1 2 x 0 2 x 4 8 x 0 3 ) 【0 0 x o o x 0 0 ，结果 哈尔滨理t 人学t 学顾f ! 学位论文 表明q q 协议可被识别。 需要说明的是， 元字符是通过给出的使能信号来实现的。当输入字符串 的第一个字符出现时，本周期内使能信号为l ，其他为0 。如果没有a 元字符， 使能信号一直为1 。$ 元字符表示字符串的结束，在硬件实现中必须许以一个特 征值才能识别，而在a s c i i 中0 0 表示空字符，故本文是用一个匹配x 0 0 的比较 器模块来实现$ 元字符。 3 3 5 星号元字符模块 星号元字符表示对它之前的字符匹配o 次或是多次，其实质就是问号和加 号的集合。从图3 3 ( 6 ) 上也可以看出，问号和加号n f a 状态图合并后可得星号 n f a 状态图。依此原理当把问号和加号元字符的电路合并在一起的时候，发现 两个或门的输入信号完全相同，故去掉一个或门。星号元字符的映射逻辑如图 3 1 7 所示。 图3 - 1 7 星号兀字符的封装 f i g 3 - 17t h ep a c k a g eo fa s t e r i s km o d u l e 利用该模块对邱协议“ 2 2 0 书邱 的进行时序验证，如图3 1 8 所示。 输入信号为“2 2 0 a b c d e f t p ”；w l 为第一个对“2 ”的比较器输出；w 2 为第二个对“2 的比较器输出；w 3 为对“0 ”的比较器输出；w 4 为星号元字符的输出：w 5 为对 “r 的比较器输出；w 6 为对“t ”的比较器输出；m a t c h l 为对“p ”的比较器输出，即 整条规则的总输出。验证结果表h 韭j f t p 协议可被识别。 哈尔滨理工人学工学硕上学位论文 t t o s t _ o o j d k 舳瞌q q r 奠 _ i - t o 盘翔7 e 心 土l i - t 鳅q q 翻 j t e s l ：_ o ：l l u u l a 3 w ! 转e 呔j 列强盘| 酬啦 l e s t _ q q j u u l a 3 t w 3 夺肛啾q q f ，a 3 岍 t e s t _ c k i j u 谴a 3 w 5 t e 奠_ 口可u 州a 3 幅 3 3 6 编码器模块 0 n 门n 门门门r r 广 门nnr l 一j o门 0 1 1 l 吣 幻啪1 1 0 0 1 01 0 0 d 尬l 1 勘，m t d l 1 1 1 嗍 鲫 j i 殳oil 锄ll 负li s t on 锄n 殳o 厂 il ii l l li i i i il i iti - t - i li iii - i 7 4 0 0 0 0 * 嚣 1 0 0 0 0 0 跖加骖 图3 1 8 星号元字符模块的仿真结果 f i g 3 - 18s i m u l a t i o nr e s u l t so f a s t e r i s km o d u l e 表3 13 - 2 编码器 t a b l e3 13 2e n c o d e r m a t c h 3 m a t c h 2m a r c h ld o u t oo0o o0 1 1 olo2 1o 0 3 在本设计中编码器是对匹配的规则进行编码，它的输入端是各个规则模块 的输出，假如整个系统只有3 条规则，这3 条规则的输出信号分别为 m a t c h l ，m a t c h 2 ，m a t c h 3 ，那么只会出现4 种状态，如表3 1 所示。d o u t 为0 时表 示输入没有匹配上任何规则；d o u t 为l 表示匹配上了规则l ；d o u t 为2 表示匹 配上了规则2 ；d o u t 为3 表示匹配上了规则3 。如果规则不限于3 条，那么以 此类推，d o u r 为几就是匹配上了第几条规则。编码器模块的仿真结果如图3 1 9 ，这里我们对如下三条规则实现了编码设计，从d o u t 的输出看，匹配了邱 协议。 m a t c h l t e l n e t ： ) ( 珥) ( f b 一x f e ) 【研、x f b - 、x f e 】x 趣k f b - x f e 】 m a t c h 2 q q ： 7 ? ) ( 0 2 + l x 0 3 5 m a t c h 3 f t p ： 2 2 0 木f t p 哈尔滨理t 人学t 学硕 ：学位论文 h e 5 鞫口酷 t e s t _ q q l c l k t e s t _ q q # s t t e s tq o j e n f 型t e s t _ q q l d i n 冷t 器t - q q f u u t f m a c c h l t e s t _ 口q t u u t m a t c h 2 f t e s t _ q c l u u t m a t c h 3 国t e s t _ q q u u t a ! 0 0 1 w 盘t 笛, t _ q q l d o u t 攫沥镭，o w 几门r 几几几厂 厂 厂 厂 厂 n 几i 厂 图3 1 9 编码器模块的仿真结果 f i g 3 19s i m u l a t i o nr e s u l t so f e n c o d e r m o d u l e 编码器的设计，除了能够更直观的看出结果是否有匹配外，且在规则数目 很大的时候能够大幅减少整个系统的输出引脚数目。试想，当有1 0 0 0 条协议 要进行识别匹配，如果不加编码器，那么硬件的输出就要有1 0 0 0 个引脚，加 了编码器模块后输出引脚只需1 0 个。 3 4 本章小结 本章主要介绍了正则表达式匹配引擎的设计流程，提出了设计的基本方 案，并对于如何构造n f a 以及实现f p g a 映射电路的方法及过程给出了详细 的介绍。将正则表达式转换成易于硬件实现的n f a 后，通过一位热码编码的 方式设计了基于n f a 的各类元字符的映射电路，诸如比较器模块、计数器模 块等。这部分的设计为构造匹配引擎系统的关键所在，所以本章着重介绍了各 模块的硬件结构并给出了时序仿真结果。 哈尔滨理t 人学t 学硕i j 学位论文 第4 章系统优化与总体性能验证 4 1 系统的优化设计 本文设计的正则表达式匹配引擎可应用在任意的基于协议分析的网络安全 类系统中。一般来说，为了满足分析上的需求此类系统都要包含大量的协议规 则，例如入侵检测系统s n o r t 规则数量达1 0 0 0 0 之多。而如果要在f p g a 上实 现这么多的规则，就要尽可能的缩减匹配每个字符时所需要占用的逻辑，如若 不然在造成大量的逻辑资源浪费的同时，还不能满足对规则数量上的要求。因 此，为了保障系统能够有效容载大量规则，并保持高的吞吐率，本文改进了系 统结构设计，针对规则的两种重复形式，分别给出其解决办法，大幅度的简化 了匹配电路，实现了系统的硬件优化。 改进的系统结构如图4 1 所示。 图4 1 优化后系统结构 f i g 4 - 1s t r u c t u r eo f t h eo p t i m i z e ds y s t e m 在这罩，本文针对单字符的重复逻辑而设计提出了一个8 - n 共享比较器的 设计。数据首先经过8 - n 共享比较器进行预处理，然后由各个改进的比较模块 进行后续的匹配工作，最后送入编码器输出。另外，对于共享子缀的情况，为 了进一步减少系统资源利用率，本文也设计了一个基于多端触发器的识别单元 结构。 哈尔滨理t 人学t 学硕 j 学f 证论文 4 1 1 对单字符的匹配优化 在设计的过程中，发现大量的逻辑资源都是对同一字符进行比较工作的。 例如为了实现! i v e 3 6 5 这条规则m e m b e m a m e * s e s s i o n * p l a y e r ，将各个比较器模 块和星号模块级联起来，则总共需要2 3 个比较器模块，其中5 个还都是