#badjumpdest? (Sorts K and NullStack incompatible)

[MrChico]

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

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]

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]

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]

@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]

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)

[ehildenb]

@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]

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