Graph structures for event matching

• US 9,413,598 B2
• Filed: 09/02/2009
• Issued: 08/09/2016
• Est. Priority Date: 09/02/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Stakhanova, Natalia, Ghorbani, Ali-akbar, Bird, William
• Primary Examiner(s): HO, DAO Q
• Application Number:
  US12/553,040
• Publication Number:
  US 20110055924A1
• Time in Patent Office: 2,533 Days
• Field of Search: 726/23
• US Class Current: 1/1
• 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, the system comprising:

a computer-readable data structure comprising a plurality of system event rules organized as a graph having a plurality of nodes, at least one node corresponding to a field in a rule and having a weight value;

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

for a node in the graph, comparing the field corresponding to the node to each field in the event;

in the event of a match between the compared fields, adding the field to a list of matches; and

sorting the list of matching fields according to the weight associated with each matching field.

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:

receiving an incoming event comprising at least one field;

traversing a computer readable-data structure comprising a plurality of system event rules organized as a graph having a plurality of nodes, at least one node corresponding to a field in a rule and having a weight value;

for a node in the graph, comparing the field corresponding to the node to each field in the event;

in the event of a match between the compared fields, adding the field to a list of matches;

sorting the list of matching fields according to the weight associated with each matching field; and

processing, using a computer, at least one rule associated with the plurality of nodes.

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

8. The method of claim 7, wherein the set of fields associated with the plurality of nodes comprises at least two fields, and wherein the processing the at least one rule associated with the plurality of nodes 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, 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.

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

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

creating a parent node of the first node; and

associating a field in the new rule with the parent node.

11. The method of claim 10, 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.

12. 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 one of the shared fields.

13. The method of claim 12, 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.