Profile-aware filtering of network traffic

• US 8,028,337 B1
• Filed: 08/10/2006
• Issued: 09/27/2011
• Est. Priority Date: 08/30/2005
• Status: Active Grant

• Current Assignee: T-Mobile Innovations LLC (Deutsche Telekom AG)
• Original Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Inventors: Zhang, Zhi-Li, Xu, Kuai, Bhattacharyya, Supratik
• Primary Examiner(s): Pearson; David
• Assistant Examiner(s): LANE, GREGORY A
• Application Number:
  US11/463,723
• Time in Patent Office: 1,874 Days
• Field of Search: 370/342, 370/465, 455/431, 455/436, 726 22- 25, 709227-229, 709220-222
• US Class Current: 726/23
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 63/00 Network architectures or network communication protocols for network security cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00; network architectures or network communication protocols for wireless network security H04W12/00; security arrangements for protecting computers or computer systems against unauthorised activity G06F21/00
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

A system and a method for profiling traffic on a computer network. Flows are observed traversing a communication link. Relative uncertainty values are computed for the dimensions of these flows. These relative uncertainty values are used to identify dominant feature values in the various flow dimensions. Flows having these dominant feature values are filtered.

Claims

1. A computer-implemented method for sampling flows observed within traffic traversing a communication link, said method comprising:

identifying a set of flows observed traversing said communication link, wherein said set of flows has a plurality of dimensions;

creating a plurality of clusters of flows by grouping together flows that share at least one common dimension;

assigning, to at least a portion of said plurality of clusters of flows, a probability value relating to the volume of flows in a cluster;

selecting a probability threshold and an uncertainty threshold, wherein said probability threshold indicates a probability where clusters above the probability threshold are deemed to be significant, and wherein said uncertainty threshold indicates a target level of uncertainty;

removing from said plurality of clusters one or more clusters that are assigned one or more probability values above said probability threshold, wherein the removed clusters are deemed to be significant clusters;

computing a relative uncertainty value for probability values assigned to the remaining clusters in said plurality of clusters, wherein said relative uncertainty value indicates uniformity or variability in said probability values assigned to said remaining clusters in said plurality of clusters;

until said relative uncertainty value exceeds said uncertainty threshold, iteratively decreasing said probability threshold and removing from said remaining clusters in said plurality of clusters one or more clusters that are assigned a probability value above said probability threshold, wherein the removed clusters are deemed to be significant clusters; and

utilizing said significant clusters to identify one or more clusters exhibiting a rare behavior or one more clusters exhibiting an anomalous behavior.

2. The method of claim 1, further comprising storing said set of flows in a flow table by utilizing a sampling ratio.

3. The method of claim 2, wherein said sampling ratio varies based on the number of flows stored in said flow table.

4. The method of claim 2, wherein said computing is responsive to the number of flows stored in said flow table reaching a predetermined threshold.

5. The method of claim 1, wherein said plurality of dimensions includes one or more dimensions related to a source port or a destination port.

6. The method of claim 1 , further comprising assigning each of a portion of said one or more significant clusters to one of a plurality of behavior classes.

7. A computer-implemented method for storing flows observed traversing a network link, the method comprising:

utilizing a sampling ratio to select a plurality of flows observed traversing a link on said computer network, wherein said plurality of flows have a plurality of dimensions, wherein the selected flows are stored in a flow table;

computing a relative uncertainty value for probability values assigned to clusters of flows stored in said flow table, wherein said relative uncertainty value indicates uniformity or variability in said probability values assigned to said clusters;

until said uncertainty value exceeds an uncertainty threshold;

(1) removing, from said clusters of flows, clusters whose assigned probability values are above a probability threshold, wherein the removed clusters are deemed to be significant clusters,

(2) re-computing said relative uncertainty value,

(3) comparing said relative uncertainty value to said uncertainty threshold, and

(4) iteratively decreasing said probability threshold when said relative uncertainty value is less than said uncertainty threshold; and

utilizing said significant clusters to identify one or more clusters exhibiting a rare behavior or one more clusters exhibiting an anomalous behavior.

8. The method of claim 7, further comprising monitoring the number of said plurality of flows storing in said flow table.

9. The method of claim 8, further comprising repeating said computing each time said flow table reaches one or more predetermined sizes.

10. The method of claim 7, wherein said plurality of dimensions includes one or more dimensions related to a source port, a source IP address, a destination port or a destination IP address.

11. The method of claim 7, further comprising decreasing said sampling ratio based on the number of said plurality of flows stored in said flow table.