GRAPH STRUCTURES FOR EVENT MATCHING

• US 20110055924A1
• Filed: 09/02/2009
• Published: 03/03/2011
• Est. Priority Date: 09/02/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Q1 Labs, Inc. (International Business Machines Corporation)
• Inventors: Bird, William, STAKHANOVA, Natalia, Ghorbani, Ali-akbar
• Granted Patent: US 9,413,598 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

A system for matching a system event to a rule is disclosed. The system includes a computer-readable data structure comprising a plurality of system event rules organizable as a partially ordered set. The system also includes a processor configured to analyze the computer-readable data structure to determine whether an event matches a description set of at least one rule from the plurality of system event rules. Methods and machine-readable mediums are also disclosed.

Claims

1. A system for matching a system event to a rule comprising:

a computer-readable data structure comprising a plurality of system event rules organizable as a partially ordered set;

a processor configured to analyze the computer-readable data structure to determine whether an event matches a description set of at least one rule from the plurality of system event rules.

2. The system of claim 1, wherein each rule is associated with a description set, and wherein a description set comprises at least one field and at least one response action.

3. The system of claim 1, wherein the system event rules are intrusion detection rules, and wherein the event is an indication of an incoming event on an electronic network.

4. The system of claim 1, wherein the processor is further configured to generate a match set based on the system event, and wherein determining whether an event matches a description set of at least one rule from the plurality of system event rules comprises identifying whether the at least one rule is associated with a set of fields that is a subset of, or equal to, a set of fields associated with the match set.

5. The system of claim 4, wherein the set of fields associated with the match set comprises at least one field, and a value associated with the field, from the system event.

6. A method for matching a system event to a rule comprising:

generating a match set based an incoming system event;

identifying at least one node, in a rule relations graph, associated with a set of fields that is a subset of, or equal to, the set of fields associated with the match set; and

processing, using a computer, at least one rule associated with the at least one node.

7. The method of claim 6, wherein the processing the at least one rule associated with the at least one node is based on a weight associated with at least one field from the set of fields associated with the at least one node.

8. The method of claim 7, wherein the set of fields associated with the at least one node comprises at least two fields, and wherein the processing the at least one rule associated with the at least one node based on the weight comprises processing a first field of the at least two fields if the first field has a smaller associated weight than a weight associated with a second field of the at least two fields.

9. The method of claim 6, further comprising ordering the match set by weight.

10. The method of claim 6, wherein the set of fields associated with the match set comprises at least one field, and a value associated with the field, from the incoming system event.

11. The method of claim 6, wherein a new rule is associated with the rule relations graph according to steps comprising:

identifying a first node, in the rule relations graph, associated with a set of fields that is a superset of the set of fields associated with the new rule;

creating a parent node of the first node; and

associating the new rule with the parent node.

12. The method of claim 11, wherein the first node is identified by traversing nodes associated with a set of fields that is a subset of, or equal to, the set of fields associated with the new rule.

13. The method of claim 6, wherein a new rule is associated with the rule relations graph according to steps comprising:

identifying a first node, in the rule relations graph, associated with a set of fields that are shared with the set of fields associated with the new rule;

creating an intermediate node associated with the shared fields.

14. The method of claim 13, wherein the first node is identified by traversing nodes associated with a set of fields that is a subset of, or equal to, the set of fields associated with the new rule.

15. A system for matching a system event to a rule comprising:

a computer-readable data structure comprising a plurality of intrusion detection rules organizable as a partially ordered set;

a processor configured to generate a match set based on the system event, the processor further configured to identify whether at least one rule, from a plurality of intrusion detection rules, is associated with a set of fields that is a subset of, or equal to, a set of fields associated with the match set, and whether the values associated with the set of fields associated with the at least one rule match the values associated with the set of fields associated with the match set,

wherein the processor is further configured to initiate at least one response action associated with the at least one rule if the set of fields associated with the at least one rule is a subset of, or equal to, a set of fields associated with the match set, and if the values associated with the set of fields associated with the at least one rule match the value associated with the set of fields associated with the match set.

16. A machine-readable medium encoded with instructions for matching a system event to a rule, the instructions comprising code for:

generating a match set based an incoming system event;

identifying at least one node, in a rule relations graph, associated with a set of fields that is a subset of or equal to, the set of fields associated with the match set; and

processing at least one rule associated with the at least one node.