网络内容分析中基于硬件的字符串匹配算法的研究

论文摘要

Internet代表的信息革命极大改变了人们的生活、生产方式,网络无处不在。但是在巨大的信息浪潮中,内容安全问题也同样无处不在,各种令人不安的信息如湍急暗流隐藏在互联网大潮下。一方面是人们生活越来越多地依靠网络,许多政府业务越来越多地使用网络,而另一方面却是Internet上信息的鱼龙混杂,黑客、病毒、网络攻击等日益盛行。保护网络空间的洁净,保护网络空间中的“国土”,已成为未来国家发展的重要问题,也是摆在人们面前的一个巨大挑战。为了建立起高效、绿色、安全的互联网世界,网络内容分析技术已经越来越受到人们的关注。论文主要针互联网中内容分析的基本问题,从算法和系统的角度研究基于硬件实现的字符串匹配技术在网络内容分析中的应用。论文有以下几点创新之处:●提出了硬件实现的基于ABNF范式的字符串匹配和协议解码方法在网络内容分析中,除了要对特定的模式串匹配,还需要对数据报文中的真实含义进行解码检查。而在传统字符串匹配中,网络数据包被简单的看成无序字符串,其内部结构和报文中的真实含义不被匹配算法本身关注。但是由于网络通信是建立在一定协议之上的,通信协议是一种高度规格化、具有明确含义和取值的数据流,为此,论文提出了一种硬件实现的基于ABNF范式的字符串匹配和协议解码方法,实验表明了此方法在性能上能比软件实现的匹配和协议解码有60倍的提高。●提出了基于加权扩展Bloom filter的字符串匹配算法为了在对模式串进行匹配的同时得到与数据报文中的字符串相匹配的模式串的值。论文对硬件实现的Bloom filter进行扩展,使其支持域值获取;同时还对此扩展Bloom filter进行加权处理以消除扩展带来的新的性能下降,并通过理论分析得出加权扩展Bloom filter(weighted extended Bloom filter:WEBF)的最优配置参数。为了提高匹配的性能,论文专门设计了基于ASIC的WEBF引擎,通过仿真和实验表明了基于此算法的芯片匹配速度大大超过了现有的各种软件和硬件的匹配算法。●设计了基于FPGA协处理器的网络内容分析处理平台论文设计和实现了一个基于嵌入式CPU和FPGA协处理器的网络内容分析处理平台用以验证文中提出的字符串匹配算法的功能和性能指标。此平台验证了文中提出的硬件实现的串匹配算法和协议解码器的模型是可行的,其匹配速度是现有的各种匹配算法无法比拟的。同时此平台上运行的GNU/Linux操作系统具有强大的特性和自由软件的优势,可以迅速的实现复杂的网络业务。此平台可以被设计为硬件支持数据包分类、协议解码、字符串匹配等最基本的网络报文处理,同时还包含高性能通用处理器内核的通用平台,它能为许多网络应用提供灵活可变、性能优异的处理能力,方便进一步的研究。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 互联网内容安全现状
• 1.2 网络内容分析系统研究现状
• 1.3 网络内容分析中的问题
• 1.3.1 字符串匹配算法的速度
• 1.3.2 字符串匹配算法的吞吐量
• 1.4 论文的目标与组织
• 1.4.1 论文的目标
• 1.4.2 论文的组织
• 第2章 字符串匹配算法概述
• 2.1 字符串匹配问题
• 2.2 字符串匹配算法概述
• 2.2.1 软件实现的字符串匹配算法
• 2.2.2 基于CAM的字符串匹配算法
• 2.2.3 基于协处理器的字符串匹配算法
• 2.2.4 基于非确定有限自动机的字符串匹配算法
• 2.2.5 基于Bloom filter的字符串匹配算法
• 2.3 小结
• 第3章 基于ABNF的字符串匹配和协议解码
• 3.1 概述
• 3.2 ABNF介绍
• 3.2.1 终结符
• 3.2.2 操作符
• 3.3 基于ABNF的字符串匹配结构
• 3.3.1 报文数据扇出模块
• 3.3.2 基于流水线的域值提取
• 3.3.3 基于ABNF的模式匹配模块
• 3.3.4 NFA构造算法
• 3.4 性能分析
• 3.4.1 流水线的性能提高
• 3.4.2 FPGA实现的基于ABNF的字符串匹配和解码算法的性能
• 3.5 小结
• 第4章 基于加权扩展BLOOM FILTER的字符串匹配算法
• 4.1 哈希查询算法原理
• 4.2 Bloom filter介绍
• 4.2.1 Bloom filter的数学描述
• 4.2.2 哈希与Bloom filter的比较
• 4.2.3 Bloom filter的应用
• 4.2.4 Bloom filter各种扩展算法应用
• 4.3 支持域值获取的扩展Bloom filter算法
• 4.4 加权扩展Bloom filter算法
• 4.5 基于ASIC的WEBF引擎
• 4.5.1 集成电路的结构化设计方法
• 4.5.2 WEBF引擎的结构设计
• 4.6 总结
• 第5章 基于FPGA协处理器的网络内容分析处理平台
• 5.1 内容分析处理平台概述
• 5.2 TMS320DM6446嵌入式处理器介绍
• 5.2.1 ARM926EJ-S处理器内核结构
• 5.2.2 C64x+DSP内核结构
• 5.3 EP3C120 FPGA器件介绍
• 5.4 FPGA协处理器设计
• 5.5 内容分析处理平台电路设计
• 5.6 内容分析处理平台软件设计
• 5.6.1 U-Boot
• 5.6.2 GNU/Linux操作系统
• 5.6.3 GNU/Linux的网络包处理过程
• util'>5.6.4 网络内容分析平台用户工具-pm_util
• 5.7 内容分析处理平台测试
• 5.7.1 基于WEBF引擎的FPGA协处理器性能测试
• 5.7.2 网络内容分析平台性能测试
• 5.8 内容分析处理平台总结
• 第6章 总结
• 6.1 论文的贡献
• 6.1.1 基于ABNF范式的字符串匹配和协议解码
• 6.1.2 基于加权扩展Bloom filter的字符串匹配算法
• 6.1.3 基于协处理器的网络内容分析处理平台
• 6.2 进一步研究的方向
• 6.2.1 非确定性字符串匹配技术
• 6.2.2 高性能网络处理芯片研究
• 参考文献
• 攻读博士学位期间的研究成果与科研项目
• 致谢