Self learning event parser

• US 20070169038A1
• Filed: 12/05/2006
• Published: 07/19/2007
• Est. Priority Date: 12/08/2005
• Status: Active Grant

• Current Assignee: Trustwave Holdings Incorporated (Singapore Telecommunications Limited)
• Original Assignee: Intellitactics, Inc. (Ontario) (Singapore Telecommunications Limited)
• Inventors: Shankar, Sanjeev, Thiessen, Chris, Gordon, Chris, Corke, Michael, Selkirk, Andrew, Lefort, Alan
• Granted Patent: US 7,577,633 B2
• Time in Patent Office: Days
• US Class Current: 717/143
• CPC Class Codes: G06F 8/427 Parsing

Abstract

An adaptive parser capable of automatically reordering expressions such that more commonly matched expressions are tested earlier than less commonly matched expressions; by reordering the expressions in this manner, less frequently matched expressions are less frequently tested, or may not be tested at all, thereby lowering the overall number of tests and increasing the amount of data that can be parsed in a given time period.

Claims

1. A method of parsing data, the method comprising:

receiving the data at a parsing unit, wherein the data comprises a plurality of expressions;

comparing at least one of the expressions in the data to at least one of a plurality of known expressions stored in an ordered list, wherein the at least one expression is compared to a first known expression in the ordered list and, if the at least one expression does not match the first known expression, the at least one expression is compared to subsequent known expressions in an order in which they are stored in the ordered list until the at least one expression is matched to a known expression, or until it is determined that the at least one expression does not match any of the known expressions; and

automatically reordering the known expressions of the ordered list based at least in part on matches between the expressions and the known expressions.

2. The method of claim 1, wherein the comparing is performed by a computer processor.

3. The method of claim 1, wherein the ordered list is stored in a memory.

4. The method of claim 1, wherein the ordered list is a database.

5. The method of claim 1, wherein the plurality of expressions are associated with network events.

6. The method of claim 1, wherein the known expressions are reordered based on an amount of times each known expression is matched.

7. The method of claim 1, wherein the known expressions are reordered based on an amount of times each known expression is matched during a predetermined period of time.

8. The method of claim 1, wherein the data is logged data.

9. The method of claim 1, wherein the data is a data stream.

10. The method of claim 1, wherein the known expressions are reordered each time an expression is matched.

11. The method of claim 10, wherein the known expressions are reordered each time an expression is matched such that the matched known expression becomes the first known expression.

12. The method of claim 1, wherein the ordered list is only reordered when the parser is in a learning mode.

13. The method of claim 12, wherein the parser is put in the learning mode based on a level of parsing activity.

14. The method of claim 1, wherein the known expressions are reordered after a predetermined number of expressions are matched.

15. The method of claim 1, wherein the known expressions are reordered when a rate of dataflow drops below a predetermine threshold.

16. The method of claim 1, wherein the known expressions are reordered when a rate of dataflow exceeds a predetermine threshold.

17. The method of claim 1, wherein the ordered list comprises a plurality of reorder groups, each reorder group comprising at least one known expression, wherein the known expressions are reordered within each of the reorder groups and the reorder groups remain in a fixed order.

18. The method of claim 1, wherein the ordered list comprises a plurality of reorder groups, each reorder group comprising at least one known expression, wherein the reorder groups are reordered and the known expressions remain in a fixed order within each of the reorder groups.

19. The method of claim 1, wherein at least one of the known expressions is prevented from being reordered.

54. The method of claim 1, wherein the known expressions are reordered after a predetermined number of default matches have occurred.

20. A machine readable storage having stored thereon a computer program for a parser, the computer program comprising a routine set of instructions which when executed by the machine can cause the machine to:

receive data at a parsing unit, wherein the data stream comprises a plurality of expressions;

compare at least one of the expressions in the data to at least one of a plurality of known expressions stored in an ordered list, wherein the at least one expression is compared to a first known expression in the ordered list and, if the at least one expression does not match the first known expression, the at least one expression is compared to subsequent known expressions in the order in which they are stored in the ordered list until the at least one expression is matched to a known expression, or until it is determined that the at least one expression does not match any of the known expressions; and

automatically reorder the known expressions of the ordered list based at least in part on matches between the expressions and the known expressions.

21. The method of claim 20, wherein a computer processor is used to compare the expression to at least one of the plurality of known expressions stored in the ordered list.

22. The method of claim 20, wherein the data is logged data.

23. The method of claim 20, wherein the data is a data stream.

24. A computer system to monitor data for network events, the system comprising:

a receiving unit to receive data comprising a plurality of expressions from at least one networked source; and

a parsing unit to parse the data, the parsing unit comprising,

an ordered list comprising a plurality of known expressions,

a comparison unit to compare the expressions in the data with the known expressions to identify occurrences where the expressions match the known expressions, such that at least one of the expressions is compared to a first known expressions and, if the expression does not match the first known expression, the expression is then to be compared to subsequent known expressions in an order according to the ordered list, until it is determined that the expression matches one of the known expressions, or until it is determined that the expression does not match any of the known expressions, and

a reordering unit to automatically reorder the known expressions in the ordered list according to matches between the expressions and the known expressions.

25. The method of claim 24, wherein the ordered list is to be stored in a memory.

26. The method of claim 24, wherein the known expressions are to be reordered based on an amount of times each known expression is matched.

27. The method of claim 24, wherein the known expressions are to be reordered based on an amount of times each known expression is matched during a predetermined period of time.

28. The method of claim 24, wherein the data is logged data.

29. The method of claim 24, wherein the data is a data stream.

30. The method of claim 24, wherein the known expressions are to be reordered each time an expression is matched.

31. The method of claim 30, wherein the known expressions are to be reordered each time an expression is matched such that the matched known expression becomes the first known expression.

32. The method of claim 24, wherein the ordered list is only to be reordered when the parser is in a learning mode.

33. The method of claim 32, wherein the parser is to be put in the learning mode based on a level of parsing activity.

34. The method of claim 24, wherein the known expressions are to be reordered after a predetermined number of expressions are matched.

35. The method of claim 24, wherein the known expressions are to be reordered when a rate of dataflow drops below a predetermine threshold.

36. The method of claim 24, wherein the ordered list comprises a plurality of reorder groups, each reorder group comprising at least one known expression, wherein the known expressions are to be reordered within each of the reorder groups and the reorder groups are to remain in a fixed order.

37. The method of claim 24, wherein the ordered list comprises a plurality of reorder groups, each reorder group comprising at least one known expression, wherein the reorder groups are to be reordered and the known expressions are to remain in a fixed order within each of the reorder groups.

38. The method of claim 24, wherein at least one of the known expressions is to be prevented from being reordered.

39. The method of claim 24, wherein the networked source is a networked device.

40. A grammar based event parser, wherein the grammar is automatically reordered based at least in part on matches between known expressions and expressions input into the event parser.

41. The event parser of claim 40, wherein the grammar is reordered based on an amount of times each known expression is matched.

42. The event parser of claim 40, wherein the grammar is reordered based on an amount of times each known expression is matched during a predetermined period of time.

43. The event parser of claim 40, wherein the grammar is reordered each time an expression is matched.

44. The event parser of claim 40, wherein the grammar is only reordered when the event parser is in a learning mode.

45. The event parser of claim 44, wherein the event parser is put in the learning mode based on a level of parsing activity.

46. The event parser of claim 40, wherein the grammar is reordered after a predetermined number of expressions are matched.

47. The event parser of claim 40, wherein the grammar is reordered when a rate of dataflow drops below a predetermine threshold.

48. The event parser of claim 40, wherein the grammar is reordered when a rate of dataflow exceeds a predetermine threshold.

49. The event parser of claim 40, wherein the grammar comprises a plurality of reorder groups, each reorder group comprising at least one known expression, wherein the known expressions are reordered within each of the reorder groups and the reorder groups remain in a fixed order.

50. The event parser of claim 40, wherein the grammar comprises a plurality of reorder groups, each reorder group comprising at least one known expression, wherein the reorder groups are reordered and the known expressions remain in a fixed order within each of the reorder groups.

51. The event parser of claim 40, wherein at least a portion of the grammar is prevented from being reordered.

52. A method for reordering grammar in a grammar based event parser, comprising automatically reordering the grammar based at least in part on matches between determined expressions and known expressions.

53. A grammar based event parser, comprising a reordering unit to automatically reorder grammar based at least in part on matches between determined expressions and known expressions.