How Fuzzing with QEMU (and AFL) Works

Whats a Fuzzer?

A fuzzer now-days is a automated testing tool to find security bugs. It does so by generating many inputs to be executed until on of them crashes the target program. In other words the objective is to crash a program, but how can we guide the fuzzer in the right direction?

AFL added to the objective a notion of code coverage: Any input that reaches an area in the code that was unreachable before is interesting. Even if it did not crash the program we can mutate that input to get even more coverage, we call this feedback. Over the past years coverage had proved to be a great feedback mechanism, but collecting it was not simple if one did not own the source code of the target binary.

Enter QEMU Fuzzing

AFL originally used compile time instrumentation to insert assembly instructions at the beginning of each basic block. Basic Block is a group of assembly instructions that are always executed one after the other. When executed, these snippets would write a byte to a shared memory area where the fuzzer can observe and determine which basic blocks had been reached.

This method works well if you have the source code and can compile it with your custom instrumentation, but what if you are fuzzing a closed source binary? One cool example of fuzzing closed source binaries would be: Effective Fuzzing Qmage.

QEMU to the rescue. QEMU is an emulator that can emulate many cpu architectures, for example it can run Android (arm) on your PC (x86) or run Windows on your iPad UTM.

By patching QEMU, TriforceAFL and AFL++ managed to get coverage feedback out of any binary that QEMU can run. How cool is that?!

So How does it Work?

QEMU user-mode is a "sub" tool of QEMU that allows emulating just the userspace (in contrast to the normal mode where both the user-mode and the kernel are emulated). This is done by forwarding any syscalls from the target program to the host machine. The main benefits are improved performance and less complex environment, but it sacrifices on the portability. AFL++ fork of QEMU uses this mechanism while adding coverage tracking and optional performance optimizations.

Example of running arm linux binaries on a x86 host

$ /AFLplusplus/afl-qemu-trace /fuzz/bin/harness <<< aaaaaaaaaaaaaaaaaa
[harness] starting main. main at: 0x550000b848
[harness] should_backtrace. argc=1
[harness] input:
  0000  61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61  aaaaaaaaaaaaaaaa

Getting the Coverage

QEMU writes the coverage feedback data to shared memory, this way both QEMU and the fuzzer can write and inspect the coverage data. The fuzzer is responsible for allocating the shared memory and cleaning it after each run, while is responsible for filling the memory with the coverage data. When the fuzzer starts QEMU, it passes the shared memory file descriptor to QEMU using the __AFL_SHM_ID environment variable and maps the memory to its own process using shmat. Then whenever the QEMU Virtual Machine executes a basic block, it marks the block as reached by writing to this shared memory. This is implemented by the INC_AFL_AREA macro.

After QEMU exits, the fuzzer can look at the shared memory for any bytes that are different from zero. The offset from the start of the map is the ID of the visited basic-block and the more bytes that are different from zero, the more basic blocks our target has hit.

A redacted version of code from afl++ qemu related to the shared memory

// qemuafl/imported/config.h
#define SHM_ENV_VAR "__AFL_SHM_ID"

// accel/tcg/cpu-exec.c
void afl_setup(void) {
  char *id_str = getenv(SHM_ENV_VAR);
  if (id_str) {
    shm_id = atoi(id_str);
    afl_area_ptr = shmat(shm_id, NULL, 0);
    if (afl_area_ptr == (void *)-1) exit(1);
  }
}

// accel/tcg/translate-all.c
void HELPER(afl_maybe_log)(target_ulong cur_loc) {
  register uintptr_t afl_idx = cur_loc ^ afl_prev_loc;
  INC_AFL_AREA(afl_idx);
  afl_prev_loc = cur_loc >> 1;
}

// qemuafl/common.h
#define INC_AFL_AREA(loc) afl_area_ptr[loc]++

Sample rust code for running QEMU and getting coverage from it

fn main() {
  let shm_id = create_shmem();
  env::set_var("__AFL_SHM_ID", format!("{}", shm_id));
  run_target_in_qemu();

  let afl_area_ptr = get_shmem(shm_id);
  let mut cov: Vec<u8> = Vec::new();

  for i in 0..0xffff {
    let value;
    unsafe {
      value = *afl_area_ptr.add(i);
    }
    if value != 0 {
      println!("coverage at cov[{}] = {}", i, value);
    }
  }
  close_shmem(shm_id);
}

Full example here https://github.com/bitterbit/fuzzer-qemu/blob/fb9170ba1f2723592844ee368fcc33ef25b04f39/src/src/main.rs

AFL ForkServer

Jann Horn introduced the idea of a fork-server to AFL. In the fork-server mode, instead of running the target from the beginning for each test case, we let the code arrive at a key point where we fork. Then each time the QEMU exits the father process forks again. This can be thought of a cheap snapshot mechanism.

In this setup we have a fuzzer, qemu-father and qemu-child, the fuzzer and the qemu-father communicate using pipes while the child is re-spawned after each test case. Each time the child is done the father can fork again to create another child. This helps avoid running the "setup" code each time we want to run our target, which helps improve performance.

In practice the communication between the fuzzer and the qemu-father is made out of two pipes, both are created by the fuzzer and given constant file descriptor ids using dup2 so the qemu-father can easily find and open them. The control pipe is used by the fuzzer to control the qemu-father and the the Status pipe is used by the qemu-father to update the fuzzer that he is alive.

While cracking at the fork-server mode, one might ask why not just "rewind" the Virtual Machine back to the starting point instead of forking again? This is exactly what I was thinking and haply there is a special mode that does exactly that: Persistent Mode.

Persistent Mode?

Persistent mode can help improve the performance of your fuzzer even more. It does so by reducing the amount of "boilerplate" code that has to be run in order to run our code, much like the fork-server mechanism but to a higher extreme. So how does it work?

Every fuzzer needs to run a target multiple times, each time with a different input and record the coverage.
Instead of re-executing QEMU for each test case, we can select a key/main function which we will run in a loop and instead of closing the VM each time the target exits, we jump right back to this main function. In other words whenever the targets main function returns, instead of returning to the caller we just jump again to the beginning of our main function.

This introduces new problems:
1) How can we know what coverage belongs to which input?
2) If we are just running the same code again, why would the input be different?

Communication between Child and Father

AFL uses the two communication pipes just like in the fork server mode. The fuzzer creates new pipes before starting the QEMU process and using dup2 makes sure that each pipe has it's predefined file descriptor so QEMU can know to use them.

Our setup looks something like this

 ________             _____________             ____________
| fuzzer | ---(1)--- | QEMU father | ---(2)--- | QEMU child |
 --------             -------------             ------------

1) communicate using status and control pipes
2) communicate using STOP and CONT signals

We have the fuzzer communicating with the QEMU father using the control and status pipes. Previously using the fork-server mode a new child was created for each test case, making it easy for the father to know the status and passing the updates up to the fuzzer using the pipes.

In the persistent mode, the child does not quit so we need another mechanism to let the father know what the status of the child. This is done with STOP and CONT unix signals.

For each instruction emulated by QEMU (by the disas_a64_insn on arm64) the current program counter (pc) is compared to the address of our main function, If they are equal we prepare the VM for a new test case and wait for the father to signal us to continue.

This function trace done each time the child resets itself

• disas_a64_insn checks for pc_curr == afl_persistent_addr
• afl_persistent_loop is called and calls
• afl_persistent_iter.
• After all this is done, a SIGSTOP is raised and the execution is paused until the father sends back a SIGCONT.

To sum it up, when the child is done with a test case it raises a STOP and then when the father is done preparing the next test case it sends back a CONT signal to the child. The fathers implementation can be found inside afl_forkserver.

/* Special handling for persistent mode: if the child is alive but
    currently stopped, simply restart it with SIGCONT. */

kill(child_pid, SIGCONT);
child_stopped = 0;

In persistent mode, the father is responsible for bridging between the fuzzer and the child QEMU process. Below is sample code to run a fuzzer with QEMU in persistent mode.

Sample code to run QEMU in persistent mode

fn main() {
  let control_pipe = Pipe::new("control_pipe".to_owned());
  let status_pipe = Pipe::new("status_pipe".to_owned());

  control_pipe.dup_read(FORKSRV_FD);
  status_pipe.dup_write(FORKSRV_FD + 1);

  let child = Command::new("./qemuafl")
  .arg("./harness")
  .arg("./input_file")
  .env("AFL_QEMU_PERSISTENT_ADDR", "<address-of-main>")
  //.env...
  .spawn().unwrap();

  status_pipe.read_i32();
  info!("[+] forkserver is alive!");

  loop {
    control_pipe.write_i32(0);  
    debug!("[+] sent alive signal to child");

    let child_pid = status_pipe.read_i32();
    assert!(child_pid >= 0);
    debug!("[+] child pid {}", child_pid);

    let status = status_pipe.read_i32();
    debug!("[+] status={}", status);

    // each time we reach this point we know a testcase was 
    // fully executed. We may want to read the coverage shared mem
    // and write a new file to the input file.
    prepare_new_testcase();
  }
}

I hope you found this useful! my twitter DMs are open at @galtashma .

Sources:

• https://lcamtuf.coredump.cx/afl/technical_details.txt
• https://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html
• https://github.com/AFLplusplus/AFLplusplus/blob/stable/qemu_mode/README.persistent.md