lib/Fuzzer/FuzzerLoop.cpp

   1 //===- FuzzerLoop.cpp - Fuzzer's main loop --------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // Fuzzer's main loop.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "FuzzerCorpus.h"
  13 #include "FuzzerInternal.h"
  14 #include "FuzzerIO.h"
  15 #include "FuzzerMutate.h"
  16 #include "FuzzerRandom.h"
  17 #include "FuzzerTracePC.h"
  18 #include <algorithm>
  19 #include <cstring>
  20 #include <memory>
  21 #include <set>
  22
  23 #if defined(__has_include)
  24 #if __has_include(<sanitizer / coverage_interface.h>)
  25 #include <sanitizer/coverage_interface.h>
  26 #endif
  27 #if __has_include(<sanitizer / lsan_interface.h>)
  28 #include <sanitizer/lsan_interface.h>
  29 #endif
  30 #endif
  31
  32 #define NO_SANITIZE_MEMORY
  33 #if defined(__has_feature)
  34 #if __has_feature(memory_sanitizer)
  35 #undef NO_SANITIZE_MEMORY
  36 #define NO_SANITIZE_MEMORY __attribute__((no_sanitize_memory))
  37 #endif
  38 #endif
  39
  40 namespace fuzzer {
  41 static const size_t kMaxUnitSizeToPrint = 256;
  42
  43 thread_local bool Fuzzer::IsMyThread;
  44
  45 static void MissingExternalApiFunction(const char *FnName) {
  46   Printf("ERROR: %s is not defined. Exiting.\n"
  47          "Did you use -fsanitize-coverage=... to build your code?\n",
  48          FnName);
  49   exit(1);
  50 }
  51
  52 #define CHECK_EXTERNAL_FUNCTION(fn)                                            \
  53   do {                                                                         \
  54     if (!(EF->fn))                                                             \
  55       MissingExternalApiFunction(#fn);                                         \
  56   } while (false)
  57
  58 // Only one Fuzzer per process.
  59 static Fuzzer *F;
  60
  61 void Fuzzer::ResetEdgeCoverage() {
  62   CHECK_EXTERNAL_FUNCTION(__sanitizer_reset_coverage);
  63   EF->__sanitizer_reset_coverage();
  64 }
  65
  66 void Fuzzer::ResetCounters() {
  67   if (Options.UseCounters)
  68     EF->__sanitizer_update_counter_bitset_and_clear_counters(0);
  69 }
  70
  71 void Fuzzer::PrepareCounters(Fuzzer::Coverage *C) {
  72   if (Options.UseCounters) {
  73     size_t NumCounters = EF->__sanitizer_get_number_of_counters();
  74     C->CounterBitmap.resize(NumCounters);
  75   }
  76 }
  77
  78 // Records data to a maximum coverage tracker. Returns true if additional
  79 // coverage was discovered.
  80 bool Fuzzer::RecordMaxCoverage(Fuzzer::Coverage *C) {
  81   bool Res = false;
  82
  83   uint64_t NewBlockCoverage = EF->__sanitizer_get_total_unique_coverage();
  84   if (NewBlockCoverage > C->BlockCoverage) {
  85     Res = true;
  86     C->BlockCoverage = NewBlockCoverage;
  87   }
  88
  89   if (Options.UseIndirCalls &&
  90       EF->__sanitizer_get_total_unique_caller_callee_pairs) {
  91     uint64_t NewCallerCalleeCoverage =
  92         EF->__sanitizer_get_total_unique_caller_callee_pairs();
  93     if (NewCallerCalleeCoverage > C->CallerCalleeCoverage) {
  94       Res = true;
  95       C->CallerCalleeCoverage = NewCallerCalleeCoverage;
  96     }
  97   }
  98
  99   if (Options.UseCounters) {
 100     uint64_t CounterDelta =
 101         EF->__sanitizer_update_counter_bitset_and_clear_counters(
 102             C->CounterBitmap.data());
 103     if (CounterDelta > 0) {
 104       Res = true;
 105       C->CounterBitmapBits += CounterDelta;
 106     }
 107   }
 108
 109   return Res;
 110 }
 111
 112 // Leak detection is expensive, so we first check if there were more mallocs
 113 // than frees (using the sanitizer malloc hooks) and only then try to call lsan.
 114 struct MallocFreeTracer {
 115   void Start(int TraceLevel) {
 116     this->TraceLevel = TraceLevel;
 117     if (TraceLevel)
 118       Printf("MallocFreeTracer: START\n");
 119     Mallocs = 0;
 120     Frees = 0;
 121   }
 122   // Returns true if there were more mallocs than frees.
 123   bool Stop() {
 124     if (TraceLevel)
 125       Printf("MallocFreeTracer: STOP %zd %zd (%s)\n", Mallocs.load(),
 126              Frees.load(), Mallocs == Frees ? "same" : "DIFFERENT");
 127     bool Result = Mallocs > Frees;
 128     Mallocs = 0;
 129     Frees = 0;
 130     TraceLevel = 0;
 131     return Result;
 132   }
 133   std::atomic<size_t> Mallocs;
 134   std::atomic<size_t> Frees;
 135   int TraceLevel = 0;
 136 };
 137
 138 static MallocFreeTracer AllocTracer;
 139
 140 ATTRIBUTE_NO_SANITIZE_MEMORY
 141 void MallocHook(const volatile void *ptr, size_t size) {
 142   size_t N = AllocTracer.Mallocs++;
 143   F->HandleMalloc(size);
 144   if (int TraceLevel = AllocTracer.TraceLevel) {
 145     Printf("MALLOC[%zd] %p %zd\n", N, ptr, size);
 146     if (TraceLevel >= 2 && EF)
 147       EF->__sanitizer_print_stack_trace();
 148   }
 149 }
 150
 151 ATTRIBUTE_NO_SANITIZE_MEMORY
 152 void FreeHook(const volatile void *ptr) {
 153   size_t N = AllocTracer.Frees++;
 154   if (int TraceLevel = AllocTracer.TraceLevel) {
 155     Printf("FREE[%zd]   %p\n", N, ptr);
 156     if (TraceLevel >= 2 && EF)
 157       EF->__sanitizer_print_stack_trace();
 158   }
 159 }
 160
 161 // Crash on a single malloc that exceeds the rss limit.
 162 void Fuzzer::HandleMalloc(size_t Size) {
 163   if (!Options.RssLimitMb || (Size >> 20) < (size_t)Options.RssLimitMb)
 164     return;
 165   Printf("==%d== ERROR: libFuzzer: out-of-memory (malloc(%zd))\n", GetPid(),
 166          Size);
 167   Printf("   To change the out-of-memory limit use -rss_limit_mb=<N>\n\n");
 168   if (EF->__sanitizer_print_stack_trace)
 169     EF->__sanitizer_print_stack_trace();
 170   DumpCurrentUnit("oom-");
 171   Printf("SUMMARY: libFuzzer: out-of-memory\n");
 172   PrintFinalStats();
 173   _Exit(Options.ErrorExitCode); // Stop right now.
 174 }
 175
 176 Fuzzer::Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
 177                FuzzingOptions Options)
 178     : CB(CB), Corpus(Corpus), MD(MD), Options(Options) {
 179   SetDeathCallback();
 180   InitializeTraceState();
 181   assert(!F);
 182   F = this;
 183   TPC.ResetMaps();
 184   ResetCoverage();
 185   IsMyThread = true;
 186   if (Options.DetectLeaks && EF->__sanitizer_install_malloc_and_free_hooks)
 187     EF->__sanitizer_install_malloc_and_free_hooks(MallocHook, FreeHook);
 188   TPC.SetUseCounters(Options.UseCounters);
 189   TPC.SetUseValueProfile(Options.UseValueProfile);
 190   TPC.SetPrintNewPCs(Options.PrintNewCovPcs);
 191
 192   if (Options.Verbosity)
 193     TPC.PrintModuleInfo();
 194   if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec)
 195     EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus);
 196   MaxInputLen = MaxMutationLen = Options.MaxLen;
 197   AllocateCurrentUnitData();
 198   CurrentUnitSize = 0;
 199   memset(BaseSha1, 0, sizeof(BaseSha1));
 200 }
 201
 202 Fuzzer::~Fuzzer() { }
 203
 204 void Fuzzer::AllocateCurrentUnitData() {
 205   if (CurrentUnitData || MaxInputLen == 0) return;
 206   CurrentUnitData = new uint8_t[MaxInputLen];
 207 }
 208
 209 void Fuzzer::SetDeathCallback() {
 210   CHECK_EXTERNAL_FUNCTION(__sanitizer_set_death_callback);
 211   EF->__sanitizer_set_death_callback(StaticDeathCallback);
 212 }
 213
 214 void Fuzzer::StaticDeathCallback() {
 215   assert(F);
 216   F->DeathCallback();
 217 }
 218
 219 static void WarnOnUnsuccessfullMerge(bool DoWarn) {
 220   if (!DoWarn) return;
 221   Printf(
 222    "***\n"
 223    "***\n"
 224    "***\n"
 225    "*** NOTE: merge did not succeed due to a failure on one of the inputs.\n"
 226    "*** You will need to filter out crashes from the corpus, e.g. like this:\n"
 227    "***   for f in WITH_CRASHES/*; do ./fuzzer $f && cp $f NO_CRASHES; done\n"
 228    "*** Future versions may have crash-resistant merge, stay tuned.\n"
 229    "***\n"
 230    "***\n"
 231    "***\n");
 232 }
 233
 234 void Fuzzer::DumpCurrentUnit(const char *Prefix) {
 235   WarnOnUnsuccessfullMerge(InMergeMode);
 236   if (!CurrentUnitData) return;  // Happens when running individual inputs.
 237   MD.PrintMutationSequence();
 238   Printf("; base unit: %s\n", Sha1ToString(BaseSha1).c_str());
 239   size_t UnitSize = CurrentUnitSize;
 240   if (UnitSize <= kMaxUnitSizeToPrint) {
 241     PrintHexArray(CurrentUnitData, UnitSize, "\n");
 242     PrintASCII(CurrentUnitData, UnitSize, "\n");
 243   }
 244   WriteUnitToFileWithPrefix({CurrentUnitData, CurrentUnitData + UnitSize},
 245                             Prefix);
 246 }
 247
 248 NO_SANITIZE_MEMORY
 249 void Fuzzer::DeathCallback() {
 250   DumpCurrentUnit("crash-");
 251   PrintFinalStats();
 252 }
 253
 254 void Fuzzer::StaticAlarmCallback() {
 255   assert(F);
 256   F->AlarmCallback();
 257 }
 258
 259 void Fuzzer::StaticCrashSignalCallback() {
 260   assert(F);
 261   F->CrashCallback();
 262 }
 263
 264 void Fuzzer::StaticInterruptCallback() {
 265   assert(F);
 266   F->InterruptCallback();
 267 }
 268
 269 void Fuzzer::CrashCallback() {
 270   Printf("==%lu== ERROR: libFuzzer: deadly signal\n", GetPid());
 271   if (EF->__sanitizer_print_stack_trace)
 272     EF->__sanitizer_print_stack_trace();
 273   Printf("NOTE: libFuzzer has rudimentary signal handlers.\n"
 274          "      Combine libFuzzer with AddressSanitizer or similar for better "
 275          "crash reports.\n");
 276   Printf("SUMMARY: libFuzzer: deadly signal\n");
 277   DumpCurrentUnit("crash-");
 278   PrintFinalStats();
 279   exit(Options.ErrorExitCode);
 280 }
 281
 282 void Fuzzer::InterruptCallback() {
 283   Printf("==%lu== libFuzzer: run interrupted; exiting\n", GetPid());
 284   PrintFinalStats();
 285   _Exit(0);  // Stop right now, don't perform any at-exit actions.
 286 }
 287
 288 NO_SANITIZE_MEMORY
 289 void Fuzzer::AlarmCallback() {
 290   assert(Options.UnitTimeoutSec > 0);
 291   if (!InFuzzingThread()) return;
 292   if (!RunningCB)
 293     return; // We have not started running units yet.
 294   size_t Seconds =
 295       duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
 296   if (Seconds == 0)
 297     return;
 298   if (Options.Verbosity >= 2)
 299     Printf("AlarmCallback %zd\n", Seconds);
 300   if (Seconds >= (size_t)Options.UnitTimeoutSec) {
 301     Printf("ALARM: working on the last Unit for %zd seconds\n", Seconds);
 302     Printf("       and the timeout value is %d (use -timeout=N to change)\n",
 303            Options.UnitTimeoutSec);
 304     DumpCurrentUnit("timeout-");
 305     Printf("==%lu== ERROR: libFuzzer: timeout after %d seconds\n", GetPid(),
 306            Seconds);
 307     if (EF->__sanitizer_print_stack_trace)
 308       EF->__sanitizer_print_stack_trace();
 309     Printf("SUMMARY: libFuzzer: timeout\n");
 310     PrintFinalStats();
 311     _Exit(Options.TimeoutExitCode); // Stop right now.
 312   }
 313 }
 314
 315 void Fuzzer::RssLimitCallback() {
 316   Printf(
 317       "==%lu== ERROR: libFuzzer: out-of-memory (used: %zdMb; limit: %zdMb)\n",
 318       GetPid(), GetPeakRSSMb(), Options.RssLimitMb);
 319   Printf("   To change the out-of-memory limit use -rss_limit_mb=<N>\n\n");
 320   if (EF->__sanitizer_print_memory_profile)
 321     EF->__sanitizer_print_memory_profile(95);
 322   DumpCurrentUnit("oom-");
 323   Printf("SUMMARY: libFuzzer: out-of-memory\n");
 324   PrintFinalStats();
 325   _Exit(Options.ErrorExitCode); // Stop right now.
 326 }
 327
 328 void Fuzzer::PrintStats(const char *Where, const char *End, size_t Units) {
 329   size_t ExecPerSec = execPerSec();
 330   if (Options.OutputCSV) {
 331     static bool csvHeaderPrinted = false;
 332     if (!csvHeaderPrinted) {
 333       csvHeaderPrinted = true;
 334       Printf("runs,block_cov,bits,cc_cov,corpus,execs_per_sec,tbms,reason\n");
 335     }
 336     Printf("%zd,%zd,%zd,%zd,%zd,%zd,%s\n", TotalNumberOfRuns,
 337            MaxCoverage.BlockCoverage, MaxCoverage.CounterBitmapBits,
 338            MaxCoverage.CallerCalleeCoverage, Corpus.size(), ExecPerSec, Where);
 339   }
 340
 341   if (!Options.Verbosity)
 342     return;
 343   Printf("#%zd\t%s", TotalNumberOfRuns, Where);
 344   if (MaxCoverage.BlockCoverage)
 345     Printf(" cov: %zd", MaxCoverage.BlockCoverage);
 346   if (size_t N = MaxCoverage.VPMap.GetNumBitsSinceLastMerge())
 347     Printf(" vp: %zd", N);
 348   if (size_t N = TPC.GetTotalPCCoverage())
 349     Printf(" cov: %zd", N);
 350   if (auto TB = MaxCoverage.CounterBitmapBits)
 351     Printf(" bits: %zd", TB);
 352   if (size_t N = Corpus.NumFeatures())
 353     Printf( " ft: %zd", N);
 354   if (MaxCoverage.CallerCalleeCoverage)
 355     Printf(" indir: %zd", MaxCoverage.CallerCalleeCoverage);
 356   if (!Corpus.empty()) {
 357     Printf(" corp: %zd", Corpus.NumActiveUnits());
 358     if (size_t N = Corpus.SizeInBytes()) {
 359       if (N < (1<<14))
 360         Printf("/%zdb", N);
 361       else if (N < (1 << 24))
 362         Printf("/%zdKb", N >> 10);
 363       else
 364         Printf("/%zdMb", N >> 20);
 365     }
 366   }
 367   if (Units)
 368     Printf(" units: %zd", Units);
 369
 370   Printf(" exec/s: %zd", ExecPerSec);
 371   Printf(" rss: %zdMb", GetPeakRSSMb());
 372   Printf("%s", End);
 373 }
 374
 375 void Fuzzer::PrintFinalStats() {
 376   if (Options.PrintCoverage)
 377     TPC.PrintCoverage();
 378   if (Options.DumpCoverage)
 379     TPC.DumpCoverage();
 380   if (Options.PrintCorpusStats)
 381     Corpus.PrintStats();
 382   if (!Options.PrintFinalStats) return;
 383   size_t ExecPerSec = execPerSec();
 384   Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
 385   Printf("stat::average_exec_per_sec:     %zd\n", ExecPerSec);
 386   Printf("stat::new_units_added:          %zd\n", NumberOfNewUnitsAdded);
 387   Printf("stat::slowest_unit_time_sec:    %zd\n", TimeOfLongestUnitInSeconds);
 388   Printf("stat::peak_rss_mb:              %zd\n", GetPeakRSSMb());
 389 }
 390
 391 void Fuzzer::SetMaxInputLen(size_t MaxInputLen) {
 392   assert(this->MaxInputLen == 0); // Can only reset MaxInputLen from 0 to non-0.
 393   assert(MaxInputLen);
 394   this->MaxInputLen = MaxInputLen;
 395   this->MaxMutationLen = MaxInputLen;
 396   AllocateCurrentUnitData();
 397   Printf("INFO: -max_len is not provided, using %zd\n", MaxInputLen);
 398 }
 399
 400 void Fuzzer::SetMaxMutationLen(size_t MaxMutationLen) {
 401   assert(MaxMutationLen && MaxMutationLen <= MaxInputLen);
 402   this->MaxMutationLen = MaxMutationLen;
 403 }
 404
 405 void Fuzzer::CheckExitOnSrcPosOrItem() {
 406   if (!Options.ExitOnSrcPos.empty()) {
 407     static auto *PCsSet = new std::set<uintptr_t>;
 408     for (size_t i = 1, N = TPC.GetNumPCs(); i < N; i++) {
 409       uintptr_t PC = TPC.GetPC(i);
 410       if (!PC) continue;
 411       if (!PCsSet->insert(PC).second) continue;
 412       std::string Descr = DescribePC("%L", PC);
 413       if (Descr.find(Options.ExitOnSrcPos) != std::string::npos) {
 414         Printf("INFO: found line matching '%s', exiting.\n",
 415                Options.ExitOnSrcPos.c_str());
 416         _Exit(0);
 417       }
 418     }
 419   }
 420   if (!Options.ExitOnItem.empty()) {
 421     if (Corpus.HasUnit(Options.ExitOnItem)) {
 422       Printf("INFO: found item with checksum '%s', exiting.\n",
 423              Options.ExitOnItem.c_str());
 424       _Exit(0);
 425     }
 426   }
 427 }
 428
 429 void Fuzzer::RereadOutputCorpus(size_t MaxSize) {
 430   if (Options.OutputCorpus.empty() || !Options.ReloadIntervalSec) return;
 431   std::vector<Unit> AdditionalCorpus;
 432   ReadDirToVectorOfUnits(Options.OutputCorpus.c_str(), &AdditionalCorpus,
 433                          &EpochOfLastReadOfOutputCorpus, MaxSize,
 434                          /*ExitOnError*/ false);
 435   if (Options.Verbosity >= 2)
 436     Printf("Reload: read %zd new units.\n", AdditionalCorpus.size());
 437   bool Reloaded = false;
 438   for (auto &U : AdditionalCorpus) {
 439     if (U.size() > MaxSize)
 440       U.resize(MaxSize);
 441     if (!Corpus.HasUnit(U)) {
 442       if (size_t NumFeatures = RunOne(U)) {
 443         CheckExitOnSrcPosOrItem();
 444         Corpus.AddToCorpus(U, NumFeatures);
 445         Reloaded = true;
 446       }
 447     }
 448   }
 449   if (Reloaded)
 450     PrintStats("RELOAD");
 451 }
 452
 453 void Fuzzer::ShuffleCorpus(UnitVector *V) {
 454   std::random_shuffle(V->begin(), V->end(), MD.GetRand());
 455   if (Options.PreferSmall)
 456     std::stable_sort(V->begin(), V->end(), [](const Unit &A, const Unit &B) {
 457       return A.size() < B.size();
 458     });
 459 }
 460
 461 void Fuzzer::ShuffleAndMinimize(UnitVector *InitialCorpus) {
 462   Printf("#0\tREAD units: %zd\n", InitialCorpus->size());
 463   if (Options.ShuffleAtStartUp)
 464     ShuffleCorpus(InitialCorpus);
 465
 466   // Test the callback with empty input and never try it again.
 467   uint8_t dummy;
 468   ExecuteCallback(&dummy, 0);
 469
 470   for (const auto &U : *InitialCorpus) {
 471     if (size_t NumFeatures = RunOne(U)) {
 472       CheckExitOnSrcPosOrItem();
 473       Corpus.AddToCorpus(U, NumFeatures);
 474       if (Options.Verbosity >= 2)
 475         Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size());
 476     }
 477     TryDetectingAMemoryLeak(U.data(), U.size(),
 478                             /*DuringInitialCorpusExecution*/ true);
 479   }
 480   PrintStats("INITED");
 481   if (Corpus.empty()) {
 482     Printf("ERROR: no interesting inputs were found. "
 483            "Is the code instrumented for coverage? Exiting.\n");
 484     exit(1);
 485   }
 486 }
 487
 488 size_t Fuzzer::RunOne(const uint8_t *Data, size_t Size) {
 489   if (!Size) return 0;
 490   TotalNumberOfRuns++;
 491
 492   ExecuteCallback(Data, Size);
 493
 494   size_t Res = 0;
 495   if (size_t NumFeatures = TPC.CollectFeatures([&](size_t Feature) -> bool {
 496         return Corpus.AddFeature(Feature, Size, Options.Shrink);
 497       }))
 498     Res = NumFeatures;
 499
 500   if (!TPC.UsingTracePcGuard()) {
 501     if (TPC.UpdateValueProfileMap(&MaxCoverage.VPMap))
 502       Res = 1;
 503     if (!Res && RecordMaxCoverage(&MaxCoverage))
 504       Res = 1;
 505   }
 506
 507   auto TimeOfUnit =
 508       duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
 509   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) &&
 510       secondsSinceProcessStartUp() >= 2)
 511     PrintStats("pulse ");
 512   if (TimeOfUnit > TimeOfLongestUnitInSeconds * 1.1 &&
 513       TimeOfUnit >= Options.ReportSlowUnits) {
 514     TimeOfLongestUnitInSeconds = TimeOfUnit;
 515     Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
 516     WriteUnitToFileWithPrefix({Data, Data + Size}, "slow-unit-");
 517   }
 518   return Res;
 519 }
 520
 521 size_t Fuzzer::GetCurrentUnitInFuzzingThead(const uint8_t **Data) const {
 522   assert(InFuzzingThread());
 523   *Data = CurrentUnitData;
 524   return CurrentUnitSize;
 525 }
 526
 527 void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
 528   assert(InFuzzingThread());
 529   // We copy the contents of Unit into a separate heap buffer
 530   // so that we reliably find buffer overflows in it.
 531   uint8_t *DataCopy = new uint8_t[Size];
 532   memcpy(DataCopy, Data, Size);
 533   if (CurrentUnitData && CurrentUnitData != Data)
 534     memcpy(CurrentUnitData, Data, Size);
 535   CurrentUnitSize = Size;
 536   AllocTracer.Start(Options.TraceMalloc);
 537   UnitStartTime = system_clock::now();
 538   ResetCounters();  // Reset coverage right before the callback.
 539   TPC.ResetMaps();
 540   RunningCB = true;
 541   int Res = CB(DataCopy, Size);
 542   RunningCB = false;
 543   UnitStopTime = system_clock::now();
 544   (void)Res;
 545   assert(Res == 0);
 546   HasMoreMallocsThanFrees = AllocTracer.Stop();
 547   CurrentUnitSize = 0;
 548   delete[] DataCopy;
 549 }
 550
 551 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
 552   if (Options.OnlyASCII)
 553     assert(IsASCII(U));
 554   if (Options.OutputCorpus.empty())
 555     return;
 556   std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
 557   WriteToFile(U, Path);
 558   if (Options.Verbosity >= 2)
 559     Printf("Written to %s\n", Path.c_str());
 560 }
 561
 562 void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) {
 563   if (!Options.SaveArtifacts)
 564     return;
 565   std::string Path = Options.ArtifactPrefix + Prefix + Hash(U);
 566   if (!Options.ExactArtifactPath.empty())
 567     Path = Options.ExactArtifactPath; // Overrides ArtifactPrefix.
 568   WriteToFile(U, Path);
 569   Printf("artifact_prefix='%s'; Test unit written to %s\n",
 570          Options.ArtifactPrefix.c_str(), Path.c_str());
 571   if (U.size() <= kMaxUnitSizeToPrint)
 572     Printf("Base64: %s\n", Base64(U).c_str());
 573 }
 574
 575 void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
 576   if (!Options.PrintNEW)
 577     return;
 578   PrintStats("NEW   ", "");
 579   if (Options.Verbosity) {
 580     Printf(" L: %zd ", U.size());
 581     MD.PrintMutationSequence();
 582     Printf("\n");
 583   }
 584 }
 585
 586 void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) {
 587   II->NumSuccessfullMutations++;
 588   MD.RecordSuccessfulMutationSequence();
 589   PrintStatusForNewUnit(U);
 590   WriteToOutputCorpus(U);
 591   NumberOfNewUnitsAdded++;
 592   TPC.PrintNewPCs();
 593 }
 594
 595 // Finds minimal number of units in 'Extra' that add coverage to 'Initial'.
 596 // We do it by actually executing the units, sometimes more than once,
 597 // because we may be using different coverage-like signals and the only
 598 // common thing between them is that we can say "this unit found new stuff".
 599 UnitVector Fuzzer::FindExtraUnits(const UnitVector &Initial,
 600                                   const UnitVector &Extra) {
 601   UnitVector Res = Extra;
 602   UnitVector Tmp;
 603   size_t OldSize = Res.size();
 604   for (int Iter = 0; Iter < 10; Iter++) {
 605     ShuffleCorpus(&Res);
 606     TPC.ResetMaps();
 607     Corpus.ResetFeatureSet();
 608     ResetCoverage();
 609
 610     for (auto &U : Initial) {
 611       TPC.ResetMaps();
 612       RunOne(U);
 613     }
 614
 615     Tmp.clear();
 616     for (auto &U : Res) {
 617       TPC.ResetMaps();
 618       if (RunOne(U))
 619         Tmp.push_back(U);
 620     }
 621
 622     char Stat[7] = "MIN   ";
 623     Stat[3] = '0' + Iter;
 624     PrintStats(Stat, "\n", Tmp.size());
 625
 626     size_t NewSize = Tmp.size();
 627     assert(NewSize <= OldSize);
 628     Res.swap(Tmp);
 629
 630     if (NewSize + 5 >= OldSize)
 631       break;
 632     OldSize = NewSize;
 633   }
 634   return Res;
 635 }
 636
 637 void Fuzzer::Merge(const std::vector<std::string> &Corpora) {
 638   if (Corpora.size() <= 1) {
 639     Printf("Merge requires two or more corpus dirs\n");
 640     return;
 641   }
 642   InMergeMode = true;
 643   std::vector<std::string> ExtraCorpora(Corpora.begin() + 1, Corpora.end());
 644
 645   assert(MaxInputLen > 0);
 646   UnitVector Initial, Extra;
 647   ReadDirToVectorOfUnits(Corpora[0].c_str(), &Initial, nullptr, MaxInputLen,
 648                          true);
 649   for (auto &C : ExtraCorpora)
 650     ReadDirToVectorOfUnits(C.c_str(), &Extra, nullptr, MaxInputLen, true);
 651
 652   if (!Initial.empty()) {
 653     Printf("=== Minimizing the initial corpus of %zd units\n", Initial.size());
 654     Initial = FindExtraUnits({}, Initial);
 655   }
 656
 657   Printf("=== Merging extra %zd units\n", Extra.size());
 658   auto Res = FindExtraUnits(Initial, Extra);
 659
 660   for (auto &U: Res)
 661     WriteToOutputCorpus(U);
 662
 663   Printf("=== Merge: written %zd units\n", Res.size());
 664 }
 665
 666 // Tries detecting a memory leak on the particular input that we have just
 667 // executed before calling this function.
 668 void Fuzzer::TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size,
 669                                      bool DuringInitialCorpusExecution) {
 670   if (!HasMoreMallocsThanFrees) return;  // mallocs==frees, a leak is unlikely.
 671   if (!Options.DetectLeaks) return;
 672   if (!&(EF->__lsan_enable) || !&(EF->__lsan_disable) ||
 673       !(EF->__lsan_do_recoverable_leak_check))
 674     return;  // No lsan.
 675   // Run the target once again, but with lsan disabled so that if there is
 676   // a real leak we do not report it twice.
 677   EF->__lsan_disable();
 678   ExecuteCallback(Data, Size);
 679   EF->__lsan_enable();
 680   if (!HasMoreMallocsThanFrees) return;  // a leak is unlikely.
 681   if (NumberOfLeakDetectionAttempts++ > 1000) {
 682     Options.DetectLeaks = false;
 683     Printf("INFO: libFuzzer disabled leak detection after every mutation.\n"
 684            "      Most likely the target function accumulates allocated\n"
 685            "      memory in a global state w/o actually leaking it.\n"
 686            "      You may try running this binary with -trace_malloc=[12]"
 687            "      to get a trace of mallocs and frees.\n"
 688            "      If LeakSanitizer is enabled in this process it will still\n"
 689            "      run on the process shutdown.\n");
 690     return;
 691   }
 692   // Now perform the actual lsan pass. This is expensive and we must ensure
 693   // we don't call it too often.
 694   if (EF->__lsan_do_recoverable_leak_check()) { // Leak is found, report it.
 695     if (DuringInitialCorpusExecution)
 696       Printf("\nINFO: a leak has been found in the initial corpus.\n\n");
 697     Printf("INFO: to ignore leaks on libFuzzer side use -detect_leaks=0.\n\n");
 698     CurrentUnitSize = Size;
 699     DumpCurrentUnit("leak-");
 700     PrintFinalStats();
 701     _Exit(Options.ErrorExitCode);  // not exit() to disable lsan further on.
 702   }
 703 }
 704
 705 static size_t ComputeMutationLen(size_t MaxInputSize, size_t MaxMutationLen,
 706                                  Random &Rand) {
 707   assert(MaxInputSize <= MaxMutationLen);
 708   if (MaxInputSize == MaxMutationLen) return MaxMutationLen;
 709   size_t Result = MaxInputSize;
 710   size_t R = Rand.Rand();
 711   if ((R % (1U << 7)) == 0)
 712     Result++;
 713   if ((R % (1U << 15)) == 0)
 714     Result += 10 + Result / 2;
 715   return Min(Result, MaxMutationLen);
 716 }
 717
 718 void Fuzzer::MutateAndTestOne() {
 719   MD.StartMutationSequence();
 720
 721   auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
 722   const auto &U = II.U;
 723   memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
 724   assert(CurrentUnitData);
 725   size_t Size = U.size();
 726   assert(Size <= MaxInputLen && "Oversized Unit");
 727   memcpy(CurrentUnitData, U.data(), Size);
 728
 729   assert(MaxMutationLen > 0);
 730
 731   size_t CurrentMaxMutationLen =
 732       Options.ExperimentalLenControl
 733           ? ComputeMutationLen(Corpus.MaxInputSize(), MaxMutationLen,
 734                                MD.GetRand())
 735           : MaxMutationLen;
 736
 737   for (int i = 0; i < Options.MutateDepth; i++) {
 738     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 739       break;
 740     size_t NewSize = 0;
 741     NewSize = MD.Mutate(CurrentUnitData, Size, CurrentMaxMutationLen);
 742     assert(NewSize > 0 && "Mutator returned empty unit");
 743     assert(NewSize <= CurrentMaxMutationLen && "Mutator return overisized unit");
 744     Size = NewSize;
 745     if (i == 0)
 746       StartTraceRecording();
 747     II.NumExecutedMutations++;
 748     if (size_t NumFeatures = RunOne(CurrentUnitData, Size)) {
 749       Corpus.AddToCorpus({CurrentUnitData, CurrentUnitData + Size}, NumFeatures,
 750                          /*MayDeleteFile=*/true);
 751       ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
 752       CheckExitOnSrcPosOrItem();
 753     }
 754     StopTraceRecording();
 755     TryDetectingAMemoryLeak(CurrentUnitData, Size,
 756                             /*DuringInitialCorpusExecution*/ false);
 757   }
 758 }
 759
 760 void Fuzzer::ResetCoverage() {
 761   ResetEdgeCoverage();
 762   MaxCoverage.Reset();
 763   PrepareCounters(&MaxCoverage);
 764 }
 765
 766 void Fuzzer::Loop() {
 767   TPC.InitializePrintNewPCs();
 768   system_clock::time_point LastCorpusReload = system_clock::now();
 769   if (Options.DoCrossOver)
 770     MD.SetCorpus(&Corpus);
 771   while (true) {
 772     auto Now = system_clock::now();
 773     if (duration_cast<seconds>(Now - LastCorpusReload).count() >=
 774         Options.ReloadIntervalSec) {
 775       RereadOutputCorpus(MaxInputLen);
 776       LastCorpusReload = system_clock::now();
 777     }
 778     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 779       break;
 780     if (TimedOut()) break;
 781     // Perform several mutations and runs.
 782     MutateAndTestOne();
 783   }
 784
 785   PrintStats("DONE  ", "\n");
 786   MD.PrintRecommendedDictionary();
 787 }
 788
 789 void Fuzzer::MinimizeCrashLoop(const Unit &U) {
 790   if (U.size() <= 2) return;
 791   while (!TimedOut() && TotalNumberOfRuns < Options.MaxNumberOfRuns) {
 792     MD.StartMutationSequence();
 793     memcpy(CurrentUnitData, U.data(), U.size());
 794     for (int i = 0; i < Options.MutateDepth; i++) {
 795       size_t NewSize = MD.Mutate(CurrentUnitData, U.size(), MaxMutationLen);
 796       assert(NewSize > 0 && NewSize <= MaxMutationLen);
 797       RunOne(CurrentUnitData, NewSize);
 798       TryDetectingAMemoryLeak(CurrentUnitData, NewSize,
 799                               /*DuringInitialCorpusExecution*/ false);
 800     }
 801   }
 802 }
 803
 804 } // namespace fuzzer
 805
 806 extern "C" {
 807
 808 size_t LLVMFuzzerMutate(uint8_t *Data, size_t Size, size_t MaxSize) {
 809   assert(fuzzer::F);
 810   return fuzzer::F->GetMD().DefaultMutate(Data, Size, MaxSize);
 811 }
 812 }  // extern "C"