Property-Based Mutation Testing

Ezio Bartocci, Leonardo Mariani, Dejan Nickovic, Drishti Yadav

TL;DR

Traditional mutation testing measures how well a test suite detects any change in software behavior, but for safety-critical systems, we only care if a fault breaks a specific safety requirement. This paper introduces Property-Based Mutation Testing (PBMT), a framework that redefines "killing a mutant" as successfully triggering a violation of a formal safety property, revealing that standard test suites are often far less robust than they appear.

What Problem Does This Paper Address?

In the world of safety-critical Cyber-Physical Systems (CPS)—like autonomous cars or medical devices—engineers use Mutation Testing (MT) to evaluate their test suites. MT works by injecting small "bugs" (mutants) into the code; if a test suite can distinguish the buggy version from the original, the mutant is "killed," and the suite is considered high-quality.

However, the authors identify a major gap: regular MT is too sensitive. In data-flow models (like those built in Simulink), almost any change propagates to the output. A test might "kill" a mutant because of a tiny, irrelevant numerical difference, even if that bug never actually causes the system to violate its safety requirements. This leads to an inflated "mutation score," giving engineers a false sense of security about their system's safety.

Methods

The authors propose a shift from general output-checking to property-specific checking.

  1. Formalizing PBMT: They define a $\phi$-killed mutant as one where a test case passes on the original program but specifically causes a violation of property $\phi$ (expressed in Signal Temporal Logic or STL) in the mutated program.
  2. Identifying "Trivial" Mutants: They introduce the concept of $\phi$-trivially different mutants—bugs that might change the output but are physically or logically incapable of ever breaking the specific safety property $\phi$.
  3. Search-Based Test Generation (SBTG): To find the "hard-to-kill" mutants, the authors developed an optimization strategy. Using the Blood Coagulation Algorithm (BCA), they search for test inputs that maximize the difference between the original and mutated signals specifically in a way that pushes the system toward a property violation.
  4. Tooling: The framework was implemented for MATLAB/Simulink models, utilizing the RTAMT library for monitoring STL properties.

Datasets

The researchers evaluated their approach on two industrial-strength benchmarks from the MathWorks documentation:

  • ATCS (Automatic Transmission Controller System): An automotive model where safety properties involve keeping engine and vehicle speeds below specific thresholds.
  • AECS (Aircraft Elevator Control System): An avionic model where the safety property requires the elevator position to stabilize within a certain time after a pilot command.

Mutants were generated using the FIM (Fault Injection and Mutation) tool, covering operators like "Negate," "Stuck-at," and "Relational Operator Replacement."

Key Insights and Ideas

  • The "False Security" Gap: The most striking insight is the massive discrepancy between regular MT and PBMT. A test suite might kill 100% of mutants in a traditional sense but fail to trigger property violations for nearly half of them.
  • Propagation vs. Violation: In CPS, "reaching" a fault is easy because the data flows constantly. The real challenge is "sufficiency"—ensuring the fault propagates with enough magnitude to actually break a safety constraint.
  • Refining the "Equivalent Mutant" Problem: In standard MT, identifying equivalent mutants (bugs that don't change behavior at all) is an undecidable problem. PBMT expands this to "property-equivalent" mutants, which are even harder to find but more relevant to safety engineering.

Key Results

The quantitative results highlight the inadequacy of standard testing strategies:

  • Score Inflation: For the ATCS model, a standard "Adaptive Random Testing" suite achieved a 100% mutation score under regular MT. However, under PBMT, its score plummeted to just 53.19%.
  • Falsification Testing (FT) Limits: Even test suites specifically designed to break properties (Falsification Testing) only achieved PBMT scores between 42% and 57%.
  • Efficiency: The authors' Search-Based strategy proved that many "live" mutants could be killed, but they required highly specific, targeted inputs that random or general-purpose testing simply couldn't find. For ATCS, they showed that while 47 mutants were "killable" by regular MT, only 25-27 were actually $\phi$-killable by standard suites.

Limitations and Future Work

  • First-Order Mutants Only: The study focuses on single-point faults (First Order Mutants). The authors acknowledge that real-world failures often result from multiple interacting faults (Higher Order Mutants), which PBMT has yet to explore.
  • Computational Cost: The search-based test generation (SBTG) is significantly more computationally expensive than random testing, as it requires running an optimization loop for every single mutant.
  • Domain Specificity: The current evaluation is limited to Simulink models and STL properties. Extending this to other modeling languages (like Stateflow) or different property formalisms is a suggested next step.

Summary updated

Abstract

Mutation testing is an established software quality assurance technique for the assessment of test suites. While it is well-suited to estimate the general fault-revealing capability of a test suite, it is not practical and informative when the software under test must be validated against specific requirements. This is often the case for embedded software, where the software is typically validated against rigorously-specified safety properties. In such a scenario (i) a mutant is relevant only if it can impact the satisfaction of the tested properties, and (ii) a mutant is meaningfully-killed with respect to a property only if it causes the violation of that property. To address these limitations of mutation testing, we introduce property-based mutation testing, a method for assessing the capability of a test suite to exercise the software with respect to a given property. We evaluate our property-based mutation testing framework on Simulink models of safety-critical Cyber-Physical Systems (CPS) from the automotive and avionic domains and demonstrate how property-based mutation testing is more informative than regular mutation testing. These results open new perspectives in both mutation testing and test case generation of CPS.
BibTeX
@inproceedings{bartocci2023property,
  author = {Ezio Bartocci and Leonardo Mariani and Dejan Nickovic and Drishti Yadav},
  title = {{Property-Based Mutation Testing}},
  booktitle = {ICST},
  year = {2023},
  doi = {10.1109/icst57152.2023.00029},
}

Loading related content...

Figure