Roll src/third_party/afl/src/ 2.14b..2.30b (16 versions).

third_party/afl/src/docs/technical_details.txt

 ===================================
 Technical "whitepaper" for afl-fuzz
 ===================================
 
   This document provides a quick overview of the guts of American Fuzzy Lop.
   See README for the general instruction manual; and for a discussion of
   motivations and design goals behind AFL, see historical_notes.txt.
 
 0) Design statement
 -------------------
@@ skipping 67 matching lines @@
 2) Detecting new behaviors
 --------------------------
 
 The fuzzer maintains a global map of tuples seen in previous executions; this
 data can be rapidly compared with individual traces and updated in just a couple
 of dword- or qword-wide instructions and a simple loop.
 
 When a mutated input produces an execution trace containing new tuples, the
 corresponding input file is preserved and routed for additional processing
 later on (see section #3). Inputs that do not trigger new local-scale state
-transitions in the execution trace are discarded, even if their overall
-instrumentation output pattern is unique.
+transitions in the execution trace (i.e., produce no new tuples) are discarded,
+even if their overall control flow sequence is unique.
 
 This approach allows for a very fine-grained and long-term exploration of
 program state while not having to perform any computationally intensive and
 fragile global comparisons of complex execution traces, and while avoiding the
 scourge of path explosion.
 
 To illustrate the properties of the algorithm, consider that the second trace
 shown below would be considered substantially new because of the presence of
 new tuples (CA, AE):
 
   #1: A -> B -> C -> D -> E
   #2: A -> B -> C -> A -> E
 
 At the same time, with #2 processed, the following pattern will not be seen
-as unique, despite having a markedly different execution path:
+as unique, despite having a markedly different overall execution path:
 
   #3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E
 
 In addition to detecting new tuples, the fuzzer also considers coarse tuple
 hit counts. These are divided into several buckets:
 
   1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+
 
 To some extent, the number of buckets is an implementation artifact: it allows
 an in-place mapping of an 8-bit counter generated by the instrumentation to
@@ skipping 20 matching lines @@
 the same code. Empirical testing strongly suggests that more generous time
 limits are not worth the cost.
 
 3) Evolving the input queue
 ---------------------------
 
 Mutated test cases that produced new state transitions within the program are
 added to the input queue and used as a starting point for future rounds of
 fuzzing. They supplement, but do not automatically replace, existing finds.
 
-This approach allows the tool to progressively explore various disjoint and
-possibly mutually incompatible features of the underlying data format, as
-shown in this image:
+In contrast to more greedy genetic algorithms, this approach allows the tool
+to progressively explore various disjoint and possibly mutually incompatible
+features of the underlying data format, as shown in this image:
 
   http://lcamtuf.coredump.cx/afl/afl_gzip.png
 
 Several practical examples of the results of this algorithm are discussed
 here:
 
   http://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html
   http://lcamtuf.blogspot.com/2014/11/afl-fuzz-nobody-expects-cdata-sections.html
 
 The synthetic corpus produced by this process is essentially a compact
@@ skipping 36 matching lines @@
     Queue extension | Blocks  | Edges   | Edge hit | Number of unique
       strategy used | reached | reached | cnt var  | crashes found
   ------------------+---------+---------+----------+------------------
      (Initial file) | 624     | 717     | 1.00     | -
                     |         |         |          |
       Blind fuzzing | 1,101   | 1,409   | 1.60     | 0
      Block coverage | 1,255   | 1,649   | 1.48     | 0
       Edge coverage | 1,259   | 1,734   | 1.72     | 0
           AFL model | 1,452   | 2,040   | 3.16     | 1
 
-Some of the earlier work on evolutionary fuzzing suggested maintaining just a
-single test case and selecting for mutations that improve coverage. At least
-in the tests described above, this "greedy" method appeared to offer no
-substantial benefits over blind fuzzing.
+At noted earlier on, some of the prior work on genetic fuzzing relied on
+maintaining a single test case and evolving it to maximize coverage. At least
+in the tests described above, this "greedy" approach appears to confer no
+substantial benefits over blind fuzzing strategies.
 
 4) Culling the corpus
 ---------------------
 
 The progressive state exploration approach outlined above means that some of
 the test cases synthesized later on in the game may have edge coverage that
 is a strict superset of the coverage provided by their ancestors.
 
 To optimize the fuzzing effort, AFL periodically re-evaluates the queue using a
 fast algorithm that selects a smaller subset of test cases that still cover
@@ skipping 38 matching lines @@
 external tools.
 
 5) Trimming input files
 -----------------------
 
 File size has a dramatic impact on fuzzing performance, both because large
 files make the target binary slower, and because they reduce the likelihood
 that a mutation would touch important format control structures, rather than
 redundant data blocks. This is discussed in more detail in perf_tips.txt.
 
-The possibility of a bad starting corpus provided by the user aside, some
-types of mutations can have the effect of iteratively increasing the size of
-the generated files, so it is important to counter this trend.
+The possibility that the user will provide a low-quality starting corpus aside,
+some types of mutations can have the effect of iteratively increasing the size
+of the generated files, so it is important to counter this trend.
 
 Luckily, the instrumentation feedback provides a simple way to automatically
 trim down input files while ensuring that the changes made to the files have no
 impact on the execution path.
 
 The built-in trimmer in afl-fuzz attempts to sequentially remove blocks of data
 with variable length and stepover; any deletion that doesn't affect the checksum
 of the trace map is committed to disk. The trimmer is not designed to be
 particularly thorough; instead, it tries to strike a balance between precision
-and the number of execve() calls spent on the process. The average per-file
-gains are around 5-20%.
+and the number of execve() calls spent on the process, selecting the block size
+and stepover to match. The average per-file gains are around 5-20%.
 
 The standalone afl-tmin tool uses a more exhaustive, iterative algorithm, and
-also attempts to perform alphabet normalization on the trimmed files.
+also attempts to perform alphabet normalization on the trimmed files. 
 
 6) Fuzzing strategies
 ---------------------
 
 The feedback provided by the instrumentation makes it easy to understand the
 value of various fuzzing strategies and optimize their parameters so that they
 work equally well across a wide range of file types. The strategies used by
 afl-fuzz are generally format-agnostic and are discussed in more detail here:
 
   http://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html
 
 It is somewhat notable that especially early on, most of the work done by
 afl-fuzz is actually highly deterministic, and progresses to random stacked
 modifications and test case splicing only at a later stage. The deterministic
 strategies include:
 
   - Sequential bit flips with varying lengths and stepovers,
 
   - Sequential addition and subtraction of small integers,
 
   - Sequential insertion of known interesting integers (0, 1, INT_MAX, etc),
 
-The non-deterministic steps include stacked bit flips, insertions, deletions,
-arithmetics, and splicing of different test cases.
+The purpose of opening with deterministic steps is related to their tendency to
+produce compact test cases and small diffs between the non-crashing and crashing
+inputs.
 
-Their relative yields and execve() costs have been investigated and are
-discussed in the aforementioned blog post.
+With deterministic fuzzing out of the way, the non-deterministic steps include
+stacked bit flips, insertions, deletions, arithmetics, and splicing of different
+test cases.
+
+The relative yields and execve() costs of all these strategies have been
+investigated and are discussed in the aforementioned blog post.
 
 For the reasons discussed in historical_notes.txt (chiefly, performance,
 simplicity, and reliability), AFL generally does not try to reason about the
 relationship between specific mutations and program states; the fuzzing steps
 are nominally blind, and are guided only by the evolutionary design of the
 input queue.
 
 That said, there is one (trivial) exception to this rule: when a new queue
-entry goes through the initial set of deterministic fuzzing steps, and some
-regions in the file are observed to have no effect on the checksum of the
+entry goes through the initial set of deterministic fuzzing steps, and tweaks to
+some regions in the file are observed to have no effect on the checksum of the
 execution path, they may be excluded from the remaining phases of
-deterministic fuzzing - and proceed straight to random tweaks. Especially for
-verbose, human-readable data formats, this can reduce the number of execs by
-10-40% or so without an appreciable drop in coverage. In extreme cases, such
-as normally block-aligned tar archives, the gains can be as high as 90%.
+deterministic fuzzing - and the fuzzer may proceed straight to random tweaks.
+Especially for verbose, human-readable data formats, this can reduce the number
+of execs by 10-40% or so without an appreciable drop in coverage. In extreme
+cases, such as normally block-aligned tar archives, the gains can be as high as
+90%.
 
 Because the underlying "effector maps" are local every queue entry and remain
 in force only during deterministic stages that do not alter the size or the
 general layout of the underlying file, this mechanism appears to work very
 reliably and proved to be simple to implement.
 
 7) Dictionaries
 ---------------
 
 The feedback provided by the instrumentation makes it easy to automatically
@@ skipping 11 matching lines @@
 design of the queue together provide a feedback mechanism to differentiate
 between meaningless mutations and ones that trigger new behaviors in the
 instrumented code - and to incrementally build more complex syntax on top of
 this discovery.
 
 The dictionaries have been shown to enable the fuzzer to rapidly reconstruct
 the grammar of highly verbose and complex languages such as JavaScript, SQL,
 or XML; several examples of generated SQL statements are given in the blog
 post mentioned above.
 
+Interestingly, the AFL instrumentation also allows the fuzzer to automatically
+isolate syntax tokens already present in an input file. It can do so by looking
+for run of bytes that, when flipped, produce a consistent change to the
+program's execution path; this is suggestive of an underlying atomic comparison
+to a predefined value baked into the code. The fuzzer relies on this signal
+to build compact "auto dictionaries" that are then used in conjunction with
+other fuzzing strategies.
+
 8) De-duping crashes
 --------------------
 
 De-duplication of crashes is one of the more important problems for any
 competent fuzzing tool. Many of the naive approaches run into problems; in
 particular, looking just at the faulting address may lead to completely
 unrelated issues being clustered together if the fault happens in a common
 library function (say, strcmp, strcpy); while checksumming call stack
 backtraces can lead to extreme crash count inflation if the fault can be
 reached through a number of different, possibly recursive code paths.
@@ skipping 43 matching lines @@
   http://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html
 
 The fork server is an integral aspect of the injected instrumentation and
 simply stops at the first instrumented function to await commands from
 afl-fuzz.
 
 With fast targets, the fork server can offer considerable performance gains,
 usually between 1.5x and 2x. It is also possible to:
 
   - Use the fork server in manual ("deferred") mode, skipping over larger,
-    user-selected chunks of initialization code. With some targets, this can
+    user-selected chunks of initialization code. It requires very modest
+    code changes to the targeted program, and With some targets, can
     produce 10x+ performance gains.
 
   - Enable "persistent" mode, where a single process is used to try out
     multiple inputs, greatly limiting the overhead of repetitive fork()
-    calls. As with the previous mode, this requires custom modifications,
+    calls. This generally requires some code changes to the targeted program,
     but can improve the performance of fast targets by a factor of 5 or more
-    - approximating the benefits of in-process fuzzing jobs.
+    - approximating the benefits of in-process fuzzing jobs while still
+    maintaining very robust isolation between the fuzzer process and the
+    targeted binary.
 
 11) Parallelization
 -------------------
 
 The parallelization mechanism relies on periodically examining the queues
 produced by independently-running instances on other CPU cores or on remote
-machines, and then selectively pulling in the test cases that produce behaviors
-not yet seen by the fuzzer at hand.
+machines, and then selectively pulling in the test cases that, when tried
+out locally, produce behaviors not yet seen by the fuzzer at hand.
 
 This allows for extreme flexibility in fuzzer setup, including running synced
 instances against different parsers of a common data format, often with
 synergistic effects.
 
 For more information about this design, see parallel_fuzzing.txt.
 
 12) Binary-only instrumentation
 -------------------------------
 
@@ skipping 61 matching lines @@
     unlikely. This is suggestive of a checksum or other "magic" integer.
 
   - "Suspected checksummed block" - a long block of data where any change 
     always triggers the same new execution path. Likely caused by failing
     a checksum or a similar integrity check before any subsequent parsing
     takes place.
 
   - "Magic value section" - a generic token where changes cause the type
     of binary behavior outlined earlier, but that doesn't meet any of the
     other criteria. May be an atomically compared keyword or so.