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 // Only one Fuzzer per process. 20 static Fuzzer *F; 21 22 Fuzzer::Fuzzer(UserCallback Callback, FuzzingOptions Options) 23 : Callback(Callback), Options(Options) { 24 SetDeathCallback(); 25 InitializeDFSan(); 26 assert(!F); 27 F = this; 28 } 29 30 void Fuzzer::SetDeathCallback() { 31 __sanitizer_set_death_callback(StaticDeathCallback); 32 } 33 34 void 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 45 void Fuzzer::StaticDeathCallback() { 46 assert(F); 47 F->DeathCallback(); 48 } 49 50 void Fuzzer::DeathCallback() { 51 std::cerr << "DEATH: " << std::endl; 52 Print(CurrentUnit, "\n"); 53 PrintUnitInASCIIOrTokens(CurrentUnit, "\n"); 54 WriteToCrash(CurrentUnit, "crash-"); 55 } 56 57 void Fuzzer::StaticAlarmCallback() { 58 assert(F); 59 F->AlarmCallback(); 60 } 61 62 void 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 75 void 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 89 void 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 124 size_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 146 static 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 154 Unit 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 168 void 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. 180 size_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. 205 size_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 215 size_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 237 void 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 245 void 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 251 void 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 260 size_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 289 size_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
