compiler-rt/lib/fuzzer/FuzzerLoop.cpp

   1 //===- FuzzerLoop.cpp - Fuzzer's main loop --------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // Fuzzer's main loop.
   9 //===----------------------------------------------------------------------===//
  10
  11 #include "FuzzerCorpus.h"
  12 #include "FuzzerIO.h"
  13 #include "FuzzerInternal.h"
  14 #include "FuzzerMutate.h"
  15 #include "FuzzerPlatform.h"
  16 #include "FuzzerRandom.h"
  17 #include "FuzzerTracePC.h"
  18 #include <algorithm>
  19 #include <cstring>
  20 #include <memory>
  21 #include <mutex>
  22 #include <set>
  23
  24 #if defined(__has_include)
  25 #if __has_include(<sanitizer / lsan_interface.h>)
  26 #include <sanitizer/lsan_interface.h>
  27 #endif
  28 #endif
  29
  30 #define NO_SANITIZE_MEMORY
  31 #if defined(__has_feature)
  32 #if __has_feature(memory_sanitizer)
  33 #undef NO_SANITIZE_MEMORY
  34 #define NO_SANITIZE_MEMORY __attribute__((no_sanitize_memory))
  35 #endif
  36 #endif
  37
  38 namespace fuzzer {
  39 static const size_t kMaxUnitSizeToPrint = 256;
  40
  41 thread_local bool Fuzzer::IsMyThread;
  42
  43 bool RunningUserCallback = false;
  44
  45 // Only one Fuzzer per process.
  46 static Fuzzer *F;
  47
  48 // Leak detection is expensive, so we first check if there were more mallocs
  49 // than frees (using the sanitizer malloc hooks) and only then try to call lsan.
  50 struct MallocFreeTracer {
  51   void Start(int TraceLevel) {
  52     this->TraceLevel = TraceLevel;
  53     if (TraceLevel)
  54       Printf("MallocFreeTracer: START\n");
  55     Mallocs = 0;
  56     Frees = 0;
  57   }
  58   // Returns true if there were more mallocs than frees.
  59   bool Stop() {
  60     if (TraceLevel)
  61       Printf("MallocFreeTracer: STOP %zd %zd (%s)\n", Mallocs.load(),
  62              Frees.load(), Mallocs == Frees ? "same" : "DIFFERENT");
  63     bool Result = Mallocs > Frees;
  64     Mallocs = 0;
  65     Frees = 0;
  66     TraceLevel = 0;
  67     return Result;
  68   }
  69   std::atomic<size_t> Mallocs;
  70   std::atomic<size_t> Frees;
  71   int TraceLevel = 0;
  72
  73   std::recursive_mutex TraceMutex;
  74   bool TraceDisabled = false;
  75 };
  76
  77 static MallocFreeTracer AllocTracer;
  78
  79 // Locks printing and avoids nested hooks triggered from mallocs/frees in
  80 // sanitizer.
  81 class TraceLock {
  82 public:
  83   TraceLock() : Lock(AllocTracer.TraceMutex) {
  84     AllocTracer.TraceDisabled = !AllocTracer.TraceDisabled;
  85   }
  86   ~TraceLock() { AllocTracer.TraceDisabled = !AllocTracer.TraceDisabled; }
  87
  88   bool IsDisabled() const {
  89     // This is already inverted value.
  90     return !AllocTracer.TraceDisabled;
  91   }
  92
  93 private:
  94   std::lock_guard<std::recursive_mutex> Lock;
  95 };
  96
  97 ATTRIBUTE_NO_SANITIZE_MEMORY
  98 void MallocHook(const volatile void *ptr, size_t size) {
  99   size_t N = AllocTracer.Mallocs++;
 100   F->HandleMalloc(size);
 101   if (int TraceLevel = AllocTracer.TraceLevel) {
 102     TraceLock Lock;
 103     if (Lock.IsDisabled())
 104       return;
 105     Printf("MALLOC[%zd] %p %zd\n", N, ptr, size);
 106     if (TraceLevel >= 2 && EF)
 107       PrintStackTrace();
 108   }
 109 }
 110
 111 ATTRIBUTE_NO_SANITIZE_MEMORY
 112 void FreeHook(const volatile void *ptr) {
 113   size_t N = AllocTracer.Frees++;
 114   if (int TraceLevel = AllocTracer.TraceLevel) {
 115     TraceLock Lock;
 116     if (Lock.IsDisabled())
 117       return;
 118     Printf("FREE[%zd]   %p\n", N, ptr);
 119     if (TraceLevel >= 2 && EF)
 120       PrintStackTrace();
 121   }
 122 }
 123
 124 // Crash on a single malloc that exceeds the rss limit.
 125 void Fuzzer::HandleMalloc(size_t Size) {
 126   if (!Options.MallocLimitMb || (Size >> 20) < (size_t)Options.MallocLimitMb)
 127     return;
 128   Printf("==%d== ERROR: libFuzzer: out-of-memory (malloc(%zd))\n", GetPid(),
 129          Size);
 130   Printf("   To change the out-of-memory limit use -rss_limit_mb=<N>\n\n");
 131   PrintStackTrace();
 132   DumpCurrentUnit("oom-");
 133   Printf("SUMMARY: libFuzzer: out-of-memory\n");
 134   PrintFinalStats();
 135   _Exit(Options.OOMExitCode); // Stop right now.
 136 }
 137
 138 Fuzzer::Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
 139                const FuzzingOptions &Options)
 140     : CB(CB), Corpus(Corpus), MD(MD), Options(Options) {
 141   if (EF->__sanitizer_set_death_callback)
 142     EF->__sanitizer_set_death_callback(StaticDeathCallback);
 143   assert(!F);
 144   F = this;
 145   TPC.ResetMaps();
 146   IsMyThread = true;
 147   if (Options.DetectLeaks && EF->__sanitizer_install_malloc_and_free_hooks)
 148     EF->__sanitizer_install_malloc_and_free_hooks(MallocHook, FreeHook);
 149   TPC.SetUseCounters(Options.UseCounters);
 150   TPC.SetUseValueProfileMask(Options.UseValueProfile);
 151
 152   if (Options.Verbosity)
 153     TPC.PrintModuleInfo();
 154   if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec)
 155     EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus);
 156   MaxInputLen = MaxMutationLen = Options.MaxLen;
 157   TmpMaxMutationLen = 0;  // Will be set once we load the corpus.
 158   AllocateCurrentUnitData();
 159   CurrentUnitSize = 0;
 160   memset(BaseSha1, 0, sizeof(BaseSha1));
 161 }
 162
 163 void Fuzzer::AllocateCurrentUnitData() {
 164   if (CurrentUnitData || MaxInputLen == 0)
 165     return;
 166   CurrentUnitData = new uint8_t[MaxInputLen];
 167 }
 168
 169 void Fuzzer::StaticDeathCallback() {
 170   assert(F);
 171   F->DeathCallback();
 172 }
 173
 174 void Fuzzer::DumpCurrentUnit(const char *Prefix) {
 175   if (!CurrentUnitData)
 176     return; // Happens when running individual inputs.
 177   ScopedDisableMsanInterceptorChecks S;
 178   MD.PrintMutationSequence();
 179   Printf("; base unit: %s\n", Sha1ToString(BaseSha1).c_str());
 180   size_t UnitSize = CurrentUnitSize;
 181   if (UnitSize <= kMaxUnitSizeToPrint) {
 182     PrintHexArray(CurrentUnitData, UnitSize, "\n");
 183     PrintASCII(CurrentUnitData, UnitSize, "\n");
 184   }
 185   WriteUnitToFileWithPrefix({CurrentUnitData, CurrentUnitData + UnitSize},
 186                             Prefix);
 187 }
 188
 189 NO_SANITIZE_MEMORY
 190 void Fuzzer::DeathCallback() {
 191   DumpCurrentUnit("crash-");
 192   PrintFinalStats();
 193 }
 194
 195 void Fuzzer::StaticAlarmCallback() {
 196   assert(F);
 197   F->AlarmCallback();
 198 }
 199
 200 void Fuzzer::StaticCrashSignalCallback() {
 201   assert(F);
 202   F->CrashCallback();
 203 }
 204
 205 void Fuzzer::StaticExitCallback() {
 206   assert(F);
 207   F->ExitCallback();
 208 }
 209
 210 void Fuzzer::StaticInterruptCallback() {
 211   assert(F);
 212   F->InterruptCallback();
 213 }
 214
 215 void Fuzzer::StaticGracefulExitCallback() {
 216   assert(F);
 217   F->GracefulExitRequested = true;
 218   Printf("INFO: signal received, trying to exit gracefully\n");
 219 }
 220
 221 void Fuzzer::StaticFileSizeExceedCallback() {
 222   Printf("==%lu== ERROR: libFuzzer: file size exceeded\n", GetPid());
 223   exit(1);
 224 }
 225
 226 void Fuzzer::CrashCallback() {
 227   if (EF->__sanitizer_acquire_crash_state &&
 228       !EF->__sanitizer_acquire_crash_state())
 229     return;
 230   Printf("==%lu== ERROR: libFuzzer: deadly signal\n", GetPid());
 231   PrintStackTrace();
 232   Printf("NOTE: libFuzzer has rudimentary signal handlers.\n"
 233          "      Combine libFuzzer with AddressSanitizer or similar for better "
 234          "crash reports.\n");
 235   Printf("SUMMARY: libFuzzer: deadly signal\n");
 236   DumpCurrentUnit("crash-");
 237   PrintFinalStats();
 238   _Exit(Options.ErrorExitCode); // Stop right now.
 239 }
 240
 241 void Fuzzer::ExitCallback() {
 242   if (!RunningUserCallback)
 243     return; // This exit did not come from the user callback
 244   if (EF->__sanitizer_acquire_crash_state &&
 245       !EF->__sanitizer_acquire_crash_state())
 246     return;
 247   Printf("==%lu== ERROR: libFuzzer: fuzz target exited\n", GetPid());
 248   PrintStackTrace();
 249   Printf("SUMMARY: libFuzzer: fuzz target exited\n");
 250   DumpCurrentUnit("crash-");
 251   PrintFinalStats();
 252   _Exit(Options.ErrorExitCode);
 253 }
 254
 255 void Fuzzer::MaybeExitGracefully() {
 256   if (!F->GracefulExitRequested) return;
 257   Printf("==%lu== INFO: libFuzzer: exiting as requested\n", GetPid());
 258   RmDirRecursive(TempPath("FuzzWithFork", ".dir"));
 259   F->PrintFinalStats();
 260   _Exit(0);
 261 }
 262
 263 int Fuzzer::InterruptExitCode() {
 264   assert(F);
 265   return F->Options.InterruptExitCode;
 266 }
 267
 268 void Fuzzer::InterruptCallback() {
 269   Printf("==%lu== libFuzzer: run interrupted; exiting\n", GetPid());
 270   PrintFinalStats();
 271   ScopedDisableMsanInterceptorChecks S; // RmDirRecursive may call opendir().
 272   RmDirRecursive(TempPath("FuzzWithFork", ".dir"));
 273   // Stop right now, don't perform any at-exit actions.
 274   _Exit(Options.InterruptExitCode);
 275 }
 276
 277 NO_SANITIZE_MEMORY
 278 void Fuzzer::AlarmCallback() {
 279   assert(Options.UnitTimeoutSec > 0);
 280   // In Windows and Fuchsia, Alarm callback is executed by a different thread.
 281   // NetBSD's current behavior needs this change too.
 282 #if !LIBFUZZER_WINDOWS && !LIBFUZZER_NETBSD && !LIBFUZZER_FUCHSIA
 283   if (!InFuzzingThread())
 284     return;
 285 #endif
 286   if (!RunningUserCallback)
 287     return; // We have not started running units yet.
 288   size_t Seconds =
 289       duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
 290   if (Seconds == 0)
 291     return;
 292   if (Options.Verbosity >= 2)
 293     Printf("AlarmCallback %zd\n", Seconds);
 294   if (Seconds >= (size_t)Options.UnitTimeoutSec) {
 295     if (EF->__sanitizer_acquire_crash_state &&
 296         !EF->__sanitizer_acquire_crash_state())
 297       return;
 298     Printf("ALARM: working on the last Unit for %zd seconds\n", Seconds);
 299     Printf("       and the timeout value is %d (use -timeout=N to change)\n",
 300            Options.UnitTimeoutSec);
 301     DumpCurrentUnit("timeout-");
 302     Printf("==%lu== ERROR: libFuzzer: timeout after %zu seconds\n", GetPid(),
 303            Seconds);
 304     PrintStackTrace();
 305     Printf("SUMMARY: libFuzzer: timeout\n");
 306     PrintFinalStats();
 307     _Exit(Options.TimeoutExitCode); // Stop right now.
 308   }
 309 }
 310
 311 void Fuzzer::RssLimitCallback() {
 312   if (EF->__sanitizer_acquire_crash_state &&
 313       !EF->__sanitizer_acquire_crash_state())
 314     return;
 315   Printf("==%lu== ERROR: libFuzzer: out-of-memory (used: %zdMb; limit: %dMb)\n",
 316          GetPid(), GetPeakRSSMb(), Options.RssLimitMb);
 317   Printf("   To change the out-of-memory limit use -rss_limit_mb=<N>\n\n");
 318   PrintMemoryProfile();
 319   DumpCurrentUnit("oom-");
 320   Printf("SUMMARY: libFuzzer: out-of-memory\n");
 321   PrintFinalStats();
 322   _Exit(Options.OOMExitCode); // Stop right now.
 323 }
 324
 325 void Fuzzer::PrintStats(const char *Where, const char *End, size_t Units,
 326                         size_t Features) {
 327   size_t ExecPerSec = execPerSec();
 328   if (!Options.Verbosity)
 329     return;
 330   Printf("#%zd\t%s", TotalNumberOfRuns, Where);
 331   if (size_t N = TPC.GetTotalPCCoverage())
 332     Printf(" cov: %zd", N);
 333   if (size_t N = Features ? Features : Corpus.NumFeatures())
 334     Printf(" ft: %zd", N);
 335   if (!Corpus.empty()) {
 336     Printf(" corp: %zd", Corpus.NumActiveUnits());
 337     if (size_t N = Corpus.SizeInBytes()) {
 338       if (N < (1 << 14))
 339         Printf("/%zdb", N);
 340       else if (N < (1 << 24))
 341         Printf("/%zdKb", N >> 10);
 342       else
 343         Printf("/%zdMb", N >> 20);
 344     }
 345     if (size_t FF = Corpus.NumInputsThatTouchFocusFunction())
 346       Printf(" focus: %zd", FF);
 347   }
 348   if (TmpMaxMutationLen)
 349     Printf(" lim: %zd", TmpMaxMutationLen);
 350   if (Units)
 351     Printf(" units: %zd", Units);
 352
 353   Printf(" exec/s: %zd", ExecPerSec);
 354   Printf(" rss: %zdMb", GetPeakRSSMb());
 355   Printf("%s", End);
 356 }
 357
 358 void Fuzzer::PrintFinalStats() {
 359   if (Options.PrintFullCoverage)
 360     TPC.PrintCoverage(/*PrintAllCounters=*/true);
 361   if (Options.PrintCoverage)
 362     TPC.PrintCoverage(/*PrintAllCounters=*/false);
 363   if (Options.PrintCorpusStats)
 364     Corpus.PrintStats();
 365   if (!Options.PrintFinalStats)
 366     return;
 367   size_t ExecPerSec = execPerSec();
 368   Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
 369   Printf("stat::average_exec_per_sec:     %zd\n", ExecPerSec);
 370   Printf("stat::new_units_added:          %zd\n", NumberOfNewUnitsAdded);
 371   Printf("stat::slowest_unit_time_sec:    %ld\n", TimeOfLongestUnitInSeconds);
 372   Printf("stat::peak_rss_mb:              %zd\n", GetPeakRSSMb());
 373 }
 374
 375 void Fuzzer::SetMaxInputLen(size_t MaxInputLen) {
 376   assert(this->MaxInputLen == 0); // Can only reset MaxInputLen from 0 to non-0.
 377   assert(MaxInputLen);
 378   this->MaxInputLen = MaxInputLen;
 379   this->MaxMutationLen = MaxInputLen;
 380   AllocateCurrentUnitData();
 381   Printf("INFO: -max_len is not provided; "
 382          "libFuzzer will not generate inputs larger than %zd bytes\n",
 383          MaxInputLen);
 384 }
 385
 386 void Fuzzer::SetMaxMutationLen(size_t MaxMutationLen) {
 387   assert(MaxMutationLen && MaxMutationLen <= MaxInputLen);
 388   this->MaxMutationLen = MaxMutationLen;
 389 }
 390
 391 void Fuzzer::CheckExitOnSrcPosOrItem() {
 392   if (!Options.ExitOnSrcPos.empty()) {
 393     static auto *PCsSet = new std::set<uintptr_t>;
 394     auto HandlePC = [&](const TracePC::PCTableEntry *TE) {
 395       if (!PCsSet->insert(TE->PC).second)
 396         return;
 397       std::string Descr = DescribePC("%F %L", TE->PC + 1);
 398       if (Descr.find(Options.ExitOnSrcPos) != std::string::npos) {
 399         Printf("INFO: found line matching '%s', exiting.\n",
 400                Options.ExitOnSrcPos.c_str());
 401         _Exit(0);
 402       }
 403     };
 404     TPC.ForEachObservedPC(HandlePC);
 405   }
 406   if (!Options.ExitOnItem.empty()) {
 407     if (Corpus.HasUnit(Options.ExitOnItem)) {
 408       Printf("INFO: found item with checksum '%s', exiting.\n",
 409              Options.ExitOnItem.c_str());
 410       _Exit(0);
 411     }
 412   }
 413 }
 414
 415 void Fuzzer::RereadOutputCorpus(size_t MaxSize) {
 416   if (Options.OutputCorpus.empty() || !Options.ReloadIntervalSec)
 417     return;
 418   std::vector<Unit> AdditionalCorpus;
 419   std::vector<std::string> AdditionalCorpusPaths;
 420   ReadDirToVectorOfUnits(
 421       Options.OutputCorpus.c_str(), &AdditionalCorpus,
 422       &EpochOfLastReadOfOutputCorpus, MaxSize,
 423       /*ExitOnError*/ false,
 424       (Options.Verbosity >= 2 ? &AdditionalCorpusPaths : nullptr));
 425   if (Options.Verbosity >= 2)
 426     Printf("Reload: read %zd new units.\n", AdditionalCorpus.size());
 427   bool Reloaded = false;
 428   for (size_t i = 0; i != AdditionalCorpus.size(); ++i) {
 429     auto &U = AdditionalCorpus[i];
 430     if (U.size() > MaxSize)
 431       U.resize(MaxSize);
 432     if (!Corpus.HasUnit(U)) {
 433       if (RunOne(U.data(), U.size())) {
 434         CheckExitOnSrcPosOrItem();
 435         Reloaded = true;
 436         if (Options.Verbosity >= 2)
 437           Printf("Reloaded %s\n", AdditionalCorpusPaths[i].c_str());
 438       }
 439     }
 440   }
 441   if (Reloaded)
 442     PrintStats("RELOAD");
 443 }
 444
 445 void Fuzzer::PrintPulseAndReportSlowInput(const uint8_t *Data, size_t Size) {
 446   auto TimeOfUnit =
 447       duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
 448   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) &&
 449       secondsSinceProcessStartUp() >= 2)
 450     PrintStats("pulse ");
 451   auto Threshhold =
 452       static_cast<long>(static_cast<double>(TimeOfLongestUnitInSeconds) * 1.1);
 453   if (TimeOfUnit > Threshhold && TimeOfUnit >= Options.ReportSlowUnits) {
 454     TimeOfLongestUnitInSeconds = TimeOfUnit;
 455     Printf("Slowest unit: %ld s:\n", TimeOfLongestUnitInSeconds);
 456     WriteUnitToFileWithPrefix({Data, Data + Size}, "slow-unit-");
 457   }
 458 }
 459
 460 static void WriteFeatureSetToFile(const std::string &FeaturesDir,
 461                                   const std::string &FileName,
 462                                   const std::vector<uint32_t> &FeatureSet) {
 463   if (FeaturesDir.empty() || FeatureSet.empty()) return;
 464   WriteToFile(reinterpret_cast<const uint8_t *>(FeatureSet.data()),
 465               FeatureSet.size() * sizeof(FeatureSet[0]),
 466               DirPlusFile(FeaturesDir, FileName));
 467 }
 468
 469 static void RenameFeatureSetFile(const std::string &FeaturesDir,
 470                                  const std::string &OldFile,
 471                                  const std::string &NewFile) {
 472   if (FeaturesDir.empty()) return;
 473   RenameFile(DirPlusFile(FeaturesDir, OldFile),
 474              DirPlusFile(FeaturesDir, NewFile));
 475 }
 476
 477 static void WriteEdgeToMutationGraphFile(const std::string &MutationGraphFile,
 478                                          const InputInfo *II,
 479                                          const InputInfo *BaseII,
 480                                          const std::string &MS) {
 481   if (MutationGraphFile.empty())
 482     return;
 483
 484   std::string Sha1 = Sha1ToString(II->Sha1);
 485
 486   std::string OutputString;
 487
 488   // Add a new vertex.
 489   OutputString.append("\"");
 490   OutputString.append(Sha1);
 491   OutputString.append("\"\n");
 492
 493   // Add a new edge if there is base input.
 494   if (BaseII) {
 495     std::string BaseSha1 = Sha1ToString(BaseII->Sha1);
 496     OutputString.append("\"");
 497     OutputString.append(BaseSha1);
 498     OutputString.append("\" -> \"");
 499     OutputString.append(Sha1);
 500     OutputString.append("\" [label=\"");
 501     OutputString.append(MS);
 502     OutputString.append("\"];\n");
 503   }
 504
 505   AppendToFile(OutputString, MutationGraphFile);
 506 }
 507
 508 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
 509                     InputInfo *II, bool ForceAddToCorpus,
 510                     bool *FoundUniqFeatures) {
 511   if (!Size)
 512     return false;
 513   // Largest input length should be INT_MAX.
 514   assert(Size < std::numeric_limits<uint32_t>::max());
 515
 516   if(!ExecuteCallback(Data, Size)) return false;
 517   auto TimeOfUnit = duration_cast<microseconds>(UnitStopTime - UnitStartTime);
 518
 519   UniqFeatureSetTmp.clear();
 520   size_t FoundUniqFeaturesOfII = 0;
 521   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
 522   TPC.CollectFeatures([&](uint32_t Feature) {
 523     if (Corpus.AddFeature(Feature, static_cast<uint32_t>(Size), Options.Shrink))
 524       UniqFeatureSetTmp.push_back(Feature);
 525     if (Options.Entropic)
 526       Corpus.UpdateFeatureFrequency(II, Feature);
 527     if (Options.ReduceInputs && II && !II->NeverReduce)
 528       if (std::binary_search(II->UniqFeatureSet.begin(),
 529                              II->UniqFeatureSet.end(), Feature))
 530         FoundUniqFeaturesOfII++;
 531   });
 532   if (FoundUniqFeatures)
 533     *FoundUniqFeatures = FoundUniqFeaturesOfII;
 534   PrintPulseAndReportSlowInput(Data, Size);
 535   size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
 536   if (NumNewFeatures || ForceAddToCorpus) {
 537     TPC.UpdateObservedPCs();
 538     auto NewII =
 539         Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile,
 540                            TPC.ObservedFocusFunction(), ForceAddToCorpus,
 541                            TimeOfUnit, UniqFeatureSetTmp, DFT, II);
 542     WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1),
 543                           NewII->UniqFeatureSet);
 544     WriteEdgeToMutationGraphFile(Options.MutationGraphFile, NewII, II,
 545                                  MD.MutationSequence());
 546     return true;
 547   }
 548   if (II && FoundUniqFeaturesOfII &&
 549       II->DataFlowTraceForFocusFunction.empty() &&
 550       FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
 551       II->U.size() > Size) {
 552     auto OldFeaturesFile = Sha1ToString(II->Sha1);
 553     Corpus.Replace(II, {Data, Data + Size}, TimeOfUnit);
 554     RenameFeatureSetFile(Options.FeaturesDir, OldFeaturesFile,
 555                          Sha1ToString(II->Sha1));
 556     return true;
 557   }
 558   return false;
 559 }
 560
 561 void Fuzzer::TPCUpdateObservedPCs() { TPC.UpdateObservedPCs(); }
 562
 563 size_t Fuzzer::GetCurrentUnitInFuzzingThead(const uint8_t **Data) const {
 564   assert(InFuzzingThread());
 565   *Data = CurrentUnitData;
 566   return CurrentUnitSize;
 567 }
 568
 569 void Fuzzer::CrashOnOverwrittenData() {
 570   Printf("==%d== ERROR: libFuzzer: fuzz target overwrites its const input\n",
 571          GetPid());
 572   PrintStackTrace();
 573   Printf("SUMMARY: libFuzzer: overwrites-const-input\n");
 574   DumpCurrentUnit("crash-");
 575   PrintFinalStats();
 576   _Exit(Options.ErrorExitCode); // Stop right now.
 577 }
 578
 579 // Compare two arrays, but not all bytes if the arrays are large.
 580 static bool LooseMemeq(const uint8_t *A, const uint8_t *B, size_t Size) {
 581   const size_t Limit = 64;
 582   if (Size <= 64)
 583     return !memcmp(A, B, Size);
 584   // Compare first and last Limit/2 bytes.
 585   return !memcmp(A, B, Limit / 2) &&
 586          !memcmp(A + Size - Limit / 2, B + Size - Limit / 2, Limit / 2);
 587 }
 588
 589 // This method is not inlined because it would cause a test to fail where it
 590 // is part of the stack unwinding. See D97975 for details.
 591 ATTRIBUTE_NOINLINE bool Fuzzer::ExecuteCallback(const uint8_t *Data,
 592                                                 size_t Size) {
 593   TPC.RecordInitialStack();
 594   TotalNumberOfRuns++;
 595   assert(InFuzzingThread());
 596   // We copy the contents of Unit into a separate heap buffer
 597   // so that we reliably find buffer overflows in it.
 598   uint8_t *DataCopy = new uint8_t[Size];
 599   memcpy(DataCopy, Data, Size);
 600   if (EF->__msan_unpoison)
 601     EF->__msan_unpoison(DataCopy, Size);
 602   if (EF->__msan_unpoison_param)
 603     EF->__msan_unpoison_param(2);
 604   if (CurrentUnitData && CurrentUnitData != Data)
 605     memcpy(CurrentUnitData, Data, Size);
 606   CurrentUnitSize = Size;
 607   int CBRes = 0;
 608   {
 609     ScopedEnableMsanInterceptorChecks S;
 610     AllocTracer.Start(Options.TraceMalloc);
 611     UnitStartTime = system_clock::now();
 612     TPC.ResetMaps();
 613     RunningUserCallback = true;
 614     CBRes = CB(DataCopy, Size);
 615     RunningUserCallback = false;
 616     UnitStopTime = system_clock::now();
 617     assert(CBRes == 0 || CBRes == -1);
 618     HasMoreMallocsThanFrees = AllocTracer.Stop();
 619   }
 620   if (!LooseMemeq(DataCopy, Data, Size))
 621     CrashOnOverwrittenData();
 622   CurrentUnitSize = 0;
 623   delete[] DataCopy;
 624   return CBRes == 0;
 625 }
 626
 627 std::string Fuzzer::WriteToOutputCorpus(const Unit &U) {
 628   if (Options.OnlyASCII)
 629     assert(IsASCII(U));
 630   if (Options.OutputCorpus.empty())
 631     return "";
 632   std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
 633   WriteToFile(U, Path);
 634   if (Options.Verbosity >= 2)
 635     Printf("Written %zd bytes to %s\n", U.size(), Path.c_str());
 636   return Path;
 637 }
 638
 639 void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) {
 640   if (!Options.SaveArtifacts)
 641     return;
 642   std::string Path = Options.ArtifactPrefix + Prefix + Hash(U);
 643   if (!Options.ExactArtifactPath.empty())
 644     Path = Options.ExactArtifactPath; // Overrides ArtifactPrefix.
 645   WriteToFile(U, Path);
 646   Printf("artifact_prefix='%s'; Test unit written to %s\n",
 647          Options.ArtifactPrefix.c_str(), Path.c_str());
 648   if (U.size() <= kMaxUnitSizeToPrint)
 649     Printf("Base64: %s\n", Base64(U).c_str());
 650 }
 651
 652 void Fuzzer::PrintStatusForNewUnit(const Unit &U, const char *Text) {
 653   if (!Options.PrintNEW)
 654     return;
 655   PrintStats(Text, "");
 656   if (Options.Verbosity) {
 657     Printf(" L: %zd/%zd ", U.size(), Corpus.MaxInputSize());
 658     MD.PrintMutationSequence(Options.Verbosity >= 2);
 659     Printf("\n");
 660   }
 661 }
 662
 663 void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) {
 664   II->NumSuccessfullMutations++;
 665   MD.RecordSuccessfulMutationSequence();
 666   PrintStatusForNewUnit(U, II->Reduced ? "REDUCE" : "NEW   ");
 667   WriteToOutputCorpus(U);
 668   NumberOfNewUnitsAdded++;
 669   CheckExitOnSrcPosOrItem(); // Check only after the unit is saved to corpus.
 670   LastCorpusUpdateRun = TotalNumberOfRuns;
 671 }
 672
 673 // Tries detecting a memory leak on the particular input that we have just
 674 // executed before calling this function.
 675 void Fuzzer::TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size,
 676                                      bool DuringInitialCorpusExecution) {
 677   if (!HasMoreMallocsThanFrees)
 678     return; // mallocs==frees, a leak is unlikely.
 679   if (!Options.DetectLeaks)
 680     return;
 681   if (!DuringInitialCorpusExecution &&
 682       TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 683     return;
 684   if (!&(EF->__lsan_enable) || !&(EF->__lsan_disable) ||
 685       !(EF->__lsan_do_recoverable_leak_check))
 686     return; // No lsan.
 687   // Run the target once again, but with lsan disabled so that if there is
 688   // a real leak we do not report it twice.
 689   EF->__lsan_disable();
 690   ExecuteCallback(Data, Size);
 691   EF->__lsan_enable();
 692   if (!HasMoreMallocsThanFrees)
 693     return; // a leak is unlikely.
 694   if (NumberOfLeakDetectionAttempts++ > 1000) {
 695     Options.DetectLeaks = false;
 696     Printf("INFO: libFuzzer disabled leak detection after every mutation.\n"
 697            "      Most likely the target function accumulates allocated\n"
 698            "      memory in a global state w/o actually leaking it.\n"
 699            "      You may try running this binary with -trace_malloc=[12]"
 700            "      to get a trace of mallocs and frees.\n"
 701            "      If LeakSanitizer is enabled in this process it will still\n"
 702            "      run on the process shutdown.\n");
 703     return;
 704   }
 705   // Now perform the actual lsan pass. This is expensive and we must ensure
 706   // we don't call it too often.
 707   if (EF->__lsan_do_recoverable_leak_check()) { // Leak is found, report it.
 708     if (DuringInitialCorpusExecution)
 709       Printf("\nINFO: a leak has been found in the initial corpus.\n\n");
 710     Printf("INFO: to ignore leaks on libFuzzer side use -detect_leaks=0.\n\n");
 711     CurrentUnitSize = Size;
 712     DumpCurrentUnit("leak-");
 713     PrintFinalStats();
 714     _Exit(Options.ErrorExitCode); // not exit() to disable lsan further on.
 715   }
 716 }
 717
 718 void Fuzzer::MutateAndTestOne() {
 719   MD.StartMutationSequence();
 720
 721   auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
 722   if (Options.DoCrossOver) {
 723     auto &CrossOverII = Corpus.ChooseUnitToCrossOverWith(
 724         MD.GetRand(), Options.CrossOverUniformDist);
 725     MD.SetCrossOverWith(&CrossOverII.U);
 726   }
 727   const auto &U = II.U;
 728   memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
 729   assert(CurrentUnitData);
 730   size_t Size = U.size();
 731   assert(Size <= MaxInputLen && "Oversized Unit");
 732   memcpy(CurrentUnitData, U.data(), Size);
 733
 734   assert(MaxMutationLen > 0);
 735
 736   size_t CurrentMaxMutationLen =
 737       Min(MaxMutationLen, Max(U.size(), TmpMaxMutationLen));
 738   assert(CurrentMaxMutationLen > 0);
 739
 740   for (int i = 0; i < Options.MutateDepth; i++) {
 741     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 742       break;
 743     MaybeExitGracefully();
 744     size_t NewSize = 0;
 745     if (II.HasFocusFunction && !II.DataFlowTraceForFocusFunction.empty() &&
 746         Size <= CurrentMaxMutationLen)
 747       NewSize = MD.MutateWithMask(CurrentUnitData, Size, Size,
 748                                   II.DataFlowTraceForFocusFunction);
 749
 750     // If MutateWithMask either failed or wasn't called, call default Mutate.
 751     if (!NewSize)
 752       NewSize = MD.Mutate(CurrentUnitData, Size, CurrentMaxMutationLen);
 753     assert(NewSize > 0 && "Mutator returned empty unit");
 754     assert(NewSize <= CurrentMaxMutationLen && "Mutator return oversized unit");
 755     Size = NewSize;
 756     II.NumExecutedMutations++;
 757     Corpus.IncrementNumExecutedMutations();
 758
 759     bool FoundUniqFeatures = false;
 760     bool NewCov = RunOne(CurrentUnitData, Size, /*MayDeleteFile=*/true, &II,
 761                          /*ForceAddToCorpus*/ false, &FoundUniqFeatures);
 762     TryDetectingAMemoryLeak(CurrentUnitData, Size,
 763                             /*DuringInitialCorpusExecution*/ false);
 764     if (NewCov) {
 765       ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
 766       break;  // We will mutate this input more in the next rounds.
 767     }
 768     if (Options.ReduceDepth && !FoundUniqFeatures)
 769       break;
 770   }
 771
 772   II.NeedsEnergyUpdate = true;
 773 }
 774
 775 void Fuzzer::PurgeAllocator() {
 776   if (Options.PurgeAllocatorIntervalSec < 0 || !EF->__sanitizer_purge_allocator)
 777     return;
 778   if (duration_cast<seconds>(system_clock::now() -
 779                              LastAllocatorPurgeAttemptTime)
 780           .count() < Options.PurgeAllocatorIntervalSec)
 781     return;
 782
 783   if (Options.RssLimitMb <= 0 ||
 784       GetPeakRSSMb() > static_cast<size_t>(Options.RssLimitMb) / 2)
 785     EF->__sanitizer_purge_allocator();
 786
 787   LastAllocatorPurgeAttemptTime = system_clock::now();
 788 }
 789
 790 void Fuzzer::ReadAndExecuteSeedCorpora(std::vector<SizedFile> &CorporaFiles) {
 791   const size_t kMaxSaneLen = 1 << 20;
 792   const size_t kMinDefaultLen = 4096;
 793   size_t MaxSize = 0;
 794   size_t MinSize = -1;
 795   size_t TotalSize = 0;
 796   for (auto &File : CorporaFiles) {
 797     MaxSize = Max(File.Size, MaxSize);
 798     MinSize = Min(File.Size, MinSize);
 799     TotalSize += File.Size;
 800   }
 801   if (Options.MaxLen == 0)
 802     SetMaxInputLen(std::clamp(MaxSize, kMinDefaultLen, kMaxSaneLen));
 803   assert(MaxInputLen > 0);
 804
 805   // Test the callback with empty input and never try it again.
 806   uint8_t dummy = 0;
 807   ExecuteCallback(&dummy, 0);
 808
 809   if (CorporaFiles.empty()) {
 810     Printf("INFO: A corpus is not provided, starting from an empty corpus\n");
 811     Unit U({'\n'}); // Valid ASCII input.
 812     RunOne(U.data(), U.size());
 813   } else {
 814     Printf("INFO: seed corpus: files: %zd min: %zdb max: %zdb total: %zdb"
 815            " rss: %zdMb\n",
 816            CorporaFiles.size(), MinSize, MaxSize, TotalSize, GetPeakRSSMb());
 817     if (Options.ShuffleAtStartUp)
 818       std::shuffle(CorporaFiles.begin(), CorporaFiles.end(), MD.GetRand());
 819
 820     if (Options.PreferSmall) {
 821       std::stable_sort(CorporaFiles.begin(), CorporaFiles.end());
 822       assert(CorporaFiles.front().Size <= CorporaFiles.back().Size);
 823     }
 824
 825     // Load and execute inputs one by one.
 826     for (auto &SF : CorporaFiles) {
 827       auto U = FileToVector(SF.File, MaxInputLen, /*ExitOnError=*/false);
 828       assert(U.size() <= MaxInputLen);
 829       RunOne(U.data(), U.size(), /*MayDeleteFile*/ false, /*II*/ nullptr,
 830              /*ForceAddToCorpus*/ Options.KeepSeed,
 831              /*FoundUniqFeatures*/ nullptr);
 832       CheckExitOnSrcPosOrItem();
 833       TryDetectingAMemoryLeak(U.data(), U.size(),
 834                               /*DuringInitialCorpusExecution*/ true);
 835     }
 836   }
 837
 838   PrintStats("INITED");
 839   if (!Options.FocusFunction.empty()) {
 840     Printf("INFO: %zd/%zd inputs touch the focus function\n",
 841            Corpus.NumInputsThatTouchFocusFunction(), Corpus.size());
 842     if (!Options.DataFlowTrace.empty())
 843       Printf("INFO: %zd/%zd inputs have the Data Flow Trace\n",
 844              Corpus.NumInputsWithDataFlowTrace(),
 845              Corpus.NumInputsThatTouchFocusFunction());
 846   }
 847
 848   if (Corpus.empty() && Options.MaxNumberOfRuns) {
 849     Printf("WARNING: no interesting inputs were found so far. "
 850            "Is the code instrumented for coverage?\n"
 851            "This may also happen if the target rejected all inputs we tried so "
 852            "far\n");
 853     // The remaining logic requires that the corpus is not empty,
 854     // so we add one fake input to the in-memory corpus.
 855     Corpus.AddToCorpus({'\n'}, /*NumFeatures=*/1, /*MayDeleteFile=*/true,
 856                        /*HasFocusFunction=*/false, /*NeverReduce=*/false,
 857                        /*TimeOfUnit=*/duration_cast<microseconds>(0s), {0}, DFT,
 858                        /*BaseII*/ nullptr);
 859   }
 860 }
 861
 862 void Fuzzer::Loop(std::vector<SizedFile> &CorporaFiles) {
 863   auto FocusFunctionOrAuto = Options.FocusFunction;
 864   DFT.Init(Options.DataFlowTrace, &FocusFunctionOrAuto, CorporaFiles,
 865            MD.GetRand());
 866   TPC.SetFocusFunction(FocusFunctionOrAuto);
 867   ReadAndExecuteSeedCorpora(CorporaFiles);
 868   DFT.Clear();  // No need for DFT any more.
 869   TPC.SetPrintNewPCs(Options.PrintNewCovPcs);
 870   TPC.SetPrintNewFuncs(Options.PrintNewCovFuncs);
 871   system_clock::time_point LastCorpusReload = system_clock::now();
 872
 873   TmpMaxMutationLen =
 874       Min(MaxMutationLen, Max(size_t(4), Corpus.MaxInputSize()));
 875
 876   while (true) {
 877     auto Now = system_clock::now();
 878     if (!Options.StopFile.empty() &&
 879         !FileToVector(Options.StopFile, 1, false).empty())
 880       break;
 881     if (duration_cast<seconds>(Now - LastCorpusReload).count() >=
 882         Options.ReloadIntervalSec) {
 883       RereadOutputCorpus(MaxInputLen);
 884       LastCorpusReload = system_clock::now();
 885     }
 886     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 887       break;
 888     if (TimedOut())
 889       break;
 890
 891     // Update TmpMaxMutationLen
 892     if (Options.LenControl) {
 893       if (TmpMaxMutationLen < MaxMutationLen &&
 894           TotalNumberOfRuns - LastCorpusUpdateRun >
 895               Options.LenControl * Log(TmpMaxMutationLen)) {
 896         TmpMaxMutationLen =
 897             Min(MaxMutationLen, TmpMaxMutationLen + Log(TmpMaxMutationLen));
 898         LastCorpusUpdateRun = TotalNumberOfRuns;
 899       }
 900     } else {
 901       TmpMaxMutationLen = MaxMutationLen;
 902     }
 903
 904     // Perform several mutations and runs.
 905     MutateAndTestOne();
 906
 907     PurgeAllocator();
 908   }
 909
 910   PrintStats("DONE  ", "\n");
 911   MD.PrintRecommendedDictionary();
 912 }
 913
 914 void Fuzzer::MinimizeCrashLoop(const Unit &U) {
 915   if (U.size() <= 1)
 916     return;
 917   while (!TimedOut() && TotalNumberOfRuns < Options.MaxNumberOfRuns) {
 918     MD.StartMutationSequence();
 919     memcpy(CurrentUnitData, U.data(), U.size());
 920     for (int i = 0; i < Options.MutateDepth; i++) {
 921       size_t NewSize = MD.Mutate(CurrentUnitData, U.size(), MaxMutationLen);
 922       assert(NewSize > 0 && NewSize <= MaxMutationLen);
 923       ExecuteCallback(CurrentUnitData, NewSize);
 924       PrintPulseAndReportSlowInput(CurrentUnitData, NewSize);
 925       TryDetectingAMemoryLeak(CurrentUnitData, NewSize,
 926                               /*DuringInitialCorpusExecution*/ false);
 927     }
 928   }
 929 }
 930
 931 } // namespace fuzzer
 932
 933 extern "C" {
 934
 935 ATTRIBUTE_INTERFACE size_t
 936 LLVMFuzzerMutate(uint8_t *Data, size_t Size, size_t MaxSize) {
 937   assert(fuzzer::F);
 938   return fuzzer::F->GetMD().DefaultMutate(Data, Size, MaxSize);
 939 }
 940
 941 } // extern "C"