State caching feature notes

[bsamuels453]

I spent some time evaluating a potential state caching mechanism that would allow some speedups in run time. This issue documents the results in case we want to do it in the future, or weigh the feature against other development options.

The core idea is that Medusa can potentially cache state databases, keying them based on H(starting merkle root | txhash). We should probably also key this using the block+timestamp delay, but I only wanted to MVP it for this exploration.

Since many transaction sequences are generated from the corpus, this would theoretically allow us to cache the state transition function that gets executed relatively often.

The biggest unknowns are how much of a speedup this would actually offer, and how much memory would be consumed.

I empirically determined the estimated speedup by adding some monitoring logic to EVMApplyTransaction. In the best case, 30% of calls to EVMApplyTransaction can be served from the state cache. In the average case, it's closer to 20-25%. This does not include the time it takes to populate and retrieve entries from the cache, so we should consider this as no better than a 25% speedup in the best case (assuming most of our execution overhead is EVMApplyTransaction).

Didn't explore how much memory would be consumed. If state caches are direct copies of the statedb, expect dozens or even hundreds of kilobytes for each cache entry. If state caches are journal-like objects, then maybe it would be a lot less, but with more time required to "retrieve" from cache.

I also didn't measure how much time EVMApplyTransaction consumes as part of the normal fuzzing session. This should be measured because it might be a lot less than we expect.

[montyly]

Nice idea.

Might be useful to try to evaluate this on our internal benchmark to see the impact on realistic codebase's exploration.

[bsamuels453]

my understanding is that our sequence mutator uses an independent random variable for selecting the type of mutation and how to perform it. If this is true, then we should see the same performance impact regardless of the codebase we test on.

If the random variable is not independent (ie: maybe it selects a certain mutator more often if it's been more successful in creating new coverage), then we'll have different caching performance on a codebase-to-codebase basis.

a side note: if we were to weigh towards mutators that preserve the sequence of the first few transactions being mutated, it would drastically increase the performance of caching

[0xalpharush]

I had tried to adapt ityfuzz's approach of fuzzing from snapshots of interesting states (https://github.com/crytic/medusa/tree/snapshot and #469). I think viewing tx seq's as trees and building new test cases as branches lends itself to start from a snapshot of the common prefix. Rather than a state root, the key would be the prefix and the value would be the KV's in the state DB.

Restoring from state root is not very performant as it adds to overhead of constructing the trie for every tx (see comment on its removal in #397) and only the state DB KV's are needed. Ofc this might need to be offloaded to disk depending how many snapshots there are (subject to some priority sort of like an LRU cache). This also would allow fuzz workers to be assigned state prefixes according to some scheduler as opposed to all workers simultaneously exploring from the post-deployment state and likely duplicating work.