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