Method and system for generating an efficient test suite from a domain description with given constraints

• US 20040255275A1
• Filed: 06/11/2003
• Published: 12/16/2004
• Est. Priority Date: 06/11/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Czerwonka, Jacek A.
• Granted Patent: US 7,278,135 B2
• Time in Patent Office: Days
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

Abstract

Provided is a system and method comprising a test suite generation mechanism for testing a domain (e.g., software program) via “black-box” testing. Parameters are defined, appropriate values for each are chosen, and via the system and method a suite of test cases are automatically generated that covers all N-way parameter combinations (e.g., pairs when N=2) while respecting any specified domain constraints. After receiving a model comprising the parameters and respective values to test, along with constraints in a form of logical predicates, the system and method produces the test cases. Based on the constraints, an algorithm removes invalid combinations in a first stage, and prevents any other invalid combinations from being used in a second stage during the test case generation process. A full set of statistically valuable test cases are thus efficiently and automatically generated, significantly improving testing while significantly reducing the resources needed to test.

Claims

1. In a computing environment, a method comprising:

receiving a plurality of parameters, and for each parameter, a value set of at least one value to test in conjunction with at least one other parameter value in an N- way combination wherein N is at least two; and

processing the plurality of parameters and the value set for each parameter into a suite of test cases, each test case comprising one value for each parameter, the suite automatically generated such that any valid N-way combination of values appears at least once in a test case.

2. The method of claim 1 wherein the N-way combination comprises a pair.

3. The method of claim 1 wherein the N-way combination is identified via a value received from an external source.

4. The method of claim 1 further comprising receiving at least one constraint, and wherein processing the parameters and the value set for each parameter into a suite of test cases comprises handling each constraint such that no test case comprises an invalid combination of parameter values.

5. The method of claim 1 wherein processing the parameters and the value set for each parameter into a suite of test cases comprises building a test case one value at a time.

6. The method of claim 1 wherein building a test case one value at a time comprises selecting a parameter, determining each valid value for that parameter with respect to any other value in a partial test case, and selecting a valid value as a selected value for that test case.

7. The method of claim 6 wherein selecting a valid value comprises evaluating the value against selection criteria.

8. The method of claim 7 wherein evaluating the value against selection criteria includes determining whether any one value for that parameter would, if used, cover more uncovered combinations of parameters than any other value.

9. The method of claim 7 wherein evaluating the value against selection criteria includes determining whether any value appears uncovered more than any other.

10. The method of claim 7 wherein evaluating the value against selection criteria includes determining whether any value has been used less often than another value.

11. The method of claim 1 further comprising, receiving at least one constraint, and parsing each constraint.

12. The method of claim 11 further comprising, providing a constraints language that can be parsed into a syntax tree.

13. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

14. In a computing environment, a method of constructing a suite of test cases, comprising:

selecting a parameter for which a value is needed in a partial test case being built;

obtaining a list comprising at least one value for the parameter which when added to the partial test case does not violate any constraint, the values arranged as a set of N-way comibinations with respect to values of other parameters;

applying selection criteria determine a selected value from the list; and

adding the selected value to the partial test case.

15. The method of claim 14 further comprising, testing whether the partial test case is made into a complete test case by adding the selected value, and if so, adding the complete test case to the test suite.

16. The method of claim 15 further comprising, covering the combinations in the set that were used in the test case by marking those combinations as used in at least one test case.

17. The method of claim 14 wherein applying selection criteria includes determining whether any one value for that parameter would, if used, cover more uncovered N-way combinations of parameter values in the set than any other value, and if so, selecting that value as the selected value.

18. The method of claim 17 wherein at least two values would, if used, tie for covering uncovered combinations of parameters, and further comprising, applying a tiebreaker to determine the selected value from the at least two values.

19. The method of claim 18 wherein applying the tiebreaker includes determining whether any value appears uncovered in the set more than any other.

20. The method of claim 18 wherein applying the tiebreaker includes determining whether any value has been used in less often in completed test cases than another value.

21. The method of claim 14 further comprising, receiving at least one constraint, and parsing each constraint.

23. The method of claim 14 further comprising, arranging the values as N-way combinations with respect to values of other parameters.

24. The method of claim 23 further comprising, removing any combinations from the set when the combination can be determined as invalid with respect to a constraint.

25. The method of claim 14 wherein obtaining a list comprises, determining whether no valid value exists, and if not, discarding the partial test case, rearranging the parameters, starting a new partial test case, selecting a new parameter, and obtaining a new list comprising at least one value for the new parameter which when added to the new partial test case does not violate any constraint

26. The method of claim 14 wherein the N-way combination comprises a pair.

27. The method of claim 14 wherein the N-way combination is identified via a value received from an external source.

28. A computer-readable medium having computer-executable instructions for performing the method of claim 14.

22. The method of claim 22 further comprising, providing a constraints language that can be parsed into a syntax tree.

29. In a computer system, a system comprising:

a test cases generation mechanism, the test cases generation mechanism configured to;

read a model comprising parameters and values to test for those parameters, and to process the model into a set of N-way combinations of values for the parameters; and

build a suite of test cases from the set by starting a partial test case, selecting a parameter, determining a valid value for that parameter by comparing the value against each other value in the partial test case with respect to any constraints, selecting a valid value and adding the selected value to the partial test case, and when adding the value makes the test case complete, adding the test case to a test suite, and tracking which N-way combinations are covered in the test case, the test suite complete when no valid combination in the set remains uncovered in at least one test case; and

a medium to which the test cases generation mechanism outputs the suite of test cases.

30. The system of claim 29 wherein the model includes at least one constraint, and further comprising a constraints parser that parses the constraint into a syntax tree.

31. In a computing environment, a system comprising:

means for receiving a plurality of parameters and parameter values to test in an N-way combination of values; and

means for processing the values in the N-way combinations into a suite of test cases, each test case comprising one value for each parameter, the suite automatically generated such that any valid N-way combination of values appears at least once in a test case.

32. A computer-readable medium having maintained thereon a data structure, comprising:

a suite of test cases;

each test case comprising a set of values for a set of parameters to be tested in N-way combinations of those values; and

each value added to each test case by automatic generation such that any value to be added to a test case that is a partial test case having at least one other value is evaluated with respect to each other value and any constraints, such that no invalid N-way combination of values is included in a test case.

33. The data structure of claim 32 wherein the test suite is configured so that every valid N-way combination is present in at least one test case.