[libFuzzer] experimental flag -drill (another search heuristic; Mike Aizatsky's idea)

[oota-llvm.git] / lib / Fuzzer / FuzzerLoop.cpp

diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp
index e206fcc9796b3531636ad7a8fc94e3c71160878c..d3c32626a3bb3c0bb4672912570bd7b3bce87411 100644 (file)
--- a/lib/Fuzzer/FuzzerLoop.cpp
+++ b/lib/Fuzzer/FuzzerLoop.cpp
@@ -18,6 +18,7 @@ extern "C" {
 // libFuzzer can be linked w/o the sanitizers and sanitizer-coveragte
 // (in which case it will complain at start-up time).
 __attribute__((weak)) void __sanitizer_print_stack_trace();
+__attribute__((weak)) void __sanitizer_reset_coverage();
 __attribute__((weak)) size_t __sanitizer_get_total_unique_caller_callee_pairs();
 __attribute__((weak)) size_t __sanitizer_get_total_unique_coverage();
 __attribute__((weak))
@@ -293,9 +294,9 @@ void Fuzzer::SaveCorpus() {
            Options.OutputCorpus.c_str());
 }
 
-void Fuzzer::ReportNewCoverage(const Unit &U) {
-  Corpus.push_back(U);
-  UnitHashesAddedToCorpus.insert(Hash(U));
+void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
+  if (!Options.PrintNEW)
+    return;
   PrintStats("NEW   ", "");
   if (Options.Verbosity) {
     Printf(" L: %zd", U.size());
@@ -306,6 +307,12 @@ void Fuzzer::ReportNewCoverage(const Unit &U) {
     }
     Printf("\n");
   }
+}
+
+void Fuzzer::ReportNewCoverage(const Unit &U) {
+  Corpus.push_back(U);
+  UnitHashesAddedToCorpus.insert(Hash(U));
+  PrintStatusForNewUnit(U);
   WriteToOutputCorpus(U);
   if (Options.ExitOnFirst)
     exit(0);
@@ -374,7 +381,7 @@ void Fuzzer::MutateAndTestOne(Unit *U) {
 // Returns an index of random unit from the corpus to mutate.
 // Hypothesis: units added to the corpus last are more likely to be interesting.
 // This function gives more wieght to the more recent units.
-size_t Fuzzer::ChooseUnitToMutate() {
+size_t Fuzzer::ChooseUnitIdxToMutate() {
     size_t N = Corpus.size();
     size_t Total = (N + 1) * N / 2;
     size_t R = USF.GetRand()(Total);
@@ -391,12 +398,57 @@ size_t Fuzzer::ChooseUnitToMutate() {
     return IdxBeg;
 }
 
-void Fuzzer::Loop() {
-  for (auto &U: Options.Dictionary)
-    USF.GetMD().AddWordToDictionary(U.data(), U.size());
+// Experimental search heuristic: drilling.
+// - Read, shuffle, execute and minimize the corpus.
+// - Choose one random unit.
+// - Reset the coverage.
+// - Start fuzzing as if the chosen unit was the only element of the corpus.
+// - When done, reset the coverage again.
+// - Merge the newly created corpus into the original one.
+void Fuzzer::Drill() {
+  // The corpus is already read, shuffled, and minimized.
+  assert(!Corpus.empty());
+  Options.PrintNEW = false;  // Don't print NEW status lines when drilling.
+
+  Unit U = ChooseUnitToMutate();
+
+  CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage);
+  __sanitizer_reset_coverage();
+
+  std::vector<Unit> SavedCorpus;
+  SavedCorpus.swap(Corpus);
+  Corpus.push_back(U);
+  assert(Corpus.size() == 1);
+  RunOne(U);
+  PrintStats("DRILL ");
+  std::string SavedOutputCorpusPath; // Don't write new units while drilling.
+  SavedOutputCorpusPath.swap(Options.OutputCorpus);
+  Loop();
+
+  __sanitizer_reset_coverage();
+
+  PrintStats("REINIT");
+  SavedOutputCorpusPath.swap(Options.OutputCorpus);
+  for (auto &U : SavedCorpus)
+    RunOne(U);
+  PrintStats("MERGE ");
+  Options.PrintNEW = true;
+  size_t NumMerged = 0;
+  for (auto &U : Corpus) {
+    if (RunOne(U)) {
+      PrintStatusForNewUnit(U);
+      NumMerged++;
+      WriteToOutputCorpus(U);
+    }
+  }
+  PrintStats("MERGED");
+  if (NumMerged && Options.Verbosity)
+    Printf("Drilling discovered %zd new units\n", NumMerged);
+}
 
+void Fuzzer::Loop() {
   while (true) {
-    size_t J1 = ChooseUnitToMutate();;
+    size_t J1 = ChooseUnitIdxToMutate();;
     SyncCorpus();
     RereadOutputCorpus();
     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
@@ -408,7 +460,7 @@ void Fuzzer::Loop() {
     CurrentUnit = Corpus[J1];
     // Optionally, cross with another unit.
     if (Options.DoCrossOver && USF.GetRand().RandBool()) {
-      size_t J2 = ChooseUnitToMutate();
+      size_t J2 = ChooseUnitIdxToMutate();
       if (!Corpus[J1].empty() && !Corpus[J2].empty()) {
         assert(!Corpus[J2].empty());
         CurrentUnit.resize(Options.MaxLen);