1 //===- FuzzerLoop.cpp - Fuzzer's main loop --------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 //===----------------------------------------------------------------------===//
12 #include "FuzzerInternal.h"
15 #if defined(__has_include)
16 # if __has_include(<sanitizer/coverage_interface.h>)
17 # include <sanitizer/coverage_interface.h>
22 // Re-declare some of the sanitizer functions as "weak" so that
23 // libFuzzer can be linked w/o the sanitizers and sanitizer-coverage
24 // (in which case it will complain at start-up time).
25 __attribute__((weak)) void __sanitizer_print_stack_trace();
26 __attribute__((weak)) void __sanitizer_reset_coverage();
27 __attribute__((weak)) size_t __sanitizer_get_total_unique_caller_callee_pairs();
28 __attribute__((weak)) size_t __sanitizer_get_total_unique_coverage();
30 void __sanitizer_set_death_callback(void (*callback)(void));
31 __attribute__((weak)) size_t __sanitizer_get_number_of_counters();
33 uintptr_t __sanitizer_update_counter_bitset_and_clear_counters(uint8_t *bitset);
34 __attribute__((weak)) uintptr_t
35 __sanitizer_get_coverage_pc_buffer(uintptr_t **data);
39 static const size_t kMaxUnitSizeToPrint = 256;
41 static void MissingWeakApiFunction(const char *FnName) {
42 Printf("ERROR: %s is not defined. Exiting.\n"
43 "Did you use -fsanitize-coverage=... to build your code?\n", FnName);
47 #define CHECK_WEAK_API_FUNCTION(fn) \
50 MissingWeakApiFunction(#fn); \
53 // Only one Fuzzer per process.
56 Fuzzer::Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options)
57 : USF(USF), Options(Options) {
59 InitializeTraceState();
64 void Fuzzer::SetDeathCallback() {
65 CHECK_WEAK_API_FUNCTION(__sanitizer_set_death_callback);
66 __sanitizer_set_death_callback(StaticDeathCallback);
69 void Fuzzer::PrintUnitInASCII(const Unit &U, const char *PrintAfter) {
70 PrintASCII(U, PrintAfter);
73 void Fuzzer::StaticDeathCallback() {
78 void Fuzzer::DeathCallback() {
80 if (CurrentUnit.size() <= kMaxUnitSizeToPrint) {
81 Print(CurrentUnit, "\n");
82 PrintUnitInASCII(CurrentUnit, "\n");
84 WriteUnitToFileWithPrefix(CurrentUnit, "crash-");
87 void Fuzzer::StaticAlarmCallback() {
92 void Fuzzer::AlarmCallback() {
93 assert(Options.UnitTimeoutSec > 0);
95 duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
96 if (Seconds == 0) return;
97 if (Options.Verbosity >= 2)
98 Printf("AlarmCallback %zd\n", Seconds);
99 if (Seconds >= (size_t)Options.UnitTimeoutSec) {
100 Printf("ALARM: working on the last Unit for %zd seconds\n", Seconds);
101 Printf(" and the timeout value is %d (use -timeout=N to change)\n",
102 Options.UnitTimeoutSec);
103 if (CurrentUnit.size() <= kMaxUnitSizeToPrint) {
104 Print(CurrentUnit, "\n");
105 PrintUnitInASCII(CurrentUnit, "\n");
107 WriteUnitToFileWithPrefix(CurrentUnit, "timeout-");
108 Printf("==%d== ERROR: libFuzzer: timeout after %d seconds\n", GetPid(),
110 if (__sanitizer_print_stack_trace)
111 __sanitizer_print_stack_trace();
112 Printf("SUMMARY: libFuzzer: timeout\n");
117 void Fuzzer::PrintStats(const char *Where, const char *End) {
118 size_t Seconds = secondsSinceProcessStartUp();
119 size_t ExecPerSec = (Seconds ? TotalNumberOfRuns / Seconds : 0);
121 if (Options.OutputCSV) {
122 static bool csvHeaderPrinted = false;
123 if (!csvHeaderPrinted) {
124 csvHeaderPrinted = true;
125 Printf("runs,block_cov,bits,cc_cov,corpus,execs_per_sec,tbms,reason\n");
127 Printf("%zd,%zd,%zd,%zd,%zd,%zd,%zd,%s\n", TotalNumberOfRuns,
128 LastRecordedBlockCoverage, TotalBits(),
129 LastRecordedCallerCalleeCoverage, Corpus.size(), ExecPerSec,
130 TotalNumberOfExecutedTraceBasedMutations, Where);
133 if (!Options.Verbosity)
135 Printf("#%zd\t%s", TotalNumberOfRuns, Where);
136 if (LastRecordedBlockCoverage)
137 Printf(" cov: %zd", LastRecordedBlockCoverage);
138 if (auto TB = TotalBits())
139 Printf(" bits: %zd", TB);
140 if (LastRecordedCallerCalleeCoverage)
141 Printf(" indir: %zd", LastRecordedCallerCalleeCoverage);
142 Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec);
143 if (TotalNumberOfExecutedTraceBasedMutations)
144 Printf(" tbm: %zd", TotalNumberOfExecutedTraceBasedMutations);
148 void Fuzzer::RereadOutputCorpus() {
149 if (Options.OutputCorpus.empty()) return;
150 std::vector<Unit> AdditionalCorpus;
151 ReadDirToVectorOfUnits(Options.OutputCorpus.c_str(), &AdditionalCorpus,
152 &EpochOfLastReadOfOutputCorpus);
153 if (Corpus.empty()) {
154 Corpus = AdditionalCorpus;
157 if (!Options.Reload) return;
158 if (Options.Verbosity >= 2)
159 Printf("Reload: read %zd new units.\n", AdditionalCorpus.size());
160 for (auto &X : AdditionalCorpus) {
161 if (X.size() > (size_t)Options.MaxLen)
162 X.resize(Options.MaxLen);
163 if (UnitHashesAddedToCorpus.insert(Hash(X)).second) {
165 CurrentUnit.insert(CurrentUnit.begin(), X.begin(), X.end());
166 if (RunOne(CurrentUnit)) {
168 PrintStats("RELOAD");
174 void Fuzzer::ShuffleAndMinimize() {
175 bool PreferSmall = (Options.PreferSmallDuringInitialShuffle == 1 ||
176 (Options.PreferSmallDuringInitialShuffle == -1 &&
177 USF.GetRand().RandBool()));
178 if (Options.Verbosity)
179 Printf("PreferSmall: %d\n", PreferSmall);
181 std::vector<Unit> NewCorpus;
182 if (Options.ShuffleAtStartUp) {
183 std::random_shuffle(Corpus.begin(), Corpus.end(), USF.GetRand());
186 Corpus.begin(), Corpus.end(),
187 [](const Unit &A, const Unit &B) { return A.size() < B.size(); });
189 Unit &U = CurrentUnit;
190 for (const auto &C : Corpus) {
191 for (size_t First = 0; First < 1; First++) {
193 size_t Last = std::min(First + Options.MaxLen, C.size());
194 U.insert(U.begin(), C.begin() + First, C.begin() + Last);
195 if (Options.OnlyASCII)
198 NewCorpus.push_back(U);
199 if (Options.Verbosity >= 2)
200 Printf("NEW0: %zd L %zd\n", LastRecordedBlockCoverage, U.size());
205 for (auto &X : Corpus)
206 UnitHashesAddedToCorpus.insert(Hash(X));
207 PrintStats("INITED");
210 bool Fuzzer::RunOne(const Unit &U) {
211 UnitStartTime = system_clock::now();
214 PrepareCoverageBeforeRun();
216 bool Res = CheckCoverageAfterRun();
218 auto UnitStopTime = system_clock::now();
220 duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
221 if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) &&
222 secondsSinceProcessStartUp() >= 2)
223 PrintStats("pulse ");
224 if (TimeOfUnit > TimeOfLongestUnitInSeconds &&
225 TimeOfUnit >= Options.ReportSlowUnits) {
226 TimeOfLongestUnitInSeconds = TimeOfUnit;
227 Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
228 WriteUnitToFileWithPrefix(U, "slow-unit-");
233 void Fuzzer::RunOneAndUpdateCorpus(Unit &U) {
234 if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
236 if (Options.OnlyASCII)
239 ReportNewCoverage(U);
242 void Fuzzer::ExecuteCallback(const Unit &U) {
243 const uint8_t *Data = U.data();
247 int Res = USF.TargetFunction(Data, U.size());
252 size_t Fuzzer::RecordBlockCoverage() {
253 CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage);
254 uintptr_t PrevCoverage = LastRecordedBlockCoverage;
255 LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage();
257 if (PrevCoverage == LastRecordedBlockCoverage || !Options.PrintNewCovPcs)
258 return LastRecordedBlockCoverage;
260 uintptr_t PrevBufferLen = LastCoveragePcBufferLen;
261 uintptr_t *CoverageBuf;
262 LastCoveragePcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf);
264 for (size_t i = PrevBufferLen; i < LastCoveragePcBufferLen; ++i) {
265 Printf("0x%x\n", CoverageBuf[i]);
268 return LastRecordedBlockCoverage;
271 size_t Fuzzer::RecordCallerCalleeCoverage() {
272 if (!Options.UseIndirCalls)
274 if (!__sanitizer_get_total_unique_caller_callee_pairs)
276 return LastRecordedCallerCalleeCoverage =
277 __sanitizer_get_total_unique_caller_callee_pairs();
280 void Fuzzer::PrepareCoverageBeforeRun() {
281 if (Options.UseCounters) {
282 size_t NumCounters = __sanitizer_get_number_of_counters();
283 CounterBitmap.resize(NumCounters);
284 __sanitizer_update_counter_bitset_and_clear_counters(0);
286 RecordBlockCoverage();
287 RecordCallerCalleeCoverage();
290 bool Fuzzer::CheckCoverageAfterRun() {
291 size_t OldCoverage = LastRecordedBlockCoverage;
292 size_t NewCoverage = RecordBlockCoverage();
293 size_t OldCallerCalleeCoverage = LastRecordedCallerCalleeCoverage;
294 size_t NewCallerCalleeCoverage = RecordCallerCalleeCoverage();
295 size_t NumNewBits = 0;
296 if (Options.UseCounters)
297 NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters(
298 CounterBitmap.data());
299 return NewCoverage > OldCoverage ||
300 NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits;
303 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
304 if (Options.OutputCorpus.empty()) return;
305 std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
306 WriteToFile(U, Path);
307 if (Options.Verbosity >= 2)
308 Printf("Written to %s\n", Path.c_str());
309 assert(!Options.OnlyASCII || IsASCII(U));
312 void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) {
313 if (!Options.SaveArtifacts)
315 std::string Path = Options.ArtifactPrefix + Prefix + Hash(U);
316 if (!Options.ExactArtifactPath.empty())
317 Path = Options.ExactArtifactPath; // Overrides ArtifactPrefix.
318 WriteToFile(U, Path);
319 Printf("artifact_prefix='%s'; Test unit written to %s\n",
320 Options.ArtifactPrefix.c_str(), Path.c_str());
321 if (U.size() <= kMaxUnitSizeToPrint)
322 Printf("Base64: %s\n", Base64(U).c_str());
325 void Fuzzer::SaveCorpus() {
326 if (Options.OutputCorpus.empty()) return;
327 for (const auto &U : Corpus)
328 WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
329 if (Options.Verbosity)
330 Printf("Written corpus of %zd files to %s\n", Corpus.size(),
331 Options.OutputCorpus.c_str());
334 void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
335 if (!Options.PrintNEW)
337 PrintStats("NEW ", "");
338 if (Options.Verbosity) {
339 Printf(" L: %zd ", U.size());
340 USF.PrintMutationSequence();
345 void Fuzzer::ReportNewCoverage(const Unit &U) {
347 UnitHashesAddedToCorpus.insert(Hash(U));
348 PrintStatusForNewUnit(U);
349 WriteToOutputCorpus(U);
350 if (Options.ExitOnFirst)
354 void Fuzzer::Merge(const std::vector<std::string> &Corpora) {
355 if (Corpora.size() <= 1) {
356 Printf("Merge requires two or more corpus dirs\n");
359 auto InitialCorpusDir = Corpora[0];
360 ReadDir(InitialCorpusDir, nullptr);
361 Printf("Merge: running the initial corpus '%s' of %d units\n",
362 InitialCorpusDir.c_str(), Corpus.size());
363 for (auto &U : Corpus)
366 std::vector<std::string> ExtraCorpora(Corpora.begin() + 1, Corpora.end());
369 size_t NumMerged = 0;
370 for (auto &C : ExtraCorpora) {
373 Printf("Merge: merging the extra corpus '%s' of %zd units\n", C.c_str(),
375 for (auto &U : Corpus) {
378 WriteToOutputCorpus(U);
383 Printf("Merge: written %zd out of %zd units\n", NumMerged, NumTried);
386 void Fuzzer::MutateAndTestOne() {
387 auto &U = CurrentUnit;
388 USF.StartMutationSequence();
390 U = ChooseUnitToMutate();
392 for (int i = 0; i < Options.MutateDepth; i++) {
393 size_t Size = U.size();
394 U.resize(Options.MaxLen);
395 size_t NewSize = USF.Mutate(U.data(), Size, U.size());
396 assert(NewSize > 0 && "Mutator returned empty unit");
397 assert(NewSize <= (size_t)Options.MaxLen &&
398 "Mutator return overisized unit");
401 StartTraceRecording();
402 RunOneAndUpdateCorpus(U);
403 StopTraceRecording();
407 // Returns an index of random unit from the corpus to mutate.
408 // Hypothesis: units added to the corpus last are more likely to be interesting.
409 // This function gives more wieght to the more recent units.
410 size_t Fuzzer::ChooseUnitIdxToMutate() {
411 size_t N = Corpus.size();
412 size_t Total = (N + 1) * N / 2;
413 size_t R = USF.GetRand()(Total);
414 size_t IdxBeg = 0, IdxEnd = N;
416 while (IdxEnd - IdxBeg >= 2) {
417 size_t Idx = IdxBeg + (IdxEnd - IdxBeg) / 2;
418 if (R > (Idx + 1) * Idx / 2)
427 // Experimental search heuristic: drilling.
428 // - Read, shuffle, execute and minimize the corpus.
429 // - Choose one random unit.
430 // - Reset the coverage.
431 // - Start fuzzing as if the chosen unit was the only element of the corpus.
432 // - When done, reset the coverage again.
433 // - Merge the newly created corpus into the original one.
434 void Fuzzer::Drill() {
435 // The corpus is already read, shuffled, and minimized.
436 assert(!Corpus.empty());
437 Options.PrintNEW = false; // Don't print NEW status lines when drilling.
439 Unit U = ChooseUnitToMutate();
441 CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage);
442 __sanitizer_reset_coverage();
444 std::vector<Unit> SavedCorpus;
445 SavedCorpus.swap(Corpus);
447 assert(Corpus.size() == 1);
449 PrintStats("DRILL ");
450 std::string SavedOutputCorpusPath; // Don't write new units while drilling.
451 SavedOutputCorpusPath.swap(Options.OutputCorpus);
454 __sanitizer_reset_coverage();
456 PrintStats("REINIT");
457 SavedOutputCorpusPath.swap(Options.OutputCorpus);
458 for (auto &U : SavedCorpus) {
462 PrintStats("MERGE ");
463 Options.PrintNEW = true;
464 size_t NumMerged = 0;
465 for (auto &U : Corpus) {
468 PrintStatusForNewUnit(U);
470 WriteToOutputCorpus(U);
473 PrintStats("MERGED");
474 if (NumMerged && Options.Verbosity)
475 Printf("Drilling discovered %zd new units\n", NumMerged);
478 void Fuzzer::Loop() {
479 system_clock::time_point LastCorpusReload = system_clock::now();
480 if (Options.DoCrossOver)
481 USF.SetCorpus(&Corpus);
484 auto Now = system_clock::now();
485 if (duration_cast<seconds>(Now - LastCorpusReload).count()) {
486 RereadOutputCorpus();
487 LastCorpusReload = Now;
489 if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
491 if (Options.MaxTotalTimeSec > 0 &&
492 secondsSinceProcessStartUp() >
493 static_cast<size_t>(Options.MaxTotalTimeSec))
495 // Perform several mutations and runs.
499 PrintStats("DONE ", "\n");
502 void Fuzzer::SyncCorpus() {
503 if (Options.SyncCommand.empty() || Options.OutputCorpus.empty()) return;
504 auto Now = system_clock::now();
505 if (duration_cast<seconds>(Now - LastExternalSync).count() <
508 LastExternalSync = Now;
509 ExecuteCommand(Options.SyncCommand + " " + Options.OutputCorpus);
512 } // namespace fuzzer