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