2024年3月30日发(作者：)

摘 要

正则表达式是一种字符串匹配模式，它能够用简洁的结构准确地描述多目标字符

串，并以此对多目标字符串进行匹配。传统的正则表达式匹配都是基于软件的，但是

随着网络流量的不断增长，基于软件的正则表达式匹配在通用处理器上已经很难完

成，需要用硬件完成一部分或全部的正则表达式匹配任务。因此，本文在分析正则表

达式结构和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 based.

But, with the rapid growth of network traffic, it has become impossible to do software

based regular expression matching. This makes it necessary to use hardware to do part or

all of the matching. Therefore, the thesis implements regular expression matching in

FPGAs.

The thesis discusses the feasibility of NFA based 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-based 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 with 1.3Gbps network traffic for 500 regular expressions.

Keyword: Regular Expression, FPGA, String Matching, Non-deterministic Finite

Automaton (NFA), Intrusion Detection System (IDS)

II