contrib/compiler-rt/lib/fuzzer/FuzzerMerge.cpp

   1 //===- FuzzerMerge.cpp - merging corpora ----------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // Merging corpora.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "FuzzerCommand.h"
  13 #include "FuzzerMerge.h"
  14 #include "FuzzerIO.h"
  15 #include "FuzzerInternal.h"
  16 #include "FuzzerTracePC.h"
  17 #include "FuzzerUtil.h"
  18
  19 #include <fstream>
  20 #include <iterator>
  21 #include <set>
  22 #include <sstream>
  23
  24 namespace fuzzer {
  25
  26 bool Merger::Parse(const std::string &Str, bool ParseCoverage) {
  27   std::istringstream SS(Str);
  28   return Parse(SS, ParseCoverage);
  29 }
  30
  31 void Merger::ParseOrExit(std::istream &IS, bool ParseCoverage) {
  32   if (!Parse(IS, ParseCoverage)) {
  33     Printf("MERGE: failed to parse the control file (unexpected error)\n");
  34     exit(1);
  35   }
  36 }
  37
  38 // The control file example:
  39 //
  40 // 3 # The number of inputs
  41 // 1 # The number of inputs in the first corpus, <= the previous number
  42 // file0
  43 // file1
  44 // file2  # One file name per line.
  45 // STARTED 0 123  # FileID, file size
  46 // DONE 0 1 4 6 8  # FileID COV1 COV2 ...
  47 // STARTED 1 456  # If DONE is missing, the input crashed while processing.
  48 // STARTED 2 567
  49 // DONE 2 8 9
  50 bool Merger::Parse(std::istream &IS, bool ParseCoverage) {
  51   LastFailure.clear();
  52   std::string Line;
  53
  54   // Parse NumFiles.
  55   if (!std::getline(IS, Line, '\n')) return false;
  56   std::istringstream L1(Line);
  57   size_t NumFiles = 0;
  58   L1 >> NumFiles;
  59   if (NumFiles == 0 || NumFiles > 10000000) return false;
  60
  61   // Parse NumFilesInFirstCorpus.
  62   if (!std::getline(IS, Line, '\n')) return false;
  63   std::istringstream L2(Line);
  64   NumFilesInFirstCorpus = NumFiles + 1;
  65   L2 >> NumFilesInFirstCorpus;
  66   if (NumFilesInFirstCorpus > NumFiles) return false;
  67
  68   // Parse file names.
  69   Files.resize(NumFiles);
  70   for (size_t i = 0; i < NumFiles; i++)
  71     if (!std::getline(IS, Files[i].Name, '\n'))
  72       return false;
  73
  74   // Parse STARTED and DONE lines.
  75   size_t ExpectedStartMarker = 0;
  76   const size_t kInvalidStartMarker = -1;
  77   size_t LastSeenStartMarker = kInvalidStartMarker;
  78   Vector<uint32_t> TmpFeatures;
  79   while (std::getline(IS, Line, '\n')) {
  80     std::istringstream ISS1(Line);
  81     std::string Marker;
  82     size_t N;
  83     ISS1 >> Marker;
  84     ISS1 >> N;
  85     if (Marker == "STARTED") {
  86       // STARTED FILE_ID FILE_SIZE
  87       if (ExpectedStartMarker != N)
  88         return false;
  89       ISS1 >> Files[ExpectedStartMarker].Size;
  90       LastSeenStartMarker = ExpectedStartMarker;
  91       assert(ExpectedStartMarker < Files.size());
  92       ExpectedStartMarker++;
  93     } else if (Marker == "DONE") {
  94       // DONE FILE_ID COV1 COV2 COV3 ...
  95       size_t CurrentFileIdx = N;
  96       if (CurrentFileIdx != LastSeenStartMarker)
  97         return false;
  98       LastSeenStartMarker = kInvalidStartMarker;
  99       if (ParseCoverage) {
 100         TmpFeatures.clear();  // use a vector from outer scope to avoid resizes.
 101         while (ISS1 >> std::hex >> N)
 102           TmpFeatures.push_back(N);
 103         std::sort(TmpFeatures.begin(), TmpFeatures.end());
 104         Files[CurrentFileIdx].Features = TmpFeatures;
 105       }
 106     } else {
 107       return false;
 108     }
 109   }
 110   if (LastSeenStartMarker != kInvalidStartMarker)
 111     LastFailure = Files[LastSeenStartMarker].Name;
 112
 113   FirstNotProcessedFile = ExpectedStartMarker;
 114   return true;
 115 }
 116
 117 size_t Merger::ApproximateMemoryConsumption() const  {
 118   size_t Res = 0;
 119   for (const auto &F: Files)
 120     Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]);
 121   return Res;
 122 }
 123
 124 // Decides which files need to be merged (add thost to NewFiles).
 125 // Returns the number of new features added.
 126 size_t Merger::Merge(const Set<uint32_t> &InitialFeatures,
 127                      Vector<std::string> *NewFiles) {
 128   NewFiles->clear();
 129   assert(NumFilesInFirstCorpus <= Files.size());
 130   Set<uint32_t> AllFeatures(InitialFeatures);
 131
 132   // What features are in the initial corpus?
 133   for (size_t i = 0; i < NumFilesInFirstCorpus; i++) {
 134     auto &Cur = Files[i].Features;
 135     AllFeatures.insert(Cur.begin(), Cur.end());
 136   }
 137   size_t InitialNumFeatures = AllFeatures.size();
 138
 139   // Remove all features that we already know from all other inputs.
 140   for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
 141     auto &Cur = Files[i].Features;
 142     Vector<uint32_t> Tmp;
 143     std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(),
 144                         AllFeatures.end(), std::inserter(Tmp, Tmp.begin()));
 145     Cur.swap(Tmp);
 146   }
 147
 148   // Sort. Give preference to
 149   //   * smaller files
 150   //   * files with more features.
 151   std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(),
 152             [&](const MergeFileInfo &a, const MergeFileInfo &b) -> bool {
 153               if (a.Size != b.Size)
 154                 return a.Size < b.Size;
 155               return a.Features.size() > b.Features.size();
 156             });
 157
 158   // One greedy pass: add the file's features to AllFeatures.
 159   // If new features were added, add this file to NewFiles.
 160   for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
 161     auto &Cur = Files[i].Features;
 162     // Printf("%s -> sz %zd ft %zd\n", Files[i].Name.c_str(),
 163     //       Files[i].Size, Cur.size());
 164     size_t OldSize = AllFeatures.size();
 165     AllFeatures.insert(Cur.begin(), Cur.end());
 166     if (AllFeatures.size() > OldSize)
 167       NewFiles->push_back(Files[i].Name);
 168   }
 169   return AllFeatures.size() - InitialNumFeatures;
 170 }
 171
 172 void Merger::PrintSummary(std::ostream &OS) {
 173   for (auto &File : Files) {
 174     OS << std::hex;
 175     OS << File.Name << " size: " << File.Size << " features: ";
 176     for (auto Feature : File.Features)
 177       OS << " " << Feature;
 178     OS << "\n";
 179   }
 180 }
 181
 182 Set<uint32_t> Merger::AllFeatures() const {
 183   Set<uint32_t> S;
 184   for (auto &File : Files)
 185     S.insert(File.Features.begin(), File.Features.end());
 186   return S;
 187 }
 188
 189 Set<uint32_t> Merger::ParseSummary(std::istream &IS) {
 190   std::string Line, Tmp;
 191   Set<uint32_t> Res;
 192   while (std::getline(IS, Line, '\n')) {
 193     size_t N;
 194     std::istringstream ISS1(Line);
 195     ISS1 >> Tmp;  // Name
 196     ISS1 >> Tmp;  // size:
 197     assert(Tmp == "size:" && "Corrupt summary file");
 198     ISS1 >> std::hex;
 199     ISS1 >> N;    // File Size
 200     ISS1 >> Tmp;  // features:
 201     assert(Tmp == "features:" && "Corrupt summary file");
 202     while (ISS1 >> std::hex >> N)
 203       Res.insert(N);
 204   }
 205   return Res;
 206 }
 207
 208 // Inner process. May crash if the target crashes.
 209 void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath) {
 210   Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str());
 211   Merger M;
 212   std::ifstream IF(CFPath);
 213   M.ParseOrExit(IF, false);
 214   IF.close();
 215   if (!M.LastFailure.empty())
 216     Printf("MERGE-INNER: '%s' caused a failure at the previous merge step\n",
 217            M.LastFailure.c_str());
 218
 219   Printf("MERGE-INNER: %zd total files;"
 220          " %zd processed earlier; will process %zd files now\n",
 221          M.Files.size(), M.FirstNotProcessedFile,
 222          M.Files.size() - M.FirstNotProcessedFile);
 223
 224   std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app);
 225   Set<size_t> AllFeatures;
 226   for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {
 227     MaybeExitGracefully();
 228     auto U = FileToVector(M.Files[i].Name);
 229     if (U.size() > MaxInputLen) {
 230       U.resize(MaxInputLen);
 231       U.shrink_to_fit();
 232     }
 233     std::ostringstream StartedLine;
 234     // Write the pre-run marker.
 235     OF << "STARTED " << std::dec << i << " " << U.size() << "\n";
 236     OF.flush();  // Flush is important since Command::Execute may crash.
 237     // Run.
 238     TPC.ResetMaps();
 239     ExecuteCallback(U.data(), U.size());
 240     // Collect coverage. We are iterating over the files in this order:
 241     // * First, files in the initial corpus ordered by size, smallest first.
 242     // * Then, all other files, smallest first.
 243     // So it makes no sense to record all features for all files, instead we
 244     // only record features that were not seen before.
 245     Set<size_t> UniqFeatures;
 246     TPC.CollectFeatures([&](size_t Feature) {
 247       if (AllFeatures.insert(Feature).second)
 248         UniqFeatures.insert(Feature);
 249     });
 250     // Show stats.
 251     if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))
 252       PrintStats("pulse ");
 253     // Write the post-run marker and the coverage.
 254     OF << "DONE " << i;
 255     for (size_t F : UniqFeatures)
 256       OF << " " << std::hex << F;
 257     OF << "\n";
 258     OF.flush();
 259   }
 260 }
 261
 262 static void WriteNewControlFile(const std::string &CFPath,
 263                                 const Vector<SizedFile> &AllFiles,
 264                                 size_t NumFilesInFirstCorpus) {
 265   RemoveFile(CFPath);
 266   std::ofstream ControlFile(CFPath);
 267   ControlFile << AllFiles.size() << "\n";
 268   ControlFile << NumFilesInFirstCorpus << "\n";
 269   for (auto &SF: AllFiles)
 270     ControlFile << SF.File << "\n";
 271   if (!ControlFile) {
 272     Printf("MERGE-OUTER: failed to write to the control file: %s\n",
 273            CFPath.c_str());
 274     exit(1);
 275   }
 276 }
 277
 278 // Outer process. Does not call the target code and thus sohuld not fail.
 279 void Fuzzer::CrashResistantMerge(const Vector<std::string> &Args,
 280                                  const Vector<std::string> &Corpora,
 281                                  const char *CoverageSummaryInputPathOrNull,
 282                                  const char *CoverageSummaryOutputPathOrNull,
 283                                  const char *MergeControlFilePathOrNull) {
 284   if (Corpora.size() <= 1) {
 285     Printf("Merge requires two or more corpus dirs\n");
 286     return;
 287   }
 288   auto CFPath =
 289       MergeControlFilePathOrNull
 290           ? MergeControlFilePathOrNull
 291           : DirPlusFile(TmpDir(),
 292                         "libFuzzerTemp." + std::to_string(GetPid()) + ".txt");
 293
 294   size_t NumAttempts = 0;
 295   if (MergeControlFilePathOrNull && FileSize(MergeControlFilePathOrNull)) {
 296     Printf("MERGE-OUTER: non-empty control file provided: '%s'\n",
 297            MergeControlFilePathOrNull);
 298     Merger M;
 299     std::ifstream IF(MergeControlFilePathOrNull);
 300     if (M.Parse(IF, /*ParseCoverage=*/false)) {
 301       Printf("MERGE-OUTER: control file ok, %zd files total,"
 302              " first not processed file %zd\n",
 303              M.Files.size(), M.FirstNotProcessedFile);
 304       if (!M.LastFailure.empty())
 305         Printf("MERGE-OUTER: '%s' will be skipped as unlucky "
 306                "(merge has stumbled on it the last time)\n",
 307                M.LastFailure.c_str());
 308       if (M.FirstNotProcessedFile >= M.Files.size()) {
 309         Printf("MERGE-OUTER: nothing to do, merge has been completed before\n");
 310         exit(0);
 311       }
 312
 313       NumAttempts = M.Files.size() - M.FirstNotProcessedFile;
 314     } else {
 315       Printf("MERGE-OUTER: bad control file, will overwrite it\n");
 316     }
 317   }
 318
 319   if (!NumAttempts) {
 320     // The supplied control file is empty or bad, create a fresh one.
 321     Vector<SizedFile> AllFiles;
 322     GetSizedFilesFromDir(Corpora[0], &AllFiles);
 323     size_t NumFilesInFirstCorpus = AllFiles.size();
 324     std::sort(AllFiles.begin(), AllFiles.end());
 325     for (size_t i = 1; i < Corpora.size(); i++)
 326       GetSizedFilesFromDir(Corpora[i], &AllFiles);
 327     std::sort(AllFiles.begin() + NumFilesInFirstCorpus, AllFiles.end());
 328     Printf("MERGE-OUTER: %zd files, %zd in the initial corpus\n",
 329            AllFiles.size(), NumFilesInFirstCorpus);
 330     WriteNewControlFile(CFPath, AllFiles, NumFilesInFirstCorpus);
 331     NumAttempts = AllFiles.size();
 332   }
 333
 334   // Execute the inner process until it passes.
 335   // Every inner process should execute at least one input.
 336   Command BaseCmd(Args);
 337   BaseCmd.removeFlag("merge");
 338   bool Success = false;
 339   for (size_t Attempt = 1; Attempt <= NumAttempts; Attempt++) {
 340     MaybeExitGracefully();
 341     Printf("MERGE-OUTER: attempt %zd\n", Attempt);
 342     Command Cmd(BaseCmd);
 343     Cmd.addFlag("merge_control_file", CFPath);
 344     Cmd.addFlag("merge_inner", "1");
 345     auto ExitCode = ExecuteCommand(Cmd);
 346     if (!ExitCode) {
 347       Printf("MERGE-OUTER: succesfull in %zd attempt(s)\n", Attempt);
 348       Success = true;
 349       break;
 350     }
 351   }
 352   if (!Success) {
 353     Printf("MERGE-OUTER: zero succesfull attempts, exiting\n");
 354     exit(1);
 355   }
 356   // Read the control file and do the merge.
 357   Merger M;
 358   std::ifstream IF(CFPath);
 359   IF.seekg(0, IF.end);
 360   Printf("MERGE-OUTER: the control file has %zd bytes\n", (size_t)IF.tellg());
 361   IF.seekg(0, IF.beg);
 362   M.ParseOrExit(IF, true);
 363   IF.close();
 364   Printf("MERGE-OUTER: consumed %zdMb (%zdMb rss) to parse the control file\n",
 365          M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb());
 366   if (CoverageSummaryOutputPathOrNull) {
 367     Printf("MERGE-OUTER: writing coverage summary for %zd files to %s\n",
 368            M.Files.size(), CoverageSummaryOutputPathOrNull);
 369     std::ofstream SummaryOut(CoverageSummaryOutputPathOrNull);
 370     M.PrintSummary(SummaryOut);
 371   }
 372   Vector<std::string> NewFiles;
 373   Set<uint32_t> InitialFeatures;
 374   if (CoverageSummaryInputPathOrNull) {
 375     std::ifstream SummaryIn(CoverageSummaryInputPathOrNull);
 376     InitialFeatures = M.ParseSummary(SummaryIn);
 377     Printf("MERGE-OUTER: coverage summary loaded from %s, %zd features found\n",
 378            CoverageSummaryInputPathOrNull, InitialFeatures.size());
 379   }
 380   size_t NumNewFeatures = M.Merge(InitialFeatures, &NewFiles);
 381   Printf("MERGE-OUTER: %zd new files with %zd new features added\n",
 382          NewFiles.size(), NumNewFeatures);
 383   for (auto &F: NewFiles)
 384     WriteToOutputCorpus(FileToVector(F, MaxInputLen));
 385   // We are done, delete the control file if it was a temporary one.
 386   if (!MergeControlFilePathOrNull)
 387     RemoveFile(CFPath);
 388 }
 389
 390 } // namespace fuzzer