[sanitizer/coverage] Add AFL-style coverage counters (search heuristic for fuzzing).

Introduce -mllvm -sanitizer-coverage-8bit-counters=1
which adds imprecise thread-unfriendly 8-bit coverage counters.

The run-time library maps these 8-bit counters to 8-bit bitsets in the same way
AFL (http://lcamtuf.coredump.cx/afl/technical_details.txt) does:
counter values are divided into 8 ranges and based on the counter
value one of the bits in the bitset is set.
The AFL ranges are used here: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+.

These counters provide a search heuristic for single-threaded
coverage-guided fuzzers, we do not expect them to be useful for other purposes.

Depending on the value of -fsanitize-coverage=[123] flag,
these counters will be added to the function entry blocks (=1),
every basic block (=2), or every edge (=3).

Use these counters as an optional search heuristic in the Fuzzer library.
Add a test where this heuristic is critical.

llvm-svn: 231166

1 files changed, 13 insertions, 1 deletions

diff --git a/llvm/lib/Fuzzer/FuzzerLoop.cpp b/llvm/lib/Fuzzer/FuzzerLoop.cpp
index 70b63eb618a..563fbf4c30d 100644
--- a/llvm/lib/Fuzzer/FuzzerLoop.cpp
+++ b/llvm/lib/Fuzzer/FuzzerLoop.cpp
@@ -138,17 +138,28 @@ size_t Fuzzer::RunOneMaximizeFullCoverageSet(const Unit &U) {
 }
 
 size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) {
+  size_t NumCounters = __sanitizer_get_number_of_counters();
+  if (Options.UseCounters) {
+    CounterBitmap.resize(NumCounters);
+    __sanitizer_update_counter_bitset_and_clear_counters(0);
+  }
   size_t OldCoverage = __sanitizer_get_total_unique_coverage();
   Callback(U.data(), U.size());
   size_t NewCoverage = __sanitizer_get_total_unique_coverage();
+  size_t NumNewBits = 0;
+  if (Options.UseCounters)
+    NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters(
+        CounterBitmap.data());
+
   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) {
     size_t Seconds = secondsSinceProcessStartUp();
     std::cerr
         << "#" << TotalNumberOfRuns
         << "\tcov: " << NewCoverage
+        << "\tbits: " << TotalBits()
         << "\texec/s: " << (Seconds ? TotalNumberOfRuns / Seconds : 0) << "\n";
   }
-  if (NewCoverage > OldCoverage)
+  if (NewCoverage > OldCoverage || NumNewBits)
     return NewCoverage;
   return 0;
 }
@@ -189,6 +200,7 @@ size_t Fuzzer::MutateAndTestOne(Unit *U) {
       if (Options.Verbosity) {
         std::cerr << "#" << TotalNumberOfRuns
                   << "\tNEW: " << NewCoverage
+                  << " B: " << TotalBits()
                   << " L: " << U->size()
                   << " S: " << Corpus.size()
                   << " I: " << i