Date 26.6.18
Today I will be discussing about various fuzzing techniques and past implementations of those, some of which you have suggested. It will be a bit unfocused because I will be covering a lot of different approaches.
I will mainly discuss about the performance/efficiency tradeoffs that will occur as we approach a "smarter" fuzzing solution, and let you decide what we should focus on. However, most fuzzing techniques that have been done in the past do not have any code or proof of concept program that implements their idea, so I have no real benchmark times to compare the different techniques
Last time I covered in-depth about AFL, and its various techniques of fuzzing. (Briefly show the slides for it). I think the most important takeaway from AFL is that it doesn't really a concept of frontiers and how one might transform input A to input B in order to advance the frontier.
So as I mentioned previously, AFL has a very primitive and minimal understanding of the target binary. It doesn't know how to manipulate the input other than making "educated guesses" of mutations. It also doesn't know what parts of an input to change.
Furthermore, although, AFL can detect when a certain input causes an advancement of the "frontier" (i.e. a branch path that is has not taken before) and will save this input so that it will not have to jump over this frontier again, AFL will struggle to efficiently allocate its resources on advancing on a "frontier" that it has not discovered yet.
The problem with focusing on resources on advancing a "frontier" that is not discovered yet is that it is pretty difficult to determine the probabilities of getting a certain input value that will allow getting past the current frontier. For example, you could possibly focus so much of your resources on a particular branch only to realize that most of your attempts are useless.
AFL go tries to focus its definition of frontier as possibly a branch that will lead it closer to a target basic block. To briefly review AFL Go's algorithm, AFL Go creates this heuristics with a series of steps: (a) it takes all the basic blocks it can find and precomputes the distance from that basic block to the target basic block(s), (b) during runtime, it computes the average relative distance of each basic block (to the target block) AFL Go visits for a particular input seed, (c) AFL Go uses this distance mixed with a power schedule, as a scaling factor to determine how much undeterministic fuzzing needs to be done for a particular input value.
Part of the reason why this makes it more effective than perhaps AFL is because the resulting target basic blocks that could introduce a bug are comparatively smaller to the program as a whole. It allows AFL to focus on frontier inputs that might lead AFL to close in on the target blocks.
However, AFL Go in itself is pretty limited. It really is designed for small targets; when the size of the target basic blocks increase, AFL Go will become sort of impractical. It also virtually cannot be used as a coverage fuzzing solution: when the target is changed from a relatively small basic block to target everything, the targeting becomes useless.
Perhaps we could try targeting frontier inputs and implement this back with AFL? i.e. the more frontier locations a input is found to have, the more importance it gets? I have not yet tested this to see if it might give more coverage.
Anyways, I think AFL Go still inherits many of the limitations of AFL. In particular, AFL Go still does not have a strong sense of frontier, but rather it is still pretty naïve. It's distance factor is still just a greedy algorithm, and it can easily get stuck in a local minimum if the program logic is complex enough. The only way that AFL Go can overcome this right now is by running a few rounds of coverage first, and then slowly transitioning into targeting, but this still depends on the efficacy of the original coverage algorithm of AFL.
AFL Go is still not smart enough to transform the input in a way that will guarantee advancement of the frontier, but rather it will still just probabilistically guess hoping that this might lead AFL in the right direction
So perhaps one step in the direction of improving our fuzzing heuristics, we can try using dynamic taint analysis to help place our fuzzer in the right direction to fuzz.
We can do this by indexing each section of input and trace where the corresponding inputs will "taint" specific branches. However, this will definitely require some sort of virtualization of the code, significantly lowering performance of fuzzing.
Taint Check was part of a proposal in a paper published in 2004.
It performs dynamic taint analysis by virtualizing the program code and traces how user input gets propagated throughout the code. It then catches whenever one of these "untrusted" inputs executes unsafe actions. This software is built on top of valgrind (which is an instrumentation software) that virtualizes a program.
This was designed to run alongside a production server software, so that if a particular input causes a bug, some developer would be alerted of this bug before the attacker has the time to exploit it. It is not designed to act as a fuzzer to systematically discover such bugs.
However, this paper was over 14 years old, and it has not released any source code or program implementing TaintCheck, so I decided to look at some other options. I have found another software called "TaintGrind" that does something similar, but after running the program, I found it to be even slower.
So these are graphs depicting the benchmarks for TaintCheck. The paper uses these three different types of applications to show how performance might vary. It also used different types of virtualization modes (native, valgrind with nullgrind, valgrind with memcheck, valgrind with taintcheck).
- Bzip2 was used because it was a long-term CPU intensive application (worse case scenario for TaintCheck).
- Cfingerd was used because it was a very short-lived application. The paper argued that caching that helped increase performance over time would not be as beneficial for short lived applications
- Apache was also used since the paper argued that a large latency issue was not with the CPU itself but due to the network or disk I/O operations.
We see that in all cases, taintcheck does invoke a very heavy performance overhead because of the needed virtualization (and also the fact that this was pretty old technology).
The paper argues that the virtualization of valgrind is causing a lot of the performance deficiency. So for a follow-up I decided to run a few more current benchmarks, compare it with afl fuzz, to see if any time improvements have been done over the years. Of course I did not have TaintCheck to work with, so I decided to use the open source alternative "taint grind".
Unfortunately, when I ran TaintGrind, it was significantly worse than the older TaintCheck program, even when Valgrind itself has been significantly improved. We also note that the AFL fuzzer instrumentation code is very lightweight, so it beats out valgrind's virtualization software.
Taint scope is a more recent attempt (2011) of whitebox-fuzzing, that also utilizes dynamic taint analysis.
The interesting approach of TaintScope is that it uses dynamic taint tracing to try to correspond certain bytes with the resulting jump outcomes. Using this data, it first tries to identify potential checksums, and removes these so that the fuzzer has an easier time passing these checksums. It then passes the hot bytes to the fuzzer so that the fuzzer can target these hot-bytes. Then finally it solves the constraints needed for checksums for those inputs that the fuzzer reports as "crashes" and then verifies that it still causes a crash.
After covering a few various techniques in dynamic taint analysis and how it can relate to fuzzing, I will now describe some of its limitations.
First of all, running with Dynamic Taint Analysis, we find that it is much slower than some faster traditional blackbox fuzzing. We could possibly limit the performance detriment by running DTA with relatively few times and run the fuzzer in non-virtualized mode. Then on a technical limitation, Dynamic Taint Analysis type fuzzers have much difficulty in trying to virtualize all the x86 assembly instructions and various system calls because they are so complicated, and often they have complex behaviors.
Furthermore, with the TaintScope program, it does require more valid input files to compare valid inputs to invalid inputs (i.e. to determine checksums).