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

基于正则表达式的深度包压缩算法研究

作　者: 段海生
导　师: 李凤华
学　校: 西安电子科技大学
专　业: 计算机系统结构
关键词: 深度包检测正则表达式压缩 DFA拆分算法
分类号: TP393.08
类　型: 硕士论文
年　份: 2010年
下　载: 66次
引　用: 0次
阅　读: 论文下载

内容摘要

传统的深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,但是随着检测的内容日益繁杂,这种检测方法已不能很好的满足要求,而正则表达式能提供更强的表达能力和灵活性,因此基于正则表达式的深度包检测渐渐成为研究的核心。一个典型的模式集合往往包含上百个正则表达式,复杂的正则表达式用DFA(确定性有限自动机)存储,因为所需内存太大,从而使得时空复杂度较大,极大地降低了检测算法的效率。目前,如何提高基于正则表达式的深度包检测技术的效率,在国内外尚处于探索阶段。本文所进行的研究正是在该背景下展开的。本文首先分析当前IDS(入侵检测系统)存在的缺点,介绍CLAY系统(关联引擎的通用程序框架),介绍当前深度包技术的相关研究；然后在介绍数据包过滤技术和入侵检测技术的基础上,阐述深度包检测技术的工作原理。通过对常见模式匹配算法优缺点的分析,介绍正则表达式压缩并提出DFA拆分算法。正则表达式压缩是对于一些符合重写规则的正则表达式在转换成DFA之前,通过重写规则来改写正则表达式,使得DFA状态数由原来的平方或指数增长降低为线性增长。DFA拆分算法将DFA状态转换表拆分为间接索引表、转换输出表、直接转换表,使得DFA所占空间大大减少,从而高效率地实现了DFA的压缩存储,达到了理想效果。最后提出将正则表达式压缩和DFA拆分算法应用到CLAY系统中,用于检测网络中的深度包,有一定的实用价值。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-11
  1.1 课题背景及意义  7-8
  1.2 课题来源  8
  1.3 CLAY系统简介  8-9
  1.4 深度包技术的相关研究  9-10
  1.5 论文结构  10-11
第二章深度包检测技术  11-21
  2.1 深度包检测  11-18
    2.1.1 数据包过滤技术  11-13
    2.1.2 入侵检测技术  13-18
  2.2 深度包检测技术工作原理  18-19
  2.3 本章小结  19-21
第三章模式匹配  21-37
  3.1 正则表达式匹配  21-31
    3.1.1 基于DFA的正则表达式匹配  22-23
    3.1.2 基于NFA的正则表达式匹配  23-24
    3.1.3 NFA与DFA的等价性和DFA的最小化  24-29
    3.1.4 由正则表达式构造FA——Thompson法  29-31
  3.2 基本的模式匹配算法  31-35
    3.2.1 Brute-Force算法  32
    3.2.2 Knuth-Morris-Pratt(KMP)算法  32-33
    3.2.3 Boyer-Moore算法  33-34
    3.2.4 Aho-Corasick算法  34-35
    3.2.5 Aho-Corasick_Boyer-Moore算法  35
  3.3 本章小结  35-37
第四章正则表达式压缩  37-45
  4.1 正则表达式压缩相关概念  37-38
    4.1.1 匹配结果完整性概念  37-38
    4.1.2 子串匹配DFA模型概念  38
  4.2 正则表达式DFA分析  38-41
    4.2.1 二次方增长的DFA  38-40
    4.2.2 指数型增长的DFA  40-41
  4.3 正则表达式的重写规则  41-43
    4.3.1 重写规则一  41-42
    4.3.2 重写规则二  42-43
  4.4 模式写作的建议  43
  4.5 本章小结  43-45
第五章 DFA拆分算法  45-53
  5.1 算法背景  45
  5.2 DFA状态转换表的可压缩性分析  45
  5.3 算法思想描述  45-51
    5.3.1 算法思想表述  47-49
    5.3.2 主要数据结构  49-51
  5.4 本章小结  51-53
第六章实验结果及应用  53-61
  6.1 模式集简介  53-55
    6.1.1 Linux L7-filter简介  53
    6.1.2 Snort简介  53-54
    6.1.3 Bro简介  54-55
  6.2 正则表达式的压缩分析统计  55-56
    6.2.1 各种模式集规则  55-56
    6.2.2 重写规则应用统计  56
  6.3 DFA拆分算法仿真实验结果  56-59
    6.3.1 仿真实验环境  56
    6.3.2 仿真实验结果  56-59
  6.4 压缩算法实用场景  59-60
  6.5 本章小结  60-61
第七章总结及展望  61-63
  7.1 本论文工作总结  61
  7.2 进一步的展望  61-63
致谢  63-65
参考文献  65-69
研究成果  69

基于正则表达式的深度包压缩算法研究

内容摘要

全文目录

相似论文