System and method for automatic test-case generation for software

• US 7,644,398 B2
• Filed: 12/19/2002
• Issued: 01/05/2010
• Est. Priority Date: 12/19/2001
• Status: Active Grant

• Current Assignee: Reactive Systems, Inc.
• Original Assignee: Reactive Systems, Inc.
• Inventors: Sims, Steve T., Hansel, David, Cleaveland, Rance
• Primary Examiner(s): Yigdall; Michael J.
• Assistant Examiner(s): Wang; Ben C
• Application Number:
  US10/499,583
• Publication Number:
  US 20050160321A1
• Time in Patent Office: 2,574 Days
• Field of Search: None
• US Class Current: 717/135
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

Abstract

A method for generating test cases for software and a test case generator comprising a simulator that drives software under test from one input state to the next. The simulator is constrained by predetermined criteria to visit states that meet the criteria thus preserving computer resources. The states reached by the simulator are tested.

Claims

1. A method for generating tests from a software artifact, each test comprising a sequence of test vectors and each test vector comprising a set of input values for inputs of the software artifact, the method comprising:

identifying a set of coverage targets in the software artifact to be exercised by the tests;

executing the software artifact from an initial input state of the software artifact according to a set of initial tests, and correspondingly;

tracking which coverage targets are exercised during the initial tests;

saving those sequences of test vectors from the initial tests that exercise at least one of the coverage targets; and

saving, as a set of bridge states, one or more input states of the software artifact reached by those sequences of test vectors;

attempting to reach those coverage targets not exercised by the initial tests, based on probing from one or more of the bridge states, rather than from the initial input state of the software artifact, wherein probing from a given bridge state comprises;

resetting the software artifact to the bridge state;

generating a probing sequence of test vectors;

executing the software artifact by applying the probing sequence as inputs to the software artifact until a new input state of the software artifact is reached or until execution terminates; and

if the probing exercises a coverage target not previously covered, appending the probing sequence of test vectors to the sequence of test vectors associated with reaching the bridge state; and

saving as said tests the sequences of test vectors from the initial tests that exercised one or more of the coverage targets, along with any probing sequences that were appended during said probing from one or more of the bridge states.

2. The method of claim 1, wherein generating a probing sequence of test vectors comprises solving for constraints over one or more inputs of the software artifact that, if satisfied, will exercise a coverage target not covered by the initial tests, forming one or more test vectors corresponding to those constraints, and stepwise executing the software artifact according to those one or more test vectors applied as inputs to the software artifact.

3. The method of claim 2, wherein probing from the bridge state further comprises, if there are no constraints to solve for, randomly probing from the bridge state by generating one or more random test vectors, and stepwise executing the software artifact according to those one or more random test vectors applied as inputs to the software artifact.

4. The method of claim 3 further comprising loading a constraint file that defines constraints for one or more inputs of the software artifact, and correspondingly constraining the generated values of the randomly generated sequences of test vectors according to the constraint file.

5. The method of claim 1, further comprising recalculating the set of bridge states, in response to exercising a coverage target not covered by the initial tests based on probing from a given bridge state in the set of bridge states.

6. The method of claim 1, wherein saving those sequences of test vectors from the initial tests that exercise at least one of the coverage targets includes eliminating any redundant sequences of test vectors.

7. The method of claim 1, further comprising forming the initial tests at least in part by loading one or more predefined sequences of test vectors from a file.

8. The method of claim 1, further comprising forming the initial tests at least in part by randomly generating one or more sequences of test vectors.

9. The method of claim 8 further comprising loading a constraint file that defines constraints for one or more inputs of the software artifact, and correspondingly constraining the generated values of the randomly generated sequences of test vectors according to the constraint file.

10. The method of claim 1, wherein saving the set of bridge states comprises, for each input state of the software artifact reached during the initial tests, saving the values taken on by variables of the software artifact for that input state.

11. The method of claim 1, wherein saving as test data those sequences of test vectors from the initial tests that exercise at least one of the coverage targets includes saving outputs of the software artifact corresponding to those sequences of test vectors, and wherein saving as said tests comprises saving the test data, including the any appended probing sequences and their corresponding outputs.