Character string matching method based on automatic control (AC) automatic machine and suffix tree

Abstract

The invention discloses a character string matching method based on an automatic control (AC) automatic machine and a suffix tree, which comprises the following steps of: S1, compiling a characteristic character string into an AC automatic machine; S2, gathering suffixes of the characteristic character string and compiling into a suffix tree; S3, as long as a data packet enters into network security equipment, matching the data packet depending on the AC automatic machine, and conserving a matching state through the suffix tree; and S4, if the matching is successful, discarding the data packet. According to the character string matching method disclosed by the invention, the state numbers of the AC automatic machine and the suffix tree are conserved while matching the character string of the data packet, so that the data packet can be matched in a manner of continuing the last state even though disorder occurs, to avoid cache of the previous data packet; the shortcomings of increment of delay, deterioration of memory consumption and local reduction of a high-speed cache memory due to the cache are overcome, resource required by the network security equipment is reduced and performance of the network security equipment is improved.

Description

technical field [0001] The invention relates to the technical field of network filtering and monitoring, in particular to a string matching method based on AC automaton and suffix tree. Background technique [0002] With the continuous improvement of network security requirements, functions such as intrusion detection, anti-virus, and content filtering are increasingly applied to network security devices. The string matching algorithm is the core algorithm supporting these functions, and also determines the performance of network security devices. At present, the string matching algorithm most widely used in network security equipment is the Aho-Corasick (AC) automaton algorithm. The AC algorithm is a string matching algorithm based on the principle of automata, such as figure 1 As shown, its basic working principle is as follows: First, compile the signature string (such as virus signature database, filter keywords, etc.) For example, in a), check whether the current stat...

AI Technical Summary

Problems solved by technology

[0004] However, caching data packets and recombining data packets have the following disadvantages: first, caching data packets will increase the network delay; Exhaustion; again, in a web security appliance with a cache memory, reading and writing packet data in large numbers in memory can also reduce the locality of the cache memory, thereby reducing the performance of the web security appliance

Images