Discovering code and data in a binary executable program

• US 6,014,513 A
• Filed: 12/23/1997
• Issued: 01/11/2000
• Est. Priority Date: 12/23/1997
• Status: Expired due to Fees

• Current Assignee: Washington University In St Louis
• Original Assignee: University of Washington
• Inventors: Chen, John Bradley, Wolman, Alastair, Romer, Theodore H., Lee, Dennis Chua, Voelker, Geoffrey Michael, Wong, Wayne Anthony, Bershad, Brian N., Levy, Henry M.
• Primary Examiner(s): Hafiz, Tanq R.
• Assistant Examiner(s): Vo, Ted T.
• Application Number:
  US08/996,839
• Time in Patent Office: 749 Days
• Field of Search: 395/703, 395/704, 395/705, 395/709
• US Class Current: 717/131
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

A computer software tool used for automatically identifying code portions and data portions of a binary executable software program in which the code portions include machine instructions that are of arbitrary length. Software products are typically distributed as binary, executable files, which comprise a string of binary values. In general, an executable file has no structure or meaning, except as determined by its behavior when dynamically executed, one instruction at a time, by a digital computer. The software tool determines a set of addresses for any known code and data portions. The tool is then used to disassemble machine instructions, beginning at a starting address for each known code portion, to identify the target addresses of other code portions and other data portions. Other sections of the binary executable software program that could be either code or data are then analyzed to identify additionAL code and data portions. As new portions are identified, the steps are repeated, until no further code or data portions are identifiable. The binary executable software program may include a plurality of executable modules. The entry addresses for each executable module and any addresses for code portions and data portions referenced and identified by any debug address, any export address, and any relocation address is added to the set of addresses. The binary executable software program is then executed to dynamically identify other executable modules so that the set of addresses can be further extended.

Claims

1. A method for automatically identifying code portions and data portions in a binary executable software program, wherein the code portions comprise machine instructions that are of arbitrary length, comprising the steps of:

(a) determining a set of addresses in the binary executable software program that are for any known code portions and for any known data portions;

(b) disassembling machine instructions at a starting address for each known code portion, to identify a set of all possible control flow paths reachable from said starting address, and from the control flow paths that are thus identified, determining a set of target addresses so as to identify other code portions and other data portions;

(c) beginning with bytes of the binary executable software program located at any address that could be a starting point for either a code portion or a data portion, analyzing the bytes to determine if said bytes comprise a code portion; and

(d) reiteratively processing addresses in the binary executable software program that have not yet been identified as being for code portions and for data portions, by repeating steps (b) and (c), to identify other code portions and data portions in the binary executable software program until no further code portions and data portions are identifiable.

2. The method of claim 1, wherein the executable software program comprises a plurality of executable modules, said step of determining the set of addresses in the binary executable software program that are for any known code portions and for any known data portions comprising the step of identifying the plurality of executable modules.

3. The method of claim 2, wherein an executable module from the plurality of executable modules includes both code and data portions.

4. The method of claim 2, further comprising the steps of statically determining and adding an entry address for each of the plurality of executable modules, to said set of addresses, and of adding any addresses for code portions and data portions that are referenced and identified by any debug address, any export address, and any relocation address within the binary executable software program, to said set of addresses.

5. The method of claim 4, further comprising the steps of:

(a) executing the binary executable software program to dynamically identify other executable modules of the plurality of executable modules while the binary executable software program is running;

(b) determining and adding an entry address for each of the other executable modules, and any addresses for code portions and data portions, which are referenced and identified by any debug address, any export address, and any relocation address within the binary executable software program, to said set of addresses.

6. The method of claim 1, further comprising the step of removing any addresses for data portions that have been determined or identified from any unexamined address ranges for code portions that have been determined or identified.

7. The method of claim 1, wherein the step of disassembling machine instructions comprises the steps of:

(a) determining for each control flow path, whether a control flow instruction in the control flow path is direct or indirect; and

(b) following the control flow path to a target address if the instruction is direct, and determining the target address from a memory location or register referenced by the instruction, if the instruction is indirect.

8. The method of claim 1, wherein the step of disassembling machine instructions comprises the steps of:

(a) determining for each control flow path, whether each control flow instruction in the control flow path is conditional or unconditional; and

(b) for each control flow instruction in the control flow path;

(i) if the control flow instruction is conditional, identifying a following instruction as an implicit target address, and also identifying a target address that is referenced in a branch by the control flow instruction;

else

(ii) if the control flow instruction is unconditional, identifying a target address based on the control flow instruction.

9. The method of claim 1, wherein the step of analyzing the bytes comprises the steps of:

(a) determining if the bytes comprise a set of instruction sequences for a procedure prolog, and if so, identifying the bytes as a code portion; and

(b) determining if the bytes include a sequence of printable characters of at least a predefined length, and if so, identifying the bytes as a data portion.

10. The method of claim 9, wherein the step of analyzing the bytes further comprises the steps of:

(a) attempting to speculatively disassemble the bytes, based on a presumption that the bytes comprise a code portion; and

(b) classifying the bytes as an unknown portion of the binary executable software program if the attempt to speculatively disassemble the bytes results in at least one of the following;

(i) an internal logical inconsistency;

(ii) an undefined machine instruction;

(iii) a transfer into a known data portion;

(iv) a plurality of machine instructions that meets one of a plurality of predefined criteria indicating that the plurality of machine instructions are abnormal;

(v) a plurality of filler bytes;

(vi) a sequence of no operation instructions; and

(vii) more than a predefined minimum of machine instructions having a length greater than a predefined threshold.

11. The method of claim 1, wherein the step of reiteratively processing addresses in the binary executable software program that have not yet been identified as being for code portions and for data portions comprises the step of treating a starting address for each range of addresses not yet identified as a presumed new root address of either a code portion or a data portion before applying steps (b) and (c).

12. The method of claim 1, wherein the binary executable software program includes sections that are not identifiable as either a code portion or a data portion, said sections being left undisturbed and treated as unidentified portions of the binary executable software program.

13. The method of claim 1, further comprising the steps of:

(a) determining a compiler that was used to compile the binary executable software program; and

(b) identifying code portions and data portions of the binary executable software program, as a function of compiler specific parameters, based upon the compiler used.

14. A system for automatically identifying code portions and data portions in a binary executable software program, wherein the code portions comprise machine instructions that are of arbitrary length, comprising:

(a) a memory in which machine instructions and data are storable, said machine instructions including the machine instructions comprising the code portions of the binary executable software program as well as machine instructions comprising a software tool; and

(b) a processor, coupled to the memory, said processor executing the machine instructions comprising the software tool, which cause the processor to;

(i) load the binary software executable program into the memory and determine a set of addresses in the binary executable software program that are for any known code portions and for any known data portions;

(ii) disassemble the machine instructions comprising the binary executable software program at a starting address for each known code portion, to identify a set of all possible control flow paths reachable from said starting address, and from the control flow paths that are thus identified, determine a set of target addresses so as to identify other code portions and other data portions;

(iii) beginning with bytes of the executable software program located at any address in the binary executable software program that could be a starting point for either a code portion or a data portion, analyze the bytes to determine if said bytes comprise a code portion; and

(iv) reiteratively process addresses in the binary executable software program that have not yet been identified as being for code portions and for data portions, by repeating (ii) and (iii) above, to identify other code portions and data portions in the binary executable software program until no further code portions and data portions therein are identifiable.

15. The system of claim 14, wherein the executable software program comprises a plurality of executable modules, said machine instructions comprising the software tool causing the processor to identify the plurality of executable modules.

16. The system of claim 15, wherein an executable module from the plurality of executable modules includes both code and data portions.

17. The system of claim 15, wherein the machine instructions comprising the software tool cause the processor to statically determine and add an entry address for each of the plurality of executable modules to said set of addresses, and further cause the processor to add any addresses for code portions and data portions that are referenced and identified by any debug address, any export address, and any relocation address within the binary executable software program, to said set of addresses.

18. The system of claim 14, wherein the processor removes any addresses for data portions that have been determined or identified from any unexamined address ranges of code portions that have been determined or identified.

19. The system of claim 18, wherein the machine instructions comprising the software tool cause the processor to:

(a) execute the binary executable software program to dynamically identify other executable modules of the plurality of executable modules while the binary executable software program is running; and

(b) determine and add an entry address for each of the other executable modules, and any addresses for code portions and data portions, which are referenced and identified by any debug address, any export address, and any relocation address within the binary executable software program, to said set of addresses.

20. The system of claim 14, wherein to disassemble the instructions, the processor:

(a) determines for each control flow path, whether a control flow instruction in the control flow path is direct or indirect; and

(b) follows the control flow path to a target address if the instruction is direct, and determines the target address from a memory location or register referenced by the instruction, if the instruction is indirect.

21. The system of claim 14, wherein to disassemble the instructions, the processor:

(a) determines for each control flow path, whether each control flow instruction in the control flow path is conditional or unconditional; and

(b) for each control flow instruction in the control flow path;

(i) if the control flow instruction is conditional, identifies a following instruction as an implicit target address, and identifies a target address that is referenced in a branch by the control flow instruction; and

(ii) if the control flow instruction is unconditional, identifies a target address based on the control flow instruction.

22. The system of claim 14, wherein to analyze the bytes, the processor:

(a) determines if the bytes comprise a set of instruction sequences for a procedure prolog, and if so, identifies the bytes as a code portion; and

(b) determines if the bytes include a sequence of printable characters of at least a predefined length, and if so, identifies the bytes as a data portion.

23. The system of claim 22, wherein to analyze the bytes, the processor further:

(a) attempts to speculatively disassemble the bytes, based on a presumption that the bytes comprise a code portion; and

(b) classifies the bytes as an unknown portion of the binary executable software program if the attempt to speculatively disassemble the bytes results in at least one of the following;

(i) an internal logical inconsistency;

(ii) an undefined machine instruction;

(iii) a transfer into a known data portion;

(iv) a plurality of machine instructions that meets one of a plurality of predefined criteria indicating that the plurality of machine instructions are abnormal;

(v) a plurality of filler bytes;

(vi) a sequence of no operation instructions; and

(vii) more than a predefined minimum of machine instructions having a length greater than a predefined threshold.

24. The system of claim 14, wherein to reiteratively process addresses in the binary executable software program that have not yet been identified as being for code portions and for data portions, the processor treats a starting address for each range of addresses not yet identified as a presumed new root address of either a code portion or a data portion before applying (b)(ii) and (b)(iii).

25. The system of claim 14, wherein the binary executable software program includes sections that are not identifiable as either a code portion or a data portion, said sections being left undisturbed and treated as unidentified portions of the binary executable software program by the processor.

26. The system of claim 14, wherein the machine instructions comprising the software tool further cause the processor to:

(a) determine a compiler that was used to compile the binary executable software program; and

(b) identify code portions and data portions of the binary executable software program, as a function of compiler specific parameters that are based upon the compiler used.

27. A computer readable medium having computer-executable instructions, which when executed on a computer, cause the computer to automatically identify code portions and data portions in a binary executable software program, wherein the code portions comprise machine instructions that are of arbitrary length, said computer-executable instructions causing the computer to perform the steps of:

(a) determining a set of addresses in the binary executable software program that are for any known code portions and for any known data portions;

(b) disassembling machine instructions at a starting address for each known code portion, to identify a set of all possible control flow paths reachable from said starting address, and from the control flow paths that are thus identified, determining a set of target addresses so as to identify other code portions and other data portions;

(c) beginning with bytes of the executable software program located at any address in the binary executable software program that could be a starting point for either a code portion or a data portion, analyzing the bytes to determine if said bytes comprise a code portion; and

(d) reiteratively processing addresses in the binary executable software program that have not yet been identified as being for code portions and for data portions, by repeating steps (b) and (c), to identify other code portions and data portions in the binary executable software program until no further code portions and data portions are identifiable.

28. The computer readable medium of claim 27, wherein the executable software program comprises a plurality of executable modules, said step of determining the set of addresses in the binary executable software program that are for any known code portions and for any known data portions comprising the step of identifying the plurality of executable modules.

29. The computer readable medium of claim 28, wherein an executable module from the plurality of executable modules includes both code and data portions.

30. The computer readable medium of claim 28, having further computer-executable instructions for performing the steps of statically determining and adding an entry address for each of the plurality of executable modules, to said set of addresses, and of adding any addresses for code portions and data portions that are referenced and identified by any debug address, any export address, and any relocation address within the binary executable software program, to said set of addresses.

31. The computer readable medium of claim 30, having further computer-executable instructions for performing the steps of:

(a) executing the binary executable software program to dynamically identify other executable modules of the plurality of executable modules while the binary executable software program is running; and

(b) determining and adding an entry address for each of the other executable modules, and any addresses for code portions and data portions, which are referenced and identified by any debug address, any export address, and any relocation address within the binary executable software program, to said set of addresses.

32. The computer readable medium of claim 27, having further computer-executable instructions for performing the step of removing any addresses for data portions that have been determined or identified from any unexamined address ranges for code portions that have been determined or identified.

33. The computer readable medium of claim 27, wherein the step of disassembling machine instructions comprises the steps of:

(a) determining for each control flow path, whether a control flow instruction in the control flow path is direct or indirect; and

(b) following the control flow path to a target address if the instruction is direct, and determining the target address from a memory location or register referenced by the instruction, if the instruction is indirect.

34. The computer readable medium of claim 27, wherein the step of disassembling machine instructions comprises the steps of:

(a) determining for each control flow path, whether each control flow instruction in the control flow path is conditional or unconditional; and

(b) for each control flow instruction in the control flow path;

(i) if the control flow instruction is conditional, identifying a following instruction as an implicit target address, and identifying a target address that is referenced in a branch by the control flow instruction;

else

(ii) if the control flow instruction is unconditional, identifying a target address based on the control flow instruction.

35. The computer readable medium of claim 27, wherein the step of analyzing the bytes comprises the steps of:

(a) determining if the bytes comprise a set of instruction sequences for a procedure prolog, and if so, identifying the bytes as a code portion; and

(b) determining if the bytes include a sequence of printable characters of at least a predefined length, and if so, identifying the bytes as a data portion.

36. The computer readable medium of claim 35, wherein the step of analyzing the bytes further comprises the steps of:

(a) attempting to speculatively disassemble the bytes, based on a presumption that the bytes comprise a code portion; and

(b) classifying the bytes as an unknown portion of the binary executable software program if the attempt to speculatively disassemble the bytes results in at least one of the following;

(i) an internal logical inconsistency;

(ii) an undefined machine instruction;

(iii) a transfer into a known data portion;

(iv) a plurality of machine instructions that meets one of a plurality of predefined criteria indicating that the plurality of machine instructions are abnormal;

(v) a plurality of filler bytes;

(vi) a sequence of no operation instructions; and

(vii) more than a predefined minimum of machine instructions having a length greater than a predefined threshold.

37. The computer readable medium of claim 27, wherein the step of reiteratively processing addresses in the binary executable software program that have not yet been identified as being for code portions and for data portions comprises the step treating a starting address for each range of addresses not yet identified as a presumed new root address of either a code portion or a data portion before applying steps (b) and (c).

38. The computer readable medium of claim 27, wherein the binary executable software program includes sections that are not identifiable as either a code portion or a data portion, said sections being left undisturbed and treated as unidentified portions of the binary executable software program.

39. The computer readable medium of claim 27, having further computer-executable instructions for performing the steps of:

(a) determining a compiler that used to compile the binary executable software program; and

(b) identifying code portions and data portions of the binary executable software program, as a function of compiler specific parameters that are based upon the compiler used.