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
51namespace fuzzer {
52
53struct MergeFileInfo {
54 std::string Name;
55 size_t Size = 0;
56 std::vector<uint32_t> Features, Cov;
57};
58
59struct 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
81void 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