This is an archive of the discontinued LLVM Phabricator instance.

Entropic: Boosting LibFuzzer Performance

Authored by marcel on Jan 31 2020, 4:48 AM.



This is collaboration between Marcel Boehme @ Monash, Australia and Valentin Manès plus Sang Kil Cha @ KAIST, South Korea.

We have made a few modifications to boost LibFuzzer performance by changing how weights are assigned to the seeds in the corpus. Essentially, seeds that reveal more "information" about globally rare features are assigned a higher weight. Our results on the Fuzzer Test Suite seem quite promising. In terms of bug finding, our Entropic patch usually finds the same errors much faster and in more runs. In terms of coverage, our version Entropic achieves the same coverage in less than half the time for the majority of subjects. For the lack of space, we shared more detailed performance results directly with @kcc. We'll publish the preprint with all the technical details as soon as it is accepted. Happy to share if you drop us an email.

There should be plenty of opportunities to optimise further. For instance, while Entropic achieves the same coverage in less than half the time, Entropic has a much lower #execs per second. We ran the perf-tool and found a few performance bottlenecks.

Thanks for open-sourcing LibFuzzer (and the entire LLVM Compiler Infrastructure)! This has been such a tremendous help to my research.

Diff Detail

Event Timeline

marcel created this revision.Jan 31 2020, 4:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 31 2020, 4:48 AM
marcel edited the summary of this revision. (Show Details)Jan 31 2020, 4:58 AM
kcc added a comment.Jan 31 2020, 2:19 PM

It's exciting that such a small change can bring such a great improvement.
Thanks for the contribution.

I left several comments in the code and here are some higher level comments:

  • put the new functionality under a flag, off by default, so that we can properly A/B test it once it's committed.

If it proves to be superior we'll enable the flag by default and then remove the old algorithm and remove the flag.

  • try to unit-test the most interesting functionality (see fuzzer/tests/FuzzerUnittest.cpp)
  • write a top-level comment explaining the algorithm.
  • try to avoid unordered_map on the hot code: sadly, the STL hash table is almost always the wrong choice of a data structure for hot code.

Once there is a top-level comment I may be able to suggest a better data structure.
But I expect it to be something like an array of pairs, organized somehow (sorted? heap?)
How many rare features do we need per input? Maybe just have a fixed size array?

  • don't use size_t where you can get away with uint32_t - memory footprint is important.
  • don't use long double (unless you have to -- in which case explain why)
  • there are mentions of local vs global frequencies. Please explain in a comment what that is (corpus vs individual input?) and reflect this in the variable names (like, RareFeaturesFreqMap => LocalFreqMap)

why not just 'double'?


Any chance to have a planer data structure here? (sorted array or some such)
Also, why size_t?
The feature is 4 bytes and the frequency can probably be 4 or even 2 bytes. (2 bytes is hard for alignment).


why is this public?
Also, why the g_ prefix?


do you need this?
the following line should take care of it


Please try to follow the coding style, i.e. capitalize the names:


Also, the term Singleton may be a bit too overloaded.
How about


or some such?


try not to use constants like this.
At the very least, use

const size_t kSomething = 100;
if (xxx.size() > kSomething)

if there is any reason to play with different value, you may want to use a flag instead

Similar for 0xFF.

Probably, the best here is to replace these two constants with function parameters so that this function becomes unit-testable.
Which reminds me: please consider adding unit tests to the key functionality like this one.


This is the hotspot, right?
My guess is that using a hash map here causes most of the slowdown, need a faster data structure...
Need to think...
It will help if you have describe the algorithm in a comment.


a top-level comment explaining the computations would be nice


use () just in case, replace 10000 with kSomething
don't use random(), pass (Random &Rand) instead


why not

for (auto It : I->RareFeaturesFreqMap)



don't use libc's rand(), pass (Random &Rand) instead


does this have to be 8-byte per feature?


do you need this change?

marcel marked 10 inline comments as done.Feb 1 2020, 6:51 PM
marcel added a subscriber: Valentin.

Thanks so much for your feedback!

  1. We maintain feature abundance counts globally (for the entire fuzzing campaign) and locally (for each InputInfo).
    • Whenever an input generated by fuzzing II executes feature f, we increment the global abundance count for f as well as the local abundance count for f @ II.
    • The global abundance counts are stored in FeaturesFreqMap, an array of size kFeatureSetSize.
      • It requires one read/write for *each* UpdateFeatureFrequency which is very hot (Line 331). To maximize efficiency, I decided to use a fixed-size array. There is only one global map. So, even though the map is fairly sparse, memory overhead might be okay.
      • Currently, each element is of size_t because a feature might be executed as often as new inputs are generated. The total number of inputs generated (g_NumExecutedMutations) will likely not fit into uint32_t.
      • However, if memory footprint is a concern over efficiency, we might even go down as much as uint16_t since only abundance counts below MostAbundant_RareFeature are relevant. This adds an overflow check to each (hot!) write (Line 331).
    • The local abundance counts are stored with each InputInfo in RareFeaturesFreqMap, and unordered_map<size_t,size_t>
      • It is written to in UpdateFeatureFrequency but only if the current feature is globally rare. In most cases UpdateFeatureFrequency returns in Line 337 before the local feature count is updated.
      • It is read when we iterate over all keys (and values) to compute the energy for an input in UpdateEnergy.
      • We can go faster with other hashmaps. Most efficient would be a fixed size array that is simply indexed with the feature ID (like the global abundance counts). However, the arrays are very sparse and the memory footprint should be too high.
    • There is also some reading of the global and local abundance counts in AddRareFeature (Line 244), but that should happen quite rarely.
  2. How do we decide what is considered a globally rare feature?
    • Currently, we fixed this definition quite arbitrary as: {the top 100 least abundant features} UNION {all features with abundance below 0xFF}.
    • When a feature becomes abundant, it is removed globally and from each II locally. This is handled in AddRareFeature (which also updates MostAbundant_RareFeature)
    • If you allow too many features to be considered as rare, you will spend more time computing the energy for a seed.
    • If you allow too few features to considered as rare, your performance gain from Entropic might decrease.
    • Not sure whether we already hit the sweet spot. We can pull these out as command line options to see what works.

In addition, we will

  • add a command line flag to enable entropic for libfuzzer,
  • pull out the constants either as command line options or as global constants,
  • turn most occurrences of long double to double (except in UpdateEnergy where we need the precision, I think).
  • update variable names, add comments, and
  • see how we can unit test our patch (@Valentin?)

Let me know what you think.


Whether or not unorder_map, see top-level comment. If unordered_map, then uint32_t for keys and values should work.


g_NumExecutedMutations contains the total number of inputs generated. It is updated in FuzzerLoop.c in MutateAndTestOne. I can drop the g_ prefix.


We will pull these constants out as command line options.


Yes. This is the hot spot. However, most executions should exit in Line 337.
FeaturesFreqMap is an array. Don't think you can get much faster here.


Each entry is upper-bounded by the total number of generated inputs g_NumExecutedMutations which likely won't fit into uint32_t. That's why I chose size_t.

However, we really only need abundance information for features with an abundance below MostAbundant_RareFeature. If memory footprint is a concern, we can go down to uint16_t at the cost of an overflow check in the hot code in UpdateFeatureFrequency. See top-level comment for more details.


Unrelated. This is just fixing a problem where LibFuzzer prints REDUCE more often than it should.

Dor1s added a comment.Feb 3 2020, 3:10 PM

I'm happy to take a review pass too. Just ping me when / if this is needed.

kcc added a comment.Feb 3 2020, 4:53 PM

Sounds good. Max and I will do the next round(s) of review.

Re RareFeaturesFreqMap, I would consider two more options:

  1. a vector of pairs (feature, freq), ordered by feature. Updating the frequency would be log(N) and removing a feature would be N*log(N), but it may still be better than unordered map.
  2. same as a above, but just use a fixed-size array of some small size, e.g. 8. My assumption is that most inputs have very few, if any, rare features, and in cases where a given input has more than 8 rare features, it doesn't matter if we drop some of them.

option 2 is an optimization of option 1, so can just go with option 1 and see if it's too slow.


yea, please drop g_.


Yea, I'd prefer uint16_t and a saturated add. Just to save some RAM


I'd prefer to not mix unrelated changes in one diff -- makes the code review quadratic.
Please contribute this one separately (I am not 100% sure I understand it)

marcel updated this revision to Diff 246591.Feb 25 2020, 4:09 PM
marcel marked 3 inline comments as done.Feb 25 2020, 4:09 PM

Changes since last commit:

  • Better memory footprint
    • Global feature frequencies is a fixed size array with uint16_t-width elements: uint16_t GlobalFeatureFreqs[kFeatureSetSize] (instead of size_t-width)
    • Local feature frequencies is a sorted vector of pairs: Vector<std::pair<uint32_t,uint16_t>> FeatureFreqs (instead of unordered unordered_map<size_t,size_t>)
  • Added options to enable/disable entropic and pulled some constants out:
    • Option entropic (default: 0): Enables entropic power schedule.
    • Option considered_rare (default: 0xFF): If entropic is enabled, all features which are observed less often than the specified value are considered as rare.
    • Option topX_rarest_features (default: 100): 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).
    • Option sparse_energy_updates (default: 10000): If entropic is enabled, the inverse value specifies the probability to update the corpus distribution even though no features or seeds were added or deleted. A larger value means less updates.
    • Constant kProbAgressiveSchedule (default: 80): Determines the probability to choose a more aggressive schedule (assigning zero weight to below average seeds).
  • Turned most occurrences of long double to double.
  • Better variable names and comments.
  • Removed some redundant code.
  • Fuzzer unit tests (Thanks @Valentin!)

The patch applies to LLVM-trunk. We tested these changes by repeating all our FTS experiments (20 runs).
The performance results look pretty much the same as with the other patch, which is good.

vitalybuka added inline comments.Feb 27 2020, 2:04 PM

it would be nice to manipulate this fields only with reasonable named methods


could you please initialize them?


It would be nice to rename variables in a such way that reader without background can understand what is going on.


please don't reuse variables like Y here
just declare as close as possible to first use, or even better with assignment


uint16_t GlobalFeatureFreqs[kFeatureSetSize] = {}; instead of memsets
it would be nice do to the same for other arrays here, but in a separate patch


entropic -> focus_rare_features

Not sure how, it would be nice to rename sparse_energy_updates as something meaningful to libfuzzer user, to make it explain behavior change, not implementation details like now.

dgg5503 added a subscriber: dgg5503.Mar 9 2020, 1:56 PM
marcel updated this revision to Diff 250155.Mar 13 2020, 2:43 AM
marcel marked an inline comment as not done.

In this *third revision*, we accomodate Vitaly's comments:

  • Better naming (e.g., s/Sum_Y/SumIncidence/g)
  • Initialized variables on struct InputInfo
  • Locally, don't reuse variables but declare them anew.
  • Instead of memset'ing or global array, we declare uint16_t GlobalFeatureFreqs[kFeatureSetSize] = {};
  • We keep the entropic option, though. Hope this is okay.

In addition, we removed option "sparse_energy_updates" and made it a constant kSparseEnergyUpdates = 10000.

Also, good news: Entropic is coming in second @ Fuzzbench:

marcel marked 15 inline comments as done.Mar 18 2020, 5:45 PM


Dor1s added inline comments.Mar 18 2020, 9:59 PM

since this is a vector, I don't think we need to manually clear it in the destructor


nit: seems like log should be sufficient, as Energy is double, not long double


nit: I'd rather use auto or decltype(RareFeatures)::value_type to avoid type mismatch if we ever change RareFeatures definition and forget to change the type here


assuming this code gets executed quite often, and the order inside RareFeatures isn't important, we can avoid erase-remove and do something like:

RareFeatures[index_from_the_loop] = RareFeatures.back();
RareFeatures.resize(RareFeatures.size() - 1);

but the loop on line 269 would have to use index in the vector (from 1 to < RareFeatures.size()) instead of the iterator

feel free to ignore though, it's just a suggestion which may or may not be a good one :)


since we always do this, resize() in my suggestion above might not be even needed, but that's a minor thing


can this and the loop on the line 294 be combined?


please consider adding a comment why we skip inputs with zero energy


invert the condition to reduce indentation:

if (!II)

can do return after this line and avoid else with extra indentation below


what is 1 here? would it make sense to have a static const variable with a descriptive name, e.g. kDefaultSomething?


same point, what is 0? a constant with a descriptive name or (less preferred) comment would be really helpful for others who come to read the code in future


From the code below it seems like Energy represents entropy and the max value is 0, which we reduce depending on the actual feature frequencies. Is that correct understanding?


it seems like the Rand(kSparseEnergyUpdates) clause is applicable to the Entropic case only, is that correct? Do we really need it in the vanilla case?


could you please rewrite this in a more readable if-else form?


why 20? a constant with a descriptive name or a comment would be appreciated


so if there is at least one input that touches focus function, we will be always wasting time in this loop (starting on the line 472) and then falling back to the VanillaSchedule case? In such case I think we should just check Options.FocusFunction and use vanilla schedule if it's set, just because almost always there will be input(s) touching the focus function


does it always need update, even when new coverage wasn't observed?

marcel marked 19 inline comments as done.Mar 19 2020, 5:08 AM

Preparing the next patch.


With the subsequent push_back (Line 292), do you mean a swap and pop_back here?


We are setting the frequency of Idx32 to 1. Adding a comment.


Zero (0) is the default value for lower_bound as binary search over a vector of pairs. In this case, any value would work.


Yes, we estimate the entropy over the probabilities of the features in the neighborhood of the seed. Entropy is positive. The maximum entropy is logl(GlobalNumberOfFeatures).


Yes. kSparseEnergyUpdates should apply only for Entropic.


For II, the local feature frequencies have changed. So we schedule an update. However, it will only be updated when the distribution needs an update, and we do not set DistributionNeedsUpdate here.

marcel updated this revision to Diff 251365.Mar 19 2020, 6:38 AM
marcel marked 4 inline comments as done.

Changes in this fourth revision.

  • Error message + exit if parameters '--focus_function` and --entropic are used together.
  • Refactored a constant (kMaxMutationFactor)
  • Better code formatting
    • early return for better indentation,
    • more comments,
    • less ternaries,
vitalybuka added inline comments.Mar 20 2020, 12:43 AM

please make field private and add access method if it's needed outside


DeleteFeatureFreq -> InputInfo::DeleteFeatureFreq


uint32_t MostAbundantRareFeatureIdx[2] = {}






"long double" is still there?


many of comments are marked as "Done" but I see no changes.

Dor1s added inline comments.Mar 23 2020, 11:29 PM

yes, swap and pop_back would have the same effect


sorry, I don't understand. Below are the code lines changing Energy value:

  II->Energy = 0.0;
  II->SumIncidence = 0;

  // Apply add-one smoothing to locally discovered features.
  for (auto F : II->FeatureFreqs) {
    size_t LocalIncidence = F.second + 1;
    Energy -= LocalIncidence * logl(LocalIncidence);
    SumIncidence += LocalIncidence;


  // Add a single locally abundant feature apply add-one smoothing.
  size_t AbdIncidence = II->NumExecutedMutations + 1;
  Energy -= AbdIncidence * logl(AbdIncidence);

  // Normalize.
  if (SumIncidence != 0)
    Energy = (Energy / SumIncidence) + logl(SumIncidence);

  II->Energy = (double)Energy;

as I read this, I see that Energy should be negative in many cases?

marcel marked 11 inline comments as done.Apr 14 2020, 6:57 AM

Just completed a few tests with the revised patch in FuzzBench. Going to upload the revision soon.


Moved directly into the InputInfo struct.


Implemented your swap and pop_back idea. Cheers!


Sorry for the brevity. This is why II->Energy is positive. Entropy is computed as $-\sum_{i=1}^S p_i \log(p_i)$ where $p_i$ is the probability that fuzzing II generates an input that exercises feature $i$ and $S$ is the total number of rare features. We could estimate the probability $p_i$ as the proportion of generated inputs that exercise $i$, i.e., $\hat p_i = LocalIncidence_i / SumIncidence$. If you plug this proportion into the formula for entropy, you can compute entropy as $[-\sum_{i=1}^S LocalIncidence_i \log(LocalIncidence_i)] / SumIncidence + log(SumIncidence)$. While Energy is certainly negative before // Normalize., it is positive after.

Just drop me a DM. I'll send you the write up.


Yes, keeping maximum precision during the processing to minimize the cumulative FP arithmetic error, and downcast to double once the processing is done.


Tried to address all comments either inline or in the summary. In this case, I wrote

  • We keep the entropic option, though. Hope this is okay.
marcel updated this revision to Diff 257332.Apr 14 2020, 7:52 AM
marcel marked 2 inline comments as done.

This is revision number 5. Thanks for all the great feedback!

  • Moved InputInfo functions (UpdateEnergy, UpdateFeatureFrequency, DeleteFeatureFreq) into InputInfo struct.
  • Made NumExecutedMutations private. Added public FuzzerCorpus::IncrementNumExecutedMutations()
  • Set kSparseEnergyUpdates to 100 (instead of 10000). Seems to give better results on some FuzzBench subjects.
  • Removed kProbAgressiveSchedule. Seems to give better results on some FuzzBench subjects.
  • Some cleanup in FuzzerCorpus::AddRareFeature(). Use swap and pop_back. Use arrary to maintain most and second-most abundant rare feature.
  • Been playing with LF's power schedule, and in preliminary experiments it seems that prioritizing faster seeds brings quite some performance gains.
  • Submitted PR to FuzzBench for evaluation:

FuzzBench results for Entropic:

kcc added a comment.Apr 22 2020, 1:03 PM

Commenting on just to issues, not the hole patch.


this is new in the patch, is it?
While I completely understand why we'd want to use execution time as a signal for weights,
it makes fuzzing process non-reproducible with a given seed, which I consider pretty bad.
If we used 32- or 64- bit edge counters we could have substituted them for time, but alas, we use 8-bit ones.


I'm still worried about long double due to portability.
Do you actually "know" that it's critical to use long double here?


for consistency, please use the C++ interface for getting current time (as elsewhere in the code).
But see above about my comment on time in gneral.

marcel marked 2 inline comments as done.Apr 22 2020, 4:40 PM
marcel added inline comments.

this is new in the patch, is it?

Yes. Been playing with a few smaller tweaks to boost LF performance.

While I completely understand why we'd want to use execution time as a signal for weights,
it makes fuzzing process non-reproducible with a given seed, which I consider pretty bad.

Do you mean LibFuzzer should be fully deterministic when you start it with the same seed corpus (e.g., by fixing *the* random seed)? Currently, even without this patch I've been observing quite some variance in the coverage achieved over time. Happy to take it out, though, if this messes with the LF design principles.


You are right. After fixing frequencies to uint16_t, this can definitely be a double.

kcc added a comment.Apr 22 2020, 5:14 PM

Please take out the time-related changes for now. If anything, extra changes make the code review process quadratic.

Yes, I expect that given the same seeds corpus and a fixed random seed (-seed=<N>) libFuzzer will produce the same mutations.
There is probably at least one case where this is not actually true today: ASLR (we use PCs to index into arrays, etc),
but other than that I'd expect LF to be deterministic.

Please also replace long double with double.
I'll try to make another review PASS ASAP.

marcel updated this revision to Diff 259448.Apr 22 2020, 7:03 PM

Revision 6: Removed time-based performance boost (would render LibFuzzer non-deterministic even if the random seed is fixed with -seed=<n>). Also, sed "s/long double/double/g".

kcc added a comment.May 1 2020, 4:58 PM

Sorry for the delay. Mostly naming/style nits left.




(use upper case)




I'd like to put these into a

struct EntropicOptions {
   bool Enabled;
   size_t EntropicFeatureFrequencyThreshold;

and pass such a struct (by value) to InputCorpus CTOR.
Of course, please match the names with those in Options


I'd prefer if these names were more descriptive (ok if longer) and have "entropic" in it.


of course, make the command line parameters match

marcel marked 5 inline comments as done.May 15 2020, 6:47 AM
marcel updated this revision to Diff 264229.May 15 2020, 6:59 AM

Thanks again everyone for your time to review. Learned a lot!

Revision 7. Created struct EntropicOptions which lives in the FuzzerCorpus.h header. The EntropicOptions are passed by value from FuzzerDriver (which handles FuzzerOptions) when constructing the InputCorpus. Renamed option parameters as per KCC's suggestions. As always, formatted with clang-format.

Let me know if there is anything else, I can do.

kcc added inline comments.May 15 2020, 2:14 PM

here and below: remove 'struct'.


When running 'ninja check-fuzzer' this test fails for me:

That's weird: why does the functionality change with Entropic off?

[5/9] Running Fuzzer unit tests
FAIL: LLVMFuzzer-Unittest :: ./Fuzzer-x86_64-Test/Corpus.Distribution (48 of 55)

  • TEST 'LLVMFuzzer-Unittest :: ./Fuzzer-x86_64-Test/Corpus.Distribution' FAILED ****

Note: Google Test filter = Corpus.Distribution
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from Corpus
[ RUN ] Corpus.Distribution
/usr/local/google/home/kcc/llvm-project/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp:609: Failure
Expected: (Hist[i]) > (TriesPerUnit / N / 3), actual: 0 vs 2184
/usr/local/google/home/kcc/llvm-project/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp:609: Failure
Expected: (Hist[i]) > (TriesPerUnit / N / 3), actual: 0 vs 2184
/usr/local/google/home/kcc/llvm-project/compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp:609: Failure


Will a simpler syntax work, e.g.:

marcel marked 4 inline comments as done.May 15 2020, 9:38 PM
marcel added inline comments.

Instead of updating the corpus distribution every time it changes (e.g., FuzzerCorpus.h#L114 and FuzzerCorpus.h#L165), entropic schedules that update by setting a flag. For efficiency, only when (and just before) a new input is chosen, the corpus distribution is actually updated. I had this update in ChooseUnitToMutate which calls ChooseUnitIdxToMutate. Now moved the call to UpdateCorpusDistribution to ChooseUnitIdxToMutate (which is used by the test case).

All 40 fuzzer unit tests pass.

marcel updated this revision to Diff 264415.May 15 2020, 9:43 PM
marcel marked an inline comment as done.

Revision 8. Moved the call to UpdateCorpusDistribution from ChooseUnitToMutate to ChooseUnitIdxToMutate and removed some nits.

make -j 32 FuzzerUnitTests && \

returns with

[==========] 40 tests from 9 test cases ran. (408 ms total)
[  PASSED  ] 40 tests.
marcel updated this revision to Diff 264416.May 15 2020, 9:49 PM

Minor. Removed one line I used for debugging..

kcc accepted this revision.May 18 2020, 11:47 AM

Thanks for this work, and the effort to make the code better!

This revision is now accepted and ready to land.May 18 2020, 11:47 AM
kcc added a comment.May 18 2020, 12:08 PM

(let me land it)

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMay 19 2020, 10:56 AM
Herald added a subscriber: Restricted Project. · View Herald Transcript