AUTOMATICALLY GENERATING TEST CASES FOR BINARY CODE
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification