[libFuzzer] Adds experimental flag -ngram that changes the fuzzer fitness function

[bshastry]

Summary

At the moment, PC guards (CFG edge hit counters) are used to select interesting fuzzer mutations. This patch allows the user to specify an optional -ngram=k (an integer that defaults to 1 i.e., vanilla libFuzzer) that uses an XOR of "k" previous PC guards encountered for selecting interesting mutations.

Requires a/b testing to qualify merit of patch.

[kcc]

I am indeed interested in experimenting with bounded path coverage, similar to this.
My prior experiments demonstrated some value but also huge corpus expansion (bad).
It might be worth submitting something like this to simplify further experiments.

FuzzerTracePC.cpp

380

By default, we don't use trace_pc_guard any more -- we have switched to the inline instrumentation https://clang.llvm.org/docs/SanitizerCoverage.html#inline-8bit-counters
So, this logic needs to be moved there. Consider trace_pc_guard is not used any more.

385

This is even less friendly to multi-threaded code than the current tracing.

387

please try to format the code as the rest of the code in these files.
Also, I recommend using clang-format on the changed lines (don't reformat the entire file, just the changes).

FuzzerTracePC.h

75

constants start with 'k'
e.g. kMaxNGram

88

Ngram = Min(N, kMaxNGram)

FuzzerDriver.cpp

if (Flags.jobs > 0 && Flags.workers == 0) {
     if (Flags.workers > 1)
       Printf("Running %u workers\n", Flags.workers);
   }
 
   if (Flags.workers > 0 && Flags.jobs > 0)
     return RunInMultipleProcesses(Args, Flags.workers, Flags.jobs);
 
   FuzzingOptions Options;
+  Options.Ngram = Flags.ngram;
+  if (Options.Ngram > 1)
+    TPC.SetNgram(Options.Ngram);
+
   Options.Verbosity = Flags.verbosity;
   Options.MaxLen = Flags.max_len;
   Options.LenControl = Flags.len_control;
   Options.UnitTimeoutSec = Flags.timeout;
   Options.ErrorExitCode = Flags.error_exitcode;
   Options.TimeoutExitCode = Flags.timeout_exitcode;
   Options.MaxTotalTimeSec = Flags.max_total_time;
   Options.DoCrossOver = Flags.cross_over;

FuzzerFlags.def

FUZZER_FLAG_INT(ignore_remaining_args, 0, "If 1, ignore all arguments passed "
                 "after this one. Useful for fuzzers that need to do their own "
                 "argument parsing.")
 
 FUZZER_FLAG_STRING(run_equivalence_server, "Experimental")
 FUZZER_FLAG_STRING(use_equivalence_server, "Experimental")
 FUZZER_FLAG_INT(analyze_dict, 0, "Experimental")
 FUZZER_FLAG_INT(use_clang_coverage, 0, "Experimental")
 FUZZER_FLAG_INT(use_feature_frequency, 0, "Experimental/internal")
+FUZZER_FLAG_INT(ngram, 1, "Experimental. Use ngram of PCs.")
+

FuzzerOptions.h

struct FuzzingOptions {
   bool Shrink = false;
   bool ReduceInputs = false;
   int ReloadIntervalSec = 1;
   bool ShuffleAtStartUp = true;
   bool PreferSmall = true;
   size_t MaxNumberOfRuns = -1L;
   int ReportSlowUnits = 10;
   bool OnlyASCII = false;
+  int Ngram = 1;
   std::string OutputCorpus;
   std::string ArtifactPrefix = "./";
   std::string ExactArtifactPath;
   std::string ExitOnSrcPos;
   std::string ExitOnItem;
   bool SaveArtifacts = true;
   bool PrintNEW = true; // Print a status line when new units are found;
   bool PrintNewCovPcs = false;

FuzzerTracePC.h

struct MemMemTable {
   }
 };
 
 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;
+  static const uint8_t nGramMax = 1 << 7;
+  uint8_t Ngram = 1;
 
   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 SetUseClangCoverage(bool UCC) { UseClangCoverage = UCC; }
   void SetUseValueProfile(bool VP) { UseValueProfile = VP; }
   void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; }
+  void SetNgram(uint8_t N) { if (N <= nGramMax) Ngram = N; else Ngram = nGramMax; }
   void SetPrintNewFuncs(size_t P) { NumPrintNewFuncs = P; }
   void UpdateObservedPCs();
   template <class Callback> void CollectFeatures(Callback CB) const;
 
   void ResetMaps() {
     ValueProfileMap.Reset();
     if (NumModules)
       memset(Counters(), 0, GetNumPCs());

FuzzerTracePC.cpp

 
 uintptr_t TracePC::GetMaxStackOffset() const {
   return InitialStack - __sancov_lowest_stack;  // Stack grows down
 }
 
 } // namespace fuzzer
 
 extern "C" {
+static uint32_t GuardHist[fuzzer::TracePC::nGramMax] = {0};
+static uint32_t XorState = 0;
+//static uint8_t Ngram = fuzzer::TPC.Ngram;//NGRAM_MAX;
 ATTRIBUTE_INTERFACE
 ATTRIBUTE_NO_SANITIZE_ALL
 void __sanitizer_cov_trace_pc_guard(uint32_t *Guard) {
   uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
   uint32_t Idx = *Guard;
+  uint32_t Idx8bit = Idx;
+  if (fuzzer::TPC.Ngram > 1) {
+    uint32_t Idx8bit = XorState ^ Idx;
+    XorState = XorState ^ *Guard ^ GuardHist[fuzzer::TPC.Ngram-1];
+    for (uint8_t i=fuzzer::TPC.Ngram-1; i>0;i--) GuardHist[i] = GuardHist[i-1];
+    GuardHist[0] = *Guard;
+  }
   __sancov_trace_pc_pcs[Idx] = PC;
-  __sancov_trace_pc_guard_8bit_counters[Idx]++;
+  __sancov_trace_pc_guard_8bit_counters[Idx8bit]++;
 }
 
 // Best-effort support for -fsanitize-coverage=trace-pc, which is available
 // in both Clang and GCC.
 ATTRIBUTE_INTERFACE
 ATTRIBUTE_NO_SANITIZE_ALL
 void __sanitizer_cov_trace_pc() {
   uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));