Comment by aleclm | Hacker News Reader

Comment by aleclm | Hacker News Reader

Parent Full thread

Hey, rev.ng core dev here.

I guess the core difference is that we do not implement the instructions semantics ourselves, but we reuse QEMU.

QEMU, when in emulation mode (i.e., not KVM), goes from executable code to an intermediate representation (tiny code instructions) and then compile it back to the host architecture.

We use the first part of QEMU but then translate tiny code instructions into LLVM IR.

This means that:

1. We don't have to implement instruction semantics on our own;

2. We can easily support the architectures supported by QEMU. Currently we support x86-64, i386, ARM, AArch64, MIPS and S390. https://wiki.qemu.org/Documentation/Platforms

3. We get out of the box the accuracy in instructions semantics of a mature emulator such as QEMU.

We used to be able to lift `gcc` to LLVM IR, recompile it and have it working.

However, the real difference is that, while it still works, we're now no longer focused on binary-to-binary translation, but we're now 100% focused on writing a full blown decompiler, i.e., something that goes from binary code to (valid) C and has a nice interactive UI.

As you can imagine, the lifter is really just the first half of a decompiler.

For instance, one core feature of rev.ng is automatic detection of `struct`s, just by looking at how they're used: https://twitter.com/_revng/status/1575553313827069952

If you have been doing some reverse engineering, I'm sure you'd appreciate this feature.

Bonus, take a look at our UI: https://twitter.com/_revng/status/1720440515265474631

As a side note, towards the end of the month we're releasing the new website and starting to invite people to the closed beta. If you wanna join: https://rev.ng/register-for-nightly.html

I once had the idea to do malware-similarity analysis. The X86 should first be lifted into a IL, so it gets "normalized" (e.g. register independant). The problem with all lifters is though that even a trivial "add rax, 1" generated a lot of IL code (probably 50-100 lines in LLVM IL), as the lifter had to implement all side effects of the X86 instructions in a fake memory space (i used remill if i remember correctly).

Does this lifter have a similar implementation, or will a "add rax, 1" be lifted to something like "register1 += 1"?

> The problem with all lifters is though that even a trivial "add rax, 1" generated a lot of IL code (probably 50-100 lines in LLVM IL)

Why is this a problem? The addition is one LLVM-IR instruction (add), followed by flag computation (maybe 10-20 instrs). Dead code elimination will afterwards quickly remove unused instructions (e.g., unused flags).

> register1 += 1

I don't see how this could be beneficial, especially on x86 where you can have "mov rax, rdx; add rax, 1" and "lea rax, [rdx + 1]", which do mostly the same (the former clobbers flags). SSA removes registers and shows the semantic operations clearly.

I had some ideas about binary diffing, but it's a difficult topic and I'm too much of a noob in ML to get to something working in a decent time frame.

I think something ABI-, compiler- and architecture-agnostic would be super cool and I started to build a training data set.

I wouldn't diff individual instructions though, I'd go for something more highlevel, such as features of the CFG and type of operations in the nodes.

Ghidriff: Ghidra Binary Diffing Engine, ghidra-patchdiff-correlator: https://news.ycombinator.com/item?id=38870593

Do you have examples of your decompilation, and how it compares to state of the art that uses other approaches? Do you run optimizations on your generated LLVM IR to clean it up and canonicalize it?

> 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

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

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.

> 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 :)

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.

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?

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.

No need to indent links.

Reply on news.ycombinator.com