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

发布时间：2018-06-02 23:29

本文选题：模式匹配 + 布尔函数　；参考：《哈尔滨理工大学》2017年硕士论文

【摘要】：目前,计算机和网络发展越来越迅速,随之而来的网络安全问题也越来越突出。现代网络安全应用通常采用深层数据包检测来识别恶意流量,如基于网络的入侵检测系统(NIDS)和防火墙。防火墙是被动防御保护技术,无法满足大量复杂变化的数据。入侵检测系统作为防火墙的补充,在网络安全领域发挥着越来越重要的作用。在入侵检测系统中,检测的性能依赖于攻击签名的准确性与多样性,因此攻击签名是入侵检测实现的关键。在网络安全中理想的模式匹配算法应用必须满足两个要求:时间效率和空间效率。由于入侵检测系统和防火墙通常部署在高速的网络节点上,要求处理每个数据的时间很小以便于满足高速网络的数据包处理速度,而空间效率要求算法运行使用的存储器空间尽量小。同时,目前大部分模式匹配只考虑包含非捕获组的正则表达式,不支持子匹配提取。子匹配提取的现有的解决方案是基于非确定性有限自动机(Nondeterministic Finite Automaton,NFA)或递归回溯的。NFA空间复杂度低,并且能够提取紧凑的内存足迹子匹配,但是时间复杂度高。有序二元决策图(Ordered Binary Decision Diagram,OBDD)可以对信息进行高效压缩,从而有效地处理大规模问题。本文结合OBDD的数据结构特点和模式匹配算法处理签名匹配。本文重点研究了模式匹配算法的问题,主要工作为以下几个方面:使用三个向量布尔变量(?),(?)和(?)为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快一到两个数量级。
[Abstract]:At present, computers and networks are developing more and more rapidly, and the problems of network security are becoming more and more prominent. Modern network security applications usually use deep packet detection to identify malicious traffic, such as network based intrusion detection systems (NIDSs) and firewalls. Firewall is a passive defense protection technology, can not meet a large number of complex changes of data. Intrusion detection system (IDS), as a supplement of firewall, plays a more and more important role in the field of network security. In intrusion detection systems, the performance of detection depends on the accuracy and diversity of attack signatures, so attack signatures are the key to the implementation of intrusion detection. The application of the ideal pattern matching algorithm in network security must meet two requirements: time efficiency and spatial efficiency. Because intrusion detection systems and firewalls are usually deployed on high-speed network nodes, the time required to process each data is very small in order to meet the packet processing speed of high-speed networks. Space efficiency requires that the memory space used by the algorithm is as small as possible. At present, most pattern matching only considers regular expressions containing uncaptured groups, and does not support submatching extraction. The existing solutions for submatching extraction are based on nondeterministic Finite automaton (NFAs) or recursive backtracking. NFA has a low space complexity, and it can extract compact memory footprint submatches, but the time complexity is high. Ordered Binary Decision Diagram can efficiently compress information and deal with large-scale problems effectively. This paper deals with signature matching based on OBDD data structure and pattern matching algorithm. This paper focuses on the problem of pattern matching algorithm. The main work is as follows: using three vector Boolean variables. ) Four Boolean functions are defined for NFA Q, 危, 未 Q 0, and then OBDD is used to express and manipulate Boolean functions. The pattern matching based on uncertain finite automata is improved. NFA-OBDDs are proposed to improve the time efficiency of signature matching based on NFA. Use tags to distinguish capture groups in regular expressions and extend Thompson's NFA constructor to support regular expressions. The marked NFAs are represented by Boolean functions, and Boolean functions are operated by OBDD. Submatch-OBDDs are proposed to improve the time efficiency of submatch extraction, so as to meet the requirements of Snort intrusion detection system deployed on high-speed networks to quickly match malicious traffic. Experimental results show that the proposed NFA-OBDD is correct and efficient, which is superior to the existing methods about one to three orders of magnitude, while avoiding memory explosion and resisting attacks of known algorithm complexity. At the same time, Submatch-OBDD can improve the extraction efficiency of submatch-OBDD, and test the time efficiency and spatial efficiency of Submatch-OBDD through network traffic, synthetic traffic, and enterprise event log. When the patterns are combined, Submatch-OBDD achieves the ideal performance. In the best case, the speed of submatch-OBDD is one or two orders of magnitude faster than that of RE2 and PCRE.
【学位授予单位】：哈尔滨理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.08

【相似文献】