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

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceArticle dans les actes d'une conférence/un colloque

Résumé

Mutation analysis is a popular test assessment method. 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 preliminary assessment of a state-of-the-art exact language equivalence tool to handle the EMP against 3 models of size up to 15,000 states on 1170 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 10% on average. We therefore conclude that the approaches can be combined for improved efficiency.
langueAnglais
titreProceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017
Lieu de publicationTokyo, Japan
EditeurIEEE
Pages424-429
Nombre de pages6
ISBN (Electronique)9781509060313
Les DOIs
étatPublié - 13 mars 2017
Evénement10th IEEE International Conference on Software Testing, Verification and Validation (ICST 2017) - Tokyo, Japon
Durée: 13 mars 201718 mars 2017
Numéro de conférence: 10
http://aster.or.jp/conference/icst2017/

Série de publications

NomICST '17
EditeurIEEE

Une conférence

Une conférence10th IEEE International Conference on Software Testing, Verification and Validation (ICST 2017)
Titre abrégéICST 2017
PaysJapon
La villeTokyo
période13/03/1718/03/17
Adresse Internet

Empreinte digitale

Automata theory
Finite automata

mots-clés

    Citer ceci

    Devroey, X., Perrouin, G., Papadakis, M., Legay, A., Schobbens, P., & Heymans, P. (2017). Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation. Dans Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017 (p. 424-429). [7927996] (ICST '17). Tokyo, Japan: IEEE. https://doi.org/10.1109/ICST.2017.46
    Devroey, Xavier ; Perrouin, Gilles ; Papadakis, Mike ; Legay, Axel ; Schobbens, Pierre ; Heymans, Patrick. / Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation. Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017. Tokyo, Japan : IEEE, 2017. p. 424-429 (ICST '17).
    @inproceedings{5073565ab73e407d8cc40bafbda5096e,
    title = "Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation",
    abstract = "Mutation analysis is a popular test assessment method. 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 preliminary assessment of a state-of-the-art exact language equivalence tool to handle the EMP against 3 models of size up to 15,000 states on 1170 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 10{\%} on average. We therefore conclude that the approaches can be combined for improved efficiency.",
    keywords = "Model-Based Mutation Analysis, Automata Language Equivalence, Random Simulations, Model-based mutation analysis, Random simulations, Automata language equivalence",
    author = "Xavier Devroey and Gilles Perrouin and Mike Papadakis and Axel Legay and Pierre Schobbens and Patrick Heymans",
    year = "2017",
    month = "3",
    day = "13",
    doi = "10.1109/ICST.2017.46",
    language = "English",
    series = "ICST '17",
    publisher = "IEEE",
    pages = "424--429",
    booktitle = "Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017",

    }

    Devroey, X, Perrouin, G, Papadakis, M, Legay, A, Schobbens, P & Heymans, P 2017, Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation. Dans Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017., 7927996, ICST '17, IEEE, Tokyo, Japan, p. 424-429, 10th IEEE International Conference on Software Testing, Verification and Validation (ICST 2017), Tokyo, Japon, 13/03/17. https://doi.org/10.1109/ICST.2017.46

    Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation. / Devroey, Xavier; Perrouin, Gilles; Papadakis, Mike; Legay, Axel; Schobbens, Pierre; Heymans, Patrick.

    Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017. Tokyo, Japan : IEEE, 2017. p. 424-429 7927996 (ICST '17).

    Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceArticle dans les actes d'une conférence/un colloque

    TY - GEN

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

    AU - Devroey, Xavier

    AU - Perrouin, Gilles

    AU - Papadakis, Mike

    AU - Legay, Axel

    AU - Schobbens, Pierre

    AU - Heymans, Patrick

    PY - 2017/3/13

    Y1 - 2017/3/13

    N2 - Mutation analysis is a popular test assessment method. 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 preliminary assessment of a state-of-the-art exact language equivalence tool to handle the EMP against 3 models of size up to 15,000 states on 1170 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 10% on average. We therefore conclude that the approaches can be combined for improved efficiency.

    AB - Mutation analysis is a popular test assessment method. 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 preliminary assessment of a state-of-the-art exact language equivalence tool to handle the EMP against 3 models of size up to 15,000 states on 1170 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 10% on average. We therefore conclude that the approaches can be combined for improved efficiency.

    KW - Model-Based Mutation Analysis

    KW - Automata Language Equivalence

    KW - Random Simulations

    KW - Model-based mutation analysis

    KW - Random simulations

    KW - Automata language equivalence

    UR - http://www.scopus.com/inward/record.url?scp=85020703419&partnerID=8YFLogxK

    U2 - 10.1109/ICST.2017.46

    DO - 10.1109/ICST.2017.46

    M3 - Conference contribution

    T3 - ICST '17

    SP - 424

    EP - 429

    BT - Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017

    PB - IEEE

    CY - Tokyo, Japan

    ER -

    Devroey X, Perrouin G, Papadakis M, Legay A, Schobbens P, Heymans P. Automata Language Equivalence vs. Simulations for Model-based Mutant Equivalence: An Empirical Evaluation. Dans Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation, ICST 2017. Tokyo, Japan: IEEE. 2017. p. 424-429. 7927996. (ICST '17). https://doi.org/10.1109/ICST.2017.46