面向网络安全的多维正则表达式匹配算法研究

发布时间：2018-07-25 15:51

【摘要】：近年来,网络安全已发展成为民生和国本的重大威胁。随着网络带宽的线速增长和入侵模式的多样化,正则表达式匹配作为应用最为广泛的DPI算法,面临着高速低存储的性能挑战。DFA匹配效率高,然而多条正则表达式联合编译时,由于“.*”相互作用会产生状态爆炸问题。该问题一直以来都是正则表达式匹配算法的研究难点和热点。研究者提出了诸多改进算法,但仍存在以下问题:1)算法普遍缺乏数学模型的理论创新,对状态和存储空间的压缩不彻底;2)算法在压缩空间的同时,往往不能保证常数级别的匹配时间复杂度,降低了系统匹配效率,难以应用于IDS中。本文依托国家973计划项目“可重构信息通信基础网络体系研究”课题,对DFA状态爆炸问题开展理论研究,按照模型创新、算法设计和算法应用的思路,提出时空高效的正则表达式匹配模型和算法。主要研究内容如下:1)提出了基于多维立方体的状态转移模型M-D-Cube-STD。首先,由于冗余状态湮没在杂乱无章的二维STD中,因此将STD在多维空间展开,根据信息论和多维空间理论给出冗余本质的解释,并将冗余状态划分为0维冗余和1维冗余;然后,将前者按照维度压缩,后者动态构建并即时更新。理论分析和实验结果表明,针对含“.*”的一类理想规则,M-D-Cube-STD对STD指数级别的状态空间进行了对数级别的压缩,使之降低到有限自动机的理论下界O(m)。2)提出了基于M-D-Cube-STD的确定性有限自动机M-D-Cube-DFA。首先,算法考虑到低存储要求,并不静态存储所有状态信息,而是采用基本结构加辅助变量的方法来获取激活状态信息;然后,多维空间中不同边上1维状态之间的跳转不再是一跳,而是以0维状态为“中转站”,进行不同维度上的二次跳转,从而实现与DFA等价的状态转移。理论分析和实验结果表明,针对含“.*”的一类理想规则,M-D-Cube-DFA在保证线速匹配的同时,将DFA存储空间降至理论下界O(m),仅付出比DFA多3~4倍的匹配时间代价。3)提出了基于多维有限自动机MFA的正则表达式匹配算法。首先,提出有限自动机的输入驱动特性理论,进一步指出由于存在规则驱动特性,DFA改进算法难以对所有类型的规则进行彻底的冗余缩减;然后,在多维立方体算法和模型的基础上,以规则模板为设计导向,针对含“.*”的一类安全规则,修正算法和模型,不断扩展规则覆盖率,最后可适用于68.9%的含“.*”的Snort规则。理论分析和实验结果表明,对于含“.*”的一类安全规则,与其他DFA改进算法相比,在保证线性匹配的同时,MFA在存储空间、匹配时间和构造时间方面有数量级级别的提高。多维正则表达式匹配算法具有时空高效性,在软件设计中可作为匹配引擎的协处理器,在硬件设计中可封装成IP核,专门处理含“.*”的一类安全规则的联合编译,用于解决“.*”相互作用产生的DFA状态爆炸问题。
[Abstract]:In recent years, network security has become a major threat to the people's livelihood and the state. With the growth of network bandwidth and the diversification of intrusion patterns, regular expression matching, as the most widely used DPI algorithm, faces the performance challenge of high speed and low storage. Due to the interaction of ". *", the problem of state explosion will occur. This problem has always been the research difficulty and hot spot of regular expression matching algorithm. Many improved algorithms have been proposed, but the following problems still exist: 1) there is a general lack of theoretical innovation in the mathematical model. The compression of state and storage space is not complete, and the algorithm compresses the space at the same time. The complexity of matching time at constant level is often not guaranteed, which reduces the system matching efficiency and is difficult to be applied in IDS. In this paper, based on the national 973 project "Research on Reconfigurable Information and Communication basic Network system", the state explosion problem of DFA is studied theoretically, according to the ideas of model innovation, algorithm design and algorithm application. A spatiotemporal efficient regular expression matching model and algorithm are proposed. The main research contents are as follows: (1) A multi-dimensional cube based state transition model (M-D-Cube-STD) is proposed. Firstly, because the redundant state is annihilated in the chaotic two-dimensional STD, the STD is expanded in multidimensional space, and the essence of redundancy is explained according to information theory and multidimensional space theory, and the redundant state is divided into 0-dimensional redundancy and 1-dimensional redundancy. The former is then compressed according to dimension, while the latter is dynamically constructed and updated instantly. Theoretical analysis and experimental results show that M-D-Cube-STD compresses the state space of STD exponent level for a class of ideal rules with ". *" A deterministic finite automaton (M-D-Cube-DFA-based) based on M-D-Cube-STD is proposed, which is reduced to the theoretical lower bound of finite automata (O (m). 2). First, considering the low storage requirements, the algorithm does not statically store all state information, but uses the basic structure plus auxiliary variables to obtain the activation state information. The jump between 1-dimensional states on different sides in multidimensional space is no longer one-hop, but takes the 0-dimensional state as the "transfer station" and performs the secondary jump on different dimensions, so as to realize the state transition equivalent to DFA. The theoretical analysis and experimental results show that the M-D-Cube-DFA can guarantee the matching of line velocities for a class of ideal rules with ". *" The DFA storage space is reduced to the theoretical lower bound. The matching time cost of O (m), is only 3 times higher than that of DFA. (3) A regular expression matching algorithm based on multidimensional finite automata (MFA) is proposed. Firstly, the input-drive characteristic theory of finite automata is proposed, and it is further pointed out that the improved DFA algorithm is difficult to reduce all types of rules completely because of the existence of rule-driven characteristics. On the basis of multi-dimension cube algorithm and model, the rule template is taken as the design direction. For a class of security rules with ". *", the algorithm and model are modified, and the rule coverage is continuously expanded. Finally, it can be applied to 68.9% of the ".*" Snort rules. The theoretical analysis and experimental results show that for a class of security rules with ". *", compared with other improved DFA algorithms, there is an order of magnitude increase in storage space, matching time and construction time while keeping linear matching. Multi-dimensional regular expression matching algorithm has high space-time efficiency. It can be used as coprocessor of matching engine in software design, and can be encapsulated into IP core in hardware design. Used to solve the DFA state explosion problem caused by the. * interaction.
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.08

【参考文献】