BinStat - An Open Source Binary Static Analysis Framework

Reverse Engineering

2010-04-11T12:26:00.000-07:00

To start off I'd like to point at a fellow student
who is doing some really good work, John.

Read about his Universal Decompiler project here

Get the source code here

AND for more RCOS projects be sure to visit this link
================================================

He's also been working on a different kind of reverse engineering.

Years ago I saw a presentation at Hope 2008 by Karsten Nohl on reversing chips. Using some space alien technologies such as "Sandpaper" and "MATLAB" they were able to break proprietary RFID cryptography. Wow! Most hackers would have just called up a secretary or something.

Read Karsten Nohl, Starbug, Henryk Plötz, and David Evans fascinating USENIX paper here.

And another nice presentation was given at cansecwest

While the skilled might be able to read www.siliconzoo.org like a coloring book,
I can not. I'm sure that maybe to VLSI CAD researchers and others it's a breeze. But a blog post over at flylogic left me equally confused. I needed something easier for a newbie like me. I kept getting my parallels vs series pretty darn wrong. So I emailed Dr. Nohl who kindly responded.

So once you see it, it's pretty magical. Sort of. I haven't worked my way through all of the zoo just yet.

Enjoy this educational visual inspection of 2-input CMOS NOR and NAND gates.

Whoaaa

2010-04-11T12:07:00.000-07:00

Hello from one year in the future.

I have not worked on RCOS-Binstat since last April. When we left off I realized I did not have enough formal background. I had implemented incomplete disassemblers for x86 and MIPS with basic value propagation for constant folding, some simple SSA, and rudimentary analysis for doing things such as resolving function arguments. Just that alone was actually useful for finding real life bugs.

That code is still available here: http://github.com/adc/rcos-binstat

It sucks.

Hopefully I will get back to it soon. Currently I'm searching around for a language with good features and no bad ones. Something painfully simple and powerful with a low learning curve.

The next thing is to analyze the tremendous amount of projects that have advanced and been created and released to the public in this past year alone.

So what have I been doing in all my free-time? I spent the summer with some very good friends in the land of pirates.

Then stuff happened when I got back to school. My computer engineering classes have picked up, landing me an infinite well of excuses. And just when I thought it got better, the club started teaching a class: www.cs.rpi.edu/academics/courses/spring10/csci4971/.

At least last Fall I finally learned what a transistor is. After all, the university I attend once digested and emitted Teddy Hoff, the father of the microprocessor and Intel employee #12.

I also got some significant appreciation for Shannon's work on boolean logic. A Jean-Claude vs Claude deathmatch will obviously show Shannon as one mighty dude.

Someone should report back on Shannon's work with genetic computing.

rcos ppt

2009-05-01T15:16:00.000-07:00

I was asked to make a presentation on current progress. Here it is: http://rpisec.net/attachments/download/21/go.pdf

The Intermediate Representation

2009-03-12T08:23:00.000-07:00

In this post I will show an example of the Intermediate Language previously described.

As previously mentioned there are more or less four basic operations.

1. operation() <- for math, takes operands and operators
2. load $register <- implicitly retrieves data from the memory address resulting from the previous operation and puts it into $register
3. store $register <- stores $register into the implicit result of the previous operat
4. branch_true <- branch if the previous operation is != 0 , otherwise fall through

For now call and ret operations are also used to make function detection more manageable. In the future these will be removed, as they can be derived from combinations of load/branch.

Here is some sample output from the MIPS translator on the print2lpr binary. In addition some basic analysis has been performed to resolve GOT entries and strings. This is fully automated but register propagation is very basic at the moment. Be sure to check out the code at http://rpisec.net/repositories/show/rcosbinstat. The majority of that code is in the libtransform function in mips_translator.py

0x4023ec ($28, '+', -32460)

0x4023ec LOAD $25 ### getenv

0x4023f0 ($4, '=', $4, '+', 1588) %%%% "LPUSER"

0x4023f4 ($0, '=', $0, '<<', $0)

0x4023f8 ($31, '=', $32, '+', 4)

0x4023f8 CALL $25

0x4023fc ($29, '+', 48)

0x4023fc LOAD $28

0x402400 ($6, '=', $2, '|', $0)

0x402404 ($2, '==', $0)

0x402404 BRANCH loc_0x402428

---end of block---

--- block 402408 -> 402424:13--

parents: []

branches: 0x402428 0x0

0x402408 ($28, '+', -32692)

0x402408 LOAD $5 %% (10000000)

0x40240c ($28, '+', -32556)

0x40240c LOAD $25 ### sprintf

0x402410 ($4, '=', $16, '|', $0)

0x402414 ($5, '=', $5, '+', 1596) %%%% "P%s

0x402418 ($31, '=', $32, '+', 4)

0x402418 CALL $25

0x40241c ($29, '+', 48)

0x40241c LOAD $28

0x402420 ($16, '=', $16, '+', $2)

On MIPS arguments are passed in registers $4 - $8 and then the stack. It would be nice to automate that translation but I haven't had a chance to. Anyway, let's look at how the sprintf function is being called.

Note that register $16 points to a global write buffer in the BSS. sprintf takes 2 arguments and then a variable number of arguments:

sprintf(dest, fmt, .... )

$4 is the destination <- $16 = global write buffer
$5 is the format string <- "P%s"
$6 is $2.

Return values on MIPS are placed in $v1/$v2 which are registers $1/$2. Looking up at the previous code block the last call was to getenv("LPBUF");

Our code is then

write_buf += sprintf(write_buf, "P%s", getenv("LPBUF"));

We are still quite a ways from automating that higher level translation, but having automated string and library resolution is certainly nice.

By the way, this particular code segment was not exploitable as there is nothing good after the global BSS buffer. If you're really interested in Irix bugs, get a life, or contact me :-).

Back to the topic at hand. The IR looks to be painfully simple. This is to make analysis very easy in the long term. In addition forcing this simplicity makes translation from other architectures better possible. Analysis tools will then be much more useful as platforms change and so on.

Why Pink?

2009-02-18T15:01:00.000-08:00

Because there are no other static analysis blogs decorated with pink. Roughly 20 days have passed and this project is finally rolling. Please check out the project in progress and play with the Wiki and forums.

Alright. It's 5 minutes to go, you're me, and you need to show your boss all the work you've done. Close the lolcat tabs. Oh gosh, I really meant to save that one, thank you oh mighty and omnipotent firefox recently closed tabs history menu.

On your sketch pad you write down:

While surfing the chaos I have built up the following:

A notion of a higher level IR that no longer resembles asm
An almost complete MIPS translator into this IR
Really basic procedure detection and inter+intra procedure flow graphs on mips-code-generated IR

Now this one is the easiest but the most important. The Intermediate Representation is the basis for what the code from all of the other architectures is translated into. Originally something along the lines of U-Code was envisioned. Now, UCode works well for writing a compiler. UCode has a concept of a stack, a heap, global variables, and so on, it's nifty! But overly complicated for what I think is needed. We need something super simple. Here it is:

There are 4 staple operations in the IR:

operation(...) (... = list of operands and operators)
load [destination]
store [source]
branch_true [destination]

#1 covers all of the bit twiddling and math instructions. #2/#3/#4 use an implicit value which is the result of the previous operation(). For example, load is implicitly given a source memory address.

In terms of analysis #4 covers many contexts, so this one has actually been re-complicated back into jump, call, and branch_true. And, call also has a corresponding ret instruction. For what purpose? Procedure detection. What's the difference between a call and a jump? A return address. A jump and a branch_true? It's philosophical but I consider it to be locality.

The next blog post will elaborate more on the IR, how the operands work, and other instruction abstractions that are created to ease analysis. If you can't wait, I encourage you to glance at the code.

Upcoming Milestones

x86 translator!
integer under and overflow hot-spot detection
unchecked return values, double frees

What's needed after those

A GUI is needed to play with these graphs, Processing? Any suggestions? Readers please help
PE file format support
IR Transformation gadgets -- an interface to the IR for applying easy transformations for detecting external library calls, function prologues and epilogues, specialized integer operations, and ....

Hello Blogosphere

2009-01-26T08:36:00.000-08:00

Hi there,

I'm proud to announce an open-source binary static analysis project. The name will come later, once the frustration factor is better scoped out.

There are quite a few impressive pieces of software out there. First, you have IDA Pro and the development of the hex-rays plugin which produces rather good looking higher-level output from machine code. There is even an SDK for this decompiler, pretty good stuff.

Second, you have projects like BitBlaze which do some great anti-malware work and make some pretty scary, although entirely plausible threats. For example I like "Automated Patch-Based Exploit Generation" a.k.a. skynet. No worries, do not panic computer scientists, they also acknowledge that they too have not yet solved the halting problem and the machine uprising still has some homework to do.

And third, you have one of the oldest tools that was free as in beer, REC - The Reverse Engineering Compiler. REC is nice, it works, the output almost compiles. It was the first such tool I had experience with and I greatly appreciate it. The newer version looks to reach for interactive RE work, very good stuff. And it supports x86, m68k, ppc, and mips (no IDA but pretty good).

I should also mention that the LLVM project has an x86 translator in progress, but it has quite a bit of work left. There are also about one hundred or so papers out there on binary static analysis. I'll be compiling a full listing as I find them, they'll be dumped on the wiki, so the general public can more easily observe their concepts, terminology, and ideas.

So what's the problem with some of these tools? (1) is pay software, and the SDK is probably nice (wouldn't know), but it's still not completely open and limits flexibility. (2) has yet to release source. And (3) is very nifty but has been targeted specifically for C-style RE but does support a few very different platforms. And although (3) is free as in beer, the source is closed.

So what's the point of this one? Why an open source alternative? The point is to give the reverse engineering community the freedom to build crazier and cooler projects without as much grunt work.

The projects will build a whole suite of APIs and tools for reverse engineering work. You want graphs for your obscure embedded microcontroller? You want a subgraph of all network I/O handling related code? Easy mode. How about for bytecode for this whole new interpreted ju-JIT-su language that just came out? No problem, just get a translator in for your architecture and you're all set. You want to find bugs? How about applying some theorem solvers using tools that have already been written like these guys (2). You want higher level output? Why not take advantage of already implemented techniques for building syntax trees. Let some code that has already been written optimize those trees for your higher-level language output so that any programmer out there can recognize it (except die-hard asm masochists).

Note that this project is made possible by the Rensselaer Center for Open Source which was very kindly created with a grant from Sean O' Sullivan, an alumn from '85. I am very grateful to RCOS for motivating me to make this concept a free software reality.

So let's start to build this thing. It might take quite a few lines of code and more than one language though, so please re /join us after this commercial break.

And Thanks,

Alex