Greedy set cover implementation of `Merger::Merge`

[arisKoutsou]

Summary

Extend the existing single-pass algorithm for Merger::Merge with an algorithm that gives better results. This new implementation can be used with a new set_cover_merge=1 flag.

This greedy set cover implementation gives a substantially smaller final corpus (40%-80% less testcases) while preserving the same features/coverage. At the same time, the execution time penalty is not that significant (+50% for ~1M corpus files and far less for smaller corpora). These results were obtained by comparing several targets with varying size corpora.

Change Merger::CrashResistantMergeInternalStep to collect all features from each file and not just unique ones. This is needed for the set cover algorithm to work correctly. The implementation of the algorithm in Merger::SetCoverMerge uses a bitvector to store features that are covered by a file while performing the pass. Collisions while indexing the bitvector are ignored similarly to the fuzzer.

[kcc]

Thanks for the change!
Indeed, the current single-pass merge is far from perfect, and it's nice to see your numbers.

Some high-level notes:

• not sure about the flag syntax (-merge=2), I'd prefer something more descriptive. Maybe add an extra flag -set_cover_merge=1?
• The current single-pass algorithm is also greedy (just less so :)), so maybe use a different name to distinguish the new algorithm
• please try to follow the coding style e.g. with respect to {} around single-statement blocks.
• please add a unit test and a .lit test

I'll let Matt make another round of review.

[morehouse]

I understand that this merge algorithm decreases the number of inputs by taking the most feature-rich inputs first. Does this lead to larger average input sizes in the merged corpus?

And what's the effect on total corpus bytes (du -hs)?

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

198

Please document the merge algorithm in a function comment here.

233

Given the multiple passes over Remaining, is this sort useful anymore?

317

Would a set be a better data structure for Remaining? Then we wouldn't need to do a linear lookup on every erase.

[arisKoutsou]

Changes:

• Renamed all occurences of MergeGreedy with SetCoverMerge.
• Added a new flag called set_cover_merge. Defaults to 0, when 1 the new set_cover_merge implementation is used to merge corpora instead of the standard merge.
• Some code-style changes.
• Added a unit test, based off the Merger::Merge unit test.
• Added a lit test based on the merge.test. Results of merge and set_cover_merge are different in some cases, as expected.
• Changed the Remaining variable in SetCoverMerge() from std::vector to a std::set.
• Addressed some inaccuracies in the algorithm, mostly regarding the first corpus (consider features in the first corpus as already covered, just like merge=1 works).
• Removed the initial sorting of files on size/features. Instead, for files with the same number of features, break ties by choosing the smaller one in size.

[arisKoutsou]

Does this lead to larger average input sizes in the merged corpus?

@morehouse It will lead to a larger average size, since we are preferring files with many features (which probably are larger in many cases). On the other hand, since the final corpus size (in files) is smaller, the sum of the file sizes in bytes may end up less than with the existing merge algorithm.

For example, consider minimizing a 70K testcase corpus for a harness of the jq target. The following workflow is performed in a container (image: https://hub.docker.com/r/ariskoutsou/jq-libfuzzer) containing the updated -set_cover_merge=1 implementation along with the target harness:

root@dd166043164c:/src/harness# mkdir 0
root@dd166043164c:/src/harness# ./fuzzer_jq -detect_leaks=0 -close_fd_mask=3 -set_cover_merge=1 0 corpus
...
MERGE-OUTER: the control file has 48616105 bytes
MERGE-OUTER: consumed 34Mb (185Mb rss) to parse the control file
MERGE-OUTER: 83 new files with 3174 new features added; 1116 new coverage edges
...
root@dd166043164c:/src/harness# find 0 -ls | awk '{sum += $7; n++;} END {print sum/n;}'
1068.81
root@dd166043164c:/src/harness# du -sh 0
356K    0
root@dd166043164c:/src/harness# rm 0/*
root@dd166043164c:/src/harness# ./fuzzer_jq -detect_leaks=0 -close_fd_mask=3 -merge=1 0 corpus
...
MERGE-OUTER: the control file has 4184437 bytes
MERGE-OUTER: consumed 5Mb (94Mb rss) to parse the control file
MERGE-OUTER: 161 new files with 3174 new features added; 1293 new coverage edges
...
root@dd166043164c:/src/harness# find 0 -ls | awk '{sum += $7; n++;} END {p
rint sum/n;}'
675.296
root@dd166043164c:/src/harness# du -sh 0/
676K    0/

Here, even though the average file size is quite bigger ~1068 bytes over ~675 bytes, the total corpus size is smaller. With the set_cover_merge flag the minimized corpus size is 356K, while with merge it is 676K.

[arisKoutsou]

• Change .lit test input to better illustrate the scenario where 2 files cover all features.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerFork.cpp

324–325

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

358

Could this continue cause an infinite loop? i.e. when Remaining is empty

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

953

IIUC, this test doesn't quite do what's intended.

We choose input C because it has the most unique features, but after that A only has {0} as a unique feature while B has {4, 5}. So we do in fact choose B, but not because it is smaller.

compiler-rt/test/fuzzer/set_cover_merge.test

49

I think we would get the same results with -merge. Perhaps we should make some feature-poor inputs smaller so that -merge would pick those first, while -set_cover_merge picks the feature-rich ones.

[arisKoutsou]

• Add comments for argument names when passing argument values.
• Change AllFeatures. Calculate all unique features by considering Feature % kFeatureSetSize as the feature value.
• Change continue to break statement in main loop. Add assertions to highlight the condition that exits the loop.
• Remove checking for feature-less files since we are not removing features from any MergeFileInfo objects.
• Update tests, add testcase for feature collision on the bitvector.

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

358

It wouldn't cause an infinite loop when Remaining is empty because the while condition (CoveredSize != AllFeatures.size()) would be false. On the other hand, I noticed that there would be a problem if a feature had a value greater than 1 << 21, which is the size of the bitvector. In that case, there could be an infinite loop because the while condition would never become false. I am addressing this problem in the latest patch.

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

953

Correct, I will adjust the features correctly so that we can test breaking ties between files with equal number of features.

compiler-rt/test/fuzzer/set_cover_merge.test

49

Should I also include a test of -merge=1 in this source file to highlight the difference in behavior?

[morehouse]

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

953

The comment above is confusing me now. I *think* what's happening is that B is picked first (over A since B is smaller), leaving A with {0, 3} unique features and C with {1, 2, 4} unique features. Then C gets picked since it has more features.

We still end up with C and B in the set, but the comment's explanation of how this happens is wrong.

compiler-rt/test/fuzzer/set_cover_merge.test

49

Yes, please do.

[arisKoutsou]

• Add -merge=1 test in set_cover_merge.test for comparison with -set_cover_merge=1.

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

953

As far as I can see here , the format of the control file is:

FT <current_file_index> <feature_1> <feature_2> ... <feature_n>

So, in our case, the feature sets are:

A = {3, 5, 6}
B = {4, 5, 6}
C = {1, 2, 3, 4}
D = {1}

Since the set cover algorithm chooses the set that covers the maximum number of previously uncovered features, the file that is chosen in the first iteration is C. This is because Covered is empty and C has 4 features while all the other files have less features. In the next iteration of the algorithm A's uncovered features are {5, 6} and B's uncovered features are {5, 6} so we break the tie by selecting the smallest which is B. Finally, all features are covered so we can exit.

[morehouse]

LGTM

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

953

Ah, yep you're right. Thanks for explaining.

[arisKoutsou]

• Fix set_cover_merge.test to not produce flaky results based on file listing order.

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

for (size_t i = 1; i < Corpora.size(); i++)
     GetSizedFilesFromDir(Corpora[i], &NewCorpus);
   std::sort(OldCorpus.begin(), OldCorpus.end());
   std::sort(NewCorpus.begin(), NewCorpus.end());
 
   std::string CFPath = CFPathOrNull ? CFPathOrNull : TempPath("Merge", ".txt");
   std::vector<std::string> NewFiles;
   std::set<uint32_t> NewFeatures, NewCov;
   CrashResistantMerge(Args, OldCorpus, NewCorpus, &NewFiles, {}, &NewFeatures,
-                      {}, &NewCov, CFPath, true);
+                      {}, &NewCov, CFPath, true, Flags.set_cover_merge);
   for (auto &Path : NewFiles)
     F->WriteToOutputCorpus(FileToVector(Path, Options.MaxLen));
   // We are done, delete the control file if it was a temporary one.
   if (!Flags.merge_control_file)
     RemoveFile(CFPath);
 
   exit(0);
 }
int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
   unsigned Seed = Flags.seed;
   // Initialize Seed.
   if (Seed == 0)
     Seed = static_cast<unsigned>(
         std::chrono::system_clock::now().time_since_epoch().count() + GetPid());
   if (Flags.verbosity)
     Printf("INFO: Seed: %u\n", Seed);
 
-  if (Flags.collect_data_flow && !Flags.fork && !Flags.merge) {
+  if (Flags.collect_data_flow && !Flags.fork &&
+      !(Flags.merge || Flags.set_cover_merge)) {
     if (RunIndividualFiles)
       return CollectDataFlow(Flags.collect_data_flow, Flags.data_flow_trace,
                         ReadCorpora({}, *Inputs));
     else
       return CollectDataFlow(Flags.collect_data_flow, Flags.data_flow_trace,
                         ReadCorpora(*Inputs, {}));
   }
 
Printf("***\n"
            "***\n");
     F->PrintFinalStats();
     exit(0);
   }
 
   if (Flags.fork)
     FuzzWithFork(F->GetMD().GetRand(), Options, Args, *Inputs, Flags.fork);
 
-  if (Flags.merge)
+  if (Flags.merge || Flags.set_cover_merge)
     Merge(F, Options, Args, *Inputs, Flags.merge_control_file);
 
   if (Flags.merge_inner) {
     const size_t kDefaultMaxMergeLen = 1 << 20;
     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);
   }
 
   if (Flags.analyze_dict) {
     size_t MaxLen = INT_MAX;  // Large max length.
     UnitVector InitialCorpus;
     for (auto &Inp : *Inputs) {
       Printf("Loading corpus dir: %s\n", Inp.c_str());

compiler-rt/lib/fuzzer/FuzzerFlags.def

 FUZZER_FLAG_INT(fork, 0, "Experimental mode where fuzzing happens "
                 "in a subprocess")
 FUZZER_FLAG_INT(ignore_timeouts, 1, "Ignore timeouts in fork mode")
 FUZZER_FLAG_INT(ignore_ooms, 1, "Ignore OOMs in fork mode")
 FUZZER_FLAG_INT(ignore_crashes, 0, "Ignore crashes in fork mode")
 FUZZER_FLAG_INT(merge, 0, "If 1, the 2-nd, 3-rd, etc corpora will be "
   "merged into the 1-st corpus. Only interesting units will be taken. "
   "This flag can be used to minimize a corpus.")
+FUZZER_FLAG_INT(set_cover_merge, 0, "If 1, the 2-nd, 3-rd, etc corpora will be "
+  "merged into the 1-st corpus. Same as the 'merge' flag, but uses the "
+  "standard greedy algorithm for the set cover problem to "
+  "compute an approximation of the minimum set of testcases that "
+  "provide the same coverage as the initial corpora")
 FUZZER_FLAG_STRING(stop_file, "Stop fuzzing ASAP if this file exists")
 FUZZER_FLAG_STRING(merge_inner, "internal flag")
 FUZZER_FLAG_STRING(merge_control_file,
                    "Specify a control file used for the merge process. "
                    "If a merge process gets killed it tries to leave this file "
                    "in a state suitable for resuming the merge. "
                    "By default a temporary file will be used."
                    "The same file can be used for multistep merge process.")

compiler-rt/lib/fuzzer/FuzzerFork.cpp

Printf("#%zd: cov: %zd ft: %zd corp: %zd exec/s %zd "
            NumRuns, Cov.size(), Features.size(), Files.size(),
            Stats.average_exec_per_sec, NumOOMs, NumTimeouts, NumCrashes,
            secondsSinceProcessStartUp(), Job->JobId, Job->DftTimeInSeconds);
 
     if (MergeCandidates.empty()) return;
 
     std::vector<std::string> FilesToAdd;
     std::set<uint32_t> NewFeatures, NewCov;
+    bool IsSetCoverMerge =
+        !Job->Cmd.getFlagValue("set_cover_merge").compare("1");
     CrashResistantMerge(Args, {}, MergeCandidates, &FilesToAdd, Features,
-                        &NewFeatures, Cov, &NewCov, Job->CFPath, false);
+                        &NewFeatures, Cov, &NewCov, Job->CFPath, false,
+                        IsSetCoverMerge);
     for (auto &Path : FilesToAdd) {
       auto U = FileToVector(Path);
       auto NewPath = DirPlusFile(MainCorpusDir, Hash(U));
       WriteToFile(U, NewPath);
       Files.push_back(NewPath);
     }
     Features.insert(NewFeatures.begin(), NewFeatures.end());
     Cov.insert(NewCov.begin(), NewCov.end());
void FuzzWithFork(Random &Rand, const FuzzingOptions &Options,
 
   if (Options.KeepSeed) {
     for (auto &File : SeedFiles)
       Env.Files.push_back(File.File);
   } else {
     auto CFPath = DirPlusFile(Env.TempDir, "merge.txt");
     std::set<uint32_t> NewFeatures, NewCov;
     CrashResistantMerge(Env.Args, {}, SeedFiles, &Env.Files, Env.Features,
-                        &NewFeatures, Env.Cov, &NewCov, CFPath, false);
+                        &NewFeatures, Env.Cov, &NewCov, CFPath,
+                        /*Verbose=*/false, /*IsSetCoverMerge=*/false);
     Env.Features.insert(NewFeatures.begin(), NewFeatures.end());
     Env.Cov.insert(NewFeatures.begin(), NewFeatures.end());
     RemoveFile(CFPath);
   }
   Printf("INFO: -fork=%d: %zd seed inputs, starting to fuzz in %s\n", NumJobs,
          Env.Files.size(), Env.TempDir.c_str());
 
   int ExitCode = 0;

compiler-rt/lib/fuzzer/FuzzerInternal.h

public:
   void ExecuteCallback(const uint8_t *Data, size_t Size);
   bool RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile = false,
               InputInfo *II = nullptr, bool ForceAddToCorpus = false,
               bool *FoundUniqFeatures = nullptr);
   void TPCUpdateObservedPCs();
 
   // Merge Corpora[1:] into Corpora[0].
   void Merge(const std::vector<std::string> &Corpora);
-  void CrashResistantMergeInternalStep(const std::string &ControlFilePath);
+  void CrashResistantMergeInternalStep(const std::string &ControlFilePath,
+                                       bool IsSetCoverMerge);
   MutationDispatcher &GetMD() { return MD; }
   void PrintFinalStats();
   void SetMaxInputLen(size_t MaxInputLen);
   void SetMaxMutationLen(size_t MaxMutationLen);
   void RssLimitCallback();
 
   bool InFuzzingThread() const { return IsMyThread; }
   size_t GetCurrentUnitInFuzzingThead(const uint8_t **Data) const;

compiler-rt/lib/fuzzer/FuzzerMerge.h

struct Merger {
 
   bool Parse(std::istream &IS, bool ParseCoverage);
   bool Parse(const std::string &Str, bool ParseCoverage);
   void ParseOrExit(std::istream &IS, bool ParseCoverage);
   size_t 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);
+  size_t 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);
   size_t ApproximateMemoryConsumption() const;
   std::set<uint32_t> AllFeatures() const;
 };
 
 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 Verbose);
+                         bool Verbose, bool IsSetCoverMerge);
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MERGE_H

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

 }
 
 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) {
+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());
for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {
     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.
-    // So it makes no sense to record all features for all files, instead we
-    // only record features that were not seen before.
-    std::set<size_t> UniqFeatures;
+    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)
-        UniqFeatures.insert(Feature);
+          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 : UniqFeatures)
+    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);

 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 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);
VPrintf(V, "MERGE-OUTER: "
             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);
-    Cmd.addFlag("merge_inner", "1");
+    // 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

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

 
 #include "FuzzerCorpus.h"
 #include "FuzzerDictionary.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
 #include "gtest/gtest.h"
 #include <memory>
 #include <set>
 #include <sstream>
 
 using namespace fuzzer;
 
 // For now, have LLVMFuzzerTestOneInput just to make it link.
 // Later we may want to make unittests that actually call
EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
   TRACED_EQ(NewFiles, {"D", "B"});
   TRACED_EQ(NewFeatures, {1, 2, 3});
 }
 
+TEST(Merger, SetCoverMerge) {
+  Merger M;
+  std::set<uint32_t> Features, NewFeatures;
+  std::set<uint32_t> Cov, NewCov;
+  std::vector<std::string> NewFiles;
+
+  // Adds new files and features
+  EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
+                      "STARTED 0 1000\n"
+                      "FT 0 1 2 3\n"
+                      "STARTED 1 1001\n"
+                      "FT 1 4 5 6 \n"
+                      "STARTED 2 1002\n"
+                      "FT 2 6 1 3\n"
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            6U);
+  TRACED_EQ(M.Files, {"A", "B", "C"});
+  TRACED_EQ(NewFiles, {"A", "B"});
+  TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
+
+  // Doesn't return features or files in the initial corpus.
+  EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
+                      "STARTED 0 1000\n"
+                      "FT 0 1 2 3\n"
+                      "STARTED 1 1001\n"
+                      "FT 1 4 5 6 \n"
+                      "STARTED 2 1002\n"
+                      "FT 2 6 1 3\n"
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            3U);
+  TRACED_EQ(M.Files, {"A", "B", "C"});
+  TRACED_EQ(NewFiles, {"B"});
+  TRACED_EQ(NewFeatures, {4, 5, 6});
+
+  // No new features, so no new files
+  EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
+                      "STARTED 0 1000\n"
+                      "FT 0 1 2 3\n"
+                      "STARTED 1 1001\n"
+                      "FT 1 4 5 6 \n"
+                      "STARTED 2 1002\n"
+                      "FT 2 6 1 3\n"
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            0U);
+  TRACED_EQ(M.Files, {"A", "B", "C"});
+  TRACED_EQ(NewFiles, {});
+  TRACED_EQ(NewFeatures, {});
+
+  // Can pass initial features and coverage.
+  Features = {1, 2, 3};
+  Cov = {};
+  EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
+                      "STARTED 0 1000\n"
+                      "FT 0 1 2 3\n"
+                      "STARTED 1 1001\n"
+                      "FT 1 4 5 6\n"
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            3U);
+  TRACED_EQ(M.Files, {"A", "B"});
+  TRACED_EQ(NewFiles, {"B"});
+  TRACED_EQ(NewFeatures, {4, 5, 6});
+  Features.clear();
+  Cov.clear();
+
+  // Prefer files with a lot of features first (C has 4 features)
+  // Then prefer B over A due to the smaller size. After choosing C and B,
+  // A and D have no new features to contribute.
+  EXPECT_TRUE(M.Parse("4\n0\nA\nB\nC\nD\n"
+                      "STARTED 0 2000\n"
+                      "FT 0 3 5 6\n"
+                      "STARTED 1 1000\n"
+                      "FT 1 4 5 6 \n"
+                      "STARTED 2 1000\n"
+                      "FT 2 1 2 3 4 \n"
+                      "STARTED 3 500\n"
+                      "FT 3 1  \n"
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            6U);
+  TRACED_EQ(M.Files, {"A", "B", "C", "D"});
+  TRACED_EQ(NewFiles, {"C", "B"});
+  TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
+
+  // Only 1 file covers all features.
+  EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
+                      "STARTED 0 2000\n"
+                      "FT 0 4 5 6 7 8\n"
+                      "STARTED 1 1100\n"
+                      "FT 1 1 2 3 \n"
+                      "STARTED 2 1100\n"
+                      "FT 2 2 3 \n"
+                      "STARTED 3 1000\n"
+                      "FT 3 1  \n"
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            3U);
+  TRACED_EQ(M.Files, {"A", "B", "C", "D"});
+  TRACED_EQ(NewFiles, {"B"});
+  TRACED_EQ(NewFeatures, {1, 2, 3});
+
+  // A Feature has a value greater than (1 << 21) and hence
+  // there are collisions in the underlying `covered features`
+  // bitvector.
+  EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
+                      "STARTED 0 2000\n"
+                      "FT 0 1 2 3\n"
+                      "STARTED 1 1000\n"
+                      "FT 1 3 4 5 \n"
+                      "STARTED 2 1000\n"
+                      "FT 2 3 2097153 \n" // Last feature is (2^21 + 1).
+                      "",
+                      true));
+  EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
+            5U);
+  TRACED_EQ(M.Files, {"A", "B", "C"});
+  // File 'C' is not added because it's last feature is considered
+  // covered due to collision with feature 1.
+  TRACED_EQ(NewFiles, {"B", "A"});
+  TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5});
+}
+
 #undef TRACED_EQ
 
 TEST(DFT, BlockCoverage) {
   BlockCoverage Cov;
   // Assuming C0 has 5 instrumented blocks,
   // C1: 7 blocks, C2: 4, C3: 9, C4 never covered, C5: 15,
 
   // Add C0

compiler-rt/test/fuzzer/set_cover_merge.test

+RUN: %cpp_compiler %S/FullCoverageSetTest.cpp -o %t-FullCoverageSetTest
+
+RUN: rm -rf %t/T1 %t/T2
+RUN: mkdir -p %t/T1 %t/T2
+RUN: echo F..... > %t/T1/1
+RUN: echo .U.... > %t/T1/2
+RUN: echo ..Z... > %t/T1/3
+
+# T1 has 3 elements, T2 is empty.
+RUN: %run %t-FullCoverageSetTest         -set_cover_merge=1 %t/T1 %t/T2 2>&1 | FileCheck %s --check-prefix=CHECK1
+CHECK1: MERGE-OUTER: 3 files, 3 in the initial corpus
+CHECK1: MERGE-OUTER: 0 new files with 0 new features added
+
+RUN: echo ...Z.. > %t/T2/1
+RUN: echo ....E. > %t/T2/2
+RUN: echo .....R > %t/T2/3
+RUN: echo F..... > %t/T2/a
+RUN: echo .U.... > %t/T2/b
+RUN: echo ..Z... > %t/T2/c
+
+# T1 has 3 elements, T2 has 6 elements, only 3 are new.
+RUN: %run %t-FullCoverageSetTest         -set_cover_merge=1 %t/T1 %t/T2 2>&1 | FileCheck %s --check-prefix=CHECK2
+CHECK2: MERGE-OUTER: 9 files, 3 in the initial corpus
+CHECK2: MERGE-OUTER: 3 new files with 3 new features added
+
+# Now, T1 has 6 units and T2 has no new interesting units.
+RUN: %run %t-FullCoverageSetTest         -set_cover_merge=1 %t/T1 %t/T2 2>&1 | FileCheck %s --check-prefix=CHECK3
+CHECK3: MERGE-OUTER: 12 files, 6 in the initial corpus
+CHECK3: MERGE-OUTER: 0 new files with 0 new features added
+
+RUN: rm -rf %t/T1/* %t/T2/*
+RUN: mkdir -p %t/T3
+RUN: echo ...... > %t/T1/1
+RUN: echo F..... > %t/T2/a
+RUN: echo .U.... > %t/T2/b
+RUN: echo ..Z... > %t/T2/c
+RUN: echo ...Z.. > %t/T3/1
+RUN: echo ....E. > %t/T3/2
+RUN: echo ...ZER > %t/T3/3
+RUN: echo .UZZER. > %t/T3/a
+RUN: echo .UZZER.. > %t/T3/b
+RUN: echo ...... > %t/T3/c
+
+# T1 is empty, T2 and T3 have overlapping features. The optimal solution
+# consists of 2 files: T2/a, T3/a. These files cover 6 new features.
+# Although T3/a is larger in size (1 more byte) we prefer it because
+# it covers more features than any other file.
+RUN: %run %t-FullCoverageSetTest         -set_cover_merge=1 %t/T1 %t/T2 %t/T3 2>&1 | FileCheck %s --check-prefix=CHECK_OVERLAP
+CHECK_OVERLAP: MERGE-OUTER: 10 files, 1 in the initial corpus
+CHECK_OVERLAP: MERGE-OUTER: 2 new files with 6 new features added
+# Make sure that we are prefering smaller files (T3/a over T3/b).
+RUN: diff %t/T1/1b2301992a0266982b135fee5164937d7f7abca3 %t/T3/a
+
+RUN: rm -rf %t/T1/* %t/T2/* %t/T3/*
+RUN: echo ...... > %t/T1/1
+RUN: echo F..... > %t/T2/a
+RUN: echo .U.... > %t/T2/b
+RUN: echo ..Z... > %t/T2/c
+RUN: echo ...Z.. > %t/T3/1
+RUN: echo ....E. > %t/T3/2
+RUN: echo .....R > %t/T3/3
+RUN: echo .UZZER. > %t/T3/a
+RUN: echo .UZZER.. > %t/T3/b
+RUN: echo ...... > %t/T3/c
+
+# Test the previous scenario with the '-merge=1' flag.
+# Expect more files to be added to the first corpus, since '-merge=1'
+# is going to prefer smaller files and ignore the fact that
+# T3/a covers almost all of the available features.
+RUN: %run %t-FullCoverageSetTest         -merge=1 %t/T1 %t/T2 %t/T3 2>&1 | FileCheck %s --check-prefix=CHECK_OVERLAP2
+CHECK_OVERLAP2: MERGE-OUTER: 10 files, 1 in the initial corpus
+CHECK_OVERLAP2: MERGE-OUTER: 6 new files with 6 new features added
 No newline at end of file