Similarity score is capped at 0.65 for binaries with no flow graph edges
Nobody has claimed this yet.
Assessment
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Newbie friendliness
- 78/100
- Issue type
- Bug
- Clarity
- Clearly specified
- Activity status
- Active
- Tech stack
- cpp
- Domain
- reverse-engineering
Research direction
Start in bindiff/differ.cc at the CallGraph overload of GetSimilarityScore(), especially the flow-graph edge match calculation cited in the issue. Reproduce the self-diff with no_jumps.BinExport, then verify that binaries with zero edges on both sides score approximately 1.0 while a one-sided zero-edge case retains the current behavior.
Written by the indexing model from the issue text.
Description
Describe the bug
The CallGraph overload of GetSimilarityScore() in bindiff/differ.cc weights the CFG edge match ratio at 0.35 of the total program similarity score. When a binary has no flow graph edges, that term is 0.35 * 0 = 0, so the score can never exceed 0.65 even when the binary is diffed against itself.
Relevant code from commit 4b643a1:
similarity +=
0.35 * counts[Counts::kFlowGraphEdgeMatchesNonLibrary] /
(std::max(1.0,
0.5 * (counts[Counts::kFlowGraphEdgesPrimaryNonLibrary] +
counts[Counts::kFlowGraphEdgesSecondaryNonLibrary])));
To Reproduce
Steps to reproduce the behavior:
- Assemble the attached
no_jumps.asmwith NASM (or use the attachedno_jumpsbinary). It contains a single function with one basic block, so the binary has no flow graph edges. With no calls, the call graph MD index is also trivially equal on both sides, which isolates the edge term. - Export it with BinExport from IDA Pro, or use the attached
no_jumps.BinExport. - Diff the export against itself:
bindiff no_jumps.BinExport no_jumps.BinExport - Observe similarity of 64.565% (0.65 × 0.9933 confidence) despite 1/1 functions matched and both sides being identical.
Expected behavior
A self-diff should report similarity ≈ 1.0.
Screenshots
Environment:
- OS and version: Ubuntu 24.04 LTS
- Locale: en-US
- Disassembler and version: IDA Pro 9.3
- BinDiff: built from
4b643a1
Additional context
Attached: no_jumps.asm, no_jumps (the compiled binary), and no_jumps.BinExport.
Suggested fix: when both kFlowGraphEdgesPrimaryNonLibrary and kFlowGraphEdgesSecondaryNonLibrary are 0, treat the edge term as a full match (contribute 0.35), since there is nothing to disagree about. When only one side has 0 edges, keep the current behavior of contributing 0, since the two binaries differ in control flow. Happy to send a PR if that approach is acceptable.
- Dominant language
- Java
- Stars
- 3.2k
- Forks
- 240
- PR merge metrics
- No merged PRs in 30d
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from google/bindiff
-
question
Difficulty 3/5 1-2 days Newbie friendliness 42/100
-
Difficulty 4/5 3-5 days Newbie friendliness 35/100
-
Difficulty 1/5 Under an hour Newbie friendliness 55/100
-
Difficulty 5/5 Over a week Newbie friendliness 15/100
-
enhancement
Difficulty 4/5 3-5 days Newbie friendliness 35/100
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
infinispan/infinispan#18150 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
-
untriaged
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
opensearch-project/k-NN#3597 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 82/100