[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

didn't you want to flush the coverage here?

382

S < U.size() ?

[vitalybuka]

lib/Fuzzer/FuzzerLoop.cpp

382

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

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

lib/Fuzzer/FuzzerLoop.cpp

362

no {}, same below

379

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

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.

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);

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, 1, "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)

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 = true;
   };
 
   // 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) {

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 TruncatePoints = 100;
 
 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;
+  Sizes.reserve(TruncatePoints);
+  for (size_t I = 0; I < TruncatePoints; ++I) {
+    Sizes.push_back(Dist(MD.GetRand().Get_mt19937()));
+  }
+  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)
+    TruncateUnits(&NewCorpus);
+
   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;
   UpdateCorpusDistribution();
   for (auto &X : Corpus)
     UnitHashesAddedToCorpus.insert(Hash(X));
   PrintStats("INITED");
   CheckForMemoryLeaks();
 }
 
+
 bool Fuzzer::UpdateMaxCoverage() {
   uintptr_t PrevBufferLen = MaxCoverage.PcBufferLen;
   bool Res = CoverageController::RecordMax(Options, &MaxCoverage);
 
   if (Options.PrintNewCovPcs && PrevBufferLen != MaxCoverage.PcBufferLen) {
     uintptr_t *CoverageBuf;
     __sanitizer_get_coverage_pc_buffer(&CoverageBuf);
     assert(CoverageBuf);