Multi-character-string mode matching method, device, computer equipment and storage medium

Abstract

The invention provides a multi-character-string mode matching method, a device, computer equipment and a storage medium. The method comprises the steps of obtaining a character string matching rule set; extracting a character pattern string set and a logic relation thereof; constructing an unconditional transfer table and a failure transfer table according to the character pattern string set based on an automaton algorithm; encoding the state of the transfer table, and distributing a ternary code and a precise code for each state of the transfer table; constructing a non-deterministic finite state automaton matching table according to the transfer table; constructing a strategy matching table according to the character pattern string set and the logic relationship; matching the character string according to the matching table, and outputting a matching result; the complete semantic meaning of the non-deterministic finite state automaton in an automaton algorithm is realized, the number of table items is ensured to be equal to the number of state transition table items of the unconditional transition table, the storage space is greatly saved, the limitation of a programmable switch calculation model and storage resources is overcome, and the number of characters processed by matching each time is increased to increase throughput.

Description

technical field [0001] The invention relates to the technical field of computer matching algorithms, in particular to a multi-character string pattern matching method, device, computer equipment and storage medium. Background technique [0002] String matching algorithm is an algorithm widely used in network security applications. It can be formalized as, given an alphabet Σ, an input string T = t 1 t 2 ...t n And a set of pattern strings P={P i}, where P i =p 1 ,p 2 …p m , and any t i ,p i ∈Σ. The multi-string pattern matching algorithm should output the pattern string P i The set of all positions in T that are substrings. [0003] The Aho-Corasick (automaton) algorithm, referred to as the AC algorithm, is an effective method for multi-string pattern matching. It constructs a nondeterministic finite automaton (NFA, Nondeterministic Finite Automata) by constructing a goto (unconditional transfer) state transition table through a dictionary tree (trie) composed o...

AI Technical Summary

Problems solved by technology

However, these hardware replacement products often have high cost, and the throughput is difficult to exceed 40Gbps

In addition, hardware replacements are often connected to the server via PCI-E, which makes it difficult to exploit its full potential due to the limited bandwidth of PCI-E

[0007] All in all, neither algorithm-optimized solutions nor hardware-accelerated solutions can provide the ideal throughput or capital cost to keep up with the dramatic increase in network traffic and network bandwidth

Images