| //===- FuzzerMerge.cpp - merging corpora ----------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // Merging corpora. |
| //===----------------------------------------------------------------------===// |
| |
| #include "FuzzerCommand.h" |
| #include "FuzzerMerge.h" |
| #include "FuzzerIO.h" |
| #include "FuzzerInternal.h" |
| #include "FuzzerTracePC.h" |
| #include "FuzzerUtil.h" |
| |
| #include <fstream> |
| #include <iterator> |
| #include <set> |
| #include <sstream> |
| #include <unordered_set> |
| |
| namespace fuzzer { |
| |
| bool Merger::Parse(const std::string &Str, bool ParseCoverage) { |
| std::istringstream SS(Str); |
| return Parse(SS, ParseCoverage); |
| } |
| |
| void Merger::ParseOrExit(std::istream &IS, bool ParseCoverage) { |
| if (!Parse(IS, ParseCoverage)) { |
| Printf("MERGE: failed to parse the control file (unexpected error)\n"); |
| exit(1); |
| } |
| } |
| |
| // The control file example: |
| // |
| // 3 # The number of inputs |
| // 1 # The number of inputs in the first corpus, <= the previous number |
| // file0 |
| // file1 |
| // file2 # One file name per line. |
| // STARTED 0 123 # FileID, file size |
| // FT 0 1 4 6 8 # FileID COV1 COV2 ... |
| // COV 0 7 8 9 # FileID COV1 COV1 |
| // STARTED 1 456 # If FT is missing, the input crashed while processing. |
| // STARTED 2 567 |
| // FT 2 8 9 |
| // COV 2 11 12 |
| bool Merger::Parse(std::istream &IS, bool ParseCoverage) { |
| LastFailure.clear(); |
| std::string Line; |
| |
| // Parse NumFiles. |
| if (!std::getline(IS, Line, '\n')) return false; |
| std::istringstream L1(Line); |
| size_t NumFiles = 0; |
| L1 >> NumFiles; |
| if (NumFiles == 0 || NumFiles > 10000000) return false; |
| |
| // Parse NumFilesInFirstCorpus. |
| if (!std::getline(IS, Line, '\n')) return false; |
| std::istringstream L2(Line); |
| NumFilesInFirstCorpus = NumFiles + 1; |
| L2 >> NumFilesInFirstCorpus; |
| if (NumFilesInFirstCorpus > NumFiles) return false; |
| |
| // Parse file names. |
| Files.resize(NumFiles); |
| for (size_t i = 0; i < NumFiles; i++) |
| if (!std::getline(IS, Files[i].Name, '\n')) |
| return false; |
| |
| // Parse STARTED, FT, and COV lines. |
| size_t ExpectedStartMarker = 0; |
| const size_t kInvalidStartMarker = -1; |
| size_t LastSeenStartMarker = kInvalidStartMarker; |
| std::vector<uint32_t> TmpFeatures; |
| std::set<uint32_t> PCs; |
| while (std::getline(IS, Line, '\n')) { |
| std::istringstream ISS1(Line); |
| std::string Marker; |
| uint32_t N; |
| if (!(ISS1 >> Marker) || !(ISS1 >> N)) |
| return false; |
| if (Marker == "STARTED") { |
| // STARTED FILE_ID FILE_SIZE |
| if (ExpectedStartMarker != N) |
| return false; |
| ISS1 >> Files[ExpectedStartMarker].Size; |
| LastSeenStartMarker = ExpectedStartMarker; |
| assert(ExpectedStartMarker < Files.size()); |
| ExpectedStartMarker++; |
| } else if (Marker == "FT") { |
| // FT FILE_ID COV1 COV2 COV3 ... |
| size_t CurrentFileIdx = N; |
| if (CurrentFileIdx != LastSeenStartMarker) |
| return false; |
| LastSeenStartMarker = kInvalidStartMarker; |
| if (ParseCoverage) { |
| TmpFeatures.clear(); // use a vector from outer scope to avoid resizes. |
| while (ISS1 >> N) |
| TmpFeatures.push_back(N); |
| std::sort(TmpFeatures.begin(), TmpFeatures.end()); |
| Files[CurrentFileIdx].Features = TmpFeatures; |
| } |
| } else if (Marker == "COV") { |
| size_t CurrentFileIdx = N; |
| if (ParseCoverage) |
| while (ISS1 >> N) |
| if (PCs.insert(N).second) |
| Files[CurrentFileIdx].Cov.push_back(N); |
| } else { |
| return false; |
| } |
| } |
| if (LastSeenStartMarker != kInvalidStartMarker) |
| LastFailure = Files[LastSeenStartMarker].Name; |
| |
| FirstNotProcessedFile = ExpectedStartMarker; |
| return true; |
| } |
| |
| size_t Merger::ApproximateMemoryConsumption() const { |
| size_t Res = 0; |
| for (const auto &F: Files) |
| Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]); |
| return Res; |
| } |
| |
| // Decides which files need to be merged (add those to NewFiles). |
| // Returns the number of new features added. |
| size_t Merger::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) { |
| NewFiles->clear(); |
| NewFeatures->clear(); |
| NewCov->clear(); |
| assert(NumFilesInFirstCorpus <= Files.size()); |
| std::set<uint32_t> AllFeatures = InitialFeatures; |
| |
| // What features are in the initial corpus? |
| for (size_t i = 0; i < NumFilesInFirstCorpus; i++) { |
| auto &Cur = Files[i].Features; |
| AllFeatures.insert(Cur.begin(), Cur.end()); |
| } |
| // Remove all features that we already know from all other inputs. |
| for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) { |
| auto &Cur = Files[i].Features; |
| std::vector<uint32_t> Tmp; |
| std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(), |
| AllFeatures.end(), std::inserter(Tmp, Tmp.begin())); |
| Cur.swap(Tmp); |
| } |
| |
| // Sort. Give preference to |
| // * smaller files |
| // * files with more features. |
| std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(), |
| [&](const MergeFileInfo &a, const MergeFileInfo &b) -> bool { |
| if (a.Size != b.Size) |
| return a.Size < b.Size; |
| return a.Features.size() > b.Features.size(); |
| }); |
| |
| // One greedy pass: add the file's features to AllFeatures. |
| // If new features were added, add this file to NewFiles. |
| for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) { |
| auto &Cur = Files[i].Features; |
| // Printf("%s -> sz %zd ft %zd\n", Files[i].Name.c_str(), |
| // Files[i].Size, Cur.size()); |
| bool FoundNewFeatures = false; |
| for (auto Fe: Cur) { |
| if (AllFeatures.insert(Fe).second) { |
| FoundNewFeatures = true; |
| NewFeatures->insert(Fe); |
| } |
| } |
| if (FoundNewFeatures) |
| NewFiles->push_back(Files[i].Name); |
| for (auto Cov : Files[i].Cov) |
| if (InitialCov.find(Cov) == InitialCov.end()) |
| NewCov->insert(Cov); |
| } |
| return NewFeatures->size(); |
| } |
| |
| std::set<uint32_t> Merger::AllFeatures() const { |
| std::set<uint32_t> S; |
| for (auto &File : Files) |
| S.insert(File.Features.begin(), File.Features.end()); |
| return S; |
| } |
| |
| // Inner process. May crash if the target crashes. |
| void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath, |
| bool IsSetCoverMerge) { |
| Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str()); |
| Merger M; |
| std::ifstream IF(CFPath); |
| M.ParseOrExit(IF, false); |
| IF.close(); |
| if (!M.LastFailure.empty()) |
| Printf("MERGE-INNER: '%s' caused a failure at the previous merge step\n", |
| M.LastFailure.c_str()); |
| |
| Printf("MERGE-INNER: %zd total files;" |
| " %zd processed earlier; will process %zd files now\n", |
| M.Files.size(), M.FirstNotProcessedFile, |
| M.Files.size() - M.FirstNotProcessedFile); |
| |
| std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app); |
| std::set<size_t> AllFeatures; |
| auto PrintStatsWrapper = [this, &AllFeatures](const char* Where) { |
| this->PrintStats(Where, "\n", 0, AllFeatures.size()); |
| }; |
| std::set<const TracePC::PCTableEntry *> AllPCs; |
| for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) { |
| Fuzzer::MaybeExitGracefully(); |
| auto U = FileToVector(M.Files[i].Name); |
| if (U.size() > MaxInputLen) { |
| U.resize(MaxInputLen); |
| U.shrink_to_fit(); |
| } |
| |
| // Write the pre-run marker. |
| OF << "STARTED " << i << " " << U.size() << "\n"; |
| OF.flush(); // Flush is important since Command::Execute may crash. |
| // Run. |
| TPC.ResetMaps(); |
| ExecuteCallback(U.data(), U.size()); |
| // Collect coverage. We are iterating over the files in this order: |
| // * First, files in the initial corpus ordered by size, smallest first. |
| // * Then, all other files, smallest first. |
| std::set<size_t> Features; |
| if (IsSetCoverMerge) |
| TPC.CollectFeatures([&](size_t Feature) { Features.insert(Feature); }); |
| else |
| TPC.CollectFeatures([&](size_t Feature) { |
| if (AllFeatures.insert(Feature).second) |
| Features.insert(Feature); |
| }); |
| TPC.UpdateObservedPCs(); |
| // Show stats. |
| if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1))) |
| PrintStatsWrapper("pulse "); |
| if (TotalNumberOfRuns == M.NumFilesInFirstCorpus) |
| PrintStatsWrapper("LOADED"); |
| // Write the post-run marker and the coverage. |
| OF << "FT " << i; |
| for (size_t F : Features) |
| OF << " " << F; |
| OF << "\n"; |
| OF << "COV " << i; |
| TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) { |
| if (AllPCs.insert(TE).second) |
| OF << " " << TPC.PCTableEntryIdx(TE); |
| }); |
| OF << "\n"; |
| OF.flush(); |
| } |
| PrintStatsWrapper("DONE "); |
| } |
| |
| // Merges all corpora into the first corpus. A file is added into |
| // the first corpus only if it adds new features. Unlike `Merger::Merge`, |
| // this implementation calculates an approximation of the minimum set |
| // of corpora files, that cover all known features (set cover problem). |
| // Generally, this means that files with more features are preferred for |
| // merge into the first corpus. When two files have the same number of |
| // features, the smaller one is preferred. |
| size_t Merger::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) { |
| assert(NumFilesInFirstCorpus <= Files.size()); |
| NewFiles->clear(); |
| NewFeatures->clear(); |
| NewCov->clear(); |
| std::set<uint32_t> AllFeatures; |
| // 1 << 21 - 1 is the maximum feature index. |
| // See 'kFeatureSetSize' in 'FuzzerCorpus.h'. |
| const uint32_t kFeatureSetSize = 1 << 21; |
| std::vector<bool> Covered(kFeatureSetSize, false); |
| size_t NumCovered = 0; |
| |
| std::set<uint32_t> ExistingFeatures = InitialFeatures; |
| for (size_t i = 0; i < NumFilesInFirstCorpus; ++i) |
| ExistingFeatures.insert(Files[i].Features.begin(), Files[i].Features.end()); |
| |
| // Mark the existing features as covered. |
| for (const auto &F : ExistingFeatures) { |
| if (!Covered[F % kFeatureSetSize]) { |
| ++NumCovered; |
| Covered[F % kFeatureSetSize] = true; |
| } |
| // Calculate an underestimation of the set of covered features |
| // since the `Covered` bitvector is smaller than the feature range. |
| AllFeatures.insert(F % kFeatureSetSize); |
| } |
| |
| std::set<size_t> RemainingFiles; |
| for (size_t i = NumFilesInFirstCorpus; i < Files.size(); ++i) { |
| // Construct an incremental sequence which represent the |
| // indices to all files (excluding those in the initial corpus). |
| // RemainingFiles = range(NumFilesInFirstCorpus..Files.size()). |
| RemainingFiles.insert(i); |
| // Insert this file's unique features to all features. |
| for (const auto &F : Files[i].Features) |
| AllFeatures.insert(F % kFeatureSetSize); |
| } |
| |
| // Integrate files into Covered until set is complete. |
| while (NumCovered != AllFeatures.size()) { |
| // Index to file with largest number of unique features. |
| size_t MaxFeaturesIndex = NumFilesInFirstCorpus; |
| // Indices to remove from RemainingFiles. |
| std::set<size_t> RemoveIndices; |
| // Running max unique feature count. |
| // Updated upon finding a file with more features. |
| size_t MaxNumFeatures = 0; |
| |
| // Iterate over all files not yet integrated into Covered, |
| // to find the file which has the largest number of |
| // features that are not already in Covered. |
| for (const auto &i : RemainingFiles) { |
| const auto &File = Files[i]; |
| size_t CurrentUnique = 0; |
| // Count number of features in this file |
| // which are not yet in Covered. |
| for (const auto &F : File.Features) |
| if (!Covered[F % kFeatureSetSize]) |
| ++CurrentUnique; |
| |
| if (CurrentUnique == 0) { |
| // All features in this file are already in Covered: skip next time. |
| RemoveIndices.insert(i); |
| } else if (CurrentUnique > MaxNumFeatures || |
| (CurrentUnique == MaxNumFeatures && |
| File.Size < Files[MaxFeaturesIndex].Size)) { |
| // Update the max features file based on unique features |
| // Break ties by selecting smaller files. |
| MaxNumFeatures = CurrentUnique; |
| MaxFeaturesIndex = i; |
| } |
| } |
| // Must be a valid index/ |
| assert(MaxFeaturesIndex < Files.size()); |
| // Remove any feature-less files found. |
| for (const auto &i : RemoveIndices) |
| RemainingFiles.erase(i); |
| if (MaxNumFeatures == 0) { |
| // Did not find a file that adds unique features. |
| // This means that we should have no remaining files. |
| assert(RemainingFiles.size() == 0); |
| assert(NumCovered == AllFeatures.size()); |
| break; |
| } |
| |
| // MaxFeaturesIndex must be an element of Remaining. |
| assert(RemainingFiles.find(MaxFeaturesIndex) != RemainingFiles.end()); |
| // Remove the file with the most features from Remaining. |
| RemainingFiles.erase(MaxFeaturesIndex); |
| const auto &MaxFeatureFile = Files[MaxFeaturesIndex]; |
| // Add the features of the max feature file to Covered. |
| for (const auto &F : MaxFeatureFile.Features) { |
| if (!Covered[F % kFeatureSetSize]) { |
| ++NumCovered; |
| Covered[F % kFeatureSetSize] = true; |
| NewFeatures->insert(F); |
| } |
| } |
| // Add the index to this file to the result. |
| NewFiles->push_back(MaxFeatureFile.Name); |
| // Update NewCov with the additional coverage |
| // that MaxFeatureFile provides. |
| for (const auto &C : MaxFeatureFile.Cov) |
| if (InitialCov.find(C) == InitialCov.end()) |
| NewCov->insert(C); |
| } |
| |
| return NewFeatures->size(); |
| } |
| |
| static size_t |
| WriteNewControlFile(const std::string &CFPath, |
| const std::vector<SizedFile> &OldCorpus, |
| const std::vector<SizedFile> &NewCorpus, |
| const std::vector<MergeFileInfo> &KnownFiles) { |
| std::unordered_set<std::string> FilesToSkip; |
| for (auto &SF: KnownFiles) |
| FilesToSkip.insert(SF.Name); |
| |
| std::vector<std::string> FilesToUse; |
| auto MaybeUseFile = [=, &FilesToUse](std::string Name) { |
| if (FilesToSkip.find(Name) == FilesToSkip.end()) |
| FilesToUse.push_back(Name); |
| }; |
| for (auto &SF: OldCorpus) |
| MaybeUseFile(SF.File); |
| auto FilesToUseFromOldCorpus = FilesToUse.size(); |
| for (auto &SF: NewCorpus) |
| MaybeUseFile(SF.File); |
| |
| RemoveFile(CFPath); |
| std::ofstream ControlFile(CFPath); |
| ControlFile << FilesToUse.size() << "\n"; |
| ControlFile << FilesToUseFromOldCorpus << "\n"; |
| for (auto &FN: FilesToUse) |
| ControlFile << FN << "\n"; |
| |
| if (!ControlFile) { |
| Printf("MERGE-OUTER: failed to write to the control file: %s\n", |
| CFPath.c_str()); |
| exit(1); |
| } |
| |
| return FilesToUse.size(); |
| } |
| |
| // Outer process. Does not call the target code and thus should not fail. |
| void 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, /*Verbose*/ |
| bool IsSetCoverMerge) { |
| if (NewCorpus.empty() && OldCorpus.empty()) return; // Nothing to merge. |
| size_t NumAttempts = 0; |
| std::vector<MergeFileInfo> KnownFiles; |
| if (FileSize(CFPath)) { |
| VPrintf(V, "MERGE-OUTER: non-empty control file provided: '%s'\n", |
| CFPath.c_str()); |
| Merger M; |
| std::ifstream IF(CFPath); |
| if (M.Parse(IF, /*ParseCoverage=*/true)) { |
| VPrintf(V, "MERGE-OUTER: control file ok, %zd files total," |
| " first not processed file %zd\n", |
| M.Files.size(), M.FirstNotProcessedFile); |
| if (!M.LastFailure.empty()) |
| VPrintf(V, "MERGE-OUTER: '%s' will be skipped as unlucky " |
| "(merge has stumbled on it the last time)\n", |
| M.LastFailure.c_str()); |
| if (M.FirstNotProcessedFile >= M.Files.size()) { |
| // Merge has already been completed with the given merge control file. |
| if (M.Files.size() == OldCorpus.size() + NewCorpus.size()) { |
| VPrintf( |
| V, |
| "MERGE-OUTER: nothing to do, merge has been completed before\n"); |
| exit(0); |
| } |
| |
| // Number of input files likely changed, start merge from scratch, but |
| // reuse coverage information from the given merge control file. |
| VPrintf( |
| V, |
| "MERGE-OUTER: starting merge from scratch, but reusing coverage " |
| "information from the given control file\n"); |
| KnownFiles = M.Files; |
| } else { |
| // There is a merge in progress, continue. |
| NumAttempts = M.Files.size() - M.FirstNotProcessedFile; |
| } |
| } else { |
| VPrintf(V, "MERGE-OUTER: bad control file, will overwrite it\n"); |
| } |
| } |
| |
| if (!NumAttempts) { |
| // The supplied control file is empty or bad, create a fresh one. |
| VPrintf(V, "MERGE-OUTER: " |
| "%zd files, %zd in the initial corpus, %zd processed earlier\n", |
| OldCorpus.size() + NewCorpus.size(), OldCorpus.size(), |
| KnownFiles.size()); |
| NumAttempts = WriteNewControlFile(CFPath, OldCorpus, NewCorpus, KnownFiles); |
| } |
| |
| // Execute the inner process until it passes. |
| // Every inner process should execute at least one input. |
| Command BaseCmd(Args); |
| BaseCmd.removeFlag("merge"); |
| BaseCmd.removeFlag("set_cover_merge"); |
| BaseCmd.removeFlag("fork"); |
| BaseCmd.removeFlag("collect_data_flow"); |
| for (size_t Attempt = 1; Attempt <= NumAttempts; Attempt++) { |
| Fuzzer::MaybeExitGracefully(); |
| VPrintf(V, "MERGE-OUTER: attempt %zd\n", Attempt); |
| Command Cmd(BaseCmd); |
| Cmd.addFlag("merge_control_file", CFPath); |
| // If we are going to use the set cover implementation for |
| // minimization add the merge_inner=2 internal flag. |
| Cmd.addFlag("merge_inner", IsSetCoverMerge ? "2" : "1"); |
| if (!V) { |
| Cmd.setOutputFile(getDevNull()); |
| Cmd.combineOutAndErr(); |
| } |
| auto ExitCode = ExecuteCommand(Cmd); |
| if (!ExitCode) { |
| VPrintf(V, "MERGE-OUTER: successful in %zd attempt(s)\n", Attempt); |
| break; |
| } |
| } |
| // Read the control file and do the merge. |
| Merger M; |
| std::ifstream IF(CFPath); |
| IF.seekg(0, IF.end); |
| VPrintf(V, "MERGE-OUTER: the control file has %zd bytes\n", |
| (size_t)IF.tellg()); |
| IF.seekg(0, IF.beg); |
| M.ParseOrExit(IF, true); |
| IF.close(); |
| VPrintf(V, |
| "MERGE-OUTER: consumed %zdMb (%zdMb rss) to parse the control file\n", |
| M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb()); |
| |
| M.Files.insert(M.Files.end(), KnownFiles.begin(), KnownFiles.end()); |
| if (IsSetCoverMerge) |
| M.SetCoverMerge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles); |
| else |
| M.Merge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles); |
| VPrintf(V, "MERGE-OUTER: %zd new files with %zd new features added; " |
| "%zd new coverage edges\n", |
| NewFiles->size(), NewFeatures->size(), NewCov->size()); |
| } |
| |
| } // namespace fuzzer |