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