Generation of API call graphs from static disassembly

• US 9,921,830 B2
• Filed: 05/27/2016
• Issued: 03/20/2018
• Est. Priority Date: 01/31/2014
• Status: Active Grant

• Current Assignee: Cylance Inc. (Blackberry Limited)
• Original Assignee: Cylance Inc. (Blackberry Limited)
• Inventors: Soeder, Derek A., Wolff, Matt
• Primary Examiner(s): Dao, Thuy
• Application Number:
  US15/167,581
• Publication Number:
  US 20160274909A1
• Time in Patent Office: 662 Days
• CPC Class Codes: G06F 11/34 Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
• CPC Class Codes: G06F 11/3414 Workload generation, e.g. scripts, playback
• CPC Class Codes: G06F 11/36 Preventing errors by testing or debugging software
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 8/53 Decompilation; Disassembly
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

Data is received that includes at least a portion of a program. Thereafter, entry point locations and execution-relevant metadata of the program are identified and retrieved. Regions of code within the program are then identified using static disassembly and based on the identified entry point locations and metadata. In addition, entry points are determined for each of a plurality of functions. Thereafter, a set of possible call sequences are generated for each function based on the identified regions of code and the determined entry points for each of the plurality of functions. Related apparatus, systems, techniques and articles are also described.

Claims

1. A method for inferring possible paths that at least a portion of a program can take during execution, the method comprising:

identifying, based on one or more entry points located in at least the portion of the program and execution-relevant metadata of the program, a region of code for disassembly within at least the portion of the program, the one or more entry points corresponding to one or more places within the at least the portion of the program at which an operating system or other program initiates execution, the execution-relevant metadata describing where code or execution-relevant data reside in the program;

generating, based on the identified region of code and the identified at least one entry point, a set of possible call sequences for at least one function at a corresponding entry point of the one or more entry points for the at least one function; and

generating a function call graph characterizing the generated set of possible call sequences to enable inferring possible paths that at least the portion of the program can take during execution;

wherein the set of possible call sequences comprises at least one application programming interface call.

2. The method of claim 1, further comprising:

identifying the one or more entry points located in at least the portion of the program, the identifying comprising scanning at least the portion of the program for pre-defined byte sequences.

3. The method of claim 1, further comprising:

retrieving the one or more entry points.

4. The method of claim 1, further comprising performing the disassembly, and wherein the disassembly comprises a static disassembly.

5. The method of claim 1, further comprising performing the disassembly, and wherein the disassembly comprises an emulation-augmented disassembly.

6. The method of claim 1, further comprising:

receiving data comprising the at least the portion of the program.

7. The method as in claim 1, further comprising:

generating the function call graph from a control flow graph characterizing a plurality of functions.

8. A system comprising:

at least one processor; and

at least one memory including instructions which, when executed by the at least one processor, result in the at least one processor performing operations comprising;

identifying, based on one or more entry points located in at least the portion of the program and execution-relevant metadata of the program, a region of code for disassembly within at least the portion of the program, the one or more entry points corresponding to one or more places within the at least the portion of the program at which an operating system or other program initiates execution, the execution-relevant metadata describing where code or execution-relevant data reside in the program;

generating, based on the identified region of code and the identified at least one entry point, a set of possible call sequences for at least one function at a corresponding entry point of the one or more entry points for the at least one function; and

generating a function call graph characterizing the generated set of possible call sequences to enable inferring possible paths that at least the portion of the program can take during execution;

wherein the set of possible call sequences comprises at least one application programming interface call.

9. The system of claim 8, wherein the operations further comprise:

identifying the one or more entry points located in at least the portion of the program, the identifying comprising scanning at least the portion of the program for pre-defined byte sequences.

10. The system of claim 8, wherein the operations further comprise:

retrieving the one or more entry points.

11. The system of claim 8, wherein the operations further comprise performing the disassembly, and wherein the disassembly comprises a static disassembly.

12. The system of claim 8, wherein the operations further comprise performing the disassembly, and wherein the disassembly comprises an emulation-augmented disassembly.

13. The system of claim 8, wherein the operations further comprise:

receiving data comprising the at least the portion of the program.

14. The system of claim 8, wherein the operations further comprise:

generating the function call graph from a control flow graph characterizing a plurality of functions.

15. A non-transitory computer-readable storage medium including instructions, which when executed by at least one processor, cause at least one processor to perform operations comprising:

identifying, based on one or more entry points located in at least the portion of the program and execution-relevant metadata of the program, a region of code for disassembly within at least the portion of the program, the one or more entry points corresponding to one or more places within the at least the portion of the program at which an operating system or other program initiates execution, the execution-relevant metadata describing where code or execution-relevant data reside in the program;

generating, based on the identified region of code and the identified at least one entry point, a set of possible call sequences for at least one function at a corresponding entry point of the one or more entry points for the at least one function; and

generating a function call graph characterizing the generated set of possible call sequences to enable inferring possible paths that at least the portion of the program can take during execution;

wherein the set of possible call sequences comprises at least one application programming interface call.

16. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise:

identifying entry points of at least the portion of the program by at least scanning at least the portion of the program for pre-defined byte sequences.

17. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise:

retrieving the one or more entry points.

18. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise performing the disassembly, and wherein the disassembly comprises a static disassembly.

19. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise performing the disassembly, and wherein the disassembly comprises an emulation-augmented disassembly.

20. The non-transitory computer-readable storage medium of claim 15, further comprising:

receiving data comprising the at least the portion of the program.

21. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise:

generating the function call graph from a control flow graph characterizing a plurality of functions.