X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FFuzzer%2FFuzzerLoop.cpp;h=5237682ff24d58001e1d9159133dc792050874c5;hp=f1802f65c37ab59e19c2353fda4ce94d824dde00;hb=43a24b5d9351abd97a0e2378cd167bb9ee6d9a8d;hpb=06465a68cc1eadc91103eab43a304acb4f55963e diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index f1802f65c37..5237682ff24 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -10,11 +10,45 @@ //===----------------------------------------------------------------------===// #include "FuzzerInternal.h" -#include #include +#if defined(__has_include) +# if __has_include() +# include +# endif +#endif + +extern "C" { +// Re-declare some of the sanitizer functions as "weak" so that +// libFuzzer can be linked w/o the sanitizers and sanitizer-coverage +// (in which case it will complain at start-up time). +__attribute__((weak)) void __sanitizer_print_stack_trace(); +__attribute__((weak)) void __sanitizer_reset_coverage(); +__attribute__((weak)) size_t __sanitizer_get_total_unique_caller_callee_pairs(); +__attribute__((weak)) size_t __sanitizer_get_total_unique_coverage(); +__attribute__((weak)) +void __sanitizer_set_death_callback(void (*callback)(void)); +__attribute__((weak)) size_t __sanitizer_get_number_of_counters(); +__attribute__((weak)) +uintptr_t __sanitizer_update_counter_bitset_and_clear_counters(uint8_t *bitset); +__attribute__((weak)) uintptr_t +__sanitizer_get_coverage_pc_buffer(uintptr_t **data); +} + namespace fuzzer { -static const size_t kMaxUnitSizeToPrint = 4096; +static const size_t kMaxUnitSizeToPrint = 256; + +static void MissingWeakApiFunction(const char *FnName) { + Printf("ERROR: %s is not defined. Exiting.\n" + "Did you use -fsanitize-coverage=... to build your code?\n", FnName); + exit(1); +} + +#define CHECK_WEAK_API_FUNCTION(fn) \ + do { \ + if (!fn) \ + MissingWeakApiFunction(#fn); \ + } while (false) // Only one Fuzzer per process. static Fuzzer *F; @@ -28,17 +62,12 @@ Fuzzer::Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options) } void Fuzzer::SetDeathCallback() { + CHECK_WEAK_API_FUNCTION(__sanitizer_set_death_callback); __sanitizer_set_death_callback(StaticDeathCallback); } -void Fuzzer::PrintUnitInASCIIOrTokens(const Unit &U, const char *PrintAfter) { - if (Options.Tokens.empty()) { - PrintASCII(U, PrintAfter); - } else { - auto T = SubstituteTokens(U); - T.push_back(0); - Printf("%s%s", T.data(), PrintAfter); - } +void Fuzzer::PrintUnitInASCII(const Unit &U, const char *PrintAfter) { + PrintASCII(U, PrintAfter); } void Fuzzer::StaticDeathCallback() { @@ -48,8 +77,10 @@ void Fuzzer::StaticDeathCallback() { void Fuzzer::DeathCallback() { Printf("DEATH:\n"); - Print(CurrentUnit, "\n"); - PrintUnitInASCIIOrTokens(CurrentUnit, "\n"); + if (CurrentUnit.size() <= kMaxUnitSizeToPrint) { + Print(CurrentUnit, "\n"); + PrintUnitInASCII(CurrentUnit, "\n"); + } WriteUnitToFileWithPrefix(CurrentUnit, "crash-"); } @@ -69,20 +100,46 @@ void Fuzzer::AlarmCallback() { Printf("ALARM: working on the last Unit for %zd seconds\n", Seconds); Printf(" and the timeout value is %d (use -timeout=N to change)\n", Options.UnitTimeoutSec); - if (CurrentUnit.size() <= kMaxUnitSizeToPrint) + if (CurrentUnit.size() <= kMaxUnitSizeToPrint) { Print(CurrentUnit, "\n"); - PrintUnitInASCIIOrTokens(CurrentUnit, "\n"); + PrintUnitInASCII(CurrentUnit, "\n"); + } WriteUnitToFileWithPrefix(CurrentUnit, "timeout-"); + Printf("==%d== ERROR: libFuzzer: timeout after %d seconds\n", GetPid(), + Seconds); + if (__sanitizer_print_stack_trace) + __sanitizer_print_stack_trace(); + Printf("SUMMARY: libFuzzer: timeout\n"); exit(1); } } -void Fuzzer::PrintStats(const char *Where, size_t Cov, const char *End) { - if (!Options.Verbosity) return; +void Fuzzer::PrintStats(const char *Where, const char *End) { size_t Seconds = secondsSinceProcessStartUp(); size_t ExecPerSec = (Seconds ? TotalNumberOfRuns / Seconds : 0); - Printf("#%zd\t%s cov: %zd bits: %zd units: %zd exec/s: %zd", - TotalNumberOfRuns, Where, Cov, TotalBits(), Corpus.size(), ExecPerSec); + + if (Options.OutputCSV) { + static bool csvHeaderPrinted = false; + if (!csvHeaderPrinted) { + csvHeaderPrinted = true; + Printf("runs,block_cov,bits,cc_cov,corpus,execs_per_sec,tbms,reason\n"); + } + Printf("%zd,%zd,%zd,%zd,%zd,%zd,%zd,%s\n", TotalNumberOfRuns, + LastRecordedBlockCoverage, TotalBits(), + LastRecordedCallerCalleeCoverage, Corpus.size(), ExecPerSec, + TotalNumberOfExecutedTraceBasedMutations, Where); + } + + if (!Options.Verbosity) + return; + Printf("#%zd\t%s", TotalNumberOfRuns, Where); + if (LastRecordedBlockCoverage) + Printf(" cov: %zd", LastRecordedBlockCoverage); + if (auto TB = TotalBits()) + Printf(" bits: %zd", TB); + if (LastRecordedCallerCalleeCoverage) + Printf(" indir: %zd", LastRecordedCallerCalleeCoverage); + Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec); if (TotalNumberOfExecutedTraceBasedMutations) Printf(" tbm: %zd", TotalNumberOfExecutedTraceBasedMutations); Printf("%s", End); @@ -106,30 +163,29 @@ void Fuzzer::RereadOutputCorpus() { if (UnitHashesAddedToCorpus.insert(Hash(X)).second) { CurrentUnit.clear(); CurrentUnit.insert(CurrentUnit.begin(), X.begin(), X.end()); - size_t NewCoverage = RunOne(CurrentUnit); - if (NewCoverage) { + if (RunOne(CurrentUnit)) { Corpus.push_back(X); - if (Options.Verbosity >= 1) - PrintStats("RELOAD", NewCoverage); + PrintStats("RELOAD"); } } } } void Fuzzer::ShuffleAndMinimize() { - size_t MaxCov = 0; bool PreferSmall = (Options.PreferSmallDuringInitialShuffle == 1 || (Options.PreferSmallDuringInitialShuffle == -1 && USF.GetRand().RandBool())); if (Options.Verbosity) Printf("PreferSmall: %d\n", PreferSmall); - PrintStats("READ ", 0); + PrintStats("READ "); std::vector NewCorpus; - std::random_shuffle(Corpus.begin(), Corpus.end(), USF.GetRand()); - if (PreferSmall) - std::stable_sort( - Corpus.begin(), Corpus.end(), - [](const Unit &A, const Unit &B) { return A.size() < B.size(); }); + if (Options.ShuffleAtStartUp) { + std::random_shuffle(Corpus.begin(), Corpus.end(), USF.GetRand()); + if (PreferSmall) + std::stable_sort( + Corpus.begin(), Corpus.end(), + [](const Unit &A, const Unit &B) { return A.size() < B.size(); }); + } Unit &U = CurrentUnit; for (const auto &C : Corpus) { for (size_t First = 0; First < 1; First++) { @@ -138,38 +194,37 @@ void Fuzzer::ShuffleAndMinimize() { U.insert(U.begin(), C.begin() + First, C.begin() + Last); if (Options.OnlyASCII) ToASCII(U); - size_t NewCoverage = RunOne(U); - if (NewCoverage) { - MaxCov = NewCoverage; + if (RunOne(U)) { NewCorpus.push_back(U); if (Options.Verbosity >= 2) - Printf("NEW0: %zd L %zd\n", NewCoverage, U.size()); + Printf("NEW0: %zd L %zd\n", LastRecordedBlockCoverage, U.size()); } } } Corpus = NewCorpus; for (auto &X : Corpus) UnitHashesAddedToCorpus.insert(Hash(X)); - PrintStats("INITED", MaxCov); + PrintStats("INITED"); } -size_t Fuzzer::RunOne(const Unit &U) { +bool Fuzzer::RunOne(const Unit &U) { UnitStartTime = system_clock::now(); TotalNumberOfRuns++; - size_t Res = 0; - if (Options.UseFullCoverageSet) - Res = RunOneMaximizeFullCoverageSet(U); - else - Res = RunOneMaximizeTotalCoverage(U); + + PrepareCoverageBeforeRun(); + ExecuteCallback(U); + bool Res = CheckCoverageAfterRun(); + auto UnitStopTime = system_clock::now(); auto TimeOfUnit = duration_cast(UnitStopTime - UnitStartTime).count(); + if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && + secondsSinceProcessStartUp() >= 2) + PrintStats("pulse "); if (TimeOfUnit > TimeOfLongestUnitInSeconds && TimeOfUnit >= Options.ReportSlowUnits) { TimeOfLongestUnitInSeconds = TimeOfUnit; Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds); - if (U.size() <= kMaxUnitSizeToPrint) - Print(U, "\n"); WriteUnitToFileWithPrefix(U, "slow-unit-"); } return Res; @@ -180,76 +235,69 @@ void Fuzzer::RunOneAndUpdateCorpus(Unit &U) { return; if (Options.OnlyASCII) ToASCII(U); - ReportNewCoverage(RunOne(U), U); + if (RunOne(U)) + ReportNewCoverage(U); } -static uintptr_t HashOfArrayOfPCs(uintptr_t *PCs, uintptr_t NumPCs) { - uintptr_t Res = 0; - for (uintptr_t i = 0; i < NumPCs; i++) { - Res = (Res + PCs[i]) * 7; - } - return Res; +void Fuzzer::ExecuteCallback(const Unit &U) { + const uint8_t *Data = U.data(); + uint8_t EmptyData; + if (!Data) + Data = &EmptyData; + int Res = USF.TargetFunction(Data, U.size()); + (void)Res; + assert(Res == 0); } -Unit Fuzzer::SubstituteTokens(const Unit &U) const { - Unit Res; - for (auto Idx : U) { - if (Idx < Options.Tokens.size()) { - std::string Token = Options.Tokens[Idx]; - Res.insert(Res.end(), Token.begin(), Token.end()); - } else { - Res.push_back(' '); - } - } - // FIXME: Apply DFSan labels. - return Res; -} +size_t Fuzzer::RecordBlockCoverage() { + CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage); + uintptr_t PrevCoverage = LastRecordedBlockCoverage; + LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage(); -void Fuzzer::ExecuteCallback(const Unit &U) { - if (Options.Tokens.empty()) { - USF.TargetFunction(U.data(), U.size()); - } else { - auto T = SubstituteTokens(U); - USF.TargetFunction(T.data(), T.size()); + if (PrevCoverage == LastRecordedBlockCoverage || !Options.PrintNewCovPcs) + return LastRecordedBlockCoverage; + + uintptr_t PrevBufferLen = LastCoveragePcBufferLen; + uintptr_t *CoverageBuf; + LastCoveragePcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf); + assert(CoverageBuf); + for (size_t i = PrevBufferLen; i < LastCoveragePcBufferLen; ++i) { + Printf("0x%x\n", CoverageBuf[i]); } + + return LastRecordedBlockCoverage; } -// Experimental. -// Fuly reset the current coverage state, run a single unit, -// compute a hash function from the full coverage set, -// return non-zero if the hash value is new. -// This produces tons of new units and as is it's only suitable for small tests, -// e.g. test/FullCoverageSetTest.cpp. FIXME: make it scale. -size_t Fuzzer::RunOneMaximizeFullCoverageSet(const Unit &U) { - __sanitizer_reset_coverage(); - ExecuteCallback(U); - uintptr_t *PCs; - uintptr_t NumPCs =__sanitizer_get_coverage_guards(&PCs); - if (FullCoverageSets.insert(HashOfArrayOfPCs(PCs, NumPCs)).second) - return FullCoverageSets.size(); - return 0; +size_t Fuzzer::RecordCallerCalleeCoverage() { + if (!Options.UseIndirCalls) + return 0; + if (!__sanitizer_get_total_unique_caller_callee_pairs) + return 0; + return LastRecordedCallerCalleeCoverage = + __sanitizer_get_total_unique_caller_callee_pairs(); } -size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) { - size_t NumCounters = __sanitizer_get_number_of_counters(); +void Fuzzer::PrepareCoverageBeforeRun() { if (Options.UseCounters) { + size_t NumCounters = __sanitizer_get_number_of_counters(); CounterBitmap.resize(NumCounters); __sanitizer_update_counter_bitset_and_clear_counters(0); } - size_t OldCoverage = __sanitizer_get_total_unique_coverage(); - ExecuteCallback(U); - size_t NewCoverage = __sanitizer_get_total_unique_coverage(); + RecordBlockCoverage(); + RecordCallerCalleeCoverage(); +} + +bool Fuzzer::CheckCoverageAfterRun() { + size_t OldCoverage = LastRecordedBlockCoverage; + size_t NewCoverage = RecordBlockCoverage(); + size_t OldCallerCalleeCoverage = LastRecordedCallerCalleeCoverage; + size_t NewCallerCalleeCoverage = RecordCallerCalleeCoverage(); size_t NumNewBits = 0; if (Options.UseCounters) NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters( CounterBitmap.data()); - - if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) - PrintStats("pulse ", NewCoverage); - - if (NewCoverage > OldCoverage || NumNewBits) - return NewCoverage; - return 0; + return NewCoverage > OldCoverage || + NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits; } void Fuzzer::WriteToOutputCorpus(const Unit &U) { @@ -262,13 +310,16 @@ void Fuzzer::WriteToOutputCorpus(const Unit &U) { } void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) { - std::string Path = Prefix + Hash(U); + if (!Options.SaveArtifacts) + return; + std::string Path = Options.ArtifactPrefix + Prefix + Hash(U); + if (!Options.ExactArtifactPath.empty()) + Path = Options.ExactArtifactPath; // Overrides ArtifactPrefix. WriteToFile(U, Path); - Printf("Test unit written to %s\n", Path.c_str()); - if (U.size() <= kMaxUnitSizeToPrint) { - Printf("Base64: "); - PrintFileAsBase64(Path); - } + Printf("artifact_prefix='%s'; Test unit written to %s\n", + Options.ArtifactPrefix.c_str(), Path.c_str()); + if (U.size() <= kMaxUnitSizeToPrint) + Printf("Base64: %s\n", Base64(U).c_str()); } void Fuzzer::SaveCorpus() { @@ -280,82 +331,172 @@ void Fuzzer::SaveCorpus() { Options.OutputCorpus.c_str()); } -void Fuzzer::ReportNewCoverage(size_t NewCoverage, const Unit &U) { - if (!NewCoverage) return; - Corpus.push_back(U); - UnitHashesAddedToCorpus.insert(Hash(U)); - PrintStats("NEW ", NewCoverage, ""); +void Fuzzer::PrintStatusForNewUnit(const Unit &U) { + if (!Options.PrintNEW) + return; + PrintStats("NEW ", ""); if (Options.Verbosity) { - Printf(" L: %zd", U.size()); - if (U.size() < 30) { - Printf(" "); - PrintUnitInASCIIOrTokens(U, "\t"); - Print(U); - } + Printf(" L: %zd ", U.size()); + USF.PrintMutationSequence(); Printf("\n"); } +} + +void Fuzzer::ReportNewCoverage(const Unit &U) { + Corpus.push_back(U); + UnitHashesAddedToCorpus.insert(Hash(U)); + PrintStatusForNewUnit(U); WriteToOutputCorpus(U); if (Options.ExitOnFirst) exit(0); } -void Fuzzer::MutateAndTestOne(Unit *U) { +void Fuzzer::Merge(const std::vector &Corpora) { + if (Corpora.size() <= 1) { + Printf("Merge requires two or more corpus dirs\n"); + return; + } + auto InitialCorpusDir = Corpora[0]; + ReadDir(InitialCorpusDir, nullptr); + Printf("Merge: running the initial corpus '%s' of %d units\n", + InitialCorpusDir.c_str(), Corpus.size()); + for (auto &U : Corpus) + RunOne(U); + + std::vector ExtraCorpora(Corpora.begin() + 1, Corpora.end()); + + size_t NumTried = 0; + size_t NumMerged = 0; + for (auto &C : ExtraCorpora) { + Corpus.clear(); + ReadDir(C, nullptr); + Printf("Merge: merging the extra corpus '%s' of %zd units\n", C.c_str(), + Corpus.size()); + for (auto &U : Corpus) { + NumTried++; + if (RunOne(U)) { + WriteToOutputCorpus(U); + NumMerged++; + } + } + } + Printf("Merge: written %zd out of %zd units\n", NumMerged, NumTried); +} + +void Fuzzer::MutateAndTestOne() { + auto &U = CurrentUnit; + USF.StartMutationSequence(); + + U = ChooseUnitToMutate(); + for (int i = 0; i < Options.MutateDepth; i++) { - StartTraceRecording(); - size_t Size = U->size(); - U->resize(Options.MaxLen); - size_t NewSize = USF.Mutate(U->data(), Size, U->size()); + size_t Size = U.size(); + U.resize(Options.MaxLen); + size_t NewSize = USF.Mutate(U.data(), Size, U.size()); assert(NewSize > 0 && "Mutator returned empty unit"); assert(NewSize <= (size_t)Options.MaxLen && "Mutator return overisized unit"); - U->resize(NewSize); - RunOneAndUpdateCorpus(*U); - size_t NumTraceBasedMutations = StopTraceRecording(); - size_t TBMWidth = - std::min((size_t)Options.TBMWidth, NumTraceBasedMutations); - size_t TBMDepth = - std::min((size_t)Options.TBMDepth, NumTraceBasedMutations); - Unit BackUp = *U; - for (size_t w = 0; w < TBMWidth; w++) { - *U = BackUp; - for (size_t d = 0; d < TBMDepth; d++) { - TotalNumberOfExecutedTraceBasedMutations++; - ApplyTraceBasedMutation(USF.GetRand()(NumTraceBasedMutations), U); - RunOneAndUpdateCorpus(*U); - } + U.resize(NewSize); + if (i == 0) + StartTraceRecording(); + RunOneAndUpdateCorpus(U); + StopTraceRecording(); + } +} + +// Returns an index of random unit from the corpus to mutate. +// Hypothesis: units added to the corpus last are more likely to be interesting. +// This function gives more wieght to the more recent units. +size_t Fuzzer::ChooseUnitIdxToMutate() { + size_t N = Corpus.size(); + size_t Total = (N + 1) * N / 2; + size_t R = USF.GetRand()(Total); + size_t IdxBeg = 0, IdxEnd = N; + // Binary search. + while (IdxEnd - IdxBeg >= 2) { + size_t Idx = IdxBeg + (IdxEnd - IdxBeg) / 2; + if (R > (Idx + 1) * Idx / 2) + IdxBeg = Idx; + else + IdxEnd = Idx; + } + assert(IdxBeg < N); + return IdxBeg; +} + +// Experimental search heuristic: drilling. +// - Read, shuffle, execute and minimize the corpus. +// - Choose one random unit. +// - Reset the coverage. +// - Start fuzzing as if the chosen unit was the only element of the corpus. +// - When done, reset the coverage again. +// - Merge the newly created corpus into the original one. +void Fuzzer::Drill() { + // The corpus is already read, shuffled, and minimized. + assert(!Corpus.empty()); + Options.PrintNEW = false; // Don't print NEW status lines when drilling. + + Unit U = ChooseUnitToMutate(); + + CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage); + __sanitizer_reset_coverage(); + + std::vector SavedCorpus; + SavedCorpus.swap(Corpus); + Corpus.push_back(U); + assert(Corpus.size() == 1); + RunOne(U); + PrintStats("DRILL "); + std::string SavedOutputCorpusPath; // Don't write new units while drilling. + SavedOutputCorpusPath.swap(Options.OutputCorpus); + Loop(); + + __sanitizer_reset_coverage(); + + PrintStats("REINIT"); + SavedOutputCorpusPath.swap(Options.OutputCorpus); + for (auto &U : SavedCorpus) { + CurrentUnit = U; + RunOne(U); + } + PrintStats("MERGE "); + Options.PrintNEW = true; + size_t NumMerged = 0; + for (auto &U : Corpus) { + CurrentUnit = U; + if (RunOne(U)) { + PrintStatusForNewUnit(U); + NumMerged++; + WriteToOutputCorpus(U); } } + PrintStats("MERGED"); + if (NumMerged && Options.Verbosity) + Printf("Drilling discovered %zd new units\n", NumMerged); } void Fuzzer::Loop() { - for (auto &U: Options.Dictionary) - USF.GetMD().AddWordToDictionary(U.data(), U.size()); - + system_clock::time_point LastCorpusReload = system_clock::now(); + if (Options.DoCrossOver) + USF.SetCorpus(&Corpus); while (true) { - for (size_t J1 = 0; J1 < Corpus.size(); J1++) { - SyncCorpus(); + SyncCorpus(); + auto Now = system_clock::now(); + if (duration_cast(Now - LastCorpusReload).count()) { RereadOutputCorpus(); - if (TotalNumberOfRuns >= Options.MaxNumberOfRuns) - return; - // First, simply mutate the unit w/o doing crosses. - CurrentUnit = Corpus[J1]; - MutateAndTestOne(&CurrentUnit); - // Now, cross with others. - if (Options.DoCrossOver && !Corpus[J1].empty()) { - for (size_t J2 = 0; J2 < Corpus.size(); J2++) { - CurrentUnit.resize(Options.MaxLen); - size_t NewSize = USF.CrossOver( - Corpus[J1].data(), Corpus[J1].size(), Corpus[J2].data(), - Corpus[J2].size(), CurrentUnit.data(), CurrentUnit.size()); - assert(NewSize > 0 && "CrossOver returned empty unit"); - assert(NewSize <= (size_t)Options.MaxLen && - "CrossOver return overisized unit"); - CurrentUnit.resize(NewSize); - MutateAndTestOne(&CurrentUnit); - } - } + LastCorpusReload = Now; } + if (TotalNumberOfRuns >= Options.MaxNumberOfRuns) + break; + if (Options.MaxTotalTimeSec > 0 && + secondsSinceProcessStartUp() > + static_cast(Options.MaxTotalTimeSec)) + break; + // Perform several mutations and runs. + MutateAndTestOne(); } + + PrintStats("DONE ", "\n"); } void Fuzzer::SyncCorpus() {