feat(forge): Invariant Testing v2 #1572

joshieDo · 2022-05-09T22:18:47Z

Alright, opening for review since it's growing too much. Let's iterate from here.

Summary:

Functions should start with invariant. eg: invariant_neverFalse()
Invariants have the following parameters on the config file

    /// The number of runs that must execute for each invariant test group.
    pub invariant_runs: u32,
    /// The number of calls executed to attempt to break invariants in one run.
    pub invariant_depth: u32,
    /// Fails the invariant fuzzing if a reversion occurs
    pub invariant_fail_on_revert: bool,
    /// Allows randomly overriding an external call when running invariant tests
    pub invariant_call_override: bool,

An invariant with depth of 15 and 256 invariant_runs will have a total of 3840 calls (excluding the invariant checks), if everything succeeds.
We currently fuzz the sender_address, target_address and calldata.
3.1 This data is generated by different proptest::TestRunner.
3.2 The data is influenced by a dictionary that is filled with new values throughout the runs.
Invariants are checked right after setUp() and before anything is called.
After each call we:
4.1 Collect stack/memory data to add to the fuzzing dictionary.
4.2 Collect newly created contracts and add them as potential target_address.
4.3 Make calls to the test contract invariant* functions. If any fails, we exit the run.
4.4 If all invariants have been broken, then exit asap.

Filtering

To better bound the test space there are certain filters that can be used:

targetContracts(): address[]: a contract address will be chosen from this list.
targetSenders(): address[]: 80% chance that a contract address will be chosen from this list.
targetSelectors(): (address, bytes4[])[]: adds to targetContracts list, and only the selectors provided will be called.
excludeContracts(): address[]: contract addresses from the setup process which are to be excluded from being targeted.

Unsafe/External call overriding

invariant_call_override allows for an external call to be overridden to simulate unsafe calls. This feature is false by default, since it requires some work, although it's already functional. (eg. testdata/fuzz/invariant/InvariantReentrancy.t.sol).
More: #1572 (comment)

Examples

testdata/fuzz/invariant/
├── InvariantInnerContract.t.sol
├── InvariantReentrancy.t.sol
├── InvariantTest1.t.sol
└── target
    ├── ExcludeContracts.t.sol
    ├── TargetContracts.t.sol
    ├── TargetSelectors.t.sol
    └── TargetSenders.t.sol

1 directory, 7 files

Follow-up (in no particular order)

old summary

However, since the repo diverged quite a bit from the `sputnik` times, I wanted to get some potential feedback, since I'm still getting acquainted with the fuzzing modules, and I'm probably missing some things and/or design choices.

Missing

forgetest!()
clean-up
...

Summary

invariant_depth
targetContracts(). if not found, then just fuzz every contract created at setUp
targetSenders(). if not found, then just fuzz the sender
excludeContracts()
targetSelectors()
invariant_fail_on_revert
identify created contracts and fuzz them too

Future/Now?

random msg.value

ref #849

mds1

Awesomeee thank you @joshieDo! Only skimmed the code / haven't tested it yet but left a few thoughts.

Also, do we check the invariant during the post-setUp state before executing any additional calls? This was mentioned in #69 because "sometimes it doesn’t hold off the bat but then that changes after txs or if all the txs revert then the invariant will show as passed when it may have totally failed if ever called"

mds1 · 2022-05-09T22:52:45Z

evm/src/invariant_fuzz.rs

+}
+
+pub fn invariant_strat(
+    depth: usize,


Let's make sure to expose the depth in the config. Perhaps invariant_runs and invariant_depth, so you can control it separately from fuzz_runs?

Yeah I agree with this, we should have a param separate from fuzz_runs

mds1 · 2022-05-09T22:56:35Z

evm/src/invariant_fuzz.rs

+        .boxed()
+}
+
+fn select_random_contract(


In dapptools, the way this worked was:

hevm will invoke any state mutating function from all addresses returned by a call to targetContracts(), if such a function exists in the testing contracts. If no such method exists, it will invoke methods from any non-testing contract available after the setUp() function has been run, checking the invariant* after each run.

I think currently all test and non-test contracts are included by default, but I like hevm's approach and would suggest sticking with that (open to alternative ideas though)

it will invoke methods from any non-testing contract available after the setUp() function has been run, checking the invariant* after each run.

Unless I misunderstood something, this is what is happening right now. Any non testing contract created during the setUp function is used.

all addresses returned by a call to targetContracts()

As a way to filter-out contracts we don't want to fuzz? Because if it includes addresses from a forked state, then it requires the use of etherscan

edit: added targetContracts() as a filter-out mechanism. etherscan can probably be added in the future

Unless I misunderstood something, this is what is happening right now. Any non testing contract created during the setUp function is used.

Ah got it, ok perfect 👌

As a way to filter-out contracts we don't want to fuzz? Because if it includes addresses from a forked state, then it requires the use of etherscan

edit: added targetContracts() as a filter-out mechanism. etherscan can probably be added in the future

Yep exactly! Sometimes considering all non-test contracts deployed during setUp is too broad and you want to limit it. That sounds great though. Lack of etherscan support seems ok because you can workaround it by adding a local contract that does something like the below, and including that contract in your targetContracts() array.

contract DaiHarness { function transfer(address from, address to, uint256 amount) public { vm.prank(from); dai.transfer(to, amount); } }

mds1 · 2022-05-09T23:06:05Z

evm/src/invariant_fuzz.rs

+    // We need to compose all the strategies generated for each parameter in all
+    // possible combinations
+    let strats = func.inputs.iter().map(|input| fuzz_param(&input.kind)).collect::<Vec<_>>();


@brockelmore Have we talked about additional invariant-specific strategies for generating calldata? I think it'd be interesting to add:

All stack/memory values, and/or

The output of calling view methods which have no inputs

to the dict for the lifetime of one invariant run, then remove them for the subsequent run to avoid flooding the dict. Maybe a separate issue/PR though.

mds1 · 2022-05-09T23:11:03Z

evm/src/invariant_fuzz.rs

+    }
+
+    /// Fuzzes the provided function, assuming it is available at the contract at `address`
+    /// If `should_fail` is set to `true`, then it will stop only when there's a success


This sounds like it refers to something like testFail, but we probably don't need to support invariantFail style tests—is there a use case for that?

mds1 · 2022-05-09T23:13:16Z

evm/src/invariant_fuzz.rs

+        let mid = self.cases.len() / 2;
+        self.cases.get(mid).map(|c| c.gas).unwrap_or_default()


Seems this doesn't handle when cases has an even length

mds1 · 2022-05-09T23:17:28Z

evm/src/invariant_fuzz.rs

+                            stipend,
+                        });
+                    } else {
+                        // call failed, continue on


Say the 3rd call in a sequence reverts (i.e. the fuzz call itself reverts, not a failed invariant), do we generate a new call or move on to the fourth call in the sequence? Looks like the latter, so wondering if we should have a flag to instead generate a new call, to help mitigate situations where many calls in the sequence revert?

For reference, relevant portion of dapptools docs:

Note that a revert in any of the randomly generated call will not trigger a test failure. The goal of invariant tests is to find a state change that results in a violation of the assertions defined in the body of the test method, and since reverts do not result in a state change, they can be safely ignored. Reverts within the body of the invariant* test method will however still cause a test failure.

i wonder if it really makes a difference tho, since it's basically a random walk ? at what Nth would you stop generating new calls?
ideally you would just increase the depth to counteract that, or better, improve your setUp with good targetContracts and targetSenders

although having a report on the number of reverted calls might be interesting, so the user can adjust his settings accordingly.

although having a report on the number of reverted calls might be interesting, so the user can adjust his settings accordingly.

Good points, this seems like a good compromise. Have the option to report min/max/mean/median number of reverts.

Another idea is to have a targetSelectors() method which returns a tuple of (address, bytes4[])[] so you can have fine grained control over the allowed methods (echidna has similar functionality where you can allow/block function selectors).

Ooooh I like the idea of targetSelectors()

brockelmore

few things

brockelmore · 2022-05-10T22:51:29Z

evm/src/invariant_fuzz.rs

+pub fn fuzz_calldata(addr: Address, func: Function) -> impl Strategy<Value = (Address, Bytes)> {
+    // We need to compose all the strategies generated for each parameter in all
+    // possible combinations
+    let strats = func.inputs.iter().map(|input| fuzz_param(&input.kind)).collect::<Vec<_>>();


Use fuzz_param_from_state and pass in state dictionary here, and union two strategies strategies with state weight and random weight like we do in normal fuzz tests

brockelmore · 2022-05-10T22:54:38Z

testdata/fuzz/InvariantFuzz.t.sol

@@ -0,0 +1,60 @@
+// SPDX-License-Identifier: Unlicense
+pragma solidity >=0.8.0;


Add this as a test:

contract InvariantBreaker { bool public flag0 = true; bool public flag1 = true; function set0(int val) public returns (bool){ if (val % 100 == 0) flag0 = false; return flag0; } function set1(int val) public returns (bool){ if (val % 10 == 0 && !flag0) flag1 = false; return flag1; } } contract InvariantTest is Test { InvariantBreaker inv; function setUp() public { inv = new InvariantBreaker(); } function invariant_neverFalse() public { require(inv.flag1()); } }

Showcases the need to do multi-tx + specific inputs

A stress test I dont know that we will solve:

contract Foo { int256 private x; int256 private y; constructor () public { x = 0; y = 0; } function Bar() public view returns (int256) { if (x == 42) { assert(false); return 1; } return 0; } function SetY(int256 ny) public { y = ny; } function IncX() public { x++; } function CopyY() public { x = y; } } contract ContractTest is Test { Foo foo; function setUp() public { foo = new Foo(); } function invariant_canBar() public { (bool success, ) = address(foo).call(abi.encodePacked(foo.Bar.selector)); require(success); } }

brockelmore · 2022-05-10T23:00:30Z

forge/src/runner.rs

+                                    ));
+                                    break
+                                } else {
+                                    // todo should we show


I lean towards no but argument could definitely be made to show calls to invariants that pass. I think we should not include them right now based on my previous experience showing them and it being a bit confusing/crowded

brockelmore · 2022-05-10T23:02:46Z

evm/src/invariant_fuzz.rs

+                        Address::from_slice(
+                            &hex::decode("000000000000000000636F6e736F6c652e6c6f67").unwrap(),
+                        ) &&
+                    (selected.is_empty() || selected.contains(addr))


nice. glad this is optional. I hate dapptool's ux there, but agree its necessary

brockelmore · 2022-05-10T23:05:22Z

evm/src/invariant_fuzz.rs

+    }
+}
+
+pub fn invariant_strat(


lets move all strategy related things to its own file in foundry/evm/src/fuzz/strategies

brockelmore · 2022-05-10T23:05:51Z

evm/src/invariant_fuzz.rs

+    let senders_: Vec<Address> = senders.clone();
+
+    if !senders.is_empty() {
+        // todo should we do an union ? 80% selected 15% random + 0x0 address by default


yes should do union

evm/src/invariant_fuzz.rs

brockelmore · 2022-05-10T23:13:17Z

also: update identified contracts after each call (instead of just after setup) < this would be nice to have. In general i think using targetContracts & targetSenders is mostly an antipattern. We should likely do unions for most of these with "random" from state/true random

mds1 · 2022-05-11T01:29:06Z

In general i think using targetContracts & targetSenders is mostly an antipattern

Just chatted with @brockelmore about this and he had a good point that you're more likely to forget to include a contract in the targetContracts list, when often the reason to use it is there's just a handful you want to exclude from being called. So I think we should also add support for a function excludeContracts() external returns (address[]) as well.

mds1 · 2022-08-02T15:16:23Z

We should make sure deterministic invariant testing is supported using #1658

joshieDo · 2022-08-02T15:30:30Z

Yeah, should be there with the recent merge. I also added it to the invariant runner. But they're sharing... is that fine or would you wish a different var?

mds1 · 2022-08-02T15:37:22Z

Sharing seems fine to keep it simple, I can't really think of a use case where you'd need them to be separate.

One oddity is we use fuzz_ and invariant_ prefixes in the config to namespace things (which I like), so having it called fuzz_seed is a bit misleading. I'd propose either calling it rng_seed OR splitting into both fuzz_seed and invariant_seed just to keep the config separation logical

mattsse

great, only a couple of smol nits style nits.

even though lot of the lower-level stuff is a bit verbose, just because of the evm/test API, this is now readable enough to make sense of it

very nice

mattsse · 2022-08-02T15:55:12Z

evm/src/fuzz/invariant/mod.rs

+};
+mod call_override;
+pub use call_override::{set_up_inner_replay, RandomCallGenerator};
+


Suggested change

evm/src/fuzz/strategies/invariants.rs

gakonst · 2022-08-02T18:10:34Z

@joshieDo whenever you feel good with this we can ship it. let's also open an issue on the book w/ the things we want to track? there's a lot to process here, the targetContracts pattern, the patterns from @lucas-manuel's https://github.com/maple-labs/revenue-distribution-token/tree/e0eca03c2ff05c36000a097de678543d7234f7cc/contracts/test tests etc.

joshieDo · 2022-08-03T11:11:48Z

good to go!

gakonst · 2022-08-03T17:14:30Z

@joshieDo just the merge conflicts remaining and good to go

onbjerg · 2022-08-03T17:18:03Z

evm/src/fuzz/strategies/state.rs

 /// A set of arbitrary 32 byte data from the VM used to generate values for the strategy.
 ///
 /// Wrapped in a shareable container.
-pub type EvmFuzzState = Rc<RefCell<HashSet<[u8; 32]>>>;
+pub type EvmFuzzState = Arc<RwLock<HashSet<[u8; 32]>>>;


Just noting here for merge conflict that it is important that this becomes a BTreeSet, otherwise the fuzzer is not deterministic when you give it a seed

joshieDo · 2022-08-03T18:54:58Z

Test failure seems unrelated? Also happening on master

onbjerg · 2022-08-03T19:57:09Z

Yeah, unrelated

mattsse · 2022-08-04T11:57:14Z

merge whenever!

gakonst · 2022-08-04T15:27:16Z

lfg

* init * invariant testing kinda working * updates * fmt * wip * wip * wip * check if there is a fuzzer for invariants * less clones * add support for targetContracts on invariant tests * move load_contracts * add TestOptions and invariant_depth as param * pass TestOptions on fuzz tests * fuzz senders as well * light cleanup * make counterexample list concise * show reverts on invariants test reports * add excludeContracts() * refactor address fetching * move invariant to fuzz module * fuzz calldata from state changes * move block into assert_invariances * add union between selected senders and random * fix sender on get_addresses * wip * add targetSelectors * add fail_on_revert for invariant tests * dont stop on the first invariant failure on each case * create a new strategy tree if a new contract is created * only collect contract addresses from NewlyCreated * display contract and sig on displaying counter example * add documentation * generate the sequence lazily instead * wip * refactor invariants into multi file module * refactor get_addresses to get_list * add test cases * add reentrancy_strat * set reentrancy target as an union with random * merge master * make call_override a flag * add inspector_config() and inspector_config_mut() * always collect data, even without override set * docs * more docs * more docs * remove unnecessary changeset clone & docs * refactor +prepare_fuzzing * more explanations and better var names * replace TestKindGas for a more generic TestKindReport * add docs to strategies * smol fixes * format failure sequence * pass TestOptions instead of fuzzer to multicontractrunner * small fixes * make counterexample an enum * add InvariantFailures * turn add_function into get_function * improve error report on assert_invariants * simplify refs * only override_call_strat needs to be sboxed, revert others * fix invariant test regression * fix: set_replay after setting the last_sequence * fix: test_contract address comparison on call gen * check invariants before calling anything * improve doc on invariant_call_override * remove unused error map from testrunner * reset executor instead of db * add type alias InvariantPreparation * move InvariantExecutor into the same file * add return status * small refactor * const instead of static * merge fixes: backend + testoptions * use iterator for functions * FuzzRunIdentifiedContracts now uses Mutex * from_utf8_lossy instead of unsafe unchecked * use Mutex for runner of RandomCallGenerator * move RandomCallGenerator to its own module * write to fmt * small refactor: error.replay * remove newlines * add remaining is_invariant_test Co-authored-by: Brock <brock.elmore@gmail.com>

brockelmore and others added 9 commits February 12, 2022 19:22

init

2ef1359

invariant testing kinda working

929d518

Merge remote-tracking branch 'origin/master' into brock/invariant

6c3eb1f

updates

e092dda

fmt

72ab802

Merge remote-tracking branch 'origin/master' into brock/invariant

89e1e73

wip

aad4e55

wip

7b88654

wip

cc41bbd

joshieDo changed the base branch from brock/invariant to master May 9, 2022 22:20

check if there is a fuzzer for invariants

814b61a

mds1 reviewed May 9, 2022

View reviewed changes

joshieDo added 5 commits May 10, 2022 11:18

less clones

803cb66

add support for targetContracts on invariant tests

2363456

move load_contracts

850258c

add TestOptions and invariant_depth as param

64e0db3

pass TestOptions on fuzz tests

aa242c8

onbjerg added the T-feature Type: feature label May 10, 2022

joshieDo added 3 commits May 10, 2022 15:49

fuzz senders as well

81347cd

light cleanup

4315d33

make counterexample list concise

b838233

joshieDo force-pushed the joshie/invariant branch from 5d2dab0 to b838233 Compare May 10, 2022 15:25

gakonst mentioned this pull request May 10, 2022

feat(forge): invariant tests #849

Closed

6 tasks

brockelmore requested changes May 10, 2022

View reviewed changes

mds1 mentioned this pull request May 11, 2022

feat: test for reentrancy in invariant tests #1578

Open

joshieDo added 3 commits May 11, 2022 11:42

show reverts on invariants test reports

dbc8dc5

add excludeContracts()

ff516c8

refactor address fetching

7551231

write to fmt

e2c34ec

small refactor: error.replay

09d9e0e

joshieDo requested a review from mattsse August 2, 2022 15:36

mattsse requested changes Aug 2, 2022

View reviewed changes

mattsse approved these changes Aug 2, 2022

View reviewed changes

remove newlines

56ba203

gakonst mentioned this pull request Aug 3, 2022

refactor: use TestFunctionExt for string #2586

Merged

gakonst mentioned this pull request Aug 3, 2022

Document invariant testing + patterns foundry-rs/book#497

Closed

onbjerg reviewed Aug 3, 2022

View reviewed changes

joshieDo added 2 commits August 3, 2022 19:17

Merge branch 'master' into joshie/invariant

fdbf2ad

add remaining is_invariant_test

e4b1c90

Merge branch 'master' into joshie/invariant

d396c2d

mattsse approved these changes Aug 4, 2022

View reviewed changes

onbjerg approved these changes Aug 4, 2022

View reviewed changes

gakonst merged commit 262bdf2 into foundry-rs:master Aug 4, 2022

varunsrin mentioned this pull request Aug 8, 2022

testing: invariants farcasterxyz/contracts#32

Open

rkrasiuk mentioned this pull request Aug 22, 2022

feat(forge): fuzz & invariant config #2882

Merged

hieronx mentioned this pull request Sep 12, 2022

Vision: Random call generator for fuzz-testing paritytech/polkadot-sdk#251

Open

PaulRBerg mentioned this pull request Jan 5, 2023

Write invariant tests sablier-labs/v2-core#244

Closed

		let mid = self.cases.len() / 2;
		self.cases.get(mid).map(\|c\| c.gas).unwrap_or_default()

		@@ -0,0 +1,60 @@
		// SPDX-License-Identifier: Unlicense
		pragma solidity >=0.8.0;

feat(forge): Invariant Testing v2 #1572

feat(forge): Invariant Testing v2 #1572

Conversation

joshieDo commented May 9, 2022 • edited

Summary:

Filtering

Unsafe/External call overriding

Examples

Follow-up (in no particular order)

mds1 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

joshieDo May 10, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

joshieDo May 10, 2022 • edited

Choose a reason for hiding this comment

mds1 May 10, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

brockelmore left a comment

Choose a reason for hiding this comment

brockelmore May 10, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

brockelmore commented May 10, 2022

mds1 commented May 11, 2022

mds1 commented Aug 2, 2022

joshieDo commented Aug 2, 2022

mds1 commented Aug 2, 2022 • edited

mattsse left a comment • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

gakonst commented Aug 2, 2022 • edited

joshieDo commented Aug 3, 2022

gakonst commented Aug 3, 2022

Choose a reason for hiding this comment

joshieDo commented Aug 3, 2022

onbjerg commented Aug 3, 2022

mattsse commented Aug 4, 2022

gakonst commented Aug 4, 2022

joshieDo commented May 9, 2022 •

edited

joshieDo May 10, 2022 •

edited

joshieDo May 10, 2022 •

edited

mds1 May 10, 2022 •

edited

brockelmore May 10, 2022 •

edited

mds1 commented Aug 2, 2022 •

edited

mattsse left a comment •

edited

gakonst commented Aug 2, 2022 •

edited