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 NumCounters = __sanitizer_get_number_of_counters();
 142   if (Options.UseCounters) {
 143     CounterBitmap.resize(NumCounters);
 144     __sanitizer_update_counter_bitset_and_clear_counters(0);
 145   }
 146   size_t OldCoverage = __sanitizer_get_total_unique_coverage();
 147   Callback(U.data(), U.size());
 148   size_t NewCoverage = __sanitizer_get_total_unique_coverage();
 149   size_t NumNewBits = 0;
 150   if (Options.UseCounters)
 151     NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters(
 152         CounterBitmap.data());
 153
 154   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) {
 155     size_t Seconds = secondsSinceProcessStartUp();
 156     std::cerr
 157         << "#" << TotalNumberOfRuns
 158         << "\tcov: " << NewCoverage
 159         << "\tbits: " << TotalBits()
 160         << "\texec/s: " << (Seconds ? TotalNumberOfRuns / Seconds : 0) << "\n";
 161   }
 162   if (NewCoverage > OldCoverage || NumNewBits)
 163     return NewCoverage;
 164   return 0;
 165 }
 166
 167 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
 168   if (Options.OutputCorpus.empty()) return;
 169   std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
 170   WriteToFile(U, Path);
 171   if (Options.Verbosity >= 2)
 172     std::cerr << "Written to " << Path << std::endl;
 173 }
 174
 175 void Fuzzer::WriteToCrash(const Unit &U, const char *Prefix) {
 176   std::string Path = Prefix + Hash(U);
 177   WriteToFile(U, Path);
 178   std::cerr << "CRASHED; file written to " << Path << std::endl;
 179 }
 180
 181 void Fuzzer::SaveCorpus() {
 182   if (Options.OutputCorpus.empty()) return;
 183   for (const auto &U : Corpus)
 184     WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
 185   if (Options.Verbosity)
 186     std::cerr << "Written corpus of " << Corpus.size() << " files to "
 187               << Options.OutputCorpus << "\n";
 188 }
 189
 190 size_t Fuzzer::MutateAndTestOne(Unit *U) {
 191   size_t NewUnits = 0;
 192   for (int i = 0; i < Options.MutateDepth; i++) {
 193     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 194       return NewUnits;
 195     Mutate(U, Options.MaxLen);
 196     size_t NewCoverage = RunOne(*U);
 197     if (NewCoverage) {
 198       Corpus.push_back(*U);
 199       NewUnits++;
 200       if (Options.Verbosity) {
 201         std::cerr << "#" << TotalNumberOfRuns
 202                   << "\tNEW: " << NewCoverage
 203                   << " B: " << TotalBits()
 204                   << " L: " << U->size()
 205                   << " S: " << Corpus.size()
 206                   << " I: " << i
 207                   << "\t";
 208         if (U->size() < 30) {
 209           PrintASCII(*U);
 210           std::cerr << "\t";
 211           Print(*U);
 212         }
 213         std::cerr << "\n";
 214       }
 215       WriteToOutputCorpus(*U);
 216       if (Options.ExitOnFirst)
 217         exit(0);
 218     }
 219   }
 220   return NewUnits;
 221 }
 222
 223 size_t Fuzzer::Loop(size_t NumIterations) {
 224   size_t NewUnits = 0;
 225   for (size_t i = 1; i <= NumIterations; i++) {
 226     for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
 227       if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 228         return NewUnits;
 229       // First, simply mutate the unit w/o doing crosses.
 230       CurrentUnit = Corpus[J1];
 231       NewUnits += MutateAndTestOne(&CurrentUnit);
 232       // Now, cross with others.
 233       if (Options.DoCrossOver) {
 234         for (size_t J2 = 0; J2 < Corpus.size(); J2++) {
 235           CurrentUnit.clear();
 236           CrossOver(Corpus[J1], Corpus[J2], &CurrentUnit, Options.MaxLen);
 237           NewUnits += MutateAndTestOne(&CurrentUnit);
 238         }
 239       }
 240     }
 241   }
 242   return NewUnits;
 243 }
 244
 245 }  // namespace fuzzer