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
94