# CmpLog instrumentation

The CmpLog instrumentation enables logging of comparison operands in a shared
memory.

These values can be used by various mutators built on top of it. At the moment,
we support the Redqueen mutator (input-2-state instructions only), for details
see [the Redqueen paper](https://github.com/RUB-SysSec/redqueen).

## Build

To use CmpLog, you have to build two versions of the instrumented target
program:

* The first version is built using the regular AFL++ instrumentation.
* The second one, the CmpLog binary, is built with setting `AFL_LLVM_CMPLOG`
  during the compilation.

For example:

```
./configure --cc=~/path/to/afl-clang-fast
make
cp ./program ./program.afl
make clean
export AFL_LLVM_CMPLOG=1
./configure --cc=~/path/to/afl-clang-fast
make
cp ./program ./program.cmplog
unset AFL_LLVM_CMPLOG
```

## Use

AFL++ has the new `-c` option that needs to be used to specify the CmpLog binary
(the second build).

For example:

```
afl-fuzz -i input -o output -c ./program.cmplog -m none -- ./program.afl @@
```

Be careful with the usage of `-m` because CmpLog can map a lot of pages.

# GCC-based instrumentation for afl-fuzz

For the general instruction manual, see [docs/README.md](../docs/README.md).

For the LLVM-based instrumentation, see [README.llvm.md](README.llvm.md).

This document describes how to build and use `afl-gcc-fast` and `afl-g++-fast`,
which instrument the target with the help of gcc plugins.

TL;DR:
* Check the version of your gcc compiler: `gcc --version`
* `apt-get install gcc-VERSION-plugin-dev` or similar to install headers for gcc
  plugins.
* `gcc` and `g++` must match the gcc-VERSION you installed headers for. You can
  set `AFL_CC`/`AFL_CXX` to point to these!
* `make`
* Just use `afl-gcc-fast`/`afl-g++-fast` normally like you would do with
  `afl-clang-fast`.

## 1) Introduction

The code in this directory allows to instrument programs for AFL++ using true
compiler-level instrumentation, instead of the more crude assembly-level
rewriting approach taken by afl-gcc and afl-clang. This has several interesting
properties:

- The compiler can make many optimizations that are hard to pull off when
  manually inserting assembly. As a result, some slow, CPU-bound programs will
  run up to around faster.

  The gains are less pronounced for fast binaries, where the speed is limited
  chiefly by the cost of creating new processes. In such cases, the gain will
  probably stay within 10%.

- The instrumentation is CPU-independent. At least in principle, you should be
  able to rely on it to fuzz programs on non-x86 architectures (after building
  `afl-fuzz` with `AFL_NOX86=1`).

- Because the feature relies on the internals of GCC, it is gcc-specific and
  will *not* work with LLVM (see [README.llvm.md](README.llvm.md) for an
  alternative).

Once this implementation is shown to be sufficiently robust and portable, it
will probably replace afl-gcc. For now, it can be built separately and co-exists
with the original code.

The idea and much of the implementation comes from Laszlo Szekeres.

## 2) How to use

In order to leverage this mechanism, you need to have modern enough GCC (>=
version 4.5.0) and the plugin development headers installed on your system. That
should be all you need. On Debian machines, these headers can be acquired by
installing the `gcc-VERSION-plugin-dev` packages.

To build the instrumentation itself, type `make`. This will generate binaries
called `afl-gcc-fast` and `afl-g++-fast` in the parent directory.

The gcc and g++ compiler links have to point to gcc-VERSION - or set these by
pointing the environment variables `AFL_CC`/`AFL_CXX` to them. If the `CC`/`CXX`
environment variables have been set, those compilers will be preferred over
those from the `AFL_CC`/`AFL_CXX` settings.

Once this is done, you can instrument third-party code in a way similar to the
standard operating mode of AFL++, e.g.:

```
  CC=/path/to/afl/afl-gcc-fast
  CXX=/path/to/afl/afl-g++-fast
  export CC CXX
  ./configure [...options...]
  make
```

Note: We also used `CXX` to set the C++ compiler to `afl-g++-fast` for C++ code.

The tool honors roughly the same environmental variables as `afl-gcc` (see
[docs/env_variables.md](../docs/env_variables.md). This includes
`AFL_INST_RATIO`, `AFL_USE_ASAN`, `AFL_HARDEN`, and `AFL_DONT_OPTIMIZE`.

Note: if you want the GCC plugin to be installed on your system for all users,
you need to build it before issuing 'make install' in the parent directory.

## 3) Gotchas, feedback, bugs

This is an early-stage mechanism, so field reports are welcome. You can send bug
reports to [email protected].

## 4) Bonus feature #1: deferred initialization

See
[README.persistent_mode.md#3) Deferred initialization](README.persistent_mode.md#3-deferred-initialization).

## 5) Bonus feature #2: persistent mode

See
[README.persistent_mode.md#4) Persistent mode](README.persistent_mode.md#4-persistent-mode).

## 6) Bonus feature #3: selective instrumentation

It can be more effective to fuzzing to only instrument parts of the code. For
details, see [README.instrument_list.md](README.instrument_list.md).

## 7) Bonus feature #4: CMPLOG

The gcc_plugin also support CMPLOG/Redqueen, just set `AFL_GCC_CMPLOG` before
instrumenting the target.
Read more about this in the llvm document.

# Injection fuzzing

Coverage guided fuzzing so far is only able to detect crashes, so usually
memory corruption issues, or - if implemented by hand in the harness -
invariants.

This is a proof-of-concept implementation to additionally hunt for injection
vulnerabilities.
It works by instrumenting calls to specific functions and parsing the
query parameter for a specific unescaped dictionary string, and if detected,
crashes the target.

This has a very low false positive rate.
But obviously this can only find injection vulnerailities that are suspectible
to this specific (but most common) issue. Hence in a rare kind of injection
vulnerability this won't find the bug - and be a false negative.
But this can be tweaked by the user - see the HOW TO MODIFY section below.

## How to use

Set one or more of the following environment variables for **compiling**
the target and - *this is important* - when **fuzzing** the target:

 - `AFL_LLVM_INJECTIONS_SQL`
 - `AFL_LLVM_INJECTIONS_LDAP`
 - `AFL_LLVM_INJECTIONS_XSS`

Alternatively you can set `AFL_LLVM_INJECTIONS_ALL` to enable all.

## How to modify

If you want to add more fuctions to check for e.g. SQL injections:
Add these to `instrumentation/injection-pass.cc` and recompile.

If you want to test for more injection inputs:
Add the dictionary tokens to `src/afl-fuzz.c` and the check for them to
`instrumentation/afl-compiler-rt.o.c`.

If you want to add new injection targets:
You will have to edit all three files.

Just search for:
```
// Marker: ADD_TO_INJECTIONS
```
in the files to see where this needs to be added.

**NOTE:** pull requests to improve this feature are highly welcome :-)

# Using AFL++ with partial instrumentation

This file describes two different mechanisms to selectively instrument only
specific parts in the target.

Both mechanisms work for LLVM and GCC_PLUGIN, but not for afl-clang/afl-gcc.

## 1) Description and purpose

When building and testing complex programs where only a part of the program is
the fuzzing target, it often helps to only instrument the necessary parts of the
program, leaving the rest uninstrumented. This helps to focus the fuzzer on the
important parts of the program, avoiding undesired noise and disturbance by
uninteresting code being exercised.

For this purpose, "partial instrumentation" support is provided by AFL++ that
allows to specify what should be instrumented and what not.

Both mechanisms for partial instrumentation can be used together.

## 2) Selective instrumentation with __AFL_COVERAGE_... directives

In this mechanism, the selective instrumentation is done in the source code.

After the includes, a special define has to be made, e.g.:

```
#include <stdio.h>
#include <stdint.h>
// ...

__AFL_COVERAGE();  // <- required for this feature to work
```

If you want to disable the coverage at startup until you specify coverage should
be started, then add `__AFL_COVERAGE_START_OFF();` at that position.

From here on out, you have the following macros available that you can use in
any function where you want:

* `__AFL_COVERAGE_ON();` - Enable coverage from this point onwards.
* `__AFL_COVERAGE_OFF();` - Disable coverage from this point onwards.
* `__AFL_COVERAGE_DISCARD();` - Reset all coverage gathered until this point.
* `__AFL_COVERAGE_SKIP();` - Mark this test case as unimportant. Whatever
  happens, afl-fuzz will ignore it.

A special function is `__afl_coverage_interesting`. To use this, you must define
`void __afl_coverage_interesting(u8 val, u32 id);`. Then you can use this
function globally, where the `val` parameter can be set by you, the `id`
parameter is for afl-fuzz and will be overwritten. Note that useful parameters
for `val` are: 1, 2, 3, 4, 8, 16, 32, 64, 128. A value of, e.g., 33 will be seen
as 32 for coverage purposes.

## 3) Selective instrumentation with AFL_LLVM_ALLOWLIST/AFL_LLVM_DENYLIST

This feature is equivalent to llvm 12 sancov feature and allows to specify on a
filename and/or function name level to instrument these or skip them.

### 3a) How to use the partial instrumentation mode

In order to build with partial instrumentation, you need to build with
afl-clang-fast/afl-clang-fast++ or afl-clang-lto/afl-clang-lto++. The only
required change is that you need to set either the environment variable
`AFL_LLVM_ALLOWLIST` or `AFL_LLVM_DENYLIST` set with a filename.

That file should contain the file names or functions that are to be instrumented
(`AFL_LLVM_ALLOWLIST`) or are specifically NOT to be instrumented
(`AFL_LLVM_DENYLIST`).

GCC_PLUGIN: you can use either `AFL_LLVM_ALLOWLIST` or `AFL_GCC_ALLOWLIST` (or
the same for `_DENYLIST`), both work.

For matching to succeed, the function/file name that is being compiled must end
in the function/file name entry contained in this instrument file list. That is
to avoid breaking the match when absolute paths are used during compilation.

**NOTE:** In builds with optimization enabled, functions might be inlined and
would not match!

For example, if your source tree looks like this:

```
project/
project/feature_a/a1.cpp
project/feature_a/a2.cpp
project/feature_b/b1.cpp
project/feature_b/b2.cpp
```

And you only want to test feature_a, then create an "instrument file list" file
containing:

```
feature_a/a1.cpp
feature_a/a2.cpp
```

However, if the "instrument file list" file contains only this, it works as
well:

```
a1.cpp
a2.cpp
```

But it might lead to files being unwantedly instrumented if the same filename
exists somewhere else in the project directories.

You can also specify function names. Note that for C++ the function names must
be mangled to match! `nm` can print these names.

AFL++ is able to identify whether an entry is a filename or a function. However,
if you want to be sure (and compliant to the sancov allow/blocklist format), you
can specify source file entries like this:

```
src: *malloc.c
```

And function entries like this:

```
fun: MallocFoo
```

Note that whitespace is ignored and comments (`# foo`) are supported.

### 3b) UNIX-style pattern matching

You can add UNIX-style pattern matching in the "instrument file list" entries.
See `man fnmatch` for the syntax. Do not set any of the `fnmatch` flags.

# laf-intel instrumentation

## Introduction

This originally is the work of an individual nicknamed laf-intel. His blog
[Circumventing Fuzzing Roadblocks with Compiler Transformations](https://lafintel.wordpress.com/)
and GitLab repo [laf-llvm-pass](https://gitlab.com/laf-intel/laf-llvm-pass/)
describe some code transformations that help AFL++ to enter conditional blocks,
where conditions consist of comparisons of large values.

## Usage

By default, these passes will not run when you compile programs using
afl-clang-fast. Hence, you can use AFL++ as usual. To enable the passes, you
must set environment variables before you compile the target project.

The following options exist:

`export AFL_LLVM_LAF_SPLIT_SWITCHES=1`

Enables the split-switches pass.

`export AFL_LLVM_LAF_TRANSFORM_COMPARES=1`

Enables the transform-compares pass (strcmp, memcmp, strncmp, strcasecmp,
strncasecmp).

`export AFL_LLVM_LAF_SPLIT_COMPARES=1`

Enables the split-compares pass. By default, it will
1. simplify operators >= (and <=) into chains of > (<) and == comparisons
2. change signed integer comparisons to a chain of sign-only comparison and
   unsigned integer comparisons
3. split all unsigned integer comparisons with bit widths of 64, 32, or 16 bits
   to chains of 8 bits comparisons.

You can change the behavior of the last step by setting `export
AFL_LLVM_LAF_SPLIT_COMPARES_BITW=<bit_width>`, where bit_width may be 64, 32, or
16. For example, a bit_width of 16 would split larger comparisons down to 16 bit
comparisons.

A new unique feature is splitting floating point comparisons into a series
of sign, exponent and mantissa comparisons followed by splitting each of them
into 8 bit comparisons when necessary. It is activated with the
`AFL_LLVM_LAF_SPLIT_FLOATS` setting.

Note that setting this automatically activates `AFL_LLVM_LAF_SPLIT_COMPARES`.

You can also set `AFL_LLVM_LAF_ALL` and have all of the above enabled. :-)

# Fast LLVM-based instrumentation for afl-fuzz

For the general instruction manual, see [docs/README.md](../docs/README.md).

For the GCC-based instrumentation, see
[README.gcc_plugin.md](README.gcc_plugin.md).

## 1) Introduction

! llvm_mode works with llvm versions 3.8 up to 17 - but 13+ is recommended !

The code in this directory allows you to instrument programs for AFL++ using
true compiler-level instrumentation, instead of the more crude assembly-level
rewriting approach taken by afl-gcc and afl-clang. This has several interesting
properties:

- The compiler can make many optimizations that are hard to pull off when
  manually inserting assembly. As a result, some slow, CPU-bound programs will
  run up to around 2x faster.

  The gains are less pronounced for fast binaries, where the speed is limited
  chiefly by the cost of creating new processes. In such cases, the gain will
  probably stay within 10%.

- The instrumentation is CPU-independent. At least in principle, you should be
  able to rely on it to fuzz programs on non-x86 architectures (after building
  afl-fuzz with AFL_NO_X86=1).

- The instrumentation can cope a bit better with multi-threaded targets.

- Because the feature relies on the internals of LLVM, it is clang-specific and
  will *not* work with GCC (see ../gcc_plugin/ for an alternative once it is
  available).

Once this implementation is shown to be sufficiently robust and portable, it
will probably replace afl-clang. For now, it can be built separately and
co-exists with the original code.

The idea and much of the initial implementation came from Laszlo Szekeres.

## 2a) How to use this - short

Set the `LLVM_CONFIG` variable to the clang version you want to use, e.g.:

```
LLVM_CONFIG=llvm-config-9 make
```

In case you have your own compiled llvm version specify the full path:

```
LLVM_CONFIG=~/llvm-project/build/bin/llvm-config make
```

If you try to use a new llvm version on an old Linux this can fail because of
old c++ libraries. In this case usually switching to gcc/g++ to compile
llvm_mode will work:

```
LLVM_CONFIG=llvm-config-7 REAL_CC=gcc REAL_CXX=g++ make
```

It is highly recommended to use the newest clang version you can put your hands
on :)

Then look at [README.persistent_mode.md](README.persistent_mode.md).

## 2b) How to use this - long

In order to leverage this mechanism, you need to have clang installed on your
system. You should also make sure that the llvm-config tool is in your path (or
pointed to via LLVM_CONFIG in the environment).

Note that if you have several LLVM versions installed, pointing LLVM_CONFIG to
the version you want to use will switch compiling to this specific version - if
you installation is set up correctly :-)

Unfortunately, some systems that do have clang come without llvm-config or the
LLVM development headers; one example of this is FreeBSD. FreeBSD users will
also run into problems with clang being built statically and not being able to
load modules (you'll see "Service unavailable" when loading afl-llvm-pass.so).

To solve all your problems, you can grab pre-built binaries for your OS from:

[https://llvm.org/releases/download.html](https://llvm.org/releases/download.html)

...and then put the bin/ directory from the tarball at the beginning of your
$PATH when compiling the feature and building packages later on. You don't need
to be root for that.

To build the instrumentation itself, type `make`. This will generate binaries
called afl-clang-fast and afl-clang-fast++ in the parent directory. Once this is
done, you can instrument third-party code in a way similar to the standard
operating mode of AFL, e.g.:

```
  CC=/path/to/afl/afl-clang-fast ./configure [...options...]
  make
```

Be sure to also include CXX set to afl-clang-fast++ for C++ code.

Note that afl-clang-fast/afl-clang-fast++ are just pointers to afl-cc. You can
also use afl-cc/afl-c++ and instead direct it to use LLVM instrumentation by
either setting `AFL_CC_COMPILER=LLVM` or pass the parameter `--afl-llvm` via
CFLAGS/CXXFLAGS/CPPFLAGS.

The tool honors roughly the same environmental variables as afl-gcc (see
[docs/env_variables.md](../docs/env_variables.md)). This includes
`AFL_USE_ASAN`, `AFL_HARDEN`, and `AFL_DONT_OPTIMIZE`. However, `AFL_INST_RATIO`
is not honored as it does not serve a good purpose with the more effective
PCGUARD analysis.

## 3) Options

Several options are present to make llvm_mode faster or help it rearrange the
code to make afl-fuzz path discovery easier.

If you need just to instrument specific parts of the code, you can create the
instrument file list which C/C++ files to actually instrument. See
[README.instrument_list.md](README.instrument_list.md)

For splitting memcmp, strncmp, etc., see
[README.laf-intel.md](README.laf-intel.md).

Then there are different ways of instrumenting the target:

1. A better instrumentation strategy uses LTO and link time instrumentation.
   Note that not all targets can compile in this mode, however, if it works it
   is the best option you can use. To go with this option, use
   afl-clang-lto/afl-clang-lto++. See [README.lto.md](README.lto.md).

2. Alternatively you can choose a completely different coverage method:

2a. N-GRAM coverage - which combines the previous visited edges with the current
    one. This explodes the map but on the other hand has proven to be effective
    for fuzzing. See
    [7) AFL++ N-Gram Branch Coverage](#7-afl-n-gram-branch-coverage).

2b. Context sensitive coverage - which combines the visited edges with an
    individual caller ID (the function that called the current one). See
    [6) AFL++ Context Sensitive Branch Coverage](#6-afl-context-sensitive-branch-coverage).

Then - additionally to one of the instrumentation options above - there is a
very effective new instrumentation option called CmpLog as an alternative to
laf-intel that allow AFL++ to apply mutations similar to Redqueen. See
[README.cmplog.md](README.cmplog.md).

Finally, if your llvm version is 8 or lower, you can activate a mode that
prevents that a counter overflow result in a 0 value. This is good for path
discovery, but the llvm implementation for x86 for this functionality is not
optimal and was only fixed in llvm 9. You can set this with AFL_LLVM_NOT_ZERO=1.

Support for thread safe counters has been added for all modes. Activate it with
`AFL_LLVM_THREADSAFE_INST=1`. The tradeoff is better precision in multi threaded
apps for a slightly higher instrumentation overhead. This also disables the
nozero counter default for performance reasons.

## 4) deferred initialization, persistent mode, shared memory fuzzing

This is the most powerful and effective fuzzing you can do. For a full
explanation, see [README.persistent_mode.md](README.persistent_mode.md).

## 5) Bonus feature: 'dict2file' pass

Just specify `AFL_LLVM_DICT2FILE=/absolute/path/file.txt` and during compilation
all constant string compare parameters will be written to this file to be used
with afl-fuzz' `-x` option.

Adding `AFL_LLVM_DICT2FILE_NO_MAIN=1` will skip parsing `main()` which often
does command line parsing which has string comparisons that are not helpful
for fuzzing.

## 6) AFL++ Context Sensitive Branch Coverage

### What is this?

This is an LLVM-based implementation of the context sensitive branch coverage.

Basically every function gets its own ID and, every time when an edge is logged,
all the IDs in the callstack are hashed and combined with the edge transition
hash to augment the classic edge coverage with the information about the calling
context.

So if both function A and function B call a function C, the coverage collected
in C will be different.

In math the coverage is collected as follows: `map[current_location_ID ^
previous_location_ID >> 1 ^ hash_callstack_IDs] += 1`

The callstack hash is produced XOR-ing the function IDs to avoid explosion with
recursive functions.

### Usage

Set the `AFL_LLVM_INSTRUMENT=CTX` or `AFL_LLVM_CTX=1` environment variable.

It is highly recommended to increase the MAP_SIZE_POW2 definition in config.h to
at least 18 and maybe up to 20 for this as otherwise too many map collisions
occur.

### Caller Branch Coverage

If the context sensitive coverage introduces too may collisions and becoming
detrimental, the user can choose to augment edge coverage with just the called
function ID, instead of the entire callstack hash.

In math the coverage is collected as follows: `map[current_location_ID ^
previous_location_ID >> 1 ^ previous_callee_ID] += 1`

Set the `AFL_LLVM_INSTRUMENT=CALLER` or `AFL_LLVM_CALLER=1` environment
variable.

## 7) AFL++ N-Gram Branch Coverage

### Source

This is an LLVM-based implementation of the n-gram branch coverage proposed in
the paper
["Be Sensitive and Collaborative: Analyzing Impact of Coverage Metrics in Greybox Fuzzing"](https://www.usenix.org/system/files/raid2019-wang-jinghan.pdf)
by Jinghan Wang, et. al.

Note that the original implementation (available
[here](https://github.com/bitsecurerlab/afl-sensitive)) is built on top of AFL's
QEMU mode. This is essentially a port that uses LLVM vectorized instructions
(available from llvm versions 4.0.1 and higher) to achieve the same results when
compiling source code.

In math the branch coverage is performed as follows: `map[current_location ^
prev_location[0] >> 1 ^ prev_location[1] >> 1 ^ ... up to n-1`] += 1`

### Usage

The size of `n` (i.e., the number of branches to remember) is an option that is
specified either in the `AFL_LLVM_INSTRUMENT=NGRAM-{value}` or the
`AFL_LLVM_NGRAM_SIZE` environment variable. Good values are 2, 4, or 8, valid
are 2-16.

It is highly recommended to increase the MAP_SIZE_POW2 definition in config.h to
at least 18 and maybe up to 20 for this as otherwise too many map collisions
occur.

## 8) NeverZero counters

In larger, complex, or reiterative programs, the byte sized counters that
collect the edge coverage can easily fill up and wrap around. This is not that
much of an issue - unless, by chance, it wraps just to a value of zero when the
program execution ends. In this case, afl-fuzz is not able to see that the edge
has been accessed and will ignore it.

NeverZero prevents this behavior. If a counter wraps, it jumps over the value 0
directly to a 1. This improves path discovery (by a very small amount) at a very
low cost (one instruction per edge).

(The alternative of saturated counters has been tested also and proved to be
inferior in terms of path discovery.)

This is implemented in afl-gcc and afl-gcc-fast, however, for llvm_mode this is
optional if multithread safe counters are selected or the llvm version is below
9 - as there are severe performance costs in these cases.

If you want to enable this for llvm versions below 9 or thread safe counters,
then set

```
export AFL_LLVM_NOT_ZERO=1
```

In case you are on llvm 9 or greater and you do not want this behavior, then you
can set:

```
AFL_LLVM_SKIP_NEVERZERO=1
```

If the target does not have extensive loops or functions that are called a lot,
then this can give a small performance boost.

Please note that the default counter implementations are not thread safe!

Support for thread safe counters in mode LLVM CLASSIC can be activated with
setting `AFL_LLVM_THREADSAFE_INST=1`.

## 8) Source code coverage through instrumentation

Measuring source code coverage is a common task in fuzzing, but it is very
difficut to do in some situations (e.g. when using snapshot fuzzing).

When using the `AFL_LLVM_INSTRUMENT=llvm-codecov` option, afl-cc will use
native trace-pc-guard instrumentation but additionally select options that
are required to utilize the instrumentation for source code coverage.

In particular, it will switch the instrumentation to be per basic block
instead of instrumenting edges, disable all guard pruning and enable the
experimental pc-table support that allows the runtime to gather 100% of
instrumented basic blocks at start, including their locations.

Note: You must compile AFL with the `CODE_COVERAGE=1` option to enable the
respective parts in the AFL compiler runtime. Support is currently only
implemented for Nyx, but can in theory also work without Nyx.

Note: You might have to adjust `MAP_SIZE_POW2` in include/config.h to ensure
that your coverage map is large enough to hold all basic blocks of your
target program without any collisions.

More documentation on how to utilize this with Nyx will follow.

# afl-clang-lto - collision free instrumentation at link time

## TL;DR:

This version requires a LLVM 12 or newer.

1. Use afl-clang-lto/afl-clang-lto++ because the resulting binaries run
   slightly faster and give better coverage.

2. You can use it together with COMPCOV, COMPLOG and the instrument file
   listing features.

3. It only works with LLVM 12 or newer.

4. AUTODICTIONARY feature (see below)

5. If any problems arise, be sure to set `AR=llvm-ar RANLIB=llvm-ranlib AS=llvm-as`.
   Some targets might need `LD=afl-clang-lto` and others `LD=afl-ld-lto`.

## Introduction and problem description

A big issue with how vanilla AFL worked was that the basic block IDs that are
set during compilation are random - and hence naturally the larger the number
of instrumented locations, the higher the number of edge collisions are in the
map. This can result in not discovering new paths and therefore degrade the
efficiency of the fuzzing process.

*This issue is underestimated in the fuzzing community* With a 2^16 = 64kb
standard map at already 256 instrumented blocks, there is on average one
collision. On average, a target has 10.000 to 50.000 instrumented blocks, hence
the real collisions are between 750-18.000!

Note that PCGUARD (our own modified implementation and the SANCOV PCGUARD
implementation from libfuzzer) also provides collision free coverage.
It is a bit slower though and can a few targets with very early constructors.

* We instrument at link time when we have all files pre-compiled.
* To instrument at link time, we compile in LTO (link time optimization) mode.
* Our compiler (afl-clang-lto/afl-clang-lto++) takes care of setting the correct
  LTO options and runs our own afl-ld linker instead of the system linker.
* The LLVM linker collects all LTO files to link and instruments them so that we
  have non-colliding edge coverage.
* We use a new (for afl) edge coverage - which is the same as in llvm
  -fsanitize=coverage edge coverage mode. :)

The result:

* 10-25% speed gain compared to llvm_mode
* guaranteed non-colliding edge coverage
* The compile time, especially for binaries to an instrumented library, can be
  much (and sometimes much much) longer.

Example build output from a libtiff build:

```
libtool: link: afl-clang-lto -g -O2 -Wall -W -o thumbnail thumbnail.o  ../libtiff/.libs/libtiff.a ../port/.libs/libport.a -llzma -ljbig -ljpeg -lz -lm
afl-clang-lto++2.63d by Marc "vanHauser" Heuse <[email protected]> in mode LTO
afl-llvm-lto++2.63d by Marc "vanHauser" Heuse <[email protected]>
AUTODICTIONARY: 11 strings found
[+] Instrumented 12071 locations with no collisions (on average 1046 collisions would be in afl-gcc/afl-clang-fast) (non-hardened mode).
```

## Getting LLVM 12+

### Installing llvm

The best way to install LLVM is to follow [https://apt.llvm.org/](https://apt.llvm.org/)

e.g. for LLVM 15:
```
wget https://apt.llvm.org/llvm.sh
chmod +x llvm.sh
sudo ./llvm.sh 15 all
```

LLVM 12 to 18 should be available in all current Linux repositories.

## How to build afl-clang-lto

That part is easy.
Just set `LLVM_CONFIG` to the llvm-config-VERSION and build AFL++, e.g. for
LLVM 15:

```
cd ~/AFLplusplus
export LLVM_CONFIG=llvm-config-15
make
sudo make install
```

## How to use afl-clang-lto

Just use afl-clang-lto like you did with afl-clang-fast or afl-gcc.

Also, the instrument file listing (AFL_LLVM_ALLOWLIST/AFL_LLVM_DENYLIST ->
[README.instrument_list.md](README.instrument_list.md)) and laf-intel/compcov
(AFL_LLVM_LAF_* -> [README.laf-intel.md](README.laf-intel.md)) work.

Example (note that you might need to add the version, e.g. `llvm-ar-15`:

```
CC=afl-clang-lto CXX=afl-clang-lto++ RANLIB=llvm-ranlib AR=llvm-ar AS=llvm-as ./configure
make
```

NOTE: some targets also need to set the linker, try both `afl-clang-lto` and
`afl-ld-lto` for `LD=` before `configure`.

## Instrumenting shared libraries

Note: this is highly discouraged! Try to compile to static libraries with
afl-clang-lto instead of shared libraries!

To make instrumented shared libraries work with afl-clang-lto, you have to do
quite some extra steps.

Every shared library you want to instrument has to be individually compiled. The
environment variable `AFL_LLVM_LTO_DONTWRITEID=1` has to be set during
compilation. Additionally, the environment variable `AFL_LLVM_LTO_STARTID` has
to be set to the added edge count values of all previous compiled instrumented
shared libraries for that target. E.g., for the first shared library this would
be `AFL_LLVM_LTO_STARTID=0` and afl-clang-lto will then report how many edges
have been instrumented (let's say it reported 1000 instrumented edges). The
second shared library then has to be set to that value
(`AFL_LLVM_LTO_STARTID=1000` in our example), for the third to all previous
counts added, etc.

The final program compilation step then may *not* have
`AFL_LLVM_LTO_DONTWRITEID` set, and `AFL_LLVM_LTO_STARTID` must be set to all
edge counts added of all shared libraries it will be linked to.

This is quite some hands-on work, so better stay away from instrumenting shared
libraries. :-)

## AUTODICTIONARY feature

While compiling, a dictionary based on string comparisons is automatically
generated and put into the target binary. This dictionary is transferred to
afl-fuzz on start. This improves coverage statistically by 5-10%. :)

Note that if for any reason you do not want to use the autodictionary feature,
then just set the environment variable `AFL_NO_AUTODICT` when starting afl-fuzz.

## Fixed memory map

To speed up fuzzing a little bit more, it is possible to set a fixed shared
memory map. Recommended is the value 0x10000.

In most cases, this will work without any problems. However, if a target uses
early constructors, ifuncs, or a deferred forkserver, this can crash the target.

Also, on unusual operating systems/processors/kernels or weird libraries the
recommended 0x10000 address might not work, so then change the fixed address.

To enable this feature, set `AFL_LLVM_MAP_ADDR` with the address.

## Document edge IDs

Setting `export AFL_LLVM_DOCUMENT_IDS=file` will document in a file which edge
ID was given to which function. This helps to identify functions with variable
bytes or which functions were touched by an input.

## Solving difficult targets

Some targets are difficult because the configure script does unusual stuff that
is unexpected for afl. See the next section `Potential issues` for how to solve
these.

### Example: ffmpeg

An example of a hard to solve target is ffmpeg. Here is how to successfully
instrument it:

1. Get and extract the current ffmpeg and change to its directory.

2. Running configure with --cc=clang fails and various other items will fail
   when compiling, so we have to trick configure:

    ```
    ./configure --enable-lto --disable-shared --disable-inline-asm
    ```

3. Now the configuration is done - and we edit the settings in
   `./ffbuild/config.mak` (-: the original line, +: what to change it into):

    ```
    -CC=gcc
    +CC=afl-clang-lto
    -CXX=g++
    +CXX=afl-clang-lto++
    -AS=gcc
    +AS=llvm-as
    -LD=gcc
    +LD=afl-clang-lto++
    -DEPCC=gcc
    +DEPCC=afl-clang-lto
    -DEPAS=gcc
    +DEPAS=afl-clang-lto++
    -AR=ar
    +AR=llvm-ar
    -AR_CMD=ar
    +AR_CMD=llvm-ar
    -NM_CMD=nm -g
    +NM_CMD=llvm-nm -g
    -RANLIB=ranlib -D
    +RANLIB=llvm-ranlib -D
    ```

4. Then type make, wait for a long time, and you are done. :)

### Example: WebKit jsc

Building jsc is difficult as the build script has bugs.

1. Checkout Webkit:

    ```
    svn checkout https://svn.webkit.org/repository/webkit/trunk WebKit
    cd WebKit
    ```

2. Fix the build environment:

    ```
    mkdir -p WebKitBuild/Release
    cd WebKitBuild/Release
    ln -s ../../../../../usr/bin/llvm-ar-12 llvm-ar-12
    ln -s ../../../../../usr/bin/llvm-ranlib-12 llvm-ranlib-12
    cd ../..
    ```

3. Build. :)

    ```
    Tools/Scripts/build-jsc --jsc-only --cli --cmakeargs="-DCMAKE_AR='llvm-ar-12' -DCMAKE_RANLIB='llvm-ranlib-12' -DCMAKE_VERBOSE_MAKEFILE:BOOL=ON -DCMAKE_CC_FLAGS='-O3 -lrt' -DCMAKE_CXX_FLAGS='-O3 -lrt' -DIMPORTED_LOCATION='/lib/x86_64-linux-gnu/' -DCMAKE_CC=afl-clang-lto -DCMAKE_CXX=afl-clang-lto++ -DENABLE_STATIC_JSC=ON"
    ```

## Potential issues

### Compiling libraries fails

If you see this message:

```
/bin/ld: libfoo.a: error adding symbols: archive has no index; run ranlib to add one
```

This is because usually gnu gcc ranlib is being called which cannot deal with
clang LTO files. The solution is simple: when you `./configure`, you also have
to set `RANLIB=llvm-ranlib` and `AR=llvm-ar`.

Solution:

```
AR=llvm-ar RANLIB=llvm-ranlib CC=afl-clang-lto CXX=afl-clang-lto++ ./configure --disable-shared
```

And on some targets you have to set `AR=/RANLIB=` even for `make` as the
configure script does not save it. Other targets ignore environment variables
and need the parameters set via `./configure --cc=... --cxx= --ranlib= ...` etc.
(I am looking at you ffmpeg!)

If you see this message:

```
assembler command failed ...
```

Then try setting `llvm-as` for configure:

```
AS=llvm-as  ...
```

### Compiling programs still fail

afl-clang-lto is still work in progress.

Known issues:
* Anything that LLVM 12+ cannot compile, afl-clang-lto cannot compile either -
  obviously.
* Anything that does not compile with LTO, afl-clang-lto cannot compile either -
  obviously.

Hence, if building a target with afl-clang-lto fails, try to build it with
LLVM 12 and LTO enabled (`CC=clang-12`, `CXX=clang++-12`, `CFLAGS=-flto=full`,
and `CXXFLAGS=-flto=full`).

If this succeeds, then there is an issue with afl-clang-lto. Please report at
[https://github.com/AFLplusplus/AFLplusplus/issues/226](https://github.com/AFLplusplus/AFLplusplus/issues/226).

Even some targets where clang-12 fails can be built if the fail is just in
`./configure`, see `Solving difficult targets` above.

## History

This was originally envisioned by hexcoder- in Summer 2019. However, we saw no
way to create a pass that is run at link time - although there is a option for
this in the PassManager: EP_FullLinkTimeOptimizationLast. ("Fun" info - nobody
knows what this is doing. And the developer who implemented this didn't respond
to emails.)

In December then came the idea to implement this as a pass that is run via the
LLVM "opt" program, which is performed via an own linker that afterwards calls
the real linker. This was first implemented in January and work ... kinda. The
LTO time instrumentation worked, however, "how" the basic blocks were
instrumented was a problem, as reducing duplicates turned out to be very, very
difficult with a program that has so many paths and therefore so many
dependencies. A lot of strategies were implemented - and failed. And then sat
solvers were tried, but with over 10.000 variables that turned out to be a
dead-end too.

The final idea to solve this came from domenukk who proposed to insert a block
into an edge and then just use incremental counters ... and this worked! After
some trials and errors to implement this vanhauser-thc found out that there is
actually an LLVM function for this: SplitEdge() :-)

Still more problems came up though as this only works without bugs from LLVM 9
onwards, and with high optimization the link optimization ruins the instrumented
control flow graph.

This is all now fixed with LLVM 12+. The llvm's own linker is now able to load
passes and this bypasses all problems we had.

Happy end :)

# llvm_mode persistent mode

## 1) Introduction

In persistent mode, AFL++ fuzzes a target multiple times in a single forked
process, instead of forking a new process for each fuzz execution. This is the
most effective way to fuzz, as the speed can easily be x10 or x20 times faster
without any disadvantages. *All professional fuzzing uses this mode.*

Persistent mode requires that the target can be called in one or more functions,
and that it's state can be completely reset so that multiple calls can be
performed without resource leaks, and that earlier runs will have no impact on
future runs. An indicator for this is the `stability` value in the `afl-fuzz`
UI. If this decreases to lower values in persistent mode compared to
non-persistent mode, then the fuzz target keeps state.

Examples can be found in [utils/persistent_mode](../utils/persistent_mode).

## 2) TL;DR:

Example `fuzz_target.c`:

```c
#include "what_you_need_for_your_target.h"

__AFL_FUZZ_INIT();

main() {

  // anything else here, e.g. command line arguments, initialization, etc.

#ifdef __AFL_HAVE_MANUAL_CONTROL
  __AFL_INIT();
#endif

  unsigned char *buf = __AFL_FUZZ_TESTCASE_BUF;  // must be after __AFL_INIT
                                                 // and before __AFL_LOOP!

  while (__AFL_LOOP(10000)) {

    int len = __AFL_FUZZ_TESTCASE_LEN;  // don't use the macro directly in a
                                        // call!

    if (len < 8) continue;  // check for a required/useful minimum input length

    /* Setup function call, e.g. struct target *tmp = libtarget_init() */
    /* Call function to be fuzzed, e.g.: */
    target_function(buf, len);
    /* Reset state. e.g. libtarget_free(tmp) */

  }

  return 0;

}
```

And then compile:

```
afl-clang-fast -o fuzz_target fuzz_target.c -lwhat_you_need_for_your_target
```

And that is it! The speed increase is usually x10 to x20.

If you want to be able to compile the target without afl-clang-fast/lto, then
add this just after the includes:

```c
#ifndef __AFL_FUZZ_TESTCASE_LEN
  ssize_t fuzz_len;
  #define __AFL_FUZZ_TESTCASE_LEN fuzz_len
  unsigned char fuzz_buf[1024000];
  #define __AFL_FUZZ_TESTCASE_BUF fuzz_buf
  #define __AFL_FUZZ_INIT() void sync(void);
  #define __AFL_LOOP(x) ((fuzz_len = read(0, fuzz_buf, sizeof(fuzz_buf))) > 0 ? 1 : 0)
  #define __AFL_INIT() sync()
#endif
```

## 3) Deferred initialization

AFL++ tries to optimize performance by executing the targeted binary just once,
stopping it just before `main()`, and then cloning this "main" process to get a
steady supply of targets to fuzz.

Although this approach eliminates much of the OS-, linker- and libc-level costs
of executing the program, it does not always help with binaries that perform
other time-consuming initialization steps - say, parsing a large config file
before getting to the fuzzed data.

In such cases, it's beneficial to initialize the forkserver a bit later, once
most of the initialization work is already done, but before the binary attempts
to read the fuzzed input and parse it; in some cases, this can offer a 10x+
performance gain. You can implement delayed initialization in LLVM mode in a
fairly simple way.

First, find a suitable location in the code where the delayed cloning can take
place. This needs to be done with *extreme* care to avoid breaking the binary.
In particular, the program will probably malfunction if you select a location
after:

- The creation of any vital threads or child processes - since the forkserver
  can't clone them easily.

- The initialization of timers via `setitimer()` or equivalent calls.

- The creation of temporary files, network sockets, offset-sensitive file
  descriptors, and similar shared-state resources - but only provided that their
  state meaningfully influences the behavior of the program later on.

- Any access to the fuzzed input, including reading the metadata about its size.

With the location selected, add this code in the appropriate spot:

```c
#ifdef __AFL_HAVE_MANUAL_CONTROL
  __AFL_INIT();
#endif
```

You don't need the #ifdef guards, but including them ensures that the program
will keep working normally when compiled with a tool other than afl-clang-fast/
afl-clang-lto/afl-gcc-fast.

Finally, recompile the program with afl-clang-fast/afl-clang-lto/afl-gcc-fast
(afl-gcc or afl-clang will *not* generate a deferred-initialization binary) -
and you should be all set!

## 4) Persistent mode

Some libraries provide APIs that are stateless, or whose state can be reset in
between processing different input files. When such a reset is performed, a
single long-lived process can be reused to try out multiple test cases,
eliminating the need for repeated `fork()` calls and the associated OS overhead.

The basic structure of the program that does this would be:

```c
  while (__AFL_LOOP(1000)) {

    /* Read input data. */
    /* Call library code to be fuzzed. */
    /* Reset state. */

  }

  /* Exit normally. */
```

The numerical value specified within the loop controls the maximum number of
iterations before AFL++ will restart the process from scratch. This minimizes
the impact of memory leaks and similar glitches; 1000 is a good starting point,
and going much higher increases the likelihood of hiccups without giving you any
real performance benefits.

A more detailed template is shown in
[utils/persistent_mode](../utils/persistent_mode). Similarly to the deferred
initialization, the feature works only with afl-clang-fast; `#ifdef` guards can
be used to suppress it when using other compilers.

Note that as with the deferred initialization, the feature is easy to misuse; if
you do not fully reset the critical state, you may end up with false positives
or waste a whole lot of CPU power doing nothing useful at all. Be particularly
wary of memory leaks and of the state of file descriptors.

When running in this mode, the execution paths will inherently vary a bit
depending on whether the input loop is being entered for the first time or
executed again.

## 5) Shared memory fuzzing

You can speed up the fuzzing process even more by receiving the fuzzing data via
shared memory instead of stdin or files. This is a further speed multiplier of
about 2x.

Setting this up is very easy:

After the includes set the following macro:

```c
__AFL_FUZZ_INIT();
```

Directly at the start of main - or if you are using the deferred forkserver with
`__AFL_INIT()`, then *after* `__AFL_INIT()`:

```c
  unsigned char *buf = __AFL_FUZZ_TESTCASE_BUF;
```

Then as first line after the `__AFL_LOOP` while loop:

```c
  int len = __AFL_FUZZ_TESTCASE_LEN;
```

And that is all!