4 ms·

Serious question, is it even possible to have something like ‘match’ or ‘dynamic_cast’ in a programming language without using branches under the hood? I’m not

Serious question, is it even possible to have something like ‘match’ or ‘dynamic_cast’ in a programming language without using branches under the hood? I’m not talking about research/example microprocessors that don’t have equivalent instructions. I mean isn’t branching a fundamental logical construct and we either do it in hardware with branch assembly operations or emulate functional equivalents of them in the software that runs on the microprocessor some other way? Or is there some clever/old logical/mathematical “alternative” to branches?

cerved 9y ago
The problem isn't the branches it's the speculative execution
earenndil 9y ago
Consider something like this: struct __internal_variable { uint64_t type; void *data; } uint64_t __last_type = [number of builtin types]; whenever you create a new type: increment __last_type and associate that type with the number; uint64_t typeof(__internal_variable var) { return var.type; } function[__last_type] typechecks; functions[] = void function(uint64_t type) { failure; } functions[int] = void function(uint64_t type) { success; } functions[typeof(myvar)]() If typeof(myvar) is int, then the function that returns success will be called, otherwise failure, no branches involved! Yes, it's a kludge, but it kind of works. --- Of course, you don't actually need this trick. If you put enough effort into it, you can essentially compile anything to c, after which you can just compile it with the movfuscator[1] 1: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- gpderetta 9y ago
  That's basically a jump table. Still vulnerable to spectre (variant 2) without mitigations, btw.
  - fpoling 9y ago
    It is even worse then switch/match statements. The jump tables can be used to train CPU to jump to a wide variety of addresses than switch/match statements so mounting a speculative execution attack is simpler.
    - gpderetta 9y ago
      true. Then again switch statements (and I assume match statements in language that have them) are often compiled down to a jump table...
kzrdude 9y ago
Yes,it's already implemented as a poc - just look at movfuscator

cerved 9y ago

The problem isn't the branches it's the speculative execution

earenndil 9y ago

Consider something like this: struct __internal_variable { uint64_t type; void *data; } uint64_t __last_type = [number of builtin types]; whenever you create a new type: increment __last_type and associate that type with the number; uint64_t typeof(__internal_variable var) { return var.type; } function[__last_type] typechecks; functions[] = void function(uint64_t type) { failure; } functions[int] = void function(uint64_t type) { success; } functions[typeof(myvar)]() If typeof(myvar) is int, then the function that returns success will be called, otherwise failure, no branches involved! Yes, it's a kludge, but it kind of works. --- Of course, you don't actually need this trick. If you put enough effort into it, you can essentially compile anything to c, after which you can just compile it with the movfuscator[1] 1: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator

gpderetta 9y ago
That's basically a jump table. Still vulnerable to spectre (variant 2) without mitigations, btw.
- fpoling 9y ago
  It is even worse then switch/match statements. The jump tables can be used to train CPU to jump to a wide variety of addresses than switch/match statements so mounting a speculative execution attack is simpler.
  - gpderetta 9y ago
    true. Then again switch statements (and I assume match statements in language that have them) are often compiled down to a jump table...

kzrdude 9y ago

Yes,it's already implemented as a poc - just look at movfuscator