Model-based mutant equivalence detection using automata language equivalence and simulations

Xavier Devroey, Gilles Perrouin, Mike Papadakis, Axel Legay, Pierre-Yves Schobbens, Patrick Heymans

Research output: Contribution to journalArticleScientificpeer-review

9 Citations (Scopus)


Mutation analysis is a popular technique for assessing the strength of test suites. It relies on the mutation score, which indicates their fault-revealing potential. Yet, there are mutants whose behaviour is equivalent to the original system, wasting analysis resources and preventing the satisfaction of a 100% mutation score. For finite behavioural models, the Equivalent Mutant Problem (EMP) can be transformed to the language equivalence problem of non-deterministic finite automata for which many solutions exist. However, these solutions are quite expensive, making computation unbearable when used for tackling the EMP. In this paper, we report on our assessment of a state-of-the-art exact language equivalence tool and two heuristics we proposed. We used 12 models, composed of (up to) 15,000 states, and 4710 mutants. We introduce a random and a mutation-biased simulation heuristics, used as baselines for comparison. Our results show that the exact approach is often more than ten times faster in the weak mutation scenario. For strong mutation, our biased simulations can be up to 1000 times faster for models larger than 300 states, while limiting the error of misclassifying non-equivalent mutants as equivalent to 8% on average. We therefore conclude that the approaches can be combined for improved efficiency.
Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalJournal of Systems and Software
Publication statusPublished - 2018


  • Model-based mutation analysis
  • Automata language equivalence
  • Random simulations


Dive into the research topics of 'Model-based mutant equivalence detection using automata language equivalence and simulations'. Together they form a unique fingerprint.

Cite this