avatar avatar 我的文献 Snort规则建模及有穷自动机的转化与合并算法研究 作者 郑丽 单位 西安电子科技大学 导师 王宇平 关键词 Snort; 规则建模; NFA确定化; DFA合并
摘要
随着计算机和网络技术的快速发展,网络安全问题日益突出。由于防火墙只是一种被动防御性的网络安全工具,不能满足如今复杂多变的网络安全需求。因此作为防火墙的补充,入侵检测系统在网络安全领域发挥着越来越重要的作用。Snort是目前最为典型的轻量级网络入侵检测系统,该系统通过将捕获到的数据包与规则库中的规则进行匹配以过滤有危害的数据包,从而达到提高网络安全的目的。在将Snort与有穷自动机理论结合起来进行网络入侵检测的过程中,有以下几个关键问题需要解决:1)如何将Snort规则选项转化成PCRE,以便进一步转化成有穷自动机;2)如何将Snort规则使用统一的规范进行表示以便减小Snort规则处理的复杂度;3)如何减少将非确定有穷自动机(Nondeterministic Finite Automaton,NFA)转化为确定有穷自动机(Deterministic Finite Automaton, DFA)过程中的重复计算,以便提高NFA到DFA的转化效率;4)如何高效地将多个DFA合并成一个DFA以便加快数据包的过滤速度。针对以上四个问题,本文的主要工作如下:(1)根据Snort规则选项对于数据包的匹配顺序,建立了选项链模型,并进一步通过将规则选项转化成PCRE从而将选项链模型归一化为PCRE链模型。(2)提出了将NFA转化为DFA的一种新的高效算法以提高数据包与Snort规则的匹配速度。该算法首先使用哈希算法将NFA字符集上的字符进行分组,再使用改进的子集构造法将NFA转化成DFA。(3)提出了合并多个DFA的一种新的高效算法。该算法既不用将多个DFA构造成一个NFA也不用计算-closure就能将多个DFA合并成了一个DFA。实验结果表明,本文提出的有穷自动机转化算法和有穷自动机合并算法都是正确和高效的。其中有穷自动机转化算法可以有效避免子集构造法的重复计算,提高了转化效率,且得到的DFA的状态转换矩阵的存储空间比起传统方法也有较大压缩。
下载 cnki {{liketext}}
©2020 - iData {{ message }} 关闭