Pattern discovery in a network system

• US 7,984,502 B2
• Filed: 10/01/2008
• Issued: 07/19/2011
• Est. Priority Date: 05/04/2004
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Saurabh, Kumar, Tidwell, Kenny C.
• Primary Examiner(s): Chai; Longbit
• Application Number:
  US12/243,838
• Publication Number:
  US 20090064333A1
• Time in Patent Office: 1,021 Days
• Field of Search: 726/23
• US Class Current: 726/23
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Patterns can be discovered in events collected by a network system. In one embodiment, the present invention includes collecting and storing events from a variety of monitor devices. In one embodiment, a subset of the stored events is provided to a manager as an event stream. In one embodiment, the present invention further includes the manager discovering one or more previously unknown event patterns in the event stream.

Claims

1. A method for discovering an event pattern in an event stream, the event stream comprising a plurality of events, the method comprising:

using a processor to create a plurality of transactions based on a transaction parameter, wherein each transaction represents a subset of the plurality of events;

generating a transaction tree based on the plurality of transactions, wherein the transaction tree includes one root node and a plurality of non-root nodes, and

wherein each non-root node represents an event;

traversing a branch of the transaction tree starting at the root node, wherein the branch extends from the root node through a first non-root node to a second non-root node;

observing a drop in support from the first non-root node to the second non-root node, wherein a support of a non-root node represents a number of transactions that include the event represented by the non-root node; and

determining that the event pattern includes the event represented by the first non-root node and does not include the event represented by the second non-root node.

2. The method of claim 1, wherein the plurality of events had been stored in an event database.

3. The method of claim 1, wherein the transaction parameter comprises an interval of time, and wherein each transaction represents events that were received during the interval of time.

4. The method of claim 1, wherein the transaction parameter comprises a value of an event field, and wherein each transaction represents events that include the value of the event field.

5. The method of claim 4, wherein the event field comprises a source address.

6. The method of claim 4, wherein the event field comprises a destination address.

7. The method of claim 1, wherein the transaction parameter comprises a point in time, and wherein each transaction represents events that were received proximate to the point in time.

8. The method of claim 1, wherein generating the transaction tree based on the plurality of transactions comprises generating the transaction tree based on a support of an event within the plurality of transactions.

9. The method of claim 1, further comprising removing a field from each event in the plurality of events.

10. The method of claim 9, wherein a value of the field is unique to each event.

11. The method of claim 1, further comprising providing a user an option to convert the event pattern into an event correlation rule.

12. The method of claim 1, further comprising creating an event correlation rule using the event pattern.

13. A method for generating a rule, comprising:

displaying a pattern discovery tool configured to enable a user to select a subset of previously stored events;

in response to the user selection;

using a processor to create a plurality of transactions based on a transaction parameter, wherein each transaction represents a subset of the selected events;

generating a transaction tree based on the plurality of transactions, wherein the transaction tree includes one root node and a plurality of non-root nodes, and wherein each non-root node represents an event;

traversing a branch of the transaction tree starting at the root node, wherein the branch extends from the root node through a first non-root node to a second non-root node;

observing a drop in support from the first non-root node to the second non-root node, wherein a support of a non-root node represents a number of transactions that include the event represented by the non-root node; and

determining that the event pattern includes the event represented by the first non-root node and does not include the event represented by the second non-root node;

displaying a rule generation tool configured to enable a user to perform an action; and

in response to the user action, converting the event pattern into a correlation rule.

14. The method of claim 13, wherein the user action comprises a single mouse-click.

15. A system for discovering an event pattern in an event stream, the event stream comprising a plurality of events, the system comprising

creating a plurality of transactions based on a transaction parameter, wherein each transaction represents a subset of the plurality of events;

generating a transaction tree based on the plurality of transactions, wherein the transaction tree includes one root node and a plurality of non-root nodes, and wherein each non-root node represents an event;

traversing a branch of the transaction tree starting at the root node, wherein the branch extends from the root node through a first non-root node to a second non-root node;

observing a drop in support from the first non-root node to the second non-root node, wherein a support of a non-root node represents a number of transactions that include the event represented by the non-root node; and

determining that the event pattern includes the event represented by the first non-root node and does not include the event represented by the second non-root node.

16. The system of claim 15, wherein the transaction parameter comprises an interval of time, and wherein each transaction represents events that were received during the interval of time.

17. The system of claim 15, wherein the transaction parameter comprises a value of an event field, and wherein each transaction represents events that include the value of the event field.

18. The system of claim 15, wherein the transaction parameter comprises a point in time, and wherein each transaction represents events that were received proximate to the point in time.

19. The system of claim 15, wherein generating the transaction tree based on the plurality of transactions comprises generating the transaction tree based on a support of an event within the plurality of transactions.

20. The system of claim 15, wherein the method further comprises removing a field from each event in the plurality of events.

21. The system of claim 15, wherein the method further comprises displaying a user interface to provide a user a tool to convert the event pattern into an event correlation rule.

22. A non-transitory machine-readable storage medium having stored thereon data representing instructions that, when executed by a processor, cause the processor to perform operations comprising:

creating a plurality of transactions based on a transaction parameter, wherein each transaction represents a subset of a plurality of events;

generating a transaction tree based on the plurality of transactions, wherein the transaction tree includes one root node and a plurality of non-root nodes, and wherein each non-root node represents an event;

traversing a branch of the transaction tree starting at the root node, wherein the branch extends from the root node through a first non-root node to a second non-root node;

observing a drop in support from the first non-root node to the second non-root node, wherein a support of a non-root node represents a number of transactions that include the event represented by the non-root node; and

determining that the event pattern includes the event represented by the first non-root node and does not include the event represented by the second non-root node.

23. The non-transitory machine-readable storage medium of claim 22, wherein generating the transaction tree based on the plurality of transactions comprises generating the transaction tree based on a support of an event within the plurality of transactions.

24. The non-transitory machine-readable storage medium of claim 22, wherein the operations further comprise removing a field from each event in the plurality of events.

25. The non-transitory machine-readable storage medium of claim 22, wherein the operations further comprise providing a user an option to convert the event pattern into an event correlation rule.

26. The non-transitory machine-readable storage medium of claim 22, wherein the operations further comprise creating an event correlation rule using the event pattern.