Reverse NFA Generation And Processing
First Claim
1. A method comprising:
- in a processor;
generating a reverse non-deterministic finite automata (rNFA) graph for a given type of a given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters to determine a match for the given regular expression pattern 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 given type of the 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
22 Claims
-
1. A method comprising:
-
in a processor; generating a reverse non-deterministic finite automata (rNFA) graph for a given type of a given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters to determine a match for the given regular expression pattern 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 given type of the given regular expression pattern. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. An apparatus comprising:
-
a processor implemented in hardware, the processor configured to implement a compiler configured to; generate a reverse non-deterministic finite automata (rNFA) graph for a given type of a given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters to determine a match for the given regular expression pattern 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 given type of the given regular expression pattern. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
Specification