4 ms·
worth reading to the end: I knew about various arcane symbol formats, but TIL that cross-architecture CFG-based diffing is a thing.
by 082349872349872 4y ago
worth reading to the end: I knew about various arcane symbol formats, but TIL that cross-architecture CFG-based diffing is a thing.
- archi42 4y agoI am only little surprised that it works; after all, compiling a program for two platforms results in a mostly equivalent control flow graphs, except for optimizations and different code gen strategies (*); and of course platform specific stuff (but that was probably already abstracted for such a project back then). BUT I was very (pleasantly) surprised someone did go through the effort of implementing this and made it available for everyone as FOSS <3 (*, rant) I think inlining and tail call optimizations (especially calls into libc or the equivalent of the era) might cause the most trouble. Also loop generation can have subtle differences reflected in the CFG (not only loop unrolling, but also transforming a while-loop into a do-while-loop causes differences in the CFGs). Back then I'd also expect compilers not always perform equally well for "simple" things like dead code elimination. I wish I had the time to check out bindiff in detail, it's really interesting (personal bias: In the past I did work on static code analysis and had a supporting role in a compiler dev team).
- tdullien 4y agoOriginal author of the BinDiff tool (ca. 2004) here. BinDiff uses a good number of different algorithms to narrow the set of candidates for CFG-based matching -- so things like identical string references may be used to match a large function, and then basic blocks in that large function may be matched, and then BinDiff may identify that the functions called from these basic blocks will be identical, too. The entire field has exploded, and there are dozens of tools for function matching nowadays, some with very sophisticated ML approaches etc. - it is somewhat surprising that BinDiff still does it's job, considering that the core engine has not been modified or improved since 2010. I'd also like to extend kudos to https://twitter.com/admvonschneider https://twitter.com/admvonschneider -- he is the sole Googler sacrificing his 20% time to keep the tool alive...
- saagarjha 4y agoDid Google ever end up open sourcing BinDiff? I've always been curious at what goes under the hood.
- tdullien 4y agoSo that has been "in the works" for 7+ years, and I think it repeatedly stalls because someone needs to really drive it against the bureaucratic internal obstacles ... There's no reason they aren't doing it, except "nobody has time to do it".
- saagarjha 4y agoDo you think the result, if open sourced, would be worth it? Or is the code not particularly amenable to maintenance and integration?
- tdullien 4y agoNot sure if it'd be worth it, but it's reasonably clean C++ code, which is not terribly difficult to maintain & integrate.
- stevemk14ebr 4y agoThis would be kind of huge if this actually happened. As a researcher in the field, I hope someone can finally do this, please.
- saagarjha 4y agoSounds like it might be worth following up on and seeing where it stalled…
- tdullien 4y agoHappy to answer any questions btw :)