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

大规模特征串匹配技术的研究

作　者: 李雪
导　师: 王春露
学　校: 北京邮电大学
专　业: 计算机应用
关键词: 字符串匹配 大规模特征串精确匹配 大规模特征串近似匹配 SRS算法 SrsPex算法
分类号: TP393.08
类　型: 硕士论文
年　份: 2008年
下　载: 340次
引　用: 5次
阅　读: 论文下载
 

内容摘要


随着计算机网络及其应用的快速发展,人们可以非常便捷地获取所需的信息,计算机网络已经成为人们日常生活中不可缺少的一部分。当我们享受着互联网带来的巨大便利的同时,也受到了非法入侵、攻击、病毒、垃圾邮件等恶意行为的困扰。网络和信息安全问题已经成为网络正常运行和继续发展的重要问题。针对网络上的各种恶意行为,出现了很多不同的防御措施。从早期的防火墙,发展到后来的网络入侵检测/防御系统(IntrutionDetection/Prevention System,IDS/IPS)、病毒扫描系统,垃圾邮件过滤系统,最近又提出了统一威胁管理(Unified Threat Management,UTM)系统。而字符串匹配技术是这些网络信息安全系统和设备的核心技术。随着网络上恶意行为种类和数量的急剧增加,不管是传统的网络入侵检测/防御系统、病毒扫描系统,还是最新的集众多功能于一身的统一威胁管理系统,需要配置的规则数量都急剧增长,少则几万,多则十几万,这就急需大规模特征集的字符串匹配技术。而且,网络的速度越来越快,网络和信息安全系统需要实时在线处理,这就对字符串匹配算法的性能提出了很高的要求。本文的主要目的就是要提出一种适用于大规模特征集的、高性能的字符串匹配算法。本文中研究了大规模特征串匹配技术,包括精确匹配算法和近似匹配算法。通过对经典算法的研究和分析,找到其不适合大规模特征集的瓶颈所在,并提出一种适用于大规模特征集的快速精确匹配算法——SRS算法,该算法性能优异,在特征集达到10万条时,匹配速度比经典算法快10倍以上;另外还给出了一种适用于大规模特征集的高效近似匹配算法——SrsPex算法,该算法在近似特征集规模为1万条时,匹配速度达到100MB/s以上,最高达到近400MB/s。在此基础上,本文从开放源码的反病毒软件ClamAV中提取实际的病毒特征库进行分析,然后用防病毒领域的真实病毒库验证了SRS算法。

全文目录


摘要  4-5
ABSTRACT  5-6
目录  6-8
缩略语  8-9
第一章 绪论  9-13
  1.1 研究背景  9-10
  1.2 国内外相关研究  10-11
    1.2.1 特征串精确匹配算法  10-11
    1.2.2 特征串近似匹配算法  11
  1.3 本文的工作和成果  11
  1.4 本文的组织结构  11-13
第二章 大规模特征串精确匹配技术的研究  13-42
  2.1 精确匹配技术的国内外研究现状和趋势  13-23
    2.1.1 单模式匹配算法  13-15
    2.1.2 多模式匹配算法  15-22
    2.1.3 各种改进算法  22-23
  2.2 经典多模式匹配算法的不足  23-24
  2.3 针对大规模特征串精确匹配的改进算法——SRS算法  24-32
    2.3.1 SRS算法思想  24-25
    2.3.2 SRS算法的结构设计  25-27
    2.3.3 shift表和prefix表的建立  27
    2.3.4 sub-shift表的建立  27-29
    2.3.5 same-pos表的建立  29-31
    2.3.6 SRS算法的搜索过程  31
    2.3.7 SRS算法优化-特征集合的划分  31-32
  2.4 SRS算法模块设计  32-33
    2.4.1 模块汇总表  32
    2.4.2 模块关系图  32-33
  2.5 模块详细设计  33-37
    2.5.1 预处理模块设计  33-35
    2.5.2 搜索模块设计  35-37
  2.6 SRS算法的性能评价  37-41
    2.6.1 实验环境描述  37
    2.6.2 算法匹配性能比较  37-41
  2.7 结束语  41-42
第三章 大规模特征串近似匹配技术的研究  42-64
  3.1 近似匹配技术的国内外研究现状和趋势  42-51
    3.1.1 近似匹配算法  42
    3.1.2 国内外研究现状  42-44
    3.1.3 单模式近似特征匹配算法  44-48
    3.1.4 多模式近似特征匹配算法  48-51
  3.2 经典多模式近似匹配算法的不足  51
  3.3 针对大规模特征串近似匹配的改进算法——SrsPex算法  51-53
    3.3.1 编辑距离下多模式近似匹配算法  51
    3.3.2 SrsPex算法设计思想  51-52
    3.3.3 SrsPex算法的结构设计  52-53
  3.4 SrsPex算法模块设计  53-54
    3.4.1 模块汇总表  53
    3.4.2 模块关系图  53-54
  3.5 算法详细设计  54-59
    3.5.1 数据结构设计  54-55
    3.5.2 预处理过程详细设计  55-57
    3.5.3 搜索过程详细设计  57-58
    3.5.4 BPM算法模块详细设计  58-59
  3.6 SrsPex算法的性能评价  59-63
    3.6.1 实验环境描述  59
    3.6.2 算法匹配性能分析  59-63
  3.7 结束语  63-64
第四章 真实病毒特征库对 SRS算法的验证  64-71
  4.1 防病毒系统原理  64-65
  4.2 采用特征代码法的防病毒系统存在的问题  65
  4.3 开源防病毒软件-ClamAV分析  65-67
    4.3.1 ClamAV中的核心算法和处理流程  65-66
    4.3.2 ClamAV病毒库分析  66-67
  4.4 SRS算法在防病毒系统中的应用  67-68
  4.5 性能测试与分析  68-70
    4.4.1 ClamAV特征集匹配速度比较  68-69
    4.4.2 ClamAV特征集占用内存比较  69
    4.4.3 ClamAV特征集预处理时间比较  69-70
  4.6 结束语  70-71
第五章 总结与展望  71-72
参考文献  72-75
作者攻读学位期间发表的学术论文目录  75
作者攻读学位期间参加的科研项目  75-77
致谢  77

相似论文

  1. 基于CPU+GPU异构平台的字符串匹配算法研究与实现,TP301.6
  2. 相似字符串匹配过滤算法研究,TP391.1
  3. 针对大规模URL关键字的多模匹配算法的性能优化,TP309
  4. 基于串匹配和文本分类的中文网页过滤系统设计,TP393.092
  5. 出版物审读系统的设计与实现,G231
  6. 基于Windows API的VB编程题自动评分系统的研究与实现,TP311.52
  7. 基于后缀语法树的代码抄袭检测研究,TP311.11
  8. 网络安全隔离设备高速匹配算法的研究与实现,TP393.08
  9. 基于改进型Bloom Filter的深度包检测技术研究,TP393.08
  10. 基于HTTP协议面向中文文本的过滤技术研究,TP391.1
  11. 文本自动标引方法研究与实现,TP391.3
  12. 全文索引结构的压缩与应用,TP391.3
  13. 基于协议分析的P2P流量检测技术,TP393.08
  14. 蠕虫型僵尸工具的传播模型及检测技术研究,TP393.08
  15. 入侵检测系统中检测引擎的研究与实现,TP393.08
  16. 对串匹配技术中的Wu-Manber算法的研究,TP301.6
  17. 高性能精确单模式串匹配算法研究,TP301.6
  18. 基于Snort系统特殊字符串匹配算法的研究,TP393.08
  19. 用位并行法进行过滤的中文近似串匹配算法,TP391.1
  20. 网络入侵检测系统框架的研究及通用测试平台的实现,TP393.08
  21. 内容过滤防火墙的设计与实现,TP393.08

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络安全
© 2012 www.xueweilunwen.com