From: Kostya Serebryany Date: Thu, 12 Nov 2015 01:02:01 +0000 (+0000) Subject: [libFuzzer] experimental flag -drill (another search heuristic; Mike Aizatsky's idea) X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=1a42a60ebc401b9e53f13bd6d4ecaaed2952a0b4 [libFuzzer] experimental flag -drill (another search heuristic; Mike Aizatsky's idea) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252838 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 363abc482cb..664436ed4f9 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -152,7 +152,7 @@ static void WorkerThread(const std::string &Cmd, std::atomic *Counter, std::string ToRun = Cmd + " > " + Log + " 2>&1\n"; if (Flags.verbosity) Printf("%s", ToRun.c_str()); - int ExitCode = system(ToRun.c_str()); + int ExitCode = ExecuteCommand(ToRun.c_str()); if (ExitCode != 0) *HasErrors = true; std::lock_guard Lock(Mu); @@ -255,15 +255,19 @@ int FuzzerDriver(const std::vector &Args, Options.ReportSlowUnits = Flags.report_slow_units; if (Flags.artifact_prefix) Options.ArtifactPrefix = Flags.artifact_prefix; + std::vector Dictionary; if (Flags.dict) - if (!ParseDictionaryFile(FileToString(Flags.dict), &Options.Dictionary)) + if (!ParseDictionaryFile(FileToString(Flags.dict), &Dictionary)) return 1; - if (Flags.verbosity > 0 && !Options.Dictionary.empty()) - Printf("Dictionary: %zd entries\n", Options.Dictionary.size()); + if (Flags.verbosity > 0 && !Dictionary.empty()) + Printf("Dictionary: %zd entries\n", Dictionary.size()); Options.SaveArtifacts = !Flags.test_single_input; Fuzzer F(USF, Options); + for (auto &U: Dictionary) + USF.GetMD().AddWordToDictionary(U.data(), U.size()); + // Timer if (Flags.timeout > 0) SetTimer(Flags.timeout / 2 + 1); @@ -294,7 +298,11 @@ int FuzzerDriver(const std::vector &Args, F.ShuffleAndMinimize(); if (Flags.save_minimized_corpus) F.SaveCorpus(); - F.Loop(); + else if (Flags.drill) + F.Drill(); + else + F.Loop(); + if (Flags.verbosity) Printf("Done %d runs in %zd second(s)\n", F.getTotalNumberOfRuns(), F.secondsSinceProcessStartUp()); diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index 9cd2dedb37a..8fc955c18bd 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -67,3 +67,5 @@ FUZZER_FLAG_STRING(test_single_input, "Use specified file as test input.") FUZZER_FLAG_STRING(artifact_prefix, "Write fuzzing artifacts (crash, " "timeout, or slow inputs) as " "$(artifact_prefix)file") +FUZZER_FLAG_INT(drill, 0, "Experimental: fuzz using a single unit as the seed " + "corpus, then merge with the initial corpus") diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 0fa0b90b803..7cb78fd91ee 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -43,7 +43,7 @@ void PrintASCII(const Unit &U, const char *PrintAfter = ""); std::string Hash(const Unit &U); void SetTimer(int Seconds); void PrintFileAsBase64(const std::string &Path); -void ExecuteCommand(const std::string &Command); +int ExecuteCommand(const std::string &Command); // Private copy of SHA1 implementation. static const int kSHA1NumBytes = 20; @@ -94,13 +94,15 @@ class Fuzzer { std::string OutputCorpus; std::string SyncCommand; std::string ArtifactPrefix = "./"; - std::vector Dictionary; bool SaveArtifacts = true; + bool PrintNEW = true; // Print a status line when new units are found; }; Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options); void AddToCorpus(const Unit &U) { Corpus.push_back(U); } - size_t ChooseUnitToMutate(); + size_t ChooseUnitIdxToMutate(); + const Unit &ChooseUnitToMutate() { return Corpus[ChooseUnitIdxToMutate()]; }; void Loop(); + void Drill(); void ShuffleAndMinimize(); void InitializeTraceState(); size_t CorpusSize() const { return Corpus.size(); } @@ -135,6 +137,7 @@ class Fuzzer { void WriteToOutputCorpus(const Unit &U); void WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix); void PrintStats(const char *Where, const char *End = "\n"); + void PrintStatusForNewUnit(const Unit &U); void PrintUnitInASCII(const Unit &U, const char *PrintAfter = ""); void SyncCorpus(); diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index e206fcc9796..d3c32626a3b 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -18,6 +18,7 @@ extern "C" { // libFuzzer can be linked w/o the sanitizers and sanitizer-coveragte // (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)) @@ -293,9 +294,9 @@ void Fuzzer::SaveCorpus() { Options.OutputCorpus.c_str()); } -void Fuzzer::ReportNewCoverage(const Unit &U) { - Corpus.push_back(U); - UnitHashesAddedToCorpus.insert(Hash(U)); +void Fuzzer::PrintStatusForNewUnit(const Unit &U) { + if (!Options.PrintNEW) + return; PrintStats("NEW ", ""); if (Options.Verbosity) { Printf(" L: %zd", U.size()); @@ -306,6 +307,12 @@ void Fuzzer::ReportNewCoverage(const Unit &U) { } 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); @@ -374,7 +381,7 @@ void Fuzzer::MutateAndTestOne(Unit *U) { // 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::ChooseUnitToMutate() { +size_t Fuzzer::ChooseUnitIdxToMutate() { size_t N = Corpus.size(); size_t Total = (N + 1) * N / 2; size_t R = USF.GetRand()(Total); @@ -391,12 +398,57 @@ size_t Fuzzer::ChooseUnitToMutate() { return IdxBeg; } -void Fuzzer::Loop() { - for (auto &U: Options.Dictionary) - USF.GetMD().AddWordToDictionary(U.data(), U.size()); +// 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) + RunOne(U); + PrintStats("MERGE "); + Options.PrintNEW = true; + size_t NumMerged = 0; + for (auto &U : Corpus) { + 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() { while (true) { - size_t J1 = ChooseUnitToMutate();; + size_t J1 = ChooseUnitIdxToMutate();; SyncCorpus(); RereadOutputCorpus(); if (TotalNumberOfRuns >= Options.MaxNumberOfRuns) @@ -408,7 +460,7 @@ void Fuzzer::Loop() { CurrentUnit = Corpus[J1]; // Optionally, cross with another unit. if (Options.DoCrossOver && USF.GetRand().RandBool()) { - size_t J2 = ChooseUnitToMutate(); + size_t J2 = ChooseUnitIdxToMutate(); if (!Corpus[J1].empty() && !Corpus[J2].empty()) { assert(!Corpus[J2].empty()); CurrentUnit.resize(Options.MaxLen); diff --git a/lib/Fuzzer/FuzzerUtil.cpp b/lib/Fuzzer/FuzzerUtil.cpp index 8d3480cf480..20a41e0d4fb 100644 --- a/lib/Fuzzer/FuzzerUtil.cpp +++ b/lib/Fuzzer/FuzzerUtil.cpp @@ -69,8 +69,8 @@ int NumberOfCpuCores() { return N; } -void ExecuteCommand(const std::string &Command) { - system(Command.c_str()); +int ExecuteCommand(const std::string &Command) { + return system(Command.c_str()); } bool ToASCII(Unit &U) { diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test index 0f1a6cc7fa1..fe949bf31ac 100644 --- a/lib/Fuzzer/test/fuzzer.test +++ b/lib/Fuzzer/test/fuzzer.test @@ -31,7 +31,11 @@ NullDerefTestPrefix: Test unit written to ZZZcrash- #not LLVMFuzzer-FullCoverageSetTest -timeout=15 -seed=1 -mutate_depth=2 -use_full_coverage_set=1 2>&1 | FileCheck %s -#not LLVMFuzzer-FourIndependentBranchesTest -timeout=15 -seed=1 -use_traces=1 2>&1 | FileCheck %s +RUN: rm -rf FourIndependentBranchesTestCORPUS +RUN: mkdir FourIndependentBranchesTestCORPUS +RUN: LLVMFuzzer-FourIndependentBranchesTest -seed=1 -runs=1000000 FourIndependentBranchesTestCORPUS +RUN: not LLVMFuzzer-FourIndependentBranchesTest -runs=100000 -drill=1 -jobs=200 FourIndependentBranchesTestCORPUS 2>&1 | FileCheck %s +RUN: rm -rf FourIndependentBranchesTestCORPUS RUN: not LLVMFuzzer-CounterTest -use_counters=1 -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s