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