[libFuzzer] Add a command-line option for tracing mutation of corpus inputs in the dot graph format.

[dokyungs]

Summary

This patch adds a new command-line option -mutation_graph_file=FILE for
debugging purposes, which traces how corpus inputs evolve during a fuzzing
run. For each new input that is added to the corpus, a new vertex corresponding
to the added input, as well as a new edge that connects its base input to itself
are written to the given file. Each vertex is labeled with the filename of the
input, and each edge is labeled with the mutation sequence that led to the input
w.r.t. its base input.

The format of the mutation graph file is the dot file format. Once prepended and
appended with "graph {" and "}", respectively, the graph becomes a valid dot
file and can be visualized.

[hctim]

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

473

Isn't std::string a more appropriate type here? We're not creating a Unit to dump, we're creating a string vertex to dump.

475

In the cases where we have a base input, we don't need to create a blank vertex, right? So shouldn't this be conditional based on not having a base input?

477

why the "V" prefixes (is there something like having a decimal at the start of the name invalid?)

if so, can we escape with quotes instead?

478

nit - instead of using operator+ inside of append, break each concatenation into its own append (and same elsewhere).

Especially for more-than-two strings being appended each time, creating the temporary is expensive: https://quick-bench.com/q/wHhQi64BxEKJyv2m08OzQ1Yzy9g

(i.e. a + b + c requires a temporary to store the result of a + b, which can be expensive)

480–482

U += newVertex; ?

492–494

same here, U += newEdge?

compiler-rt/test/fuzzer/mutation-graph.test

11

Could you grab the vertex (perhaps the one that does the edge from H -> Hi) and explicitly enter the SHA's for that mutation here? Probably don't want to include the type of the mutation (in case that changes over time), but the testcase contents should be the same.

[dokyungs]

Addressed comments.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

473

Yes. std::string sounds much more appropriate. The patch now uses std::string.

475

BaseII being null means that II is seed input. So we should always create a vertex both for seed input and non-seed input, but we don't need any edge for the seed input. That's why the edge addition below is conditioned on BaseII.

477

Escaped with quotes.

478

Thanks for the benchmark! I changed every operator+ to .append.

492–494

I am appending to a single output string for both vertex and edge. How does it look now?

compiler-rt/test/fuzzer/mutation-graph.test

11

I am now grabbing two vertex * edge pairs. The test still doesn't check, however, from what input "H" and "Hi" was found, because there are many candidates (e.g., "H" -> "Hx" -> "Hi" or "H" -> "HHH" -> "Hi", etc.) if we give a random seed.

Still I give seed=1 here to avoid the cases where libFuzzer finds Hi in a single mutation, although it's very unlikely.

[hctim]

Mostly just some nits - other than that LGTM.

compiler-rt/lib/fuzzer/FuzzerFlags.def

91–92

"internal flag. Saves a graph (in DOT format) to mutation_graph_file. The graph contains a vertex for each input that has unique coverage; directed edges are provided between parents and children where the child has unique coverage, and are recorded with the type of mutation that caused the child."

compiler-rt/lib/fuzzer/FuzzerIO.cpp

86

Shouldn't mode "a" be sufficient here?

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

487–489

nit - collapse these "\" -> \""

491–492

nit - again collapse

[dokyungs]

Addressed comments.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerIO.cpp

86

Yes!

[morehouse]

This is a great patch, thank you DK!

compiler-rt/lib/fuzzer/FuzzerFlags.def

91

I think this is not an "internal flag", since it needs to be passed by the user.

compiler-rt/lib/fuzzer/FuzzerIO.cpp

81

s/c_str/data

[dokyungs]

Addressed comments.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerFlags.def

91

Removed. Thanks!

compiler-rt/lib/fuzzer/FuzzerIO.cpp

81

Done.

[hctim]

LGTM

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
   if (Flags.focus_function)
     Options.FocusFunction = Flags.focus_function;
   if (Flags.data_flow_trace)
     Options.DataFlowTrace = Flags.data_flow_trace;
   if (Flags.features_dir) {
     Options.FeaturesDir = Flags.features_dir;
     ValidateDirectoryExists(Options.FeaturesDir, Flags.create_missing_dirs);
   }
+  if (Flags.mutation_graph_file)
+    Options.MutationGraphFile = Flags.mutation_graph_file;
   if (Flags.collect_data_flow)
     Options.CollectDataFlow = Flags.collect_data_flow;
   if (Flags.stop_file)
     Options.StopFile = Flags.stop_file;
   Options.Entropic = Flags.entropic;
   Options.EntropicFeatureFrequencyThreshold =
       (size_t)Flags.entropic_feature_frequency_threshold;
   Options.EntropicNumberOfRarestFeatures =

compiler-rt/lib/fuzzer/FuzzerFlags.def

FUZZER_FLAG_INT(cleanse_crash, 0, "If 1, tries to cleanse the provided"
   " crash input to make it contain fewer original bytes."
   " Use with -exact_artifact_path to specify the output."
   )
 FUZZER_FLAG_INT(minimize_crash_internal_step, 0, "internal flag")
 FUZZER_FLAG_STRING(features_dir, "internal flag. Used to dump feature sets on disk."
   "Every time a new input is added to the corpus, a corresponding file in the features_dir"
   " is created containing the unique features of that input."
   " Features are stored in binary format.")
+FUZZER_FLAG_STRING(mutation_graph_file, "internal flag. Used to dump"
+  " a corpus mutation graph on disk.")
 FUZZER_FLAG_INT(use_counters, 1, "Use coverage counters")
 FUZZER_FLAG_INT(use_memmem, 1,
                 "Use hints from intercepting memmem, strstr, etc")
 FUZZER_FLAG_INT(use_value_profile, 0,
                 "Experimental. Use value profile to guide fuzzing.")
 FUZZER_FLAG_INT(use_cmp, 1, "Use CMP traces to guide mutations")
 FUZZER_FLAG_INT(shrink, 0, "Experimental. Try to shrink corpus inputs.")
 FUZZER_FLAG_INT(reduce_inputs, 1,

compiler-rt/lib/fuzzer/FuzzerIO.h

 
 void CopyFileToErr(const std::string &Path);
 
 void WriteToFile(const uint8_t *Data, size_t Size, const std::string &Path);
 // Write Data.c_str() to the file without terminating null character.
 void WriteToFile(const std::string &Data, const std::string &Path);
 void WriteToFile(const Unit &U, const std::string &Path);
 
+void AppendToFile(const uint8_t *Data, size_t Size, const std::string &Path);
+void AppendToFile(const std::string &Data, const std::string &Path);
+
 void ReadDirToVectorOfUnits(const char *Path, Vector<Unit> *V,
                             long *Epoch, size_t MaxSize, bool ExitOnError);
 
 // Returns "Dir/FileName" or equivalent for the current OS.
 std::string DirPlusFile(const std::string &DirPath,
                         const std::string &FileName);
 
 // Returns the name of the dir, similar to the 'dirname' utility.

compiler-rt/lib/fuzzer/FuzzerIO.cpp

 void WriteToFile(const uint8_t *Data, size_t Size, const std::string &Path) {
   // Use raw C interface because this function may be called from a sig handler.
   FILE *Out = fopen(Path.c_str(), "wb");
   if (!Out) return;
   fwrite(Data, sizeof(Data[0]), Size, Out);
   fclose(Out);
 }
 
+void AppendToFile(const std::string &Data, const std::string &Path) {
+  AppendToFile(reinterpret_cast<const uint8_t *>(Data.c_str()), Data.size(),
+               Path);
+}
+
+void AppendToFile(const uint8_t *Data, size_t Size, const std::string &Path) {
+  FILE *Out = fopen(Path.c_str(), "a+");
+  if (!Out)
+    return;
+  fwrite(Data, sizeof(Data[0]), Size, Out);
+  fclose(Out);
+}
+
 void ReadDirToVectorOfUnits(const char *Path, Vector<Unit> *V,
                             long *Epoch, size_t MaxSize, bool ExitOnError) {
   long E = Epoch ? *Epoch : 0;
   Vector<std::string> Files;
   ListFilesInDirRecursive(Path, Epoch, &Files, /*TopDir*/true);
   size_t NumLoaded = 0;
   for (size_t i = 0; i < Files.size(); i++) {
     auto &X = Files[i];

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

 static void RenameFeatureSetFile(const std::string &FeaturesDir,
                                  const std::string &OldFile,
                                  const std::string &NewFile) {
   if (FeaturesDir.empty()) return;
   RenameFile(DirPlusFile(FeaturesDir, OldFile),
              DirPlusFile(FeaturesDir, NewFile));
 }
 
+static void WriteEdgeToMutationGraphFile(const std::string &MutationGraphFile,
+                                         const InputInfo *II,
+                                         const InputInfo *BaseII,
+                                         const std::string &MS) {
+  if (MutationGraphFile.empty())
+    return;
+
+  std::string Sha1 = Sha1ToString(II->Sha1);
+
+  std::string OutputString;
+
+  // Add a new vertex.
+  OutputString.append("\"");
+  OutputString.append(Sha1);
+  OutputString.append("\"\n");
+
+  // Add a new edge if there is base input.
+  if (BaseII) {
+    std::string BaseSha1 = Sha1ToString(BaseII->Sha1);
+    OutputString.append("\"");
+    OutputString.append(BaseSha1);
+    OutputString.append("\"");
+    OutputString.append(" -> ");
+    OutputString.append("\"");
+    OutputString.append(Sha1);
+    OutputString.append("\"");
+    OutputString.append(" [label=\"");
+    OutputString.append(MS);
+    OutputString.append("\"];\n");
+  }
+
+  AppendToFile(OutputString, MutationGraphFile);
+}
+
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                     InputInfo *II, bool ForceAddToCorpus,
                     bool *FoundUniqFeatures) {
   if (!Size)
     return false;
 
   ExecuteCallback(Data, Size);
   auto TimeOfUnit = duration_cast<microseconds>(UnitStopTime - UnitStartTime);
bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
   if (NumNewFeatures || ForceAddToCorpus) {
     TPC.UpdateObservedPCs();
     auto NewII =
         Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile,
                            TPC.ObservedFocusFunction(), ForceAddToCorpus,
                            TimeOfUnit, UniqFeatureSetTmp, DFT, II);
     WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1),
                           NewII->UniqFeatureSet);
+    WriteEdgeToMutationGraphFile(Options.MutationGraphFile, NewII, II,
+                                 MD.MutationSequence());
     return true;
   }
   if (II && FoundUniqFeaturesOfII &&
       II->DataFlowTraceForFocusFunction.empty() &&
       FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
       II->U.size() > Size) {
     auto OldFeaturesFile = Sha1ToString(II->Sha1);
     Corpus.Replace(II, {Data, Data + Size});

compiler-rt/lib/fuzzer/FuzzerMutate.h

 class MutationDispatcher {
 public:
   MutationDispatcher(Random &Rand, const FuzzingOptions &Options);
   ~MutationDispatcher() {}
   /// Indicate that we are about to start a new sequence of mutations.
   void StartMutationSequence();
   /// Print the current sequence of mutations.
   void PrintMutationSequence();
+  /// Return the current sequence of mutations.
+  std::string MutationSequence();
   /// Indicate that the current sequence of mutations was successful.
   void RecordSuccessfulMutationSequence();
   /// Mutates data by invoking user-provided mutator.
   size_t Mutate_Custom(uint8_t *Data, size_t Size, size_t MaxSize);
   /// Mutates data by invoking user-provided crossover.
   size_t Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
   /// Mutates data by shuffling bytes.
   size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize);

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

if (!CurrentDictionaryEntrySequence.empty()) {
     Printf(" DE: ");
     for (auto DE : CurrentDictionaryEntrySequence) {
       Printf("\"");
       PrintASCII(DE->GetW(), "\"-");
     }
   }
 }
 
+std::string MutationDispatcher::MutationSequence() {
+  std::string MS;
+  for (auto M : CurrentMutatorSequence) {
+    MS += M.Name;
+    MS += "-";
+  }
+  return MS;
+}
+
 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
   return MutateImpl(Data, Size, MaxSize, Mutators);
 }
 
 size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
                                          size_t MaxSize) {
   return MutateImpl(Data, Size, MaxSize, DefaultMutators);
 }

compiler-rt/lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   std::string ArtifactPrefix = "./";
   std::string ExactArtifactPath;
   std::string ExitOnSrcPos;
   std::string ExitOnItem;
   std::string FocusFunction;
   std::string DataFlowTrace;
   std::string CollectDataFlow;
   std::string FeaturesDir;
+  std::string MutationGraphFile;
   std::string StopFile;
   bool SaveArtifacts = true;
   bool PrintNEW = true; // Print a status line when new units are found;
   bool PrintNewCovPcs = false;
   int PrintNewCovFuncs = 0;
   bool PrintFinalStats = false;
   bool PrintCorpusStats = false;
   bool PrintCoverage = false;

compiler-rt/test/fuzzer/mutation-graph.test

+REQUIRES: linux, x86_64
+RUN: %cpp_compiler %S/SimpleTest.cpp -o %t-SimpleTest
+
+RUN: rm -rf %t-SimpleTestGraph
+
+RUN: not %run %t-SimpleTest -seed=1 -max_len=3 -mutation_graph_file=%t-SimpleTestGraph 2>&1 | FileCheck %s
+CHECK: BINGO
+
+RUN: cat %t-SimpleTestGraph | FileCheck %s --check-prefix=GRAPH
+
+# A vertex and edge that correspond to the discovery of "H"
+GRAPH: "7cf184f4c67ad58283ecb19349720b0cae756829"
+GRAPH: {{.*}} -> "7cf184f4c67ad58283ecb19349720b0cae756829" [label="{{.*}}"];
+
+# A vertex and edge that correspond to the discovery of "Hi"
+GRAPH: "94dd9e08c129c785f7f256e82fbe0a30e6d1ae40"
+GRAPH: {{.*}} -> "94dd9e08c129c785f7f256e82fbe0a30e6d1ae40" [label="{{.*}}"];