Reverse NFA generation and processing
First Claim
1. A method comprising:
- in a processor of a security appliance coupled to a network;
walking an input of a sequence of characters through a deterministic finite automata (DFA) graph generated for at least one given regular expression pattern to enable inspection of packet content, the at least one given regular expression employed to detect a security breach or an intrusion; and
at a marked node of the DFA graph, the marked node being a node that marks a match of the at least one given regular expression pattern;
based on a specific type of the at least one given regular expression pattern matching at the marked node, walking the input sequence of characters through a reverse non-deterministic finite automata (rNFA) graph by walking the input sequence of characters backwards through the rNFA graph beginning from an offset of the input sequence of characters associated with the marked node, the rNFA graph generated for the at least one given regular expression pattern and having at least one processing node inserted therein, the at least one processing node inserted into the rNFA graph based on the specific type of the at least one regular expression pattern; and
based on the specific type of the at least one given regular expression pattern not matching at the marked node, reporting the match of the at least one given regular expression pattern.
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
34 Claims
-
1. A method comprising:
-
in a processor of a security appliance coupled to a network; walking an input of a sequence of characters through a deterministic finite automata (DFA) graph generated for at least one given regular expression pattern to enable inspection of packet content, the at least one given regular expression employed to detect a security breach or an intrusion; and at a marked node of the DFA graph, the marked node being a node that marks a match of the at least one given regular expression pattern; based on a specific type of the at least one given regular expression pattern matching at the marked node, walking the input sequence of characters through a reverse non-deterministic finite automata (rNFA) graph by walking the input sequence of characters backwards through the rNFA graph beginning from an offset of the input sequence of characters associated with the marked node, the rNFA graph generated for the at least one given regular expression pattern and having at least one processing node inserted therein, the at least one processing node inserted into the rNFA graph based on the specific type of the at least one regular expression pattern; and based on the specific type of the at least one given regular expression pattern not matching at the marked node, reporting the match of the at least one given regular expression pattern. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A security appliance coupled to a network, the security appliance comprising:
a processor implemented in hardware configured to; walk an input of a sequence of characters through a deterministic finite automata (DFA) graph generated for at least one given regular expression pattern to enable inspection of packet content, the at least one given regular expression employed to detect a security breach or an intrusion; and at a marked node of the DFA graph; based on a specific type of the at least one given regular expression pattern matching at the marked node, walk the input sequence of characters through a reverse non-deterministic finite automata (rNFA) graph by walking the input sequence of characters backwards through the rNFA graph beginning from an offset of the input sequence of characters associated with the marked node, the rNFA graph generated for the at least one given regular expression pattern and having at least one processing node inserted therein, the at least one processing node inserted into the rNFA graph based on the specific type of the at least one regular expression pattern; and based on the specific type of the at least one given regular expression pattern not matching at the marked node, reporting the match of the at least one given regular expression pattern. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
Specification