[libFuzzer] Initial implementation of weighted mutation leveraging during runtime.

[kodewilliams]

Summary

Added functions that calculate stats while fuzz targets are running and give
mutations weight based on how much new coverage they provide, and choose better
performing mutations more often.

Patch by Kodé Williams (@kodewilliams).

[metzman]

Left a few comments with high level concerns and some less important ones as well.
Did you use clang-format on this? If not I may have to start using vscode myself since clang-format had no suggested changes to this. Good job.

lib/fuzzer/FuzzerFlags.def

166

Please put some kind of explanation here.

lib/fuzzer/FuzzerLoop.cpp

562

Is this assertion useful?

563

Let's not use magic numbers. Please use a constant instead of 10,000.

lib/fuzzer/FuzzerMutate.cpp

525

Better not to clobber the original mutator. I would do:

if (UseMutationWeights)
  ...
else
  ...

instead of what we have here.

592

I think this should be SetMutationStats since it sets something rather than returns something.
I would also add a comment explaining what this method does since it changes the vector it accepts.

596

Although we use percentages in when printing stats, I'm not sure we need to do it here (and in other parts of this CL), since the only other thing that will see this number is your own code.

607

nit: Please add a period to the end of this comment and all others that are missing one.

610

I don't think I like the fact that 1 is the default weight. But maybe I misunderstand what its implications are.

I think because 1 is the default weight, a totally useless mutation would be weighted higher than a mutation that is useful less than 1/1000 times.

Less importantly:

Let's use a constant instead of 1 a magic number.

Also, I think it would be better if the body of this if were on its own line (for consistency with the else) but clang-format agrees with you.
I don't think you should change this unless matt or kcc says to.

611

I think the placement of this comment is awkward. Maybe put on the same line as else.

613

I'm somewhat unsure why we divide by SumOfStats, can you explain this to me please?

615

Think this loop can be eliminated and that SumOfWeights can be calculated in the previous loop.
Actually, won't it always be 1000?

620

Helpful comment! I think it can be improved in 2 ways:

1. Move it outside the function.
2. Change the order so that it says the main purpose first and then says what happens to lowest weighted mutations.

624

I don't think this line does what you want. Did you have any warnings compiling your code?

RandomMark and MutationWeights are both unsigned values so RandomMark - MutationWeights[i] will never be less than 0.
I think comparing them directly will work better than subtracting them (which I think is harder to understand).

627

Is the purpose of this to ensure that we return an index on the last iteration?
I need to think about this technique more but I am not sure it is fair (ie: things with equal weight have equal chance of being picked).

629

I would add an assert(false) so that it is obvious if it does happen.

lib/fuzzer/FuzzerMutate.h

103

IMO the word "Records" is better than "Gets" which implies something returned.
I also think this sentence is easier to understand with a comma after "coverage"

173

super nit: I think the language here can be slightly improved. Maybe this instead:

// Used to weight mutations based on usefulness.

174

I don't think MutationWeights should store size_t since it isn't really storing sizes.
This size_t seems to have infected a lot of other code in this CL so removing it will be nice.

175

I don't find it great to use UseMutationWeights to special case the case when we haven't assigned any weights yet.
It would be cleaner if GetMutationStats and AssignMutationWeights were called before any mutations happened, so that we don't need to special case but everything works as if we did.

test/fuzzer/fuzzer-weightedmutations.test

4 ↗

(On Diff #156623)

How long does it take to do 100k runs? Does this UnitTest take long?

Also, what behavior does this test verify? The only thing I can tell is that weighted mutations doesn't crash anything.
I think it would be nice to have a test of something more substantial if possible.

[metzman]

lib/fuzzer/FuzzerMutate.cpp

611

I'm also unsure what three decimal places this comment is referring to. We don't round anywhere here do we?

627

Actually I think it is fair. But let's have a comment explaining how this technique works.

[kodewilliams]

I used git version of clang-format with -p flag for the non-trivial changes, but I believe there is also a VS Code plugin that includes clang-format, so you should try it @metzman

[Dor1s]

lib/fuzzer/FuzzerFlags.def

166

please format the line to be consistent with style of the rest of the file

lib/fuzzer/FuzzerLoop.cpp

41

why not static?

41

I think it may have a better name, maybe something like kUpdateMutationWeightRuns

559

Check the bool flag first, then check number of runs

lib/fuzzer/FuzzerMutate.cpp

23

Do we use this anywhere outside of MutationDispatcher::AssignMutationWeights? Looks like we don't, please use a local variable inside the function for that.

67

This won't use Mutate_CustomCrossOver, will it? We should probably use Mutators.size() here and debug what was the root cause of the test that was failing for you.

594

Mismatch with line 69

613

+1

622

That's not good, we should not loop through the array and implement our own weighted random selector, there are STL classes for that. See how corpus distribution is implemented, for an example: https://github.com/llvm-mirror/compiler-rt/blob/master/lib/fuzzer/FuzzerCorpus.h#L294

I think you can try std::discrete_distribution instead, it looks sufficient for our purpose.

test/fuzzer/fuzzer-weightedmutations.test

4 ↗

(On Diff #156623)

+1

[metzman]

lib/fuzzer/FuzzerMutate.cpp

592

Please make this comment say explicitly that it modifies the argument it is passed.

596

Since this isn't a percentage anymore, the name UsefulPercentage needs to be updated.
Some general advice: After making suggested changes in a code review, you should go back through your code to see if it still makes sense, and then update it where the suggested changes have amde it necessary to do so.
Also, the parentheses don't do anything here.

605

SumOfStats can be calculated in the loop in SetMutationStats right?

610

How about instead of having a default usefulness stat of 0 and a default MutationWeight of 1 we just use 1/(100 * 1000) as the default stat.

613

Please leave a comment explaining why we are adding kDefaultMutationWeight here.
Also, since this else body is multiple lines, please put curly braces around it.
Another thing: let's use a const instead of magic number 1000.
Some general advice about code reviews: If a reviewer comments that a change should be made, you should go through your code and see if that same change needs to be made elsewhere.

nit: inner parentheses not actually needed.

615

Doesn't it always end up as 1000 (now 1000+Mutators.size()*kDefaultMutationWeight) at the end of the loop?

Also, if a reviewer leaves a question/comment that looks like it needs a response, (ie: not a request to change something) please reply to it instead of marking it Done.
It's impossible to properly review code if the author is unresponsive.
Even if the question was discussed offline (in this particular case it wasn't), it is good to summarized the answer when for reviewers who weren't in the offline conversation.
Do this for every question I have asked in this review.

620

Does this need to return a size_t?
Also, was this inspired by https://stackoverflow.com/a/1761646 ?

lib/fuzzer/FuzzerMutate.h

119

This comment is phrased somewhat differently from the others, maybe phrase it like so:
Returns the Index of a mutation...

[metzman]

This CL is still broken, it doesn't actually do what it is intended to do.
I recommend testing it more thoroughly (manually, or preferably using written tests) to ensure that it accomplishes it what is intended to, in at least a few cases, before starting the next review.
I personally would build one or two fuzzers with this change, and use print statements or GDB to verify that this change is doing what is intended (using sanitizer_keep_symbols=true as a gn arg will let you print variable values in gdb), and then write some tests.
This is good advice for most code reviews, really they should only contain broken code if you are asking the reviewer why certain code is broken.

lib/fuzzer/FuzzerLoop.cpp

41

+1, the name we originally picked together is incorrect.

559

+1.
When you have a condition composed of two or more conditions, you can take advantage of short circuiting by putting the more efficient (especially if likely to be false) conditions first.
You can read more on this here.

lib/fuzzer/FuzzerMutate.cpp

593

This method is kind of weird. It is only called once with an argument called Stats which is a file-scope variable that it then shadows.
Please change the method so it no longer shadows the variable (ie: change the name of the argument or less preferably, change the method to not take any argument at all).
I'm also unsure it's worth keeping as its own function.

597

This is a serious bug, it pretty much breaks the CL.
The size of Stats on the first iteration is Mutators.size() not 0. Pushing to the back simply doubles the size of the array so every mutator ends up with a default weight.

lib/fuzzer/FuzzerMutate.h

96

Please use Doxygen style comments (ie: ///) like the other methods in this file.

test/fuzzer/fuzzer-weightedmutations.test

4 ↗

(On Diff #156623)

I think it will be hard to verify some of the behavior that I have observed is broken in this CL with an integration test. You may want to use a unittest for this purpose.

[metzman]

In D49621#1173805, @metzman wrote:

This is good advice for most code reviews, really they should only contain broken code if you are asking the reviewer why certain code is broken.

Obviously we can't always write perfect code, but in the above comment, I mean that the code we put up for review should work as intended in simple cases.

[kodewilliams]

Unit test giving problems to write due to most members being private. Addressed all other comments.

[kodewilliams]

lib/fuzzer/FuzzerMutate.cpp

597

Oversight on my end, not sure how I missed this so many times reading it. Stats should be cleared before these push_back instructions are executed.

605

It was suggested that SumOfStats be declared locally in AssignMutationWeights.

610

I feel like that works, it's close enough to zero to show basically minimal usefulness but isn't actually zero so it eliminates the case of me setting the default weight to 1.

611

We don't round anything, just when printing but even then that's just the format specifier rounding.

613

I divide by SumOfStats in order to normalize the numbers, since the usefulness percentages are ratios of themselves and not a total, the only way to determine which one is better than the other is by finding how much of the total usefulness each mutation accounts for.

615

Using discrete_distribution, I no longer need the SumOfWeights. And will do.

620

I had the original thought to decrement each mutation stat until it got to zero (we had discussed it in person). Then I realized it would not work in a case where the number of runs was not specified, so I got to searching and someone had the same problem I had (https://medium.com/@peterkellyonline/weighted-random-selection-3ff222917eb6). Inspired by this Medium post.

In MutateImpl, by default it uses Rand(Mutators.size()) to choose a Mutator index and Rand returns a size_t, hence my choice to also return size_t.

[metzman]

lib/fuzzer/FuzzerMutate.cpp

23

Please add a comment to explain the significance of 100 and 1000 (frankly i don't know what the purpose is of either since we don't actually round anything).

585

I like that you went to fix something based on comments you saw in on the review even if they weren't explicit.
But in general it's better not to refactor unrelated code in a CL. I'll accept it though.
This assignment statement is starting to look pretty bad, please make use a regular if else instead of ternary.

[Dor1s]

Haven't looked at the test yet, as the code needs a lot of clean up.

lib/fuzzer/FuzzerLoop.cpp

41

Repeating my previous comment:

why not static?

lib/fuzzer/FuzzerMutate.cpp

23

+1, what is it for?

66

nit: end the comment with a period

524–529

How will this work during first 10000 runs? Do we have a uniform distribution by default?

lib/fuzzer/FuzzerMutate.h

113

nit: "Returns" -> "Prints" or "Outputs"

[Dor1s]

lib/fuzzer/FuzzerMutate.cpp

581–582

It would be much safer to use Stats.size() here instead of Mutators.size() since you're using i to access elements in Stats, not in Mutators.

582

Move Printf call to the next line please. Also, this stat::... syntax is used for final stats. If we decide to print something during runtime, we should probably follow the style of the other log messages.

583

Again, overcomplication. We should start with some initial weights, and later on only overwrite those.

585

+1

585

Actually, that seems to be unnecessary complicated. Initially, we should have some default values in Stats. Probably zero, since none of the stats have been useful at that point. Later on, we should be able to overwrite default Stats value with a new one. That's it, there is no way we'll have to put the default value back.

Also, I don't find it good to check whether TotalCount is 0 or not on every run. Let's just initialize it with 1 in the very beginning, so it will never be 0 and it always will be safe to use that value as a divisor.

588

I don't understand why we need + kDefaultMutationWeight, as well as why we multiply the value by 1000.

590

This code is duplicated in MutationDispatcher::PrintMutationStats, can you please have it in a one place and call it from different places as needed.

600

I'd ask you to move SumOfStats += Stat; to the next line just to follow the style, but actually you should use std::accumulate instead of manual looping through the values.

609

It would be very inefficient to create a new random generator every time when we need to select an index. There is Random Rand(Seed); declared in the FuzzerDriver and I believe all the other code is using it, please use it as well.

610

Also, it's not the first time it looks like you've just copied the code from somewhere without even changing variable names to follow project's style. I guess, https://en.cppreference.com/w/cpp/numeric/random/discrete_distribution this time.

Also, please don't forget to run clang format before uploading a CL.

615

This is an overkill, we never change sizes of Mutators and MutationWeights from the very beginning of the fuzzing. If you want to assert that their sizes are equal, somewhere after FuzzerMutate.cpp:68 would be the best place, but that wouldn't make any sense since you've just called resize there. Just remove the assert and return SelectIndex(gen).

[kodewilliams]

PTAL @metzman @Dor1s

lib/fuzzer/FuzzerMutate.cpp

23

It is just there to represent a usefulness ratio that is near to but not entirely useless. So that it still gets weight instead of calculating to 0.

524–529

AssignMutationWeights is called initially and sets all the mutation weights to the default, therefore they would be all be weighted the same and have the same probability before 10k runs.

588

I add the default to ensure that mutations that are any amount more useful than the default get weighted higher in the distribution. No longer multiplying by 1000.

test/fuzzer/fuzzer-weightedmutations.test

4 ↗

(On Diff #156623)

Real: 0m 0.157s
User: 0m 0.036s
Sys: 0m 0.076s

[metzman]

lib/fuzzer/FuzzerMutate.cpp

33–36

Can you leave a comment here about why we are starting with a UsefulCount and a TotalCount of 1?

37–38

Why do ChangeASCIIInt and ChangeBinInt start with a UsefulCount of 0 when everything else starts with 1?

602

I don't think we need to multiply by 1.0, right? I don't think it (or the parentheses) does anything, please remove them if I am correct.

606

Kode, I don't think this is what Max meant. I believe that here you need to use the rand obtained by calling GetRand.
It's possible, though unlikely, that not doing this was causing the test flakiness you were seeing before.
I would run the previously flaky test in a loop and ensure that the tests pass every time, since if there is any flake we don't know about, it will be more painful to get rid of later rather than now.

[metzman]

test/fuzzer/fuzzer-weightedmutations.test

4 ↗

(On Diff #156623)

Amount of time LGTM.

[Dor1s]

lib/fuzzer/FuzzerMutate.cpp

23

That doesn't seem right to me. Let's say we have a tough target -- where it's hard to reach any new coverage. In fact, we have a lot of them, when we use a full corpus.

So, after running for a while, it finally finds a couple useful mutations, all of them get weights, say, 10^(-6) (again, totally possible), while all "useless" mutations get the default weight of 10^(-5). That would mean, "useless" mutations would be chosen much more often than "useful" ones.

IMO, the better approach would be something like what we've discussed in the past:

1. make random decision whether we use weighted mutations or default selection, 80% vs 20% should be fine. Once start testing, can change to 90 vs 10 or any other proportion
2. if weighted mutations was chosen, call WeightedIndex(); otherwise, use default case

That approach would be universal as it doesn't use any magic numbers which correspond to a particular target, as your 100*1000 can behave very differently with targets having different speed.

37–38

+1

588

That won't work well for all targets. If mutations stats are very low numbers, that default mutation weight constant will bias the selection towards more uniform distribution, rather than giving more favor to more useful mutations.

594

here and on line 603, what's the point of multiplying by 1.0?

606

Yes, don't create a new Random object, use an existing one from FuzzerDriver. That's crucial for keeping deterministic behavior, as Jonathan has pointed out.

[metzman]

lib/fuzzer/FuzzerMutate.cpp

23

I think it will be harder to determine if this technique is useful with the 80/20 strategy.
If the concern is that the weight is too high, why don't we use the smallest positive double as the default?

[Dor1s]

lib/fuzzer/FuzzerMutate.cpp

23

I think it will be harder to determine if this technique is useful with the 80/20 strategy.

Why will it be harder? That percentage would just control the factor of how strongly our strategy affects fuzzing process. We should still be able to see either a negative a positive impact. Changing the distribution (e.g. use 90/10 after 80/20) would multiple that impact a little bit.

If the concern is that the weight is too high, why don't we use the smallest positive double as the default?

I can't think of a value that would work well for both cases when useful mutations have stats like 10^(-3) and 10^(-6). We should avoid relying on anything that depends on fuzz targets speed / complexity of finding a new input. We already have magic threshold of 10000, let's not add more of those.

524–529

With my proposal it will be something like:

// 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())];

[kodewilliams]

lib/fuzzer/FuzzerMutate.cpp

23

@metzman @Dor1s PTAL. Made changes and ran tests. Test in question is no longer flaky (ran about 50 times) and ran two experiments locally. In both cases, the corpus grew more with the option enabled :) so maybe a good sign.

594

Both UsefulCount and TotalCount are uint64_t but Stats is a vector of doubles, so I multiply by 1.0 to make sure it gets calculated as double.

[Dor1s]

lib/fuzzer/FuzzerMutate.cpp

594

It's an obscure way to cast a value to another type. Please use static_cast<double>(Mutators[i].UsefulCount) instead.

[Dor1s]

I don't like the test as it only tests that we do not completely break libFuzzer, but doesn't test the feature itself. I'll play with some ideas locally, will share those if anything works out. Otherwise, I guess we'll proceed with this test.

lib/fuzzer/FuzzerMutate.cpp

33–36

"zero division" -> "division by zero"

66

add ", init with uniform weights distribution." to the comment please

67

Let's remove kDefaultMutationWeight variable, just use 1.0 here.

68

We should start with 0 values in Stats, remove kDefaultMutationStat and leave Stats.resize(Mutators.size() here.

522

Please do Mutator *M = nullptr; just to be safe in case there ever will be any bug and the pointer won't be initialized.

608

We should keep the distribution object inside of MutationDispatcher class and update it only every kUpdateMutationWeightRuns, not for every weighted index retrieval.

lib/fuzzer/FuzzerMutate.h

104

Let's rename this method to UpdateMutationStats, that name would make more sense.

174

This line and line 175 feel slightly inconsistent, both should be MutationWeights and MutationStats or just Weights and Stats. I'd prefer the latter, as we're already inside MutationDispatcher class and clearly deal with mutations here.

174

Actually, we don't need MutationWeights here, we need only the distribution. Could you please do the following:

1. Remove this MutationWeights member

2. Add Distribution member (also see my comment for WeightedIndex() function)

3. Rename MutationDispatcher::AssignMutationWeights() to MutationDispatcher::UpdateDistribution()

4. In MutationDispatcher::UpdateDistribution() create a local vector Weights and update it using Stats value as you do now

5. Update the Distribution using the Weights, e.g. see how it's done for the corpus distribution (FuzzerCorpus.h:294)

[kodewilliams]

PTAL @metzman @Dor1s

[Dor1s]

Left a couple minor comments. Looks good otherwise. Still not happy with the test, but can't think of anything better so far.

Matt, please take a look when you get a change.

lib/fuzzer/FuzzerMutate.cpp

599

This variable is not needed until line 605. And may be not needed at all if we do an early return on line 603. Please declare it between lines 603 and 605.

600

We don't need to do this, just pass Mutators.size()to constructor of Vector<double> Weights. Default weight should be 0, so Vector<double> Weights(Mutators.size()); would be enough

[Dor1s]

LGTM

[morehouse]

lib/fuzzer/FuzzerMutate.cpp

524–529

use -> using

526

Maybe if (... && Rand(5)) would be simpler.

605

Is normalization necessary? I think discrete_distribution might do this internally.

606

I think you can do Distribution.param(Weights) rather than reconstructing. Might be faster.

lib/fuzzer/FuzzerMutate.h

103–111

What is the "most previous run"? Please clarify comment

[Dor1s]

lib/fuzzer/FuzzerMutate.cpp

606

Oh, right. Thanks for spotting, Matt! Kode, please remove lines 603-605 and try passing Stats to the distribution.

[kodewilliams]

PTAL @morehouse

[morehouse]

lib/fuzzer/FuzzerMutate.cpp

602

Does Distribution.param(Stats) work instead?

lib/fuzzer/FuzzerMutate.h

104

There's nothing inside UpdateMutationStats that refers to the number 10,000.

Maybe something like "Recalculates mutation stats based on latest run data."

test/fuzzer/fuzzer-weightedmutations.test

6 ↗

(On Diff #158793)

This really only tests that there's no major regression with the flag on. If this flag performs better under some circumstances, we should add a test to demonstrate that.

[morehouse]

test/fuzzer/fuzzer-weightedmutations.test

6 ↗

(On Diff #158793)

Also, we can probably add this to fuzzer-mutationstats.test instead.

[kodewilliams]

lib/fuzzer/FuzzerMutate.cpp

602

Please see other comment on Distribution.param(Weights).

606

One param function doesnt take arguments (returns a param_type object) and the other one sets the new params based on a passed in param_type object, but there would have to be another discrete_distribution object from which the param_type object would be obtained so I think that's why they do it this way in https://cs.corp.google.com/piper///depot/google3/third_party/llvm/llvm/projects/compiler-rt/lib/fuzzer/FuzzerCorpus.h?rcl=206864844&l=294

Quite literally I would have to do Distribution.param(Distribution.param()) but I'm not sure that would update the distribution.

[morehouse]

lib/fuzzer/FuzzerMutate.cpp

601

SumOfStats doesn't need to be calculated.

[Dor1s]

lib/fuzzer/FuzzerMutate.cpp

601

Matt, we needed SumOfStats to be non zero to ensure that we have at least some distribution. Until that moment is reached, we should be using the initial weights. I like this simplification though, but in that case we'll have to initialize UsefulCount with 1, so that initial Stats will be 1 / 1 for every mutation.

[morehouse]

lib/fuzzer/FuzzerMutate.cpp

601

Either approach SGTM.

[kodewilliams]

All comments addressed @morehouse

[Dor1s]

Getting ready to land.

[Dor1s]

Rebase

lib/fuzzer/FuzzerDriver.cpp

if (Flags.verbosity > 0 && !Dictionary.empty())
     Printf("Dictionary: %zd entries\n", Dictionary.size());
   bool DoPlainRun = AllInputsAreFiles();
   Options.SaveArtifacts =
       !DoPlainRun || Flags.minimize_crash_internal_step;
   Options.PrintNewCovPcs = Flags.print_pcs;
   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;
   if (Flags.handle_unstable == TracePC::MinUnstable ||
       Flags.handle_unstable == TracePC::ZeroUnstable)
     Options.HandleUnstable = Flags.handle_unstable;
   Options.DumpCoverage = Flags.dump_coverage;
   if (Flags.exit_on_src_pos)

lib/fuzzer/FuzzerFlags.def

FUZZER_FLAG_STRING(focus_function, "Experimental. "
      "Fuzzing will focus on inputs that trigger calls to this function")
 
 FUZZER_DEPRECATED_FLAG(run_equivalence_server)
 FUZZER_DEPRECATED_FLAG(use_equivalence_server)
 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_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.")

lib/fuzzer/FuzzerLoop.cpp

 #if __has_feature(memory_sanitizer)
 #undef NO_SANITIZE_MEMORY
 #define NO_SANITIZE_MEMORY __attribute__((no_sanitize_memory))
 #endif
 #endif
 
 namespace fuzzer {
 static const size_t kMaxUnitSizeToPrint = 256;
+static const size_t kUpdateMutationWeightRuns = 10000;
 
 thread_local bool Fuzzer::IsMyThread;
 
 SharedMemoryRegion SMR;
 
 bool RunningUserCallback = false;
 
 // Only one Fuzzer per process.
if (Size <= 64)
     return !memcmp(A, B, Size);
   // Compare first and last Limit/2 bytes.
   return !memcmp(A, B, Limit / 2) &&
          !memcmp(A + Size - Limit / 2, B + Size - Limit / 2, Limit / 2);
 }
 
 void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
   TPC.RecordInitialStack();
+  if (Options.UseWeightedMutations &&
+      TotalNumberOfRuns % kUpdateMutationWeightRuns == 0)
+    MD.UpdateDistribution();
   TotalNumberOfRuns++;
   assert(InFuzzingThread());
   if (SMR.IsClient())
     SMR.WriteByteArray(Data, Size);
   // We copy the contents of Unit into a separate heap buffer
   // so that we reliably find buffer overflows in it.
   uint8_t *DataCopy = new uint8_t[Size];
   memcpy(DataCopy, Data, Size);
   if (EF->__msan_unpoison)
     EF->__msan_unpoison(DataCopy, Size);
   if (CurrentUnitData && CurrentUnitData != Data)

lib/fuzzer/FuzzerMutate.h

public:
   void AddWordToManualDictionary(const Word &W);
 
   void PrintRecommendedDictionary();
 
   void SetCorpus(const InputCorpus *Corpus) { this->Corpus = Corpus; }
 
   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();
+  /// Recalculates mutation stats based on latest run data.
+  void UpdateMutationStats();
+
+  /// Sets weights based on mutation performance during fuzzer run.
+  void UpdateDistribution();
+
+  /// 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 {
     size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
     const char *Name;
     uint64_t UsefulCount;
     uint64_t TotalCount;
   };
 
   size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size,
                                size_t MaxSize);
   size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize,
                     Vector<Mutator> &Mutators);
 
   size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
                       size_t ToSize, size_t MaxToSize);
private:
   Vector<uint8_t> MutateInPlaceHere;
   Vector<uint8_t> MutateWithMaskTemp;
   // CustomCrossOver needs its own buffer as a custom implementation may call
   // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere.
   Vector<uint8_t> CustomCrossOverInPlaceHere;
 
   Vector<Mutator> Mutators;
   Vector<Mutator> DefaultMutators;
+
+  // Used to weight mutations based on usefulness.
+  Vector<double> Stats;
+  std::discrete_distribution<size_t> Distribution;
 };
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MUTATE_H

lib/fuzzer/FuzzerMutate.cpp

 #include "FuzzerExtFunctions.h"
 #include "FuzzerIO.h"
 #include "FuzzerOptions.h"
 
 namespace fuzzer {
 
 const size_t Dictionary::kMaxDictSize;
 
 static void PrintASCII(const Word &W, const char *PrintAfter) {
   PrintASCII(W.data(), W.size(), PrintAfter);
 }
 
 MutationDispatcher::MutationDispatcher(Random &Rand,
                                        const FuzzingOptions &Options)
     : Rand(Rand), Options(Options) {
   DefaultMutators.insert(
       DefaultMutators.begin(),
       {
-          {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes", 0, 0},
-          {&MutationDispatcher::Mutate_InsertByte, "InsertByte", 0, 0},
+          // Initialize useful and total mutation counts as 1 in order to
+          // have mutation stats (i.e. weights) with equal non-zero values.
+          {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes", 1, 1},
+          {&MutationDispatcher::Mutate_InsertByte, "InsertByte", 1, 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},
-          {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt", 0,
-           0},
-          {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt", 0,
-           0},
-          {&MutationDispatcher::Mutate_CopyPart, "CopyPart", 0, 0},
-          {&MutationDispatcher::Mutate_CrossOver, "CrossOver", 0, 0},
+           "InsertRepeatedBytes", 1, 1},
+          {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte", 1, 1},
+          {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit", 1, 1},
+          {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes", 1, 1},
+          {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt", 1,
+           1},
+          {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt", 1,
+           1},
+          {&MutationDispatcher::Mutate_CopyPart, "CopyPart", 1, 1},
+          {&MutationDispatcher::Mutate_CrossOver, "CrossOver", 1, 1},
           {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
-           "ManualDict", 0, 0},
+           "ManualDict", 1, 1},
           {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
-           "PersAutoDict", 0, 0},
+           "PersAutoDict", 1, 1},
       });
   if(Options.UseCmp)
     DefaultMutators.push_back(
-        {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP", 0, 0});
+        {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP", 1, 1});
 
   if (EF->LLVMFuzzerCustomMutator)
-    Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom", 0, 0});
+    Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom", 1, 1});
   else
     Mutators = DefaultMutators;
 
   if (EF->LLVMFuzzerCustomCrossOver)
     Mutators.push_back(
-        {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver", 0, 0});
+        {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver", 1, 1});
+
+  // For weighted mutation selection, init with uniform weights distribution.
+  Stats.resize(Mutators.size());
 }
 
 static char RandCh(Random &Rand) {
   if (Rand.RandBool()) return Rand(256);
   const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
   return Special[Rand(sizeof(Special) - 1)];
 }
 
 size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size,

 // Mutates Data in place, returns new size.
 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
                                       size_t MaxSize,
                                       Vector<Mutator> &Mutators) {
   assert(MaxSize > 0);
   // 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 = nullptr;
   for (int Iter = 0; Iter < 100; Iter++) {
-    auto M = &Mutators[Rand(Mutators.size())];
+    // Even when using weighted mutations, fallback to the default selection in
+    // 20% of cases.
+    if (Options.UseWeightedMutations && Rand(5))
+      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)
         ToASCII(Data, NewSize);
       CurrentMutatorSequence.push_back(M);
       M->TotalCount++;
       return NewSize;
     }
ManualDictionary.push_back(
       {W, std::numeric_limits<size_t>::max()});
 }
 
 void MutationDispatcher::RecordUsefulMutations() {
   for (auto M : CurrentMutatorSequence) M->UsefulCount++;
 }
 
 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(",");
-  }
+  UpdateMutationStats();
+  for (size_t i = 0; i < Stats.size(); i++) {
+    Printf("%.3f", 100 * Stats[i]);
+    if (i < Stats.size() - 1)
+      Printf(",");
+    else
       Printf("\n");
   }
+}
+
+void MutationDispatcher::UpdateMutationStats() {
+  // Calculate usefulness statistic for each mutation
+  for (size_t i = 0; i < Stats.size(); i++)
+    Stats[i] =
+        static_cast<double>(Mutators[i].UsefulCount) / Mutators[i].TotalCount;
+}
+
+void MutationDispatcher::UpdateDistribution() {
+  UpdateMutationStats();
+  Distribution = std::discrete_distribution<size_t>(Stats.begin(), Stats.end());
+}
+
+size_t MutationDispatcher::WeightedIndex() { return Distribution(GetRand()); }
 
 }  // namespace fuzzer

lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   std::string FocusFunction;
   std::string DataFlowTrace;
   bool SaveArtifacts = true;
   bool PrintNEW = true; // Print a status line when new units are found;
   bool PrintNewCovPcs = false;
   int PrintNewCovFuncs = 0;
   bool PrintFinalStats = false;
   bool PrintMutationStats = false;
+  bool UseWeightedMutations = false;
   bool PrintCorpusStats = false;
   bool PrintCoverage = false;
   bool PrintUnstableStats = false;
   int HandleUnstable = 0;
   bool DumpCoverage = false;
   bool DetectLeaks = true;
   int PurgeAllocatorIntervalSec = 1;
   int  TraceMalloc = 0;

test/fuzzer/fuzzer-mutationstats.test

 RUN: %cpp_compiler %S/SimpleTest.cpp -o %t-MutationStatsTest
-RUN: not %run %t-MutationStatsTest -print_mutation_stats=1 2>&1 | FileCheck %s
+RUN: not %run %t-MutationStatsTest -print_mutation_stats=1 2>&1 | FileCheck %s --check-prefix=STAT
 
 # Ensures there are some non-zero values in the usefulness percentages printed.
-CHECK: stat::mutation_usefulness:   {{[0-9]+\.[0-9]+}}
+STAT: stat::mutation_usefulness:   {{[0-9]+\.[0-9]+}}
+
+# Weighted mutations only trigger after first 10,000 runs, hence flag.
+RUN: not %run %t-MutationStatsTest -use_weighted_mutations=1 -seed=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=WEIGHTED
+
+WEIGHTED: BINGO