[libFuzzer] Scale energy assigned to each input based on input execution time.

[dokyungs]

Summary

This patch scales the energy computed by the Entropic schedule based on the
execution time of each input. The input execution time is compared with the
average execution time of inputs in the corpus, and, based on the amount by
which they differ, the energy is scaled from 0.1x (for inputs executing slow) to
3x (for inputs executing fast). Note that the exact formula is borrowed from
AFL.

On FuzzBench, this gives a sizeable throughput increase, which in turn leads to
more coverage on several benchmarks. For details, see the following report.

https://storage.googleapis.com/fuzzer-test-suite-public/exectime-report/index.html

[morehouse]

LGTM for an experiment!

[hctim]

compiler-rt/lib/fuzzer/FuzzerFlags.def

164

(prior to real submission - please describe this feature)

[dokyungs]

Fixed compiler warnings by using signed int type for the average time variable (AverageTimeOfUnit); also fixed the unit tests.

[morehouse]

Please add a test.

compiler-rt/lib/fuzzer/FuzzerFlags.def

164

Yes, please document this feature.

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

599–600

Please fix this clang-tidy.

[dokyungs]

Addressed comments.

[dokyungs]

In D86092#2250157, @morehouse wrote:

Please add a test.

I will do this in the next upload.

[dokyungs]

Add a test.

[dokyungs]

compiler-rt/test/fuzzer/entropic-scale-per-exec-time.test

3

This test is not deterministic, but mostly falls in the same bucket of scaling; so it mostly takes around 44,557 (and around 1.3-1.5 sec in my machine) to find the crash.

4

This test is deterministic, it takes 126,633 executions (and around 5.4-5.6 sec) to find the crash if I give more runs.

[hctim]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

69

Nit: please update comment to describe the strategy behind ScalePerExecTime

71

std::chrono::microseconds AverageUnitExecutionTime

98–111

I suspect that these multiplications are going to be really expensive.

Can you instead use a shift-based approach here?

Like:

if (TimeOfUnit.count() < (AverageTimeOfUnit >> 1)) // 2x faster.
  PerfScore = 150;
else if (TimeOfUnit.count() < (AverageTimeOfUnit >> 2)) // 4x faster.
  PerfScore = 200;

etc...

490–493

rewrite as:

std::chrono::microseconds AverageUnitExecutionTime(0);
for (auto II : Inputs) {
  AverageUnitExecutionTime += II->TimeOfUnit;
}
AverageUnitExecutionTime /= N;

Also I was going to say something about overflow check, but 1 << 55 microseconds (minimum precision defined by the spec) is 1141 years, so I'm not particularly concerned here...

501

pass AverageUnitExecutionTime

compiler-rt/test/fuzzer/entropic-scale-per-exec-time.test

4

Thanks for the heads up. Instead of running this test (I'd prefer not to introduce tests with sleeps(), apart from the one were we're deliberately trying to avoid the sleeps() by scheduling those inputs less), could you just add the results as a comment?

[dokyungs]

Addressed comments.

[dokyungs]

Variable name change, as suggested.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

98–111

I changed multiplication to shift where I can. I am not sure how to handle non-power-of-two cases. Do you have any recommendation for those?

[morehouse]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

98–111

These shifts make the code harder to understand.

I might prefer we keep the multiplications for readability, but we can probably avoid the slow floating point operations with some algebra:

TimeOfUnit.count() * 0.1 > AverageUnitExecutionTime.count()

becomes

TimeOfUnit.count() > 10 * AverageUnitExecutionTime.count()

For powers of 2, the compiler will optimize to shifts under the hood. And I'd also expect it to optimize things like 10 * x into x << 3 + x << 1 if that's faster than the multiplication.

[hctim]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

98–111

https://quick-bench.com/q/z8GU7H0hFkmai-AEFvSWQiOEzno

Yep - let's just remove the floating points here - as long as the multiplicand can be shift-optimised as you mention we should be good.

[dokyungs]

Remove floting point by turning them into integer multiplication.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

98–111

Thanks for benchmarking! I turned them into integer multiplication.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerCorpus.h

102

I think this line should have * 2

[dokyungs]

Addressed comment.

[morehouse]

LGTM

compiler-rt/lib/fuzzer/FuzzerCorpus.h

 
 #include "FuzzerDataFlowTrace.h"
 #include "FuzzerDefs.h"
 #include "FuzzerIO.h"
 #include "FuzzerRandom.h"
 #include "FuzzerSHA1.h"
 #include "FuzzerTracePC.h"
 #include <algorithm>
+#include <chrono>
 #include <numeric>
 #include <random>
 #include <unordered_set>
 
 namespace fuzzer {
 
 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;
   size_t Tmp = 0; // Used by ValidateFeatureSet.
   // Stats.
   size_t NumExecutedMutations = 0;
   size_t NumSuccessfullMutations = 0;
   bool MayDeleteFile = false;
bool DeleteFeatureFreq(uint32_t Idx) {
     }
     return false;
   }
 
   // Assign more energy to a high-entropy seed, i.e., that reveals more
   // information about the globally rare features in the neighborhood
   // 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;
 
     // Apply add-one smoothing to locally discovered features.
     for (auto F : FeatureFreqs) {
       size_t LocalIncidence = F.second + 1;
       Energy -= LocalIncidence * logl(LocalIncidence);
       SumIncidence += LocalIncidence;
     }
 
     // Apply add-one smoothing to locally undiscovered features.
     //   PreciseEnergy -= 0; // since logl(1.0) == 0)
     SumIncidence += (GlobalNumberOfFeatures - FeatureFreqs.size());
 
     // Add a single locally abundant feature apply add-one smoothing.
     size_t AbdIncidence = NumExecutedMutations + 1;
     Energy -= AbdIncidence * logl(AbdIncidence);
     SumIncidence += AbdIncidence;
 
     // 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.
   void UpdateFeatureFrequency(uint32_t Idx) {
     NeedsEnergyUpdate = true;
 
     // The local feature frequencies is an ordered vector of pairs.
     // If there are no local feature frequencies, push_back preserves order.
void UpdateFeatureFrequency(uint32_t Idx) {
     }
   }
 };
 
 struct EntropicOptions {
   bool Enabled;
   size_t NumberOfRarestFeatures;
   size_t FeatureFrequencyThreshold;
+  bool ScalePerExecTime;
 };
 
 class InputCorpus {
   static const uint32_t kFeatureSetSize = 1 << 21;
   static const uint8_t kMaxMutationFactor = 20;
   static const size_t kSparseEnergyUpdates = 100;
 
   size_t NumExecutedMutations = 0;
return std::count_if(Inputs.begin(), Inputs.end(), [](const InputInfo *II) {
       return !II->DataFlowTraceForFocusFunction.empty();
     });
   }
 
   bool empty() const { return Inputs.empty(); }
   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<uint32_t> &FeatureSet,
                          const DataFlowTrace &DFT, const InputInfo *BaseII) {
     assert(!U.empty());
     if (FeatureDebug)
       Printf("ADD_TO_CORPUS %zd NF %zd\n", Inputs.size(), NumFeatures);
     Inputs.push_back(new InputInfo());
     InputInfo &II = *Inputs.back();
     II.U = U;
     II.NumFeatures = NumFeatures;
+    II.TimeOfUnit = TimeOfUnit;
     II.MayDeleteFile = MayDeleteFile;
     II.UniqFeatureSet = FeatureSet;
     II.HasFocusFunction = HasFocusFunction;
     // Assign maximal energy to the new seed.
     II.Energy = RareFeatures.empty() ? 1.0 : log(RareFeatures.size());
     II.SumIncidence = RareFeatures.size();
     II.NeedsEnergyUpdate = false;
     std::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());
void UpdateCorpusDistribution(Random &Rand) {
     DistributionNeedsUpdate = false;
 
     size_t N = Inputs.size();
     assert(N);
     Intervals.resize(N + 1);
     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);
         }
       }
 
       for (size_t i = 0; i < N; i++) {
 
         if (Inputs[i]->NumFeatures == 0) {
           // If the seed doesn't represent any features, assign zero energy.
           Weights[i] = 0.;

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

if (Flags.collect_data_flow)
     Options.CollectDataFlow = Flags.collect_data_flow;
   if (Flags.stop_file)
     Options.StopFile = Flags.stop_file;
   Options.Entropic = Flags.entropic;
   Options.EntropicFeatureFrequencyThreshold =
       (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 "
              "be used together.\n");
       exit(1);
     }
     Printf("INFO: Running with entropic power schedule (0x%X, %d).\n",
            Options.EntropicFeatureFrequencyThreshold,
            Options.EntropicNumberOfRarestFeatures);
   }
   struct EntropicOptions Entropic;
   Entropic.Enabled = Options.Entropic;
   Entropic.FeatureFrequencyThreshold =
       Options.EntropicFeatureFrequencyThreshold;
   Entropic.NumberOfRarestFeatures = Options.EntropicNumberOfRarestFeatures;
+  Entropic.ScalePerExecTime = Options.EntropicScalePerExecTime;
 
   unsigned Seed = Flags.seed;
   // Initialize Seed.
   if (Seed == 0)
     Seed =
         std::chrono::system_clock::now().time_since_epoch().count() + GetPid();
   if (Flags.verbosity)
     Printf("INFO: Seed: %u\n", Seed);

compiler-rt/lib/fuzzer/FuzzerFlags.def

 FUZZER_FLAG_INT(entropic, 0, "Experimental. Enables entropic power schedule.")
 FUZZER_FLAG_INT(entropic_feature_frequency_threshold, 0xFF, "Experimental. If "
      "entropic is enabled, all features which are observed less often than "
      "the specified value are considered as rare.")
 FUZZER_FLAG_INT(entropic_number_of_rarest_features, 100, "Experimental. If "
      "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)
 FUZZER_FLAG_STRING(data_flow_trace, "Experimental: use the data flow trace")
 FUZZER_FLAG_STRING(collect_data_flow,
                    "Experimental: collect the data flow trace")

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

 }
 
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                     InputInfo *II, bool *FoundUniqFeatures) {
   if (!Size)
     return false;
 
   ExecuteCallback(Data, Size);
+  auto TimeOfUnit = duration_cast<microseconds>(UnitStopTime - UnitStartTime);
 
   UniqFeatureSetTmp.clear();
   size_t FoundUniqFeaturesOfII = 0;
   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
   TPC.CollectFeatures([&](size_t Feature) {
     if (Corpus.AddFeature(Feature, Size, Options.Shrink))
       UniqFeatureSetTmp.push_back(Feature);
     if (Options.Entropic)
       Corpus.UpdateFeatureFrequency(II, Feature);
     if (Options.ReduceInputs && II)
       if (std::binary_search(II->UniqFeatureSet.begin(),
                              II->UniqFeatureSet.end(), Feature))
         FoundUniqFeaturesOfII++;
   });
   if (FoundUniqFeatures)
     *FoundUniqFeatures = FoundUniqFeaturesOfII;
   PrintPulseAndReportSlowInput(Data, Size);
   size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
   if (NumNewFeatures) {
     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;
   }
   if (II && FoundUniqFeaturesOfII &&
       II->DataFlowTraceForFocusFunction.empty() &&
       FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
       II->U.size() > Size) {

compiler-rt/lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   bool ShuffleAtStartUp = true;
   bool PreferSmall = true;
   size_t MaxNumberOfRuns = -1L;
   int ReportSlowUnits = 10;
   bool OnlyASCII = false;
   bool Entropic = false;
   size_t EntropicFeatureFrequencyThreshold = 0xFF;
   size_t EntropicNumberOfRarestFeatures = 100;
+  bool EntropicScalePerExecTime = false;
   std::string OutputCorpus;
   std::string ArtifactPrefix = "./";
   std::string ExactArtifactPath;
   std::string ExitOnSrcPos;
   std::string ExitOnItem;
   std::string FocusFunction;
   std::string DataFlowTrace;
   std::string CollectDataFlow;

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

 
 #include "FuzzerCorpus.h"
 #include "FuzzerDictionary.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
 #include "gtest/gtest.h"
 #include <memory>
 #include <set>
 #include <sstream>
 
 using namespace fuzzer;
 
 // For now, have LLVMFuzzerTestOneInput just to make it link.
 // Later we may want to make unittests that actually call LLVMFuzzerTestOneInput.

 
 TEST(Corpus, Distribution) {
   DataFlowTrace DFT;
   Random Rand(0);
   struct EntropicOptions Entropic = {false, 0xFF, 100};
   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
   size_t N = 10;
   size_t TriesPerUnit = 1<<16;
   for (size_t i = 0; i < N; i++)
-    C->AddToCorpus(Unit{static_cast<uint8_t>(i)}, 1, false, false, {}, DFT,
-                   nullptr);
+    C->AddToCorpus(Unit{static_cast<uint8_t>(i)}, 1, false, false,
+                   std::chrono::microseconds(0), {}, DFT, nullptr);
 
   Vector<size_t> Hist(N);
   for (size_t i = 0; i < N * TriesPerUnit; i++) {
     Hist[C->ChooseUnitIdxToMutate(Rand)]++;
   }
   for (size_t i = 0; i < N; i++) {
     // A weak sanity check that every unit gets invoked.
     EXPECT_GT(Hist[i], TriesPerUnit / N / 3);

 TEST(Entropic, ComputeEnergy) {
   const double Precision = 0.01;
   struct EntropicOptions Entropic = {true, 0xFF, 100};
   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
   std::unique_ptr<InputInfo> II(new InputInfo());
   Vector<std::pair<uint32_t, uint16_t>> 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<uint32_t, uint16_t>(42, 6));
   II->NumExecutedMutations = 20;
-  II->UpdateEnergy(10);
+  II->UpdateEnergy(10, false, 0.0);
   EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision);
 }
 
 int main(int argc, char **argv) {
   testing::InitGoogleTest(&argc, argv);
   return RUN_ALL_TESTS();
 }

compiler-rt/test/fuzzer/EntropicScalePerExecTimeTest.cpp

+// 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 <cstdint>
+#include <chrono>
+#include <thread>
+
+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;
+}

compiler-rt/test/fuzzer/entropic-scale-per-exec-time.test

+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