Method and apparatus for prioritizing software tests

• US 7,028,290 B2
• Filed: 04/29/2002
• Issued: 04/11/2006
• Est. Priority Date: 04/29/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thiagarajan, Jayaraman, Srivastava, Amitabh
• Primary Examiner(s): Zhen, Wei Y.
• Assistant Examiner(s): RAMPURIA, SATISH
• Application Number:
  US10/133,427
• Publication Number:
  US 20030204836A1
• Time in Patent Office: 1,443 Days
• Field of Search: 717124-135, 717/101, 717/115, 714/38, 714/724, 716/2, 716/4, 712/227
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3676 for coverage analysis

Abstract

A computer system and method is provided for prioritizing software tests. Software tests are prioritized based on coverage indicators for the software tests and an indication of impacted areas of the software. Each of the coverage indicators indicates which portions of the software are executed for a respective one of the software tests. The portions of the software include at least one of a plurality of blocks. The indication of impacted areas of the software indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software. A prioritized list of software tests is output. The prioritized list includes at least one test sequence.

Claims

1. A computer-implemented method of prioritizing software tests, the method comprising the steps of:

(A) prioritizing software tests for software to be tested based on coverage indicators for the software tests and an indication of impacted areas of the software, each of the coverage indicators indicating which portions of the software are executed for a respective one of the software tests; and

(B) generating a prioritized list of the software tests, the prioritized list including at least one test sequence, wherein;

the portions of the software include at least one of a plurality of blocks, and

the indication of impacted areas of the software indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software, wherein the step (A) comprises the steps of;

(A1) computing a weight for each of the software tests, the weight being based on a number of the new and the modified blocks that are indicated as being executed by each respective one of the software tests;

(A2) selecting a first test having a maximum weight among the software tests, wherein when two or more of the software tests have the same computed maximum weight, the step (A2) further comprises the steps of;

(A2a) determining which one of the two or more of the software tests has a maximum overall coverage of the software to be tested; and

(A2b) selecting as the first test, the one of the two or more software tests having the maximum overall coverage of the software to be tested; and

(A3) adding the selected first test to a current test sequence.

2. The computer-implemented method of claim 1, wherein the blocks include blocks of binary code and each of the blocks has a single entry point and a single exit point.

3. The computer-implemented method of claim 1, wherein a coverage indicator of a new block indicates that the respective one of the software tests executes the new block when a predecessor block and a successor block of the new block have been indicated as being executed by the respective one of the software tests.

4. The computer-implemented method of claim 1, wherein a coverage indicator of a new block indicates that the respective one of the software tests executes the new block when a successor block of the new block has been indicated as being executed by the respective one of the software tests.

5. The computer-implemented method of claim 1, wherein:

the step (A) comprises determining whether ones of the modified and the new blocks exist that are not indicated as being executed by any of the software tests, and

the computer-implemented method further comprises the step (C) of generating a list of the ones of the modified and the new blocks that are not indicated as being executed by any of the software tests.

6. The computer-implemented method of claim 1, wherein the step (A) further comprises the steps of:

(A4) removing from consideration the selected first software test and any of the new and the modified blocks that are indicated as being executed by the selected first test;

(A5) computing a weight for each of the software tests under consideration, the weight being based on a number of the new and the modified blocks under consideration that are indicated as executed by each of the respective ones of the software tests;

(A6) selecting a second test having a maximum weight among the software tests under consideration; and

(A7) adding the selected second test to the current test sequence.

7. The computer-implemented method of claim 1, wherein the step (A1) includes adding to the weight of the respective one of the software tests when any of the new and the modified blocks that are indicated as being executed by the respective one of the software tests is in a performance critical part of the software to be tested.

8. The computer-implemented method of claim 1, wherein the step (A1) includes utilizing a rate of fault detection of each of the respective ones of the software tests when computing a respective weight.

9. The computer-implemented method of claim 1, wherein the coverage indicators indicate one or more arcs that are covered by each respective one of the software tests and the indication of impacted areas of the software further indicates ones of the arcs that are new or modified with respect to a previous version of the software.

10. The computer-implemented method of claim 9, wherein:

the step (A) comprises determining whether ones of the arcs are not indicated as being taken by any of the software tests, and

the computer-implemented method further comprising the step (C) of generating a list of the ones of the arcs that are not indicated as taken by any of the software tests.

11. The computer-implemented method of claim 9, wherein the step (A) comprises the steps of:

(A1) computing a weight for each of the software tests, the weight being based on a number of the ones of the arcs that are indicated as taken by each respective one of the software tests;

(A2) selecting a first test having a maximum weight among the software tests; and

(A3) adding the selected first test to a current test sequence.

12. The computer-implemented method of claim 11, further comprising:

(A4) removing from consideration the selected first software test and any of the ones of the arcs that are indicated as taken by the selected first test;

(A5) computing a weight for each of the software tests under consideration, the weight being based on a number of the ones of the arcs under consideration that are indicated as taken by each of the respective ones of the software tests;

(A6) selecting a second test having a maximum weight among the software tests under consideration; and

(A7) adding the selected second test to the current test sequence.

13. A computer-implemented method of prioritizing software tests, the method comprising the steps of:

(A) prioritizing software tests for software to be tested based on coverage indicators for the software tests and an indication of impacted areas of the software, each of the coverage indicators indicating which portions of the software are executed for a respective one of the software tests; and

(B) generating a prioritized list of the software tests, the prioritized list including at least one test sequence, wherein;

the portions of the software include at least one of a plurality of blocks, and

the indication of impacted areas of the software indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software, wherein the step (A) comprises the steps of;

(A1) computing a weight for each of the software tests, the weight being based on a number of the new and the modified blocks that are indicated as being executed by each respective one of the software tests;

(A2) selecting a first test having a maximum weight among the software tests, wherein when two or more of the software tests have a same computed maximum weight, the step (A2) further comprises the steps of;

(A2a) determining which one of the two or more of the software tests has a minimum execution time; and

(A2b) selecting as the first test, the one of the two or more software tests having the minimum execution time; and

(A3) adding the selected first test to a current test sequence.

14. A computer-readable medium having instructions stored thereon, such that when the instructions are loaded and executed by a processor, the processor is caused to perform the steps of:

(A) prioritizing software tests based on coverage indicators for the software tests and an indication of impacted areas of software to be tested, each of the coverage indicators indicating which portions of the software to be tested are executed for a respective one of the software tests; and

(B) generating a prioritized list of the software tests, the prioritized list including at least one test sequence, wherein;

the software to be tested includes a plurality of blocks,

each of the coverage indicators indicates at least one block of the plurality of blocks that is executed by a respective one of the software tests, and

the indication of impacted areas indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software to be tested,

wherein the step (A) comprises the steps of;

(A1) computing a weight for each of the software tests, the weight being based on a number of the new and the modified blocks that are indicated as being executed by each respective one of the software tests;

(A2) selecting a first test having a maximum weight among the software tests, wherein when two or more of the software tests have the same computed maximum weight, the step (A2) further comprises the steps of;

(A2a) determining which one of the two or more of the software tests has a maximum overall coverage of the software to be tested; and

(A2b) selecting as the first test, the one of the two or more software tests having the maximum overall coverage of the software to be tested; and

(A3) adding the selected first test to a current test sequence.

15. A computer-readable medium having instructions stored thereon, such that when the instructions are loaded and executed by a processor, the processor is caused to perform the steps of:

(A) prioritizing software tests based on coverage indicators for the software tests and an indication of impacted areas of software to be tested, each of the coverage indicators indicating which portions of the software to be tested are executed for a respective one of the software tests; and

(B) generating a prioritized list of the software tests, the prioritized list including at least one test sequence, wherein;

the software to be tested includes a plurality of blocks,

each of the coverage indicators indicates at least one block of the plurality of blocks that is executed by a respective one of the software tests, and

the indication of impacted areas indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software to be tested,

wherein the step (A) comprises the steps of;

(A1) computing a weight for each of the software tests, the weight being based on a number of the new and the modified blocks that are indicated as being executed by each respective one of the software tests;

(A2) selecting a first test having a maximum weight among the software tests, wherein when two or more of the software tests have the same computed maximum weight, the step (A2) further comprises the steps of;

(A2a) determining which one of the two or more of the software tests has a minimum execution time; and

(A2b) selecting as the first test, the one of the two or more software tests having the minimum execution time; and

(A3) adding the selected first test to a current test sequence.

16. The computer-readable medium of claim 15, wherein the blocks include blocks of binary code and each of the blocks has a single entry point and a single exit point.

17. The computer-readable medium of claim 15, wherein a coverage indicator of a new block indicates that the respective one of the software tests executes the new block when a predecessor block and a successor block of the new block have been indicated as being executed by the respective one of the software tests.

18. The computer-readable medium of claim 15, wherein a coverage indicator of a new block indicates that the respective one of the software tests executes the new block when a successor block of the new block has been indicated as being executed by the respective one of the software tests.

19. The computer-readable medium of claim 15, wherein:

the step (A) comprises determining whether ones of the modified and the new blocks exist that are not indicated as being executed by any of the software tests, and

the processor further performs the step (C) of outputting a list of the ones of the modified and the new blocks that are not indicated as being executed by any of the software tests.

20. The computer-readable medium of claim 15, wherein the step (A) further comprises the steps of:

(A4) deleting from consideration the selected first software test and any of the new and the modified blocks that are indicated as being executed by the selected first test;

(A5) computing a weight for each of the software tests under consideration, the weight being based on a number of the new and the modified blocks under consideration that are indicated as being executed by each of the respective ones of the software test;

(A6) selecting a second test having a maximum weight among the software tests under consideration; and

(A7) adding the selected second test to the current test sequence.

21. The computer-readable medium of claim 15, wherein the step (A1) includes adding to the weight of the respective one of the software tests when any of the new and the modified blocks that are indicated as being executed by the respective one of the software tests are in a performance critical part of the software to be tested.

22. The computer-readable medium of claim 15, wherein the step (A1) includes considering a rate of fault detection of each of the respective ones of the software tests when computing a respective weight.

23. The computer-readable medium of claim 15, wherein the coverage indicators indicate one or more arcs that are covered by each respective one of the software tests and the indication of impacted areas further indicates ones of the arcs tat branch to or from a block that is new or modified with respect to a previous version of the software to be tested.

24. The computer-readable medium of claim 23, wherein:

the step (A) comprises determining whether the ones of the arcs are not indicated as being caused to be taken by any of the software tests, and

the processor further performing the step (C) of outputting a list of the ones of the arcs that are not caused to be taken by any of the software tests.

25. The computer-readable medium of claim 23, wherein the step (A) comprises the steps of:

(A1) computing a weight for each of the software tests, the weight being based on a number of the ones of the arcs that are indicated as being caused to be taken by each respective one of the software tests;

(A2) selecting a first test having a maximum weight among the software tests; and

(A3) adding the selected first test to a current test sequence.

26. The computer-readable medium of claim 25, wherein the step (A) farther comprises the step of:

(A4) deleting from consideration the selected first software test and any of the ones of the arcs that are indicated as caused to be taken by the selected first test;

(A5) computing a weight for each of the software tests under consideration, the weight being based on a number of the ones of the arcs under consideration that are indicated as caused to be taken by each of the respective ones of the software tests;

(A6) selecting a second test having a maximum weight among the software tests under consideration; and

(A7) adding the selected second test to the current test sequence.

27. A computer system for prioritizing software tests, the computer system comprising:

a prioritizer for prioritizing the software tests based on coverage indicators for the software tests and an indication of impacted areas of software to be tested, each of the coverage indicators indicating which portions of the software to be tested are caused to be executed by a respective one of the software tests; and

an outputter for outputting a prioritized list of the software tests, the prioritized list including at least one test sequence, wherein;

the software to be tested includes a plurality of blocks,

each of the coverage indicators indicates at least one block of the plurality of blocks that is caused to be executed by a respective one of the software tests, and

the indication of impacted areas indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software to be tested,

wherein the prioritizer further comprises;

a weight determiner for determining a weight for each of the software tests, the weight being based on a number of the new and the modified blocks that are indicated as being caused to be executed by each respective one of the software tests;

a selector for selecting a first test having a maximum weight among the software tests, wherein when two or more of the software tests have the same computed maximum weight, the selector is further adapted for;

determining which one of the two or more of the software tests has a maximum overall coverage of the software to be tested; and

selecting as the first test, the one of the two or more software tests having the maximum overall coverage of the software to be tested; and

a test adder for adding the selected first test to a current test sequence.

28. The computer system of claim 27, wherein the blocks include blocks of binary code and each of the blocks have a single entry point and a single exit point.

29. The computer system of claim 27 wherein a coverage indicator of a new block indicates that the respective one of the software tests executes the new block when a predecessor block and a successor block of the new block have been indicated as being executed by the respective one of the software tests.

30. The computer system of claim 27, wherein a coverage indicator of a new block indicates that the respective one of the software tests executes the new block when a successor block of the new block has been indicated as being executed by the respective one of the software tests.

31. The computer system of claim 27 wherein:

the prioritizer comprises a block determiner for determining whether ones of the modified and the new blocks exist that are not indicated as being caused to be executed by any of the software tests, and

the outputter is further adapted for outputting a list of the ones of the modified and the new blocks that are determined by the block determiner as not being caused to be executed by any of the software tests.

32. The computer system of claim 27, wherein the weight determiner is further adapted for adding to the weight of the respective one of the software tests when any of the new and the modified blocks that are indicated as being caused to be executed by the respective one of the software tests is in a performance critical part of the software to be tested.

33. The computer system of claim 27, wherein the weight determiner is further adapted for considering a rate of fault detection of each of the respective ones of the software tests when computing a respective weight.

34. The computer system of claim 27, wherein the coverage indicators indicate one or more arcs that are covered by each respective one of the software tests and the indication of impacted areas further indicates ones of the arcs that branch to or from a block that is new or modified with respect to a previous version of the software to be tested.

35. The computer system of claim 34, wherein:

the prioritizer is further adapted for determining whether the ones of the arcs are not indicated as being caused to be taken by any of the software tests, and

the outputter is further adapted for outputting a list of the ones of the arcs that are not indicated as being caused to be taken by any of the software tests.

36. The computer system of claim 34, wherein the prioritizer further comprises:

a weight determiner for determining a weight for each of the software tests, the weight being based on a number of the ones of the arcs that are indicated as being caused to be taken by each respective one of the software tests;

a selector for selecting a first test having a maximum weight among the software tests; and

a test adder for adding the selected first test to a current test sequence.

37. A computer system for prioritizing software tests, the computer system comprising:

a prioritizer for prioritizing the software tests based on coverage indicators for the software tests and an indication of impacted areas of software to be tested, each of the coverage indicators indicating which portions of the software to be tested are caused to be executed by a respective one of the software tests; and

an outputter for outputting a prioritized list of the software tests, the prioritized list including at least one test sequence, wherein;

the software to be tested includes a plurality of blocks,

each of the coverage indicators indicates at least one block of the plurality of blocks that is caused to be executed by a respective one of the software tests, and

the indication of impacted areas indicates ones of the plurality of blocks that are modified or new with respect to a previous version of the software to be tested,

wherein the prioritizer further comprises;

a weight determiner for determining a weight for each of the software tests, the weight being based on a number of the new and the modified blocks that are indicated as being caused to be executed by each respective one of the software tests;

a selector for selecting a first test having a maximum weight among the software tests, wherein when two or more of the software tests have the same computed maximum weight, the selector is further adapted for;

determining which one of the two or more of the software tests has a minimum execution time; and

selecting as the first test, the one of the two or more software tests having the minimum execution time; and

a test adder for adding the selected first test to a current test sequence.