3 ms·
Just from taking a quick look at their description of how it works, this appears to essentially be a glorified pattern-matching approach to decompilation. This
by jcranmer 8y ago
Just from taking a quick look at their description of how it works, this appears to essentially be a glorified pattern-matching approach to decompilation. This is generally the worst approach to take to the issue, since it's extremely brittle and trivial optimization or obfuscation will complicate your approach.
A modern decompiler framework tends to take a very different approach. For native executables, the hardest problems are actually disassembly and higher-level type recovery. Bytecode is easier in that the type information is essentially retained and code is very nicely and obviously differentiated from data; no need to worry about jump tables or constant pools.
Control flow for a decompiler is recovered via some form of control flow structuring; the problem is essentially a graph grammar parsing problem, but this is not an easy problem to solve. In practice, it's the existence of goto-like edges (gotos, breaks, and continues) that really screws things up. It's usually easy to tell what the structure should look like without these edges, but identifying which edges fall into this category turns out to be challenging in practice. Especially if you start trying to undo jump threading.
The other interesting issue is working out what the decompiled variables are and should have been. SSA is actually a pretty clean way to separate out different variables that get assigned to the same register (this identification problem exists even in bytecode, as local variable slots due get reused whenever possible), but doing the PHI elimination and finding out where you've got bitcasted type magic going on (more of an issue for native code) can be a challenge.
- XMPPwocky 8y agoDo note that CPython bytecode has explicit break, continue, and "for loop" instructions, and (ofc) the language itself has no goto- so you can unambiguously recover high-level structure from a CFG far more easily than you might with compiled C.
- rockybernstein 8y agoYes and no. If you are sure that you start out with something generated by Python, then assuming the Python compiler is faithful, then of course you can always produces source code that doesn't have goto's in it. If instead someone crafts custom bytecode, like I did here: http://rocky.github.io/pycon2018-light.co/#/ http://rocky.github.io/pycon2018-light.co/#/ it might not have a high-level Python translation. When there is a translation, is it always unambiguous? No. The same bytecode could get decompiled "a and b" or as "if a: b". Why this happens less often in Python, especially earlier versions fo Python, is that it's code generation is very much template driven and there very little in the way of the kinds of compiler optimization that would make decompiling control flow otherwise harder. Using the example given above, I believe earlier versions of Python would always enclose the "then" statement/expression with "push_block", "pop_block" pairs. Even though in certain situations (no new variables are introduced in the "then" block) this isn't needed. But the fact that those two additional instructions are there can then distinguish between those two different constructs. It is sort of like matching ancestry based on the largely "junk" DNA strands that exist in a person. Finally, I should note that Python with its control structures with "else" clauses like "for/else" "while/else" and "try/else" make control flow detection much harder. And this is the major weakness of uncompyle6. That's why I started https://github.com/rocky/python-control-flow https://github.com/rocky/python-control-flow to try to address this. In contrast, the current python uncompyle6 code which has a lot of hacky control flow detection, this creates a control flow graph, computes dominators and reverse domninators in support of distinguishing these high-level structures better.
- XMPPwocky 8y agoDefinitely- though, arguably trying to decompile something which was never Python into Python is a bit of a fool's errand! Didn't think of for/else and friends, yeah, that's tricky. Definitely using doms/idoms is the right approach.
- mehrdadn 8y agoConfused, so you say it's taking the worst approach but then you just list a bunch of difficulties with doing it better... what is the criticism here? When I read your first paragraph I expected you were going to explain how to do it better.
- rockybernstein 8y agoInstead of taking a quick look at the description of how it works, why not instead spend a little more time to understand more, before passing judgement? I have written http://rocky.github.io/Deparsing-Paper.pdf http://rocky.github.io/Deparsing-Paper.pdf to help people who want understand how this fits into the conventional decompiler landscape, and how things are a little different here. Spoiler alert: no is it no more a glorified pattern-matching approach any more than a dragon-book-style compiler is.