Optimize fuzzer value generation to prevent duplicate values and improve coverage

[wirew0lf]

Component

Forge

Describe the feature you would like

After doing some testing with the basic fuzzer I've found out the fuzzer generates lots of duplicate values.

In order to test this I created the following test which generates a .csv file with both forge fuzzer ouput and bound function ouput:

function testGenerateUint(uint a) public {
  uint b = bound(a, 0, 1_000_000*10e18);
  
  string memory path = "./results/FuzzUintGenerationResults.csv"; 
  string memory line = string.concat(string.concat(vm.toString(a), ","), vm.toString(b));
  vm.writeLine(path, line);
}

Then post-processed this information and this are the results:

Out of 256 runs, 101 of them are duplicate runs with a value already tested, I've also tried with other type of value such as bytes32 and obtained similar results.

For example, the max value of uint256 was run 33 times, althoughI believe the number of duplicate runs may decrease in functions with more than one parameter. Focusing on numbers near 0 and near the max value for uint256 might be useful to trigger edge cases however, the fuzzer is not generating much values in mid ranges. Also, given that most deApps use 18 decimals I think it would be better to focus more on generating values in a range of for example, between 1e17 and 100_000_000e18.

I think a better approach could be:

• 20% of values generated should be values near 0 and max uint256 including both, to trigger edge cases.
• 60% of values between 1e17 and 1e25.
• The remaining 20% throughout the whole uint256 range.

I could also prepare a pull request if any of the more senior contributors agrees this should be addressed.

Additional context

No response

[KholdStare]

Did not know that this was the case. Perhaps the random generation is biased (which it should be), but each draw is independent (it shouldn't be). Probably need some state per fuzzed input to know whether an extreme value was already tried.

How does the "OG" Quickcheck from Haskell draw random values?

[mds1]

IIRC the cause is due to the fact that the edge bias strategy is chosen too frequently relative to the number of values the edge bias strategy can actually generate. More info in #3521 with my proposed fix in #3521 (comment)

Draws are independent like you said, changing that is also a possible solution but requires tracking more data which increases memory usage and incurs a performance penalty, especially as number of fuzz runs grows, which is why my proposed solution avoids that by leveraging the dictionary

[wirew0lf]

I'm closing the issue, let's keep the discussion on #3521