[libFuzzer] Remove unstable edge handling

[metzman]

Summary

Remove code for handling unstable edges from libFuzzer since
it has not been found useful.

[metzman]

• undo accidental change

[metzman]

Add whitespace change back

[metzman]

Please take a look.
This commit reverts the following commits:
https://reviews.llvm.org/D50411
https://reviews.llvm.org/D50264
https://reviews.llvm.org/D49684
https://reviews.llvm.org/D49578
https://reviews.llvm.org/D49453
https://reviews.llvm.org/D49525
https://reviews.llvm.org/D49212

[morehouse]

LGTM

[Dor1s]

Thanks a ton, Jonathan!

[metzman]

squash

compiler-rt/lib/fuzzer/FuzzerCorpus.h

if (OldSize == 0 || (Shrink && OldSize > NewSize)) {
         Printf("ADD FEATURE %zd sz %d\n", Idx, NewSize);
       SmallestElementPerFeature[Idx] = Inputs.size();
       InputSizesPerFeature[Idx] = NewSize;
       return true;
     }
     return false;
   }
 
-  bool IsFeatureNew(size_t Idx, uint32_t NewSize, bool Shrink) {
-    assert(NewSize);
-    uint32_t OldSize = GetFeature(Idx % kFeatureSetSize);
-    return OldSize == 0 || (Shrink && OldSize > NewSize);
-  }
-
   size_t NumFeatures() const { return NumAddedFeatures; }
   size_t NumFeatureUpdates() const { return NumUpdatedFeatures; }
 
 private:
 
   static const bool FeatureDebug = false;
 
   size_t GetFeature(size_t Idx) const { return InputSizesPerFeature[Idx]; }

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
   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.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)
     Options.ExitOnSrcPos = Flags.exit_on_src_pos;
   if (Flags.exit_on_item)
     Options.ExitOnItem = Flags.exit_on_item;
   if (Flags.focus_function)
     Options.FocusFunction = Flags.focus_function;
   if (Flags.data_flow_trace)

compiler-rt/lib/fuzzer/FuzzerFlags.def

 FUZZER_FLAG_INT(print_final_stats, 0, "If 1, print statistics at exit.")
 FUZZER_FLAG_INT(print_corpus_stats, 0,
   "If 1, print statistics on corpus elements at exit.")
 FUZZER_FLAG_INT(print_coverage, 0, "If 1, print coverage information as text"
                                    " at exit.")
 FUZZER_FLAG_INT(dump_coverage, 0, "Deprecated."
                                   " If 1, dump coverage information as a"
                                   " .sancov file at exit.")
-FUZZER_FLAG_INT(handle_unstable, 0, "Experimental."
-                   " Executes every input 3 times in total if a unique feature"
-                   " is found during the first execution."
-                   " If 1, we only use the minimum hit count from the 3 runs"
-                   " to determine whether an input is interesting."
-                   " If 2, we disregard edges that are found unstable for"
-                   " feature collection.")
-FUZZER_FLAG_INT(print_unstable_stats, 0, "Experimental."
-          " If 1, print unstable statistics at exit.")
 FUZZER_FLAG_INT(handle_segv, 1, "If 1, try to intercept SIGSEGV.")
 FUZZER_FLAG_INT(handle_bus, 1, "If 1, try to intercept SIGBUS.")
 FUZZER_FLAG_INT(handle_abrt, 1, "If 1, try to intercept SIGABRT.")
 FUZZER_FLAG_INT(handle_ill, 1, "If 1, try to intercept SIGILL.")
 FUZZER_FLAG_INT(handle_fpe, 1, "If 1, try to intercept SIGFPE.")
 FUZZER_FLAG_INT(handle_int, 1, "If 1, try to intercept SIGINT.")
 FUZZER_FLAG_INT(handle_term, 1, "If 1, try to intercept SIGTERM.")
 FUZZER_FLAG_INT(handle_xfsz, 1, "If 1, try to intercept SIGXFSZ.")

compiler-rt/lib/fuzzer/FuzzerInternal.h

public:
   static void StaticAlarmCallback();
   static void StaticCrashSignalCallback();
   static void StaticExitCallback();
   static void StaticInterruptCallback();
   static void StaticFileSizeExceedCallback();
   static void StaticGracefulExitCallback();
 
   void ExecuteCallback(const uint8_t *Data, size_t Size);
-  void CheckForUnstableCounters(const uint8_t *Data, size_t Size);
   bool RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile = false,
               InputInfo *II = nullptr, bool *FoundUniqFeatures = nullptr);
 
   // Merge Corpora[1:] into Corpora[0].
   void Merge(const Vector<std::string> &Corpora);
   void CrashResistantMerge(const Vector<std::string> &Args,
                            const Vector<std::string> &Corpora,
                            const char *CoverageSummaryInputPathOrNull,

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

void Fuzzer::PrintStats(const char *Where, const char *End, size_t Units) {
   Printf(" exec/s: %zd", ExecPerSec);
   Printf(" rss: %zdMb", GetPeakRSSMb());
   Printf("%s", End);
 }
 
 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.PrintFinalStats)
     return;
   size_t ExecPerSec = execPerSec();
   Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
void Fuzzer::PrintPulseAndReportSlowInput(const uint8_t *Data, size_t Size) {
   if (TimeOfUnit > TimeOfLongestUnitInSeconds * 1.1 &&
       TimeOfUnit >= Options.ReportSlowUnits) {
     TimeOfLongestUnitInSeconds = TimeOfUnit;
     Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
     WriteUnitToFileWithPrefix({Data, Data + Size}, "slow-unit-");
   }
 }
 
-void Fuzzer::CheckForUnstableCounters(const uint8_t *Data, size_t Size) {
-  auto CBSetupAndRun = [&]() {
-    ScopedEnableMsanInterceptorChecks S;
-    UnitStartTime = system_clock::now();
-    TPC.ResetMaps();
-    RunningUserCallback = true;
-    CB(Data, Size);
-    RunningUserCallback = false;
-    UnitStopTime = system_clock::now();
-  };
-
-  // Copy original run counters into our unstable counters
-  TPC.InitializeUnstableCounters();
-
-  // First Rerun
-  CBSetupAndRun();
-  if (TPC.UpdateUnstableCounters(Options.HandleUnstable)) {
-    // Second Rerun
-    CBSetupAndRun();
-    TPC.UpdateAndApplyUnstableCounters(Options.HandleUnstable);
-  }
-}
-
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                     InputInfo *II, bool *FoundUniqFeatures) {
   if (!Size)
     return false;
 
   ExecuteCallback(Data, Size);
 
   UniqFeatureSetTmp.clear();
   size_t FoundUniqFeaturesOfII = 0;
   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
-  bool NewFeaturesUnstable = false;
-
-  if (Options.HandleUnstable || Options.PrintUnstableStats) {
-    TPC.CollectFeatures([&](size_t Feature) {
-      if (Corpus.IsFeatureNew(Feature, Size, Options.Shrink))
-        NewFeaturesUnstable = true;
-    });
-    if (NewFeaturesUnstable)
-      CheckForUnstableCounters(Data, Size);
-  }
-
   TPC.CollectFeatures([&](size_t 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++;
   });

compiler-rt/lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   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 PrintCorpusStats = false;
   bool PrintCoverage = false;
-  bool PrintUnstableStats = false;
-  int HandleUnstable = 0;
   bool DumpCoverage = false;
   bool DetectLeaks = true;
   int PurgeAllocatorIntervalSec = 1;
   int  TraceMalloc = 0;
   bool HandleAbrt = false;
   bool HandleBus = false;
   bool HandleFpe = false;
   bool HandleIll = false;

compiler-rt/lib/fuzzer/FuzzerTracePC.h

 };
 
 class TracePC {
  public:
   static const size_t kNumPCs = 1 << 21;
   // How many bits of PC are used from __sanitizer_cov_trace_pc.
   static const size_t kTracePcBits = 18;
 
-  enum HandleUnstableOptions {
-    MinUnstable = 1,
-    ZeroUnstable = 2,
-  };
-
   void HandleInit(uint32_t *Start, uint32_t *Stop);
   void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop);
   void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop);
   void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee);
   template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2);
   size_t GetTotalPCCoverage();
   void SetUseCounters(bool UC) { UseCounters = UC; }
   void SetUseValueProfileMask(uint32_t VPMask) { UseValueProfileMask = VPMask; }
public:
 
   void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
   void PrintFeatureSet();
 
   void PrintModuleInfo();
 
   void PrintCoverage();
   void DumpCoverage();
-  void PrintUnstableStats();
 
   template<class CallBack>
   void IterateCoveredFunctions(CallBack CB);
 
   void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
                          size_t n, bool StopAtZero);
 
   TableOfRecentCompares<uint32_t, 32> TORC4;
public:
   void ForEachObservedPC(CallBack CB) {
     for (auto PC : ObservedPCs)
       CB(PC);
   }
 
   void SetFocusFunction(const std::string &FuncName);
   bool ObservedFocusFunction();
 
-  void InitializeUnstableCounters();
-  bool UpdateUnstableCounters(int UnstableMode);
-  void UpdateAndApplyUnstableCounters(int UnstableMode);
-
 private:
-  struct UnstableEdge {
-    uint8_t Counter;
-    bool IsUnstable;
-  };
-
-  UnstableEdge UnstableCounters[kNumPCs];
-
   bool UseCounters = false;
   uint32_t UseValueProfileMask = false;
   bool DoPrintNewPCs = false;
   size_t NumPrintNewFuncs = 0;
 
   struct Module {
     uint32_t *Start, *Stop;
   };
private:
   size_t NumPCsInPCTables;
 
   uint8_t *Counters() const;
   uintptr_t *PCs() const;
 
   Set<uintptr_t> ObservedPCs;
   std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs;  // PC => Counter.
 
-  template <class Callback>
-  void IterateInline8bitCounters(Callback CB) const;
-
   std::pair<size_t, size_t> FocusFunction = {-1, -1};  // Module and PC IDs.
 
   ValueBitMap ValueProfileMap;
   uintptr_t InitialStack;
 };
 
 template <class Callback>
 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

if (ObservedPCs.size())
     return ObservedPCs.size();
   size_t Res = 0;
   for (size_t i = 1, N = GetNumPCs(); i < N; i++)
     if (PCs()[i])
       Res++;
   return Res;
 }
 
-template<class CallBack>
-void TracePC::IterateInline8bitCounters(CallBack CB) const {
-  if (NumInline8bitCounters && NumInline8bitCounters == NumPCsInPCTables) {
-    size_t CounterIdx = 0;
-    for (size_t i = 0; i < NumModulesWithInline8bitCounters; i++) {
-      uint8_t *Beg = ModuleCounters[i].Start;
-      size_t Size = ModuleCounters[i].Stop - Beg;
-      assert(Size == (size_t)(ModulePCTable[i].Stop - ModulePCTable[i].Start));
-      for (size_t j = 0; j < Size; j++, CounterIdx++)
-        CB(i, j, CounterIdx);
-    }
-  }
-}
-
-// Initializes unstable counters by copying Inline8bitCounters to unstable
-// counters.
-void TracePC::InitializeUnstableCounters() {
-  IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    UnstableCounters[UnstableIdx].Counter = ModuleCounters[i].Start[j];
-  });
-}
-
-// Compares the current counters with counters from previous runs
-// and records differences as unstable edges.
-bool TracePC::UpdateUnstableCounters(int UnstableMode) {
-  bool Updated = false;
-  IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter) {
-      Updated = true;
-      UnstableCounters[UnstableIdx].IsUnstable = true;
-      if (UnstableMode == ZeroUnstable)
-        UnstableCounters[UnstableIdx].Counter = 0;
-      else if (UnstableMode == MinUnstable)
-        UnstableCounters[UnstableIdx].Counter = std::min(
-            ModuleCounters[i].Start[j], UnstableCounters[UnstableIdx].Counter);
-    }
-  });
-  return Updated;
-}
-
-// Updates and applies unstable counters to ModuleCounters in single iteration
-void TracePC::UpdateAndApplyUnstableCounters(int UnstableMode) {
-  IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter) {
-      UnstableCounters[UnstableIdx].IsUnstable = true;
-      if (UnstableMode == ZeroUnstable)
-        ModuleCounters[i].Start[j] = 0;
-      else if (UnstableMode == MinUnstable)
-        ModuleCounters[i].Start[j] = std::min(
-            ModuleCounters[i].Start[j], UnstableCounters[UnstableIdx].Counter);
-    }
-  });
-}
 
 void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) {
   if (Start == Stop) return;
   if (NumModulesWithInline8bitCounters &&
       ModuleCounters[NumModulesWithInline8bitCounters-1].Start == Start) return;
   assert(NumModulesWithInline8bitCounters <
          sizeof(ModuleCounters) / sizeof(ModuleCounters[0]));
   ModuleCounters[NumModulesWithInline8bitCounters++] = {Start, Stop};
auto Observe = [&](const PCTableEntry &TE) {
     if (TE.PCFlags & 1)
       if (++ObservedFuncs[TE.PC] == 1 && NumPrintNewFuncs)
         CoveredFuncs.push_back(TE.PC);
     ObservePC(TE.PC);
   };
 
   if (NumPCsInPCTables) {
     if (NumInline8bitCounters == NumPCsInPCTables) {
-      IterateInline8bitCounters([&](int i, int j, int CounterIdx) {
-        if (ModuleCounters[i].Start[j])
+      for (size_t i = 0; i < NumModulesWithInline8bitCounters; i++) {
+        uint8_t *Beg = ModuleCounters[i].Start;
+        size_t Size = ModuleCounters[i].Stop - Beg;
+        assert(Size ==
+               (size_t)(ModulePCTable[i].Stop - ModulePCTable[i].Start));
+        for (size_t j = 0; j < Size; j++)
+          if (Beg[j])
             Observe(ModulePCTable[i].Start[j]);
-      });
+      }
     } else if (NumGuards == NumPCsInPCTables) {
       size_t GuardIdx = 1;
       for (size_t i = 0; i < NumModules; i++) {
         uint32_t *Beg = Modules[i].Start;
         size_t Size = Modules[i].Stop - Beg;
         assert(Size ==
                (size_t)(ModulePCTable[i].Stop - ModulePCTable[i].Start));
         for (size_t j = 0; j < Size; j++, GuardIdx++)
void TracePC::DumpCoverage() {
   if (EF->__sanitizer_dump_coverage) {
     Vector<uintptr_t> PCsCopy(GetNumPCs());
     for (size_t i = 0; i < GetNumPCs(); i++)
       PCsCopy[i] = PCs()[i] ? GetPreviousInstructionPc(PCs()[i]) : 0;
     EF->__sanitizer_dump_coverage(PCsCopy.data(), PCsCopy.size());
   }
 }
 
-void TracePC::PrintUnstableStats() {
-  size_t count = 0;
-  Printf("UNSTABLE_FUNCTIONS:\n");
-  IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    const PCTableEntry &TE = ModulePCTable[i].Start[j];
-    if (UnstableCounters[UnstableIdx].IsUnstable) {
-      count++;
-      if (ObservedFuncs.count(TE.PC)) {
-        auto VisualizePC = GetNextInstructionPc(TE.PC);
-        std::string FunctionStr = DescribePC("%F", VisualizePC);
-        if (FunctionStr.find("in ") == 0)
-          FunctionStr = FunctionStr.substr(3);
-        Printf("%s\n", FunctionStr.c_str());
-      }
-    }
-  });
-
-  Printf("stat::stability_rate: %.2f\n",
-         100 - static_cast<float>(count * 100) / NumInline8bitCounters);
-}
-
 // Value profile.
 // We keep track of various values that affect control flow.
 // These values are inserted into a bit-set-based hash map.
 // Every new bit in the map is treated as a new coverage.
 //
 // For memcmp/strcmp/etc the interesting value is the length of the common
 // prefix of the parameters.
 // For cmp instructions the interesting value is a XOR of the parameters.

compiler-rt/test/fuzzer/PrintUnstableStatsTest.cpp

-#include <assert.h>
-#include <cstdint>
-#include <cstdio>
-#include <cstdlib>
-
-int x = 0;
-bool skip0 = false;
-bool skip1 = false;
-bool skip2 = false;
-
-__attribute__((noinline)) void det0() { x++; }
-__attribute__((noinline)) void det1() { x++; }
-__attribute__((noinline)) void det2() { x++; }
-__attribute__((noinline)) void det3() { x++; }
-__attribute__((noinline)) void det4() { x++; }
-
-__attribute__((noinline)) void ini0() { x++; }
-__attribute__((noinline)) void ini1() { x++; }
-__attribute__((noinline)) void ini2() { x++; }
-
-__attribute__((noinline)) void t0(int a) { x += a; }
-__attribute__((noinline)) void t1() { x++; }
-__attribute__((noinline)) void t2(int a, int b) { x += a + b; }
-__attribute__((noinline)) void t3() { x++; }
-__attribute__((noinline)) void t4(int a, int b, int c) { x += a + b +c; }
-
-extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
-  if (Size == 1 && Data[0] == 'A' && !skip0) {
-    skip0 = true;
-    ini0();
-  }
-  if (Size == 1 && Data[0] == 'B' && !skip1) {
-    skip1 = true;
-    ini1();
-  }
-  if (Size == 1 && Data[0] == 'C' && !skip2) {
-    skip2 = true;
-    ini2();
-  }
-
-  det0();
-  det1();
-  int a = rand();
-  det2();
-
-  switch (a % 5) {
-  case 0:
-    t0(a);
-    break;
-  case 1:
-    t1();
-    break;
-  case 2:
-    t2(a, a);
-    break;
-  case 3:
-    t3();
-    break;
-  case 4:
-    t4(a, a, a);
-    break;
-  default:
-    assert(false);
-  }
-
-  det3();
-  det4();
-  return 0;
-}

compiler-rt/test/fuzzer/handle-unstable.test

-# Tests -handle_unstable
-# FIXME: Disabled on Windows until symbolization works properly.
-UNSUPPORTED: windows
-
-RUN: %cpp_compiler %S/PrintUnstableStatsTest.cpp -o %t-HandleUnstableTest
-
-; Normal
-RUN: %run %t-HandleUnstableTest -print_coverage=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=NORMAL
-NORMAL-DAG: det0()
-NORMAL-DAG: det1()
-NORMAL-DAG: det2()
-NORMAL-DAG: det3()
-NORMAL-DAG: det4()
-NORMAL-DAG: ini0()
-NORMAL-DAG: ini1()
-NORMAL-DAG: ini2()
-NORMAL-DAG: t0(int)
-NORMAL-DAG: t1()
-NORMAL-DAG: t2(int, int)
-NORMAL-DAG: t3()
-NORMAL-DAG: t4(int, int, int)
-
-; MinUnstable
-RUN: %run %t-HandleUnstableTest -print_coverage=1 -handle_unstable=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=MIN
-MIN-NOT: ini0()
-MIN-NOT: ini1()
-MIN-NOT: ini2()
-MIN: det0()
-MIN: det1()
-MIN: det2()
-MIN: det3()
-MIN: det4()
-
-; ZeroUnstable
-RUN: %run %t-HandleUnstableTest -print_coverage=1 -handle_unstable=2 -runs=1 2>&1 | FileCheck %s --check-prefix=ZERO
-ZERO-NOT: ini0()
-ZERO-NOT: ini1()
-ZERO-NOT: ini2()
-ZERO: det0()
-ZERO: det1()
-ZERO: det2()
-ZERO: det3()
-ZERO: det4()

compiler-rt/test/fuzzer/print_unstable_stats.test

-# Tests -print_unstable_stats
-# Disabled on Windows because of differences symbolizing and flakiness.
-UNSUPPORTED: aarch64, windows
-
-RUN: %cpp_compiler %S/PrintUnstableStatsTest.cpp -o %t-PrintUnstableStatsTest
-
-RUN: %run %t-PrintUnstableStatsTest -print_unstable_stats=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=LONG
-# We do not observe ini functions since we take the minimum hit counts, and minimum hit counts for ini is 0.
-LONG: UNSTABLE_FUNCTIONS:
-LONG-NOT: det0()
-LONG-NOT: det1()
-LONG-NOT: det2()
-LONG-NOT: det3()
-LONG-NOT: det4()
-LONG-NOT: ini0()
-LONG-NOT: ini1()
-LONG-NOT: ini2()
-LONG-DAG: t0(int)
-LONG-DAG: t1()
-LONG-DAG: t2(int, int)
-LONG-DAG: t3()
-LONG-DAG: t4(int, int, int)
-
-LONG-DAG: stat::stability_rate: 27.59