Index: lib/Fuzzer/FuzzerDriver.cpp =================================================================== --- lib/Fuzzer/FuzzerDriver.cpp +++ lib/Fuzzer/FuzzerDriver.cpp @@ -330,6 +330,7 @@ Options.SaveArtifacts = !DoPlainRun; Options.PrintNewCovPcs = Flags.print_new_cov_pcs; Options.PrintFinalStats = Flags.print_final_stats; + Options.TruncateUnits = Flags.truncate_units; unsigned Seed = Flags.seed; // Initialize Seed. Index: lib/Fuzzer/FuzzerFlags.def =================================================================== --- lib/Fuzzer/FuzzerFlags.def +++ lib/Fuzzer/FuzzerFlags.def @@ -84,6 +84,7 @@ "try to detect memory leaks during fuzzing (i.e. not only at shut down).") FUZZER_FLAG_INT(rss_limit_mb, 2048, "If non-zero, the fuzzer will exit upon" "reaching this limit of RSS memory usage.") +FUZZER_FLAG_INT(truncate_units, 1, "Try truncated units when loading corpus.") FUZZER_DEPRECATED_FLAG(exit_on_first) FUZZER_DEPRECATED_FLAG(save_minimized_corpus) Index: lib/Fuzzer/FuzzerInternal.h =================================================================== --- lib/Fuzzer/FuzzerInternal.h +++ lib/Fuzzer/FuzzerInternal.h @@ -317,6 +317,7 @@ bool PrintNewCovPcs = false; bool PrintFinalStats = false; bool DetectLeaks = true; + bool TruncateUnits = true; }; // Aggregates all available coverage measurements. @@ -354,6 +355,7 @@ } size_t ChooseUnitIdxToMutate(); const Unit &ChooseUnitToMutate() { return Corpus[ChooseUnitIdxToMutate()]; }; + void TruncateUnits(std::vector *NewCorpus); void Loop(); void Drill(); void ShuffleAndMinimize(); @@ -396,6 +398,9 @@ void SetMaxLen(size_t MaxLen); void RssLimitCallback(); + // Public for tests. + void ResetCoverage(); + private: void AlarmCallback(); void CrashCallback(); @@ -416,7 +421,6 @@ // Must be called whenever the corpus or unit weights are changed. void UpdateCorpusDistribution(); - void ResetCoverage(); bool UpdateMaxCoverage(); // Trace-based fuzzing: we run a unit with some kind of tracing Index: lib/Fuzzer/FuzzerLoop.cpp =================================================================== --- lib/Fuzzer/FuzzerLoop.cpp +++ lib/Fuzzer/FuzzerLoop.cpp @@ -59,6 +59,7 @@ namespace fuzzer { static const size_t kMaxUnitSizeToPrint = 256; +static const size_t TruncateMaxRuns = 1000; static void MissingWeakApiFunction(const char *FnName) { Printf("ERROR: %s is not defined. Exiting.\n" @@ -353,12 +354,55 @@ }); } +// Tries random prefixes of corpus items. +// Prefix length is chosen according to exponential distribution +// to sample short lengths much more heavily. +void Fuzzer::TruncateUnits(std::vector *NewCorpus) { + size_t MaxCorpusLen = 0; + for (const auto &U : Corpus) { + MaxCorpusLen = std::max(MaxCorpusLen, U.size()); + } + + if (MaxCorpusLen <= 1) + return; + + // 50% of exponential distribution is Log[2]/lambda. + // Choose lambda so that median is MaxCorpusLen / 2. + double Lambda = 2.0 * log(2.0) / static_cast(MaxCorpusLen); + std::exponential_distribution<> Dist(Lambda); + std::vector Sizes; + size_t TruncatePoints = std::max(1ul, TruncateMaxRuns / Corpus.size()); + Sizes.reserve(TruncatePoints); + for (size_t I = 0; I < TruncatePoints; ++I) { + Sizes.push_back(Dist(MD.GetRand().Get_mt19937()) + 1); + } + std::sort(Sizes.begin(), Sizes.end()); + + for (size_t S : Sizes) { + for (const auto &U : Corpus) { + if (S < U.size() && RunOne(U.data(), S)) { + Unit U1(U.begin(), U.begin() + S); + NewCorpus->push_back(U1); + WriteToOutputCorpus(U1); + PrintStatusForNewUnit(U1); + } + } + } + PrintStats("TRUNC "); +} + void Fuzzer::ShuffleAndMinimize() { PrintStats("READ "); std::vector NewCorpus; if (Options.ShuffleAtStartUp) ShuffleCorpus(&Corpus); + if (Options.TruncateUnits) { + ResetCoverage(); + TruncateUnits(&NewCorpus); + ResetCoverage(); + } + for (const auto &U : Corpus) { if (RunOne(U)) { NewCorpus.push_back(U); Index: lib/Fuzzer/test/FuzzerUnittest.cpp =================================================================== --- lib/Fuzzer/test/FuzzerUnittest.cpp +++ lib/Fuzzer/test/FuzzerUnittest.cpp @@ -13,6 +13,10 @@ abort(); } +extern "C" int EmptyLLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + return 0; +} + TEST(Fuzzer, CrossOver) { Random Rand(0); MutationDispatcher MD(Rand); @@ -423,3 +427,21 @@ EXPECT_GT(Hist[i], TriesPerUnit / N / 3); } } + +TEST(Corpus, TruncateUnits) { + Random Rand(0); + MutationDispatcher MD(Rand); + Fuzzer::FuzzingOptions Options; + Options.OutputCorpus = ""; // stops from writing new units. + Fuzzer Fuzz(EmptyLLVMFuzzerTestOneInput, MD, Options); + + Fuzz.AddToCorpus(Unit(1024, static_cast(1))); + Fuzz.ResetCoverage(); + + std::vector NewCorpus; + Fuzz.TruncateUnits(&NewCorpus); + + // New corpus should have a shorter unit. + EXPECT_EQ(1ul, NewCorpus.size()); + EXPECT_EQ(1ul, NewCorpus[0].size()); +}