PaperlayerView exact revision on arXiv

Source-linked AI summary

Mull it over: mutation testing based on LLVM

Alex Denisov, Stanislav Pankevich

arXiv:1908.01540v1cs.SE

TL;DR

The authors identify a lack of usable mutation-testing tools for some compiled languages, despite mature tools for Java and Ruby. Mull is a general-purpose mutation-testing tool built on LLVM and evaluated on real-world open-source projects. Mull was applied to RODOS, OpenSSL, and LLVM; the LLVM analysis took 3 hours 46 minutes in real execution.

  • Problem

    The authors identify a lack of usable mutation-testing tools for some compiled languages, despite mature tools for Java and Ruby.

    Source: §I · p. 1

  • Method

    Mull is a general-purpose mutation-testing tool built on LLVM and evaluated on real-world open-source projects.

    Source: §I · p. 1, §V · p. 4

  • Results

    Mull was applied to RODOS, OpenSSL, and LLVM; the LLVM analysis took 3 hours 46 minutes in real execution.

    Source: §V · p. 4, C. LLVM · p. 5

  • Takeaways & Limitations

    The authors present Mull as a tool for exploring mutation testing across compiled-language projects, including RODOS, OpenSSL, and LLVM.

    Source: §VIII · p. 6

    LLVM JIT does not support projects using Thread Local Storage or the Objective-C Runtime, limiting full Objective-C and Swift support.

    Source: B. Current limitations of LLVM JIT · pp. 5–6

Abstract

from arXiv · show

This paper describes Mull, an open-source tool for mutation testing based on the LLVM framework. Mull works with LLVM IR, a low-level intermediate representation, to perform mutations, and uses LLVM JIT for just-in-time compilation. This design choice enables the following two capabilities of Mull: language independence and fine-grained control over compilation and execution of a tested program and its mutations. Mull can work with code written in any programming language that supports compilation to LLVM IR, such as C, C++, Rust, or Swift. Direct manipulation of LLVM IR allows Mull to do less work to generate mutations: only modified fragments of IR code are recompiled, and this results in faster processing of mutated programs. To our knowledge, no existing mutation testing tool provides these capabilities for compiled programming languages. We describe the algorithm and implementation details of Mull, highlight current limitations of Mull, and present the results of our evaluation of Mull on real-world projects such as RODOS, OpenSSL, LLVM.

I. INTRODUCTION

Mull targets the gap in usable mutation-testing tools for some compiled languages, using LLVM IR for mutations and LLVM JIT for compilation and execution. Its LLVM basis supports multiple LLVM-IR languages, while its design aims for practical use across real-world projects.

I. INTRODUCTION

  • Mull targets compiled languages with a general-purpose mutation-testing tool built on LLVM.It uses LLVM IR to perform mutations and LLVM JIT to compile and execute tested programs and mutants.Source: §I · p. 1
  • Mull's practical design criteria include speed, configurability, ease of setup and use, build-tool integration, real-world readiness, and a useful range of operators.The intended domains include systems and application programming, algorithms, and mathematical computations.Source: §I · p. 1
  • Mull can support languages that compile to LLVM IR, including Rust, Swift, and Objective-C, with test-framework adapters required for each language.The project initially focused on C and C++.Source: §I · p. 1
  • Mull takes configuration and bitcode inputs, stores session results in SQLite, and relies on a separate program to generate HTML reports.The database includes tests, mutation points, and mutant outcomes.Source: §I · p. 1

II. ALGORITHM

  • The paper's remaining sections cover Mull's algorithm, implementation, operators, evaluation on RODOS, OpenSSL, and LLVM, limitations, future work, and conclusions.The algorithm section introduces a sequence of steps performed during a session.Source: §I · p. 1, §II · p. 2

Step 1:

Mull loads LLVM bitcode, instruments functions, and uses LLVM JIT to run tests and collect coverage. It uses that coverage to identify mutation points.

Step 1:

  • Mull loads LLVM bitcode into memory as the first session step.Source: Step 1 · p. 2

Step 2:

  • Mull inserts instrumentation into each function to collect code-coverage information.Source: Step 2 · p. 2

Step 3:

  • Mull compiles instrumented LLVM bitcode to machine code and prepares it for execution by LLVM JIT.Source: Step 3 · p. 2

Step 4:

  • Mull finds tests in LLVM IR using the test framework specified in the configuration file.Source: Step 4 · p. 2

Step 5:

  • Mull runs each test with LLVM JIT and collects code-coverage information.Source: Step 5 · p. 2

Step 6:

  • Mull uses per-test coverage information to find mutations in LLVM IR and create mutation points.Source: Step 6 · p. 2

Step 7:

For each mutation point, Mull creates a mutant and runs tests that can kill it, recompiling only part of the bitcode. Dynamic call-tree coverage limits mutations to reachable code, while LLVM JIT performs compilation and linking in memory.

Step 7:

Step 8:

  • Mull writes all information collected during a session to an SQLite database as its final step.Source: Step 8 · p. 2

A. Instrumentation and Dynamic Call Tree

  • Mull instruments functions and runs tests to identify reachable code, then constructs a dynamic call tree to guide mutation placement.Mutations can be injected into subtrees of a test function that contain the code being tested.Source: A. Instrumentation and Dynamic Call Tree · p. 2
  • Mutation distance measures the call distance from a test function to a function with a mutation, letting Mull ignore mutations beyond a chosen distance.For a chain A calls B calls C, the distance from A to C is 2.Source: A. Instrumentation and Dynamic Call Tree · p. 2
  • Instrumentation adds overhead, but the authors say it is necessary for accurate coverage; static analysis was inadequate when functions were resolved at runtime.C function pointers and C++ virtual calls are cited as examples.Source: A. Instrumentation and Dynamic Call Tree · p. 2

B. JIT and Runtime Compilation

C. Sandboxing

Mull isolates each test in a child process to contain abnormal mutant behavior. It distinguishes ordinary test completion from timeouts and crashes.

C. Sandboxing

  • Mull runs each test in a separate child process to sandbox execution of potentially misbehaving mutated code.Source: C. Sandboxing · p. 2

1) Normal execution (test has passed or failed):

2) Timeout:

  • Mull sets a child-process alarm so nonterminating mutated code exits with timeout code 239 after a set interval.Source: 2) Timeout · p. 2

3) Crash:

  • Mull uses WIFSIGNALED() to detect when mutated code crashes in a child process.Source: 3) Crash · p. 2

4) Abnormal exit:

Mull distinguishes abnormal child-process exits, offers a dry run to estimate analysis time, and supports multiple test-framework arrangements, including custom suites configured per project.

4) Abnormal exit:

  • Mull uses custom exit code 227 to distinguish a mutated child process’s abnormal exit from a normal exit when premature termination prevents a test from finishing.Source: 4) Abnormal exit · p. 2

D. Dry Run

  • Dry-run mode collects mutation information without running tests, recompiling fragments, or sandboxing, and estimates runtime pessimistically by assuming every mutant times out.The estimate is higher than real execution time but provides a hint of expected runtime.Source: D. Dry Run · pp. 2–3

E. Test Framework: plugin architecture

  • Test-framework plugins separate test discovery from execution; Mull requires only that each test can run independently.A finder identifies tests in bitcode, and a runner executes one test using the framework’s calling conventions.Source: E. Test Framework: plugin architecture · p. 3
  • CustomTestFramework lets projects with custom suites define tests in configuration instead of requiring a dedicated finder-runner pair for each project.For OpenSSL, the configuration identifies the test function and program arguments to run it.Source: E. Test Framework: plugin architecture · p. 3

F. Fail Fast mode

Mull reduces test runs with optional fail-fast execution and reuses cached objects, while its supported mutation operators include arithmetic substitutions in LLVM IR.

G. Caching

  • Mull’s on-disk cache reuses object files when reading them is faster than compiling bitcode in memory, and names cached files using bitcode checksums and mutation-point identifiers.Source: G. Caching · p. 3

IV. SUPPORTED MUTATION OPERATORS

  • Mull’s mutation operators operate on LLVM IR instructions, and the paper’s supported-operator list refers to instructions in the LLVM IR manual.Source: §IV · p. 3

A. Math: Add, Sub, Mul, Div

  • Mull’s supported arithmetic operators substitute add with sub, sub with add, mul with div, and div with mul, including floating-point equivalents.Operator implementation follows LLVM IR specifications, with Pitest documentation informing which operators to implement first.Source: A. Math: Add, Sub, Mul, Div · p. 3, §IV · p. 3

B. Negate Condition

Mull’s operators alter comparison conditions, remove void calls, replace scalar-returning calls with 42, or toggle scalar values between zero and one. The evaluation measures real-project applicability, performance, and integration using selected operators, test suites, and cache conditions.

B. Negate Condition

  • Negate Condition changes integer or floating-point comparison codes to their logical opposites, such as equal to not equal or signed less than to signed greater than or equal.Source: B. Negate Condition · p. 3

C. Remove Void Function

D. Replace Call

  • Replace Call substitutes a function call returning an integer or floating-point scalar with the corresponding typed value 42.The operator applies to both call and invoke instructions.Source: D. Replace Call · p. 4

V. EVALUATION

  • The evaluation applies Mull to RODOS, OpenSSL, and LLVM, focusing on integration, performance, and practical applicability rather than bugs found or shallow tests.Project bitcode-file count and total weight matter to performance because code must be loaded, analyzed, compiled, and linked.Source: §V · p. 4
  • The evaluation uses Math Add, Negate Condition, and Remove Void Function, enables fail-fast and caching, and measures tests, mutants, test runs, and cold- and hot-run time.Source: §V · p. 4

A. RODOS

Applying Mull to RODOS and OpenSSL required adapting test selection and reporting to Mull’s per-test execution needs, with project-specific build and configuration work.

A. RODOS

  • RODOS test suites originally selected one test at compile time and always returned exit code 0, so the setup changed selection to runtime and made the exit code reflect failed tests.The build also needed compiler flags to emit LLVM bitcode, plus object-file and CppUnit library configuration for assembly and dynamic-library components.Source: A. RODOS · p. 4

B. OpenSSL

  • OpenSSL’s unit-test programs originally ran all tests together, so they were adapted to accept one test’s command-line arguments and configured with each test’s function and arguments.The build used -flto to produce bitcode; test information was extracted manually.Source: B. OpenSSL · p. 5

C. LLVM

The LLVM evaluation uses ADTTests, excludes unsupported typed tests, and reports whole-suite and subset runtimes to assess Mull on a large project.

C. LLVM

  • The evaluation uses ADTTests, covering LLVM abstract data types, and excludes GoogleTest typed tests unsupported by GoogleTestFinder.Source: C. LLVM · p. 5
  • LLVM’s LTO setting supplies bitcode, but one source file using thread-local storage had to be excluded because LLVM JIT does not support TLS.That file is not used by the test suite, so its absence does not affect the analysis.Source: C. LLVM · p. 5
  • Almost four hours on LLVM’s whole test suite is impractical for iteration, compared with two minutes for a test subset.The result is presented for different configurations and test groups.Source: Table IV · p. 5, C. LLVM · p. 5

A. Junk and stray mutations

The paper identifies mutations introduced by lowering and inlining, LLVM JIT constraints, and remaining work toward production use of Mull.

A. Junk and stray mutations

  • A single C++ source line can produce around 200 LLVM IR instructions, creating bitcode mutations with no equivalent source edit; some operators lack robust solutions.Source: A. Junk and stray mutations · p. 5

B. Current limitations of LLVM JIT

VII. FUTURE WORK

  • Planned performance work includes parallelizing child processes and recompiling mutated functions rather than whole bitcode files, which may help with large files.Source: §VII · p. 6
  • IDE integration is a planned step toward making Mull part of modern development workflows, beyond its current command-line and HTML-report use.Source: §VII · p. 6
  • Further project exploration is intended to drive new test-framework adapters, better Rust and Swift support, and operation on BSD and Windows.Source: §VII · p. 6
  • The authors leave proper comparison with other compiled-language mutation tools for separate research.Source: §VII · p. 6

VIII. CONCLUSION

The authors report that Mull satisfies their practical-tool criteria after LLVM-based experiments outperformed earlier source- and AST-level attempts. They evaluated it on real-world projects and describe future goals for industry and research use.

VIII. CONCLUSION

  • LLVM IR/JIT experiments outperformed the authors’ earlier source- and AST-level attempts, and they report that Mull satisfies their practical-tool criteria.They also identify broad application potential and room for further improvement.Source: §VIII · p. 6
  • To probe real-world use and possible limitations, they tested projects including LLVM, OpenSSL, RODOS, rustc-demangle, and CryptoSwift.The projects span C/C++, Rust, and Swift settings.Source: §VIII · p. 6
  • The authors’ long-term goal is an industry-ready drop-in mutation-testing solution, with research use also anticipated.They expect research interactions with other tools and approaches to seek faster mutation testing with automatic test generation.Source: §VIII · p. 6
Loading 1908.01540v1…