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