feat(`testing`): add mutation testing support

[onbjerg]

Mutation testing is used to design new tests and evaluate the quality of an existing test suite. In other words, it can tell you about the quality of your tests, where coverage only tells you about how much code you have not yet written a test for.

It works by changing the behavior of a program by changing parts of the code ("mutating it"), running the test suite with this new mutation and checking if the test suite passed. If the test suite passed, the mutation is considered to have survived - if not, it is considered to have died.

If dead / total is below some threshold, then there is room for improvement in the test suite. In other words, the more dead mutations you have, the better.

I think this would be a pretty cool tool to have in Foundry - and I think it is somewhat trivial to implement as well (simplified strategy):

• Have a list of mutations we can do
• Parse the source contracts
• Insert mutation somewhere
• Run tests
• Repeat until we're satisfied

Here's a paper on mutation testing for Solidity that I found interesting: https://arxiv.org/pdf/2105.03626.pdf

[onbjerg]

More notes:

• You can identify weakly tested pieces of code: mutations are not killed for these snippets
• You can identify weak tests: they never kill mutants

Paper has a handy list of mutations we could implement

[gakonst]

Related DappTools PRs/Issues:

• dapp mutate dapphub/dapptools#829
• Coverage Guided / Mutation Based Fuzzing dapphub/dapptools#687

[brockelmore]

potential inspiration: https://github.com/JoranHonig/vertigo
the paper: https://sci-hub.ru/downloads/2019-09-21/f6/10.1007@978-3-030-31500-9.pdf#chapter.19

has some good tips in it like knowing what test hits a particular mutation

we could do this by:

1. running all tests, build up a mapping of op -> Vec
2. perform mutation
3. run all tests for a mutated op

Vertigo works on solidity, but we may want to do part solidity, part raw opcodes so we can be faster and not have to recompile for all mutation types

[onbjerg]

alternatively we could sacrifice some disk space by copying the source of the project into cache/tmp/mutation-{1,2,3,n}, performing the mutation and in parallel spawn forge test --src ./cache/tmp/mutation-{1,2,3,n} (you get the idea).

if the command exits with status 0 the tests passed, otherwise they failed. afterwards we clean up by deleting those directories (or keep them around for diffing). if our cache works on hashes we theoretically(?) would only recompile the mutated contract anyway

[JoranHonig]

Yoyoyo, just seeing this thread now.

Not sure if this is possible already but if foundry could include the solc json ast in the compilation artifacts then it'll be relatively straightforward to create a Vertigo adapter for foundry.

alternatively we could sacrifice some disk space by copying the source of the project into cache/tmp/mutation-{1,2,3,n}, performing the mutation and in parallel spawn forge test --src ./cache/tmp/mutation-{1,2,3,n} (you get the idea).

if the command exits with status 0 the tests passed, otherwise they failed. afterwards we clean up by deleting those directories (or keep them around for diffing). if our cache works on hashes we theoretically(?) would only recompile the mutated contract anyway

That is close how Vertigo works right now (except that it doesn't create all of the mutations up front), and how the integration would work 👍

---

Vertigo works on solidity, but we may want to do part solidity, part raw opcodes so we can be faster and not have to recompile for all mutation types

There are some papers that evaluate this approach. From the top of my head there are two benefits to doing source code mutation:

1. Trivial Compiler Equivalence (basically free equivalent mutant detection)
2. Easier manual inspection of mutants (specifically equivalent mutations)

[chandrakananandi]

Hey all,

We have been working on a mutation generator called Gambit. It is implemented in Rust so it might be possible to integrate it with Forge easily.

Gambit is a mutation generator only and it works by traversing the Solidity AST to identify where to perform the mutations, then performs the mutations directly at the source level, and dumps them in a designated directory.

We are actively working on adding more functionality and better mutation generation when possible so let us know if you have any suggestions. PRs are also welcome :)

[gakonst]

This is great @chandrakananandi thank you for sharing!

The AST modification logic makes sense - cc @mattsse we could add that a mutate fn to the Project struct in ethers solc? Which would traverse all the tests and perform a random mutation? And we would run the the tests against the mutation inside of forge mutate?

[sambacha]

There is also Universal Simulator, one of the engineers from Trail of Bits maintains it -

here is some usage:
https://github.com/sambacha/universalmutator/tree/new-solidity-rules