# US 2021/0006471 A1 · Fingerprinting application traffic in a network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0006471 A1
- Document ID: US20210006471A1
- Status: Published application
- Kind: A1
- Application number: 16/459,962
- Filed: 2019-07-02
- Published: 2021-01-07
- Earliest claimed: 2019-07-02
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Andrey Kvasyuk; Hazim Hashim Dahir; Robert Bukofser; Saad Syed Hasan
- Web page: https://patentgrep.com/patent/US20210006471A1

## CPC

- H04L 41/142: using statistical or mathematical methods
- H04L 41/145: {involving simulating, designing, planning or modelling of a network}
- H04L 43/062: related to network traffic
- H04L 47/127: by using congestion prediction
- H04L 47/2483: involving identification of individual flows
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In one embodiment, a device obtains telemetry data regarding a plurality of traffic flows in a network. The device forms a directed graph based on the telemetry data, wherein nodes of the graph represent devices in the network. The device simulates traffic for one or more of the devices by performing random walks starting at a particular node on the directed graph to generate a set of trails, each trail representing a sequence of one or more flows. The device clusters the set of trails to form one or more clusters. The device generates an application fingerprint for an application based on one of the one or more clusters. The device uses the application fingerprint to identify traffic in the network as associated with the application.

## Claims

### Claim 1

A method comprising:
obtaining, by a device, telemetry data regarding a plurality of traffic flows in a network;
forming, by the device, a directed graph based on the telemetry data, wherein nodes of the graph represent devices in the network;
simulating, by the device, traffic for one or more of the devices by performing random walks starting at a particular node on the directed graph to generate a set of trails, each trail representing a sequence of one or more flows;
clustering, by device, the set of trails to form one or more clusters;
generating, by the device, an application fingerprint for an application based on one of the one or more clusters; and
using, by the device, the application fingerprint to identify traffic in the network as associated with the application.

### Claim 2 (depends on 1)

The method as in claim 1, wherein simulating traffic for one or more of the devices by performing random walks on the directed graph to generate a set of trails comprises:
using a Markov Chain Monte Carlo model to determine a probability of a traffic flow between a current node in the graph and a neighbor node.

### Claim 3 (depends on 1)

The method as in claim 1, wherein clustering the set of trails to form one or more clusters comprises:
transforming the trails into sequences of terms by using a dictionary lexicon to represent each flow in a trail as a code;
converting the codes in each trail into a vector representation; and
applying clustering to the vector representations of the trails.

### Claim 4 (depends on 3)

The method as in claim 3, further comprising:
sending a visualization of the one or more clusters to a user interface.

### Claim 5 (depends on 1)

The method as in claim 1, wherein generating the application fingerprint for the application based on one of the one or more cluster comprises:
computing a conditional probability distribution based on flows associated with that cluster.

### Claim 6 (depends on 5)

The method as in claim 5, wherein generating the application fingerprint for the application based on one of the one or more cluster comprises:
calculating a prevalence for the cluster by multiplying a number of trails in that cluster by a number of unique client devices associated with that cluster.

### Claim 7 (depends on 1)

The method as in claim 1, further comprising:
simulating, by the device, backwards traffic by performing random walks on the directed graph starting from nodes in the graph that represent devices with no outbound connections, to generate a set of backwards trails;
clustering the set of backwards trails into one or more clusters;
using one of the clusters of backwards trails to identify a source device of traffic in the network.

### Claim 8 (depends on 1)

The method as in claim 1, further comprising:
measuring a frequency of each flow within a time interval; and
applying fast independent component analysis to the frequencies of the flows within the time interval, to generate an application fingerprint.

### Claim 9

An apparatus, comprising:
one or more network interfaces to communicate with one or more networks;
a processor coupled to the network interfaces and configured to execute one or more processes; and
a memory configured to store a process executable by the processor, the process when executed configured to:
obtain telemetry data regarding a plurality of traffic flows in a network;
form a directed graph based on the telemetry data, wherein nodes of the graph represent devices in the network;
simulate traffic for one or more of the devices by performing random walks starting at a particular node on the directed graph to generate a set of trails, each trail representing a sequence of one or more flows;
cluster the set of trails to form one or more clusters;
generate an application fingerprint for an application based on one of the one or more clusters; and
use the application fingerprint to identify traffic in the network as associated with the application.

### Claim 10 (depends on 9)

The apparatus as in claim 9, wherein the apparatus simulates traffic for one or more of the devices by performing random walks on the directed graph to generate a set of trails by:
using a Markov Chain Monte Carlo model to determine a probability of a traffic flow between a current node in the graph and a neighbor node.

### Claim 11 (depends on 9)

The apparatus as in claim 9, wherein the apparatus clusters the set of trails to form one or more clusters by:
transforming the trails into sequences of terms by using a dictionary lexicon to represent each flow in a trail as a code;
converting the codes in each trail into a vector representation; and
applying clustering to the vector representations of the trails.

### Claim 12 (depends on 11)

The apparatus as in claim 11, wherein the process when executed is further configured to:
sending a visualization of the one or more clusters to a user interface.

### Claim 13 (depends on 9)

The apparatus as in claim 9, wherein the apparatus generates the application fingerprint for the application based on one of the one or more cluster by:
computing a conditional probability distribution based on flows associated with that cluster.

### Claim 14 (depends on 13)

The apparatus as in claim 13, wherein the apparatus generates the application fingerprint for the application based on one of the one or more cluster by:
calculating a prevalence for the cluster by multiplying a number of trails in that cluster by a number of unique client devices associated with that cluster.

### Claim 15 (depends on 9)

The apparatus as in claim 9, wherein the process when executed is further configured to:
simulate backwards traffic by performing random walks on the directed graph starting from nodes in the graph that represent devices with no outbound connections, to generate a set of backwards trails;
cluster the set of backwards trails into one or more clusters;
use one of the clusters of backwards trails to identify a source device of traffic in the network.

### Claim 16 (depends on 9)

The apparatus as in claim 9, wherein the process when executed is further configured to:
measure a frequency of each flow within a time interval; and
apply fast independent component analysis to the frequencies of the flows within the time interval, to generate an application fingerprint.

### Claim 17

A tangible, non-transitory, computer-readable medium storing program instructions that cause a device to execute a process comprising:
obtaining, by a device, telemetry data regarding a plurality of traffic flows in a network;
forming, by the device, a directed graph based on the telemetry data, wherein nodes of the graph represent devices in the network;
simulating, by the device, traffic for one or more of the devices by performing random walks starting at a particular node on the directed graph to generate a set of trails, each trail representing a sequence of one or more flows;
clustering, by device, the set of trails to form one or more clusters;
generating, by the device, an application fingerprint for an application based on one of the one or more clusters; and
using, by the device, the application fingerprint to identify traffic in the network as associated with the application.

### Claim 18 (depends on 17)

The computer-readable medium as in claim 17, wherein simulating traffic for one or more of the devices by performing random walks on the directed graph to generate a set of trails comprises:
using a Markov Chain Monte Carlo model to determine a probability of a traffic flow between a current node in the graph and a neighbor node.

### Claim 19 (depends on 17)

The computer-readable medium as in claim 17, wherein clustering the set of trails to form one or more clusters comprises:
transforming the trails into sequences of terms by using a dictionary lexicon to represent each flow in a trail as a code;
converting the codes in each trail into a vector representation; and
applying clustering to the vector representations of the trails.

### Claim 20 (depends on 17)

The computer-readable medium as in claim 17, wherein generating the application fingerprint for the application based on one of the one or more cluster comprises:
computing a conditional probability distribution based on flows associated with that cluster.
