4 ms·

> Do you have examples of your decompilation, and how it compares to state of the art that uses other approaches? We don't have any exhaustive comparison, and

by aleclm 3y ago

> Do you have examples of your decompilation, and how it compares to state of the art that uses other approaches? We don't have any exhaustive comparison, and for sure IDA are better than what we currently produce in many aspects (we're not at 1.0 release), but I can tell you where we want to go: 1. Automatic data structures detection: our goal is to basically never emit pointer arithmetic but automatically reconstruct data types so you see `pointer->field2 = 3` instead of `*(pointer + 8) = 3`. And we want to do this exploiting global (interprocedural) information, not just within a single function. AFAIK, this has never been done out of academia. https://twitter.com/_revng/status/1674788459213631505 https://twitter.com/_revng/status/1674788459213631505 2. Emit way less gotos, ideally none. That's one of the things that makes the code hard to read. https://rev.ng/downloads/asiaccs-2020-paper.pdf https://rev.ng/downloads/asiaccs-2020-paper.pdf But again, I invite you to register for the beta and wait for the blog post where we'll show some recent developments. > Do you run optimizations on your generated LLVM IR to clean it up and canonicalize it? Sure, but it's not just about cleaning it up. LLVM has a set of analyses that we exploit to detect access patterns and automatically detect data structures containing arrays too. LLVM is so nice: it's scalable, you can recompile it, there's lots of analyses and you don't need to reinvent the wheel with six edges.

vient 3y ago
> Emit way less gotos, ideally none I vaguely remember two questions regarding this when a "No More Gotos" paper was published: 1. What if programmer did use gotos, and without them you can't really map code structure to language's available control flow mechanisms? 2. What if compiler decided to duplicate or deduplicate some basic blocks? Time to revisit original paper, and also read yours, to see what is said about these :)
- aleclm 3y ago
  1) Our goal is emitting goto rarely, not excluding them entirely. However, most of the gotos one sees in IDA are due limitations in control-flow recovery, example: switch (x) { case 0: do_0(); // Missing case 1 case 2: do_2(); case 3: do_3(); default: do_default(); } IDA will produce something like... if (x > 3) goto label; switch (x) { case 0: do_0(); case 1: label: do_default(); case 2: do_2(); case 3: do_3(); } gotos originally present in the original code are almost never the reason you see a goto in IDA. In any case, in presence of gotos, we currently duplicate code and sometimes this is good. Imagine the following code snippet which represents a legitimate use of gotos: int *x = malloc(sizeof(int)); if (x == NULL) goto cleanup; int *y = malloc(sizeof(int)); if (y == NULL) goto cleanup; do_stuff(x, y); cleanup: if (x != NULL) free(x); if (y != NULL) free(y); return; By "inlining" the gotos and doing some trivial optimizations we'd get: int *x = malloc(sizeof(int)); if (x == NULL) return; int *y = malloc(sizeof(int)); if (y == NULL) { free(x); return; } do_stuff(x, y); free(x); free(y); return; Which is not bad a at all IMO. 2) We don't deal with duplication, it's way less of a problem, usually. For deduplication, if it leads to gotos, we duplicate.
stevemk14ebr 3y ago
I read a paper once that a more ideal goal would be to not aim for goto free code, but instead aim at decompilation output that matches the source input best. The idea being that some C programs are really implemented as gotos and it's more natural to decompile them that way. This suggests some low % of gotos is the best rather than zero. Thoughts?
- aleclm 3y ago
  I was writing a response to the paper (which compares with rev.ng), but never managed to complete it. I wanted to make a thread on Twitter about it, but it was getting longer and longer, more like a blog post. If you're really interested, drop me an e-mail and I'll forward it to you. The bottom line is more or less summarized in my other response in this thread.

by aleclm 3y ago

vient 3y ago

> Emit way less gotos, ideally none I vaguely remember two questions regarding this when a "No More Gotos" paper was published: 1. What if programmer did use gotos, and without them you can't really map code structure to language's available control flow mechanisms? 2. What if compiler decided to duplicate or deduplicate some basic blocks? Time to revisit original paper, and also read yours, to see what is said about these :)

aleclm 3y ago
1) Our goal is emitting goto rarely, not excluding them entirely. However, most of the gotos one sees in IDA are due limitations in control-flow recovery, example: switch (x) { case 0: do_0(); // Missing case 1 case 2: do_2(); case 3: do_3(); default: do_default(); } IDA will produce something like... if (x > 3) goto label; switch (x) { case 0: do_0(); case 1: label: do_default(); case 2: do_2(); case 3: do_3(); } gotos originally present in the original code are almost never the reason you see a goto in IDA. In any case, in presence of gotos, we currently duplicate code and sometimes this is good. Imagine the following code snippet which represents a legitimate use of gotos: int *x = malloc(sizeof(int)); if (x == NULL) goto cleanup; int *y = malloc(sizeof(int)); if (y == NULL) goto cleanup; do_stuff(x, y); cleanup: if (x != NULL) free(x); if (y != NULL) free(y); return; By "inlining" the gotos and doing some trivial optimizations we'd get: int *x = malloc(sizeof(int)); if (x == NULL) return; int *y = malloc(sizeof(int)); if (y == NULL) { free(x); return; } do_stuff(x, y); free(x); free(y); return; Which is not bad a at all IMO. 2) We don't deal with duplication, it's way less of a problem, usually. For deduplication, if it leads to gotos, we duplicate.

stevemk14ebr 3y ago

I read a paper once that a more ideal goal would be to not aim for goto free code, but instead aim at decompilation output that matches the source input best. The idea being that some C programs are really implemented as gotos and it's more natural to decompile them that way. This suggests some low % of gotos is the best rather than zero. Thoughts?

aleclm 3y ago
I was writing a response to the paper (which compares with rev.ng), but never managed to complete it. I wanted to make a thread on Twitter about it, but it was getting longer and longer, more like a blog post. If you're really interested, drop me an e-mail and I'll forward it to you. The bottom line is more or less summarized in my other response in this thread.