Index: lib/Fuzzer/FuzzerInternal.h =================================================================== --- lib/Fuzzer/FuzzerInternal.h +++ lib/Fuzzer/FuzzerInternal.h @@ -17,6 +17,7 @@ #include #include #include +#include #include #include #include @@ -241,6 +242,7 @@ void WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix); void PrintStats(const char *Where, const char *End = "\n"); void PrintStatusForNewUnit(const Unit &U); + void UpdateCorpusDistribution(); void SyncCorpus(); @@ -280,6 +282,8 @@ return Res; } + std::mt19937 Generator; + std::piecewise_constant_distribution CorpusDistribution; UserSuppliedFuzzer &USF; FuzzingOptions Options; system_clock::time_point ProcessStartTime = system_clock::now(); Index: lib/Fuzzer/FuzzerLoop.cpp =================================================================== --- lib/Fuzzer/FuzzerLoop.cpp +++ lib/Fuzzer/FuzzerLoop.cpp @@ -56,7 +56,7 @@ static Fuzzer *F; Fuzzer::Fuzzer(UserSuppliedFuzzer &USF, FuzzingOptions Options) - : USF(USF), Options(Options) { + : Generator(USF.GetRand()(RAND_MAX)), USF(USF), Options(Options) { SetDeathCallback(); InitializeTraceState(); assert(!F); @@ -163,6 +163,7 @@ if (UnitHashesAddedToCorpus.insert(Hash(X)).second) { if (RunOne(X)) { Corpus.push_back(X); + UpdateCorpusDistribution(); PrintStats("RELOAD"); } } @@ -200,6 +201,7 @@ } } Corpus = NewCorpus; + UpdateCorpusDistribution(); for (auto &X : Corpus) UnitHashesAddedToCorpus.insert(Hash(X)); PrintStats("INITED"); @@ -347,6 +349,7 @@ void Fuzzer::ReportNewCoverage(const Unit &U) { Corpus.push_back(U); + UpdateCorpusDistribution(); UnitHashesAddedToCorpus.insert(Hash(U)); USF.GetMD().RecordSuccessfulMutationSequence(); PrintStatusForNewUnit(U); @@ -411,20 +414,9 @@ // 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(Generator)); + assert(Idx < Corpus.size()); + return Idx; } // Experimental search heuristic: drilling. @@ -447,6 +439,7 @@ std::vector SavedCorpus; SavedCorpus.swap(Corpus); Corpus.push_back(U); + UpdateCorpusDistribution(); assert(Corpus.size() == 1); RunOne(U); PrintStats("DRILL "); @@ -510,4 +503,15 @@ ExecuteCommand(Options.SyncCommand + " " + Options.OutputCorpus); } +void Fuzzer::UpdateCorpusDistribution() { + std::vector Intervals { 0 }; + std::vector 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( + Intervals.begin(), Intervals.end(), Weights.begin()); +} + } // namespace fuzzer Index: lib/Fuzzer/test/fuzzer-traces.test =================================================================== --- lib/Fuzzer/test/fuzzer-traces.test +++ lib/Fuzzer/test/fuzzer-traces.test @@ -19,7 +19,7 @@ RUN: not LLVMFuzzer-SimpleHashTest -use_traces=1 -seed=1 -runs=10000000 2>&1 | FileCheck %s RUN: LLVMFuzzer-SimpleHashTest -seed=1 -runs=10000000 2>&1 | FileCheck %s --check-prefix=Done10000000 -RUN: LLVMFuzzer-RepeatedMemcmp -seed=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT +RUN: LLVMFuzzer-RepeatedMemcmp -seed=2 -runs=100000 2>&1 | FileCheck %s --check-prefix=RECOMMENDED_DICT RECOMMENDED_DICT:###### Recommended dictionary. ###### RECOMMENDED_DICT-DAG: "foo" RECOMMENDED_DICT-DAG: "bar"