Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

mahaloz.re

Post reply on HN
Print view View original

11–16 of 16 posts

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

#11

Post by ryanjshaw »

Philpax wrote: post #7

This is great! I’m always on the lookout for advancements in decompilation. Looking forward to Part 2 :)

I build a static analyzer in my spare time and read a bunch of +fravia in my youth, so I have some familiarity with the space but I'm not an expert so I could be completely off here: I wonder if the LLM advances we've seen recently could be used to improve the state of the art in structuring?

As in, could you abstract away the CFG and feed it into an LLM trained on a bunch of CFGs and corresponding ASTs? Especially given that the LLM could be trained on a lot of code that may very well have been reused in the code being decompiled. Even if not the same code, the same algorithms may be similar enough to improve the structuring output.

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

#12

Post by JonChesterfield »

HALtheWise wrote: post #8

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.

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.

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

#13

Post by Philpax »

ryanjshaw wrote: post #11
Philpax wrote: post #7

This is great! I’m always on the lookout for advancements in decompilation. Looking forward to Part 2 :)

I build a static analyzer in my spare time and read a bunch of +fravia in my youth, so I have some familiarity with the space but I'm not an expert so I could be completely off here: I wonder if the LLM advances we've seen recently could be used to improve the state of the art in structuring? As in, could you abstract away the CFG and feed it into an LLM trained on a bunch of CFGs and corresponding ASTs? Especially g…

Yes, I suspect so; there's been some work on this already (from a cursory arXiV search: [0] [1] [2], but there are more). I'm also curious to see if graph neural networks can be used for structuring, as well - given a decompiled CFG, can the original CFG be predicted?

There's lots to be researched here, but as the post alludes to, (public) development is limited. My hope is that there will be more work in this space to enable porting of closed-source applications on older architectures to newer architectures; I have a few ideas on how to go about that, but not enough time to look into it.

[0]: https://arxiv.org/abs/2310.06530

[1]: https://arxiv.org/abs/2306.02546

[2]: https://arxiv.org/abs/2304.03854

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

#14

Post by turol »

HALtheWise wrote: post #8

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.

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.

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

#15

Post by [deleted] »

turol wrote: post #14
HALtheWise wrote: post #8

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.

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.

[deleted]

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

#16

Post by konstante »

turol wrote: post #14
HALtheWise wrote: post #8

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.

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.

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".

Post reply on HN