# US 2021/0344696 A1 · Large scale malware sample identification

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

- Number: US 2021/0344696 A1
- Document ID: US20210344696A1
- Status: Published application
- Kind: A1
- Application number: 16/863,806
- Filed: 2020-04-30
- Published: 2021-11-04
- Earliest claimed: 2020-04-30
- Assignees: McAfee, Inc.
- Applicants: McAfee, LLC
- Inventors: German Lancioni; Jonathan B. King; Steven Grobman
- Web page: https://patentgrep.com/patent/US20210344696A1

## CPC

- G06F 21/564: {by virus signature recognition}
- H04L 63/1425: {Traffic logging, e.g. anomaly detection}
- G06F 16/2255: {Hash tables}
- G06F 16/245: Query processing
- G06F 16/285: {Clustering or classification}
- G06F 21/568: {eliminating virus, restoring damaged files}
- H04L 63/1416: {Event detection, e.g. attack signature detection}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method including receiving a feature vector of an unknown sample, computing a MinHash of the unknown sample based on Jaccard-compatible features, querying a Locality Sensitive Hashing forest of known samples with the MinHash of the unknown sample to identify a first subset of known samples that are similar to the unknown sample, receiving for each individual known sample in the first subset, a feature vector including non-Jaccard distance-compatible features, computing a first sub-distance and a second sub-distance between the unknown sample and the known samples in the first subset, calculating a total distance for each known sample in the first subset by combining the first and the second sub-distances, identifying, based on the calculated total distances, a second subset of known samples that are most similar to the unknown sample, and classifying the unknown sample based on the second subset.

## Claims

### Claim 1

An apparatus, comprising:
a memory element operable to store instructions; and
a processor operable to execute the instructions, such that the apparatus is configured to:
receive a feature vector of an unknown sample, wherein the feature vector includes Jaccard-compatible features and non-Jaccard distance-compatible features;
compute a MinHash of the unknown sample based on the Jaccard-compatible features;
query a MinHash Locality Sensitive Hashing (LSH) Forest of known samples with the MinHash of the unknown sample to identify a first subset of known samples that are similar to the unknown sample;
receive, for each individual known sample in the first subset, a feature vector having non-Jaccard distance-compatible features;
compute, for each individual known sample in the first subset, a first sub-distance between the unknown sample and the known sample using a first non-Jaccard distance-compatible feature and a second sub-distance between the unknown sample and the known sample using a second non-Jaccard distance-compatible feature;
calculate, for each individual known sample in the first subset, an overall distance between the unknown sample and the known sample by combining the first and the second sub-distances;
identify, based on the overall distance between the unknown sample and each individual known sample in the first subset, a second subset of known samples that are most similar to the unknown sample; and
classify the unknown sample based on the second subset of known samples.

### Claim 2 (depends on 1)

The apparatus of claim 1, further configured to:
assign a remediation to the classified unknown sample.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the unknown sample and the known samples are malware.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein identifying the second subset of known samples includes selecting the known samples having the overall distance that is equal to or less than a threshold.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein identifying the second subset of known samples includes selecting a number of known samples with the lowest overall distance.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein a number of known samples in the second subset is between 10 and 25.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein a number of known samples in the first subset is between 250 and 500.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein the first non-Jaccard distance-compatible feature is Euclidean-compatible and the second non-Jaccard distance-compatible feature is Hamming-compatible.

### Claim 9 (depends on 1)

The apparatus of claim 1, further configured to:
receive a unique identifier of the unknown sample;
query an index of the MinHash LSH Forest using the unique identifier to determine whether the unknown sample is in the MinHash LSH Forest; and
add the unknown sample to the MinHash LSH Forest based on a determination that the unknown sample is not in the MinHash LSH Forest.

### Claim 10

At least one non-transitory computer-readable medium comprising one or more instructions that when executed by a processor, cause the processor to:
receive a feature vector of an unknown malware, wherein the feature vector includes Jaccard-compatible features, a first non-Jaccard sub-distance feature, and a second non-Jaccard sub-distance feature;
compute a MinHash of the unknown malware;
identify a first subset of known malware, wherein identifying the first subset includes querying a MinHash Locality Sensitive Hashing (LSH) Forest of known malware with the MinHash of the unknown malware;
receive a feature vector for each individual known malware in the first subset, wherein the feature vector includes a first non-Jaccard sub-distance feature and a second non-Jaccard sub-distance feature;
calculate a first sub-distance and a second sub-distance between the unknown malware and each individual known malware in the first subset, wherein the first sub-distance is based on the first non-Jaccard sub-distance features and the second sub-distance is based on the second non-Jaccard sub-distance features;
calculate a Custom Distance Metric (CDM) for each individual known malware in the first subset by combining the first and the second sub-distances;
identify, using the calculated CDM for each individual known malware in the first subset, a second subset of known malware that are most similar to the unknown malware; and
classify the unknown malware based on the second subset of known malware.

### Claim 11 (depends on 10)

The at least one non-transitory computer-readable medium of claim 10, further comprising one or more instructions that when executed by a processor, cause the processor to:
assign a remediation to the classified unknown malware.

### Claim 12 (depends on 10)

The at least one non-transitory computer-readable medium of claim 10, wherein identifying the second subset of known malware includes selecting the known malware having the CDM that is equal to or less than a threshold.

### Claim 13 (depends on 10)

The at least one non-transitory computer-readable medium of claim 10, wherein identifying the second subset of known malware includes selecting a number of known malware with the lowest CDM.

### Claim 14 (depends on 10)

The at least one non-transitory computer-readable medium of claim 10, wherein classifying the known malware includes assigning a type, a family, an author, or a source location.

### Claim 15 (depends on 10)

The at least one non-transitory computer-readable medium of claim 10, further comprising one or more instructions that when executed by a processor, cause the processor to:
receive a unique identifier for the unknown malware;
query an index of the MinHash LSH Forest using the unique identifier to determine whether the unknown malware is in the MinHash LSH Forest; and
add the unknown malware to the MinHash LSH Forest based on a determination that the unknown malware is not in the MinHash LSH Forest.

### Claim 16

A method, comprising:
receiving a MinHash for an unknown malware sample;
querying a MinHash Locality Sensitive Hashing (LSH) Forest using the MinHash for the unknown malware sample to identify a first set of similar samples, wherein the MinHash LSH Forest is based on a plurality of known malware samples, and wherein each known malware sample in the plurality of known malware samples includes a unique hashing identifier and a MinHash;
receiving a first non-Jaccard distance-compatible feature and a second non-Jaccard distance-compatible feature for the unknown malware sample;
receiving a first non-Jaccard distance-compatible feature and a second non-Jaccard distance-compatible feature for each known malware sample in the first set of similar samples;
calculating a total distance between the unknown malware sample and each known malware sample in the first set of similar samples, wherein the total distance is a combination of a first distance and a second distance, and wherein the first distance is calculated using the first non-Jaccard distance-compatible features and the second distance is calculated using the second non-Jaccard distance-compatible features;
identifying, based on the total distance for each known malware sample, a second set of similar samples; and
classifying the unknown malware sample based on the second set of similar samples.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
receiving a unique identifier of the classified unknown sample;
querying an index of the MinHash LSH Forest using the unique identifier to determine whether the classified unknown sample is in the MinHash LSH Forest; and
adding the classified unknown sample to the MinHash LSH Forest based on a determination that the classified unknown sample is not in the MinHash LSH Forest.

### Claim 18 (depends on 16)

The method of claim 16, further comprising:
assigning a remediation to the classified unknown sample.

### Claim 19 (depends on 16)

The method of claim 16, wherein the first non-Jaccard distance-compatible features are Euclidean-type and the second non-Jaccard distance-compatible features are non-Euclidean-type.

### Claim 20 (depends on 16)

The method of claim 16, wherein a number of known samples in the second set is between 10 and 25.
