学位论文 > 优秀研究生学位论文题录展示
基于K步长的多模式匹配算法及硬件实现研究
作 者: 苏晓博
导 师: 李训根
学 校: 杭州电子科技大学
专 业: 电路与系统
关键词: 模式匹配 布鲁姆过滤器 确定有限自动机 FPGA
分类号: TP393.08
类 型: 硕士论文
年 份: 2012年
下 载: 24次
引 用: 0次
阅 读: 论文下载
内容摘要
随着全球信息化水平的不断提高,网络与信息安全的重要性日趋增强。当前网络与信息安全产业已成为对各国的国家安全、政治稳定、经济发展、社会生活、健康文化等方方面面具有生存性和保障性支撑作用的关键产业,网络与信息安全产业在整个产业布局乃至国家战略格局中具有举足轻重的地位和作用。我国自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命中时,流水线就要停止,然后逐个的匹配进入到流水线中的数据,匹配完之后,再重新开启流水线,这样使处理的效率大大提高。
|
全文目录
摘要 5-6 ABSTRACT 6-10 第1章 绪论 10-17 1.1 研究背景和意义 10-12 1.1.1 研究背景 10-11 1.1.2 研究意义 11-12 1.2 研究现状及发展趋势 12-14 1.3 主要研究内容 14-15 1.4 论文结构安排 15-17 第2章 模式匹配算法及硬件实现 17-33 2.1 IDS 简介 17 2.2 入侵检测系统 17-19 2.2.1 IDS 基本工作原理 17-18 2.2.2 IDS 在信息安全中的地位 18-19 2.3 IDS 的标准 19-22 2.3.1 公共入侵检测框架 19-20 2.3.2 入侵检测信息交换格式 20-21 2.3.3 国内入侵检测系统标准 21-22 2.4 模式匹配算法 22-30 2.4.1 Knuth-Morris-Pratt(KMP)算法 22 2.4.2 基本 Aho-Corasick 算法 22-24 2.4.3 改进的 AC 算法 24-26 2.4.4 Boyer-Moore(BM)算法 26-27 2.4.5 Wu-Manber(WM)算法 27-30 2.5 多模式匹配算法的硬件实现 30-32 2.5.1 结合 ROM 和存储器的 FPGA 实现 30-31 2.5.2 基于 TCAM 31-32 2.6 本章小结 32-33 第3章 布鲁姆过滤器 33-39 3.1 布鲁姆过滤器基本原理 33-34 3.2 错误率估计 34-35 3.3 最优的哈希函数个数 35 3.4 位数组的大小 35-37 3.5 改进的 Bloom Filter 算法 37-38 3.5.1 算法思想 37 3.5.2 算法分析 37-38 3.6 小结 38-39 第4章 基于 K 步长的多模式匹配算法的 FPGA 实现 39-52 4.1 K 步长多模式匹配算法 39-41 4.2 系统结构 41-48 4.2.1 失效状态的处理 43 4.2.2 数据拆分模块的设计 43-44 4.2.3 匹配引擎的设计 44-48 4.3 硬件原型验证及性能分析 48-50 4.4 小结 50-52 第5章 总结与展望 52-54 5.1 论文总结 52-53 5.2 展望 53-54 致谢 54-55 参考文献 55-60 附录 60-61 详细摘要 61-69
|
相似论文
- 基于FPGA的电磁超声检测系统的研究,TH878.2
- 基于FPGA的五相PMSM驱动控制系统的研究,TM341
- LXI任意波形发生器研制,TM935
- 基于FPGA的射频功放数字预失真器设计,TN722.75
- 突发OFDM系统同步与信道估计算法及FPGA实现,TN919.3
- 直扩系统抗多径性能分析及补偿方法研究,TN914.42
- 电视制导系统中视频图像压缩优化设计及实现研究,TN919.81
- 基于FPGA的多用户扩频码捕获研究及硬件仿真,TN914.42
- 基于FPGA的数字图像处理基本算法研究与实现,TP391.41
- 基于FPGA的高速图像预处理技术的研究,TP391.41
- 基于FPGA的高速数字图像采集与接口设计,TP274.2
- 基于FPGA的电感传感器数据采集系统的研制,TP274.2
- 基于Nios的串行总线分析仪研制,TP274
- 基于FPGA-RocketIO_X的PMC高速数据传输板开发,TP274.2
- PXI高性能数字I/O模块研制,TP274
- LXI计数器研制,TP274
- 基于FPGA的高速实时数据采集系统,TP274.2
- 基于Nios Ⅱ的GPS信息接收系统设计,TN967.1
- 温压炸药爆炸温度场存储测试技术研究,TQ560.7
- 掺铒光纤放大器中泵浦激光器驱动源的研究应用,TN248
- FPGA系统远程安全升级的设计与实现,TP309
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络安全
© 2012 www.xueweilunwen.com
|