Deterministic finite-state machine construction method based on classification counter

Abstract

The invention disclosesa deterministic finite-state machine construction method based on a classification counter, and belongs to the field of Internet intrusion inspection. The deterministic finite-state machine construction method comprises the following steps: firstly, classifying all regular expressions in a regular expression set (rule set) into a linear-level complexity class, a multiplication-level complexity class, a square-level complexity class and an exponential-level complexity class according to DFA (Deterministic Finite Automaton) construction complexity; then, generating a specific DFA with the counter for the regular expressions of each class of complexity; and finally, combining states which contain the same output excitation, and are not internal start states and internal end states in the DFA to generate a final ODFA (Overlaid Deterministic Finite Automaton). The reception message inspection speed of an intrusion inspection system can be quickened, accuracy is improved, a false alarm rate is lowered, and the consumption of memory resources by the system can be reduced. The construction method has a great practical application value.

Description

technical field [0001] The invention relates to the field of Internet intrusion detection, in particular to the construction and compression of a definite finite state machine corresponding to a regular expression in an intrusion detection system. Background technique [0002] Intrusion detection technology is a new security defense measure. As a supplementary strategy of the firewall, it can be used to identify illegal attacks on computer systems and network systems or information systems in a wider sense, including detection of external illegal intruders. Malicious attack or temptation. Deep Packet Inspection (DPIDeepPacketInspection) is an important method based on the rule-matching network intrusion detection system. It is a new technology compared with ordinary packet analysis. Ordinary packet inspection only analyzes the contents below the fourth layer of IP packets. Including source address, destination address, source port, destination port and protocol type, deep p...

AI Technical Summary

Problems solved by technology

But XFA can only count single characters, and can't do anything for repeated strings

The D2FA algorithm proposed by Kumar can compress the number of transfers, but its disadvantage is that the matching efficiency is low. For each character incentive, it may take multiple jumps along the default state to reach the target state.

Images