1//===- FuzzerLoop.cpp - Fuzzer's main loop --------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9// Fuzzer's main loop.
10//===----------------------------------------------------------------------===//
11
12#include "FuzzerInternal.h"
13#include <sanitizer/coverage_interface.h>
14#include <algorithm>
15#include <iostream>
16
17namespace fuzzer {
18
19// Only one Fuzzer per process.
20static Fuzzer *F;
21
22Fuzzer::Fuzzer(UserCallback Callback, FuzzingOptions Options)
23    : Callback(Callback), Options(Options) {
24  SetDeathCallback();
25  InitializeDFSan();
26  assert(!F);
27  F = this;
28}
29
30void Fuzzer::SetDeathCallback() {
31  __sanitizer_set_death_callback(StaticDeathCallback);
32}
33
34void Fuzzer::PrintUnitInASCIIOrTokens(const Unit &U, const char *PrintAfter) {
35  if (Options.Tokens.empty()) {
36    PrintASCII(U, PrintAfter);
37  } else {
38    auto T = SubstituteTokens(U);
39    T.push_back(0);
40    std::cerr << T.data();
41    std::cerr << PrintAfter;
42  }
43}
44
45void Fuzzer::StaticDeathCallback() {
46  assert(F);
47  F->DeathCallback();
48}
49
50void Fuzzer::DeathCallback() {
51  std::cerr << "DEATH: " <<  std::endl;
52  Print(CurrentUnit, "\n");
53  PrintUnitInASCIIOrTokens(CurrentUnit, "\n");
54  WriteToCrash(CurrentUnit, "crash-");
55}
56
57void Fuzzer::StaticAlarmCallback() {
58  assert(F);
59  F->AlarmCallback();
60}
61
62void Fuzzer::AlarmCallback() {
63  size_t Seconds =
64      duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
65  std::cerr << "ALARM: working on the last Unit for " << Seconds << " seconds"
66            << std::endl;
67  if (Seconds >= 3) {
68    Print(CurrentUnit, "\n");
69    PrintUnitInASCIIOrTokens(CurrentUnit, "\n");
70    WriteToCrash(CurrentUnit, "timeout-");
71  }
72  exit(1);
73}
74
75void Fuzzer::PrintStats(const char *Where, size_t Cov, const char *End) {
76  if (!Options.Verbosity) return;
77  size_t Seconds = secondsSinceProcessStartUp();
78  size_t ExecPerSec = (Seconds ? TotalNumberOfRuns / Seconds : 0);
79  std::cerr
80      << "#" << TotalNumberOfRuns
81      << "\t" << Where
82      << " cov " << Cov
83      << " bits " << TotalBits()
84      << " units " << Corpus.size()
85      << " exec/s " << ExecPerSec
86      << End;
87}
88
89void Fuzzer::ShuffleAndMinimize() {
90  size_t MaxCov = 0;
91  bool PreferSmall =
92      (Options.PreferSmallDuringInitialShuffle == 1 ||
93       (Options.PreferSmallDuringInitialShuffle == -1 && rand() % 2));
94  if (Options.Verbosity)
95    std::cerr << "PreferSmall: " << PreferSmall << "\n";
96  PrintStats("READ  ", 0);
97  std::vector<Unit> NewCorpus;
98  std::random_shuffle(Corpus.begin(), Corpus.end());
99  if (PreferSmall)
100    std::stable_sort(
101        Corpus.begin(), Corpus.end(),
102        [](const Unit &A, const Unit &B) { return A.size() < B.size(); });
103  Unit &U = CurrentUnit;
104  for (const auto &C : Corpus) {
105    for (size_t First = 0; First < 1; First++) {
106      U.clear();
107      size_t Last = std::min(First + Options.MaxLen, C.size());
108      U.insert(U.begin(), C.begin() + First, C.begin() + Last);
109      size_t NewCoverage = RunOne(U);
110      if (NewCoverage) {
111        MaxCov = NewCoverage;
112        NewCorpus.push_back(U);
113        if (Options.Verbosity >= 2)
114          std::cerr << "NEW0: " << NewCoverage
115                    << " L " << U.size()
116                    << "\n";
117      }
118    }
119  }
120  Corpus = NewCorpus;
121  PrintStats("INITED", MaxCov);
122}
123
124size_t Fuzzer::RunOne(const Unit &U) {
125  UnitStartTime = system_clock::now();
126  TotalNumberOfRuns++;
127  size_t Res = 0;
128  if (Options.UseFullCoverageSet)
129    Res = RunOneMaximizeFullCoverageSet(U);
130  else if (Options.UseCoveragePairs)
131    Res = RunOneMaximizeCoveragePairs(U);
132  else
133    Res = RunOneMaximizeTotalCoverage(U);
134  auto UnitStopTime = system_clock::now();
135  auto TimeOfUnit =
136      duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
137  if (TimeOfUnit > TimeOfLongestUnitInSeconds) {
138    TimeOfLongestUnitInSeconds = TimeOfUnit;
139    std::cerr << "Longest unit: " << TimeOfLongestUnitInSeconds
140              << " s:\n";
141    Print(U, "\n");
142  }
143  return Res;
144}
145
146static uintptr_t HashOfArrayOfPCs(uintptr_t *PCs, uintptr_t NumPCs) {
147  uintptr_t Res = 0;
148  for (uintptr_t i = 0; i < NumPCs; i++) {
149    Res = (Res + PCs[i]) * 7;
150  }
151  return Res;
152}
153
154Unit Fuzzer::SubstituteTokens(const Unit &U) const {
155  Unit Res;
156  for (auto Idx : U) {
157    if (Idx < Options.Tokens.size()) {
158      std::string Token = Options.Tokens[Idx];
159      Res.insert(Res.end(), Token.begin(), Token.end());
160    } else {
161      Res.push_back(' ');
162    }
163  }
164  // FIXME: Apply DFSan labels.
165  return Res;
166}
167
168void Fuzzer::ExecuteCallback(const Unit &U) {
169  if (Options.Tokens.empty()) {
170    Callback(U.data(), U.size());
171  } else {
172    auto T = SubstituteTokens(U);
173    Callback(T.data(), T.size());
174  }
175}
176
177// Experimental. Does not yet scale.
178// Fuly reset the current coverage state, run a single unit,
179// collect all coverage pairs and return non-zero if a new pair is observed.
180size_t Fuzzer::RunOneMaximizeCoveragePairs(const Unit &U) {
181  __sanitizer_reset_coverage();
182  ExecuteCallback(U);
183  uintptr_t *PCs;
184  uintptr_t NumPCs = __sanitizer_get_coverage_guards(&PCs);
185  bool HasNewPairs = false;
186  for (uintptr_t i = 0; i < NumPCs; i++) {
187    if (!PCs[i]) continue;
188    for (uintptr_t j = 0; j < NumPCs; j++) {
189      if (!PCs[j]) continue;
190      uint64_t Pair = (i << 32) | j;
191      HasNewPairs |= CoveragePairs.insert(Pair).second;
192    }
193  }
194  if (HasNewPairs)
195    return CoveragePairs.size();
196  return 0;
197}
198
199// Experimental.
200// Fuly reset the current coverage state, run a single unit,
201// compute a hash function from the full coverage set,
202// return non-zero if the hash value is new.
203// This produces tons of new units and as is it's only suitable for small tests,
204// e.g. test/FullCoverageSetTest.cpp. FIXME: make it scale.
205size_t Fuzzer::RunOneMaximizeFullCoverageSet(const Unit &U) {
206  __sanitizer_reset_coverage();
207  ExecuteCallback(U);
208  uintptr_t *PCs;
209  uintptr_t NumPCs =__sanitizer_get_coverage_guards(&PCs);
210  if (FullCoverageSets.insert(HashOfArrayOfPCs(PCs, NumPCs)).second)
211    return FullCoverageSets.size();
212  return 0;
213}
214
215size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) {
216  size_t NumCounters = __sanitizer_get_number_of_counters();
217  if (Options.UseCounters) {
218    CounterBitmap.resize(NumCounters);
219    __sanitizer_update_counter_bitset_and_clear_counters(0);
220  }
221  size_t OldCoverage = __sanitizer_get_total_unique_coverage();
222  ExecuteCallback(U);
223  size_t NewCoverage = __sanitizer_get_total_unique_coverage();
224  size_t NumNewBits = 0;
225  if (Options.UseCounters)
226    NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters(
227        CounterBitmap.data());
228
229  if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity)
230    PrintStats("pulse ", NewCoverage);
231
232  if (NewCoverage > OldCoverage || NumNewBits)
233    return NewCoverage;
234  return 0;
235}
236
237void Fuzzer::WriteToOutputCorpus(const Unit &U) {
238  if (Options.OutputCorpus.empty()) return;
239  std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
240  WriteToFile(U, Path);
241  if (Options.Verbosity >= 2)
242    std::cerr << "Written to " << Path << std::endl;
243}
244
245void Fuzzer::WriteToCrash(const Unit &U, const char *Prefix) {
246  std::string Path = Prefix + Hash(U);
247  WriteToFile(U, Path);
248  std::cerr << "CRASHED; file written to " << Path << std::endl;
249}
250
251void Fuzzer::SaveCorpus() {
252  if (Options.OutputCorpus.empty()) return;
253  for (const auto &U : Corpus)
254    WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
255  if (Options.Verbosity)
256    std::cerr << "Written corpus of " << Corpus.size() << " files to "
257              << Options.OutputCorpus << "\n";
258}
259
260size_t Fuzzer::MutateAndTestOne(Unit *U) {
261  size_t NewUnits = 0;
262  for (int i = 0; i < Options.MutateDepth; i++) {
263    if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
264      return NewUnits;
265    MutateWithDFSan(U);
266    Mutate(U, Options.MaxLen);
267    size_t NewCoverage = RunOne(*U);
268    if (NewCoverage) {
269      Corpus.push_back(*U);
270      NewUnits++;
271      PrintStats("NEW   ", NewCoverage, "");
272      if (Options.Verbosity) {
273        std::cerr << " L: " << U->size();
274        if (U->size() < 30) {
275          std::cerr << " ";
276          PrintUnitInASCIIOrTokens(*U, "\t");
277          Print(*U);
278        }
279        std::cerr << "\n";
280      }
281      WriteToOutputCorpus(*U);
282      if (Options.ExitOnFirst)
283        exit(0);
284    }
285  }
286  return NewUnits;
287}
288
289size_t Fuzzer::Loop(size_t NumIterations) {
290  size_t NewUnits = 0;
291  for (size_t i = 1; i <= NumIterations; i++) {
292    for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
293      if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
294        return NewUnits;
295      // First, simply mutate the unit w/o doing crosses.
296      CurrentUnit = Corpus[J1];
297      NewUnits += MutateAndTestOne(&CurrentUnit);
298      // Now, cross with others.
299      if (Options.DoCrossOver) {
300        for (size_t J2 = 0; J2 < Corpus.size(); J2++) {
301          CurrentUnit.clear();
302          CrossOver(Corpus[J1], Corpus[J2], &CurrentUnit, Options.MaxLen);
303          NewUnits += MutateAndTestOne(&CurrentUnit);
304        }
305      }
306    }
307  }
308  return NewUnits;
309}
310
311}  // namespace fuzzer
312