Compilation of finite automata based on memory hierarchy
First Claim
Patent Images
1. A security appliance operatively coupled to a network, the security appliance comprising:
- at least one processor;
at least one network interface configured to receive an input stream including a payload, the security appliance configured to identify an existence of at least one regular expression pattern in the payload of the input stream prior to forwarding the payload;
a plurality of memories mapped to hierarchical levels in a memory hierarchy and operatively coupled to the at least one processor and the at least one network interface, the at least one processor configured to;
generate at least one per-pattern non-deterministic finite automaton (NFA), each per-pattern NFA generated for a single regular expression pattern, of the at least one regular expression pattern, and including a respective set of nodes; and
improve performance of the security appliance by optimizing match performance for identifying the existence of the at least one regular expression pattern, the match performance optimized by distributing nodes, of the respective set of nodes of each per-pattern NFA generated, in the plurality of memories based on the hierarchical levels mapped and per-pattern NFA storage allocation settings configured for the hierarchical levels.
6 Assignments
0 Petitions
Accused Products
Abstract
At least one per-pattern non-deterministic finite automaton (NFA) may be generated for a single regular expression pattern and may include a respective set of nodes. Nodes of the respective set of nodes of each per-pattern NFA generated may be distributed for storing in a plurality of memories based on hierarchical levels mapped to the plurality of memories and per-pattern NFA storage allocation settings configured for the hierarchical levels, optimizing run time performance for matching regular expression patterns in an input stream.
142 Citations
37 Claims
-
1. A security appliance operatively coupled to a network, the security appliance comprising:
-
at least one processor; at least one network interface configured to receive an input stream including a payload, the security appliance configured to identify an existence of at least one regular expression pattern in the payload of the input stream prior to forwarding the payload; a plurality of memories mapped to hierarchical levels in a memory hierarchy and operatively coupled to the at least one processor and the at least one network interface, the at least one processor configured to; generate at least one per-pattern non-deterministic finite automaton (NFA), each per-pattern NFA generated for a single regular expression pattern, of the at least one regular expression pattern, and including a respective set of nodes; and improve performance of the security appliance by optimizing match performance for identifying the existence of the at least one regular expression pattern, the match performance optimized by distributing nodes, of the respective set of nodes of each per-pattern NFA generated, in the plurality of memories based on the hierarchical levels mapped and per-pattern NFA storage allocation settings configured for the hierarchical levels. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method comprising:
in at least one processor operatively coupled to at least one network interface and a plurality of memories mapped to hierarchical levels in a memory hierarchy in a security appliance operatively coupled to a network, the at least one network interface configured to receive an input stream including a payload, the security appliance configured to identify an existence of at least one regular expression pattern in the payload of the input stream prior to forwarding the payload; generating at least one per-pattern non-deterministic finite automaton (NFA), each per-pattern NFA generated for a single regular expression pattern, of the at least one regular expression pattern, and including a respective set of nodes; and improve performance of the security appliance by optimizing match performance for identifying the existence of the at least one regular expression pattern, the match performance optimized by distributing nodes of the respective set of nodes of each per-pattern NFA in the plurality of memories based on the hierarchical levels mapped and per-pattern NFA storage allocation settings configured for the hierarchical levels. - 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 stored thereon a sequence of instructions which, when loaded and executed by a processor operatively coupled to a plurality of memories and at least one network interface in a security appliance, causes the processor to:
-
generate at least one per-pattern non-deterministic finite automaton (NFA), each per-pattern NFA generated for a single regular expression pattern, of the at least one regular expression pattern, and including a respective set of nodes, the processor operatively coupled to a plurality of memories mapped to hierarchical levels, the at least one network interface configured to receive an input stream including a payload, the security appliance configured to identify an existence of at least one regular expression pattern in the payload of the input stream prior to forwarding the payload; and improve performance of the security appliance by optimizing match performance for identifying the existence of the at least one regular expression pattern, the match performance optimized by distributing nodes of the respective set of nodes of each per-pattern NFA in the plurality of memories based on the hierarchical levels mapped and per-pattern NFA storage allocation settings configured for the hierarchical levels.
-
Specification