[libFuzzer] Evenly select inputs to cross over with from the corpus regardless of the input's coverage.

[dokyungs]

Summary

This patch adds an option "cross_over_uniform_dist", which, if 1, utilizes all
inputs in the corpus for the crossover mutation. More specifically, this patch
uses a uniform distribution of all inputs in the corpus for the CrossOver input
selection. Note that input selection for mutation is still fully determined by
the scheduling policy (i.e., vanilla or Entropic); the uniform distribution only
applies to the secondary input selection, only for the crossover mutation of the
base input chosen by the scheduling policy. This way the corpus inputs that have
useful fragments in them, even though they are deprioritized by the scheduling
policy, have chances of getting mixed with other inputs that are prioritized and
selected as base input for mutation.

[dokyungs]

compiler-rt/test/fuzzer/cross_over_uniform_dist.test

3

Will revisit this test after getting the keep seed patch upstreamed.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerFlags.def

32

Please also document when this is useful.

[hctim]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

274–279

nit: short branch first:

if (!UniformDist)
  return ChooseUnitToMutate(Rand);
...

[dokyungs]

Addressed comments.

[hctim]

LGTM (after the keep_seed patch lands)

[morehouse]

Please make sure the harbormaster test passes before landing.

[dokyungs]

Fix cross_over_uniform_dist.test. If -cross_over_uniform_dist=1, it takes 766,756 execs to find the crash; if 0, it takes more than 2,000,000 execs to find the crash.

[dokyungs]

Try adding double-quotes around seed input string being echoed.

[dokyungs]

Adjust the test - make sure corpus/B input does not discover any more coverage than corpus/A, so that it's not scheduled for mutation even with -keep_seed=1. Only with uniform distribution. corpus/B has chances of getting crossed over with.

compiler-rt/lib/fuzzer/FuzzerCorpus.h

public:
   bool HasUnit(const Unit &U) { return Hashes.count(Hash(U)); }
   bool HasUnit(const std::string &H) { return Hashes.count(H); }
   InputInfo &ChooseUnitToMutate(Random &Rand) {
     InputInfo &II = *Inputs[ChooseUnitIdxToMutate(Rand)];
     assert(!II.U.empty());
     return II;
   }
 
+  InputInfo &ChooseUnitToCrossOverWith(Random &Rand, bool UniformDist) {
+    if (!UniformDist) {
+      return ChooseUnitToMutate(Rand);
+    }
+    InputInfo &II = *Inputs[Rand(Inputs.size())];
+    assert(!II.U.empty());
+    return II;
+  }
+
   // Returns an index of random unit from the corpus to mutate.
   size_t ChooseUnitIdxToMutate(Random &Rand) {
     UpdateCorpusDistribution(Rand);
     size_t Idx = static_cast<size_t>(CorpusDistribution(Rand));
     assert(Idx < Inputs.size());
     return Idx;
   }
 

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
   Options.UnitTimeoutSec = Flags.timeout;
   Options.ErrorExitCode = Flags.error_exitcode;
   Options.TimeoutExitCode = Flags.timeout_exitcode;
   Options.IgnoreTimeouts = Flags.ignore_timeouts;
   Options.IgnoreOOMs = Flags.ignore_ooms;
   Options.IgnoreCrashes = Flags.ignore_crashes;
   Options.MaxTotalTimeSec = Flags.max_total_time;
   Options.DoCrossOver = Flags.cross_over;
+  Options.CrossOverUniformDist = Flags.cross_over_uniform_dist;
   Options.MutateDepth = Flags.mutate_depth;
   Options.ReduceDepth = Flags.reduce_depth;
   Options.UseCounters = Flags.use_counters;
   Options.UseMemmem = Flags.use_memmem;
   Options.UseCmp = Flags.use_cmp;
   Options.UseValueProfile = Flags.use_value_profile;
   Options.Shrink = Flags.shrink;
   Options.ReduceInputs = Flags.reduce_inputs;

compiler-rt/lib/fuzzer/FuzzerFlags.def

 FUZZER_FLAG_STRING(seed_inputs, "A comma-separated list of input files "
   "to use as an additional seed corpus. Alternatively, an \"@\" followed by "
   "the name of a file containing the comma-separated list.")
 FUZZER_FLAG_INT(keep_seed, 0, "If 1, keep seed inputs in the corpus even if "
   "they do not produce new coverage. When used with |reduce_inputs==1|, the "
   "seed inputs will never be reduced. This option can be useful when seeds are"
   "not properly formed for the fuzz target but still have useful snippets.")
 FUZZER_FLAG_INT(cross_over, 1, "If 1, cross over inputs.")
+FUZZER_FLAG_INT(cross_over_uniform_dist, 0, "Experimental. If 1, use a "
+  "uniform probability distribution when choosing inputs to cross over with. "
+  "Some of the inputs in the corpus may never get chosen for mutation "
+  "depending on the input mutation scheduling policy. With this flag, all "
+  "inputs, regardless of the input mutation scheduling policy, can be chosen "
+  "as an input to cross over with. This can be particularly useful with "
+  "|keep_seed==1|; all the initial seed inputs, even though they do not "
+  "increase coverage because they are not properly formed, will still be "
+  "chosen as an input to cross over with.")
+
 FUZZER_FLAG_INT(mutate_depth, 5,
             "Apply this number of consecutive mutations to each input.")
 FUZZER_FLAG_INT(reduce_depth, 0, "Experimental/internal. "
                 "Reduce depth if mutations lose unique features")
 FUZZER_FLAG_INT(shuffle, 1, "Shuffle inputs at startup")
 FUZZER_FLAG_INT(prefer_small, 1,
     "If 1, always prefer smaller inputs during the corpus shuffle.")
 FUZZER_FLAG_INT(

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

if (EF->__lsan_do_recoverable_leak_check()) { // Leak is found, report it.
     _Exit(Options.ErrorExitCode); // not exit() to disable lsan further on.
   }
 }
 
 void Fuzzer::MutateAndTestOne() {
   MD.StartMutationSequence();
 
   auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
-  if (Options.DoCrossOver)
-    MD.SetCrossOverWith(&Corpus.ChooseUnitToMutate(MD.GetRand()).U);
+  if (Options.DoCrossOver) {
+    auto &CrossOverII = Corpus.ChooseUnitToCrossOverWith(
+        MD.GetRand(), Options.CrossOverUniformDist);
+    MD.SetCrossOverWith(&CrossOverII.U);
+  }
   const auto &U = II.U;
   memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
   assert(CurrentUnitData);
   size_t Size = U.size();
   assert(Size <= MaxInputLen && "Oversized Unit");
   memcpy(CurrentUnitData, U.data(), Size);
 
   assert(MaxMutationLen > 0);

compiler-rt/lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   int ErrorExitCode = 77;
   bool IgnoreTimeouts = true;
   bool IgnoreOOMs = true;
   bool IgnoreCrashes = false;
   int MaxTotalTimeSec = 0;
   int RssLimitMb = 0;
   int MallocLimitMb = 0;
   bool DoCrossOver = true;
+  bool CrossOverUniformDist = false;
   int MutateDepth = 5;
   bool ReduceDepth = false;
   bool UseCounters = false;
   bool UseMemmem = true;
   bool UseCmp = false;
   int UseValueProfile = false;
   bool Shrink = false;
   bool ReduceInputs = false;

compiler-rt/test/fuzzer/cross_over_uniform_dist.test

+REQUIRES: linux, x86_64
+RUN: %cpp_compiler %S/KeepSeedTest.cpp -o %t-CrossOverUniformDistTest
+
+RUN: rm -rf %t-corpus
+RUN: mkdir %t-corpus
+RUN: echo -n "@SELECT" > %t-corpus/A
+RUN: echo -n "@FROM WHERE" > %t-corpus/B
+
+RUN: not %run %t-CrossOverUniformDistTest -keep_seed=1 -cross_over_uniform_dist=1 -seed=1 -runs=2000000 %t-corpus 2>&1 | FileCheck %s
+CHECK: BINGO
+
+RUN: rm -rf %t-corpus
+RUN: mkdir %t-corpus
+RUN: echo -n "@SELECT" > %t-corpus/A
+RUN: echo -n "@FROM WHERE" > %t-corpus/B
+RUN: %run %t-CrossOverUniformDistTest -keep_seed=1 -seed=1 -runs=2000000 %t-corpus 2>&1