acuarica / evm

A Symbolic Ethereum Virtual Machine (EVM) bytecode interpreter, parser and decompiler, along with several other utils for programmatically extracting information from EVM bytecode.
https://acuarica.github.io/evm/
MIT License
46 stars 5 forks source link

Conditional expression serialization based on its size #94

Closed acuarica closed 5 months ago

acuarica commented 5 months ago

This PR introduces depth and count, referring to the depth and count of AST nodes in expression d9c366997af76624b916b63324e5a1bb4fb423fa.

This allows Solidity serialization to decide whether or not to serialize an expression based on its size or depth. When the size is too big >1000 nodes, the serialization bails. This is to avoid OOM errors. This kind of issue can arise in the following contract https://etherscan.io/address/0xaeef3c744e07b4ceeb7469460f220c697b8fb8bc#code

library ModexpInverse {
    function run(uint256 t2) internal pure returns (uint256 t0) {
        // solium-disable-next-line security/no-inline-assembly
        assembly {
            let n := 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47
            t0 := mulmod(t2, t2, n)
            let t5 := mulmod(t0, t2, n)
            let t1 := mulmod(t5, t0, n)
            let t3 := mulmod(t5, t5, n)
            let t8 := mulmod(t1, t0, n)
            let t4 := mulmod(t3, t5, n)
            let t6 := mulmod(t3, t1, n)
            t0 := mulmod(t3, t3, n)
            let t7 := mulmod(t8, t3, n)
            t3 := mulmod(t4, t3, n)
            t0 := mulmod(t0, t0, n)
            t0 := mulmod(t0, t0, n)
            t0 := mulmod(t0, t0, n)
            t0 := mulmod(t0, t0, n)
            t0 := mulmod(t0, t0, n)
            // [...many more mulmod]
        }
    }
}

where each mulmod(t0, t0, n) duplicates the size of expression when serialized. Note that when it is not serialized, there is no issue since internally object references are stored.

Moreover, this PR memoizes eval for Local expression bd54ba64976f081efbf4d003c022d29a244bc8f7 This avoids re-evaluating the same expression multiple times. This happens when this Local is used in multiple places.

acuarica commented 5 months ago