3 ms·

Happy to answer any questions btw :)

saagarjha 4y ago
Sure, I have a couple. I will warn you that I don’t know much about how BinDiff works, other than knowing it does :) The “Achilles heel” of binary differs is recompiling with different flags or making other minor changes that alter all basic blocks. Do you think the techniques BinDiff uses could be extended to work on “semantics” at a higher level rather than actual code? Like, doing the diff after an optimizing decompiler has run over it and lifted it. If you were writing BinDiff today, what new techniques would you integrate? Or are you happy with the algorithms as they are already? What kinds of things is BinDiff good at identifying? It’s often difficult to know beforehand “how well” a diff will work. How would you judge whether it’ll be worth it?
- tdullien 4y ago
  1) You could try to lift BinDiff to operate on the semantics more, but I am not entirely sure that it'd affect diffing quality. "Semantics" are a difficult thing to define at the assembly level: If your compiler optimizes less, and uses a stack slot instead of a register, the assembly-level semantics are actually changed. If you recompile using frame pointer omission, the assembly-level semantics are also changed. If you compile code for ARM/Thumb and ARM normally, different assembly-level semantics are emitted. So if you are trying to do diffing on the semantic level, you have to lift to high-level-language semantics, and account for stuff like /GS stack cookies etc. etc. - this path, madness lies. Even state-of-the-art decompilers tend not to generate the same C output if you decompile differently-compiled assembly. And all of this assumes that no inlining changes happen... It is more promising to use things that are "affected by semantics, but not excessively so". CFGs fall into the category, and a variety of other things are. BinDiff can sometimes work around heavily changing CFGs by using string references, relative positioning in the call graph, and a variety of other tricks. In general, if a function X that calls Y is properly matched, the odds that Y will be properly matched increase greatly. In a nutshell, BinDiffs algorithm is a "attempt to match two nodes in a graph (callgraph of CFG) using a variety of criteria (ordered from precise to loos) -- and each time a match is generated, try to generate additional matches in the neighborhood of the matched node by taking the new match into account". So you try to get high-fidelity matches first, if you get any, you propagate that information to generate more high-fidelity matches, and as time goes by your criteria for allowing two functions to match get looser and looser ... but hopefully you've already done good high-fidelity matches so this counterbalances the later recklessness of the algo. If I was writing BinDiff today ... wow, there's a million things I'd do differently. I last touched that engine in 2009 or so, and things that I've learnt since that'd be very helpful: 1. There's fantastic use of locality sensitive hashing to be applied here. There's a bit of work in the functionsimsearch github repo around this, but BinDiffs performance could be boosted significantly using these techniques. 2. There's a ton of good academic research on metric learning, and using ML to generate embeddings to then do similarity comparisons. If you combine this with (1), you will see a significant performance boost. 3. The algorithm is pretty sequential, I think it could be multi-cored reasonably easily. 4. I'd like to add a little bit more semantic diffing 5. I think one could very profitably use the distribution of constant offsets in a function as additional matching criteria ("two functions that have approximately similar data structure access might be the same"). 6. ... lots more ... Regarding "what is BinDiff good at" -- if you can get a bunch of initial high-fidelity matches, the overall success of the diffing process will be much higher than if the initial matches are poor. You can use BinDiff interactively and do incremental diffing -- look at the BinDiff config files, you can selectively disable individual matching criteria, and then start with an essentially empty diff, match a few functions manually, and then ask BinDiff to propagate them. Come to think of this, BinDiff tries too hard to solve vastly different use cases: A) Patch diffing, where you want to be very sensitive to even small changes B) Symbol porting, where you want to be very loose to small changes The tool should probably be split into two -- one matching phase, and one semantic analysis phase; and for the matching phase, making the interactive diffing experience better would be a great idea... In general, it blows my mind that BinDiff is still in use. I had expected a superior successor to arrive within 2-3 years of Google acquiring zynamics, I would have never expected that 10+ years on, without any change to the core engine, BinDiff still produces reasonably-ish results...
  - saagarjha 4y ago
    Thanks for the insight :)

Sure, I have a couple. I will warn you that I don’t know much about how BinDiff works, other than knowing it does :) The “Achilles heel” of binary differs is recompiling with different flags or making other minor changes that alter all basic blocks. Do you think the techniques BinDiff uses could be extended to work on “semantics” at a higher level rather than actual code? Like, doing the diff after an optimizing decompiler has run over it and lifted it. If you were writing BinDiff today, what new techniques would you integrate? Or are you happy with the algorithms as they are already? What kinds of things is BinDiff good at identifying? It’s often difficult to know beforehand “how well” a diff will work. How would you judge whether it’ll be worth it?

tdullien 4y ago
1) You could try to lift BinDiff to operate on the semantics more, but I am not entirely sure that it'd affect diffing quality. "Semantics" are a difficult thing to define at the assembly level: If your compiler optimizes less, and uses a stack slot instead of a register, the assembly-level semantics are actually changed. If you recompile using frame pointer omission, the assembly-level semantics are also changed. If you compile code for ARM/Thumb and ARM normally, different assembly-level semantics are emitted. So if you are trying to do diffing on the semantic level, you have to lift to high-level-language semantics, and account for stuff like /GS stack cookies etc. etc. - this path, madness lies. Even state-of-the-art decompilers tend not to generate the same C output if you decompile differently-compiled assembly. And all of this assumes that no inlining changes happen... It is more promising to use things that are "affected by semantics, but not excessively so". CFGs fall into the category, and a variety of other things are. BinDiff can sometimes work around heavily changing CFGs by using string references, relative positioning in the call graph, and a variety of other tricks. In general, if a function X that calls Y is properly matched, the odds that Y will be properly matched increase greatly. In a nutshell, BinDiffs algorithm is a "attempt to match two nodes in a graph (callgraph of CFG) using a variety of criteria (ordered from precise to loos) -- and each time a match is generated, try to generate additional matches in the neighborhood of the matched node by taking the new match into account". So you try to get high-fidelity matches first, if you get any, you propagate that information to generate more high-fidelity matches, and as time goes by your criteria for allowing two functions to match get looser and looser ... but hopefully you've already done good high-fidelity matches so this counterbalances the later recklessness of the algo. If I was writing BinDiff today ... wow, there's a million things I'd do differently. I last touched that engine in 2009 or so, and things that I've learnt since that'd be very helpful: 1. There's fantastic use of locality sensitive hashing to be applied here. There's a bit of work in the functionsimsearch github repo around this, but BinDiffs performance could be boosted significantly using these techniques. 2. There's a ton of good academic research on metric learning, and using ML to generate embeddings to then do similarity comparisons. If you combine this with (1), you will see a significant performance boost. 3. The algorithm is pretty sequential, I think it could be multi-cored reasonably easily. 4. I'd like to add a little bit more semantic diffing 5. I think one could very profitably use the distribution of constant offsets in a function as additional matching criteria ("two functions that have approximately similar data structure access might be the same"). 6. ... lots more ... Regarding "what is BinDiff good at" -- if you can get a bunch of initial high-fidelity matches, the overall success of the diffing process will be much higher than if the initial matches are poor. You can use BinDiff interactively and do incremental diffing -- look at the BinDiff config files, you can selectively disable individual matching criteria, and then start with an essentially empty diff, match a few functions manually, and then ask BinDiff to propagate them. Come to think of this, BinDiff tries too hard to solve vastly different use cases: A) Patch diffing, where you want to be very sensitive to even small changes B) Symbol porting, where you want to be very loose to small changes The tool should probably be split into two -- one matching phase, and one semantic analysis phase; and for the matching phase, making the interactive diffing experience better would be a great idea... In general, it blows my mind that BinDiff is still in use. I had expected a superior successor to arrive within 2-3 years of Google acquiring zynamics, I would have never expected that 10+ years on, without any change to the core engine, BinDiff still produces reasonably-ish results...
- saagarjha 4y ago
  Thanks for the insight :)