学位论文 > 优秀研究生学位论文题录展示

千万模式集高效匹配算法的研究与实现

作　者: 曹晓龙
导　师: 张宏莉
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 字符串匹配千万模式集合 AC算法 Wu-Manber算法 DAT算法内存压缩
分类号: TP393.08
类　型: 硕士论文
年　份: 2012年
下　载: 12次
引　用: 0次
阅　读: 论文下载

内容摘要

字符串匹配一直都是计算机科学的研究热点和难点。在信息安全领域中，关键字规模变大、互联网流量的增加，使得字符串匹配算法成为网络安全系统的性能瓶颈。本论文首先综述了三种经典的多模式精确匹配算法，深入总结了这三种算法的优缺点。然后，在深入分析了现有规则集合的基础上，总结出了千万模式集合的特点。其次，针对千万模式集合匹配的需求，设计了基于AVL树的AC优化算法ACVL和基于分类思想的多模匹配算法CDWH两种算法。ACVL算法是利用AVL树来优化AC算法的内存占用情况，使AC算法可以支持千万模式集合的要求，同时还给出了ACVL算法的优化方面，使用规则去重、状态压缩、路径压缩三种方法来进一步压缩内存，实验表明ACVL算法在加载千万模式集合时使用内存仅为2.5G。CDWH算法是利用分类的思想，将模式集合分为长字符串模式集合和短字符串模式集合，然后分别采用DAT算法和WM算法进行匹配。CDWH算法还对DAT算法进行了内存压缩和缩短初始化时间的优化，并对WM算法进行了Hash冲突集减小和加快完全匹配速度的优化。最后，本论文分别实现了ACVL算法和CDWH算法，以可扩展的方式支持真实系统的运行，并进行了性能测试。离线测试分别测试算法的正确性，以及算法在不同规则模式集下的性能表现，包括初始化时间、占用内存量和扫描时间等。在线测试则测试了ACVL算法和CDWH算法的扫描速度。然后比较了ACVL算法和CDWH算法的测试结果，结果表明CDWH算法明显优于ACVL算法，它可以为系统带来21.4%的性能提升。

全文目录

摘要  4-5
Abstract  5-8
第1章绪论  8-16
  1.1 课题研究的背景及意义  8-11
    1.1.1 课题的研究背景  8-10
    1.1.2 课题的研究意义  10-11
  1.2 字符串匹配算法的国内外研究现状和分析  11-14
    1.2.1 相关研究工作  11-13
    1.2.2 存在的问题  13-14
  1.3 课题的主要研究内容和贡献  14-15
  1.4 内容安排  15-16
第2章精确多模式匹配算法分析  16-27
  2.1 字符串匹配基本概念  16-17
  2.2 常用的多模式匹配算法  17-24
    2.2.1 基于前缀搜索的 AC 自动机算法  18-19
    2.2.2 基于后缀搜索的 Wu-Manber 跳越扫描算法  19-22
    2.2.3 基于子串搜索的 SBOM 算法  22-24
  2.3 常用多模匹配算法性能分析  24-26
  2.4 本章小结  26-27
第3章基于 AVL 树的 AC 优化算法 ACVL  27-42
  3.1 引言  27
  3.2 AVL 树简介  27-31
  3.3 基于 AVL 树的 AC 优化算法 ACVL  31-35
    3.3.1 规则去重  32-33
    3.3.2 状态压缩  33-34
    3.3.3 路径压缩  34-35
  3.4 ACVL 算法的实现  35-41
    3.4.1 基本匹配流程  35-36
    3.4.2 规则集合初始化流程  36-39
    3.4.3 数据扫描流程  39-41
  3.5 本章小结  41-42
第4章基于分类思想的多模匹配算法 CDWH  42-55
  4.1 引言  42
  4.2 DAT 算法简介  42-45
  4.3 基于分类思想的多模匹配优化算法 CDWH  45-50
    4.3.1 DAT 算法的优化  46-48
    4.3.2 WM 算法的优化  48-50
  4.4 CDWH 算法的实现  50-54
    4.4.1 规则集初始化流程  51-53
    4.4.2 数据扫描流程  53-54
  4.5 本章小结  54-55
第5章实验结果与分析  55-65
  5.1 离线测试  55-61
    5.1.1 测试环境  55
    5.1.2 正确性测试  55-56
    5.1.3 性能测试  56-60
    5.1.4 离线测试总结  60-61
  5.2 在线测试  61-64
    5.2.1 测试环境  61
    5.2.2 测试方案  61-62
    5.2.3 ACVL 算法测试结果  62
    5.2.4 CDWH 算法测试结果  62-63
    5.2.5 在线测试总结  63-64
  5.3 本章小结  64-65
结论  65-67
参考文献  67-72
致谢  72

千万模式集高效匹配算法的研究与实现

内容摘要

全文目录

相似论文