Index: lib/fuzzer/FuzzerDriver.cpp =================================================================== --- lib/fuzzer/FuzzerDriver.cpp +++ lib/fuzzer/FuzzerDriver.cpp @@ -616,6 +616,7 @@ Options.PrintNewCovFuncs = Flags.print_funcs; Options.PrintFinalStats = Flags.print_final_stats; Options.PrintMutationStats = Flags.print_mutation_stats; + Options.UseWeightedMutations = Flags.use_weighted_mutations; Options.PrintCorpusStats = Flags.print_corpus_stats; Options.PrintCoverage = Flags.print_coverage; Options.PrintUnstableStats = Flags.print_unstable_stats; Index: lib/fuzzer/FuzzerFlags.def =================================================================== --- lib/fuzzer/FuzzerFlags.def +++ lib/fuzzer/FuzzerFlags.def @@ -163,3 +163,5 @@ FUZZER_DEPRECATED_FLAG(use_clang_coverage) FUZZER_FLAG_STRING(data_flow_trace, "Experimental: use the data flow trace") FUZZER_FLAG_INT(print_mutation_stats, 0, "Experimental") +FUZZER_FLAG_INT(use_weighted_mutations, 0, "Experimental: If 1, fuzzing will " + "favor mutations that perform better during runtime.") Index: lib/fuzzer/FuzzerLoop.cpp =================================================================== --- lib/fuzzer/FuzzerLoop.cpp +++ lib/fuzzer/FuzzerLoop.cpp @@ -38,6 +38,7 @@ namespace fuzzer { static const size_t kMaxUnitSizeToPrint = 256; +static const size_t kUpdateMutationWeightRuns = 10000; thread_local bool Fuzzer::IsMyThread; @@ -554,6 +555,9 @@ void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) { TPC.RecordInitialStack(); + if (Options.UseWeightedMutations && + TotalNumberOfRuns % kUpdateMutationWeightRuns == 0) + MD.AssignMutationWeights(); TotalNumberOfRuns++; assert(InFuzzingThread()); if (SMR.IsClient()) Index: lib/fuzzer/FuzzerMutate.h =================================================================== --- lib/fuzzer/FuzzerMutate.h +++ lib/fuzzer/FuzzerMutate.h @@ -93,9 +93,22 @@ Random &GetRand() { return Rand; } + /// Records tally of mutations resulting in new coverage, for usefulness + /// metric. + void RecordUsefulMutations(); + + /// Outputs usefulness stats on command line if option is enabled. void PrintMutationStats(); - void RecordUsefulMutations(); + /// Refreshes current mutation stats recalculated based on most previous run. + void SetMutationStats(); + + /// Sets weights based on mutation performance during fuzzer run. + void AssignMutationWeights(); + + /// Returns the index of a mutation based on how useful it has been. + /// Favors mutations with higher usefulness ratios but can return any index. + size_t WeightedIndex(); private: struct Mutator { @@ -156,6 +169,10 @@ Vector Mutators; Vector DefaultMutators; + + // Used to weight mutations based on usefulness. + Vector MutationWeights; + Vector Stats; }; } // namespace fuzzer Index: lib/fuzzer/FuzzerMutate.cpp =================================================================== --- lib/fuzzer/FuzzerMutate.cpp +++ lib/fuzzer/FuzzerMutate.cpp @@ -19,6 +19,8 @@ namespace fuzzer { const size_t Dictionary::kMaxDictSize; +const double kDefaultMutationWeight = 1; +const double kDefaultMutationStat = 1; static void PrintASCII(const Word &W, const char *PrintAfter) { PrintASCII(W.data(), W.size(), PrintAfter); @@ -30,36 +32,41 @@ DefaultMutators.insert( DefaultMutators.begin(), { - {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes", 0, 0}, - {&MutationDispatcher::Mutate_InsertByte, "InsertByte", 0, 0}, + // Initialize total count as 1 to prevent zero division. + {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes", 0, 1}, + {&MutationDispatcher::Mutate_InsertByte, "InsertByte", 0, 1}, {&MutationDispatcher::Mutate_InsertRepeatedBytes, - "InsertRepeatedBytes", 0, 0}, - {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte", 0, 0}, - {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit", 0, 0}, - {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes", 0, 0}, + "InsertRepeatedBytes", 0, 1}, + {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte", 0, 1}, + {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit", 0, 1}, + {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes", 0, 1}, {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt", 0, - 0}, + 1}, {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt", 0, - 0}, - {&MutationDispatcher::Mutate_CopyPart, "CopyPart", 0, 0}, - {&MutationDispatcher::Mutate_CrossOver, "CrossOver", 0, 0}, + 1}, + {&MutationDispatcher::Mutate_CopyPart, "CopyPart", 0, 1}, + {&MutationDispatcher::Mutate_CrossOver, "CrossOver", 0, 1}, {&MutationDispatcher::Mutate_AddWordFromManualDictionary, - "ManualDict", 0, 0}, + "ManualDict", 0, 1}, {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, - "PersAutoDict", 0, 0}, + "PersAutoDict", 0, 1}, }); if(Options.UseCmp) DefaultMutators.push_back( - {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP", 0, 0}); + {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP", 0, 1}); if (EF->LLVMFuzzerCustomMutator) - Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom", 0, 0}); + Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom", 0, 1}); else Mutators = DefaultMutators; if (EF->LLVMFuzzerCustomCrossOver) Mutators.push_back( - {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver", 0, 0}); + {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver", 0, 1}); + + // For weighted mutation selection. + MutationWeights.resize(Mutators.size(), kDefaultMutationWeight); + Stats.resize(Mutators.size(), kDefaultMutationStat); } static char RandCh(Random &Rand) { @@ -514,8 +521,14 @@ // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), // in which case they will return 0. // Try several times before returning un-mutated data. + Mutator *M; for (int Iter = 0; Iter < 100; Iter++) { - auto M = &Mutators[Rand(Mutators.size())]; + // Even when use weighted mutations, fallback to the default selection in + // 20% of cases. + if (Options.UseWeightedMutations && Rand(100) < 80) + M = &Mutators[WeightedIndex()]; + else + M = &Mutators[Rand(Mutators.size())]; size_t NewSize = (this->*(M->Fn))(Data, Size, MaxSize); if (NewSize && NewSize <= MaxSize) { if (Options.OnlyASCII) @@ -568,15 +581,36 @@ void MutationDispatcher::PrintMutationStats() { Printf("\nstat::mutation_usefulness: "); - for (size_t i = 0; i < Mutators.size(); i++) { - double UsefulPercentage = - Mutators[i].TotalCount - ? (100.0 * Mutators[i].UsefulCount) / Mutators[i].TotalCount - : 0; - Printf("%.3f", UsefulPercentage); - if (i < Mutators.size() - 1) Printf(","); + SetMutationStats(); + for (size_t i = 0; i < Stats.size(); i++) { + Printf("%.3f", 100 * Stats[i]); + if (i < Stats.size() - 1) + Printf(","); + else + Printf("\n"); } - Printf("\n"); +} + +void MutationDispatcher::SetMutationStats() { + // Calculate usefulness statistic for each mutation + for (size_t i = 0; i < Stats.size(); i++) + Stats[i] = + static_cast(Mutators[i].UsefulCount) / Mutators[i].TotalCount; +} + +void MutationDispatcher::AssignMutationWeights() { + SetMutationStats(); + double SumOfStats = std::accumulate(Stats.begin(), Stats.end(), 0.0); + if (!SumOfStats) return; + // Normalize stats into weights. + for (size_t i = 0; i < Stats.size(); i++) + MutationWeights[i] = Stats[i] / SumOfStats; +} + +size_t MutationDispatcher::WeightedIndex() { + std::discrete_distribution SelectIndex(MutationWeights.begin(), + MutationWeights.end()); + return SelectIndex(GetRand()); } } // namespace fuzzer Index: lib/fuzzer/FuzzerOptions.h =================================================================== --- lib/fuzzer/FuzzerOptions.h +++ lib/fuzzer/FuzzerOptions.h @@ -53,6 +53,7 @@ int PrintNewCovFuncs = 0; bool PrintFinalStats = false; bool PrintMutationStats = false; + bool UseWeightedMutations = false; bool PrintCorpusStats = false; bool PrintCoverage = false; bool PrintUnstableStats = false; Index: test/fuzzer/fuzzer-weightedmutations.test =================================================================== --- /dev/null +++ test/fuzzer/fuzzer-weightedmutations.test @@ -0,0 +1,6 @@ +RUN: %cpp_compiler %S/SimpleTest.cpp -o %t-WeightedMutationsTest + +# Weighted mutations only trigger after first 10,000 runs, hence flag. +RUN: not %run %t-WeightedMutationsTest -use_weighted_mutations=1 -seed=1 -runs=100000 2>&1 | FileCheck %s + +CHECK: BINGO