[libFuzzer] improve -reduce_inputs=1: now only consider the unique features of very input (seems to work much better)

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

4 files changed, 23 insertions, 26 deletions

diff --git a/lib/Fuzzer/FuzzerCorpus.h b/lib/Fuzzer/FuzzerCorpus.h
index 2567fe4d135..5d2a47d2fe7 100644
--- a/lib/Fuzzer/FuzzerCorpus.h
+++ b/lib/Fuzzer/FuzzerCorpus.h
@@ -34,7 +34,7 @@ struct InputInfo {
   size_t NumExecutedMutations = 0;
   size_t NumSuccessfullMutations = 0;
   bool MayDeleteFile = false;
-  std::vector<uint32_t> FeatureSet;
+  std::vector<uint32_t> UniqFeatureSet;
 };
 
 class InputCorpus {
@@ -79,7 +79,8 @@ class InputCorpus {
     II.U = U;
     II.NumFeatures = NumFeatures;
     II.MayDeleteFile = MayDeleteFile;
-    II.FeatureSet = FeatureSet;
+    II.UniqFeatureSet = FeatureSet;
+    std::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());
     ComputeSHA1(U.data(), U.size(), II.Sha1);
     Hashes.insert(Sha1ToString(II.Sha1));
     UpdateCorpusDistribution();
@@ -117,27 +118,13 @@ class InputCorpus {
         Printf("%s sz=%zd ", Sha1ToString(II->Sha1).c_str(), II->U.size());
         PrintUnit(II->U);
         Printf(" ");
-        PrintFeatureSet(II->FeatureSet);
+        PrintFeatureSet(II->UniqFeatureSet);
         Printf("\n");
       }
       i++;
     }
   }
 
-  // If FeatureSet is that same as in II, replace II->U with {Data,Size}.
-  bool TryToReplace(InputInfo *II, const uint8_t *Data, size_t Size,
-                    const std::vector<uint32_t> &FeatureSet) {
-    if (II->U.size() > Size && II->FeatureSet.size() &&
-        II->FeatureSet == FeatureSet) {
-      if (FeatureDebug)
-        Printf("Replace: %zd => %zd\n", II->U.size(), Size);
-      Replace(II, {Data, Data + Size});
-      PrintCorpus();
-      return true;
-    }
-    return false;
-  }
-
   void Replace(InputInfo *II, const Unit &U) {
     assert(II->U.size());
     Hashes.erase(Sha1ToString(II->Sha1));
@@ -198,7 +185,7 @@ class InputCorpus {
       Printf("EVICTED %zd\n", Idx);
   }
 
-  void AddFeature(size_t Idx, uint32_t NewSize, bool Shrink) {
+  bool AddFeature(size_t Idx, uint32_t NewSize, bool Shrink) {
     assert(NewSize);
     Idx = Idx % kFeatureSetSize;
     uint32_t OldSize = GetFeature(Idx);
@@ -218,7 +205,9 @@ class InputCorpus {
         Printf("ADD FEATURE %zd sz %d\n", Idx, NewSize);
       SmallestElementPerFeature[Idx] = Inputs.size();
       InputSizesPerFeature[Idx] = NewSize;
+      return true;
     }
+    return false;
   }
 
   size_t NumFeatures() const { return NumAddedFeatures; }
diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h
index 549ebc0a3c3..8993f2cdaf0 100644
--- a/lib/Fuzzer/FuzzerInternal.h
+++ b/lib/Fuzzer/FuzzerInternal.h
@@ -132,7 +132,7 @@ private:
   size_t MaxInputLen = 0;
   size_t MaxMutationLen = 0;
 
-  std::vector<uint32_t> FeatureSetTmp;
+  std::vector<uint32_t> UniqFeatureSetTmp;
 
   // Need to know our own thread.
   static thread_local bool IsMyThread;
diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp
index 1693cd078a9..046816c5d77 100644
--- a/lib/Fuzzer/FuzzerLoop.cpp
+++ b/lib/Fuzzer/FuzzerLoop.cpp
@@ -402,22 +402,29 @@ bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
 
   ExecuteCallback(Data, Size);
 
-  FeatureSetTmp.clear();
+  UniqFeatureSetTmp.clear();
+  size_t FoundUniqFeaturesOfII = 0;
   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
   TPC.CollectFeatures([&](size_t Feature) {
-    Corpus.AddFeature(Feature, Size, Options.Shrink);
-    if (Options.ReduceInputs)
-      FeatureSetTmp.push_back(Feature);
+    if (Corpus.AddFeature(Feature, Size, Options.Shrink))
+      UniqFeatureSetTmp.push_back(Feature);
+    if (Options.ReduceInputs && II)
+      if (std::binary_search(II->UniqFeatureSet.begin(),
+                             II->UniqFeatureSet.end(), Feature))
+        FoundUniqFeaturesOfII++;
   });
   PrintPulseAndReportSlowInput(Data, Size);
   size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
   if (NumNewFeatures) {
     Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile,
-                       FeatureSetTmp);
+                       UniqFeatureSetTmp);
     CheckExitOnSrcPosOrItem();
     return true;
   }
-  if (II && Corpus.TryToReplace(II, Data, Size, FeatureSetTmp)) {
+  if (II && FoundUniqFeaturesOfII &&
+      FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
+      II->U.size() > Size) {
+    Corpus.Replace(II, {Data, Data + Size});
     CheckExitOnSrcPosOrItem();
     return true;
   }
diff --git a/lib/Fuzzer/test/reduce_inputs.test b/lib/Fuzzer/test/reduce_inputs.test
index a4a5c57123d..5ce4440788f 100644
--- a/lib/Fuzzer/test/reduce_inputs.test
+++ b/lib/Fuzzer/test/reduce_inputs.test
@@ -9,5 +9,6 @@ CHECK: INFO: found item with checksum '0eb8e4ed029b774d80f2b66408203801cb982a60'
 RUN: LLVMFuzzer-ShrinkControlFlowSimpleTest -runs=0 %t/C 2>&1 | FileCheck %s --check-prefix=COUNT
 COUNT: READ units: 3
 
-
+# a bit longer test
+RUN: LLVMFuzzer-ShrinkControlFlowTest  -exit_on_item=0eb8e4ed029b774d80f2b66408203801cb982a60  -seed=1 -reduce_inputs=1 -runs=1000000  2>&1 | FileCheck %s