540 lines · cpp
1//===- FuzzerMerge.cpp - merging corpora ----------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8// Merging corpora.9//===----------------------------------------------------------------------===//10 11#include "FuzzerCommand.h"12#include "FuzzerMerge.h"13#include "FuzzerIO.h"14#include "FuzzerInternal.h"15#include "FuzzerTracePC.h"16#include "FuzzerUtil.h"17 18#include <fstream>19#include <iterator>20#include <set>21#include <sstream>22#include <unordered_set>23 24namespace fuzzer {25 26bool Merger::Parse(const std::string &Str, bool ParseCoverage) {27 std::istringstream SS(Str);28 return Parse(SS, ParseCoverage);29}30 31void Merger::ParseOrExit(std::istream &IS, bool ParseCoverage) {32 if (!Parse(IS, ParseCoverage)) {33 Printf("MERGE: failed to parse the control file (unexpected error)\n");34 exit(1);35 }36}37 38// The control file example:39//40// 3 # The number of inputs41// 1 # The number of inputs in the first corpus, <= the previous number42// file043// file144// file2 # One file name per line.45// STARTED 0 123 # FileID, file size46// FT 0 1 4 6 8 # FileID COV1 COV2 ...47// COV 0 7 8 9 # FileID COV1 COV148// STARTED 1 456 # If FT is missing, the input crashed while processing.49// STARTED 2 56750// FT 2 8 951// COV 2 11 1252bool Merger::Parse(std::istream &IS, bool ParseCoverage) {53 LastFailure.clear();54 std::string Line;55 56 // Parse NumFiles.57 if (!std::getline(IS, Line, '\n')) return false;58 std::istringstream L1(Line);59 size_t NumFiles = 0;60 L1 >> NumFiles;61 if (NumFiles == 0 || NumFiles > 10000000) return false;62 63 // Parse NumFilesInFirstCorpus.64 if (!std::getline(IS, Line, '\n')) return false;65 std::istringstream L2(Line);66 NumFilesInFirstCorpus = NumFiles + 1;67 L2 >> NumFilesInFirstCorpus;68 if (NumFilesInFirstCorpus > NumFiles) return false;69 70 // Parse file names.71 Files.resize(NumFiles);72 for (size_t i = 0; i < NumFiles; i++)73 if (!std::getline(IS, Files[i].Name, '\n'))74 return false;75 76 // Parse STARTED, FT, and COV lines.77 size_t ExpectedStartMarker = 0;78 const size_t kInvalidStartMarker = -1;79 size_t LastSeenStartMarker = kInvalidStartMarker;80 bool HaveFtMarker = true;81 std::vector<uint32_t> TmpFeatures;82 std::set<uint32_t> PCs;83 while (std::getline(IS, Line, '\n')) {84 std::istringstream ISS1(Line);85 std::string Marker;86 uint32_t N;87 if (!(ISS1 >> Marker) || !(ISS1 >> N))88 return false;89 if (Marker == "STARTED") {90 // STARTED FILE_ID FILE_SIZE91 if (ExpectedStartMarker != N)92 return false;93 ISS1 >> Files[ExpectedStartMarker].Size;94 LastSeenStartMarker = ExpectedStartMarker;95 assert(ExpectedStartMarker < Files.size());96 ExpectedStartMarker++;97 HaveFtMarker = false;98 } else if (Marker == "FT") {99 // FT FILE_ID COV1 COV2 COV3 ...100 size_t CurrentFileIdx = N;101 if (CurrentFileIdx != LastSeenStartMarker)102 return false;103 HaveFtMarker = true;104 if (ParseCoverage) {105 TmpFeatures.clear(); // use a vector from outer scope to avoid resizes.106 while (ISS1 >> N)107 TmpFeatures.push_back(N);108 std::sort(TmpFeatures.begin(), TmpFeatures.end());109 Files[CurrentFileIdx].Features = TmpFeatures;110 }111 } else if (Marker == "COV") {112 size_t CurrentFileIdx = N;113 if (CurrentFileIdx != LastSeenStartMarker)114 return false;115 if (ParseCoverage)116 while (ISS1 >> N)117 if (PCs.insert(N).second)118 Files[CurrentFileIdx].Cov.push_back(N);119 } else {120 return false;121 }122 }123 if (!HaveFtMarker && LastSeenStartMarker != kInvalidStartMarker)124 LastFailure = Files[LastSeenStartMarker].Name;125 126 FirstNotProcessedFile = ExpectedStartMarker;127 return true;128}129 130size_t Merger::ApproximateMemoryConsumption() const {131 size_t Res = 0;132 for (const auto &F: Files)133 Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]);134 return Res;135}136 137// Decides which files need to be merged (add those to NewFiles).138// Returns the number of new features added.139size_t Merger::Merge(const std::set<uint32_t> &InitialFeatures,140 std::set<uint32_t> *NewFeatures,141 const std::set<uint32_t> &InitialCov,142 std::set<uint32_t> *NewCov,143 std::vector<std::string> *NewFiles) {144 NewFiles->clear();145 NewFeatures->clear();146 NewCov->clear();147 assert(NumFilesInFirstCorpus <= Files.size());148 std::set<uint32_t> AllFeatures = InitialFeatures;149 150 // What features are in the initial corpus?151 for (size_t i = 0; i < NumFilesInFirstCorpus; i++) {152 auto &Cur = Files[i].Features;153 AllFeatures.insert(Cur.begin(), Cur.end());154 }155 // Remove all features that we already know from all other inputs.156 for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {157 auto &Cur = Files[i].Features;158 std::vector<uint32_t> Tmp;159 std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(),160 AllFeatures.end(), std::inserter(Tmp, Tmp.begin()));161 Cur.swap(Tmp);162 }163 164 // Sort. Give preference to165 // * smaller files166 // * files with more features.167 std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(),168 [&](const MergeFileInfo &a, const MergeFileInfo &b) -> bool {169 if (a.Size != b.Size)170 return a.Size < b.Size;171 return a.Features.size() > b.Features.size();172 });173 174 // One greedy pass: add the file's features to AllFeatures.175 // If new features were added, add this file to NewFiles.176 for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {177 auto &Cur = Files[i].Features;178 // Printf("%s -> sz %zd ft %zd\n", Files[i].Name.c_str(),179 // Files[i].Size, Cur.size());180 bool FoundNewFeatures = false;181 for (auto Fe: Cur) {182 if (AllFeatures.insert(Fe).second) {183 FoundNewFeatures = true;184 NewFeatures->insert(Fe);185 }186 }187 if (FoundNewFeatures)188 NewFiles->push_back(Files[i].Name);189 for (auto Cov : Files[i].Cov)190 if (InitialCov.find(Cov) == InitialCov.end())191 NewCov->insert(Cov);192 }193 return NewFeatures->size();194}195 196std::set<uint32_t> Merger::AllFeatures() const {197 std::set<uint32_t> S;198 for (auto &File : Files)199 S.insert(File.Features.begin(), File.Features.end());200 return S;201}202 203// Inner process. May crash if the target crashes.204void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath,205 bool IsSetCoverMerge) {206 Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str());207 Merger M;208 std::ifstream IF(CFPath);209 M.ParseOrExit(IF, false);210 IF.close();211 if (!M.LastFailure.empty())212 Printf("MERGE-INNER: '%s' caused a failure at the previous merge step\n",213 M.LastFailure.c_str());214 215 Printf("MERGE-INNER: %zd total files;"216 " %zd processed earlier; will process %zd files now\n",217 M.Files.size(), M.FirstNotProcessedFile,218 M.Files.size() - M.FirstNotProcessedFile);219 220 std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app);221 std::set<size_t> AllFeatures;222 auto PrintStatsWrapper = [this, &AllFeatures](const char* Where) {223 this->PrintStats(Where, "\n", 0, AllFeatures.size());224 };225 std::set<const TracePC::PCTableEntry *> AllPCs;226 for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {227 Fuzzer::MaybeExitGracefully();228 auto U = FileToVector(M.Files[i].Name);229 if (U.size() > MaxInputLen) {230 U.resize(MaxInputLen);231 U.shrink_to_fit();232 }233 234 // Write the pre-run marker.235 OF << "STARTED " << i << " " << U.size() << "\n";236 OF.flush(); // Flush is important since Command::Execute may crash.237 // Run.238 TPC.ResetMaps();239 ExecuteCallback(U.data(), U.size());240 // Collect coverage. We are iterating over the files in this order:241 // * First, files in the initial corpus ordered by size, smallest first.242 // * Then, all other files, smallest first.243 std::set<size_t> Features;244 if (IsSetCoverMerge)245 TPC.CollectFeatures([&](size_t Feature) { Features.insert(Feature); });246 else247 TPC.CollectFeatures([&](size_t Feature) {248 if (AllFeatures.insert(Feature).second)249 Features.insert(Feature);250 });251 TPC.UpdateObservedPCs();252 // Show stats.253 if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))254 PrintStatsWrapper("pulse ");255 if (TotalNumberOfRuns == M.NumFilesInFirstCorpus)256 PrintStatsWrapper("LOADED");257 // Write the post-run marker and the coverage.258 OF << "FT " << i;259 for (size_t F : Features)260 OF << " " << F;261 OF << "\n";262 OF << "COV " << i;263 TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) {264 if (AllPCs.insert(TE).second)265 OF << " " << TPC.PCTableEntryIdx(TE);266 });267 OF << "\n";268 OF.flush();269 }270 PrintStatsWrapper("DONE ");271}272 273// Merges all corpora into the first corpus. A file is added into274// the first corpus only if it adds new features. Unlike `Merger::Merge`,275// this implementation calculates an approximation of the minimum set276// of corpora files, that cover all known features (set cover problem).277// Generally, this means that files with more features are preferred for278// merge into the first corpus. When two files have the same number of279// features, the smaller one is preferred.280size_t Merger::SetCoverMerge(const std::set<uint32_t> &InitialFeatures,281 std::set<uint32_t> *NewFeatures,282 const std::set<uint32_t> &InitialCov,283 std::set<uint32_t> *NewCov,284 std::vector<std::string> *NewFiles) {285 assert(NumFilesInFirstCorpus <= Files.size());286 NewFiles->clear();287 NewFeatures->clear();288 NewCov->clear();289 std::set<uint32_t> AllFeatures;290 // 1 << 21 - 1 is the maximum feature index.291 // See 'kFeatureSetSize' in 'FuzzerCorpus.h'.292 const uint32_t kFeatureSetSize = 1 << 21;293 std::vector<bool> Covered(kFeatureSetSize, false);294 size_t NumCovered = 0;295 296 std::set<uint32_t> ExistingFeatures = InitialFeatures;297 for (size_t i = 0; i < NumFilesInFirstCorpus; ++i)298 ExistingFeatures.insert(Files[i].Features.begin(), Files[i].Features.end());299 300 // Mark the existing features as covered.301 for (const auto &F : ExistingFeatures) {302 if (!Covered[F % kFeatureSetSize]) {303 ++NumCovered;304 Covered[F % kFeatureSetSize] = true;305 }306 // Calculate an underestimation of the set of covered features307 // since the `Covered` bitvector is smaller than the feature range.308 AllFeatures.insert(F % kFeatureSetSize);309 }310 311 std::set<size_t> RemainingFiles;312 for (size_t i = NumFilesInFirstCorpus; i < Files.size(); ++i) {313 // Construct an incremental sequence which represent the314 // indices to all files (excluding those in the initial corpus).315 // RemainingFiles = range(NumFilesInFirstCorpus..Files.size()).316 RemainingFiles.insert(i);317 // Insert this file's unique features to all features.318 for (const auto &F : Files[i].Features)319 AllFeatures.insert(F % kFeatureSetSize);320 }321 322 // Integrate files into Covered until set is complete.323 while (NumCovered != AllFeatures.size()) {324 // Index to file with largest number of unique features.325 size_t MaxFeaturesIndex = NumFilesInFirstCorpus;326 // Indices to remove from RemainingFiles.327 std::set<size_t> RemoveIndices;328 // Running max unique feature count.329 // Updated upon finding a file with more features.330 size_t MaxNumFeatures = 0;331 332 // Iterate over all files not yet integrated into Covered,333 // to find the file which has the largest number of334 // features that are not already in Covered.335 for (const auto &i : RemainingFiles) {336 const auto &File = Files[i];337 size_t CurrentUnique = 0;338 // Count number of features in this file339 // which are not yet in Covered.340 for (const auto &F : File.Features)341 if (!Covered[F % kFeatureSetSize])342 ++CurrentUnique;343 344 if (CurrentUnique == 0) {345 // All features in this file are already in Covered: skip next time.346 RemoveIndices.insert(i);347 } else if (CurrentUnique > MaxNumFeatures ||348 (CurrentUnique == MaxNumFeatures &&349 File.Size < Files[MaxFeaturesIndex].Size)) {350 // Update the max features file based on unique features351 // Break ties by selecting smaller files.352 MaxNumFeatures = CurrentUnique;353 MaxFeaturesIndex = i;354 }355 }356 // Must be a valid index/357 assert(MaxFeaturesIndex < Files.size());358 // Remove any feature-less files found.359 for (const auto &i : RemoveIndices)360 RemainingFiles.erase(i);361 if (MaxNumFeatures == 0) {362 // Did not find a file that adds unique features.363 // This means that we should have no remaining files.364 assert(RemainingFiles.size() == 0);365 assert(NumCovered == AllFeatures.size());366 break;367 }368 369 // MaxFeaturesIndex must be an element of Remaining.370 assert(RemainingFiles.find(MaxFeaturesIndex) != RemainingFiles.end());371 // Remove the file with the most features from Remaining.372 RemainingFiles.erase(MaxFeaturesIndex);373 const auto &MaxFeatureFile = Files[MaxFeaturesIndex];374 // Add the features of the max feature file to Covered.375 for (const auto &F : MaxFeatureFile.Features) {376 if (!Covered[F % kFeatureSetSize]) {377 ++NumCovered;378 Covered[F % kFeatureSetSize] = true;379 NewFeatures->insert(F);380 }381 }382 // Add the index to this file to the result.383 NewFiles->push_back(MaxFeatureFile.Name);384 // Update NewCov with the additional coverage385 // that MaxFeatureFile provides.386 for (const auto &C : MaxFeatureFile.Cov)387 if (InitialCov.find(C) == InitialCov.end())388 NewCov->insert(C);389 }390 391 return NewFeatures->size();392}393 394static size_t395WriteNewControlFile(const std::string &CFPath,396 const std::vector<SizedFile> &OldCorpus,397 const std::vector<SizedFile> &NewCorpus,398 const std::vector<MergeFileInfo> &KnownFiles) {399 std::unordered_set<std::string> FilesToSkip;400 for (auto &SF: KnownFiles)401 FilesToSkip.insert(SF.Name);402 403 std::vector<std::string> FilesToUse;404 auto MaybeUseFile = [=, &FilesToUse](std::string Name) {405 if (FilesToSkip.find(Name) == FilesToSkip.end())406 FilesToUse.push_back(Name);407 };408 for (auto &SF: OldCorpus)409 MaybeUseFile(SF.File);410 auto FilesToUseFromOldCorpus = FilesToUse.size();411 for (auto &SF: NewCorpus)412 MaybeUseFile(SF.File);413 414 RemoveFile(CFPath);415 std::ofstream ControlFile(CFPath);416 ControlFile << FilesToUse.size() << "\n";417 ControlFile << FilesToUseFromOldCorpus << "\n";418 for (auto &FN: FilesToUse)419 ControlFile << FN << "\n";420 421 if (!ControlFile) {422 Printf("MERGE-OUTER: failed to write to the control file: %s\n",423 CFPath.c_str());424 exit(1);425 }426 427 return FilesToUse.size();428}429 430// Outer process. Does not call the target code and thus should not fail.431void CrashResistantMerge(const std::vector<std::string> &Args,432 const std::vector<SizedFile> &OldCorpus,433 const std::vector<SizedFile> &NewCorpus,434 std::vector<std::string> *NewFiles,435 const std::set<uint32_t> &InitialFeatures,436 std::set<uint32_t> *NewFeatures,437 const std::set<uint32_t> &InitialCov,438 std::set<uint32_t> *NewCov, const std::string &CFPath,439 bool V, /*Verbose*/440 bool IsSetCoverMerge) {441 if (NewCorpus.empty() && OldCorpus.empty()) return; // Nothing to merge.442 size_t NumAttempts = 0;443 std::vector<MergeFileInfo> KnownFiles;444 if (FileSize(CFPath)) {445 VPrintf(V, "MERGE-OUTER: non-empty control file provided: '%s'\n",446 CFPath.c_str());447 Merger M;448 std::ifstream IF(CFPath);449 if (M.Parse(IF, /*ParseCoverage=*/true)) {450 VPrintf(V, "MERGE-OUTER: control file ok, %zd files total,"451 " first not processed file %zd\n",452 M.Files.size(), M.FirstNotProcessedFile);453 if (!M.LastFailure.empty())454 VPrintf(V, "MERGE-OUTER: '%s' will be skipped as unlucky "455 "(merge has stumbled on it the last time)\n",456 M.LastFailure.c_str());457 if (M.FirstNotProcessedFile >= M.Files.size()) {458 // Merge has already been completed with the given merge control file.459 if (M.Files.size() == OldCorpus.size() + NewCorpus.size()) {460 VPrintf(461 V,462 "MERGE-OUTER: nothing to do, merge has been completed before\n");463 exit(0);464 }465 466 // Number of input files likely changed, start merge from scratch, but467 // reuse coverage information from the given merge control file.468 VPrintf(469 V,470 "MERGE-OUTER: starting merge from scratch, but reusing coverage "471 "information from the given control file\n");472 KnownFiles = M.Files;473 } else {474 // There is a merge in progress, continue.475 NumAttempts = M.Files.size() - M.FirstNotProcessedFile;476 }477 } else {478 VPrintf(V, "MERGE-OUTER: bad control file, will overwrite it\n");479 }480 }481 482 if (!NumAttempts) {483 // The supplied control file is empty or bad, create a fresh one.484 VPrintf(V, "MERGE-OUTER: "485 "%zd files, %zd in the initial corpus, %zd processed earlier\n",486 OldCorpus.size() + NewCorpus.size(), OldCorpus.size(),487 KnownFiles.size());488 NumAttempts = WriteNewControlFile(CFPath, OldCorpus, NewCorpus, KnownFiles);489 }490 491 // Execute the inner process until it passes.492 // Every inner process should execute at least one input.493 Command BaseCmd(Args);494 BaseCmd.removeFlag("merge");495 BaseCmd.removeFlag("set_cover_merge");496 BaseCmd.removeFlag("fork");497 BaseCmd.removeFlag("collect_data_flow");498 for (size_t Attempt = 1; Attempt <= NumAttempts; Attempt++) {499 Fuzzer::MaybeExitGracefully();500 VPrintf(V, "MERGE-OUTER: attempt %zd\n", Attempt);501 Command Cmd(BaseCmd);502 Cmd.addFlag("merge_control_file", CFPath);503 // If we are going to use the set cover implementation for504 // minimization add the merge_inner=2 internal flag.505 Cmd.addFlag("merge_inner", IsSetCoverMerge ? "2" : "1");506 if (!V) {507 Cmd.setOutputFile(getDevNull());508 Cmd.combineOutAndErr();509 }510 auto ExitCode = ExecuteCommand(Cmd);511 if (!ExitCode) {512 VPrintf(V, "MERGE-OUTER: successful in %zd attempt(s)\n", Attempt);513 break;514 }515 }516 // Read the control file and do the merge.517 Merger M;518 std::ifstream IF(CFPath);519 IF.seekg(0, IF.end);520 VPrintf(V, "MERGE-OUTER: the control file has %zd bytes\n",521 (size_t)IF.tellg());522 IF.seekg(0, IF.beg);523 M.ParseOrExit(IF, true);524 IF.close();525 VPrintf(V,526 "MERGE-OUTER: consumed %zdMb (%zdMb rss) to parse the control file\n",527 M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb());528 529 M.Files.insert(M.Files.end(), KnownFiles.begin(), KnownFiles.end());530 if (IsSetCoverMerge)531 M.SetCoverMerge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles);532 else533 M.Merge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles);534 VPrintf(V, "MERGE-OUTER: %zd new files with %zd new features added; "535 "%zd new coverage edges\n",536 NewFiles->size(), NewFeatures->size(), NewCov->size());537}538 539} // namespace fuzzer540