In the February 2020 issue of Communications of the ACM, Microsoft researcher Patrice Godefroid published a new review article entitled “Fuzzing: Hack, Art, and Science,” which presents an overview of the main automated testing techniques in use today for finding security vulnerabilities in software.
Fuzzing means automatic test generation and execution with the goal of finding security vulnerabilities. Over the last two decades, fuzzing has become a mainstay in software security. Thousands of security vulnerabilities in all kinds of software have been found using fuzzing.
Why should developers add fuzzing to their toolkit?
- Fuzzing is an effective way to find security bugs in software, so much so that the Microsoft Security Development Lifecycle requires fuzzing at every untrusted interface of every product.
- If you develop software that may process untrusted inputs, you should use fuzzing.
- If you are working with standalone applications with large, complex data parsers, fuzzing is very effective.
- Fuzzing finds vulnerabilities often missed by static program analysis and manual code inspection.
At a high level, there are three main types of fuzzing techniques.
Blackbox random fuzzing simply randomly mutates well-formed program inputs and then runs the program with those mutated inputs with the hope of triggering bugs. It is a simple hack, but it can be remarkably effective in finding bugs in programs that have never been fuzzed.
Grammar-based fuzzing is an alternative approach for fuzzing complex formats. With this approach, the user provides an input grammar specifying the input format of the application under test. Often, the user also specifies what input parts are to be fuzzed and how. From such an input grammar, a grammar-based “fuzzer” then generates many new inputs, each satisfying the constraints encoded by the grammar. Grammar-based fuzzing extends fuzzing to an art by allowing the user’s creativity and expertise to guide fuzzing. (According to the Oxford English Dictionary, art is “the expression … of human creative skill and imagination.”)
The third main approach to fuzzing is whitebox fuzzing, which has been pioneered at Microsoft Research (first published in 2008). This approach consists of symbolically executing the program under test dynamically and gathering constraints on inputs from conditional branches encountered along the execution. All these constraints are then systematically negated one by one and solved with a constraint solver, whose solutions are mapped to new inputs that exercise different program execution paths. This process is repeated using systematic search techniques that attempt to sweep through all (in practice, many) feasible execution paths of the program. Compared to blackbox random fuzzing, whitebox fuzzing is usually more precise, can exercise more code, and thus discover more bugs. Whitebox fuzzing leverages advances in computer science research on program verification and explores how and when fuzzing can be mathematically “sound and complete” and can provide verification guarantees.
The advantages and limitations of each of these three main fuzzing techniques are described in detail in Godefroid’s article. Various combinations of these techniques are also discussed.
So in the end, is fuzzing a hack, an art, or a science? Well, in practice, it is a bit of all three, depending on the situation or technique used.
The bottom line is this: If you develop software that may process untrusted inputs (that an attacker could control) and have never used fuzzing, you probably should!
If you want to give it a try and start fuzzing your software, visit and try out Microsoft Security Risk Detection, the first commercial cloud fuzzing service.