What is fuzz testing?

Question

I've been looking at the Bitcoin Core PR review club sessions on fuzz testing here and here.

Can you explain at a high level what is fuzz testing?

Answer 1

In the paper The Art, Science and Engineering of Fuzzing the authors define fuzzing as “a process of repeatedly running a program with generated inputs that may be syntactically or semantically malformed”.

Fuzz testing is not a new concept. It was introduced in the early 1990s but at the present time its potential for finding bugs has not been fully explored in the Bitcoin Core codebase.

Of course fuzzing is a technique not only used by those seeking to prevent bugs in a software project (defenders) but also those seeking to exploit a bug (attackers). There is a danger that if projects like Bitcoin Core fall behind the state of the art in defense techniques that attackers could take advantage.

Matt Corallo discussed fuzz testing at London Bitcoin Devs in February 2019.

Fuzz testing is a general testing approach of black boxing a test case that takes as input some random set of bytes, running a program on it and trying to make it crash. This is primarily used for decoders, things like that. They have proven to be very, very, very effective at taking an image decompression library or something that processes untrusted data off a network and making it crash, finding vulnerabilities in it, finding stack overflow, buffer overflow kind of vulnerabilities. They are not just completely dumb, like shove in random bytes. They actually instrument the binary. Usually what they do is they instrument the binary, and you can do this in hardware or in software, and detect when a given input has found new paths in the program. So you map out all the if statements and all the branches in the program and if it finds an input that hits a new branch then it considers that input interesting and it will mutate that input a little bit more than other inputs.

Matt Corallo added at Advancing Bitcoin in February 2019:

Fuzzing has been incredibly useful across the software world but mostly for finding vulnerabilities in things like image decompressors, image decoders, message deserializers, that sort of thing. And what it does is you write a program that takes as input some arbitrary string of bytes and you do something with those bytes and the fuzzer tries to make you crash. So if you have some image decoder or decompressor often times it will find a bug where you used too much memory, you have an out of memory condition and you have a DoS vulnerability there. Or maybe it will find a bug where you have some buffer overflow, something like that. Or whatever depending on the language you’re writing in. Fuzzers have been amazing. You can go look up all of the various CVEs and vulnerabilities they’ve found. We’ve been playing a lot with them in rust-lightning and we have the standard ones of just make sure all of our message deserializers don’t crash or don’t use infinite memory. But we also have some allow nodes to do completely arbitrary things. So we have one fuzz target that runs a full node and can receive bytes on the wire. This allows you to literally do anything that another node could do to you possibly in a fuzzing environment where the fuzzer is trying to creatively crash your program and comes up with different inputs that might exercise different code paths