Introduction to Fuzz Testing

What’s All the Fuzz About?

Fuzzing is a powerful tool that finds bugs in programs. Hackers regularly use fuzzing to discover software vulnerabilities to build their attacks. However, companies can also use fuzzing to find and fix vulnerabilities and thus improve the security of their software. Since both attackers and defenders have access to powerful IT resources, fuzzing has become an essential tool in the “arms race” between hackers and security experts.

Fuzzing technology emerged in 1988 (in a class project by Prof. Barton Miller) and has gained more exposure recently through the release of the AFL tool in 2016. Despite the high rate of adoption by major players such as Google, Microsoft, Facebook and the like, fuzzing is still not widely adopted and is unknown to many professionals.

What Fuzzing Is

Fuzzing is a dynamic testing method used for identifying bugs and vulnerabilities in software. As opposed to static analysis, fuzzing produces almost no false-positives. With fuzzing, you can conduct black-box, grey-box, and white-box tests. This flexibility makes fuzzing an extremely useful tool in software testing, regardless of source code availability. Black-box fuzzing, for example, can be applied by anyone who wants to examine the reliability of the software they are using or are planning to use.

So, what happens during the fuzzing process? During fuzzing, random inputs are fed to the software under test until a crash happens. The input that resulted in a crash is then analyzed, and discovered bugs can be fixed. If the given inputs did not produce a crash, they are mutated to produce further inputs. Software solutions that work with fuzzing are called fuzzers. In 2016, american fuzzy lop (AFL) improved fuzzing by considering the coverage, i.e. the share of traversed code paths in the generation of new inputs. AFL and other coverage-based fuzzers could discover far more paths of a program than “dumb” fuzzers. The next major improvement in the world of fuzzing came in the form of Sanitizers that detect more types of errors than just crashes. The AddressSanitizer, for example, monitors memory access, while the ThreadSanitizer watches for race conditions between multiple threads. Using Sanitizers for fuzzing was made even more practical with the advent of libFuzzer, a fuzzing engine baked into LLVM, due to smart handing of the large virtual memory requirements of the AddressSanitizer. In short, the combination of coverage information with Sanitizers is what we call modern fuzzing. This technology allows continuous and precise targeting of real vulnerabilities in software.

Types of Fuzzers

Dumb Fuzzing

These fuzzing engines produce input completely randomly, without considering what input format is expected. A dumb fuzzer is relatively easy and inexpensive to set up, but is also very inefficient.

Smart Fuzzing

These fuzzers produce inputs that are based on valid input formats. This is very useful, since some programs only execute when inputs match certain patterns. In case invalid inputs are provided, the applications cannot be run and thus cannot be tested. A smart fuzzer recognizes what input format is desired and produces inputs matching this format. This type of fuzzing requires detailed knowledge about input format and thus takes longer to set up, meaning that more costs are involved.

Feedback-Based Fuzzing

Feedback-based fuzzing (or coverage-based fuzzing) uses code coverage information when generating new inputs. As a result, feedback-based fuzzers can cover and test more paths in programs than smart fuzzers. Due to measuring code coverage, the fuzzer can monitor which parts of the program were reached with a given input and reach other program parts by generating similar inputs with random but small changes.

Mutation-Based Fuzzing

Mutation-based fuzzing mutates original valid inputs by introducing small changes that may still keep the input valid, yet exercise new behavior.

Generation-Based Fuzzing

Generation-based fuzzing can generate new inputs from scratch. As opposed to mutation-based fuzzers, no original valid input is needed to start producing new inputs. It is important, however, that generated inputs are based on a certain data model so that corresponding code coverage can be reached.

Anatomy of a fuzzer

A fuzzer can be divided into several parts:

Fuzz Target

In order to use fuzzing, so-called fuzz targets need to be created. Fuzz targets are small programs that test predefined API functions, similar to unit tests. However, the inputs are not provided by the developer but produced with a fuzz generator.

Fuzz Generator

Fuzz generators are responsible for creating random mutations of inputs that are sent to the software under test (SUT). There are different input generation patterns that, to a large extent, influence the fuzzing process. During generation, inputs are changed in a number of ways: parts of the inputs are interchanged, added or deleted. Feedback provided by Sanitizers plays a large role in this process.

Delivery Mechanism

The output of a fuzz generator (i.e. random inputs) are then sent to the SUT. The delivery mechanism processes inputs from fuzz generator and feeds them to SUT for execution.

Monitoring System

The monitoring system keeps track of how the inputs are executed within SUT and detects triggered bugs. The monitoring system plays a critical part in the fuzzing process as it also influences what types of vulnerabilities can be discovered during fuzzing.