10b57cec5SDimitry Andric //===- FuzzerMerge.cpp - merging corpora ----------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric // Merging corpora.
90b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
100b57cec5SDimitry Andric
110b57cec5SDimitry Andric #include "FuzzerCommand.h"
120b57cec5SDimitry Andric #include "FuzzerMerge.h"
130b57cec5SDimitry Andric #include "FuzzerIO.h"
140b57cec5SDimitry Andric #include "FuzzerInternal.h"
150b57cec5SDimitry Andric #include "FuzzerTracePC.h"
160b57cec5SDimitry Andric #include "FuzzerUtil.h"
170b57cec5SDimitry Andric
180b57cec5SDimitry Andric #include <fstream>
190b57cec5SDimitry Andric #include <iterator>
200b57cec5SDimitry Andric #include <set>
210b57cec5SDimitry Andric #include <sstream>
2268d75effSDimitry Andric #include <unordered_set>
230b57cec5SDimitry Andric
240b57cec5SDimitry Andric namespace fuzzer {
250b57cec5SDimitry Andric
Parse(const std::string & Str,bool ParseCoverage)260b57cec5SDimitry Andric bool Merger::Parse(const std::string &Str, bool ParseCoverage) {
270b57cec5SDimitry Andric std::istringstream SS(Str);
280b57cec5SDimitry Andric return Parse(SS, ParseCoverage);
290b57cec5SDimitry Andric }
300b57cec5SDimitry Andric
ParseOrExit(std::istream & IS,bool ParseCoverage)310b57cec5SDimitry Andric void Merger::ParseOrExit(std::istream &IS, bool ParseCoverage) {
320b57cec5SDimitry Andric if (!Parse(IS, ParseCoverage)) {
330b57cec5SDimitry Andric Printf("MERGE: failed to parse the control file (unexpected error)\n");
340b57cec5SDimitry Andric exit(1);
350b57cec5SDimitry Andric }
360b57cec5SDimitry Andric }
370b57cec5SDimitry Andric
380b57cec5SDimitry Andric // The control file example:
390b57cec5SDimitry Andric //
400b57cec5SDimitry Andric // 3 # The number of inputs
410b57cec5SDimitry Andric // 1 # The number of inputs in the first corpus, <= the previous number
420b57cec5SDimitry Andric // file0
430b57cec5SDimitry Andric // file1
440b57cec5SDimitry Andric // file2 # One file name per line.
450b57cec5SDimitry Andric // STARTED 0 123 # FileID, file size
460b57cec5SDimitry Andric // FT 0 1 4 6 8 # FileID COV1 COV2 ...
470b57cec5SDimitry Andric // COV 0 7 8 9 # FileID COV1 COV1
480b57cec5SDimitry Andric // STARTED 1 456 # If FT is missing, the input crashed while processing.
490b57cec5SDimitry Andric // STARTED 2 567
500b57cec5SDimitry Andric // FT 2 8 9
510b57cec5SDimitry Andric // COV 2 11 12
Parse(std::istream & IS,bool ParseCoverage)520b57cec5SDimitry Andric bool Merger::Parse(std::istream &IS, bool ParseCoverage) {
530b57cec5SDimitry Andric LastFailure.clear();
540b57cec5SDimitry Andric std::string Line;
550b57cec5SDimitry Andric
560b57cec5SDimitry Andric // Parse NumFiles.
570b57cec5SDimitry Andric if (!std::getline(IS, Line, '\n')) return false;
580b57cec5SDimitry Andric std::istringstream L1(Line);
590b57cec5SDimitry Andric size_t NumFiles = 0;
600b57cec5SDimitry Andric L1 >> NumFiles;
610b57cec5SDimitry Andric if (NumFiles == 0 || NumFiles > 10000000) return false;
620b57cec5SDimitry Andric
630b57cec5SDimitry Andric // Parse NumFilesInFirstCorpus.
640b57cec5SDimitry Andric if (!std::getline(IS, Line, '\n')) return false;
650b57cec5SDimitry Andric std::istringstream L2(Line);
660b57cec5SDimitry Andric NumFilesInFirstCorpus = NumFiles + 1;
670b57cec5SDimitry Andric L2 >> NumFilesInFirstCorpus;
680b57cec5SDimitry Andric if (NumFilesInFirstCorpus > NumFiles) return false;
690b57cec5SDimitry Andric
700b57cec5SDimitry Andric // Parse file names.
710b57cec5SDimitry Andric Files.resize(NumFiles);
720b57cec5SDimitry Andric for (size_t i = 0; i < NumFiles; i++)
730b57cec5SDimitry Andric if (!std::getline(IS, Files[i].Name, '\n'))
740b57cec5SDimitry Andric return false;
750b57cec5SDimitry Andric
760b57cec5SDimitry Andric // Parse STARTED, FT, and COV lines.
770b57cec5SDimitry Andric size_t ExpectedStartMarker = 0;
780b57cec5SDimitry Andric const size_t kInvalidStartMarker = -1;
790b57cec5SDimitry Andric size_t LastSeenStartMarker = kInvalidStartMarker;
8006c3fb27SDimitry Andric bool HaveFtMarker = true;
81349cc55cSDimitry Andric std::vector<uint32_t> TmpFeatures;
82349cc55cSDimitry Andric std::set<uint32_t> PCs;
830b57cec5SDimitry Andric while (std::getline(IS, Line, '\n')) {
840b57cec5SDimitry Andric std::istringstream ISS1(Line);
850b57cec5SDimitry Andric std::string Marker;
86fe6060f1SDimitry Andric uint32_t N;
87fe6060f1SDimitry Andric if (!(ISS1 >> Marker) || !(ISS1 >> N))
88fe6060f1SDimitry Andric return false;
890b57cec5SDimitry Andric if (Marker == "STARTED") {
900b57cec5SDimitry Andric // STARTED FILE_ID FILE_SIZE
910b57cec5SDimitry Andric if (ExpectedStartMarker != N)
920b57cec5SDimitry Andric return false;
930b57cec5SDimitry Andric ISS1 >> Files[ExpectedStartMarker].Size;
940b57cec5SDimitry Andric LastSeenStartMarker = ExpectedStartMarker;
950b57cec5SDimitry Andric assert(ExpectedStartMarker < Files.size());
960b57cec5SDimitry Andric ExpectedStartMarker++;
9706c3fb27SDimitry Andric HaveFtMarker = false;
980b57cec5SDimitry Andric } else if (Marker == "FT") {
990b57cec5SDimitry Andric // FT FILE_ID COV1 COV2 COV3 ...
1000b57cec5SDimitry Andric size_t CurrentFileIdx = N;
1010b57cec5SDimitry Andric if (CurrentFileIdx != LastSeenStartMarker)
1020b57cec5SDimitry Andric return false;
10306c3fb27SDimitry Andric HaveFtMarker = true;
1040b57cec5SDimitry Andric if (ParseCoverage) {
1050b57cec5SDimitry Andric TmpFeatures.clear(); // use a vector from outer scope to avoid resizes.
1060b57cec5SDimitry Andric while (ISS1 >> N)
1070b57cec5SDimitry Andric TmpFeatures.push_back(N);
1080b57cec5SDimitry Andric std::sort(TmpFeatures.begin(), TmpFeatures.end());
1090b57cec5SDimitry Andric Files[CurrentFileIdx].Features = TmpFeatures;
1100b57cec5SDimitry Andric }
1110b57cec5SDimitry Andric } else if (Marker == "COV") {
1120b57cec5SDimitry Andric size_t CurrentFileIdx = N;
11306c3fb27SDimitry Andric if (CurrentFileIdx != LastSeenStartMarker)
11406c3fb27SDimitry Andric return false;
1150b57cec5SDimitry Andric if (ParseCoverage)
1160b57cec5SDimitry Andric while (ISS1 >> N)
1170b57cec5SDimitry Andric if (PCs.insert(N).second)
1180b57cec5SDimitry Andric Files[CurrentFileIdx].Cov.push_back(N);
1190b57cec5SDimitry Andric } else {
1200b57cec5SDimitry Andric return false;
1210b57cec5SDimitry Andric }
1220b57cec5SDimitry Andric }
12306c3fb27SDimitry Andric if (!HaveFtMarker && LastSeenStartMarker != kInvalidStartMarker)
1240b57cec5SDimitry Andric LastFailure = Files[LastSeenStartMarker].Name;
1250b57cec5SDimitry Andric
1260b57cec5SDimitry Andric FirstNotProcessedFile = ExpectedStartMarker;
1270b57cec5SDimitry Andric return true;
1280b57cec5SDimitry Andric }
1290b57cec5SDimitry Andric
ApproximateMemoryConsumption() const1300b57cec5SDimitry Andric size_t Merger::ApproximateMemoryConsumption() const {
1310b57cec5SDimitry Andric size_t Res = 0;
1320b57cec5SDimitry Andric for (const auto &F: Files)
1330b57cec5SDimitry Andric Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]);
1340b57cec5SDimitry Andric return Res;
1350b57cec5SDimitry Andric }
1360b57cec5SDimitry Andric
1370b57cec5SDimitry Andric // Decides which files need to be merged (add those to NewFiles).
1380b57cec5SDimitry Andric // Returns the number of new features added.
Merge(const std::set<uint32_t> & InitialFeatures,std::set<uint32_t> * NewFeatures,const std::set<uint32_t> & InitialCov,std::set<uint32_t> * NewCov,std::vector<std::string> * NewFiles)139349cc55cSDimitry Andric size_t Merger::Merge(const std::set<uint32_t> &InitialFeatures,
140349cc55cSDimitry Andric std::set<uint32_t> *NewFeatures,
141349cc55cSDimitry Andric const std::set<uint32_t> &InitialCov,
142349cc55cSDimitry Andric std::set<uint32_t> *NewCov,
143349cc55cSDimitry Andric std::vector<std::string> *NewFiles) {
1440b57cec5SDimitry Andric NewFiles->clear();
145fe6060f1SDimitry Andric NewFeatures->clear();
146fe6060f1SDimitry Andric NewCov->clear();
1470b57cec5SDimitry Andric assert(NumFilesInFirstCorpus <= Files.size());
148349cc55cSDimitry Andric std::set<uint32_t> AllFeatures = InitialFeatures;
1490b57cec5SDimitry Andric
1500b57cec5SDimitry Andric // What features are in the initial corpus?
1510b57cec5SDimitry Andric for (size_t i = 0; i < NumFilesInFirstCorpus; i++) {
1520b57cec5SDimitry Andric auto &Cur = Files[i].Features;
1530b57cec5SDimitry Andric AllFeatures.insert(Cur.begin(), Cur.end());
1540b57cec5SDimitry Andric }
1550b57cec5SDimitry Andric // Remove all features that we already know from all other inputs.
1560b57cec5SDimitry Andric for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
1570b57cec5SDimitry Andric auto &Cur = Files[i].Features;
158349cc55cSDimitry Andric std::vector<uint32_t> Tmp;
1590b57cec5SDimitry Andric std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(),
1600b57cec5SDimitry Andric AllFeatures.end(), std::inserter(Tmp, Tmp.begin()));
1610b57cec5SDimitry Andric Cur.swap(Tmp);
1620b57cec5SDimitry Andric }
1630b57cec5SDimitry Andric
1640b57cec5SDimitry Andric // Sort. Give preference to
1650b57cec5SDimitry Andric // * smaller files
1660b57cec5SDimitry Andric // * files with more features.
1670b57cec5SDimitry Andric std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(),
1680b57cec5SDimitry Andric [&](const MergeFileInfo &a, const MergeFileInfo &b) -> bool {
1690b57cec5SDimitry Andric if (a.Size != b.Size)
1700b57cec5SDimitry Andric return a.Size < b.Size;
1710b57cec5SDimitry Andric return a.Features.size() > b.Features.size();
1720b57cec5SDimitry Andric });
1730b57cec5SDimitry Andric
1740b57cec5SDimitry Andric // One greedy pass: add the file's features to AllFeatures.
1750b57cec5SDimitry Andric // If new features were added, add this file to NewFiles.
1760b57cec5SDimitry Andric for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
1770b57cec5SDimitry Andric auto &Cur = Files[i].Features;
1780b57cec5SDimitry Andric // Printf("%s -> sz %zd ft %zd\n", Files[i].Name.c_str(),
1790b57cec5SDimitry Andric // Files[i].Size, Cur.size());
1800b57cec5SDimitry Andric bool FoundNewFeatures = false;
1810b57cec5SDimitry Andric for (auto Fe: Cur) {
1820b57cec5SDimitry Andric if (AllFeatures.insert(Fe).second) {
1830b57cec5SDimitry Andric FoundNewFeatures = true;
1840b57cec5SDimitry Andric NewFeatures->insert(Fe);
1850b57cec5SDimitry Andric }
1860b57cec5SDimitry Andric }
1870b57cec5SDimitry Andric if (FoundNewFeatures)
1880b57cec5SDimitry Andric NewFiles->push_back(Files[i].Name);
1890b57cec5SDimitry Andric for (auto Cov : Files[i].Cov)
1900b57cec5SDimitry Andric if (InitialCov.find(Cov) == InitialCov.end())
1910b57cec5SDimitry Andric NewCov->insert(Cov);
1920b57cec5SDimitry Andric }
1930b57cec5SDimitry Andric return NewFeatures->size();
1940b57cec5SDimitry Andric }
1950b57cec5SDimitry Andric
AllFeatures() const196349cc55cSDimitry Andric std::set<uint32_t> Merger::AllFeatures() const {
197349cc55cSDimitry Andric std::set<uint32_t> S;
1980b57cec5SDimitry Andric for (auto &File : Files)
1990b57cec5SDimitry Andric S.insert(File.Features.begin(), File.Features.end());
2000b57cec5SDimitry Andric return S;
2010b57cec5SDimitry Andric }
2020b57cec5SDimitry Andric
2030b57cec5SDimitry Andric // Inner process. May crash if the target crashes.
CrashResistantMergeInternalStep(const std::string & CFPath,bool IsSetCoverMerge)204349cc55cSDimitry Andric void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath,
205349cc55cSDimitry Andric bool IsSetCoverMerge) {
2060b57cec5SDimitry Andric Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str());
2070b57cec5SDimitry Andric Merger M;
2080b57cec5SDimitry Andric std::ifstream IF(CFPath);
2090b57cec5SDimitry Andric M.ParseOrExit(IF, false);
2100b57cec5SDimitry Andric IF.close();
2110b57cec5SDimitry Andric if (!M.LastFailure.empty())
2120b57cec5SDimitry Andric Printf("MERGE-INNER: '%s' caused a failure at the previous merge step\n",
2130b57cec5SDimitry Andric M.LastFailure.c_str());
2140b57cec5SDimitry Andric
2150b57cec5SDimitry Andric Printf("MERGE-INNER: %zd total files;"
2160b57cec5SDimitry Andric " %zd processed earlier; will process %zd files now\n",
2170b57cec5SDimitry Andric M.Files.size(), M.FirstNotProcessedFile,
2180b57cec5SDimitry Andric M.Files.size() - M.FirstNotProcessedFile);
2190b57cec5SDimitry Andric
2200b57cec5SDimitry Andric std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app);
221349cc55cSDimitry Andric std::set<size_t> AllFeatures;
22268d75effSDimitry Andric auto PrintStatsWrapper = [this, &AllFeatures](const char* Where) {
22368d75effSDimitry Andric this->PrintStats(Where, "\n", 0, AllFeatures.size());
22468d75effSDimitry Andric };
225349cc55cSDimitry Andric std::set<const TracePC::PCTableEntry *> AllPCs;
2260b57cec5SDimitry Andric for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {
2270b57cec5SDimitry Andric Fuzzer::MaybeExitGracefully();
2280b57cec5SDimitry Andric auto U = FileToVector(M.Files[i].Name);
2290b57cec5SDimitry Andric if (U.size() > MaxInputLen) {
2300b57cec5SDimitry Andric U.resize(MaxInputLen);
2310b57cec5SDimitry Andric U.shrink_to_fit();
2320b57cec5SDimitry Andric }
23368d75effSDimitry Andric
2340b57cec5SDimitry Andric // Write the pre-run marker.
2350b57cec5SDimitry Andric OF << "STARTED " << i << " " << U.size() << "\n";
2360b57cec5SDimitry Andric OF.flush(); // Flush is important since Command::Execute may crash.
2370b57cec5SDimitry Andric // Run.
2380b57cec5SDimitry Andric TPC.ResetMaps();
2390b57cec5SDimitry Andric ExecuteCallback(U.data(), U.size());
2400b57cec5SDimitry Andric // Collect coverage. We are iterating over the files in this order:
2410b57cec5SDimitry Andric // * First, files in the initial corpus ordered by size, smallest first.
2420b57cec5SDimitry Andric // * Then, all other files, smallest first.
243349cc55cSDimitry Andric std::set<size_t> Features;
244349cc55cSDimitry Andric if (IsSetCoverMerge)
245349cc55cSDimitry Andric TPC.CollectFeatures([&](size_t Feature) { Features.insert(Feature); });
246349cc55cSDimitry Andric else
2470b57cec5SDimitry Andric TPC.CollectFeatures([&](size_t Feature) {
2480b57cec5SDimitry Andric if (AllFeatures.insert(Feature).second)
249349cc55cSDimitry Andric Features.insert(Feature);
2500b57cec5SDimitry Andric });
2510b57cec5SDimitry Andric TPC.UpdateObservedPCs();
2520b57cec5SDimitry Andric // Show stats.
2530b57cec5SDimitry Andric if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))
25468d75effSDimitry Andric PrintStatsWrapper("pulse ");
25568d75effSDimitry Andric if (TotalNumberOfRuns == M.NumFilesInFirstCorpus)
25668d75effSDimitry Andric PrintStatsWrapper("LOADED");
2570b57cec5SDimitry Andric // Write the post-run marker and the coverage.
2580b57cec5SDimitry Andric OF << "FT " << i;
259349cc55cSDimitry Andric for (size_t F : Features)
2600b57cec5SDimitry Andric OF << " " << F;
2610b57cec5SDimitry Andric OF << "\n";
2620b57cec5SDimitry Andric OF << "COV " << i;
2630b57cec5SDimitry Andric TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) {
2640b57cec5SDimitry Andric if (AllPCs.insert(TE).second)
2650b57cec5SDimitry Andric OF << " " << TPC.PCTableEntryIdx(TE);
2660b57cec5SDimitry Andric });
2670b57cec5SDimitry Andric OF << "\n";
2680b57cec5SDimitry Andric OF.flush();
2690b57cec5SDimitry Andric }
27068d75effSDimitry Andric PrintStatsWrapper("DONE ");
2710b57cec5SDimitry Andric }
2720b57cec5SDimitry Andric
273349cc55cSDimitry Andric // Merges all corpora into the first corpus. A file is added into
274349cc55cSDimitry Andric // the first corpus only if it adds new features. Unlike `Merger::Merge`,
275349cc55cSDimitry Andric // this implementation calculates an approximation of the minimum set
276349cc55cSDimitry Andric // of corpora files, that cover all known features (set cover problem).
277349cc55cSDimitry Andric // Generally, this means that files with more features are preferred for
278349cc55cSDimitry Andric // merge into the first corpus. When two files have the same number of
279349cc55cSDimitry Andric // features, the smaller one is preferred.
SetCoverMerge(const std::set<uint32_t> & InitialFeatures,std::set<uint32_t> * NewFeatures,const std::set<uint32_t> & InitialCov,std::set<uint32_t> * NewCov,std::vector<std::string> * NewFiles)280349cc55cSDimitry Andric size_t Merger::SetCoverMerge(const std::set<uint32_t> &InitialFeatures,
281349cc55cSDimitry Andric std::set<uint32_t> *NewFeatures,
282349cc55cSDimitry Andric const std::set<uint32_t> &InitialCov,
283349cc55cSDimitry Andric std::set<uint32_t> *NewCov,
284349cc55cSDimitry Andric std::vector<std::string> *NewFiles) {
285349cc55cSDimitry Andric assert(NumFilesInFirstCorpus <= Files.size());
286349cc55cSDimitry Andric NewFiles->clear();
287349cc55cSDimitry Andric NewFeatures->clear();
288349cc55cSDimitry Andric NewCov->clear();
289349cc55cSDimitry Andric std::set<uint32_t> AllFeatures;
290349cc55cSDimitry Andric // 1 << 21 - 1 is the maximum feature index.
291349cc55cSDimitry Andric // See 'kFeatureSetSize' in 'FuzzerCorpus.h'.
292349cc55cSDimitry Andric const uint32_t kFeatureSetSize = 1 << 21;
293349cc55cSDimitry Andric std::vector<bool> Covered(kFeatureSetSize, false);
294349cc55cSDimitry Andric size_t NumCovered = 0;
295349cc55cSDimitry Andric
296349cc55cSDimitry Andric std::set<uint32_t> ExistingFeatures = InitialFeatures;
297349cc55cSDimitry Andric for (size_t i = 0; i < NumFilesInFirstCorpus; ++i)
298349cc55cSDimitry Andric ExistingFeatures.insert(Files[i].Features.begin(), Files[i].Features.end());
299349cc55cSDimitry Andric
300349cc55cSDimitry Andric // Mark the existing features as covered.
301349cc55cSDimitry Andric for (const auto &F : ExistingFeatures) {
302349cc55cSDimitry Andric if (!Covered[F % kFeatureSetSize]) {
303349cc55cSDimitry Andric ++NumCovered;
304349cc55cSDimitry Andric Covered[F % kFeatureSetSize] = true;
305349cc55cSDimitry Andric }
306349cc55cSDimitry Andric // Calculate an underestimation of the set of covered features
307349cc55cSDimitry Andric // since the `Covered` bitvector is smaller than the feature range.
308349cc55cSDimitry Andric AllFeatures.insert(F % kFeatureSetSize);
309349cc55cSDimitry Andric }
310349cc55cSDimitry Andric
311349cc55cSDimitry Andric std::set<size_t> RemainingFiles;
312349cc55cSDimitry Andric for (size_t i = NumFilesInFirstCorpus; i < Files.size(); ++i) {
313349cc55cSDimitry Andric // Construct an incremental sequence which represent the
314349cc55cSDimitry Andric // indices to all files (excluding those in the initial corpus).
315349cc55cSDimitry Andric // RemainingFiles = range(NumFilesInFirstCorpus..Files.size()).
316349cc55cSDimitry Andric RemainingFiles.insert(i);
317349cc55cSDimitry Andric // Insert this file's unique features to all features.
318349cc55cSDimitry Andric for (const auto &F : Files[i].Features)
319349cc55cSDimitry Andric AllFeatures.insert(F % kFeatureSetSize);
320349cc55cSDimitry Andric }
321349cc55cSDimitry Andric
322349cc55cSDimitry Andric // Integrate files into Covered until set is complete.
323349cc55cSDimitry Andric while (NumCovered != AllFeatures.size()) {
324349cc55cSDimitry Andric // Index to file with largest number of unique features.
325349cc55cSDimitry Andric size_t MaxFeaturesIndex = NumFilesInFirstCorpus;
326349cc55cSDimitry Andric // Indices to remove from RemainingFiles.
327349cc55cSDimitry Andric std::set<size_t> RemoveIndices;
328349cc55cSDimitry Andric // Running max unique feature count.
329349cc55cSDimitry Andric // Updated upon finding a file with more features.
330349cc55cSDimitry Andric size_t MaxNumFeatures = 0;
331349cc55cSDimitry Andric
332349cc55cSDimitry Andric // Iterate over all files not yet integrated into Covered,
333349cc55cSDimitry Andric // to find the file which has the largest number of
334349cc55cSDimitry Andric // features that are not already in Covered.
335349cc55cSDimitry Andric for (const auto &i : RemainingFiles) {
336349cc55cSDimitry Andric const auto &File = Files[i];
337349cc55cSDimitry Andric size_t CurrentUnique = 0;
338349cc55cSDimitry Andric // Count number of features in this file
339349cc55cSDimitry Andric // which are not yet in Covered.
340349cc55cSDimitry Andric for (const auto &F : File.Features)
341349cc55cSDimitry Andric if (!Covered[F % kFeatureSetSize])
342349cc55cSDimitry Andric ++CurrentUnique;
343349cc55cSDimitry Andric
344349cc55cSDimitry Andric if (CurrentUnique == 0) {
345349cc55cSDimitry Andric // All features in this file are already in Covered: skip next time.
346349cc55cSDimitry Andric RemoveIndices.insert(i);
347349cc55cSDimitry Andric } else if (CurrentUnique > MaxNumFeatures ||
348349cc55cSDimitry Andric (CurrentUnique == MaxNumFeatures &&
349349cc55cSDimitry Andric File.Size < Files[MaxFeaturesIndex].Size)) {
350349cc55cSDimitry Andric // Update the max features file based on unique features
351349cc55cSDimitry Andric // Break ties by selecting smaller files.
352349cc55cSDimitry Andric MaxNumFeatures = CurrentUnique;
353349cc55cSDimitry Andric MaxFeaturesIndex = i;
354349cc55cSDimitry Andric }
355349cc55cSDimitry Andric }
356349cc55cSDimitry Andric // Must be a valid index/
357349cc55cSDimitry Andric assert(MaxFeaturesIndex < Files.size());
358349cc55cSDimitry Andric // Remove any feature-less files found.
359349cc55cSDimitry Andric for (const auto &i : RemoveIndices)
360349cc55cSDimitry Andric RemainingFiles.erase(i);
361349cc55cSDimitry Andric if (MaxNumFeatures == 0) {
362349cc55cSDimitry Andric // Did not find a file that adds unique features.
363349cc55cSDimitry Andric // This means that we should have no remaining files.
364349cc55cSDimitry Andric assert(RemainingFiles.size() == 0);
365349cc55cSDimitry Andric assert(NumCovered == AllFeatures.size());
366349cc55cSDimitry Andric break;
367349cc55cSDimitry Andric }
368349cc55cSDimitry Andric
369349cc55cSDimitry Andric // MaxFeaturesIndex must be an element of Remaining.
370349cc55cSDimitry Andric assert(RemainingFiles.find(MaxFeaturesIndex) != RemainingFiles.end());
371349cc55cSDimitry Andric // Remove the file with the most features from Remaining.
372349cc55cSDimitry Andric RemainingFiles.erase(MaxFeaturesIndex);
373349cc55cSDimitry Andric const auto &MaxFeatureFile = Files[MaxFeaturesIndex];
374349cc55cSDimitry Andric // Add the features of the max feature file to Covered.
375349cc55cSDimitry Andric for (const auto &F : MaxFeatureFile.Features) {
376349cc55cSDimitry Andric if (!Covered[F % kFeatureSetSize]) {
377349cc55cSDimitry Andric ++NumCovered;
378349cc55cSDimitry Andric Covered[F % kFeatureSetSize] = true;
379349cc55cSDimitry Andric NewFeatures->insert(F);
380349cc55cSDimitry Andric }
381349cc55cSDimitry Andric }
382349cc55cSDimitry Andric // Add the index to this file to the result.
383349cc55cSDimitry Andric NewFiles->push_back(MaxFeatureFile.Name);
384349cc55cSDimitry Andric // Update NewCov with the additional coverage
385349cc55cSDimitry Andric // that MaxFeatureFile provides.
386349cc55cSDimitry Andric for (const auto &C : MaxFeatureFile.Cov)
387349cc55cSDimitry Andric if (InitialCov.find(C) == InitialCov.end())
388349cc55cSDimitry Andric NewCov->insert(C);
389349cc55cSDimitry Andric }
390349cc55cSDimitry Andric
391349cc55cSDimitry Andric return NewFeatures->size();
392349cc55cSDimitry Andric }
393349cc55cSDimitry Andric
394349cc55cSDimitry Andric static size_t
WriteNewControlFile(const std::string & CFPath,const std::vector<SizedFile> & OldCorpus,const std::vector<SizedFile> & NewCorpus,const std::vector<MergeFileInfo> & KnownFiles)395349cc55cSDimitry Andric WriteNewControlFile(const std::string &CFPath,
396349cc55cSDimitry Andric const std::vector<SizedFile> &OldCorpus,
397349cc55cSDimitry Andric const std::vector<SizedFile> &NewCorpus,
398349cc55cSDimitry Andric const std::vector<MergeFileInfo> &KnownFiles) {
39968d75effSDimitry Andric std::unordered_set<std::string> FilesToSkip;
40068d75effSDimitry Andric for (auto &SF: KnownFiles)
40168d75effSDimitry Andric FilesToSkip.insert(SF.Name);
40268d75effSDimitry Andric
403349cc55cSDimitry Andric std::vector<std::string> FilesToUse;
40468d75effSDimitry Andric auto MaybeUseFile = [=, &FilesToUse](std::string Name) {
40568d75effSDimitry Andric if (FilesToSkip.find(Name) == FilesToSkip.end())
40668d75effSDimitry Andric FilesToUse.push_back(Name);
40768d75effSDimitry Andric };
40868d75effSDimitry Andric for (auto &SF: OldCorpus)
40968d75effSDimitry Andric MaybeUseFile(SF.File);
41068d75effSDimitry Andric auto FilesToUseFromOldCorpus = FilesToUse.size();
41168d75effSDimitry Andric for (auto &SF: NewCorpus)
41268d75effSDimitry Andric MaybeUseFile(SF.File);
41368d75effSDimitry Andric
4140b57cec5SDimitry Andric RemoveFile(CFPath);
4150b57cec5SDimitry Andric std::ofstream ControlFile(CFPath);
41668d75effSDimitry Andric ControlFile << FilesToUse.size() << "\n";
41768d75effSDimitry Andric ControlFile << FilesToUseFromOldCorpus << "\n";
41868d75effSDimitry Andric for (auto &FN: FilesToUse)
41968d75effSDimitry Andric ControlFile << FN << "\n";
42068d75effSDimitry Andric
4210b57cec5SDimitry Andric if (!ControlFile) {
4220b57cec5SDimitry Andric Printf("MERGE-OUTER: failed to write to the control file: %s\n",
4230b57cec5SDimitry Andric CFPath.c_str());
4240b57cec5SDimitry Andric exit(1);
4250b57cec5SDimitry Andric }
42668d75effSDimitry Andric
42768d75effSDimitry Andric return FilesToUse.size();
4280b57cec5SDimitry Andric }
4290b57cec5SDimitry Andric
4300b57cec5SDimitry Andric // Outer process. Does not call the target code and thus should not fail.
CrashResistantMerge(const std::vector<std::string> & Args,const std::vector<SizedFile> & OldCorpus,const std::vector<SizedFile> & NewCorpus,std::vector<std::string> * NewFiles,const std::set<uint32_t> & InitialFeatures,std::set<uint32_t> * NewFeatures,const std::set<uint32_t> & InitialCov,std::set<uint32_t> * NewCov,const std::string & CFPath,bool V,bool IsSetCoverMerge)431349cc55cSDimitry Andric void CrashResistantMerge(const std::vector<std::string> &Args,
432349cc55cSDimitry Andric const std::vector<SizedFile> &OldCorpus,
433349cc55cSDimitry Andric const std::vector<SizedFile> &NewCorpus,
434349cc55cSDimitry Andric std::vector<std::string> *NewFiles,
435349cc55cSDimitry Andric const std::set<uint32_t> &InitialFeatures,
436349cc55cSDimitry Andric std::set<uint32_t> *NewFeatures,
437349cc55cSDimitry Andric const std::set<uint32_t> &InitialCov,
438349cc55cSDimitry Andric std::set<uint32_t> *NewCov, const std::string &CFPath,
439349cc55cSDimitry Andric bool V, /*Verbose*/
440349cc55cSDimitry Andric bool IsSetCoverMerge) {
4410b57cec5SDimitry Andric if (NewCorpus.empty() && OldCorpus.empty()) return; // Nothing to merge.
4420b57cec5SDimitry Andric size_t NumAttempts = 0;
443349cc55cSDimitry Andric std::vector<MergeFileInfo> KnownFiles;
4440b57cec5SDimitry Andric if (FileSize(CFPath)) {
4450b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: non-empty control file provided: '%s'\n",
4460b57cec5SDimitry Andric CFPath.c_str());
4470b57cec5SDimitry Andric Merger M;
4480b57cec5SDimitry Andric std::ifstream IF(CFPath);
44968d75effSDimitry Andric if (M.Parse(IF, /*ParseCoverage=*/true)) {
4500b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: control file ok, %zd files total,"
4510b57cec5SDimitry Andric " first not processed file %zd\n",
4520b57cec5SDimitry Andric M.Files.size(), M.FirstNotProcessedFile);
4530b57cec5SDimitry Andric if (!M.LastFailure.empty())
4540b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: '%s' will be skipped as unlucky "
4550b57cec5SDimitry Andric "(merge has stumbled on it the last time)\n",
4560b57cec5SDimitry Andric M.LastFailure.c_str());
4570b57cec5SDimitry Andric if (M.FirstNotProcessedFile >= M.Files.size()) {
45868d75effSDimitry Andric // Merge has already been completed with the given merge control file.
45968d75effSDimitry Andric if (M.Files.size() == OldCorpus.size() + NewCorpus.size()) {
4600b57cec5SDimitry Andric VPrintf(
46168d75effSDimitry Andric V,
46268d75effSDimitry Andric "MERGE-OUTER: nothing to do, merge has been completed before\n");
4630b57cec5SDimitry Andric exit(0);
4640b57cec5SDimitry Andric }
4650b57cec5SDimitry Andric
46668d75effSDimitry Andric // Number of input files likely changed, start merge from scratch, but
46768d75effSDimitry Andric // reuse coverage information from the given merge control file.
46868d75effSDimitry Andric VPrintf(
46968d75effSDimitry Andric V,
47068d75effSDimitry Andric "MERGE-OUTER: starting merge from scratch, but reusing coverage "
47168d75effSDimitry Andric "information from the given control file\n");
47268d75effSDimitry Andric KnownFiles = M.Files;
47368d75effSDimitry Andric } else {
47468d75effSDimitry Andric // There is a merge in progress, continue.
4750b57cec5SDimitry Andric NumAttempts = M.Files.size() - M.FirstNotProcessedFile;
47668d75effSDimitry Andric }
4770b57cec5SDimitry Andric } else {
4780b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: bad control file, will overwrite it\n");
4790b57cec5SDimitry Andric }
4800b57cec5SDimitry Andric }
4810b57cec5SDimitry Andric
4820b57cec5SDimitry Andric if (!NumAttempts) {
4830b57cec5SDimitry Andric // The supplied control file is empty or bad, create a fresh one.
48468d75effSDimitry Andric VPrintf(V, "MERGE-OUTER: "
48568d75effSDimitry Andric "%zd files, %zd in the initial corpus, %zd processed earlier\n",
48668d75effSDimitry Andric OldCorpus.size() + NewCorpus.size(), OldCorpus.size(),
48768d75effSDimitry Andric KnownFiles.size());
48868d75effSDimitry Andric NumAttempts = WriteNewControlFile(CFPath, OldCorpus, NewCorpus, KnownFiles);
4890b57cec5SDimitry Andric }
4900b57cec5SDimitry Andric
4910b57cec5SDimitry Andric // Execute the inner process until it passes.
4920b57cec5SDimitry Andric // Every inner process should execute at least one input.
4930b57cec5SDimitry Andric Command BaseCmd(Args);
4940b57cec5SDimitry Andric BaseCmd.removeFlag("merge");
495349cc55cSDimitry Andric BaseCmd.removeFlag("set_cover_merge");
4960b57cec5SDimitry Andric BaseCmd.removeFlag("fork");
4970b57cec5SDimitry Andric BaseCmd.removeFlag("collect_data_flow");
4980b57cec5SDimitry Andric for (size_t Attempt = 1; Attempt <= NumAttempts; Attempt++) {
4990b57cec5SDimitry Andric Fuzzer::MaybeExitGracefully();
5000b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: attempt %zd\n", Attempt);
5010b57cec5SDimitry Andric Command Cmd(BaseCmd);
5020b57cec5SDimitry Andric Cmd.addFlag("merge_control_file", CFPath);
503349cc55cSDimitry Andric // If we are going to use the set cover implementation for
504349cc55cSDimitry Andric // minimization add the merge_inner=2 internal flag.
505349cc55cSDimitry Andric Cmd.addFlag("merge_inner", IsSetCoverMerge ? "2" : "1");
5060b57cec5SDimitry Andric if (!V) {
5070b57cec5SDimitry Andric Cmd.setOutputFile(getDevNull());
5080b57cec5SDimitry Andric Cmd.combineOutAndErr();
5090b57cec5SDimitry Andric }
5100b57cec5SDimitry Andric auto ExitCode = ExecuteCommand(Cmd);
5110b57cec5SDimitry Andric if (!ExitCode) {
512349cc55cSDimitry Andric VPrintf(V, "MERGE-OUTER: successful in %zd attempt(s)\n", Attempt);
5130b57cec5SDimitry Andric break;
5140b57cec5SDimitry Andric }
5150b57cec5SDimitry Andric }
5160b57cec5SDimitry Andric // Read the control file and do the merge.
5170b57cec5SDimitry Andric Merger M;
5180b57cec5SDimitry Andric std::ifstream IF(CFPath);
5190b57cec5SDimitry Andric IF.seekg(0, IF.end);
5200b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: the control file has %zd bytes\n",
5210b57cec5SDimitry Andric (size_t)IF.tellg());
5220b57cec5SDimitry Andric IF.seekg(0, IF.beg);
5230b57cec5SDimitry Andric M.ParseOrExit(IF, true);
5240b57cec5SDimitry Andric IF.close();
5250b57cec5SDimitry Andric VPrintf(V,
5260b57cec5SDimitry Andric "MERGE-OUTER: consumed %zdMb (%zdMb rss) to parse the control file\n",
5270b57cec5SDimitry Andric M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb());
52868d75effSDimitry Andric
52968d75effSDimitry Andric M.Files.insert(M.Files.end(), KnownFiles.begin(), KnownFiles.end());
530349cc55cSDimitry Andric if (IsSetCoverMerge)
531349cc55cSDimitry Andric M.SetCoverMerge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles);
532349cc55cSDimitry Andric else
5330b57cec5SDimitry Andric M.Merge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles);
5340b57cec5SDimitry Andric VPrintf(V, "MERGE-OUTER: %zd new files with %zd new features added; "
5350b57cec5SDimitry Andric "%zd new coverage edges\n",
5360b57cec5SDimitry Andric NewFiles->size(), NewFeatures->size(), NewCov->size());
5370b57cec5SDimitry Andric }
5380b57cec5SDimitry Andric
5390b57cec5SDimitry Andric } // namespace fuzzer
540