The comments on this blog are now back from their GDPR-induced coma. I’m using a custom comment system powered by HTMX and a backend built on Loko Scheme. While writing the backend, one thing lead to another and I wanted to see if my HTTP message parser could crash. This is when I discovered that the AFL support in Loko Scheme had suffered bit rot. I have repaired it now and wanted to demonstrate how to fuzz Scheme code with Loko Scheme and AFL++.

AFL++ is a fuzzer based on the original American Fuzzy Lop (AFL) by Michał “lcamtuf” Zalewski. Loko Scheme previously had support for AFL but it inadvertently stopped working back when the .data segment was made read-only. The fuzzer support is now repaired and accessible with a command line flag.

I did find one bug in the HTTP message parser, but it was not very interesting. More interesting were the problems that I found in laesare, my Scheme reader library. AFL++ found a way to crash it and to make it hang. Oops!

Steps to Fuzzing

Here is how you fuzz a Scheme program (R6RS or R7RS):

1. First make sure you have AFL++ installed: sudo apt install afl++.
2. Install Akku.scm, the Scheme package manager. It is required by Loko Scheme.
3. Install Loko Scheme from git, or any future version later than 0.12.0.
4. Write a program that reads input from standard input and passes it to your function under test.
5. Compile that program with loko -fcoverage=afl++ --compile coverage.sps.
6. Create a directory called inputs with sample input files. It is often enough to provide a single file, but it can help speed up the fuzzing process if you have samples of a wide variety.
7. Run AFL++ with env AFL_CRASH_EXITCODE=70 afl-fuzz -i inputs/ -o outputs -- ./coverage. Watch the pretty status screen and wait for it to find crashes and timeouts.
8. Analyze the outputs.

That’s essentially it. Only steps 4—8 are really specific to fuzzing, so I will go through them in detail.

Program Under Test

You need a program that reads from standard input and passes the data to the code you want to test with AFL++. This is usually very simple to accomplish.

If your program works with textual data then you read from (current-input-port), but if it binary data then you make a new binary input port with (standard-input-port) and read from that. You can either read until you see the eof object and pass all the data directly to the code under test, or you can pass the port directly to the code under test. It depends on what your API needs as input.

Here is an example program that feeds data to get-token from laesare:

;; SPDX-License-Identifier: MIT
(import
  (rnrs)
  (laesare reader))

(let ((reader (make-reader (current-input-port) "stdin")))
  (reader-mode-set! reader 'r6rs)
  (let lp ()
    (let-values ([(type token)
                  (guard (con
                          ((lexical-violation? con)
                           (values 'condition con)))
                    (get-token reader))])
      (write type)
      (display #\space)
      (write token)
      (newline)
      (unless (eof-object? token)
        (lp)))))

Compile with Instrumentation

The program now needs to be compiled with instrumentation for AFL++. This is done by passing a new flag to loko:

.akku/env loko -fcoverage=afl++ --compile coverage.sps

The new -fcoverage=afl++ flag tells the code generator to insert a special code sequence inside every if expression.

The way that AFL++ works is that the program receives a shared memory segment from afl-fuzz that it mutates during the execution of the program. You can imagine that this program:

(if test
    conseq
    altern)

is transformed into this program:

(if test
    (begin (afl-mutate (compile-time-random)) conseq)
    (begin (afl-mutate (compile-time-random)) altern))

The expression (compile-time-random) should be fixed at compile-time and should be different for the two branches. Therefore the effect of afl-mutate on the shared memory segment will be different depending on which branch is taken at runtime, but it will be identical for different runs of the program if the input is identical.

Now suppose that this transformation is applied to the whole program. The path of all branches taken through the program for a given input generates a unique fingerprint that AFL++ uses to explore all the branches in the program. It uses some clever algorithms to mutate the input in ways that uncover new paths through the program. This is repeated thousands of times per second to eventually (maybe) find inputs that crash or hang the program.

By the way, when you use the -fcoverage=afl++ flag with Loko you also get an instrumented standard library. This means that AFL++ can see into (rnrs), (scheme base), etc, and can fuzz them along with your code. This means that AFL++ can be smarter when it searches for bugs that are triggered by how your program interacts with the standard library, which would otherwise be a black box.

Run the Fuzzer

With the binary built you can start the fuzzer:

$ env AFL_CRASH_EXITCODE=70 afl-fuzz -i inputs \
    -o outputs -- ./coverage

It will tell you if something is wrong with the program. Otherwise it starts up a screen that looks like this:

Not all crashes and timeouts are necessarily unique, many of them are likely to be triggered by the same bug.

The speed of fuzzing can shift over time, but I commonly see around 2500 4300 executions/sec using a single core on my machine. This can be further sped up by using multiple cores and system tuning that the AFL++ manual can tell you more about.

Analyze the outputs

If the “findings in depth” box reports crashes and timeouts then you can go and look in the output directory. The outputs/default/crashes directory contains files that you can just feed directly into your test program:

$ ./coverage < outputs/default/crashes/id:000000,*
…
 Frame 2 has return address #x26987C.
  Local 3: #<closure dynamic-wind /usr/local/lib/loko/loko/runtime/control.loko.sls:164:0>
  Local 4: #[reader port: #<textual-input-port "*stdin*" fd: 0>
                    filename: "stdin" line: 1 column: 40 saved-line: 1
                    saved-column: 10 fold-case?: #f mode: r6rs tolerant?: #f]
  Local 5: &lexical
 Frame 3 has return address #x24282F.
  Local 0: #f
  Local 1: 0
  Local 2: 0
End of stack trace.
The condition has 6 components:
 1. &assertion &violation &serious
 2. &who: get-token
 3. &who: "/usr/local/lib/loko/laesare/reader.sls:460:0"
 4. &message: "Type error: expected a fixnum"
 5. &program-counter: #x2E68F1
 6. &continuation
     k: #<closure continuation /usr/local/lib/loko/loko/runtime/control.loko.sls:152:21>
End of condition components.
…

This tells us there is a crash in the get-token procedure. Unfortunately this is a huge procedure and Loko does not yet generate DWARF information that lets us get source line information from the instruction pointer. We know that something in get-token expected a fixnum, but Loko is a bit sloppy with the &who condition when it comes to assertions from inlined built-ins.

We can use objdump -d ./coverage and look for the instruction at 0x2E68F1 or the instruction that jumps to that address and try to make sense of the context. But there is another way.

More Tools for Easier Fun

AFL++ comes with tools that let you analyze the crashes and minimize the inputs. When you report a bug found using a fuzzer it is important to first use a minimizer to find a minimal reproducer. The person reading your bug report does not want to have to guess which parts of the input are relevant and which are noise. This applies also to us when we’re the ones using AFL++ for our own code.

Minimize with afl-tmin

Here is how you run the minimizer:

$ env AFL_CRASH_EXITCODE=70 afl-tmin  \
  -i outputs/default/crashes/id:000000,* \
  -o crash -- ./coverage

The afl-tmin program uses the same binary as before but has a different goal: remove as much of the input as possible.

This is what happened to the file:

$ hexdump outputs/default/crashes/id:000000,*
0000000 0023 0100 2300 0000 0001 5c23 4678 4646
0000010 4646 4646 4646 4646 4646 4646 4646 4646
0000020 4646 4646 4646 4646 4623 4646 1821 3070
0000030 1818 1818 1818 1702 1818 5c00 7038
000003e
$ hexdump crash
0000000 5c23 4678 3030 3030 3030 3030 3030 3030
0000010 3030 0030                              
0000013
$ cat -vet crash
#\xF000000000000000

AFL++ has just told us that laesare crashes if it attempts to read a large character constant! That bug is now fixed in the git repo.

Perhaps even more impressive is that the minimizer works even when the program hangs and it turns out that (string->number "0F800000") hangs Loko Scheme. Oops again!

Analyze with afl-analyze

The analyzer is another fun tool and here is how you run it:

$ afl-analyze -i crash -- ./coverage

In this case we already know what the problem is a character constant that is too large, so it is not telling us anything new. But it has figured out that the middle zeros do not really affect the program flow, which can be useful information when analyzing other test cases.

tl;dr

Fuzzing is a powerful technique that automatically searches for inputs that crash or hang your program. Loko Scheme can now be used with AFL++ to fuzz Scheme programs.

Write a program coverage.sps that passes standard input to the procedure you want to test and then compile it with a recent Loko Scheme:

mkdir inputs
echo '()' > inputs/nil
.akku/env loko -ftarget=linux -fcoverage=afl++ --compile coverage.sps
env AFL_CRASH_EXITCODE=70 afl-fuzz -i inputs -o outputs -- ./coverage