From 3af68729f8c41496b5f0ead14f03ac0b4ae43f90 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Fri, 14 Oct 2016 20:20:33 +0000 Subject: [PATCH] [libFuzzer] add -trace_cmp=1 (guiding mutations based on the observed CMP instructions). This is a reincarnation of the previously deleted -use_traces, but using a different approach for collecting traces. Still a toy, but at least it scales well. Also fix -merge in trace-pc-guard mode git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@284273 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerCorpus.h | 6 +++++ lib/Fuzzer/FuzzerDefs.h | 6 +++++ lib/Fuzzer/FuzzerDriver.cpp | 1 + lib/Fuzzer/FuzzerFlags.def | 3 ++- lib/Fuzzer/FuzzerLoop.cpp | 16 ++++++++++-- lib/Fuzzer/FuzzerMutate.cpp | 15 ++++++++--- lib/Fuzzer/FuzzerMutate.h | 10 ++++++++ lib/Fuzzer/FuzzerOptions.h | 1 + lib/Fuzzer/FuzzerTracePC.cpp | 54 ++++++++++++++++++++++++++++++++++++++- lib/Fuzzer/FuzzerTracePC.h | 49 +++++++++++++++++++++++++++++++++++ lib/Fuzzer/FuzzerTraceState.cpp | 6 ++--- lib/Fuzzer/test/trace-malloc.test | 2 +- 12 files changed, 157 insertions(+), 12 deletions(-) diff --git a/lib/Fuzzer/FuzzerCorpus.h b/lib/Fuzzer/FuzzerCorpus.h index 714ca2c988f..355c242e1f4 100644 --- a/lib/Fuzzer/FuzzerCorpus.h +++ b/lib/Fuzzer/FuzzerCorpus.h @@ -153,6 +153,12 @@ class InputCorpus { return Res; } + void ResetFeatureSet() { + assert(Inputs.empty()); + memset(InputSizesPerFeature, 0, sizeof(InputSizesPerFeature)); + memset(SmallestElementPerFeature, 0, sizeof(SmallestElementPerFeature)); + } + private: static const bool FeatureDebug = false; diff --git a/lib/Fuzzer/FuzzerDefs.h b/lib/Fuzzer/FuzzerDefs.h index b282a83ac98..99b478ff6ed 100644 --- a/lib/Fuzzer/FuzzerDefs.h +++ b/lib/Fuzzer/FuzzerDefs.h @@ -111,5 +111,11 @@ int NumberOfCpuCores(); int GetPid(); void SleepSeconds(int Seconds); + +struct ScopedDoingMyOwnMemmem { + ScopedDoingMyOwnMemmem(); + ~ScopedDoingMyOwnMemmem(); +}; + } // namespace fuzzer #endif // LLVM_FUZZER_DEFS_H diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index f15c79fcd4d..78d73927cf6 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -397,6 +397,7 @@ int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) { Options.UseIndirCalls = Flags.use_indir_calls; Options.UseMemcmp = Flags.use_memcmp; Options.UseMemmem = Flags.use_memmem; + Options.UseCmp = Flags.use_cmp; Options.UseValueProfile = Flags.use_value_profile; Options.Shrink = Flags.shrink; Options.ShuffleAtStartUp = Flags.shuffle; diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index d3b8b98ca3a..01f733d5226 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -49,6 +49,7 @@ FUZZER_FLAG_INT(use_memmem, 1, "Use hints from intercepting memmem, strstr, etc") FUZZER_FLAG_INT(use_value_profile, 0, "Experimental. Use value profile to guide fuzzing.") +FUZZER_FLAG_INT(use_cmp, 0, "Experimenta. Use CMP traces to guide mutations") FUZZER_FLAG_INT(shrink, 0, "Experimental. Try to shrink corpus elements.") FUZZER_FLAG_INT(jobs, 0, "Number of jobs to run. If jobs >= 1 we spawn" " this number of jobs in separate worker processes" @@ -92,7 +93,7 @@ FUZZER_FLAG_INT(close_fd_mask, 0, "If 1, close stdout at startup; " FUZZER_FLAG_INT(detect_leaks, 1, "If 1, and if LeakSanitizer is enabled " "try to detect memory leaks during fuzzing (i.e. not only at shut down).") FUZZER_FLAG_INT(trace_malloc, 0, "If >= 1 will print all mallocs/frees. " - "If >= 2 will also print stack traces.") + "If >= 2 will also print stack traces.") FUZZER_FLAG_INT(rss_limit_mb, 2048, "If non-zero, the fuzzer will exit upon" "reaching this limit of RSS memory usage.") FUZZER_FLAG_STRING(exit_on_src_pos, "Exit if a newly found PC originates" diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index 32e5536c42f..a8f640307fc 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -479,6 +479,9 @@ size_t Fuzzer::RunOne(const uint8_t *Data, size_t Size) { Res = 1; } + if (Res && Options.UseCmp) + TPC.ProcessTORC(MD.GetTraceCmpDictionary(), CurrentUnitData, Size); + CheckExitOnSrcPos(); auto TimeOfUnit = duration_cast(UnitStopTime - UnitStartTime).count(); @@ -513,6 +516,8 @@ void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) { UnitStartTime = system_clock::now(); ResetCounters(); // Reset coverage right before the callback. TPC.ResetMaps(); + if (Options.UseCmp) + TPC.ResetTORC(); if (Options.UseCounters) TPC.ResetGuards(); int Res = CB(DataCopy, Size); @@ -594,15 +599,22 @@ UnitVector Fuzzer::FindExtraUnits(const UnitVector &Initial, ShuffleCorpus(&Res); TPC.ResetMaps(); TPC.ResetGuards(); + Corpus.ResetFeatureSet(); ResetCoverage(); - for (auto &U : Initial) + for (auto &U : Initial) { + TPC.ResetMaps(); + TPC.ResetGuards(); RunOne(U); + } Tmp.clear(); - for (auto &U : Res) + for (auto &U : Res) { + TPC.ResetMaps(); + TPC.ResetGuards(); if (RunOne(U)) Tmp.push_back(U); + } char Stat[7] = "MIN "; Stat[3] = '0' + Iter; diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp index e3b35d4de81..76585dcfe16 100644 --- a/lib/Fuzzer/FuzzerMutate.cpp +++ b/lib/Fuzzer/FuzzerMutate.cpp @@ -43,12 +43,16 @@ MutationDispatcher::MutationDispatcher(Random &Rand, {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, {&MutationDispatcher::Mutate_AddWordFromManualDictionary, - "AddFromManualDict"}, + "ManualDict"}, {&MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary, - "AddFromTempAutoDict"}, + "TempAutoDict"}, {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, - "AddFromPersAutoDict"}, + "PersAutoDict"}, }); + if(Options.UseCmp) + DefaultMutators.push_back( + {&MutationDispatcher::Mutate_AddWordFromTraceCmpDictionary, + "TraceCmpDict"}); if (EF->LLVMFuzzerCustomMutator) Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); @@ -171,6 +175,11 @@ size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary( return AddWordFromDictionary(TempAutoDictionary, Data, Size, MaxSize); } +size_t MutationDispatcher::Mutate_AddWordFromTraceCmpDictionary( + uint8_t *Data, size_t Size, size_t MaxSize) { + return AddWordFromDictionary(TraceCmpDictionary, Data, Size, MaxSize); +} + size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( uint8_t *Data, size_t Size, size_t MaxSize) { return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); diff --git a/lib/Fuzzer/FuzzerMutate.h b/lib/Fuzzer/FuzzerMutate.h index f8611a77124..125185bda9e 100644 --- a/lib/Fuzzer/FuzzerMutate.h +++ b/lib/Fuzzer/FuzzerMutate.h @@ -55,6 +55,10 @@ public: size_t Mutate_AddWordFromTemporaryAutoDictionary(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by adding a word from the trace-cmp dictionary. + size_t Mutate_AddWordFromTraceCmpDictionary(uint8_t *Data, size_t Size, + size_t MaxSize); + /// Mutates data by adding a word from the persistent automatic dictionary. size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size, size_t MaxSize); @@ -88,6 +92,8 @@ public: Random &GetRand() { return Rand; } + Dictionary *GetTraceCmpDictionary() { return &TraceCmpDictionary; } + private: struct Mutator { @@ -116,6 +122,10 @@ private: // Persistent dictionary modified by the fuzzer, consists of // entries that led to successfull discoveries in the past mutations. Dictionary PersistentAutoDictionary; + + // Dictionary from tracing CMP instructions. + Dictionary TraceCmpDictionary; + std::vector CurrentMutatorSequence; std::vector CurrentDictionaryEntrySequence; const InputCorpus *Corpus = nullptr; diff --git a/lib/Fuzzer/FuzzerOptions.h b/lib/Fuzzer/FuzzerOptions.h index d0bac9cee83..59126a231e3 100644 --- a/lib/Fuzzer/FuzzerOptions.h +++ b/lib/Fuzzer/FuzzerOptions.h @@ -30,6 +30,7 @@ struct FuzzingOptions { bool UseIndirCalls = true; bool UseMemcmp = true; bool UseMemmem = true; + bool UseCmp = false; bool UseValueProfile = false; bool Shrink = false; int ReloadIntervalSec = 1; diff --git a/lib/Fuzzer/FuzzerTracePC.cpp b/lib/Fuzzer/FuzzerTracePC.cpp index d843f542cdd..cfaf9c5e571 100644 --- a/lib/Fuzzer/FuzzerTracePC.cpp +++ b/lib/Fuzzer/FuzzerTracePC.cpp @@ -14,6 +14,7 @@ #include "FuzzerCorpus.h" #include "FuzzerDefs.h" +#include "FuzzerDictionary.h" #include "FuzzerTracePC.h" #include "FuzzerValueBitMap.h" @@ -170,11 +171,62 @@ __attribute__((always_inline)) #endif // __clang__ void TracePC::HandleCmp(void *PC, T Arg1, T Arg2) { uintptr_t PCuint = reinterpret_cast(PC); - uint64_t ArgDistance = __builtin_popcountl(Arg1 ^ Arg2) + 1; // [1,65] + uint64_t ArgXor = Arg1 ^ Arg2; + uint64_t ArgDistance = __builtin_popcountl(ArgXor) + 1; // [1,65] uintptr_t Idx = ((PCuint & 4095) + 1) * ArgDistance; + TORCInsert(ArgXor, Arg1, Arg2); HandleValueProfile(Idx); } +void TracePC::ProcessTORC(Dictionary *Dict, const uint8_t *Data, size_t Size) { + TORCToDict(TORC8, Dict, Data, Size); + TORCToDict(TORC4, Dict, Data, Size); +} + +template +void TracePC::TORCToDict(const TableOfRecentCompares &TORC, + Dictionary *Dict, const uint8_t *Data, size_t Size) { + ScopedDoingMyOwnMemmem scoped_doing_my_own_memmem; + for (size_t i = 0; i < TORC.kSize; i++) { + T A[2] = {TORC.Table[i][0], TORC.Table[i][1]}; + if (!A[0] && !A[1]) continue; + for (int j = 0; j < 2; j++) + TORCToDict(Dict, A[j], A[!j], Data, Size); + } +} + +template +void TracePC::TORCToDict(Dictionary *Dict, T FindInData, T Substitute, + const uint8_t *Data, size_t Size) { + if (FindInData == Substitute) return; + if (sizeof(T) == 4) { + uint16_t HigherBytes = Substitute >> sizeof(T) * 4; + if (HigherBytes == 0 || HigherBytes == 0xffff) + TORCToDict(Dict, static_cast(FindInData), + static_cast(Substitute), Data, Size); + } + const size_t DataSize = sizeof(T); + const uint8_t *End = Data + Size; + int Attempts = 3; + // TODO: also swap bytes in FindInData. + for (const uint8_t *Cur = Data; Cur < End && Attempts--; Cur++) { + Cur = (uint8_t *)memmem(Cur, End - Cur, &FindInData, DataSize); + if (!Cur) + break; + size_t Pos = Cur - Data; + for (int Offset = 0; Offset <= 0; Offset++) { + T Tmp = Substitute + Offset; + Word W(reinterpret_cast(&Tmp), sizeof(Tmp)); + DictionaryEntry DE(W, Pos); + // TODO: evict all entries from Dic if it's full. + Dict->push_back(DE); + // Printf("Dict[%zd] TORC%zd %llx => %llx pos %zd\n", Dict->size(), + // sizeof(T), + // (uint64_t)FindInData, (uint64_t)Tmp, Pos); + } + } +} + } // namespace fuzzer extern "C" { diff --git a/lib/Fuzzer/FuzzerTracePC.h b/lib/Fuzzer/FuzzerTracePC.h index 788e6f4d935..632cd541e2b 100644 --- a/lib/Fuzzer/FuzzerTracePC.h +++ b/lib/Fuzzer/FuzzerTracePC.h @@ -17,6 +17,25 @@ namespace fuzzer { +// TableOfRecentCompares (TORC) remembers the most recently performed +// comparisons of type T. +// We record the arguments of CMP instructions in this table unconditionally +// because it seems cheaper this way than to compute some expensive +// conditions inside __sanitizer_cov_trace_cmp*. +// After the unit has been executed we may decide to use the contents of +// this table to populate a Dictionary. +template +struct TableOfRecentCompares { + static const size_t kSize = kSizeT; + void Insert(size_t Idx, T Arg1, T Arg2) { + Idx = Idx % kSize; + Table[Idx][0] = Arg1; + Table[Idx][1] = Arg2; + } + void Clear() { memset(Table, 0, sizeof(Table)); } + T Table[kSize][2]; +}; + class TracePC { public: static const size_t kFeatureSetSize = ValueBitMap::kNumberOfItems; @@ -48,6 +67,11 @@ class TracePC { memset(Counters, 0, sizeof(Counters)); } + void ResetTORC() { + TORC4.Clear(); + TORC8.Clear(); + } + void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize); void PrintFeatureSet(); @@ -64,6 +88,8 @@ class TracePC { bool UsingTracePcGuard() const {return NumModules; } + void ProcessTORC(Dictionary *Dict, const uint8_t *Data, size_t Size); + private: bool UseCounters = false; bool UseValueProfile = false; @@ -87,6 +113,29 @@ private: static const size_t kNumCounters = 1 << 14; alignas(8) uint8_t Counters[kNumCounters]; + static const size_t kTORCSize = 1 << 12; + TableOfRecentCompares TORC4; + TableOfRecentCompares TORC8; + void TORCInsert(size_t Idx, uint8_t Arg1, uint8_t Arg2) { + // Do nothing, too small to be interesting. + } + void TORCInsert(size_t Idx, uint16_t Arg1, uint16_t Arg2) { + // Do nothing, these don't usually hapen. + } + void TORCInsert(size_t Idx, uint32_t Arg1, uint32_t Arg2) { + TORC4.Insert(Idx, Arg1, Arg2); + } + void TORCInsert(size_t Idx, uint64_t Arg1, uint64_t Arg2) { + TORC8.Insert(Idx, Arg1, Arg2); + } + + template + void TORCToDict(const TableOfRecentCompares &TORC, + Dictionary *Dict, const uint8_t *Data, size_t Size); + template + void TORCToDict(Dictionary *Dict, T FindInData, T Substitute, + const uint8_t *Data, size_t Size); + static const size_t kNumPCs = 1 << 24; uintptr_t PCs[kNumPCs]; diff --git a/lib/Fuzzer/FuzzerTraceState.cpp b/lib/Fuzzer/FuzzerTraceState.cpp index cea348b6e23..9cccfcbc26f 100644 --- a/lib/Fuzzer/FuzzerTraceState.cpp +++ b/lib/Fuzzer/FuzzerTraceState.cpp @@ -34,10 +34,8 @@ static bool RecordingMemcmp = false; static bool RecordingMemmem = false; static bool DoingMyOwnMemmem = false; -struct ScopedDoingMyOwnMemmem { - ScopedDoingMyOwnMemmem() { DoingMyOwnMemmem = true; } - ~ScopedDoingMyOwnMemmem() { DoingMyOwnMemmem = false; } -}; +ScopedDoingMyOwnMemmem::ScopedDoingMyOwnMemmem() { DoingMyOwnMemmem = true; } +ScopedDoingMyOwnMemmem::~ScopedDoingMyOwnMemmem() { DoingMyOwnMemmem = false; } class TraceState { public: diff --git a/lib/Fuzzer/test/trace-malloc.test b/lib/Fuzzer/test/trace-malloc.test index c8ef833a56d..c95147904d4 100644 --- a/lib/Fuzzer/test/trace-malloc.test +++ b/lib/Fuzzer/test/trace-malloc.test @@ -1,4 +1,4 @@ -RUN: LLVMFuzzer-TraceMallocTest -seed=1 -trace_malloc=1 -runs=1000 2>&1 | FileCheck %s +RUN: LLVMFuzzer-TraceMallocTest -seed=1 -trace_malloc=1 -runs=10000 2>&1 | FileCheck %s CHECK-DAG: MallocFreeTracer: STOP 0 0 (same) CHECK-DAG: MallocFreeTracer: STOP 0 1 (DIFFERENT) CHECK-DAG: MallocFreeTracer: STOP 1 0 (DIFFERENT) -- 2.11.0