Recall-Oriented Precise Binary-to-Source Function Matching

Motivation

• Existing embedding-based methods restrict final results to retrieved candidates, while inlining can combine multiple source functions into one binary function.The paper identifies both as shortcomings of prior approaches.Source: §1 · pp. 1–2

Approach

• BScout uses positional information to filter matches and supplement candidates for unresolved binary functions, extending results beyond initial embedding-based retrieval.It also uses LLMs to refine candidates and outputs a 1-to-1 binary-source function mapping.Source: §1 · p. 2
• Composition-aware training accounts for multiple source functions in an inlined binary function, while chunk-based full-function embeddings support long functions.The paper presents these as responses to the inlining challenge and long-function handling.Source: §1 · p. 2

Results

• At least 32% precision improvement and about 2.9 times the recall on large stripped binaries distinguish BScout from BinaryAI and SBridge.Across the evaluated datasets, BScout achieves the best comprehensive performance, high precision in all cases, and enhanced recall over embedding-based matching results.Source: §1 · p. 2

Evaluation

• BScout was evaluated on a public dataset and a manually collected dataset containing large software binaries and popular TPLs as source corpus.The paper reports acceptable efficiency and cost for large-scale matching.Source: §1 · p. 2

2.1 Function Retrieval under Multi-Source Composition

• Inlining combines multiple source functions into one binary function, producing noisy and dissimilar presentations that make embedding-based retrieval difficult.The example describes an entry function and two implementations, with inlining eliminating some calls and repeating others.Source: §2.1 · p. 3
• Composition-aware training teaches the model relations between the binary function and each composition, including major compositions.In the example, the second and third source functions rank within the top five among one million source functions.Source: §2.1 · p. 3

2.2 Reliable Matching with Incomplete Candidate Sets

• A correct match may sit outside the initial candidates: in the example it ranks twentieth while the LLM selects a false candidate ranked tenth.Positional information supplements candidates from a source file associated with nearby matches, after which the LLM selects the correct function.Source: §2.2 · p. 4

3.1 Overview

• BScout uses embedding-based retrieval first, then refines candidates with chat-style LLMs and positional information to report matching results.The refinement also seeks candidates for unresolved binary functions.Source: §3.1 · p. 5

3.2.1 Full-Function Embedding and Retrieval.

• Functions are split into contiguous 512-token chunks, independently embedded, and combined into a full-function embedding for retrieval.For training functions exceeding eight chunks, the method retains the first and last chunks and randomly samples six others.Source: §3.2.1 · pp. 5–6

3.2.2 Function Composition-Aware Training.

• Composition-aware training weights source functions by their contributions to an inlined binary function and further rewards major contributors.The training loss balances learning across all compositions and major ones.Source: §3.2.2 · pp. 6–7

3.3.1 Interval construction.

• Intervals group continuous binary functions between same-file anchors, subject to a size constraint; overlapping same-file intervals may be merged.Anchors that cannot form or belong to an interval remain individual points.Source: §3.3.1 · p. 7

3.3.2 Candidate supplementation.

• For unresolved functions inside or near an interval, BScout supplements candidates from nearby source functions associated with the nearest anchors.The method scores candidates using names, callees, signatures, code lengths, positions, and prior matches or file membership.Source: §3.3.2 · pp. 7–8, Figure 5 · p. 8

3.3.3 LLM as a judge.

• The LLM selects or rejects candidates, reviews same-name, individual-anchor, and N-to-1 matches, and assesses whether a TPL is reused.A high-confidence “no” TPL assessment leads BScout to remove matches associated with that TPL.Source: §3.3.3 · p. 8

3.3.4 Filtering.

• Filtering removes contextually inconsistent candidates and anomalously large N-to-1 matches, while structural filtering retains newly added matches that meet interval conditions.Structural filtering can require similarity of at least 0.6 for qualifying newly added intervals.Source: §3.3.4 · p. 9

3.3.5 High-confidence TPL revisiting.

• BScout revisits unresolved functions for high-confidence TPLs, retrieving that TPL’s candidates over an adaptive threshold for further verification.High confidence can come from an LLM “yes” or a dominant TPL match count meeting the stated criteria.Source: §3.3.5 · p. 9

• The evaluation uses a prototype of BScout and, unless otherwise specified, reports results from a single round.Source: §4 · p. 9
• The first research question asks how effective BScout is in binary-to-source function matching.Source: §4 · p. 9
• The other research questions examine the proposed techniques and BScout’s efficiency and cost.Source: §4 · p. 9

4.1.1 Datasets.

• More than one-quarter of training/validation functions and one-third of Large-10 functions contain inlined source functions; BinKit-BCSA is simpler, with nearly one-tenth showing inlining.The testing datasets also differ from training in binary-function length distributions.Source: §4.1.1 · p. 10

4.1.2 Implementation.

• BScout is implemented with Qwen models and trained for 10 epochs, taking about 12 days on three NVIDIA RTX 5880 Ada-48GB GPUs.The implementation uses LoRA fine-tuning and a batch size of 384.Source: §4.1.2 · p. 10

4.1.3 Baselines.

• SBridge was run without modification, but its Large-10 evaluation omitted the extra 120 TPLs and took more than two months.For BinKit-BCSA, SBridge used all 122 programs as its source corpus.Source: §4.1.3 · p. 11

4.1.4 Metrics.

• Final matching is evaluated with precision, recall, and F1; retrieval-stage performance uses R@k and MRR.SBridge’s top-1 candidate is treated as its final result because it does not report confident-match or no-match decisions.Source: §4.1.4 · p. 11

4.2 Overall Effectiveness

• 77.21% vs. 9.45% precision on stripped BinKit-BCSA lets BScout-9B achieve high comprehensive performance despite lower recall than BinaryAI.Across the dataset, BScout-9B has the best precision, while BScout-Flash has the highest recall and F1 in each category and overall.Source: §4.2 · p. 12
• On Large-10, BScout-Flash achieves the best recall in all cases, and BScout-9B achieves the best precision in most cases.SBridge nearly failed to select corresponding source functions as top-1 candidates across the software projects.Source: §4.2 · p. 12
• BScout-9B reports fewer matches and is more precise than BScout-Flash, especially for stripped binaries, but may miss correct candidates during supplementation.The paper attributes this risk to fewer reliable anchors and intervals, which can lead to correct supplemented candidates being rejected.Source: §4.2 · pp. 12–13
• BScout’s overall performance surpasses the baselines with either backend LLM.Source: §4.2 · p. 13

4.3 Effectiveness of Full-Function Retrieval and Composition-Aware Training

• Full-function embedding with all compositions and major compositions performs best among the six tested configurations.For multi-source function matches, this approach raises R@10 from 46.55% to 55.47%, an improvement of at least 8.92%.Source: §4.3 · p. 13
• Combining all-composition and major-composition factors performs better than using either factor alone.The all-composition factor is more effective than the major-composition factor when each is used separately.Source: §4.3 · p. 13
• BScout yields 10 times as many multi-source functions with at least two compositions in the top 10 as BinaryAI.The reported comparison is 42.97 versus 3.86; Table 5 reports results for at least one or two compositions in R@10.Source: §4.3 · p. 13
• The results support the effectiveness of full-function embedding and composition-aware training, particularly for multi-source retrieval.Source: §4.3 · p. 14

4.4.1 Necessity of Stage 2.

• Stage 2 greatly improves precision and also enhances recall over taking stage 1’s top-1 candidate as the result.About one-tenth of BinKit-BCSA’s and one-seventh of Large-10’s matches are newly found beyond stage 1’s top 10; most are correct.Source: §4.4.1 · p. 14

4.4.2 Ablation Study of Two Essential Techniques in Stage 2.

• Removing the LLM reduces precision substantially, while disabling candidate supplementation reduces both precision and recall.Supplementation-disabled results miss newly found matches; compared with removing the LLM, they retain relatively higher precision and F1.Source: §4.4.2 · p. 15

4.4.3 Effect of Each Update Step in Stage 2.

• The first LLM selection step raises precision from 30.82% to 71.59%, while the first candidate supplementation yields the largest recall gain, 5.07%.Precision continues to rise through subsequent selection steps, while addressing high-confidence TPLs brings recall and F1 to their highest points in round 1.Source: §4.4.3 · p. 15, Table 8 · p. 15
• Users can stop at different update steps to trade precision against recall.Source: §4.4.3 · p. 15

4.4.4 Effect of More Rounds.

• A second round yields higher recall than round 1 and higher F1, but lower precision than round 1’s final result.Its API cost is twice that of round 1, and the performance gain is described as marginal.Source: §4.4.4 · p. 16

4.5 Efficiency and Cost

• Stage 2 takes 15 seconds, 24 minutes, and 35 minutes per binary across the three datasets, with non-LLM analysis accounting for 21.6%–47.0% of the time.For Large-10-stripped, average total time is 50 minutes; stage 1 matching is the unstable component and grows linearly with source-corpus size.Source: §4.5 · p. 16
• API cost averages about 0.01 USD per BinKit-BCSA binary and approximately 3–5 USD per Large-10 binary.API calls, token use, and cost are bounded by binary size.Source: §4.5 · p. 16
• The reported efficiency and costs make BScout practical for matching real-world large software against a large source corpus.The efficiency evaluation covers a single BScout-Flash refinement round.Source: §4.5 · p. 16

Function representation and composition supervision

• Independent chunk encoding does not explicitly model relationships across chunks, potentially limiting function representations under the available computing resources.With sufficient GPUs, the authors say full-function embedding could be performed in one go and used during training.Source: §5 · p. 16

Position-driven candidate supplementation

• Candidate supplementation depends on positional evidence from existing matches, so sparse anchors or unreliable TPL clues can leave functions unresolved.Supplemented candidates may still be incorrect and require LLM selection and subsequent filtering; recovering more matches trades off against rejecting unreliable ones.Source: §5 · p. 17

Backend LLM and refinement rounds

• Backend model choice and refinement-round count trade matching quality against deployment, privacy, computational, and API-cost constraints.On Large-10-stripped, a second BScout-Flash round improves recall and F1 but reduces precision, with substantial additional API cost.Source: §5 · p. 17

LLM-assisted refinement of decompiled code

• LLM-refined decompiled code can resemble source code in some cases but differ significantly in others, and its effects on refinement and retrieval need further evaluation.Source: §5 · p. 17

Threats to validity

• Ground-truth and dataset coverage limit the evaluation: missing valid correspondences can make precision and recall appear lower, and performance on other programs and build configurations remains unevaluated.BinKit-BCSA covers varied architectures and build conditions but only small utility programs; Large-10 covers larger projects but only x86-64 with O2.Source: §5 · p. 17

6.1 Binary-to-Source Function Matching and Software Composition Analysis

• Earlier binary-to-source matching uses traceable features, shared embeddings, link-time locality, or control-block comparisons, while composition analysis also targets libraries, modules, and reuse patterns.The cited work additionally examines build configurations, modified reuse, dependencies, vulnerabilities, and library versions.Source: §6.1 · pp. 17–18

6.2 Function Representations and Inlining-Aware Matching

• Function representations encode control flow, dependencies, instruction semantics, or code chunks, while inlining-aware methods address the multiple source functions that can contribute to one binary function.BScout builds on contrastive learning and emphasizes major contributors during composition-aware training.Source: §6.2 · p. 18

6.3 Structural Context and LLM-Assisted Matching

• Prior work uses domain knowledge, dependencies, environmental relationships, or call context, while LLM-assisted systems retrieve and verify candidates or propagate matches along call relations.BScout uses positional information both to filter and to supplement candidates beyond initial retrieval.Source: §6.3 · p. 18

7 Conclusion

• BScout combines full-function embeddings and composition-aware training to handle long functions and multiple source compositions introduced by inlining.Source: §7 · p. 18
• Backend LLMs select and review matches, while positional information filters inconsistent matches and supplements candidates for unresolved binary functions beyond initial retrieval.Source: §7 · p. 18
• BScout achieves higher overall precision, recall, and F1 than the state-of-the-art competitors, with acceptable efficiency and cost on large software and TPLs.Source: §7 · p. 18