X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FFuzzer%2FFuzzerLoop.cpp;h=5237682ff24d58001e1d9159133dc792050874c5;hp=9347831119d106b2e417caa4ccbad381671999d1;hb=43a24b5d9351abd97a0e2378cd167bb9ee6d9a8d;hpb=1969ec112de1093bd09385ba6cb6c9e7d2ae3463 diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 9347831119d..5237682ff24 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -10,16 +10,46 @@ //===----------------------------------------------------------------------===// #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 = 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; @@ -32,6 +62,7 @@ Fuzzer::Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options) } void Fuzzer::SetDeathCallback() { + CHECK_WEAK_API_FUNCTION(__sanitizer_set_death_callback); __sanitizer_set_death_callback(StaticDeathCallback); } @@ -83,14 +114,31 @@ void Fuzzer::AlarmCallback() { } } -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); + + 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); - Printf(" cov: %zd", Cov); + 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); @@ -117,8 +165,7 @@ void Fuzzer::RereadOutputCorpus() { CurrentUnit.insert(CurrentUnit.begin(), X.begin(), X.end()); if (RunOne(CurrentUnit)) { Corpus.push_back(X); - if (Options.Verbosity >= 1) - PrintStats("RELOAD", LastRecordedBlockCoverage); + PrintStats("RELOAD"); } } } @@ -130,7 +177,7 @@ void Fuzzer::ShuffleAndMinimize() { USF.GetRand().RandBool())); if (Options.Verbosity) Printf("PreferSmall: %d\n", PreferSmall); - PrintStats("READ ", 0); + PrintStats("READ "); std::vector NewCorpus; if (Options.ShuffleAtStartUp) { std::random_shuffle(Corpus.begin(), Corpus.end(), USF.GetRand()); @@ -157,7 +204,7 @@ void Fuzzer::ShuffleAndMinimize() { Corpus = NewCorpus; for (auto &X : Corpus) UnitHashesAddedToCorpus.insert(Hash(X)); - PrintStats("INITED", LastRecordedBlockCoverage); + PrintStats("INITED"); } bool Fuzzer::RunOne(const Unit &U) { @@ -171,8 +218,9 @@ bool Fuzzer::RunOne(const Unit &U) { auto UnitStopTime = system_clock::now(); auto TimeOfUnit = duration_cast(UnitStopTime - UnitStartTime).count(); - if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) - PrintStats("pulse ", LastRecordedBlockCoverage); + if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && + secondsSinceProcessStartUp() >= 2) + PrintStats("pulse "); if (TimeOfUnit > TimeOfLongestUnitInSeconds && TimeOfUnit >= Options.ReportSlowUnits) { TimeOfLongestUnitInSeconds = TimeOfUnit; @@ -192,13 +240,41 @@ void Fuzzer::RunOneAndUpdateCorpus(Unit &U) { } void Fuzzer::ExecuteCallback(const Unit &U) { - int Res = USF.TargetFunction(U.data(), U.size()); + 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); } size_t Fuzzer::RecordBlockCoverage() { - return LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage(); + CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage); + uintptr_t PrevCoverage = LastRecordedBlockCoverage; + LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage(); + + 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; +} + +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(); } void Fuzzer::PrepareCoverageBeforeRun() { @@ -208,16 +284,20 @@ void Fuzzer::PrepareCoverageBeforeRun() { __sanitizer_update_counter_bitset_and_clear_counters(0); } 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()); - return NewCoverage > OldCoverage || NumNewBits; + return NewCoverage > OldCoverage || + NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits; } void Fuzzer::WriteToOutputCorpus(const Unit &U) { @@ -233,13 +313,13 @@ void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) { 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("artifact_prefix='%s'; Test unit written to %s\n", Options.ArtifactPrefix.c_str(), Path.c_str()); - if (U.size() <= kMaxUnitSizeToPrint) { - Printf("Base64: "); - PrintFileAsBase64(Path); - } + if (U.size() <= kMaxUnitSizeToPrint) + Printf("Base64: %s\n", Base64(U).c_str()); } void Fuzzer::SaveCorpus() { @@ -251,86 +331,172 @@ void Fuzzer::SaveCorpus() { Options.OutputCorpus.c_str()); } -void Fuzzer::ReportNewCoverage(const Unit &U) { - Corpus.push_back(U); - UnitHashesAddedToCorpus.insert(Hash(U)); - PrintStats("NEW ", LastRecordedBlockCoverage, ""); +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(" "); - PrintUnitInASCII(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; - if (Options.MaxTotalTimeSec > 0 && - secondsSinceProcessStartUp() > - static_cast(Options.MaxTotalTimeSec)) - return; - CurrentUnit = Corpus[J1]; - // Optionally, cross with another unit. - if (Options.DoCrossOver && USF.GetRand().RandBool()) { - size_t J2 = USF.GetRand()(Corpus.size()); - if (!Corpus[J1].empty() && !Corpus[J2].empty()) { - assert(!Corpus[J2].empty()); - 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 returned overisized unit"); - CurrentUnit.resize(NewSize); - } - } - // Perform several mutations and runs. - 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() {