[libFuzzer] Remove mutation stats and weighted mutation selection.

[Dor1s]

Summary

This was an experimental feature. After evaluating it with:

1. https://github.com/google/fuzzer-test-suite/tree/master/engine-comparison

2. enabling on real world fuzz targets running at ClusterFuzz and OSS-Fuzz

The following conclusions were made:

1. With fuzz targets that have reached a code coverage plateau, the feature does not improve libFuzzer's ability to discover new coverage and may actually negatively impact it.

2. With fuzz targets that have not yet reached a code coverage plateau, the feature might speed up new units discovery in some cases, but it is quite rare and hard to confirm with a high level on confidence.

Revert of https://reviews.llvm.org/D48054 and https://reviews.llvm.org/D49621.

[metzman]

LGTM

[morehouse]

LGTM

lib/fuzzer/FuzzerDriver.cpp

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
   if (Flags.verbosity > 0 && !Dictionary.empty())
     Printf("Dictionary: %zd entries\n", Dictionary.size());
   bool DoPlainRun = AllInputsAreFiles();
   Options.SaveArtifacts =
       !DoPlainRun || Flags.minimize_crash_internal_step;
   Options.PrintNewCovPcs = Flags.print_pcs;
   Options.PrintNewCovFuncs = Flags.print_funcs;
   Options.PrintFinalStats = Flags.print_final_stats;
-  Options.PrintMutationStats = Flags.print_mutation_stats;
-  Options.UseWeightedMutations = Flags.use_weighted_mutations;
   Options.PrintCorpusStats = Flags.print_corpus_stats;
   Options.PrintCoverage = Flags.print_coverage;
   Options.PrintUnstableStats = Flags.print_unstable_stats;
   if (Flags.handle_unstable == TracePC::MinUnstable ||
       Flags.handle_unstable == TracePC::ZeroUnstable)
     Options.HandleUnstable = Flags.handle_unstable;
   Options.DumpCoverage = Flags.dump_coverage;
   if (Flags.exit_on_src_pos)

lib/fuzzer/FuzzerFlags.def

 FUZZER_FLAG_STRING(focus_function, "Experimental. "
      "Fuzzing will focus on inputs that trigger calls to this function")
 
 FUZZER_DEPRECATED_FLAG(run_equivalence_server)
 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")
-FUZZER_FLAG_INT(use_weighted_mutations, 0, "Experimental: If 1, fuzzing will "
-    "favor mutations that perform better during runtime.")

lib/fuzzer/FuzzerLoop.cpp

 #if __has_feature(memory_sanitizer)
 #undef NO_SANITIZE_MEMORY
 #define NO_SANITIZE_MEMORY __attribute__((no_sanitize_memory))
 #endif
 #endif
 
 namespace fuzzer {
 static const size_t kMaxUnitSizeToPrint = 256;
-static const size_t kUpdateMutationWeightRuns = 10000;
 
 thread_local bool Fuzzer::IsMyThread;
 
 SharedMemoryRegion SMR;
 
 bool RunningUserCallback = false;
 
 // Only one Fuzzer per process.
void Fuzzer::PrintFinalStats() {
   if (Options.PrintCoverage)
     TPC.PrintCoverage();
   if (Options.PrintUnstableStats)
     TPC.PrintUnstableStats();
   if (Options.DumpCoverage)
     TPC.DumpCoverage();
   if (Options.PrintCorpusStats)
     Corpus.PrintStats();
-  if (Options.PrintMutationStats) MD.PrintMutationStats();
   if (!Options.PrintFinalStats)
     return;
   size_t ExecPerSec = execPerSec();
   Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
   Printf("stat::average_exec_per_sec:     %zd\n", ExecPerSec);
   Printf("stat::new_units_added:          %zd\n", NumberOfNewUnitsAdded);
   Printf("stat::slowest_unit_time_sec:    %zd\n", TimeOfLongestUnitInSeconds);
   Printf("stat::peak_rss_mb:              %zd\n", GetPeakRSSMb());
if (Size <= 64)
     return !memcmp(A, B, Size);
   // Compare first and last Limit/2 bytes.
   return !memcmp(A, B, Limit / 2) &&
          !memcmp(A + Size - Limit / 2, B + Size - Limit / 2, Limit / 2);
 }
 
 void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
   TPC.RecordInitialStack();
-  if (Options.UseWeightedMutations &&
-      TotalNumberOfRuns % kUpdateMutationWeightRuns == 0)
-    MD.UpdateDistribution();
   TotalNumberOfRuns++;
   assert(InFuzzingThread());
   if (SMR.IsClient())
     SMR.WriteByteArray(Data, Size);
   // We copy the contents of Unit into a separate heap buffer
   // so that we reliably find buffer overflows in it.
   uint8_t *DataCopy = new uint8_t[Size];
   memcpy(DataCopy, Data, Size);

lib/fuzzer/FuzzerMutate.h

public:
   void AddWordToManualDictionary(const Word &W);
 
   void PrintRecommendedDictionary();
 
   void SetCorpus(const InputCorpus *Corpus) { this->Corpus = Corpus; }
 
   Random &GetRand() { return Rand; }
 
-  /// Records tally of mutations resulting in new coverage, for usefulness
-  /// metric.
-  void RecordUsefulMutations();
-
-  /// Outputs usefulness stats on command line if option is enabled.
-  void PrintMutationStats();
-
-  /// Recalculates mutation stats based on latest run data.
-  void UpdateMutationStats();
-
-  /// Sets weights based on mutation performance during fuzzer run.
-  void UpdateDistribution();
-
-  /// Returns the index of a mutation based on how useful it has been.
-  /// Favors mutations with higher usefulness ratios but can return any index.
-  size_t WeightedIndex();
-
  private:
   struct Mutator {
     size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
     const char *Name;
-    uint64_t UsefulCount;
-    uint64_t TotalCount;
   };
 
   size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size,
                                size_t MaxSize);
   size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize,
                     Vector<Mutator> &Mutators);
 
   size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
private:
   // Temporary dictionary modified by the fuzzer itself,
   // recreated periodically.
   Dictionary TempAutoDictionary;
   // Persistent dictionary modified by the fuzzer, consists of
   // entries that led to successful discoveries in the past mutations.
   Dictionary PersistentAutoDictionary;
 
   Vector<DictionaryEntry *> CurrentDictionaryEntrySequence;
-  Vector<Mutator *> CurrentMutatorSequence;
 
   static const size_t kCmpDictionaryEntriesDequeSize = 16;
   DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize];
   size_t CmpDictionaryEntriesDequeIdx = 0;
 
   const InputCorpus *Corpus = nullptr;
   Vector<uint8_t> MutateInPlaceHere;
   Vector<uint8_t> MutateWithMaskTemp;
   // CustomCrossOver needs its own buffer as a custom implementation may call
   // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere.
   Vector<uint8_t> CustomCrossOverInPlaceHere;
 
   Vector<Mutator> Mutators;
   Vector<Mutator> DefaultMutators;
-
-  // Used to weight mutations based on usefulness.
-  Vector<double> Stats;
-  std::discrete_distribution<size_t> Distribution;
+  Vector<Mutator> CurrentMutatorSequence;
 };
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MUTATE_H

lib/fuzzer/FuzzerMutate.cpp

 }
 
 MutationDispatcher::MutationDispatcher(Random &Rand,
                                        const FuzzingOptions &Options)
     : Rand(Rand), Options(Options) {
   DefaultMutators.insert(
       DefaultMutators.begin(),
       {
-          // Initialize useful and total mutation counts as 1 in order to
-          // have mutation stats (i.e. weights) with equal non-zero values.
-          {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes", 1, 1},
-          {&MutationDispatcher::Mutate_InsertByte, "InsertByte", 1, 1},
+          {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
+          {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
           {&MutationDispatcher::Mutate_InsertRepeatedBytes,
-           "InsertRepeatedBytes", 1, 1},
-          {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte", 1, 1},
-          {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit", 1, 1},
-          {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes", 1, 1},
-          {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt", 1,
-           1},
-          {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt", 1,
-           1},
-          {&MutationDispatcher::Mutate_CopyPart, "CopyPart", 1, 1},
-          {&MutationDispatcher::Mutate_CrossOver, "CrossOver", 1, 1},
+           "InsertRepeatedBytes"},
+          {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
+          {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
+          {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
+          {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
+          {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
+          {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
+          {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
           {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
-           "ManualDict", 1, 1},
+           "ManualDict"},
           {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
-           "PersAutoDict", 1, 1},
+           "PersAutoDict"},
       });
   if(Options.UseCmp)
     DefaultMutators.push_back(
-        {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP", 1, 1});
+        {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"});
 
   if (EF->LLVMFuzzerCustomMutator)
-    Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom", 1, 1});
+    Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
   else
     Mutators = DefaultMutators;
 
   if (EF->LLVMFuzzerCustomCrossOver)
     Mutators.push_back(
-        {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver", 1, 1});
-
-  // For weighted mutation selection, init with uniform weights distribution.
-  Stats.resize(Mutators.size());
+        {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
 }
 
 static char RandCh(Random &Rand) {
   if (Rand.RandBool()) return Rand(256);
   const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
   return Special[Rand(sizeof(Special) - 1)];
 }
 
void MutationDispatcher::RecordSuccessfulMutationSequence() {
   for (auto DE : CurrentDictionaryEntrySequence) {
     // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
     DE->IncSuccessCount();
     assert(DE->GetW().size());
     // Linear search is fine here as this happens seldom.
     if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
       PersistentAutoDictionary.push_back({DE->GetW(), 1});
   }
-  RecordUsefulMutations();
 }
 
 void MutationDispatcher::PrintRecommendedDictionary() {
   Vector<DictionaryEntry> V;
   for (auto &DE : PersistentAutoDictionary)
     if (!ManualDictionary.ContainsWord(DE.GetW()))
       V.push_back(DE);
   if (V.empty()) return;
   Printf("###### Recommended dictionary. ######\n");
   for (auto &DE: V) {
     assert(DE.GetW().size());
     Printf("\"");
     PrintASCII(DE.GetW(), "\"");
     Printf(" # Uses: %zd\n", DE.GetUseCount());
   }
   Printf("###### End of recommended dictionary. ######\n");
 }
 
 void MutationDispatcher::PrintMutationSequence() {
   Printf("MS: %zd ", CurrentMutatorSequence.size());
-  for (auto M : CurrentMutatorSequence) Printf("%s-", M->Name);
+  for (auto M : CurrentMutatorSequence)
+    Printf("%s-", M.Name);
   if (!CurrentDictionaryEntrySequence.empty()) {
     Printf(" DE: ");
     for (auto DE : CurrentDictionaryEntrySequence) {
       Printf("\"");
       PrintASCII(DE->GetW(), "\"-");
     }
   }
 }

 // Mutates Data in place, returns new size.
 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
                                       size_t MaxSize,
                                       Vector<Mutator> &Mutators) {
   assert(MaxSize > 0);
   // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
   // in which case they will return 0.
   // Try several times before returning un-mutated data.
-  Mutator *M = nullptr;
   for (int Iter = 0; Iter < 100; Iter++) {
-    // Even when using weighted mutations, fallback to the default selection in
-    // 20% of cases.
-    if (Options.UseWeightedMutations && Rand(5))
-      M = &Mutators[WeightedIndex()];
-    else
-      M = &Mutators[Rand(Mutators.size())];
-    size_t NewSize = (this->*(M->Fn))(Data, Size, MaxSize);
+    auto M = Mutators[Rand(Mutators.size())];
+    size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
     if (NewSize && NewSize <= MaxSize) {
       if (Options.OnlyASCII)
         ToASCII(Data, NewSize);
       CurrentMutatorSequence.push_back(M);
-      M->TotalCount++;
       return NewSize;
     }
   }
   *Data = ' ';
   return 1;   // Fallback, should not happen frequently.
 }
 
 // Mask represents the set of Data bytes that are worth mutating.
size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
   return Size;
 }
 
 void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
   ManualDictionary.push_back(
       {W, std::numeric_limits<size_t>::max()});
 }
 
-void MutationDispatcher::RecordUsefulMutations() {
-  for (auto M : CurrentMutatorSequence) M->UsefulCount++;
-}
-
-void MutationDispatcher::PrintMutationStats() {
-  Printf("\nstat::mutation_usefulness:      ");
-  UpdateMutationStats();
-  for (size_t i = 0; i < Stats.size(); i++) {
-    Printf("%.3f", 100 * Stats[i]);
-    if (i < Stats.size() - 1)
-      Printf(",");
-    else
-      Printf("\n");
-  }
-}
-
-void MutationDispatcher::UpdateMutationStats() {
-  // Calculate usefulness statistic for each mutation
-  for (size_t i = 0; i < Stats.size(); i++)
-    Stats[i] =
-        static_cast<double>(Mutators[i].UsefulCount) / Mutators[i].TotalCount;
-}
-
-void MutationDispatcher::UpdateDistribution() {
-  UpdateMutationStats();
-  Distribution = std::discrete_distribution<size_t>(Stats.begin(), Stats.end());
-}
-
-size_t MutationDispatcher::WeightedIndex() { return Distribution(GetRand()); }
-
 }  // namespace fuzzer

lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   std::string ExitOnItem;
   std::string FocusFunction;
   std::string DataFlowTrace;
   bool SaveArtifacts = true;
   bool PrintNEW = true; // Print a status line when new units are found;
   bool PrintNewCovPcs = false;
   int PrintNewCovFuncs = 0;
   bool PrintFinalStats = false;
-  bool PrintMutationStats = false;
-  bool UseWeightedMutations = false;
   bool PrintCorpusStats = false;
   bool PrintCoverage = false;
   bool PrintUnstableStats = false;
   int HandleUnstable = 0;
   bool DumpCoverage = false;
   bool DetectLeaks = true;
   int PurgeAllocatorIntervalSec = 1;
   int  TraceMalloc = 0;

test/fuzzer/fuzzer-mutationstats.test

-RUN: %cpp_compiler %S/SimpleTest.cpp -o %t-MutationStatsTest
-RUN: not %run %t-MutationStatsTest -print_mutation_stats=1 2>&1 | FileCheck %s --check-prefix=STAT
-
-# Ensures there are some non-zero values in the usefulness percentages printed.
-STAT: stat::mutation_usefulness:   {{[0-9]+\.[0-9]+}}
-
-# Weighted mutations only trigger after first 10,000 runs, hence flag.
-RUN: not %run %t-MutationStatsTest -use_weighted_mutations=1 -seed=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=WEIGHTED
-
-WEIGHTED: BINGO