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

Patent metadata

Field	Value
Publication number	US-10601849-B2
Application number	US-201715685827-A
Country	US
Kind code	B2
Filing date	Aug 24, 2017
Priority date	Aug 24, 2017
Publication date	Mar 24, 2020
Grant date	Mar 24, 2020

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.

First claim

What is claimed is:

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.

Assignees

• Level 3 Communications Llc

Inventors

• Yermakov Sergey

Classifications

• G06F21/577

  Assessing vulnerabilities and evaluating computer system security · CPC title

• H04L63/0236

  Filtering by address, protocol, port number or service, e.g. IP-address or URL · CPC title

• H04L41/142

  using statistical or mathematical methods · CPC title

• H04L43/16

  Threshold monitoring · CPC title

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title