From db5325aae361388388fe297a90dd3da74c3d16c0 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Tue, 17 Jan 2017 23:09:05 +0000 Subject: [PATCH] [libFuzzer] use table of recent compares for memcmp/strcmp (to unify the code between cmp and memcmp handling) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@292287 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Fuzzer/FuzzerDictionary.h | 3 +- lib/Fuzzer/FuzzerFlags.def | 2 +- lib/Fuzzer/FuzzerInterface.h | 2 +- lib/Fuzzer/FuzzerMutate.cpp | 51 ++++++++++++++++++------ lib/Fuzzer/FuzzerMutate.h | 7 ++++ lib/Fuzzer/FuzzerTracePC.cpp | 39 +++++++----------- lib/Fuzzer/FuzzerTracePC.h | 12 +++--- lib/Fuzzer/FuzzerTraceState.cpp | 18 ++++----- lib/Fuzzer/test/SingleStrcmpTest.cpp | 12 ++++-- lib/Fuzzer/test/fuzzer-traces-hooks.test | 16 ++++---- 10 files changed, 94 insertions(+), 68 deletions(-) diff --git a/lib/Fuzzer/FuzzerDictionary.h b/lib/Fuzzer/FuzzerDictionary.h index eba0eabb683..f15ac930f2c 100644 --- a/lib/Fuzzer/FuzzerDictionary.h +++ b/lib/Fuzzer/FuzzerDictionary.h @@ -20,8 +20,9 @@ namespace fuzzer { // A simple POD sized array of bytes. -template class FixedWord { +template class FixedWord { public: + static const size_t kMaxSize = kMaxSizeT; FixedWord() {} FixedWord(const uint8_t *B, uint8_t S) { Set(B, S); } diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def index 22aad353ace..0deca1793c7 100644 --- a/lib/Fuzzer/FuzzerFlags.def +++ b/lib/Fuzzer/FuzzerFlags.def @@ -45,7 +45,7 @@ FUZZER_FLAG_INT(minimize_crash, 0, "If 1, minimizes the provided" FUZZER_FLAG_INT(minimize_crash_internal_step, 0, "internal flag") FUZZER_FLAG_INT(use_counters, 1, "Use coverage counters") FUZZER_FLAG_INT(use_indir_calls, 1, "Use indirect caller-callee counters") -FUZZER_FLAG_INT(use_memcmp, 1, +FUZZER_FLAG_INT(use_memcmp, 0, "Use hints from intercepting memcmp, strcmp, etc") FUZZER_FLAG_INT(use_memmem, 1, "Use hints from intercepting memmem, strstr, etc") diff --git a/lib/Fuzzer/FuzzerInterface.h b/lib/Fuzzer/FuzzerInterface.h index d47e20e3a2b..c2c0a39843c 100644 --- a/lib/Fuzzer/FuzzerInterface.h +++ b/lib/Fuzzer/FuzzerInterface.h @@ -55,7 +55,7 @@ size_t LLVMFuzzerCustomCrossOver(const uint8_t *Data1, size_t Size1, unsigned int Seed); // Experimental, may go away in future. -// libFuzzer-provided function to be used inside LLVMFuzzerTestOneInput. +// libFuzzer-provided function to be used inside LLVMFuzzerCustomMutator. // Mutates raw data in [Data, Data+Size) inplace. // Returns the new size, which is not greater than MaxSize. size_t LLVMFuzzerMutate(uint8_t *Data, size_t Size, size_t MaxSize); diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp index 96a87b879d6..f059264db8a 100644 --- a/lib/Fuzzer/FuzzerMutate.cpp +++ b/lib/Fuzzer/FuzzerMutate.cpp @@ -200,28 +200,27 @@ size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size, // It first tries to find one of the arguments (possibly swapped) in the // input and if it succeeds it creates a DE with a position hint. // Otherwise it creates a DE with one of the arguments w/o a position hint. -template DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( - T Arg1, T Arg2, const uint8_t *Data, size_t Size) { + const void *Arg1, const void *Arg2, + const void *Arg1Mutation, const void *Arg2Mutation, + size_t ArgSize, const uint8_t *Data, + size_t Size) { ScopedDoingMyOwnMemmem scoped_doing_my_own_memmem; bool HandleFirst = Rand.RandBool(); - T ExistingBytes, DesiredBytes; + const void *ExistingBytes, *DesiredBytes; Word W; const uint8_t *End = Data + Size; for (int Arg = 0; Arg < 2; Arg++) { ExistingBytes = HandleFirst ? Arg1 : Arg2; - DesiredBytes = HandleFirst ? Arg2 : Arg1; - DesiredBytes += Rand(-1, 1); - if (Rand.RandBool()) ExistingBytes = Bswap(ExistingBytes); - if (Rand.RandBool()) DesiredBytes = Bswap(DesiredBytes); + DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation; HandleFirst = !HandleFirst; - W.Set(reinterpret_cast(&DesiredBytes), sizeof(T)); + W.Set(reinterpret_cast(DesiredBytes), ArgSize); const size_t kMaxNumPositions = 8; size_t Positions[kMaxNumPositions]; size_t NumPositions = 0; for (const uint8_t *Cur = Data; Cur < End && NumPositions < kMaxNumPositions; Cur++) { - Cur = (uint8_t *)SearchMemory(Cur, End - Cur, &ExistingBytes, sizeof(T)); + Cur = (uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize); if (!Cur) break; Positions[NumPositions++] = Cur - Data; } @@ -232,20 +231,46 @@ DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( return DE; } + +template +DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( + T Arg1, T Arg2, const uint8_t *Data, size_t Size) { + if (Rand.RandBool()) Arg1 = Bswap(Arg1); + if (Rand.RandBool()) Arg2 = Bswap(Arg2); + T Arg1Mutation = Arg1 + Rand(-1, 1); + T Arg2Mutation = Arg2 + Rand(-1, 1); + return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation, + sizeof(Arg1), Data, Size); +} + +DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP( + const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) { + return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(), + Arg2.data(), Arg1.size(), Data, Size); +} + size_t MutationDispatcher::Mutate_AddWordFromTORC( uint8_t *Data, size_t Size, size_t MaxSize) { Word W; DictionaryEntry DE; - if (Rand.RandBool()) { + switch (Rand(3)) { + case 0: { auto X = TPC.TORC8.Get(Rand.Rand()); DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); - } else { + } break; + case 1: { auto X = TPC.TORC4.Get(Rand.Rand()); if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool()) - DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, - Size); + DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size); else DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); + } break; + case 2: { + auto X = TPC.TORCW.Get(Rand.Rand()); + DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size); + } break; + default: + assert(0); } Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE); if (!Size) return 0; diff --git a/lib/Fuzzer/FuzzerMutate.h b/lib/Fuzzer/FuzzerMutate.h index 26e23aff955..3d78b111c66 100644 --- a/lib/Fuzzer/FuzzerMutate.h +++ b/lib/Fuzzer/FuzzerMutate.h @@ -114,6 +114,13 @@ private: template DictionaryEntry MakeDictionaryEntryFromCMP(T Arg1, T Arg2, const uint8_t *Data, size_t Size); + DictionaryEntry MakeDictionaryEntryFromCMP(const Word &Arg1, const Word &Arg2, + const uint8_t *Data, size_t Size); + DictionaryEntry MakeDictionaryEntryFromCMP(const void *Arg1, const void *Arg2, + const void *Arg1Mutation, + const void *Arg2Mutation, + size_t ArgSize, + const uint8_t *Data, size_t Size); Random &Rand; const FuzzingOptions Options; diff --git a/lib/Fuzzer/FuzzerTracePC.cpp b/lib/Fuzzer/FuzzerTracePC.cpp index 39d6e602621..e9101fbb786 100644 --- a/lib/Fuzzer/FuzzerTracePC.cpp +++ b/lib/Fuzzer/FuzzerTracePC.cpp @@ -212,38 +212,27 @@ void TracePC::DumpCoverage() { ATTRIBUTE_NO_SANITIZE_MEMORY void TracePC::AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2, - size_t n) { + size_t n, bool StopAtZero) { if (!n) return; - size_t Len = std::min(n, (size_t)32); - const uint8_t *A1 = reinterpret_cast(s1); - const uint8_t *A2 = reinterpret_cast(s2); - size_t I = 0; - for (; I < Len; I++) - if (A1[I] != A2[I]) - break; - size_t PC = reinterpret_cast(caller_pc); - size_t Idx = I; - // if (I < Len) - // Idx += __builtin_popcountl((A1[I] ^ A2[I])) - 1; - TPC.HandleValueProfile((PC & 4095) | (Idx << 12)); -} - -ATTRIBUTE_NO_SANITIZE_MEMORY -void TracePC::AddValueForStrcmp(void *caller_pc, const char *s1, const char *s2, - size_t n) { - if (!n) return; - size_t Len = std::min(n, (size_t)32); + size_t Len = std::min(n, Word::GetMaxSize()); const uint8_t *A1 = reinterpret_cast(s1); const uint8_t *A2 = reinterpret_cast(s2); + uint8_t B1[Word::kMaxSize]; + uint8_t B2[Word::kMaxSize]; + // Copy the data into locals in this non-msan-instrumented function + // to avoid msan complaining further. + for (size_t i = 0; i < Len; i++) { + B1[i] = A1[i]; + B2[i] = A2[i]; + } size_t I = 0; for (; I < Len; I++) - if (A1[I] != A2[I] || A1[I] == 0) + if (B1[I] != B2[I] || (StopAtZero && B1[I] == 0)) break; size_t PC = reinterpret_cast(caller_pc); - size_t Idx = I; - // if (I < Len && A1[I]) - // Idx += __builtin_popcountl((A1[I] ^ A2[I])) - 1; - TPC.HandleValueProfile((PC & 4095) | (Idx << 12)); + size_t Idx = (PC & 4095) | (I << 12); + TPC.HandleValueProfile(Idx); + TORCW.Insert(Idx, Word(B1, Len), Word(B2, Len)); } template diff --git a/lib/Fuzzer/FuzzerTracePC.h b/lib/Fuzzer/FuzzerTracePC.h index b6b26b6c9af..3f9dced2558 100644 --- a/lib/Fuzzer/FuzzerTracePC.h +++ b/lib/Fuzzer/FuzzerTracePC.h @@ -13,7 +13,9 @@ #define LLVM_FUZZER_TRACE_PC #include "FuzzerDefs.h" +#include "FuzzerDictionary.h" #include "FuzzerValueBitMap.h" + #include namespace fuzzer { @@ -74,15 +76,13 @@ class TracePC { void DumpCoverage(); void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2, - size_t n); - void AddValueForStrcmp(void *caller_pc, const char *s1, const char *s2, - size_t n); + size_t n, bool StopAtZero); bool UsingTracePcGuard() const {return NumModules; } - static const size_t kTORCSize = 1 << 5; - TableOfRecentCompares TORC4; - TableOfRecentCompares TORC8; + TableOfRecentCompares TORC4; + TableOfRecentCompares TORC8; + TableOfRecentCompares TORCW; void PrintNewPCs(); void InitializePrintNewPCs(); diff --git a/lib/Fuzzer/FuzzerTraceState.cpp b/lib/Fuzzer/FuzzerTraceState.cpp index 2ad9702fab0..8c812512fd1 100644 --- a/lib/Fuzzer/FuzzerTraceState.cpp +++ b/lib/Fuzzer/FuzzerTraceState.cpp @@ -50,7 +50,7 @@ public: const uint8_t *DesiredData, size_t DataSize); void StartTraceRecording() { - if (!Options.UseMemcmp) + if (!Options.UseMemcmp && !Options.UseMemmem) return; RecordingMemcmp = Options.UseMemcmp; RecordingMemmem = Options.UseMemmem; @@ -60,7 +60,7 @@ public: } void StopTraceRecording() { - if (!RecordingMemcmp) + if (!RecordingMemcmp && !RecordingMemmem) return; RecordingMemcmp = false; for (size_t i = 0; i < NumMutations; i++) { @@ -192,7 +192,7 @@ void Fuzzer::StopTraceRecording() { } void Fuzzer::InitializeTraceState() { - if (!Options.UseMemcmp) return; + if (!Options.UseMemcmp && !Options.UseMemmem) return; TS = new TraceState(MD, Options, this); } @@ -217,37 +217,37 @@ extern "C" { #if LLVM_FUZZER_DEFINES_SANITIZER_WEAK_HOOOKS void __sanitizer_weak_hook_memcmp(void *caller_pc, const void *s1, const void *s2, size_t n, int result) { - fuzzer::TPC.AddValueForMemcmp(caller_pc, s1, s2, n); - if (!RecordingMemcmp) return; if (result == 0) return; // No reason to mutate. if (n <= 1) return; // Not interesting. + fuzzer::TPC.AddValueForMemcmp(caller_pc, s1, s2, n, /*StopAtZero*/false); + if (!RecordingMemcmp) return; TS->TraceMemcmpCallback(n, reinterpret_cast(s1), reinterpret_cast(s2)); } void __sanitizer_weak_hook_strncmp(void *caller_pc, const char *s1, const char *s2, size_t n, int result) { - fuzzer::TPC.AddValueForStrcmp(caller_pc, s1, s2, n); - if (!RecordingMemcmp) return; if (result == 0) return; // No reason to mutate. size_t Len1 = fuzzer::InternalStrnlen(s1, n); size_t Len2 = fuzzer::InternalStrnlen(s2, n); n = std::min(n, Len1); n = std::min(n, Len2); if (n <= 1) return; // Not interesting. + fuzzer::TPC.AddValueForMemcmp(caller_pc, s1, s2, n, /*StopAtZero*/true); + if (!RecordingMemcmp) return; TS->TraceMemcmpCallback(n, reinterpret_cast(s1), reinterpret_cast(s2)); } void __sanitizer_weak_hook_strcmp(void *caller_pc, const char *s1, const char *s2, int result) { - fuzzer::TPC.AddValueForStrcmp(caller_pc, s1, s2, 64); - if (!RecordingMemcmp) return; if (result == 0) return; // No reason to mutate. size_t Len1 = strlen(s1); size_t Len2 = strlen(s2); size_t N = std::min(Len1, Len2); if (N <= 1) return; // Not interesting. + fuzzer::TPC.AddValueForMemcmp(caller_pc, s1, s2, N, /*StopAtZero*/true); + if (!RecordingMemcmp) return; TS->TraceMemcmpCallback(N, reinterpret_cast(s1), reinterpret_cast(s2)); } diff --git a/lib/Fuzzer/test/SingleStrcmpTest.cpp b/lib/Fuzzer/test/SingleStrcmpTest.cpp index 73470b527ee..48f481dfc51 100644 --- a/lib/Fuzzer/test/SingleStrcmpTest.cpp +++ b/lib/Fuzzer/test/SingleStrcmpTest.cpp @@ -8,10 +8,14 @@ #include extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { - char *S = (char*)Data; - if (Size >= 7 && !strcmp(S, "qwerty")) { - fprintf(stderr, "BINGO\n"); - exit(1); + if (Size >= 7) { + char Copy[7]; + memcpy(Copy, Data, 6); + Copy[6] = 0; + if (!strcmp(Copy, "qwerty")) { + fprintf(stderr, "BINGO\n"); + exit(1); + } } return 0; } diff --git a/lib/Fuzzer/test/fuzzer-traces-hooks.test b/lib/Fuzzer/test/fuzzer-traces-hooks.test index 71fe6f2daf1..0c22523be42 100644 --- a/lib/Fuzzer/test/fuzzer-traces-hooks.test +++ b/lib/Fuzzer/test/fuzzer-traces-hooks.test @@ -5,19 +5,19 @@ REQUIRES: linux CHECK: BINGO Done1000000: Done 1000000 runs in -RUN: not LLVMFuzzer-MemcmpTest -seed=4294967295 -runs=100000 2>&1 | FileCheck %s -RUN: LLVMFuzzer-MemcmpTest -use_memcmp=0 -seed=4294967295 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 +RUN: not LLVMFuzzer-MemcmpTest -seed=1 -runs=1000000 2>&1 | FileCheck %s +ZZZ: LLVMFuzzer-MemcmpTest -use_memcmp=0 -seed=4294967295 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-StrncmpTest -seed=2 -runs=100000 2>&1 | FileCheck %s -RUN: LLVMFuzzer-StrncmpTest -use_memcmp=0 -seed=3 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 +RUN: not LLVMFuzzer-StrncmpTest -seed=2 -runs=1000000 2>&1 | FileCheck %s +ZZZ: LLVMFuzzer-StrncmpTest -use_memcmp=0 -seed=3 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: not LLVMFuzzer-StrcmpTest -seed=4 -runs=200000 2>&1 | FileCheck %s -RUN: LLVMFuzzer-StrcmpTest -use_memcmp=0 -seed=5 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 +RUN: not LLVMFuzzer-StrcmpTest -seed=4 -runs=1000000 2>&1 | FileCheck %s +ZZZ: LLVMFuzzer-StrcmpTest -use_memcmp=0 -seed=5 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 RUN: not LLVMFuzzer-StrstrTest -seed=6 -runs=200000 2>&1 | FileCheck %s -RUN: LLVMFuzzer-StrstrTest -use_memmem=0 -seed=7 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 +ZZZ: LLVMFuzzer-StrstrTest -use_memmem=0 -seed=7 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -RUN: LLVMFuzzer-RepeatedMemcmp -seed=10 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT +DISABLED: LLVMFuzzer-RepeatedMemcmp -seed=11 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT RECOMMENDED_DICT:###### Recommended dictionary. ###### RECOMMENDED_DICT-DAG: "foo" RECOMMENDED_DICT-DAG: "bar" -- 2.40.0