High speed mode matching algorithm based on field programmable gate array

Abstract

The invention relates to a method for matching a high-speed mode based on a field programmable gate array. The method generates a DFA state table by dynamically expanding a jump function goto in an AC algorithm, compresses the DFA state table and realizes content detection and application identification in the hardware mode, so as to meet the demands of processing of a network application layer and network information security of users. The invention relates to rule description based on a regular expression, a pattern matching engine of the state machine technology, and compression and optimization of a rule base. DFA pattern matching is a algorithm for converting time complexity into space complexity, wherein a plurality of rules can be matched in parallel; the length of the rules is not limited; and matched feature values can be subjected to non-positioning pattern matching or positioning pattern matching. The DFA algorithm skillfully converts the processing procedure of multi-pattern matching into the processing procedure of state transition, so as to realize the O(n)-level matching speed. Therefore, the compression algorithm of the rule base not only can guarantee the search speed but also can realize high-efficiency compression.

Description

technical field [0001] The invention relates to a matching algorithm of a computer, in particular to a high-speed pattern matching algorithm of a coprocessor which realizes content detection function based on computer hardware technology. The invention belongs to the technical field of computer network security (network security). Background technique [0002] The security threats faced by the network can be roughly divided into two types: one is the threat to network data; the other is the threat to network equipment. These threats may originate from a variety of factors. Among them, malicious attacks and intrusions from external and internal personnel are the biggest threat to the current Internet network, and it is also the most important problem to be solved by network security strategies. In order to meet the network information security requirements and prevent illegal users from taking advantage of the security flaws of the network system to steal, forge and destroy...

AI Technical Summary

Problems solved by technology

However, with the continuous increase of pattern matching rules, such as adding more content filtering rules, virus identification features, etc., the pattern matching speed based on software technology will decrease accordingly, and the pattern database will become increasingly large (space complexity is 0(2 n ), n is the length of the pattern string)

Images