Fuzzing the entire runtime

[matklad]

[OKR 2021Q4] At a high level, our runtime is a pure function which takes some state, a bunch of actions, interprets those actions and returns a new state. We also care a lot about runtime being correct even in the phase of adversary inputs. So it behooves us to implement fuzzing of the runtime. This article (and it's bibliography) give a good overview of state of the art fuzzing in Rust: https://fitzgeraldnick.com/2020/08/24/writing-a-test-case-generator.html.

The TL;DR is that the best approach is structured, coverage guided fuzzing. We use something like libfuzzer to generate random inputs &[u8], then we use this input as a seed to generate a random sequence of valid actions, then we feed this input into the runtime. The fuzzer then observes code coverage as the runtime executes the input, and uses that info to generate better seeds to cover more of the branches, and to minimize failures for free.

Practically, that means that we should:

• define a data structure describing a series of inputs to the runtime
• implement https://docs.rs/arbitrary/1.0.1/arbitrary/trait.Arbitrary.html for this data structure. Care must be taken to generate reasonably well-formed sequences. Ie, maintain a pool of active accounts, using valid signatures, etc. Of course, generating invalid inputs is also something we need to do from time-to-time. The link blog post (and the wasm-smith crate it describes) are a good model here. We actually should directly use wasm-smith for DeployContract action.
• implement a fuzzing target for cargo-fuzz
• run the fuzzing locally and test that the coverage is reasonable. That is, deliberately introduce paniking bugs into runtime, and check that fuzzing catches them
• setup some kind of CI job to run the fuzzing. Perhaps even apply for https://google.github.io/oss-fuzz/ ?
• optional: look into "swarm testing" (see the link in the post)

[bowenwang1996]

Regarding fuzz testing function calls, I think we should focus on the following:

• fuzzing function calls that generate receipts with different types of actions (transfer, delete account, create account, deploy contracts, etc). Fuzzing should be able to uncover bugs like what is fixed in fix(runtime): revert implicit account creation on account deletion #4512.
• fuzzing all host functions. Host function bugs like fix(runtime): Fix validator stake host function #4535 should be discovered by fuzzing.
• fuzzing cross-contract calls. This should ideally be combined with the two above to make fuzzing more robust and useful.

[posvyatokum]

Pushed more code to #4546
Right now switching to #4550 to run current fuzzer in CI