On the use of commit-relevant mutants

Milos Ojdanic, Wei Ma, Thomas Laurent, Thierry Titcheu Chekam, Anthony Ventresque, Mike Papadakis

TL;DR

Traditional mutation testing is often too "noisy" and expensive for evaluating small code changes. This paper introduces commit-relevant mutants—a specialized subset of mutants that specifically interact with the behavioral changes introduced by a code commit. The authors demonstrate that these mutants are 30% more effective at catching commit-related bugs than traditional mutants, proving that where a mutant is located is often less important than how it interacts with the "delta" of a change.

What Problem Does This Paper Address?

Mutation testing is a powerful way to measure test suite effectiveness by injecting tiny "bugs" (mutants) into code and seeing if tests catch them. However, it has a major efficiency problem: generating and running thousands of mutants is computationally expensive.

When developers submit a small change (a commit), they don't necessarily care if their test suite can find every possible bug in the entire system; they care if the tests cover the new or altered behaviors. Existing approaches usually focus on mutants located directly on the modified lines of code. The authors argue this is insufficient because a change in one function can alter the behavior of unmodified code elsewhere. There is a need for a "change-aware" metric that filters out the noise of irrelevant mutants while capturing the subtle side effects of a commit.

Methods

The authors define a commit-relevant mutant based on "observable dependence." Intuitively, a mutant is relevant if:

  1. The commit affects the mutant's behavior.
  2. The mutant, in turn, affects the program's output.

To identify these, they compare the execution of test cases across four versions: the original pre-commit code, the post-commit code, and mutated versions of both.

The core algorithm for identifying commit-relevant mutants by comparing outputs across pre-commit, post-commit, and mutated versions.

The Core Algorithm: They developed an automated procedure to approximate the set of relevant mutants using large test pools (including developer tests and automatically generated tests from tools like KLEE and SEMu). A mutant is flagged as relevant if at least one test case can distinguish the behavior of the mutant in the post-commit version from its behavior in the pre-commit version.

The study also compares these mutants against other established categories, such as subsuming mutants (those that represent the "hardest" requirements) and hard-to-kill mutants (those caught by very few tests).

Datasets

The researchers evaluated their approach using a massive scale of 2,253,610 mutants across 83 commits from 25 different projects:

  • C Programs: 34 commits from GNU Coreutils and 13 fault-introducing commits from CoREBench.
  • Java Programs: 36 commits from well-known Apache Commons projects (cli, collections, io, net), Joda-Time, and Jsoup.
  • Tools: They used Mart for C mutation and Pitest for Java, along with KLEE for symbolic execution to augment their test suites.

Key Insights and Ideas

  • Location is a Red Herring: Surprisingly, the majority of commit-relevant mutants are located on unmodified code parts. This debunked the common practice of only looking at mutants on the changed lines. If you only mutate the "diff," you miss the ripple effects of the change.
  • Standard Scores are Misleading: There is only a weak correlation (0.15–0.4) between a traditional mutation score and a commit-relevant mutation score. A high overall mutation score doesn't guarantee that a specific new change is well-tested.
  • A Distinct Class of Mutants: Commit-relevant mutants don't overlap significantly with "hard-to-kill" or "subsuming" mutants. This means relevance is a unique property that existing mutant reduction techniques aren't capturing.
  • Efficiency via Relevance: By focusing only on relevant mutants, testers can achieve better results with much less effort. Analyzing just a few relevant mutants provides more "fault-revelation power" than a random selection of traditional mutants.

Key Results

  • Higher Bug-Catching Potential: For the same number of mutants analyzed, commit-relevant mutants have a 30% higher chance of revealing real bugs introduced by a commit compared to traditional mutants.
  • Sparsity: Commit-relevant mutants represent a small subset of the total mutant population (ranging from 0.5% to 47% depending on the commit), suggesting a massive opportunity for optimization.
  • Regression Testing: In a use case for Test Case Prioritization (TCP), the authors found that using commit-relevant mutants as a metric significantly improved the ability to order tests to find bugs faster, especially when using "Additional Mutant" coverage strategies.

Limitations and Future Work

  • Oracle Dependency: The method currently relies on having a large pool of tests to "approximate" relevance. If the test pool is weak, the identification of relevant mutants might be incomplete.
  • Computational Cost of Identification: While using the mutants is efficient, identifying them currently requires executing many versions of the program. The authors suggest that future work should focus on using static analysis or machine learning to predict relevance without full execution.
  • Test Contracts: The study focused on commits that did not change "test contracts" (i.e., the tests themselves weren't rewritten). Future research is needed to see how this applies to commits that involve major refactoring of the test suite itself.

Summary updated

Abstract

Applying mutation testing to test subtle program changes, such as program patches or other small-scale code modifications, requires using mutants that capture the delta of the altered behaviours. To address this issue, we introduce the concept of commit-relevant mutants, which are the mutants that interact with the behaviours of the system affected by a particular commit. Therefore, commit-aware mutation testing, is a test assessment metric tailored to a specific commit. By analysing 83 commits from 25 projects involving 2,253,610 mutants in both C and Java, we identify the commit-relevant mutants and explore their relationship with other categories of mutants. Our results show that commit-relevant mutants represent a small subset of all mutants, which differs from the other classes of mutants (subsuming and hard-to-kill), and that the commit-relevant mutation score is weakly correlated with the traditional mutation score (Kendall/Pearson 0.15-0.4). Moreover, commit-aware mutation analysis provides insights about the testing of a commit, which can be more efficient than the classical mutation analysis; in our experiments, by analysing the same number of mutants, commit-aware mutants have better fault-revelation potential (30% higher chances of revealing commit-introducing faults) than traditional mutants. We also illustrate a possible application of commit-aware mutation testing as a metric to evaluate test case prioritisation.
BibTeX
@article{ojdanic2022use,
  author = {Milos Ojdanic and Wei Ma and Thomas Laurent and Thierry Titcheu Chekam and Anthony Ventresque and Mike Papadakis},
  title = {{On the use of commit-relevant mutants}},
  journal = {Empir. Softw. Eng.},
  year = {2022},
  doi = {10.1007/s10664-022-10138-1},
}
Figure