compiler-rt/lib/fuzzer/FuzzerMerge.h

   1 //===- FuzzerMerge.h - merging corpa ----------------------------*- C++ -* ===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // Merging Corpora.
   9 //
  10 // The task:
  11 //   Take the existing corpus (possibly empty) and merge new inputs into
  12 //   it so that only inputs with new coverage ('features') are added.
  13 //   The process should tolerate the crashes, OOMs, leaks, etc.
  14 //
  15 // Algorithm:
  16 //   The outer process collects the set of files and writes their names
  17 //   into a temporary "control" file, then repeatedly launches the inner
  18 //   process until all inputs are processed.
  19 //   The outer process does not actually execute the target code.
  20 //
  21 //   The inner process reads the control file and sees a) list of all the inputs
  22 //   and b) the last processed input. Then it starts processing the inputs one
  23 //   by one. Before processing every input it writes one line to control file:
  24 //   STARTED INPUT_ID INPUT_SIZE
  25 //   After processing an input it writes the following lines:
  26 //   FT INPUT_ID Feature1 Feature2 Feature3 ...
  27 //   COV INPUT_ID Coverage1 Coverage2 Coverage3 ...
  28 //   If a crash happens while processing an input the last line in the control
  29 //   file will be "STARTED INPUT_ID" and so the next process will know
  30 //   where to resume.
  31 //
  32 //   Once all inputs are processed by the inner process(es) the outer process
  33 //   reads the control files and does the merge based entirely on the contents
  34 //   of control file.
  35 //   It uses a single pass greedy algorithm choosing first the smallest inputs
  36 //   within the same size the inputs that have more new features.
  37 //
  38 //===----------------------------------------------------------------------===//
  39
  40 #ifndef LLVM_FUZZER_MERGE_H
  41 #define LLVM_FUZZER_MERGE_H
  42
  43 #include "FuzzerDefs.h"
  44 #include "FuzzerIO.h"
  45
  46 #include <istream>
  47 #include <ostream>
  48 #include <set>
  49 #include <vector>
  50
  51 namespace fuzzer {
  52
  53 struct MergeFileInfo {
  54   std::string Name;
  55   size_t Size = 0;
  56   std::vector<uint32_t> Features, Cov;
  57 };
  58
  59 struct Merger {
  60   std::vector<MergeFileInfo> Files;
  61   size_t NumFilesInFirstCorpus = 0;
  62   size_t FirstNotProcessedFile = 0;
  63   std::string LastFailure;
  64
  65   bool Parse(std::istream &IS, bool ParseCoverage);
  66   bool Parse(const std::string &Str, bool ParseCoverage);
  67   void ParseOrExit(std::istream &IS, bool ParseCoverage);
  68   size_t Merge(const std::set<uint32_t> &InitialFeatures,
  69                std::set<uint32_t> *NewFeatures,
  70                const std::set<uint32_t> &InitialCov, std::set<uint32_t> *NewCov,
  71                std::vector<std::string> *NewFiles);
  72   size_t SetCoverMerge(const std::set<uint32_t> &InitialFeatures,
  73                        std::set<uint32_t> *NewFeatures,
  74                        const std::set<uint32_t> &InitialCov,
  75                        std::set<uint32_t> *NewCov,
  76                        std::vector<std::string> *NewFiles);
  77   size_t ApproximateMemoryConsumption() const;
  78   std::set<uint32_t> AllFeatures() const;
  79 };
  80
  81 void CrashResistantMerge(const std::vector<std::string> &Args,
  82                          const std::vector<SizedFile> &OldCorpus,
  83                          const std::vector<SizedFile> &NewCorpus,
  84                          std::vector<std::string> *NewFiles,
  85                          const std::set<uint32_t> &InitialFeatures,
  86                          std::set<uint32_t> *NewFeatures,
  87                          const std::set<uint32_t> &InitialCov,
  88                          std::set<uint32_t> *NewCov, const std::string &CFPath,
  89                          bool Verbose, bool IsSetCoverMerge);
  90
  91 }  // namespace fuzzer
  92
  93 #endif  // LLVM_FUZZER_MERGE_H