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