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

• US 7,278,135 B2
• Filed: 06/11/2003
• Issued: 10/02/2007
• Est. Priority Date: 06/11/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Czerwonka, Jacek A.
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Francis; Mark P.
• Application Number:
  US10/459,893
• Publication Number:
  US 20040255275A1
• Time in Patent Office: 1,574 Days
• Field of Search: 717104-131
• 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, wherein processing the plurality of parameters and the value set for each parameter into a suite of test cases 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, and wherein selecting a valid value comprises determining whether any value appears uncovered more than any other.

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 5 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 anyone 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 has been used less often than another value.

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

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

28. The method of claim 1, wherein generating N-way combinations for all valid combinations of parameter values assigned to parameters comprises:

generating all possible N-way combinations for the parameter values; and

removing invalid N-way combinations.

12. A computer-readable storage medium having computer-executable instructions that when executed by a processor are configured to:

receive 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

process 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, wherein processing the plurality of parameters and the value set for each parameter into a suite of test cases 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, and wherein selecting a valid value comprises determining whether any value appears uncovered more than any other.

13. 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 combinations with respect to values of other parameters;

applying selection criteria to determine a selected value from the list, 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; and

adding the selected value to the partial test case.

14. The method of claim 13 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.

15. The method of claim 14 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.

16. The method of claim 13 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.

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

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

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

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

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

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

23. The method of claim 13 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.

24. The method of claim 13 wherein the N-way combination comprises a pair.

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

26. A computer-readable storage medium having computer executable instructions that when executed by a processor are configured to:

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

obtain 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 combinations with respect to values of other parameters;

apply selection criteria to determine a selected value from the list, 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; and

add the selected value to the partial test case.

27. A computer system comprising:

a processor;

one or more computer readable storage media comprising computer executable instructions that are configured to be executed by the processor, and that when executed by the processor, are configured to;

generate a plurality of parameter values, each parameter value being applicable to at least one parameter;

generate a plurality of N-way combinations where N parameters are each assigned a value from among the plurality of parameter values, and wherein generating a plurality of N-way combinations comprises generating N-way combinations for all valid combinations of parameter values assigned to parameters; and

generate a test case, by selecting a plurality of N-way combinations for the test case and where a sufficient number of parameters have been assigned parameter values to create a valid test case, wherein one or more of the N-way combinations arc selected from remaining untested N-way combinations to maximize the number of valid N-way combinations, from among the plurality of N-way combinations, in the test case.

29. In a computing environment, a method of creating a test suite comprising one or more test cases, wherein each test case comprises a plurality of parameters, each parameter having a parameter value, wherein parameter values for the test cases are selected such that all valid value combinations for different parameters in an N-way combination are represented in the test suite, where N is a value greater than two, the method comprising:

generating a plurality of parameter values, each parameter value being applicable to at least one parameter;

generating a plurality of N-way combinations where N parameters are each assigned a value from among the plurality of parameter values, and wherein generating a plurality of N-way combinations comprises generating N-way combinations for all valid combinations of parameter values assigned to parameters; and

generating a test case, by selecting a plurality of N-way combinations for the test case and where a sufficient number of parameters have been assigned parameter values to create a valid test case, wherein one or more of the N-way combinations are selected from remaining untested N-way combinations to maximize the number of valid N-way combinations, from among the plurality of N-way combinations, in the test case.