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?
How does BinDiff work?
tools;tool bindiff
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 MatchesFirst of all BinDiff associates a signature based on the following attributes to each function:the number of basic blocksthe number of edges between those blocksthe number of calls to subfunctionsThis 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 DownIn 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 paperGraph-based Comparison of Executable ObjectsStructural Comparison of Executable Objects(Disclaimer: working @ team zynamics / google, hopefully I didn't mess up anything, otherwise soeren is going to grill me ;-))