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