docs/LibFuzzer.rst

   1 ========================================================
   2 LibFuzzer -- a library for coverage-guided fuzz testing.
   3 ========================================================
   4 .. contents::
   5    :local:
   6    :depth: 4
   7
   8 Introduction
   9 ============
  10
  11 This library is intended primarily for in-process coverage-guided fuzz testing
  12 (fuzzing) of other libraries. The typical workflow looks like this:
  13
  14 * Build the Fuzzer library as a static archive (or just a set of .o files).
  15   Note that the Fuzzer contains the main() function.
  16   Preferably do *not* use sanitizers while building the Fuzzer.
  17 * Build the library you are going to test with
  18   `-fsanitize-coverage={bb,edge}[,indirect-calls]`
  19   and one of the sanitizers. We recommend to build the library in several
  20   different modes (e.g. asan, msan, lsan, ubsan, etc) and even using different
  21   optimizations options (e.g. -O0, -O1, -O2) to diversify testing.
  22 * Build a test driver using the same options as the library.
  23   The test driver is a C/C++ file containing interesting calls to the library
  24   inside a single function  ``extern "C" void LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size);``
  25 * Link the Fuzzer, the library and the driver together into an executable
  26   using the same sanitizer options as for the library.
  27 * Collect the initial corpus of inputs for the
  28   fuzzer (a directory with test inputs, one file per input).
  29   The better your inputs are the faster you will find something interesting.
  30   Also try to keep your inputs small, otherwise the Fuzzer will run too slow.
  31 * Run the fuzzer with the test corpus. As new interesting test cases are
  32   discovered they will be added to the corpus. If a bug is discovered by
  33   the sanitizer (asan, etc) it will be reported as usual and the reproducer
  34   will be written to disk.
  35   Each Fuzzer process is single-threaded (unless the library starts its own
  36   threads). You can run the Fuzzer on the same corpus in multiple processes
  37   in parallel. For run-time options run the Fuzzer binary with '-help=1'.
  38
  39
  40 The Fuzzer is similar in concept to AFL_,
  41 but uses in-process Fuzzing, which is more fragile, more restrictive, but
  42 potentially much faster as it has no overhead for process start-up.
  43 It uses LLVM's SanitizerCoverage_ instrumentation to get in-process
  44 coverage-feedback
  45
  46 The code resides in the LLVM repository, requires the fresh Clang compiler to build
  47 and is used to fuzz various parts of LLVM,
  48 but the Fuzzer itself does not (and should not) depend on any
  49 part of LLVM and can be used for other projects w/o requiring the rest of LLVM.
  50
  51 Usage examples
  52 ==============
  53
  54 Toy example
  55 -----------
  56
  57 A simple function that does something interesting if it receives the input "HI!"::
  58
  59   cat << EOF >> test_fuzzer.cc
  60   extern "C" void LLVMFuzzerTestOneInput(const unsigned char *data, unsigned long size) {
  61     if (size > 0 && data[0] == 'H')
  62       if (size > 1 && data[1] == 'I')
  63          if (size > 2 && data[2] == '!')
  64          __builtin_trap();
  65   }
  66   EOF
  67   # Get lib/Fuzzer. Assuming that you already have fresh clang in PATH.
  68   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
  69   # Build lib/Fuzzer files.
  70   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
  71   # Build test_fuzzer.cc with asan and link against lib/Fuzzer.
  72   clang++ -fsanitize=address -fsanitize-coverage=edge test_fuzzer.cc Fuzzer*.o
  73   # Run the fuzzer with no corpus.
  74   ./a.out
  75
  76 You should get ``Illegal instruction (core dumped)`` pretty quickly.
  77
  78 PCRE2
  79 -----
  80
  81 Here we show how to use lib/Fuzzer on something real, yet simple: pcre2_::
  82
  83   COV_FLAGS=" -fsanitize-coverage=edge,indirect-calls,8bit-counters"
  84   # Get PCRE2
  85   svn co svn://vcs.exim.org/pcre2/code/trunk pcre
  86   # Get lib/Fuzzer. Assuming that you already have fresh clang in PATH.
  87   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
  88   # Build PCRE2 with AddressSanitizer and coverage.
  89   (cd pcre; ./autogen.sh; CC="clang -fsanitize=address $COV_FLAGS" ./configure --prefix=`pwd`/../inst && make -j && make install)
  90   # Build lib/Fuzzer files.
  91   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
  92   # Build the the actual function that does something interesting with PCRE2.
  93   cat << EOF > pcre_fuzzer.cc
  94   #include <string.h>
  95   #include "pcre2posix.h"
  96   extern "C" void LLVMFuzzerTestOneInput(const unsigned char *data, size_t size) {
  97     if (size < 1) return;
  98     char *str = new char[size+1];
  99     memcpy(str, data, size);
 100     str[size] = 0;
 101     regex_t preg;
 102     if (0 == regcomp(&preg, str, 0)) {
 103       regexec(&preg, str, 0, 0, 0);
 104       regfree(&preg);
 105     }
 106     delete [] str;
 107   }
 108   EOF
 109   clang++ -g -fsanitize=address $COV_FLAGS -c -std=c++11  -I inst/include/ pcre_fuzzer.cc
 110   # Link.
 111   clang++ -g -fsanitize=address -Wl,--whole-archive inst/lib/*.a -Wl,-no-whole-archive Fuzzer*.o pcre_fuzzer.o -o pcre_fuzzer
 112
 113 This will give you a binary of the fuzzer, called ``pcre_fuzzer``.
 114 Now, create a directory that will hold the test corpus::
 115
 116   mkdir -p CORPUS
 117
 118 For simple input languages like regular expressions this is all you need.
 119 For more complicated inputs populate the directory with some input samples.
 120 Now run the fuzzer with the corpus dir as the only parameter::
 121
 122   ./pcre_fuzzer ./CORPUS
 123
 124 You will see output like this::
 125
 126   Seed: 1876794929
 127   #0      READ   cov 0 bits 0 units 1 exec/s 0
 128   #1      pulse  cov 3 bits 0 units 1 exec/s 0
 129   #1      INITED cov 3 bits 0 units 1 exec/s 0
 130   #2      pulse  cov 208 bits 0 units 1 exec/s 0
 131   #2      NEW    cov 208 bits 0 units 2 exec/s 0 L: 64
 132   #3      NEW    cov 217 bits 0 units 3 exec/s 0 L: 63
 133   #4      pulse  cov 217 bits 0 units 3 exec/s 0
 134
 135 * The ``Seed:`` line shows you the current random seed (you can change it with ``-seed=N`` flag).
 136 * The ``READ``  line shows you how many input files were read (since you passed an empty dir there were inputs, but one dummy input was synthesised).
 137 * The ``INITED`` line shows you that how many inputs will be fuzzed.
 138 * The ``NEW`` lines appear with the fuzzer finds a new interesting input, which is saved to the CORPUS dir. If multiple corpus dirs are given, the first one is used.
 139 * The ``pulse`` lines appear periodically to show the current status.
 140
 141 Now, interrupt the fuzzer and run it again the same way. You will see::
 142
 143   Seed: 1879995378
 144   #0      READ   cov 0 bits 0 units 564 exec/s 0
 145   #1      pulse  cov 502 bits 0 units 564 exec/s 0
 146   ...
 147   #512    pulse  cov 2933 bits 0 units 564 exec/s 512
 148   #564    INITED cov 2991 bits 0 units 344 exec/s 564
 149   #1024   pulse  cov 2991 bits 0 units 344 exec/s 1024
 150   #1455   NEW    cov 2995 bits 0 units 345 exec/s 1455 L: 49
 151
 152 This time you were running the fuzzer with a non-empty input corpus (564 items).
 153 As the first step, the fuzzer minimized the set to produce 344 interesting items (the ``INITED`` line)
 154
 155 It is quite convenient to store test corpuses in git.
 156 As an example, here is a git repository with test inputs for the above PCRE2 fuzzer::
 157
 158   git clone https://github.com/kcc/fuzzing-with-sanitizers.git
 159   ./pcre_fuzzer ./fuzzing-with-sanitizers/pcre2/C1/
 160
 161 You may run ``N`` independent fuzzer jobs in parallel on ``M`` CPUs::
 162
 163   N=100; M=4; ./pcre_fuzzer ./CORPUS -jobs=$N -workers=$M
 164
 165 By default (``-reload=1``) the fuzzer processes will periodically scan the CORPUS directory
 166 and reload any new tests. This way the test inputs found by one process will be picked up
 167 by all others.
 168
 169 If ``-workers=$M`` is not supplied, ``min($N,NumberOfCpuCore/2)`` will be used.
 170
 171 Heartbleed
 172 ----------
 173 Remember Heartbleed_?
 174 As it was recently `shown <https://blog.hboeck.de/archives/868-How-Heartbleed-couldve-been-found.html>`_,
 175 fuzzing with AddressSanitizer can find Heartbleed. Indeed, here are the step-by-step instructions
 176 to find Heartbleed with LibFuzzer::
 177
 178   wget https://www.openssl.org/source/openssl-1.0.1f.tar.gz
 179   tar xf openssl-1.0.1f.tar.gz
 180   COV_FLAGS="-fsanitize-coverage=edge,indirect-calls" # -fsanitize-coverage=8bit-counters
 181   (cd openssl-1.0.1f/ && ./config &&
 182     make -j 32 CC="clang -g -fsanitize=address $COV_FLAGS")
 183   # Get and build LibFuzzer
 184   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
 185   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
 186   # Get examples of key/pem files.
 187   git clone   https://github.com/hannob/selftls
 188   cp selftls/server* . -v
 189   cat << EOF > handshake-fuzz.cc
 190   #include <openssl/ssl.h>
 191   #include <openssl/err.h>
 192   #include <assert.h>
 193   SSL_CTX *sctx;
 194   int Init() {
 195     SSL_library_init();
 196     SSL_load_error_strings();
 197     ERR_load_BIO_strings();
 198     OpenSSL_add_all_algorithms();
 199     assert (sctx = SSL_CTX_new(TLSv1_method()));
 200     assert (SSL_CTX_use_certificate_file(sctx, "server.pem", SSL_FILETYPE_PEM));
 201     assert (SSL_CTX_use_PrivateKey_file(sctx, "server.key", SSL_FILETYPE_PEM));
 202     return 0;
 203   }
 204   extern "C" void LLVMFuzzerTestOneInput(unsigned char *Data, size_t Size) {
 205     static int unused = Init();
 206     SSL *server = SSL_new(sctx);
 207     BIO *sinbio = BIO_new(BIO_s_mem());
 208     BIO *soutbio = BIO_new(BIO_s_mem());
 209     SSL_set_bio(server, sinbio, soutbio);
 210     SSL_set_accept_state(server);
 211     BIO_write(sinbio, Data, Size);
 212     SSL_do_handshake(server);
 213     SSL_free(server);
 214   }
 215   EOF
 216   # Build the fuzzer.
 217   clang++ -g handshake-fuzz.cc  -fsanitize=address \
 218     openssl-1.0.1f/libssl.a openssl-1.0.1f/libcrypto.a Fuzzer*.o
 219   # Run 20 independent fuzzer jobs.
 220   ./a.out  -jobs=20 -workers=20
 221
 222 Voila::
 223
 224   #1048576        pulse  cov 3424 bits 0 units 9 exec/s 24385
 225   =================================================================
 226   ==17488==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x629000004748 at pc 0x00000048c979 bp 0x7fffe3e864f0 sp 0x7fffe3e85ca8
 227   READ of size 60731 at 0x629000004748 thread T0
 228       #0 0x48c978 in __asan_memcpy
 229       #1 0x4db504 in tls1_process_heartbeat openssl-1.0.1f/ssl/t1_lib.c:2586:3
 230       #2 0x580be3 in ssl3_read_bytes openssl-1.0.1f/ssl/s3_pkt.c:1092:4
 231
 232 Advanced features
 233 =================
 234
 235 Tokens
 236 ------
 237
 238 By default, the fuzzer is not aware of complexities of the input language
 239 and when fuzzing e.g. a C++ parser it will mostly stress the lexer.
 240 It is very hard for the fuzzer to come up with something like ``reinterpret_cast<int>``
 241 from a test corpus that doesn't have it.
 242 See a detailed discussion of this topic at
 243 http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html.
 244
 245 lib/Fuzzer implements a simple technique that allows to fuzz input languages with
 246 long tokens. All you need is to prepare a text file containing up to 253 tokens, one token per line,
 247 and pass it to the fuzzer as ``-tokens=TOKENS_FILE.txt``.
 248 Three implicit tokens are added: ``" "``, ``"\t"``, and ``"\n"``.
 249 The fuzzer itself will still be mutating a string of bytes
 250 but before passing this input to the target library it will replace every byte ``b`` with the ``b``-th token.
 251 If there are less than ``b`` tokens, a space will be added instead.
 252
 253 AFL compatibility
 254 -----------------
 255 LibFuzzer can be used in parallel with AFL_ on the same test corpus.
 256 Both fuzzers expect the test corpus to reside in a directory, one file per input.
 257 You can run both fuzzers on the same corpus in parallel::
 258
 259   ./afl-fuzz -i testcase_dir -o findings_dir /path/to/program -r @@
 260   ./llvm-fuzz testcase_dir findings_dir  # Will write new tests to testcase_dir
 261
 262 Periodically restart both fuzzers so that they can use each other's findings.
 263
 264 How good is my fuzzer?
 265 ----------------------
 266
 267 Once you implement your target function ``LLVMFuzzerTestOneInput`` and fuzz it to death,
 268 you will want to know whether the function or the corpus can be improved further.
 269 One easy to use metric is, of course, code coverage.
 270 You can get the coverage for your corpus like this::
 271
 272   ASAN_OPTIONS=coverage_pcs=1 ./fuzzer CORPUS_DIR -runs=0
 273
 274 This will run all the tests in the CORPUS_DIR but will not generate any new tests
 275 and dump covered PCs to disk before exiting.
 276 Then you can subtract the set of covered PCs from the set of all instrumented PCs in the binary,
 277 see SanitizerCoverage_ for details.
 278
 279 Fuzzing components of LLVM
 280 ==========================
 281
 282 clang-format-fuzzer
 283 -------------------
 284 The inputs are random pieces of C++-like text.
 285
 286 Build (make sure to use fresh clang as the host compiler)::
 287
 288     cmake -GNinja  -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ -DLLVM_USE_SANITIZER=Address -DLLVM_USE_SANITIZE_COVERAGE=YES -DCMAKE_BUILD_TYPE=Release /path/to/llvm
 289     ninja clang-format-fuzzer
 290     mkdir CORPUS_DIR
 291     ./bin/clang-format-fuzzer CORPUS_DIR
 292
 293 Optionally build other kinds of binaries (asan+Debug, msan, ubsan, etc).
 294
 295 TODO: commit the pre-fuzzed corpus to svn (?).
 296
 297 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=23052
 298
 299 clang-fuzzer
 300 ------------
 301
 302 The default behavior is very similar to ``clang-format-fuzzer``.
 303 Clang can also be fuzzed with Tokens_ using ``-tokens=$LLVM/lib/Fuzzer/cxx_fuzzer_tokens.txt`` option.
 304
 305 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=23057
 306
 307 Buildbot
 308 --------
 309
 310 We have a buildbot that runs the above fuzzers for LLVM components
 311 24/7/365 at http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer .
 312
 313 Pre-fuzzed test inputs in git
 314 -----------------------------
 315
 316 The buildbot occumulates large test corpuses over time.
 317 The corpuses are stored in git on github and can be used like this::
 318
 319   git clone https://github.com/kcc/fuzzing-with-sanitizers.git
 320   bin/clang-format-fuzzer fuzzing-with-sanitizers/llvm/clang-format/C1
 321   bin/clang-fuzzer        fuzzing-with-sanitizers/llvm/clang/C1/
 322   bin/clang-fuzzer        fuzzing-with-sanitizers/llvm/clang/TOK1  -tokens=$LLVM/llvm/lib/Fuzzer/cxx_fuzzer_tokens.txt
 323
 324
 325 FAQ
 326 =========================
 327
 328 Q. Why Fuzzer does not use any of the LLVM support?
 329 ---------------------------------------------------
 330
 331 There are two reasons.
 332
 333 First, we want this library to be used outside of the LLVM w/o users having to
 334 build the rest of LLVM. This may sound unconvincing for many LLVM folks,
 335 but in practice the need for building the whole LLVM frightens many potential
 336 users -- and we want more users to use this code.
 337
 338 Second, there is a subtle technical reason not to rely on the rest of LLVM, or
 339 any other large body of code (maybe not even STL). When coverage instrumentation
 340 is enabled, it will also instrument the LLVM support code which will blow up the
 341 coverage set of the process (since the fuzzer is in-process). In other words, by
 342 using more external dependencies we will slow down the fuzzer while the main
 343 reason for it to exist is extreme speed.
 344
 345 Q. What about Windows then? The Fuzzer contains code that does not build on Windows.
 346 ------------------------------------------------------------------------------------
 347
 348 The sanitizer coverage support does not work on Windows either as of 01/2015.
 349 Once it's there, we'll need to re-implement OS-specific parts (I/O, signals).
 350
 351 Q. When this Fuzzer is not a good solution for a problem?
 352 ---------------------------------------------------------
 353
 354 * If the test inputs are validated by the target library and the validator
 355   asserts/crashes on invalid inputs, the in-process fuzzer is not applicable
 356   (we could use fork() w/o exec, but it comes with extra overhead).
 357 * Bugs in the target library may accumulate w/o being detected. E.g. a memory
 358   corruption that goes undetected at first and then leads to a crash while
 359   testing another input. This is why it is highly recommended to run this
 360   in-process fuzzer with all sanitizers to detect most bugs on the spot.
 361 * It is harder to protect the in-process fuzzer from excessive memory
 362   consumption and infinite loops in the target library (still possible).
 363 * The target library should not have significant global state that is not
 364   reset between the runs.
 365 * Many interesting target libs are not designed in a way that supports
 366   the in-process fuzzer interface (e.g. require a file path instead of a
 367   byte array).
 368 * If a single test run takes a considerable fraction of a second (or
 369   more) the speed benefit from the in-process fuzzer is negligible.
 370 * If the target library runs persistent threads (that outlive
 371   execution of one test) the fuzzing results will be unreliable.
 372
 373 Q. So, what exactly this Fuzzer is good for?
 374 --------------------------------------------
 375
 376 This Fuzzer might be a good choice for testing libraries that have relatively
 377 small inputs, each input takes < 1ms to run, and the library code is not expected
 378 to crash on invalid inputs.
 379 Examples: regular expression matchers, text or binary format parsers.
 380
 381 .. _pcre2: http://www.pcre.org/
 382
 383 .. _AFL: http://lcamtuf.coredump.cx/afl/
 384
 385 .. _SanitizerCoverage: http://clang.llvm.org/docs/SanitizerCoverage.html
 386
 387 .. _Heartbleed: http://en.wikipedia.org/wiki/Heartbleed