Testing a parser

Content

All the parsers I wrote until now have a common underlying issue: they are recursive.

This means that with certain inputs it is possible to overflow the stack.

Why it is not enough to limit the amount of recursive calls

An implementation could use a counter and exit gracefully once the counter reaches a predefined maximum value, thus imposing an upper limit to the amount of recursive calls.

But since there is no way in C++ to query how big the stack is, there is also no safe upper bound that can be defined.

Is a counter of 10 enough? 100? 1000? Should the limit be a constant, or provided by the user of the parser?

And last, since all the parsers have no fixed limitation about the number of elements in an array or object, why should it have one for the number of subobjects?

Although it is not possible to query how much memory is available it is possible to handle failure gracefully.

Even on systems where it is not possible to allocate, using a buffer with a maximum length might still be better than recursive implementation: static analysis can get better insight if there is a stack overflow.

Non-recursive parser

A non-recursive parser needs to implement its own stack, which would use the heap to grow dynamically.

For brevity, I wrote an implementation only for the SAX parser implemented on top of a pull parser:

#include <vector>

enum class arr_or_obj{arr, obj};

// true if added element to stack and caller should evaluate next stack element
bool parse_json_impl(parser& p, json_callbacks& cb, std::vector<arr_or_obj>& stack){
       if(             p.null()   ) cb.on_null();
  else if(auto value = p.boolean()) cb.on_bool(*value);
  else if(auto value = p.string() ) cb.on_string(*value);
  else if(auto value = p.number() ) cb.on_number(*value);
  else if(p.array_start())         {cb.on_array_begin();stack.emplace_back(arr_or_obj::arr); return true;}
  else if(p.object_start())        {cb.on_object_begin();stack.emplace_back(arr_or_obj::obj); return true;}
  else cb.on_error();
  return false;
}

void parse_json(std::string_view sv, json_callbacks& cb) {
  auto p = parser(sv);
  std::vector<arr_or_obj> stack;
  if(not p.object_start()){
    cb.on_error();
  }
  cb.on_object_begin();
  stack.emplace_back(arr_or_obj::obj);
  while(not stack.empty()){
    const auto v = stack.back();

    if(v == arr_or_obj::arr){
      bool gonext = false;
      while(not gonext and p.element()){
        gonext = parse_json_impl(p, cb, stack);
      }
      if(gonext){continue;}
      if(not p.array_finish()) cb.on_error();
      cb.on_array_end();
    } else if(v == arr_or_obj::obj){
      bool gonext = false;
      #if 1
      while(auto key = p.key()) {
        cb.on_key(*key);
        gonext = parse_json_impl(p, cb, stack);
        if(gonext){break;}
      }
      #else
      for(auto key = p.key(); key.has_value() and not gonext;
        key = !gonext ? p.key() : std::optional<std::string_view>()
      ){
        cb.on_key(*key);
        gonext = parse_json_impl(p, cb, stack);
      }
      #endif
      if(gonext){continue;}
      if(not p.object_finish()) cb.on_error();
      cb.on_object_end();
    } else {
      assert(false);
    }
    stack.pop_back();
  }
}

I almost never have to deal with nested loops. In the first iteration break did the wrong thing. Also, I really dislike the code for iterating objects, since there are multiple conditions that need to be controlled at different moments, contrary to the case of an array.

I tried to rewrite it as for loop, but the result is even less legible.

Fortunately, there is another approach that I did not recognize at the beginning: avoid the nested loops.

Instead of trying to iterate over all elements of an array at once, just continue after every element. The same holds for the key-values pairs in an object:

no nested loops
void parse_json2(std::string_view sv, json_callbacks& cb) {
  auto p = parser(sv);
  std::vector<arr_or_obj> stack;
  if(not p.object_start()){
    cb.on_error();
  }
  cb.on_object_begin();
  stack.emplace_back(arr_or_obj::obj);
  while(not stack.empty()){
    const auto v = stack.back();
    if(v == arr_or_obj::arr){
      if(p.element()){
        parse_json_impl(p, cb, stack);
        continue;
      }
      if(not p.array_finish()) cb.on_error();
      cb.on_array_end();
    } else if(v == arr_or_obj::obj){
      if(auto key = p.key()) {
        cb.on_key(*key);
        parse_json_impl(p, cb, stack);
        continue;
      }
      if(not p.object_finish()) cb.on_error();
      cb.on_object_end();
    } else {
      assert(false);
    }
    stack.pop_back();
  }
}

The code is simpler, with no need to use an additional variable to track if one needs to continue in the outer loop, and no complex conditions to test while iterating over keys. Handling all elements in an array (and object) is more implicit, but it does not seem to be a major drawback.

Possible further improvements

Instead of allocating memory for every object that needs to be added to the stack, our stack variable could provide use a local array of some amount of elements, and resort to the heap only after a certain amount of elements, similarly to how some std::string implementation store short strings.

In this particular case, since std::vector<arr_or_obj> stack; uses only two types of elements, using std::vector<bool> stack; would reduce memory usage further. Normally using std::vector<bool> is discouraged, but in this case, we only get the benefits of the class specialization, which uses a bitmap internally.

The fact that it is possible to use std::vector<bool> has to do that our stack only needs to store the information if we are parsing an array or object. In the general case, this is not possible, and one needs to store more information, just like createdom_callbacks does.

The implementation is also relatively simple because json_callbacks does not get any additional state, and a std::vector<bool> is sufficient.

But for most use cases, when parsing the content directly or writing a DOM parser, one needs to store more data.

If we need the whole state, one can just copy the state from createdom_callbacks.

Thus the overhead between the non-recursive DOM parser on top of SAX versus a handwritten non-recursive DOM parser is probably negligible, as both implementations will have the stack, the DOM, and the SAX parser has additionally the std::vector<bool>:

Fuzzing

All my implementation went at least through a couple of revisions, and there were mainly two types of errors, apart from logical errors:

  • dereferencing nullptr in the SAX parser

  • an out of bound read

Both errors can be avoided at runtime with appropriate constructs; static analyzers can also help here.

Especially for parsers, fuzzing can be extremely convenient. In less than a couple of seconds AFL++ found both types of errors.

What is AFL++

AFL++ is a fork of AFL. With this program it is possible to stress-test a specific API; what the program does is to modify an input file, and feed it to the executable. If the tested program crashes or hangs, AFL stores the file on disk. The test program needs to be instrumented accordingly so that AFL can "see" which paths have been executed, and it will try to execute all possible execution paths that depend on the input.

Setting up AFL++

The setup process is not that complicated:

# install afl++
sudo apt install afl++

# configure the machine to take advantage of all cores
# configs will be reset at reboot
# if you are not sure about this step, afl-fuzz will complain and explain
# what can be done
sudo afl-system-config

# create a valid input as initial test
mkdir -p input;
echo 'hello world!'>input/test

# create a program for testing
printf '//test program that reads from stdin
#include <iostream>
#include <string>

int main(){
  auto str = std::string(std::istreambuf_iterator<char>(std::cin),std::istreambuf_iterator<char>());
  (void) str.at(4);
}
' > main.cpp

# compile the program with compiler-wrapper
afl-c++ -o main main.cpp

# avoid storing results directly on disk, to prevent excessive usage
# in my case, tmp is stored on RAM, so use there a subfolder
afl-fuzz -i input -o /tmp/output -- ./main
Warning ⚠️
Ensure that afl-fuzz is not continuosly writing and reading data from your disk. You can use iotop, iostat, htop, nmon or other tools to enusre that afl-fuzz is not wearing your drive. In my case, /tmp is a tmpfs file system, but if it is not your case, consider using AFL_TMPDIR and a RAM-disk. Consider also monitoring you CPU and memory usage.

After a little while (a couple of seconds at most), the output should look like the following:

            american fuzzy lop ++4.21c {default} (./main) [explore]
┌─ process timing ────────────────────────────────────┬─ overall results ────┐
│        run time : 0 days, 0 hrs, 0 min, 2 sec       │  cycles done : 0     │
│   last new find : 0 days, 0 hrs, 0 min, 0 sec       │ corpus count : 10    │
│last saved crash : 0 days, 0 hrs, 0 min, 1 sec       │saved crashes : 2     │
│ last saved hang : none seen yet                     │  saved hangs : 0     │
├─ cycle progress ─────────────────────┬─ map coverage┴──────────────────────┤
│  now processing : 0.1 (0.0%)         │    map density : 23.36% / 41.12%    │
│  runs timed out : 0 (0.00%)          │ count coverage : 6.43 bits/tuple    │
├─ stage progress ─────────────────────┼─ findings in depth ─────────────────┤
│  now trying : havoc                  │ favored items : 1 (10.00%)          │
│ stage execs : 656/12.8k (5.12%)      │  new edges on : 3 (30.00%)          │
│ total execs : 739                    │ total crashes : 12 (2 saved)        │
│  exec speed : 342.3/sec              │  total tmouts : 0 (0 saved)         │
├─ fuzzing strategy yields ────────────┴─────────────┬─ item geometry ───────┤
│   bit flips : 0/0, 0/0, 0/0                        │    levels : 2         │
│  byte flips : 0/0, 0/0, 0/0                        │   pending : 10        │
│ arithmetics : 0/0, 0/0, 0/0                        │  pend fav : 1         │
│  known ints : 0/0, 0/0, 0/0                        │ own finds : 9         │
│  dictionary : 0/0, 0/0, 0/0, 0/0                   │  imported : 0         │
│havoc/splice : 0/0, 0/0                             │ stability : 100.00%   │
│py/custom/rq : unused, unused, unused, unused       ├───────────────────────┘
│    trim/eff : 30.77%/3, n/a                        │          [cpu000: 50%]
└─ strategy: explore ────────── state: started :-) ──┘

With saved crashes: and total crashes followed by a number different than zero, highlighted in red.

You can stop the execution anytime with Ctrl+C, and look in /tmp/output/default/crashes/ the files that lead to a crash, and try them out directly:

> cat /tmp/output/default/crashes/id:000000,sig:06,src:000000,time:235,execs:88,op:havoc,rep:2 | ./main
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 4) >= this->size() (which is 2)
zsh: done             cat  |
zsh: IOT instruction  ./main

Test from argv filename parameter

If your program takes a filename as an input parameter instead of stdin, then you should use the placeholder @@

printf '//test program that reads from stdin
#include <fstream>
#include <streambuf>
#include <string>

int main(int argc, char** argv){
  if(argc < 2) return 1;
  std::ifstream t(argv[1]);
  auto str = std::string(std::istreambuf_iterator<char>(t),std::istreambuf_iterator<char>());
  (void) str.at(4);
}
' > main.cpp

afl-c++ -o main main.cpp

# avoid storing results directly on disk, to prevent excessive usage
# in my case, tmp is stored on RAM, so use there a subfolder
afl-fuzz -i input -o /tmp/output -- ./main '@@'

afl-fuzz will replace @@ with the actual file name it generated.

Again, you can test directly the file that causes the process to crash:

./main /tmp/output/default/crashes/id:000000,sig:06,src:000000,time:229,execs:70,op:havoc,rep:12
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 4) >= this->size() (which is 1)
zsh: IOT instruction  ./main

Having written that, if possible I would avoid reading from a file; using stdin is generally faster. But if you really want speed, read further.

Test with persistent mode

Persistent mode 🗄️ is a technique for testing your program faster.

printf '//test program that uses persistent mode
#include <cstdio>
#include <string_view>
#include <unistd.h>

__AFL_FUZZ_INIT();

int main() {

  // command line arguments, initialization, ...
#ifdef __AFL_HAVE_MANUAL_CONTROL
  __AFL_INIT();
#endif

  unsigned char *buf = __AFL_FUZZ_TESTCASE_BUF;
  while (__AFL_LOOP(10000)) {
    int len = __AFL_FUZZ_TESTCASE_LEN;
    auto str = std::string_view(reinterpret_cast<const char*>(buf), len);
    (void) str.at(4);
  }
}
' > main.cpp

afl-c++ -o main main.cpp
afl-fuzz -i input -o /tmp/output -- ./main

With this construct, the program is still reading from stdin, but afl-fuzz will not start the program for every test case.

This makes fuzzing much faster, as the whole initialization routine does not need to be repeated every time, and there is less need to read data from the disk (the binary itself, linked libraries, …​).

For comparison, on the same machine/environment, the output of afl-fuzz looks like

            american fuzzy lop ++4.21c {default} (./main) [explore]
┌─ process timing ────────────────────────────────────┬─ overall results ────┐
│        run time : 0 days, 0 hrs, 0 min, 1 sec       │  cycles done : 13    │
│   last new find : none yet (odd, check syntax!)     │ corpus count : 1     │
│last saved crash : 0 days, 0 hrs, 0 min, 1 sec       │saved crashes : 1     │
│ last saved hang : none seen yet                     │  saved hangs : 0     │
├─ cycle progress ─────────────────────┬─ map coverage┴──────────────────────┤
│  now processing : 0.41 (0.0%)        │    map density : 17.65% / 17.65%    │
│  runs timed out : 0 (0.00%)          │ count coverage : 118.33 bits/tuple  │
├─ stage progress ─────────────────────┼─ findings in depth ─────────────────┤
│  now trying : havoc                  │ favored items : 1 (100.00%)         │
│ stage execs : 25/100 (25.00%)        │  new edges on : 1 (100.00%)         │
│ total execs : 4049                   │ total crashes : 568 (1 saved)       │
│  exec speed : 8516/sec               │  total tmouts : 0 (0 saved)         │
├─ fuzzing strategy yields ────────────┴─────────────┬─ item geometry ───────┤
│   bit flips : 0/0, 0/0, 0/0                        │    levels : 1         │
│  byte flips : 0/0, 0/0, 0/0                        │   pending : 0         │
│ arithmetics : 0/0, 0/0, 0/0                        │  pend fav : 0         │
│  known ints : 0/0, 0/0, 0/0                        │ own finds : 0         │
│  dictionary : 0/0, 0/0, 0/0, 0/0                   │  imported : 0         │
│havoc/splice : 1/4000, 0/0                          │ stability : 100.00%   │
│py/custom/rq : unused, unused, unused, unused       ├───────────────────────┘
│    trim/eff : 88.89%/11, n/a                       │          [cpu000: 62%]
└─ strategy: explore ────────── state: started :-) ──┘

and exec speed changed from 342.3/sec to 8516/sec; nearly two orders of magnitude faster!

Counterintuitively, replacing std::string_view with std::string, makes the program run even faster:

printf '//test program that uses persistent mode
#include <cstdio>
#include <string_view>
#include <unistd.h>

__AFL_FUZZ_INIT();

int main() {

  // command line arguments, initialization, ...
#ifdef __AFL_HAVE_MANUAL_CONTROL
  __AFL_INIT();
#endif

  unsigned char *buf = __AFL_FUZZ_TESTCASE_BUF;
  while (__AFL_LOOP(10000)) {
    int len = __AFL_FUZZ_TESTCASE_LEN;
    auto str = std::string(reinterpret_cast<const char*>(buf), len);
    (void) str.at(4);
  }
}
' > main.cpp

afl-c++ -o main main.cpp
afl-fuzz -i input -o /tmp/output -- ./main

The output is

           american fuzzy lop ++4.21c {default} (./main) [explore]
┌─ process timing ────────────────────────────────────┬─ overall results ────┐
│        run time : 0 days, 0 hrs, 0 min, 2 sec       │  cycles done : 41    │
│   last new find : 0 days, 0 hrs, 0 min, 2 sec       │ corpus count : 2     │
│last saved crash : 0 days, 0 hrs, 0 min, 2 sec       │saved crashes : 3     │
│ last saved hang : none seen yet                     │  saved hangs : 0     │
├─ cycle progress ─────────────────────┬─ map coverage┴──────────────────────┤
│  now processing : 1.90 (50.0%)       │    map density : 24.14% / 31.03%    │
│  runs timed out : 0 (0.00%)          │ count coverage : 30.22 bits/tuple   │
├─ stage progress ─────────────────────┼─ findings in depth ─────────────────┤
│  now trying : havoc                  │ favored items : 2 (100.00%)         │
│ stage execs : 81/100 (81.00%)        │  new edges on : 2 (100.00%)         │
│ total execs : 46.7k                  │ total crashes : 1591 (3 saved)      │
│  exec speed : 17.8k/sec              │  total tmouts : 0 (0 saved)         │
├─ fuzzing strategy yields ────────────┴─────────────┬─ item geometry ───────┤
│   bit flips : 0/0, 0/0, 0/0                        │    levels : 2         │
│  byte flips : 0/0, 0/0, 0/0                        │   pending : 0         │
│ arithmetics : 0/0, 0/0, 0/0                        │  pend fav : 0         │
│  known ints : 0/0, 0/0, 0/0                        │ own finds : 1         │
│  dictionary : 0/0, 0/0, 0/0, 0/0                   │  imported : 0         │
│havoc/splice : 2/16.7k, 2/29.9k                     │ stability : 88.89%    │
│py/custom/rq : unused, unused, unused, unused       ├───────────────────────┘
│    trim/eff : 13.33%/14, n/a                       │          [cpu003: 50%]
└─ strategy: explore ────────── state: started :-) ──┘

17.8k/sec against 8516/sec!

I have currently no good explanation for this behavior.

Parallel fuzzing

The easiest way to speed up a long process is to split in into smaller parts, and execute the smaller process in parallel but fuzzing in parallel is not an embarrassingly parallel problem; you want to avoid that two different instances test the same input or execution paths.

Thus the different fuzzer instances need to communicate what they are doing or going to do.

afl-fuzz supports fuzzing in parallel, I also wrote some years ago some wrapper scripts for monitoring the different instances with tmux:

afl-c++ -o main main.cpp
afl-pfuzz -i input -o /tmp/output  --session session-name -- ./main

afl-pfuzz creates a tmux session, with multiple afl-fuzz instances running. Internally the script uses the flag -M and -S.

The call to sleep where necessary to avoid binding multiple instances to the same CPU.

Detect if running under AFL

When a target is fuzzed, there are two things to consider:

  • the execution should be as deterministic as possible, it should solely depend on the input parameter

  • the execution should be as fast as possible

The most obvious way, and also most recommended, is by using the preprocessor, and verifying if __AFL_FUZZ_TESTCASE_LEN is defined.

I actually would like to reuse the exact same binary/library; it has the advantage I can half the amount of builds, and use the same binary for fuzzing and for regular tests. This means I want to detect at runtime if the binary is being fuzzed.

The function cond_exec_with_afl hides most of the implementation details. It can be used both with afl-c++ and a normal compiler, and at runtime, it verifies if the executable is being executed with afl-fuzz.

The business logic, apart from the input, also gets a boolean value, which can be used, for example, to disable logging at runtime.

If the program si being executed from afl_fuzz, then a program should avoid writing to the console, asking user input, using random numbers, and so on.

#include <iostream>
#include <string>

#ifdef __AFL_FUZZ_TESTCASE_LEN
#include <unistd.h>
__AFL_FUZZ_INIT();
#else
#endif

template<class F>
void cond_exec_with_afl(F f) noexcept {
#ifdef __AFL_HAVE_MANUAL_CONTROL
  __AFL_INIT();
#endif

#ifdef __AFL_FUZZ_TESTCASE_LEN
  if(std::getenv("__AFL_SHM_ID") != nullptr){
    unsigned char* buf = __AFL_FUZZ_TESTCASE_BUF;
    while (__AFL_LOOP(10000)) {
      int len = __AFL_FUZZ_TESTCASE_LEN;
      (void)f(true, std::string_view(reinterpret_cast<const char*>(buf), len));
    }
  }
  else
#endif
  {
    (void)f(false, std::string(std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()));
  }
}

int main() {
  cond_exec_with_afl([](bool with_afl, std::string_view sv){
    try{
      (void) parse_json(sv);
      if(not with_afl) std::puts("Parsed succesfully");
    } catch (...){
      if(not with_afl) std::puts("Error while parsing");
    }
  });
}

I could not find any documentation for __AFL_SHM_ID, but it is the official way to achieve what I wanted.

If possible, the tested code should also avoid to modify global state, unless it reverts the changes at the end of the test. This is not a strict requirement, but it helps to make the persistent mode more stable.

Speed up functions depending on a file

If an API depends on a file, it might not be easy or possible to change it to use a buffer.

In particular, if an API takes a FILE*, then you can use fmemopen 🗄️, which creates a FILE* that points to some memory.

If the API requires a file descriptor (an int), then it is possible to use memfd_create. Using fileno 🗄️ on the value returned by fmemopen seems to always fail (it returns -1).

Last, but not least, if the API depends on a file name, then you can use memfd_create, and then "/proc/self/fd/<value>" as filename. If possible, you can avoid using memfd_create, and "just" use stdin and hardcode "/proc/self/fd/0" as filename:

printf 'int main(){
  std::ifstream t("/proc/self/fd/0");
  auto str = std::string(std::istreambuf_iterator<char>(t),std::istreambuf_iterator<char>());
  std::puts(str.c_str());
}'>test.cpp
c++ -o test test.cpp && echo "test read from stdin" | ./test

Expose more bugs

An assert is ideally dead code; it should always evaluate to true.

I use them to document invariants and fuzzers can help to ensure that they are correct. Throwing an exception is problematic because someone might be catching it. With a non-recoverable error, the fuzzer can report the errors as such.

If you feel uneasy about using assert for productive code, as it might not be well-understood, or tested, and even fuzzers might only partially test it, you could consider using the assert only when fuzzing.

Another well-recommended practice is to use sanitizers, as they help to find bugs more easily.

Just add, for example -fsanitize=address to the compiler flags.

Last but not least, use a hardened 🗄️ standard library will help too.

Future libraries might be hardened by default 🗄️, but not necessarily when building with optimization. In the case of libstdc++, one needs to define _GLIBCXX_ASSERTIONS, while for lib++ one needs to set _LIBCPP_HARDENING_MODE to one specific value.

Otherwise, there might be additional compiler flags that can help to find bugs more easily, like _FORTIFY_SOURCE, althoug if you GCC version is recent enough, you should give -fhardened 🗄️ a try.

Choose the initial test input

For the JSON parser, you can use '{}' as the starting test case, and at some point afl-fuzz should cover all paths. As brute force approaches work best when they are fast, using a good starting point and using persistent mode is important.

A test case like {"a":"b","a":"c","c":[1,-2,null,true,false]} is much better, as it will execute most if not all, functions of all parsers. Which gives the AFL++ a much better starting point.

It also generates more interesting test cases that can be used for verifying if the parser accepts invalid input as valid, or valid input as invalid.

The more complex a format, the more important a good input is. For graphic libraries, providing small and valid images should be the way to go.

Note 📝
one of the generated test files had 17806 times the character '['. Thus even if such files will not be parsed in practice, having a non-recursive implementation helps, as otherwise one would need to analyze and ignore those crashes reported by the fuzzer.

Alternatives to AFL++

There is libFuzzer 🗄️, of the LLVM project, although it is in "manteinance mode":

The original authors of libFuzzer have stopped active work on it and switched to working on another fuzzing engine, Centipede. LibFuzzer is still fully supported in that important bugs will get fixed. However, please do not expect major new features or code reviews, other than for bug fixes.

This is not necessarily a bad thing, the product is stable and works as expected, it’s just that new feature are not planned. Since there is always a matching clang version, it should also be up to date.

The project centipede has been archived, and development shifted to FuzzTest, which is not only a fuzzer, but a whole test suite.

Example with libFuzzer

For completeness, and example with libFuzzer

printf '//test program that uses libFuzzer
#include <string_view>

extern "C" int LLVMFuzzerTestOneInput(const unsigned char* buf, size_t len) {
    auto str = std::string_view(reinterpret_cast<const char*>(buf), len);
    (void) str.at(4);
    return 0;
}
' > main.cpp
mkdir -p input;
echo 'hello world!'>input/test
clang++ -fsanitize=fuzzer -o main main.cpp
./main ./input

Contrary to ALF++ you do not control the main function, and instead of using a helper program for testing your binary, you can execute it directly.

AFL++ and libFuzzer

It turns out that it is possible to use libFuzzer together with AFL++, but setting it up lead to an unexpected surprise:

printf '//test program that uses libFuzzer
#include <string_view>

extern "C" int LLVMFuzzerTestOneInput(const unsigned char* buf, size_t len) {
    auto str = std::string_view(reinterpret_cast<const char*>(buf), len);
    (void) str.at(4); // crash on invalid data
    return 0;
}
' > main.cpp


afl-clang-fast++  -fsanitize=fuzzer -o main main.cpp
afl-fuzz -i input -o /tmp/output -- ./main

it crashes on a valid input!

It seems that the initial string is ##SI, exactly four character, so I just found it out by accident. If the program can handle this string gracefully, then afl-fuzz start succesfully and continues to fuzz the target, I guess that subsequent inputs are passed correctly to LLVMFuzzerTestOneInput.

From a performance perspective, there was no big difference between using afl-fuzz with and without libfuzz, although the outcome might vary on specific programs, compiler flags, environments.

Since there is something wrong during the initialisation, I do not think I’m going to use this combination at the moment.

Conclusion

This is by no mean a complete introduction to fuzzin or ALF++, you should check the corresponding documentation, in particular tools like afl-tmin and afl-cmin.

Once AFL++ did not manage to crash (or hang) the parser, and with a non-recursive implementation, I’m confident enough that the presented parsers can be used for a subset of JSON files.

Granted, those two properties do still not ensure how well the parser can handle the input data, but

  • the non-recursive implementations do not make it susceptible to stack overflows

  • using a fuzzer helps to guarantee that there are no inputs that lead to non-recoverable errors

  • using a fuzzer also helps to determine if the parser does not hang on certain inputs

  • using a fuzzer helps to determine if it is not too slow

A possible next step is to collect the files that AFL generated, and manually verify if they are parsed or rejected correctly by the parser.

Also, if different libraries parse the same type of data, a fuzzer can be used to ensure that both libraries produce the same output. This makes it possible, for example, to replace one library with another, and test automatically if there are any regressions (or improvements).

It is not always easy to fuzz a program, especially if it is slow, or depends on complex data structures.

But every program that has an interface that deals with raw data or text input, like format parsers and compression algorithms, which should handle malformed data gracefully, should really get in the situation where a fuzzer is at least part of the release process.


If you have questions, comments, or found typos, the notes are not clear, or there are some errors; then just contact me.