aleclm

Yes.

Roadmap item: https://rev.ng/roadmap#feature-798

Design pad: https://pad.rev.ng/s/eDHi2PUoP#

should SLL decompile to x << y or x << (y % 32)?

I think this a bit of a misguided question. The hardware has a precise semantic defined, usually. QEMU's << behaves similarly to C (undefined behavior for rhs > 32), but this means that the lifter (still QEMU) will account for this and emit code preserving the semantics.

tl;dr: the code we emit should do the right thing depending on what the original instruction did, without making assumptions on what happens in case of C undefined behaviors.

Ghidra's type system lacks function pointer types

Weird limitation, we support those.

it doesn't seem to understand stack slot reuse

That's a tricky one. We're now re-designing certain parts of the pipeline to enable LLVM to promote stack accesses to SSA values, which basically solves the stack slot reuse. This is probably one of the most important features experienced reversers ask for.

that language need not be C--

Making up your own language is temptation one should resist.

Anyway, we're rewriting our backend using an MLIR dialect (we call it clift) which targets C but should be good enough to emit something "similar to C but slightly different". It might make sense to have a different backend there. But a "standard C" backend has to be the first use case.

We thought about emitting C++, it would make our life simpler. But I think targeting non-C as the first and foremost backend would be a mistake.

Also, a Python backend would be cool.

Analysis necessarily involves...

I would be interested in discussing more what exactly you mean here. Why don't you join our discord server?

I'd absolutely love to be able to import C++ header files to fill in known structure types

We have a project for importing from header files. Basically we want use a compiler to turn them into DWARF debug symbols and then import those. Not too hard.

Thanks!

It has been working very well. Two regrets:

1. Not rebasing our fork of QEMU for years has put us in a bad spot. But just today a member of our team managed to lift stuff with the latest QEMU. And he has also been able to lift Qualcomm Hexagon code, for which we helped to add support in QEMU. Eventually we'll be the first proper Hexagon decompiler :)

2. Focusing too much on QEMU led our frontend to be tightly coupled with QEMU. It will now take some effort to enable support for additional frontends, non-QEMU based. But not impossible: our idea is to let user add support for a new architecture by defining, in C, a struct for the CPU state and a bunch of functions acting on it. That's it. No need to learn any internal representation.

tl;dr QEMU was a great choice, it worked so well that we didn't work on that part of the codebase for too much time and now there's some technical debt there. But we're addressing it.

I 120% agree with what you're saying, but emitting valid C is kinda part of what you're asking, in design terms.

Our goal is: omit all the casts that can be omitted without changing the semantics according to C. In fact, we have a PR doing exactly this (still on the old repo, hopefully it will go in soon).

But, how can you expect to be able to be strict with what C allows you to do implicitly, if you're not even emitting valid C? For instance, thanks to the fact that we emit valid C, we could test if the assembly emitted by a compiler is the same before and after removing redundant casts.

My point is that emitting valid C is kind of a prerequisite for what you're asking, a rather low bar to pass, but that, in practice, no mainstream decompiler passes. It's pretty obvious the decompiled code will often be redundant and outright wrong if you don't even guarantee it's syntactically valid. Then clearly it's not a panacea, but it's an important design criterion and shows the direction we want to go.

As for comments: we still haven't implemented inline comments, but they will be attached to program addresses, so they will be available both in disassembly and decompiled C. It's not very hard to do, but that needs some love.

`source ./environment` is what's written on the announcement page at the top of this thread. './revng' doesn't appear anywhere on it.

You're right, but after that there's a link to the docs where we say to use `./revng`. The blog post is for the impatient :) On the long run the docs is what most people will look at.

I don't think we want to support use cases that might break system packages too. If you set LD_LIBRARY_PATH to a directory where you have an LLVM installation, that might break any system program using LLVM too... Why should we try to fix that using `DT_RPATH` (which is a deprecated way of doing things) when system components don't do it?

We might cleanup the environment from LD_LIBRARY_PATH and other stuff, that might be a sensible default, yeah. Also we might have some sanity check printing a warning if weird libraries are pulled in.

But it's hard to take a decision without a specific use case in mind. If you have an example, bring it forward and I'm happy to discuss what should be the right approach there.

Can you open an issue on GitHub and attach the binary? I don't think it should be too hard to load that.

In IDA you basically have only detection of stack frame layout (in a quite confusing fashion) and "create struct out of this pointer", which is something you have to do manually and its intraprocedural.

Imagine this being done automatically, across all of the binary. If you pass a pointer to another function the type is correct and you build the type from all the functions using it.

Then obviously the user needs to fix things, but boostrapping can definitely be hugely improved.

I think most of your concerns about messing with the environment are sensible only under the assumption that you actually do `source environment`.

In truth, we suggest to do that only so you use the GCC we distribute for the demo binary. The actual way this is intended to be used is through the `./revng` script. In that way, the environment changes only affect the invocation of `revng`.

This is documented here: https://docs.rev.ng/user-manual/working-environment/ We should probably add a warning about `source ./environment`.

Now, let's get to each of your comments :D

though thankfully not LD_LIBRARY_PATH

We spent a lot of time to have a completely self-contained set of binaries where each ELF refers to its dependencies through relative paths. LD_LIBRARY_PATH is evil.

Mostly prefixed "HARD_"

Those are just used by our compiler wrappers, I don't think those environment variables collide with anything in practice.

It sets `AWS_EC2_METADATA_DISABLED="true"`

Original discussion: https://github.com/revng/revng/pull/309#discussion_r12805759...

I guess we could patch the AWS SDK to avoid this. Anyway, it affects only when rev.ng is running in the cloud.

export RPATH_PLACEHOLDER=... export HARD_FLAGS_CXX_CLANG=...

Those are used when linking binaries translated by revng. If you're not interested in end-to-end binary translation, they don't matter.

it means 'runpath' which is a similar but much less useful construct

We specifically want DT_RUNPATH. DT_RPATH is deprecated and there might an use case for overriding our libraries with LD_LIBRARY_PATH.

There's a good chance you can completely remove the environment mangling

I think your observations concerning "mangling the environment" are only valid for non-private environment variables. The following variables are private: RPATH_PLACEHOLDER, HARD_*, REVNG_*. Also, they are all only for binary translation purposes. We could push them down into some smaller-scoped compiler wrappers, but those make sense only if we can get rid of environment entirely, which we can't because we ship Python.

a combination of setting different flags when building clang

No, the flags also affect the linker and there's some features of our wrappers that cannot simply be burned in. We can push them in more private places, though.

a lot of failure modes can be removed libc++abi and libunwind can and probably should be statically linked into the libc++

We no longer have issues with that, our build system is pretty reliable in that regard. LLVM is just one of the components, these things need to work robustly in general, and they do (with quite some effort).

You seem to be wary of using dynamic linking, we put some effort in it, now it works pretty good and always looks up things in the right place, and without ever hardcoding absolute paths anywhere, nor any install phase that "patches" the binaries. The unpacked directory can be moved wherever you want.

I am completely out of patience with distributing dynamically linked programs on Linux

You're thinking of some other solution, our solution does not use LD_LIBRARY_PATH and all the binaries reference each other in a robust way using `$ORIGIN`. Try:

    ./root/bin/python ./root/bin/revng artifact --help

But again, doing `source environment` is mostly for demo purposes, in the actual use case, you just do `./revng` and your environment is untouched.

We ship our Python, but you don't have to use it: you're supposed to just do ./revng (or interact over the network in daemon mode).

Our approach is: use whatever tool you like for scripting as long as it can parse our YAML project file, make changes to it, and then invoke `./revng artifact` (or interact with the daemon): https://docs.rev.ng/user-manual/model-tutorial/

Result: we get to use our Python version (the latest) and you get to use whatever language you like. Then we'll provide on pypi wrappers that help you with that and are compatible with large set of Python versions.

tl;dr Don't `source ./environment`, use `./revng`.

Thanks again for shipping, and I hope some of the above feedback is helpful!

I'm happy there's someone that cares about this :D

Our next big iteration of this might involve simplifying things a lot by adopting nix + mount namespace to make /nix/store available without root.

Maybe this is not the right place for discussing this, we can chat on our discord server if you'd like :)

Languages with a rich standard library and generating a lot of code for you usually need some love to get rid/represent idiomatically common patterns and to detect common data structures.

We haven't looked into it yet, but the automatic data structure recognition might help.

Frankly, Rust looks particularly scary: https://media.ccc.de/v/37c3-11684-rust_binary_analysis_featu...

Sure, in those cases we emit calls to C functions. The only thing we need to know is what registers are taken as input, what registers are output and what registers are preserved.

In QEMU parlance, these are helper functions, and they have actual implementations. But for decompilation purposes, you don't need to implement them. You just need to know how they interact with the registers.

Students shouldn't pay a dime. They are poor.

Our view is: the engine is 100% open source. The UI is available for free in the cloud for anyone experimenting, which we define as "I'm OK with leaving the project public".

Basically, the decompiler engine is Free Software, extensible and available for automation/scripting, while the UI is available for free for students/researchers and we can make a living out of professionals (i.e., when your company is paying for it).

That's unlikely, since we use QEMU as a lifter, which sometimes supports new instructions before they hit silicon.

However, I think we'll emit a call to some `noreturn` function. Basically we emit a call to `abort`.

Short answer: if you want to execute a program (maybe with some instrumentation, for fuzzing purposes) it's much easier to adopt a dynamic approach (i.e., emulation or virtualization). With static binary translation you can get better performance, but there's a lot of other things you need to get 100% right and that with a dynamic approach are a given (e.g., the CFG).

There's much more space of improvement in the field of analyzing code (as opposed to running it), so we're investing our energies there.

Then we're strong believers in integrating dynamic and static information, for instance see PageBuster: https://rev.ng/blog/pagebuster

But other than that, static binary translation is a feature of rev.ng in maintenance mode.

That's our goal. We used to use QtCreator as a basis for the UI, terrible idea.

Then we switched to VSCode, which happens to be able to run in the browser. So we added some magic kubernetes sauce and voilà, you got the cloud decompiler with exactly the same user experience as the fully standalone one.

We still need to perform some QA on collaboration, but basically works. One daemon, many clients. Very simple architecture.

I think we got inspiration to do this from a CTF where we were doing "collaboration" using IDA with multiple windows on a X session on a server with multiple cursors. Very cursed, but effective.

Decompilation is often the least important (and least reliable) part of IDA/Ghidra

This is something all people using decompilers say and sort of shows how low is trust towards decompilers. Expectations have always been rather low.

I've been there, but this does not have to be the case, the whole reason why we started rev.ng is to prove that expectations can be raised.

Apart from accuracy, which is difficult but engineering work, why don't decompilers emit syntactically valid C? Have you ever tried to re-compile code from any decompiler? It's a terrible experience.

rev.ng only emits valid C code, and we test it with a bunch of -Wall -Wextra:

https://github.com/revng/revng-c/blob/develop/share/revng-c/...

Other key topic: data structures. When reversing I spend half of the time renaming things and half of the time detecting data structures. The help I get from decompilers in latter is basically none.

rev.ng, by default, detects data structures on the whole binary, interprocedurally, including arrays. See the linked list example in the blog post. We also have plans to detect enums and other stuff.

Clearly we're not there yet, we still need to work on robustness, but our goal is to increase the confidence in decompilers and actually offer features that save time. Certain tools have made progress in improving the UI and the scripting experience, but there's other things to do beyond that.

I see this a bit like the transition from the phase in which C developers where using macros to ensure things were being inlined/unrolled to the phase where they stopped doing that because compilers got smart enough to the right thing and to do it much more effectively.

For scripting, our approach is to give you access to the project file (just a YAML file), and you can make changes from any scripting language you want. Everything the user can customize is in there, all the rest is deterministically produced from that file.

I really disliked the fact that you usually need to buy into the version of Python that $TOOL requires you to use, or the fact itself that you need to use a specific language.

Can parse YAML? You're mostly done.

The "project file" is what we call the model: https://docs.rev.ng/user-manual/model-tutorial/

For xrefs, CFG and the rest: we have all of that in the UI, but we also produce them in a rich way. For instance, when we emit disassembly and decompiled code, we actually emit plain text + HTML-like markup to provide metainformation for navigation (basically, xrefs) and highlighting. So you can use all that from any language that can parse HTML/XML. It's called PTML: https://docs.rev.ng/references/ptml/

For lifting: we use LLVM IR as our internal representation. This means that: 1) you don't have to learn an IR that no one else uses, 2) you can use off the shelf tools (e.g., KLEE for symbolic execution) but you can also use all the standard LLVM optimizations and analyses and 3) you can recompile it, but we're not into the binary translation business anymore.

In the past we were thinking to do something like this by hand. For instance, we detect induction variables, we could rename them into `i`.

However, nowadays, it seems pretty obvious that the right way to do this things is using LLMs.

This said, at this stage, we see ourselves as people building robust infrastructure. Once the infrastructure is there, using some off the shelf model to rename things or add comments is relatively easy.

Basically: we do the hard decompilation work that needs 100% accuracy, and then we can adopt LLMs for things that are OK to be approximate such as names, comments and the like.

Anyway, writing a script that renames stuff is pretty easy. Check out the docs: https://docs.rev.ng/user-manual/model-tutorial/

About the book, here's the full story: I was getting into compilers, but I was really struggling with the theory, the most famous books weren't doing it for me, and I felt really down.

Then I find this book, which seems very dense, but clear. So I ask my advisor if I could buy it and goes like "well, first check out the university library". I check it out and there's a copy, but... it's taken.

Working in the only group that was doing research on compilers I'm like "who dares do compilers stuff out of our group!?".

I go to the library:

Me: who has the book?

Library guy: can't tell you, privacy reasons.

Me: what's the third letter of its surname?

Library guy: Z

Me: what's the second letter of its name?

Library: I

Me: thanks.

I go here: https://www.deib.polimi.it/ita/personale-lista-alfabetica I found him.

Fast forward, we become friends and we start the company together.

Congrats on the launch.

Thanks! It was a lot of work.

The CTO mostly works on the backend of the decompiler, revng-c, which we just released:

https://github.com/revng/revng-c/commits/develop/

Eventually we'll merge the two repos.

Also, I develop stuff every day. For some reason GitHub is not picking up my user correctly.

Anyway, if this works, then I guess it's a lot of fun for them.

It is!

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.

architectural registers are always updated

In tiny code, the guest registers (global TCG variables) are stored in the host's registers until you either call an helper which can access the CPU state or you return (`git grep la_global_sync`). This is the reason why QEMU is not so terribly slow.

But after a check, this also happens when you access the guest memory address space! https://github.com/qemu/qemu/blob/master/include/tcg/tcg-opc... (TCG_OPF_SIDE_EFFECTS is what matters)

But still, in the end, it's the same problem. What QEMU does, can be done in LLVM too. You could probably be more efficient in LLVM by using the exception handling mechanism (invoke and friends) to only serialize back to memory when there's an actual exception, at the cost of higher register pressure. More or less what we do here: https://rev.ng/downloads/bar-2019-paper.pdf

I see your position, but I've to say that in 8 years of rev.ng we revised many many design choices we initially made, but not using LLVM was not one of them, so I can't agree.

Rolling your own IR is not hard, in fact, it's very easy (and sometimes we roll temporary IRs for specific purposes), but it's also true that most IRs look more or less the same. QEMU's tiny code and LLVM IR, for instance, are quite similar. What matters is the ecosystem around them, and the ecosystem around LLVM is really great.

Anyway, every Friday morning 11:00 CEST we have the rev.ng hour, our weekly internal technical meeting. It would be interesting to discuss what limitations you hit with LLVM that we did not hit and your concerns about efficiency of LLVM and MLIR.

We used to stream the rev.ng hour and we're in the process of going back to publish some talks every now and then. If you're interested, drop me an e-mail! :)

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.

every memory access can cause a synchronous signal (SIGSEGV/SIGBUS)

AFAIU you have all the same problems as soon as you translate more than one instruction at a time and allow merging them, which QEMU does, even if just at basic block level. IIRC post-SIGSEGV state is not 100% correct in QEMU, but I'd need to investigate some more.

We built a dynamic binary translator for a customer dealing with mainframes using ORC JIT where we translate large amounts of code, handle self-modifying code and caching things on disk (similar approach to the one you suggest). Compile time is a problem, but then we the performance results are impressive. Giving visibility over loops to LLVM helps a lot.

But the real reason why nothing like this is upstream is that it's difficult to get things upstream, it requires a lot of effort compared to putting together a PoC. :)

Running O2 optimizations sounds great in theory, but is often not too helpful in practice

I cannot stress how important it is to have at your disposal an alias analysis framework and analyses such as LazyValueInfo and ScalarEvolution. In fact, some whole key features of rev.ng are possible thanks to them. Either one (thinks) they're not need them or you have to reinvent the wheel. People think binary analysis is something special, it's not, just compilers. And there's really really a lot to learn from the design of LLVM.

Add with carry doesn't sound like a gigantic problem to me, given what you get in return. About vector instructions, a lot of autovectorization takes place in the mid-end and LLVM supports vector types, but I'm not sure if you're talking about them in input or in output.

If you really want to roll your own thing, one could at least use MLIR, where you can define your own operations but you reuse MLIR infrastructure, pass manager, DCE and much more. However, you'd lose the above mentioned passes in the early stages of the pipeline is too much of a loss.

As mentioned, we started facing the limitations of LLVM when you want sophisticated types (e.g., unions) and more and more high level concepts while you get close to C. That's why we're rolling our MLIR dialect, clift.

LLVM-IR is fairly heavy-weight and not particularly efficient

I guess it depends what's the comparison, but in our experience, it scales pretty pretty well.

But overall... no one wants to learn your custom IR, there's much more incentive in learning an (the most?) established IR, in particular for a lifter. If you use LLVM IR you get AddressSanitizer, CoverageSanitizer, KLEE, polly, libFuzzer, bindings, documentation and so much more.

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();
    }

    if (x > 3)
      goto label;

    switch (x) {
    case 0:
      do_0();
    case 1:
    label:
      do_default();
    case 2:
      do_2();
    case 3:
      do_3();
    }

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;

    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;

2) We don't deal with duplication, it's way less of a problem, usually. For deduplication, if it leads to gotos, we duplicate.

the binary code to LLVM IR uplifting loses a lot of context

Losing context is good in order to ensure you properly decoupled the frontend from the rest of the pipeline.

We don't even keep track of what a "call" instruction is, we re-detect it on the LLVM IR.

One reason you may want to preserve context is to let the user know where a specific piece of lifted code originated from. In order to preserve this information, we exploit LLVM's debugging metadata and it works pretty well. There's some loss there, but LLVM transformations strive to preserve it.

After all, imagine you have `add rax, 4; add rax, 4`, you'll want to optimize it to a +8 and you'll either have to decide if you want to associate your +8 operation with the first or the second instruction.

the binary code to LLVM IR uplifting loses a lot of [...] semantics information

Not sure what you mean here, we use QEMU as a lifter and that's very accurate in terms of semantics.

I'm not sure what MIR and Swift IR have to do with the discussion, those are higher level IRs for specific languages. LLVM is rather low level and it's language agnostic.

However, for going beyond lifting, i.e., decompilation, it's true that LLVM shows some significant limitations. That's why we're rolling our own MLIR dialect, but we can still benefit of all the MLIR/LLVM infrastructure, optimizations and analyses. We're not starting from scratch.

emulating pieces of the code sparsely to figure out indirect jumps and so on

It's hard to emulate without starting from the beginning. Maybe you're thinking about symbolic execution?

In any case, rev.ng does not emulate and does not do any symbolic execution: we have a data-flow analysis that detects destinations of indirect jumps and it's pretty scalable and effective. Example of things we handle: https://github.com/revng/revng-qa/blob/master/share/revng/te...

Here you can find some data: https://rev.ng/downloads/bar-2019-slides.pdf

Cool projects, but let me make two observations:

1. Writing a binary analysis tool is an enormous task. Before getting to the useful and new part, you need a lot of infrastructure (e.g., a scalable intermediate representation). Rolling your own infrastructure is not a great idea IMO, there are great compiler frameworks (LLVM, but GCC would work too) that provide you with a lot of tools to start with. We can literally run the LLVM -O2 optimization pipeline on our IR.

2. In binary analysis there's a trend to use SMT solvers. We absolutely do not, by design. They simply do not scale. Binary analysis theory is really just compiler theory. Have you ever seen a mainstream compiler use SMT solvers for the standard compilation pipeline? No, it does not scale. Depending on what you need to do, you go the old fashioned way and write a data-flow analysis that does what you need, instead of using an SMT solver that can solve much more complex problems but does not scale. At rev.ng, we're in love with Monotone Frameworks. If your analysis fits in the framework, it will run in linear time. It's more difficult than going "Z3 solve it for me", but it scales great. Suggested reading: https://link.springer.com/book/10.1007/978-3-662-03811-6

Don't get me wrong, there are use cases where using an SMT solver makes sense, for instance looking for bugs, but SMT solvers should be a last resource measure for tasks where you're OK with saying "OK, I didn't find anything in 10 minutes, let's bail out". But that's not the case for simply lifting and even decompiling a binary.

This said, I haven't been following closely the developments of rizin, but my comments are more on the general trend in binary analysis that I see.

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.