From b53243e19496ae59ae1ce457a40e3ea610011fd1 Mon Sep 17 00:00:00 2001 From: Dokyung Song Date: Tue, 1 Sep 2020 16:22:59 +0000 Subject: [PATCH] [libFuzzer] Evenly select inputs to cross over with from the corpus regardless of the input's coverage. This patch adds an option "cross_over_uniform_dist", which, if 1, considers all inputs in the corpus for the crossover input selection. 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. Differential Revision: https://reviews.llvm.org/D86954 --- compiler-rt/lib/fuzzer/FuzzerCorpus.h | 9 +++++++++ compiler-rt/lib/fuzzer/FuzzerDriver.cpp | 1 + compiler-rt/lib/fuzzer/FuzzerFlags.def | 10 ++++++++++ compiler-rt/lib/fuzzer/FuzzerLoop.cpp | 7 +++++-- compiler-rt/lib/fuzzer/FuzzerOptions.h | 1 + compiler-rt/test/fuzzer/cross_over_uniform_dist.test | 16 ++++++++++++++++ 6 files changed, 42 insertions(+), 2 deletions(-) create mode 100644 compiler-rt/test/fuzzer/cross_over_uniform_dist.test diff --git a/compiler-rt/lib/fuzzer/FuzzerCorpus.h b/compiler-rt/lib/fuzzer/FuzzerCorpus.h index fd8ff6c..6b45d37 100644 --- a/compiler-rt/lib/fuzzer/FuzzerCorpus.h +++ b/compiler-rt/lib/fuzzer/FuzzerCorpus.h @@ -270,6 +270,15 @@ public: 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); diff --git a/compiler-rt/lib/fuzzer/FuzzerDriver.cpp b/compiler-rt/lib/fuzzer/FuzzerDriver.cpp index a13fb03..93b1ff6 100644 --- a/compiler-rt/lib/fuzzer/FuzzerDriver.cpp +++ b/compiler-rt/lib/fuzzer/FuzzerDriver.cpp @@ -680,6 +680,7 @@ int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) { 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; diff --git a/compiler-rt/lib/fuzzer/FuzzerFlags.def b/compiler-rt/lib/fuzzer/FuzzerFlags.def index 1dc805d..5194666 100644 --- a/compiler-rt/lib/fuzzer/FuzzerFlags.def +++ b/compiler-rt/lib/fuzzer/FuzzerFlags.def @@ -28,6 +28,16 @@ FUZZER_FLAG_INT(keep_seed, 0, "If 1, keep seed inputs in the corpus even if " "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. " diff --git a/compiler-rt/lib/fuzzer/FuzzerLoop.cpp b/compiler-rt/lib/fuzzer/FuzzerLoop.cpp index d76075b..f97b4d2 100644 --- a/compiler-rt/lib/fuzzer/FuzzerLoop.cpp +++ b/compiler-rt/lib/fuzzer/FuzzerLoop.cpp @@ -666,8 +666,11 @@ 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); diff --git a/compiler-rt/lib/fuzzer/FuzzerOptions.h b/compiler-rt/lib/fuzzer/FuzzerOptions.h index 26961973..281658d 100644 --- a/compiler-rt/lib/fuzzer/FuzzerOptions.h +++ b/compiler-rt/lib/fuzzer/FuzzerOptions.h @@ -31,6 +31,7 @@ struct FuzzingOptions { int RssLimitMb = 0; int MallocLimitMb = 0; bool DoCrossOver = true; + bool CrossOverUniformDist = false; int MutateDepth = 5; bool ReduceDepth = false; bool UseCounters = false; diff --git a/compiler-rt/test/fuzzer/cross_over_uniform_dist.test b/compiler-rt/test/fuzzer/cross_over_uniform_dist.test new file mode 100644 index 0000000..0dff5fd --- /dev/null +++ b/compiler-rt/test/fuzzer/cross_over_uniform_dist.test @@ -0,0 +1,16 @@ +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 -- 2.7.4