Static analysis of mutant subsumption

Mutation analysis generates a large set of variants, or mutants, and then demands a test set that distinguishes each variant from the original artifact. It has long been apparent that many mutants contribute little, if anything, to the subsequent test set. Researchers have developed various approaches to separate valuable mutants from redundant mutants. The notion of subsumption underlies several such approaches. Informally, one mutant subsumes another if tests that kill the first also kill the second. Computing subsumption relations is, not surprisingly, undecidable. Recent work formalized the notion of a mutant subsumption graph (MSG) and showed that root nodes in the MSG precisely identify mutants that are not redundant. To address the decidability issue, we first defined the dynamic subsumption graph as an approximation to the MSG. This paper continues by showing how symbolic execution can be used to construct static subsumption graphs. While symbolic execution has some distinct shortcomings, we show how we can mitigate these problems with a hybrid approach that extracts test cases from the analysis process and re-evaluates the subsumption graph dynamically.