Anchored patterns

• US 8,990,259 B2
• Filed: 06/24/2011
• Issued: 03/24/2015
• Est. Priority Date: 06/24/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Billa, Satyanarayana Lakshmipathi, Goyal, Rajan
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US13/168,323
• Publication Number:
  US 20120331007A1
• Time in Patent Office: 1,369 Days
• Field of Search: 707/794, 707/797
• US Class Current: 707/797
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method and apparatus relate to recognizing anchored patterns from an input stream. Patterns from a plurality of given patterns are marked as anchored patterns. An anchored state tree for the anchored patterns of the plurality of given patterns is built, including nodes representing a state of the anchored state tree. For each node of the anchored state tree, a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns is determined.

Claims

1. A method comprising:

in a processor of a security appliance coupled to a network;

marking given patterns from a plurality of given patterns as anchored patterns;

building an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

building a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determining a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns; and

including a failure value of a root node of the anchored state tree, the failure value being equivalent to a root node of the unanchored state tree.

2. The method of claim 1 wherein the anchored state tree includes a root node that is set as a start node for processing anchored and unanchored patterns in an input payload.

4. The method of claim 1 wherein marking includes adding a reference indicating a location within an input of a string of text to begin searching for the anchored pattern.

3. A method comprising:

in a processor of a security appliance coupled to a network;

marking given patterns from a plurality of given patterns as anchored patterns;

building an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

building a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determining a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

wherein each node of the anchored state tree includes an output function, the output function of each node is calculated as a function of both the anchored patterns and unanchored patterns.

5. A method comprising:

in a processor of a security appliance coupled to a network;

marking given patterns from a plurality of given patterns as anchored patterns;

building an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

building a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determining a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

wherein building the anchored state tree and building the separate unanchored state tree includes determining a number of states and transitions from one state to another.

6. A method comprising:

in a processor of a security appliance coupled to a network;

marking given patterns from a plurality of given patterns as anchored patterns;

building an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

building a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determining a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

upon receiving an input string of text, processing the input string of text through the anchored state tree; and

transitioning processing of the input string of text to a node of the unanchored state tree if a character of the input string of text results in one of the determined failure values on one of the nodes of the anchored state tree, the resulting failure value determining the node of the unanchored state tree to transition processing.

7. A method comprising:

in a processor of a security appliance coupled to a network;

marking given patterns from a plurality of given patterns as anchored patterns;

building an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

building a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determining a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

wherein the failure value being equivalent to the root node of the unanchored state tree enables tracking of the unanchored patterns of the plurality of given patterns if none of the anchored patterns of the plurality of given patterns are matched.

8. A security appliance coupled to a network, the security appliance comprising a processor configured to implement a compiler, the compiler configured to:

mark given patterns from a plurality of given patterns as anchored patterns;

build an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

build a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determine a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns; and

determine a failure value of a root node of the anchored state tree, the failure value being equivalent to a root node of the unanchored state tree.

9. The security appliance of claim 8 wherein the anchored state tree includes a root node that is set as a start node for processing anchored and unanchored patterns in an input payload.

11. The security appliance of claim 8 wherein the compiler is further configured to mark given patterns by adding a reference indicating a location within an input of a string of text to begin searching for the anchored pattern.

10. A security appliance coupled to a network, the security appliance comprising a processor configured to implement a compiler, the compiler configured to:

mark given patterns from a plurality of given patterns as anchored patterns;

build an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

build a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determine a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

wherein each node of the anchored state tree includes an output function, the output function of each node is calculated as a function of both the anchored patterns and unanchored patterns.

12. A security appliance coupled to a network, the security appliance comprising a processor configured to implement a compiler, the compiler configured to:

mark given patterns from a plurality of given patterns as anchored patterns;

build an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

build a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determine a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

wherein the compiler is further configured to build the anchored state tree and the separate unanchored state tree by determining a number of states and transitions from one state to another.

13. A security appliance coupled to a network, the security appliance comprising a processor configured to implement a compiler, the compiler configured to:

mark given patterns from a plurality of given patterns as anchored patterns;

build an unanchored state tree for unanchored patterns of the plurality of given patterns, the unanchored state tree including nodes representing a state of the unanchored state tree;

build a separate anchored state tree for the anchored patterns of the plurality of given patterns, the anchored state tree including nodes representing a state of the anchored state tree;

for each node of the anchored state tree, determine a failure value equivalent to a node representing a state in an unanchored state tree representing unanchored patterns of the plurality of given patterns;

wherein the compiler is further configured to;

upon receiving an input string of text, process the input string of text through the anchored state tree; and

transition processing of the input string of text to a node of the unanchored state tree if a character of the input string of text results in one of the determined failure values of one of the nodes of the anchored state tree, the resulting failure value determining the node of the unanchored state tree to transition processing.