Method and system for generating test matrices for software programs

• US 20030208744A1
• Filed: 05/06/2002
• Published: 11/06/2003
• Est. Priority Date: 05/06/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bar-Lev, Dan, Schur, Liron, Arnon, Yoel, Amir, Erez
• Granted Patent: US 7,032,212 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

Methods and data structures are disclosed for a program module (e.g., API) test matrix generator system/process. The disclosed methods and data structures facilitate and carry out a streamlined, yet logically thorough test to verify the proper operation and/or expose errors within the program module under test. The method comprises breaking a set of input parameters to the program module into clusters of related parameters (i.e., parameters whose values affect each other'"'"'s validity regarding the output of the program module). Thereafter, a set of groups, representing different usages of a set of clustered parameters, are identified. After identifying the groups, a set of test calls (or a test matrix) is rendered for the program module. A covering set of test calls for a particular cluster comprises a sum of all logically/operationally distinct input value combinations rendered for each group. Such distinct input value combinations are rendered according to parameter equivalence classes defined for each parameter of each one of the cluster'"'"'s groups. An actual test call includes a representative set of parameter values for a particular selected combination of equivalence classes.

Claims

1. A method for generating a test model facilitating creating a set of test calls for submission to a program module that includes an interface definition identifying a set of input parameters, the method comprising the steps of:

defining equivalence classes for each one of the set of input parameters, each equivalence class defining a set of values wherein any one of the set of values is considered representative of the equivalence class with regard to verifying proper operation of the program module;

partitioning the set of input parameters into a set of one or more clusters, wherein input parameters assigned to differing clusters exhibit no cross-influence behavior between one another with regard to execution of the program module; and

generating, a set of groups for each cluster, each group defining a set of parameter elements corresponding to a particular usage of program module input parameters assigned to a cluster, and wherein the set of parameter elements are thereafter used to assign combinations of values to the input parameters in accordance with the parameter elements defined for the particular usage, and the assigned combinations of values are submitted in a call to the program module during a testing procedure.

2. The method of claim 1 wherein each parameter element comprises a set of equivalence classes for a particular parameter.

3. The method of claim 2 wherein a covering set of test combinations for a cluster is rendered from a summation, across all groups for a cluster, of distinct equivalence class combinations rendered from the equivalence classes defined for each parameter element.

4. The method of claim 2 wherein the union of a set of equivalence classes for a parameter element covers all potential values for a parameter corresponding to the parameter element in the context of a particular use.

5. The method of claim 4 wherein at least two equivalence classes of a set of equivalence classes for a particular parameter element overlap.

6. The method of claim 2 wherein a set of equivalence classes for a particular parameter element include at least one invalid equivalence class.

7. The method of claim 2 wherein at least two clusters are defined during the partitioning stage, and wherein a first set of parameters and a second set of parameters defined for respective first and second clusters are non-overlapping.

8. The method of claim 1 wherein a union of all equivalence classes for an input parameter does not represent all possible values for the input parameter.

9. The method of claim 1 wherein a union of all groups within the set of groups represents all contemplated modes of using the set of input parameters.

10. The method of claim 1 further comprising storing the test model as a data structure comprising:

for each cluster, a set of group elements corresponding to groups defined under each cluster, and

for each group element, a set of parameter elements, and

wherein each parameter element defines a set of equivalence class elements for a particular parameter to which the parameter element corresponds.

11. A method for testing a program module according to a test model comprising a set of one or more clusters for which a set of groups are defined, wherein each group defines a set of parameter elements corresponding to a particular usage of program module input parameters assigned to a cluster, and each parameter element comprises a set of equivalence classes for a parameter, the method comprising:

creating a set of calls to the program module, wherein the creating step includes, for a call within the set of calls, the further sub-step of;

first assigning a value to each one of a first set of parameters within a first cluster under test, the assigning step comprising the sub-steps of;

first selecting, for the first cluster, a group,

second selecting an equivalence class from each one of the set of parameter elements for the selected group, and

designating, for each selected equivalence class, a representative value within the selected equivalence class; and

submitting the set of calls containing the designated representative values to the program module under test.

12. The method of claim 11 wherein the first assigning step is performed in accordance with a cluster index value that maps to a particular combination of equivalence classes corresponding to a group and set of equivalence classes designated during the first and second selecting steps.

13. The method of claim 11 wherein an order in which particular combinations of equivalence classes corresponding to a group and set of equivalence classes designated during the first and second selecting steps is modified for differing runs of a test generator.

14. The method of claim 11 wherein the creating step further comprises the sub-step of second assigning a value to each one of a second set of input parameters orthogonal to the first set of parameters.

15. The method of claim 14 wherein the second set of input parameters correspond to a second cluster and wherein the second assigning sub-step comprises:

second assigning a value to each one of the second set of parameters within the second cluster, the second assigning step comprising the sub-steps of;

first selecting, for the second cluster, a group,

second selecting an equivalence class from each one of the set of parameter elements for the selected group, and

designating, for each selected equivalence class, a representative value within the selected equivalence class.

16. The method of claim 14 wherein the second set of input parameters consists of all the parameters that are not within the first cluster, and wherein the second assigning sub-step comprises assigning values to each one of the second set of input parameters from valid equivalence classes.

17. The method of claim 11 wherein a counter of created calls containing at least one value from an invalid equivalence class is maintained and wherein, once the counter reaches a particular count value, created calls containing at least a value representing an invalid parameter class are discarded without passing the call to the program module under test.

18. The method of claim 11 wherein a validity code is appended to each call rendered by the creating step, the validity code indicating the presence of at least one invalid value assigned to a parameter during the first assigning step.

19. The method of claim 11 further comprising executing the creating step multiple times on the first cluster, and modifying selection of a representative value for input parameters of the first cluster each one of the multiple times.

20. The method of claim 11 further comprising generating a reproduction token for a particular execution of the creating a set of calls step.

21. The method of claim 11 wherein the first assigning step comprises assigning values to a parameter that itself comprises embedded parameters, and wherein the equivalence classes for a parameter element expose equivalences classes for the embedded parameters.

22. The method of claim 11 wherein created calls containing at least a value representing an invalid parameter class are discarded without passing the call to the program module under test.

23. The method of claim 22 further comprising executing the creating step multiple times on the first cluster, and modifying selection of a representative value for input parameters of the first cluster each one of the multiple times.

24. The method of claim 11 further comprising an investigation step executed in association with the submitting step, wherein the investigation step is performed in response to detecting an error in a call, and wherein the investigation step performs a set of parameter substitutions to determine which one of the set of parameter equivalence classes caused the error.

25. A computer-readable medium including computer-executable instructions for testing a program module according to a test model comprising a set of one or more clusters for which a set of groups are defined, wherein each group defines a set of parameter elements corresponding to a particular usage of program module input parameters assigned to a cluster, and each parameter element comprises a set of equivalence classes for a parameter, the computer-executable instructions facilitating executing the steps of:

creating a set of calls to the program module, wherein the creating step includes, for a call within the set of calls, the further sub-step of;

first assigning a value to each one of a first set of parameters within a first cluster under test, the assigning step comprising the sub-steps of;

first selecting, for the first cluster, a group,

second selecting an equivalence class from each one of the set of parameter elements for the selected group, and

designating, for each selected equivalence class, a representative value within the selected equivalence class; and

submitting the set of calls containing the designated representative values to the program module under test.

26. The computer-readable medium of claim 25 wherein the first assigning step is performed in accordance with a cluster index value that maps to a particular combination of equivalence classes corresponding to a group and set of equivalence classes designated during the first and second selecting steps.

27. The computer-readable medium of claim 25 wherein an order in which particular combinations of equivalence classes corresponding to a group and set of equivalence classes designated during the first and second selecting steps is modified for differing runs of a test generator.

28. The computer-readable medium of claim 25 wherein the creating step further comprises the sub-step of second assigning a value to each one of a second set of input parameters orthogonal to the first set of parameters.

29. The computer-readable medium of claim 28 wherein the second set of input parameters correspond to a second cluster and wherein the second assigning sub-step comprises:

second assigning a value to each one of the second set of parameters within the second cluster, the second assigning step comprising the sub-steps of;

first selecting, for the second cluster, a group,

second selecting an equivalence class from each one of the set of parameter elements for the selected group, and

designating, for each selected equivalence class, a representative value within the selected equivalence class.

30. The computer-readable medium of claim 28 wherein the second set of input parameters consists of all the parameters that are not within the first cluster, and wherein the second assigning sub-step comprises assigning values to each one of the second set of input parameters from valid equivalence classes.

31. The computer-readable medium of claim 25 wherein a counter of created calls containing at least one value from an invalid equivalence class is maintained and wherein, once the counter reaches a particular count value, created calls containing at least a value representing an invalid parameter class are discarded without passing the call to the program module under test.

32. The computer-readable medium of claim 25 wherein a validity code is appended to each call rendered by the creating step, the validity code indicating the presence of at least one invalid value assigned to a parameter during the first assigning step.

33. The computer-readable medium of claim 25 further comprising executing the creating step multiple times on the first cluster, and modifying selection of a representative value for input parameters of the first cluster each one of the multiple times.

34. The computer-readable medium of claim 25 further comprising generating a reproduction token for a particular execution of the creating a set of calls step.

35. The computer-readable medium of claim 25 wherein the first assigning step comprises assigning values to a parameter that itself comprises embedded parameters, and wherein the equivalence classes for a parameter element expose equivalences classes for the embedded parameters.

36. The computer-readable medium of claim 25 wherein created calls containing at least a value representing an invalid parameter class are discarded without passing the call to the program module under test.

37. The computer-readable medium of claim 36 further comprising executing the creating step multiple times on the first cluster, and modifying selection of a representative value for input parameters of the first cluster each one of the multiple times.

38. The computer-readable medium of claim 25 further comprising an investigation step executed in association with the submitting step, wherein the investigation step is performed in response to detecting an error in a call, and wherein the investigation step performs a set of parameter substitutions to determine which one of the set of parameter equivalence classes caused the error.

39. A structure for maintaining a test model for guiding generating a set of calls to a program module, the structure comprising:

a cluster element specifying a set of group elements corresponding to groups defined under a cluster;

for each of the set of group elements, specifying a set of parameter elements; and

wherein each of the set of parameter elements defines a set of equivalence class elements for a particular parameter to which the parameter element corresponds.

40. The structure of claim 39 wherein each parameter element includes a parameter ID.

41. The structure of claim 39 wherein each parameter element includes a list of equivalence classes.

42. The structure of claim 41 wherein an equivalence class element within the list of equivalence classes includes a validity indicator for the equivalence class.

43. The structure of claim 41 wherein an equivalence class identified within the list structure includes a class structure type indicator facilitating automated selection of a representative value from the equivalence class.