Aggregator for connection based anomaly detection

• US 8,479,057 B2
• Filed: 11/03/2003
• Issued: 07/02/2013
• Est. Priority Date: 11/04/2002
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Poletto, Massimiliano Antonio, Ratin, Andrew, Gorelik, Andrew
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US10/701,356
• Publication Number:
  US 20040221190A1
• Time in Patent Office: 3,529 Days
• Field of Search: 714/47, 714/48, 714/4.1, 714/47.2, 714/47.3, 709/223, 709/224, 709/225, 709/226, 726/22, 726/23, 726/25, 726/24
• US Class Current: 714/47.3
• CPC Class Codes: H04L 41/0233 Object-oriented techniques, for representation of network management data, e.g. common object request broker architecture [CORBA]
• 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 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

A system for detecting network intrusions and other conditions in a network is described. The system includes a plurality of collector devices that are disposed to collect data and statistical information on packets that are sent between nodes on a network. An aggregator device is disposed to receive data and statistical information from the plurality of collector devices. The aggregator device produces a connection table that maps each node on the network to a record that stores information about traffic to or from the node. The aggregator runs processes that determine network events from aggregating of anomalies into network events.

Claims

1. A device, comprising:

a processor;

a memory storing;

a connection table that maps each node of a network to a host object that stores information about traffic to the node and from the node, wherein the connection table includes a plurality of sub-tables to track data at different time-scales, and the connection sub-tables include a time-slice connection table that operates on a small unit of time and at least one other sub-table that operates on a larger unit of time than the time slice sub-table with each sub-table holding the sum of records received from all collectors during respective units of time; and

a computer readable medium storing a computer program product comprising instructions for causing the device to;

detect anomalies in network traffic based on information in the connection table and to aggregate the anomalies into network events according to connection patterns.

2. The device of claim 1 wherein the connection table further includes group information, with Host objects storing group information about an identified group of nodes that an associated node belonged to.

3. The device of claim 2 further comprises instructions to:

communicate occurrences of network events to an operator.

4. The device of claim 1 wherein the information about traffic includes aggregated network traffic statistics and the host object maintains the aggregated network traffic statistics for the associated node and a hash map from host identifiers of peers of a node as host pair objects that maintain traffic statistics for each pair of nodes.

5. The device of claim 4 wherein the instructions to determine events track a moving average of at least one of the aggregated network traffic statistics to allow the device to adapt to slowly changing network conditions.

6. The device of claim 4 wherein the instructions to determine events track a variance of at least one of the aggregated network traffic statistics to allow the device to account for burstiness in network traffic.

7. The device of claim 4 wherein the amount of memory space used to detect and aggregate is bounded in order to avoid denial of service attacks on the aggregator process.

8. The device of claim 7 wherein if the memory space exceeds a memory use threshold “

m_{hi}”

, the aggregator de-allocates records until its memory use falls below the threshold “

m_{hi}”

.

9. The device of claim 8 wherein the instructions to detect and aggregate de-allocate records by random eviction of records.

10. The device of claim 8 wherein the instructions to detect and aggregate de-allocate records by picking records of low-connectivity hosts to evict over high connectivity hosts.

11. The device of claim 8 wherein the instructions to detect and aggregate de-allocate records by picking records of high-connectivity hosts to evict before records of low connectivity hosts.

12. The device of claim 8 wherein the instructions to detect and aggregate de-allocate records by evicting records of most recently added hosts first.

13. The device of claim 1 wherein each host object in the connection table maps to a plurality of records that are indexed by source address, the plurality of records including host-pair records that map network traffic between pairs of nodes.

14. The device of claim 1 wherein each host object in the connection table maps to a plurality of records that are indexed by destination address, the plurality of records including host-pair records that map network traffic between pairs of nodes.

15. The device of claim 1 wherein each host object in the connection table maps to a plurality of records that are indexed by time, the plurality of records including host-pair records that map network traffic between pairs of nodes.

16. The device of claim 1 wherein each host object in the connection table maps to a plurality of records that are indexed by source address, destination address and time, the plurality of records including host-pair records that map network traffic between pairs of nodes.

17. The device of claim 1 wherein the host object further maps, for each node, a node pair record that has information about traffic between a pair of nodes to provide a two-level map that enables an analysis algorithm to efficiently obtain summary information about one node and about traffic in either direction between any pair of nodes.

18. A computer program product residing on a non-transitory computer readable medium for use in detecting network intrusions comprises instructions for causing a processor to:

store a connection table that maps each node of a network to a host object, the connection table stores information about traffic to or from the node, wherein the connection table includes a plurality of sub-tables to track data at different time-scales, and the connection sub-tables include a time-slice connection table that operates on a small unit of time and at least one other sub-table that operates on a larger unit of time than the time slice sub-table with each sub-table holding the sum of records received from all collectors during respective units of time; and

aggregate anomalies determined from information in the connection table into network events according to connection patterns.

19. The program of claim 18 wherein the instructions further comprise instructions to:

store an aggregator process to aggregate occurrences of network anomalies into events.

20. The program of claim 18 wherein the instructions further comprise instructions to:

communicate occurrences of network events to an operator.

21. The program of claim 18 wherein the instructions further comprise instructions to:

populate the connection table with group information, with Host objects storing group information about an identified group of hosts that the associated host belonged to.

22. The computer program product of claim 18 wherein instructions to store the host object further comprises instructions to:

store, for each node, a node pair record that has information about traffic between a pair of nodes to provide a two-level map that enables an analysis algorithm to efficiently obtain summary information about one node and about traffic in either direction between any pair of nodes.

23. A method comprising:

producing in a computer system a connection table that maps each node of a network to a host object, the connection table stores information about traffic to or from the node, wherein the connection table includes a plurality of sub-tables to track data at different time-scales, and the connection sub-tables include a time-slice connection table that operates on a small unit of time and at least one other sub-table that operates on a larger unit of time than the time slice sub-table with each sub-table holding the sum of records received from all collectors during respective units of time; and

aggregating anomalies into the network events according to connection patterns.

24. The method of claim 23, further comprising:

executing an aggregator process in the computer system to aggregate occurrences of network anomalies into events.

25. The method of claim 24, further comprising:

sending occurrences of network events to an operator.

26. The method of claim 24, further comprising:

populating the connection table with group information, with Host objects storing group information about an identified group of nodes that an associated node belonged to.

27. The method of claim 26, further comprising:

collecting network traffic statistics for nodes on the network;

storing host pair objects that maintain traffic statistics for each pair of nodes; and

determining events by tracking a moving average of at least one of the statistics to adapt to slowly changing network conditions.

28. The method of claim 24, further comprising:

managing the amount of memory space used in aggregating in order to avoid denial of service attacks on the computer system performing the aggregating.

29. The method of claim 24, wherein if the aggregating exceeds a memory use threshold “

m_{hi}”

, the method further comprises;

de-allocating records until the memory use falls below a threshold “

m_{hi}”

.

30. The method of claim 23 wherein producing the host object further comprises:

producing for each node a node pair record that has information about traffic between a pair of nodes to provide a two-level map that enables an analysis algorithm to efficiently obtain summary information about one node and about traffic in either direction between any pair of nodes.