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