google / google/bindiff

Similarity score is capped at 0.65 for binaries with no flow graph edges

Open Beginner friendly
#90 1 comment 0 reactions 0 assignees View on GitHub
bug
Dominant language
Java
Stars
3.2k
Forks
240
PR merge metrics
No merged PRs in 30d

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`](https://www.github.com/google/bindiff/blob/4b643a1b234063c7a1590a832e7817f04cd85a95/differ.cc#L549-L579):
```cpp
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:

1. Assemble the attached `no_jumps.asm` with NASM (or use the attached `no_jumps` binary). 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.
2. Export it with BinExport from IDA Pro, or use the attached `no_jumps.BinExport`.
3. Diff the export against itself: `bindiff no_jumps.BinExport no_jumps.BinExport`
4. 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**

Image

**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`.

[no_jumps.zip](https://github.com/user-attachments/files/32106764/no_jumps.zip)

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.

Contributor guide

Open the contributing guide

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.

Assessment

Tech stack
cpp
Domain
reverse-engineering
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
78/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.