基于K步长的多模式匹配算法及硬件实现研究

论文摘要

随着全球信息化水平的不断提高，网络与信息安全的重要性日趋增强。当前网络与信息安全产业已成为对各国的国家安全、政治稳定、经济发展、社会生活、健康文化等方方面面具有生存性和保障性支撑作用的关键产业，网络与信息安全产业在整个产业布局乃至国家战略格局中具有举足轻重的地位和作用。我国自2003年以来也在网络与信息安全方面有了较大的进展，但是总体相对落后。网络与信息安全方面的研究是当前信息行业的研究重点之一。本文首先介绍了Aho-Corasick、Aho-Corasick-Boyer-Moore和Wu-Manber等经典多模式匹配算法。阐述了模式匹配技术的发展现状和未来的发展趋势。随着网络带宽的不断升级和应用的复杂化，基于软件的多模式匹配算法已经远远不能满足应用的需要，就是一些基于硬件实现的精确模式串匹配算法在复杂模式情况下也不能满足数十Gbps流量的冲击，存在严重的可扩展性问题。所以模式匹配算法的硬件化是必然的发展趋势。本文随后介绍了布鲁姆过滤器的原理和应用。分析了影响布鲁姆过滤器性能的因素，在此基础上实现布鲁姆过滤器的FPGA实现，通过分析hash函数的硬件运算时间的影响因素来选择合适的hash函数及函数个数和映射空间的大小，提高了布鲁姆过滤器的硬件性能。通过对输入集合信息的分解，经过多次哈希，优化和改进了布鲁姆过滤器的性能，跟传统的布鲁姆过滤器相比，改进后的布鲁姆过滤器在哈希函数的个数、映射空间的大小和运算时间等方面有不错的改善。为克服经典的Aho-Corasick算法需不断访问RAM的匹配速度瓶颈，本文最后设计了一个基于K步长多模式匹配算法的FPGA电路。匹配电路包括输入数据拆分模块、失效状态处理模块、匹配引擎模块、分析和仲裁和存储器访问接口等模块。对于某个输入，进入Bloom Filter之后还要等待，经过Hash运算、查找数组、判断，要4个时钟周期之后才能得到Bloom Filter的结果，而在实际的应用中，只有不到3%的数据有可能发生匹配，所以设计了一种“Bloom Filter+匹配流水线”的处理方式，数据依次进入匹配流水线，不必逐个等待Bloom Filter的结果，对于那些安全的数据，经过Bloom Filter和匹配流水线的处理可以快速的过滤。当Bloom Filter命中时，流水线就要停止，然后逐个的匹配进入到流水线中的数据，匹配完之后，再重新开启流水线，这样使处理的效率大大提高。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景和意义
• 1.1.1 研究背景
• 1.1.2 研究意义
• 1.2 研究现状及发展趋势
• 1.3 主要研究内容
• 1.4 论文结构安排
• 第2章 模式匹配算法及硬件实现
• 2.1 IDS 简介
• 2.2 入侵检测系统
• 2.2.1 IDS 基本工作原理
• 2.2.2 IDS 在信息安全中的地位
• 2.3 IDS 的标准
• 2.3.1 公共入侵检测框架
• 2.3.2 入侵检测信息交换格式
• 2.3.3 国内入侵检测系统标准
• 2.4 模式匹配算法
• 2.4.1 Knuth-Morris-Pratt（KMP）算法
• 2.4.2 基本 Aho-Corasick 算法
• 2.4.3 改进的 AC 算法
• 2.4.4 Boyer-Moore（BM）算法
• 2.4.5 Wu-Manber（WM）算法
• 2.5 多模式匹配算法的硬件实现
• 2.5.1 结合 ROM 和存储器的 FPGA 实现
• 2.5.2 基于 TCAM
• 2.6 本章小结
• 第3章 布鲁姆过滤器
• 3.1 布鲁姆过滤器基本原理
• 3.2 错误率估计
• 3.3 最优的哈希函数个数
• 3.4 位数组的大小
• 3.5 改进的 Bloom Filter 算法
• 3.5.1 算法思想
• 3.5.2 算法分析
• 3.6 小结
• 第4章 基于 K 步长的多模式匹配算法的 FPGA 实现
• 4.1 K 步长多模式匹配算法
• 4.2 系统结构
• 4.2.1 失效状态的处理
• 4.2.2 数据拆分模块的设计
• 4.2.3 匹配引擎的设计
• 4.3 硬件原型验证及性能分析
• 4.4 小结
• 第5章 总结与展望
• 5.1 论文总结
• 5.2 展望
• 致谢
• 参考文献
• 附录
• 详细摘要