MUPPAAL: Efficient Elimination and Reduction of Useless Mutants in Real-Time Model-Based Systems

Jaime Cuartas, David Cortés, Joan S. Betancourt, Jesús Aranda, Maxime Cordy, James Ortiz, Gilles Perrouin, Pierre-Yves SchobbensSoftw. Test. Verification Reliab 2025 · DOI

TL;DR

This paper introduces MUPPAAL, a novel framework for mutation testing of real-time systems modeled as Timed Automata. MUPPAAL tackles the significant problem of "useless mutants" (equivalent or duplicate mutants) by introducing a new mutation operator and efficient detection techniques, thereby improving the accuracy and efficiency of mutation testing for these critical systems.

What Problem Does This Paper Address?

Mutation testing is a powerful technique for evaluating the quality of test suites by introducing artificial faults (mutants) into a system and checking if tests can detect them. However, in the context of real-time systems modeled as Timed Automata (TA), a substantial portion of generated mutants can be "useless." These include:

  • Equivalent mutants: Mutants that behave identically to the original system, making them impossible to detect by any test.
  • Duplicate mutants: Mutants that behave identically to other mutants, offering no additional value for test evaluation.

These useless mutants inflate the cost of mutation testing, waste computational resources, and can lead to misleading mutation scores. Existing approaches often fail to address both equivalent and duplicate mutants effectively, especially for timed systems. This paper aims to fill this gap by presenting a framework that prevents and removes these useless mutants.

Methods

MUPPAAL employs a multi-pronged approach to handle useless mutants:

  • Novel Mutation Operator (SMI-NR): The paper introduces a new mutation operator, SMI-NR, specifically designed to prevent the generation of duplicate mutants from the outset, particularly when combined with existing operators like SMI (State Missing) and TMI (Transition Missing).
  • Timed Bisimulation for Duplicate Detection: To detect duplicate mutants (those with identical behavior), MUPPAAL leverages a parallelized timed bisimulation algorithm. This algorithm efficiently partitions mutants into equivalence classes, where members of each class are considered duplicates.
  • Biased Simulation for Faster Duplicate Suggestion: Recognizing the computational cost of exact bisimulation (which is EXPTIME-complete), MUPPAAL also incorporates a biased simulation heuristic. This approach uses infected states and transitions to generate targeted traces, offering a faster, albeit approximate, method to identify potential duplicates.
  • Integration with UPPAAL and UPPAAL-TRON: The framework is built upon the UPPAAL tool for modeling and simulating Timed Automata and UPPAAL-TRON for online testing and trace analysis.

Datasets

The evaluation of MUPPAAL was performed on six UPPAAL models from distinct domains:

  • Gear Control (GC)
  • Collision Avoidance (CA)
  • Train Gate Controller (TGC)
  • Combined Gear Control (CGC)
  • Tram Door (TD)
  • Scheduling Framework (SF)

These models vary in size and complexity, including different numbers of states, clocks, and clock constraints, providing a diverse testbed for evaluating the framework.

Key Insights and Ideas

  • Significant Duplicate Mutant Problem: The study reveals that duplicate mutants can constitute a substantial portion of generated mutants, up to 32% in their experiments, highlighting the necessity of addressing this issue.
  • Biased Simulation as a Practical Heuristic: Biased simulation proves to be a highly effective and efficient heuristic for identifying potential duplicates, significantly outperforming random simulation in both accuracy and speed. It is notably faster than exact timed bisimulation.
  • Synergy of Exact and Approximate Methods: The paper advocates for a hybrid approach: using fast biased simulation to filter out most duplicates and then employing computationally expensive but exact timed bisimulation only on the remaining candidates. This offers a practical trade-off between speed and accuracy.
  • SMI-NR Operator Effectiveness: The novel SMI-NR operator successfully prevents duplicate mutants without sacrificing the original mutation operator's behavior, offering a valuable addition to mutation testing toolkits.

Key Results

  • Duplicate Mutant Prevalence: Up to 32% of generated mutants were found to be duplicates across the studied systems.
  • Random Simulation Overestimation: Random trace simulation overestimated the number of duplicates by up to an order of magnitude.
  • Biased Simulation Accuracy: Biased simulation was found to be 1.8 times more accurate in identifying duplicates than the random baseline and correctly predicted duplicates in over 60% of cases, exceeding 80% for 5 out of 6 case studies.
  • Performance Comparison: Timed bisimulation was generally faster than random simulation, especially for larger configurations. Biased simulation was consistently faster than timed bisimulation, achieving speedups of up to 90 times in the best case.
  • SMI-NR vs. SMI: The SMI-NR operator effectively prevents duplicates, producing unique mutants while preserving the behavior of the original SMI operator.

Limitations and Future Work

  • Generalizability: The authors acknowledge that their results are based on a selected set of UPPAAL models and a specific set of mutation operators. They cannot guarantee that the findings will extend to all timed systems or all possible mutation operators.
  • Tool Bugs: Despite manual verification and checks, the authors admit that the tool might not be entirely free of bugs.
  • Future Work: The authors plan to continuously extend MUPPAAL, particularly by designing mutation operators for timed automata networks. They also suggest exploring larger values of N (number of traces) and k (simulation time) for more comprehensive evaluations.

Summary updated

BibTeX
@article{cuartas2025muppaal,
  author = {Jaime Cuartas and David Cortés and Joan S. Betancourt and Jesús Aranda and Maxime Cordy and James Ortiz and Gilles Perrouin and Pierre-Yves Schobbens},
  title = {{MUPPAAL: Efficient Elimination and Reduction of Useless Mutants in Real-Time Model-Based Systems}},
  journal = {Softw. Test. Verification Reliab.},
  year = {2025},
  doi = {10.1002/stvr.1907},
}
Figure