How does BinDiff work?

Question

I would like to know what are the basic principles (and maybe a few things about the optimizations and heuristics) of the BinDiff software. Does anyone have a nice and pedagogic explanation of it?

Answer 1

In general, BinDiff in its current version as of this writing (4.x) works by matching attributes on the function level. Basically, matching is divided into two phases: first initial matches are generated which are then refined in the drill down phase.

Initial Matches

First of all BinDiff associates a signature based on the following attributes to each function:

• the number of basic blocks
• the number of edges between those blocks
• the number of calls to subfunctions

This step gives us a set of signatures for each binary which in turn are used to generate the set of initial matches. Following a one-to-one relation, BinDiff selects these initial matches based on the above characteristics.

The next step tries to find matchings on the call graph of each binary: for a verified match, the set of called functions from the matched function is examined in order to find event more matches. This process is repeated as long as new matches are found.

Drill Down

In practice, not all functions will be matched by the one-to-one relation induced by the initial matching strategy, so after the initial matchings have been determined we still have a list of unmatched functions. The idea of the drill down phase is to have multiple different function matchings strategies which are applied until a match is found. The order of applying these strategies is important: BinDiff tries those strategies for which it assumes the highest confidence, first. Only if no match could be found, it goes on with the next strategy. This is repeated until BinDiff runs out of strategies, or until all functions are matched. Examples include MD index, match based on function names (i.e. imports), callgraph edges MD index, etc.

MD-Index paper

Graph-based Comparison of Executable Objects

Structural Comparison of Executable Objects

(Disclaimer: working @ team zynamics / google, hopefully I didn't mess up anything, otherwise soeren is going to grill me ;-))

Answer 2

I can tell just a couple of words about control-flow graph building, though my answer is definitely not the full one.

BinDiff uses a static type of detecting execution flows, I suppose because executing code isn't always possible (e.g. for ring 0 drivers) or reasonable (malware). Actually, the given file is disassembled, then it should be split into basic blocks (these are pieces of code that have straight way of execution, though this definition is right in that very case). It's clear (considering the x86 architecture, for example) that instructions like jxx change the control flow of a program. So basic blocks are usually terminated by them. This very process of splitting code into blocks isn't a complicated task, the more challenging part is determining jump destination.

For example something like that:

...
jz eax

So we can't (easily) understand with automated static analysis where this call is pointed to. Trivial cases can be "emulated", but in general that work is very hard and frustrating. The other option is to trace program to look which paths does code execute (that can be done manually). When these blocks are found the only one thing left is to build human-readable graph.

Anyway there is a pile of ways execution flow can be changed (exceptions, hot patching by another thread, system-dependent events etc).