TL;DR
This paper introduces MOTIF, a novel tool that combines grey-box fuzzing with mutation testing to automatically generate more effective unit tests for C programs, particularly those used in safety-critical cyber-physical systems (CPS). MOTIF significantly outperforms traditional symbolic execution-based mutation testing tools, especially for complex programs where symbolic execution struggles.
What Problem Does This Paper Address?
Ensuring the reliability of software is paramount, especially in safety-critical domains like cyber-physical systems (CPS). Mutation testing is a powerful technique for this, where small, artificial faults (mutants) are injected into the software, and a test suite's ability to detect these mutants is measured. A high "mutation score" generally indicates a robust test suite. However, existing state-of-the-art tools for C, like SEMu, rely on symbolic execution (SE). SE has limitations: it struggles with programs requiring complex input generation, such as those involving floating-point arithmetic, making it difficult to apply mutation testing to a broad range of CPS software. This paper addresses the challenge of applying mutation testing effectively to C-based CPS software by overcoming the limitations of symbolic execution.
Methods
MOTIF leverages a grey-box fuzzer, specifically AFL++, to automate mutation testing. The core idea is to use fuzzing's ability to automatically generate inputs guided by code coverage feedback, which circumvents the input generation limitations of symbolic execution.
Here's a breakdown of MOTIF's workflow:
- Generate Fuzzing Drivers: MOTIF uses the clang static analysis library to parse the C source code and create abstract syntax trees. This allows it to understand function signatures and generate specialized C "fuzzing drivers." These drivers are designed to:
- Load input data provided by the fuzzer.
- Declare variables for both the original and mutated functions' parameters.
- Invoke both the original and mutated functions with the same fuzzed input.
- Compare the outputs (including return values and modified parameters) of the original and mutated functions. If differences are found, the driver aborts, signaling to the fuzzer that a mutant might have been killed.
- Generate Seed Files: Based on the input parameter types, MOTIF creates initial "seed" input files. These seeds are designed to cover basic cases for different data types (e.g., zero, negative, and positive for numeric types).
- Compile Drivers: The generated fuzzing drivers, the mutated functions, and the original software under test (SUT) are compiled.
- Mutation Testing: The AFL++ fuzzer is then run with the compiled fuzzing drivers and seed files. The fuzzer explores the program, generating new inputs based on coverage feedback. MOTIF processes the fuzzer's logs to identify inputs that likely killed mutants. A crucial post-processing step checks for non-determinism in the SUT by re-executing the original function with the same input to ensure the observed difference wasn't due to inherent variability in the SUT.
- Test Case Generation: For mutants that are killed, MOTIF can generate a unit test case. This test case uses the input that killed the mutant and the observed output of the original function as an assertion, which can be used for regression testing.
Datasets
The paper evaluates MOTIF on three software subjects used in commercial satellites:
- MLFS: The Mathematical Library for Flight Software.
- LibU: A utility library from an industry partner.
- ASNLib: A serialization/deserialization library.
These subjects were chosen because they represent real-world CPS software. The mutants were generated using the MASS tool.
Key Insights and Ideas
- Fuzzing as a Mutation Testing Enabler: The most significant insight is that grey-box fuzzing, with its ability to explore complex input spaces guided by coverage, can effectively overcome the limitations of symbolic execution for mutation testing.
- Differential Testing for Mutant Detection: MOTIF's core mechanism of comparing the outputs of the original and mutated functions with the same input is a clever way to detect if a mutant has been killed, without needing explicit oracle information for each mutant.
- Handling Non-Determinism: The explicit check for non-deterministic behavior in the original function is crucial for ensuring that reported mutant kills are genuine and not artifacts of the SUT's inherent variability.
- Broader Applicability: MOTIF extends mutation testing to programs that are challenging or impossible for symbolic execution-based tools, thereby increasing the reach of mutation testing in critical software domains.
Key Results
MOTIF demonstrates superior performance compared to a modified version of SEMu (SEMuP) that uses SEMu for mutation testing:
- Higher Mutation Score: Across two subjects (LibU and ASNLib), MOTIF killed a significantly higher percentage of mutants. Specifically, it achieved 46.86 percentage points (pp) and 10.52 pp higher than SEMuP on LibU and ASNLib, respectively.
- Effectiveness on Infeasible Subjects: For MLFS and a subset of LibU mutants, where symbolic execution was infeasible, MOTIF was still able to kill a substantial number of mutants. On average, it killed 1,399.4 (35.97%) mutants for MLFS and 120 (41.38%) mutants for LibU.
- Applicability: The results highlight that MOTIF can be applied to subjects that are not amenable to symbolic execution-based approaches.
Limitations and Future Work
- Limitations: The paper notes that for subjects with mathematical functions, the number of killed mutants might be lower because these mutants are often only detectable by inputs from very specific, small input domains. The current work focuses on C programs.
- Future Work: The authors plan to extend MOTIF to support C++ and investigate the effectiveness improvements gained by using different fuzzing configurations and tools.
Summary updated