Mull it over: mutation testing based on LLVM

Published on

Somewhere in December of 2017 I found an academic event called 11th IEEE Conference on Software Testing, Validation and Verification. What is interesting is that this conference included several workshops, one of which covered latest research in the area of mutation testing: The 13th International Workshop on Mutation Analysis. It was too late to submit papers for the main event, but CFP for the workshop was still open. I thought it is a good idea to submit a paper about our tool there. Especially, given that they also accept papers from industry folks, not only academics.

Recently the paper became available online: Mull it over: mutation testing based on LLVM. This article shortly highlights the key ideas from this paper.

Introduction

What is Mutation Testing?

Mutation Testing, a fault-based software testing technique, serves as a way to evaluate and improve quality of software tests. A tool for mutation testing creates many slightly modified versions of original program and then runs a test suite against each version, which is called a mutant. A mutant is said to be killed if the test suite detects a change to the program introduced by this mutant, i.e., at least one of the tests starts to fail, or survived otherwise.

Each mutation of original program is created based on one of the predefined rules for program modification called mutation operators. Each mutant is represented by a mutation point: a combination of mutation operator and location of a mutation in the program’s source code. To assess the quality of a test suite mutation testing uses a metric called mutation score, or mutation coverage.

What is Mull?

The Mull project is our attempt to build a general-purpose mutation testing tool targeting compiled languages. Mull is built on top of the LLVM compiler framework: it uses LLVM IR or Bitcode to perform mutations, and LLVM JIT engine to execute original and mutated programs.

Mull’s primary focus is C and C++, but due to its LLVM nature it can be applied for other languages such as Swift, Rust, Objective-C.

Mull is a command line tool. It takes a configuration file as an input and produces an SQLite database with the results as output. Configuration file contains list of tested program’s bitcode files, a set of mutation operators, a test framework, and few other things. The SQLite database contains information gathered during the run, such as tests, mutation points, mutants (killed or survided), and more.

Algorithm

The following are the steps that Mull performs during a session:

  • Step 1: Mull loads LLVM Bitcode into memory.
  • Step 2: Mull inserts instrumentation code into each function. This code is used to collect code coverage information. We describe our approach to instrumentation later.
  • Step 3: Mull compiles instrumented LLVM Bitcode to machine code and prepares the machine code for execution by LLVM JIT engine.
  • Step 4: In the LLVM IR code Mull finds the tests according to a test framework specified in the configuration file.
  • Step 5: Mull runs each test using LLVM JIT engine and collects code coverage information.
  • Step 6: Mull finds mutations in the LLVM IR code based on a code coverage information collected for each test. A set of mutation points is created.
  • Step 7: For each mutation point, Mull creates a mutant and runs each test that can possibly kill the mutant. For each mutant, only part of bitcode is recompiled into machine code. We describe our approach to runtime compilation later.
  • Step 8: All information collected during the session is written to the SQLite database. This is the final step. Mull finishes its execution at this point.

Implementation

Instrumentation and Dynamic Call Tree

llvm, mutation testing

Comments