Processing of finite automata based on memory hierarchy

• US 10,110,558 B2
• Filed: 04/14/2014
• Issued: 10/23/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,299
• Publication Number:
  US 20150293846A1
• Time in Patent Office: 1,653 Days
• Field of Search: 726 11
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

At least one processor may be operatively coupled to a plurality of memories and a node cache and configured to walk nodes of a per-pattern non-deterministic finite automaton (NFA). Nodes of the per-pattern NFA may be stored amongst one or more of the 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, optimizing run time performance of the walk.

Claims

1. A security appliance operatively coupled to a network, the security appliance comprising:

at least one network interface configured to receive an input stream including a payload, the security appliance configured to identify an existence of a respective regular expression pattern in the payload of the input stream prior to forwarding the payload;

a plurality of memories configured to store nodes of at least one finite automaton, the at least one finite automaton including a given per-pattern non-deterministic finite automaton (NFA) of at least one per-pattern NFA, the given per-pattern NFA generated for the respective regular expression pattern and including a respective set of nodes; and

at least one processor operatively coupled to the plurality of memories and the at least one network interface and configured to walk nodes of the respective set of nodes with segments of the payload to match the respective regular expression pattern in the input stream, performance of the security appliance improved by optimizing match performance of the at least one processor for identifying the existence of the respective regular expression pattern, the match performance optimized by having distributed and stored the respective set of nodes amongst one or more memories of the 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.

2. The security appliance of claim 1, wherein the respective set of nodes of the given per-pattern NFA are statically stored amongst the one or more memories of the plurality of memories based on the node distribution.

3. The security appliance of claim 1, wherein to walk nodes of the respective set of nodes with segments of the payload of the input stream, the at least one processor is further configured to walk from a given node to a next node of the respective set of nodes based on (i) a positive match of a given segment of the payload at the given node and (ii) a next node address associated with the given node, the next node address configured to identify the next node and a given memory of the plurality of memories in which the next node is stored.

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 each at least one per-pattern NFA, 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 the given per-pattern NFA.

6. The security appliance of claim 4, wherein the respective regular expression pattern is a given pattern in a set of regular expression patterns and 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 of the at least one per-pattern NFA in an event a per-pattern NFA is generated for each regular expression pattern in the 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 of each of the at least one per-pattern NFA, 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 of each at least one per-pattern NFA, 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 and 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 the node distribution determined is based on:

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 12, wherein a number of nodes in the first distribution is maximized 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 12, wherein a number of nodes in each at least one second distribution is maximized 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 node distribution determined is determined by the at least one processor during a compilation stage of the given per-pattern NFA.

16. The security appliance of claim 1, wherein the walk progresses based on individual nodes of the respective set of nodes matching segments of the payload and the at least one processor is further configured to determine the per-pattern NFA storage allocation settings during a compilation stage of the at least one per-pattern NFA 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 walk nodes of a unified deterministic finite automaton (DFA), stored in a given memory of the plurality of memories and generated based on at least one subpattern selected from each pattern in a set of regular expression patterns, with segments from the input stream, wherein the walk of the respective set of nodes of the given per-pattern NFA is based on a partial match of the respective regular expression pattern in the input stream determined via the DFA node walk.

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. The security appliance of claim 1, wherein the security appliance further comprises a node cache configured to store at least a threshold number of nodes and the at least one processor is further operatively coupled to the node cache.

20. The security appliance of claim 19, wherein the at least one processor is further configured to cache one or more nodes, of the respective set of nodes, in the node cache based on a cache miss during the walk of a given node of the one or more nodes read from a given memory of the plurality of memories and a respective hierarchical node transaction size associated with a respective hierarchical level of the hierarchical levels that is mapped to the given memory.

21. The security appliance of claim 20, wherein the hierarchical node transaction size associated with the respective hierarchical level denotes a maximum number of nodes to fetch from the given memory mapped to the respective hierarchical level for a read access of the given memory.

22. The security appliance of claim 20, wherein a highest ranked hierarchical level of the hierarchical levels is associated with a smallest hierarchical node transaction size of hierarchical node transaction sizes associated with the hierarchical levels.

23. The security appliance of claim 20, wherein the respective hierarchical node transaction size enables the at least one processor to cache the threshold number of nodes from the given memory if the respective hierarchical level is a lowest ranked hierarchical level of the hierarchical levels.

24. The security appliance of claim 20, wherein the at least one processor is further configured to evict the threshold number of nodes cached in the node cache if the respective hierarchical level is a lowest ranked hierarchical level of the hierarchical levels.

25. The security appliance of claim 20, wherein to cache the one or more nodes the at least one processor is further configured to employ a least recently used (LRU) or round-robin replacement policy to evict one or more cached nodes from the node cache, if the respective hierarchical level is higher than a lowest ranked hierarchical level of the hierarchical levels, a number of the one or more cache nodes evicted determined based on the hierarchical level.

26. 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 a respective regular expression pattern in the payload of the input stream prior to forwarding the payload;

walking nodes of a respective set of nodes of a given per-pattern non-deterministic finite automaton (NFA) of at least one per-pattern NFA generated for the respective regular expression pattern with segments of the payload to match the respective regular expression pattern in the input stream, performance of the security appliance improved by optimizing match performance of the at least one processor for identifying the existence of the respective regular expression pattern, the match performance optimized by having distributed and stored the respective set of nodes amongst one or more memories of the 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.

27. The method of claim 26, wherein the respective set of nodes of the given per-pattern NFA are statically stored amongst the one or more memories of the plurality of memories based on the node distribution.

28. The method of claim 26, walking nodes of the respective set of nodes with segments of the payload of the input stream includes walking from a given node to a next node of the respective set of nodes based on (i) a positive match of a given segment of the payload at the given node and (ii) a next node address associated with the given node, the next node address configured to identify the next node and a given memory of the plurality of memories in which the next node is stored.

29. The method of claim 26, 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 each at least one per-pattern NFA, to distribute for storing in a given memory, of the plurality of memories, that is mapped to the respective hierarchical level.

30. The method of claim 29, wherein the unique nodes of the respective set of nodes are arranged in a consecutive manner within the given per-pattern NFA.

31. The method of claim 29, wherein the respective regular expression pattern is a given pattern in a set of regular expression patterns and 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 of the at least one per-pattern NFA in an event a per-pattern NFA is generated for each regular expression pattern in the set of regular expression patterns.

32. The method of claim 29, wherein the target number of unique nodes is denoted via an absolute value and is a common value for each respective set of nodes of each at least one per-pattern NFA, 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.

33. The method of claim 29, 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 of each at least one per-pattern NFA, 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.

34. The method of claim 26, 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.

35. The method of claim 26, 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 and the second per-pattern NFA storage allocation setting is configured for the next highest ranked hierarchical level.

36. The method of claim 26, wherein the node distribution determined is based on:

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.

37. The method of claim 36, 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.

38. The method of claim 37, wherein a number of nodes in the first distribution is maximized 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.

39. The method of claim 37, wherein a number of nodes in each at least one second distribution is maximized 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.

40. The method of claim 26, wherein the node distribution determined is determined by the at least one processor during a compilation stage of the given per-pattern NFA.

41. The method of claim 26, wherein walking further includes progressing the walk based on individual nodes of the respective set of nodes matching segments of the payload and the at least one processor is further configured to determine the per-pattern NFA storage allocation settings during a compilation stage of the at least one per-pattern NFA 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.

42. The method of claim 26, further comprising walking nodes of a unified deterministic finite automaton (DFA), stored in a given memory of the plurality of memories and generated based on at least one subpattern selected from each pattern in a set of regular expression patterns, with segments from the input stream, and walking the respective set of nodes of the given per-pattern NFA is based on a partial match of the respective regular expression pattern in the input stream determined via the DFA node walking.

43. The method of claim 26, wherein the plurality of memories includes 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.

44. The method of claim 26, further including configuring a node cache in the security appliance to store at least a threshold number of nodes of the at least one finite automaton and operatively coupling the at least one processor to the node cache.

45. The method of claim 44, further including caching one or more nodes, of the respective set of nodes, based on a cache miss of a given node of the one or more nodes read from a given memory of the plurality of memories and a respective hierarchical node transaction size associated with a respective hierarchical level of the hierarchical levels that is mapped to the given memory.

46. The method of claim 45, wherein the hierarchical node transaction size associated with the respective hierarchical level denotes a maximum number of nodes to fetch from the given memory mapped to the respective hierarchical level for a read access of the given memory.

47. The method of claim 45, wherein a highest ranked hierarchical level of the hierarchical levels is associated with a smallest hierarchical node transaction size of hierarchical node transaction sizes associated with the hierarchical levels.

48. The method of claim 45, wherein the respective hierarchical node transaction size enables the at least one processor to cache the threshold number of nodes from the given memory if the respective hierarchical level is a lowest ranked hierarchical level of the hierarchical levels.

49. The method of claim 45, wherein caching the one or more nodes includes evicting the threshold number of nodes cached in the node cache if the respective hierarchical level is a lowest ranked hierarchical level of the hierarchical levels.

50. The method of claim 45, wherein caching the one or more nodes includes employing a least recently used (LRU) or round-robin replacement policy to evict one or more cached nodes from the node cache, if the respective hierarchical level is higher than a lowest ranked hierarchical level of the hierarchical levels, a number of the one or more cache nodes evicted determined based on the hierarchical level.

51. 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:

walk nodes of a respective set of nodes of at least one per-pattern non-deterministic finite automaton (NFA) generated for a single regular expression pattern with segments of a payload to match a respective regular expression pattern in an input stream, the at least one network interface configured to receive the input stream including the payload, the security appliance configured to identify an existence of the respective regular expression pattern in the payload of the input stream prior to forwarding the payload, performance of the security appliance improved by optimizing match performance of the processor for identifying the existence of the respective regular expression pattern, the match performance optimized by having distributed and stored the respective set of nodes stored amongst one or more memories of the 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.