[GH-ISSUE #6407] [Design] Ranked, non-binding counterpart candidates for unmatched functions in match_native_functions #3839

New issue

Open

opened 2026-10-31 00:44:31 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-31 00:44:31 +00:00

Owner

Originally created by @coygeek on GitHub (Oct 22, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/6407

Before submitting

I searched the open and closed issues and pull requests for a related discussion.
I understand the contribution scope must be reviewed before integration; open questions are welcome here.
This discussion does not include credentials, private samples, or sensitive target data.

Decision needed

Should match_native_functions offer an opt-in list of ranked counterpart candidates for functions it leaves only_left, only_right or unresolved, with each score backed by the observed facts that produced it, and if so, which facts and anchoring rules may contribute without weakening its exact-match contract?

Context and evidence

Examined at REA main e83e3ceadd (source reading; the tool is not in the 6.7.0 release). Matching is exact by design: name, then body SHA-256, then an optional structural fingerprint that only "connect[s] unresolved candidate groups" (docs/native-function-matching.md). The structural fingerprint (src/domain/native/functionStructuralCandidate.ts) returns nothing unless the dossier has an identical normalized CFG including block sizes, complete call coverage, non-empty calls or strings, and every callee name is not an auto-name. isAutoName treats FUN_…, sub_… and fcn.… as auto-names (src/domain/functionComparisonNormalization.ts).

Inferred consequence: in a stripped build most internal callees are FUN_…, and a security patch usually changes at least one block size, so the patched function — the one an analyst most wants — lands in only_left / only_right with no hint where its counterpart is. The analyst then has to compare candidates by hand with compare_functions, one pair at a time. Not yet measured on a real stripped build pair; that measurement is part of the proposal's verification.

Existing scope decisions point the same way: #4395 lists "fuzzy or similarity-based function matching" as "a separate problem", and #5343 (closed, delivered exact matching) left remaining functions unknown. No issue tracks the similarity side.

Expected interaction with targets

Read existing files or captured data

Boundary details (optional)

Input is existing authenticated Evidence (inventories and optional analyze_function dossiers); nothing is executed. Invariants the candidates must keep: they never change matched / only_* / unresolved states, never force 1:1 pairing, and are labelled as candidates with their score and contributing facts. Non-goals: claiming behavioral equivalence (that is #4972) and acquiring dossiers implicitly (their cost should stay visible to the caller, as the matching docs already require).

Options and tradeoffs

A. Feature-vector similarity over dossier facts: CFG shape statistics (block and edge counts, loop count), imported-callee names, referenced strings, constants. Cheap and order-free, but weak alone on small functions.
B. Anchor propagation in the style of BinDiff or Ghidra Version Tracking: start from already-matched pairs and rank unmatched callees/callers of matched functions by call-graph position, then by A's facts. Stronger on stripped builds; needs call-graph facts on both sides.
C. Delegate to an external differ (BinDiff/Diaphora) as a provider. Mature algorithms, but adds a provider, and their results would need re-expression as Evidence.

My preference is B with A as the tiebreaker, but this is the decision requested.

Verification available so far

I can suggest a sample or manual check

Success criteria and open questions

On a variant of tests/fixtures/nativeFunctionMatching.c in which both builds are stripped and the changed function's block sizes differ, the changed function's true counterpart ranks first and the result's matched / only_* / unresolved groups are byte-for-byte the same as with candidates off.
Identical-code aliases stay unresolved rather than receiving a confident candidate.
On one real pair of stripped builds, report the rate of wrong top-ranked candidates with its denominator, token cost and elapsed time.
Open: should candidates be emitted only for functions whose dossiers the caller already supplied, or should the tool ask for specific dossiers?
Open: how should candidate scores be exposed so an agent does not read them as probabilities?

References

Design cautions for a similarity score: a constant feature or all-positive feature vectors inflate cosine similarity between unrelated functions, counts of callees and strings without their identities discriminate poorly, and a forced 1:1 assignment manufactures pairs that should stay unresolved.
Related: #4395, #5343, #5390, #1947, #3506, #4972.

Originally created by @coygeek on GitHub (Oct 22, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/6407 ### Before submitting - [X] I searched the open and closed issues and pull requests for a related discussion. - [X] I understand the [contribution scope](https://github.com/morluto/rea/blob/main/CONTRIBUTING.md#contribution-scope) must be reviewed before integration; open questions are welcome here. - [X] This discussion does not include credentials, private samples, or sensitive target data. ### Decision needed Should `match_native_functions` offer an opt-in list of ranked counterpart candidates for functions it leaves `only_left`, `only_right` or `unresolved`, with each score backed by the observed facts that produced it, and if so, which facts and anchoring rules may contribute without weakening its exact-match contract? ### Context and evidence Examined at REA `main` e83e3ceadd97770a50b8afa97f4077916e4d2b81 (source reading; the tool is not in the 6.7.0 release). Matching is exact by design: name, then body SHA-256, then an optional structural fingerprint that only "connect[s] unresolved candidate groups" (`docs/native-function-matching.md`). The structural fingerprint (`src/domain/native/functionStructuralCandidate.ts`) returns nothing unless the dossier has an identical normalized CFG including block sizes, complete call coverage, non-empty calls or strings, and every callee name is not an auto-name. `isAutoName` treats `FUN_…`, `sub_…` and `fcn.…` as auto-names (`src/domain/functionComparisonNormalization.ts`). Inferred consequence: in a stripped build most internal callees are `FUN_…`, and a security patch usually changes at least one block size, so the patched function — the one an analyst most wants — lands in `only_left` / `only_right` with no hint where its counterpart is. The analyst then has to compare candidates by hand with `compare_functions`, one pair at a time. Not yet measured on a real stripped build pair; that measurement is part of the proposal's verification. Existing scope decisions point the same way: #4395 lists "fuzzy or similarity-based function matching" as "a separate problem", and #5343 (closed, delivered exact matching) left remaining functions unknown. No issue tracks the similarity side. ### Expected interaction with targets - Read existing files or captured data ### Boundary details (optional) Input is existing authenticated Evidence (inventories and optional `analyze_function` dossiers); nothing is executed. Invariants the candidates must keep: they never change matched / `only_*` / `unresolved` states, never force 1:1 pairing, and are labelled as candidates with their score and contributing facts. Non-goals: claiming behavioral equivalence (that is #4972) and acquiring dossiers implicitly (their cost should stay visible to the caller, as the matching docs already require). ### Options and tradeoffs - A. Feature-vector similarity over dossier facts: CFG shape statistics (block and edge counts, loop count), imported-callee names, referenced strings, constants. Cheap and order-free, but weak alone on small functions. - B. Anchor propagation in the style of BinDiff or Ghidra Version Tracking: start from already-matched pairs and rank unmatched callees/callers of matched functions by call-graph position, then by A's facts. Stronger on stripped builds; needs call-graph facts on both sides. - C. Delegate to an external differ (BinDiff/Diaphora) as a provider. Mature algorithms, but adds a provider, and their results would need re-expression as Evidence. My preference is B with A as the tiebreaker, but this is the decision requested. ### Verification available so far I can suggest a sample or manual check ### Success criteria and open questions - On a variant of `tests/fixtures/nativeFunctionMatching.c` in which both builds are stripped and the changed function's block sizes differ, the changed function's true counterpart ranks first and the result's matched / `only_*` / `unresolved` groups are byte-for-byte the same as with candidates off. - Identical-code aliases stay unresolved rather than receiving a confident candidate. - On one real pair of stripped builds, report the rate of wrong top-ranked candidates with its denominator, token cost and elapsed time. - Open: should candidates be emitted only for functions whose dossiers the caller already supplied, or should the tool ask for specific dossiers? - Open: how should candidate scores be exposed so an agent does not read them as probabilities? ### References - Design cautions for a similarity score: a constant feature or all-positive feature vectors inflate cosine similarity between unrelated functions, counts of callees and strings without their identities discriminate poorly, and a forced 1:1 assignment manufactures pairs that should stay unresolved. - Related: #4395, #5343, #5390, #1947, #3506, #4972.

bsakaguchi referenced this issue

2026-10-31 01:10:37 +00:00

[PR #3846] [CLOSED] fix(javascript): bound getter reference expansion #5943

bsakaguchi referenced this issue

2026-10-31 01:10:42 +00:00

[PR #3857] [CLOSED] fix(javascript): scope this emitters to the receiver that binds them #5953

bsakaguchi referenced this issue

2026-10-31 01:10:42 +00:00

[PR #3860] [MERGED] fix(javascript): reject Webpack getters replaced through any identity write #5955

bsakaguchi referenced this issue

2026-10-31 01:10:44 +00:00

[PR #3897] [MERGED] fix(javascript): keep releases through a replaced handle as candidates #5957