[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

llvm-svn: 284273

1 files changed, 53 insertions, 1 deletions

diff --git a/llvm/lib/Fuzzer/FuzzerTracePC.cpp b/llvm/lib/Fuzzer/FuzzerTracePC.cpp
index d843f542cdd..cfaf9c5e571 100644
--- a/llvm/lib/Fuzzer/FuzzerTracePC.cpp
+++ b/llvm/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<uintptr_t>(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 <class T>
+void TracePC::TORCToDict(const TableOfRecentCompares<T, kTORCSize> &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 <class T>
+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<uint16_t>(FindInData),
+                 static_cast<uint16_t>(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<uint8_t *>(&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" {