Determining the similarity of binary executables

Patent metadata

Field	Value
Publication number	US-10685113-B2
Application number	US-201715676329-A
Country	US
Kind code	B2
Filing date	Aug 14, 2017
Priority date	Jun 28, 2017
Publication date	Jun 16, 2020
Grant date	Jun 16, 2020

Abstract

In some implementations, a computing device can determine the similarity of binary executables. For example, the computing device can receive an application, including a binary executable. The computing device can generate function signatures for the functions called within the binary executable. The computing device can generate a locality sensitive hash value for the application based on the function signatures. The computing device can group applications based on the locality sensitive hash value generated for each application. The computing device can compare the function signatures of the binary executables of the applications within a group to determine the similarity of the applications. If two applications have binary executables that are over a threshold percentage of similarity, the two applications can be identified as clones of each other.

First claim

What is claimed is:

1. A method comprising:
receiving, by a computing device, an application executable;
generating, by the computing device, one or more first function signatures for functions called within the application executable;
generating, by the computing device, a first value for the application executable based on the one or more first function signatures;
grouping, by the computing device, the received application executable with one or more other application executables into an application group based on the first value;
comparing, by the computing device, the received application executable to the one or more other application executables in the application group; and
determining, by the computing device, based upon the comparing, that the received application executable and at least one of the one or more other application executables are functionally the same application executable.

2. The method of claim 1 , wherein generating function signatures includes:
determining opcodes within the application executable corresponding to a particular function;
combining the opcodes to generate a string of opcodes; and
generating a hash value based on the string of opcodes.

3. The method of claim 1 , wherein the first value is a locality sensitive hash value that is generated by performing a minimum hash function.

4. The method of claim 1 , wherein each application executable in the application group corresponds to the same first value.

5. The method of claim 1 , wherein comparing the received application executable to the one or more other applications in the application group includes generating a Jaccard coefficient based on a first set of function signatures corresponding to the received application executable and a second set of function signatures corresponding to a selected application executable selected from the application group.

6. The method of claim 5 , further comprising:
determining whether the Jaccard coefficient is above a threshold value; and
determining that the received application executable and the at least one of the one or more other application executables are functionally the same application executable when the Jaccard coefficient is above the threshold value.

7. The method of claim 1 , further comprising:
generating a graphical user interface that identifies application executables that are functionally the same;
causing the graphical user interface to be presented by a client device; and
allowing selection and deletion of one or more functionally similar application executables.

8. A non-transitory computer readable medium including one or more sequences of instructions that, when executed by one or more processors, causes the processors to perform operations comprising:
receiving, by a computing device, an application executable;
generating, by the computing device, one or more first function signatures for functions called within the application executable;
generating, by the computing device, a first value for the application executable based on the one or more first function signatures;
grouping, by the computing device, the received application executable with one or more other application executables into an application group based on the first value;
comparing, by the computing device, the received application executable to the one or more other application executables in the application group; and
determining, by the computing device, based upon the comparing, that the received application executable and at least one of the one or more other application executables are functionally the same application executable.

9. The non-transitory computer readable medium of claim 8 , wherein the instructions that cause generating function signatures include instructions that cause:
determining opcodes within the application executable corresponding to a particular function;
combining the opcodes to generate a string of opcodes; and
generating a hash value based on the string of opcodes.

10. The non-transitory computer readable medium of claim 8 , wherein the first value is a locality sensitive hash value that is generated by performing a minimum hash function.

11. The non-transitory computer readable medium of claim 8 , wherein each application executable in the application group corresponds to the same first value.

12. The non-transitory computer readable medium of claim 8 , wherein the instructions that cause comparing the received application executable to the one or more other applications in the application group include instructions that cause generating a Jaccard coefficient based on a first set of function signatures corresponding to the received application executable and a second set of function signatures corresponding to a selected application executable selected from the application group.

13. The non-transitory computer readable medium of claim 12 , wherein the instructions cause the processors to perform operations comprising:
determining whether the Jaccard coefficient is above a threshold value; and
determining that the received application executable and the at least one of the one or more other application executables are functionally the same application executable when the Jaccard coefficient is above the threshold value.

14. The non-transitory computer readable medium of claim 8 , wherein the instructions cause the processors to perform operations comprising:
generating a graphical user interface that identifies applications that are functionally the same; and
causing the graphical user interface to be presented by a client device.

15. The non-transitory computer readable medium of claim 8 , wherein each application executable in the application group corresponds to the same locality sensitive hash value.

16. A system comprising:
one or more processors; and
a non-transitory computer readable medium including one or more sequences of instructions that, when executed by the one or more processors, causes the processors to perform operations comprising:
receiving, by a computing device, an application executable;
generating, by the computing device, one or more first function signatures for functions called within the application executable;
generating, by the computing device, a first value for the application executable based on the one or more first function signatures;
grouping, by the computing device, the received application executable with one or more other application executables into an application group based on the first value;
comparing, by the computing device, the received application executable to the one or more other application executables in the application group; and
determining, by the computing device, based upon the comparing, that the received application executable and at least one of the one or more other application executables are functionally the same application executable.

17. The system of claim 16 , wherein the instructions that cause generating function signatures include instructions that cause:
determining opcodes within the application executable corresponding to a particular function;
combining the opcodes to generate a string of opcodes; and
generating a hash value based on the string of opcodes.

18. The system of claim 16 , wherein the first value is a locality sensitive hash value that is generated by performing a minimum hash function.

19. The system of claim 16 , wherein the instructions that cause comparing the received application executable to the one or more other applications in the a

Assignees

• Apple Inc

Inventors

• Agarwal Ashish
• Peng Fei
• Deng Zhui

Classifications

• G06F21/564 Primary

  by virus signature recognition · CPC title

• G06F2221/033

  Test or assess software · CPC title

• G06F21/566 Primary

  Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities · CPC title