diff --git a/compiler-rt/lib/fuzzer/FuzzerCorpus.h b/compiler-rt/lib/fuzzer/FuzzerCorpus.h --- a/compiler-rt/lib/fuzzer/FuzzerCorpus.h +++ b/compiler-rt/lib/fuzzer/FuzzerCorpus.h @@ -18,6 +18,7 @@ #include "FuzzerSHA1.h" #include "FuzzerTracePC.h" #include +#include #include #include #include @@ -26,6 +27,7 @@ struct InputInfo { Unit U; // The actual input data. + std::chrono::microseconds TimeOfUnit; uint8_t Sha1[kSHA1NumBytes]; // Checksum. // Number of features that this input has and no smaller input has. size_t NumFeatures = 0; @@ -65,7 +67,8 @@ // of the seed. Since we do not know the entropy of a seed that has // never been executed we assign fresh seeds maximum entropy and // let II->Energy approach the true entropy from above. - void UpdateEnergy(size_t GlobalNumberOfFeatures) { + void UpdateEnergy(size_t GlobalNumberOfFeatures, bool ScalePerExecTime, + int64_t AverageTimeOfUnit) { Energy = 0.0; SumIncidence = 0; @@ -88,6 +91,27 @@ // Normalize. if (SumIncidence != 0) Energy = (Energy / SumIncidence) + logl(SumIncidence); + + if (ScalePerExecTime) { + // Scaling to favor inputs with lower execution time. + uint32_t PerfScore = 100; + if (TimeOfUnit.count() * 0.1 > AverageTimeOfUnit) + PerfScore = 10; + else if (TimeOfUnit.count() * 0.25 > AverageTimeOfUnit) + PerfScore = 25; + else if (TimeOfUnit.count() * 0.5 > AverageTimeOfUnit) + PerfScore = 50; + else if (TimeOfUnit.count() * 0.75 > AverageTimeOfUnit) + PerfScore = 75; + else if (TimeOfUnit.count() * 4 < AverageTimeOfUnit) + PerfScore = 300; + else if (TimeOfUnit.count() * 3 < AverageTimeOfUnit) + PerfScore = 200; + else if (TimeOfUnit.count() * 2 < AverageTimeOfUnit) + PerfScore = 150; + + Energy *= PerfScore; + } } // Increment the frequency of the feature Idx. @@ -120,6 +144,7 @@ bool Enabled; size_t NumberOfRarestFeatures; size_t FeatureFrequencyThreshold; + bool ScalePerExecTime; }; class InputCorpus { @@ -178,6 +203,7 @@ const Unit &operator[] (size_t Idx) const { return Inputs[Idx]->U; } InputInfo *AddToCorpus(const Unit &U, size_t NumFeatures, bool MayDeleteFile, bool HasFocusFunction, + std::chrono::microseconds TimeOfUnit, const Vector &FeatureSet, const DataFlowTrace &DFT, const InputInfo *BaseII) { assert(!U.empty()); @@ -187,6 +213,7 @@ InputInfo &II = *Inputs.back(); II.U = U; II.NumFeatures = NumFeatures; + II.TimeOfUnit = TimeOfUnit; II.MayDeleteFile = MayDeleteFile; II.UniqFeatureSet = FeatureSet; II.HasFocusFunction = HasFocusFunction; @@ -460,12 +487,18 @@ Weights.resize(N); std::iota(Intervals.begin(), Intervals.end(), 0); + std::chrono::microseconds TotalTimeOfUnit(0); + for (auto II : Inputs) { + TotalTimeOfUnit += II->TimeOfUnit; + } + bool VanillaSchedule = true; if (Entropic.Enabled) { for (auto II : Inputs) { if (II->NeedsEnergyUpdate && II->Energy != 0.0) { II->NeedsEnergyUpdate = false; - II->UpdateEnergy(RareFeatures.size()); + II->UpdateEnergy(RareFeatures.size(), Entropic.ScalePerExecTime, + TotalTimeOfUnit.count() / N); } } diff --git a/compiler-rt/lib/fuzzer/FuzzerDriver.cpp b/compiler-rt/lib/fuzzer/FuzzerDriver.cpp --- a/compiler-rt/lib/fuzzer/FuzzerDriver.cpp +++ b/compiler-rt/lib/fuzzer/FuzzerDriver.cpp @@ -746,6 +746,7 @@ (size_t)Flags.entropic_feature_frequency_threshold; Options.EntropicNumberOfRarestFeatures = (size_t)Flags.entropic_number_of_rarest_features; + Options.EntropicScalePerExecTime = Flags.entropic_scale_per_exec_time; if (Options.Entropic) { if (!Options.FocusFunction.empty()) { Printf("ERROR: The parameters `--entropic` and `--focus_function` cannot " @@ -761,6 +762,7 @@ Entropic.FeatureFrequencyThreshold = Options.EntropicFeatureFrequencyThreshold; Entropic.NumberOfRarestFeatures = Options.EntropicNumberOfRarestFeatures; + Entropic.ScalePerExecTime = Options.EntropicScalePerExecTime; unsigned Seed = Flags.seed; // Initialize Seed. diff --git a/compiler-rt/lib/fuzzer/FuzzerFlags.def b/compiler-rt/lib/fuzzer/FuzzerFlags.def --- a/compiler-rt/lib/fuzzer/FuzzerFlags.def +++ b/compiler-rt/lib/fuzzer/FuzzerFlags.def @@ -161,6 +161,11 @@ "entropic is enabled, we keep track of the frequencies only for the " "Top-X least abundant features (union features that are considered as " "rare).") +FUZZER_FLAG_INT(entropic_scale_per_exec_time, 0, "Experimental. If 1, " + "the Entropic power schedule gets scaled based on the input execution " + "time. Inputs with lower execution time get scheduled more (up to 30x). " + "Note that, if 1, fuzzer stops from being deterministic even if a " + "non-zero random seed is given.") FUZZER_FLAG_INT(analyze_dict, 0, "Experimental") FUZZER_DEPRECATED_FLAG(use_clang_coverage) diff --git a/compiler-rt/lib/fuzzer/FuzzerLoop.cpp b/compiler-rt/lib/fuzzer/FuzzerLoop.cpp --- a/compiler-rt/lib/fuzzer/FuzzerLoop.cpp +++ b/compiler-rt/lib/fuzzer/FuzzerLoop.cpp @@ -469,6 +469,7 @@ return false; ExecuteCallback(Data, Size); + auto TimeOfUnit = duration_cast(UnitStopTime - UnitStartTime); UniqFeatureSetTmp.clear(); size_t FoundUniqFeaturesOfII = 0; @@ -491,7 +492,7 @@ TPC.UpdateObservedPCs(); auto NewII = Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile, TPC.ObservedFocusFunction(), - UniqFeatureSetTmp, DFT, II); + TimeOfUnit, UniqFeatureSetTmp, DFT, II); WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1), NewII->UniqFeatureSet); return true; diff --git a/compiler-rt/lib/fuzzer/FuzzerOptions.h b/compiler-rt/lib/fuzzer/FuzzerOptions.h --- a/compiler-rt/lib/fuzzer/FuzzerOptions.h +++ b/compiler-rt/lib/fuzzer/FuzzerOptions.h @@ -47,6 +47,7 @@ bool Entropic = false; size_t EntropicFeatureFrequencyThreshold = 0xFF; size_t EntropicNumberOfRarestFeatures = 100; + bool EntropicScalePerExecTime = false; std::string OutputCorpus; std::string ArtifactPrefix = "./"; std::string ExactArtifactPath; diff --git a/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp b/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp --- a/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp +++ b/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp @@ -597,8 +597,8 @@ size_t N = 10; size_t TriesPerUnit = 1<<16; for (size_t i = 0; i < N; i++) - C->AddToCorpus(Unit{static_cast(i)}, 1, false, false, {}, DFT, - nullptr); + C->AddToCorpus(Unit{static_cast(i)}, 1, false, false, + std::chrono::microseconds(0), {}, DFT, nullptr); Vector Hist(N); for (size_t i = 0; i < N * TriesPerUnit; i++) { @@ -1099,17 +1099,17 @@ Vector> FeatureFreqs = {{1, 3}, {2, 3}, {3, 3}}; II->FeatureFreqs = FeatureFreqs; II->NumExecutedMutations = 0; - II->UpdateEnergy(4); + II->UpdateEnergy(4, false, 0.0); EXPECT_LT(SubAndSquare(II->Energy, 1.450805), Precision); II->NumExecutedMutations = 9; - II->UpdateEnergy(5); + II->UpdateEnergy(5, false, 0.0); EXPECT_LT(SubAndSquare(II->Energy, 1.525496), Precision); II->FeatureFreqs[0].second++; II->FeatureFreqs.push_back(std::pair(42, 6)); II->NumExecutedMutations = 20; - II->UpdateEnergy(10); + II->UpdateEnergy(10, false, 0.0); EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision); } diff --git a/compiler-rt/test/fuzzer/EntropicScalePerExecTimeTest.cpp b/compiler-rt/test/fuzzer/EntropicScalePerExecTimeTest.cpp new file mode 100644 --- /dev/null +++ b/compiler-rt/test/fuzzer/EntropicScalePerExecTimeTest.cpp @@ -0,0 +1,32 @@ +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception + +// Tests whether scaling the Entropic scheduling weight based on input execution +// time is effective or not. Inputs of size 10 will take at least 100 +// microseconds more than any input of size 1-9. The input of size 2 in the +// corpus should be favored by the exec-time-scaled Entropic scheduling policy +// than the input of size 10 in the corpus, eventually finding the crashing +// input {0xab, 0xcd} with less executions. +#include +#include +#include + +static volatile int Sink; +static volatile int *Nil = nullptr; + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + if (Size > 10) return 0; // To make the test quicker. + + if (Size == 10) { + size_t ExecTimeUSec = 100; + std::this_thread::sleep_for(std::chrono::microseconds(ExecTimeUSec)); + + Sink = 0; // execute a lot slower than the crashing input below. + } + + if (Size == 2 && Data[0] == 0xab && Data[1] == 0xcd) + *Nil = 42; // crash. + + return 0; +} diff --git a/compiler-rt/test/fuzzer/entropic-scale-per-exec-time.test b/compiler-rt/test/fuzzer/entropic-scale-per-exec-time.test new file mode 100644 --- /dev/null +++ b/compiler-rt/test/fuzzer/entropic-scale-per-exec-time.test @@ -0,0 +1,4 @@ +REQUIRES: linux, x86_64 +RUN: %cpp_compiler %S/EntropicScalePerExecTimeTest.cpp -o %t-EntropicScalePerExecTimeTest +RUN: not %run %t-EntropicScalePerExecTimeTest -entropic=1 -entropic_scale_per_exec_time=1 -seed=1 -runs=100000 -max_len=10 +RUN: %run %t-EntropicScalePerExecTimeTest -entropic=1 -seed=1 -runs=100000 -max_len=10