dgpv / bsst

B'SST: Bitcoin-like Script Symbolic Tracer
Other
32 stars 5 forks source link

Detect effect-less code fragments #39

Open dgpv opened 3 months ago

dgpv commented 3 months ago
          I think it would be great to detect 'effect-less' code fragments like  `DUP DROP DUP DROP 2DUP 2DROP DUP DROP`, because it also can help detect the bugs, just like the compiler warnings can tell you that you probably want to look at this piece of code second time.

Right now bsst can only detect always-true enforcement conditions, but not effect-less code. It can be a useful enhancement.

It should be possible to 'turn off the warnings', though. But because the focus of bsst from the beginning was helping to detect the bugs, turning off warnings should result in one big warning at the start of the report, that tells that warnings are off :-)

Originally posted by @dgpv in https://github.com/dgpv/bsst/issues/33#issuecomment-2124223594

dgpv commented 2 months ago

We have the log of 'exec states' for each position of program counter, so we can compare current exec state with previous exec states to check if any previous state is identical to the current exec state, to detect effect-less code fragments.

We can also look for 'too small' differences in exec states, like when a big code fragment only resulted in small amount of shuffling the same values on the stack. We can have a table for 'small shuffles', like (a, b) -> (a, a): SWAP DROP DUP. If the code fragment is longer than the simple code for the same shuffle, we can give a note

dgpv commented 2 months ago

The vfExec array should be identical for the exec states

We should also check differences in the altstack. It will complicate the 'shuffles table', though, if we consider shuffles with changes to altstack. But may be still manageable to build the shuffles table manually for small shuffles

for longer shuffles some 'optimizer' have to be built that can output a shortest fragment for certain stack permutation. Given that it will only concern shuffles, and not value computation, it should not bee too complex, though