Index: compiler-rt/lib/fuzzer/FuzzerDriver.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerDriver.cpp +++ compiler-rt/lib/fuzzer/FuzzerDriver.cpp @@ -521,7 +521,7 @@ Vector NewFiles; Set NewFeatures, NewCov; CrashResistantMerge(Args, OldCorpus, NewCorpus, &NewFiles, {}, &NewFeatures, - {}, &NewCov, CFPath, true); + {}, &NewCov, CFPath, true, Flags.merge == 2); for (auto &Path : NewFiles) F->WriteToOutputCorpus(FileToVector(Path, Options.MaxLen)); // We are done, delete the control file if it was a temporary one. @@ -877,7 +877,8 @@ if (Options.MaxLen == 0) F->SetMaxInputLen(kDefaultMaxMergeLen); assert(Flags.merge_control_file); - F->CrashResistantMergeInternalStep(Flags.merge_control_file); + F->CrashResistantMergeInternalStep(Flags.merge_control_file, + !strncmp(Flags.merge_inner, "2", 1)); exit(0); } Index: compiler-rt/lib/fuzzer/FuzzerFork.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerFork.cpp +++ compiler-rt/lib/fuzzer/FuzzerFork.cpp @@ -213,8 +213,10 @@ Vector FilesToAdd; Set NewFeatures, NewCov; + bool MergeGreedy = !Job->Cmd.getFlagValue("merge").compare("2"); CrashResistantMerge(Args, {}, MergeCandidates, &FilesToAdd, Features, - &NewFeatures, Cov, &NewCov, Job->CFPath, false); + &NewFeatures, Cov, &NewCov, Job->CFPath, false, + MergeGreedy); for (auto &Path : FilesToAdd) { auto U = FileToVector(Path); auto NewPath = DirPlusFile(MainCorpusDir, Hash(U)); @@ -318,7 +320,7 @@ auto CFPath = DirPlusFile(Env.TempDir, "merge.txt"); Set NewFeatures, NewCov; CrashResistantMerge(Env.Args, {}, SeedFiles, &Env.Files, Env.Features, - &NewFeatures, Env.Cov, &NewCov, CFPath, false); + &NewFeatures, Env.Cov, &NewCov, CFPath, false, false); Env.Features.insert(NewFeatures.begin(), NewFeatures.end()); Env.Cov.insert(NewFeatures.begin(), NewFeatures.end()); RemoveFile(CFPath); Index: compiler-rt/lib/fuzzer/FuzzerInternal.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerInternal.h +++ compiler-rt/lib/fuzzer/FuzzerInternal.h @@ -73,7 +73,8 @@ // Merge Corpora[1:] into Corpora[0]. void Merge(const Vector &Corpora); - void CrashResistantMergeInternalStep(const std::string &ControlFilePath); + void CrashResistantMergeInternalStep(const std::string &ControlFilePath, + bool MergeGreedy); MutationDispatcher &GetMD() { return MD; } void PrintFinalStats(); void SetMaxInputLen(size_t MaxInputLen); Index: compiler-rt/lib/fuzzer/FuzzerMerge.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerMerge.h +++ compiler-rt/lib/fuzzer/FuzzerMerge.h @@ -67,20 +67,20 @@ size_t Merge(const Set &InitialFeatures, Set *NewFeatures, const Set &InitialCov, Set *NewCov, Vector *NewFiles); + size_t MergeGreedy(const Set &InitialFeatures, + Set *NewFeatures, + const Set &InitialCov, Set *NewCov, + Vector *NewFiles); size_t ApproximateMemoryConsumption() const; Set AllFeatures() const; }; -void CrashResistantMerge(const Vector &Args, - const Vector &OldCorpus, - const Vector &NewCorpus, - Vector *NewFiles, - const Set &InitialFeatures, - Set *NewFeatures, - const Set &InitialCov, - Set *NewCov, - const std::string &CFPath, - bool Verbose); +void CrashResistantMerge( + const Vector &Args, const Vector &OldCorpus, + const Vector &NewCorpus, Vector *NewFiles, + const Set &InitialFeatures, Set *NewFeatures, + const Set &InitialCov, Set *NewCov, + const std::string &CFPath, bool Verbose, bool MergeGreedy); } // namespace fuzzer Index: compiler-rt/lib/fuzzer/FuzzerMerge.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerMerge.cpp +++ compiler-rt/lib/fuzzer/FuzzerMerge.cpp @@ -17,6 +17,7 @@ #include #include +#include #include #include #include @@ -195,8 +196,145 @@ return S; } +size_t Merger::MergeGreedy(const Set &InitialFeatures, + Set *NewFeatures, + const Set &InitialCov, + Set *NewCov, + Vector *NewFiles) { + NewFiles->clear(); + NewFeatures->clear(); + NewCov->clear(); + assert(NumFilesInFirstCorpus <= Files.size()); + Set AllFeatures = InitialFeatures; + + // Construct the feature aggregate of all files. + for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) { + AllFeatures.insert(Files[i].Features.begin(), Files[i].Features.end()); + } + + // Construct an incremental sequence which represent the + // indices to all files (excluding those in the initial corpus). + // Remaining = range(NumFilesInFirstCorpus..Files.size()) + Vector Remaining(Files.size() - NumFilesInFirstCorpus); + std::iota(Remaining.begin(), Remaining.end(), NumFilesInFirstCorpus); + + // Sort. Give preference to + // * smaller files + // * files with more features. + std::sort(Remaining.begin(), Remaining.end(), + [&](const size_t A, const size_t B) -> bool { + const MergeFileInfo &a = Files[A]; + const MergeFileInfo &b = Files[B]; + + if (a.Size != b.Size) + return a.Size < b.Size; + + return a.Features.size() > b.Features.size(); + }); + + // 1 << 21 - 1 is the maximum feature index. + // See 'kFeatureSetSize' in 'FuzzerCorpus.h'. + uint32_t kFeatureSetSize = 1 << 21; + Vector Covered(kFeatureSetSize, false); + + size_t CoveredSize = 0; + + for (const auto Feature : InitialFeatures) { + if (!Covered[Feature % kFeatureSetSize]) { + CoveredSize++; + Covered[Feature % kFeatureSetSize] = true; + } + } + + // Integrate files into Covered until set is complete. + while (CoveredSize != AllFeatures.size()) { + // Index to file with largest number of unique features. + size_t MaxFeaturesIndex = 0; + + // Indices to remove from Remaining. + Set 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 : Remaining) { + const auto &Cur = Files[i].Features; + + // This is a file with no features: skip next time. + if (Cur.empty()) { + RemoveIndices.insert(i); + continue; + } + + // Count number of features in this file + // which are not yet in Covered. + size_t CurrentUnique = 0; + for (const auto Feature : Cur) { + if (!Covered[Feature % kFeatureSetSize]) { + CurrentUnique++; + } + } + + if (CurrentUnique == 0) { + // All features in this file are already in Covered: skip next time. + RemoveIndices.insert(i); + } else if (CurrentUnique > MaxNumFeatures) { + MaxNumFeatures = CurrentUnique; + // MaxFeaturesIndex = index to current file. + MaxFeaturesIndex = i; + } + } + } + + // Must be a valid index/ + assert(MaxFeaturesIndex < Files.size()); + + // Must be an element of Remaining. + assert(std::find(Remaining.begin(), Remaining.end(), MaxFeaturesIndex) != + Remaining.end()); + + const auto &MaxFeatureFile = Files[MaxFeaturesIndex]; + + // Add the features of the max feature file to Covered. + for (const auto Feature : MaxFeatureFile.Features) { + if (!Covered[Feature % kFeatureSetSize]) { + CoveredSize++; + Covered[Feature % kFeatureSetSize] = true; + } + } + NewFeatures->insert(MaxFeatureFile.Features.begin(), + MaxFeatureFile.Features.end()); + + // Remove the indices to this file and featureless files. + RemoveIndices.insert(MaxFeaturesIndex); + for (const auto i : RemoveIndices) { + Remaining.erase(std::remove(Remaining.begin(), Remaining.end(), i), + Remaining.end()); + } + + // 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 &Cov : MaxFeatureFile.Cov) { + if (InitialCov.find(Cov) == InitialCov.end()) { + NewCov->insert(Cov); + } + } + } + + return NewFeatures->size(); +} + // Inner process. May crash if the target crashes. -void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath) { +void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath, + bool MergeGreedy) { Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str()); Merger M; std::ifstream IF(CFPath); @@ -234,13 +372,14 @@ // 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. - // So it makes no sense to record all features for all files, instead we - // only record features that were not seen before. - Set UniqFeatures; - TPC.CollectFeatures([&](size_t Feature) { - if (AllFeatures.insert(Feature).second) - UniqFeatures.insert(Feature); - }); + Set Features; + if (MergeGreedy) + 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))) @@ -249,7 +388,7 @@ PrintStatsWrapper("LOADED"); // Write the post-run marker and the coverage. OF << "FT " << i; - for (size_t F : UniqFeatures) + for (size_t F : Features) OF << " " << F; OF << "\n"; OF << "COV " << i; @@ -305,10 +444,9 @@ Vector *NewFiles, const Set &InitialFeatures, Set *NewFeatures, - const Set &InitialCov, - Set *NewCov, - const std::string &CFPath, - bool V /*Verbose*/) { + const Set &InitialCov, Set *NewCov, + const std::string &CFPath, bool V, /*Verbose*/ + bool MergeGreedy) { if (NewCorpus.empty() && OldCorpus.empty()) return; // Nothing to merge. size_t NumAttempts = 0; Vector KnownFiles; @@ -370,7 +508,7 @@ VPrintf(V, "MERGE-OUTER: attempt %zd\n", Attempt); Command Cmd(BaseCmd); Cmd.addFlag("merge_control_file", CFPath); - Cmd.addFlag("merge_inner", "1"); + Cmd.addFlag("merge_inner", MergeGreedy ? "2" : "1"); if (!V) { Cmd.setOutputFile(getDevNull()); Cmd.combineOutAndErr(); @@ -395,7 +533,10 @@ M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb()); M.Files.insert(M.Files.end(), KnownFiles.begin(), KnownFiles.end()); - M.Merge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles); + if (MergeGreedy) + M.MergeGreedy(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());