undefined | Better HN

0 pointsedflsafoiewq7y ago0 comments

In a sense you can mechanically translate between any Turing complete languages, but there's not a "naive" translation, so to speak, because C can have irreducible CFGs and Rust cannot. It's not clear to me that reflowing a CFG can always be done without a performance impact.

0 comments

6 comments · 3 top-level

legulere7y ago· 2 in thread

You can convert an irreducible CFG to a reducible CFG with a loop and a switch case(/match in case of rust):

In pseudocode

  Goto = Start;
  While(Goto!=End) {
    Match(Goto) {
    ...
    }
  }

It’s a pretty basic obfuscation technique. Compilers will happily unroll this leaving you with an irreducible CFG.

edflsafoiewqOP7y ago

You have more faith in the compiler than I do. Here's a stupid test I made.

* In C++, using goto: https://godbolt.org/z/YqCMbU

* In Rust, with relooped CFG: https://godbolt.org/z/IIXtKo

The compiler was obviously not able to unroll the relooped code into the original CFG.

A specific example: in principle, the compiler could see the exact target of every continue in the Rust code, so the continue on line 34 could go directly to line 27 (or, better, as in C++ the basic blocks could just be laid out adjacently), but the compiler does not actually do this and there are a bunch of unnecessary tests on the path between those two lines.

dbaupp7y ago

It's unfortunate that the enum-based solution doesn't work, but that particular example can be made "optimal" (at least, as good control flow as LLVM can get this code: the same as clang, not GCC), by using a rather unpleasant series of loops and labelled breaks: https://godbolt.org/z/sQ1nH8 (rustfmt'd version: https://play.rust-lang.org/?gist=b1091e0c583b88f27bf1eaeae3a...).

This doesn't work in general, and is ... impossible to maintain, but it's not an unreasonable approach for generated code.

pcwalton7y ago· 1 in thread

True, I forgot about goto.

edflsafoiewqOP7y ago

Not only true goto but also switch and computed goto. AFAIK C/C++ are essentially the only games in town for these. No modern language has even corrected the purely syntactic limitation that prevents nested switches (by eg. allowing you to attach label names to switch blocks and cases).

eddyb7y ago

Note that Rust has "forward goto" in the form of "labelled break" (which can even carry a value), so I suspect some cases might not even need converting to a loop-match "state machine".

j / k navigate · click thread line to collapse

0 comments

6 comments · 3 top-level

legulere7y ago· 2 in thread

You can convert an irreducible CFG to a reducible CFG with a loop and a switch case(/match in case of rust):

In pseudocode

  Goto = Start;
  While(Goto!=End) {
    Match(Goto) {
    ...
    }
  }

It’s a pretty basic obfuscation technique. Compilers will happily unroll this leaving you with an irreducible CFG.

edflsafoiewqOP7y ago

You have more faith in the compiler than I do. Here's a stupid test I made.

* In C++, using goto: https://godbolt.org/z/YqCMbU

* In Rust, with relooped CFG: https://godbolt.org/z/IIXtKo

The compiler was obviously not able to unroll the relooped code into the original CFG.

dbaupp7y ago

This doesn't work in general, and is ... impossible to maintain, but it's not an unreasonable approach for generated code.

pcwalton7y ago· 1 in thread

True, I forgot about goto.

edflsafoiewqOP7y ago

eddyb7y ago

Note that Rust has "forward goto" in the form of "labelled break" (which can even carry a value), so I suspect some cases might not even need converting to a loop-match "state machine".

j / k navigate · click thread line to collapse