fix: improve bound so there's no shifting of input values when they're within range

[mds1]

Problem

• Whenever there's an SSTORE or SLOAD, and whenever there's a PUSH opcode, those values are added to a dictionary. If dict weight is 40% then 40% of values are from the dict and 60% are random
• So let's say the value 100 is in storage and gets added to the dict. We want the fuzzer to pick 100 from the dict and use it as an input. And maybe I need the input to no bigger than 1000.
• If the minimum value in bound we had was zero: no problem—any x values < 1000 are unchanged (because 5 % 1000 = 5)
• But let's say I don't want the values 0-74 as inputs, because maybe they result in zero shares being minted which causes a revert. So you want the fuzzer to generate 74–1000 as inputs, i.e. bound(x, 75, 1000)
• Now you have a bias, because inputs are shifted by the min to get them in range

Potential solution

If x is within the range of the bound limits, do not shift the value. Basically add something like if (x >= min && x <= max) return x;. Mainly just need to make sure this doesn't introduce some weird bias/distribution, but I think it's ok and a good solution

[nventuro]

The proposed solution suffices for arbitrary values, but it won't help with edge conditions, particularly on the upper range. E.g. if I bound an 8 bit value to [10, 20], input value 255 is mapped to 10 + 255 % (20 - 10 + 1) = 12, which is not a useful value, and we'll end up relying on being lucky to test the actual upper bound.

[mds1]

Yep that's true, this mainly fixes dict limitations and ensures that stays useful, but doesn't help with edge values. One thing implicit in #1350 (which I'll add a comment for) is that it would also require a change to the edge-biasing strategy to factor in the user-provided upper limit

[0xPhaze]

This has also been a pain point in many of my tests. In particular, I often find myself writing general fuzz unit-tests (that use bound) and compose these in other tests. Then when dealing with bound, I always need to take the shift into account which gets messy.

This is an invariant that should hold imo:

bound(x, a, b) == bound(bound(x, a, b), a, b)

Some other things to note about bound:

• generally the upper limit is excluded in ranges (though it could be an issue when trying to get the full range, i.e. [0, 2^256-1]; then again - you wouldn't really need bound here)
• the logs get annoying when bound is used in non-fuzz tests (e.g. when composing fuzz-tests in other tests) - a cheap (but non-robust) workaround could be to conditionally log depending on msg.data.length

[mds1]

Just pushed a commit to #184 that should improve bound, @nventuro @0xPhaze lmk what you think: 16f109d

generally the upper limit is excluded in ranges (though it could be an issue when trying to get the full range, i.e. [0, 2^256-1]; then again - you wouldn't really need bound here)

This is true, though you could also have a range like [2^128, 2^256]. Using an inclusive range makes bounds easier to work with IMO, even though it's not necessary common for slice/range type methods

the logs get annoying when bound is used in non-fuzz tests (e.g. when composing fuzz-tests in other tests) - a cheap (but non-robust) workaround could be to conditionally log depending on msg.data.length

You're saying when you call a fuzz test from within a concrete (non-fuzz) test, right? i.e. adding a quietBound like method wouldn't help IIUC. If so that makes sense, I think your approach should work, but let's track in a separate issue

[mds1]

Ah actually I don't think I'm handling the size increment correctly in that comment, think that needs to be moved up a few lines. Will come back to this later to fix that

Edit: nevermind, it's currently correct actually. Because assertEq(bound(2, 50, 51), 50); passes and that makes sense. If you move the size++ line the expetecd return value becomes 52 which is of course wrong

[0xPhaze]

Looks good to me.

You're saying when you call a fuzz test from within a concrete (non-fuzz) test, right? i.e. adding a quietBound like method wouldn't help IIUC. If so that makes sense, I think your approach should work, but let's track in a separate issue

Yes, having the logs is very helpful for failing fuzz tests, but makes it ugly to combine with extended unit-tests / user-journey tests. Though you're right, it should be tracked in a separate issue.

[mds1]

Closed by #184