Update aosp/master LLVM for rebase to r230699.

Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9

26 files changed, 1303 insertions, 0 deletions

diff --git a/lib/Fuzzer/CMakeLists.txt b/lib/Fuzzer/CMakeLists.txt
new file mode 100644
index 0000000..81e51d1
--- /dev/null
+++ b/lib/Fuzzer/CMakeLists.txt
@@ -0,0 +1,21 @@
+# Disable the coverage instrumentation for the fuzzer itself.
+set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O2 -fsanitize-coverage=0")
+if( LLVM_USE_SANITIZE_COVERAGE  )
+  add_library(LLVMFuzzerNoMain OBJECT
+    FuzzerCrossOver.cpp
+    FuzzerDriver.cpp
+    FuzzerIO.cpp
+    FuzzerLoop.cpp
+    FuzzerMutate.cpp
+    FuzzerSanitizerOptions.cpp
+    FuzzerUtil.cpp
+    )
+  add_library(LLVMFuzzer STATIC
+    FuzzerMain.cpp
+    $<TARGET_OBJECTS:LLVMFuzzerNoMain>
+    )
+
+  if( LLVM_INCLUDE_TESTS )
+    add_subdirectory(test)
+  endif()
+endif()
diff --git a/lib/Fuzzer/FuzzerCrossOver.cpp b/lib/Fuzzer/FuzzerCrossOver.cpp
new file mode 100644
index 0000000..94af6d5
--- /dev/null
+++ b/lib/Fuzzer/FuzzerCrossOver.cpp
@@ -0,0 +1,47 @@
+//===- FuzzerCrossOver.cpp - Cross over two test inputs -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Cross over test inputs.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInternal.h"
+#include <algorithm>
+
+namespace fuzzer {
+
+// Cross A and B, store the result (ap to MaxLen bytes) in U.
+void CrossOver(const Unit &A, const Unit &B, Unit *U, size_t MaxLen) {
+  size_t Size = rand() % MaxLen + 1;
+  U->clear();
+  const Unit *V = &A;
+  size_t PosA = 0;
+  size_t PosB = 0;
+  size_t *Pos = &PosA;
+  while (U->size() < Size && (PosA < A.size() || PosB < B.size())) {
+    // Merge a part of V into U.
+    size_t SizeLeftU = Size - U->size();
+    if (*Pos < V->size()) {
+      size_t SizeLeftV = V->size() - *Pos;
+      size_t MaxExtraSize = std::min(SizeLeftU, SizeLeftV);
+      size_t ExtraSize = rand() % MaxExtraSize + 1;
+      U->insert(U->end(), V->begin() + *Pos, V->begin() + *Pos + ExtraSize);
+      (*Pos) += ExtraSize;
+    }
+
+    // Use the other Unit on the next iteration.
+    if (Pos == &PosA) {
+      Pos = &PosB;
+      V = &B;
+    } else {
+      Pos = &PosA;
+      V = &A;
+    }
+  }
+}
+
+}  // namespace fuzzer
diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp
new file mode 100644
index 0000000..1746afd
--- /dev/null
+++ b/lib/Fuzzer/FuzzerDriver.cpp
@@ -0,0 +1,199 @@
+//===- FuzzerDriver.cpp - FuzzerDriver function and flags -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// FuzzerDriver and flag parsing.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInterface.h"
+#include "FuzzerInternal.h"
+
+#include <cstring>
+#include <unistd.h>
+#include <iostream>
+#include <thread>
+#include <atomic>
+#include <mutex>
+
+namespace fuzzer {
+
+// Program arguments.
+struct FlagDescription {
+  const char *Name;
+  const char *Description;
+  int   Default;
+  int   *Flag;
+};
+
+struct {
+#define FUZZER_FLAG(Type, Name, Default, Description) Type Name;
+#include "FuzzerFlags.def"
+#undef FUZZER_FLAG
+} Flags;
+
+static FlagDescription FlagDescriptions [] {
+#define FUZZER_FLAG(Type, Name, Default, Description) {#Name, Description, Default, &Flags.Name},
+#include "FuzzerFlags.def"
+#undef FUZZER_FLAG
+};
+
+static const size_t kNumFlags =
+    sizeof(FlagDescriptions) / sizeof(FlagDescriptions[0]);
+
+static std::vector<std::string> inputs;
+static const char *ProgName;
+
+static void PrintHelp() {
+  std::cerr << "Usage: " << ProgName
+            << " [-flag1=val1 [-flag2=val2 ...] ] [dir1 [dir2 ...] ]\n";
+  std::cerr << "\nFlags: (strictly in form -flag=value)\n";
+  size_t MaxFlagLen = 0;
+  for (size_t F = 0; F < kNumFlags; F++)
+    MaxFlagLen = std::max(strlen(FlagDescriptions[F].Name), MaxFlagLen);
+
+  for (size_t F = 0; F < kNumFlags; F++) {
+    const auto &D = FlagDescriptions[F];
+    std::cerr << "  " << D.Name;
+    for (size_t i = 0, n = MaxFlagLen - strlen(D.Name); i < n; i++)
+      std::cerr << " ";
+    std::cerr << "\t";
+    std::cerr << D.Default << "\t" << D.Description << "\n";
+  }
+}
+
+static const char *FlagValue(const char *Param, const char *Name) {
+  size_t Len = strlen(Name);
+  if (Param[0] == '-' && strstr(Param + 1, Name) == Param + 1 &&
+      Param[Len + 1] == '=')
+      return &Param[Len + 2];
+  return nullptr;
+}
+
+static bool ParseOneFlag(const char *Param) {
+  if (Param[0] != '-') return false;
+  for (size_t F = 0; F < kNumFlags; F++) {
+    const char *Name = FlagDescriptions[F].Name;
+    const char *Str = FlagValue(Param, Name);
+    if (Str)  {
+      int Val = std::stol(Str);
+      *FlagDescriptions[F].Flag = Val;
+      if (Flags.verbosity >= 2)
+        std::cerr << "Flag: " << Name << " " << Val << "\n";
+      return true;
+    }
+  }
+  PrintHelp();
+  exit(1);
+}
+
+// We don't use any library to minimize dependencies.
+static void ParseFlags(int argc, char **argv) {
+  for (size_t F = 0; F < kNumFlags; F++)
+    *FlagDescriptions[F].Flag = FlagDescriptions[F].Default;
+  for (int A = 1; A < argc; A++) {
+    if (ParseOneFlag(argv[A])) continue;
+    inputs.push_back(argv[A]);
+  }
+}
+
+static void WorkerThread(const std::string &Cmd, std::atomic<int> *Counter,
+                        int NumJobs, std::atomic<bool> *HasErrors) {
+  static std::mutex CerrMutex;
+  while (true) {
+    int C = (*Counter)++;
+    if (C >= NumJobs) break;
+    std::string Log = "fuzz-" + std::to_string(C) + ".log";
+    std::string ToRun = Cmd + " > " + Log + " 2>&1\n";
+    if (Flags.verbosity)
+      std::cerr << ToRun;
+    int ExitCode = system(ToRun.c_str());
+    if (ExitCode != 0)
+      *HasErrors = true;
+    std::lock_guard<std::mutex> Lock(CerrMutex);
+    std::cerr << "================== Job " << C
+              << " exited with exit code " << ExitCode
+              << " =================\n";
+    fuzzer::CopyFileToErr(Log);
+  }
+}
+
+static int RunInMultipleProcesses(int argc, char **argv, int NumWorkers,
+                                  int NumJobs) {
+  std::atomic<int> Counter(0);
+  std::atomic<bool> HasErrors(false);
+  std::string Cmd;
+  for (int i = 0; i < argc; i++) {
+    if (FlagValue(argv[i], "jobs") || FlagValue(argv[i], "workers")) continue;
+    Cmd += argv[i];
+    Cmd += " ";
+  }
+  std::vector<std::thread> V;
+  for (int i = 0; i < NumWorkers; i++)
+    V.push_back(std::thread(WorkerThread, Cmd, &Counter, NumJobs, &HasErrors));
+  for (auto &T : V)
+    T.join();
+  return HasErrors ? 1 : 0;
+}
+
+int FuzzerDriver(int argc, char **argv, UserCallback Callback) {
+  using namespace fuzzer;
+
+  ProgName = argv[0];
+  ParseFlags(argc, argv);
+  if (Flags.help) {
+    PrintHelp();
+    return 0;
+  }
+
+  if (Flags.workers > 0 && Flags.jobs > 0)
+    return RunInMultipleProcesses(argc, argv, Flags.workers, Flags.jobs);
+
+  Fuzzer::FuzzingOptions Options;
+  Options.Verbosity = Flags.verbosity;
+  Options.MaxLen = Flags.max_len;
+  Options.DoCrossOver = Flags.cross_over;
+  Options.MutateDepth = Flags.mutate_depth;
+  Options.ExitOnFirst = Flags.exit_on_first;
+  Options.UseFullCoverageSet = Flags.use_full_coverage_set;
+  Options.UseCoveragePairs = Flags.use_coverage_pairs;
+  Options.PreferSmallDuringInitialShuffle =
+      Flags.prefer_small_during_initial_shuffle;
+  if (Flags.runs >= 0)
+    Options.MaxNumberOfRuns = Flags.runs;
+  if (!inputs.empty())
+    Options.OutputCorpus = inputs[0];
+  Fuzzer F(Callback, Options);
+
+  unsigned seed = Flags.seed;
+  // Initialize seed.
+  if (seed == 0)
+    seed = time(0) * 10000 + getpid();
+  if (Flags.verbosity)
+    std::cerr << "Seed: " << seed << "\n";
+  srand(seed);
+
+  // Timer
+  if (Flags.timeout > 0)
+    SetTimer(Flags.timeout);
+
+  for (auto &inp : inputs)
+    F.ReadDir(inp);
+
+  if (F.CorpusSize() == 0)
+    F.AddToCorpus(Unit());  // Can't fuzz empty corpus, so add an empty input.
+  F.ShuffleAndMinimize();
+  if (Flags.save_minimized_corpus)
+    F.SaveCorpus();
+  F.Loop(Flags.iterations < 0 ? INT_MAX : Flags.iterations);
+  if (Flags.verbosity)
+    std::cerr << "Done " << F.getTotalNumberOfRuns()
+              << " runs in " << F.secondsSinceProcessStartUp()
+              << " seconds\n";
+  return 0;
+}
+
+}  // namespace fuzzer
diff --git a/lib/Fuzzer/FuzzerFlags.def b/lib/Fuzzer/FuzzerFlags.def
new file mode 100644
index 0000000..068f245
--- /dev/null
+++ b/lib/Fuzzer/FuzzerFlags.def
@@ -0,0 +1,45 @@
+//===- FuzzerFlags.def - Run-time flags -------------------------*- C++ -* ===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Flags. FUZZER_FLAG macro should be defined at the point of inclusion.
+// We are not using any flag parsing library for better portability and
+// independence.
+//===----------------------------------------------------------------------===//
+FUZZER_FLAG(int, verbosity, 1, "Verbosity level.")
+FUZZER_FLAG(int, seed, 0, "Random seed. If 0, seed is generated.")
+FUZZER_FLAG(int, iterations, -1,
+            "Number of iterations of the fuzzer internal loop"
+            " (-1 for infinite iterations).")
+FUZZER_FLAG(int, runs, -1,
+            "Number of individual test runs (-1 for infinite runs).")
+FUZZER_FLAG(int, max_len, 64, "Maximal length of the test input.")
+FUZZER_FLAG(int, cross_over, 1, "If 1, cross over inputs.")
+FUZZER_FLAG(int, mutate_depth, 5,
+            "Apply this number of consecutive mutations to each input.")
+FUZZER_FLAG(
+    int, prefer_small_during_initial_shuffle, -1,
+    "If 1, always prefer smaller inputs during the initial corpus shuffle."
+    " If 0, never do that. If -1, do it sometimes.")
+FUZZER_FLAG(int, exit_on_first, 0,
+            "If 1, exit after the first new interesting input is found.")
+FUZZER_FLAG(int, timeout, -1, "Timeout in seconds (if positive).")
+FUZZER_FLAG(int, help, 0, "Print help.")
+FUZZER_FLAG(
+    int, save_minimized_corpus, 0,
+    "If 1, the minimized corpus is saved into the first input directory")
+FUZZER_FLAG(int, use_full_coverage_set, 0,
+            "Experimental: Maximize the number of different full"
+            " coverage sets as opposed to maximizing the total coverage."
+            " This is potentially MUCH slower, but may discover more paths.")
+FUZZER_FLAG(int, use_coverage_pairs, 0,
+            "Experimental: Maximize the number of different coverage pairs.")
+FUZZER_FLAG(int, jobs, 0, "Number of jobs to run. If jobs >= 1 we spawn"
+                          " this number of jobs in separate worker processes"
+                          " with stdout/stderr redirected to fuzz-JOB.log.")
+FUZZER_FLAG(int, workers, 0,
+            "Number of simultaneous worker processes to run the jobs.")
diff --git a/lib/Fuzzer/FuzzerIO.cpp b/lib/Fuzzer/FuzzerIO.cpp
new file mode 100644
index 0000000..224808c
--- /dev/null
+++ b/lib/Fuzzer/FuzzerIO.cpp
@@ -0,0 +1,57 @@
+//===- FuzzerIO.cpp - IO utils. -------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// IO functions.
+//===----------------------------------------------------------------------===//
+#include "FuzzerInternal.h"
+#include <iostream>
+#include <iterator>
+#include <fstream>
+#include <dirent.h>
+namespace fuzzer {
+
+static std::vector<std::string> ListFilesInDir(const std::string &Dir) {
+  std::vector<std::string> V;
+  DIR *D = opendir(Dir.c_str());
+  if (!D) return V;
+  while (auto E = readdir(D)) {
+    if (E->d_type == DT_REG || E->d_type == DT_LNK)
+      V.push_back(E->d_name);
+  }
+  closedir(D);
+  return V;
+}
+
+Unit FileToVector(const std::string &Path) {
+  std::ifstream T(Path);
+  return Unit((std::istreambuf_iterator<char>(T)),
+              std::istreambuf_iterator<char>());
+}
+
+void CopyFileToErr(const std::string &Path) {
+  std::ifstream T(Path);
+  std::copy(std::istreambuf_iterator<char>(T), std::istreambuf_iterator<char>(),
+            std::ostream_iterator<char>(std::cerr, ""));
+}
+
+void WriteToFile(const Unit &U, const std::string &Path) {
+  std::ofstream OF(Path);
+  OF.write((const char*)U.data(), U.size());
+}
+
+void ReadDirToVectorOfUnits(const char *Path, std::vector<Unit> *V) {
+  for (auto &X : ListFilesInDir(Path))
+    V->push_back(FileToVector(DirPlusFile(Path, X)));
+}
+
+std::string DirPlusFile(const std::string &DirPath,
+                        const std::string &FileName) {
+  return DirPath + "/" + FileName;
+}
+
+}  // namespace fuzzer
diff --git a/lib/Fuzzer/FuzzerInterface.h b/lib/Fuzzer/FuzzerInterface.h
new file mode 100644
index 0000000..49d8c0f
--- /dev/null
+++ b/lib/Fuzzer/FuzzerInterface.h
@@ -0,0 +1,25 @@
+//===- FuzzerInterface.h - Interface 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.
+//
+//===----------------------------------------------------------------------===//
+// Define the interface between the Fuzzer and the library being tested.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_INTERFACE_H
+#define LLVM_FUZZER_INTERFACE_H
+
+#include <cstddef>
+#include <cstdint>
+
+namespace fuzzer {
+
+typedef void (*UserCallback)(const uint8_t *data, size_t size);
+int FuzzerDriver(int argc, char **argv, UserCallback Callback);
+
+}  // namespace fuzzer
+
+#endif  // LLVM_FUZZER_INTERFACE_H
diff --git a/lib/Fuzzer/FuzzerInternal.h b/lib/Fuzzer/FuzzerInternal.h
new file mode 100644
index 0000000..980b00e
--- /dev/null
+++ b/lib/Fuzzer/FuzzerInternal.h
@@ -0,0 +1,104 @@
+//===- FuzzerInternal.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.
+//
+//===----------------------------------------------------------------------===//
+// Define the main class fuzzer::Fuzzer and most functions.
+//===----------------------------------------------------------------------===//
+#include <cassert>
+#include <climits>
+#include <chrono>
+#include <cstddef>
+#include <cstdlib>
+#include <string>
+#include <vector>
+#include <unordered_set>
+
+#include "FuzzerInterface.h"
+
+namespace fuzzer {
+typedef std::vector<uint8_t> Unit;
+using namespace std::chrono;
+
+Unit ReadFile(const char *Path);
+void ReadDirToVectorOfUnits(const char *Path, std::vector<Unit> *V);
+void WriteToFile(const Unit &U, const std::string &Path);
+void CopyFileToErr(const std::string &Path);
+// Returns "Dir/FileName" or equivalent for the current OS.
+std::string DirPlusFile(const std::string &DirPath,
+                        const std::string &FileName);
+
+void Mutate(Unit *U, size_t MaxLen);
+
+void CrossOver(const Unit &A, const Unit &B, Unit *U, size_t MaxLen);
+
+void Print(const Unit &U, const char *PrintAfter = "");
+void PrintASCII(const Unit &U, const char *PrintAfter = "");
+std::string Hash(const Unit &U);
+void SetTimer(int Seconds);
+
+class Fuzzer {
+ public:
+  struct FuzzingOptions {
+    int Verbosity = 1;
+    int MaxLen = 0;
+    bool DoCrossOver = true;
+    int  MutateDepth = 5;
+    bool ExitOnFirst = false;
+    bool UseFullCoverageSet  = false;
+    bool UseCoveragePairs = false;
+    int PreferSmallDuringInitialShuffle = -1;
+    size_t MaxNumberOfRuns = ULONG_MAX;
+    std::string OutputCorpus;
+  };
+  Fuzzer(UserCallback Callback, FuzzingOptions Options)
+      : Callback(Callback), Options(Options) {
+    SetDeathCallback();
+  }
+  void AddToCorpus(const Unit &U) { Corpus.push_back(U); }
+  size_t Loop(size_t NumIterations);
+  void ShuffleAndMinimize();
+  size_t CorpusSize() const { return Corpus.size(); }
+  void ReadDir(const std::string &Path) {
+    ReadDirToVectorOfUnits(Path.c_str(), &Corpus);
+  }
+  // Save the current corpus to OutputCorpus.
+  void SaveCorpus();
+
+  size_t secondsSinceProcessStartUp() {
+    return duration_cast<seconds>(system_clock::now() - ProcessStartTime)
+        .count();
+  }
+
+  size_t getTotalNumberOfRuns() { return TotalNumberOfRuns; }
+
+  static void AlarmCallback();
+
+ private:
+  size_t MutateAndTestOne(Unit *U);
+  size_t RunOne(const Unit &U);
+  size_t RunOneMaximizeTotalCoverage(const Unit &U);
+  size_t RunOneMaximizeFullCoverageSet(const Unit &U);
+  size_t RunOneMaximizeCoveragePairs(const Unit &U);
+  void WriteToOutputCorpus(const Unit &U);
+  static void WriteToCrash(const Unit &U, const char *Prefix);
+
+  void SetDeathCallback();
+  static void DeathCallback();
+  static Unit CurrentUnit;
+
+  size_t TotalNumberOfRuns = 0;
+
+  std::vector<Unit> Corpus;
+  std::unordered_set<uintptr_t> FullCoverageSets;
+  std::unordered_set<uint64_t>  CoveragePairs;
+  UserCallback Callback;
+  FuzzingOptions Options;
+  system_clock::time_point ProcessStartTime = system_clock::now();
+  static system_clock::time_point UnitStartTime;
+};
+
+};  // namespace fuzzer
diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp
new file mode 100644
index 0000000..70b63eb
--- /dev/null
+++ b/lib/Fuzzer/FuzzerLoop.cpp
@@ -0,0 +1,233 @@
+//===- FuzzerLoop.cpp - Fuzzer's main loop --------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Fuzzer's main loop.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInternal.h"
+#include <sanitizer/coverage_interface.h>
+#include <algorithm>
+#include <iostream>
+
+namespace fuzzer {
+
+// static
+Unit Fuzzer::CurrentUnit;
+system_clock::time_point Fuzzer::UnitStartTime;
+
+void Fuzzer::SetDeathCallback() {
+  __sanitizer_set_death_callback(DeathCallback);
+}
+
+void Fuzzer::DeathCallback() {
+  std::cerr << "DEATH: " <<  std::endl;
+  Print(CurrentUnit, "\n");
+  PrintASCII(CurrentUnit, "\n");
+  WriteToCrash(CurrentUnit, "crash-");
+}
+
+void Fuzzer::AlarmCallback() {
+  size_t Seconds =
+      duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
+  std::cerr << "ALARM: working on the last Unit for " << Seconds << " seconds"
+            << std::endl;
+  if (Seconds >= 3) {
+    Print(CurrentUnit, "\n");
+    PrintASCII(CurrentUnit, "\n");
+    WriteToCrash(CurrentUnit, "timeout-");
+  }
+  exit(1);
+}
+
+void Fuzzer::ShuffleAndMinimize() {
+  bool PreferSmall =
+      (Options.PreferSmallDuringInitialShuffle == 1 ||
+       (Options.PreferSmallDuringInitialShuffle == -1 && rand() % 2));
+  if (Options.Verbosity)
+    std::cerr << "Shuffle: Size: " << Corpus.size()
+              << " prefer small: " << PreferSmall
+              << "\n";
+  std::vector<Unit> NewCorpus;
+  std::random_shuffle(Corpus.begin(), Corpus.end());
+  if (PreferSmall)
+    std::stable_sort(
+        Corpus.begin(), Corpus.end(),
+        [](const Unit &A, const Unit &B) { return A.size() < B.size(); });
+  size_t MaxCov = 0;
+  Unit &U = CurrentUnit;
+  for (const auto &C : Corpus) {
+    for (size_t First = 0; First < 1; First++) {
+      U.clear();
+      size_t Last = std::min(First + Options.MaxLen, C.size());
+      U.insert(U.begin(), C.begin() + First, C.begin() + Last);
+      size_t NewCoverage = RunOne(U);
+      if (NewCoverage) {
+        MaxCov = NewCoverage;
+        NewCorpus.push_back(U);
+        if (Options.Verbosity >= 2)
+          std::cerr << "NEW0: " << NewCoverage
+                    << " L " << U.size()
+                    << "\n";
+      }
+    }
+  }
+  Corpus = NewCorpus;
+  if (Options.Verbosity)
+    std::cerr << "Shuffle done: " << Corpus.size() << " IC: " << MaxCov << "\n";
+}
+
+size_t Fuzzer::RunOne(const Unit &U) {
+  UnitStartTime = system_clock::now();
+  TotalNumberOfRuns++;
+  if (Options.UseFullCoverageSet)
+    return RunOneMaximizeFullCoverageSet(U);
+  if (Options.UseCoveragePairs)
+    return RunOneMaximizeCoveragePairs(U);
+  return RunOneMaximizeTotalCoverage(U);
+}
+
+static uintptr_t HashOfArrayOfPCs(uintptr_t *PCs, uintptr_t NumPCs) {
+  uintptr_t Res = 0;
+  for (uintptr_t i = 0; i < NumPCs; i++) {
+    Res = (Res + PCs[i]) * 7;
+  }
+  return Res;
+}
+
+// Experimental. Does not yet scale.
+// Fuly reset the current coverage state, run a single unit,
+// collect all coverage pairs and return non-zero if a new pair is observed.
+size_t Fuzzer::RunOneMaximizeCoveragePairs(const Unit &U) {
+  __sanitizer_reset_coverage();
+  Callback(U.data(), U.size());
+  uintptr_t *PCs;
+  uintptr_t NumPCs = __sanitizer_get_coverage_guards(&PCs);
+  bool HasNewPairs = false;
+  for (uintptr_t i = 0; i < NumPCs; i++) {
+    if (!PCs[i]) continue;
+    for (uintptr_t j = 0; j < NumPCs; j++) {
+      if (!PCs[j]) continue;
+      uint64_t Pair = (i << 32) | j;
+      HasNewPairs |= CoveragePairs.insert(Pair).second;
+    }
+  }
+  if (HasNewPairs)
+    return CoveragePairs.size();
+  return 0;
+}
+
+// Experimental.
+// Fuly reset the current coverage state, run a single unit,
+// compute a hash function from the full coverage set,
+// return non-zero if the hash value is new.
+// This produces tons of new units and as is it's only suitable for small tests,
+// e.g. test/FullCoverageSetTest.cpp. FIXME: make it scale.
+size_t Fuzzer::RunOneMaximizeFullCoverageSet(const Unit &U) {
+  __sanitizer_reset_coverage();
+  Callback(U.data(), U.size());
+  uintptr_t *PCs;
+  uintptr_t NumPCs =__sanitizer_get_coverage_guards(&PCs);
+  if (FullCoverageSets.insert(HashOfArrayOfPCs(PCs, NumPCs)).second)
+    return FullCoverageSets.size();
+  return 0;
+}
+
+size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) {
+  size_t OldCoverage = __sanitizer_get_total_unique_coverage();
+  Callback(U.data(), U.size());
+  size_t NewCoverage = __sanitizer_get_total_unique_coverage();
+  if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) {
+    size_t Seconds = secondsSinceProcessStartUp();
+    std::cerr
+        << "#" << TotalNumberOfRuns
+        << "\tcov: " << NewCoverage
+        << "\texec/s: " << (Seconds ? TotalNumberOfRuns / Seconds : 0) << "\n";
+  }
+  if (NewCoverage > OldCoverage)
+    return NewCoverage;
+  return 0;
+}
+
+void Fuzzer::WriteToOutputCorpus(const Unit &U) {
+  if (Options.OutputCorpus.empty()) return;
+  std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
+  WriteToFile(U, Path);
+  if (Options.Verbosity >= 2)
+    std::cerr << "Written to " << Path << std::endl;
+}
+
+void Fuzzer::WriteToCrash(const Unit &U, const char *Prefix) {
+  std::string Path = Prefix + Hash(U);
+  WriteToFile(U, Path);
+  std::cerr << "CRASHED; file written to " << Path << std::endl;
+}
+
+void Fuzzer::SaveCorpus() {
+  if (Options.OutputCorpus.empty()) return;
+  for (const auto &U : Corpus)
+    WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
+  if (Options.Verbosity)
+    std::cerr << "Written corpus of " << Corpus.size() << " files to "
+              << Options.OutputCorpus << "\n";
+}
+
+size_t Fuzzer::MutateAndTestOne(Unit *U) {
+  size_t NewUnits = 0;
+  for (int i = 0; i < Options.MutateDepth; i++) {
+    if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
+      return NewUnits;
+    Mutate(U, Options.MaxLen);
+    size_t NewCoverage = RunOne(*U);
+    if (NewCoverage) {
+      Corpus.push_back(*U);
+      NewUnits++;
+      if (Options.Verbosity) {
+        std::cerr << "#" << TotalNumberOfRuns
+                  << "\tNEW: " << NewCoverage
+                  << " L: " << U->size()
+                  << " S: " << Corpus.size()
+                  << " I: " << i
+                  << "\t";
+        if (U->size() < 30) {
+          PrintASCII(*U);
+          std::cerr << "\t";
+          Print(*U);
+        }
+        std::cerr << "\n";
+      }
+      WriteToOutputCorpus(*U);
+      if (Options.ExitOnFirst)
+        exit(0);
+    }
+  }
+  return NewUnits;
+}
+
+size_t Fuzzer::Loop(size_t NumIterations) {
+  size_t NewUnits = 0;
+  for (size_t i = 1; i <= NumIterations; i++) {
+    for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
+      if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
+        return NewUnits;
+      // First, simply mutate the unit w/o doing crosses.
+      CurrentUnit = Corpus[J1];
+      NewUnits += MutateAndTestOne(&CurrentUnit);
+      // Now, cross with others.
+      if (Options.DoCrossOver) {
+        for (size_t J2 = 0; J2 < Corpus.size(); J2++) {
+          CurrentUnit.clear();
+          CrossOver(Corpus[J1], Corpus[J2], &CurrentUnit, Options.MaxLen);
+          NewUnits += MutateAndTestOne(&CurrentUnit);
+        }
+      }
+    }
+  }
+  return NewUnits;
+}
+
+}  // namespace fuzzer
diff --git a/lib/Fuzzer/FuzzerMain.cpp b/lib/Fuzzer/FuzzerMain.cpp
new file mode 100644
index 0000000..d0c3df3
--- /dev/null
+++ b/lib/Fuzzer/FuzzerMain.cpp
@@ -0,0 +1,20 @@
+//===- FuzzerMain.cpp - main() function and flags -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// main() and flags.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInterface.h"
+#include "FuzzerInternal.h"
+
+// This function should be defined by the user.
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size);
+
+int main(int argc, char **argv) {
+  return fuzzer::FuzzerDriver(argc, argv, TestOneInput);
+}
diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp
new file mode 100644
index 0000000..b28264a
--- /dev/null
+++ b/lib/Fuzzer/FuzzerMutate.cpp
@@ -0,0 +1,70 @@
+//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Mutate a test input.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInternal.h"
+
+namespace fuzzer {
+
+static char FlipRandomBit(char X) {
+  int Bit = rand() % 8;
+  char Mask = 1 << Bit;
+  char R;
+  if (X & (1 << Bit))
+    R = X & ~Mask;
+  else
+    R = X | Mask;
+  assert(R != X);
+  return R;
+}
+
+static char RandCh() {
+  if (rand() % 2) return rand();
+  const char *Special = "!*'();:@&=+$,/?%#[]123ABCxyz-`~.";
+  return Special[rand() % (sizeof(Special) - 1)];
+}
+
+// Mutate U in place.
+void Mutate(Unit *U, size_t MaxLen) {
+  assert(MaxLen > 0);
+  assert(U->size() <= MaxLen);
+  if (U->empty()) {
+    for (size_t i = 0; i < MaxLen; i++)
+      U->push_back(RandCh());
+    return;
+  }
+  assert(!U->empty());
+  switch (rand() % 3) {
+  case 0:
+    if (U->size() > 1) {
+      U->erase(U->begin() + rand() % U->size());
+      break;
+    }
+    [[clang::fallthrough]];
+  case 1:
+    if (U->size() < MaxLen) {
+      U->insert(U->begin() + rand() % U->size(), RandCh());
+    } else { // At MaxLen.
+      uint8_t Ch = RandCh();
+      size_t Idx = rand() % U->size();
+      (*U)[Idx] = Ch;
+    }
+    break;
+  default:
+    {
+      size_t Idx = rand() % U->size();
+      (*U)[Idx] = FlipRandomBit((*U)[Idx]);
+    }
+    break;
+  }
+  assert(!U->empty());
+}
+
+}  // namespace fuzzer
diff --git a/lib/Fuzzer/FuzzerSanitizerOptions.cpp b/lib/Fuzzer/FuzzerSanitizerOptions.cpp
new file mode 100644
index 0000000..1c58f3a
--- /dev/null
+++ b/lib/Fuzzer/FuzzerSanitizerOptions.cpp
@@ -0,0 +1,18 @@
+//===- FuzzerSanitizerOptions.cpp - default flags for sanitizers ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Set default options for sanitizers while running the fuzzer.
+// Options reside in a separate file, so if we don't want to set the default
+// options we simply do not link this file in.
+// ASAN options:
+//   * don't dump the coverage to disk.
+//   * enable coverage by default.
+//===----------------------------------------------------------------------===//
+extern "C" const char *__asan_default_options() {
+  return "coverage_pcs=0:coverage=1";
+}
diff --git a/lib/Fuzzer/FuzzerUtil.cpp b/lib/Fuzzer/FuzzerUtil.cpp
new file mode 100644
index 0000000..679f289
--- /dev/null
+++ b/lib/Fuzzer/FuzzerUtil.cpp
@@ -0,0 +1,61 @@
+//===- FuzzerUtil.cpp - Misc utils ----------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Misc utils.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInternal.h"
+#include <iostream>
+#include <sys/time.h>
+#include <cassert>
+#include <cstring>
+#include <signal.h>
+
+namespace fuzzer {
+
+void Print(const Unit &v, const char *PrintAfter) {
+  std::cerr << v.size() << ": ";
+  for (auto x : v)
+    std::cerr << (unsigned) x << " ";
+  std::cerr << PrintAfter;
+}
+
+void PrintASCII(const Unit &U, const char *PrintAfter) {
+  for (auto X : U)
+    std::cerr << (char)((isascii(X) && X >= ' ') ? X : '?');
+  std::cerr << PrintAfter;
+}
+
+std::string Hash(const Unit &in) {
+  size_t h1 = 0, h2 = 0;
+  for (auto x : in) {
+    h1 += x;
+    h1 *= 5;
+    h2 += x;
+    h2 *= 7;
+  }
+  return std::to_string(h1) + std::to_string(h2);
+}
+
+static void AlarmHandler(int, siginfo_t *, void *) {
+  Fuzzer::AlarmCallback();
+}
+
+void SetTimer(int Seconds) {
+  struct itimerval T {{Seconds, 0}, {Seconds, 0}};
+  std::cerr << "SetTimer " << Seconds << "\n";
+  int Res = setitimer(ITIMER_REAL, &T, nullptr);
+  assert(Res == 0);
+  struct sigaction sigact;
+  memset(&sigact, 0, sizeof(sigact));
+  sigact.sa_sigaction = AlarmHandler;
+  Res = sigaction(SIGALRM, &sigact, 0);
+  assert(Res == 0);
+}
+
+}  // namespace fuzzer
diff --git a/lib/Fuzzer/README.txt b/lib/Fuzzer/README.txt
new file mode 100644
index 0000000..e4d6b4f
--- /dev/null
+++ b/lib/Fuzzer/README.txt
@@ -0,0 +1,112 @@
+===============================
+Fuzzer -- a library for coverage-guided fuzz testing.
+===============================
+
+This library is intended primarily for in-process coverage-guided fuzz testing
+(fuzzing) of other libraries. The typical workflow looks like this:
+
+  * Build the Fuzzer library as a static archive (or just a set of .o files).
+    Note that the Fuzzer contains the main() function.
+    Preferably do *not* use sanitizers while building the Fuzzer.
+  * Build the library you are going to test with -fsanitize-coverage=[234]
+    and one of the sanitizers. We recommend to build the library in several
+    different modes (e.g. asan, msan, lsan, ubsan, etc) and even using different
+    optimizations options (e.g. -O0, -O1, -O2) to diversify testing.
+  * Build a test driver using the same options as the library.
+    The test driver is a C/C++ file containing interesting calls to the library
+    inside a single function:
+    extern "C" void TestOneInput(const uint8_t *Data, size_t Size);
+  * Link the Fuzzer, the library and the driver together into an executable
+    using the same sanitizer options as for the library.
+  * Collect the initial corpus of inputs for the
+    fuzzer (a directory with test inputs, one file per input).
+    The better your inputs are the faster you will find something interesting.
+    Also try to keep your inputs small, otherwise the Fuzzer will run too slow.
+  * Run the fuzzer with the test corpus. As new interesting test cases are
+    discovered they will be added to the corpus. If a bug is discovered by
+    the sanitizer (asan, etc) it will be reported as usual and the reproducer
+    will be written to disk.
+    Each Fuzzer process is single-threaded (unless the library starts its own
+    threads). You can run the Fuzzer on the same corpus in multiple processes.
+    in parallel. For run-time options run the Fuzzer binary with '-help=1'.
+
+
+The Fuzzer is similar in concept to AFL (http://lcamtuf.coredump.cx/afl/),
+but uses in-process Fuzzing, which is more fragile, more restrictive, but
+potentially much faster as it has no overhead for process start-up.
+It uses LLVM's "Sanitizer Coverage" instrumentation to get in-process
+coverage-feedback https://code.google.com/p/address-sanitizer/wiki/AsanCoverage
+
+The code resides in the LLVM repository and is (or will be) used by various
+parts of LLVM, but the Fuzzer itself does not (and should not) depend on any
+part of LLVM and can be used for other projects. Ideally, the Fuzzer's code
+should not have any external dependencies. Right now it uses STL, which may need
+to be fixed later. See also F.A.Q. below.
+
+Examples of usage in LLVM:
+  * clang-format-fuzzer. The inputs are random pieces of C++-like text.
+  * Build (make sure to use fresh clang as the host compiler):
+    cmake -GNinja  -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ \
+    -DLLVM_USE_SANITIZER=Address -DLLVM_USE_SANITIZE_COVERAGE=YES \
+    /path/to/llvm -DCMAKE_BUILD_TYPE=Release
+    ninja clang-format-fuzzer
+  * Optionally build other kinds of binaries (asan+Debug, msan, ubsan, etc)
+  * TODO: commit the pre-fuzzed corpus to svn (?).
+  * Run:
+      clang-format-fuzzer CORPUS_DIR
+
+Toy example (see SimpleTest.cpp):
+a simple function that does something interesting if it receives bytes "Hi!".
+  # Build the Fuzzer with asan:
+  % clang++ -std=c++11 -fsanitize=address -fsanitize-coverage=3 -O1 -g \
+     Fuzzer*.cpp test/SimpleTest.cpp
+  # Run the fuzzer with no corpus (assuming on empty input)
+  % ./a.out
+
+===============================================================================
+F.A.Q.
+
+Q. Why Fuzzer does not use any of the LLVM support?
+A. There are two reasons.
+First, we want this library to be used outside of the LLVM w/o users having to
+build the rest of LLVM. This may sound unconvincing for many LLVM folks,
+but in practice the need for building the whole LLVM frightens many potential
+users -- and we want more users to use this code.
+Second, there is a subtle technical reason not to rely on the rest of LLVM, or
+any other large body of code (maybe not even STL). When coverage instrumentation
+is enabled, it will also instrument the LLVM support code which will blow up the
+coverage set of the process (since the fuzzer is in-process). In other words, by
+using more external dependencies we will slow down the fuzzer while the main
+reason for it to exist is extreme speed.
+
+Q. What about Windows then? The Fuzzer contains code that does not build on
+Windows.
+A. The sanitizer coverage support does not work on Windows either as of 01/2015.
+Once it's there, we'll need to re-implement OS-specific parts (I/O, signals).
+
+Q. When this Fuzzer is not a good solution for a problem?
+A.
+  * If the test inputs are validated by the target library and the validator
+    asserts/crashes on invalid inputs, the in-process fuzzer is not applicable
+    (we could use fork() w/o exec, but it comes with extra overhead).
+  * Bugs in the target library may accumulate w/o being detected. E.g. a memory
+    corruption that goes undetected at first and then leads to a crash while
+    testing another input. This is why it is highly recommended to run this
+    in-process fuzzer with all sanitizers to detect most bugs on the spot.
+  * It is harder to protect the in-process fuzzer from excessive memory
+    consumption and infinite loops in the target library (still possible).
+  * The target library should not have significant global state that is not
+    reset between the runs.
+  * Many interesting target libs are not designed in a way that supports
+    the in-process fuzzer interface (e.g. require a file path instead of a
+    byte array).
+  * If a single test run takes a considerable fraction of a second (or
+    more) the speed benefit from the in-process fuzzer is negligible.
+  * If the target library runs persistent threads (that outlive
+    execution of one test) the fuzzing results will be unreliable.
+
+Q. So, what exactly this Fuzzer is good for?
+A. This Fuzzer might be a good choice for testing libraries that have relatively
+small inputs, each input takes < 1ms to run, and the library code is not expected
+to crash on invalid inputs.
+Examples: regular expression matchers, text or binary format parsers.
diff --git a/lib/Fuzzer/test/CMakeLists.txt b/lib/Fuzzer/test/CMakeLists.txt
new file mode 100644
index 0000000..bed9cd8
--- /dev/null
+++ b/lib/Fuzzer/test/CMakeLists.txt
@@ -0,0 +1,61 @@
+# Build all these tests with -O0, otherwise optimizations may merge some
+# basic blocks and we'll fail to discover the targets.
+# Also enable the coverage instrumentation back (it is disabled
+# for the Fuzzer lib)
+set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O0 -fsanitize-coverage=4")
+
+set(Tests
+  FourIndependentBranchesTest
+  FullCoverageSetTest
+  InfiniteTest
+  NullDerefTest
+  SimpleTest
+  TimeoutTest
+  )
+
+set(TestBinaries)
+
+foreach(Test ${Tests})
+  add_executable(LLVMFuzzer-${Test}
+    EXCLUDE_FROM_ALL
+    ${Test}.cpp
+    )
+  target_link_libraries(LLVMFuzzer-${Test}
+    LLVMFuzzer
+    )
+  set(TestBinaries ${TestBinaries} LLVMFuzzer-${Test})
+endforeach()
+
+configure_lit_site_cfg(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.in
+  ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg
+  )
+
+configure_lit_site_cfg(
+  ${CMAKE_CURRENT_SOURCE_DIR}/unit/lit.site.cfg.in
+  ${CMAKE_CURRENT_BINARY_DIR}/unit/lit.site.cfg
+  )
+
+include_directories(..)
+include_directories(${LLVM_MAIN_SRC_DIR}/utils/unittest/googletest/include)
+
+add_executable(LLVMFuzzer-Unittest
+  FuzzerUnittest.cpp
+  $<TARGET_OBJECTS:LLVMFuzzerNoMain>
+  )
+
+target_link_libraries(LLVMFuzzer-Unittest
+  gtest
+  gtest_main
+  )
+
+set(TestBinaries ${TestBinaries} LLVMFuzzer-Unittest)
+
+set_target_properties(${TestBinaries}
+  PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+  )
+
+add_lit_testsuite(check-fuzzer "Running Fuzzer tests"
+    ${CMAKE_CURRENT_BINARY_DIR}
+    DEPENDS ${TestBinaries} FileCheck not
+    )
diff --git a/lib/Fuzzer/test/FourIndependentBranchesTest.cpp b/lib/Fuzzer/test/FourIndependentBranchesTest.cpp
new file mode 100644
index 0000000..171668b
--- /dev/null
+++ b/lib/Fuzzer/test/FourIndependentBranchesTest.cpp
@@ -0,0 +1,18 @@
+// Simple test for a fuzzer. The fuzzer must find the string "FUZZ".
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  int bits = 0;
+  if (Size > 0 && Data[0] == 'F') bits |= 1;
+  if (Size > 1 && Data[1] == 'U') bits |= 2;
+  if (Size > 2 && Data[2] == 'Z') bits |= 4;
+  if (Size > 3 && Data[3] == 'Z') bits |= 8;
+  if (bits == 15) {
+    std::cerr <<  "BINGO!\n";
+    exit(1);
+  }
+}
+
diff --git a/lib/Fuzzer/test/FullCoverageSetTest.cpp b/lib/Fuzzer/test/FullCoverageSetTest.cpp
new file mode 100644
index 0000000..d4f8c11
--- /dev/null
+++ b/lib/Fuzzer/test/FullCoverageSetTest.cpp
@@ -0,0 +1,20 @@
+// Simple test for a fuzzer. The fuzzer must find the string "FUZZER".
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  int bits = 0;
+  if (Size > 0 && Data[0] == 'F') bits |= 1;
+  if (Size > 1 && Data[1] == 'U') bits |= 2;
+  if (Size > 2 && Data[2] == 'Z') bits |= 4;
+  if (Size > 3 && Data[3] == 'Z') bits |= 8;
+  if (Size > 4 && Data[4] == 'E') bits |= 16;
+  if (Size > 5 && Data[5] == 'R') bits |= 32;
+  if (bits == 63) {
+    std::cerr <<  "BINGO!\n";
+    exit(1);
+  }
+}
+
diff --git a/lib/Fuzzer/test/FuzzerUnittest.cpp b/lib/Fuzzer/test/FuzzerUnittest.cpp
new file mode 100644
index 0000000..368a0f2
--- /dev/null
+++ b/lib/Fuzzer/test/FuzzerUnittest.cpp
@@ -0,0 +1,62 @@
+#include "FuzzerInternal.h"
+#include "gtest/gtest.h"
+#include <set>
+
+// For now, have TestOneInput just to make it link.
+// Later we may want to make unittests that actually call TestOneInput.
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  abort();
+}
+
+TEST(Fuzzer, CrossOver) {
+  using namespace fuzzer;
+  Unit A({0, 1, 2}), B({5, 6, 7});
+  Unit C;
+  Unit Expected[] = {
+       { 0 },
+       { 0, 1 },
+       { 0, 5 },
+       { 0, 1, 2 },
+       { 0, 1, 5 },
+       { 0, 5, 1 },
+       { 0, 5, 6 },
+       { 0, 1, 2, 5 },
+       { 0, 1, 5, 2 },
+       { 0, 1, 5, 6 },
+       { 0, 5, 1, 2 },
+       { 0, 5, 1, 6 },
+       { 0, 5, 6, 1 },
+       { 0, 5, 6, 7 },
+       { 0, 1, 2, 5, 6 },
+       { 0, 1, 5, 2, 6 },
+       { 0, 1, 5, 6, 2 },
+       { 0, 1, 5, 6, 7 },
+       { 0, 5, 1, 2, 6 },
+       { 0, 5, 1, 6, 2 },
+       { 0, 5, 1, 6, 7 },
+       { 0, 5, 6, 1, 2 },
+       { 0, 5, 6, 1, 7 },
+       { 0, 5, 6, 7, 1 },
+       { 0, 1, 2, 5, 6, 7 },
+       { 0, 1, 5, 2, 6, 7 },
+       { 0, 1, 5, 6, 2, 7 },
+       { 0, 1, 5, 6, 7, 2 },
+       { 0, 5, 1, 2, 6, 7 },
+       { 0, 5, 1, 6, 2, 7 },
+       { 0, 5, 1, 6, 7, 2 },
+       { 0, 5, 6, 1, 2, 7 },
+       { 0, 5, 6, 1, 7, 2 },
+       { 0, 5, 6, 7, 1, 2 }
+  };
+  for (size_t Len = 1; Len < 8; Len++) {
+    std::set<Unit> FoundUnits, ExpectedUnitsWitThisLength;
+    for (int Iter = 0; Iter < 3000; Iter++) {
+      CrossOver(A, B, &C, Len);
+      FoundUnits.insert(C);
+    }
+    for (const Unit &U : Expected)
+      if (U.size() <= Len)
+        ExpectedUnitsWitThisLength.insert(U);
+    EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits);
+  }
+}
diff --git a/lib/Fuzzer/test/InfiniteTest.cpp b/lib/Fuzzer/test/InfiniteTest.cpp
new file mode 100644
index 0000000..dcb3030
--- /dev/null
+++ b/lib/Fuzzer/test/InfiniteTest.cpp
@@ -0,0 +1,20 @@
+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+static volatile int Sink;
+
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size > 0 && Data[0] == 'H') {
+    Sink = 1;
+    if (Size > 1 && Data[1] == 'i') {
+      Sink = 2;
+      if (Size > 2 && Data[2] == '!') {
+        Sink = 2;
+      }
+    }
+  }
+}
+
diff --git a/lib/Fuzzer/test/NullDerefTest.cpp b/lib/Fuzzer/test/NullDerefTest.cpp
new file mode 100644
index 0000000..8811e38
--- /dev/null
+++ b/lib/Fuzzer/test/NullDerefTest.cpp
@@ -0,0 +1,22 @@
+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+static volatile int Sink;
+static volatile int *Null = 0;
+
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size > 0 && Data[0] == 'H') {
+    Sink = 1;
+    if (Size > 1 && Data[1] == 'i') {
+      Sink = 2;
+      if (Size > 2 && Data[2] == '!') {
+        std::cout << "Found the target, dereferencing NULL\n";
+        *Null = 1;
+      }
+    }
+  }
+}
+
diff --git a/lib/Fuzzer/test/SimpleTest.cpp b/lib/Fuzzer/test/SimpleTest.cpp
new file mode 100644
index 0000000..adb90ce
--- /dev/null
+++ b/lib/Fuzzer/test/SimpleTest.cpp
@@ -0,0 +1,21 @@
+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+static volatile int Sink;
+
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size > 0 && Data[0] == 'H') {
+    Sink = 1;
+    if (Size > 1 && Data[1] == 'i') {
+      Sink = 2;
+      if (Size > 2 && Data[2] == '!') {
+        std::cout << "Found the target, exiting\n";
+        exit(0);
+      }
+    }
+  }
+}
+
diff --git a/lib/Fuzzer/test/TimeoutTest.cpp b/lib/Fuzzer/test/TimeoutTest.cpp
new file mode 100644
index 0000000..23683ce
--- /dev/null
+++ b/lib/Fuzzer/test/TimeoutTest.cpp
@@ -0,0 +1,22 @@
+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#include <cstdint>
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+static volatile int Sink;
+
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size > 0 && Data[0] == 'H') {
+    Sink = 1;
+    if (Size > 1 && Data[1] == 'i') {
+      Sink = 2;
+      if (Size > 2 && Data[2] == '!') {
+        Sink = 2;
+        while (Sink)
+          ;
+      }
+    }
+  }
+}
+
diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test
new file mode 100644
index 0000000..1e42e72
--- /dev/null
+++ b/lib/Fuzzer/test/fuzzer.test
@@ -0,0 +1,19 @@
+RUN: ./LLVMFuzzer-SimpleTest 2>&1 | FileCheck %s --check-prefix=SimpleTest
+SimpleTest: Found the target, exiting
+
+RUN: not ./LLVMFuzzer-InfiniteTest -timeout=2 2>&1 | FileCheck %s --check-prefix=InfiniteTest
+InfiniteTest: ALARM: working on the last Unit for
+InfiniteTest-NOT: CRASHED; file written to timeout
+
+RUN: not ./LLVMFuzzer-TimeoutTest -timeout=5 2>&1 | FileCheck %s --check-prefix=TimeoutTest
+TimeoutTest: ALARM: working on the last Unit for
+TimeoutTest: CRASHED; file written to timeout
+
+RUN: not ./LLVMFuzzer-NullDerefTest 2>&1 | FileCheck %s --check-prefix=NullDerefTest
+NullDerefTest: CRASHED; file written to crash-
+
+RUN: not ./LLVMFuzzer-FullCoverageSetTest -timeout=15 -seed=1 -mutate_depth=2 -use_full_coverage_set=1 2>&1 | FileCheck %s --check-prefix=FullCoverageSetTest
+FullCoverageSetTest: BINGO
+
+RUN: not ./LLVMFuzzer-FourIndependentBranchesTest -timeout=15 -seed=1 -use_coverage_pairs=1 2>&1 | FileCheck %s --check-prefix=FourIndependentBranchesTest
+FourIndependentBranchesTest: BINGO
diff --git a/lib/Fuzzer/test/lit.cfg b/lib/Fuzzer/test/lit.cfg
new file mode 100644
index 0000000..834a16ae
--- /dev/null
+++ b/lib/Fuzzer/test/lit.cfg
@@ -0,0 +1,14 @@
+import lit.formats
+
+config.name = "LLVMFuzzer"
+config.test_format = lit.formats.ShTest(True)
+config.suffixes = ['.test']
+config.test_source_root = os.path.dirname(__file__)
+
+# Tweak PATH to include llvm tools dir.
+llvm_tools_dir = getattr(config, 'llvm_tools_dir', None)
+if (not llvm_tools_dir) or (not os.path.exists(llvm_tools_dir)):
+  lit_config.fatal("Invalid llvm_tools_dir config attribute: %r" % llvm_tools_dir)
+path = os.path.pathsep.join((llvm_tools_dir, config.environment['PATH']))
+config.environment['PATH'] = path
+
diff --git a/lib/Fuzzer/test/lit.site.cfg.in b/lib/Fuzzer/test/lit.site.cfg.in
new file mode 100644
index 0000000..e520db8
--- /dev/null
+++ b/lib/Fuzzer/test/lit.site.cfg.in
@@ -0,0 +1,3 @@
+config.test_exec_root = "@CMAKE_CURRENT_BINARY_DIR@"
+config.llvm_tools_dir = "@LLVM_TOOLS_DIR@"
+lit_config.load_config(config, "@CMAKE_CURRENT_SOURCE_DIR@/lit.cfg")
diff --git a/lib/Fuzzer/test/unit/lit.cfg b/lib/Fuzzer/test/unit/lit.cfg
new file mode 100644
index 0000000..0cc3193
--- /dev/null
+++ b/lib/Fuzzer/test/unit/lit.cfg
@@ -0,0 +1,7 @@
+import lit.formats
+
+config.name = "LLVMFuzzer-Unittest"
+print config.test_exec_root
+config.test_format = lit.formats.GoogleTest(".", "Unittest")
+config.suffixes = []
+config.test_source_root = config.test_exec_root
diff --git a/lib/Fuzzer/test/unit/lit.site.cfg.in b/lib/Fuzzer/test/unit/lit.site.cfg.in
new file mode 100644
index 0000000..114daf4
--- /dev/null
+++ b/lib/Fuzzer/test/unit/lit.site.cfg.in
@@ -0,0 +1,2 @@
+config.test_exec_root = "@CMAKE_CURRENT_BINARY_DIR@"
+lit_config.load_config(config, "@CMAKE_CURRENT_SOURCE_DIR@/unit/lit.cfg")