A Fuzzing Mirkwood

Getting into fuzzing is so confusing. I remember my first Google search on the subject. You hear about different colors, black/white/grey. You hear about mutation- and model-based generation. So many techniques. And, every fuzzer seems to have a little bit of everything. It’s a confusing field. It’s like entering a thick forest: You can’t even say where the vines are starting or ending.

Usually, My entry point to any concept is Wikipedia. Let’s see what our dear friend has to say on the subject:

– A fuzzer can be generation-based or mutation-based depending on whether inputs are generated from scratch or by modifying existing inputs.
– A fuzzer can be dumb or smart depending on whether it is aware of the input structure.
– A fuzzer can be white-, grey-, or black-box, depending on whether it is aware of the program structure.

Wikipedia

“Generation-based” usually means you have a model to do so. So what would be the difference between “smart” and “generation-based” fuzzing? You can be white or grey, but dumb? Even if you have been here from the start, and you had time to see everything coming little by little, now things are moving very fast and it’s hard to keep up with the dozens of new fuzzer and papers coming out every year.

We are getting close to 200 fuzzers recorded on the fuzzing-survey.org [1] project 🤯. (And this excludes fuzzing papers that are not releasing a new fuzzer.) How to deal with this increasing amount of complexity!

TL;DR: We cannot reduce the large number of fuzzers, but we can make them easier to understand by having a framework to understand. Our survey [2] decomposes all fuzzers in five parts to enable a faster and simpler understanding and analysis, see the diagram at the end of the post.

🎥 Or you can see it on YouTube as well:

A First Step in the Forest

Let’s get back to the first search from Google most of us do when first hearing about fuzzing. As we said, what appears at first is a confusing amount of weird terminology. What is not here, however, is a clear definition of what fuzzing is at its core. There is not a simple accepted definition of fuzzing. I have seen several debates on Twitter involving both people from academia and practitioners. Everyone had their own vision of what is the core of fuzzers.

Let’s turn back to Wikipedia to see its definition of fuzzing:

Fuzzing or fuzz testing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program. The program is then monitored for exceptions such as crashes, failing built-in code assertions, or potential memory leaks.

Wikipedia

We see two components:

1. Creating an input that must be invalid, and with some randomness.
2. We are looking for program crashes.

The first part is not so far from the definition we will settle on as we will see below, but there is an issue. It has assumptions on the way inputs are generated and even the goal of their generation. Some fuzzers do not aim to produce “invalid” inputs. Some fuzzers are not generating based on randomness. A definition should not be method-oriented. Fuzzer’s authors have shown great inventiveness in how to create inputs in the past. Every time, I am amazed at the innovation I see in newly published papers and released tools. It’s likely they will continue to do so in the future, so let’s not constrain ourselves with a restricting definition.

The second part of Wikipedia’s definition is even more misleading. As the sentence itself shows, what is a crash is not well defined. Some fuzzers do not even look for crashes anymore. We should let the users decide what they are aiming at.

Definition and First Model

Fuzzing refers to a process of repeatedly running a program with generated inputs to test if a program violates a correctness policy.

This is the definition we settled on for the survey (or more accurately, a simplified version because we formalized it). What is important is what is not there:

• It does not say how inputs are generated.
• There is no mention of randomness, even if this major component of how fuzzers are usually implemented.
• It does not define a goal to fuzzing. We only have a “correctness policy” which can be defined however the user sees fit.

What we are left with is specific enough to get to the core of fuzzing, a dynamic, self-repeating, testing process, but general enough to encompass all techniques and goals fuzzers and their users might want to use. However, by being so general, you might say this definition does not help us understanding fuzzers. We will address this point by building a general-purpose model.

Let’s start with a simple model based on the definition. Fundamentally a fuzzer does only two things:

1. InputGen generates inputs.
2. InputEval executes these inputs on the program-under-test and checks whether or not they violate the correctness policy (e.g. “is there a segmentation fault happening”).

And these two steps are repeated indefinitely, as many times as the users choose.

Refining the Model

The model described above is enough to explain the first fuzzers like the approach first proposed by Miller in 1990. Fortunately, the field has evolved a lot since then. Fuzzers are now more complex and our model should reflect that to enable a smoother understanding of the current state-of-the-art.

The first opportunity people found to improve fuzzers was out of the main loop: An initial preparation step to make the looping process more efficient. What we call the PreProcess function is very flexible. For instance, it can be used to prepare the input generation. Either by creating a model based on which inputs will be generated, or by preparing seeds. Fuzzers commonly use these seeds to generate new inputs by modifying them. This first step may also be used to prepare the program itself. For example by making the correctness policy detectable while running the program. This is called sanitizing, see this excellent survey [3] for more information about this topic. The PreProcess step is also a good time to instrument the program to get more information on the execution. This is what distinguishes black-, grey- and white-box fuzzing. Here I invite you to look at our survey [2] for more details on the subject.

The next function that was added is the Schedule function. It is essentially a planning step. It is where the fuzzer can decide what it thinks is the most effective way to reach its goals. (Although, the goal definition is not straightforward in this field.) In practice, scheduling is often about choosing the seeds that will be modified to produce the next set of inputs, or how a model will be used to generate inputs. Academia has been focused on this topic for the last few years, most notably AFLFast [4]. An analogy to “energy allocation” is often made: A fuzzer has a given amount of time, how is it going to use it?

Finally, the most complicated step, but probably the most impacting as well, is what we call the “configuration update”, or ConfUpdate. This is where the fuzzer can learn. If Schedule is about energy, this step is about information. Each execution of the program potentially generates so much data that it is impossible to store it all forever. So the fuzzer has to choose what is the most useful from the last executions. This is what distinguished white- and grey-box fuzzers from the black- ones. A black-box fuzzer is not learning anything from the execution it performs (or close to nothing). Whereas in white- and grey-box fuzzers each execution can impact all the following ones. This is where the evolutionary algorithm, first invented by Sidewinder [5] and popularised by the infamous AFL [6], is implemented. (See below for an example of this algorithm.)

Final Fuzzing Model:

From Theory to Practice

The goal of having a model is to be able to understand the world better. So now that we are geared up with this shiny model, let’s see how it fares.

Starting easy with zzuf. This is one of the first fuzzer that came on the scene. As we said above, the first fuzzers were simpler to understand:

• InputGen of zzuf is the mutation (i.e. modification) of a seed.
• Its InputEval is the raw execution of the program on the input generated.

And that’s it. All other functions are not implemented by zzuf.

OK, now let’s step up our game and look at AFL. Can our model pass the challenge of this fuzzer full of features 💪! Here we address the “canonical usage” of AFL because it provides a ton of options to customize your fuzzing.

1. PreProcess: AFL prepares its campaign by instrumenting the program to get the number of times each branch of the program was executed by a particular input. This information is called branch-hit-count.
2. InputGen: AFL is a seed-based grey-box fuzzer, so the input generation is actually similar to zzuf: the seeds are modified to generate new inputs. (Experts in this area might kill me here because it’s actually quite different under the hood, but we are not here to go into the details 😝.)
3. InputEval: The program is executed. Thanks to step (1), here we get an instrumented execution instead of a raw one.
4. The core innovation of grey-box fuzzers: in the ConfUpdate step, AFL adds the input it just executed to its set of seeds if it is different enough from the other ones. The function deciding whether or not it is “different enough” is called the fitness function. If you are interested, I wrote a paper specifically on this topic, Ankou.
5. The Schedule may look boring: In a round-robin fashion, AFL goes over each seed one by one. But to spice it up for you, AFL allocates a different number of executions to each seed depending on some internal heuristics.

If still in doubt, see the survey paper [2], where we projected over 50 fuzzers on this framework 😉. This decomposition shaped the way I think about fuzzing and greatly helps me in my research. Every time I read a paper, I ask myself “which step are we trying to improve here”. For example, AFLFast we mentioned is working on the Schedule function. (It also slightly modifies the ConfUpdate to collect the information needed for this scheduling.) I hope this framework will be beneficial to you as well!

A final tip before you go off, to have a good understanding of any topic, doing is an essential part as well. In fuzzing, Andreas Zeller’s group has created an excellent fuzzing book [7]. It provides a simple and fun way to play with the fuzzers in jupyter notebooks online.

Reference

[1] https://fuzzing-survey.org/
[2] The Art, Science, and Engineering of Fuzzing: A Survey, TSE 2019
[3] SoK: Sanitizing for Security, IEEE S&P 2019
[4] AFLFast, https://github.com/mboehme/aflfast
[5] Sidewinder: An Evolutionary Guidance System For Malicious Input Crafting, Black Hat USA 2006
[6] AFL, https://lcamtuf.coredump.cx/afl/
[7] The Fuzzing Book, https://www.fuzzingbook.org/

1 명이 이 글에 공감합니다.