基于网络处理器的多模式串匹配算法研究

摘要

随着计算机网络的迅速普及以及人们对网络越来越强的的依赖性，网络安全问题日益突出并引起广泛关注。入侵检测是网络安全系统的一个重要组成部分，其目的是通过监视和分析网络流量来发现可疑的攻击行为，进而采取有效的防护措施。目前入侵检测最常采用的方法是先根据各种入侵行为的特点建立一个入侵行为特征(数据流中出现的特征字符串)库，并为每一种入侵行为关联一个安全措施，运行时通过在收到的数据包中检查是否存在这些特征字符串来判断是否存在入侵行为。在数据包中查找入侵特征串使用的是模式串匹配技术，研究表明模式串匹配是入侵检测系统中耗时最多的操作。随着网络速度及网络流量的激增，模式串匹配已成为决定入侵检测系统性能的主要因素。 模式串匹配是一个已经研究了很久的的问题，其应用十分广泛，也已经有很多算法被提出。根据应用的特点选择合适的模式串匹配算法、进行适应性改造并在特定平台上高效实现是模式串匹配应用研究的一个重要方面。随着网络速度及流量的增长，入侵检测面临的压力越来越大。目前基于通用处理器实现的模式串匹配只能达到100Mbps左右的速度，距离10Gbps的网络速度还很远，如何提高模式串匹配的速度是目前亟待解决的难题。网络处理器的出现为以较低的代价实现高速模式串匹配带来了新的解决方案，但目前基于网络处理器的模式串匹配研究开展得还不多。 本文研究适合于入侵检测的模式串匹配算法以及算法在网络处理器上的高效实现。在对目前使用最广泛的Snort入侵特征库的统计特性进行分析的基础上，本文选择FNP算法作为主要的模式串匹配算法并做了适应性改变，在具有相同前缀的模式串数量超过一定阈值时将FNP算法和AC算法相结合以改善FNP算法在最坏情况下的性能。本文选择IntelIXP2800网络处理器作为算法实现的平台，仔细研究了IXP2800的软硬件体系结构，充分利用其多核多线程的特点对算法进行了并行化。在IntelDevWorkbench仿真平台上对FNP-AC算法的测试表明，算法具有很好的扩放性，在10k规模的模式串集合上可达到6Gbps的吞吐量，且具有近乎线性的加速比。

目录

文摘

英文文摘

声明

第1章绪论

1.1模式串匹配问题

1.1.1模式串匹配在安全领域中的应用

1.1.2模式串匹配在生物信息学中的应用

1.1.3模式串匹配在信息检索中的应用

1.2模式串匹配研究现状

1.2.1模式串精确匹配算法(Gonzalo Navaro,2004)

1.2.2模式串近似匹配算法

1.2.3正则表达式匹配算法

1.2.4单模式串匹配算法

1.2.5多模式串匹配算法

1.3模式串匹配面临的困难

1.4本文贡献和内容结构安排

第2章相关多模式串匹配算法研究

2.1Aho-Corasick算法(LI Wei-Nan,2006)

2.2 Bitmapped AC算法

2.3 Wm-Manber算法

2.4 FNP算法

2.5基于Intel网络处理器的AC算法实现

2.5.1基于IXP2800的并行化AC算法

2.5.2基于IXP2850的Bit-Byte AC算法

2.6基于通用多核CPU的匹配算法

2.7本章小结

第三章网络处理器软硬件体系结构

3.1网络处理器概述

3.2 IXP2800的硬件体系结构

3.3 IXP2800的软件体系结构

3.3.1 Microblock

3.3.2核心组件

3.3.3优化的微引擎数据平面库

3.3.4 Dipatch环和微模块基础框架库

3.3.5资源管理器

3.3.6操作系统服务库

3.3.7核心组件

3.3.8控制面平台开发包

3.4基于IXP2800的编程模型

3.4.1上下文流水线模型

3.4.2功能流水线模型

3.5开发平台

3.6本章小节

第4章FNP-AC算法的设计与优化实现

4.1入侵规则集统计特性分析

4.2 FNP-AC算法设计思想

4.3 FNP-AC算法匹配操作流程

4.4数据结构设计

4.4.1 SDT表项中的位设置

4.4.2 哈希表HashT

4.5基于IXP2800的算法实现和优化

4.5.1内存压缩

4.5.2指令选择

4.5.3数据分配

4.5.4任务划分

4.5.5延迟槽填充技术

4.5.6长延迟隐藏

4.5.7 HASH指令的选择

4.5.8微代码实现

4.6本章小节

第5章算法仿真与性能分析

5.1 HCL链表的长度分析

5.2相对加速比

5.3访存测试

5.4微引擎空闲比率测试

5.5 SDT表跳跃距离分析

5.6 FNP-AC算法扩展性分析

5.7与FN算法最坏情况下比较分析

5.8与基于Intel NPU的匹配算法的性能比较

5.8.1与基于Intel NPU匹配算法的性能比较

5.8.2与基于Intel NPU匹配算法的内存模型比较

5.8.3与基于Intel NPU匹配算法的扩展行比较

5.9其他匹配算法的出现和发展

5.10本章小结

第6章结束语

6.1本文总结

6.2未来工作

参考文献

致谢

在读期间发表的学术论文与取得的研究成果