Vision: Random call generator for fuzz-testing

[kianenigma]

Some notes about the fuzzing outcome: As you see in the code, I randomly generate calls that may or may not be valid and bombard the pallet with these calls, and every so often I execute the entire set of sanity checks that are defined in the pallet.

We could create a tool which generates a set of calls from the metadata of a pallet. Could even be done in PolkadotJS, as general fuzzy testing framework.

Originally posted by @ggwpez in paritytech/substrate#12002 (comment)

[kianenigma]

another alternative would be to use https://docs.rs/arbitrary/latest/arbitrary/. If this works out, it plugs nicely into the rest of the Rust ecosystem.

[ggwpez]

Yea, using a fuzzy library with test-case minimization, auto retry and all the extras would be smart.

[shawntabrizi]

The problem is that a lot of the pallet calls only make sense when set up with other calls. For example, the steps of a treasury bounty or democracy proposal.

Additionally, i question whether a spectrum of inputs would reveal anything that just looking at the extremes would not reveal. But yeah, if it is easy to implement, would be interested to see. I think SR Labs already does this quite a bit for us when they audit code.

[ggwpez]

The problem is that a lot of the pallet calls only make sense when set up with other calls. For example, the steps of a treasury bounty or democracy proposal.

I think @kianenigma exclusively focused on sanity checks.
But yea, we need some kind of setup and a set of invariants which are then checked each time.

Additionally, i question whether a spectrum of inputs would reveal anything that just looking at the extremes would not reveal. But yeah, if it is easy to implement, would be interested to see. I think SR Labs already does this quite a bit for us when they audit code.

Probably makes the most sense when it interacts with multiple pallets.
Stuff like reference counting, or reserved/locked balance, I think there are a lot of spots where stuff can go wrong, especially when used from different pallets.

[hieronx]

I think this is similar to invariant testing as implemented in Foundry, for Solidity: foundry-rs/foundry#1572 (which was inspired by dapptools: https://github.com/dapphub/dapptools/blob/master/src/dapp/README.md#invariant-testing).

I’ve also discussed this a bit with SR Labs recently: they currently are indeed fuzzing calls and checking basic invariants (e.g. “does not panic”), but this can probably be made significantly more effective by:

• Making the fuzzing more specific by encoding specific setup calls and target methods.
• Adding invariants specific to a particular pallet rather than just checking for panics.

I definitely agree that this is most useful when interacting with multiple pallets. I've been playing around with the idea of using https://github.com/centrifuge/fudge to a setup a chain, specify a list of calls to make, including passing time (since a lot of our logic depends on time, e.g. debt accrual), and then using a fuzzer (or maybe https://github.com/srlabs/ziggy to be able to use different fuzzers) to generate different states and try to break any of the specified invariants.

As a side note: this is an especially interesting read about the kinds of issues that this can find: https://hackmd.io/@SaferMaker/DAICertoraSurprise. This in particular used Certora's FV toolkit, but the same could probably be found using fuzzing with invariant testing.

[bkchr]

If we would use some learning/AI based fuzzer (not sure what the correct naming is here), could we not use this to let it start with random bytes? Start from zero it let it walk through creating and applying transactions. Not sure there would be any useful output coming from this. However, we could try and see :D

[kianenigma]

The problem is that a lot of the pallet calls only make sense when set up with other calls. For example, the steps of a treasury bounty or democracy proposal.

I don't think this is a showstopper. If you generate enough random calls, with enough iteration, any setup that you can think of should be created. Perhaps you need to call on_inititalize in between as well. I do a similar thing for the pools fuzz testing merged recently, and it does eventually lead to all possible outcomes (at least based on events, I can say we hit a lot of the corners).

Additionally, i question whether a spectrum of inputs would reveal anything that just looking at the extremes would not reveal.

I think this flies in the face of why fuzzing is generally a thing in comp. engineering. The argument is that a lot of edge cases will actually be missed by a human, but a fuzzer can catch. Hard to tell, but I am a fan of not relying on human detected edge cases only.

We can also apply the same logic to the whole runtime and apply random RuntimeCalls.

Indeed, all of this makes little sense if you blindly send these calls. It makes a lot more sense if each pallet would have a set of clear "invariants" (what should be coded as fn try_state henceforth). Then, it is a pretty good testing scenario: regardless of what garbage call you submit, the invariants must be met.

[kianenigma]

Adding invariants specific to a particular pallet rather than just checking for panics.

I hope we standardize the try_state or something similar soon, and do actual state testing. Checking for panics only is, in my opinion, even worse, because it actually gives the false sense that things are being checked, but in reality are, in my opinion, very meaningless. A runtime can be extremely faulty but not generate any panics.

[Polkadot-Forum]

This issue has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/testing-complext-frame-pallets-discussion-tools/356/1

[louismerlin]

Here is the code SRLabs has been using for the past couple of years to fuzz-test substrate runtimes.

Parity is already aware, but posting here for reference.

https://github.com/srlabs/substrate-runtime-fuzzer

[kianenigma]

@louismerlin how fast can this fuzzer reach calls that are decode-able?

For example, if you run the fuzzer for 1 day, what percentage of the inputs fail in actual dispatch and not in decoding?

If this is fast enough, it is good news.