Hello World
Generally the first progam anyone writes in a language, hello world is about the simplest you can get and still do something interesting. Compile the following code on Pentium and SPARC (unix) platforms and you get very different output binaries.
int main() {
printf("hello world\n");
return 0;
}
Using the intermediate representation of Boomerang we can ignore the particular mnemonics of the target architecture and look at the raw semantics. For Pentium the generated code looks like:
void main()
Call BB:
08048918 *32* r[28] := r[28] - 4
*32* m[r[28]] := r[29]
08048919 *32* r[29] := r[28]
0804891b *32* r[28] := r[28] - 4
*32* m[r[28]] := 0x80493f8
08048920 *32* r[28] := r[28] - 4
*32* m[r[28]] := %pc
*32* %pc := (%pc + 5) + 135840976
08048920 r[24] := CALL printf(m[r[28] + 4])
internal *32* %pc := m[r[28]]
internal *32* r[28] := r[28] + 4
Oneway BB:
08048925 *32* r[tmp1] := r[28]
*32* r[28] := r[28] + 4
*32* %flags := ADDFLAGS32( r[tmp1], r[28], 4 )
08048928 *32* r[24] := 0
*32* %flags := LOGICALFLAGS32( r[24] )
0804892a JUMP 0x804892c
L1: Ret BB:
0804892c *32* r[28] := r[29]
*32* r[29] := m[r[28]]
*32* r[28] := r[28] + 4
0804892d *32* %pc := m[r[28]]
*32* r[28] := r[28] + 4
0804892d RET
The statements with address "internal" represent the calling convention of the
printf library function. All they say is that the value of the program counter
is popped off the stack to perform a return. The statements before the call do
the opposite, pushing the current value of the program counter and then jumping
to the address of printf. Representing these low level semantics in a
decompiler is unusual, but using dataflow analysis we can get rid of them
without the need for a special pass to remove them.
Here is the same program compiled for the SPARC architecture:
void main()
Call BB:
00010a54 *32* r[tmp] := r[14] - 112
*32* m[r[14]] := r[16]
*32* m[r[14] + 4] := r[17]
*32* m[r[14] + 8] := r[18]
*32* m[r[14] + 12] := r[19]
*32* m[r[14] + 16] := r[20]
*32* m[r[14] + 20] := r[21]
*32* m[r[14] + 24] := r[22]
*32* m[r[14] + 28] := r[23]
*32* m[r[14] + 32] := r[24]
*32* m[r[14] + 36] := r[25]
*32* m[r[14] + 40] := r[26]
*32* m[r[14] + 44] := r[27]
*32* m[r[14] + 48] := r[28]
*32* m[r[14] + 52] := r[29]
*32* m[r[14] + 56] := r[30]
*32* m[r[14] + 60] := r[31]
*32* r[24] := r[8]
*32* r[25] := r[9]
*32* r[26] := r[10]
*32* r[27] := r[11]
*32* r[28] := r[12]
*32* r[29] := r[13]
*32* r[30] := r[14]
*32* r[31] := r[15]
*32* r[14] := r[tmp]
00010a58 *32* r[9] := 70656
00010a5c *32* r[8] := r[9] | 464
00010a60 r[8] := CALL printf(r[8])
Oneway BB:
00010a68 *32* r[24] := r[0]
00010a6c JUMP 0x10a74
L1: Ret BB:
00010a74 *32* r[tmp] := r[0] + r[0]
*32* r[8] := r[24]
*32* r[9] := r[25]
*32* r[10] := r[26]
*32* r[11] := r[27]
*32* r[12] := r[28]
*32* r[13] := r[29]
*32* r[14] := r[30]
*32* r[15] := r[31]
*32* r[0] := r[tmp]
*32* r[16] := m[r[14]]
*32* r[17] := m[r[14] + 4]
*32* r[18] := m[r[14] + 8]
*32* r[19] := m[r[14] + 12]
*32* r[20] := m[r[14] + 16]
*32* r[21] := m[r[14] + 20]
*32* r[22] := m[r[14] + 24]
*32* r[23] := m[r[14] + 28]
*32* r[24] := m[r[14] + 32]
*32* r[25] := m[r[14] + 36]
*32* r[26] := m[r[14] + 40]
*32* r[27] := m[r[14] + 44]
*32* r[28] := m[r[14] + 48]
*32* r[29] := m[r[14] + 52]
*32* r[30] := m[r[14] + 56]
*32* r[31] := m[r[14] + 60]
*32* r[0] := r[tmp]
00010a74 RET
There appears to be more code here, but this is simply due to the large
semantics of the SPARC save and restore instructions. I havn't included the low
level semantics of the program counter here as SPARC delay slots give me the
willies, but in principle their removal should be just as general as they were
on Pentium.
The first step in the decompilation process from this represntation begins by
calculating dataflow information. We are interested in determining which
statements are live at the beginning and end of each basic block (which we use
to determine the liveness of all statements at any other given statement). We
use an interative solution to the liveness problem, found in the fabulous
Dragon Book. Using the liveness information we can calculate which
statements are used by any given statement. Here is this information presented
for Pentium.
void main()
Call BB: live in:
08048918 *32* r[28] := r[28] - 4 uses: used by: *32* r[29] := r[28], *32* m[r[28]] := r[29], *32* r[28] := r[28] - 4,
*32* m[r[28]] := r[29] uses: *32* r[28] := r[28] - 4, used by:
08048919 *32* r[29] := r[28] uses: *32* r[28] := r[28] - 4, used by: *32* r[28] := r[29],
0804891b *32* r[28] := r[28] - 4 uses: *32* r[28] := r[28] - 4, used by: *32* r[28] := r[28] - 4, *32* m[r[28]] := 0x80493f8,
*32* m[r[28]] := 0x80493f8 uses: *32* r[28] := r[28] - 4, used by:
08048920 *32* r[28] := r[28] - 4 uses: *32* r[28] := r[28] - 4, used by: *32* %pc := m[r[28]], *32* r[28] := r[28] + 4, r[24] := CALL printf(m[r[28] + 4]), *32* m[r[28]] := %pc,
*32* m[r[28]] := %pc uses: *32* r[28] := r[28] - 4, used by: *32* %pc := m[r[28]], *32* r[29] := m[r[28]], *32* %pc := m[r[28]],
*32* %pc := (%pc + 5) + 135840976 uses: used by:
08048920 r[24] := CALL printf(m[r[28] + 4])
internal *32* %pc := m[r[28]] uses: *32* r[28] := r[28] - 4, *32* m[r[28]] := %pc, used by:
internal *32* r[28] := r[28] + 4 uses: *32* r[28] := r[28] - 4, used by: *32* r[28] := r[28] + 4, *32* r[tmp1] := r[28],
Oneway BB: live in: *32* %pc := m[r[28]], *32* r[29] := r[28], *32* r[28] := r[28] + 4, r[24] := CALL printf(m[r[28] + 4]), *32* m[r[28]] := %pc,
08048925 *32* r[tmp1] := r[28] uses: *32* r[28] := r[28] + 4, used by: *32* %flags := ADDFLAGS32( r[tmp1], r[28], 4 ),
*32* r[28] := r[28] + 4 uses: *32* r[28] := r[28] + 4, used by: *32* %flags := ADDFLAGS32( r[tmp1], r[28], 4 ),
*32* %flags := ADDFLAGS32( r[tmp1], r[28], 4 ) uses: *32* r[28] := r[28] + 4, *32* r[tmp1] := r[28], used by:
08048928 *32* r[24] := 0 uses: used by: *32* %flags := LOGICALFLAGS32( r[24] ),
*32* %flags := LOGICALFLAGS32( r[24] ) uses: *32* r[24] := 0, used by:
0804892a JUMP 0x804892c
L1: Ret BB: live in: *32* %pc := m[r[28]], *32* r[29] := r[28], *32* %flags := LOGICALFLAGS32( r[24] ), *32* r[28] := r[28] + 4, *32* r[24] := 0, *32* r[tmp1] := r[28], *32* m[r[28]] := %pc,
0804892c *32* r[28] := r[29] uses: *32* r[29] := r[28], used by: *32* r[29] := m[r[28]], *32* r[28] := r[28] + 4,
*32* r[29] := m[r[28]] uses: *32* r[28] := r[29], *32* m[r[28]] := %pc, used by:
*32* r[28] := r[28] + 4 uses: *32* r[28] := r[29], used by: *32* %pc := m[r[28]], *32* r[28] := r[28] + 4,
0804892d *32* %pc := m[r[28]] uses: *32* r[28] := r[28] + 4, *32* m[r[28]] := %pc, used by:
*32* r[28] := r[28] + 4 uses: *32* r[28] := r[28] + 4, used by:
0804892d RET
Armed with this information there are a number of things we can see.
Firstly, some statements are not used by any other statement. However, to
remove all of these would be incorrect. Consider the second statement at
address 8048918, it is apparently use by no-one, however, it is clear that the
second statement of 804892c does actually want to use this statement, it just
unfortunately happens to not be live at the destination. On the other hand, the
last statement of 8048925 is live at the second statement of 8048928, which
assigns to the same left hand side. This statement is said to kill the original
statement, and a statement that is killed before it is every used is said to be
dead, it is always safe to remove dead code. Removing this statement frees up
the statement before it, which actually now reaches a statement which kills it
before it is used, therefore also becoming dead. The summary of all the dead
code we can remove on a first pass through this procedure follows.
removing dead code: *32* %pc := (%pc + 5) + 135840976
removing dead code: *32* %flags := ADDFLAGS32( r[tmp1], r[28], 4 )
removing dead code: *32* r[28] := r[28] + 4
removing dead code: *32* %flags := LOGICALFLAGS32( r[24] )
removing dead code: r[24] := CALL printf(m[r[28] + 4])
Clearly removing the call to printf would be a mistake! Whenever we are called upon to remove a call we simply instruct the call that we will be ignoring the return value. We still wish to execute the call (for it's side effects) but we will be removing it from liveness analysis.
Removing statements is good, our input binary has 21 statements, when in fact we want only one, the printf. This is all the statement we can remove using dead code analysis but there is another important transformation we can perform that will allow us to remove five more statements.
It is possible to propogate the first statement in the procedure to all it's uses. That is, we can safely replace the left hand side of the statement where-ever it appears in the statements that use the statement with the right hand side of the statement. Once this is complete, we can remove the statement. A number of constraints must be satisified before we can propogate a statement to a statement that uses it.
- All the statements used by the statement we want to propogate must be live at the statement we want to propogate the statement to.
- Had the statements that are live at the statement we want to propogate the statement to been live at the statement, they would not have been used by the statement. This is slightly complex, but it essentially means that we much not introduce any "false uses" by propogating the statement.
- The statment cannot be a call.
Here are all the replacements that we can do in the first pass:
replace *32* r[28] := r[28] - 4 in *32* r[29] := r[28]
replace *32* r[28] := r[28] - 4 in *32* m[r[28]] := r[29]
replace *32* r[28] := r[28] - 4 in *32* r[28] := r[28] - 4
replace *32* r[28] := r[28] + 4 in *32* r[tmp1] := r[28]
replace *32* r[28] := r[28] + 4 in *32* %pc := m[r[28]]
replace *32* r[28] := r[28] + 4 in *32* r[28] := r[28] + 4
replace *32* r[28] := r[28] - 8 in *32* r[28] := r[28] - 4
replace *32* r[28] := r[28] - 8 in *32* m[r[28]] := 0x80493f8
replace *32* r[28] := r[28] - 12 in *32* %pc := m[r[28]]
replace *32* r[28] := r[28] - 12 in CALL printf(m[r[28] + 4])
replace *32* r[28] := r[28] - 12 in *32* r[tmp1] := r[28] + 4
replace *32* r[28] := r[28] - 12 in *32* m[r[28]] := %pc
replace *32* m[r[28] - 8] := 0x80493f8 in CALL printf(m[r[28] - 8])
replace *32* m[r[28] - 12] := %pc in %pc = m[r[28] - 12]
We have now made significant progress in our decompilation. Our procedure
now looks like this.
void main()
Call BB: live in:
08048918 *32* m[r[28] - 4] := r[29] uses: used by:
08048919 *32* r[29] := r[28] - 4 uses: used by: *32* r[28] := r[29],
0804891b
08048920 CALL printf(0x80493f8)
internal *32* %pc := %pc uses: used by:
Oneway BB: live in: %pc := %pc, *32* r[29] := r[28] - 4, *32* m[r[28] - 4] := r[29],
08048925 *32* r[tmp1] := r[28] - 8 uses: used by:
08048928 *32* r[24] := 0 uses: used by:
0804892a JUMP 0x804892c
L1: Ret BB: live in: *32* r[29] := r[28] - 4, *32* m[r[28] - 4] := r[29], *32* r[24] := 0, *32* r[tmp1] := r[28] - 8, %pc := %pc,
0804892c *32* r[28] := r[29] uses: *32* r[29] := r[28] - 4, used by: *32* r[29] := m[r[28]], *32* %pc := m[r[28] + 4], *32* r[28] := r[28] + 8,
*32* r[29] := m[r[28]] uses: *32* r[28] := r[29], used by:
0804892d *32* %pc := m[r[28] + 4] uses: *32* r[28] := r[29], used by:
*32* r[28] := r[28] + 8 uses: *32* r[28] := r[29], used by:
0804892d RET
We can continue to propogate and remove dead code in this way until we end up with just the solitary call statement seen above. There is two things left to do. First we must replace the address constant with a string constant. To do this we utilize the information we know about the types of the parameters of printf and the section of the executable that we found the string in (it is read only, therefore it is always safe to inline). Second, we have to perform some analysis to determine the value returned by this function. Indeed, we do not even know that anything is returned. Again, we make use of calling convetion information. On the pentium platform it is always the case that integer values are returned in EAX or r[24]. As we saw above, there is an assignment of zero to r[24]. Using this information we can premote the custom signature of the procedure that we have been using to a standard C/pentium signature.
The final stage in the decompilation is code generation. The code generated is identical to this input code, however this will most often never be the case!
The decompilation of hello world is suprisingly challenging. The
analysis performed above is general enough to handle branching and
multi-procedural programs. This is the direction we will be heading next. Many
other challenges lie ahead.
Trent Waddington
4/12/2002
