3 ms·
Having read the paper, this effort, while interesting, does raise some red flags as to how viable the approach actually is. The first big one is that their app
by jcranmer 9y ago
Having read the paper, this effort, while interesting, does raise some red flags as to how viable the approach actually is.
The first big one is that their approach relies on matching the compiler and flags. While they claim that this is relatively easy to find (though the cited paper doesn't attempt to match flags), there is no indication of what the impact of not having, or having incorrect, information will do to the results. I'm left to guesstimate from their main experiment.
Let's talk about that. It seems that a substantial fraction of the good results comes from having a substantially correct seed. Without having any decompiler helpers, they were able to byte-equivalently decompile exactly 4 programs, one of which was hello world. With the decompiler's output as a seed, they got 10 programs--with the decompiler's output providing byte-equivalent output for 6 of those. Without an oracle for program correctness, it's hard to get an idea of what, say, a 60% equivalent program really means, especially. Having their example say "the answer was argv[i], but we did argv instead" is concerning--it's not implying that close is accurate.
One thing that's completely understated: they had to seed values. Having to seed strings is understandable, but then they give the example of the compiler-generated (x + x + x) << 2 for 12 x. The Project Euler example they couldn't decompile is "largest prime factor", and given that they did it worse on optimized than the unoptimized binary, I'm guessing that there's some small constant division and/or modulo operations that they can't seed.
The examples they evaluate on are tiny--the largest one is 88 lines (I'm guessing that's including whitespace and #include <stdio.h> judging from the size of hello world). They also look guaranteed not to trigger many advanced compiler optimizations (e.g., vectorization). It would be more interesting and useful to see the results on code from programming computations or things like the benchmark game which are somewhat designed to exercise more advanced features.
Scaling is, as others noted, not evidenced at all. They claim that it should be solved by doing functions individually, but it is worth noting that even trying to find the functions is a very challenging problem in decompilation. Moreover, interprocedural optimizations are an important part of optimizing compilers, and some of those kinds of optimizations are not going to be easily derived from a function-by-function approach (devirtualization comes to mind).
At the end of the day, while intriguing, this approach doesn't seem fruitful. The quality is still quite poor, despite running on very tiny programs. There's no evidence for being able to handle advanced compiler techniques (such as vectorization), and some a priori reasons to doubt its ability to handle it. It doesn't free the decompiler writer from having to put a fair amount of effort into solving hard problems (identifying functions), nor does it free them from having to do brittle pattern matching (the extent to which it is necessary is not made clear).