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