Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(277)

Unified Diff: third_party/afl/src/docs/technical_details.txt

Issue 2662883002: Roll AFL 2.31b:2.38b and switch coverage to use trace-pc-guard. (Closed)
Patch Set: Remove unneeded vuln_samples binaries. Created 3 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: third_party/afl/src/docs/technical_details.txt
diff --git a/third_party/afl/src/docs/technical_details.txt b/third_party/afl/src/docs/technical_details.txt
index 3ec487414e7d87698cb1933d6b9023186fc58256..af6131c1057507c094b78fb3db268a318824dbab 100644
--- a/third_party/afl/src/docs/technical_details.txt
+++ b/third_party/afl/src/docs/technical_details.txt
@@ -279,7 +279,38 @@ 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. The
+operation of afl-tmin is as follows.
+
+First, the tool automatically selects the operating mode. If the initial input
+crashes the target binary, afl-tmin will run in non-instrumented mode, simply
+keeping any tweaks that produce a simpler file but still crash the target. If
+the target is non-crashing, the tool uses an instrumented mode and keeps only
+the tweaks that produce exactly the same execution path.
+
+The actual minimization algorithm is:
+
+ 1) Attempt to zero large blocks of data with large stepovers. Empirically,
+ this is shown to reduce the number of execs by preempting finer-grained
+ efforts later on.
+
+ 2) Perform a block deletion pass with decreasing block sizes and stepovers,
+ binary-search-style.
+
+ 3) Perform alphabet normalization by counting unique characters and trying
+ to bulk-replace each with a zero value.
+
+ 4) As a last result, perform byte-by-byte normalization on non-zero bytes.
+
+Instead of zeroing with a 0x00 byte, afl-tmin uses the ASCII digit '0'. This
+is done because such a modification is much less likely to interfere with
+text parsing, so it is more likely to result in successful minimization of
+text files.
+
+The algorithm used here is less involved than some other test case
+minimization approaches proposed in academic work, but requires far fewer
+executions and tends to produce comparable results in most real-world
+applications.
6) Fuzzing strategies
---------------------
« no previous file with comments | « third_party/afl/src/docs/sister_projects.txt ('k') | third_party/afl/src/docs/vuln_samples/bash-cmd-exec.var » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698