Method and apparatus for optimizing finite automata processing
First Claim
Patent Images
1. A security appliance operatively coupled to a network, the security appliance comprising:
- at least one memory configured to store at least one finite automaton including a plurality of nodes generated from at least one regular expression pattern;
at least one processor operatively coupled to the at least one memory and configured to walk the at least one finite automaton, with segments of an input stream received via the network, to match the at least one regular expression pattern in the input stream, the walk including iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.
6 Assignments
0 Petitions
Accused Products
Abstract
A method, and corresponding apparatus and system are provided for optimizing matching at least one regular expression pattern in an input stream by walking at least one finite automaton in a speculative manner. The speculative manner may include iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.
-
Citations
37 Claims
-
1. A security appliance operatively coupled to a network, the security appliance comprising:
-
at least one memory configured to store at least one finite automaton including a plurality of nodes generated from at least one regular expression pattern; at least one processor operatively coupled to the at least one memory and configured to walk the at least one finite automaton, with segments of an input stream received via the network, to match the at least one regular expression pattern in the input stream, the walk including iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method comprising:
-
storing at least one finite automaton including a plurality of nodes generated from at least one regular expression pattern in at least one memory; and operatively coupling the at least one memory to at least one processor, the at least one processor configured to walk the at least one finite automaton, with segments of an input stream received via a hardware network interface operatively coupled to a network, to match for the at least one regular expression pattern in the input stream, the walk including iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by at least one processor, causes the at least one processor to:
walk at least one finite automaton, including a plurality of nodes generated from at least one regular expression pattern, with segments of an input stream, to match the at least one regular expression pattern in the input stream, the walk including iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.
Specification