search

runtimeverification / evm-semantics

K Semantics of the Ethereum Virtual Machine (EVM)
BSD 3-Clause "New" or "Revised" License
508 stars 143 forks source link

#badjumpdest? (Sorts K and NullStack incompatible) #192

Closed MrChico closed 5 years ago

MrChico commented 6 years ago

We are trying to make the following circularity claim: https://github.com/dapphub/verified-smart-contracts/blob/dappsys/dappsys/exp-naive-circ-spec.k but are given the following error

screen shot 2018-04-16 at 15 19 07

Does this error stem from something wrong in our spec? It looks like an error that has to do with the internal workings of K...

MrChico commented 6 years ago

I'm pretty sure this error has to with the #badJumpDest? rule, specifically clauses like this:

    rule <k> #badJumpDest? [ JUMP ] => #end EVMC_BAD_JUMP_DESTINATION ... </k>
         <wordStack> DEST : WS </wordStack>
         <program> ... DEST |-> OP ... </program>
       requires OP =/=K JUMPDEST

seem to be comparing JUMPDEST (with sort NullStackOp) with a general OP (of sort K)

ehildenb commented 6 years ago

Hmmmm, we could add extra operator ==OpCode and =/=OpCode which insert the additional sort-checks needed. I wonder if this would cut down on how many "missing SMTLIB translation" errors people get.

ehildenb commented 6 years ago

@MrChico I'm trying some other optimizations on another branch (just local for now), but I'm running into a (potentially) similar issue. Can you try changing <program> ... DEST |-> OP ... </program> to <program> ... DEST |-> OP:OpCode ... </program> for both the JUMP and JUMPI cases of your semantics of #badJumpDest? and see if it changes the behavior on this example?

MrChico commented 6 years ago

Yes, @ehildenb , I did some experimentation with that before which did change the example.

After spending some time thinking about this, my hypothesis is that this mainly becomes an issue in trying to prove very general specs that end up having the jumpdestination as a symbolic value, forcing K to evaluate whether an OP-code at an arbitrary position is a JUMPDEST or not.

Another behavior I just noticed with #badjumpdest is that there is an unnecessary branching when checking #badJumpDest?[JUMPI ], see screenshots from @mhhf 's kdebugger (WIP)

screen shot 2018-05-03 at 15 16 42 screen shot 2018-05-03 at 15 16 50
ehildenb commented 6 years ago

@yzhang90 has noticed the same. You can try out branch opcode-basic-blocks, which should remove this unnecessary branching. #badJumpDest? is removed altogether, and instead the semantics are given directly over JUMP and JUMPI. Be warned though, the tests do not pass yet on that branch. I'm working on getting these branches merged, but it's 3 PRs back.

ehildenb commented 5 years ago

I believe this was solved by delaying checking for bad jump destinations until we semantic execution time (instead of a pre-check).