The project as a whole is released under the terms of the GNU General Public License, version 2. A copy of this license can be found in LICENSE.gpl.
Each individual file, unless otherwise noted, is released under the terms of the MIT License. A copy of this license can be found in LICENSE.mit.”
Does that paragraph about GPLv2 constitute a version of “unless otherwise noted”?
If so, why mention the MIT license at all?
If not, doesn’t that mean it effectively is dual licensed? If everything is GPLv2, and I take a single file, that’s still GPLv2, and if if have set of MIT licensed files and group them, the result still is MIT licensed.
(Browsing the code, all source files seem to have a MIT header, so, presumably, they mean this to beMIT licensed)
Also, it’s not “GPLv2 or later”, but I think you can take the MIT licensed files and rerelease them as GPLv3, if you’d want to (or is the attribution requirement a showstopper there?)
If you have a set of MIT files, and group them, the group is whatever you want it to be.
It just means someone else can take all the files and make something else with them, but they just can't redistribute the new project under the name revng, unless it conforms to gpl2.
> Each individual file, unless otherwise noted, is released under the terms of the MIT License. A copy of this license can be found in LICENSE.mit.
Worth . . . noting . . . that every file with license info says MIT; none say anything else. So the "unless otherwise noted" is purely future-proofing.
The qemu TCG parts that it presumably links to are GPLv2, so the combined project is GPLv2 by necessity[1]. I think that's all they're trying to get across.
[1]: apart from viral licenses being pretty much meaningless under EU copyright law
I think you could phrase that better. Maybe something like “This projects builds on GPLv2-licensed code, so the project is GPLv2-licensed. If you want to use our additions in isolation, you can choose to use them as either GPLv2 or MIT licensed”?
We wanted to have a demo on our website where you could upload your binary and run it in the browser recompiling to WASM. Feasible, but not a negligible amount of work.
About macOS: we can lift any binary for any platform, but we can recompile to an executable only programs for Linux. The reason for this is that the QEMU user mode only supports running Linux on Linux.
It would be, in principle, possible to add support for macOS user mode (there's a half dead FreeBSD user mode), but it's quite some work.
Windows would be almost impossible: in Windows, the compatibility layer for user applications (i.e., the boundary where Microsoft tells you that things will stay the same in the future) is not the boundary between the user space and the kernel (as it is in Linux) but the system DLLs. So QEMU should become KERNEL32.dll-aware, which would be weird and very different from the current design of QEMU user mode.
This said, if you have a dynamic binary that does not perform any syscall (if not through other dynamic libraries), something can be worked out.
Wonder if you could use this with binfmt and a cache to create a kind of super-Rosetta for Linux. Any Linux binary not for the host architecture will be translated, and translated binaries are cached somewhere by a hash of the original binary so the translation only has to happen once. All transparent to the user.
Just like Rosetta, that will be an incomplete solution, without also including a JIT.
Nothing stops a binary from generating native code at runtime, loading it from a random file, and many such things. A static recompiler is not possible to write such that it covers ALL the possibilities. You need a runtime component
True but does not seem to make it not worth doing.
Incomplete? OK but how incomplete really? I have never written anything myself that relied on generating and then executing machine code at run time. Sure it exists, but so what if one app out of everything I ever use turns out to do it? Or even say ten?
Complete but only by dint of including a jit? OK but does that imply there might as well just be the jit alone? I don't think so. The general concept of caching has been well proven to be overwhelmingly worth it in pretty much any context it's possible.
If you ran the transpiled binaries with a security flag prohibiting execution of generated code, that would cause anything with a jit to crash neatly and possibly with an informative error message. Docs for this system would have to be clear that jits will not work and must be native.
I think Linux has some kind of no-exec flag like that. I know macOS does.
that would not save you from someone doing things like:
((void (*)(void))(((uintptr_t)&myfunc) + 1))();
and there you go - on x86 this could plausibly be a way to obfuscate code since it has variable-length instrs. And your static analysis may not catch this. This does not require writeable executable pages or JIT.
Hell, i can receive a uint32 from the network, cast to a func pointer, and jump to it. And for all you know, my protocol relies on a lack of ASLR and sends me a valid entry point addr in my executable, which will have changed in the translation you do. (Fun story: long ago, AIM's anti-protocol-cloning code did that - server would send a VA and ask for a few bytes at that VA. Unless you had a current copy of the aim executable in memory running you had no way to correctly reply)
The long tail of valid but freaky shit is ....very long, and disallowing W&X pages will not protect you from it all
Correct, your incremented function pointer won't be caught -- but now we're really getting down to the parts-per-million of programs that use this. Demoscene code, sometimes, maybe?
I would say W^X protection will protect you from all non-adversarial programs.
However, the code we emit is faster than the one emitted by QEMU.
We have a secret plan to use LLVM in QEMU as a tier 2 JIT engine to optimize hot code paths more aggressively.
This has already been done, but never upstreamed.
Adding an on-disk cache would also be quite useful.
> [LLVM in QEMU] has already been done, but never upstreamed.
Yeah, that's a long history, and it never worked great, the architectures are too different. LLVM is great for compiling functions while QEMU compiles basic blocks, which is somewhat required for correctness. LLVM for binary translation requires longer superblocks (HQEMU) or functions (Instrew).
I don't see _correct_ binary translation with LLVM as viable anytime soon, though: every memory access can cause a synchronous signal (SIGSEGV/SIGBUS), and I'd expect recovering the full register state at the prior instruction boundary from the LLVM-compiled code to come at severe performance penalties.
> Adding an on-disk cache would also be quite useful.
I implemented a persistent cache in Instrew to work around LLVM's high compile times. Cache access is done by decoding the code-to-be-translated (very fast) and using a hash of that code for lookup. So shared libraries and even the same code in different binaries will hit the cache, regardless of their address or path name.
If translation is fast (QEMU/TCG), caching is probably not very useful, though.
> 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. :)
> allow merging them, which QEMU does, even if just at basic block level. IIRC post-SIGSEGV state is not 100% correct in QEMU
A quick and very limited testing shows that all registers and even status flags are correct in the ucontext in the signal handler. Glancing at the source code, TCG optimizations (e.g., liveness analysis) primarily apply to temporaries, but the architectural registers are always updated. That's also why QEMU is so slow (and easy to beat in papers, which very often disregard strict correctness).
Function-level lifting to LLVM gives massive performance improvements, but sacrifices correctness w.r.t. signals (synchronous and also asynchronous, unless you add a check for pending signals to every loop, or somehow else recover the state in not-too-distant time).
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 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 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;
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.
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
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
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.
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.
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.
Rizin[1] is also able to uplift native code to the new RzIL, which is based on the BAP Core Theory[2] and is essentially an extension of SMT theories of bitvectors, bitvector-indexed arrays of bitvectors and effects[3].
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.
> compiler frameworks (LLVM, but GCC would work too) that provide you with a lot of tools to start with.
While I agree with this, the binary code to LLVM IR uplifting loses a lot of context and semantics information because LLVM IR was designed to do precisely the opposite. Moreover, the increasing popularity of using "middle level" IRs in LLVM-based compilers, like MIR and Swift IR, makes the "distance" between code and the IR representation even bigger. This is why IRs specifically designed to tackle RE tasks would perform better (RzIL and any relatively modern intermediate representation).
> They simply do not scale.
I agree with this notion, but you don't need to "solve" a whole program; it's impossible for any real-world software; you can selectively pick places to do so. Currently, existing binary analysis software already does that, but usually in a more "manual" way, e.g., by emulating pieces of the code sparsely to figure out indirect jumps and so on.
> 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...
> Rolling your own infrastructure is not a great idea IMO
For the start, I'd agree, but as soon as you want to do non-trivial things, I don't think that standard compiler IRs (e.g., LLVM) are a good way for binary analysis. (POV: been there, done that.) The time investment in fighting the existing IR quickly becomes larger than just writing a custom IR, which is not _that_ much effort. Running O2 optimizations sounds great in theory, but is often not too helpful in practice.
LLVM is clearly intended to provide a (not too large) set of semantics that can be mapped easily to different architectures. This is great for compilation, but not for the other direction, as even simple things like add-with-carry end up being multiple non-trivial instructions which aren't handled by existing optimization patterns. The same goes for vector instructions, where many patterns are encoded in the back-ends and not in the IR passes. So you end up writing custom passes fairly quickly, but still fight against an IR that doesn't allow you to express the things you'd like to have.
In the long run, a custom IR allows for a much more idiomatic code representation and more flexible analyses; not to mention that LLVM-IR is fairly heavy-weight and not particularly efficient. If I were to write another binary translator (I wrote Instrew/Rellume based on LLVM), I would definitely not choose LLVM.
I completely agree on the SMT part. I experimented with SMT, but standard data flow analysis suffice 90% of the time and are much more efficient and predictable.
> 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.
> People think binary analysis is something special, it's not, just compilers.
I (conceptually) agree! But there's different sorts of compilers, and they have different requirements, which (should) materialize in the code representation. An offline C/C++ compiler has different requirements than a JIT JavaScript compiler, and so their architecture is very different. The IR should be express the relevant operations/data structures well and should easily support the analyses/transformations. If LLVM is a good fit for you, that's great. But in many cases, it's not.
I've been bitten from being warned about not writing my own IR (effort concerns), and in hindsight, it would've been the much easier way, both for low-level and high-level transformations. IMHO, people should not be afraid to roll their own IR and make it a good fit for their use case.
> one could at least use MLIR
MLIR is a nice idea (and great for selling/publishing). I find the implementation to be somewhat lacking and constraining, difficult to work with, and not particularly efficient.
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! :)
We don't follow radare2 development closely, to be honest. Instead, we prefer to focus on our own roadmap, which roughly is migrating to a new RzIL instead of ESIL in the context of the discussion, improving UX in both Rizin CLI and Cutter GUI, also providing consistent library API for every Rizin feature (before the code was riddled with command calls inside, for example). And it's not a superset of r2 features since some were actually removed because they are out of the scope as we feel it - for example, "mount" commands to mount the filesystems. We don't have the time and resources to maintain numerous filesystems, and this feature can be better implemented in other tools. We focus on the program analysis and raw data reverse engineering instead. As well as improving support for already existing but undervalued before architectures that are common in specific niches, like Hexagon (QDSP) and Tricore - many months of coding and manual testing were put to make Rizin/Cutter usable for reversing code of these architectures, and more will come.
57 comments
[ 4.5 ms ] story [ 106 ms ] thread“Licensing information
Copyright (c) 2015-2017 Alessandro Di Federico <ale@clearmind.me>
Copyright (c) 2017-2020 rev.ng Labs Srl <info@rev.ng>
The project as a whole is released under the terms of the GNU General Public License, version 2. A copy of this license can be found in LICENSE.gpl.
Each individual file, unless otherwise noted, is released under the terms of the MIT License. A copy of this license can be found in LICENSE.mit.”
Does that paragraph about GPLv2 constitute a version of “unless otherwise noted”?
If so, why mention the MIT license at all?
If not, doesn’t that mean it effectively is dual licensed? If everything is GPLv2, and I take a single file, that’s still GPLv2, and if if have set of MIT licensed files and group them, the result still is MIT licensed.
(Browsing the code, all source files seem to have a MIT header, so, presumably, they mean this to beMIT licensed)
Also, it’s not “GPLv2 or later”, but I think you can take the MIT licensed files and rerelease them as GPLv3, if you’d want to (or is the attribution requirement a showstopper there?)
It just means someone else can take all the files and make something else with them, but they just can't redistribute the new project under the name revng, unless it conforms to gpl2.
Worth . . . noting . . . that every file with license info says MIT; none say anything else. So the "unless otherwise noted" is purely future-proofing.
[1]: apart from viral licenses being pretty much meaningless under EU copyright law
QEMU does something similar:
I think you could phrase that better. Maybe something like “This projects builds on GPLv2-licensed code, so the project is GPLv2-licensed. If you want to use our additions in isolation, you can choose to use them as either GPLv2 or MIT licensed”?
For the wasm runtime, we planned to use this: https://browsix.org/
About macOS: we can lift any binary for any platform, but we can recompile to an executable only programs for Linux. The reason for this is that the QEMU user mode only supports running Linux on Linux.
It would be, in principle, possible to add support for macOS user mode (there's a half dead FreeBSD user mode), but it's quite some work.
Windows would be almost impossible: in Windows, the compatibility layer for user applications (i.e., the boundary where Microsoft tells you that things will stay the same in the future) is not the boundary between the user space and the kernel (as it is in Linux) but the system DLLs. So QEMU should become KERNEL32.dll-aware, which would be weird and very different from the current design of QEMU user mode.
This said, if you have a dynamic binary that does not perform any syscall (if not through other dynamic libraries), something can be worked out.
Nothing stops a binary from generating native code at runtime, loading it from a random file, and many such things. A static recompiler is not possible to write such that it covers ALL the possibilities. You need a runtime component
Incomplete? OK but how incomplete really? I have never written anything myself that relied on generating and then executing machine code at run time. Sure it exists, but so what if one app out of everything I ever use turns out to do it? Or even say ten?
Complete but only by dint of including a jit? OK but does that imply there might as well just be the jit alone? I don't think so. The general concept of caching has been well proven to be overwhelmingly worth it in pretty much any context it's possible.
I think Linux has some kind of no-exec flag like that. I know macOS does.
Hell, i can receive a uint32 from the network, cast to a func pointer, and jump to it. And for all you know, my protocol relies on a lack of ASLR and sends me a valid entry point addr in my executable, which will have changed in the translation you do. (Fun story: long ago, AIM's anti-protocol-cloning code did that - server would send a VA and ask for a few bytes at that VA. Unless you had a current copy of the aim executable in memory running you had no way to correctly reply)
The long tail of valid but freaky shit is ....very long, and disallowing W&X pages will not protect you from it all
I would say W^X protection will protect you from all non-adversarial programs.
However, the code we emit is faster than the one emitted by QEMU. We have a secret plan to use LLVM in QEMU as a tier 2 JIT engine to optimize hot code paths more aggressively. This has already been done, but never upstreamed.
Adding an on-disk cache would also be quite useful.
Assume you're referring to hqemu http://csl.iis.sinica.edu.tw/hqemu/
> Adding an on-disk cache would also be quite useful.
+100
Yeah, that's a long history, and it never worked great, the architectures are too different. LLVM is great for compiling functions while QEMU compiles basic blocks, which is somewhat required for correctness. LLVM for binary translation requires longer superblocks (HQEMU) or functions (Instrew).
I don't see _correct_ binary translation with LLVM as viable anytime soon, though: every memory access can cause a synchronous signal (SIGSEGV/SIGBUS), and I'd expect recovering the full register state at the prior instruction boundary from the LLVM-compiled code to come at severe performance penalties.
> Adding an on-disk cache would also be quite useful.
I implemented a persistent cache in Instrew to work around LLVM's high compile times. Cache access is done by decoding the code-to-be-translated (very fast) and using a hash of that code for lookup. So shared libraries and even the same code in different binaries will hit the cache, regardless of their address or path name.
If translation is fast (QEMU/TCG), caching is probably not very useful, though.
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. :)
A quick and very limited testing shows that all registers and even status flags are correct in the ucontext in the signal handler. Glancing at the source code, TCG optimizations (e.g., liveness analysis) primarily apply to temporaries, but the architectural registers are always updated. That's also why QEMU is so slow (and easy to beat in papers, which very often disregard strict correctness).
Function-level lifting to LLVM gives massive performance improvements, but sacrifices correctness w.r.t. signals (synchronous and also asynchronous, unless you add a check for pending signals to every loop, or somehow else recover the state in not-too-distant time).
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
0: https://github.com/lifting-bits/remill
1: https://github.com/aengelke/rellume
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
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.
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 :)
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:
By "inlining" the gotos and doing some trivial optimizations we'd get: 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.
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.
Does this lifter have a similar implementation, or will a "add rax, 1" be lifted to something like "register1 += 1"?
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 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.
video https://youtu.be/5CbuU4KwBCE?si=eUN_UGr7cjat3P8U
slides https://www.llvm.org/devmtg/2016-11/Slides/DiFederico-rev.ng...
[1] https://rizin.re/
[2] https://binaryanalysisplatform.github.io/bap/api/master/bap-...
[3] https://github.com/rizinorg/rizin/blob/dev/doc/rzil.md
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.
While I agree with this, the binary code to LLVM IR uplifting loses a lot of context and semantics information because LLVM IR was designed to do precisely the opposite. Moreover, the increasing popularity of using "middle level" IRs in LLVM-based compilers, like MIR and Swift IR, makes the "distance" between code and the IR representation even bigger. This is why IRs specifically designed to tackle RE tasks would perform better (RzIL and any relatively modern intermediate representation).
> They simply do not scale.
I agree with this notion, but you don't need to "solve" a whole program; it's impossible for any real-world software; you can selectively pick places to do so. Currently, existing binary analysis software already does that, but usually in a more "manual" way, e.g., by emulating pieces of the code sparsely to figure out indirect jumps and so on.
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...
For the start, I'd agree, but as soon as you want to do non-trivial things, I don't think that standard compiler IRs (e.g., LLVM) are a good way for binary analysis. (POV: been there, done that.) The time investment in fighting the existing IR quickly becomes larger than just writing a custom IR, which is not _that_ much effort. Running O2 optimizations sounds great in theory, but is often not too helpful in practice.
LLVM is clearly intended to provide a (not too large) set of semantics that can be mapped easily to different architectures. This is great for compilation, but not for the other direction, as even simple things like add-with-carry end up being multiple non-trivial instructions which aren't handled by existing optimization patterns. The same goes for vector instructions, where many patterns are encoded in the back-ends and not in the IR passes. So you end up writing custom passes fairly quickly, but still fight against an IR that doesn't allow you to express the things you'd like to have.
In the long run, a custom IR allows for a much more idiomatic code representation and more flexible analyses; not to mention that LLVM-IR is fairly heavy-weight and not particularly efficient. If I were to write another binary translator (I wrote Instrew/Rellume based on LLVM), I would definitely not choose LLVM.
I completely agree on the SMT part. I experimented with SMT, but standard data flow analysis suffice 90% of the time and are much more efficient and predictable.
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.
I (conceptually) agree! But there's different sorts of compilers, and they have different requirements, which (should) materialize in the code representation. An offline C/C++ compiler has different requirements than a JIT JavaScript compiler, and so their architecture is very different. The IR should be express the relevant operations/data structures well and should easily support the analyses/transformations. If LLVM is a good fit for you, that's great. But in many cases, it's not.
I've been bitten from being warned about not writing my own IR (effort concerns), and in hindsight, it would've been the much easier way, both for low-level and high-level transformations. IMHO, people should not be afraid to roll their own IR and make it a good fit for their use case.
> one could at least use MLIR
MLIR is a nice idea (and great for selling/publishing). I find the implementation to be somewhat lacking and constraining, difficult to work with, and not particularly efficient.
> no one wants to learn your custom IR
That's a problem, but there's no silver bullet.
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! :)