System and method for clustering files and assigning a maliciousness property based on clustering

• US 10,546,143 B1
• Filed: 11/14/2017
• Issued: 01/28/2020
• Est. Priority Date: 08/10/2017
• Status: Active Grant

• Current Assignee: Support Intelligence, Inc.
• Original Assignee: Support Intelligence, Inc.
• Inventors: Wesson, Rick Holloman
• Primary Examiner(s): Perungavoor, Venkat
• Application Number:
  US15/812,915
• Time in Patent Office: 805 Days
• Field of Search: None
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/17 Details of further file system functions
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself

Abstract

A file is received. File contents are transformed using a space-filling curve. The results are down-sampled to generate a sample locus. A cluster identifier is assigned to the file. In response to a determination that the cluster identifier is not present in a data store, a set of candidate nearest neighbors is determined for the cluster identifier. For each candidate nearest neighbor, a set of existing cluster identifiers present in the data store is determined. For each existing cluster identifier, a set of member loci is determined. An edit distance between the sample locus and each of the member loci is determined. Finally, in response to a determination that a first locus in the set of member loci is within a threshold edit distance of the sample locus, one or more properties associated with the first locus is assigned to the file.

Claims

1. A system, comprising:

an interface configured to receive a file;

a processor configured to;

transform file contents using a space-filling curve;

down-sample the transformed file contents to generate a sample locus;

perform a hashing operation on the sample locus and assign a cluster identifier to the file based at least in part on a result of the hashing operation;

in response to a determination that the cluster identifier is not present in a data store, determine a set of candidate nearest neighbors for the cluster identifier;

for each candidate nearest neighbor included in the set of candidate nearest neighbors, determine a set of existing cluster identifiers present in the data store;

for each existing cluster identifier included in the set of existing cluster identifiers, determine a set of member loci;

determine an edit distance between the sample locus and each of the respective loci in the set of member loci; and

in response to a determination that at least a first locus included the set of member loci is within a threshold edit distance of the sample locus, assign one or more properties to the file based at least in part on properties associated with first locus, wherein at least one property assigned to the file is an indicator of maliciousness; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. The system of claim 1 wherein, in response to associating an indicator of maliciousness with the file, the processor is further configured to transmit a verdict that the file is malicious.

3. The system of claim 2 wherein the processor is configured to transmit the verdict to a device from which the file was received by the interface.

4. The system of claim 1 wherein the processor is further configured to transmit an indication of at least one of the properties associated with the file to a device from which the file was received by the interface.

5. The system of claim 1 wherein associating the one or more properties to the file includes assigning one or more properties to the cluster identifier.

6. The system of claim 5 wherein at least one of the one or more properties comprises a label, and wherein the label is generated by selecting one or more words from a set of candidate words provided by a plurality of engines.

7. The system of claim 1 wherein the cluster identifier is assigned to the file based at least in part on a locality-sensitive hashing operation.

8. The system of claim 1 wherein the space-filling curve comprises a Hilbert curve.

9. The system of claim 8 wherein the processor is further configured to select a size for the Hilbert curve based at least in part on a size of the received file.

10. The system of claim 8 wherein the processor is further configured to select a size for the Hilbert curve based at least in part on a determination of a threshold amount of negative space to be included in the curve.

11. The system of claim 1 wherein down-sampling the transformed file includes performing a blur operation.

12. The system of claim 1 wherein down-sampling the transformed file includes performing an anti-aliasing operation.

13. The system of claim 1 wherein down-sampling the transformed file includes performing a resize operation.

14. The method of claim 1 wherein the space-filling curve comprises a Hilbert curve.

15. The method of claim 14 further comprising selecting a size for the Hilbert curve based at least in part on a size of the received file.

16. The method of claim 14 further comprising selecting a size for the Hilbert curve based at least in part on a determination of a threshold amount of negative space to be included in the curve.

17. A method, comprising:

receiving a file;

transforming file contents using a space-filling curve;

down-sampling the transformed file contents to generate a sample locus;

performing a hashing operation on the sample locus and assigning a cluster identifier to the file based at least in part on a result of the hashing operation;

in response to a determination that the cluster identifier is not present in a data store, determining a set of candidate nearest neighbors for the cluster identifier;

for each candidate nearest neighbor included in the set of candidate nearest neighbors, determining a set of existing cluster identifiers present in the data store;

for each existing cluster identifier included in the set of existing cluster identifiers, determining a set of member loci;

determining an edit distance between the sample locus and each locus included in the set of member loci; and

in response to determining that at least a first locus included in the set of member loci is within a threshold edit distance of the sample locus, assigning one or more properties to the file based at least in part on properties associated with the first locus, wherein at least one property assigned to the file is an indicator of maliciousness.

18. The method of claim 17, further comprising transmitting a verdict that the file is malicious in response to associating an indicator of maliciousness with the file.

19. The method of claim 18 wherein the verdict is transmitted to a device from which the file was received.

20. The method of claim 17, further comprising transmitting an indication of at least one of the properties associated with the file to a device from which the file was received.

21. The method of claim 17 wherein associating the one or more properties to the file includes assigning one or more properties to the cluster identifier.

22. The method of claim 17 wherein at least one of the one or more properties comprises a label, and wherein the label is generated by selecting one or more words from a set of candidate words provided by a plurality of engines.

23. The method of claim 17 wherein the cluster identifier is assigned to the file based at least in part on a locality-sensitive hashing operation.

24. The method of claim 17 wherein down-sampling the transformed file includes performing a blur operation.

25. The method of claim 17 wherein down-sampling the transformed file includes performing an anti-aliasing operation.

26. The method of claim 17 wherein down-sampling the transformed file includes performing a resize operation.

27. A system, comprising:

an interface configured to receive a file;

a processor configured to;

transform file contents using a space-filling curve;

down-sample the transformed file contents to generate a sample locus;

assign a cluster identifier to the file based at least in part on the sample locus;

in response to a determination that the cluster identifier is not present in a data store, determine a set of candidate nearest neighbors for the cluster identifier;

for each candidate nearest neighbor included in the set of candidate nearest neighbors, determine a set of existing cluster identifiers present in the data store;

for each existing cluster identifier included in the set of existing cluster identifiers, determine a set of member loci;

determine an edit distance between the sample locus and each locus included in the set of member loci; and

in response to determining that at least a first locus included in the set of member loci is within a threshold edit distance of the sample locus, assign one or more properties to the file based at least in part on properties associated with the first locus, wherein at least one property assigned to the file is an indicator of maliciousness; and

a memory coupled to the processor and configured to provide the processor with instructions.

28. A method, comprising:

receiving a file;

transforming file contents using a space-filling curve;

down-sampling the transformed file contents to generate a sample locus;

assigning a cluster identifier to the file based at least in part on the sample locus;

in response to determining that the cluster identifier is not present in a data store, determining a set of candidate nearest neighbors for the cluster identifier;

for each candidate nearest neighbor included in the set of candidate nearest neighbors, determining a set of existing cluster identifiers present in the data store;

for each existing cluster identifier included in the set of existing cluster identifiers, determining a set of member loci;

determining an edit distance between the sample locus and each locus included in the set of member loci; and

in response to determining that at least a first locus included in the set of member loci is within a threshold edit distance of the sample locus, assigning one or more properties to the file based at least in part on properties associated with the first locus, wherein at least one property assigned to the file is an indicator of maliciousness.