System and method for automatic test-case generation for software

• US 20050160321A1
• Filed: 12/19/2002
• Published: 07/21/2005
• Est. Priority Date: 12/19/2001
• Status: Active Grant

• Current Assignee: Reactive Systems, Inc.
• Original Assignee: Reactive Systems, Inc.
• Inventors: Sims, Steve T., Cleaveland, Rance, Hansel, David
• Granted Patent: US 7,644,398 B2
• Time in Patent Office: Days
• US Class Current: 714/38
• 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 test cases for software comprising:

simulating software from an initial input state to a subsequent input state (output) by automatically processing input values to output values; and

generating a test to determine whether the subsequent input state (output) conforms to a predetermined criteria.

2. A method for generating test cases as in claim 1 wherein:

the software is an executable model of software.

3. A method for generating test cases as in claim 1 wherein:

the input values are constrained to predetermined criteria.

4. A method for generating test cases as in claim 3 wherein:

the predetermined criteria is one or more from a set-of values.

5. A method for generating test cases as in claim 3 wherein:

the predetermined criteria is provided by a user.

6. A method for generating test cases as in claim 1 wherein:

input states are stored in a data structure.

7. A method for generating test case as in claim 6 wherein:

the simulation can be restarted from a stored input state.

8. A method for generating test cases as in claim 1 wherein:

coverage of coverage targets is stored.

9. A method for generating test cases as in claim 1 wherein:

a current set of bridge states is maintained.

10. A method for generating test cases as in claim 1 wherein:

sets of interesting values are computed for input values.

11. A method for generating test cases as in claim 1 wherein:

input values are constrained for a bridge state wherein if satisfied, a new coverage target is covered.

12. A method for generating test cases as in claim 1 wherein:

the test maximizes the number of coverage targets.

13. A method for automating test case generation for software comprising:

simulating software;

automatically constructing internal data structures for storing states of the software reached during simulation;

initializing a counter to track coverage information;

assembling data type information for the software states;

constraints for the software states;

loading test data;

testing the software states using the simulator; and

computing coverage information for the test data.

14. A method for automating test case generation as in claim 13 wherein:

the test data is a previously constructed test suite that is converted into an internal data structure.

15. A method for automating test case generation as in claim 13 wherein:

the test data is semi-randomly generated.

16. A method for automating test case generation as in claim 13 wherein:

bridge states are identified and used to determine software states to reach uncovered targets.

17. A method for automating test case generation as in claim 16 wherein:

the software states are determined from the bridges states by computing a set of constraints involving input values whose solution guarantees coverage of a target.

18. A method for automating test case generation as in claim 16 wherein:

the software states are determined from the bridge states by using probes to identifying uncovered targets.

19. A method for automating test case as in claim 13 wherein:

the test data is both semi-randomly generated and used from a previously constructed test suite.

20. A method for automating test case as in claim 13 wherein:

the test data is both semi-randomly generated and determined from bridge states.

21. A method for automating test case as in claim 13 wherein:

the test data is both determined from bridge states and from a previously constructed test suite.

22. A method for automating test case as in claim 13 wherein:

the test data is determined from bridge states, is semi-randomly generated and is from a previously constructed test suite.

23. A method for automating test case as in claim 13 wherein:

a specific percentage of coverage targets covered can be specified by a user.

24. A method for automating test case as in claim 13 wherein:

a user may define weighted values to constraints.

25. A method for automating test case as in claim 13 wherein:

a user can terminate the generation of test cases upon satisfaction of a predetermined criteria.

26. A method for automating test case as in claim 22 wherein:

the test case generation is terminated upon reaching a specified percentage of coverage.

27. A method for automating test case as in claim 22 wherein:

the test case generation is terminated upon reaching a predetermined number of generated tests.

28. A method for automating test case as in claim 22 wherein:

the test case generation is terminated upon reaching a predetermined length of generated tests.

29. An automated software test case generator comprising:

a simulator for automatically simulating software from an initial state to a subsequent input (output) state; and

a test case generator that constructs tests consisting of a sequence of input/output pairs generated by the software simulation which outputs match those stored in a test.

30. A test case generator as in claim 29 wherein:

the software is an executable model of software.

31. A test case generator as in claim 29 wherein:

the test case generator is constrained by predetermined criteria.

32. A test case generator as in claim 29 wherein:

a counter is used to track coverage information.