Every now and then, someone comes along and writes a short novel of a comment on an older post. Such was the case when Sean Barrett used the occasion of my What RE Looks Like post to take three hours of his rather busy life and compose a “symbolic executor” — a basic block decompiler. It’s a valiant effort and I would like to try my hand at it, as with all RE tools. I am having trouble compiling the source he posted (I converted CR format, but I am still having trouble with missing symbols from his custom library-in-a-header-file). It works on Microsoft-compatible disassembly output but probably would not be too hard to adapt for ‘objdump -Mintel’ in the GNU toolchain.
Many people have gone down this basic block disassembly road. The details are hazy but I seem to recall that I have made the journey as well. It’s a good thing I keep this blog as a journal. I guess the reason I can’t remember what my experiment was called is because it was the “Unnamed RE Project”. It looks like all I accomplished there was straight ASM -> C translation without any effort at higher level language abstraction.
Anyway, I still maintain that figuring out the overriding purpose of these basic blocks is not the biggest challenge in traditional binary reverse engineering– indeed, I personally consider it the most interesting part. No, what I think is the toughest part is figuring out — or more likely guessing — what the sometimes hundreds of referenced variables are actually used for, and assigning them appropriate names. The biggest nightmare is when functions pass around multiple gigantic nested structures and actually use a bunch of variables within.
In other words, true understanding of the underlying algorithm is the goal. But, Sean, I still want to try your tool.
Hey, yeah, like I said, some stuff isn’t portable currently, and I don’t have anything other than Windows set up to test at the moment. In the worst case you could just go into the header file and ifdef/delete all the threading stuff (and anything that then doesn’t compile due to that–there shouldn’t be many dependencies and none of its used for this app).
If that sounds like too much work I can go into source control and dig up an old version of stb.h before I added the threading libs and get it working that way, although I’m sure there will be the odd incompatibility here or there.
Oh yeah:
“I still maintain that figuring out the overriding purpose of these basic blocks is not the biggest challenge in traditional binary reverse engineering– indeed, I personally consider it the most interesting part.”
Yeah, I don’t think it’s hard to figure this out yourself, but I think it can be tedious, and you had fingered the 8087 instructions as being particularly annoying, I assume because of the stack. So I think it could be valuable for eliminating the tedium.
Of course, if you _enjoy_ doing the “tedious” bit, it won’t be that useful!
Yeah, what I consider “fun” tends to run orthogonal to traditional definitions of the notion. I often forget about the x87 instructions, but I do believe that some kind of automated tool will help immensely with FPU basic blocks. There are still a number of undiscovered audio codecs out there and they tend to rely heavily on the fractional part of a processor.
I would like to see pattern-based approach because when I RE something the better half of the code comes to “hey, I’ve seen that in that function”. If only I could specify to replace the same code (using different registers) everywhere…
FPU would be a bit easier than usual CPU because it’s stack-based and the most obscure part there is manipulating control word. And resulting expression should be less complicated (as there’s no ‘lea’ for FPU).
I think a large part of a decompiler is the same as a compiler (converting asm ->SSA, dataflow and loop iv-finding would certainly help) so a good one might be based off gcc or llvm?
llvm’s C emitter is really, really bad, though. Straight branching and it completely ignores all the variable naming hints.
Now, if only everyone had stuck to an ISA that wasn’t crazy. At least I get to assume -mfpmath=sse.
“At least I get to assume -mfpmath=sse.”
As long as the FPU stack pointer is left at the same point at entry and exit of each basic block, it’s really not that bad to automatically decode the FPU stuff–and I imagine compilers do that. Within a basic block, you just model it as 8 FP fixed-location registers and track the stack pointer through each operation to determine which registers each operation updates; fairly trivial.
(I actually implemented an arbitrarily deep stack, which is wrong, but was slightly easier given the dynamic array support I already had in my library.)