Both the execution of test cases against the system under test (the "SUT") and their maintenance have an associated cost: if the system changes, maybe the test cases must be changed, recompiled, reviewed and reexecuted. So, it is important to have test cases prioritized according, for example, to their ability to find faults on the SUT, or to any other "test requirement" (which, in general, will be some coverage criterion).
If we use the number of faults as test requirement, we'll be interested in executing firstly those test cases that find more faults in the SUT:
- In a new system, this prioritization can be made counting the number of artificial changes introduced in the SUT by a mutation tool.
- In an old system, the prioritization will depend on the number of faults found by the test cases in previous system releases.
Suppose a SUT for which 7 mutants have been generated, and a test suite composed by 6 test cases. The following matrix may show the number of faults found by each test case:
tc1 finds the errors seeded on
m1 and
m2, tc2 the errors in
m1, m2 and
m3; tc6 does not find any fault.
| tc1 | tc2 | tc3 | tc4 | tc5 | tc6 |
m1 | X | X |
|
|
|
|
m2 | X | X |
|
| X |
|
m3 |
| X |
|
|
|
|
m4 |
|
| X |
|
|
|
m5 |
|
| X |
|
|
|
m6 |
|
| X | X |
|
|
m7 |
|
|
| X |
|
|
tc1 and tc5 are redundant with respect to tc2, since the faults they find are a subset of the faults found by tc2: thus, tc2 is a better test case than the formers. To build a prioritized test suite, we would add test cases in this order: {tc2, tc3, tc4, tc1, tc5} (tc2 or tc3 could be added in a random order, since they find three faults). tc6 can be removed because it's an ineffective test case.
This kind of prioritizations are made by greedy algorithms.
Some other related papers are:
| Reference | Brief summary |
| Harrold M, Gupta R and Soffa M (1993). A methodology for controlling the size of a test suite. ACM Transactions on Software Engineering and Methodology, 2(3), p. 270-285. |
They give a greedy algorithm (usually referred to as HGS) for reducing the suite of test cases into another one, preserving the fulfillment of the test requirements reached by the original suite. The main steps of this algorithm are:
- Initially, all the test requirements are unmarked.
- Add to T’ those test cases that only exercise a test requirement. Mark the requirements covered by the selected test cases.
- Order the unmarked requirements according to the cardinality of the set of test cases exercising one requirement. If several requirements are tied (since the sets of test cases exercising them have the same cardinality), select the test case that would mark the highest number of unmarked requirements tied for this cardinality. If multiple such test cases are tied, break the tie in favor of the test case that would mark the highest number of requirements with testing sets of successively higher cardinalities; if the highest cardinality is reached and some test cases are still tied, arbitrarily select a test case from among those tied. Mark the requirements exercised by the selected test. Remove test cases that become redundant as they no longer cover any of the unmarked requirements.
Repeat the above step until all testing requirements are marked.
|
| Jeffrey D and Gupta N (2005). Test suite reduction with selective redundancy. International Conference on Software Maintenance. Budapest (Hungary): IEEE Computer Society. | With Jeffrey, Gupta adds “selective redundancy” to the HGS algorithm. “Selective redundancy” makes it possible to select test cases that, for any given test requirement, provide the same coverage as another previously selected test case, but that adds the coverage of a new, different test requirement. Thus, maybe T’ reaches the All-branches criterion but not def-uses; therefore, a new test case t can be added to T’ if it increases the coverage of the def-uses requirement: now, T’ will not increase the All-branches criterion, but it will do with def-uses. |
| Tallam S and NG (2005). A concept analysis inspired greedy algorithm for test suite minimization. 6th ACM SIG-PLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. | With Tallam, the test case selection method of HGS is based on Concept Analysis techniques. According to the authors, this version achieves same size or smaller size reduced test suites than prior heuristics as well as a similar time performance |
| Heimdahl M and George D (2004). Test-Suite Reduction for Model Based Tests: Effects on Test Quality and Implications for Testing. 19th IEEE International Conference on Automated Software Engineering. |
Propose a greedy algorithm for reducing the test suite. Basically, they take a random test case, execute it and check the coverage reached. If this one is greater than the highest coverage, then they add it to the result. The algorithm is repeated five times to obtain five different reduced sets of test cases. Since chance is an essential component of this algorithm, the good quality of the results is not guaranteed. |
| McMaster S and Memon A (2005). Call Stack Coverage for Test Suite Reduction. 21st IEEE International Conference on Software Maintenance. Budapest (Hungary). |
McMaster and Memon present an also–greedy algorithm. The parameter taken into account to include test cases in the reduced suite is based on the “unique call stacks” that test cases produce on the program under test.
As it is seen, the criterion for selecting test cases is not a “usual test requirement”, as it is common, but the number of unique call stacks.
|
