[libFuzzer] Mutation tracking and logging implemented

Code now exists to track number of mutations that are used in fuzzing in
total and ones that produce new coverage. The stats are currently being
dumped to the command line.

Patch By: Kode Williams

Differntial Revision: https://reviews.llvm.org/D48054

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@336597 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 61 insertions, 22 deletions

diff --git a/lib/fuzzer/FuzzerDriver.cpp b/lib/fuzzer/FuzzerDriver.cpp
index c2f8583b7..6c785ebca 100644
--- a/lib/fuzzer/FuzzerDriver.cpp
+++ b/lib/fuzzer/FuzzerDriver.cpp
@@ -613,6 +613,7 @@ int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
   Options.PrintNewCovPcs = Flags.print_pcs;
   Options.PrintNewCovFuncs = Flags.print_funcs;
   Options.PrintFinalStats = Flags.print_final_stats;
+  Options.PrintMutationStats = Flags.print_mutation_stats;
   Options.PrintCorpusStats = Flags.print_corpus_stats;
   Options.PrintCoverage = Flags.print_coverage;
   Options.DumpCoverage = Flags.dump_coverage;
diff --git a/lib/fuzzer/FuzzerFlags.def b/lib/fuzzer/FuzzerFlags.def
index aaa172716..b77a1ffe1 100644
--- a/lib/fuzzer/FuzzerFlags.def
+++ b/lib/fuzzer/FuzzerFlags.def
@@ -153,3 +153,4 @@ FUZZER_DEPRECATED_FLAG(use_equivalence_server)
 FUZZER_FLAG_INT(analyze_dict, 0, "Experimental")
 FUZZER_DEPRECATED_FLAG(use_clang_coverage)
 FUZZER_FLAG_STRING(data_flow_trace, "Experimental: use the data flow trace")
+FUZZER_FLAG_INT(print_mutation_stats, 0, "Experimental")
diff --git a/lib/fuzzer/FuzzerLoop.cpp b/lib/fuzzer/FuzzerLoop.cpp
index d412b584d..1a2276fd1 100644
--- a/lib/fuzzer/FuzzerLoop.cpp
+++ b/lib/fuzzer/FuzzerLoop.cpp
@@ -355,6 +355,8 @@ void Fuzzer::PrintFinalStats() {
     TPC.DumpCoverage();
   if (Options.PrintCorpusStats)
     Corpus.PrintStats();
+  if (Options.PrintMutationStats)
+    MD.PrintMutationStats();
   if (!Options.PrintFinalStats)
     return;
   size_t ExecPerSec = execPerSec();
diff --git a/lib/fuzzer/FuzzerMutate.cpp b/lib/fuzzer/FuzzerMutate.cpp
index 865e598fd..ef059fc22 100644
--- a/lib/fuzzer/FuzzerMutate.cpp
+++ b/lib/fuzzer/FuzzerMutate.cpp
@@ -58,6 +58,10 @@ MutationDispatcher::MutationDispatcher(Random &Rand,
   if (EF->LLVMFuzzerCustomCrossOver)
     Mutators.push_back(
         {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
+
+  // Initialize mutation statistic counters.
+  TotalMutations.resize(Mutators.size(), 0);
+  UsefulMutations.resize(Mutators.size(), 0);
 }
 
 static char RandCh(Random &Rand) {
@@ -261,9 +265,9 @@ size_t MutationDispatcher::Mutate_AddWordFromTORC(
     DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
   } break;
   case 3: if (Options.UseMemmem) {
-    auto X = TPC.MMT.Get(Rand.Rand());
-    DE = DictionaryEntry(X);
-  } break;
+      auto X = TPC.MMT.Get(Rand.Rand());
+      DE = DictionaryEntry(X);
+    } break;
   default:
     assert(0);
   }
@@ -431,18 +435,18 @@ size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
   auto &U = MutateInPlaceHere;
   size_t NewSize = 0;
   switch(Rand(3)) {
-    case 0:
-      NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size());
-      break;
-    case 1:
-      NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize);
-      if (!NewSize)
-        NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size());
-      break;
-    case 2:
+  case 0:
+    NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size());
+    break;
+  case 1:
+    NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize);
+    if (!NewSize)
       NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size());
-      break;
-    default: assert(0);
+    break;
+  case 2:
+    NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size());
+    break;
+  default: assert(0);
   }
   assert(NewSize > 0 && "CrossOver returned empty unit");
   assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
@@ -451,7 +455,7 @@ size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
 }
 
 void MutationDispatcher::StartMutationSequence() {
-  CurrentMutatorSequence.clear();
+  CurrentMutatorIdxSequence.clear();
   CurrentDictionaryEntrySequence.clear();
 }
 
@@ -465,6 +469,7 @@ void MutationDispatcher::RecordSuccessfulMutationSequence() {
     if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
       PersistentAutoDictionary.push_back({DE->GetW(), 1});
   }
+  RecordUsefulMutations();
 }
 
 void MutationDispatcher::PrintRecommendedDictionary() {
@@ -484,9 +489,9 @@ void MutationDispatcher::PrintRecommendedDictionary() {
 }
 
 void MutationDispatcher::PrintMutationSequence() {
-  Printf("MS: %zd ", CurrentMutatorSequence.size());
-  for (auto M : CurrentMutatorSequence)
-    Printf("%s-", M.Name);
+  Printf("MS: %zd ", CurrentMutatorIdxSequence.size());
+  for (auto M : CurrentMutatorIdxSequence)
+    Printf("%s-", Mutators[M].Name);
   if (!CurrentDictionaryEntrySequence.empty()) {
     Printf(" DE: ");
     for (auto DE : CurrentDictionaryEntrySequence) {
@@ -514,12 +519,14 @@ size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
   // in which case they will return 0.
   // Try several times before returning un-mutated data.
   for (int Iter = 0; Iter < 100; Iter++) {
-    auto M = Mutators[Rand(Mutators.size())];
+    size_t MutatorIdx = Rand(Mutators.size());
+    auto M = Mutators[MutatorIdx];
     size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
     if (NewSize && NewSize <= MaxSize) {
       if (Options.OnlyASCII)
         ToASCII(Data, NewSize);
-      CurrentMutatorSequence.push_back(M);
+      CurrentMutatorIdxSequence.push_back(MutatorIdx);
+      TotalMutations[MutatorIdx]++;
       return NewSize;
     }
   }
@@ -532,4 +539,23 @@ void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
       {W, std::numeric_limits<size_t>::max()});
 }
 
+void MutationDispatcher::RecordUsefulMutations() {
+  for (const size_t M : CurrentMutatorIdxSequence)
+    UsefulMutations[M]++;
+}
+
+void MutationDispatcher::PrintMutationStats() {
+  Printf("\nstat::mutation_usefulness:      ");
+  for (size_t i = 0; i < Mutators.size(); i++) {
+    double UsefulPercentage =
+        TotalMutations[i]
+            ? (100.0 * UsefulMutations[i]) / TotalMutations[i]
+            : 0;
+    Printf("%.3f", UsefulPercentage);
+    if (i < Mutators.size() - 1)
+      Printf(",");
+  }
+  Printf("\n");
+}
+
 }  // namespace fuzzer
diff --git a/lib/fuzzer/FuzzerMutate.h b/lib/fuzzer/FuzzerMutate.h
index 996d756cd..32165227c 100644
--- a/lib/fuzzer/FuzzerMutate.h
+++ b/lib/fuzzer/FuzzerMutate.h
@@ -86,8 +86,11 @@ public:
 
   Random &GetRand() { return Rand; }
 
-private:
+  void PrintMutationStats();
+
+  void RecordUsefulMutations();
 
+private:
   struct Mutator {
     size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
     const char *Name;
@@ -128,8 +131,8 @@ private:
   // entries that led to successful discoveries in the past mutations.
   Dictionary PersistentAutoDictionary;
 
-  Vector<Mutator> CurrentMutatorSequence;
   Vector<DictionaryEntry *> CurrentDictionaryEntrySequence;
+  Vector<size_t> CurrentMutatorIdxSequence;
 
   static const size_t kCmpDictionaryEntriesDequeSize = 16;
   DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize];
@@ -143,6 +146,11 @@ private:
 
   Vector<Mutator> Mutators;
   Vector<Mutator> DefaultMutators;
+
+  // A total count of each mutation used in the fuzzing process.
+  Vector<uint64_t> TotalMutations;
+  // The number of each mutation that resulted in new coverage.
+  Vector<uint64_t> UsefulMutations;
 };
 
 }  // namespace fuzzer
diff --git a/lib/fuzzer/FuzzerOptions.h b/lib/fuzzer/FuzzerOptions.h
index ab90df82a..019dc6fca 100644
--- a/lib/fuzzer/FuzzerOptions.h
+++ b/lib/fuzzer/FuzzerOptions.h
@@ -52,6 +52,7 @@ struct FuzzingOptions {
   bool PrintNewCovPcs = false;
   int PrintNewCovFuncs = 0;
   bool PrintFinalStats = false;
+  bool PrintMutationStats = false;
   bool PrintCorpusStats = false;
   bool PrintCoverage = false;
   bool DumpCoverage = false;