In this paper we explore how values from the state space of a program can be used to guide feedback fuzzers such as AFL. By selectively exposing the fuzzer to values from the target program, the fuzzer can become able to solve challenges that would be very hard to solve otherwise. To select the values that are being used to produce the feedback for the fuzzer, the user inserts simple annotations in the target program.
For example, AFL becoms quite capable to play Super Mario Bros. when exposing a single variable (the player’s x coordinate). If a fuzzer is stuck in a hard spot, similar tricks are often possible. For example, we used Ijon to automatically crashing inputs for message sequences involvig checksums: First we patch out the checksum check and fuzz until a crash is found. The resulting input will not crash a normal program, because the checksums need to be fixed. Now we use an Ijon annotation to expose the difference between the correct checksum and the value derived from the input to Ijon. By running AFL in crash exploration mode, we force it to only consider inputs that keep the crashing property. After a few seconds, AFL finds corrects the checksum, producing an input that crashes the unmodified target.
The paper describing Redqueen was published at Oakland Security & Privacy 2020. A recording of the presentation and the slides can be found here: