People ask me what binary reverse engineering is like. It’s tedious, that’s what it is. When it gets right down to it, you just have to concentrate on little (in the sense that they do not do much individually) instructions and carefully trace the bigger picture from huge blocks of these baby steps.
If you want to see what RE really looks like, come inside my notebook. Here are 3 choice pages, illustrating the process I used to figure out one of the inverse transforms that RealVideo 4 (and 3, for that matter; both H.264 prototypes) employ:
page 1, page 2, page 3
In this example, I used a lot of back substitution in order to figure out a series of math formulas. This case was greatly simplified by the fact that there were not very many mystery parameters to deal with. However, the property that complicated matters here is that there were few if any straightforward imul (integer multiplication) instructions. Even though multiplication figures heavily into the transform, most multiplications were performed by sequences of additions, bit shifts, and compound add/shift instructions (lea).
Here I put two my scripts that helped me to gather longer expressions
http://codecs.multimedia.cx/wp-content/scripts.tar.bz2
re.pl will try to transform disassembly into the series of expressions like
var_1 = ((eax)*8+1)-((eax*7)+(ebx*4))
and compl.pl will try to make it into normalized expression like
var_1 = 1*eax + -4*ebx + 1*1
It does not handle OR’s AND’s most of LEA’s and memory accesses but may help on some maths (like calculating result of integer multiplication expressed as LEAs and ADD/SUBs).
Feel free to make it into anything useful ;)
Good stuff. I would like to see something similar for sequences of x87 FPU instructions. That would be useful for some of the more involved audio codecs.
Even worse than FPU instructions is when the code you are trying to RE has MMX/SSE/SSE2/3DNow!/etc instructions built in.
This is true. However, I have yet to encounter a situation where I absolutely MUST RE a sequence of SIMD instructions. Generally, there is a C equivalent for such functions. Such was the case for this transform– there were also SIMD-optimized versions for the function.
You guys should try Hex-Rays :)
http://www.hex-rays.com/compare.shtml
This seemed like an interesting challenge, and it seemed like a way to indirectly give a little something to ffmpeg, so I threw a “symbolic executor” together in about 3 hours.
http://nothings.org/remote/bb86.zip
“Basic Block x86” is a simple decompiler for basic blocks of 80×86 instructions, written in C. Public domain.
It currently wants to be fed the disassembly output from Visual Studio 6’s compiler, since that’s all I had handy to test with; it’s not very complete, especially in regards to integer instructions; and it’s probably got bugs up the wazoo. It generates extremely overcomplicated expressions which you’ll want to use another program to simplify (e.g. like the perl tool above). I’ve only compiled it with VC6 (it should be portable, except the library file hasn’t been compiled under linux/macos in a year, so it probably doesn’t have proper ifdefs).
But it successfully handled my test case, so I think it’s probably useful (modulo bugs).
I compiled a rather naive MDCT implementation. One basic block looked like this in the source:
u[n2 + k2 ] = ( v[n2 + k2] + v[n-2-k2] + C[k2+1]*(v[n2+k2]-v[n-2-k2]) + C[k2]*(v[n2+k2+1]+v[n-2-k2+1]))/2;
u[n-2 – k2] = ( v[n2 + k2] + v[n-2-k2] – C[k2+1]*(v[n2+k2]-v[n-2-k2]) – C[k2]*(v[n2+k2+1]+v[n-2-k2+1]))/2;
u[n2+1+ k2] = ( v[n2+1+k2] – v[n-1-k2] + C[k2+1]*(v[n2+1+k2]+v[n-1-k2]) – C[k2]*(v[n2+k2]-v[n-2-k2]))/2;
u[n-1 – k2] = (-v[n2+1+k2] + v[n-1-k2] + C[k2+1]*(v[n2+1+k2]+v[n-1-k2]) – C[k2]*(v[n2+k2]-v[n-2-k2]))/2;
which is pretty fricking hard to read due to all the index calculations, but it was what I typed in straight out of a paper a while back (for a vorbis decoder).
The decompiler generated this (I’ll show the asm at the end, since it’s long):
Memory locations:
mem2 EQU 20+(ebp_0)
mem13 EQU 8+(ebp_0)
mem1 EQU (eax_0)-4
mem3 EQU (ecx_0)
mem8 EQU ((eax_0 + 8))-12
mem4 EQU ((esi_0 + 8))-4
mem5 EQU ((eax_0 + 8))-8
mem9 EQU ((ecx_0 – 8))+8
mem7 EQU ((esi_0 + 8))-8
mem10 EQU (mem2)+((eax_0 + 8))-12
mem6 EQU ((ecx_0 – 8))+12
mem11 EQU ((ecx_0 – 8))+(mem2)+8
mem14 EQU ((mem13 – 8))+8
mem12 EQU (mem2)+((eax_0 + 8))-8
Integer registers:
eax = (eax_0 + 8)
ecx = (ecx_0 – 8)
esi = (esi_0 + 8)
edi = (mem13 – 8)
Floating point stack:
st(0) = fp3
st(1) = fp2
st(2) = fp1
st(3) = fp0
Memory locations:
[8+(ebp_0)] <= (mem13 – 8)
[(mem2)+((eax_0 + 8))-12] <= ((((((mem1 – mem3) * mem4) + ((mem5 + mem6) * mem7)) + mem8) + mem9) * dword ptr __real@3f000000)
[((ecx_0 – 8))+(mem2)+8] <= ((((mem8 + mem9) – ((mem8 – mem9) * mem4)) – ((mem5 + mem6) * mem7)) * dword ptr __real@3f000000)
[((mem13 – 8))+8] <= ((((((mem5 + mem6) * mem4) – mem5) + mem6) – ((mem8 – mem9) * mem7)) * dword ptr __real@3f000000)
[(mem2)+((eax_0 + 8))-8] <= (((((mem5 + mem6) * mem4) + (mem5 – mem6)) – ((mem8 – mem9) * mem7)) * dword ptr __real@3f000000)
If you look closely at those last four lines you can see that it’s computing the same set of operations as the original, so I pronounced this “close enough to working to ship it”.
(The “eax_0” notation means ‘the value of eax at the start of the basic block’. The equ notation is just to show that its an address. Maybe it should be more like ‘mem4 = mem[esi_0+16]’ or something to make it clearer when there’s indirected fetching going on… but that’s just a printf.)
I’ll probably forget to check the comments on this entry later, so send me email if there’s a followup…
The assembly it decompiled didn’t have anything really heinous (for example, fxch is still untested since this doesn’t have any):
fld DWORD PTR [eax-4]
mov edi, DWORD PTR 20+[ebp]
fsub DWORD PTR [ecx]
add eax, 8
add esi, 8
sub ecx, 8
fmul DWORD PTR [esi-4]
fld DWORD PTR [eax-8]
fadd DWORD PTR [ecx+12]
fmul DWORD PTR [esi-8]
faddp ST(1), ST(0)
fadd DWORD PTR [eax-12]
fadd DWORD PTR [ecx+8]
fmul DWORD PTR __real@3f000000
fstp DWORD PTR [edi+eax-12]
; Line 2968
fld DWORD PTR [eax-12]
fadd DWORD PTR [ecx+8]
fld DWORD PTR [eax-12]
fsub DWORD PTR [ecx+8]
fmul DWORD PTR [esi-4]
fsubp ST(1), ST(0)
fld DWORD PTR [eax-8]
fadd DWORD PTR [ecx+12]
fmul DWORD PTR [esi-8]
fsubp ST(1), ST(0)
fmul DWORD PTR __real@3f000000
fstp DWORD PTR [ecx+edi+8]
; Line 2969
fld DWORD PTR [eax-8]
fadd DWORD PTR [ecx+12]
fmul DWORD PTR [esi-4]
fld DWORD PTR [eax-8]
fsub DWORD PTR [ecx+12]
faddp ST(1), ST(0)
fld DWORD PTR [eax-12]
fsub DWORD PTR [ecx+8]
fmul DWORD PTR [esi-8]
fsubp ST(1), ST(0)
fmul DWORD PTR __real@3f000000
fstp DWORD PTR [edi+eax-8]
; Line 2970
mov edi, DWORD PTR 8+[ebp]
fld DWORD PTR [eax-8]
sub edi, 8
fadd DWORD PTR [ecx+12]
mov DWORD PTR 8+[ebp], edi
fmul DWORD PTR [esi-4]
fsub DWORD PTR [eax-8]
fadd DWORD PTR [ecx+12]
fld DWORD PTR [eax-12]
fsub DWORD PTR [ecx+8]
fmul DWORD PTR [esi-8]
fsubp ST(1), ST(0)
fmul DWORD PTR __real@3f000000
fstp DWORD PTR [edi+8]
Thanks, Sean! Followed up in this post: http://multimedia.cx/eggs/the-quest-for-decompilation/