[libFuzzer] Unstable Edge Handling

[kevinwkt]

Summary

If dump_unstable_coverage.
We use the first CollectFeatures to count how many features there are.

If no new features, CollectFeatures like before.

If there are new coverage, we run CB 2 more times,

We check which edges are unstable per input and we store the least amount of hit counts for each edge.
We then apply these hit counts back to inline8bitcounters so that CollectFeatures can work as intended.

[metzman]

This code seems like an improvement over last time, but I'll make another pass tomorrow morning just to be sure =)
It might be easier to review this if it were diffed against https://reviews.llvm.org/D48150 so that I don't need to see changes that aren't relevant. But don't spend too much time figuring out how to do this.

lib/fuzzer/FuzzerLoop.cpp

492

I think it would be cleaner to have one anonymous function that handles Options.DumpUnstableCoverage rather than having two.

498

I think the body of this else (and that of the if for consistency) should be in curly braces since it is more than a few lines long.
Otherwise it's easy to introduce bugs by adding a statement to the end of the else body not realizing that it won't actually be part of the body.

507

dump_unstable_coveragem -> dump_unstable_coverage
Also, don't break comments at random points.
Unless you are breaking up a comment by lines to improve clarity, it's a good rule of thumb to include as many words on a single line as possible (while keeping the line < 80 chars).
In this case:

// If dump_unstable_coverage and found new features, execute the same input
// two more times to detect unstable edges.

(If my example, is over 80 chars don't copy it directly)

513

Let's put curly braces around this, multiline if-else bodies without braces are a bad idea IMO

514

Does there have to be 3 anonymous functions here? Let's discuss tomorrow how we can make this cleaner.

[Dor1s]

lib/fuzzer/FuzzerCorpus.h

240

nit: unnecessary () around the second condition

lib/fuzzer/FuzzerLoop.cpp

492

+1, definitely.

528

I don't think this comment makes sense. The first part just repeats the following if condition, and the second part explains what's going on inside of CheckForUnstableCounters, which is not good. E.g. let's say we start re-running an input 5 times, or come up with a completely different implementation of CheckForUnstableCounters. This comment likely won't be updated and thus will create ambiguity. Just remove it.

lib/fuzzer/FuzzerTracePC.cpp

64

Maybe inverse invert this condition and do return;? Also, shouldn't it be an assert?

The same for other functions below.

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 CheckFeature(size_t Idx, uint32_t NewSize) {
+    assert(NewSize);
+    Idx = Idx % kFeatureSetSize;
+    uint32_t OldSize = GetFeature(Idx);
+    if (OldSize == 0 || (OldSize > NewSize))
+      return true;
+    return false;
+  }
+
   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]; }

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;
+  if (Flags.dump_unstable_coverage && Flags.dump_coverage) {
+    Printf("Can not use dump_unstable_coverage and dump_coverage options together\n");
+    _Exit(1);
+  }
+  if (Flags.dump_unstable_coverage == TracePC::AllUnstable ||
+      Flags.dump_unstable_coverage == TracePC::IgnoreInitUnstable)
+    Options.DumpUnstableCoverage = Flags.dump_unstable_coverage;
   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)

lib/fuzzer/FuzzerExtFunctions.def

 EXT_FUNC(__sanitizer_symbolize_pc, void,
          (void *, const char *fmt, char *out_buf, size_t out_buf_size), false);
 EXT_FUNC(__sanitizer_get_module_and_offset_for_pc, int,
          (void *pc, char *module_path,
          size_t module_path_len,void **pc_offset), false);
 EXT_FUNC(__sanitizer_set_death_callback, void, (void (*)(void)), true);
 EXT_FUNC(__sanitizer_set_report_fd, void, (void*), false);
 EXT_FUNC(__sanitizer_dump_coverage, void, (const uintptr_t *, uintptr_t),
-         false);
+         true);

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(dump_unstable_coverage, 0, "Experimental."
+          " Is not compatible with dump_coverage flag."
+          " Dumps unstable edge coverage information"
+          " as a .sancov file at exit."
+          " Executes every input 3 times in total if a unique feature"
+          " is found during the first execution."
+          " If 1, compares all 3 runs for unstable edges"
+          " If 2, compares run 2 and 3 only taking into account"
+          " that run 1 is initialization run.")
 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.")

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,

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.DumpUnstableCoverage)
+    TPC.DumpUnstableCoverage();
   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 = [&]() {
+    UnitStartTime = system_clock::now();
+    TPC.ResetMaps();
+    RunningCB = true;
+    CB(Data, Size);
+    RunningCB = false;
+    UnitStopTime = system_clock::now();
+  };
+
+  // Copy original run counters into our unstable counters
+  if (Options.DumpUnstableCoverage == TPC.AllUnstable)
+    TPC.InitializeUnstableCounters();
+
+  // First Rerun
+  CBSetupAndRun();
+
+  if (Options.DumpUnstableCoverage == TPC.AllUnstable)
+    TPC.UpdateUnstableCounters();
+  else
+    TPC.InitializeUnstableCounters();
+
+  // Second Rerun
+  CBSetupAndRun();
+
+  TPC.UpdateUnstableCounters();
+
+  TPC.ApplyUnstableCounters();
+}
+
 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();
+  int NumNewFeaturesForUnstable = 0;  
+
+  // If DumpUnstableCoverage, we don't add the features now
+  // since more checks must be done.
+  if (Options.DumpUnstableCoverage)
+    TPC.CollectFeatures([&](size_t Feature) {
+      if (Corpus.CheckFeature(Feature, Size))
+        NumNewFeaturesForUnstable++;
+    });
+  else
+    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++;
+    });
+
+  // If dump_unstable_coveragem and found new features, execute 
+  // the same input two more times to detect unstable edges.
+  if (Options.DumpUnstableCoverage && NumNewFeaturesForUnstable)
+    CheckForUnstableCounters(Data, Size);
+
+  // CollectFeatures for dump_unstable_coverage now that the checks are done.
+  if (Options.DumpUnstableCoverage)
     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++;
     });
+
   if (FoundUniqFeatures)
     *FoundUniqFeatures = FoundUniqFeaturesOfII;
   PrintPulseAndReportSlowInput(Data, Size);
   size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
+
+  // If dump_unstable_coverage, execute the same input two more times to detect
+  // unstable edges.
+  if (NumNewFeatures && Options.DumpUnstableCoverage)
+    CheckForUnstableCounters(Data, Size);
+
   if (NumNewFeatures) {
     TPC.UpdateObservedPCs();
     Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile,
                        TPC.ObservedFocusFunction(),
                        UniqFeatureSetTmp, DFT);
     return true;
   }
   if (II && FoundUniqFeaturesOfII &&

lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   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 DumpCoverage = false;
+  int DumpUnstableCoverage = 0;
   bool DetectLeaks = true;
   int PurgeAllocatorIntervalSec = 1;
   int  TraceMalloc = 0;
   bool HandleAbrt = false;
   bool HandleBus = false;
   bool HandleFpe = false;
   bool HandleIll = false;
   bool HandleInt = false;

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 DumpUnstableCoverageOptions {
+    AllUnstable = 1,
+    IgnoreInitUnstable = 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 SetUseValueProfile(bool VP) { UseValueProfile = VP; }
public:
 
   void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
   void PrintFeatureSet();
 
   void PrintModuleInfo();
 
   void PrintCoverage();
   void DumpCoverage();
+  void DumpUnstableCoverage();
 
   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();
+  void UpdateUnstableCounters();
+  void ApplyUnstableCounters();
+
 private:
+  // Value used to represent unstable edge.
+  static constexpr int16_t kUnstableCounter = -1;
+
+  // Uses 16-bit signed type to be able to accommodate any possible value from
+  // uint8_t counter and -1 constant as well.
+  int16_t UnstableCounters[kNumPCs];
+
   bool UseCounters = false;
   bool UseValueProfile = false;
   bool DoPrintNewPCs = false;
   size_t NumPrintNewFuncs = 0;
 
   struct Module {
     uint32_t *Start, *Stop;
   };
private:
   struct PCTableEntry {
     uintptr_t PC, PCFlags;
   };
 
   struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096];
   size_t NumPCTables;
   size_t NumPCsInPCTables;
 
-  uint8_t *Counters() const;
-  uintptr_t *PCs() const;
-
   Set<uintptr_t> ObservedPCs;
   Set<uintptr_t> ObservedFuncs;
 
   std::pair<size_t, size_t> FocusFunction = {-1, -1};  // Module and PC IDs.
 
 
   ValueBitMap ValueProfileMap;
   uintptr_t InitialStack;
+
+  uintptr_t *PCs() const;
+  uint8_t *Counters() const;
 };
 
 template <class Callback>
 // void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);
 ATTRIBUTE_NO_SANITIZE_ALL
 void ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,
                         size_t FirstFeature, Callback Handle8bitCounter) {
   typedef uintptr_t LargeType;

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;
 }
 
+// Initializes unstable counters by copying Inline8bitCounters to unstable counters.
+void TracePC::InitializeUnstableCounters() {
+  if (NumInline8bitCounters == NumPCsInPCTables) {
+    size_t UnstableIdx = 1;
+    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++, UnstableIdx++)
+        UnstableCounters[UnstableIdx] = Beg[j];
+    }
+  }
+}
+
+// Compares the current counters with counters from previous runs
+// and records differences as unstable edges.
+void TracePC::UpdateUnstableCounters() {
+  if (NumInline8bitCounters == NumPCsInPCTables) {
+    size_t UnstableIdx = 1;
+    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++, UnstableIdx++)
+        if (Beg[j] < UnstableCounters[UnstableIdx])
+          UnstableCounters[UnstableIdx] = Beg[j];
+    }
+  }
+}
+
+// Move UnstableCounters to Inline8bitCounters to collect the features.
+void TracePC::ApplyUnstableCounters() {
+  if (NumInline8bitCounters == NumPCsInPCTables) {
+    size_t UnstableIdx = 1;
+    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++, UnstableIdx++)
+        Beg[j] = UnstableCounters[UnstableIdx];
+    }
+  }
+}
 
 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};
for (auto PC: UncoveredPCs) {
              DescribePC("%s:%l", GetNextInstructionPc(PC)).c_str());
     }
   };
 
   IterateCoveredFunctions(CoveredFunctionCallback);
 }
 
 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());
-  }
+  if (!EF->__sanitizer_dump_coverage)
+    return;
+
+
+void TracePC::DumpUnstableCoverage() {
+  if (!EF->__sanitizer_dump_coverage)
+    return;
+
+  Vector<uintptr_t> PCsCopy(GetNumPCs());
+  for (size_t i = 0; i < GetNumPCs(); i++)
+    PCsCopy[i] = 0;
+
+  size_t UnstableIdx = 1;
+  if (NumInline8bitCounters == NumPCsInPCTables) {
+    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++, UnstableIdx++)
+        if (UnstableCounters[UnstableIdx] == kUnstableCounter)
+          PCsCopy[UnstableIdx] = ModulePCTable[i].Start[j].PC;
+    }
+  }
+  EF->__sanitizer_dump_coverage(PCsCopy.data(), PCsCopy.size());
 }
 
 // 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