[libfuzzer] Trying random unit prefixes during corpus load.

[aizatsky]

format.

[kcc]

I wonder if it makes sense to add a test here?

lib/Fuzzer/FuzzerLoop.cpp

360 ↗

(On Diff #57401)

didn't you want to flush the coverage here?

382 ↗

(On Diff #57401)

S < U.size() ?

[vitalybuka]

lib/Fuzzer/FuzzerLoop.cpp

382 ↗

(On Diff #57401)

Probably unimportant here.

[aizatsky]

fuzzer unit test.

[aizatsky]

reset coverage.

[aizatsky]

Added test and limited the number of truncation points. PTAL.

[kcc]

lib/Fuzzer/FuzzerFlags.def

87 ↗

(On Diff #58150)

I'd prefer to have this flag of by default for now

lib/Fuzzer/FuzzerLoop.cpp

362 ↗

(On Diff #58150)

no {}, same below

379 ↗

(On Diff #58150)

do you expect duplicates here?

lib/Fuzzer/test/FuzzerUnittest.cpp

16 ↗

(On Diff #58150)

make it static and not extern "C"

[aizatsky]

review

lib/Fuzzer/FuzzerLoop.cpp

379 ↗

(On Diff #58150)

There might be, but I don't really care. For big corpus there would be only one point.

[kcc]

LGTM, ok as an off-by-default feature.
I am still not convinced it's good enough yet, will need to play and see.
Some things to check:

• are there many duplicate sizes?
• will this blow up the corpus too much?

[aizatsky]

My plan is to enable it for fuzzer in chrome with big units and see if units get smaller over time.

llvm/trunk/lib/Fuzzer/FuzzerDriver.cpp

if (Flags.dict)
     if (!ParseDictionaryFile(FileToString(Flags.dict), &Dictionary))
       return 1;
   if (Flags.verbosity > 0 && !Dictionary.empty())
     Printf("Dictionary: %zd entries\n", Dictionary.size());
   bool DoPlainRun = AllInputsAreFiles();
   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.
   if (Seed == 0)
     Seed = (std::chrono::system_clock::now().time_since_epoch().count() << 10) +
            getpid();
   if (Flags.verbosity)
     Printf("INFO: Seed: %u\n", Seed);

llvm/trunk/lib/Fuzzer/FuzzerFlags.def

 FUZZER_FLAG_INT(handle_term, 1, "If 1, try to intercept SIGTERM.")
 FUZZER_FLAG_INT(close_fd_mask, 0, "If 1, close stdout at startup; "
     "if 2, close stderr; if 3, close both. "
     "Be careful, this will also close e.g. asan's stderr/stdout.")
 FUZZER_FLAG_INT(detect_leaks, 1, "If 1, and if LeakSanitizer is enabled "
     "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, 0, "Try truncated units when loading corpus.")
 
 FUZZER_DEPRECATED_FLAG(exit_on_first)
 FUZZER_DEPRECATED_FLAG(save_minimized_corpus)
 FUZZER_DEPRECATED_FLAG(sync_command)
 FUZZER_DEPRECATED_FLAG(sync_timeout)
 FUZZER_DEPRECATED_FLAG(test_single_input)

llvm/trunk/lib/Fuzzer/FuzzerInternal.h

struct FuzzingOptions {
     std::string ArtifactPrefix = "./";
     std::string ExactArtifactPath;
     bool SaveArtifacts = true;
     bool PrintNEW = true; // Print a status line when new units are found;
     bool OutputCSV = false;
     bool PrintNewCovPcs = false;
     bool PrintFinalStats = false;
     bool DetectLeaks = true;
+    bool TruncateUnits = false;
   };
 
   // Aggregates all available coverage measurements.
   struct Coverage {
     Coverage() { Reset(); }
 
     void Reset() {
       BlockCoverage = 0;
public:
 
   Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options);
   void AddToCorpus(const Unit &U) {
     Corpus.push_back(U);
     UpdateCorpusDistribution();
   }
   size_t ChooseUnitIdxToMutate();
   const Unit &ChooseUnitToMutate() { return Corpus[ChooseUnitIdxToMutate()]; };
+  void TruncateUnits(std::vector<Unit> *NewCorpus);
   void Loop();
   void Drill();
   void ShuffleAndMinimize();
   void InitializeTraceState();
   void AssignTaintLabels(uint8_t *Data, size_t Size);
   size_t CorpusSize() const { return Corpus.size(); }
   size_t MaxUnitSizeInCorpus() const;
   void ReadDir(const std::string &Path, long *Epoch, size_t MaxSize) {
public:
   void Merge(const std::vector<std::string> &Corpora);
   // Returns a subset of 'Extra' that adds coverage to 'Initial'.
   UnitVector FindExtraUnits(const UnitVector &Initial, const UnitVector &Extra);
   MutationDispatcher &GetMD() { return MD; }
   void PrintFinalStats();
   void SetMaxLen(size_t MaxLen);
   void RssLimitCallback();
 
+  // Public for tests.
+  void ResetCoverage();
+
 private:
   void AlarmCallback();
   void CrashCallback();
   void InterruptCallback();
   void MutateAndTestOne();
   void ReportNewCoverage(const Unit &U);
   bool RunOne(const Unit &U) { return RunOne(U.data(), U.size()); }
   void RunOneAndUpdateCorpus(uint8_t *Data, size_t Size);
   void WriteToOutputCorpus(const Unit &U);
   void WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix);
   void PrintStats(const char *Where, const char *End = "\n");
   void PrintStatusForNewUnit(const Unit &U);
   void ShuffleCorpus(UnitVector *V);
   void TryDetectingAMemoryLeak(uint8_t *Data, size_t Size);
   void CheckForMemoryLeaks();
 
   // Updates the probability distribution for the units in the corpus.
   // 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
   // enabled and record potentially useful mutations. Then
   // We apply these mutations one by one to the unit and run it again.
 
   // Start tracing; forget all previously proposed mutations.
   void StartTraceRecording();

llvm/trunk/lib/Fuzzer/FuzzerLoop.cpp

 __attribute__((weak)) void __sanitizer_free_hook(void *ptr);
 __attribute__((weak)) void __lsan_enable();
 __attribute__((weak)) void __lsan_disable();
 __attribute__((weak)) int __lsan_do_recoverable_leak_check();
 }
 
 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"
          "Did you use -fsanitize-coverage=... to build your code?\n",
          FnName);
   exit(1);
 }
 

 void Fuzzer::ShuffleCorpus(UnitVector *V) {
   std::random_shuffle(V->begin(), V->end(), MD.GetRand());
   if (Options.PreferSmall)
     std::stable_sort(V->begin(), V->end(), [](const Unit &A, const Unit &B) {
       return A.size() < B.size();
     });
 }
 
+// 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<Unit> *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<double>(MaxCorpusLen);
+  std::exponential_distribution<> Dist(Lambda);
+  std::vector<double> 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<Unit> 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);
       if (Options.Verbosity >= 2)
         Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size());
     }
   }
   Corpus = NewCorpus;

llvm/trunk/lib/Fuzzer/test/FuzzerUnittest.cpp

 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 
 #include "FuzzerInternal.h"
 #include "gtest/gtest.h"
 #include <set>
 
 using namespace fuzzer;
 
 // For now, have LLVMFuzzerTestOneInput just to make it link.
 // Later we may want to make unittests that actually call LLVMFuzzerTestOneInput.
 extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
   abort();
 }
 
+static int EmptyLLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  return 0;
+}
+
 TEST(Fuzzer, CrossOver) {
   Random Rand(0);
   MutationDispatcher MD(Rand);
   Unit A({0, 1, 2}), B({5, 6, 7});
   Unit C;
   Unit Expected[] = {
        { 0 },
        { 0, 1 },
TEST(Corpus, Distribution) {
   for (size_t i = 0; i < N * TriesPerUnit; i++) {
     Hist[Fuzz.ChooseUnitIdxToMutate()]++;
   }
   for (size_t i = 0; i < N; i++) {
     // A weak sanity check that every unit gets invoked.
     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<uint8_t>(1)));
+  Fuzz.ResetCoverage();
+
+  std::vector<Unit> NewCorpus;
+  Fuzz.TruncateUnits(&NewCorpus);
+
+  // New corpus should have a shorter unit.
+  EXPECT_EQ(1ul, NewCorpus.size());
+  EXPECT_EQ(1ul, NewCorpus[0].size());
+}