基于入侵检测系统的正则表达式匹配引擎设计

摘要

模式匹配是入侵检测系统中的一项关键技术，其算法性能的好坏直接影响到入侵检测系统的性能。早期的模式匹配技术以精确匹配算法为主，如KMP，AC，BM等。随着互联网信息的迅速增长，攻击模式的多样化，这种基于字符串特征的模式规则定义越来越不能满足日益增长的规则库需求，而正则表达式因其丰富和灵活的表达能力在模式匹配中得到了广泛应用。但是，传统的基于软件的正则表达式匹配引擎已经无法满足高速网络的要求，基于硬件的正则表达匹配引擎逐渐成为了国内外学者研究的重点。
　　本文介绍了网络安全防护体系中的入侵检测技术及正则表达匹配算法在入侵检测系统中的应用，详细分析了正则表达式匹配的两种方法DFA和NFA及其硬件实现方法。在此基础上，本文选择了基于DFA的存储器查询的正则表达式匹配架构作为本文的研究内容。针对其存在的不足，从扩展系统一次处理的数据位宽出发，设计了一种基于起始状态猜测的多路正则表达式匹配算法。该算法根据DFA状态转移的流程及RAM的读写速度，把输入字符流缓存成相同长度的多路，猜测除第一路之外的起始状态，先使各路并行匹配，并行匹配完后如果发现起始状态猜测错误，再通过验证匹配纠正其错误。该算法能够在不增加DFA个数的基础上，提高正则表达式的匹配速度。
　　针对正则表达式匹配因FPGA片上存储资源不足需要频繁访问外部存储器的问题，本文研究了Bloom Filter在FPGA上的实现方法；设计一种把D2FA和“失效状态”相结合的转移边优化方法。然后，在基于猜测的多路正则表达式匹配算法的基础上，采用了转移边优化后的状态机，结合Bloom Filter，设计了一个快速高效的正则表达式匹配引擎。该引擎根据状态深度和其转移边的数目，对状态转移信息进行分类存储和过滤，把匹配过程中经常需要查询和转移边较多的状态信息存放在FPGA内部RAM，把转移边较少的状态信息经过Bloom Filter过滤，从而优化了状态信息存储所需的空间，减少了正则表达式匹配过程中访问外部存储器的次数，提高了匹配引擎的整体性能。
　　本文在 FPGA上实现了多路正则表达式匹配算法及其匹配引擎，搭建了测试平台，设计了详细的测试方案，对匹配算法及其匹配引擎的性能进行了详细的分析和测试。实验结果表明，本文设计的匹配引擎能够提高匹配速度。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景及意义

1.2 研究现状及发展趋势

1.3 主要研究内容及安排

第2章 入侵检测系统与正则表达式匹配

2.1 入侵检测技术

2.2 正则表达式匹配

2.3 基于FPGA的正则表达式匹配

2.4 本章小结

第3章 基于猜测的多路正则表达式匹配算法设计

3.1 多路并行匹配算法设计

3.2 多路并行匹配算法在FPGA上的设计及实现

3.3 测试与分析

第4章 基于FPGA的正则表达式匹配引擎设计及实现

4.1 设计分析

4.2 基于FPGA的Bloom Filter研究

4.3状态转移边优化方法设计

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

4.5 系统测试与分析

4.6本章小结

第5章 总结与展望

5.1 论文总结

5.2 课题展望

致谢

参考文献

附 录

作者在读期间发表的学术论文及参加的科研项目