Low-complexity detection of potential network anomalies using intermediate-stage processing

• US 10,601,849 B2
• Filed: 08/24/2017
• Issued: 03/24/2020
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Yermakov, Sergey
• Primary Examiner(s): Turchen, James R
• Application Number:
  US15/685,827
• Publication Number:
  US 20190068623A1
• Time in Patent Office: 943 Days
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• 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

In an embodiment, a computer implemented method receives flow data for a network flows. The method extracts a tuple from the flow data and calculates long-term and short-term trends based at least in part on the tuple. The long-term and short-term trends are compared to determine whether a potential network anomaly exists. If a potential network anomaly does exist, the method initiates a heavy hitter detection algorithm. The method forms a low-complexity intermediate stage of processing that enables a high-complexity heavy hitter detection algorithm to execute when heavy hitters are likely to be detected.

Claims

1. A computer implemented method, comprising:

receiving flow data for a network flow;

parsing the flow data into a plurality of time buckets;

extracting a plurality of tuples describing the flow data, the tuple comprising a time duration of the network flow and information identifying an amount of data transmitted during the flow;

calculating a long-term trend based at least in part on at least a first tuple and two or more time buckets of the plurality of time buckets including assigning the first tuple to a long-term cluster of a plurality of long-term clusters;

calculating a short-term trend based at least in part on a second tuple and a most recent time bucket of the plurality of time buckets including assigning the second tuple to a short-term cluster of a plurality of short-term clusters;

determining that the short-term trend diverges from the long-term trend to detect a potential network anomaly by determining that a percentage of tuples in a short-term cluster relative to other short-term clusters is significantly more than a percentage of tuples in a long-term cluster, corresponding to the short-term cluster, relative to other long-term clusters; and

when the potential network anomaly is detected, initiating a heavy hitter detection algorithm.

2. The method of claim 1, further comprising assigning one or more tuples of the plurality of tuples to a time bucket.

3. The method of claim 2, wherein calculating the long-term trend comprises forming a long-term bucket comprising tuples assigned to at least one of the two or more buckets.

4. The method of claim 3, wherein calculating the long-term trend further comprises normalizing the first tuple relative to other tuples in the long-term bucket.

5. A system, comprising:

a memory; and

at least one processor coupled to the memory and configured to;

receive flow data for a network flow;

parse the flow data into a plurality of time buckets;

extract a plurality of tuples describing the flow data, wherein a tuple comprises a time duration of the network flow and information identifying an amount of data transmitted during the flow;

calculate a long-term trend based at least in part on at least a first tuple and two or more time buckets of the plurality of time buckets including assigning the first tuple to a long-term cluster of a plurality of long-term clusters;

calculate a short-term trend based at least in part on a second tuple and a most recent time bucket of the plurality of time buckets including assigning the second tuple to a short-term cluster of a plurality of short-term clusters;

determining that the short-term trend diverges from the long-term trend to detect a potential network anomaly by determining that a percentage of tuples in a short-term cluster relative to other short-term clusters is significantly more than a percentage of tuples in a long-term cluster, corresponding to the short-term cluster, relative to other long-term clusters; and

when the potential network anomaly is detected, initiate a heavy hitter detection algorithm.

6. The system of claim 5, wherein the at least one processor is further configured to assign one of more tuples of the plurality of tuples to a time bucket.

7. The system of claim 6, wherein the at least one processor is configured to calculate the long-term trend by forming a long-term bucket comprising tuples assigned to at least one the two or more buckets.

8. The system of claim 7, wherein the at least one processor is further configured to calculate the long-term trend by normalizing the first tuple relative to other tuples in the long-term bucket.

9. A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

receiving flow data for a network flow;

parsing the flow data into a plurality of time buckets;

extracting a plurality of tuples describing the flow data, wherein a tuple comprises a time duration of the network flow and information identifying an amount of data transmitted during the flow;

calculating a long-term trend based at least in part on at least a first tuple and two or more time buckets of the plurality of time buckets including assigning the first tuple to a long-term cluster of a plurality of long-term clusters;

calculating a short-term trend based at least in part on a second tuple and a most recent time bucket of the plurality of time buckets including assigning the second tuple to a short-term cluster of a plurality of short-term clusters;

determining that the short-term trend diverges from the long-term trend to detect a potential network anomaly by determining that a percentage of tuples in a short-term cluster relative to other short-term clusters is significantly more than a percentage of tuples in a long-term cluster, corresponding to the short-term cluster, relative to other long-term clusters; and

when the potential network anomaly is detected, initiating a heavy hitter detection algorithm.

10. The non-transitory computer-readable medium of claim 9, the instructions further comprising assigning on or more tuples of the plurality of tuples to a time bucket.

11. The non-transitory computer-readable medium of claim 10, wherein calculating the long-term trend comprises forming a long-term bucket comprising tuples assigned to at least one of the two or more buckets.

12. The non-transitory computer-readable medium of claim 11, wherein calculating the long-term trend further comprises normalizing the first tuple relative to other tuples in the long-term bucket.