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,8bit-counters]`
  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   By default, the Fuzzer limits the size of every input to 64 bytes
  32   (use ``-max_len=N`` to override).
  33 * Run the fuzzer with the test corpus. As new interesting test cases are
  34   discovered they will be added to the corpus. If a bug is discovered by
  35   the sanitizer (asan, etc) it will be reported as usual and the reproducer
  36   will be written to disk.
  37   Each Fuzzer process is single-threaded (unless the library starts its own
  38   threads). You can run the Fuzzer on the same corpus in multiple processes
  39   in parallel.
  40
  41
  42 The Fuzzer is similar in concept to AFL_,
  43 but uses in-process Fuzzing, which is more fragile, more restrictive, but
  44 potentially much faster as it has no overhead for process start-up.
  45 It uses LLVM's SanitizerCoverage_ instrumentation to get in-process
  46 coverage-feedback
  47
  48 The code resides in the LLVM repository, requires the fresh Clang compiler to build
  49 and is used to fuzz various parts of LLVM,
  50 but the Fuzzer itself does not (and should not) depend on any
  51 part of LLVM and can be used for other projects w/o requiring the rest of LLVM.
  52
  53 Flags
  54 =====
  55 The most important flags are::
  56
  57   seed                                  0       Random seed. If 0, seed is generated.
  58   runs                                  -1      Number of individual test runs (-1 for infinite runs).
  59   max_len                               64      Maximum length of the test input.
  60   cross_over                            1       If 1, cross over inputs.
  61   mutate_depth                          5       Apply this number of consecutive mutations to each input.
  62   timeout                               1200    Timeout in seconds (if positive). If one unit runs more than this number of seconds the process will abort.
  63   help                                  0       Print help.
  64   save_minimized_corpus                 0       If 1, the minimized corpus is saved into the first input directory
  65   jobs                                  0       Number of jobs to run. If jobs >= 1 we spawn this number of jobs in separate worker processes with stdout/stderr redirected to fuzz-JOB.log.
  66   workers                               0       Number of simultaneous worker processes to run the jobs. If zero, "min(jobs,NumberOfCpuCores()/2)" is used.
  67   tokens                                0       Use the file with tokens (one token per line) to fuzz a token based input language.
  68   apply_tokens                          0       Read the given input file, substitute bytes  with tokens and write the result to stdout.
  69   sync_command                          0       Execute an external command "<sync_command> <test_corpus>" to synchronize the test corpus.
  70   sync_timeout                          600     Minimum timeout between syncs.
  71   use_traces                            0       Experimental: use instruction traces
  72   only_ascii                            0       If 1, generate only ASCII (isprint+isspace) inputs.
  73
  74
  75 For the full list of flags run the fuzzer binary with ``-help=1``.
  76
  77 Usage examples
  78 ==============
  79
  80 Toy example
  81 -----------
  82
  83 A simple function that does something interesting if it receives the input "HI!"::
  84
  85   cat << EOF >> test_fuzzer.cc
  86   extern "C" void LLVMFuzzerTestOneInput(const unsigned char *data, unsigned long size) {
  87     if (size > 0 && data[0] == 'H')
  88       if (size > 1 && data[1] == 'I')
  89          if (size > 2 && data[2] == '!')
  90          __builtin_trap();
  91   }
  92   EOF
  93   # Get lib/Fuzzer. Assuming that you already have fresh clang in PATH.
  94   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
  95   # Build lib/Fuzzer files.
  96   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
  97   # Build test_fuzzer.cc with asan and link against lib/Fuzzer.
  98   clang++ -fsanitize=address -fsanitize-coverage=edge test_fuzzer.cc Fuzzer*.o
  99   # Run the fuzzer with no corpus.
 100   ./a.out
 101
 102 You should get ``Illegal instruction (core dumped)`` pretty quickly.
 103
 104 PCRE2
 105 -----
 106
 107 Here we show how to use lib/Fuzzer on something real, yet simple: pcre2_::
 108
 109   COV_FLAGS=" -fsanitize-coverage=edge,indirect-calls,8bit-counters"
 110   # Get PCRE2
 111   svn co svn://vcs.exim.org/pcre2/code/trunk pcre
 112   # Get lib/Fuzzer. Assuming that you already have fresh clang in PATH.
 113   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
 114   # Build PCRE2 with AddressSanitizer and coverage.
 115   (cd pcre; ./autogen.sh; CC="clang -fsanitize=address $COV_FLAGS" ./configure --prefix=`pwd`/../inst && make -j && make install)
 116   # Build lib/Fuzzer files.
 117   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
 118   # Build the actual function that does something interesting with PCRE2.
 119   cat << EOF > pcre_fuzzer.cc
 120   #include <string.h>
 121   #include "pcre2posix.h"
 122   extern "C" void LLVMFuzzerTestOneInput(const unsigned char *data, size_t size) {
 123     if (size < 1) return;
 124     char *str = new char[size+1];
 125     memcpy(str, data, size);
 126     str[size] = 0;
 127     regex_t preg;
 128     if (0 == regcomp(&preg, str, 0)) {
 129       regexec(&preg, str, 0, 0, 0);
 130       regfree(&preg);
 131     }
 132     delete [] str;
 133   }
 134   EOF
 135   clang++ -g -fsanitize=address $COV_FLAGS -c -std=c++11  -I inst/include/ pcre_fuzzer.cc
 136   # Link.
 137   clang++ -g -fsanitize=address -Wl,--whole-archive inst/lib/*.a -Wl,-no-whole-archive Fuzzer*.o pcre_fuzzer.o -o pcre_fuzzer
 138
 139 This will give you a binary of the fuzzer, called ``pcre_fuzzer``.
 140 Now, create a directory that will hold the test corpus::
 141
 142   mkdir -p CORPUS
 143
 144 For simple input languages like regular expressions this is all you need.
 145 For more complicated inputs populate the directory with some input samples.
 146 Now run the fuzzer with the corpus dir as the only parameter::
 147
 148   ./pcre_fuzzer ./CORPUS
 149
 150 You will see output like this::
 151
 152   Seed: 1876794929
 153   #0      READ   cov 0 bits 0 units 1 exec/s 0
 154   #1      pulse  cov 3 bits 0 units 1 exec/s 0
 155   #1      INITED cov 3 bits 0 units 1 exec/s 0
 156   #2      pulse  cov 208 bits 0 units 1 exec/s 0
 157   #2      NEW    cov 208 bits 0 units 2 exec/s 0 L: 64
 158   #3      NEW    cov 217 bits 0 units 3 exec/s 0 L: 63
 159   #4      pulse  cov 217 bits 0 units 3 exec/s 0
 160
 161 * The ``Seed:`` line shows you the current random seed (you can change it with ``-seed=N`` flag).
 162 * 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).
 163 * The ``INITED`` line shows you that how many inputs will be fuzzed.
 164 * 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.
 165 * The ``pulse`` lines appear periodically to show the current status.
 166
 167 Now, interrupt the fuzzer and run it again the same way. You will see::
 168
 169   Seed: 1879995378
 170   #0      READ   cov 0 bits 0 units 564 exec/s 0
 171   #1      pulse  cov 502 bits 0 units 564 exec/s 0
 172   ...
 173   #512    pulse  cov 2933 bits 0 units 564 exec/s 512
 174   #564    INITED cov 2991 bits 0 units 344 exec/s 564
 175   #1024   pulse  cov 2991 bits 0 units 344 exec/s 1024
 176   #1455   NEW    cov 2995 bits 0 units 345 exec/s 1455 L: 49
 177
 178 This time you were running the fuzzer with a non-empty input corpus (564 items).
 179 As the first step, the fuzzer minimized the set to produce 344 interesting items (the ``INITED`` line)
 180
 181 It is quite convenient to store test corpuses in git.
 182 As an example, here is a git repository with test inputs for the above PCRE2 fuzzer::
 183
 184   git clone https://github.com/kcc/fuzzing-with-sanitizers.git
 185   ./pcre_fuzzer ./fuzzing-with-sanitizers/pcre2/C1/
 186
 187 You may run ``N`` independent fuzzer jobs in parallel on ``M`` CPUs::
 188
 189   N=100; M=4; ./pcre_fuzzer ./CORPUS -jobs=$N -workers=$M
 190
 191 By default (``-reload=1``) the fuzzer processes will periodically scan the CORPUS directory
 192 and reload any new tests. This way the test inputs found by one process will be picked up
 193 by all others.
 194
 195 If ``-workers=$M`` is not supplied, ``min($N,NumberOfCpuCore/2)`` will be used.
 196
 197 Heartbleed
 198 ----------
 199 Remember Heartbleed_?
 200 As it was recently `shown <https://blog.hboeck.de/archives/868-How-Heartbleed-couldve-been-found.html>`_,
 201 fuzzing with AddressSanitizer can find Heartbleed. Indeed, here are the step-by-step instructions
 202 to find Heartbleed with LibFuzzer::
 203
 204   wget https://www.openssl.org/source/openssl-1.0.1f.tar.gz
 205   tar xf openssl-1.0.1f.tar.gz
 206   COV_FLAGS="-fsanitize-coverage=edge,indirect-calls" # -fsanitize-coverage=8bit-counters
 207   (cd openssl-1.0.1f/ && ./config &&
 208     make -j 32 CC="clang -g -fsanitize=address $COV_FLAGS")
 209   # Get and build LibFuzzer
 210   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
 211   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
 212   # Get examples of key/pem files.
 213   git clone   https://github.com/hannob/selftls
 214   cp selftls/server* . -v
 215   cat << EOF > handshake-fuzz.cc
 216   #include <openssl/ssl.h>
 217   #include <openssl/err.h>
 218   #include <assert.h>
 219   SSL_CTX *sctx;
 220   int Init() {
 221     SSL_library_init();
 222     SSL_load_error_strings();
 223     ERR_load_BIO_strings();
 224     OpenSSL_add_all_algorithms();
 225     assert (sctx = SSL_CTX_new(TLSv1_method()));
 226     assert (SSL_CTX_use_certificate_file(sctx, "server.pem", SSL_FILETYPE_PEM));
 227     assert (SSL_CTX_use_PrivateKey_file(sctx, "server.key", SSL_FILETYPE_PEM));
 228     return 0;
 229   }
 230   extern "C" void LLVMFuzzerTestOneInput(unsigned char *Data, size_t Size) {
 231     static int unused = Init();
 232     SSL *server = SSL_new(sctx);
 233     BIO *sinbio = BIO_new(BIO_s_mem());
 234     BIO *soutbio = BIO_new(BIO_s_mem());
 235     SSL_set_bio(server, sinbio, soutbio);
 236     SSL_set_accept_state(server);
 237     BIO_write(sinbio, Data, Size);
 238     SSL_do_handshake(server);
 239     SSL_free(server);
 240   }
 241   EOF
 242   # Build the fuzzer.
 243   clang++ -g handshake-fuzz.cc  -fsanitize=address \
 244     openssl-1.0.1f/libssl.a openssl-1.0.1f/libcrypto.a Fuzzer*.o
 245   # Run 20 independent fuzzer jobs.
 246   ./a.out  -jobs=20 -workers=20
 247
 248 Voila::
 249
 250   #1048576        pulse  cov 3424 bits 0 units 9 exec/s 24385
 251   =================================================================
 252   ==17488==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x629000004748 at pc 0x00000048c979 bp 0x7fffe3e864f0 sp 0x7fffe3e85ca8
 253   READ of size 60731 at 0x629000004748 thread T0
 254       #0 0x48c978 in __asan_memcpy
 255       #1 0x4db504 in tls1_process_heartbeat openssl-1.0.1f/ssl/t1_lib.c:2586:3
 256       #2 0x580be3 in ssl3_read_bytes openssl-1.0.1f/ssl/s3_pkt.c:1092:4
 257
 258 Advanced features
 259 =================
 260
 261 Tokens
 262 ------
 263
 264 By default, the fuzzer is not aware of complexities of the input language
 265 and when fuzzing e.g. a C++ parser it will mostly stress the lexer.
 266 It is very hard for the fuzzer to come up with something like ``reinterpret_cast<int>``
 267 from a test corpus that doesn't have it.
 268 See a detailed discussion of this topic at
 269 http://lcamtuf.blogspot.com/2015/01/afl-fuzz-making-up-grammar-with.html.
 270
 271 lib/Fuzzer implements a simple technique that allows to fuzz input languages with
 272 long tokens. All you need is to prepare a text file containing up to 253 tokens, one token per line,
 273 and pass it to the fuzzer as ``-tokens=TOKENS_FILE.txt``.
 274 Three implicit tokens are added: ``" "``, ``"\t"``, and ``"\n"``.
 275 The fuzzer itself will still be mutating a string of bytes
 276 but before passing this input to the target library it will replace every byte ``b`` with the ``b``-th token.
 277 If there are less than ``b`` tokens, a space will be added instead.
 278
 279 Data-flow-guided fuzzing
 280 ------------------------
 281
 282 *EXPERIMENTAL*.
 283 With an additional compiler flag ``-fsanitize-coverage=trace-cmp`` (see SanitizerCoverageTraceDataFlow_)
 284 and extra run-time flag ``-use_traces=1`` the fuzzer will try to apply *data-flow-guided fuzzing*.
 285 That is, the fuzzer will record the inputs to comparison instructions, switch statements,
 286 and several libc functions (``memcmp``, ``strcmp``, ``strncmp``, etc).
 287 It will later use those recorded inputs during mutations.
 288
 289 This mode can be combined with DataFlowSanitizer_ to achieve better sensitivity.
 290
 291 AFL compatibility
 292 -----------------
 293 LibFuzzer can be used in parallel with AFL_ on the same test corpus.
 294 Both fuzzers expect the test corpus to reside in a directory, one file per input.
 295 You can run both fuzzers on the same corpus in parallel::
 296
 297   ./afl-fuzz -i testcase_dir -o findings_dir /path/to/program -r @@
 298   ./llvm-fuzz testcase_dir findings_dir  # Will write new tests to testcase_dir
 299
 300 Periodically restart both fuzzers so that they can use each other's findings.
 301
 302 How good is my fuzzer?
 303 ----------------------
 304
 305 Once you implement your target function ``LLVMFuzzerTestOneInput`` and fuzz it to death,
 306 you will want to know whether the function or the corpus can be improved further.
 307 One easy to use metric is, of course, code coverage.
 308 You can get the coverage for your corpus like this::
 309
 310   ASAN_OPTIONS=coverage_pcs=1 ./fuzzer CORPUS_DIR -runs=0
 311
 312 This will run all the tests in the CORPUS_DIR but will not generate any new tests
 313 and dump covered PCs to disk before exiting.
 314 Then you can subtract the set of covered PCs from the set of all instrumented PCs in the binary,
 315 see SanitizerCoverage_ for details.
 316
 317 User-supplied mutators
 318 ----------------------
 319
 320 LibFuzzer allows to use custom (user-supplied) mutators,
 321 see FuzzerInterface.h_
 322
 323 Fuzzing components of LLVM
 324 ==========================
 325
 326 clang-format-fuzzer
 327 -------------------
 328 The inputs are random pieces of C++-like text.
 329
 330 Build (make sure to use fresh clang as the host compiler)::
 331
 332     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
 333     ninja clang-format-fuzzer
 334     mkdir CORPUS_DIR
 335     ./bin/clang-format-fuzzer CORPUS_DIR
 336
 337 Optionally build other kinds of binaries (asan+Debug, msan, ubsan, etc).
 338
 339 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=23052
 340
 341 clang-fuzzer
 342 ------------
 343
 344 The default behavior is very similar to ``clang-format-fuzzer``.
 345 Clang can also be fuzzed with Tokens_ using ``-tokens=$LLVM/lib/Fuzzer/cxx_fuzzer_tokens.txt`` option.
 346
 347 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=23057
 348
 349 llvm-as-fuzzer
 350 --------------
 351
 352 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=24639
 353
 354 Buildbot
 355 --------
 356
 357 We have a buildbot that runs the above fuzzers for LLVM components
 358 24/7/365 at http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer .
 359
 360 Pre-fuzzed test inputs in git
 361 -----------------------------
 362
 363 The buildbot occumulates large test corpuses over time.
 364 The corpuses are stored in git on github and can be used like this::
 365
 366   git clone https://github.com/kcc/fuzzing-with-sanitizers.git
 367   bin/clang-format-fuzzer fuzzing-with-sanitizers/llvm/clang-format/C1
 368   bin/clang-fuzzer        fuzzing-with-sanitizers/llvm/clang/C1/
 369   bin/clang-fuzzer        fuzzing-with-sanitizers/llvm/clang/TOK1  -tokens=$LLVM/llvm/lib/Fuzzer/cxx_fuzzer_tokens.txt
 370   bin/llvm-as-fuzzer      fuzzing-with-sanitizers/llvm/llvm-as/C1  -only_ascii=1
 371
 372
 373 FAQ
 374 =========================
 375
 376 Q. Why Fuzzer does not use any of the LLVM support?
 377 ---------------------------------------------------
 378
 379 There are two reasons.
 380
 381 First, we want this library to be used outside of the LLVM w/o users having to
 382 build the rest of LLVM. This may sound unconvincing for many LLVM folks,
 383 but in practice the need for building the whole LLVM frightens many potential
 384 users -- and we want more users to use this code.
 385
 386 Second, there is a subtle technical reason not to rely on the rest of LLVM, or
 387 any other large body of code (maybe not even STL). When coverage instrumentation
 388 is enabled, it will also instrument the LLVM support code which will blow up the
 389 coverage set of the process (since the fuzzer is in-process). In other words, by
 390 using more external dependencies we will slow down the fuzzer while the main
 391 reason for it to exist is extreme speed.
 392
 393 Q. What about Windows then? The Fuzzer contains code that does not build on Windows.
 394 ------------------------------------------------------------------------------------
 395
 396 The sanitizer coverage support does not work on Windows either as of 01/2015.
 397 Once it's there, we'll need to re-implement OS-specific parts (I/O, signals).
 398
 399 Q. When this Fuzzer is not a good solution for a problem?
 400 ---------------------------------------------------------
 401
 402 * If the test inputs are validated by the target library and the validator
 403   asserts/crashes on invalid inputs, the in-process fuzzer is not applicable
 404   (we could use fork() w/o exec, but it comes with extra overhead).
 405 * Bugs in the target library may accumulate w/o being detected. E.g. a memory
 406   corruption that goes undetected at first and then leads to a crash while
 407   testing another input. This is why it is highly recommended to run this
 408   in-process fuzzer with all sanitizers to detect most bugs on the spot.
 409 * It is harder to protect the in-process fuzzer from excessive memory
 410   consumption and infinite loops in the target library (still possible).
 411 * The target library should not have significant global state that is not
 412   reset between the runs.
 413 * Many interesting target libs are not designed in a way that supports
 414   the in-process fuzzer interface (e.g. require a file path instead of a
 415   byte array).
 416 * If a single test run takes a considerable fraction of a second (or
 417   more) the speed benefit from the in-process fuzzer is negligible.
 418 * If the target library runs persistent threads (that outlive
 419   execution of one test) the fuzzing results will be unreliable.
 420
 421 Q. So, what exactly this Fuzzer is good for?
 422 --------------------------------------------
 423
 424 This Fuzzer might be a good choice for testing libraries that have relatively
 425 small inputs, each input takes < 1ms to run, and the library code is not expected
 426 to crash on invalid inputs.
 427 Examples: regular expression matchers, text or binary format parsers.
 428
 429 Trophies
 430 ========
 431 * GLIBC: https://sourceware.org/glibc/wiki/FuzzingLibc
 432
 433 * MUSL LIBC:
 434
 435   * http://git.musl-libc.org/cgit/musl/commit/?id=39dfd58417ef642307d90306e1c7e50aaec5a35c
 436   * http://www.openwall.com/lists/oss-security/2015/03/30/3
 437
 438 * pugixml: https://github.com/zeux/pugixml/issues/39
 439
 440 * PCRE: Search for "LLVM fuzzer" in http://vcs.pcre.org/pcre2/code/trunk/ChangeLog?view=markup
 441
 442 * ICU: http://bugs.icu-project.org/trac/ticket/11838
 443
 444 * LLVM:
 445
 446   * Clang: https://llvm.org/bugs/show_bug.cgi?id=23057
 447
 448   * Clang-format: https://llvm.org/bugs/show_bug.cgi?id=23052
 449
 450   * libc++: https://llvm.org/bugs/show_bug.cgi?id=24411
 451
 452   * llvm-as: https://llvm.org/bugs/show_bug.cgi?id=24639
 453
 454
 455
 456 .. _pcre2: http://www.pcre.org/
 457
 458 .. _AFL: http://lcamtuf.coredump.cx/afl/
 459
 460 .. _SanitizerCoverage: http://clang.llvm.org/docs/SanitizerCoverage.html
 461 .. _SanitizerCoverageTraceDataFlow: http://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow
 462 .. _DataFlowSanitizer: http://clang.llvm.org/docs/DataFlowSanitizer.html
 463
 464 .. _Heartbleed: http://en.wikipedia.org/wiki/Heartbleed
 465
 466 .. _FuzzerInterface.h: https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/FuzzerInterface.h