From 0cdb698aaef899bf6a5550f5e2ab60219fda677e Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Mon, 11 May 2015 20:51:19 +0000 Subject: [PATCH] [lib/Fuzzer] add a trace-based mutatation logic. Same idea as with DFSan-based mutator, but instead of relying on taint tracking, try to find the data directly in the input. More (logic and comments) to go. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@237043 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerDFSan.cpp | 76 +++++++++++++++++++++++++++++++------ lib/Fuzzer/FuzzerDriver.cpp | 1 + lib/Fuzzer/FuzzerFlags.def | 1 + lib/Fuzzer/FuzzerInternal.h | 1 + lib/Fuzzer/test/fuzzer.test | 1 + 5 files changed, 68 insertions(+), 12 deletions(-) diff --git a/lib/Fuzzer/FuzzerDFSan.cpp b/lib/Fuzzer/FuzzerDFSan.cpp index 53f852e6bb0..217124d2110 100644 --- a/lib/Fuzzer/FuzzerDFSan.cpp +++ b/lib/Fuzzer/FuzzerDFSan.cpp @@ -85,7 +85,11 @@ __attribute__((weak)) dfsan_label dfsan_read_label(const void *addr, size_t size); } // extern "C" -namespace { +namespace fuzzer { + +static bool ReallyHaveDFSan() { + return &dfsan_create_label != nullptr; +} // These values are copied from include/llvm/IR/InstrTypes.h. // We do not include the LLVM headers here to remain independent. @@ -166,13 +170,17 @@ struct TraceBasedMutation { class DFSanState { public: - DFSanState(const fuzzer::Fuzzer::FuzzingOptions &Options) - : Options(Options) {} + DFSanState(const Fuzzer::FuzzingOptions &Options, const Unit &CurrentUnit) + : Options(Options), CurrentUnit(CurrentUnit) {} LabelRange GetLabelRange(dfsan_label L); void DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType, uint64_t Arg1, uint64_t Arg2, dfsan_label L1, dfsan_label L2); + void TraceCmpCallback(size_t CmpSize, size_t CmpType, uint64_t Arg1, + uint64_t Arg2); + int TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData, + size_t DataSize); void StartTraceRecording() { RecordingTraces = true; @@ -188,10 +196,16 @@ class DFSanState { void ApplyTraceBasedMutation(size_t Idx, fuzzer::Unit *U); private: + bool IsTwoByteData(uint64_t Data) { + int64_t Signed = static_cast(Data); + Signed >>= 16; + return Signed == 0 || Signed == -1L; + } bool RecordingTraces = false; std::vector Mutations; LabelRange LabelRanges[1 << (sizeof(dfsan_label) * 8)] = {}; - const fuzzer::Fuzzer::FuzzingOptions &Options; + const Fuzzer::FuzzingOptions &Options; + const Unit &CurrentUnit; }; LabelRange DFSanState::GetLabelRange(dfsan_label L) { @@ -216,6 +230,7 @@ void DFSanState::ApplyTraceBasedMutation(size_t Idx, fuzzer::Unit *U) { void DFSanState::DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType, uint64_t Arg1, uint64_t Arg2, dfsan_label L1, dfsan_label L2) { + assert(ReallyHaveDFSan()); if (!RecordingTraces) return; if (L1 == 0 && L2 == 0) return; // Not actionable. @@ -248,11 +263,42 @@ void DFSanState::DFSanCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType, << "\n"; } -static DFSanState *DFSan; +int DFSanState::TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData, + size_t DataSize) { + int Res = 0; + const uint8_t *Beg = CurrentUnit.data(); + const uint8_t *End = Beg + CurrentUnit.size(); + for (const uint8_t *Cur = Beg; Cur < End; Cur += DataSize) { + Cur = (uint8_t *)memmem(Cur, End - Cur, &PresentData, DataSize); + if (!Cur) + break; + // std::cerr << "Cur " << (void*)Cur << "\n"; + size_t Pos = Cur - Beg; + assert(Pos < CurrentUnit.size()); + Mutations.push_back({Pos, DataSize, DesiredData}); + Mutations.push_back({Pos, DataSize, DesiredData + 1}); + Mutations.push_back({Pos, DataSize, DesiredData - 1}); + Cur += DataSize; + Res++; + } + return Res; +} -} // namespace +void DFSanState::TraceCmpCallback(size_t CmpSize, size_t CmpType, uint64_t Arg1, + uint64_t Arg2) { + if (!Options.UseTraces) return; + int Added = 0; + if (Options.Verbosity >= 3) + std::cerr << "TraceCmp: " << Arg1 << " " << Arg2 << "\n"; + Added += TryToAddDesiredData(Arg1, Arg2, CmpSize); + Added += TryToAddDesiredData(Arg2, Arg1, CmpSize); + if (!Added && CmpSize == 4 && IsTwoByteData(Arg1) && IsTwoByteData(Arg2)) { + Added += TryToAddDesiredData(Arg1, Arg2, 2); + Added += TryToAddDesiredData(Arg2, Arg1, 2); + } +} -namespace fuzzer { +static DFSanState *DFSan; void Fuzzer::StartTraceRecording() { if (!DFSan) return; @@ -270,9 +316,11 @@ void Fuzzer::ApplyTraceBasedMutation(size_t Idx, Unit *U) { } void Fuzzer::InitializeDFSan() { - if (!&dfsan_create_label || !Options.UseDFSan) return; - DFSan = new DFSanState(Options); + if (!Options.UseDFSan) return; + DFSan = new DFSanState(Options, CurrentUnit); CurrentUnit.resize(Options.MaxLen); + // The rest really requires DFSan. + if (!ReallyHaveDFSan()) return; for (size_t i = 0; i < static_cast(Options.MaxLen); i++) { dfsan_label L = dfsan_create_label("input", (void*)(i + 1)); // We assume that no one else has called dfsan_create_label before. @@ -283,6 +331,8 @@ void Fuzzer::InitializeDFSan() { } // namespace fuzzer +using fuzzer::DFSan; + extern "C" { void __dfsw___sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1, uint64_t Arg2, dfsan_label L0, @@ -304,13 +354,15 @@ void dfsan_weak_hook_memcmp(void *caller_pc, const void *s1, const void *s2, memcpy(&S2, s2, std::min(n, sizeof(S2))); dfsan_label L1 = dfsan_read_label(s1, n); dfsan_label L2 = dfsan_read_label(s2, n); - DFSan->DFSanCmpCallback(PC, n, ICMP_EQ, S1, S2, L1, L2); + DFSan->DFSanCmpCallback(PC, n, fuzzer::ICMP_EQ, S1, S2, L1, L2); } void __sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1, uint64_t Arg2) { - // This symbol will be present if dfsan is disabled on the given function. - // FIXME: implement poor man's taint analysis here (w/o dfsan). + if (!DFSan) return; + uint64_t CmpSize = (SizeAndType >> 32) / 8; + uint64_t Type = (SizeAndType << 32) >> 32; + DFSan->TraceCmpCallback(CmpSize, Type, Arg1, Arg2); } } // extern "C" diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 641221194c5..c24ecbd57eb 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -201,6 +201,7 @@ int FuzzerDriver(int argc, char **argv, UserCallback Callback) { Options.MutateDepth = Flags.mutate_depth; Options.ExitOnFirst = Flags.exit_on_first; Options.UseCounters = Flags.use_counters; + Options.UseTraces = Flags.use_traces; Options.UseFullCoverageSet = Flags.use_full_coverage_set; Options.UseCoveragePairs = Flags.use_coverage_pairs; Options.UseDFSan = Flags.dfsan; diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index 1222feb5937..ff74518245f 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -33,6 +33,7 @@ FUZZER_FLAG_INT( save_minimized_corpus, 0, "If 1, the minimized corpus is saved into the first input directory") FUZZER_FLAG_INT(use_counters, 0, "Use coverage counters") +FUZZER_FLAG_INT(use_traces, 0, "Experimental: use instruction traces") FUZZER_FLAG_INT(use_full_coverage_set, 0, "Experimental: Maximize the number of different full" " coverage sets as opposed to maximizing the total coverage." diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h index 8363ef020b2..f085f94d612 100644 --- a/lib/Fuzzer/FuzzerInternal.h +++ b/lib/Fuzzer/FuzzerInternal.h @@ -53,6 +53,7 @@ class Fuzzer { int MutateDepth = 5; bool ExitOnFirst = false; bool UseCounters = false; + bool UseTraces = false; bool UseFullCoverageSet = false; bool UseCoveragePairs = false; bool UseDFSan = false; diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test index 7d1908f6179..8913706c006 100644 --- a/lib/Fuzzer/test/fuzzer.test +++ b/lib/Fuzzer/test/fuzzer.test @@ -20,6 +20,7 @@ RUN: not ./LLVMFuzzer-FourIndependentBranchesTest -timeout=15 -seed=1 -use_cover RUN: not ./LLVMFuzzer-CounterTest -use_counters=1 -max_len=6 -seed=1 -timeout=15 2>&1 | FileCheck %s RUN: not ./LLVMFuzzer-DFSanSimpleCmpTest-DFSan -seed=1 -runs=1000000 -timeout=5 2>&1 | FileCheck %s +RUN: not ./LLVMFuzzer-DFSanSimpleCmpTest -use_traces=1 -seed=1 -runs=1000000 -timeout=5 2>&1 | FileCheck %s RUN: not ./LLVMFuzzer-DFSanMemcmpTest-DFSan -seed=1 -runs=100 -timeout=5 2>&1 | FileCheck %s -- 2.34.1