Use std::piecewise_constant_distribution instead of ad-hoc binary search.

[krasin]

Summary

Fix the issue with the most recently discovered unit receiving much less attention.

Note: I had to change the seed for one test to make it pass. Alternatively,
the number of runs could be increased. I believe that the average time of
'foo' discovery is not increased, just seed=1 was particularly convenient
for the previous PRNG scheme used.

[krasin]

Added a comment.

[kcc]

lib/Fuzzer/FuzzerInternal.h

287

We should not be using yet another random generator, we already have one.
Please use it. (USF.GetRand())

[krasin]

lib/Fuzzer/FuzzerInternal.h

287

USF.GetRand does not meet the requirements for UniformRandomNumberGenerator: http://en.cppreference.com/w/cpp/concept/UniformRandomNumberGenerator and that is needed to use std::piecewise_constant_distribution.

Should I change USF.GetRand definition to be more standard-compliant?

[kcc]

lib/Fuzzer/FuzzerInternal.h

287

Can you *extend* it to be more standard-compliant?

[krasin]

Extend FuzzerRandomBase to satisfy UniformRandomNumberGenerator requirement.

[krasin]

nits

[krasin]

lib/Fuzzer/FuzzerInternal.h

287

Done, but I have made an assumption about the max value of Rand(). I imply it's RAND_MAX.

If that could be not the case, the implementation is broken. Please, complain loudly, if so.

[kcc]

lib/Fuzzer/FuzzerLoop.cpp

417

please use an explicit cast operator.
Are you sure it will ever return the corner values (0 and N-1)?

507

why do you need two vectors here, given that their values are the same?

please avoid sp many push backs, just create a properly sized vector.

the following loop looks like std::iota, please replace with such.

[krasin]

Addressed comments.

[krasin]

Please, take another look.

lib/Fuzzer/FuzzerLoop.cpp

417

I've taken a closer look at the generated values. One bug found (not here, though).
This is what I get (histogram for a corpus of size 15)

16606 0
33392 1
49472 2
66160 3
82898 4
99791 5

116215 6
132234 7
149854 8
166098 9
183056 10
199628 11
216078 12
232118 13
248708 14

507

why do you need two vectors here, given that their values are the same?

I need two vectors because one is for intervals and another one for weights.
They are coincidentally similar. That will not be the case, when dynamic weights are introduced.
See http://en.cppreference.com/w/cpp/numeric/random/piecewise_constant_distribution

please avoid sp many push backs, just create a properly sized vector.

Done. Thank you.

the following loop looks like std::iota, please replace with such.

Sorry, I don't understand the request. Can you please rephrase the request or give an example?

[kcc]

lib/Fuzzer/FuzzerLoop.cpp

507

a loop like

for (size_t i = 0; i < Corpus.size(); i++)  x[i] = i + 1

can be replaced with
std::iota(x.begin(), x.end(), 1);

[krasin]

Added a unit test for the CorpusDistribution.

[krasin]

lib/Fuzzer/FuzzerLoop.cpp

507

ugh. Obscure!

Let me know, if you really want it.

[kcc]

almost LGTM

lib/Fuzzer/FuzzerLoop.cpp

511

yep, iota would be nicer.
Also, the current code does not initialize Intervals[0]

lib/Fuzzer/test/FuzzerUnittest.cpp

410 ↗

(On Diff #45618)

why cast from double from size_t.
Better just write 1 << 20.

[krasin]

Use std::iota

lib/Fuzzer/FuzzerLoop.cpp

511

yep, iota would be nicer.

Done

Also, the current code does not initialize Intervals[0]

explicit vector(size_type count) constructor initializes Intervals with all zeros.

lib/Fuzzer/test/FuzzerUnittest.cpp

410 ↗

(On Diff #45618)

Sorry, I don't understand which cast do you mean here. The function does not cast from double to size_t anywhere.

[kcc]

LGTM with a nit

lib/Fuzzer/test/FuzzerUnittest.cpp

410 ↗

(On Diff #45623)

1E6 is a floating point constant

[kcc]

LGTM with a nit

[krasin]

1E6 -> 1<<20.

lib/Fuzzer/test/FuzzerUnittest.cpp

410 ↗

(On Diff #45623)

Done.

Thank you. Golang has typeless constants (which get types at the time of assignment). I totally forgot that C does not. :)

lib/Fuzzer/FuzzerInterface.h

public:
   FuzzerRandomBase(){}
   virtual ~FuzzerRandomBase(){};
   virtual void ResetSeed(unsigned int seed) = 0;
   // Return a random number.
   virtual size_t Rand() = 0;
   // Return a random number in range [0,n).
   size_t operator()(size_t n) { return n ? Rand() % n : 0; }
   bool RandBool() { return Rand() % 2; }
+
+  // The methods below is to satisfy UniformRandomNumberGenerator:
+  // http://en.cppreference.com/w/cpp/concept/UniformRandomNumberGenerator\
+
+  // Returns a random number between 0 and 1.
+  double operator()() { return static_cast<double>(operator()(RAND_MAX)) / RAND_MAX; }
+
+  // Returns the smallest value that operator() may return.
+  double min() { return 0; }
+
+  // Returns the largest value that operator() may return.
+  double max() { return 1; }
 };
 
 // Using libc's stand/rand.
 class FuzzerRandomLibc : public FuzzerRandomBase {
  public:
   FuzzerRandomLibc(unsigned int seed) { ResetSeed(seed); }
   void ResetSeed(unsigned int seed) override;
   ~FuzzerRandomLibc() override {};

lib/Fuzzer/FuzzerInternal.h

 #ifndef LLVM_FUZZER_INTERNAL_H
 #define LLVM_FUZZER_INTERNAL_H
 
 #include <cassert>
 #include <climits>
 #include <chrono>
 #include <cstddef>
 #include <cstdlib>
+#include <random>
 #include <string>
 #include <string.h>
 #include <vector>
 #include <unordered_set>
 
 #include "FuzzerInterface.h"
 
 namespace fuzzer {
private:
   void MutateAndTestOne();
   void ReportNewCoverage(const Unit &U);
   bool RunOne(const Unit &U);
   void RunOneAndUpdateCorpus(Unit &U);
   void WriteToOutputCorpus(const Unit &U);
   void WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix);
   void PrintStats(const char *Where, const char *End = "\n");
   void PrintStatusForNewUnit(const Unit &U);
+  // Updates the probability distribution for the units in the corpus.
+  // Must be called whenever the corpus or unit weights are changed.
+  void UpdateCorpusDistribution();
 
   void SyncCorpus();
 
   size_t RecordBlockCoverage();
   size_t RecordCallerCalleeCoverage();
   void PrepareCoverageBeforeRun();
   bool CheckCoverageAfterRun();
 
private:
   // For UseCounters
   std::vector<uint8_t> CounterBitmap;
   size_t TotalBits() {  // Slow. Call it only for printing stats.
     size_t Res = 0;
     for (auto x : CounterBitmap) Res += __builtin_popcount(x);
     return Res;
   }
 
+  std::piecewise_constant_distribution<double> CorpusDistribution;
   UserSuppliedFuzzer &USF;
   FuzzingOptions Options;
   system_clock::time_point ProcessStartTime = system_clock::now();
   system_clock::time_point LastExternalSync = system_clock::now();
   system_clock::time_point UnitStartTime;
   long TimeOfLongestUnitInSeconds = 0;
   long EpochOfLastReadOfOutputCorpus = 0;
   size_t LastRecordedBlockCoverage = 0;

lib/Fuzzer/FuzzerLoop.cpp

void Fuzzer::RereadOutputCorpus() {
   if (Options.Verbosity >= 2)
     Printf("Reload: read %zd new units.\n",  AdditionalCorpus.size());
   for (auto &X : AdditionalCorpus) {
     if (X.size() > (size_t)Options.MaxLen)
       X.resize(Options.MaxLen);
     if (UnitHashesAddedToCorpus.insert(Hash(X)).second) {
       if (RunOne(X)) {
         Corpus.push_back(X);
+        UpdateCorpusDistribution();
         PrintStats("RELOAD");
       }
     }
   }
 }
 
 void Fuzzer::ShuffleAndMinimize() {
   bool PreferSmall = (Options.PreferSmallDuringInitialShuffle == 1 ||
for (size_t First = 0; First < 1; First++) {
       if (RunOne(U)) {
         NewCorpus.push_back(U);
         if (Options.Verbosity >= 2)
           Printf("NEW0: %zd L %zd\n", LastRecordedBlockCoverage, U.size());
       }
     }
   }
   Corpus = NewCorpus;
+  UpdateCorpusDistribution();
   for (auto &X : Corpus)
     UnitHashesAddedToCorpus.insert(Hash(X));
   PrintStats("INITED");
 }
 
 bool Fuzzer::RunOne(const Unit &U) {
   UnitStartTime = system_clock::now();
   TotalNumberOfRuns++;
if (Options.Verbosity) {
     Printf(" L: %zd ", U.size());
     USF.GetMD().PrintMutationSequence();
     Printf("\n");
   }
 }
 
 void Fuzzer::ReportNewCoverage(const Unit &U) {
   Corpus.push_back(U);
+  UpdateCorpusDistribution();
   UnitHashesAddedToCorpus.insert(Hash(U));
   USF.GetMD().RecordSuccessfulMutationSequence();
   PrintStatusForNewUnit(U);
   WriteToOutputCorpus(U);
   if (Options.ExitOnFirst)
     exit(0);
 }
 
for (int i = 0; i < Options.MutateDepth; i++) {
     StopTraceRecording();
   }
 }
 
 // Returns an index of random unit from the corpus to mutate.
 // Hypothesis: units added to the corpus last are more likely to be interesting.
 // This function gives more wieght to the more recent units.
 size_t Fuzzer::ChooseUnitIdxToMutate() {
-    size_t N = Corpus.size();
-    size_t Total = (N + 1) * N / 2;
-    size_t R = USF.GetRand()(Total);
-    size_t IdxBeg = 0, IdxEnd = N;
-    // Binary search.
-    while (IdxEnd - IdxBeg >= 2) {
-      size_t Idx = IdxBeg + (IdxEnd - IdxBeg) / 2;
-      if (R > (Idx + 1) * Idx / 2)
-        IdxBeg = Idx;
-      else
-        IdxEnd = Idx;
-    }
-    assert(IdxBeg < N);
-    return IdxBeg;
+    size_t Idx = size_t(CorpusDistribution(USF.GetRand()));
+    assert(Idx < Corpus.size());
+    return Idx;
 }
 
 // Experimental search heuristic: drilling.
 // - Read, shuffle, execute and minimize the corpus.
 // - Choose one random unit.
 // - Reset the coverage.
 // - Start fuzzing as if the chosen unit was the only element of the corpus.
 // - When done, reset the coverage again.
 // - Merge the newly created corpus into the original one.
 void Fuzzer::Drill() {
   // The corpus is already read, shuffled, and minimized.
   assert(!Corpus.empty());
   Options.PrintNEW = false;  // Don't print NEW status lines when drilling.
 
   Unit U = ChooseUnitToMutate();
 
   CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage);
   __sanitizer_reset_coverage();
 
   std::vector<Unit> SavedCorpus;
   SavedCorpus.swap(Corpus);
   Corpus.push_back(U);
+  UpdateCorpusDistribution();
   assert(Corpus.size() == 1);
   RunOne(U);
   PrintStats("DRILL ");
   std::string SavedOutputCorpusPath; // Don't write new units while drilling.
   SavedOutputCorpusPath.swap(Options.OutputCorpus);
   Loop();
 
   __sanitizer_reset_coverage();
void Fuzzer::SyncCorpus() {
   auto Now = system_clock::now();
   if (duration_cast<seconds>(Now - LastExternalSync).count() <
       Options.SyncTimeout)
     return;
   LastExternalSync = Now;
   ExecuteCommand(Options.SyncCommand + " " + Options.OutputCorpus);
 }
 
+void Fuzzer::UpdateCorpusDistribution() {
+  std::vector<double> Intervals { 0 };
+  std::vector<double> Weights;
+  for (size_t i = 0; i < Corpus.size(); i++) {
+    Intervals.push_back(i+1);
+    Weights.push_back(i+1);
+  }
+  CorpusDistribution = std::piecewise_constant_distribution<double>(
+      Intervals.begin(), Intervals.end(), Weights.begin());
+}
+
 }  // namespace fuzzer