Why there are not any disassemblers that can generate re-assemblable asm code?

Question

I am struggling on this problem for around three months:

How to use disassemblers (IDA Pro and others...) to generate re-assemblable asm code and assemble it back

My experience is that:

1. There is NO tool that can generate re-assemblable asm code on 32-bit x86.

2. You need to adjust/heuristically modify the asm code created by IDA Pro to make it re-assemblable.

3. It is doable to automatically adjust/heuristically modify process on benign program (one without obfuscation).

4. It is very tedious, and VS compiled PE binary is much more complex than GCC compiled ELF binary.

So my questions are:

1. Why there are not any disassemblers that can generate re-assemblable asm code targeting on benign program (one without obfuscation) ?

2. If I want to implement such a tool (without the help of IDA Pro, sketching from the beginning), is it possible?

3. Are there any other concerns related to this that I may have missed?

Answer 1

Because this is really hard to do.

To elaborate:

You'll also need to extract things that are not code. Think of import tables, export tables, strings and other data.

When you write code, this is only one part of the program. The other part is the Compiler Optimizations and data section. This makes it almost impossible to create re-compilable assembly. If you want to edit a program on assembly level I'd recommend to use windbg and LordPE.

Answer 2

This is from the IDA Pro book, but even IDA, as good as it is, is still in the end making guesses. The answers here are from "The IDA Pro Book" by Chris Eagle.

1. "Why there are not any disassemblers that can generate re-assemblable asm code targeting on benign program (one without obfuscation) ?"

The compilation process is lossy.

At the machine language level there are no variable or function names, and variable type information can be determined only by how the data is used rather than explicit type declarations. When you observe 32 bits of data being transferred, you’ll need to do some investigative work to determine whether those 32 bits represent an integer, a 32-bit floating point value, or a 32-bit pointer.

Compilation is a many-to-many operation.

This means that a source program can be translated to assembly language in many different ways, and machine language can be translated back to source in many different ways. As a result, it is quite common that compiling a file and immediately decompiling it may yield a vastly different source file from the one that was input. Decompilers are very language and library dependent. Processing a binary produced by a Delphi compiler with a decompiler designed to generate C code can yield very strange results. Similarly, feeding a compiled Windows binary through a decompiler that has no knowledge of the Windows programming API may not yield anything useful.

Basically, at this point it still requires human judgment. The best analogy I've heard is that compiling a binary from source is like computing a Hash.

1. "If I want to implement such a tool (without the help of IDA Pro, sketching from the beginning), is it possible?"

This sounds to me like an interesting theoretical research question: Can compilation truly be viewed as generating a hash signature? My gut says "Yes." The math would be terribly intricate, and would probably have to be done with a provable language. We typically use hashes because they aren't easy to reverse engineer. However you can still attack hashes using things like rainbow tables, so there's one mega-project to consider. My instinct tells me that rainbow tables on all possible binaries is NP-Complete.

Also consider that determining data types kinda requires human judgment, and we still aren't terribly good at automating THAT kind of intelligence. Is it possible? Maybe. There's a reason why smart people still make tools like IDA.

1. "Are there any other concerns related to this that I may have missed?"

I'm new to disassembly, so I'll leave that to the big boys, but hopefully at least I answered the question on why its so difficult to do what you ask.

Eagle, Chris (2011-06-16). The IDA Pro Book: The Unofficial Guide to the World's Most Popular Disassembler (Kindle Locations 151-152). No Starch Press. Kindle Edition.

Answer 3

Your question is very interesting, though, not really new.

Many people already use what we call binary rewriting for profiling purposes. For example DynInst & MAQAO do that to profile applications in order to locate bottlenecks in basic blocks. Now the question you'll probably be asking yourself is how is it done ? Simple. Most available disassemblers like objdump, objconv, IDA, etc. work in standalone mode and usually print an instruction on disassembly, but others like udis86 & distorm offer an API to access the disassembled code in addition to being available in standalone mode. But, what DynInst, MAQAO, and most binary rewriting tools do is disassemble a binary file and insert probes wherever it is appropriate in the data structure before reassembling the binary. Thus all necessary changes related to addresses, branches, context saving, and so on are handled properly before reassembly.

What you must know is that it is extremely hard to write such tools. The first challenge is to write a reliable disassembler. This of course implies choosing a disassembly algorithm (linear sweep vs. recursive traversal), separating the instructions from the data (they can be mixed - shellcodes for example), and so on. Then comes the second challenge, patching the disassembled code. This is extremely tricky and I'll point out this document which should be of great help : http://www.maqao.org/publications/techreports/madras_techreport.pdf. It has been written by the author of the disassembler used in MAQAO (MADRAS - Multi Architecture Disassembler Rewriter and Assembler). The interesting part about this documents is the references (over 50 and extremely helpful) and the appendices which describe the algorithms used.

Though I'm not really acquainted with neither MAQAO nor DynInst I would recommend you checking publications around them (documentation, scientific papers, ...). I would also recommend you checking PEBIL (PMaCs Efficient Binary Instrumentation Toolkit), Intel's PIN, Valgrind, PLTO, Elfsh/ERESI, and Etch.

Most of these tools perform binary rewriting & patching extensively and I believe are good examples of how binary rewriting can be approached.

I hope my answer will help you find what you were looking for.

Answer 4

By far, the established method for binary rewriting is dynamic rewriting where the binary is rewritten while being run on real inputs. Think of instrumentation tools like PIN, DynamoRIO and Dyninst and also binary translators like qemu.

Static rewriting tools have a fundamental challenge compared to dynamic rewriting which is precise Control Flow Graph recovery. That is, for each basic block in the binary we need to know the set of possible targets of its jump instruction. The difficulty is that binaries have many indirect jump instructions. For example, if we face a basic block that ends with bx r3 then we need to have a precise and reliable Value Set Analysis (VSA) that can tell us the possible values that r3 can take at run-time. Unfortunately, such analysis is, generally, undecidable. However, well-behaving compilers produce binaries that are structured somehow which is a fact that can be useful to a large extent.

Note that the solving CFG recovery problem would allow us to solve the code/data separation problem as a by product. That is, recursive descent disassembly would allow us in that case to perfectly seperate code from data in the code byte stream.

I can refer here to the following paper introduced in last year's USENIX Security:

Shuai Wang, Pei Wang, Dinghao Wu: Reassembleable Disassembling. USENIX Security 2015: 627-642

Their tool Uroboros is not open source. It's based on iterative linear sweep disassembly using objdump. The disassembly technique itself is discussed in an earlier paper. Nonetheless, it provides interesting techniques for static binary rewriting that actually works (or at least that is their claim). They even rewrite the same binary multiple times without breaking it. Finally, note that static binary rewriting is largely inapplicable to binaries with run-time code generation.

Update:

It seems like many of the shortcomings of Uroboros has been addressed in Ramblr which is discussed here:

Wang et. al. "Ramblr: Making Reassembly Great Again", Proceedings of the Network and Distributed System Security Symposium (NDSS'17). 2017

Particularly, they mention that their reassembled binaries have no execution overhead or size expansion.

Answer 5

Some systems use a simple executable format which is linked by combining the instructions and defined data contained in the processed assembly files, in a specified sequence; the linker will apply address fix-ups, but otherwise the contents of the output executable will be exactly what the programmer specified--nothing more; nothing less. The old MS-DOS .COM file format was like that, and so it's possible for a disassembler to take a COM file and produce an file which, when assembled and linked, will yield a bit-identical file (the disassembly may have to use data directives for anything it doesn't understand, or for any instructions which might compile to something other than the bit pattern than appears in the file, but any executable-file bytes could be created using define-byte directives if nothing else.

Other systems, however, use linkers which are more sophisticated and have to generate additional information which gets stored within the file. It's possible that building the same source file with different versions of the tools may yield different binary files. In general, when doing a disassemble-patch-reassemble sequence, one would strive to minimize the amount of code whose address changes. If code stores the address of a function somewhere but the disassembler doesn't realize it's a function address rather than a constant, the only way the code will work is if the function stays at the same address. Unfortunately, there's no way for an object file which is compatible with MS-DOS or Windows build tools to specify where things should be located. When the code was originally compiled or assembled, the linker would be free to put the function anywhere and would update the "constant" function address appropriately. When processing disassembled code, there's no way to ensure that the function stays at the old address, nor of having all addresses which depend upon it will get updated if it moves.