Understanding what medusa
is doing under-the-hood significantly aids in understanding how to fuzz smart contracts
and also in writing fuzz tests. This chapter will walk you through the process of deploying the target contracts,
generating and executing call sequences, using the corpus, updating coverage, and resetting the blockchain.
The contract deployment process will deploy each contract specified in the
fuzzing.targetContracts
one-by-one. Any contracts that
are dynamically deployed during the construction of a target contract are also deployed. The deployment of these
contracts are done by the configurable
fuzzing.deployerAddress
address.
We will call the state of the blockchain after all the target contracts are deployed as the "initial deployment state".
This is the state of the blockchain before any transactions have been executed by the fuzzer. Here is what the underlying
blockchain would look like after the deployment of contracts A
, B
, C
(assuming no other dynamic deployments).
Now that we have our target contracts deployed, we can start executing call sequences!
Call sequence execution is the crux of the fuzzing lifecycle. At a high-level, call sequence execution is the iterative process of executing fuzzed transactions on the initial deployment state in hopes of violating (or validating) an invariant. Before continuing, it is important to understand what a call sequence is.
A call sequence is an array of individual transactions. The length of the array is governed by the
fuzzing.callSequenceLength
configuration parameter.
The fuzzer will maintain EVM state for the duration of a call sequence before resetting the state.
Thus, if you have a call sequence length of 10, medusa
will execute 10 transactions, maintain state throughout that
process, and then wipe the EVM state. Having a call sequence length of 1 means that medusa
will wipe the state after
each transaction. This is useful for fuzz testing arithmetic libraries or isolated functions.
Now that you know what a call sequence is, let's discuss how to generate a call sequence.
Call sequence generation can happen in two main ways:
- Generate a completely random call sequence
- Mutate an existing call sequence from the corpus
Let's talk about each possibility. Generating a completely random call sequence is straightforward. If we have a
fuzzing.callSequenceLength
of 50, we will generate 50 random transactions.
Definition: A random transaction is a call to a random method in one of the target contracts. Any input arguments to the method are fuzzed values.
The second possibility is more nuanced. To understand how to mutate an existing call sequence from the corpus, we need to first discuss the idea of coverage and what a corpus is.
Tracking coverage is one of the most powerful features of medusa
.
Definition: Coverage is a measure of what parts of the code have been executed by the fuzzer
Coverage is tracked in a rather simple fashion. For each target contract, we maintain a byte array where the length of the byte array is equal to the length of that contract's bytecode. If a certain transaction caused us to execute an opcode that we had not executed before, we increased coverage of that contract.
As shown in the figure above, the CALL
opcode was just executed causing the coverage array's value to be updated at that
index. The next natural question is, how do we harness this information to improve the fuzzer?
This is where the idea of a corpus comes in.
Definition: The corpus is a structure that holds "interesting" or "coverage-increasing" call sequences.
Thus, when medusa
runs, if it finds a call sequence that increased its coverage of the system, it will add it to the corpus.
These call sequences are invaluable to medusa
because they allowed it to explore a larger portion of the system. This is
what makes medusa
a coverage-guided fuzzer.
Definition: A coverage-guided fuzzer is one that aims to maximize its coverage of the system.
Tracking coverage and storing coverage-increasing sequences in the corpus also allows medusa
to re-use these sequences.
This takes us back to the second possibility when generating call sequences: mutating an existing sequence from the corpus.
The reason we re-use call sequences is that we know that the call sequence in question improved our coverage. So, we
might as well re-use it, mutate it, and then execute that mutated call sequence in hopes of further increasing our coverage.
There are a variety of mutational strategies that medusa
employs. For example, medusa
can take a call sequence from the corpus and append a new random
transaction at the end of it. This is called mutational fuzzing.
Definition: Mutational fuzzing is the practice of taking existing data samples and generating new variants of them (mutants).
Now that we know what a call sequence is, how to generate them, and how to track coverage, we can finally discuss how these call sequences are executed.
Call sequence execution happens in an iterative fashion. Here is some pseudocode on how it happens:
# Generate a new call sequence or mutate one from the corpus
sequence = generator.NewCallSequence()
# Iteratively execute each call in the call sequence
for i < len(sequence) {
# Retrieve the i-th element in the sequence
tx = sequence[i]
# Run the transaction on the blockchain and retrieve the result
result = blockchain.executeTransaction(tx)
# Update coverage
increasedCoverage = coverageTracker.updateCoverage()
# If coverage increased, add sequence[:i+1] to the corpus
if increasedCoveraged {
corpus.addCallSequence(tx[:i+1])
}
# Check for invariant failures
encounteredFailure = tester.checkForInvariantFailures(result)
# Let user know we had a failing test case
if encounteredFailure {
reportFailedTestCase()
}
}
The one portion of the above pseudocode that we did not discuss is checking for invariant failures. We will discuss the different types of invariants and what an invariant failure means in the next chapter.
The final step in the fuzzing lifecycle is resetting the blockchain. Resetting the blockchain is as simple as reverting to the "initial deployment state" of the blockchain. Once we reset back to the "initial deployment state", we can now generate and execute another call sequence!