高性能大规模模式匹配算法研究

论文摘要

作为网络安全系统的核心技术之一,模式匹配算法的效率直接影响,甚至是决定了系统的整体性能,因而一直是学术界和工业界普遍关注的热点问题。目前,模式匹配算法研究所面临的主要挑战是模式集规模的迅速增大。绝大多数经典的模式匹配算法无法直接有效地运用到大规模模式集条件下。而且,随着网络带宽的不断增加,模式匹配算法往往会成为系统的瓶颈所在。所以,研究高性能的适用于大规模模式集的模式匹配算法是当务之急,具有重要的学术意义和广阔的应用前景。本文介绍了一种高效的大规模模式匹配算法MDH。该算法利用多级哈希思想削减了算法在大规模模式集下的内存空间占用,又通过动态切割策略充分挖掘了模式集的启发式信息,提升了算法的匹配性能。实验证明,在模式串个数大于2万的情况下,相比于AC,WM,SBOM等等几种经典的多模式匹配算法,MDH算法的匹配速度要快100%到300%以上,内存消耗却非常小。然后,本文又在MDH算法的基础上,设计了模式长度自适应优化和智能验证优化方案,突破了算法固有的局限性,进一步增强了算法的可扩展性。同时,还设计了多种MDH多核多线程并行算法,充分利用通用多核CPU平台和最新的多核专用网络应用处理器平台的硬件架构优势,大幅提升了算法的匹配性能。最后,本文以实际的病毒扫描系统Clam AntiVirus为依托,提出了一套基于MDH算法的高性能病毒扫描解决方案。系统整体性能的提升证明了MDH算法的实用性和优秀的可移植性。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 网络安全技术
• 1.2 模式匹配研究
• 1.3 论文主要工作和贡献
• 1.4 论文结构安排
• 第2章 模式匹配算法综述
• 2.1 模式匹配基本问题
• 2.2 模式匹配经典算法
• 2.2.1 前缀匹配算法
• 2.2.2 后缀匹配算法
• 2.2.3 子串匹配算法
• 2.3 BOYER-MOORE 算法
• 2.4 WU-MANBER 算法
• 2.5 经典算法比较分析
• 2.6 本章小结
• 第3章 高性能大规模模式匹配算法MDH 的设计与实现
• 3.1 主要设计思想
• 3.1.1 多级哈希思想
• 3.1.2 动态切割策略
• 3.1.3 小结
• 3.2 算法数据结构和流程
• 3.2.1 算法数据结构
• 3.2.2 预处理阶段
• 3.2.3 匹配阶段
• 3.3 实验测试与结果分析
• 3.3.1 算法匹配性能实验
• 3.3.2 算法思想论证实验
• 3.3.3 优化参数选择实验
• 3.3.4 本章小结
• 第4章 MDH 算法优化
• 4.1 MDH 算法局限性分析
• 4.2 模式长度自适应优化算法
• 4.3 智能验证算法优化
• 4.3.1 智能验证思想
• 4.3.2 具体流程
• 4.3.3 实验测试
• 4.4 并行化优化算法设计
• 4.4.1 利用并行技术提升算法性能
• 4.4.2 通用CPU 平台下的多线程优化
• 4.4.3 专用多核硬件平台并行优化
• 4.5 本章小结
• 第5章 实际应用研究
• 5.1 CLAMAV 系统架构和模式集分析
• 5.1.1 系统架构
• 5.1.2 模式组成
• 5.1.3 模式特征
• 5.2 MDH-CLAMAV 系统设计与实现
• 5.2.1 匹配流程分析
• 5.2.2 系统瓶颈判断
• 5.2.3 解决方案
• 5.3 实验设计与结果分析
• 5.3.1 实验一：MDH 和BMEXT 算法性能对比
• 5.3.2 实验二：新旧ClamAV 病毒扫描性能对比
• 5.4 本章小结
• 第6章 结论与展望
• 6.1 论文研究工作总结
• 6.2 未来的一些研究方向
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果