10
$\begingroup$

I'm researching static recompilation but there doesn't seem to be too much information about the subject. I've heard that dynamic recompilation (emulation) can be up to 6 times slower than native assembly, but I'm curious why we aren't able to translate to a different architecture ahead of time. Even though some instructions wouldn't be 1:1, can't we just shift the rest of the code, and all of the jump instructions with it?

Furthermore, if the problem is a lack of source code, would this mean that Super Mario 64 (which has already been completely reverse engineered, to exactly identical binaries), can be fairly easily recompiled into a different architecture?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Dynamic recompilation being slow is not just a result of the overhead of translating at runtime. It’s also a result of having to work around feature differences between the source and target architecture. Running POWER8 code on 64-bit x86 for example runs into the issue of handling the 96+ registers that a POWER8 system provides using the only 32 registers that 64-bit x86 provides, and handling that imposes a significant performance penalty on it’s own. That aspect can’t be solved just by using static recompilation though, you need to actually rewrite the code to avoid the issue. $\endgroup$ Commented Nov 18, 2022 at 12:34
  • 1
    $\begingroup$ Manual static recompilation from source code is not only possible, but relatively easy. Sometimes extremely easy. We call it "porting" the program. Given that decompilers exist, automatic recompilation from binaries is possible in principle, albeit problematic in practice. $\endgroup$ Commented Nov 18, 2022 at 13:13
  • $\begingroup$ There is a difference between "dynamic recompilation" and "emulation". Maybe. I guess it depends on what you think "dynamic recompilation" means. I think it most appropriately means "binary translation, perhaps just-in-time". Consider, for example, the early highly successful FX!32 for running Windows NT x86 binaries on Alpha - very high performance was achieved. Try searching on "binary translation" - there's been a lot of work in that area, including commercially successful systems. $\endgroup$ Commented Nov 20, 2022 at 17:59

2 Answers 2

Reset to default
21
$\begingroup$

Static recompilation from a binary is hard, because it is challenging to reconstruct the structure of the program. It is hard to statically figure out the location of all instructions that will be executed, the starting point of all functions, and the set of all jump targets. This information is needed for natural methods of recompilation: we need to know where all the instructions are, so we can recompile them; we need to know where function prologues and epilogues are, so we can translate them to other function calling conventions; we need to know the set of all jump targets, because all of those locations need to be recompiled. It's not impossible, but it can be extremely challenging to do with 100% fidelity.

Given a binary executable, it is hard to reliably find all of the executable code statically, due to the presence of indirect jumps. In particular, on x86, it is possible to jump into the "middle" of an instruction, which will cause the stream of bytes to be interpreted differently than you might expect. Since we can't predict all possible jump targets of indirect jumps (this is as hard as the halting problem), it is hard to know all locations that might be executed as code, and at what offset. This makes reliable static disassembly hard. And of course, if you can't even disassemble, it's challenging to re-assemble or re-compile.

See, e.g., work on static disassembly to learn about the subject. Here are some sample papers:

  1. From Hack to Elaborate Technique—A Survey on Binary Rewriting. Matthias Wenzl, Georg Merzdovnik, Johanna Ullrich, and Edgar Weippl. ACM Computing Surveys (CSUR), 52(3), 1-37
  2. An In-Depth Analysis of Disassembly on Full-Scale x86/x64 Binaries . Dennis Andriesse, Xi Chen, Victor van der Veen, Asia Slowinska, Herbert Bos. Usenix Security 2016.
  3. SoK: All You Ever Wanted to Know About x86/x64 Binary Disassembly But Were Afraid to Ask. Chengbin Pang, Ruotong Yu, Yaohui Chen, Eric Koskinen, Georgios Portokalidis, Bing Mao, Jun Xu. 2021 IEEE Symposium on Security and Privacy (SP) (pp. 833-851).

See also https://hexterisk.github.io/blog/posts/2020/04/02/disassembly-and-binary-analysis-fundamentals/.

This problem is particularly intractable for obfuscated binaries, but even for normal non-obfuscated binaries, existing methods have difficulty fully recovering 100% of the instructions, function starts, and jump targets with perfect accuracy. This is a problem, because if there is even one mistake, then the entire program might crash.

An additional challenge is that if the program does any kind of runtime code generation or runtime JIT or runtime recompilation, then this only makes the static recompilation problem even harder.

In contrast, runtime (dynamic) methods avoid this problem, because they can observe which instructions and code paths actually get executed and recompile only the ones that are executed, at the time they are executed.

Improve this answer
$\endgroup$
12
  • 10
    $\begingroup$ BTW, non-obfuscated compiler-generated x86 executables don't do that kind of crazy stuff like jumping into the middle of instructions, or even mixing code and data in ways that gets naive disassembly out of sync with the starts of instructions. GNU Binutils objdump -d is fully naive top-to-bottom disassembly, not using jump targets to find start points for other pieces of code, and it will correctly find all the instructions in a compiler-generated executable even if it's been stripped so there's only minimal metadata. (Just .text ELF section header, which isn't necessary for execution) $\endgroup$ Commented Nov 18, 2022 at 8:25
  • 5
    $\begingroup$ So the challenge here is intentionally obfuscated binaries. (And ones that do JIT code-generation, since translating some code that produces MIPS machine code in memory and jumps to it won't go well on x86-64). See also Why do Compilers put data inside .text(code) section of the PE and ELF files and how does the CPU distinguish between data and code? - x86 compilers proper don't, for performance reasons. x86 obfuscators might. ARM compilers do (literal pools for short-ranged PC-relative loads.) $\endgroup$ Commented Nov 18, 2022 at 8:28
  • $\begingroup$ @PeterCordes, Thank you for highlighting that. That's a great point about obfuscation vs normal binaries. The second paper I cite seems to suggest that the situation is a little nuanced: for instance, S3.1.1.1 says Visual Studio occasionally produces output that confuses linear disassembly (like objdump), and objdump has a few issues with disassembling glibc. It also shows that identifying the start of functions -- which might be important for recompilation -- is error-prone. Also, identifying all possible indirect branch targets -- which is also important for recompilation -- is hard. $\endgroup$ Commented Nov 18, 2022 at 8:45
  • 1
    $\begingroup$ @DanielWagner: I think you're talking about the lock prefix, that makes memory-destination instructions into atomic RMWs. Like lock add [rdi], eax vs. add [rdi], eax. A Linux kernel built to be able to run on an SMP system will patch itself if booted on a uniprocessor, overwriting the LOCK prefix with something else, I think a separate nop instruction. gcc/clang compiling C or C++ with __atomic builtins (used by C++11 stdatomic.h) or C11 _Atomic stuff don't have a mechanism for doing what you describe, but hand-written library code might? $\endgroup$ Commented Nov 18, 2022 at 16:18
  • 1
    $\begingroup$ @DanielWagner: And BTW, I'm not saying recompilation for another ISA is remotely easy, just that usable disassembly hasn't been a problem in my experience (which is primarily with GNU/Linux systems, where open source makes it pointless to obfuscate binaries, and GCC and clang are very tame in this respect, apparently moreso than MSVC.) e.g. Rosetta2 on MacOS needs hardware support from the CPU to have x86-style strong memory ordering when running AArch64 machine code recompiled from x86-64 executables. $\endgroup$ Commented Nov 18, 2022 at 16:25
4
$\begingroup$

Static recompilation is used, for example it is central in Apple's Rosetta 2 emulator. But there are challenges that make it difficult to apply.

Most importantly, all jump targets are not readily determined from the code. Compilers generate code using methods such as branch tables, virtual method tables and plain old function pointers. All of these take the jump target address from somewhere else than directly from the branch instruction argument. Knowing the compiler helps, but for generic code translation compiler-specific algorithms would involve a lot of work.

If jump targets are not known, the code must be translated so that each source instruction corresponds to a continuous sequence of target instructions. The dynamic target address can then be resolved at runtime. For some instruction sets this is feasible: in Apple's case, ARM64 has more registers than x86-64 and specific extensions to make this possible. For other cases, static recompilation without cross-instruction optimizations would result in very slow code.

And in any case, there are many applications using just-in-time compilation - including e.g. most JavaScript interpreters. While the JIT compiler could be statically recompiled to a different instruction set, it will still generate code in the original instruction set. Which is why dynamic recompilation is still needed as a fallback.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ It should be noted that the impressive performance figures for Rosetta 2 are usually obtained with native macOS applications. In native macOS applications, most of the heavy computation is delegated to native macOS libraries for ML, graphics, video, audio, parallelism, concurrency, and so on, and the actual application binary serves more as an "orchestrator" for those libraries. In that case, Rosetta 2 statically translates calls into those libraries into calls to the native libraries instead of translating them into calls to the x86 libraries and recompiling those. $\endgroup$ Commented Nov 19, 2022 at 18:04
  • $\begingroup$ Of all these; branch tables are the only really hard one. Indirect calls via function pointers are findable. There's a theorem about the ability to do this. Basically, it involves determining the type of all variables. $\endgroup$ Commented Nov 21, 2022 at 3:51

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.