网包正则表达式匹配算法研究

发布时间：2021-11-19 00:54

　　随着互联网逐步发展成为综合性业务运营平台，新型应用不断涌现，信息容量稳步增长，网络接口速率快速提升。作为网络安全和精细化运营、管理的重要支撑，报文检测技术在匹配速率、资源占用等方面面临严峻挑战。为解决以上问题，正则表达式匹配技术成为现代网络关注和研究的热点。本文以提升正则表达式匹配速率为目标，按照理论分析、算法设计、平台验证的思路，对正则表达式匹配算法进行了研究。主要内容包括三个方面：提升正则表达式匹配速率、降低内存占用以及支持并发数据流的匹配。为提升正则表达式匹配速率，从自动机基础理论出发，分析了单周期多字符匹配结构的特性，并针对其存在的问题，提出一种单周期处理多字符的正则表达式匹配算法MC-DFA。通过合并标准DFA结构中的单字符状态转移，MC-DFA算法可以在单周期内处理多个字符，达到提升匹配速率的目标；为降低多字符处理引入的存储冗余，MC-DFA针对性的设计了状态转移表深度压缩算法，使得内存占用增长较小。MC-DFA算法在FPGA平台上达到了6.7Gbps的吞吐率。为降低DFA结构的内存占用，通过分析NFA转化为DFA时的状态指数增长现象，设计了基于状态约束的混合自动机结构SC... 

【文章来源】：战略支援部队信息工程大学河南省

【文章页数】：70 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
图录
表录
第一章 绪论
    1.1 研究背景与意义
    1.2 相关工作回顾
        1.2.1 正则表达式匹配原理
        1.2.2 提升匹配速率的方法
        1.2.3 减少内存占用的方法
        1.2.4 支持并发数据流匹配的方法
        1.2.5 正则表达式匹配技术总结与展望
    1.3 主要研究内容
    1.4 论文组织结构
第二章 支持单周期多字符匹配的 MC-DFA
    2.1 多字符匹配特性分析
    2.2 核心算法
        2.2.1 输入字符翻倍算法 ICDA
        2.2.2 ICDA 算法性能分析
        2.2.3 STT 深度压缩算法 STT-DCA
        2.2.4 MC-DFA 性能分析
    2.3 性能评价
        2.3.1 测试数据及平台
        2.3.2 单字符平均内存访问次数
        2.3.3 吞吐率
        2.3.4 内存占用
        2.3.5 预处理时间
    2.4 本章小结
第三章 支持大规模特征的混合自动机结构 SC-HFA
    3.1 状态数指数增长现象分析
    3.2 核心算法
        3.2.1 状态间约束关系设计
        3.2.2 NFA 状态分组算法
        3.2.3 NFA/DFA 混合结构生成算法
        3.2.4 性能分析
        3.2.5 SC-HFA 结构
    3.3 性能评价
        3.3.1 测试数据及平台
        3.3.2 二级分割参数 k p 的选取
        3.3.3 空间存储性能
        3.3.4 吞吐率
        3.3.5 单字符平均内存访问次数
        3.3.6 预处理时间
    3.4 本章小结
第四章 基于时分复用的并发数据流匹配方案 VLSM-HFA
    4.1 时分复用的特点
    4.2 核心思想
        4.2.1 Memory-HFA
        4.2.2 数据流的预处理
        4.2.3 变长切换机制 VLS
        4.2.4 VLSM-HFA 结构
        4.2.5 性能分析
    4.3 FPGA 实现
        4.3.1 硬件结构设计
        4.3.2 分布式 RAM 映射
        4.3.3 流水线设计
    4.4 性能评价
        4.4.1 测试数据及平台
        4.4.2 多数据流支持和内存占用
        4.4.3 吞吐率
        4.4.4 预处理时间
    4.5 本章小结
第五章 总结与展望
    5.1 主要成果
    5.2 工作展望
致谢
参考文献
作者简历 攻读硕士学位期间完成的主要工作


【参考文献】：
博士论文
[1]网络内容分析中基于硬件的字符串匹配算法的研究[D]. 李奇越.中国科学技术大学 2008



本文编号：3503954