594 lines · c
1//===- FuzzerCorpus.h - Internal header for the Fuzzer ----------*- C++ -* ===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8// fuzzer::InputCorpus9//===----------------------------------------------------------------------===//10 11#ifndef LLVM_FUZZER_CORPUS12#define LLVM_FUZZER_CORPUS13 14#include "FuzzerDataFlowTrace.h"15#include "FuzzerDefs.h"16#include "FuzzerIO.h"17#include "FuzzerRandom.h"18#include "FuzzerSHA1.h"19#include "FuzzerTracePC.h"20#include <algorithm>21#include <bitset>22#include <chrono>23#include <numeric>24#include <random>25#include <unordered_set>26 27namespace fuzzer {28 29struct InputInfo {30 Unit U; // The actual input data.31 std::chrono::microseconds TimeOfUnit;32 uint8_t Sha1[kSHA1NumBytes]; // Checksum.33 // Number of features that this input has and no smaller input has.34 size_t NumFeatures = 0;35 size_t Tmp = 0; // Used by ValidateFeatureSet.36 // Stats.37 size_t NumExecutedMutations = 0;38 size_t NumSuccessfulMutations = 0;39 bool NeverReduce = false;40 bool MayDeleteFile = false;41 bool Reduced = false;42 bool HasFocusFunction = false;43 std::vector<uint32_t> UniqFeatureSet;44 std::vector<uint8_t> DataFlowTraceForFocusFunction;45 // Power schedule.46 bool NeedsEnergyUpdate = false;47 double Energy = 0.0;48 double SumIncidence = 0.0;49 std::vector<std::pair<uint32_t, uint16_t>> FeatureFreqs;50 51 // Delete feature Idx and its frequency from FeatureFreqs.52 bool DeleteFeatureFreq(uint32_t Idx) {53 if (FeatureFreqs.empty())54 return false;55 56 // Binary search over local feature frequencies sorted by index.57 auto Lower = std::lower_bound(FeatureFreqs.begin(), FeatureFreqs.end(),58 std::pair<uint32_t, uint16_t>(Idx, 0));59 60 if (Lower != FeatureFreqs.end() && Lower->first == Idx) {61 FeatureFreqs.erase(Lower);62 return true;63 }64 return false;65 }66 67 // Assign more energy to a high-entropy seed, i.e., that reveals more68 // information about the globally rare features in the neighborhood of the69 // seed. Since we do not know the entropy of a seed that has never been70 // executed we assign fresh seeds maximum entropy and let II->Energy approach71 // the true entropy from above. If ScalePerExecTime is true, the computed72 // entropy is scaled based on how fast this input executes compared to the73 // average execution time of inputs. The faster an input executes, the more74 // energy gets assigned to the input.75 void UpdateEnergy(size_t GlobalNumberOfFeatures, bool ScalePerExecTime,76 std::chrono::microseconds AverageUnitExecutionTime) {77 Energy = 0.0;78 SumIncidence = 0.0;79 80 // Apply add-one smoothing to locally discovered features.81 for (const auto &F : FeatureFreqs) {82 double LocalIncidence = F.second + 1;83 Energy -= LocalIncidence * log(LocalIncidence);84 SumIncidence += LocalIncidence;85 }86 87 // Apply add-one smoothing to locally undiscovered features.88 // PreciseEnergy -= 0; // since log(1.0) == 0)89 SumIncidence +=90 static_cast<double>(GlobalNumberOfFeatures - FeatureFreqs.size());91 92 // Add a single locally abundant feature apply add-one smoothing.93 double AbdIncidence = static_cast<double>(NumExecutedMutations + 1);94 Energy -= AbdIncidence * log(AbdIncidence);95 SumIncidence += AbdIncidence;96 97 // Normalize.98 if (SumIncidence != 0)99 Energy = Energy / SumIncidence + log(SumIncidence);100 101 if (ScalePerExecTime) {102 // Scaling to favor inputs with lower execution time.103 uint32_t PerfScore = 100;104 if (TimeOfUnit.count() > AverageUnitExecutionTime.count() * 10)105 PerfScore = 10;106 else if (TimeOfUnit.count() > AverageUnitExecutionTime.count() * 4)107 PerfScore = 25;108 else if (TimeOfUnit.count() > AverageUnitExecutionTime.count() * 2)109 PerfScore = 50;110 else if (TimeOfUnit.count() * 3 > AverageUnitExecutionTime.count() * 4)111 PerfScore = 75;112 else if (TimeOfUnit.count() * 4 < AverageUnitExecutionTime.count())113 PerfScore = 300;114 else if (TimeOfUnit.count() * 3 < AverageUnitExecutionTime.count())115 PerfScore = 200;116 else if (TimeOfUnit.count() * 2 < AverageUnitExecutionTime.count())117 PerfScore = 150;118 119 Energy *= PerfScore;120 }121 }122 123 // Increment the frequency of the feature Idx.124 void UpdateFeatureFrequency(uint32_t Idx) {125 NeedsEnergyUpdate = true;126 127 // The local feature frequencies is an ordered vector of pairs.128 // If there are no local feature frequencies, push_back preserves order.129 // Set the feature frequency for feature Idx32 to 1.130 if (FeatureFreqs.empty()) {131 FeatureFreqs.push_back(std::pair<uint32_t, uint16_t>(Idx, 1));132 return;133 }134 135 // Binary search over local feature frequencies sorted by index.136 auto Lower = std::lower_bound(FeatureFreqs.begin(), FeatureFreqs.end(),137 std::pair<uint32_t, uint16_t>(Idx, 0));138 139 // If feature Idx32 already exists, increment its frequency.140 // Otherwise, insert a new pair right after the next lower index.141 if (Lower != FeatureFreqs.end() && Lower->first == Idx) {142 Lower->second++;143 } else {144 FeatureFreqs.insert(Lower, std::pair<uint32_t, uint16_t>(Idx, 1));145 }146 }147};148 149struct EntropicOptions {150 bool Enabled;151 size_t NumberOfRarestFeatures;152 size_t FeatureFrequencyThreshold;153 bool ScalePerExecTime;154};155 156class InputCorpus {157 static const uint32_t kFeatureSetSize = 1 << 21;158 static const uint8_t kMaxMutationFactor = 20;159 static const size_t kSparseEnergyUpdates = 100;160 161 size_t NumExecutedMutations = 0;162 163 EntropicOptions Entropic;164 165public:166 InputCorpus(const std::string &OutputCorpus, EntropicOptions Entropic)167 : Entropic(Entropic), OutputCorpus(OutputCorpus) {168 memset(InputSizesPerFeature, 0, sizeof(InputSizesPerFeature));169 memset(SmallestElementPerFeature, 0, sizeof(SmallestElementPerFeature));170 }171 ~InputCorpus() {172 for (auto II : Inputs)173 delete II;174 }175 size_t size() const { return Inputs.size(); }176 size_t SizeInBytes() const {177 size_t Res = 0;178 for (auto II : Inputs)179 Res += II->U.size();180 return Res;181 }182 size_t NumActiveUnits() const {183 size_t Res = 0;184 for (auto II : Inputs)185 Res += !II->U.empty();186 return Res;187 }188 size_t MaxInputSize() const {189 size_t Res = 0;190 for (auto II : Inputs)191 Res = std::max(Res, II->U.size());192 return Res;193 }194 void IncrementNumExecutedMutations() { NumExecutedMutations++; }195 196 size_t NumInputsThatTouchFocusFunction() {197 return std::count_if(Inputs.begin(), Inputs.end(), [](const InputInfo *II) {198 return II->HasFocusFunction;199 });200 }201 202 size_t NumInputsWithDataFlowTrace() {203 return std::count_if(Inputs.begin(), Inputs.end(), [](const InputInfo *II) {204 return !II->DataFlowTraceForFocusFunction.empty();205 });206 }207 208 bool empty() const { return Inputs.empty(); }209 const Unit &operator[] (size_t Idx) const { return Inputs[Idx]->U; }210 InputInfo *AddToCorpus(const Unit &U, size_t NumFeatures, bool MayDeleteFile,211 bool HasFocusFunction, bool NeverReduce,212 std::chrono::microseconds TimeOfUnit,213 const std::vector<uint32_t> &FeatureSet,214 const DataFlowTrace &DFT, const InputInfo *BaseII) {215 assert(!U.empty());216 if (FeatureDebug)217 Printf("ADD_TO_CORPUS %zd NF %zd\n", Inputs.size(), NumFeatures);218 // Inputs.size() is cast to uint32_t below.219 assert(Inputs.size() < std::numeric_limits<uint32_t>::max());220 Inputs.push_back(new InputInfo());221 InputInfo &II = *Inputs.back();222 II.U = U;223 II.NumFeatures = NumFeatures;224 II.NeverReduce = NeverReduce;225 II.TimeOfUnit = TimeOfUnit;226 II.MayDeleteFile = MayDeleteFile;227 II.UniqFeatureSet = FeatureSet;228 II.HasFocusFunction = HasFocusFunction;229 // Assign maximal energy to the new seed.230 II.Energy = RareFeatures.empty() ? 1.0 : log(RareFeatures.size());231 II.SumIncidence = static_cast<double>(RareFeatures.size());232 II.NeedsEnergyUpdate = false;233 std::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());234 ComputeSHA1(U.data(), U.size(), II.Sha1);235 auto Sha1Str = Sha1ToString(II.Sha1);236 Hashes.insert(Sha1Str);237 if (HasFocusFunction)238 if (auto V = DFT.Get(Sha1Str))239 II.DataFlowTraceForFocusFunction = *V;240 // This is a gross heuristic.241 // Ideally, when we add an element to a corpus we need to know its DFT.242 // But if we don't, we'll use the DFT of its base input.243 if (II.DataFlowTraceForFocusFunction.empty() && BaseII)244 II.DataFlowTraceForFocusFunction = BaseII->DataFlowTraceForFocusFunction;245 DistributionNeedsUpdate = true;246 PrintCorpus();247 // ValidateFeatureSet();248 return &II;249 }250 251 // Debug-only252 void PrintUnit(const Unit &U) {253 if (!FeatureDebug) return;254 for (uint8_t C : U) {255 if (C != 'F' && C != 'U' && C != 'Z')256 C = '.';257 Printf("%c", C);258 }259 }260 261 // Debug-only262 void PrintFeatureSet(const std::vector<uint32_t> &FeatureSet) {263 if (!FeatureDebug) return;264 Printf("{");265 for (uint32_t Feature: FeatureSet)266 Printf("%u,", Feature);267 Printf("}");268 }269 270 // Debug-only271 void PrintCorpus() {272 if (!FeatureDebug) return;273 Printf("======= CORPUS:\n");274 int i = 0;275 for (auto II : Inputs) {276 if (std::find(II->U.begin(), II->U.end(), 'F') != II->U.end()) {277 Printf("[%2d] ", i);278 Printf("%s sz=%zd ", Sha1ToString(II->Sha1).c_str(), II->U.size());279 PrintUnit(II->U);280 Printf(" ");281 PrintFeatureSet(II->UniqFeatureSet);282 Printf("\n");283 }284 i++;285 }286 }287 288 void Replace(InputInfo *II, const Unit &U,289 std::chrono::microseconds TimeOfUnit) {290 assert(II->U.size() > U.size());291 Hashes.erase(Sha1ToString(II->Sha1));292 DeleteFile(*II);293 ComputeSHA1(U.data(), U.size(), II->Sha1);294 Hashes.insert(Sha1ToString(II->Sha1));295 II->U = U;296 II->Reduced = true;297 II->TimeOfUnit = TimeOfUnit;298 DistributionNeedsUpdate = true;299 }300 301 bool HasUnit(const Unit &U) { return Hashes.count(Hash(U)); }302 bool HasUnit(const std::string &H) { return Hashes.count(H); }303 InputInfo &ChooseUnitToMutate(Random &Rand) {304 InputInfo &II = *Inputs[ChooseUnitIdxToMutate(Rand)];305 assert(!II.U.empty());306 return II;307 }308 309 InputInfo &ChooseUnitToCrossOverWith(Random &Rand, bool UniformDist) {310 if (!UniformDist) {311 return ChooseUnitToMutate(Rand);312 }313 InputInfo &II = *Inputs[Rand(Inputs.size())];314 assert(!II.U.empty());315 return II;316 }317 318 // Returns an index of random unit from the corpus to mutate.319 size_t ChooseUnitIdxToMutate(Random &Rand) {320 UpdateCorpusDistribution(Rand);321 size_t Idx = static_cast<size_t>(CorpusDistribution(Rand));322 assert(Idx < Inputs.size());323 return Idx;324 }325 326 void PrintStats() {327 for (size_t i = 0; i < Inputs.size(); i++) {328 const auto &II = *Inputs[i];329 Printf(" [% 3zd %s] sz: % 5zd runs: % 5zd succ: % 5zd focus: %d\n", i,330 Sha1ToString(II.Sha1).c_str(), II.U.size(),331 II.NumExecutedMutations, II.NumSuccessfulMutations,332 II.HasFocusFunction);333 }334 }335 336 void PrintFeatureSet() {337 for (size_t i = 0; i < kFeatureSetSize; i++) {338 if(size_t Sz = GetFeature(i))339 Printf("[%zd: id %zd sz%zd] ", i, (size_t)SmallestElementPerFeature[i],340 Sz);341 }342 Printf("\n\t");343 for (size_t i = 0; i < Inputs.size(); i++)344 if (size_t N = Inputs[i]->NumFeatures)345 Printf(" %zd=>%zd ", i, N);346 Printf("\n");347 }348 349 void DeleteFile(const InputInfo &II) {350 if (!OutputCorpus.empty() && II.MayDeleteFile)351 RemoveFile(DirPlusFile(OutputCorpus, Sha1ToString(II.Sha1)));352 }353 354 void DeleteInput(size_t Idx) {355 InputInfo &II = *Inputs[Idx];356 DeleteFile(II);357 Unit().swap(II.U);358 II.Energy = 0.0;359 II.NeedsEnergyUpdate = false;360 DistributionNeedsUpdate = true;361 if (FeatureDebug)362 Printf("EVICTED %zd\n", Idx);363 }364 365 void AddRareFeature(uint32_t Idx) {366 // Maintain *at least* TopXRarestFeatures many rare features367 // and all features with a frequency below ConsideredRare.368 // Remove all other features.369 while (RareFeatures.size() > Entropic.NumberOfRarestFeatures &&370 FreqOfMostAbundantRareFeature > Entropic.FeatureFrequencyThreshold) {371 372 // Find most and second most abbundant feature.373 uint32_t MostAbundantRareFeatureIndices[2] = {RareFeatures[0],374 RareFeatures[0]};375 size_t Delete = 0;376 for (size_t i = 0; i < RareFeatures.size(); i++) {377 uint32_t Idx2 = RareFeatures[i];378 if (GlobalFeatureFreqs[Idx2] >=379 GlobalFeatureFreqs[MostAbundantRareFeatureIndices[0]]) {380 MostAbundantRareFeatureIndices[1] = MostAbundantRareFeatureIndices[0];381 MostAbundantRareFeatureIndices[0] = Idx2;382 Delete = i;383 }384 }385 386 // Remove most abundant rare feature.387 IsRareFeature[Delete] = false;388 RareFeatures[Delete] = RareFeatures.back();389 RareFeatures.pop_back();390 391 for (auto II : Inputs) {392 if (II->DeleteFeatureFreq(MostAbundantRareFeatureIndices[0]))393 II->NeedsEnergyUpdate = true;394 }395 396 // Set 2nd most abundant as the new most abundant feature count.397 FreqOfMostAbundantRareFeature =398 GlobalFeatureFreqs[MostAbundantRareFeatureIndices[1]];399 }400 401 // Add rare feature, handle collisions, and update energy.402 RareFeatures.push_back(Idx);403 IsRareFeature[Idx] = true;404 GlobalFeatureFreqs[Idx] = 0;405 for (auto II : Inputs) {406 II->DeleteFeatureFreq(Idx);407 408 // Apply add-one smoothing to this locally undiscovered feature.409 // Zero energy seeds will never be fuzzed and remain zero energy.410 if (II->Energy > 0.0) {411 II->SumIncidence += 1;412 II->Energy += log(II->SumIncidence) / II->SumIncidence;413 }414 }415 416 DistributionNeedsUpdate = true;417 }418 419 bool AddFeature(size_t Idx, uint32_t NewSize, bool Shrink) {420 assert(NewSize);421 Idx = Idx % kFeatureSetSize;422 uint32_t OldSize = GetFeature(Idx);423 if (OldSize == 0 || (Shrink && OldSize > NewSize)) {424 if (OldSize > 0) {425 size_t OldIdx = SmallestElementPerFeature[Idx];426 InputInfo &II = *Inputs[OldIdx];427 assert(II.NumFeatures > 0);428 II.NumFeatures--;429 if (II.NumFeatures == 0)430 DeleteInput(OldIdx);431 } else {432 NumAddedFeatures++;433 if (Entropic.Enabled)434 AddRareFeature((uint32_t)Idx);435 }436 NumUpdatedFeatures++;437 if (FeatureDebug)438 Printf("ADD FEATURE %zd sz %d\n", Idx, NewSize);439 // Inputs.size() is guaranteed to be less than UINT32_MAX by AddToCorpus.440 SmallestElementPerFeature[Idx] = static_cast<uint32_t>(Inputs.size());441 InputSizesPerFeature[Idx] = NewSize;442 return true;443 }444 return false;445 }446 447 // Increment frequency of feature Idx globally and locally.448 void UpdateFeatureFrequency(InputInfo *II, size_t Idx) {449 uint32_t Idx32 = Idx % kFeatureSetSize;450 451 // Saturated increment.452 if (GlobalFeatureFreqs[Idx32] == 0xFFFF)453 return;454 uint16_t Freq = GlobalFeatureFreqs[Idx32]++;455 456 // Skip if abundant.457 if (Freq > FreqOfMostAbundantRareFeature || !IsRareFeature[Idx32])458 return;459 460 // Update global frequencies.461 if (Freq == FreqOfMostAbundantRareFeature)462 FreqOfMostAbundantRareFeature++;463 464 // Update local frequencies.465 if (II)466 II->UpdateFeatureFrequency(Idx32);467 }468 469 size_t NumFeatures() const { return NumAddedFeatures; }470 size_t NumFeatureUpdates() const { return NumUpdatedFeatures; }471 472private:473 474 static const bool FeatureDebug = false;475 476 uint32_t GetFeature(size_t Idx) const { return InputSizesPerFeature[Idx]; }477 478 void ValidateFeatureSet() {479 if (FeatureDebug)480 PrintFeatureSet();481 for (size_t Idx = 0; Idx < kFeatureSetSize; Idx++)482 if (GetFeature(Idx))483 Inputs[SmallestElementPerFeature[Idx]]->Tmp++;484 for (auto II: Inputs) {485 if (II->Tmp != II->NumFeatures)486 Printf("ZZZ %zd %zd\n", II->Tmp, II->NumFeatures);487 assert(II->Tmp == II->NumFeatures);488 II->Tmp = 0;489 }490 }491 492 // Updates the probability distribution for the units in the corpus.493 // Must be called whenever the corpus or unit weights are changed.494 //495 // Hypothesis: inputs that maximize information about globally rare features496 // are interesting.497 void UpdateCorpusDistribution(Random &Rand) {498 // Skip update if no seeds or rare features were added/deleted.499 // Sparse updates for local change of feature frequencies,500 // i.e., randomly do not skip.501 if (!DistributionNeedsUpdate &&502 (!Entropic.Enabled || Rand(kSparseEnergyUpdates)))503 return;504 505 DistributionNeedsUpdate = false;506 507 size_t N = Inputs.size();508 assert(N);509 Intervals.resize(N + 1);510 Weights.resize(N);511 std::iota(Intervals.begin(), Intervals.end(), 0);512 513 std::chrono::microseconds AverageUnitExecutionTime(0);514 for (auto II : Inputs) {515 AverageUnitExecutionTime += II->TimeOfUnit;516 }517 AverageUnitExecutionTime /= N;518 519 bool VanillaSchedule = true;520 if (Entropic.Enabled) {521 for (auto II : Inputs) {522 if (II->NeedsEnergyUpdate && II->Energy != 0.0) {523 II->NeedsEnergyUpdate = false;524 II->UpdateEnergy(RareFeatures.size(), Entropic.ScalePerExecTime,525 AverageUnitExecutionTime);526 }527 }528 529 for (size_t i = 0; i < N; i++) {530 531 if (Inputs[i]->NumFeatures == 0) {532 // If the seed doesn't represent any features, assign zero energy.533 Weights[i] = 0.;534 } else if (Inputs[i]->NumExecutedMutations / kMaxMutationFactor >535 NumExecutedMutations / Inputs.size()) {536 // If the seed was fuzzed a lot more than average, assign zero energy.537 Weights[i] = 0.;538 } else {539 // Otherwise, simply assign the computed energy.540 Weights[i] = Inputs[i]->Energy;541 }542 543 // If energy for all seeds is zero, fall back to vanilla schedule.544 if (Weights[i] > 0.0)545 VanillaSchedule = false;546 }547 }548 549 if (VanillaSchedule) {550 for (size_t i = 0; i < N; i++)551 Weights[i] =552 Inputs[i]->NumFeatures553 ? static_cast<double>((i + 1) *554 (Inputs[i]->HasFocusFunction ? 1000 : 1))555 : 0.;556 }557 558 if (FeatureDebug) {559 for (size_t i = 0; i < N; i++)560 Printf("%zd ", Inputs[i]->NumFeatures);561 Printf("SCORE\n");562 for (size_t i = 0; i < N; i++)563 Printf("%f ", Weights[i]);564 Printf("Weights\n");565 }566 CorpusDistribution = std::piecewise_constant_distribution<double>(567 Intervals.begin(), Intervals.end(), Weights.begin());568 }569 std::piecewise_constant_distribution<double> CorpusDistribution;570 571 std::vector<double> Intervals;572 std::vector<double> Weights;573 574 std::unordered_set<std::string> Hashes;575 std::vector<InputInfo *> Inputs;576 577 size_t NumAddedFeatures = 0;578 size_t NumUpdatedFeatures = 0;579 uint32_t InputSizesPerFeature[kFeatureSetSize];580 uint32_t SmallestElementPerFeature[kFeatureSetSize];581 582 bool DistributionNeedsUpdate = true;583 uint16_t FreqOfMostAbundantRareFeature = 0;584 uint16_t GlobalFeatureFreqs[kFeatureSetSize] = {};585 std::vector<uint32_t> RareFeatures;586 std::bitset<kFeatureSetSize> IsRareFeature;587 588 std::string OutputCorpus;589};590 591} // namespace fuzzer592 593#endif // LLVM_FUZZER_CORPUS594