Automatically generating test cases for binary code

• US 7,873,945 B2
• Filed: 06/29/2007
• Issued: 01/18/2011
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tan, Lin, Musuvathi, Madanlal
• Primary Examiner(s): Pham; Thomas K
• Application Number:
  US11/770,905
• Publication Number:
  US 20090007077A1
• Time in Patent Office: 1,299 Days
• Field of Search: 717/124
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites

Abstract

The present invention extends to methods, systems, and computer program products for automatically generating test cases for binary code. Embodiments of the present invention can automatically generate test inputs for systematically covering program execution paths within binary code. By monitoring program execution of the binary code on existing or random test cases, branch predicates on execution paths can be dynamically inferred. These inferred branch predicates can then be used to drive the program along previously unexplored execution paths, enabling the learning of further execution paths. Embodiments of the invention can be used in combination with other analysis and testing techniques to provide better test coverage and expose program errors.

Claims

1. At a computer system, a method for automatically generating test cases for testing binary code, the method comprising:

an act of accessing a portion of binary code that has a specified number of input variables;

an act of analyzing the portion of binary code to identify the locations of conditional statements within the portion of binary code, each conditional statement including a branch predicate, the branch predicate used to determine the direction of the branch execution within the portion of binary code;

an act of inserting instrumentation probes into the portion of binary code to probe input values supplied to the branch predicates of the identified conditional statements, each inserted instrumentation probe inserted into the portion of binary code at a location preceding the location of an identified conditional statement, each instrumentation probe including a probe predicate function configured to calculate a value for the branch predicate that is to be used in the conditional statement it precedes;

for each identified conditional statement;

an act of submitting a plurality of input test cases at least equal to the number of specified input variables to the portion of binary code plus one;

for each input test case;

an act of submitting a random input value for each different variable of the specified number of variables;

an act of receiving an output value calculated by the probe predicate function preceding the conditional statement, the output value having been generated from processing one or more of the input values;

an act of using the input values included in each of the plurality of input test cases and the corresponding output values calculated by the probe predicate function to infer an equation representing the variable portion of the branch predicate of the conditional statement; and

an act of refining further input test cases to the portion of binary code to include input values that cause the conditional statement to take a path to further executable instructions, and not to exit the program, based on the inferred equation such that executable instructions after the conditional statement can be more efficiently tested using the further input cases.

2. The method as recited in claim 1, further comprising:

an act of analyzing the portion of binary code to identify relations associated with conditional statements within the portion of binary code.

3. The method as recited in claim 2, wherein the act of identify relations associated with conditional statements comprises an act of identifying a relation selected from among:

greater than, greater than or equal to, less than, less than or equal to, equal to, and not equal to.

4. The method as recited in claim 1, wherein the act of inserting instrumentation probes into the portion of binary code to probe input values supplied to the branch predicates of the identified conditional statements comprises an act of inserting an instrumentation probe that indicates the relation associated with the branch predicate of an identified conditional statement.

5. The method as recited in claim 4, wherein the act of inserting instrumentation probes into the portion of binary code to probe input values supplied to the branch predicates of the identified conditional statements comprises an act of inserting instrumentation probes configured to perform a mathematical operation on the input values supplied to the branch predicates based on the associated relations, the results of the mathematical operation resulting in the output for the instrumentation probe.

6. The method as recited in claim 1, wherein the act of receiving an output value calculated by the probe predicate function preceding the conditional statement comprises an act of receiving an output value and an indication of the relation associated with the conditional statement

7. The method as recited in claim 6, further comprising:

an act of combining the inferred equation with the identified relation to formulate a branch predicate for the conditional statement.

8. The method as recited in claim 7, further comprising:

an act of adding the formulated branch predicate to a predicate tree for the portion of binary code.

9. The method as recited in claim 1, where the act of inferring an equation representing the variable portion of the branch predicate of the conditional statement comprises an act of solving a linear equation representing the variable portion of the branch predicate based on the input values and corresponding output values.

10. The method as recite in claim 1, further comprising:

an act of decomposing an array of input values into a corresponding number of linear equations prior to inferring an equation;

11. The method as recited in claim 1, wherein the an act of refining further input test cases to the portion of binary code comprises an act of refining further input test cases to the portion of binary code based on a predicate tree that has a predicate branch including the inferred equation.

12. At a computer system, a method for automatically generating test cases for testing binary code for memory buffer overruns, the method comprising:

an act of accessing an portion of binary code that has a specified number of input variables;

an act of analyzing the portion of binary to identify any memory allocation instructions, to identify any memory access instructions, and to identify any memory deallocation instructions within the binary code;

an act of inserting instrumentation probes into the portion of binary code to probe memory buffer overruns in the portion of binary code, including;

for any identified memory allocation instructions inserting an instrumentation probe for the address and length of the allocated memory region;

for any identified memory access instructions inserting an instrumentation probe for the address to be accessed; and

for any identified memory deallocation instructions inserting a instrumentation probe for the address freed;

an act of submitting a plurality of input test cases to the portion of binary code, each input test case including a plurality of input values;

for each input test case;

an act of instrumentation probes monitoring memory allocation and memory deallocation based on the input values; and

an act of instrumentation probes determining the memory region a memory access instruction is to access by doing a range search based on the input values;

an act of using the input values included in each of the plurality of input test cases and the regions of memory that are to be accessed to infer locations for potential memory buffer overruns; and

an act of refining further input test cases to the portion of binary code to include input values configured to cause buffer overruns at the inferred locations so as to test the portion of binary code for buffer overruns.

13. A computer program product for use at a computer system, the computer program product for implementing a method for automatically generating test cases for testing binary code, the computer-program product comprising one or more computer-readable media having stored thereon computer-executable instructions that, when executed at a processor, cause the computer system to perform the following:

access a portion of binary code that has a specified number of input variables;

analyze the portion of binary code to identify the locations of conditional statements within the portion of binary code, each conditional statement including a branch predicate, the branch predicate used to determine the direction of the branch execution within the portion of binary code;

insert instrumentation probes into the portion of binary code to probe input values supplied to the branch predicates of the identified conditional statements, each inserted instrumentation probe inserted into the portion of binary code at a location preceding the location of an identified conditional statement, each instrumentation probe including a probe predicate function configured to calculate a value for the branch predicate that is to be used in the conditional statement it precedes;

for each identified conditional statement;

submit a plurality of input test cases at least equal to the number of specified input variables to the portion of binary code plus one;

for each input test case;

submit a random input value for each different variable of the specified number of variables;

receive an output value calculated by the probe predicate function preceding the conditional statement, the output value having been generated from processing one or more of the input values;

use the input values included in each of the plurality of input test cases and the corresponding output values calculated by the probe predicate function to infer an equation representing the variable portion of the branch predicate of the conditional statement; and

refine further input test cases to the portion of binary code to include input values that cause the conditional statement to take a path to further executable instructions, and not to exit the program, based on the inferred equation such that executable instructions after the conditional statement can be more efficiently tested using the further input cases.

14. The computer program product of claim 13, furthering comprising computer-executable instructions that, when executed, cause the computer system to analyze the portion of binary code to identify relations associated with conditional statements within the portion of binary code.

15. The computer program product of claim 13, wherein computer-executable instructions that, when executed, cause the computer system to insert instrumentation probes into the portion of binary code to probe input values supplied to the branch predicates of the identified conditional statements comprise computer-executable instructions that, when executed, cause the computer system to insert an instrumentation probe that indicates the relation associated with the branch predicate of an identified conditional statement.

16. The computer program product of claim 15, wherein computer-executable instructions that, when executed, cause the computer system to insert instrumentation probes into the portion of binary code to probe input values supplied to the branch predicates of the identified conditional statements comprise computer-executable instructions that, when executed, cause the computer system to insert instrumentation probes configured to perform a mathematical operation on the input values supplied to the branch predicates based on the associated relations, the results of the mathematical operation resulting in the output for the instrumentation probe.

17. The computer program product of claim 13, wherein computer-executable instructions that, when executed, cause the computer system to receive an output value calculated by the probe predicate function preceding the conditional statement comprise computer-executable instructions that, when executed, cause the computer system to receive an output value and an indication of the relation associated with the conditional statement.

18. The computer program product of claim 17, furthering comprising computer-executable instructions that, when executed, cause the computer system to combining the inferred equation with the identified relation to formulate a branch predicate for the conditional statement.

19. The computer program product of claim 18, furthering comprising computer-executable instructions that, when executed, cause the computer system to add the formulated branch predicate to a predicate tree for the portion of binary code.

20. The computer program product of claim 13, wherein computer-executable instructions that, when executed, cause the computer system to infer an equation representing the variable portion of the branch predicate of the conditional statement comprise computer-executable instructions that, when executed, cause the computer system to solve a linear equation representing the variable portion of the branch predicate based on the input values and corresponding output values.