What is structured fuzzing and is the fuzzing that Bitcoin Core does currently considered structured?

Question

Can you define what structured fuzzing is and the benefits it brings over plain vanilla fuzzing?

Is some of the fuzzing that Bitcoin Core does currently considered "structured"?

Answer 1

I'll use the definitions used in this presentation from Jonathan Metzman at Black Hat 2019 but obviously this is a relatively new field and so there may well be disagreement amongst researchers and academia on formal definitions.

In this presentation Metzman explained how the first rudmimentary fuzzers were completely black box meaning they knew nothing about the target they were fuzzing. They were also structure unaware meaning they knew nothing about the format that they were supposed to be mutating or generating and were just piping bytes from /dev/urandom etc.

The next generation of fuzzers were still black box but they were now structure aware as in when fuzzing for example HTML, they provided inputs that looked like HTML rather than just random nonsense.

Metzman believes current day fuzzers (e.g. AFL) are coverage guided, structure aware but they are unstructured. This is where Bitcoin Core is now in terms of fuzzing. I don't think there has been any experimentation with structured fuzzing (I will update if wrong).

The reason why AFL has had such a large effect and this technique as well, is because unstructured fuzzing allows people to use it without actually understanding much about the format that they are actually fuzzing. But because it is coverage guided the fuzzer generates progressively more interesting inputs and that’s why it is actually fairly good at finding bugs.

Metzman believes the next generation of fuzzers will be structured. They won’t just do the general purpose mutations that AFL does on inputs. They will do format specific ones like deleting expressions from programs rather than just flipping bits. They will also allow you to fuzz where you think the bugs are going to be.

With structured fuzzing you are almost becoming part of the fuzzer where you see code that isn’t being covered and you make a decision whether you think it is worth covering that code. Then you make the fuzzer cover that code.

You will be able to do this by writing custom mutators where you define the function that will be called to mutate test cases rather than the default mutator. Currently you can write custom mutators with libFuzzer.