Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation

Xavier Devroey 1 Gilles Perrouin 1 Mike Papadakis 2 Axel Legay 3 Pierre-Yves Schobbens 1 Patrick Heymans 1
2 SERVAL - Security Design and Validation Research Group
SnT - Interdisciplinary Centre for Security, Reliability and Trust [Luxembourg]
3 TAMIS - Threat Analysis and Mitigation for Information Security
Inria Rennes – Bretagne Atlantique , IRISA_D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Mutation analysis is a popular technique to assess the effectiveness of test suites with respect to their fault-finding abilities. It relies on the mutation score, which indicates how many mutants are revealed by a test suite. Yet, there are mutants whose behaviour is equivalent to the original system, wasting analysis resources and preventing the satisfaction of the full (100%) mutation score. For finite behavioural models, the Equivalent Mutant Problem (EMP) can be addressed through language equivalence of non-deterministic finite automata, which is a well-studied, yet computationally expensive, problem in automata theory. In this paper, we report on our assessment of a state-of-the-art exact language equivalence tool to handle the EMP against 12 models of size up to 15,000 states on 4710 mutants. We introduce random and mutation-biased simulation heuristics as baselines for comparison. Results show that the exact approach is often more than ten times faster in the weak mutation scenario. For strong mutation, our biased simulations are faster for models larger than 300 states. They can be up to 1,000 times faster 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.
Type de document :
Communication dans un congrès
ICST 2017 - International Conference on Software Testing, Verification and Validation, Mar 2017, tokyo, Japan
Liste complète des métadonnées

Littérature citée [65 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01640101
Contributeur : Nisrine Jafri <>
Soumis le : lundi 20 novembre 2017 - 16:51:20
Dernière modification le : jeudi 12 avril 2018 - 01:58:42
Document(s) archivé(s) le : mercredi 21 février 2018 - 15:12:20

Fichier

ICST_2017_paper_48.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01640101, version 1

Citation

Xavier Devroey, Gilles Perrouin, Mike Papadakis, Axel Legay, Pierre-Yves Schobbens, et al.. Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation. ICST 2017 - International Conference on Software Testing, Verification and Validation, Mar 2017, tokyo, Japan. 〈hal-01640101〉

Partager

Métriques

Consultations de la notice

578

Téléchargements de fichiers

74