[libFuzzer] suggest a dictionary to the user of some of the trace-based dictionary entries were successful

llvm-svn: 257736

9 files changed, 103 insertions, 23 deletions

diff --git a/llvm/lib/Fuzzer/FuzzerInterface.h b/llvm/lib/Fuzzer/FuzzerInterface.h
index e22b27a3dd2..e5a8c86e3ea 100644
--- a/llvm/lib/Fuzzer/FuzzerInterface.h
+++ b/llvm/lib/Fuzzer/FuzzerInterface.h
@@ -76,6 +76,8 @@ class MutationDispatcher {
   void StartMutationSequence();
   /// Print the current sequence of mutations.
   void PrintMutationSequence();
+  /// Indicate that the current sequence of mutations was successfull.
+  void RecordSuccessfulMutationSequence();
   /// Mutates data by shuffling bytes.
   size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize);
   /// Mutates data by erasing a byte.
@@ -91,9 +93,13 @@ class MutationDispatcher {
   size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size,
                                             size_t MaxSize);
 
-  /// Mutates data by adding a word from the automatic dictionary.
-  size_t Mutate_AddWordFromAutoDictionary(uint8_t *Data, size_t Size,
-                                          size_t MaxSize);
+  /// Mutates data by adding a word from the temporary automatic dictionary.
+  size_t Mutate_AddWordFromTemporaryAutoDictionary(uint8_t *Data, size_t Size,
+                                                   size_t MaxSize);
+
+  /// Mutates data by adding a word from the persistent automatic dictionary.
+  size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size,
+                                                    size_t MaxSize);
 
   /// Tries to find an ASCII integer in Data, changes it to another ASCII int.
   size_t Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, size_t MaxSize);
@@ -113,6 +119,7 @@ class MutationDispatcher {
 
   void AddWordToAutoDictionary(const Unit &Word, size_t PositionHint);
   void ClearAutoDictionary();
+  void PrintRecommendedDictionary();
 
   void SetCorpus(const std::vector<Unit> *Corpus);
 
@@ -157,8 +164,6 @@ class UserSuppliedFuzzer {
   UserSuppliedFuzzer(FuzzerRandomBase *Rand);
   /// Executes the target function on 'Size' bytes of 'Data'.
   virtual int TargetFunction(const uint8_t *Data, size_t Size) = 0;
-  virtual void StartMutationSequence() { MD.StartMutationSequence(); }
-  virtual void PrintMutationSequence() { MD.PrintMutationSequence(); }
   virtual void SetCorpus(const std::vector<Unit> *Corpus) {
     MD.SetCorpus(Corpus);
   }
diff --git a/llvm/lib/Fuzzer/FuzzerLoop.cpp b/llvm/lib/Fuzzer/FuzzerLoop.cpp
index 7d9f397e45e..9b64e36dbf6 100644
--- a/llvm/lib/Fuzzer/FuzzerLoop.cpp
+++ b/llvm/lib/Fuzzer/FuzzerLoop.cpp
@@ -340,7 +340,7 @@ void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
   PrintStats("NEW   ", "");
   if (Options.Verbosity) {
     Printf(" L: %zd ", U.size());
-    USF.PrintMutationSequence();
+    USF.GetMD().PrintMutationSequence();
     Printf("\n");
   }
 }
@@ -348,6 +348,7 @@ void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
 void Fuzzer::ReportNewCoverage(const Unit &U) {
   Corpus.push_back(U);
   UnitHashesAddedToCorpus.insert(Hash(U));
+  USF.GetMD().RecordSuccessfulMutationSequence();
   PrintStatusForNewUnit(U);
   WriteToOutputCorpus(U);
   if (Options.ExitOnFirst)
@@ -387,7 +388,7 @@ void Fuzzer::Merge(const std::vector<std::string> &Corpora) {
 }
 
 void Fuzzer::MutateAndTestOne() {
-  USF.StartMutationSequence();
+  USF.GetMD().StartMutationSequence();
 
   auto U = ChooseUnitToMutate();
 
@@ -496,6 +497,7 @@ void Fuzzer::Loop() {
   }
 
   PrintStats("DONE  ", "\n");
+  USF.GetMD().PrintRecommendedDictionary();
 }
 
 void Fuzzer::SyncCorpus() {
diff --git a/llvm/lib/Fuzzer/FuzzerMutate.cpp b/llvm/lib/Fuzzer/FuzzerMutate.cpp
index 30e5b43c083..4ea8265dfb8 100644
--- a/llvm/lib/Fuzzer/FuzzerMutate.cpp
+++ b/llvm/lib/Fuzzer/FuzzerMutate.cpp
@@ -27,12 +27,28 @@ struct DictionaryEntry {
   size_t PositionHint;
 };
 
+struct Dictionary : public std::vector<DictionaryEntry>{
+  bool ContainsWord(const Unit &W) const {
+    return end() !=
+           std::find_if(begin(), end(), [&](const DictionaryEntry &DE) {
+             return DE.Word == W;
+           });
+  }
+};
+
 struct MutationDispatcher::Impl {
-  std::vector<DictionaryEntry> ManualDictionary;
-  std::vector<DictionaryEntry> AutoDictionary;
+  // Dictionary provided by the user via -dict=DICT_FILE.
+  Dictionary ManualDictionary;
+  // Temporary dictionary modified by the fuzzer itself,
+  // recreated periodically.
+  Dictionary TempAutoDictionary;
+  // Persistent dictionary modified by the fuzzer, consists of
+  // entries that led to successfull discoveries in the past mutations.
+  Dictionary PersistentAutoDictionary;
+
   std::vector<Mutator> Mutators;
   std::vector<Mutator> CurrentMutatorSequence;
-  std::vector<DictionaryEntry> CurrentDictionaryEntrySequence;
+  Dictionary CurrentDictionaryEntrySequence;
   const std::vector<Unit> *Corpus = nullptr;
   FuzzerRandomBase &Rand;
 
@@ -47,8 +63,10 @@ struct MutationDispatcher::Impl {
     Add({&MutationDispatcher::Mutate_CrossOver, "CrossOver"});
     Add({&MutationDispatcher::Mutate_AddWordFromManualDictionary,
          "AddFromManualDict"});
-    Add({&MutationDispatcher::Mutate_AddWordFromAutoDictionary,
-         "AddFromAutoDict"});
+    Add({&MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary,
+         "AddFromTempAutoDict"});
+    Add({&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
+         "AddFromPersAutoDict"});
   }
   void SetCorpus(const std::vector<Unit> *Corpus) { this->Corpus = Corpus; }
   size_t AddWordFromDictionary(const std::vector<DictionaryEntry> &D,
@@ -126,10 +144,15 @@ size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
                                        MaxSize);
 }
 
-size_t MutationDispatcher::Mutate_AddWordFromAutoDictionary(uint8_t *Data,
-                                                            size_t Size,
-                                                            size_t MaxSize) {
-  return MDImpl->AddWordFromDictionary(MDImpl->AutoDictionary, Data, Size,
+size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary(
+    uint8_t *Data, size_t Size, size_t MaxSize) {
+  return MDImpl->AddWordFromDictionary(MDImpl->TempAutoDictionary, Data, Size,
+                                       MaxSize);
+}
+
+size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
+    uint8_t *Data, size_t Size, size_t MaxSize) {
+  return MDImpl->AddWordFromDictionary(MDImpl->PersistentAutoDictionary, Data, Size,
                                        MaxSize);
 }
 
@@ -211,13 +234,36 @@ void MutationDispatcher::StartMutationSequence() {
   MDImpl->CurrentDictionaryEntrySequence.clear();
 }
 
+// Copy successful dictionary entries to PersistentAutoDictionary.
+void MutationDispatcher::RecordSuccessfulMutationSequence() {
+  for (auto &DE : MDImpl->CurrentDictionaryEntrySequence)
+    // Linear search is fine here as this happens seldom.
+    if (!MDImpl->PersistentAutoDictionary.ContainsWord(DE.Word))
+      MDImpl->PersistentAutoDictionary.push_back(
+          {DE.Word, std::numeric_limits<size_t>::max()});
+}
+
+void MutationDispatcher::PrintRecommendedDictionary() {
+  std::vector<Unit> V;
+  for (auto &DE : MDImpl->PersistentAutoDictionary)
+    if (!MDImpl->ManualDictionary.ContainsWord(DE.Word))
+      V.push_back(DE.Word);
+  if (V.empty()) return;
+  Printf("###### Recommended dictionary. ######\n");
+  for (auto &U: V) {
+    Printf("\"");
+    PrintASCII(U, "\"\n");
+  }
+  Printf("###### End of recommended dictionary. ######\n");
+}
+
 void MutationDispatcher::PrintMutationSequence() {
   Printf("MS: %zd ", MDImpl->CurrentMutatorSequence.size());
   for (auto M : MDImpl->CurrentMutatorSequence)
     Printf("%s-", M.Name);
   if (!MDImpl->CurrentDictionaryEntrySequence.empty()) {
     Printf(" DE: ");
-    for (auto DE : MDImpl->CurrentDictionaryEntrySequence) {
+    for (auto &DE : MDImpl->CurrentDictionaryEntrySequence) {
       Printf("\"");
       PrintASCII(DE.Word, "\"-");
     }
@@ -261,12 +307,12 @@ void MutationDispatcher::AddWordToManualDictionary(const Unit &Word) {
 void MutationDispatcher::AddWordToAutoDictionary(const Unit &Word,
                                                  size_t PositionHint) {
   static const size_t kMaxAutoDictSize = 1 << 14;
-  if (MDImpl->AutoDictionary.size() >= kMaxAutoDictSize) return;
-  MDImpl->AutoDictionary.push_back({Word, PositionHint});
+  if (MDImpl->TempAutoDictionary.size() >= kMaxAutoDictSize) return;
+  MDImpl->TempAutoDictionary.push_back({Word, PositionHint});
 }
 
 void MutationDispatcher::ClearAutoDictionary() {
-  MDImpl->AutoDictionary.clear();
+  MDImpl->TempAutoDictionary.clear();
 }
 
 MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {
diff --git a/llvm/lib/Fuzzer/test/CMakeLists.txt b/llvm/lib/Fuzzer/test/CMakeLists.txt
index 2d526bdaa0b..91a61f43375 100644
--- a/llvm/lib/Fuzzer/test/CMakeLists.txt
+++ b/llvm/lib/Fuzzer/test/CMakeLists.txt
@@ -20,6 +20,7 @@ set(Tests
   FullCoverageSetTest
   MemcmpTest
   NullDerefTest
+  RepeatedMemcmp
   SimpleCmpTest
   SimpleDictionaryTest
   SimpleHashTest
diff --git a/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp b/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
index b33e0c96145..b09f232bd0d 100644
--- a/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
+++ b/llvm/lib/Fuzzer/test/FuzzerUnittest.cpp
@@ -302,7 +302,7 @@ void TestAddWordFromDictionaryWithHint(Mutator M, int NumIter) {
 
 TEST(FuzzerMutate, AddWordFromDictionaryWithHint1) {
   TestAddWordFromDictionaryWithHint(
-      &MutationDispatcher::Mutate_AddWordFromAutoDictionary, 1 << 5);
+      &MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary, 1 << 5);
 }
 
 TEST(FuzzerMutate, AddWordFromDictionaryWithHint2) {
diff --git a/llvm/lib/Fuzzer/test/MemcmpTest.cpp b/llvm/lib/Fuzzer/test/MemcmpTest.cpp
index c19c95717bb..c72f2c2cb51 100644
--- a/llvm/lib/Fuzzer/test/MemcmpTest.cpp
+++ b/llvm/lib/Fuzzer/test/MemcmpTest.cpp
@@ -9,7 +9,7 @@ extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
   if (Size >= 8 && memcmp(Data, "01234567", 8) == 0) {
     if (Size >= 12 && memcmp(Data + 8, "ABCD", 4) == 0) {
       if (Size >= 14 && memcmp(Data + 12, "XY", 2) == 0) {
-        if (Size >= 16 && memcmp(Data + 14, "KLM", 3) == 0) {
+        if (Size >= 17 && memcmp(Data + 14, "KLM", 3) == 0) {
           if (Size >= 27 && memcmp(Data + 17, "ABCDE-GHIJ", 10) == 0){
             fprintf(stderr, "BINGO %zd\n", Size);
             for (size_t i = 0; i < Size; i++) {
diff --git a/llvm/lib/Fuzzer/test/RepeatedMemcmp.cpp b/llvm/lib/Fuzzer/test/RepeatedMemcmp.cpp
new file mode 100644
index 00000000000..cb5e130003b
--- /dev/null
+++ b/llvm/lib/Fuzzer/test/RepeatedMemcmp.cpp
@@ -0,0 +1,19 @@
+
+#include <cstring>
+#include <cstdint>
+#include <cstdio>
+#include <cstdlib>
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  int Matches = 0;
+  for (size_t i = 0; i + 2 < Size; i += 3) {
+    const char *Pat = i % 2 ? "foo" : "bar";
+    if (!memcmp(Data + i, Pat, 3))
+      Matches++;
+  }
+  if (Matches > 20) {
+    fprintf(stderr, "BINGO!\n");
+    exit(1);
+  }
+  return 0;
+}
diff --git a/llvm/lib/Fuzzer/test/fuzzer-dfsan.test b/llvm/lib/Fuzzer/test/fuzzer-dfsan.test
index 567086ed65a..b7c887b8b92 100644
--- a/llvm/lib/Fuzzer/test/fuzzer-dfsan.test
+++ b/llvm/lib/Fuzzer/test/fuzzer-dfsan.test
@@ -10,7 +10,7 @@ CHECK_DFSanMemcmpCallback: DFSanMemcmpCallback: Pos
 RUN: not LLVMFuzzer-SimpleCmpTest-DFSan -use_traces=1 -seed=1 -runs=1000000 -timeout=5 2>&1 | FileCheck %s --check-prefix=CHECK1
 RUN: LLVMFuzzer-SimpleCmpTest-DFSan -use_traces=1 -seed=1 -runs=100 -timeout=5 -verbosity=3 2>&1 | FileCheck %s  -check-prefix=CHECK_DFSanCmpCallback
 
-RUN: not LLVMFuzzer-MemcmpTest-DFSan -use_traces=1 -seed=1 -runs=10000 -timeout=5 2>&1 | FileCheck %s --check-prefix=CHECK2
+RUN: not LLVMFuzzer-MemcmpTest-DFSan -use_traces=1 -seed=1 -runs=100000 -timeout=5 2>&1 | FileCheck %s --check-prefix=CHECK2
 RUN: LLVMFuzzer-MemcmpTest-DFSan -use_traces=1 -seed=1 -runs=2 -timeout=5 -verbosity=3 2>&1 | FileCheck %s  -check-prefix=CHECK_DFSanMemcmpCallback
 
 RUN: not LLVMFuzzer-StrncmpTest-DFSan -use_traces=1 -seed=1 -runs=10000 -timeout=5 2>&1 | FileCheck %s --check-prefix=CHECK3
diff --git a/llvm/lib/Fuzzer/test/fuzzer-traces.test b/llvm/lib/Fuzzer/test/fuzzer-traces.test
index 3b8639b8e94..12d4e9b5e45 100644
--- a/llvm/lib/Fuzzer/test/fuzzer-traces.test
+++ b/llvm/lib/Fuzzer/test/fuzzer-traces.test
@@ -18,3 +18,10 @@ RUN:     LLVMFuzzer-SwitchTest               -seed=1 -runs=1000000  2>&1 | FileC
 
 RUN: not LLVMFuzzer-SimpleHashTest -use_traces=1 -seed=1 -runs=10000000  2>&1 | FileCheck %s
 RUN:     LLVMFuzzer-SimpleHashTest               -seed=1 -runs=10000000 2>&1 | FileCheck %s --check-prefix=Done10000000
+
+RUN: LLVMFuzzer-RepeatedMemcmp -use_traces=1 -seed=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT
+RECOMMENDED_DICT:###### Recommended dictionary. ######
+RECOMMENDED_DICT-DAG: "foo"
+RECOMMENDED_DICT-DAG: "bar"
+RECOMMENDED_DICT:###### End of recommended dictionary. ######
+