An experimental comparison of edge, edge-pair, and prime path criteria

摘要

Background: Many criteria have been proposed to generate test inputs. Criteria are usually compared in terms of subsumption: if a criterion C1 subsumes C2, it is guaranteed that every test set that satisfies C1 will also satisfy C2. An implication of this notion of subsumption is that C1-adequate tests tend to find more faults than C2-adequate tests, but C1-adequate tests tend to be larger. Thus, while useful, the idea of subsumption does not elaborate on some practical properties of expensive criteria as, for instance, how many more faults a C1-adequate test set will find? More generally, what is the return on investment for choosing more expensive criteria? Method: To provide a more accurate idea of the fault finding ability and cost of several criteria, we set out to compare three structural graph coverage criteria: edge coverage (EC), edge-pair coverage (EPC), and prime path coverage (PPC). PPC and EPC subsume EC. To compare these criteria we examined 189 functions from 39 C programs, used mutants as a proxy for faults, and performed a statistical analysis of the results. Result: The three criteria are very similar in terms of effectiveness when all mutants are taken into account: PPC killed 98% of the mutants, EPC 97%, and EC 94%. However, the difference between the criteria is emphasized with minimal mutant sets: PPC killed 75% of the mutants, EPC killed 67%, and EC killed only 57%. As for the cost of these criteria, we found that there is not much difference in terms of the number of TRs. We expected PPC to have the most TRs, so we were surprised to find that, on average, the number of TRs for EPC was highest. Conclusion: PPC can detect more faults, specially in programs that have complicated control flows, but at higher cost. Thus, a practical tester can make an informed cost versus benefit decision. A better understanding of which structures in the programs contribute to the expense might help to choose when to use PPC.