[libFuzzer] use table of recent compares for memcmp/strcmp (to unify the code between cmp and memcmp handling)

llvm-svn: 292287

10 files changed, 94 insertions, 68 deletions

diff --git a/llvm/lib/Fuzzer/FuzzerDictionary.h b/llvm/lib/Fuzzer/FuzzerDictionary.h
index eba0eabb683..f15ac930f2c 100644
--- a/llvm/lib/Fuzzer/FuzzerDictionary.h
+++ b/llvm/lib/Fuzzer/FuzzerDictionary.h
@@ -20,8 +20,9 @@
 
 namespace fuzzer {
 // A simple POD sized array of bytes.
-template <size_t kMaxSize> class FixedWord {
+template <size_t kMaxSizeT> class FixedWord {
 public:
+  static const size_t kMaxSize = kMaxSizeT;
   FixedWord() {}
   FixedWord(const uint8_t *B, uint8_t S) { Set(B, S); }
 
diff --git a/llvm/lib/Fuzzer/FuzzerFlags.def b/llvm/lib/Fuzzer/FuzzerFlags.def
index 22aad353ace..0deca1793c7 100644
--- a/llvm/lib/Fuzzer/FuzzerFlags.def
+++ b/llvm/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/llvm/lib/Fuzzer/FuzzerInterface.h b/llvm/lib/Fuzzer/FuzzerInterface.h
index d47e20e3a2b..c2c0a39843c 100644
--- a/llvm/lib/Fuzzer/FuzzerInterface.h
+++ b/llvm/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/llvm/lib/Fuzzer/FuzzerMutate.cpp b/llvm/lib/Fuzzer/FuzzerMutate.cpp
index 96a87b879d6..f059264db8a 100644
--- a/llvm/lib/Fuzzer/FuzzerMutate.cpp
+++ b/llvm/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 <class T>
 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<uint8_t*>(&DesiredBytes), sizeof(T));
+    W.Set(reinterpret_cast<const uint8_t*>(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 <class T>
+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/llvm/lib/Fuzzer/FuzzerMutate.h b/llvm/lib/Fuzzer/FuzzerMutate.h
index 26e23aff955..3d78b111c66 100644
--- a/llvm/lib/Fuzzer/FuzzerMutate.h
+++ b/llvm/lib/Fuzzer/FuzzerMutate.h
@@ -114,6 +114,13 @@ private:
   template <class T>
   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/llvm/lib/Fuzzer/FuzzerTracePC.cpp b/llvm/lib/Fuzzer/FuzzerTracePC.cpp
index 39d6e602621..e9101fbb786 100644
--- a/llvm/lib/Fuzzer/FuzzerTracePC.cpp
+++ b/llvm/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<const uint8_t *>(s1);
-  const uint8_t *A2 = reinterpret_cast<const uint8_t *>(s2);
-  size_t I = 0;
-  for (; I < Len; I++)
-    if (A1[I] != A2[I])
-      break;
-  size_t PC = reinterpret_cast<size_t>(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<const uint8_t *>(s1);
   const uint8_t *A2 = reinterpret_cast<const uint8_t *>(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<size_t>(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 <class T>
diff --git a/llvm/lib/Fuzzer/FuzzerTracePC.h b/llvm/lib/Fuzzer/FuzzerTracePC.h
index b6b26b6c9af..3f9dced2558 100644
--- a/llvm/lib/Fuzzer/FuzzerTracePC.h
+++ b/llvm/lib/Fuzzer/FuzzerTracePC.h
@@ -13,7 +13,9 @@
 #define LLVM_FUZZER_TRACE_PC
 
 #include "FuzzerDefs.h"
+#include "FuzzerDictionary.h"
 #include "FuzzerValueBitMap.h"
+
 #include <set>
 
 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<uint32_t, kTORCSize> TORC4;
-  TableOfRecentCompares<uint64_t, kTORCSize> TORC8;
+  TableOfRecentCompares<uint32_t, 32> TORC4;
+  TableOfRecentCompares<uint64_t, 32> TORC8;
+  TableOfRecentCompares<Word, 32> TORCW;
 
   void PrintNewPCs();
   void InitializePrintNewPCs();
diff --git a/llvm/lib/Fuzzer/FuzzerTraceState.cpp b/llvm/lib/Fuzzer/FuzzerTraceState.cpp
index 2ad9702fab0..8c812512fd1 100644
--- a/llvm/lib/Fuzzer/FuzzerTraceState.cpp
+++ b/llvm/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<const uint8_t *>(s1),
                           reinterpret_cast<const uint8_t *>(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<const uint8_t *>(s1),
                           reinterpret_cast<const uint8_t *>(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<const uint8_t *>(s1),
                           reinterpret_cast<const uint8_t *>(s2));
 }
diff --git a/llvm/lib/Fuzzer/test/SingleStrcmpTest.cpp b/llvm/lib/Fuzzer/test/SingleStrcmpTest.cpp
index 73470b527ee..48f481dfc51 100644
--- a/llvm/lib/Fuzzer/test/SingleStrcmpTest.cpp
+++ b/llvm/lib/Fuzzer/test/SingleStrcmpTest.cpp
@@ -8,10 +8,14 @@
 #include <cstdlib>
 
 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/llvm/lib/Fuzzer/test/fuzzer-traces-hooks.test b/llvm/lib/Fuzzer/test/fuzzer-traces-hooks.test
index 71fe6f2daf1..0c22523be42 100644
--- a/llvm/lib/Fuzzer/test/fuzzer-traces-hooks.test
+++ b/llvm/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"