Snort规则建模及有穷自动机的转化与合并算法研究

发布时间：2018-07-04 17:49

本文选题：Snort + 规则建模　；参考：《西安电子科技大学》2014年硕士论文

【摘要】：随着计算机和网络技术的快速发展，，网络安全问题日益突出。由于防火墙只是一种被动防御性的网络安全工具，不能满足如今复杂多变的网络安全需求。因此作为防火墙的补充，入侵检测系统在网络安全领域发挥着越来越重要的作用。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的状态转换矩阵的存储空间比起传统方法也有较大压缩。
[Abstract]:With the rapid development of computer and network technology, the problem of network security is becoming more and more prominent. Since firewall is only a passive defensive network security tool, it can not meet the needs of complex and changeable network security. Therefore, as a supplement of firewall, intrusion detection system (IDS) plays a more and more important role in the field of network security. Snort is the most typical lightweight network intrusion detection system. By matching the captured data packets with the rules in the rule base, the system filters the harmful data packets, so as to improve the network security. In the process of network intrusion detection based on snort and finite automata theory, there are several key problems that need to be solved: 1) how to convert snort rule options into PCREs in order to further transform snort rules into finite automata; 2) how to express snort rules using uniform specification to reduce the complexity of snort rule processing. How to reduce the double computation in the process of converting nondeterministic finite automata (NFA) into deterministic finite automaton (DFA). In order to improve the conversion efficiency of NFA to DFA 4) how to efficiently combine multiple DFAs into one DFA to speed up packet filtering. For the above four problems, the main work of this paper is as follows: (1) based on the snort rule options for the matching order of packets, a necklace-selecting model is established. Furthermore, by transforming the rule options to PCRE, the necklace-selection model is normalized to PCRE chain model. (2) A new efficient algorithm for converting NFA to DFA is proposed to improve the matching speed between packets and snort rules. The algorithm first uses hash algorithm to group characters on NFA character set, then transforms NFA into DFAs by using improved subset construction method. (3) A new efficient algorithm for merging multiple DFAs is proposed. The algorithm can combine multiple DFAs into a single DFA without either constructing multiple DFAs into one NFA or calculating a closure. The experimental results show that both the finite automata transform algorithm and the finite automata merging algorithm proposed in this paper are correct and efficient. The finite automata transform algorithm can effectively avoid the repeated computation of the subset construction method and improve the conversion efficiency. The storage space of the state conversion matrix of the obtained DFA is also larger than that of the traditional method.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.08

【参考文献】