Network security monitoring system

• US 7,483,972 B2
• Filed: 05/21/2003
• Issued: 01/27/2009
• Est. Priority Date: 01/08/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Lawrence, Jan Christian, Bhattacharya, Partha
• Primary Examiner(s): Vaugn, Jr.; William C
• Assistant Examiner(s): Mesfin; Yemane
• Application Number:
  US10/443,946
• Publication Number:
  US 20040133672A1
• Time in Patent Office: 2,078 Days
• Field of Search: 709/223, 709/224, 709/229, 726/3, 726/11, 726/22, 726/23, 726/25
• US Class Current: 709/224
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

A security monitoring system processes event messages related to computer network security in real time, evaluating inter-event constraints so as to identify combinations of events that are partial solutions to a predefined event correlation rule, and furthermore evaluating combinations of the partial solutions do determine if they together satisfy the predefined event correlation rule. A decision tree is formed based on the rule. Event messages are categorized into groups at leaf nodes of the tree in accordance with a plurality of intra-event constraints, and then the messages are correlated in accordance with a plurality of inter-event constraints at non-leaf nodes of the tree. When the inter-event constraint at a root node of the tree has been satisfied, a network attack alert is issued and protective actions may be taken.

Claims

1. A method of processing event messages, comprising:

defining a graph of nodes, including a plurality of leaf nodes, a plurality of non-leaf nodes;

receiving a stream of event messages, each event message characterized by a plurality of event parameters;

for each event message, identifying leaf nodes, if any, that correspond to the event message, and for each identified leaf node, storing in association with the identified leaf node a partial solution identifying the event message; and

at predefined times, invoking each of a plurality of non-leaf nodes, wherein invoking a non-leaf node comprises evaluating an inter-event constraint associated with the non-leaf node utilizing the partial solutions stored for one or more nodes lower in the graph, and storing in association with the non-leaf node partial solutions representing sets of event messages meeting the evaluated constraint of the non-leaf node.

2. The method of claim 1, wherein

each leaf node has an associated intra-event constraint;

when a received event message is found to satisfy the intra-event constraint of a leaf node, the parent node of the leaf-node is invoked.

3. The method of claim 1, wherein

each leaf node has an associated intra-event constraint and an associated set of predefined relevant event parameters;

when a received event message is found to satisfy the intra-event constraint of a leaf node, the event message is stored in a value set associated with the leaf node, each value set comprising one or more event messages that correspond to the same relevant event parameter values, and the parent node of the leaf-node is invoked.

4. The method of claim 3, wherein

the identifying includes

determining whether the received event message satisfies the intra-event constraint of a leaf node;

when the event message is determined to satisfy the intra-event constraint, storing an identifier of the event message in an existing value set of the leaf node when there is an existing value set having relevant event parameter values matching the relevant parameter values of the event message, and otherwise creating a new value set for the leaf node using the relevant parameter values of the event message and storing an identifier of the event message in the new value set.

5. The method of claim 3, wherein

the leaf node comprises a plurality of partial solutions and a plurality of value sets, each partial solution having a pointer to one value set.

6. The method of claim 3, wherein

a partial solution stored in a non-leaf node comprises pointers to value sets from at least one leaf node.

7. The method of claim 3, wherein

the inter-event constraint associated with the non-leaf node defines a relationship between at least two distinct leaf nodes, wherein the relationship is defined with respect to the relevant parameter values associated with the at least two leaf nodes.

8. The method of claim 3, wherein

each relevant event parameter of a leaf node appears at least once in an inter-event constraint associated with a non-leaf node that is a parent node of the leaf node.

9. The method of claim 1, wherein

a partial solution stored in a non-leaf node comprises pointers to partial solutions in at least one child node of the non-leaf node.

10. The method of claim 1, wherein

the evaluating includes

first applying a logical operation to the partial solutions stored at the child nodes of the non-leaf node;

if the logical operation returns TRUE, second applying the inter-event constraint to the partial solutions, and otherwise waiting for new event messages.

11. The method of claim 10, wherein

the logical operation is selected from the set consisting of logical AND, logical OR, and logical AND NOT.

12. The method of claim 10, wherein

the second applying includes

retrieving a first set of event parameter values from one or more leaf nodes associated with the partial solutions of a first child node;

retrieving a second set of event parameter values from one or more leaf nodes associated with the partial solutions of a second child node; and

generating a new partial solution having pointers to the partial solutions of the child nodes if the first and second sets of event parameter values satisfy the inter-event constraint associated with the non-leaf node.

13. The method of claim 1, wherein

the graph of nodes includes a root node;

if the non-leaf node is the root node of the graph, the partial solutions associated with the non-leaf node comprise complete solutions; and

for a particular complete solution, identifying event messages that satisfy the inter-event constraint of the root node.

14. The method of claim 1, wherein

the graph of nodes includes a root node;

if the non-leaf node is the root node of the graph, the partial solutions associated with the non-leaf node comprise complete solutions; and

the method includes generating an alert corresponding to at least one of the complete solutions.

15. The method of claim 1, including

storing in high speed memory partial solutions of leaf and non-leaf nodes, thereby enabling real time processing of the stream of event messages.

16. The method of claim 1, wherein

the stream of event messages include event messages generated by one or more intrusion detection sensors.

17. The method of claim 1, wherein

the plurality of event parameters include source address, source port, destination address, destination port, IP protocol, timestamp, event type, and event id.

18. The method of claim 17, wherein

the event id of each event message is unique to a device that generated the event message.

19. The method of claim 1, wherein the invoking of non-leaf nodes includes deferring invocations of at least some of the non-leaf nodes and processing the deferred invocations once per predefined evaluation period.

20. A system monitoring network security, comprising:

one or more central processing units for executing programs;

an interface for receiving event messages; and

a rule evaluation engine module executable by the one or more central processing units, the module comprising;

data representing a graph of nodes, including a plurality of leaf nodes, a plurality of non-leaf nodes;

instructions for receiving a stream of event messages, each event message characterized by a plurality of event parameters;

instructions for identifying leaf nodes, if any, that correspond to an event message in the stream of event messages;

instructions for storing in association with the identified leaf nodes a partial solution identifying the event message; and

instructions for invoking each of the plurality of non-leaf nodes at predefined times, wherein invoking a non-leaf node comprises evaluating an inter-event constraint associated with the non-leaf node utilizing the partial solutions stored for one or more nodes lower in the graph, and storing in association with the non-leaf node partial solutions representing sets of event messages meeting the evaluated constraint of the non-leaf node.

21. The system of claim 20, wherein

each leaf node has an associated intra-event constraint;

when a received event message is found to satisfy the intra-event constraint of a leaf node, the parent node of the leaf-node is invoked.

22. The system of claim 20, wherein

each leaf node has an associated intra-event constraint and an associated set of predefined relevant event parameters;

when a received event message is found to satisfy the intra-event constraint of a leaf node, the event message is stored in a value set associated with the leaf node, each value set comprising one or more event messages that correspond to the same relevant event parameter values, and the parent node of the leaf-node is invoked.

23. The system of claim 20, wherein

the identifying includes

determining whether the received event message satisfies the intra-event constraint of a leaf node;

when the event message is determined to satisfy the intra-event constraint, storing an identifier of the event message in an existing value set of the leaf node when there is an existing value set having relevant event parameter values matching the relevant parameter values of the event message, and otherwise creating a new value set for the leaf node using the relevant parameter values of the event message and storing an identifier of the event message in the new value set.

24. The system of claim 20, wherein

the leaf node comprises a plurality of partial solutions and a plurality of value sets, each partial solution having a pointer to one value set.

25. The system of claim 20, wherein

a partial solution stored in a non-leaf node comprises pointers to value sets from at least one leaf node.

26. The system of claim 20, wherein

the inter-event constraint associated with the non-leaf node defines a relationship between at least two distinct leaf nodes, wherein the relationship is defined with respect to the relevant parameter values associated with the at least two leaf nodes.

27. The system of claim 20, wherein

each relevant event parameter of a leaf node appears at least once in an inter-event constraint associated with a non-leaf node that is a parent node of the leaf node.

28. The system of claim 20, wherein

a partial solution stored in a non-leaf node comprises pointers to partial solutions in at least one child node of the non-leaf node.

29. The system of claim 20, wherein

the evaluating includes

first applying a logical operation to the partial solutions stored at the child nodes of the non-leaf node;

if the logical operation returns TRUE, second applying the inter-event constraint to the partial solutions, and otherwise waiting for new event messages.

30. The system of claim 29, wherein

the logical operation is selected from the set consisting of logical AND, logical OR, and logical AND NOT.

31. The system of claim 29, wherein

the second applying includes

retrieving a first set of event parameter values from one or more leaf nodes associated with the partial solutions of a first child node;

retrieving a second set of event parameter values from one or more leaf nodes associated with the partial solutions of a second child node; and

generating a new partial solution having pointers to the partial solutions of the child nodes if the first and second sets of event parameter values satisfy the inter-event constraint associated with the non-leaf node.

32. The system of claim 20, wherein

the graph of nodes includes a root node;

if the non-leaf node is the root node of the graph, the partial solutions associated with the non-leaf node comprise complete solutions; and

for a particular complete solution, identifying event messages that satisfy the inter-event constraint of the root node.

33. The system of claim 20, wherein

the graph of nodes includes a root node;

if the non-leaf node is the root node of the graph, the partial solutions associated with the non-leaf node comprise complete solutions; and

the method includes generating an alert corresponding to at least one of the complete solutions.

34. The system of claim 20, including

storing in high speed memory partial solutions of leaf and non-leaf nodes, thereby enabling real time processing of the stream of event messages.

35. The system of claim 20, wherein

the stream of event messages include event messages generated by one or more intrusion detection sensors.

36. The system of claim 20, wherein

the plurality of event parameters include source address, source port, destination address, destination port, IP protocol, timestamp, event type, and event id.

37. The system of claim 20, wherein

the event id of each event message is unique to a device that generated the event message.

38. The system of claim 20, wherein the instructions for invoking non-leaf nodes include instructions for deferring invocations of at least some of the non-leaf nodes and for processing the deferred invocations once per predefined evaluation period.

39. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for constructing a graph of nodes, including a plurality of leaf nodes, a plurality of non-leaf nodes;

instructions for receiving a stream of event messages, each event message characterized by a plurality of event parameters;

instructions for identifying leaf nodes, if any, that correspond to an event message in the stream of event messages;

instructions for storing in association with the identified leaf nodes a partial solution identifying the event message; and

instructions for invoking each of the plurality of non-leaf nodes at predefined times, wherein invoking a non-leaf node comprises evaluating an inter-event constraint associated with the non-leaf node utilizing the partial solutions stored for one or more nodes lower in the graph, and storing in association with the non-leaf node partial solutions representing sets of event messages meeting the evaluated constraint of the non-leaf node.

40. The computer program product of claim 39, wherein

each leaf node has an associated intra-event constraint;

when a received event message is found to satisfy the intra-event constraint of a leaf node, the parent node of the leaf-node is invoked.

41. The computer program product of claim 39, wherein

each leaf node has an associated intra-event constraint and an associated set of predefined relevant event parameters;

when a received event message is found to satisfy the intra-event constraint of a leaf node, the event message is stored in a value set associated with the leaf node, each value set comprising one or more event messages that correspond to the same relevant event parameter values, and the parent node of the leaf-node is invoked.

42. The computer program product of claim 39, wherein

the identifying includes

determining whether the received event message satisfies the intra-event constraint of a leaf node;

when the event message is determined to satisfy the intra-event constraint, storing an identifier of the event message in an existing value set of the leaf node when there is an existing value set having relevant event parameter values matching the relevant parameter values of the event message, and otherwise creating a new value set for the leaf node using the relevant parameter values of the event message and storing an identifier of the event message in the new value set.

43. The computer program product of claim 39, wherein

the leaf node comprises a plurality of partial solutions and a plurality of value sets, each partial solution having a pointer to one value set.

44. The computer program product of claim 39, wherein

a partial solution stored in a non-leaf node comprises pointers to value sets from at least one leaf node.

45. The computer program product of claim 39, wherein

the inter-event constraint associated with the non-leaf node defines a relationship between at least two distinct leaf nodes, wherein the relationship is defined with respect to the relevant parameter values associated with the at least two leaf nodes.

46. The computer program product of claim 39, wherein

each relevant event parameter of a leaf node appears at least once in an inter-event constraint associated with a non-leaf node that is a parent node of the leaf node.

47. The computer program product of claim 39, wherein

a partial solution stored in a non-leaf node comprises pointers to partial solutions in at least one child node of the non-leaf node.

48. The computer program product of claim 39, wherein

the evaluating includes

first applying a logical operation to the partial solutions stored at the child nodes of the non-leaf node;

if the logical operation returns TRUE, second applying the inter-event constraint to the partial solutions, and otherwise waiting for new event messages.

49. The computer program product of claim 48, wherein

the logical operation is selected from the set consisting of logical AND, logical OR, and logical AND NOT.

50. The computer program product of claim 48, wherein

the second applying includes

retrieving a first set of event parameter values from one or more leaf nodes associated with the partial solutions of a first child node;

retrieving a second set of event parameter values from one or more leaf nodes associated with the partial solutions of a second child node; and

generating a new partial solution having pointers to the partial solutions of the child nodes if the first and second sets of event parameter values satisfy the inter-event constraint associated with the non-leaf node.

51. The computer program product of claim 39, wherein

the graph of nodes includes a root node;

if the non-leaf node is the root node of the graph, the partial solutions associated with the non-leaf node comprise complete solutions; and

for a particular complete solution, identifying event messages that satisfy the inter-event constraint of the root node.

52. The computer program product of claim 39, wherein

the graph of nodes includes a root node;

if the non-leaf node is the root node of the graph, the partial solutions associated with the non-leaf node comprise complete solutions; and

the method includes generating an alert corresponding to at least one of the complete solutions.

53. The computer program product of claim 39, including

storing in high speed memory partial solutions of leaf and non-leaf nodes, thereby enabling real time processing of the stream of event messages.

54. The computer program product of claim 39, wherein

the stream of event messages include event messages generated by one or more intrusion detection sensors.

55. The computer program product of claim 39, wherein

the plurality of event parameters include source address, source port, destination address, destination port, IP protocol, timestamp, event type, and event id.

56. The computer program product of claim 39, wherein

the event id of each event message is unique to a device that generated the event message.

57. The computer program product of claim 39, wherein the instructions for invoking non-leaf nodes include instructions for deferring invocations of at least some of the non-leaf nodes and for processing the deferred invocations once per predefined evaluation period.