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

正则表达式匹配中的DFA优化技术研究

作　者: 秦元坤
导　师: 汪东升；薛一波
学　校: 清华大学
专　业: 计算机科学与技术
关键词: 词法分析 正则表达式 DFA优化技术 DFA分组 应用层协议解析
分类号: TP393.08
类　型: 硕士论文
年　份: 2008年
下　载: 286次
引　用: 6次
阅　读: 论文下载
 

内容摘要


随着Internet互联网技术的发展,针对应用层的攻击现象越来越多,传统的状态检测防火墙有效性越来越低。防火墙的功能重心从网络层发展到了应用层,因而诞生了深度包检测技术。深度包检测技术不仅检测数据包头部,而且深入到有效载荷,能够发现隐藏在其中的特征。随着深度包检测技术的发展,传统的字符串精确匹配技术逐渐被正则表达式匹配所代替。正则表达式具有字符串所不具备的强大和灵活的表达能力,能够准确地表达出复杂的特征。越来越多的防火墙和入侵检测系统已经使用正则表达式来描述它们的规则。正则表达式匹配可以分为基于NFA的正则表达式匹配与基于DFA的正则表达式匹配。由于DFA与NFA相比更适合在网络应用中使用,我们一般研究基于DFA的正则表达式匹配。虽然DFA具有先天的速度优势,但是匹配消耗空间过大和规则集规模较大时性能下降严重是它的两大缺点。本论文在对现有DFA优化技术深入研究和分析的基础上,提出了DFA分组算法EasyDG和字母表压缩算法SmallAlpha。前者可以提高规则集规模较大时的匹配性能,后者可以大幅减少匹配消耗空间。基于这两个算法,本文设计并实现了基于DFA的正则表达式匹配引擎SmartRE,与普通的DFA引擎相比,优化后的SmartRE在匹配性能与内存消耗方面均有比较出色的表现。最后,论文针对现实中的一种网络安全应用——应用层协议识别,设计并实现了应用层协议解析系统Jupiter。通过使用SmartRE作为核心模块并设置快速通道与慢速通道的匹配策略,Jupiter的匹配性能可以达到具有类似功能的L7-filter的70-80倍。

全文目录


摘要  3-4
Abstract  4-9
第1章 引言  9-17
  1.1 研究背景及课题意义  9-10
  1.2 深度包检测技术简介  10-13
  1.3 国内外研究现状  13-14
  1.4 论文主要工作及创新点  14-15
  1.5 论文组织结构及内容安排  15-17
第2章 正则表达式匹配  17-25
  2.1 正则表达式  17-19
  2.2 基于NFA 的正则表达式匹配  19-20
  2.3 基于DFA 的正则表达式匹配  20-22
  2.4 两种实现方式的比较  22-23
  2.5 选择DFA 引擎的原因  23-24
  2.6 本章小结  24-25
第3章 正则表达式匹配中的DFA 优化技术研究  25-43
  3.1 DFA 引擎的不足  25
  3.2 优化策略概述  25-26
  3.3 DFA 分组  26-31
    3.3.1 分组基础  26-28
    3.3.2 正则表达式的相互作用  28-29
    3.3.3 DFA 分组算法  29-31
  3.4 DFA 结构优化  31-42
    3.4.1 DDFA  31-35
    3.4.2 改进的DDFA  35-38
    3.4.3 HFA  38-42
  3.5 本章小结  42-43
第4章 基于DFA 的正则表达式匹配引擎SMARTRE  43-59
  4.1 设计背景  43
  4.2 DFA 分组算法EASYDG  43-48
    4.2.1 算法背景  43-45
    4.2.2 算法流程  45-47
    4.2.3 算法描述  47-48
  4.3 字母表压缩算法SMALLALPHA  48-51
    4.3.1 算法背景  48-49
    4.3.2 算法流程  49-50
    4.3.3 算法描述  50-51
  4.4 引擎架构设计与实现  51-56
    4.4.1 RegexToNFA 模块  52-56
    4.4.2 NFAtoDFA 模块  56
    4.4.3 DFA 优化模块  56
    4.4.4 匹配模块  56
  4.5 实验步骤及结果  56-58
    4.5.1 实验环境  56
    4.5.2 实验一：EasyDG 算法性能测试  56-57
    4.5.3 实验二：SmallAlpha 算法性能测试  57-58
    4.5.4 实验三：SmartRE 性能测试  58
  4.6 本章小结  58-59
第5章 应用层协议解析系统JUPITER  59-69
  5.1 系统简介及主要功能  59
  5.2 整体框架设计  59-61
  5.3 网络相关子系统  61-64
    5.3.1 抓包模块  61
    5.3.2 协议解析模块  61-62
    5.3.3 包分类及流重组模块  62-64
  5.4 协议识别子系统  64-66
    5.4.1 识别策略控制模块  64
    5.4.2 快速通道  64-65
    5.4.3 慢速通道  65-66
  5.5 结果处理子系统  66
  5.6 实验步骤及结果  66-67
    5.6.1 实验环境  66-67
    5.6.2 Jupiter 性能测试  67
  5.7 本章小结  67-69
第6章 总结与展望  69-70
参考文献  70-73
致谢  73-74
个人简历、在学期间发表的学术论文与研究成果  74

相似论文

  1. 基于CPU+GPU异构平台的字符串匹配算法研究与实现,TP301.6
  2. 面向存储的正则表达式匹配算法研究,TP393.08
  3. 基于特征匹配的深度报文检测性能优化研究,TP393.08
  4. BGP协议中正则表达式匹配系统的研究与软硬件实现,TP368.1
  5. 基于正则表达式的深度包压缩算法研究,TP393.08
  6. 基于GPU的高速正则表达式匹配技术研究,TP393.08
  7. WWW孤立文件发现机制的设计与应用,TP393.092
  8. 基于数据库的自然语言查询技术研究与实现,TP391.1
  9. 基于PTK嵌入系统的集成测试工具研究与实现,TP311.52
  10. Web信息抽取技术的研究与应用,TP393.09
  11. AFTN电报自动处理系统研究,TN917.72
  12. 基于FPGA的正则匹配引擎自动生成方法的研究,TN791
  13. 基于FPGA的正则表达式匹配技术的研究,TN791
  14. 面向农业领域的垂直搜索技术的研究,TP391.3
  15. 融合统计与规则技术的蒙古语词法分析研究,TP391.1
  16. RE控制程序源代码自动生成程序的研究与实现,TP311.52
  17. 日语词法分析及在跨语言信息检索中的应用研究,TP391.1
  18. 主观题自动阅卷系统的设计与实现,TP311.52
  19. 基于有限自动机的航班计划编排技术研究,V352
  20. Linux环境下基于正则表达式的DDoS防御算法研究及实现,TP393.08
  21. 基于协议分析的入侵防御系统的研究与实现,TP393.08

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