正则表达式匹配存储优化技术研究

发布时间：2017-04-20 00:04

  本文关键词：正则表达式匹配存储优化技术研究，由笔耕文化传播整理发布。

【摘要】：网络安全问题成为关乎我国国计民生的大事,基于深度包检测(Deep Packet Inspection,DPI)技术的入侵检测系统(Intrusion Detection System, IDS)作为网络防护的重要手段,近年来得到广泛应用。正则表达式因其强大的功能和灵活表达手段成为DPI的核心算法。随着网络安全攻防双方的发展,攻击模式的不断复杂化和网络业务及应用的日新月异,IDS中正则表达式匹配技术仍存在诸多问题,其中最重要的是高速低存储的正则表达式匹配算法的设计。基于确定型有限状态自动机(Deterministic Finite Automata, DFA)的正则表达式算法因其线性的匹配速度得到广泛应用,但存在部分类型的规则编译时会产生状态爆炸问题、存储空间急剧增长的情况。本文从DFA的构建过程出发,分析当前算法的改进思路和存在的不足,对DFA算法进行存储优化,设计高速低存储的正则表达式算法。本文主要工作如下：多维立方体自动机(Multi-dimensional Finite Automata, MFA)利用多维结构的对称性,仅保留坐标轴和当前所处位置信息,通过状态的实时更新,降低存储空间。针对MFA适用规则类型较少问题,结合入侵检测系统克林闭包规则的特点,设计了扩展多维有限自动机算法(eXtend Multi-dimensional Finite Automata, XMFA)。对不满足对称性的结构,进行结构调整,增加辅助变量,增加适用的规则类型；为了完成快速状态更新,设计简单完备的状态跳转指针。理论分析和仿真实验表明,XMFA与DFA数量级相当的匹配时间,同时占用存储空间比基于DFA算法大大减少。采用分组算法解决DFA状态爆炸问题,随着分组数目的增加,时间效率大大降低。基于正则表达式引擎输入驱动特性理论,提出了驱动特性有限自动机(Drive Character Finite Automata, DCFA)分组算法。DCFA分组算法将规则类型作为正则表达式分组的依据,根据规则类型确定各分组采用的改进算法,保证各个类型的规则集不出现状态爆炸问题。实验表明,在简单规则情况下,DCFA用更少的分组数目达到Multiple DFAs(mDFA)算法存储压缩效果,提高了匹配效率。与经典的改进算法相比,DCFA预处理时间和存储空间比Hybrid-FA、D2FA算法降低了2～3个数量级；匹配时间与DFA算法相当。分析当前入侵检测系统Perl兼容的正则表达式(Perl Compatible Regular Expressions, PCRE)规则特点,基于驱动特性的分组方案和扩展多维有限自动机结构,设计一种可以应用于当前入侵检测系统的模板有限自动机(Templates Based Finite Automata, TFA)匹配算法。TFA算法根据IDS规则类型特点,设计规则分组模板,然后根据规则模板将规则集划分为若干个规则子集,各个规则子集根据系统结构分别构建高速低存储的匹配引擎。实验表明,与经典的改进算法相比,TFA预处理时间和存储空间比Hybrid-FA、D2FA算法降低了几个数量级；匹配时间与DFA算法数量级相当。
【关键词】：入侵检测系统 正则表达式匹配 确定性有限自动机 扩展多维有限自动机 分组算法 规则驱动特性 驱动特性有限自动机 模板有限自动机
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.08
【目录】：

• 摘要4-6
• Abstract6-12
• 第一章 绪论12-24
• 1.1 课题研究背景及研究意义12-14
• 1.2 正则表达式匹配相关研究14-16
• 1.2.1 正则表达式与有限自动机14-15
• 1.2.2 正则表达式匹配15-16
• 1.3 问题描述及研究现状16-21
• 1.3.1 DFA状态爆炸问题16-18
• 1.3.2 DFA改进算法综述18-21
• 1.4 论文的主要内容和章节安排21-24
• 1.4.1 主要内容21-22
• 1.4.2 章节安排22-24
• 第二章 多维扩展有限自动机XMFA24-38
• 2.1 引言24
• 2.2 多维立方体有限自动机MFA24-26
• 2.2.1 MFA简介24-25
• 2.2.2 MFA规则受限问题25-26
• 2.3 扩展多维有限自动机模型26-30
• 2.3.1 字符重叠26-27
• 2.3.2 克林闭包27-29
• 2.3.3 精确字符串29
• 2.3.4 起始标记29-30
• 2.4 XMFA算法设计30-35
• 2.4.1 XMFA激活状态设计31-32
• 2.4.2 规则预处理32-34
• 2.4.3 字符匹配过程34-35
• 2.5 仿真分析35-37
• 2.6 本章小结37-38
• 第三章 基于驱动特性的分组算法DCFA38-48
• 3.1 引言38
• 3.2 正则匹配引擎的驱动特性38-40
• 3.3 DCFA算法设计40-44
• 3.3.1 规则分组42
• 3.3.2 匹配引擎构造42-43
• 3.3.3 匹配过程43-44
• 3.4 仿真分析44-46
• 3.5 本章小结46-48
• 第四章 模板有限自动机TFA48-58
• 4.1 引言48
• 4.2 PCRE规则48-50
• 4.3 TFA算法设计50-54
• 4.3.1 规则模板制定与规则分组51-52
• 4.3.2 引擎构造和存储空间52-53
• 4.3.3 字符匹配过程53-54
• 4.4 仿真分析54-56
• 4.5 本章小结56-58
• 第五章 结束语58-60
• 5.1 论文主要的创新点和贡献58-59
• 5.2 下一步工作59-60
• 致谢60-62
• 参考文献62-68
• 作者简历68

【参考文献】

中国期刊全文数据库 前6条

1 贺炜;郭云飞;扈红超;;基于状态约束的大规模正则表达式匹配算法[J];通信学报;2013年10期

2 乔登科;王卿;柳厅文;孙永;郭莉;;基于状态分组的高效i-DFA构造技术[J];通信学报;2013年08期

3 张大方;张洁坤;黄昆;;一种基于智能有限自动机的正则表达式匹配算法[J];电子学报;2012年08期

4 张树壮;罗浩;方滨兴;云晓春;;一种面向网络安全检测的高性能正则表达式匹配算法[J];计算机学报;2010年10期

5 杨毅夫;刘燕兵;刘萍;郭牧怡;郭莉;;正则表达式的DFA压缩算法[J];通信学报;2009年S1期

6 徐乾;鄂跃鹏;葛敬国;钱华林;;深度包检测中一种高效的正则表达式压缩算法[J];软件学报;2009年08期

中国博士学位论文全文数据库 前1条

1 张树壮;面向网络安全的高性能特征匹配技术研究[D];哈尔滨工业大学;2011年

  本文关键词：正则表达式匹配存储优化技术研究，由笔耕文化传播整理发布。

，

本文编号：317434