[Automated Fuzz Driver Generation] Dive Into GraphFuzz

Contents

1. Overview
2. Endpoint & Graphs
3. How it Works
4. Simple Demo: Car
5. Personal Thoughts
6. References

---

1. Overview

GraphFuzz is a software testing tool. It is focused to API testing by invoking API functions at valid order that are mutated from a structure of a graph. With this mechanism, GraphFuzz is able to find bugs that arise from invoking API functions in a certain order.
 
The main objective of GraphFuzz is to automatically search through various 'valid' api interaction space that produces a bug. This tool maneuvers through this space with the help of a graph mutation algorithm to form only valid graphs. 

Unit testing can be seen as finding a bug by testing a single API interaction while GraphFuzz tests multiple different API iteraction.

---

2. Endpoint & Graphs

GraphFuzz defines a single API function as an endpoint. Each endpoint can be assigned with an input, output, and an argument. Input and output receives and returns an object while arguments are embedded into the code. The following image shows one example of a single endpoint.

As seen in the image above, the drive function from Car class is an endpoint that receives an Car object and a Route object as its input and returning both Car and Route object as an output. With these information of multiple different API function defined as an endpoint, GraphFuzz forms and mutates graphs that are valid interactions. The image below shows a short simple graph of a valid API interaction. For the following graph, each API funcitons are invoked in the given order.

---

3. How it Works

Schema

The target API we aim to test should be described as a schema. The schema rules can be found in this link (by GraphFuzz). A schema is written in YAML describing functions, class, structures to be tested.

 
Harness Files

With the given schema, GraphFuzz's command line interface, gfuzz, generates a harness file. This file contains an endpoint driver for all the endpoints described in the schema. It also holds the initialization of an array that hold all the endpoint drivers as function pointer.
 
The harness file is compiled and linked with GraphFuzz's core source code, producing a standard LibFuzzer executable (LLVM libfuzzer). When such harness file is compiled executed, libfuzzer selects a raw byte stream in the corpus. It then utilizes protobuf (google's protocol buffers) to convert the raw byte stream into a structure of a graph. Utilizeing libfuzzer's interface LLVMFuzzerCustomMutator and LLVMFuzzerCustomCrossOver, the given graph is mutated. Finally, in LLVMFuzzerTestOneInput, each API function are invoked from the initialized array of function pointers according to the graph.
 
The image on the left pictures the graph mutation algorithm. The image on the right shows the flow of testing an API interaction through GraphFuzz. When a selected graph has new coverage, it is saved back into the corpus for more testing. (Both images are form figure within the paper of GraphFuzz)

---

4. Simple Demo: Car

Let us say that we are to test the API given in the following C++ source code.
By creating a route and adding points, a car can drive, following the points in given route. When the route contains "CRASH" as its first 5 points, the program falls into the planted trap.

// lib.h source code file in C++
#include <cstring>
#include <vector>

class Route {
public:
    Route(): history(0) {}
    void checkpoint(char flag) {
        history.push_back(flag);
    }

    std::vector<char> history;
};

class Car {
public:
    Car() {}

    void drive(Route *route) {
        if (route->history.size() >= 5 && \
            route->history[0] == 'C' && \
            route->history[1] == 'R' && \
            route->history[2] == 'A' && \
            route->history[3] == 'S' && \
            route->history[4] == 'H') {
                __builtin_trap();
            }
    }
};

We can describe lib.h in schema format:

Route:
  type: struct
  name: Route
  default_destructor: True
  headers:
  - lib.h
  methods:
  - Route():
      inputs: []
      outputs: ['Route']
      args: []
      exec: |
        $o0 = new Route();
  - checkpoint(char flag):
      inputs: ['Route']
      outputs: ['Route']
      args: ['char']
      exec: |
        $i0->checkpoint($a0);
        $o0 = $i0;


Car:
  type: struct
  name: Car
  default_destructor: True
  headers:
  - lib.h
  methods:
  - Car():
      inputs: []
      outputs: ['Car']
      exec: |
        $o0 = new Car();
  - drive(Route route):
      inputs: ['Car', 'Route']
      outputs: ['Car', 'Route']
      args: []
      exec: |
        $i0->drive($i1);
        $o0 = $i0;
        $o1 = $i1;

Both the functions in Car and Route class are described. With gfuzz, with this schema, harness file is automatically generated contained a total of 6 endpoint driver and an initialization of the array containing all the endpoint driver as a function pointer.

// fuzz_exec.cpp (harness file, a standard libfuzzer executable when compiled/linked)
#include "lib.h"


#include <string.h>
#include <stdlib.h>
#include <cstdint>

extern "C" int graphfuzz_try();
extern "C" void graphfuzz_bail();

extern "C" void __attribute__((visibility ("default"))) global_init(int *argc, char ***argv) {

}

extern "C" void __attribute__((visibility ("default"))) shim_init() {

}

extern "C" void __attribute__((visibility ("default"))) shim_finalize() {

}


#define MAKE(t) static_cast<t *>(calloc(sizeof(t), 1))

struct GFUZZ_BUNDLE {
public:
    void *active;
    void *inactive;
    GFUZZ_BUNDLE(void *_active, void *_inactive): active(_active), inactive(_inactive) {}
};

#define BUNDLE(a,b) new GFUZZ_BUNDLE((void *)a, (void *)b)



/* CPPScope(name=Route()) */
extern "C" void shim_0(void **in_ref, void **out_ref, const char *context) {
    Route *_o0;
    _o0 = new Route();
    
    out_ref[0] = reinterpret_cast<void *>(_o0);
}


/* CPPScope(name=checkpoint(char flag)) */
extern "C" void shim_1(void **in_ref, void **out_ref, const char *context) {
    Route *_i0 = reinterpret_cast<Route *>(in_ref[0]);
    char _a0;
    memcpy(&_a0, context + 0, sizeof(char));
    Route *_o0;
    _i0->checkpoint(_a0);
    _o0 = _i0;
    
    out_ref[0] = reinterpret_cast<void *>(_o0);
}


/* CPPScope(name=(auto) Route::~Route();) */
extern "C" void shim_2(void **in_ref, void **out_ref, const char *context) {
    Route *_i0 = reinterpret_cast<Route *>(in_ref[0]);
    free(_i0);
    
                    
}


/* CPPScope(name=Car()) */
extern "C" void shim_3(void **in_ref, void **out_ref, const char *context) {
    Car *_o0;
    _o0 = new Car();
    
    out_ref[0] = reinterpret_cast<void *>(_o0);
}


/* CPPScope(name=drive(Route route)) */
extern "C" void shim_4(void **in_ref, void **out_ref, const char *context) {
    Car *_i0 = reinterpret_cast<Car *>(in_ref[0]);
    Route *_i1 = reinterpret_cast<Route *>(in_ref[1]);
    Car *_o0;
    Route *_o1;
    _i0->drive(_i1);
    _o0 = _i0;
    _o1 = _i1;
    
    out_ref[0] = reinterpret_cast<void *>(_o0);
    out_ref[1] = reinterpret_cast<void *>(_o1);
}


/* CPPScope(name=(auto) Car::~Car();) */
extern "C" void shim_5(void **in_ref, void **out_ref, const char *context) {
    Car *_i0 = reinterpret_cast<Car *>(in_ref[0]);
    free(_i0);
    
                    
}


void __attribute__((visibility ("default"))) (*FUZZER_SHIMS[])(void **, void **, const char *) = {
    &shim_0,
    &shim_1,
    &shim_2,
    &shim_3,
    &shim_4,
    &shim_5,
};

Compiling and linking the harness file with the following command produces a standard libfuzzer executable.

# fuzz_exec: main fuzzer, executes test cases
clang++ fuzz_exec.cpp \
    -lgraphfuzz -lprotobuf \
    -fsanitize=address,fuzzer \
    -o fuzz_exec

Through libfuzzer engine, it executes test cases to find existing bugs.
When a crash is found, we can visualize the API interaction through fuzz_write.cpp.

---

5. Personal Thoughts

• Enjoyed learning the utilization of function pointers to test different valid API interactions.
• Seems schema format have limitation of not being able to define global variables, class, and structures.
• Graph mutations are limited to randomly assigning constructed objects to the proceeding API function.
• Endpoint drivers are implemented in a specifically fixed way. What if we can make various different endpoint drivers for a single endpoint? Can this affect in a beneficial way?
• Schema without manual revision very insufficient in generating a usable harness. [such function int add(int) is not generated]

---

6. References

[1] Harrison Green, Thanassis Avgerinos, GraphFuzz: Library API Fuzzing with Lifetime-aware Dataflow Graphs
[2] GraphFuzz: Github Link

GitHub - hgarrereyn/GraphFuzz: GraphFuzz is an experimental framework for building structure-aware, library API fuzzers.

[3] GraphFuzz: Documentation

GraphFuzz

[4] GraphFuzz: Youtube Video

[5] LibFuzzer by LLVM

libFuzzer – a library for coverage-guided fuzz testing. — LLVM 18.0.0git documentation

[6] Protocol Buffer by Google

Protocol Buffers

[7] Material Studies in PPT

231010-intoGraphFuzz-v1.pptx

1.18MB