2b32337aebbe65f186fbf8b4c9b40f31fce121fd
[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" 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. Example: ./fuzzer -save_minimized_corpus=1 NEW_EMPTY_DIR OLD_CORPUS
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   sync_command                          0       Execute an external command "<sync_command> <test_corpus>" to synchronize the test corpus.
68   sync_timeout                          600     Minimum timeout between syncs.
69   use_traces                            0       Experimental: use instruction traces
70   only_ascii                            0       If 1, generate only ASCII (isprint+isspace) inputs.
71
72
73 For the full list of flags run the fuzzer binary with ``-help=1``.
74
75 Usage examples
76 ==============
77
78 Toy example
79 -----------
80
81 A simple function that does something interesting if it receives the input "HI!"::
82
83   cat << EOF >> test_fuzzer.cc
84   extern "C" void LLVMFuzzerTestOneInput(const unsigned char *data, unsigned long size) {
85     if (size > 0 && data[0] == 'H')
86       if (size > 1 && data[1] == 'I')
87          if (size > 2 && data[2] == '!')
88          __builtin_trap();
89   }
90   EOF
91   # Get lib/Fuzzer. Assuming that you already have fresh clang in PATH.
92   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
93   # Build lib/Fuzzer files.
94   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
95   # Build test_fuzzer.cc with asan and link against lib/Fuzzer.
96   clang++ -fsanitize=address -fsanitize-coverage=edge test_fuzzer.cc Fuzzer*.o
97   # Run the fuzzer with no corpus.
98   ./a.out
99
100 You should get ``Illegal instruction (core dumped)`` pretty quickly.
101
102 PCRE2
103 -----
104
105 Here we show how to use lib/Fuzzer on something real, yet simple: pcre2_::
106
107   COV_FLAGS=" -fsanitize-coverage=edge,indirect-calls,8bit-counters"
108   # Get PCRE2
109   svn co svn://vcs.exim.org/pcre2/code/trunk pcre
110   # Get lib/Fuzzer. Assuming that you already have fresh clang in PATH.
111   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
112   # Build PCRE2 with AddressSanitizer and coverage.
113   (cd pcre; ./autogen.sh; CC="clang -fsanitize=address $COV_FLAGS" ./configure --prefix=`pwd`/../inst && make -j && make install)
114   # Build lib/Fuzzer files.
115   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
116   # Build the actual function that does something interesting with PCRE2.
117   cat << EOF > pcre_fuzzer.cc
118   #include <string.h>
119   #include "pcre2posix.h"
120   extern "C" void LLVMFuzzerTestOneInput(const unsigned char *data, size_t size) {
121     if (size < 1) return;
122     char *str = new char[size+1];
123     memcpy(str, data, size);
124     str[size] = 0;
125     regex_t preg;
126     if (0 == regcomp(&preg, str, 0)) {
127       regexec(&preg, str, 0, 0, 0);
128       regfree(&preg);
129     }
130     delete [] str;
131   }
132   EOF
133   clang++ -g -fsanitize=address $COV_FLAGS -c -std=c++11  -I inst/include/ pcre_fuzzer.cc
134   # Link.
135   clang++ -g -fsanitize=address -Wl,--whole-archive inst/lib/*.a -Wl,-no-whole-archive Fuzzer*.o pcre_fuzzer.o -o pcre_fuzzer
136
137 This will give you a binary of the fuzzer, called ``pcre_fuzzer``.
138 Now, create a directory that will hold the test corpus::
139
140   mkdir -p CORPUS
141
142 For simple input languages like regular expressions this is all you need.
143 For more complicated inputs populate the directory with some input samples.
144 Now run the fuzzer with the corpus dir as the only parameter::
145
146   ./pcre_fuzzer ./CORPUS
147
148 You will see output like this::
149
150   Seed: 1876794929
151   #0      READ   cov 0 bits 0 units 1 exec/s 0
152   #1      pulse  cov 3 bits 0 units 1 exec/s 0
153   #1      INITED cov 3 bits 0 units 1 exec/s 0
154   #2      pulse  cov 208 bits 0 units 1 exec/s 0
155   #2      NEW    cov 208 bits 0 units 2 exec/s 0 L: 64
156   #3      NEW    cov 217 bits 0 units 3 exec/s 0 L: 63
157   #4      pulse  cov 217 bits 0 units 3 exec/s 0
158
159 * The ``Seed:`` line shows you the current random seed (you can change it with ``-seed=N`` flag).
160 * 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).
161 * The ``INITED`` line shows you that how many inputs will be fuzzed.
162 * 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.
163 * The ``pulse`` lines appear periodically to show the current status.
164
165 Now, interrupt the fuzzer and run it again the same way. You will see::
166
167   Seed: 1879995378
168   #0      READ   cov 0 bits 0 units 564 exec/s 0
169   #1      pulse  cov 502 bits 0 units 564 exec/s 0
170   ...
171   #512    pulse  cov 2933 bits 0 units 564 exec/s 512
172   #564    INITED cov 2991 bits 0 units 344 exec/s 564
173   #1024   pulse  cov 2991 bits 0 units 344 exec/s 1024
174   #1455   NEW    cov 2995 bits 0 units 345 exec/s 1455 L: 49
175
176 This time you were running the fuzzer with a non-empty input corpus (564 items).
177 As the first step, the fuzzer minimized the set to produce 344 interesting items (the ``INITED`` line)
178
179 It is quite convenient to store test corpuses in git.
180 As an example, here is a git repository with test inputs for the above PCRE2 fuzzer::
181
182   git clone https://github.com/kcc/fuzzing-with-sanitizers.git
183   ./pcre_fuzzer ./fuzzing-with-sanitizers/pcre2/C1/
184
185 You may run ``N`` independent fuzzer jobs in parallel on ``M`` CPUs::
186
187   N=100; M=4; ./pcre_fuzzer ./CORPUS -jobs=$N -workers=$M
188
189 By default (``-reload=1``) the fuzzer processes will periodically scan the CORPUS directory
190 and reload any new tests. This way the test inputs found by one process will be picked up
191 by all others.
192
193 If ``-workers=$M`` is not supplied, ``min($N,NumberOfCpuCore/2)`` will be used.
194
195 Heartbleed
196 ----------
197 Remember Heartbleed_?
198 As it was recently `shown <https://blog.hboeck.de/archives/868-How-Heartbleed-couldve-been-found.html>`_,
199 fuzzing with AddressSanitizer can find Heartbleed. Indeed, here are the step-by-step instructions
200 to find Heartbleed with LibFuzzer::
201
202   wget https://www.openssl.org/source/openssl-1.0.1f.tar.gz
203   tar xf openssl-1.0.1f.tar.gz
204   COV_FLAGS="-fsanitize-coverage=edge,indirect-calls" # -fsanitize-coverage=8bit-counters
205   (cd openssl-1.0.1f/ && ./config &&
206     make -j 32 CC="clang -g -fsanitize=address $COV_FLAGS")
207   # Get and build LibFuzzer
208   svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
209   clang -c -g -O2 -std=c++11 Fuzzer/*.cpp -IFuzzer
210   # Get examples of key/pem files.
211   git clone   https://github.com/hannob/selftls
212   cp selftls/server* . -v
213   cat << EOF > handshake-fuzz.cc
214   #include <openssl/ssl.h>
215   #include <openssl/err.h>
216   #include <assert.h>
217   SSL_CTX *sctx;
218   int Init() {
219     SSL_library_init();
220     SSL_load_error_strings();
221     ERR_load_BIO_strings();
222     OpenSSL_add_all_algorithms();
223     assert (sctx = SSL_CTX_new(TLSv1_method()));
224     assert (SSL_CTX_use_certificate_file(sctx, "server.pem", SSL_FILETYPE_PEM));
225     assert (SSL_CTX_use_PrivateKey_file(sctx, "server.key", SSL_FILETYPE_PEM));
226     return 0;
227   }
228   extern "C" void LLVMFuzzerTestOneInput(unsigned char *Data, size_t Size) {
229     static int unused = Init();
230     SSL *server = SSL_new(sctx);
231     BIO *sinbio = BIO_new(BIO_s_mem());
232     BIO *soutbio = BIO_new(BIO_s_mem());
233     SSL_set_bio(server, sinbio, soutbio);
234     SSL_set_accept_state(server);
235     BIO_write(sinbio, Data, Size);
236     SSL_do_handshake(server);
237     SSL_free(server);
238   }
239   EOF
240   # Build the fuzzer. 
241   clang++ -g handshake-fuzz.cc  -fsanitize=address \
242     openssl-1.0.1f/libssl.a openssl-1.0.1f/libcrypto.a Fuzzer*.o
243   # Run 20 independent fuzzer jobs.
244   ./a.out  -jobs=20 -workers=20
245
246 Voila::
247
248   #1048576        pulse  cov 3424 bits 0 units 9 exec/s 24385
249   =================================================================
250   ==17488==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x629000004748 at pc 0x00000048c979 bp 0x7fffe3e864f0 sp 0x7fffe3e85ca8
251   READ of size 60731 at 0x629000004748 thread T0
252       #0 0x48c978 in __asan_memcpy
253       #1 0x4db504 in tls1_process_heartbeat openssl-1.0.1f/ssl/t1_lib.c:2586:3
254       #2 0x580be3 in ssl3_read_bytes openssl-1.0.1f/ssl/s3_pkt.c:1092:4
255
256 Advanced features
257 =================
258
259 Dictionaries
260 ------------
261 *EXPERIMENTAL*.
262 LibFuzzer supports user-supplied dictionaries with input language keywords
263 or other interesting byte sequences (e.g. multi-byte magic values).
264 Use ``-dict=DICTIONARY_FILE``. For some input languages using a dictionary
265 may significantly improve the search speed.
266 The dictionary syntax is similar to that used by AFL_ for its ``-x`` option::
267
268   # Lines starting with '#' and empty lines are ignored.
269
270   # Adds "blah" (w/o quotes) to the dictionary.
271   kw1="blah"
272   # Use \\ for backslash and \" for quotes.
273   kw2="\"ac\\dc\""
274   # Use \xAB for hex values
275   kw3="\xF7\xF8"
276   # the name of the keyword followed by '=' may be omitted:
277   "foo\x0Abar"
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 behavior is very similar to ``clang-format-fuzzer``.
345
346 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=23057
347
348 llvm-as-fuzzer
349 --------------
350
351 Tracking bug: https://llvm.org/bugs/show_bug.cgi?id=24639
352
353 Buildbot
354 --------
355
356 We have a buildbot that runs the above fuzzers for LLVM components
357 24/7/365 at http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer .
358
359 Pre-fuzzed test inputs in git
360 -----------------------------
361
362 The buildbot occumulates large test corpuses over time.
363 The corpuses are stored in git on github and can be used like this::
364
365   git clone https://github.com/kcc/fuzzing-with-sanitizers.git
366   bin/clang-format-fuzzer fuzzing-with-sanitizers/llvm/clang-format/C1
367   bin/clang-fuzzer        fuzzing-with-sanitizers/llvm/clang/C1/
368   bin/llvm-as-fuzzer      fuzzing-with-sanitizers/llvm/llvm-as/C1  -only_ascii=1
369
370
371 FAQ
372 =========================
373
374 Q. Why Fuzzer does not use any of the LLVM support?
375 ---------------------------------------------------
376
377 There are two reasons.
378
379 First, we want this library to be used outside of the LLVM w/o users having to
380 build the rest of LLVM. This may sound unconvincing for many LLVM folks,
381 but in practice the need for building the whole LLVM frightens many potential
382 users -- and we want more users to use this code.
383
384 Second, there is a subtle technical reason not to rely on the rest of LLVM, or
385 any other large body of code (maybe not even STL). When coverage instrumentation
386 is enabled, it will also instrument the LLVM support code which will blow up the
387 coverage set of the process (since the fuzzer is in-process). In other words, by
388 using more external dependencies we will slow down the fuzzer while the main
389 reason for it to exist is extreme speed.
390
391 Q. What about Windows then? The Fuzzer contains code that does not build on Windows.
392 ------------------------------------------------------------------------------------
393
394 The sanitizer coverage support does not work on Windows either as of 01/2015.
395 Once it's there, we'll need to re-implement OS-specific parts (I/O, signals).
396
397 Q. When this Fuzzer is not a good solution for a problem?
398 ---------------------------------------------------------
399
400 * If the test inputs are validated by the target library and the validator
401   asserts/crashes on invalid inputs, the in-process fuzzer is not applicable
402   (we could use fork() w/o exec, but it comes with extra overhead).
403 * Bugs in the target library may accumulate w/o being detected. E.g. a memory
404   corruption that goes undetected at first and then leads to a crash while
405   testing another input. This is why it is highly recommended to run this
406   in-process fuzzer with all sanitizers to detect most bugs on the spot.
407 * It is harder to protect the in-process fuzzer from excessive memory
408   consumption and infinite loops in the target library (still possible).
409 * The target library should not have significant global state that is not
410   reset between the runs.
411 * Many interesting target libs are not designed in a way that supports
412   the in-process fuzzer interface (e.g. require a file path instead of a
413   byte array).
414 * If a single test run takes a considerable fraction of a second (or
415   more) the speed benefit from the in-process fuzzer is negligible.
416 * If the target library runs persistent threads (that outlive
417   execution of one test) the fuzzing results will be unreliable.
418
419 Q. So, what exactly this Fuzzer is good for?
420 --------------------------------------------
421
422 This Fuzzer might be a good choice for testing libraries that have relatively
423 small inputs, each input takes < 1ms to run, and the library code is not expected
424 to crash on invalid inputs.
425 Examples: regular expression matchers, text or binary format parsers.
426
427 Trophies
428 ========
429 * GLIBC: https://sourceware.org/glibc/wiki/FuzzingLibc
430
431 * MUSL LIBC:
432
433   * http://git.musl-libc.org/cgit/musl/commit/?id=39dfd58417ef642307d90306e1c7e50aaec5a35c
434   * http://www.openwall.com/lists/oss-security/2015/03/30/3
435
436 * pugixml: https://github.com/zeux/pugixml/issues/39
437
438 * PCRE: Search for "LLVM fuzzer" in http://vcs.pcre.org/pcre2/code/trunk/ChangeLog?view=markup
439
440 * ICU: http://bugs.icu-project.org/trac/ticket/11838
441
442 * Freetype: https://savannah.nongnu.org/search/?words=LibFuzzer&type_of_search=bugs&Search=Search&exact=1#options
443
444 * Linux Kernel's BPF verifier: https://github.com/iovisor/bpf-fuzzer
445
446 * LLVM:
447
448   * Clang: https://llvm.org/bugs/show_bug.cgi?id=23057
449
450   * Clang-format: https://llvm.org/bugs/show_bug.cgi?id=23052
451
452   * libc++: https://llvm.org/bugs/show_bug.cgi?id=24411
453
454   * llvm-as: https://llvm.org/bugs/show_bug.cgi?id=24639
455
456   * Disassembler:
457     * Mips: Discovered a number of untested instructions for the Mips target
458       (see valid-mips*.s in http://reviews.llvm.org/rL247405,
459       http://reviews.llvm.org/rL247414, http://reviews.llvm.org/rL247416,
460       http://reviews.llvm.org/rL247417, http://reviews.llvm.org/rL247420,
461       and http://reviews.llvm.org/rL247422) as well some instructions that
462       successfully disassembled on ISA's where they were not valid (see
463       invalid-xfail.s files in the same commits).
464
465 .. _pcre2: http://www.pcre.org/
466
467 .. _AFL: http://lcamtuf.coredump.cx/afl/
468
469 .. _SanitizerCoverage: http://clang.llvm.org/docs/SanitizerCoverage.html
470 .. _SanitizerCoverageTraceDataFlow: http://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow
471 .. _DataFlowSanitizer: http://clang.llvm.org/docs/DataFlowSanitizer.html
472
473 .. _Heartbleed: http://en.wikipedia.org/wiki/Heartbleed
474
475 .. _FuzzerInterface.h: https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/FuzzerInterface.h