Predicate-based test coverage and generation

• US 7,584,455 B2
• Filed: 05/12/2004
• Issued: 09/01/2009
• Est. Priority Date: 10/23/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ball, Thomas J.
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): Brophy; Matthew J
• Application Number:
  US10/844,710
• Publication Number:
  US 20050229044A1
• Time in Patent Office: 1,938 Days
• Field of Search: 717124-135, 714/38, 714/738
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3676 for coverage analysis

Abstract

Techniques and tools for achieving improved test coverage in a finite program state space are described, such as a technique for selecting a set of predicates, calculating a set of possible predicate values, calculating a subset of the set of possible predicate values, and generating a test for the computer program based at least in part on the subset. The subset comprises an approximation (e.g., an under-approximation) of reachable states in the program. A superset of the set of possible predicate values also can be calculated; the superset comprises an over-approximation of the reachable states in the program. In another aspect, a Boolean abstraction of a program is generated, reachability analysis is performed based at least in part on the Boolean abstraction, and symbolic execution is performed to generate test data. The reachability analysis can include computing lower and/or upper bounds of reachable observable states.

Claims

1. In a computer system, a method of performing test generation for a computer program, the method comprising:

generating a Boolean abstraction of the computer program, wherein the generating comprises selecting a set of predicates in the computer program and calculating a set of possible predicate values for plural statements in the computer program, wherein at least one of the predicates is derived from a conditional statement of the computer program;

performing a state reachability analysis of the computer program, wherein performing the state reachability analysis comprises identifying a subset of the set of possible predicate values for the plural statements in the computer program, wherein the subset comprises an approximation of reachable states in the computer program, and outputting a set of paths that covers states in the approximation of reachable states; and

performing symbolic execution, wherein the symbolic execution determines whether the paths are feasible and generates inputs for the computer program to cover a path when the oath is feasible.

2. The method of claim 1 further comprising, prior to calculating a set of possible predicate values for the plural statements in the computer program, generating a Boolean program based on the selected set of predicates.

3. The method of claim 1 wherein the approximation is an under-approximation of reachable states in the computer program.

4. The method of claim 3 further comprising calculating a superset of the set of possible predicate values, the superset comprising an over-approximation of reachable states in the computer program.

5. The method of claim 1 wherein the possible predicate values are possible Boolean values of the predicates.

6. The method of claim 1 wherein the generating a test comprises generating a test for a bytecode representation intermediate language.

7. A tangible computer-readable storage medium having stored thereon computer-executable instructions for performing a method of performing test generation for a computer program, the method comprising:

generating a Boolean abstraction of the computer program, wherein the generating comprises selecting a set of predicates in the computer program and calculating a set of possible predicate values for plural statements in the computer program, wherein at least one of the predicates is derived from a conditional statement of the computer program;

performing a state reachability analysis of the computer program, wherein performing the state reachability analysis comprises identifying a subset of the set of possible predicate values for the plural statements in the computer program, wherein the subset comprises an approximation of reachable states in the computer program, and outputting a set of paths that covers states in the approximation of reachable states; and

performing symbolic execution, wherein the symbolic execution determines whether the paths are feasible and generates inputs for the computer program to cover a path when the path is feasible.

8. In a computer system, a method of performing test generation for a computer program, the method comprising:

generating a Boolean abstraction of the computer program, comprising selecting a set of predicates in the computer program, and calculating a set of possible predicate values for plural statements in the computer program;

performing a state reachability analysis of the computer program, wherein the state reachability analysis comprises finding a set of reachable states of the computer program, the state reachability analysis based at least in part on the Boolean abstraction of the computer program; and

performing symbolic execution to generate test data for testing the computer program;

wherein the state reachability analysis further comprises computing an upper bound of reachable observable states of the computer program, comprising states with valid correlations between the predicates in the set of predicates;

wherein the state reachability analysis further comprises computing a lower bound of reachable observable states of the computer program, the lower bound comprising states reachable from states with valid correlations between the predicates in the set of predicates;

wherein the state reachability analysis further comprises outputting a set of paths that covers states in the upper bound of reachable states; and

wherein the symbolic execution comprises determining whether the paths are feasible and generates inputs for the computer program to cover a path when the path is feasible.

9. A tangible computer-readable storage medium having stored thereon computer-executable instructions for performing a method of performing test generation for a computer program, the method comprising:

generating a Boolean abstraction of the computer program, comprising selecting a set of predicates in the computer program, and calculating a set of possible predicate values for plural statements in the computer program;

performing a state reachability analysis of the computer program, wherein the state reachability analysis comprises finding a set of reachable states of the computer program, the state reachability analysis based at least in part on the Boolean abstraction of the computer program; and

performing symbolic execution to generate test data for testing the computer program;

wherein the state reachability analysis further comprises computing an upper bound of reachable observable states of the computer program, comprising states with valid correlations between the predicates in the set of predicates;

wherein the state reachability analysis further comprises computing a lower bound of reachable observable states of the computer program, the lower bound comprising the states reachable from states with valid correlations between the predicates in the set of predicates;

wherein the state reachability analysis further comprises outputting a set of paths that covers states in the upper bound of reachable states; and

wherein the symbolic execution comprises determining whether the paths are feasible and generates inputs for the computer program to cover a path when the path is feasible.

10. In a computer system, a method of modeling behavior of a computer program:

generating a Boolean abstraction of the computer program, wherein the generating comprises deriving an initial plurality of predicates;

wherein a predicate is derived from at least one of a conditional statement, an assertion, or a run-time safety check of the computer program;

performing a state reachability analysis of the computer program, wherein performing the state reachability analysis comprises defining an upper bound for a set of reachable observable states in the computer program wherein the reachable observable states comprise an evaluation of a state of the predicate at a statement in the computer program;

defining a lower bound for the set of reachable observable states in the computer program;

using the upper bound and the lower bound to form a static coverage metric of the computer program, which measures an amount of test coverage;

forming a behavior model of the computer program using the upper and lower bound, wherein forming the behavior model comprises outputting a set of oaths that covers states in the lower bound for the set of reachable observable states in the computer program;

performing symbolic execution, wherein the symbolic execution determines whether the paths are feasible and generates inputs for the computer program to cover a path out of the paths when the path is feasible and comprises performing test generation of reachable states based at least in part on the behavior model wherein a percentage of reachable observable states are covered by a generated test; and

adding new predicates to the initial plurality of predicates to increase percentage of reachable observable states covered by a generated test.

11. The method of claim 10 wherein the defining the lower bound comprises a pessimistic lower bound computation.

12. The method of claim 10 wherein the defining the lower bound comprises an optimistic lower bound computation.

13. The method of claim 10 further comprising performing test generation based at least in part on the behavior model.

14. The method of claim 13 wherein the test generation comprises generating tests for a subset of the reachable observable states defined by the lower bound prior to generating tests for other reachable observable states.

15. The method of claim 13 further comprising:

increasing the lower bound; and

using the increased lower bound in the test generation.

16. The method of claim 13 further comprising:

decreasing the upper bound; and

using the decreased upper bound in the test generation.

17. The method of claim 15 wherein the increasing the lower bound comprises refining Boolean abstraction for the computer program.

19. The method of claim 10 wherein performing test generation comprises:

1) generating paths to cover the lower bound for the set of reachable observable states in the computer program;

2) symbolically executing the generated paths to generate test data to cover the paths; and

3) running the computer program against the generated test data.

20. The method of claim 19 wherein the generating paths uses a depth first procedure to identify must transitions followed by zero or one may transition.

21. The method of claim 17 wherein adding new predicates to the plurality of predicates to increase percentage of reachable observable states covered by a generated test comprises adding a predicate that tracks a boundary condition that was not observed by the initial plurality of predicates.

22. The method of claim 10 wherein defining a upper bound for the set of reachable observable states in the computer program comprises choosing states wherein states corresponding to infeasible correlations between the predicates in the initial plurality of predicates are excluded.

23. The method of claim 10 wherein a reachable state is a state without an inherent logical contradiction between predicates.

18. A tangible computer-readable storage medium having stored thereon computer-executable instructions for performing a method of modeling behavior of a computer program:

generating a Boolean abstraction of the computer program, wherein the generating comprises deriving an initial plurality of predicates;

wherein a predicate is derived from at least one of a conditional statement, an assertion, or a run-time safety check of the computer program;

performing a state reachability analysis of the computer program, wherein performing the state reachability analysis comprises defining an upper bound for a set of reachable observable states in the computer program wherein the reachable observable states comprise an evaluation of a state of the predicate at a statement in the computer program;

defining a lower bound for the set of reachable observable states in the computer program;

using the upper bound and the lower bound to form a static coverage metric of the computer program, which measures an amount of test coverage;

forming a behavior model of the computer program using the upper and lower bound, wherein forming the behavior model comprises outputting a set of paths that covers states in the lower bound for the set of reachable observable states in the computer program;

performing symbolic execution, wherein the symbolic execution determines whether the paths are feasible and generates inputs for the computer program to cover a path out of the paths when the path is feasible and comprises performing test generation of reachable states based at least in part on the behavior model wherein a percentage of reachable observable states are covered by a generated test; and

adding new predicates to the initial plurality of predicates to increase percentage of reachable observable states covered by a generated test.