Add a Fuzzer library

[kcc]

Summary

A simple genetic in-process coverage-guided fuzz testing library.

I've used this fuzzer to test clang-format
(it found 12+ bugs, thanks djasper@ for the fixes!)
and it may also help us test other parts of LLVM.
So why not keep it in the LLVM repository?

I plan to add the cmake build rules later (in a separate patch, if that's ok)
and also add a clang-format-fuzzer target.

See README.txt for details.

[dblaikie]

It'd probably be good to have the build infrastructure go in with the source - having non-building/non-testing source in tree isn't terribly useful.

lib/Fuzzer/FuzzerIO.cpp

17

Dir could be StringRef here, maybe?

35

Path should be passed by const ref here?

lib/Fuzzer/FuzzerInternal.h

39

I suspect MSVC 2012 (2013? whatever our min support is) doesn't support non-static data member initializers.

53

StringPiece

63

StringPiece? Maybe?

lib/Fuzzer/FuzzerLoop.cpp

114

idiomatic != rather than <? And prefix increment rather than post increment?

(& maybe use a name like 'i' which I think is idiomatic LLVM for index variables - since this is an index, not an iterator)

(similar comments on lots of other loops)

lib/Fuzzer/FuzzerMain.cpp

26

StringRef (for both of these)?

61

Compute the bound once rather than on every iteration?

lib/Fuzzer/FuzzerMutate.cpp

35

pass U by reference?

39

Is this clang-format/LLVM's formatting for case? I would've expected the 'case' to be at the same level as the 'switch'.

lib/Fuzzer/FuzzerUtil.cpp

43

Could be marginally more efficient to use an ostringstream here to avoid two allocations? (Well, I guess they'll be short strings, etc... - so maybe not a problem)

[rnk]

Looks good. Specifically, it doesn't seem worth trying to get access to any of the LLVM helpers I would suggest due to the desire to remain isolated.

lib/Fuzzer/FuzzerFlags.h

1 ↗

(On Diff #18780)

LLVM typically uses a .def suffix for such repeated include files. Also, you can change the header comment to match.

[ygribov]

lib/Fuzzer/FuzzerFlags.h

16 ↗

(On Diff #18780)

I wonder if people will mostly be interested to run fuzzer until coverage keeps increasing.

lib/Fuzzer/FuzzerIO.cpp

20

Perhaps allow files as well?

lib/Fuzzer/FuzzerLoop.cpp

119

Just curious, have you considered making this a heap to explore the most covering units first?

lib/Fuzzer/FuzzerMain.cpp

71

You know the len so perhaps just do memcmp for both checks?

86

Extra ;

119

Perhaps add an option for this?

lib/Fuzzer/FuzzerMutate.cpp

35

Ditto for other places (CrossOver, MutateAndTestOne, etc.)?

lib/Fuzzer/FuzzerUtil.cpp

57

Don't you need SA_SIGINFO and perhaps SA_ONSTACK here?

[ygribov]

lib/Fuzzer/FuzzerMutate.cpp

37

These asserts are not very user-friendly, perhaps check for them in main() instead? Actually I wonder if MaxLen should be MaxSizeIncreasePercentage...

[kcc]

It'd probably be good to have the build infrastructure go in with the source - having non-building/non-testing source in tree isn't terribly useful.

I'll send the patch for cmake support later today (I already have it working, but would like to disentangle the two commits)

lib/Fuzzer/FuzzerFlags.h

1 ↗

(On Diff #18780)

done.

16 ↗

(On Diff #18780)

How do you know that coverage keeps increasing?
And generally, no. Even if the coverage is steady fuzzing is still interesting (it finds bugs :))

lib/Fuzzer/FuzzerIO.cpp

17

This lib should not have any external dependencies.

20

Maybe in next steps, or maybe not.
Allowing files trades (small) flexibility to (small) complexity.

35

done

lib/Fuzzer/FuzzerInternal.h

39

Grrrr. I'd prefer not to bother about old MSVC at this point...
The whole thing (even sanitizer coverage) does not work on windows yet.
And the fuzzer is a strictly tool for developers, they can use the newest MSVC.

lib/Fuzzer/FuzzerLoop.cpp

114

changed back to 'i'. the rest is bikesheding (?)

119

Sure, I wanted to add a suite minimizer here. (later)

lib/Fuzzer/FuzzerMain.cpp

61

done

71

will it make the code more readable?

86

done

119

Err. Maybe. need to see how this will be used.
If we can get away w/o extra options -- we should.

lib/Fuzzer/FuzzerMutate.cpp

37

Well, asserts are not for users, they are for developers.

MaxSizeIncreasePercentage is something to consider, yes.

39

reformatted.

lib/Fuzzer/FuzzerUtil.cpp

43

This is a very cold part of code.
Much better to keep things simple.
Also, I want to depend on STL less, not more.
I actually may need to get rid of all of STL later.

Reason: this fuzzer is in-process, so it will be testing other code that also uses STL in the same process,
i.e. it will receive coverage feedback from STL functions. We don't want to mix coverage data from the library under test and the fuzzer itself.

57

What for? For now all I need it to die on timeout.
I may need these later, sure.

[kcc]

addressed most of the comments

[kcc]

add cmake rules to build the Fuzzer lib.

[majnemer]

lib/Fuzzer/FuzzerIO.cpp

19

Could you instead use fs::directory_iterator so that this works on Windows too?

42

Perhaps use sys::path::get_separator() instead of hardcoding '/'

[kcc]

lib/Fuzzer/FuzzerIO.cpp

19

No. This lib has to be independent from the rest of LLVM.
Same below

[ygribov]

Well, asserts are not for users, they are for developers.

Still, you don't verify inputs in main() so user will face an assert if she passes invalid arguments.

How do you know that coverage keeps increasing?

Does not __sanitizer_get_total_unique_coverage tell you this?

And generally, no. Even if the coverage is steady fuzzing is still interesting (it finds bugs :))

Hm, interesting.

[kcc]

In D7184#114061, @ygribov wrote:

Well, asserts are not for users, they are for developers.

Still, you don't verify inputs in main() so user will face an assert if she passes invalid arguments.

The inputs are truncated in Fuzzer::ShuffleAndMinimize

If Mutate gets inputs of unexpected length this is a bug => assertion should fail.

How do you know that coverage keeps increasing?

Does not __sanitizer_get_total_unique_coverage tell you this?

Of course.
But how do you know that you are not going to discover new coverage after 100000000 iterations?
The only way you may be certain of that is if you've already covered *all* basic blocks. In practice this never happens.

And generally, no. Even if the coverage is steady fuzzing is still interesting (it finds bugs :))

Hm, interesting.

edge and bb coverage is a rather weak signal.
Even if you have a full edge coverage you still may find lots of funny stuff with simple mutations.

[rnk]

lgtm

lib/Fuzzer/CMakeLists.txt

1

Maybe this should be LLVMFuzzer to namespace it better? You're bypassing the add_llvm_library wrapper which will add this prefix.

lib/CMakeLists.txt

 add_subdirectory(Object)
 add_subdirectory(Option)
 add_subdirectory(DebugInfo)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(Target)
 add_subdirectory(AsmParser)
 add_subdirectory(LineEditor)
 add_subdirectory(ProfileData)
+add_subdirectory(Fuzzer)

lib/Fuzzer/CMakeLists.txt

+add_library(Fuzzer STATIC
+  EXCLUDE_FROM_ALL  # Do not build if you are not building fuzzers.
+  FuzzerCrossOver.cpp
+  FuzzerIO.cpp
+  FuzzerLoop.cpp
+  FuzzerMain.cpp
+  FuzzerMutate.cpp
+  FuzzerUtil.cpp
+  )

lib/Fuzzer/FuzzerCrossOver.cpp

+//===- 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"
+
+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

lib/Fuzzer/FuzzerFlags.def

+//===- 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 (-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, 10,
+            "Apply this number of consecutive mutations to each input.")
+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.")

lib/Fuzzer/FuzzerIO.cpp

+//===- 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 <fstream>
+#include <dirent.h>
+namespace fuzzer {
+
+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 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(std::string(Path) + "/" + X));
+}
+
+}  // namespace fuzzer

lib/Fuzzer/FuzzerInternal.h

+//===- 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 <chrono>
+#include <cstddef>
+#include <cstdlib>
+#include <string>
+#include <vector>
+
+namespace fuzzer {
+typedef std::vector<uint8_t> Unit;
+using namespace std::chrono;
+
+Unit ReadFile(const char *Path);
+std::vector<std::string> ListFilesInDir(const std::string &Dir);
+void ReadDirToVectorOfUnits(const char *Path, std::vector<Unit> *V);
+void WriteToFile(const Unit &U, const std::string &Path);
+
+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;
+    bool MutateDepth = 10;
+    bool ExitOnFirst = false;
+    std::string OutputCorpus;
+  };
+  Fuzzer(FuzzingOptions Options) : 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);
+  }
+
+  static void AlarmCallback();
+
+ private:
+  size_t MutateAndTestOne(Unit *U);
+  size_t RunOne(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;
+  FuzzingOptions Options;
+  system_clock::time_point ProcessStartTime = system_clock::now();
+  static system_clock::time_point UnitStartTime;
+};
+
+};  // namespace fuzzer

lib/Fuzzer/FuzzerLoop.cpp

+//===- 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/asan_interface.h>
+#include <algorithm>
+#include <string>
+#include <iostream>
+#include <stdlib.h>
+
+// This function should be defined by the user.
+extern "C" void TestOneInput(const uint8_t *Data, size_t Size);
+
+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 > 60) {
+    Print(CurrentUnit, "\n");
+    PrintASCII(CurrentUnit, "\n");
+    WriteToCrash(CurrentUnit, "timeout-");
+  }
+  abort();
+}
+
+void Fuzzer::ShuffleAndMinimize() {
+  if (Options.Verbosity)
+    std::cerr << "Shuffle: " << Corpus.size() << "\n";
+  std::vector<Unit> NewCorpus;
+  random_shuffle(Corpus.begin(), Corpus.end());
+  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 << "\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++;
+  size_t OldCoverage = __sanitizer_get_total_unique_coverage();
+  TestOneInput(U.data(), U.size());
+  size_t NewCoverage = __sanitizer_get_total_unique_coverage();
+  if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) {
+    size_t Seconds =
+        duration_cast<seconds>(system_clock::now() - ProcessStartTime).count();
+    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 = 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;
+}
+
+size_t Fuzzer::MutateAndTestOne(Unit *U) {
+  size_t NewUnits = 0;
+  for (size_t i = 0; i < Options.MutateDepth; i++) {
+    Mutate(U, Options.MaxLen);
+    if (U->empty()) continue;
+    size_t NewCoverage = RunOne(*U);
+    if (NewCoverage) {
+      Corpus.push_back(*U);
+      NewUnits++;
+      if (Options.Verbosity) {
+        std::cerr << "#" << TotalNumberOfRuns
+                  << "\tNEW: " << NewCoverage
+                  << " L: " << U->size()
+                  << "\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++) {
+    if (Options.DoCrossOver) {
+      for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
+        for (size_t J2 = 0; J2 < Corpus.size(); J2++) {
+          CurrentUnit.clear();
+          CrossOver(Corpus[J1], Corpus[J2], &CurrentUnit, Options.MaxLen);
+          NewUnits += MutateAndTestOne(&CurrentUnit);
+        }
+      }
+    } else {  // No CrossOver
+      for (size_t J = 0; J < Corpus.size(); J++) {
+        CurrentUnit = Corpus[J];
+        NewUnits += MutateAndTestOne(&CurrentUnit);
+      }
+    }
+  }
+  return NewUnits;
+}
+
+}  // namespace fuzzer

lib/Fuzzer/FuzzerMain.cpp

+//===- 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 "FuzzerInternal.h"
+
+#include <climits>
+#include <cstring>
+#include <unistd.h>
+#include <iostream>
+
+// ASAN options:
+//   * don't dump the coverage to disk.
+extern "C" const char* __asan_default_options() { return "coverage_pcs=0"; }
+
+// 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]);
+  }
+}
+
+int main(int argc, char **argv) {
+  using namespace fuzzer;
+
+  ProgName = argv[0];
+  ParseFlags(argc, argv);
+  if (Flags.help) {
+    PrintHelp();
+    return 0;
+  }
+  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;
+  if (!inputs.empty())
+    Options.OutputCorpus = inputs[0];
+  Fuzzer F(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();
+  F.Loop(Flags.iterations < 0 ? INT_MAX : Flags.iterations);
+  if (Flags.verbosity)
+    std::cerr << "Done\n";
+  return 1;
+}

lib/Fuzzer/FuzzerMutate.cpp

+//===- 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)];
+}
+
+void Mutate(Unit *U, size_t MaxLen) {
+  assert(MaxLen > 0);
+  assert(U->size() <= MaxLen);
+  switch (rand() % 3) {
+  case 0:
+    if (U->size())
+      U->erase(U->begin() + rand() % U->size());
+    break;
+  case 1:
+    if (U->empty()) {
+      U->push_back(RandCh());
+    } else 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:
+    if (!U->empty()) {
+      size_t idx = rand() % U->size();
+      (*U)[idx] = FlipRandomBit((*U)[idx]);
+    }
+    break;
+  }
+}
+
+}  // namespace fuzzer

lib/Fuzzer/FuzzerUtil.cpp

+//===- 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

lib/Fuzzer/README.txt

+===============================
+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.
+
+Examples of usage in LLVM:
+  * clang-format-fuzzer. The inputs are random pieces of C++-like text.
+  * TODO: add more
+
+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

lib/Fuzzer/test/ExactTest.cpp

+// Simple test for a fuzzer. The fuzzer must find the string "FUZZER".
+#include <cstdlib>
+#include <cstddef>
+#include <iostream>
+
+static volatile int Sink;
+
+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";
+    abort();
+  }
+}
+

lib/Fuzzer/test/InfiniteTest.cpp

+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#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] == '!') {
+        Size = 2;
+      }
+    }
+  }
+}
+

lib/Fuzzer/test/NullDerefTest.cpp

+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#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;
+      }
+    }
+  }
+}
+

lib/Fuzzer/test/SimpleTest.cpp

+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#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);
+      }
+    }
+  }
+}
+

lib/Fuzzer/test/TestFuzzerCrossOver.cpp

+#include "FuzzerInternal.h"
+
+int main() {
+  using namespace fuzzer;
+  Unit A({0, 1, 2, 3, 4}), B({5, 6, 7, 8, 9});
+  Unit C;
+  for (size_t Len = 1; Len < 15; Len++) {
+    for (int Iter = 0; Iter < 1000; Iter++) {
+      CrossOver(A, B, &C, Len);
+      Print(C);
+    }
+  }
+}

lib/Fuzzer/test/TimeoutTest.cpp

+// Simple test for a fuzzer. The fuzzer must find the string "Hi!".
+#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] == '!') {
+        Size = 2;
+        while (Sink)
+          ;
+      }
+    }
+  }
+}
+