Assumptions for fuzzed arrays

[PaulRBerg]

It is possible to fuzz arrays like this:

function testFuzzArr(uint256[] memory arr) external {
    // ...
}

But I wonder if it is possible to have some advanced vm.assume assumptions for fuzzed arrays?

e.g. each array element should not be greater than X, or the array elements should be ordered in ascending order.

I guess I could iterate over the array items and do a vm.assume on each, but that would quickly get me over the max global rejects threshold.

Does Foundry offer any support for this use case?

[mds1]

each array element should not be greater than X,

This should be easy to write a helper method for, but you should use bound instead of vm.assume for performance/reject reasons

or the array elements should be ordered in ascending order.

This would be a bad assume condition, as the odds of getting a sorted array are small, especially as array length increases. For this, you should just sort the received array

Also in general, I don't think the uint array fuzz strategy is as good as the regular uint strategy, you can see the arrays don't use UintStrategy. Probably something that should be improved

foundry/evm/src/fuzz/strategies/param.rs

Lines 25 to 34 in b78509f

	ParamType::Uint(n) => {
	super::UintStrategy::new(*n, vec![]).prop_map(|x| x.into_token()).boxed()
	}
	ParamType::Bool => any::<bool>().prop_map(|x| x.into_token()).boxed(),
	ParamType::String => any::<Vec<u8>>()
	.prop_map(|x| Token::String(unsafe { std::str::from_utf8_unchecked(&x).to_string() }))
	.boxed(),
	ParamType::Array(param) => proptest::collection::vec(fuzz_param(param), 0..MAX_ARRAY_LEN)
	.prop_map(Token::Array)
	.boxed(),

[PaulRBerg]

Thanks @mds1, your answer is helpful.

you should use bound instead of vm.assume for performance/reject reasons

Right, I forgot about bound.

you should just sort the received array

Yeah, I thought about this, but I was worried about performance, especially in CI where I have 10,000 runs. I will report my findings here in case the performance is bad.

you can see the arrays don't use UintStrategy

Are you sure they don't? It seems to me that the implementation calls fuzz_param recursively so, in case of an uint[] array, the UintStrategy would eventually be picked up. But maybe I'm missing something.

[mds1]

Are you sure they don't? It seems to me that the implementation calls fuzz_param recursively so, in case of an uint[] array, the UintStrategy would eventually be picked up. But maybe I'm missing something.

Ah yes you are totally right here. I misremembered and was in a rush when I tried verifying before commenting—thanks for confirming!

[PaulRBerg]

To follow up on this topic .. I just bumped into another nasty issue. Consider the following use case:

function testBar(uint256[] memory a, uint256[] memory b, uint256[] memory c) external {
    // ...
}

Where you want:

• All arrays to have a non-zero length
• All arrays to have equal length

The naive way of enforcing this would be to use vm.assume like this:

vm.assume(a.length != 0);
vm.assume(a.length == b.length && a.length == c.length);

However, it doesn't take long to notice that this is not a good approach, because of the too many rejects issue. I got this error as soon as I implemented the assumptions above:

[FAIL. Reason: The vm.assume cheatcode rejected too many inputs (100000 allowed)]

I tried increasing the max_test_rejects property to 1 million. Same story, but longer wait time until hitting an error.

One potential workaround is to fuzz the length of the array and then generate the array data based on some seed .. but this is not trivial and it involves writing a mini-fuzzer, basically.

Another potential solution is to create one large array, and then create the three sub-arrays based off that large array. This does have the downside of (i) not allowing more than 256 / 3 = ~85 element arrays (256 is the maximum array length used by the fuzzer) and (ii) having to manually convert the types for the sub-arrays, if they are meant to have different types.

@mds1, can you think of any other solution? Sorry to ping you but I'm stuck.

[mds1]

One potential workaround is to fuzz the length of the array and then generate the array data based on some seed .. but this is not trivial and it involves writing a mini-fuzzer, basically.

Also not a fan because then you lose the dictionary benefits

Another potential solution is to create one large array, and then create the three sub-arrays based off that large array. This does have the downside of (i) not allowing more than 256 / 3 = ~85 element arrays (256 is the maximum array length used by the fuzzer) and (ii) having to manually convert the types for the sub-arrays, if they are meant to have different types.

This seems like good approach. If the max length of 256 is too limiting you can pull that out into a config option (prob need two, one for [fuzz] and another for [invariant], maybe call it max_array_length

Converting to types can of course be done natively in solidity, but may be easier via cheats with e.g. vm.toAddress(vm.toString(myUint)) (this should work, worth sanity checking though). The foundry fuzzer doesn't distinguish types in the dictionary (it treats everything as just bytes) which helps you in this case

---

One other idea is to truncate the longer arrays so they are the size of the shortest array and just keep the assume check that each has a non-zero length. A similar approach with looser assumes is take elements from the longest array and move them to the shortest until all arrays are the same length (and maybe you end up discarding an element or two).

Arrays in solidity are a pain, so this may be a good use case for @brockelmore's memmove

[PaulRBerg]

Thanks again Matt for sharing your thoughts on the discussions that I open. A lot of food for thought here.

If the max length of 256 is too limiting you can pull that out into a config option

You mean implement it in Foundry and open a PR, right? I don't see this option available today.

vm.toAddress(vm.toString(myUint))

Same question here, the toAddress cheatcode doesn't exist now.

One other idea is to truncate the longer arrays so they are the size of the shortest array and just keep the assume check that each has a non-zero length

Unfortunately this is difficult to do in my case because of reasons having to do with the business logic of the protocol.

[mds1]

You mean implement it in Foundry and open a PR, right? I don't see this option available today.

Yes correct!

Same question here, the toAddress cheatcode doesn't exist now.

Sorry got the name wrong here, it's parseAddress. Basically there's one set of cheats to convert types to string, and another set to convert strings to types: https://github.com/foundry-rs/forge-std/blob/83c6e5b7bbbc865a83ed636ad32a8b7f2fc9185e/src/Vm.sol#L140-L153

[PaulRBerg]

Oh, right! I wrote the names args for parseAddress 😅

Thanks.

[PaulRBerg]

Following up here for posterity - I ended up doing something more creative.

1. Set a predefined value for the 1st element.
2. Use your library @mds1 solidity-generators to generate a linearly spaced array.
3. Bound each element.

Code snippet here:

https://gist.github.com/PaulRBerg/23bb1e7b04a43aa5376974d9f7a6aa1c