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

面向存储的正则表达式匹配算法研究

作　者: 刘鹏
导　师: 姚远
学　校: 解放军信息工程大学
专　业: 计算机应用技术
关键词: 正则表达式深度报文检测面向存储确定的有限自动机状态爆炸
分类号: TP393.08
类　型: 硕士论文
年　份: 2010年
下　载: 110次
引　用: 1次
阅　读: 论文下载

内容摘要

正则表达式匹配作为网络安全应用的关键性技术,发挥着日益重要的作用。本文研究的正则表达式匹配算法以存储为中心,基于确定的有限自动机进行算法研究,以满足深度报文检测应用不断发展的需求。本文主要研究内容和工作如下:1、对传统正则表达式匹配算法进行分析和比较,阐述了选择面向存储架构进行算法设计的优势。对面向存储架构下的正则表达式匹配算法进行研究,为算法设计提供了多方位多角度的研究基础。2、研究规则集中正则表达式语法,分析正则表达式匹配准则及对算法设计的影响,对普遍存在的状态爆炸问题进行研究,为算法设计提供切入点和理论依据。3、设计了一种基于稀疏矩阵存储的状态表压缩算法,同字符表压缩算法结合,给出了该算法的优化策略。实验结果表明:结合单字符压缩表优化后的算法在Linux L7-filter和Bro规则集的存储空间压缩率普遍达到90%以上。4、给出了一种限制缺省路径条件下输入延迟的确定的有限自动机优化算法,采用权值优先原则和节点优先原则两种优化策略进行优化。实验结果表明:在Linux L7-filter规则集中直径限制较小时,优化算法可进一步压缩存储空间。5、针对单一计数约束模式引起的状态爆炸问题,设计了一种高效匹配单一计数约束模式的位图移位有限自动机。在对多计数约束模式合成研究的基础上,针对外部状态爆炸问题,设计了一种高效匹配多计数约束模式的蝶式自动机。

全文目录

摘要  10-11
ABSTRACT  11-12
第一章绪论  12-20
  1.1 课题的背景和意义  12-14
    1.1.1 课题的研究背景  12-13
    1.1.2 课题的意义  13-14
  1.2 深度报文检测技术简介  14-15
  1.3 国内外研究现状  15-17
  1.4 课题研究内容  17-18
  1.5 论文组织结构  18-20
第二章正则表达式匹配算法  20-36
  2.1 传统正则表达式匹配算法  20-25
    2.1.1 正则表达式  20-21
    2.1.2 基于NFA 的匹配算法  21-22
    2.1.3 基于DFA 的匹配算法  22-23
    2.1.4 DFA 和NFA 优劣分析  23-24
    2.1.5 多正则表达式匹配算法  24-25
  2.2 正则表达式匹配算法设计架构  25-26
    2.2.1 FPGA 逻辑架构的不足  25
    2.2.2 面向存储架构的优势  25-26
  2.3 面向存储的正则表达式匹配算法  26-35
    2.3.1 转换压缩算法  27-29
    2.3.2 状态压缩算法  29-33
    2.3.3 字符表压缩算法  33-35
  2.4 本章小结  35-36
第三章规则集中的正则表达式语法  36-44
  3.1 规则集中的正则表达式语法  36-39
    3.1.1 元字符和元序列  36-38
    3.1.2 正则表达式库比较  38-39
  3.2 匹配准则及对算法设计的影响  39-40
    3.2.1 匹配结果的完整性  39-40
    3.2.2 子串搜索模型  40
  3.3 状态爆炸问题  40-42
    3.3.1 Kleene 闭包  41-42
    3.3.2 计数字符组  42
  3.4 本章小结  42-44
第四章基于稀疏矩阵存储的状态表压缩算法  44-54
  4.1 稀疏矩阵索引的状态压缩表  44-49
    4.1.1 实例分析  44-45
    4.1.2 主要思想  45-49
  4.2 存储空间优化策略  49-50
  4.3 存储压缩效果评估  50-53
    4.3.1 实验环境及规则集  50
    4.3.2 实验结果与分析  50-53
  4.4 本章小结  53-54
第五章一种限制缺省路径的D~2FA 优化算法  54-62
  5.1 限制缺省路径的D~2FA 算法  54-55
  5.2 算法缺陷及分析  55-56
  5.3 基于可选策略的优化算法  56-58
  5.4 存储压缩效果评估  58-61
    5.4.1 实验环境及规则集  58-59
    5.4.2 实验结果与分析  59-61
  5.5 本章小结  61-62
第六章高效匹配计数约束模式的扩展自动机  62-80
  6.1 计数约束模式复杂性分析  62-65
  6.2 现有匹配算法局限性  65-67
    6.2.1 XFA 的局限性  65-66
    6.2.2 重写规则的局限性  66-67
  6.3 计数约束模式分类  67-69
  6.4 位图移位有限自动机  69-72
    6.4.1 实例分析  69-71
    6.4.2 形式化描述  71-72
  6.5 蝶式自动机  72-77
    6.5.1 外部状态爆炸  72-74
    6.5.2 问题的简化  74
    6.5.3 主要思想  74-76
    6.5.4 形式化描述  76-77
  6.6 存储压缩效果评估  77-79
    6.6.1 BS-FA  77-78
    6.6.2 蝶式自动机  78-79
  6.7 本章小结  79-80
结束语  80-82
参考文献  82-85
作者简历攻读硕士学位期间完成的主要工作  85-86
致谢  86

面向存储的正则表达式匹配算法研究

内容摘要

全文目录

相似论文