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