Processing of finite automata based on a node cache
First Claim
Patent Images
1. A method comprising:
- in at least one processor operatively coupled to at least one network interface, a plurality of memories in a memory hierarchy, and a node cache, in a security appliance operatively coupled to a network;
storing a plurality of nodes of at least one finite automaton in the plurality of memories for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; and
caching a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the at least one processor for identifying the existence of the least one regular expression pattern in the input stream.
6 Assignments
0 Petitions
Accused Products
Abstract
Nodes of a per-pattern NFA may be stored amongst one or more of a plurality of memories based on a node distribution determined as a function of hierarchical levels mapped to the plurality of memories and per-pattern NFA storage allocation settings configured for the hierarchical levels. At least one processor may be configured to cache one or more nodes of the per-pattern NFA in the node cache based on a cache miss of a given node of the one or more nodes and a hierarchical node transaction size associated with a given hierarchical level mapped to a given memory in which the given node is stored, optimizing run time performance of the walk.
-
Citations
19 Claims
-
1. A method comprising:
in at least one processor operatively coupled to at least one network interface, a plurality of memories in a memory hierarchy, and a node cache, in a security appliance operatively coupled to a network; storing a plurality of nodes of at least one finite automaton in the plurality of memories for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; and caching a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the at least one processor for identifying the existence of the least one regular expression pattern in the input stream. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
10. A security appliance operatively coupled to a network, the security appliance comprising:
-
at least one network interface; a plurality of memories in a memory hierarchy configured to store a plurality of nodes of at least one finite automaton for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; a node cache configured to store at least a threshold number of nodes of the at least one finite automaton; and at least one processor operatively coupled to the at least one network interface, the plurality of memories, and the node cache, and configured to cache a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the at least one processor for identifying the existence of the at least one regular expression pattern in the input stream. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, the processor operatively coupled to at least one network interface, a plurality of memories in a memory hierarchy, and a node cache, causes the processor to:
-
store a plurality of nodes of at least one finite automaton in the plurality of memories for identifying existence of at least one regular expression pattern in an input stream received via the at least one network interface; and cache a given node and one or more additional nodes, of the plurality of nodes, stored in a given memory of the plurality of memories at a hierarchical level in the memory hierarchy, in the node cache based on a cache miss of the given node, the one or more additional nodes cached based on a hierarchical node transaction size associated with the hierarchical level, optimizing match performance of the processor for identifying the existence of the at least one regular expression pattern in the input stream.
-
Specification