By: Kostya Serebryany, Google, with Souheil Moghnie, NortonLifeLock, Rohit Shambhuni, Autodesk and Adith Sudhakar, VMWare
This is the third blog post in SAFECode’s Focus on Fuzzing Series.
In our last post, we provided a simple overview of the different types of fuzzers. One of the differentiators between fuzzers we referenced was their knowledge of the application structure. Within this discussion, we promised a deeper dive into coverage-guided fuzzing.
Coverage-guided fuzzing has been used for over a decade and has gained popularity in recent years as more and better tools became available. In this post, we explain what coverage-guided fuzzing is, and why it may often be a great choice for you. We will also give examples of some tools that implement coverage-guided fuzzing (however, for an in-depth study of such tools, stay tuned to our upcoming blog post on tools!)
Code coverage is a metric used to measure the quality of tests that is often used by developers and test engineers to decide what areas of code need more testing. Code coverage can also be used in an automated fashion for “corpus distillation” – a process that minimizes the set of test inputs while preserving their full combined code coverage.
Mutation-based fuzzing, which applies random mutations to existing test inputs, commonly relies on corpus distillation to improve its efficiency. Coverage-guided fuzzing goes one step deeper: it uses the code coverage to guide the corpus expansion. The basic algorithm can be expressed as follows:
- Set up: creating a set of representative test inputs (the corpus) for the code under test
- Fuzzing:
- Choosing a random input and randomly mutating it
- Measuring the mutant’s code coverage
- If the mutant covers new code, add it to the main corpus, otherwise, ignore it
- Repeating
Coverage-guided fuzzing is essentially a genetic algorithm where the natural selection is based on achieving unique code coverage.
When fuzzing highly structured input types (e.g. API call sequences, or programming languages, or IDLs), simple mutations that are unaware of the input structure, such as random bit flips, will rarely produce interesting mutants. In such cases, the mutation is typically delegated to a specialized module that is aware of the input structure.
An important byproduct of coverage-guided fuzzing is the generated corpus, which typically achieves better code coverage than any manually collected set. This corpus can be used outside of fuzzing, e.g. for a regular continuous testing process. When a bug is found by fuzzing, the faulty input can be added to the corpus to serve as a regression test.
There are many ways to collect code coverage during fuzzing. Among them are compiler instrumentation (e.g. LLVM’s SanitizerCoverage), dynamic binary instrumentation (e.g. PIN), or specialized hardware features (e.g. Intel PT). One can easily construct a custom coverage-guided fuzzer based on these techniques, but in most cases using an existing fuzzing engine is simpler.
Among the popular general-purpose coverage-guided fuzzing engines are tools like AFL, libFuzzer, and Honggfuzz. They differ in their interface, the way they collect coverage, and supported environments, but in most cases, they can be used interchangeably, or even together. libFuzzer supports structure-aware fuzzing via user-defined mutators. Syzkaller is a coverage-guided fuzzing engine with a focus on fuzzing OS system call APIs. It allows users to describe their system call API via a custom language. These four tools alone have been responsible for finding tens of thousands of bugs and vulnerabilities in the last several years.
Organizations can also leverage a fuzzing framework such as ClusterFuzz or services like OSS-Fuzz that will allow these fuzzers to run continuously. Microsoft Security Risk Detection is another fuzzing service that can be used for continuous fuzzing.
Our upcoming posts will cover these tools and services in greater detail, starting with specific coverage-guided fuzzing engines.