Adaptive regression test selection within testing environments

• US 8,276,123 B1
• Filed: 01/09/2009
• Issued: 09/25/2012
• Est. Priority Date: 07/22/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Deng, Tao, Vasudeva, Sachin
• Primary Examiner(s): Tecklu, Isaac
• Assistant Examiner(s): Kabir, Mohammad
• Application Number:
  US12/351,457
• Time in Patent Office: 1,355 Days
• Field of Search: None
• US Class Current: 717/125
• CPC Class Codes: G06F 11/368 for test version control, e.g. updating test cases to a new software version
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites

Abstract

In general, techniques are described for intelligently selecting test cases within testing environments. Specifically, a computing device may include a user interface with which a user interacts to specify a safety level. The device also includes a control unit that determines those functions of source code that changed. Based on these changed functions, the control unit determines those functions of the source code not changed but impacted by the changes within a set distance. The control unit then selects, for each of these determined functions, one or more test cases in accordance with one or more test selection algorithms by adaptively applying these algorithms in order of decreasing safety assurances and increasing precision. The control unit further aggregates these selected test cases and implement the test cases to ensure the safety level with respect to a percentage of functional errors occurring within a software program compiled from the source code.

Claims

1. A method comprising:

determining, with a computing device, those functions of source code whose lines of code have changed between different versions of the software program;

determining, with the computing device, those of the functions of the source code whose lines of code have not changed but have been impacted by the changes based on dependency data and the determined changed functions, wherein the dependency data defines dependencies between the functions of the source code;

selecting, with the computing device, one or more test cases from a full set of test cases for each one of the changed and impacted functions in accordance with an adaptive test selection algorithm, wherein the adaptive test selection algorithm adaptively applies one or more test selection algorithms in order of decreasing safety assurances and increasing precision provided by each of the test selection algorithms until one of the test selection algorithms returns a number of test cases less than a maximum test case limit;

aggregating, with the computing device, the one or more test cases selected for each one of the changed and impacted functions to generate a final test set that includes a subset of test cases from the full set of test cases; and

executing, with the computing device, the final test set to ensure a given level of safety with respect to a percentage of functional errors that reside within a software program compiled from the source code, wherein the given level of safety requires the computing device to select the subset of test cases from the full set of test cases such that execution of the subset of test cases reveals at least the percentage of functional errors.

2. The method of claim 1, wherein selecting one or more test cases comprises selecting, based on coverage data, a subset of test cases from the full set of test cases in accordance with one of the test selection algorithms that selects the subset of test cases such that each test case of the subset uniquely exercises a current one of the changed and impacted functions.

3. The method of claim 2,

wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases,

wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code,

wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit, and

wherein selecting, based on the coverage data, the subset comprises:

determining, based on the coverage data, each of the function-level block combinations that is a unique block combination for the current function; and

selecting, for each of the unique block combination, one or more test cases that exercises the unique block combination.

4. The method of claim 3, wherein selecting the test case comprises:

listing the selected test cases in order of decreasing efficiency;

determining a number of test cases in the list;

comparing the number of test cases in the list to a maximum number of test cases allowed for each of the unique block combinations; and

selecting the maximum number of test cases allowed for each of the unique block combinations from the list such that the only the most efficient of the selected test cases of the list are selected.

5. The method of claim 4, wherein selecting, based on the coverage data, the subset further comprises:

determining a number of test cases included within the subset by adding together each of the one or more test cases that exercises each one of the unique block combinations of the current function;

determining whether the number of tests is greater than or equal to a maximum test case limit for functions;

decrementing the maximum number of test cases allowed for each of the unique block combinations upon determining the number of tests is greater than the maximum test case limit for functions; and

reiterating the selection using the decremented maximum number of test cases allowed for each of the unique block combinations.

6. The method of claim 1, wherein determining, with the computing device, those of the functions of the source code whose lines of code have not changed but have been impacted by the changes comprises:

accessing a graph data structure defined by the dependency data, wherein the graph data structure includes a plurality of nodes, and wherein each of the plurality of nodes represents either one of the functions or a variable of the source code;

traversing the nodes of the graph data structure to determine which of the nodes represents one of the determined changed functions;

traversing the nodes of the graph data structure to one or more impacted nodes that lie a set distance from the one of the nodes determined to represent the one of the changed functions; and

determining, based on which of the functions the impacted nodes represent, those of the functions of the source code whose lines of code have not changed but have been impacted by the change.

7. The method of claim 1, wherein selecting one or more test cases comprises selecting, based on coverage data, the subset of test cases from the full set of test cases in accordance with one of the test selection algorithms that selects the subset of test cases such that each test case of the subset exercises a current one of the changed and impacted functions.

8. The method of claim 7,

wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases,

wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code,

wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit, and

wherein selecting, based on the coverage data, the subset comprises:

determining whether one of the function-level block combinations exercises at least one block of the current function; and

selecting the test case in response to a determination that the one of the block combinations exercises at least one block of the current function.

9. The method of claim 1, wherein selecting one or more test cases comprises selecting, based on coverage data, the subset of test cases from the full set of test cases in accordance with one of the test selection algorithms that selects the subset of test cases such that the subset of test cases exercises the current function with little overlap.

10. The method of claim 9, wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases, wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code,

wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit, and

wherein selecting, based on the coverage data, the subset comprises:

determining whether one of the function-level block combinations associated with a test case of the subset represents a maximum block combination that provides a maximum coverage over blocks associated with the current function; and

selecting the test case in response to a determination that the one of the block combinations associated with the test case represents the maximum block combination.

11. The method of claim 1, further comprising:

presenting a user interface that displays a plurality of safety levels; and

receiving a selection from a user via the user interface that indicates one of the plurality of safety levels as the given level of safety.

12. The method of claim 11,

wherein presenting the user interface comprises presenting a user interface that displays a plurality of handles, wherein each handle corresponds to a different one of the plurality of safety levels, and wherein the plurality of handles include a handle indicated a major release, a handle indicating a minor release, a handle indicating a security release, and a handle indicating an internal release,

wherein receiving the selection comprises receiving the selection from the user via the user interface that indicates one of the plurality of handles, and

the method further comprising selecting one of the plurality of safety levels that corresponds to the indicated one of the plurality of handles as the given level of safety.

13. The method of claim 1, further comprising:

configuring the test selection algorithms and the maximum test case limit to tailor a precision and safety when selecting the final test set,

wherein executing the final test set comprises executing the final test set to detect a set of functional errors within a previous version of the software program compiled from a previous version of the source code,

comparing the detected set of functional errors to a known set of functional errors detected by way of previous execution of the full test set;

determining a level of safety based on the comparison of the set of functional errors and the known set of functional errors;

comparing the level of safety to the given level of safety; and

re-configuring the test selection algorithms and the maximum test case limit based on the comparison between the level of safety and the given level of safety so as to select the final test set such that the final test set ensures the given level of safety.

14. The method of claim 1, wherein the computing device comprises a regression server.

15. A method comprising:

determining, with a computing device, those functions of source code whose lines of code have changed between different versions of the software program;

determining, with the computing device, those of the functions of the source code whose lines of code have not changed but have been impacted by the changes based on dependency data and the determined changed functions, wherein the dependency data defines dependencies between the functions of the source code;

selecting, with the computing device, a subset of a full set of test cases that uniquely exercises every one of the changed and impacted functions based on coverage data, wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases, wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code, wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit; and

executing, with the computing device, the subset of the full set of test cases to ensure a given level of safety with respect to a percentage of functional errors that reside within a software program compiled from the source code, wherein the given level of safety requires the computing device to select the subset of test cases from the full set of test cases such that execution of the subset of test cases reveals at least the percentage of functional errors.

16. The method of claim 15, wherein selecting, based on the coverage data, the subset comprises:

determining, based on the coverage data, each of the function-level block combinations that is a unique block combination for the current function; and

selecting, for each of the unique block combination, one or more test cases that exercises the unique block combination.

17. The method of claim 16, wherein selecting the test case comprises:

listing the selected test cases in order of decreasing efficiency;

determining a number of test cases in the list;

comparing the number of test cases in the list to a maximum number of test cases allowed for each of the unique block combinations; and

selecting the maximum number of test cases allowed for each of the unique block combinations from the list such that the only the most efficient of the selected test cases of the list are selected.

18. The method of claim 17, wherein selecting, based on the coverage data, the subset further comprises:

determining a number of test cases included within the subset by adding together each of the one or more test cases that exercises each one of the unique block combinations of the current function;

determining whether the number of tests is greater than or equal to a maximum test case limit for functions;

decrementing the maximum number of test cases allowed for each of the unique block combinations upon determining the number of tests is greater than the maximum test case limit for functions; and

reiterating the selection of the subset of the full set of test cases using the decremented maximum number of test cases allowed for each of the unique block combinations.

19. A testing server comprising:

a control unit that includes one or more processors that execute an intelligent test selection module that determines those functions of source code whose lines of code have changed between different versions of the software program, determines those of the functions of the source code whose lines of code have not changed but have been impacted by the changes based on dependency data and the determined changed functions, wherein the dependency data defines dependencies between the functions of the source code, selects one or more test cases from a full set of test cases for each one of the changed and impacted functions in accordance with an adaptive test selection algorithm, wherein the adaptive test selection algorithm adaptively applies one or more test selection algorithms in order of decreasing safety assurances and increasing precision provided by each of the test selection algorithms until one of the test selection algorithms returns a number of test cases less than a maximum test case limit and aggregates the one or more test cases selected for each one of the changed and impacted functions to generate a final test set that includes a subset of test cases from the full set of test cases,

wherein the one or more processors also execute a regression harness that executes the final test set to ensure a given level of safety with respect to a percentage of functional errors that reside within a software program compiled from the source code, wherein the given level of safety requires the computing device to select the subset of test cases from the full set of test cases such that execution of the subset of test cases reveals at least the percentage of functional errors.

20. The testing server of claim 19, wherein the intelligent test selection module includes an a test selection engine that selects, based on the coverage data, a subset of test cases from the full set of test cases in accordance with one of the test selection algorithms that selects the subset of test cases such that each test case of the subset uniquely exercises a current one of the changed and impacted functions.

21. The testing server of claim 20, wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases, wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code, wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit, and

wherein the test selection engine further determines, based on the coverage data, each of the function-level block combinations that is a unique block combination for the current function and selects, for each of the unique block combination, one or more test cases that exercises the unique block combination.

22. The testing server of claim 21, wherein the test selection engine further lists the selected test cases in order of decreasing efficiency, determines a number of test cases in the list, compares the number of test cases in the list to a maximum number of test cases allowed for each of the unique block combinations and selects the maximum number of test cases allowed for each of the unique block combinations from the list such that the only the most efficient of the selected test cases of the list are selected.

23. The testing server of claim 22, wherein the test selection engine further determines a number of test cases included within the subset by adding together each of the one or more test cases that exercises each one of the unique block combinations of the current function, determines whether the number of tests is greater than or equal to a maximum test case limit for functions, decrements the maximum number of test cases allowed for each of the unique block combinations upon determining the number of tests is greater than the maximum test case limit for functions, and reiterates the selection using the decremented maximum number of test cases allowed for each of the unique block combinations.

24. The testing server of claim 19, wherein the intelligent test selection module includes an impact analyzer that accesses a graph data structure defined by the dependency data, wherein the graph data structure includes a plurality of nodes, and wherein each of the plurality of nodes represents either one of the functions or a variable of the source code, traverses the nodes of the graph data structure to determine which of the nodes represents one of the determined changed functions, traverses the nodes of the graph data structure to one or more impacted nodes that lie a set distance from the one of the nodes determined to represent the one of the changed functions, and determines, based on which of the functions the impacted nodes represent, those of the functions of the source code whose lines of code have not changed but have been impacted by the change.

25. The testing server of claim 19, wherein the intelligent test selection module includes a test selection engine that selects, based on coverage data, the subset of test cases from the full set of test cases in accordance with one of the test selection algorithms that selects the subset of test cases such that each test case of the subset exercises a current one of the changed and impacted functions.

26. The testing server of claim 25,

wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases,

wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code,

wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit, and

wherein the test selection engine further determines whether one of the function-level block combinations exercises at least one block of the current function, and selects the test case in response to a determination that the one of the block combinations exercises at least one block of the current function.

27. The testing server of claim 19, wherein the intelligent test selection module includes a test selection engine that selects, based on coverage data, the subset of test cases from the full set of test cases in accordance with one of the test selection algorithms that selects the subset of test cases such that the subset of test cases exercises the current function with little overlap.

28. The testing server of claim 27,

wherein the coverage data defines at least one function-level block combination for each test case of the full set of test cases,

wherein each of the function-level block combinations comprises data that associates a different one of the test cases with one or more blocks of a particular one of the functions of the source code,

wherein each of the blocks comprises a contiguous block of the source code having a single point of entry and a single point of exit, and

wherein the test selection engine further determines whether one of the function-level block combinations associated with a test case of the subset represents a maximum block combination that provides a maximum coverage over blocks associated with the current function, and selects the test case in response to a determination that the one of the block combinations associated with the test case represents the maximum block combination.

29. The testing server of claim 19, wherein the one or more processors also execute a user interface module that presents a user interface to i) display a plurality of safety levels and ii) receive a selection from a user via the user interface that indicates one of the plurality of safety levels as the given level of safety.

30. The testing server of claim 29, wherein the user interface further presents the user interface to i) display a plurality of pre-defined handles, wherein each of the handles corresponds to a different one of the plurality of safety levels, and wherein the plurality of handles include a first handle indicating a major software release, a second handle indicating a minor software release, a third handle indicating a security software release, and a fourth handle indicating an internal software release, and ii) receive the selection from the user via the user interface that indicates one of the plurality of handles, and

wherein the control unit stores data defining a corporate policy specifying one of the plurality of levels of safety for each of the major, minor, security and internal software releases and selects the corresponding one of the plurality of levels of safety as the given level of safety based on the selection indicating one of the plurality of handles.

31. The testing server of claim 19,

wherein the control unit includes a user interface module that presents a user interface with which a user may interact to configure the test selection algorithms and the maximum test case limit to tailor a precision and safety with which the final test set is selected,

wherein the regression harness further executes the final test set to detect a set of functional errors within a previous version of the software program compiled from a previous version of the source code,

wherein the control unit further compares the detected set of functional errors to a known set of functional errors detected by way of previous execution of the full test set, and determines a level of safety based on the comparison of the set of functional errors and the known set of functional errors,

wherein the user interface module presents via the user interface presents the level of safety, and

wherein the user interface module presents the user interface to enable the user to re-configure the test selection algorithms and the maximum test case limit based on a comparison between the presented level of safety and the given level of safety so as to select the final test set such that the final test set ensures the given level of safety.

32. A testing system comprising:

a test bench comprising a plurality of network devices;

a test selection database that stores dependency data and code change data;

a test case database that stores a full set of test cases;

a testing server communicatively coupled to the test bench, the test selection database and the test case database, wherein the testing server includes;

a control unit that comprises one or more processors that execute an intelligent test selection module that determines those functions of source code whose lines of code have changed between different versions of the software program based on the code change data, determines those of the functions of the source code whose lines of code have not changed but have been impacted by the changes based on the dependency data and the determined changed functions, wherein the dependency data defines dependencies between the functions of the source code, selects one or more test cases from the full set of test cases for each one of the changed and impacted functions in accordance with an adaptive test selection algorithm, wherein the adaptive test selection algorithm adaptively applies one or more test selection algorithms in order of decreasing safety assurances and increasing precision provided by each of the test selection algorithms until one of the test selection algorithms returns a number of test cases less than a maximum test case limit and aggregates the one or more test cases selected for each one of the changed and impacted functions to generate a final test set that includes a subset of test cases from the full set of test cases, and

wherein the one or more processors also execute a regression harness that executes the final test set within the plurality of network devices of the test bench to ensure a given level of safety with respect to a percentage of functional errors that reside within a software program compiled from the source code, wherein the given level of safety requires the computing device to select the subset of test cases from the full set of test cases such that execution of the subset of test cases reveals at least the percentage of functional errors.

33. A non-transitory computer-readable medium comprising instructions for causing a programmable processor to:

determine, with a computing device, those functions of source code whose lines of code have changed between different versions of the software program;

determine, with the computing device, those of the functions of the source code whose lines of code have not changed but have been impacted by the changes based on dependency data and the determined changed functions, wherein the dependency data defines dependencies between the functions of the source code;

select, with the computing device, one or more test cases from a full set of test cases for each one of the changed and impacted functions in accordance with an adaptive test selection algorithm, wherein the adaptive test selection algorithm adaptively applies one or more test selection algorithms in order of decreasing safety assurances and increasing precision provided by each of the test selection algorithms until one of the test selection algorithms returns a number of test cases less than a maximum test case limit;

aggregate, with the computing device, the one or more test cases selected for each one of the changed and impacted functions to generate a final test set that includes a subset of test cases from the full set of test cases; and

execute, with the computing device, the final test set to ensure a given level of safety with respect to a percentage of functional errors that reside within a software program compiled from the source code, wherein the given level of safety requires the computing device to select the subset of test cases from the full set of test cases such that execution of the subset of test cases reveals at least the percentage of functional errors.