[libFuzzer] Implement stat::stability_rate based on the percentage of unstable edges.

[kevinwkt]

Summary

Created a -print_unstable_stats flag.
When -print_unstable_stats=1, we run it 2 more times on interesting inputs poisoning unstable edges in an array.
On program termination, we run PrintUnstableStats() which will print a line with a stability percentage like AFL does.

Patch by Kyungtak Woo (@kevinwkt).

[metzman]

Just some minor suggestions.

lib/fuzzer/FuzzerExtFunctions.def

48

What is this change for? To trow an error if dump_coverage is not available?
I'm not sure this change is good (what if we only compile with new instrumentation where there is no dump_coverage) but in any case it isn't needed. I think you should undo this change.

lib/fuzzer/FuzzerFlags.def

113

I think this should be named print_unstable_stat instead.

lib/fuzzer/FuzzerTracePC.cpp

335

Please remove this change if it isn't necessary for this patch.

349

Please use the same style as the final stats in PrintFinalStats .

lib/fuzzer/FuzzerTracePC.h

183

Please don't make unnecessary changes.

test/fuzzer/PrintUnstableStatsTest.cpp

10

You can ignore this comment if Matt/Kostya approved of the style you used here, but I think it makes sense to put the attributes and function names on the same line, eg:

__attribute__((noinline)) void det0() { x++; }

40

I think this newline isn't necessary.
Also, the newlines in this function seem arbitrary.

[metzman]

Also, you should add @Dor1s as a reviewer.

[metzman]

lib/fuzzer/FuzzerFlags.def

113

Maybe ignore this comment for now, only make the change if someone else brings this up since it's kinda pedantic and I can see someone asking you why print_unstable_stat is inconsistent with all other stats

[kevinwkt]

Fixed comments.

[Dor1s]

Looks great, left some comments.

lib/fuzzer/FuzzerTracePC.cpp

353

nit: size_t (the same type as NumInline8bitCounters uses) might be a safer choice.

354

same here, since NumInline8bitCounters is of size_t type, please use the same type for the index variable

357

why %lf? I don't think that l makes any sense here, as it will be the same as %f: http://www.cplusplus.com/reference/cstdio/printf/

test/fuzzer/PrintUnstableStatsTest.cpp

59

I'd recommend changing this to case 4:. If compiler starts to complain that you don't have the default clause, add a one with assert(false) to declare that that case is unreachable.

[kevinwkt]

Max's changes

[metzman]

Just one question

lib/fuzzer/FuzzerTracePC.cpp

64–65

I'm a bit confused, why not make use of the 0th element in UnstableCounters?

[kevinwkt]

lib/fuzzer/FuzzerTracePC.cpp

64–65

I based this method off of UpdateObservedPCs() in FuzzerTracePC.cpp.
In line 206, they also utilize GuardIdx starting from 1.

[metzman]

Please run clang-format as you agreed to do, it's giving me some small formatting changes for this patch.

FYI, I used clang-format-diff.py since it will format just the code you added rather than everything.

lib/fuzzer/FuzzerTracePC.cpp

64–65

OK. SGTM.
The space wasn't a concern to me by the way. It just looked confusing.

[Dor1s]

I'd also recommend to make the CL summary and description a bit more verbose. Just think about it in a way that any other LLVM developer who was not reviewing the CL would still be able to get an idea on what's going on by just reading the summary and the description. I apologize for being selfish, but you can take a look at some of my CLs descriptions as an example:

• https://reviews.llvm.org/rL333034
• https://reviews.llvm.org/rL331801

[kevinwkt]

Updated with clang-format-diff.

[metzman]

Commit message needs tweaking.

we run the unstable checks 2 more times

What are "the unstable checks"? Just say we run it two more times.

In program termination, we run PrintUnstableStats() which will print a line with a stability percentage like AFL does.

In->On

I would leave out details about the test

[Dor1s]

Also update the title to something like "[libFuzzer] Implement stat::stability_rate based on the percentage of unstable edges."

lib/fuzzer/FuzzerTracePC.cpp

357

Please remove %%. Other stats do not print any units, just a number, so let's keep it consistent. That would also allow us to get this stat collected by CF and stored in BigQuery without any modifications, I believe.

test/fuzzer/print_unstable_stats.test

7

Don't forget to fix the test as well when you remove %%.

[kevinwkt]

Removed %% from the stat print.

[Dor1s]

Please ask @morehouse and @kcc to review. I'd be happy to land the change after their approval.

[morehouse]

lib/fuzzer/FuzzerLoop.cpp

449

Should probably put ScopedEnableMsanInterceptorChecks S; at the beginning of this function, since that might cause different coverage now that we have it in ExecuteCallback.

468

Too much vertical whitespace here. Let's condense things a bit.

lib/fuzzer/FuzzerTracePC.cpp

64–65

The index should start at 0. The only reason GuardIdx starts at 1 is because pc-guards reserve the value 0 to disable the guard. But you're using the inline counters instead.

65

I think you also need to check that NumPCsInPCTables or NumInline8bitCounters are non-zero. Because the current condition will probably be true when using pc-guards.

(Here and below)

89

The second condition is pointless.

Essentially you're doing:

if (x != 5)
  x = 5;

test/fuzzer/print_unstable_stats.test

2

-fsanitize=fuzzer is unnecessary here. It is already built into the %cpp_compiler macro.

6

What's coverage_dir used for?

[kevinwkt]

Fixed UnstableIdx to start from 1 to 0
Erased Whitelines.

[morehouse]

lib/fuzzer/FuzzerTracePC.cpp

65

The style libFuzzer generally follows is:

if (NumInline8bitCounters && ...)

(here and below)

[kevinwkt]

Changed formatting for libFuzzer

[Dor1s]

Rebase on the ToT and getting ready to commit.

[Dor1s]

Reverted in https://reviews.llvm.org/rCRT337180.

[Dor1s]

Kevin, it looks like you've applied clang-format (not clang-format-diff) on Friday and that has introduced a bunch of unnecessary changes. Click on "History" in "Revision Contents" table, then change "Whitespace Changes" listbox to "Show All" in the bottom: https://reviews.llvm.org/D49212?vs=on&id=155681&whitespace=show-all#toc

I'll clean those up for you and re-land the CL, but please be more careful next time. One more sanity check you could do locally is to run svn diff | colordiff and quickly inspect the diff you're about to upload for review.

[Dor1s]

Remove unintentional format changes

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;
   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(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.")

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.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 = [&]() {
+    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
+  TPC.InitializeUnstableCounters();
+
+  // First Rerun
+  CBSetupAndRun();
+
+  TPC.UpdateUnstableCounters();
+
+  // Second Rerun
+  CBSetupAndRun();
+
+  TPC.UpdateUnstableCounters();
+}
+
 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();
   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 print_unstable_stats, execute the same input two more times to detect
+  // unstable edges.
+  if (NumNewFeatures && Options.PrintUnstableStats)
+    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 {
   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;
   bool DumpCoverage = false;
   bool DetectLeaks = true;
   int PurgeAllocatorIntervalSec = 1;
   int  TraceMalloc = 0;
   bool HandleAbrt = false;
   bool HandleBus = false;
   bool HandleFpe = false;
   bool HandleIll = false;

lib/fuzzer/FuzzerTracePC.h

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();
+  void UpdateUnstableCounters();
+
 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++)
+        if (UnstableCounters[UnstableIdx] != kUnstableCounter)
+          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] != kUnstableCounter)
+          UnstableCounters[UnstableIdx] = kUnstableCounter;
+    }
+  }
+}
 
 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::PrintUnstableStats() {
+  int count = 0;
+  for (unsigned int i = 1; i <= NumInline8bitCounters; i++)
+    if (UnstableCounters[i] == kUnstableCounter)
+      count++;
+  Printf("Stability rate is at %.2lf%%\n", 100 - static_cast<double>(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.
 // The interesting value is mixed up with the PC and is then added to the map.
 
 ATTRIBUTE_NO_SANITIZE_ALL
 void TracePC::AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
                                 size_t n, bool StopAtZero) {
   if (!n) return;

test/fuzzer/PrintUnstableStatsTest.cpp

+#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() { x++; }
+__attribute__((noinline))
+  void t1() { x++; }
+__attribute__((noinline))
+  void t2() { x++; }
+__attribute__((noinline))
+  void t3() { x++; }
+__attribute__((noinline))
+  void t4() { x++; }
+
+  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();
+        break;
+      case 1:
+        t1();
+        break;
+      case 2:
+        t2();
+        break;
+      case 3:
+        t3();
+        break;
+      default:
+        t4();
+        break;
+    }
+
+    det3();
+    det4();
+
+    return 0;
+  }

test/fuzzer/print_unstable_stats.test

+RUN: %cpp_compiler -fsanitize=fuzzer  %S/PrintUnstableStatsTest.cpp -o %t-PrintUnstableStatsTest
+
+RUN: rm -rf %t_workdir && mkdir -p %t_workdir
+
+RUN: env ASAN_OPTIONS=coverage_dir='"%t_workdir"' %run %t-PrintUnstableStatsTest -print_unstable_stats=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=LONG
+LONG: Stability rate is at 27.59%