Back to results
US 9,426,166 B2Granted
Method and apparatus for processing finite automata
AssigneeCavium, Inc.
InventorsSatyanarayana Lakshmipathi Billa, Rajan Goyal
Life of this patent
Estimating the term…
Abstract
A method and corresponding apparatus for run time processing use a Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) to find the existence of a pattern in a payload. A subpattern may be selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic. The DFA may be generated from selected subpatterns from all patterns in the set, and at least one NFA may be generated for at least one pattern in the set, optimizing run time performance of the run time processing.
Claims67
A security appliance operatively coupled to a network, the security appliance comprising:
- at least one memory;
- at least one processor operatively coupled to the at least one memory, the at least one processor configured to:
- walk characters of a payload in an input stream through a unified deterministic finite automata (DFA) stored in the at least one memory, by traversing nodes of the unified DFA with characters from the payload, the unified DFA generated from subpatterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic;
- and
- walk characters of the payload through at least one non-deterministic finite automata (NFA) stored in the at least one memory, by traversing nodes of the at least one NFA with characters from the payload, the at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used for generating the at least one NFA, and at least one walk direction for walking characters through the at least one NFA, being based on whether a length of a subpattern selected from the at least one pattern is fixed or variable and a location of the subpattern selected within the at least one pattern to optimize performance of run time processing of the at least one processor for identifying an existence of the at least one pattern in the input stream.
2 more elements
A method comprising:
- in at least one processor operatively coupled to at least one memory in a security appliance operatively coupled to a network:
- walking characters of a payload in an input stream through a unified deterministic finite automata (DFA) stored in the at least one memory, by traversing nodes of the unified DFA with characters from the payload, the unified DFA generated from subpatterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic;
- and
- walking characters of the payload through at least one non-deterministic finite automata (NFA) stored in the at least one memory, by traversing nodes of the at least one NFA with characters from the payload, the at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used for generating the at least one NFA, and at least one walk direction for walking characters through the at least one NFA, being based on whether a length of a subpattern selected from the at least one pattern is fixed or variable and a location of the subpattern selected within the at least one pattern to optimize performance of run time processing of the at least one processor for identifying an existence of the at least one pattern in the input stream.
1 more element
A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:
- walk characters of a payload in an input stream through a unified deterministic finite automata (DFA) stored in the at least one memory, by traversing nodes of the unified DFA with characters from the payload, the unified DFA generated from subpatterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic;
- and
- walk characters of the payload through at least one non-deterministic finite automata (NFA) stored in the at least one memory, by traversing nodes of the at least one NFA with characters from the payload, the at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used for generating the at least one NFA, and at least one walk direction for walking characters through the at least one NFA, being based on whether a length of a subpattern selected from the at least one pattern is fixed or variable and a location of the subpattern selected within the at least one pattern to optimize performance of run time processing of the processor for identifying an existence of the at least one pattern in the input stream.
Dependencies are inferred from the claim text.