基于FPGA的可配置正则表达式匹配引擎的设计

摘要

正则表达式具有较强的灵活性、逻辑性及功能性，是一种字符串匹配模式，可以迅速地用较简单的方式来表述复杂的字符串。正则表达式多用于入侵检测系统及文本处理等。一般地，都是采用软件方式来实现正则表达式的匹配。然而，随着网络带宽的大幅度提高、网络数据流量的剧增以及云计算技术等的快速发展，软件实现的方式成了正则表达式高速匹配的瓶颈。而硬件由于其并行化工作的特点，可以用于快速处理模式的匹配，因此成为研究人员设计、构造匹配引擎的新载体。
　　FPGA由于其特殊结构及具有可重复配置等特性，现多用于高速多数据处理的场合。本文介绍了采用FPGA来实现正则表达式匹配的方法。论文首先对正则表达式构造自动机的几种经典算法进行了简述。在分析对比各自优缺点之后提出了一种新的NFA构造算法，该算法的空间复杂度理论上为O（n），时间复杂度为O（n2）。且构造生成的NFA的规模数相对很小，其中状态数比正则表达式中含有的普通字符数n要少，转换数约等于n。有且只有一个终止状态。其次对在FPGA中实现匹配的过程进行了研究，提出了构建匹配子模块的设计，生成匹配子模块库。该设计可以大大节约后续设计过程中的时间成本，加快入侵检测系统中的特征模式的更新速度。对于一些特殊结构的正则表达式，论文给出了设计中的一些优化方案以节约实现中的硬件资源。最后利用论文中构建的子模块库，分别采用新算法S-NFA和经典的Thompson算法对正则表达式进行处理，生成对应的NFA。论文的第四章给出了将NFA进行逻辑化处理的方法，以适用于硬件化的处理。搭建Testbench测试平台，对各实例进行测试并给出了仿真结果，从得到的NFA规模以及实际匹配延时两个方面对新的算法进行了评价。
　　综上所述，本文在对正则表达式匹配技术的研究基础之上，提出了一种新的NFA构造算法及NFA的逻辑化处理方法，构建了匹配子模块库，通过仿真实验对该子模块库进行了验证，并比较了S-NFA算法和Thompson算法的性能。结果表明S-NFA算法在构造过程、生成的NFA的规模以及应用后的实际延时等方面要优于传统的Thompson算法，且适合于用FPGA来实现。

目录

声明

摘要

第1章 绪论

1．1 课题背景及研究意义

1．2 国内外研究现状

1．3 入侵检测系统概述

1．4 论文主要研究内容

第2章 基于正则表达式的NFA的构造算法及应用

2．1 概述

2．1．1 正则表达式概述

2．1．2 有限自动机概述

2．2 NFA的一般构造算法

2．2．1 Thompson构造法

2．2．2 Glushkov构造法

2．2．3 Follow宦l动机构造法

2．3 NFA的简单构造法

2．3．1 预处理

2．3．2 NFA的构造法

2．4 IDS规则的NFA实现

2．4．1 IDS规则概述

2．4．2 NFA的算法实现规模分析

2．5 本章小结

第3章 基于FPGA的正则表达式的通用匹配子模块设计

3．1 概述

3．2 FPGA概述

3．3 匹配子模块分类与设计

3．3．1 比较器模块

3．3．2 重复匹配模块

3．3．3 范围约束匹配模块

3．3．4 任意字符匹配模块

3．3．5 其它字符匹配模块

3．4 应用实例匹配设计及验证

3．5 资源优化设计方案

3．5．1 子缀共享

3．5．2 多字符共享

3．6 本章小结

第4章 基于FPGA的NFA实现及仿真验证

4．1 概述

4．2 基于S-NFA算法的NFA构造

4．2．1 NFA的S-NFA算法构造

4．2．2 NFA的硬件逻辑化

4．3 基于Thompson算法的NFA构造

4．3．1 NFA的Thompson算法构造

4．3．2 NFA的硬件逻辑化

4．4 Testbench仿真验证

4．4．1 Testbench构建

4．4．2 仿真结果分析

4．5 实验验证

4．6 本章小结

第5章 总结与展望

5．1 总结

5．1．1 本文完成主要工作

5．1．2 本文主要创新点

5．2 展望

参考文献

致谢

攻读硕士期间发表的论文