ecfg panics on certain contracts

[dvush]

I noticed that ecfg fails on most of the nontrivial contracts that I tried.

Here is an example, contact. AFAIR is just trivial "get uint from slot - put uint to slot" contract compiled with solidity (opt enabled).

Bytecode

0x6080604052348015600f57600080fd5b506004361060325760003560e01c8063b2010978146037578063cfae3217146049575b600080fd5b60476042366004605e565b600055565b005b60005460405190815260200160405180910390f35b600060208284031215606e578081fd5b503591905056fea2646970667358221220158feba571c05db2dfbfcf6d4bfd06d8ff6d697ef52c8e1fbba805a33a17720764736f6c63430008040033

Result of ecfg run

$ RUST_BACKTRACE=1 ./target/release/ecfg -x code.txt 
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `4`,
 right: `0`', etk-dasm/src/blocks/annotated.rs:172:13
stack backtrace:
   0: rust_begin_unwind
             at /rustc/7737e0b5c4103216d6fd8cf941b7ab9bdbaace7c/library/std/src/panicking.rs:584:5
   1: core::panicking::panic_fmt
             at /rustc/7737e0b5c4103216d6fd8cf941b7ab9bdbaace7c/library/core/src/panicking.rs:143:14
   2: core::panicking::assert_failed_inner
   3: core::panicking::assert_failed
   4: etk_dasm::blocks::annotated::AnnotatedBlock::annotate
   5: etk_analyze::cfg::ControlFlowGraph::new
   6: ecfg::main
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Naive cfg picture

Maybe this could be useful for anyone debugging this. Here is a "naive cfg" of this contract. Each block is symbolically executed on its own: if jump location is static—nodes are connected on the graph, if jump location comes from the stack—I draw (borrowed n) that means that this block ends with a jump to stack[-n] value at the beginning of the block, where stack[-1] is top.

I wonder if panics occurs precisely because of this kind of cfg nodes that jump to non-static locations—precisely nodes "6e" and "42".

[SamWilsn]

It looks like this is caused by the bytes after the invalid instruction. I haven't looked into why yet, but if you remove that, ecfg generates a graph:

---

I'm actually working on some upgrades (extremely slowly) for ecfg that should get much better results.

[dvush]

Thanks for the response and a picture! I think I understand now.
It looks like ecfg's "cfg node splitting algorithm" differs from what I used. Basically, on the first linear scan of the bytecode I lump everything after invalid instruction but before valid jumpdest into one cfg node, while ecfg probably sees invalid instruction as a termination of one particular block and starts the next block from the next instruction.

example: // reminder: "fe" is invalid opcode
ecfg -c "0xfefe" will show 2 nodes (one with offset 0, another one with offset 1)

As a sidenote:
These nodes with non-static jumps make a graph really messed up! Even for such a small contract, they attach themselves to so many places, even when solver was able to prune some possible jumps.

[SamWilsn]

ecfg probably sees invalid instruction as a termination of one particular block and starts the next block from the next instruction.

Yep, that's correct.

These nodes with non-static jumps make a graph really messed up! Even for such a small contract, they attach themselves to so many places, even when solver was able to prune some possible jumps.

This is the biggest problem with ecfg's current approach. If the jump destination comes from the stack before a block (or god forbid memory, calldata, or storage), it can't prune most of the edges.

My original plan was to do a second pass over the blocks, executing from the first block and figuring out what the possible inputs to each block are, but I've mostly scrapped that and have a symbolic evm branch instead.