(1) bring back support of dfsan into libFuzzer (2) introduce more dfsan hooks (3) introduce a bias in mutations towards locations found by dfsan (4) add support for taking input from static analyzer abouts hints to potentially buggy locations and...

[farahhariri]

Summary

...hook that with dfsan and libFuzzer to guide fuzzing towards those locations

[kcc]

• I'd like to see some kind of design doc first (preferably, in a form of comment in e.g. FuzzerDFSan.h
• Is it possible to split this patch into several (e.g. can static-analyzer-pl-parser.py go separately? )
• does static-analyzer-pl-parser.py have to be in pythoin? Why is C++ less/not suitable?
• tests are must-have
• don't copy-paste code (e.g. lots of changes in FuzzerMutate.cpp seem similar)
• try to put dfsan-specific code in separate file(s)
• please obey the LLVM coding style

[farahhariri]

This comment was removed by farahhariri.

lib/Fuzzer/FuzzerDFSan.h

+//===- FuzzerDFSan.h - Internal header for the Fuzzer -----------*- C++ -* ===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// DFSan interface.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_DFSAN_H
+#define LLVM_FUZZER_DFSAN_H
+
+#define LLVM_FUZZER_SUPPORTS_DFSAN 0
+#if defined(__has_include)
+# if __has_include(<sanitizer/dfsan_interface.h>)
+#  if defined (__linux__)
+#   undef LLVM_FUZZER_SUPPORTS_DFSAN
+#   define LLVM_FUZZER_SUPPORTS_DFSAN 1
+#   include <sanitizer/dfsan_interface.h>
+#  endif  // __linux__
+# endif
+#endif  // defined(__has_include)
+
+#if LLVM_FUZZER_SUPPORTS_DFSAN
+
+extern "C" {
+__attribute__((weak))
+dfsan_label dfsan_create_label(const char *desc, void *userdata);
+__attribute__((weak))
+void dfsan_set_label(dfsan_label label, void *addr, size_t size);
+__attribute__((weak))
+void dfsan_add_label(dfsan_label label, void *addr, size_t size);
+__attribute__((weak))
+const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label);
+__attribute__((weak))
+dfsan_label dfsan_read_label(const void *addr, size_t size);
+__attribute__((weak))
+void dfsan_reset(void);
+}  // extern "C"
+
+namespace fuzzer {
+static bool ReallyHaveDFSan() {
+  return &dfsan_create_label != nullptr;
+}
+}  // namespace fuzzer
+#else
+// When compiling with a compiler which does not support dfsan,
+// this code is still expected to build (but not necessary work).
+typedef unsigned short dfsan_label;
+struct dfsan_label_info {
+  dfsan_label l1, l2;
+  const char *desc;
+  void *userdata;
+};
+namespace fuzzer {
+static bool ReallyHaveDFSan() { return false; }
+}  // namespace fuzzer
+
+#endif // LLVM_FUZZER_SUPPORTS_DFSAN
+
+#endif // LLVM_FUZZER_DFSAN_H

lib/Fuzzer/FuzzerDriver.cpp

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
 
   if (Flags.workers > 0 && Flags.jobs > 0)
     return RunInMultipleProcesses(Args, Flags.workers, Flags.jobs);
 
   const size_t kMaxSaneLen = 1 << 20;
   const size_t kMinDefaultLen = 4096;
   FuzzingOptions Options;
   Options.Verbosity = Flags.verbosity;
+  if (Flags.sa_locs_file)
+    Options.InterestingLocsFile = Flags.sa_locs_file;
+  else
+    Options.InterestingLocsFile = "";
   Options.MaxLen = Flags.max_len;
   Options.ExperimentalLenControl = Flags.experimental_len_control;
   if (Flags.experimental_len_control && Flags.max_len == kMinDefaultLen)
     Options.MaxLen = 1 << 20;
   Options.UnitTimeoutSec = Flags.timeout;
   Options.ErrorExitCode = Flags.error_exitcode;
   Options.TimeoutExitCode = Flags.timeout_exitcode;
   Options.MaxTotalTimeSec = Flags.max_total_time;

lib/Fuzzer/FuzzerFlags.def

FUZZER_FLAG_INT(timeout_exitcode, 77, "When libFuzzer reports a timeout "
   "this exit code will be used.")
 FUZZER_FLAG_INT(max_total_time, 0, "If positive, indicates the maximal total "
                                    "time in seconds to run the fuzzer.")
 FUZZER_FLAG_INT(help, 0, "Print help.")
 FUZZER_FLAG_INT(merge, 0, "If 1, the 2-nd, 3-rd, etc corpora will be "
   "merged into the 1-st corpus. Only interesting units will be taken. "
   "This flag can be used to minimize a corpus.")
 FUZZER_FLAG_STRING(merge_control_file, "internal flag")
+FUZZER_FLAG_STRING(sa_locs_file, "file containing interesting locations found by static analyzer for guided fuzzing.")
 FUZZER_FLAG_STRING(save_coverage_summary, "Experimental:"
                    " save coverage summary to a given file."
                    " Used with -merge=1")
 FUZZER_FLAG_STRING(load_coverage_summary, "Experimental:"
                    " load coverage summary from a given file."
                    " Treat this coverage as belonging to the first corpus. "
                    " Used with -merge=1")
 FUZZER_FLAG_INT(minimize_crash, 0, "If 1, minimizes the provided"

lib/Fuzzer/FuzzerInternal.h

public:
 
   Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
          FuzzingOptions Options);
   ~Fuzzer();
   void Loop();
   void MinimizeCrashLoop(const Unit &U);
   void ShuffleAndMinimize(UnitVector *V);
   void InitializeTraceState();
+  void AssignTaintLabels(uint8_t *Data, size_t Size);
   void RereadOutputCorpus(size_t MaxSize);
 
   size_t secondsSinceProcessStartUp() {
     return duration_cast<seconds>(system_clock::now() - ProcessStartTime)
         .count();
   }
 
   bool TimedOut() {

lib/Fuzzer/FuzzerLoop.cpp

void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
   if (SMR.IsClient())
     SMR.WriteByteArray(Data, Size);
   // We copy the contents of Unit into a separate heap buffer
   // so that we reliably find buffer overflows in it.
   uint8_t *DataCopy = new uint8_t[Size];
   memcpy(DataCopy, Data, Size);
   if (CurrentUnitData && CurrentUnitData != Data)
     memcpy(CurrentUnitData, Data, Size);
+  AssignTaintLabels(DataCopy, Size);
   CurrentUnitSize = Size;
   AllocTracer.Start(Options.TraceMalloc);
   UnitStartTime = system_clock::now();
   TPC.ResetMaps();
   RunningCB = true;
   int Res = CB(DataCopy, Size);
   RunningCB = false;
   UnitStopTime = system_clock::now();
size_t CurrentMaxMutationLen =
                                MD.GetRand())
           : MaxMutationLen;
 
   for (int i = 0; i < Options.MutateDepth; i++) {
     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
       break;
     size_t NewSize = 0;
     NewSize = MD.Mutate(CurrentUnitData, Size, CurrentMaxMutationLen);
+    if (NewSize ==1)
+      break;
     assert(NewSize > 0 && "Mutator returned empty unit");
     assert(NewSize <= CurrentMaxMutationLen && "Mutator return overisized unit");
     Size = NewSize;
     if (i == 0)
       StartTraceRecording();
     II.NumExecutedMutations++;
     if (size_t NumFeatures = RunOne(CurrentUnitData, Size)) {
       Corpus.AddToCorpus({CurrentUnitData, CurrentUnitData + Size}, NumFeatures,

lib/Fuzzer/FuzzerMutate.h

public:
   size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2,
                    size_t Size2, uint8_t *Out, size_t MaxOutSize);
 
   void AddWordToManualDictionary(const Word &W);
 
   void AddWordToAutoDictionary(DictionaryEntry DE);
   void ClearAutoDictionary();
   void PrintRecommendedDictionary();
+  void AddInputLocation(size_t loc);
 
   void SetCorpus(const InputCorpus *Corpus) { this->Corpus = Corpus; }
 
   Random &GetRand() { return Rand; }
 
+
 private:
 
   struct Mutator {
     size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
     const char *Name;
   };
 
   size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size,
private:
   const InputCorpus *Corpus = nullptr;
   std::vector<uint8_t> MutateInPlaceHere;
   // CustomCrossOver needs its own buffer as a custom implementation may call
   // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere.
   std::vector<uint8_t> CustomCrossOverInPlaceHere;
 
   std::vector<Mutator> Mutators;
   std::vector<Mutator> DefaultMutators;
+  std::vector<size_t> InterestingInputLocs;
 };
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MUTATE_H

lib/Fuzzer/FuzzerMutate.cpp

size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size,
   memmove(Data + Idx, Data + Idx + N, Size - Idx - N);
   // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx);
   return Size - N;
 }
 
 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
                                              size_t MaxSize) {
   if (Size >= MaxSize) return 0;
-  size_t Idx = Rand(Size + 1);
+  size_t Idx;
+  size_t InterestingLocsNum = InterestingInputLocs.size();
+  if( InterestingLocsNum > 0) {
+    bool found = false;
+    size_t index;
+    for(int i = 0; i < 100; i++) {
+      index = Rand(InterestingLocsNum);
+      Idx = InterestingInputLocs[index];
+      if (Idx < Size) {
+        found = true;
+        break;
+      }
+    }
+    // if we don't find a good index after 100 trials, give up and default to random
+    if (!found)
+      Idx = Rand(Size + 1);
+  } else {
+    Idx = Rand(Size + 1);
+  }
   // Insert new value at Data[Idx].
   memmove(Data + Idx + 1, Data + Idx, Size - Idx);
   Data[Idx] = RandCh(Rand);
   return Size + 1;
 }
 
 size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data,
                                                       size_t Size,
                                                       size_t MaxSize) {
   const size_t kMinBytesToInsert = 3;
   if (Size + kMinBytesToInsert >= MaxSize) return 0;
   size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128);
   size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert;
   assert(Size + N <= MaxSize && N);
-  size_t Idx = Rand(Size + 1);
+  size_t Idx;
+  size_t InterestingLocsNum = InterestingInputLocs.size();
+  if(InterestingLocsNum > 0) {
+    bool found = false;
+    size_t index;
+    for(int i = 0; i < 100; i++) {
+      index = Rand(InterestingLocsNum);
+      Idx = InterestingInputLocs[index];
+      if (Idx < Size) {
+        found = true;
+        break;
+      }
+    }
+    // if we don't find a good index after 100 trials, give up and default to random
+    if (!found)
+      Idx = Rand(Size + 1);
+  } else {
+    Idx = Rand(Size + 1);
+  }
   // Insert new values at Data[Idx].
   memmove(Data + Idx + N, Data + Idx, Size - Idx);
   // Give preference to 0x00 and 0xff.
   uint8_t Byte = Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255);
   for (size_t i = 0; i < N; i++)
     Data[Idx + i] = Byte;
   return Size + N;
 }
 
 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
                                              size_t MaxSize) {
   if (Size > MaxSize) return 0;
-  size_t Idx = Rand(Size);
+  size_t Idx;
+  size_t InterestingLocsNum = InterestingInputLocs.size();
+  if( InterestingLocsNum > 0) {
+    bool found = false;
+    size_t index;
+    for(int i = 0; i < 100; i++) {
+      index = Rand(InterestingLocsNum);
+      Idx = InterestingInputLocs[index];
+      if (Idx < Size) {
+        found = true;
+        break;
+      }
+    }
+    // if we don't find a good index after 100 trials, give up and default to random
+    if (!found)
+      Idx = Rand(Size);
+  } else {
+    Idx = Rand(Size);
+  }
   Data[Idx] = RandCh(Rand);
   return Size;
 }
 
 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
                                             size_t MaxSize) {
   if (Size > MaxSize) return 0;
-  size_t Idx = Rand(Size);
+  size_t Idx;
+  size_t InterestingLocsNum = InterestingInputLocs.size();
+  if( InterestingLocsNum > 0) {
+    bool found = false;
+    size_t index;
+    for(int i = 0; i < 100; i++) {
+      index = Rand(InterestingLocsNum);
+      Idx = InterestingInputLocs[index];
+      if (Idx < Size) {
+        found = true;
+        break;
+      }
+    }
+    // if we don't find a good index after 100 trials, give up and default to random
+    if (!found)
+      Idx = Rand(Size);
+  } else {
+    Idx = Rand(Size);
+  }
   Data[Idx] ^= 1 << Rand(8);
   return Size;
 }
 
 size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
                                                               size_t Size,
                                                               size_t MaxSize) {
   return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
 }
 
 size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary(
     uint8_t *Data, size_t Size, size_t MaxSize) {
   return AddWordFromDictionary(TempAutoDictionary, Data, Size, MaxSize);
 }
 
 size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size,
                                                 size_t MaxSize,
                                                 DictionaryEntry &DE) {
   const Word &W = DE.GetW();
+  bool CachedPosition = false;
+  size_t CachedIdx;
+  size_t InterestingLocsNum = InterestingInputLocs.size();
+  if( InterestingLocsNum > 0) {
+    size_t index = Rand(InterestingLocsNum);
+    CachedIdx = InterestingInputLocs[index];
+    if (CachedIdx + W.size() < Size)
+      CachedPosition = true;
+  }
   bool UsePositionHint = DE.HasPositionHint() &&
                          DE.GetPositionHint() + W.size() < Size &&
                          Rand.RandBool();
+  if(UsePositionHint) {
+    uint8_t size = W.size();
+    const uint8_t* data = W.data();
+  }
+
   if (Rand.RandBool()) {  // Insert W.
     if (Size + W.size() > MaxSize) return 0;
-    size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
+    size_t Idx;
+    if (CachedPosition)
+      Idx = CachedIdx;
+    else
+      Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
     memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
     memcpy(Data + Idx, W.data(), W.size());
     Size += W.size();
   } else {  // Overwrite some bytes with W.
     if (W.size() > Size) return 0;
     size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size());
     memcpy(Data + Idx, W.data(), W.size());
   }

 }
 
 void MutationDispatcher::AddWordToAutoDictionary(DictionaryEntry DE) {
   static const size_t kMaxAutoDictSize = 1 << 14;
   if (TempAutoDictionary.size() >= kMaxAutoDictSize) return;
   TempAutoDictionary.push_back(DE);
 }
 
+void MutationDispatcher::AddInputLocation(size_t loc) {
+  InterestingInputLocs.push_back(loc);
+}
+
 void MutationDispatcher::ClearAutoDictionary() {
   TempAutoDictionary.clear();
 }
 
 }  // namespace fuzzer

lib/Fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   bool Shrink = false;
   int ReloadIntervalSec = 1;
   bool ShuffleAtStartUp = true;
   bool PreferSmall = true;
   size_t MaxNumberOfRuns = -1L;
   int ReportSlowUnits = 10;
   bool OnlyASCII = false;
   std::string OutputCorpus;
+  std::string InterestingLocsFile;
   std::string ArtifactPrefix = "./";
   std::string ExactArtifactPath;
   std::string ExitOnSrcPos;
   std::string ExitOnItem;
   bool SaveArtifacts = true;
   bool PrintNEW = true; // Print a status line when new units are found;
   bool PrintNewCovPcs = false;
   bool PrintFinalStats = false;

lib/Fuzzer/FuzzerSHA1.cpp

void ComputeSHA1(const uint8_t *Data, size_t Len, uint8_t *Out) {
   sha1_init(&s);
   sha1_write(&s, (const char*)Data, Len);
   memcpy(Out, sha1_result(&s), HASH_LENGTH);
 }
 
 std::string Sha1ToString(const uint8_t Sha1[kSHA1NumBytes]) {
   std::stringstream SS;
   for (int i = 0; i < kSHA1NumBytes; i++)
-    SS << std::hex << std::setfill('0') << std::setw(2) << (unsigned)Sha1[i];
+    SS << std::hex << std::setfill('0') << std::setw(2) << reinterpret_cast<unsigned char>(Sha1[i]);
   return SS.str();
 }
 
 std::string Hash(const Unit &U) {
   uint8_t Hash[kSHA1NumBytes];
   ComputeSHA1(U.data(), U.size(), Hash);
   return Sha1ToString(Hash);
 }
 
 }

lib/Fuzzer/FuzzerTraceState.cpp

 //===- FuzzerTraceState.cpp - Trace-based fuzzer mutator ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 // Data tracing.
 //===----------------------------------------------------------------------===//
 
+#include "FuzzerDFSan.h"
 #include "FuzzerDictionary.h"
-#include "FuzzerIO.h"
 #include "FuzzerInternal.h"
+#include "FuzzerIO.h"
 #include "FuzzerMutate.h"
 #include "FuzzerTracePC.h"
+
 #include <algorithm>
 #include <cstring>
+#include <execinfo.h>
+#include <fstream>
 #include <map>
 #include <set>
+#include <sys/stat.h>
+#include <stdio.h>
+#include <stdlib.h>
 #include <thread>
+#include <inttypes.h>
+
+#if !LLVM_FUZZER_SUPPORTS_DFSAN
+// Stubs for dfsan for platforms where dfsan does not exist and weak
+// functions don't work.
+extern "C" {
+dfsan_label dfsan_create_label(const char *desc, void *userdata) { return 0; }
+void dfsan_set_label(dfsan_label label, void *addr, size_t size) {}
+void dfsan_add_label(dfsan_label label, void *addr, size_t size) {}
+void dfsan_reset(void) {}
+const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
+  return nullptr;
+}
+dfsan_label dfsan_read_label(const void *addr, size_t size) { return 0; }
+}  // extern "C"
+#endif  // !LLVM_FUZZER_SUPPORTS_DFSAN
+
+
 
 namespace fuzzer {
 
 // Declared as static globals for faster checks inside the hooks.
 static bool RecordingMemmem = false;
+static bool SaLocs = false;
+static std::vector<std::string> InterestingLocs;
 
 int ScopedDoingMyOwnMemOrStr::DoingMyOwnMemOrStr;
 
+struct LabelRange {
+  uint16_t Beg, End;  // Range is [Beg, End), thus Beg==End is an empty range.
+
+  LabelRange(uint16_t Beg = 0, uint16_t End = 0) : Beg(Beg), End(End) {}
+
+  static LabelRange Join(LabelRange LR1, LabelRange LR2) {
+    if (LR1.Beg == LR1.End) return LR2;
+    if (LR2.Beg == LR2.End) return LR1;
+    return {std::min(LR1.Beg, LR2.Beg), std::max(LR1.End, LR2.End)};
+  }
+  LabelRange &Join(LabelRange LR) {
+    return *this = Join(*this, LR);
+  }
+  static LabelRange Singleton(const dfsan_label_info *LI) {
+    uint16_t Idx = (uint16_t)(uintptr_t)LI->userdata;
+    assert(Idx > 0);
+    return {(uint16_t)(Idx - 1), Idx};
+  }
+};
+
+struct TraceBasedMutation {
+  uint32_t Pos;
+  Word W;
+};
+
+
 class TraceState {
 public:
+  LabelRange GetLabelRange(dfsan_label L);
+  void DFSanMemcmpCallback(size_t CmpSize, const uint8_t *Data1,
+                           const uint8_t *Data2, dfsan_label L1,
+                           dfsan_label L2);
+  void DFSanStrchrCallback(dfsan_label s_label, dfsan_label c_label) ;
+  void DFSanStrlenCallback(dfsan_label Label);
+  void AddInputLocsInRange(LabelRange LR);
   TraceState(MutationDispatcher &MD, const FuzzingOptions &Options,
              const Fuzzer *F)
-      : MD(MD), Options(Options), F(F) {}
+      : MD(MD), Options(Options), F(F) {
+    fuzzer::SaLocs = ReadInterestingLocations(Options.InterestingLocsFile);
+  }
+
+  static bool ReadInterestingLocations(std::string fileName) {
+    struct stat buffer;
+    if (stat(fileName.c_str(), &buffer) != 0)
+      return false;
+
+    std::fstream inFile(fileName);
+    std::string location;
+    while(std::getline(inFile, location)) {
+      InterestingLocs.push_back(location);
+      printf("we are pushing back the line: %s\n", location.c_str());
+    }
+    return true;
+  }
 
   void StartTraceRecording() {
+    printf("START RECORDING\n");
     if (!Options.UseMemmem)
       return;
     RecordingMemmem = true;
+    NumMutations = 0;
     InterestingWords.clear();
-    MD.ClearAutoDictionary();
   }
 
   void StopTraceRecording() {
     if (!RecordingMemmem)
       return;
+    for (size_t i = 0; i < NumMutations; i++) {
+      auto &M = Mutations[i];
+      MD.AddWordToAutoDictionary({M.W, M.Pos});
+    }
     for (auto &W : InterestingWords)
       MD.AddWordToAutoDictionary({W});
   }
 
   void AddInterestingWord(const uint8_t *Data, size_t Size) {
     if (!RecordingMemmem || !F->InFuzzingThread()) return;
     if (Size <= 1) return;
     Size = std::min(Size, Word::GetMaxSize());
     Word W(Data, Size);
     InterestingWords.insert(W);
   }
 
+  void EnsureDfsanLabels(size_t Size) {
+    for(int i = 0; i < 1 << (sizeof(dfsan_label) * 8); i++) {
+      LabelRanges[i] = LabelRange();
+    }
+    LastDfsanLabel = 0;
+    NumMutations = 0;
+    for (; LastDfsanLabel < Size; LastDfsanLabel++) {
+      dfsan_label L = dfsan_create_label("input", (void *)(LastDfsanLabel + 1));
+      // We assume that no one else has called dfsan_create_label before.
+      if (L != LastDfsanLabel + 1) {
+        Printf("DFSan labels are not starting from 1, exiting\n");
+        exit(1);
+      }
+    }
+  }
+
+  void AddMutation(uint32_t Pos, uint32_t Size, const uint8_t *Data) {
+    if (NumMutations >= kMaxMutations) return;
+    if (Size > fuzzer::Word::kMaxSize) return;
+    auto &M = Mutations[NumMutations++];
+    M.Pos = Pos;
+    M.W.Set(Data, Size);
+  }
+
+  void AddMutation(uint32_t Pos, uint32_t Size, uint64_t Data) {
+    assert(Size <= sizeof(Data));
+    AddMutation(Pos, Size, reinterpret_cast<uint8_t*>(&Data));
+  }
+
+
  private:
 
+  static const size_t kMaxMutations = 1 << 16;
+  size_t NumMutations;
+  TraceBasedMutation Mutations[kMaxMutations];
   // TODO: std::set is too inefficient, need to have a custom DS here.
   std::set<Word> InterestingWords;
   MutationDispatcher &MD;
+  LabelRange LabelRanges[1 << (sizeof(dfsan_label) * 8)];
+  size_t LastDfsanLabel = 0;
   const FuzzingOptions Options;
   const Fuzzer *F;
 };
 
 static TraceState *TS;
 
+LabelRange TraceState::GetLabelRange(dfsan_label L) {
+  LabelRange &LR = LabelRanges[L];
+  if (LR.Beg < LR.End || L == 0)
+    return LR;
+  const dfsan_label_info *LI = dfsan_get_label_info(L);
+  if (LI->l1 || LI->l2)
+    return LR = LabelRange::Join(GetLabelRange(LI->l1),
+                                 GetLabelRange(LI->l2));
+
+  return LR = LabelRange::Singleton(LI);
+}
+
+void TraceState::DFSanMemcmpCallback(size_t CmpSize, const uint8_t *Data1,
+                                     const uint8_t *Data2, dfsan_label L1,
+                                     dfsan_label L2) {
+  assert(ReallyHaveDFSan());
+  if (!F->InFuzzingThread()) return;
+  if (L1 == 0 && L2 == 0)
+    return;  // Not actionable.
+  if (L1 != 0 && L2 != 0)
+    return;  // Probably still actionable.
+  const uint8_t *Data = L1 ? Data2 : Data1;
+  LabelRange LR = L1 ? GetLabelRange(L1) : GetLabelRange(L2);
+  for (size_t Pos = LR.Beg; Pos + CmpSize <= LR.End; Pos++) {
+    MD.AddInputLocation(Pos);
+    AddMutation(Pos, CmpSize, Data);
+    if (Options.Verbosity >= 3)
+      Printf("DFSanMemcmpCallback: Pos %d Size %d\n", Pos, CmpSize);
+  }
+}
+
+void TraceState::AddInputLocsInRange(LabelRange LR) {
+  for (size_t Loc = LR.Beg; Loc <= LR.End; Loc++) {
+    MD.AddInputLocation(Loc);
+  }
+}
+
+void TraceState::DFSanStrchrCallback(dfsan_label s_label, dfsan_label c_label) {
+  LabelRange LR1 = GetLabelRange(s_label);
+  LabelRange LR2 = GetLabelRange(c_label);
+  AddInputLocsInRange(LR1);
+  AddInputLocsInRange(LR2);
+}
+
+void TraceState::DFSanStrlenCallback(dfsan_label Label) {
+  LabelRange LR = GetLabelRange(Label);
+  AddInputLocsInRange(LR);
+}
+
+bool FindCodeLineInTrace ()
+{
+  void *array[20];
+  size_t size;
+  size_t i;
+
+  size = backtrace (array, 20);
+
+  for (int i = 0; i < size; i++) {
+    char data[1000];
+    for (std::string location: fuzzer::InterestingLocs) {
+      std::string line(data);
+      std::size_t found = line.find(location);
+      if (found!=std::string::npos)
+        return true;
+    }
+    fuzzer::EF->__sanitizer_symbolize_pc(array[i], "%p %F %L", data,
+                           sizeof(data));
+  }
+
+  return false;
+}
+
 void Fuzzer::StartTraceRecording() {
   if (!TS) return;
   TS->StartTraceRecording();
 }
 
 void Fuzzer::StopTraceRecording() {
   if (!TS) return;
   TS->StopTraceRecording();
 }
 
 void Fuzzer::InitializeTraceState() {
   if (!Options.UseMemmem) return;
   TS = new TraceState(MD, Options, this);
 }
 
 static size_t InternalStrnlen(const char *S, size_t MaxLen) {
   size_t Len = 0;
   for (; Len < MaxLen && S[Len]; Len++) {}
   return Len;
 }
 
+void Fuzzer::AssignTaintLabels(uint8_t *Data, size_t Size) {
+  if (!ReallyHaveDFSan()) return;
+  dfsan_reset();
+  TS->EnsureDfsanLabels(Size);
+  for (size_t i = 0; i < Size; i++) {
+    dfsan_set_label(i + 1, &Data[i], 1);
+  }
+}
+
+
+
 // Finds min of (strlen(S1), strlen(S2)).
 // Needed bacause one of these strings may actually be non-zero terminated.
 static size_t InternalStrnlen2(const char *S1, const char *S2) {
   size_t Len = 0;
   for (; S1[Len] && S2[Len]; Len++)  {}
   return Len;
 }
 
 }  // namespace fuzzer
 
 using fuzzer::TS;
 
 extern "C" {
+#define DFSAN_CMP_CALLBACK(N)                                                  \
+  void __dfsw___sanitizer_cov_trace_cmp##N(uint64_t Arg1, uint64_t Arg2,       \
+                                           dfsan_label L1, dfsan_label L2) {   \
+  }
+
+DFSAN_CMP_CALLBACK(1)
+DFSAN_CMP_CALLBACK(2)
+DFSAN_CMP_CALLBACK(4)
+DFSAN_CMP_CALLBACK(8)
+#undef DFSAN_CMP_CALLBACK
+
+void __dfsw___sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases,
+                                         dfsan_label L1, dfsan_label L2) {
+  TS->DFSanStrchrCallback(L1, L2);
+}
+
+void dfsan_weak_hook_memcmp(void *caller_pc, const void *s1, const void *s2,
+                            size_t n, dfsan_label s1_label,
+                            dfsan_label s2_label, dfsan_label n_label) {
+  dfsan_label L1 = dfsan_read_label(s1, n);
+  dfsan_label L2 = dfsan_read_label(s2, n);
+  if(!fuzzer::SaLocs || (fuzzer::SaLocs && fuzzer::FindCodeLineInTrace()))
+    TS->DFSanMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
+                            reinterpret_cast<const uint8_t *>(s2), L1, L2);
+}
+
+void dfsan_weak_hook_strchr( void *caller_pc,const char *s, int c, dfsan_label s_label,
+                             dfsan_label c_label) {
+  TS->DFSanStrchrCallback(s_label, c_label);
+}
+
+void dfsan_weak_hook_strncasecmp(void *caller_pc, const char *s1,
+                                 const char *s2, size_t n, dfsan_label s1_label,
+                                 dfsan_label s2_label, dfsan_label n_label) {
+  TS->DFSanMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
+                          reinterpret_cast<const uint8_t *>(s2), s1_label, s2_label);
+}
+
+void dfsan_weak_hook_strcasecmp(void *caller_pc, const char *s1, const char *s2,
+                                dfsan_label s1_label, dfsan_label s2_label) {
+  size_t Len1 = strlen(s1);
+  size_t Len2 = strlen(s2);
+  size_t N = std::min(Len1, Len2);
+  TS->DFSanMemcmpCallback(N, reinterpret_cast<const uint8_t *>(s1),
+                          reinterpret_cast<const uint8_t *>(s2), s1_label,
+                          s2_label);
+}
+
+void dfsan_weak_hook_strlen(void *caller_pc, const char *s, dfsan_label s_label) {
+  TS->DFSanStrlenCallback(s_label);
+}
+
+void dfsan_weak_hook_memcpy(void *caller_pc, void *dest, const void *src, size_t n,
+                            dfsan_label dest_label, dfsan_label src_label,
+                            dfsan_label n_label) {
+  TS->DFSanMemcmpCallback(n, reinterpret_cast<const uint8_t *>(src),
+                          reinterpret_cast<const uint8_t *>(dest),
+                          src_label, dest_label);
+}
+
+void dfsan_weak_hook_memset(void *caller_pc, void *s, int c, size_t n,
+                            dfsan_label s_label, dfsan_label c_label,
+                            dfsan_label n_label) {
+  TS->DFSanStrchrCallback(s_label, c_label);
+}
+
+void dfsan_weak_hook_strncpy(void *caller_pc, char *s1, const char *s2, size_t n,
+                             dfsan_label s1_label, dfsan_label s2_label,
+                             dfsan_label n_label) {
+  TS->DFSanStrchrCallback(s1_label, s2_label);
+}
+
+void dfsan_weak_hook_strcpy(void *caller_pc, char *dest, const char *src,
+                            dfsan_label dst_label, dfsan_label src_label) {
+  TS->DFSanStrchrCallback(src_label, dst_label);
+}
+
+void dfsan_weak_hook_strncmp(void *caller_pc, const char *s1, const char *s2,
+                             size_t n, dfsan_label s1_label,
+                             dfsan_label s2_label, dfsan_label n_label) {
+  n = std::min(n, fuzzer::InternalStrnlen(s1, n));
+  n = std::min(n, fuzzer::InternalStrnlen(s2, n));
+  dfsan_label L1 = dfsan_read_label(s1, n);
+  dfsan_label L2 = dfsan_read_label(s2, n);
+  if(!fuzzer::SaLocs || (fuzzer::SaLocs && fuzzer::FindCodeLineInTrace()))
+    TS->DFSanMemcmpCallback(n, reinterpret_cast<const uint8_t *>(s1),
+                            reinterpret_cast<const uint8_t *>(s2), L1, L2);
+}
+
+void dfsan_weak_hook_strcmp(void *caller_pc, const char *s1, const char *s2,
+                            dfsan_label s1_label, dfsan_label s2_label) {
+  size_t Len1 = strlen(s1);
+  size_t Len2 = strlen(s2);
+  size_t N = std::min(Len1, Len2);
+  if (N <= 1) return;  // Not interesting.
+  dfsan_label L1 = dfsan_read_label(s1, Len1);
+  dfsan_label L2 = dfsan_read_label(s2, Len2);
+  if(!fuzzer::SaLocs || (fuzzer::SaLocs && fuzzer::FindCodeLineInTrace()))
+    TS->DFSanMemcmpCallback(N, reinterpret_cast<const uint8_t *>(s1),
+                            reinterpret_cast<const uint8_t *>(s2), L1, L2);
+}
 
 // We may need to avoid defining weak hooks to stay compatible with older clang.
 #ifndef LLVM_FUZZER_DEFINES_SANITIZER_WEAK_HOOOKS
 # define LLVM_FUZZER_DEFINES_SANITIZER_WEAK_HOOOKS 1
 #endif
 
 #if LLVM_FUZZER_DEFINES_SANITIZER_WEAK_HOOOKS
 

lib/Fuzzer/static-analyzer-pl-parser.py

+import argparse
+from collections import defaultdict
+import fnmatch
+import os
+import plistlib
+import sys
+
+
+parser = argparse.ArgumentParser()
+parser.add_argument('-pd', '--plist_directory', default = '', help = 'path to the directory containing the plist files generated by static analyzer')
+parser.add_argument('-o', '--output_file', default = '/tmp/file_map', help = 'name of output file')
+
+def findFiles(pattern, path):
+  ''' Get list of files in path matching pattern. '''
+
+  result = []
+  for root, dirs, files in os.walk(path):
+    for name in files:
+      if fnmatch.fnmatch(name, pattern):
+        result.append(os.path.join(root, name))
+
+  return result
+
+def parseArgs():
+  ''' Get the list of plist files. '''
+
+  cl_args = parser.parse_args()
+  pl_dir = cl_args.plist_directory
+  out_file = cl_args.output_file
+  if not pl_dir:
+    print('ERROR: missing plistdirectory argument.')
+    sys.exit()
+
+  return findFiles('*.plist', pl_dir), out_file
+
+def getInterestingLinesFromFile(file_name, file_lines_map):
+  ''' Map interesting lines to code files from a given plist file. '''
+
+  parsed_map = plistlib.readPlist(file_name)
+  interesting_files = parsed_map['files']
+  if not interesting_files:
+    return file_lines_map
+  diagnostics_list = parsed_map['diagnostics']
+  for bug_dict in diagnostics_list: # each bug has one dict in that list
+    location_dict = bug_dict['location']
+    fname = interesting_files[location_dict['file']]
+    file_lines_map[fname].add(location_dict['line'])
+    path_list = bug_dict['path']
+    for path_node_dict in path_list:
+      if 'location' in path_node_dict.keys():
+        fname = interesting_files[path_node_dict['location']['file']]
+        file_lines_map[fname].add(path_node_dict['location']['line'])
+      elif 'edges' in path_node_dict.keys():
+        for d in path_node_dict['edges']:
+          loc1 = d['start'][0]
+          loc2 = d['end'][0]
+          fname1 = interesting_files[loc1['file']]
+          fname2 = interesting_files[loc2['file']]
+          file_lines_map[fname1].add(loc1['line'])
+          file_lines_map[fname2].add(loc2['line'])
+
+
+  return file_lines_map
+
+
+def getInterestingLinesFromFileList(file_list):
+  ''' list the list of interesting lines to code files from plist files. '''
+
+  file_lines_map = defaultdict(set)
+
+  for file_name in file_list:
+    file_lines_map = getInterestingLinesFromFile(file_name, file_lines_map)
+
+  return file_lines_map
+
+def main():
+  pl_files, out_file = parseArgs();
+  file_lines_map = getInterestingLinesFromFileList(pl_files);
+  with open(out_file, 'w') as out:
+    for file_name in file_lines_map:
+      for line in file_lines_map[file_name]:
+        out.write(file_name + ":" +  str(line) + "\n")
+
+if __name__ == '__main__':
+            main()