Network intrusion detection signature analysis using decision graphs

• US 6,609,205 B1
• Filed: 03/18/1999
• Issued: 08/19/2003
• Est. Priority Date: 03/18/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Lathem, Gerald S., Shanklin, Steven D., Bernhard, Thomas E.
• Primary Examiner(s): HUA, LY
• Application Number:
  US09/272,927
• Time in Patent Office: 1,615 Days
• Field of Search: 713/200, 713/201, 713/202
• US Class Current: 726/22
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

A method of detecting signatures representing misuse of a local network. Known reference signatures having one or more common events are identified, and represented with a decision graph having one or more shared nodes. Each node of the decision graph represents the occurrence of an event. Given a set of input events, test functions associated with nodes determine the path taken during traversal of the graph. A path of the graph from the parent node to a leaf node represents the occurrence of all events that comprise a signature. The decision graph permits any of the signatures to be detected with only one traversal, and avoids the need for a separate matching process for each signature. In this manner, an entire set of all known reference signatures may be consolidated into a smaller set of decision graphs.

Claims

1. A method of using a signature processor to detect signatures in an incoming datastream, the signatures representing intrusion to a local network, comprising the steps of:

selecting at least two reference signatures having at least one common event;

representing each said common event as a node of a decision graph;

representing a non-common event associated with each signature as a subsequent level node of said decision graph;

defining at least one function for each said signature, for determining a transition between nodes associated with that signature;

providing events indicated by said datastream as input to said decision graph; and

traversing said decision graph so as to determine whether said events comprise a signature that matches one of said reference signatures;

wherein said events are of at least one event type.

2. The method of claim 1, wherein at least one event is of a type indicated by information within single packet of said datastream.

3. The method of claim 1, wherein at least one event is of a type indicated by information within a session of said datastream.

4. The method of claim 1, wherein at least one event is of a type indicated by information across multiple sessions said datastream.

5. The method of claim 1, wherein at least one event is of a type indicated by occurrences related to said datastream.

6. The method of claim 1, wherein said decision graph is a decision tree.

7. The method of claim 1, wherein said decision graph contains a loop, such that said subsequent level event may transition back to a common event.

8. A computer-readable memory device encoded with a data structure for representing multiple signatures associated with misuse of a network, comprising:

a decision graph, having the following elements;

at least one node representing an event common to said multiple signatures;

at least two subsequent nodes, each of which represent an event not common to said multiple signatures;

at least two leaf nodes, each of which is associated with one of said multiple signatures; and

a function associated with each node that is not a leaf node, for determining transitions between nodes;

wherein said event common to said multiple signatures and said event not common to said multiple signatures are of at least one event type.

9. The computer-readable memory device of claim 8, wherein at least one event is of a type indicated by information within single packet of said datastream.

10. The computer-readable memory device of claim 8, wherein at least one event is of a type indicated by information within a session of said datastream.

11. The computer-readable memory device of claim 8, wherein at least one event is of a type indicated by information across multiple sessions said datastream.

12. The computer-readable memory device of claim 8, wherein at least one event is of a type indicated by occurrences related to said datastream.

13. The computer-readable memory device of claim 8, wherein said decision graph is a decision tree.

14. The computer-readable memory device of claim 8, wherein said decision graph comprises a loop for transitioning a subsequent level event back to a common event.

15. A method of generating a decision graph for representing multiple signatures representing misuse of a local network, comprising the steps of:

describing a set of reference signatures with a regular expression language;

compiling the regular expressions representing the reference signatures, such that said reference signatures are parsed in terms of events; and

generating a decision graph as the output of said compiling step, said decision graph having nodes representing occurrences of events, wherein said events are of at least one event type, and said decision graph having functions determining transitions between nodes, and said decision graph having leaf nodes each of which represent the bottom of a path of said decision graph that connects nodes associated with events that comprise a signature.

16. The method of claim 15, wherein at least one event is of a type indicated by information within single packet of said datastream.

17. The method of claim 15, wherein at least one event is of a type indicated by information within a session of said datastream.

18. The method of claim 15, wherein at least one event is of a type indicated by information across multiple sessions said datastream.

19. The method of claim 15, wherein at least one event is of a type indicated by occurrences related to said datastream.

20. The method of claim 15, wherein said decision graph is a decision tree.

21. The method of claim 15, wherein said decision graph contains a loop, such that said subsequent level event may transition back to a common event.

22. The method of claim 15, wherein said step of generating a decision graph is performed by selecting at least two reference signatures having at least one common event, representing each said common event as a node of a decision graph, and representing a non-common event associated with each signature as a subsequent level node of said decision graph.

23. A method of using a signature processor to detect signatures in an incoming data stream, the signatures representing intrusion to a local network, comprising:

selecting at least two reference signatures having a common event and at least one non-common event;

representing the common event as a corresponding node of a decision graph;

representing the at least one non-common event as a subsequent level node of the decision graph;

defining a function for a path that associates the corresponding node and the subsequent level node, the function representing at least one criterion for transitioning from the corresponding node and the subsequent level node;

identifying one or more events indicated by the data stream; and

traversing the decision graph to determine that the identified one or more events form a signature that matches one of the at least two reference signatures, wherein traversing the decision graph comprises,

determining that one of the one or more events matches the corresponding node,

determining that the at least one criterion of the function for the path that associates the corresponding node and the subsequent level node is met, and

in response to the determination that the at least one criterion is met, determining that another one of the one or more events that is subsequent to the one of the one or more events matches the subsequent level node.

24. The method of claim 23, wherein the one or more events are indicated by a single packet of the data stream.

25. The method of claim 23, wherein the one or more events are indicated by information within a session of the data stream.

26. The method of claim 23, wherein the one or more events are indicated by information across multiple sessions of the data stream.

27. The method of claim 23, wherein the one or more events are indicated by one or more occurrences related to the data stream.

28. The method of claim 23, wherein the decision graph is a decision tree.

29. The method of claim 23, wherein the decision graph further comprises a loop indicating a transition from the subsequent level node back to the common node.

30. An apparatus, comprising:

a program stored on a computer readable medium and operable, when executed on a processor, to;

access a decision graph having,

a node representing a common event of at least two reference signatures,

a subsequent level node representing at least one non-common event of the at least two reference signatures,

a path associating the node and the subsequent level node, the path having a function representing at least one criterion for transitioning from the node to the subsequent level node;

identify one or more events indicated by the data stream;

determine that the identified one or more events form a signature that matches one of the at least two reference signatures by traversing the decision graph, wherein traversing the decision graph comprises,

determining that one of the one or more events matches the node,

determining that the at least one criterion of the function for the path that associates the node and the subsequent level node is met, and

in response to the determination that the at least one criterion is met, determining that another one of the one or more events that is subsequent to the one of the one or more events matches the subsequent level node.

31. The apparatus of claim 30, wherein the one or more events are indicated by a single packet of the data stream.

32. The apparatus of claim 30, wherein the one or more events are indicated by information within a session of the data stream.

33. The apparatus of claim 30, wherein the one or more events are indicated by information across multiple sessions of the data stream.

34. The apparatus of claim 30, wherein the one or more events are indicated by one or more occurrences related to the data stream.

35. The apparatus of claim 30, wherein the decision graph is a decision tree.

36. The apparatus of claim 30, wherein the decision graph further comprises a loop indicating a transition from the subsequent level node back to the node.

37. An apparatus, comprising:

means for storing a decision graph having,

a node representing a common event of at least two reference signatures,

a subsequent level node representing at least one non-common event of the at least two reference signatures,

a path associating the node and the subsequent level node, the path having a function representing at least one criterion for transitioning from the node to the subsequent level node;

means for identifying one or more events indicated by the data stream; and

means for accessing the decision graph, comparing at least a part of the identified one or more events to at least a portion of the decision graph, and determining that the identified one or more events form a signature that matches one of the at least two reference signatures by traversing the decision graph, wherein traversing the decision graph comprises,

determining that one of the one or more events matches the node,

determining that the at least one criterion of the function for the path that associates the node and the subsequent level node is met, and

in response to the determination that the at least one criterion is met, determining that another one of the one or more events that is subsequent to the one of the one or more events matches the subsequent level node.