30 Years of Decompilation and the Unsolved Structuring Problem: Part 1

Re:30 Years of Decompilation and the Unsolved Structuring Pr... by HALtheWise on Thursday January 04, 2024 @12:31AM (#38863422)

I've wondered whether it would be possible to design a language with the explicit intent of being a decompilation target, such that you could guarantee that any program could be decompiled into it and then subsequently re-compiled with the original behavior preserved. Having such a language (perhaps a superset of C?) would make it way easier to perform binary patching.

[ Parent | on HN ]

Re:30 Years of Decompilation and the Unsolved Structuring Pr... by rgovostes on Thursday January 04, 2024 @01:23AM (#38863745)

In a way disassembler output is exactly this. It’s a low level programming language, but one nonetheless.

There are tools like Remill (https://www.trailofbits.com/opensource/#binary) that disassemble to LLVM IR that can be fed back to the compiler to produce a new binary. You can actually target a different architecture, so it works for binary translation too.

[ Parent | on HN ]

Re:30 Years of Decompilation and the Unsolved Structuring Pr... by ltfish on Thursday January 04, 2024 @01:18AM (#38863725)

DARPA’s Enhanced SBOM for Optimized Software Sustainment (E-BOSS) program may achieve this goal (via a slightly different approach).

[ Parent | on HN ]

Re:30 Years of Decompilation and the Unsolved Structuring Pr... by JonChesterfield on Thursday January 04, 2024 @05:40AM (#38865452)

I don't think you'd need to change the language, only the implementation. The easy way to go is to emit metadata along with the machine code to aid reconstruction, roughly a variant on dwarf format debug information.

[ Parent | on HN ]

Re:30 Years of Decompilation and the Unsolved Structuring Pr... by turol on Friday January 05, 2024 @08:56AM (#38879061)

This is not possible. Both disassembly and decompilation are equivalent to the halting problem. At least Mike Van Emmerik's PhD thesis ("Static Single Assignment for Decompilation") mentions this though I'm not sure if that's the original source.

[ Parent | on HN ]

Re:30 Years of Decompilation and the Unsolved Structuring Pr... by konstante on Sunday January 07, 2024 @06:30AM (#38900351)

Yes, static disassembling is well known undecidable, data and code are indistinguishable in general. The reason is very simple (it's actually just an exercice), consider an assembly code:

jmp rax

...some binary data...

Where the value of "rax" depends on some input, so the disassembler can never be sure that "some binary data" is actually "data" or "code".

[ Parent | on HN ]