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