# US 9,438,620 B2 · Control flow graph representation and classification

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

- Number: US 9,438,620 B2
- Document ID: US9438620B2
- Status: Granted
- Kind: B2
- Application number: 14/126,872
- Filed: 2013-10-22
- Published: 2015-06-25
- Granted: 2016-09-06
- Earliest claimed: 2013-10-22
- Assignees: McAfee, Inc.
- Applicants: McAfee, Inc.
- Inventors: Erdem Aktas; Rachit Mathur
- Web page: https://patentgrep.com/patent/US9438620B2

## CPC

- H04L 63/145: {the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms}
- G06F 9/46: Multiprogramming arrangements
- G06F 16/287: {Visualization; Browsing}
- G06F 21/564: {by virus signature recognition}
- H04L 63/1408: {by monitoring network traffic (monitoring network traffic per se H04L43/00)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A software sample is identified that includes code and a control flow graph is generated for each of a plurality of functions included in the sample. Features are identified in each of the functions that correspond to instances of a set of control flow fragment types. A feature set is generated for the sample from the identified features.

## Claims

### Claim 1

At least one non-transitory machine accessible storage medium having instructions stored thereon, the instructions when executed on a machine, cause the machine to:
identify a particular sample comprising code;
generate a structure to represent the particular sample, wherein the structure represents a plurality of functions included in the particular sample;
identify, in each of the functions, respective control flow fragments of the function;
identify a subset of the fragments of the plurality of functions as features of the particular sample based on each of the subset of fragments comprising an instance of a respective one of a predefined set of fragment types;
generate a feature set for the particular sample from the identified features; and
classify the particular sample based on a determination that feature sets of a cluster of other samples overlap with the feature set of the particular sample.

### Claim 2 (depends on 1)

The storage medium of claim 1, wherein the instructions, when executed, are to further cause the machine to combine the features identified for each of the functions to generate a consolidated string for the particular sample, wherein the feature set is generated from the consolidated string.

### Claim 3 (depends on 2)

The storage medium of claim 2, wherein the instructions, when executed, are to further cause the machine to generate, for each of the functions, a string describing the respective features identified for the function.

### Claim 4 (depends on 3)

The storage medium of claim 3, wherein combining the features includes:
identifying a call in a particular one of the plurality of functions to another one of the plurality of functions; and
replacing a portion of the string of the particular function referencing the other function with contents of the string of the other function.

### Claim 5 (depends on 3)

The storage medium of claim 3, wherein identifying the features includes abstracting each of the strings of the functions such that only features of the set of fragment types are described in the strings and fragments of the functions of types outside the set of fragment types are excluded from the feature set.

### Claim 6 (depends on 1)

The storage medium of claim 1, wherein the set of fragment types comprise memory accesses by the function and function calls by the function.

### Claim 7 (depends on 5)

The storage medium of claim 5, wherein identifying the features comprises:
identifying instances of memory accesses by each of the functions; and
identifying instances of function calls by each of the functions.

### Claim 8 (depends on 1)

The storage medium of claim 1, wherein the feature set identifies each of the features identified for each of the functions.

### Claim 9 (depends on 1)

The storage medium of claim 1, wherein the feature set comprises an n-graph.

### Claim 10 (depends on 1)

The storage medium of claim 1, wherein classifying the particular sample includes determining a set of features relevant to a cluster of samples.

### Claim 11 (depends on 1)

The storage medium of claim 1, wherein classifying the particular sample includes determining whether to classify the sample as malware.

### Claim 12 (depends on 1)

The storage medium of claim 1, wherein classifying the particular sample includes determining whether the sample is likely one of one or more families of malware.

### Claim 13 (depends on 1)

The storage medium of claim 1, wherein identifying the features includes abstracting each of the structures such that only features of the set of control flow fragment types are described in the structures.

### Claim 14

A method comprising:
identifying a particular sample comprising code;
generating, using at least one data processing apparatus, a structure for the particular sample, wherein the structure represents a plurality of functions included in the particular sample;
identifying, using at least one data processing apparatus, in each of the functions, respective fragments of the function;
identify a subset of the fragments of the plurality of functions as features of the particular sample based on each of the subset of fragments comprising an instance of a respective one of a predefined set of fragment types;
generating, using at least one data processing apparatus, a feature set for the particular sample from the identified features; and
classifying the particular sample based on a determination that feature sets of a cluster of other samples overlap with the feature set of the particular sample.

### Claim 15 (depends on 14)

The method of claim 14, further comprising combining the features identified for each of the functions to generate a consolidated string for the particular sample, wherein the feature set is generated from the consolidated string.

### Claim 16 (depends on 15)

The method of claim 15, further comprising generating, for each of the functions, a string describing the respective features identified for the function.

### Claim 17 (depends on 16)

The method of claim 16, wherein combining the features includes:
identifying a call in a particular one of the plurality of functions to another one of the plurality of functions; and
replacing a portion of the string of the particular function referencing the other function with contents of the string of the other function.

### Claim 18 (depends on 14)

The method of claim 14, further comprising receiving a plurality of samples including the particular sample.

### Claim 19 (depends on 18)

The method of claim 18, wherein the plurality of samples are received from a plurality of sources.

### Claim 20

A system comprising:
at least one processor device;
at least one memory element; and
a feature set builder, when executed by the at least one processor device, to:
identify a particular sample comprising code;
generate a structure for the particular sample, wherein the structure represents a plurality of functions included in the particular sample;
identify, in each of the functions, respective fragments of the function;
identify a subset of the fragments of the plurality of functions as features of the particular sample based on each of the subset of fragments comprising an instance of a respective one of a predefined set of fragment types;
generate a feature set for the particular sample from the identified subset of the fragments; and
classify the particular sample based on a determination that feature sets of a cluster of other samples overlap with the feature set of the particular sample.

### Claim 21 (depends on 20)

The system of claim 20, wherein the cluster comprises a particular one of a plurality of clusters.

### Claim 22 (depends on 20)

The system of claim 20, wherein the feature set identifies a subset of features identified in the structures of the functions of the particular sample.

### Claim 23 (depends on 22)

The system of claim 22, wherein the subset of features corresponds to memory accesses and function calls in the sample code.