Novel conversion algorithm used for regular expression matching

Abstract

The invention discloses a novel construction algorithm used for a regular expression matching method. The algorithm comprises the following steps that: S1: through software, generating any regular expression based on a PCRE (Perl Compatible Regular Expressions) rule set; S2: analyzing the regular expression, and converting the regular expression into a regular expression tree structure; S3: continuously converting the regular expression parse tree form into a token list form; S4: traversing the regular expression of the token list form, processing each node in the token list by the basic formation rule of the algorithm for characters, and generating a finite state machine of the regular expression; and S5: through the finite state machine of the regular expression, generating a corresponding circuit structure, and realizing a regular expression compiler. By use of the algorithm, any regular expression in the rule can be converted. In addition, compared with a traditional conversion algorithm, the generated finite state machine reduces a great quantity of intermediate node states and simplifies a circuit structure so as to finally obtain a regular expression matching circuit suitable for an FPGA (Field Programmable Gate Array), and the algorithm exhibits certain innovation.

Description

technical field [0001] The invention relates to a conversion method in the field of regular expression matching, in particular to an algorithm for constructing a finite state machine used in the process of converting a regular expression into a matching engine. Background technique [0002] With the rapid growth of Internet traffic and the proliferation of data collected and exchanged through the network, a large number of regular expression patterns are matched with high-bandwidth data, making regular expression matching a major bottleneck in applications. While the increasing network bandwidth provides convenience to people, it also greatly increases the risk of network attacks. Regular expression matching is the process of finding all substrings in a text document. We generally use a pattern to describe a regular expression. Since regular expression matching plays a vital role in intrusion detection systems (NIDSs), open source intrusion detection systems such as SNORT a...

AI Technical Summary

Problems solved by technology

While the increasing network bandwidth provides convenience to people, it also greatly increases the risk of network attacks

Images