12

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?

  • @Nirlzr: I don't see how it does improve anything to change the tags 'bindiff' into 'tool-bindiff'... But, I may just have a twisted mind, so tell me more about it... – perror Oct 11 '16 at 14:08
  • Perhaps you should voice in meta.reverseengineering.stackexchange.com/questions/322/… – kennytm Oct 11 '16 at 17:46
  • @kennytm: Ah, I missed this... Good catch, thanks. – perror Oct 11 '16 at 20:48
16

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 ;-))

  • So you're still working on it? Or is that just the every-Friday project? – wishi Apr 2 '13 at 21:17
  • I'm not working on it and never did, but BinDiff hasn't been cancelled if that's what you meant!? – newgre Apr 2 '13 at 22:11
  • Zynamics, the company behind BinDiff, was acquired by Google. You can message some employees that sit on the reverse engineering reddit. – sw. Apr 6 '13 at 18:20
7

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).

  • 2
    The original article on the algorithm of graph homomorphism is a good start. More recently, some tools have been proposed (see this paper and this poster). But, this Reddit thread suggests that some improvements have been made on BinDiff. – perror Apr 2 '13 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.