基于OBDD的模式匹配算法研究

摘要

目前，计算机和网络发展越来越迅速，随之而来的网络安全问题也越来越突出。现代网络安全应用通常采用深层数据包检测来识别恶意流量，如基于网络的入侵检测系统(NIDS)和防火墙。防火墙是被动防御保护技术，无法满足大量复杂变化的数据。入侵检测系统作为防火墙的补充，在网络安全领域发挥着越来越重要的作用。
　　在入侵检测系统中，检测的性能依赖于攻击签名的准确性与多样性，因此攻击签名是入侵检测实现的关键。在网络安全中理想的模式匹配算法应用必须满足两个要求:时间效率和空间效率。由于入侵检测系统和防火墙通常部署在高速的网络节点上，要求处理每个数据的时间很小以便于满足高速网络的数据包处理速度，而空间效率要求算法运行使用的存储器空间尽量小。同时，目前大部分模式匹配只考虑包含非捕获组的正则表达式，不支持子匹配提取。子匹配提取的现有的解决方案是基于非确定性有限自动机(Nondeterministic FiniteAutomaton，NFA)或递归回溯的。NFA空间复杂度低，并且能够提取紧凑的内存足迹子匹配，但是时间复杂度高。
　　有序二元决策图(Ordered Binary Decision Diagram，OBDD)可以对信息进行高效压缩，从而有效地处理大规模问题。本文结合OBDD的数据结构特点和模式匹配算法处理签名匹配。
　　本文重点研究了模式匹配算法的问题，主要工作为以下几个方面:
　　使用三个向量布尔变量→x，→y和→i为NFA(Q，∑，δ，q0，Fin)定义四个布尔函数，然后使用OBDD来表示和操作布尔函数，对基于不确定有限自动机(NFA)的模式匹配进行改进，提出NFA-OBDD，提高基于NFA的签名匹配的时间效率。
　　使用标记来区分正则表达式中的捕获组，并扩展Thompson的NFA构造方法来支持正则表达式。
　　用布尔函数表示标记的NFA，并采用OBDD来操作布尔函数，提出Submatch-OBDD，提高子匹配提取的时间效率，以满足部署在高速的网络上的Snort入侵检测系统实现快速匹配恶意流量的需求。
　　实验结果表明，提出的NFA-OBDD是正确且高效的，优于现有的方法约一至三个数量级，同时避免内存爆炸和抵抗已知算法复杂度的攻击。同时，Submatch-OBDD有效提高子匹配提取效率，通过网络流量，合成的流量，和企业的事件日志来测试Submatch-OBDD的时间效率和空间效率，当把模式组合的时候，Submatch-OBDD达到了理想的性能。在最好的情况下，Submatch-OBDD的速度比RE2和PCRE快一到两个数量级。

目录

声明

摘要

第1章 绪论

1．1 课题研究的目的及意义

1．2 国内外研究现状

1．2．1 模式匹配在网络安全中的应用

1．2．2 模式匹配研究现状

1．3 课题研究的内容

1．4 本文结构

第2章 有序二元决策图

2．1 OBDD的定义

2．2 OBDD的操作

2．3 表示关系和集合

2．4 OBDD的应用

2．5 本章小结

第3章 采用OBDD改进基于NFA签名匹配算法

3．1 概述

3．2 NFA-OBDD的表示和设计

3．2．1 使用布尔函数的NFA操作

3．2．2 NFA-OBDD的实现

3．3 实验结果与分析

3．3．1 实验数据集

3．3．2 实验装置

3．3．3 NFA-OBDD的结构和性能

3．3．4 NFA-OBDD与NFA的比较

3．3．5 NFA-OBDD与PCRE的比较

3．3．6 NFA-OBDD与DFA变体的比较

3．4 本章小结

第4章 采用OBDD实现快速子匹配

4．1 概述

4．2 Submatch-OBDD的设计与实现

4．2．1 为NFA分配标记

4．2．2 在标记的NFA上的操作

4．2．3 布尔函数的表示

4．2．4 Submatch-OBDD的实现

4．3 实验结果和分析

4．3．1 数据集

4．3．2 实验装置

4．3．3 实验结果

4．4 本章小结

结论

参考文献

攻读硕士学位期间所发表的学术论文

致谢