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