7

After writing my own disassembler, I am now looking to making its assembly listing more human readable, e.g. from an (artificial) example

push    ebp
mov     ebp, esp
sub     esp, 10h
mov     eax, dword ptr [55431824h]
imul    eax, dword ptr [ebp+8]
add     eax, dword ptr [ebp+0ch]
mov     dword ptr [ebp-4], eax
mov     eax, dword ptr [ebp-4]
leave
ret     10h

via (> marks an auto-recognized prologue/epilogue):

>push    ebp
>mov     ebp, esp
>sub     esp, 10h

 mov     eax, dword ptr [_global_55431824]
 imul    eax, dword ptr [arg_0]
 add     eax, dword ptr [arg_4]
 mov     dword ptr [local_4], eax
 mov     eax, dword ptr [local_4]

>leave
>ret     10h

towards

eax = 10
eax *= arg_0
eax += arg_4
local_4 = eax
eax = local_4
return

At this point, each pseudo instruction is still tied to its original disassembled representation. When printing out, I can scan for certain sequences and so I replace the first two lines with

eax = 10 * arg_0

and then just skip printing the next line. However, there is a limit to how far I can get with that. Concatenating the next operation, which would lead to

eax = 10 * arg_0 + arg_4

requires to look ahead two instructions, and would only work for this specific combination of mov, imul, and add, while assuring the same destination register is still targeted and the intermediate instructions have no lasting effect on other registers.

The goal is to end up with something like this:

local_4 = 10 * arg_0 + arg_4
eax = local_4
return

where obviously eax is specifically assigned a value before a return, so the last line can be

return eax

and finally the entire construction can be collapsed into

return 10 * arg_0 + arg_4

(which is very close to what I started with in the original trivial C program). I am struggling with the internal representation of composite lines such as the last one. The otherwise very reliable decompiler page backerstreet.com/creating_statements casually switches between raw assembler and C-like compound statements:

if(!expr1 && !expr2)
  ...

without explaining how this intermediate step is stored in memory and can create the output string.

What type of intermediate storage form should I be looking at, which (a) can be constructed from the original disassembled instructions, (b) can have its elements combined and rearranged, and (c) can be translated into human-readable output such as the last line?

It may be worth mentioning that I am not aiming to create the Definitive Universal Decompiler :) My test input was compiled with an ancient version (most likely pre-1993) of Delphi Pascal, but while its assembly is not really optimized and fairly readable to begin with, I'd still like to go the extra mile and make my computer do what it does best and make it yet easier to understand the code.


A longer real world example

Below is some actual disassembly. The basic block number is followed by a dominator bit set (the loops hex number; I generate them but have not used that data yet). The ENTRY and EXIT numbers are to basic blocks again and used to generate a .dot view of the function.

; ## BLOCK 0; loops: 01; EXIT to 1, 4
401966A8    (  0)  8B 15 42201590       mov     edx,dword ptr [42201590]
401966AE    (  0)  8B 12                mov     edx,dword ptr [edx]
401966B0    (  0)  80 BA 39 01 00 00 02 cmp     byte ptr [edx+139h],2
401966B7    (  0)  75 11                jnz     label_4

; ## BLOCK 1; loops: 03; ENTER from 0; EXIT to 2, 4
401966B9    (  0)  83 78 24 02          cmp     dword ptr [eax+24h],2
401966BD    (  0)  7D 0B                jge     label_4

; ## BLOCK 2; loops: 07; ENTER from 1; EXIT to 3=RET
401966BF    (  0)  BA 02 00 00 00       mov     edx,2
401966C4    (  0)  2B 50 24             sub     edx,dword ptr [eax+24h]
401966C7    (  0)  8B C2                mov     eax,edx

; ## BLOCK 3 (epilog); loops: 0F; ENTER from 2
401966C9          >C3                   retn    

; ## BLOCK 4; loops: 11; ENTER from 0, 1; EXIT to 5, 7
                        label_4:
401966CA    (  0)  8B 15 42201590       mov     edx,dword ptr [42201590]
401966D0    (  0)  8B 12                mov     edx,dword ptr [edx]
401966D2    (  0)  80 BA 39 01 00 00 01 cmp     byte ptr [edx+139h],1
401966D9    (  0)  75 0D                jnz     label_7

; ## BLOCK 5; loops: 31; ENTER from 4; EXIT to 6, 7
401966DB    (  0)  83 78 24 00          cmp     dword ptr [eax+24h],0
401966DF    (  0)  75 07                jnz     label_7

; ## BLOCK 6; loops: 71; ENTER from 5; EXIT to 8=RET
401966E1    (  0)  B8 01 00 00 00       mov     eax,1
401966E6    (  0)  EB 02                jmp     label_8

; ## BLOCK 7; loops: 91; ENTER from 4, 5; EXIT to 8=RET
                        label_7:
401966E8    (  0)  33 C0                xor     eax,eax

; ## BLOCK 8 (epilog); loops: 0111; ENTER from 6, 7
                        label_8:
401966EA          >C3                   retn    

401966EB                align 4

This is the .dot image; clear ifs are yellow, and the nodes contain their dominator bit sets so I can try and make sense of them (a TO-DO as yet). This explains the flow but you cannot see how much code each node represents.

function flow

The disassembly gets parsed into the following pseudo-code. Some notes are manually added.

; #### PARSED
401966A8    (  0)       edx = Main.UnitList@20551314 ;
401966AE    (  0)       edx = (dword)[edx] ;
401966B0    (  0)       if ((byte)[edx + 139h] != 2) goto label_4 ;

401966B9    (  0)       if ((dword)[eax + 24h] >= 2) goto label_4 ;

401966BF    (  0)       edx = 2 ;
401966C4    (  0)       edx -= (dword)[eax + 24h] ;
401966C7    (  0)       return edx ; MOV EAX,.. where an exit block follows

                        return ;  .. and this line is generated by the actual exit block

                    label_4:
401966CA    (  0)       edx = Main.UnitList@20551314 ;
401966D0    (  0)       edx = (dword)[edx] ;
401966D2    (  0)       if ((byte)[edx + 139h] != 1) goto label_7 ;

401966DB    (  0)       if ((dword)[eax + 24h] != 0) goto label_7 ;

401966E1    (  0)       eax = 1 ;
401966E6    (  0)       return ;  this was a jump-to-exit-block, so missed

                    label_7:
401966E8    (  0)       eax = 0 ; this was a XOR, not a MOV, so missed

                    label_8:
                        return ;

The loss in verbosity is already worth the effort: from 21 lines of code to 16 lines, even though the lookahead to check if EAX got written to right before a RET failed twice.

Yet, it is obvious that the two successive ifs at 401966B0 can be combined into a single one, with an OR. Inverting the condition, that whole block can be a single if and braced up to the return, removing label_4.
The manipulation of edx from 401966BF onwards can be concatenated into a single return statement.
Also, the if conditions at 401966D2 can be combined into a single one and put inside an if block. Since there is a return at its end, an else is not necessary there. Manually reconstructed:

401966A8    (  0)       edx = Main.UnitList@20551314 ;
401966AE    (  0)       edx = (dword)[edx] ;
401966B0    (  0)       if ((byte)[edx + 139h] == 2 &&
401966B9    (  0)           (dword)[eax + 24h] < 2)
                        {
401966BF    (  0)           return 2 - (dword)[eax + 24h] ;
                        }

401966CA    (  0)       edx = Main.UnitList@20551314 ;
401966D0    (  0)       edx = (dword)[edx] ;
401966D2    (  0)       if ((byte)[edx + 139h] == 1 &&
401966DB    (  0)          (dword)[eax + 24h] == 0)
                        {
401966E1    (  0)           return 1 ;
                        }

401966E8    (  0)       return 0 ;

reducing the original 21 lines to a mere 11. Furthermore, register value propagation resolves the references to the global class Main.UnitList. I manually created names for its elements; 401966A8 and forwards collapses into

401966B0    (  0)       if (Main.UnitList.flag == 2 &&
401966B9    (  0)           Main.UnitList.count < 2)

which makes the code practically readable.

Accessing eax before it gets written is not an error here. The function is a class function, and eax points to a class instance, so (dword)[eax + 24h] reads a data member of the structure. Main.UnitList is a pointer to a globally declared class instance, since it points into the BSS.

  • What you're trying to do is very hard. Consider how long the Hex-Rays decompilers have been developed, and how much manual tuning the results need. – Guntram Blohm May 7 '15 at 10:51
  • @GuntramBlohm: well I cannot but agree with that. The next step, from registers and 'local' variable to 'actual' variables, is within my capabilities (tracking the life time of each registers), but then I end up with a list of singular operations, which I want to concatenate – at least for the trivial cases. That needs an IL, conceptually separated from the original assembly. – usr2564301 May 7 '15 at 11:47
  • Indeed, as @GuntramBlohm stated, decompilation isn't for the faint of heart. But, it is doable, though you'll have to make difficult choices. Check out McSema (blog.trailofbits.com/2014/08/07/…), it does a remarkable job transforming x86 assembly into LLVM IR. Keep in mind that what you're trying to do requires the extensive use of heuristics & pattern matching. – yaspr May 7 '15 at 11:55
  • @yaspr: that looks good! Yes, as my target is fairly limited (I added a paragraph about that), I may look in to pattern matching. The compiler that was used was an oldie, no fancy optimizations – here and there not even (humanly) obvious ones. – usr2564301 May 7 '15 at 12:06
  • @Jongware Well, I kind of noticed the stack operations which most modern compilers would've avoided; my thought was either this is -O0 code or an old compiler. – yaspr May 7 '15 at 12:19
2

For creating "humanly" readable expressions, i'd use an arithmetic parse tree. In fact, one separate parse tree for each of the registers and memory locations that are involved.

Every assignment copies the root of the target tree to the destination tree.

Every arithmetic operation creates a new root containing the operation, with the operands as the left & right child. The resulting tree is assigned to the target of the arithmetic operation.

Your example builds up like this:

example parse trees

From there, emitting the resulting formula is just a ltr tree walk. You'll probably want to simplify your expression first; you can replace an operator that has two constant subnodes with the operation result, and you might want to transform your tree by moving constants down where possible, like this:

              eax
               |
              add
               |
     +---------+--------+
     |                  |
    add                 5
     |                  
+----+-------+          
|            |
2           ebx


              eax
               |
              add
               |
     +---------+--------+
     |                  |
    add                ebx
     |                  
+----+-------+         
|            |
2            5

              eax
               |
              add
               |
     +---------+--------+
     |                  |
     7                 ebx

Google for "expression tree" and "constant folding" for more resources on this.

Mind that trees might be "self-referencing", especially in loops; the loop control variable will be seen at the top node, and somewhere down the tree as well. This is actually a good way to identify loop variables.

I'd probably start with trying to recognize basic blocks (everything that doesn't contain a jmp instruction or destination), and then build and dump the expression trees for these basic blocks. If you get this working well, you might continue by identifying stuff that stretches over several blocks, but is constant in some of them, like loops, to find out what's being built over the whole function.

EDIT: Another example, which shows how to treat register moves

A raw register move just copies the tree from the source register to the destination register. This is from an old watcom C program, compiled when imul was slow, and a series of shift/add instructions was faster; the compiler calculates var*45 here:

mov eax, [var]
mov edx, eax      <-- tree copy here (not much of a tree, however)
shl edx, 2
add eax, edx
mov edx, eax      <-- tree copy again
shl eax, 3
add eax, edx

arithmetic example var*45

  • Thanks for the excellent example. I already have the Basic Blocks (improved since my last question on those), and they help a lot in deciding variable scope. Since variables need cleaning up anyway, could that be done by storing the raw register moves in this same tree and then cleaning up the branches? – usr2564301 May 7 '15 at 19:31
  • 2
    Added another example. A raw register move translates to the tree being copied from the source to the destination. At the end, each register has a tree that has the register value (edx, not shown in the last step, still has var*5), and each tree depends on input variables only (there's no edx in the last representation of eax, even though it was used in the calculation). After cleaning up the eax tree, you have var mul 45. – Guntram Blohm May 8 '15 at 6:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.