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   return RunOneMaximizeTotalCoverage(U);
  90 }
  91
  92 static uintptr_t HashOfArrayOfPCs(uintptr_t *PCs, uintptr_t NumPCs) {
  93   uintptr_t Res = 0;
  94   for (uintptr_t i = 0; i < NumPCs; i++) {
  95     Res = (Res + PCs[i]) * 7;
  96   }
  97   return Res;
  98 }
  99
 100 // Fuly reset the current coverage state, run a single unit,
 101 // compute a hash function from the full coverage set,
 102 // return non-zero if the hash value is new.
 103 // This produces tons of new units and as is it's only suitable for small tests,
 104 // e.g. test/FullCoverageSetTest.cpp. FIXME: make it scale.
 105 size_t Fuzzer::RunOneMaximizeFullCoverageSet(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   if (FullCoverageSets.insert(HashOfArrayOfPCs(PCs, NumPCs)).second)
 111     return FullCoverageSets.size();
 112   return 0;
 113 }
 114
 115 size_t Fuzzer::RunOneMaximizeTotalCoverage(const Unit &U) {
 116   size_t OldCoverage = __sanitizer_get_total_unique_coverage();
 117   Callback(U.data(), U.size());
 118   size_t NewCoverage = __sanitizer_get_total_unique_coverage();
 119   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) && Options.Verbosity) {
 120     size_t Seconds = secondsSinceProcessStartUp();
 121     std::cerr
 122         << "#" << TotalNumberOfRuns
 123         << "\tcov: " << NewCoverage
 124         << "\texec/s: " << (Seconds ? TotalNumberOfRuns / Seconds : 0) << "\n";
 125   }
 126   if (NewCoverage > OldCoverage)
 127     return NewCoverage;
 128   return 0;
 129 }
 130
 131 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
 132   if (Options.OutputCorpus.empty()) return;
 133   std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
 134   WriteToFile(U, Path);
 135   if (Options.Verbosity >= 2)
 136     std::cerr << "Written to " << Path << std::endl;
 137 }
 138
 139 void Fuzzer::WriteToCrash(const Unit &U, const char *Prefix) {
 140   std::string Path = Prefix + Hash(U);
 141   WriteToFile(U, Path);
 142   std::cerr << "CRASHED; file written to " << Path << std::endl;
 143 }
 144
 145 void Fuzzer::SaveCorpus() {
 146   if (Options.OutputCorpus.empty()) return;
 147   for (const auto &U : Corpus)
 148     WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
 149   if (Options.Verbosity)
 150     std::cerr << "Written corpus of " << Corpus.size() << " files to "
 151               << Options.OutputCorpus << "\n";
 152 }
 153
 154 size_t Fuzzer::MutateAndTestOne(Unit *U) {
 155   size_t NewUnits = 0;
 156   for (int i = 0; i < Options.MutateDepth; i++) {
 157     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 158       return NewUnits;
 159     Mutate(U, Options.MaxLen);
 160     size_t NewCoverage = RunOne(*U);
 161     if (NewCoverage) {
 162       Corpus.push_back(*U);
 163       NewUnits++;
 164       if (Options.Verbosity) {
 165         std::cerr << "#" << TotalNumberOfRuns
 166                   << "\tNEW: " << NewCoverage
 167                   << " L: " << U->size()
 168                   << " S: " << Corpus.size()
 169                   << " I: " << i
 170                   << "\t";
 171         if (U->size() < 30) {
 172           PrintASCII(*U);
 173           std::cerr << "\t";
 174           Print(*U);
 175         }
 176         std::cerr << "\n";
 177       }
 178       WriteToOutputCorpus(*U);
 179       if (Options.ExitOnFirst)
 180         exit(0);
 181     }
 182   }
 183   return NewUnits;
 184 }
 185
 186 size_t Fuzzer::Loop(size_t NumIterations) {
 187   size_t NewUnits = 0;
 188   for (size_t i = 1; i <= NumIterations; i++) {
 189     for (size_t J1 = 0; J1 < Corpus.size(); J1++) {
 190       if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
 191         return NewUnits;
 192       // First, simply mutate the unit w/o doing crosses.
 193       CurrentUnit = Corpus[J1];
 194       NewUnits += MutateAndTestOne(&CurrentUnit);
 195       // Now, cross with others.
 196       if (Options.DoCrossOver) {
 197         for (size_t J2 = 0; J2 < Corpus.size(); J2++) {
 198           CurrentUnit.clear();
 199           CrossOver(Corpus[J1], Corpus[J2], &CurrentUnit, Options.MaxLen);
 200           NewUnits += MutateAndTestOne(&CurrentUnit);
 201         }
 202       }
 203     }
 204   }
 205   return NewUnits;
 206 }
 207
 208 }  // namespace fuzzer