Reverse NFA generation and processing
First Claim
1. A method comprising:
- in an apparatus including a multi-layer protocol processor configured to inspect content of data received from a network;
improving inspection performance of the processor by (a) determining whether or not a given regular expression pattern requires a match of at least one back-reference and (b) in response to determining that the given regular expression pattern requires the match and prior to inspecting the content received from the network, generating a reverse non-deterministic finite automata (rNFA) graph for the given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters for inspecting the content to enable recognition of the given regular expression pattern in the sequence of characters, the rNFA graph having at least one processing node inserted into the rNFA graph based on the at least one back reference, the apparatus forwarding the content of the data to the network based on the inspecting.
6 Assignments
0 Petitions
Accused Products
Abstract
In a processor of a security appliance, an input of a sequence of characters is walked through a finite automata graph generated for at least one given pattern. At a marked node of the finite automata graph, if a specific type of the at least one given pattern is matched at the marked node, the input sequence of characters is processed through a reverse non-deterministic finite automata (rNFA) graph generated for the specific type of the at least one given pattern by walking the input sequence of characters backwards through the rNFA beginning from an offset of the input sequence of characters associated with the marked node. Generating the rNFA for a given pattern includes inserting processing nodes for processing an input sequence of patterns to determine a match for the given pattern. In addition, the rNFA is generated from the given type of pattern.
-
Citations
12 Claims
-
1. A method comprising:
-
in an apparatus including a multi-layer protocol processor configured to inspect content of data received from a network; improving inspection performance of the processor by (a) determining whether or not a given regular expression pattern requires a match of at least one back-reference and (b) in response to determining that the given regular expression pattern requires the match and prior to inspecting the content received from the network, generating a reverse non-deterministic finite automata (rNFA) graph for the given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters for inspecting the content to enable recognition of the given regular expression pattern in the sequence of characters, the rNFA graph having at least one processing node inserted into the rNFA graph based on the at least one back reference, the apparatus forwarding the content of the data to the network based on the inspecting. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An apparatus, the apparatus comprising:
-
a multi-layer protocol processor implemented in hardware, the processor configured to inspect content of data received from a network and to implement a compiler configured to; improve inspection performance of the processor by (a) determining whether or not a given regular expression pattern requires a match of at least one back-reference and (b) in response to determining that the given regular expression pattern requires the match and prior to inspecting the content received from the network, generating a reverse non-deterministic finite automata (rNFA) graph for the given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters for inspecting the content to enable recognition of the given regular expression pattern in the sequence of characters, the rNFA graph having at least one processing node inserted into the rNFA graph based on the at least one back reference, the apparatus configured to forward the content of the data to the network based on the inspecting. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification