Collaborative Research: SHF: Small: Feedback-Driven Mutation Testing for Any Language

Testing, validation, and verification are all central activities in programming and software engineering. Unfortunately, existing techniques for testing remain inadequate for finding and eliminating key vulnerabilities before software deployment -- even the most critical modern software is rife with security vulnerabilities and defects that ultimately cost the economy billions of dollars annually in lost productivity and compromised data.

A technique known as "mutation testing" has been researched since the 1970s; it aims to help software engineers improve their tests and their software at the same time, by automatically adding bugs to a program and checking whether the test suite can detect them. Although in theory this technique is extremely effective for improving software quality, there are several fundamental factors that prevent it from being widely used in practice: it is difficult and time-consuming to use, and the tools that exist for it cannot all handle the diversity of program languages that are deployed in modern software systems.

This project will tackle these challenges and allow this important technique to be used to improve quality of real-world software by developing efficient tools that can apply mutation testing to programs written in any language; prioritize the output of the tools to reduce the amount of time and effort needed to make maximal use of them; and incorporate user feedback into the technique to maximize testing efficiency. The project will be evaluated on real-world open source software like the Linux kernel, and build on the researchers' previous collaborations to substantially improve program and test effort quality on critical real-world software.

The core problem this project aims to address is making program mutants practical in nonresearch settings, in a way that meets the needs of developers and test engineers, by making it possible for someone creating or enhancing a test suite, or developing code and test suite in tandem, to (1) use "just enough" mutation testing for their needs, maximizing benefit gained in exchange for work performed, and (2) to work in any programming language without worrying about the quality of tool support provided for mutation testing, and without sacrificing the ease of understanding of source-based mutants, while easily adding custom mutation operators that target their specific software development task. This project aims to adapt the Furthest-Point-First metric previously used in fuzzer bug triaging to the problem of maximizing the novelty of mutants examined by a user, in order to make it possible to quickly discover unkilled mutants that expose serious defects in a testing or verification effort.

However, novelty alone is not sufficient: feedback-driven mutation testing must also help users avoid inconsequential, equivalent mutants, kill mutants high in the dominance hierarchy, and (most importantly) incorporate user feedback. If a user marks a mutant as inconsequential, or equivalent, or (especially) high impact, then that information must be used to inform the ranking of future mutants as well.

In order to make such an approach maximally valuable, this project also proposes to improve the state-of-the-art in source-level multilingual mutant generation, allowing users to easily generate mutants for new programming languages, or even for custom DSLs that are part of a specific project.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.