Method and system for maintaining network activity data for intrusion detection

• US 7,017,185 B1
• Filed: 12/21/2000
• Issued: 03/21/2006
• Est. Priority Date: 12/21/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hall, Michael L. Jr., Lathem, Gerald S., Wiley, Kevin L.
• Primary Examiner(s): REVAK, CHRISTOPHER A
• Application Number:
  US09/746,305
• Time in Patent Office: 1,916 Days
• Field of Search: 713/150, 713/168, 713/176, 713/200, 713/201, 709/223, 709/224, 707/1, 707/3, 707/200, 707/201, 707/203
• US Class Current: 726/23
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method and system for maintaining network activity data for intrusion detection includes storing data representative of network activity in datasets. The datasets include root datasets each having a root keyset and child datasets each having a child keyset with a key combination derived from and less granular than a root keyset. Child datasets are identified through their root datasets.

Claims

1. A method for maintaining network activity data for an intrusion detection system, comprising:

storing data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination being a subset of, and less granular than, a root keyset; and

identifying a child dataset of a root dataset through the root dataset.

2. The method of claim 1, further comprising identifying a plurality of child datasets of the root dataset through the root dataset.

3. The method of claim 1, further comprising identifying all child datasets of the root dataset through the root dataset.

4. The method of claim 1, further comprising identifying the child dataset of the root dataset with a pointer from the root dataset to the child dataset.

5. The method of claim 1, further comprising identifying all child datasets through their root datasets.

6. The method of claim 1, wherein each root dataset comprises a plurality of child datasets.

7. The method of claim 1, wherein the root dataset includes a sibling root dataset, the sibling root dataset and the root dataset having root keysets a reverse of each other, further comprising identifying the sibling root dataset through the root dataset.

8. The method of claim 7, wherein the root dataset and the sibling root dataset collectively identify all of their child datasets and identify one another.

9. The method of claim 1, wherein the root keysets each comprise a source address key and a destination address key.

10. The method of claim 1, wherein the root keysets comprise quad keysets.

11. The method of claim 10, wherein the quad keysets each comprise a source address key, a source port key, a destination address key and a destination port key.

12. The method of claim 1, wherein the child keysets comprise one of single, dual and triple keysets.

13. The method of claim 1, wherein the root keysets comprise stream based keysets.

14. The method of claim 13, wherein the stream based keysets comprise a source address key, a source port key, a destination address key and a destination port key, a first child keyset comprises a source address key and a destination address key, a second child keyset comprises a destination address key and a destination port key, and a third child keyset comprises a source address key and a destination port key.

15. The method of claim 1, wherein the datasets comprise data buckets.

16. The method of claim 1, further comprising identifying all child datasets of the root dataset through the root dataset with a single search of a database storing the datasets.

17. The method of claim 1, further comprising:

receiving a traffic signature not having a root dataset;

generating a root dataset having a root keyset representative of the traffic signature;

identifying all existing child and sibling root datasets of the root dataset;

generating all absent child and sibling root datasets of the root dataset; and

associating the child and sibling root datasets with the root dataset.

18. The method of claim 1, further comprising automatically removing outdated root datasets and child datasets.

19. The method of claim 18, further comprising storing a counter for each child dataset, the counter operable to indicate an outdated status of the child dataset.

20. The method of claim 1, further comprising retrieving data for processing a traffic signature by searching a data storage system including the datasets for an existing root dataset having a root keyset corresponding to the traffic signature and identifying all child datasets, sibling root datasets, and child datasets of the sibling root datasets through the root dataset.

21. An intrusion detection system, comprising:

logic encoded in computer-readable media; and

the logic operable to store data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination being a subset of, and less granular than, a root keyset and further operable to identify a child dataset for a root dataset through the root dataset.

22. The intrusion detection system of claim 21, the logic further operable to identify a plurality of child datasets of the root dataset through the root dataset.

23. The intrusion detection system of claim 21, the logic further operable to identify all child datasets of the root dataset through the root dataset.

24. The intrusion detection system of claim 21, the logic further operable to identify the child dataset of the root dataset with a pointer from the root dataset to the child dataset.

25. The intrusion detection system of claim 21, the logic further operable to identify all child datasets through their root datasets.

26. The intrusion detection system of claim 21, wherein each root dataset comprises a plurality of child datasets.

27. The intrusion detection system of claim 21, wherein the root dataset includes a sibling root dataset, the root dataset and the sibling root dataset having root keysets a reverse of each other, the logic further operable to identify the sibling root dataset through the root dataset.

28. The intrusion detection system of claim 27, wherein the root dataset and the sibling root dataset collectively identify all of their child datasets and identify one another.

29. The intrusion detection system of claim 21, wherein the root keysets each comprise a source address key and a destination address key.

30. The intrusion detection system of claim 21, wherein the root keysets comprise quad keysets.

31. The intrusion detection system of claim 30, wherein the root keysets comprise quad keysets, the quad keysets each including a source address key, a source port key, a destination address key, and a destination port key.

32. The intrusion detection system of claim 21, wherein the child keysets comprise one of single, dual and triple keysets.

33. The intrusion detection system of claim 21, wherein the root keysets comprise stream based keysets.

34. The intrusion detection system of claim 21, the logic further operable to receive a traffic signature not having a root dataset, to generate a root dataset having a root keyset representative of the traffic signature, to identify all existing child and sibling root datasets of the root dataset, to generate absent child and sibling root datasets of the root dataset and to associate the child and sibling root datasets of the root dataset with the root dataset.

35. The intrusion detection system of claim 21, wherein the datasets comprise data buckets.

36. The intrusion detection system of claim 21, the logic further operable to automatically remove outdated root and child datasets.

37. The intrusion detection system of claim 36, the logic further operable to maintain a counter for each child dataset, the counter operable to indicate an outdated status of the child dataset.

38. The intrusion detection system of claim 21, the logic further operable to retrieve data for processing of a traffic signature by searching a data storage system including the datasets for an existing root dataset corresponding to the traffic signature and to identify all child datasets, sibling root datasets and child datasets of the root dataset and the sibling root dataset through the root dataset.

39. A system for maintaining data on network activity for an intrusion detection system, comprising:

means for storing data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination being a subset of, and less granular than, a root keyset; and

means for identifying a child dataset of a root dataset through the root dataset.

40. The system of claim 39, further comprising means for identifying the child dataset of the root dataset with a pointer from the root dataset to the child dataset.

41. The system of claim 39, further comprising means for identifying all child datasets of the root dataset through the root dataset.

42. The system of claim 39, further comprising means for identifying all child datasets through their root datasets.

43. The system of claim 39, wherein the root datasets include a sibling root dataset, the sibling root dataset and the root dataset having root keysets a reverse of each other, further comprising means for identifying the root dataset and the sibling root dataset through each other.

44. The system of claim 39, further comprising:

means for receiving a traffic signature not having a root dataset;

means for generating a root dataset having a root keyset representative of the traffic signature;

means for identifying all existing child and sibling root datasets of the root dataset;

means for generating absent child and sibling root datasets of the root dataset; and

means for associating the child and sibling root datasets of the root dataset with the root dataset.

45. The system of claim 39, further comprising means for automatically removing outdated root datasets and child datasets.

46. The system of claim 39, further comprising:

means for retrieving data for processing of a traffic signature by searching a data storage system for an existing root dataset having a root keyset corresponding to the traffic signature; and

means for identifying all child datasets, sibling root datasets, and child datasets of the root dataset through the root dataset.

47. A method for maintaining data on Internet Protocol (IP) traffic for an intrusion detection system, comprising:

storing data representative of network activity in datasets, the datasets including root datasets each having a quad keyset comprising a source address key, a source port key, a destination address key and a destination port key and child datasets each having a dual keyset with a key combination derived from and less granular than a quad keyset of a root dataset;

storing pointers for each root dataset, the pointers each identifying a child dataset having a dual keyset derived from the quad keyset of the root dataset and a sibling root dataset having a quad keyset a reverse of the quad keyset of the root dataset; and

retrieving data for processing of a traffic signature by performing a single search for a root dataset having a quad keyset corresponding to the traffic signature and identifying relevant child and sibling root datasets through the pointers of the root dataset.

48. The method of claim 47, wherein the dual keysets include a first dual keyset comprising a source address key and a destination address key, a second dual keyset comprising a destination address key and a destination port key, and a third dual keyset comprising a source address key and a destination port key.

49. A method for maintaining network activity data for an intrusion detection system, comprising:

storing data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination derived from and less granular than a root keyset;

identifying a child dataset of a root dataset through the root dataset;

receiving a traffic signature not having a root dataset;

generating a root dataset having a root keyset representative of the traffic signature;

identifying all existing child and sibling root datasets of the root dataset;

generating all absent child and sibling root datasets of the root dataset; and

associating the child and sibling root datasets with the root dataset.

50. A method for maintaining network activity data for an intrusion detection system, comprising:

storing data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination derived from and less granular than a root keyset;

identifying a child dataset of a root dataset through the root dataset; and

retrieving data for processing a traffic signature by searching a data storage system including the datasets for an existing root dataset having a root keyset corresponding to the traffic signature and identifying all child datasets, sibling root datasets, and child datasets of the sibling root datasets through the root dataset.

51. An intrusion detection system, comprising:

logic encoded in computer-readable media;

the logic operable to store data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination derived from and less granular than a root keyset and further operable to identify a child dataset for a root dataset through the root dataset; and

the logic further operable to retrieve data for processing of a traffic signature by searching a data storage system including the datasets for an existing root dataset corresponding to the traffic signature and to identify all child datasets, sibling root datasets and child datasets of the root dataset and the sibling root dataset through the root dataset.

52. A system for maintaining data on network activity for an intrusion detection system, comprising:

means for storing data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination derived from and less granular than a root keyset;

means for identifying a child dataset of a root dataset through the root dataset;

means for receiving a traffic signature not having a root dataset;

means for generating a root dataset having a root keyset representative of the traffic signature;

means for identifying all existing child and sibling root datasets of the root dataset;

means for generating absent child and sibling root datasets of the root dataset; and

means for associating the child and sibling root datasets of the root dataset with the root dataset.

53. A system for maintaining data on network activity for an intrusion detection system, comprising:

means for storing data representative of network activity in datasets, the datasets including root datasets each having a root keyset and child datasets each having a child keyset with a key combination derived from and less granular than a root keyset;

means for identifying a child dataset of a root dataset through the root dataset;

means for retrieving data for processing of a traffic signature by searching a data storage system for an existing root dataset having a root keyset corresponding to the traffic signature; and

means for identifying all child datasets, sibling root datasets, and child datasets of the root dataset through the root dataset.