lib/Fuzzer/FuzzerLoop.cpp

   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
  17 namespace fuzzer {
  18
  19 // static
  20 Unit Fuzzer::CurrentUnit;
  21 system_clock::time_point Fuzzer::UnitStartTime;
  22
  23 void Fuzzer::SetDeathCallback() {
  24   __sanitizer_set_death_callback(DeathCallback);
  25 }
  26
  27 void Fuzzer::DeathCallback() {
  28   std::cerr << "DEATH: " <<  std::endl;
  29   Print(CurrentUnit, "\n");
  30   PrintASCII(CurrentUnit, "\n");
  31   WriteToCrash(CurrentUnit, "crash-");
  32 }
  33
  34 void Fuzzer::AlarmCallback() {
  35   size_t Seconds =
  36       duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
  37   std::cerr << "ALARM: working on the last Unit for " << Seconds << " seconds"
  38             << std::endl;
  39   if (Seconds >= 3) {
  40     Print(CurrentUnit, "\n");
  41     PrintASCII(CurrentUnit, "\n");
  42     WriteToCrash(CurrentUnit, "timeout-");
  43   }
  44   exit(1);
  45 }
  46
  47 void Fuzzer::ShuffleAndMinimize() {
  48   bool PreferSmall =
  49       (Options.PreferSmallDuringInitialShuffle == 1 ||
  50        (Options.PreferSmallDuringInitialShuffle == -1 && rand() % 2));
  51   if (Options.Verbosity)
  52     std::cerr << "Shuffle: Size: " << Corpus.size()
  53               << " prefer small: " << PreferSmall
  54               << "\n";
  55   std::vector<Unit> NewCorpus;
  56   std::random_shuffle(Corpus.begin(), Corpus.end());
  57   if (PreferSmall)
  58     std::stable_sort(
  59         Corpus.begin(), Corpus.end(),
  60         [](const Unit &A, const Unit &B) { return A.size() < B.size(); });
  61   size_t MaxCov = 0;
  62   Unit &U = CurrentUnit;
  63   for (const auto &C : Corpus) {
  64     for (size_t First = 0; First < 1; First++) {
  65       U.clear();
  66       size_t Last = std::min(First + Options.MaxLen, C.size());
  67       U.insert(U.begin(), C.begin() + First, C.begin() + Last);
  68       size_t NewCoverage = RunOne(U);
  69       if (NewCoverage) {
  70         MaxCov = NewCoverage;
  71         NewCorpus.push_back(U);
  72         if (Options.Verbosity >= 2)
  73           std::cerr << "NEW0: " << NewCoverage
  74                     << " L " << U.size()
  75                     << "\n";
  76       }
  77     }
  78   }
  79   Corpus = NewCorpus;
  80   if (Options.Verbosity)
  81     std::cerr << "Shuffle done: " << Corpus.size() << " IC: " << MaxCov << "\n";
  82 }
  83
  84 size_t Fuzzer::RunOne(const Unit &U) {
  85   UnitStartTime = system_clock::now();
  86   TotalNumberOfRuns++;
  87   if (Options.UseFullCoverageSet)
  88     return RunOneMaximizeFullCoverageSet(U);
  89   if (Options.UseCoveragePairs)
  90     return RunOneMaximizeCoveragePairs(U);
  91   return RunOneMaximizeTotalCoverage(U);
  92 }
  93
  94 static uintptr_t HashOfArrayOfPCs(uintptr_t *PCs, uintptr_t NumPCs) {
  95   uintptr_t Res = 0;
  96   for (uintptr_t i = 0; i < NumPCs; i++) {
  97     Res = (Res + PCs[i]) * 7;
  98   }
  99   return Res;
 100 }
 101
 102 // Experimental. Does not yet scale.
 103 // Fuly reset the current coverage state, run a single unit,
 104 // collect all coverage pairs and return non-zero if a new pair is observed.
 105 size_t Fuzzer::RunOneMaximizeCoveragePairs(const Unit &U) {
 106   __sanitizer_reset_coverage();
 107   Callback(U.data(), U.size());
 108   uintptr_t *PCs;
 109   uintptr_t NumPCs = __sanitizer_get_coverage_guards(&PCs);
 110   bool HasNewPairs = false;
 111   for (uintptr_t i = 0; i < NumPCs; i++) {
 112     if (!PCs[i]) continue;
 113     for (uintptr_t j = 0; j < NumPCs; j++) {
 114       if (!PCs[j]) continue;
 115       uint64_t Pair = (i << 32) | j;
 116       HasNewPairs |= CoveragePairs.insert(Pair).second;
 117     }
 118   }
 119   if (HasNewPairs)
 120     return CoveragePairs.size();
 121   return 0;
 122 }
 123
 124 // Experimental.
 125 // Fuly reset the current coverage state, run a single unit,
 126 // compute a hash function from the full coverage set,
 127 // return non-zero if the hash value is new.
 128 // This produces tons of new units and as is it's only suitable for small tests,
 129 // e.g. test/FullCoverageSetTest.cpp. FIXME: make it scale.
 130 size_t Fuzzer::RunOneMaximizeFullCoverageSet(const Unit &U) {
 131   __sanitizer_reset_coverage();
 132   Callback(U.data(), U.size());
 133   uintptr_t *PCs;
 134   uintptr_t NumPCs =__sanitizer_get_coverage_guards(&PCs);
 135   if (FullCoverageSets.insert(HashOfArrayOfPCs(PCs, NumPCs)).second)
 136     return FullCoverageSets.size();
 137   return 0;
 138 }
 139
 140 size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) {
 141   size_t OldCoverage = __sanitizer_get_total_unique_coverage();
 142   Callback(U.data(), U.size());
 143   size_t NewCoverage = __sanitizer_get_total_unique_coverage();
 144   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) {
 145     size_t Seconds = secondsSinceProcessStartUp();
 146     std::cerr
 147         << "#" << TotalNumberOfRuns
 148         << "\tcov: " << NewCoverage
 149         << "\texec/s: " << (Seconds ? TotalNumberOfRuns / Seconds : 0) << "\n";
 150   }
 151   if (NewCoverage > OldCoverage)
 152     return NewCoverage;
 153   return 0;
 154 }
 155
 156 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
 157   if (Options.OutputCorpus.empty()) return;
 158   std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
 159   WriteToFile(U, Path);
 160   if (Options.Verbosity >= 2)
 161     std::cerr << "Written to " << Path << std::endl;
 162 }
 163
 164 void Fuzzer::WriteToCrash(const Unit &U, const char *Prefix) {
 165   std::string Path = Prefix + Hash(U);
 166   WriteToFile(U, Path);
 167   std::cerr << "CRASHED; file written to " << Path << std::endl;
 168 }
 169
 170 void Fuzzer::SaveCorpus() {
 171   if (Options.OutputCorpus.empty()) return;
 172   for (const auto &U : Corpus)
 173     WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
 174   if (Options.Verbosity)
 175     std::cerr << "Written corpus of " << Corpus.size() << " files to "
 176               << Options.OutputCorpus << "\n";
 177 }
 178
 179 size_t Fuzzer::MutateAndTestOne(Unit *U) {
 180   size_t NewUnits = 0;
 181   for (int i = 0; i < Options.MutateDepth; i++) {
 182     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 183       return NewUnits;
 184     Mutate(U, Options.MaxLen);
 185     size_t NewCoverage = RunOne(*U);
 186     if (NewCoverage) {
 187       Corpus.push_back(*U);
 188       NewUnits++;
 189       if (Options.Verbosity) {
 190         std::cerr << "#" << TotalNumberOfRuns
 191                   << "\tNEW: " << NewCoverage
 192                   << " L: " << U->size()
 193                   << " S: " << Corpus.size()
 194                   << " I: " << i
 195                   << "\t";
 196         if (U->size() < 30) {
 197           PrintASCII(*U);
 198           std::cerr << "\t";
 199           Print(*U);
 200         }
 201         std::cerr << "\n";
 202       }
 203       WriteToOutputCorpus(*U);
 204       if (Options.ExitOnFirst)
 205         exit(0);
 206     }
 207   }
 208   return NewUnits;
 209 }
 210
 211 size_t Fuzzer::Loop(size_t NumIterations) {
 212   size_t NewUnits = 0;
 213   for (size_t i = 1; i <= NumIterations; i++) {
 214     for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
 215       if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 216         return NewUnits;
 217       // First, simply mutate the unit w/o doing crosses.
 218       CurrentUnit = Corpus[J1];
 219       NewUnits += MutateAndTestOne(&CurrentUnit);
 220       // Now, cross with others.
 221       if (Options.DoCrossOver) {
 222         for (size_t J2 = 0; J2 < Corpus.size(); J2++) {
 223           CurrentUnit.clear();
 224           CrossOver(Corpus[J1], Corpus[J2], &CurrentUnit, Options.MaxLen);
 225           NewUnits += MutateAndTestOne(&CurrentUnit);
 226         }
 227       }
 228     }
 229   }
 230   return NewUnits;
 231 }
 232
 233 }  // namespace fuzzer