Finite automaton generating method of regular expression with wildcards

Abstract

The invention relates to a finite automaton generating method of a regular expression with wildcards. The finite automaton generating method is characterized in that the finite automaton generating method is realized in the following steps of S1 generating an abstract syntax tree according to the regular expression with the wildcards, and numbering each node of the abstract syntax tree; S2 calculating nullable (n) of each node and a three-position set of each node according to the abstract syntax tree; S3 using firstpos (n0) of a root node of the abstract syntax tree as a first state to be stored into a state set; traversing the state set, if a new state is generated in a traversing process, the new state is added in the state set, and a conversion relation is recorded; when each state is traversed, a following state of each character in the state is calculated and stored in the state set according to conditions. By using the finite automaton generating method of the regular expression with the wildcards, the compiling efficiency is effectively improved, and the memory consumption is reduced.

Description

technical field [0001] The invention relates to the technical field of network intrusion detection, in particular to a method for generating finite automata with wildcard regular expressions. Background technique [0002] Now that network intrusions are becoming more and more complex, the vulnerabilities in the network application layer have become the key attack targets of hackers. When using the vulnerabilities in the network application layer to attack, the attacker's data is hidden in the normal data channel. The state detection method allows normal channels to pass through, and it is difficult to detect such application layer attacks. Therefore, for application layer attack detection, it is generally necessary to check the data content in the network path to see if it has attack characteristics. Due to the high flexibility of regular expressions, in content-based detection methods, most attack rules are expressed by regular expressions. [0003] Wildcards are a very wi...

AI Technical Summary

Problems solved by technology

Among them, NFA is called a non-deterministic finite state automaton, and DFA is called a deterministic finite automaton. NFA uses a backtracking mechanism, so it can support more wildcards, etc., but due to the backtracking mechanism, the efficiency is not high.

DFA adopts the state transfer method, which is very efficient and very suitable for intrusion detection methods with high performance requirements. However, DFA also has a defect that it cannot support wildcards well.

When DFA compiles regular expressions containing wildcards, the compilation time is very long, a large number of states will be generated, the host memory will be exhausted, and a large amount of compilation time will be consumed

Images