1 //===- FuzzerMerge.cpp - merging corpora ----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 //===----------------------------------------------------------------------===//
12 #include "FuzzerMerge.h"
14 #include "FuzzerInternal.h"
15 #include "FuzzerTracePC.h"
16 #include "FuzzerUtil.h"
25 bool Merger::Parse(const std::string &Str, bool ParseCoverage) {
26 std::istringstream SS(Str);
27 return Parse(SS, ParseCoverage);
30 void Merger::ParseOrExit(std::istream &IS, bool ParseCoverage) {
31 if (!Parse(IS, ParseCoverage)) {
32 Printf("MERGE: failed to parse the control file (unexpected error)\n");
37 // The control file example:
39 // 3 # The number of inputs
40 // 1 # The number of inputs in the first corpus, <= the previous number
43 // file2 # One file name per line.
44 // STARTED 0 123 # FileID, file size
45 // DONE 0 1 4 6 8 # FileID COV1 COV2 ...
46 // STARTED 1 456 # If DONE is missing, the input crashed while processing.
49 bool Merger::Parse(std::istream &IS, bool ParseCoverage) {
54 if (!std::getline(IS, Line, '\n')) return false;
55 std::istringstream L1(Line);
58 if (NumFiles == 0 || NumFiles > 10000000) return false;
60 // Parse NumFilesInFirstCorpus.
61 if (!std::getline(IS, Line, '\n')) return false;
62 std::istringstream L2(Line);
63 NumFilesInFirstCorpus = NumFiles + 1;
64 L2 >> NumFilesInFirstCorpus;
65 if (NumFilesInFirstCorpus > NumFiles) return false;
68 Files.resize(NumFiles);
69 for (size_t i = 0; i < NumFiles; i++)
70 if (!std::getline(IS, Files[i].Name, '\n'))
73 // Parse STARTED and DONE lines.
74 size_t ExpectedStartMarker = 0;
75 const size_t kInvalidStartMarker = -1;
76 size_t LastSeenStartMarker = kInvalidStartMarker;
77 std::vector<uint32_t> TmpFeatures;
78 while (std::getline(IS, Line, '\n')) {
79 std::istringstream ISS1(Line);
84 if (Marker == "STARTED") {
85 // STARTED FILE_ID FILE_SIZE
86 if (ExpectedStartMarker != N)
88 ISS1 >> Files[ExpectedStartMarker].Size;
89 LastSeenStartMarker = ExpectedStartMarker;
90 assert(ExpectedStartMarker < Files.size());
91 ExpectedStartMarker++;
92 } else if (Marker == "DONE") {
93 // DONE FILE_ID COV1 COV2 COV3 ...
94 size_t CurrentFileIdx = N;
95 if (CurrentFileIdx != LastSeenStartMarker)
97 LastSeenStartMarker = kInvalidStartMarker;
99 TmpFeatures.clear(); // use a vector from outer scope to avoid resizes.
100 while (ISS1 >> std::hex >> N)
101 TmpFeatures.push_back(N);
102 std::sort(TmpFeatures.begin(), TmpFeatures.end());
103 Files[CurrentFileIdx].Features = TmpFeatures;
109 if (LastSeenStartMarker != kInvalidStartMarker)
110 LastFailure = Files[LastSeenStartMarker].Name;
112 FirstNotProcessedFile = ExpectedStartMarker;
116 size_t Merger::ApproximateMemoryConsumption() const {
118 for (const auto &F: Files)
119 Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]);
123 // Decides which files need to be merged (add thost to NewFiles).
124 // Returns the number of new features added.
125 size_t Merger::Merge(const std::set<uint32_t> &InitialFeatures,
126 std::vector<std::string> *NewFiles) {
128 assert(NumFilesInFirstCorpus <= Files.size());
129 std::set<uint32_t> AllFeatures(InitialFeatures);
131 // What features are in the initial corpus?
132 for (size_t i = 0; i < NumFilesInFirstCorpus; i++) {
133 auto &Cur = Files[i].Features;
134 AllFeatures.insert(Cur.begin(), Cur.end());
136 size_t InitialNumFeatures = AllFeatures.size();
138 // Remove all features that we already know from all other inputs.
139 for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
140 auto &Cur = Files[i].Features;
141 std::vector<uint32_t> Tmp;
142 std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(),
143 AllFeatures.end(), std::inserter(Tmp, Tmp.begin()));
147 // Sort. Give preference to
149 // * files with more features.
150 std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(),
151 [&](const MergeFileInfo &a, const MergeFileInfo &b) -> bool {
152 if (a.Size != b.Size)
153 return a.Size < b.Size;
154 return a.Features.size() > b.Features.size();
157 // One greedy pass: add the file's features to AllFeatures.
158 // If new features were added, add this file to NewFiles.
159 for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
160 auto &Cur = Files[i].Features;
161 // Printf("%s -> sz %zd ft %zd\n", Files[i].Name.c_str(),
162 // Files[i].Size, Cur.size());
163 size_t OldSize = AllFeatures.size();
164 AllFeatures.insert(Cur.begin(), Cur.end());
165 if (AllFeatures.size() > OldSize)
166 NewFiles->push_back(Files[i].Name);
168 return AllFeatures.size() - InitialNumFeatures;
171 void Merger::PrintSummary(std::ostream &OS) {
172 for (auto &File : Files) {
174 OS << File.Name << " size: " << File.Size << " features: ";
175 for (auto Feature : File.Features)
176 OS << " " << Feature;
181 std::set<uint32_t> Merger::AllFeatures() const {
182 std::set<uint32_t> S;
183 for (auto &File : Files)
184 S.insert(File.Features.begin(), File.Features.end());
188 std::set<uint32_t> Merger::ParseSummary(std::istream &IS) {
189 std::string Line, Tmp;
190 std::set<uint32_t> Res;
191 while (std::getline(IS, Line, '\n')) {
193 std::istringstream ISS1(Line);
195 ISS1 >> Tmp; // size:
196 assert(Tmp == "size:" && "Corrupt summary file");
198 ISS1 >> N; // File Size
199 ISS1 >> Tmp; // features:
200 assert(Tmp == "features:" && "Corrupt summary file");
201 while (ISS1 >> std::hex >> N)
207 // Inner process. May crash if the target crashes.
208 void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath) {
209 Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str());
211 std::ifstream IF(CFPath);
212 M.ParseOrExit(IF, false);
214 if (!M.LastFailure.empty())
215 Printf("MERGE-INNER: '%s' caused a failure at the previous merge step\n",
216 M.LastFailure.c_str());
218 Printf("MERGE-INNER: %zd total files;"
219 " %zd processed earlier; will process %zd files now\n",
220 M.Files.size(), M.FirstNotProcessedFile,
221 M.Files.size() - M.FirstNotProcessedFile);
223 std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app);
224 for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {
225 auto U = FileToVector(M.Files[i].Name);
226 if (U.size() > MaxInputLen) {
227 U.resize(MaxInputLen);
230 std::ostringstream StartedLine;
231 // Write the pre-run marker.
232 OF << "STARTED " << std::dec << i << " " << U.size() << "\n";
233 OF.flush(); // Flush is important since ExecuteCommand may crash.
236 ExecuteCallback(U.data(), U.size());
238 std::set<size_t> Features;
239 TPC.CollectFeatures([&](size_t Feature) -> bool {
240 Features.insert(Feature);
244 if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))
245 PrintStats("pulse ");
246 // Write the post-run marker and the coverage.
248 for (size_t F : Features)
249 OF << " " << std::hex << F;
254 // Outer process. Does not call the target code and thus sohuld not fail.
255 void Fuzzer::CrashResistantMerge(const std::vector<std::string> &Args,
256 const std::vector<std::string> &Corpora,
257 const char *CoverageSummaryInputPathOrNull,
258 const char *CoverageSummaryOutputPathOrNull) {
259 if (Corpora.size() <= 1) {
260 Printf("Merge requires two or more corpus dirs\n");
263 std::vector<std::string> AllFiles;
264 ListFilesInDirRecursive(Corpora[0], nullptr, &AllFiles, /*TopDir*/true);
265 size_t NumFilesInFirstCorpus = AllFiles.size();
266 for (size_t i = 1; i < Corpora.size(); i++)
267 ListFilesInDirRecursive(Corpora[i], nullptr, &AllFiles, /*TopDir*/true);
268 Printf("MERGE-OUTER: %zd files, %zd in the initial corpus\n",
269 AllFiles.size(), NumFilesInFirstCorpus);
270 auto CFPath = DirPlusFile(TmpDir(),
271 "libFuzzerTemp." + std::to_string(GetPid()) + ".txt");
272 // Write the control file.
274 std::ofstream ControlFile(CFPath);
275 ControlFile << AllFiles.size() << "\n";
276 ControlFile << NumFilesInFirstCorpus << "\n";
277 for (auto &Path: AllFiles)
278 ControlFile << Path << "\n";
280 Printf("MERGE-OUTER: failed to write to the control file: %s\n",
286 // Execute the inner process untill it passes.
287 // Every inner process should execute at least one input.
288 auto BaseCmd = SplitBefore("-ignore_remaining_args=1",
289 CloneArgsWithoutX(Args, "keep-all-flags"));
290 bool Success = false;
291 for (size_t i = 1; i <= AllFiles.size(); i++) {
292 Printf("MERGE-OUTER: attempt %zd\n", i);
293 auto ExitCode = ExecuteCommand(BaseCmd.first + " -merge_control_file=" +
294 CFPath + " " + BaseCmd.second);
296 Printf("MERGE-OUTER: succesfull in %zd attempt(s)\n", i);
302 Printf("MERGE-OUTER: zero succesfull attempts, exiting\n");
305 // Read the control file and do the merge.
307 std::ifstream IF(CFPath);
309 Printf("MERGE-OUTER: the control file has %zd bytes\n", (size_t)IF.tellg());
311 M.ParseOrExit(IF, true);
313 Printf("MERGE-OUTER: consumed %zdMb (%zdMb rss) to parse the control file\n",
314 M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb());
315 if (CoverageSummaryOutputPathOrNull) {
316 Printf("MERGE-OUTER: writing coverage summary for %zd files to %s\n",
317 M.Files.size(), CoverageSummaryOutputPathOrNull);
318 std::ofstream SummaryOut(CoverageSummaryOutputPathOrNull);
319 M.PrintSummary(SummaryOut);
321 std::vector<std::string> NewFiles;
322 std::set<uint32_t> InitialFeatures;
323 if (CoverageSummaryInputPathOrNull) {
324 std::ifstream SummaryIn(CoverageSummaryInputPathOrNull);
325 InitialFeatures = M.ParseSummary(SummaryIn);
326 Printf("MERGE-OUTER: coverage summary loaded from %s, %zd features found\n",
327 CoverageSummaryInputPathOrNull, InitialFeatures.size());
329 size_t NumNewFeatures = M.Merge(InitialFeatures, &NewFiles);
330 Printf("MERGE-OUTER: %zd new files with %zd new features added\n",
331 NewFiles.size(), NumNewFeatures);
332 for (auto &F: NewFiles)
333 WriteToOutputCorpus(FileToVector(F));
334 // We are done, delete the control file.
338 } // namespace fuzzer