How do you optimise AST's or convert them to a real language

Question

I have been interested in automatic vulnerability assessment and decompilation of code for a while now. And as a result I have been building parsers in Python that reads a bin, disassembles it instruction by instruction while tracing the execution (the way IDA does it).

I have been tracing the polluted registers (polluted as in user input) to check when such registers allow us to setup a call or a jump.

This research has grown to the point, where I want to transform it to a decompiler. I had a look at boomerang and other open source decompilers. I have also had a quick peek inside the dragon book (I don't own it). I would like to hear what you guys think about this idea. Below is my outline:

1. Open the binary file to decompile.
2. Detect a filetype (PE or ELF) to select the EP and memory layout.
3. Jump to the EP and follow execution path of the code while disassembling. I use udis86 for it. This execution is in a libemu kind of way.
4. Parse the resulting assembly an middle language. To get simpler instructions, (e.g. always remove things like SHL EAX, 0x02 and change those things to MUL instructions).
5. Parse it into a Abstract Syntax Tree.
6. Optimize the AST (although, I have no idea how).
7. Transform the AST to something that looks like C.

I am having issues with the last 2 steps. How does someone parse AST to a real language or something that looks like it? How do you optimize ASTs? Are there build C or Python libraries to accomplish it?

Answer 1

The classic work on the decompilation is Cristina Cifuentes' PhD thesis "Reverse Compilation Techniques". She describes generation of C code in Chapter 7.

The author of the REC decompiler also has a nice summary about the decompilation process, though it's more informal:

http://www.backerstreet.com/decompiler/introduction.htm

For completeness, here's Ilfak's whitepaper on the Hex-Rays decompiler, though he glances over this specific issue, only mentioning that it's "Very straightforward and easy" :):

http://www.hex-rays.com/products/ida/support/ppt/decompilers_and_beyond_white_paper.pdf