基于规则集的正则表达式匹配算法研究

发布时间：2021-11-11 09:11

　　随着正则表达式在网络安全系统和各种服务中的应用越来越广泛,这些系统采用正则表达式匹配算法作为他们的核心,检测数据包有效载荷中的攻击特征。最近几年的研究大多集中在大规模的正则表达式规则集下,如何有效地减少DFA存储空间的开销。在现代网络入侵检测系统中,如何从海量数据中甄别出有害信息,对阻止和遏制潜在的危险行为,对维护网络中数据的传输安全与稳定,对促进互联网产业健康发展,都具有十分重要的现实意义。为了检测数据包有效载荷中的危险模式,需要在线速度内完成正则表达式匹配。虽然确定性有限状态机（DFAs）允许此操作在线性时间内完成,但他们在内存中的存储可能会需要过高的需求。在内存存储空间中,DFA的开销主要用于存储其状态转移表,表的行宽对应DFA的状态数目,而表的列宽对应着每个状态的转移边数目|Σ|（Σ是输入字符的字母表）。对正则表达式规则集进行分组是一种用于解决DFA状态膨胀问题的重要方法。目前为止,对于DFA在内存中存储开销过大问题的解决思路,可以分为两种,即减少DFA的状态数目和压缩DFA的转移边,通过正则表达式规则集分组算法来压缩DFA的存储空间属于上述中的第一种解决思路。本文在对目前状态... 

【文章来源】：杭州电子科技大学浙江省

【文章页数】：60 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 课题研究背景及意义
    1.2 国内外研究现状
    1.3 论文研究内容安排
第2章 正则表达式匹配原理
    2.1 正则表达式介绍
    2.2 正则表达式匹配
        2.2.1 匹配算法
        2.2.2 匹配系统
    2.3 自动机选择
    2.4 基于规则集的分组算法
        2.4.1 分组算法背景知识
        2.4.2 分组算法介绍
        2.4.3 改进的分组算法介绍
    2.5 实验结果
    2.6 本章小结
第3章 DFA优化技术
    3.1 背景知识介绍
    3.2 压缩算法介绍
    3.3 改进的压缩算法介绍
    3.4 压缩算法比较
        3.4.1 最差时间边界和内存减少量
        3.4.2 算法复杂度比较和实际情况中的细节
        3.4.3 额外的方面
    3.5 字母表减少算法
        3.5.1 思想
        3.5.2 算法
    3.6 内存编码方式
        3.6.1 无压缩布局
        3.6.2 线性编码
        3.6.3 位图编码
        3.6.4 小结
    3.7 多步长DFAs
        3.7.1 多步长DFAs的寻址
        3.7.2 多步长DFA生成算法
    3.8 实验评估
    3.9 本章小结
第4章 基于规则集的最优匹配算法配置方法
    4.1 输入介绍
    4.2 实验评估
        4.2.1 参数
        4.2.2 度量
    4.3 处理器模拟器结果
        4.3.1 cache大小
        4.3.2 内存带宽和并行执行
    4.4 最佳正则表达式匹配配置
        4.4.1 最佳配置
        4.4.2 最优化指导
    4.5 本章小结
第5章 总结与展望
    5.1 论文总结
    5.2 研究方向展望
致谢
参考文献
附录


【参考文献】：
期刊论文
[1]正则表达式分组的1/（1-1/k）-近似算法[J]. 柳厅文,孙永,卜东波,郭莉,方滨兴.  软件学报. 2012(09)
[2]深度包检测中一种高效的正则表达式压缩算法[J]. 徐乾,鄂跃鹏,葛敬国,钱华林.  软件学报. 2009(08)
[3]基于GPU的串匹配算法研究[J]. 张庆丹,戴正华,冯圣中,孙凝晖.  计算机应用. 2006(07)



本文编号：3488594