Fuzzing-based property-based testing

[ruuda]

This is an idea that was just mentioned during the meeting with the Solana team: property-test some invariants of Lido.

One great way of doing this is to encode every operation in a data structure, derive Arbitrary for it, and then run it in cargo-fuzz. This way you get coverage-driven property testing which is very powerful.

The thing I’m not sure about is how this would pan out in practice, because not all interactions happen in the Rust program itself, there are interactions with the Solana validator. Perhaps this thing that is also used in tests could be useful here.

[joncinque]

If it helps, we've found that using both proptest for specific calculations and fuzzing from the top-level gives great coverage

[ruuda]

Proptest looks very similar to cargo-fuzz + Arbitrary. If I understand correctly Proptest is not coverage-driven, whereas cargo-fuzz is. It’s a wrapper around LLVM’s libFuzzer, which inserts instrumentation into the program that records coverage, which helps it to explore “interesting” inputs that have a low probability of being generated with QuickCheck-style generators. I’m not sure if libFuzzer will work with Solana, Proptest looks like a good alternative :+1:

[joncinque]

They're a bit similar, but they have different intended uses. An analogy could be that proptests are like unit tests, and fuzzing is like integration tests. So for example, to test the fix to the fee calculation, I'll write a proptest.

Separately, honggfuzz and libFuzzer both work with Solana. I've used both of them and preferred honggfuzz only because it doesn't require rust nightly. There's a nice example of using honggfuzz with program-test in the bonfida bot repo: https://github.com/Bonfida/bonfida-bot/tree/main/program/fuzz and an example without program-test using libFuzzer at https://github.com/project-serum/serum-dex/tree/master/dex/fuzz

[ruuda]

So I’ve been thinking some more about this, and I don’t think it is something we can do at this point.

• Traditional fuzzing is aimed mostly at things like parsers, and tries to find memory safety issues or hangs and crashes in there. While we do deserialize things in the on-chain program, the impact of a crash there is not as severe as it is for native binaries, where such issues can lead to DoS or are even exploitable. If the on-chain program crashes, the transaction will just fail, nothing bad happens. (Same with arithmetic overflow; silent wrapping is very bad, but letting the program crash, vs. reporting an error properly, both lead to the transaction failing.) Conclusion: Fuzzing the deserializers is not that useful.
• A more interesting use case of fuzzing is to have it generate operations, and fire those at your application, and then assert your invariants in between. But to be able to do that, you need
  • To have invariants in the first place, and a way to assert them
  • A way to run your application in the fuzzing environment Because our on-chain program interacts with the Solana runtime, the only way to run it, aside from running it for real, is with the solana_program_test framework. But that one only runs with cargo test-bpf, which I don’t think is compatible with something like cargo-fuzz, because they both want control over the rustc and LLVM flags. Aside from that, we have very little invariants in Solido that could be violated. (One I can think of is AccountMap, which should never store more elements than its configured maximum.) We have pretty nice data structures where every instance in principle is valid, so there are no obvious things to assert.
• There are some instructions that require authorization checks, but this is more suitable for traditional tests (which we have); randomized testing is not going to help detect violations, because the test logic to determine the desired outcome would be more complex than the authorization check itself.
• There are some properties we would like to check, such as “the user can always get their SOL out”, but that statement has many caveats (you have to break up your withdrawals, validators have minimum balances, so it may require removing validators, which may require deactivation, which can take an unbounded amount of time). So again I’m not sure how to match this to randomized testing, where the logic to determine the desired outcome is not more complex than the implementation of the feature itself.

There are a few narrow use cases where fuzzing is a good fit:

• Roundtripping of serializers. For derived serializers I think we can trust the generated code, but for e.g. SOL formatting and parsing, we can do this. Also if we in the future write a (de)serializer for the Lido struct manually, roundtripping would be a good thing to fuzz.