From 7fddde954395bddb59a708579f0df4a7b5595e6f Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Sat, 9 Jan 2016 03:08:58 +0000 Subject: [PATCH] [libFuzzer] change the way trace-based mutations are applied. Instead of a custom code just rely on the automatically created dictionary git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257248 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerDriver.cpp | 2 -- lib/Fuzzer/FuzzerFlags.def | 4 --- lib/Fuzzer/FuzzerInterface.h | 3 ++ lib/Fuzzer/FuzzerInternal.h | 8 ++---- lib/Fuzzer/FuzzerLoop.cpp | 18 ++---------- lib/Fuzzer/FuzzerMutate.cpp | 6 ++++ lib/Fuzzer/FuzzerTraceState.cpp | 45 ++++++++++-------------------- lib/Fuzzer/test/fuzzer-traces.test | 7 +++-- 8 files changed, 33 insertions(+), 60 deletions(-) diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 595e39759c9..66e46dbf3aa 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -259,8 +259,6 @@ int FuzzerDriver(const std::vector &Args, Flags.prefer_small_during_initial_shuffle; Options.Reload = Flags.reload; Options.OnlyASCII = Flags.only_ascii; - Options.TBMDepth = Flags.tbm_depth; - Options.TBMWidth = Flags.tbm_width; Options.OutputCSV = Flags.output_csv; if (Flags.runs >= 0) Options.MaxNumberOfRuns = Flags.runs; diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index 6d98f66ef9c..977efb76922 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -56,10 +56,6 @@ FUZZER_FLAG_INT(report_slow_units, 10, FUZZER_FLAG_INT(only_ascii, 0, "If 1, generate only ASCII (isprint+isspace) inputs.") FUZZER_FLAG_STRING(dict, "Experimental. Use the dictionary file.") -FUZZER_FLAG_INT(tbm_depth, 5, "Apply at most this number of consecutive" - "trace-based-mutations (tbm).") -FUZZER_FLAG_INT(tbm_width, 5, "Apply at most this number of independent" - "trace-based-mutations (tbm)") 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 " diff --git a/lib/Fuzzer/FuzzerInterface.h b/lib/Fuzzer/FuzzerInterface.h index 0950a1a6610..e22b27a3dd2 100644 --- a/lib/Fuzzer/FuzzerInterface.h +++ b/lib/Fuzzer/FuzzerInterface.h @@ -110,7 +110,10 @@ class MutationDispatcher { size_t Size2, uint8_t *Out, size_t MaxOutSize); void AddWordToManualDictionary(const Unit &Word); + void AddWordToAutoDictionary(const Unit &Word, size_t PositionHint); + void ClearAutoDictionary(); + void SetCorpus(const std::vector *Corpus); private: diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 17a2cae94a5..1f4f8fb336b 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -88,8 +88,6 @@ class Fuzzer { int SyncTimeout = 600; int ReportSlowUnits = 10; bool OnlyASCII = false; - int TBMDepth = 10; - int TBMWidth = 10; std::string OutputCorpus; std::string SyncCommand; std::string ArtifactPrefix = "./"; @@ -156,10 +154,8 @@ class Fuzzer { // Start tracing; forget all previously proposed mutations. void StartTraceRecording(); - // Stop tracing and return the number of proposed mutations. - size_t StopTraceRecording(); - // Apply Idx-th trace-based mutation to U. - void ApplyTraceBasedMutation(size_t Idx, Unit *U); + // Stop tracing. + void StopTraceRecording(); void SetDeathCallback(); static void StaticDeathCallback(); diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 0b1d9d9686a..089e911a697 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -390,7 +390,6 @@ void Fuzzer::MutateAndTestOne() { 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()); @@ -398,21 +397,10 @@ void Fuzzer::MutateAndTestOne() { assert(NewSize <= (size_t)Options.MaxLen && "Mutator return overisized unit"); U.resize(NewSize); + if (i == 0) + StartTraceRecording(); 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); - } - } + StopTraceRecording(); } } diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp index 11d320b7bc3..219837f4a0f 100644 --- a/lib/Fuzzer/FuzzerMutate.cpp +++ b/lib/Fuzzer/FuzzerMutate.cpp @@ -250,9 +250,15 @@ void MutationDispatcher::AddWordToManualDictionary(const Unit &Word) { void MutationDispatcher::AddWordToAutoDictionary(const Unit &Word, size_t PositionHint) { + static const size_t kMaxAutoDictSize = 1 << 14; + if (MDImpl->AutoDictionary.size() >= kMaxAutoDictSize) return; MDImpl->AutoDictionary.push_back({Word, PositionHint}); } +void MutationDispatcher::ClearAutoDictionary() { + MDImpl->AutoDictionary.clear(); +} + MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) { MDImpl = new Impl(Rand); } diff --git a/lib/Fuzzer/FuzzerTraceState.cpp b/lib/Fuzzer/FuzzerTraceState.cpp index 1dc93df1f35..83130444a16 100644 --- a/lib/Fuzzer/FuzzerTraceState.cpp +++ b/lib/Fuzzer/FuzzerTraceState.cpp @@ -46,8 +46,6 @@ // * The __dfsw_* functions (implemented in this file) record the // parameters (i.e. the application data and the corresponding taint labels) // in a global state. -// * Fuzzer::ApplyTraceBasedMutation() tries to use the data recorded -// by __dfsw_* hooks to guide the fuzzing towards new application states. // // Parts of this code will not function when DFSan is not linked in. // Instead of using ifdefs and thus requiring a separate build of lib/Fuzzer @@ -176,8 +174,9 @@ const size_t TraceBasedMutation::kMaxSize; class TraceState { public: - TraceState(const Fuzzer::FuzzingOptions &Options, const Unit &CurrentUnit) - : Options(Options), CurrentUnit(CurrentUnit) { + TraceState(UserSuppliedFuzzer &USF, + const Fuzzer::FuzzingOptions &Options, const Unit &CurrentUnit) + : USF(USF), Options(Options), CurrentUnit(CurrentUnit) { // Current trace collection is not thread-friendly and it probably // does not have to be such, but at least we should not crash in presence // of threads. So, just ignore all traces coming from all threads but one. @@ -209,15 +208,18 @@ class TraceState { if (!Options.UseTraces) return; RecordingTraces = true; NumMutations = 0; + USF.GetMD().ClearAutoDictionary(); } - size_t StopTraceRecording(FuzzerRandomBase &Rand) { + void StopTraceRecording() { + if (!RecordingTraces) return; RecordingTraces = false; - return NumMutations; + for (size_t i = 0; i < NumMutations; i++) { + auto &M = Mutations[i]; + USF.GetMD().AddWordToAutoDictionary(Unit(M.Data, M.Data + M.Size), M.Pos); + } } - void ApplyTraceBasedMutation(size_t Idx, fuzzer::Unit *U); - void AddMutation(uint32_t Pos, uint32_t Size, const uint8_t *Data) { if (NumMutations >= kMaxMutations) return; assert(Size <= TraceBasedMutation::kMaxSize); @@ -243,6 +245,7 @@ class TraceState { size_t NumMutations; TraceBasedMutation Mutations[kMaxMutations]; LabelRange LabelRanges[1 << (sizeof(dfsan_label) * 8)]; + UserSuppliedFuzzer &USF; const Fuzzer::FuzzingOptions &Options; const Unit &CurrentUnit; static thread_local bool IsMyThread; @@ -260,19 +263,6 @@ LabelRange TraceState::GetLabelRange(dfsan_label L) { return LR = LabelRange::Singleton(LI); } -void TraceState::ApplyTraceBasedMutation(size_t Idx, fuzzer::Unit *U) { - assert(Idx < NumMutations); - auto &M = Mutations[Idx]; - if (Options.Verbosity >= 3) { - Printf("TBM Pos %u Size %u ", M.Pos, M.Size); - for (uint32_t i = 0; i < M.Size; i++) - Printf("%02x", M.Data[i]); - Printf("\n"); - } - if (M.Pos + M.Size > U->size()) return; - memcpy(U->data() + M.Pos, &M.Data[0], M.Size); -} - void TraceState::DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType, uint64_t Arg1, uint64_t Arg2, dfsan_label L1, dfsan_label L2) { @@ -438,19 +428,14 @@ void Fuzzer::StartTraceRecording() { TS->StartTraceRecording(); } -size_t Fuzzer::StopTraceRecording() { - if (!TS) return 0; - return TS->StopTraceRecording(USF.GetRand()); -} - -void Fuzzer::ApplyTraceBasedMutation(size_t Idx, Unit *U) { - assert(TS); - TS->ApplyTraceBasedMutation(Idx, U); +void Fuzzer::StopTraceRecording() { + if (!TS) return; + TS->StopTraceRecording(); } void Fuzzer::InitializeTraceState() { if (!Options.UseTraces) return; - TS = new TraceState(Options, CurrentUnit); + TS = new TraceState(USF, Options, CurrentUnit); CurrentUnit.resize(Options.MaxLen); // The rest really requires DFSan. if (!ReallyHaveDFSan()) return; diff --git a/lib/Fuzzer/test/fuzzer-traces.test b/lib/Fuzzer/test/fuzzer-traces.test index 084cf30d698..3b8639b8e94 100644 --- a/lib/Fuzzer/test/fuzzer-traces.test +++ b/lib/Fuzzer/test/fuzzer-traces.test @@ -1,7 +1,8 @@ CHECK: BINGO Done1000000: Done 1000000 runs in +Done10000000: Done 10000000 runs in -RUN: not LLVMFuzzer-SimpleCmpTest -use_traces=1 -seed=1 -runs=1000001 2>&1 | FileCheck %s +RUN: not LLVMFuzzer-SimpleCmpTest -use_traces=1 -seed=1 -runs=10000001 2>&1 | FileCheck %s RUN: not LLVMFuzzer-MemcmpTest -use_traces=1 -seed=4294967295 -runs=100000 2>&1 | FileCheck %s RUN: LLVMFuzzer-MemcmpTest -seed=4294967295 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 @@ -15,5 +16,5 @@ RUN: LLVMFuzzer-StrcmpTest -seed=1 -runs=1000000 2>&1 | FileC RUN: not LLVMFuzzer-SwitchTest -use_traces=1 -seed=1 -runs=1000002 2>&1 | FileCheck %s RUN: LLVMFuzzer-SwitchTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-SimpleHashTest -use_traces=1 -seed=1 -runs=100000 2>&1 | FileCheck %s -RUN: LLVMFuzzer-SimpleHashTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 +RUN: not LLVMFuzzer-SimpleHashTest -use_traces=1 -seed=1 -runs=10000000 2>&1 | FileCheck %s +RUN: LLVMFuzzer-SimpleHashTest -seed=1 -runs=10000000 2>&1 | FileCheck %s --check-prefix=Done10000000 -- 2.34.1