Compilation of finite automata based on memory hierarchy

• US 10,002,326 B2
• Filed: 04/14/2014
• Issued: 06/19/2018
• Est. Priority Date: 04/14/2014
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi
• Primary Examiner(s): Rashid, Harunur
• Application Number:
  US14/252,293
• Publication Number:
  US 20150295889A1
• Time in Patent Office: 1,527 Days
• Field of Search: 726 11
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models
• CPC Class Codes: G06N 5/047 Pattern matching networks; Rete networks
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

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.

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.

2. The security appliance of claim 1, wherein the at least one processor is further configured to statically store the nodes, of the respective set of nodes of each per-pattern NFA generated, in the plurality of memories, based on the distribution.

3. The security appliance of claim 1, wherein to generate the at least one per-pattern NFA includes specifying a transition from a given node to a next node via a next node address associated with the given node and the next node address is configured to identify the next node and a given memory of the plurality of memories to which the next node is distributed for storing.

4. The security appliance of claim 1, wherein each per-pattern NFA storage allocation setting, of the per-pattern NFA storage allocation settings, is configured for a respective hierarchical level, of the hierarchical levels, to denote a target number of unique nodes, of the respective set of nodes of each per-pattern NFA generated, to distribute for storing in a given memory, of the plurality of memories, that is mapped to the respective hierarchical level.

5. The security appliance of claim 4, wherein the unique nodes of the respective set of nodes are arranged in a consecutive manner within a given per-pattern NFA of the at least one per-pattern NFA including the respective set of nodes.

6. The security appliance of claim 4, wherein each per-pattern NFA storage allocation setting is configured for the respective hierarchical level in a manner enabling the given memory to provide a sufficient storage capacity for storing the target number of unique nodes denoted from each per-pattern NFA generated in an event a per-pattern NFA is generated for each regular expression pattern in a set of regular expression patterns.

7. The security appliance of claim 4, wherein the target number of unique nodes is denoted via an absolute value and is a common value for each respective set of nodes enabling each respective set of nodes to have a same value for the target number of unique nodes for storing in the given memory that is mapped to the respective hierarchical level.

8. The security appliance of claim 4, wherein the target number of unique nodes is denoted via a percentage value for applying to a respective total number of nodes of each respective set of nodes enabling each respective set of nodes to have a separate value for the target number of unique nodes for storing in the given memory that is mapped to the respective hierarchical level.

9. The security appliance of claim 1, wherein each memory of the plurality of memories is mapped to a respective hierarchical level, of the hierarchical levels, consecutively, in descending order, based on a performance ranking of the plurality of memories and a highest performance ranked memory of the plurality of memories is mapped to a highest ranked hierarchical level of the hierarchical levels.

10. The security appliance of claim 1, wherein the per-pattern NFA storage allocation settings include a first per-pattern NFA storage allocation setting and a second per-pattern NFA storage allocation setting, the hierarchical levels include a highest ranked hierarchical level and a next highest ranked hierarchical level, the first per-pattern NFA storage allocation setting is configured for the highest ranked hierarchical level, the second per-pattern NFA storage allocation setting is configured for the next highest ranked hierarchical level.

11. The security appliance of claim 1, wherein to distribute the nodes of the respective set of nodes of each per-pattern NFA generated includes distributing the nodes of the respective set of nodes in a consecutive manner including:

a first distribution, of the nodes of the respective set of nodes, for storing in a first memory of the plurality of memories, the first memory mapped to a highest ranked hierarchical level of the hierarchical levels; and

at least one second distribution, of the nodes of the respective set of nodes, based on at least one undistributed node remaining in the respective set of nodes after a previous distribution, each at least one second distribution for storing in a given memory of the plurality of memories, the given memory mapped to a given hierarchical level of the hierarchical levels, consecutively lower, per distribution of the nodes of the respective set of nodes, than the highest ranked hierarchical level.

12. The security appliance of claim 11, wherein a given distribution of the at least one second distribution includes all undistributed nodes remaining in the respective set of nodes if the given hierarchical level is a lowest ranked hierarchical level of the hierarchical levels.

13. The security appliance of claim 11, wherein the at least one processor is further configured to maximize a number of nodes in the first distribution and the number maximized is limited by a respective per-pattern NFA storage allocation setting, of the per-pattern NFA storage allocation settings, configured for the highest ranked hierarchical level.

14. The security appliance of claim 11, wherein the at least one processor is further configured to maximize a number of nodes in each at least one second distribution and the number maximized is limited, per distribution, by a respective per-pattern NFA storage allocation setting, of the per-pattern NFA storage allocation settings, configured for the given hierarchical level.

15. The security appliance of claim 1, wherein the nodes of the respective set of nodes of each per-pattern NFA are statically stored to enable the at least one processor to walk the nodes of each respective set of nodes, with segments of payloads in an input stream received from the network, to determine a match at least one regular expression pattern in the input stream.

16. The security appliance of claim 15, wherein the walk progresses based on individual nodes of the respective set of nodes matching segments of the payloads and the at least one processor is further configured to determine the per-pattern NFA storage allocation settings based on a total number of regular expression patterns in a set of regular expression patterns and a desired performance metric associated with the walk.

17. The security appliance of claim 1, wherein the at least one processor is further configured to:

generate a unified deterministic finite automaton (DFA) based on at least one subpattern selected from each pattern in a set of regular expression patterns; and

store the unified DFA in a given memory of the plurality of memories.

18. The security appliance of claim 1, wherein the plurality of memories include a first memory, a second memory, and a third memory, and the first and second memories are co-located on a chip with the at least one processor and the third memory is an external memory located off the chip and mapped to a lowest ranked hierarchical level of the hierarchical levels.

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.

20. The method of claim 19, further including statically storing the nodes, of the respective set of nodes of each per-pattern NFA generated, in the plurality of memories, based on the distribution.

21. The method of claim 19, wherein generating the at least one per-pattern NFA includes specifying a transition from a given node to a next node via a next node address associated with the given node and configuring the next node address to identify the next node and a given memory of the plurality of memories to which the next node is distributed for storing.

22. The method of claim 19, further including configuring each per-pattern NFA storage allocation setting, of the per-pattern NFA storage allocation settings, for a respective hierarchical level, of the hierarchical levels, to denote a target number of unique nodes, of the respective set of nodes of each per-pattern NFA generated, to distribute for storing in a given memory, of the plurality of memories, that is mapped to the respective hierarchical level.

23. The method of claim 22, wherein the unique nodes of the respective set of nodes are arranged in a consecutive manner within a given per-pattern NFA of the at least one per-pattern NFA including the respective set of nodes.

24. The method of claim 22, further including configuring each per-pattern NFA storage allocation setting for the respective hierarchical level in a manner enabling the given memory to provide a sufficient storage capacity for storing the target number of unique nodes denoted from each per-pattern NFA generated in an event a per-pattern NFA is generated for each regular expression pattern in a set of regular expression patterns.

25. The method of claim 22, further including denoting the target number of unique nodes via an absolute value and is a common value for each respective set of nodes enabling each respective set of nodes to have a same value for the target number of unique nodes for storing in the given memory that is mapped to the respective hierarchical level.

26. The method of claim 22, further including denoting the target number of unique nodes via a percentage value for applying to a respective total number of nodes of each respective set of nodes enabling each respective set of nodes to have a separate value for the target number of unique nodes for storing in the given memory that is mapped to the respective hierarchical level.

27. The method of claim 19, wherein each memory of the plurality of memories is mapped to a respective hierarchical level, of the hierarchical levels, consecutively, in descending order, based on a performance ranking of the plurality of memories and a highest performance ranked memory of the plurality of memories is mapped to a highest ranked hierarchical level of the hierarchical levels.

28. The method of claim 19, wherein the per-pattern NFA storage allocation settings include a first per-pattern NFA storage allocation setting and second per-pattern NFA storage allocation setting, the hierarchical levels include a highest ranked hierarchical level and a next highest ranked hierarchical level, the first per-pattern NFA storage allocation setting is configured for the highest ranked hierarchical level, the second per-pattern NFA storage allocation setting is configured for the next highest ranked hierarchical level.

29. The method of claim 19, wherein distributing the nodes of the respective set of nodes of each per-pattern NFA generated includes distributing the nodes of the respective set of nodes in a consecutive manner including:

a first distribution, of the nodes of the respective set of nodes, for storing in a first memory of the plurality of memories, the first memory mapped to a highest ranked hierarchical level of the hierarchical levels; and

at least one second distribution, of the nodes of the respective set of nodes, based on at least one undistributed node remaining in the respective set of nodes after a previous distribution, each at least one second distribution for storing in a given memory of the plurality of memories, the given memory mapped to a given hierarchical level of the hierarchical levels, consecutively lower, per distribution of the nodes of the respective set of nodes, than the highest ranked hierarchical level.

30. The method of claim 29, wherein a given distribution of the at least one second distribution includes all undistributed nodes remaining in the respective set of nodes if the given hierarchical level is a lowest ranked hierarchical level of the hierarchical levels.

31. The method of claim 29, further including maximizing a number of nodes in the first distribution and the number maximized is limited by a respective per-pattern NFA storage allocation setting, of the per-pattern NFA storage allocation settings, configured for the highest ranked hierarchical level.

32. The method of claim 29, further including maximizing a number of nodes in each at least one second distribution and the number maximized is limited, per distribution, by a respective per-pattern NFA storage allocation setting, of the per-pattern NFA storage allocation settings, configured for the given hierarchical level.

33. The method of claim 19, further including statically storing the nodes of the respective set of nodes of each per-pattern NFA enabling a walk of the nodes of each respective set of nodes, with segments of payloads in an input stream received from the network, to determine a match at least one regular expression pattern in the input stream.

34. The method of claim 33, wherein the walk progresses based on individual nodes of the respective set of nodes matching segments of the payloads and the method further includes determining the per-pattern NFA storage allocation settings based on a total number of regular expression patterns in a set of regular expression patterns and a desired performance metric associated with the walk.

35. The method of claim 19, further including:

generating a unified deterministic finite automaton (DFA) based on at least one subpattern selected from each pattern in a set of regular expression patterns; and

storing the unified DFA in a given memory of the plurality of memories.

36. The method of claim 19, wherein the plurality of memories include a first memory, a second memory, and a third memory, and the first and second memories are co-located on a chip with the at least one processor and the third memory is an external memory located off the chip and mapped to a lowest ranked hierarchical level of the hierarchical levels.

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.