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

[giscus[bot]]

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

A two-part series on the history of decompiler research and the fight against the unsolved control flow structuring problem. In part 1, we revisit the history of foundational decompilers and techniques, concluding on a look at modern works. In part 2, we deep-dive into the fundamentals of modern control flow structuring techniques, and their limitations, and look to the future.

https://mahaloz.re/dec-history-pt1

[sprowell]

Interesting. Every year I have the students in my RE class write code to generate structured disassembly

[mahaloz]

Oh interesting, so you have your students write code to make assembly that when decompiled looks exactly how it was compiled? Is the purpose of this to make code that is never optimized? P.s. if you want to see something wacky, have them use a switch statement with a small amount of cases... optimizations happen regardless of compiler flags :)

[sprowell]

They get an unknown binary, find main using a heuristic or fall back on the entry point, then use capstone to find and disassemble basic blocks. Then they compose structures from those and build a structured program using an approach very similar to Mills' CSF. The result is high level structures wrapping disassembly.

[mikewarot]

Ward Christensen's program RESOURCE pre-dates dcc by at least a decade. It was a widely available interactive disassembler.

[mahaloz]

I like to make the distinction between decompilers and disassemblers, since one is always harder to do because it requires the other.

There are a few instances of decompilers that came before Cifuentes (linked in the post), but, to my knowledge, her work is the first to explain any of these theoretical and formal problems in decompiling.