摘要
正则表达式是一种字符串匹配模式，它能够用简洁的结构准确地描述多目标字符串，并以此对多目标字符串进行匹配。传统的正则表达式匹配都是基于软件的，但是随着网络流量的不断增长，基于软件的正则表达式匹配在通用处理器上已经很难完成，需要用硬件完成一部分或全部的正则表达式匹配任务。因此，本文在分析正则表达式结构和FPGA特点的基础上，设计实现了基于FPGA的正则表达式匹配。
厨房下水管道本文结合正则表达式和有限状态机的研究，讨论了基于非确定有限状态机（NFA）实现正则表达式匹配的可行性，然后提出了一种分步设计流程，针对具体环境提出设计目标，并按照设计流程进行了详细设计。本文将正则表达式到FPGA逻辑的实现过程分解为三步，在一个入侵检测系统中实现了正则表达式匹配。针对实现时占用资源较多的情况，结合FPGA和正则表达式的特点提出了九种有效的优化设计方法，本文最后进行了系统级和模块级的仿真与验证，验证结果表明优化后的设计完全达到了设计目标规定的各项指标。
基于FPGA的正则表达式匹配的实现与应用，不仅能够有效地提高入侵检测系统的处理能力，而且能够通过FPGA的重新下载实现正则表达式库的升级。本文实现的系统能够处理1.3Gbps数据流量情况下，500条正则表达式的高速字符串匹配。
关键词：正则表达式, 现场可编程逻辑阵列, 字符串匹配, 非确定有限状态机, 入侵检测系统
I
Abstract
Regular expression is a pattern matching mechanism, which can describe the structure of multiple strings with simple structures. Normally, regular expression is software bad. But, with the rapid growth of network traffic, it has become impossible to do software bad regular expression matching. This makes it necessary to u hardware to do part or all of the matching. Therefore, the thesis implements regular expression matching in FPGAs.防火检查
走进大山The thesis discuss the feasibility of NFA bad regular expression implementation, and then, gives the design flow, design goals and the design details of regular expression. The implementation of regular expression in an IDS system is broken into 3 steps. It is found that a large part of FPGA logic is occupied by the regular expression engine. So, considering the characteristics of FPGA and regular expression, the thesis tried 9 different techniques to optimize the design. The simulation and verification is given in the last chapter which showed that the design can well achieve the goals.
FPGA-bad regular expression matching can improve the ability of IDS systems. It can also make it possible to update the regular expression library of IDS systems easily. The final system can deal wit
与冬天有关的成语
h 1.3Gbps network traffic for 500 regular expressions.
Keyword: Regular Expression, FPGA, String Matching, Non-deterministic Finite Automaton (NFA), Intrusion Detection System (IDS)
杉篙
II
缩略语表
ASIC - Application Specific Integrated Circuit专用集成电路
Block RAM - Random Access Memory随机存取内存带海的成语
CAD - Computer Aided Design 计算机辅助设计
CAM - Content Addressable Memory 内容可寻址存储器CLB - Configurable Logic Block 可配置逻辑模块
DCM - Digital Circuit Module 数字电路模块
DSP - Digital Signal Processing数字信号处理
DFA - Deterministic Finite Automaton 确定有限状态自动机DUT - Design Under Test被测模块淘宝品牌女装
EDA - Electronic Design Automation 电子设计自动化
FF - Flip Flop 触发器
FIFO - First Input First Output 先入先出队列
FPGA - Field Programmable Gate Array 现场可编程门阵列IDS - Intrusion Detection Systems 入侵检测系统
IP - Intellectual Property 知识产权核
ISP - In-System Programming 现场可编程技术
LUT – Look Up Table 查找表
MAC - Media Access Control 介质访问控制子层NFA - Non-deterministic Finite Automaton 非确定有限状态自动机OHE - One Hot Encoding 一位热码编码
PCRE - Perl Compatible Regular Expression Perl兼容正则表达式PLD - Programmable Logic Device
可编程逻辑器件
RAM - Random Access Memory 随机存取存储器
RTL - Register Trasfer Level 寄存器传输级
SOC - System on Chip 片上系统
TCAM - Ternary Content Access Memories 三态内容可寻址存储器TDP - Targeted Design Platform 目标设计平台
V
独创性声明
本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知，除文中已标明引用的内容外，本论文不包含任何其他人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名：
告别黑眼圈日期：年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
保密□，在______年解密后适用本授权书。
本论文属于
不保密□√。
（请在以上方框内打“√”）
学位论文作者签名：指导教师签名：
日期：年月日日期：年月日
1 绪论
1.1 课题背景
字符串匹配（即模式匹配）有单模式匹配和多模式匹配两种类型，正则表达式（Regular Expressions通常缩写为“Reg Exp或者RE”［1］）是一种多模式匹配。它能够对多目标字符串进行模式匹配，可以用来进行关键字搜索、文本替换等。现在正则表达式匹配被广泛应用在包括医学、数据挖掘、文本处理、网络安全、电信［2］等领域，在医学中的应用包括DNA序列匹配，蛋白质匹配，基因序列匹配等等［3］，在文本处理方面的应用包括文本搜索、词法分析等等，在网络安全方面的应用包括入侵检测、防火墙、病毒漏洞扫描等等，基于内容的路由器也用到了正则表达式匹配技术。
随着计算机网络和计算机存储系统的持续发展，计算机内部模块之间以及各计算机之间交换的数据量也持续增加［4］。与此同时，处于数据安全性、服务质量、协议识别等方面的考虑，需要对这些不断增长的数据流量进行模式匹配［5, 6］。由于计算机技术的迅速发展，通用处理器的处理能力大幅提升，基于通用处理器的软件处理方式已经能够处理绝大部分模式匹配，而且软件匹配的方式开发成本低周期短，因此，当前很多模式匹配都是基于软件的［7, 8］。但是，对于高速数据处理，限于处理器性能，在普通的处理器上软件方法最大只能处理100Mbps左右的流量。这时，就需要用硬件完成一部分或全部模式匹配任务，但是传统的基于定制芯片的方法又不能灵活进行配置与修改，基于现场
可编程门阵列（Field Programmable Gate Array，FPGA）的正则表达式匹配的实现方式正是在这样的需求下提出的。
国外现阶段的研究多数集中于正则表达式理论、构造算法，开发工具等方面的基础及应用研究。例如正则表达式的基本语法、构造生成正则表达式的方法、应用正则表达式自动从报文中提取数据、正则表达式在各种语言和工具中的使用方法。国内关于正则表达式的研究还主要集中在医学，气象，网络监控，电信等领域［9］。虽然正则表达式理论已经有良好的发展，但使用正则表达式做高性能模式匹配仍然比较困难，是一个正在进行研究的领域［10］。
现阶段主要有两种方法实现正则表达式匹配：基于确定有限状态机（Deterministic Finite Automata，DFA）和基于非确定有限状态机（Nondeterministic Finite Automata，NFA）［11］。由于两种实现方法的理论基础有很大的不同，因此实现起来，两种方法在实现的难易度、实现性能、匹配速度等方面都有很大的差异性。一般而言，基于DFA 的正则表达式匹配有较高的匹配速度，但占用的内存空间相对较大，［12, 13］，而基于NFA的正则表达式匹配设计上更为灵活，但匹配速度较慢。目前国际和国内基于硬件
1
