Method and apparatus for compilation of finite automata

摘要

A method and corresponding apparatus are provided implementing run time processing using 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 and a unified deterministic finite automata (DFA) may be generated using the subpatterns selected from all patterns in the set, and at least one non-deterministic finite automata (NFA) may be generated for at least one pattern in the set, optimizing run time performance of the run time processing.

主权项

1. A security appliance operatively coupled to a network, the security appliance comprising:
at least one memory and at least one network interface; at least one processor operatively coupled to the at least one memory and the at least one network interface, the at least one processor configured to:
select a subpattern from each pattern in a set of one or more regular expression patterns based on at least one heuristic;generate a unified deterministic finite automata (DFA) using the subpatterns selected from all patterns in the set;generate at least one non-deterministic finite automata (NFA) 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 selected from a reverse and forward walk direction for run time processing of the at least one NFA, being determined based on whether a length of the 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; andstore the unified DFA and the at least one NFA generated in the at least one memory for run time processing by the at least one processor with a payload received via the at least one network interface, to determine pattern matches in the payload prior to forwarding the payload, the subpatterns selected based on the at least one heuristic to minimize a number of false positives identified in the at least one NFA to reduce the run time processing of the at least one processor.