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"
13 #include <sanitizer/coverage_interface.h>
17 // Re-declare some of the sanitizer functions as "weak" so that
18 // libFuzzer can be linked w/o the sanitizers and sanitizer-coveragte
19 // (in which case it will complain at start-up time).
20 __attribute__((weak)) void __sanitizer_print_stack_trace();
21 __attribute__((weak)) size_t __sanitizer_get_total_unique_caller_callee_pairs();
22 __attribute__((weak)) size_t __sanitizer_get_total_unique_coverage();
24 void __sanitizer_set_death_callback(void (*callback)(void));
25 __attribute__((weak)) size_t __sanitizer_get_number_of_counters();
27 uintptr_t __sanitizer_update_counter_bitset_and_clear_counters(uint8_t *bitset);
31 static const size_t kMaxUnitSizeToPrint = 256;
33 static void MissingWeakApiFunction(const char *FnName) {
34 Printf("ERROR: %s is not defined. Exiting.\n"
35 "Did you use -fsanitize-coverage=... to build your code?\n", FnName);
39 #define CHECK_WEAK_API_FUNCTION(fn) \
42 MissingWeakApiFunction(#fn); \
45 // Only one Fuzzer per process.
48 Fuzzer::Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options)
49 : USF(USF), Options(Options) {
51 InitializeTraceState();
56 void Fuzzer::SetDeathCallback() {
57 CHECK_WEAK_API_FUNCTION(__sanitizer_set_death_callback);
58 __sanitizer_set_death_callback(StaticDeathCallback);
61 void Fuzzer::PrintUnitInASCII(const Unit &U, const char *PrintAfter) {
62 PrintASCII(U, PrintAfter);
65 void Fuzzer::StaticDeathCallback() {
70 void Fuzzer::DeathCallback() {
72 if (CurrentUnit.size() <= kMaxUnitSizeToPrint) {
73 Print(CurrentUnit, "\n");
74 PrintUnitInASCII(CurrentUnit, "\n");
76 WriteUnitToFileWithPrefix(CurrentUnit, "crash-");
79 void Fuzzer::StaticAlarmCallback() {
84 void Fuzzer::AlarmCallback() {
85 assert(Options.UnitTimeoutSec > 0);
87 duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
88 if (Seconds == 0) return;
89 if (Options.Verbosity >= 2)
90 Printf("AlarmCallback %zd\n", Seconds);
91 if (Seconds >= (size_t)Options.UnitTimeoutSec) {
92 Printf("ALARM: working on the last Unit for %zd seconds\n", Seconds);
93 Printf(" and the timeout value is %d (use -timeout=N to change)\n",
94 Options.UnitTimeoutSec);
95 if (CurrentUnit.size() <= kMaxUnitSizeToPrint) {
96 Print(CurrentUnit, "\n");
97 PrintUnitInASCII(CurrentUnit, "\n");
99 WriteUnitToFileWithPrefix(CurrentUnit, "timeout-");
100 Printf("==%d== ERROR: libFuzzer: timeout after %d seconds\n", GetPid(),
102 if (__sanitizer_print_stack_trace)
103 __sanitizer_print_stack_trace();
104 Printf("SUMMARY: libFuzzer: timeout\n");
109 void Fuzzer::PrintStats(const char *Where, const char *End) {
110 if (!Options.Verbosity) return;
111 size_t Seconds = secondsSinceProcessStartUp();
112 size_t ExecPerSec = (Seconds ? TotalNumberOfRuns / Seconds : 0);
113 Printf("#%zd\t%s", TotalNumberOfRuns, Where);
114 if (LastRecordedBlockCoverage)
115 Printf(" cov: %zd", LastRecordedBlockCoverage);
116 if (auto TB = TotalBits())
117 Printf(" bits: %zd", TB);
118 if (LastRecordedCallerCalleeCoverage)
119 Printf(" indir: %zd", LastRecordedCallerCalleeCoverage);
120 Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec);
121 if (TotalNumberOfExecutedTraceBasedMutations)
122 Printf(" tbm: %zd", TotalNumberOfExecutedTraceBasedMutations);
126 void Fuzzer::RereadOutputCorpus() {
127 if (Options.OutputCorpus.empty()) return;
128 std::vector<Unit> AdditionalCorpus;
129 ReadDirToVectorOfUnits(Options.OutputCorpus.c_str(), &AdditionalCorpus,
130 &EpochOfLastReadOfOutputCorpus);
131 if (Corpus.empty()) {
132 Corpus = AdditionalCorpus;
135 if (!Options.Reload) return;
136 if (Options.Verbosity >= 2)
137 Printf("Reload: read %zd new units.\n", AdditionalCorpus.size());
138 for (auto &X : AdditionalCorpus) {
139 if (X.size() > (size_t)Options.MaxLen)
140 X.resize(Options.MaxLen);
141 if (UnitHashesAddedToCorpus.insert(Hash(X)).second) {
143 CurrentUnit.insert(CurrentUnit.begin(), X.begin(), X.end());
144 if (RunOne(CurrentUnit)) {
146 if (Options.Verbosity >= 1)
147 PrintStats("RELOAD");
153 void Fuzzer::ShuffleAndMinimize() {
154 bool PreferSmall = (Options.PreferSmallDuringInitialShuffle == 1 ||
155 (Options.PreferSmallDuringInitialShuffle == -1 &&
156 USF.GetRand().RandBool()));
157 if (Options.Verbosity)
158 Printf("PreferSmall: %d\n", PreferSmall);
160 std::vector<Unit> NewCorpus;
161 if (Options.ShuffleAtStartUp) {
162 std::random_shuffle(Corpus.begin(), Corpus.end(), USF.GetRand());
165 Corpus.begin(), Corpus.end(),
166 [](const Unit &A, const Unit &B) { return A.size() < B.size(); });
168 Unit &U = CurrentUnit;
169 for (const auto &C : Corpus) {
170 for (size_t First = 0; First < 1; First++) {
172 size_t Last = std::min(First + Options.MaxLen, C.size());
173 U.insert(U.begin(), C.begin() + First, C.begin() + Last);
174 if (Options.OnlyASCII)
177 NewCorpus.push_back(U);
178 if (Options.Verbosity >= 2)
179 Printf("NEW0: %zd L %zd\n", LastRecordedBlockCoverage, U.size());
184 for (auto &X : Corpus)
185 UnitHashesAddedToCorpus.insert(Hash(X));
186 PrintStats("INITED");
189 bool Fuzzer::RunOne(const Unit &U) {
190 UnitStartTime = system_clock::now();
193 PrepareCoverageBeforeRun();
195 bool Res = CheckCoverageAfterRun();
197 auto UnitStopTime = system_clock::now();
199 duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
200 if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1))
201 && secondsSinceProcessStartUp() >= 2
202 && Options.Verbosity)
203 PrintStats("pulse ");
204 if (TimeOfUnit > TimeOfLongestUnitInSeconds &&
205 TimeOfUnit >= Options.ReportSlowUnits) {
206 TimeOfLongestUnitInSeconds = TimeOfUnit;
207 Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
208 WriteUnitToFileWithPrefix(U, "slow-unit-");
213 void Fuzzer::RunOneAndUpdateCorpus(Unit &U) {
214 if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
216 if (Options.OnlyASCII)
219 ReportNewCoverage(U);
222 void Fuzzer::ExecuteCallback(const Unit &U) {
223 int Res = USF.TargetFunction(U.data(), U.size());
228 size_t Fuzzer::RecordBlockCoverage() {
229 CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage);
230 return LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage();
233 size_t Fuzzer::RecordCallerCalleeCoverage() {
234 if (!Options.UseIndirCalls)
236 if (!__sanitizer_get_total_unique_caller_callee_pairs)
238 return LastRecordedCallerCalleeCoverage =
239 __sanitizer_get_total_unique_caller_callee_pairs();
242 void Fuzzer::PrepareCoverageBeforeRun() {
243 if (Options.UseCounters) {
244 size_t NumCounters = __sanitizer_get_number_of_counters();
245 CounterBitmap.resize(NumCounters);
246 __sanitizer_update_counter_bitset_and_clear_counters(0);
248 RecordBlockCoverage();
249 RecordCallerCalleeCoverage();
252 bool Fuzzer::CheckCoverageAfterRun() {
253 size_t OldCoverage = LastRecordedBlockCoverage;
254 size_t NewCoverage = RecordBlockCoverage();
255 size_t OldCallerCalleeCoverage = LastRecordedCallerCalleeCoverage;
256 size_t NewCallerCalleeCoverage = RecordCallerCalleeCoverage();
257 size_t NumNewBits = 0;
258 if (Options.UseCounters)
259 NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters(
260 CounterBitmap.data());
261 return NewCoverage > OldCoverage ||
262 NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits;
265 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
266 if (Options.OutputCorpus.empty()) return;
267 std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
268 WriteToFile(U, Path);
269 if (Options.Verbosity >= 2)
270 Printf("Written to %s\n", Path.c_str());
271 assert(!Options.OnlyASCII || IsASCII(U));
274 void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) {
275 if (!Options.SaveArtifacts)
277 std::string Path = Options.ArtifactPrefix + Prefix + Hash(U);
278 WriteToFile(U, Path);
279 Printf("artifact_prefix='%s'; Test unit written to %s\n",
280 Options.ArtifactPrefix.c_str(), Path.c_str());
281 if (U.size() <= kMaxUnitSizeToPrint) {
283 PrintFileAsBase64(Path);
287 void Fuzzer::SaveCorpus() {
288 if (Options.OutputCorpus.empty()) return;
289 for (const auto &U : Corpus)
290 WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
291 if (Options.Verbosity)
292 Printf("Written corpus of %zd files to %s\n", Corpus.size(),
293 Options.OutputCorpus.c_str());
296 void Fuzzer::ReportNewCoverage(const Unit &U) {
298 UnitHashesAddedToCorpus.insert(Hash(U));
299 PrintStats("NEW ", "");
300 if (Options.Verbosity) {
301 Printf(" L: %zd", U.size());
304 PrintUnitInASCII(U, "\t");
309 WriteToOutputCorpus(U);
310 if (Options.ExitOnFirst)
314 void Fuzzer::Merge(const std::vector<std::string> &Corpora) {
315 if (Corpora.size() <= 1) {
316 Printf("Merge requires two or more corpus dirs\n");
319 auto InitialCorpusDir = Corpora[0];
320 ReadDir(InitialCorpusDir, nullptr);
321 Printf("Merge: running the initial corpus '%s' of %d units\n",
322 InitialCorpusDir.c_str(), Corpus.size());
323 for (auto &U : Corpus)
326 std::vector<std::string> ExtraCorpora(Corpora.begin() + 1, Corpora.end());
329 size_t NumMerged = 0;
330 for (auto &C : ExtraCorpora) {
333 Printf("Merge: merging the extra corpus '%s' of %zd units\n", C.c_str(),
335 for (auto &U : Corpus) {
338 WriteToOutputCorpus(U);
343 Printf("Merge: written %zd out of %zd units\n", NumMerged, NumTried);
346 void Fuzzer::MutateAndTestOne(Unit *U) {
347 for (int i = 0; i < Options.MutateDepth; i++) {
348 StartTraceRecording();
349 size_t Size = U->size();
350 U->resize(Options.MaxLen);
351 size_t NewSize = USF.Mutate(U->data(), Size, U->size());
352 assert(NewSize > 0 && "Mutator returned empty unit");
353 assert(NewSize <= (size_t)Options.MaxLen &&
354 "Mutator return overisized unit");
356 RunOneAndUpdateCorpus(*U);
357 size_t NumTraceBasedMutations = StopTraceRecording();
359 std::min((size_t)Options.TBMWidth, NumTraceBasedMutations);
361 std::min((size_t)Options.TBMDepth, NumTraceBasedMutations);
363 for (size_t w = 0; w < TBMWidth; w++) {
365 for (size_t d = 0; d < TBMDepth; d++) {
366 TotalNumberOfExecutedTraceBasedMutations++;
367 ApplyTraceBasedMutation(USF.GetRand()(NumTraceBasedMutations), U);
368 RunOneAndUpdateCorpus(*U);
374 // Returns an index of random unit from the corpus to mutate.
375 // Hypothesis: units added to the corpus last are more likely to be interesting.
376 // This function gives more wieght to the more recent units.
377 size_t Fuzzer::ChooseUnitToMutate() {
378 size_t N = Corpus.size();
379 size_t Total = (N + 1) * N / 2;
380 size_t R = USF.GetRand()(Total);
381 size_t IdxBeg = 0, IdxEnd = N;
383 while (IdxEnd - IdxBeg >= 2) {
384 size_t Idx = IdxBeg + (IdxEnd - IdxBeg) / 2;
385 if (R > (Idx + 1) * Idx / 2)
394 void Fuzzer::Loop() {
395 for (auto &U: Options.Dictionary)
396 USF.GetMD().AddWordToDictionary(U.data(), U.size());
399 size_t J1 = ChooseUnitToMutate();;
401 RereadOutputCorpus();
402 if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
404 if (Options.MaxTotalTimeSec > 0 &&
405 secondsSinceProcessStartUp() >
406 static_cast<size_t>(Options.MaxTotalTimeSec))
408 CurrentUnit = Corpus[J1];
409 // Optionally, cross with another unit.
410 if (Options.DoCrossOver && USF.GetRand().RandBool()) {
411 size_t J2 = ChooseUnitToMutate();
412 if (!Corpus[J1].empty() && !Corpus[J2].empty()) {
413 assert(!Corpus[J2].empty());
414 CurrentUnit.resize(Options.MaxLen);
415 size_t NewSize = USF.CrossOver(
416 Corpus[J1].data(), Corpus[J1].size(), Corpus[J2].data(),
417 Corpus[J2].size(), CurrentUnit.data(), CurrentUnit.size());
418 assert(NewSize > 0 && "CrossOver returned empty unit");
419 assert(NewSize <= (size_t)Options.MaxLen &&
420 "CrossOver returned overisized unit");
421 CurrentUnit.resize(NewSize);
424 // Perform several mutations and runs.
425 MutateAndTestOne(&CurrentUnit);
429 void Fuzzer::SyncCorpus() {
430 if (Options.SyncCommand.empty() || Options.OutputCorpus.empty()) return;
431 auto Now = system_clock::now();
432 if (duration_cast<seconds>(Now - LastExternalSync).count() <
435 LastExternalSync = Now;
436 ExecuteCommand(Options.SyncCommand + " " + Options.OutputCorpus);
439 } // namespace fuzzer