How to write a C decompiler using AI?

Question

I would like to learn more about whether it is possible and how to write a program that decompiles executable binary (an object file) to the C source. I'm not asking exactly 'how', but rather how this can be achieved.

Given the following hello.c file (as example):

#include <stdio.h>
int main() {
  printf("Hello World!");
}

Then after compilation (gcc hello.c) I've got the binary file like:

$ hexdump -C a.out | head
00000000  cf fa ed fe 07 00 00 01  03 00 00 80 02 00 00 00  |................|
00000010  0f 00 00 00 b0 04 00 00  85 00 20 00 00 00 00 00  |.......... .....|
00000020  19 00 00 00 48 00 00 00  5f 5f 50 41 47 45 5a 45  |....H...__PAGEZE|
00000030  52 4f 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |RO..............|
00000040  00 00 00 00 01 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000060  00 00 00 00 00 00 00 00  19 00 00 00 d8 01 00 00  |................|
00000070  5f 5f 54 45 58 54 00 00  00 00 00 00 00 00 00 00  |__TEXT..........|
$ wc -c hello.c a.out 
  60 hello.c
8432 a.out

For the learning dataset, I assume I'll have to have thousands of source code files along with its binary representation, so the algorithm can learn about moving parts on certain changes.

How would you tackle this problem?

My concerns (and sub-questions) are:

• Does my algorithm need to be aware of the header file, or it's "smart" enough to figure it out?

• If it needs to know about the header, how do I tell my algorithm "here is the header file"?

• What should be input/output mapping (whether some section to section or file to file)?

• Do I need to divide my source code into some sections?

• Do I need to know exactly how decompilers work or AI can figure it out for me?

• Should I have two neural networks, one for header, another for body it-self?

• or more separate neural networks, each one for each logical component (e.g. byte->C tag, etc.)

Answer 1

In-between your input and desired output, there's obviously a huge space to search. The more relevant domain information you include as features, the higher chance that the Deep Learning (DL) algorithm can find the desired mapping.

At this early stage in DL research, there aren't so many rules of thumb to tell you what features to explicitly encode - not least because it depends on the size of your training corpus. My suggestion would be: obtain (or generate) a large corpus of C code, train on that with the most naive feature representation that you think might work, then repeatedly gather data and add more feature preprocessing as necessary.

This following paper describes a DL approach to what is almost the 'reverse problem' to yours - generating the source code for a program described in natural language.

I found the strength of the results reported in this paper surprising, but it does give me some hope that what you are asking might be possible.

Answer 2

Software Reverse Engineering is one of my hobby.

First things first: forget about headers. All information about headers and separate C file is gone.

You're missing some crucial step, IMHO.

• Compilation creates one or multiple object files (.o), then the linker creates an executable.

• You should work from disassembled code. The disassembler works pretty well with some exceptions (self-modifying code, self-extracting executable, various obfuscation techniques) and will take care of a lot of work for you: identifying various sections, finding functions, guessing (fairly accurately) the calling convention.

• Then the compiler optimization will mess up your code in a very clever way and some part of your original code will never ever be seen again (hey, look, your 200 lines of bugged code always return 0 anyway so I'll just replace them with "xor eax, eax").

• Sometimes, it's fine, and sometimes it produces unreadable C code (vectorizations that have no C equivalent and will be decompiled into hundreds of lines of intrinsic instead of a fine readable "for" loop).

• I'm not done yet. You also have exceptions and interrupts, structures, union, function pointers, function inlining, threading, system call and signals, loop unrolling, etc.

Going down (from human-readable to binary) is relatively easy compared to going up (decompilation) because so much information is lost during the compilation process.

My best bet would be to have a bunch of disassembled function produced by a disassembler and produce an LLVM intermediate representation using your AI, then compare it with the LLVM IR produced by Clang (clang -S -emit-llvm foo.c).

An infinite quantity of C code can produce the exact same code. Therefore, I think it's meaningless to make an AI read C code for the purpose of decompilation: the information is lost forever.

Commercial and Open/Free decompilers do not produce C code either, they produce some kind of pseudo-C full of errors, missing code, or code even less readable than the ASM.

The following code :

int main() {
    int toto = 0x0000BEEF;
    int titi = 0xDEAD0000;
    toto = toto | titi;
    return toto;
}

produces this:

int __cdecl main(int argc, const char **argv, const char **envp)
{
     return -559038737;
}

And this is the disassembled version:

mov     eax, 0DEADBEEFh
retn

Plus a few thousands lines of assembly that are unrelated to your code but are needed to make the program work.

You can't go back and you have no way of knowing this is the exact same code unless

1. you can do static analysis (very easy in this case, but absurdly difficult in the real world)

2. or compare the IR or ASM produced by both code with the same compiler with the same options on the same architecture and operating system.