acceptodds
Under review as a conference paper at ICLR 2027

APRM: Learning Binary Function Representations with Radially Ordered Context

Abstract

Node-level graph representation learning often requires encoding a directed, variable-size neighborhood into a fixed-dimensional representation. We study this problem in binary code similarity detection (BCSD), where compiled instances of the same source-level function are mapped to comparable representations. Compilation can change the target function and its surrounding function call graph (FCG). Therefore, absolute depth and node membership can differ across compilation pairs. However, among source-matched function nodes present in both FCGs, relative radial order and the directions of pairwise ancestor relations are often preserved. We introduce Augmented Predecessor-Radial Moments (APRM), a graph readout conditioned on the root function. APRM combines a normalized root-relative radial coordinate with signed contrasts between each node and its shortest-path predecessors within the same FCG. Across four fixed upstream encoders and four compilation conditions, APRM improves mean Macro Recall@1 from 6.48% to 14.75% on galleries containing 10,000 functions. APRM also outperforms four matched message-passing baselines, with the strongest baseline reaching 12.75% under the same retrieval protocol. On Dataset-1, an external BCSD benchmark introduced by Marcelli et al., APRM improves retrieval without using target data for training, checkpoint selection, or adaptation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Representation Learning, Graph Readout, Structural Inductive Biases, Directed Graphs, Binary Code Similarity Detection, Cross-Compilation Retrieval

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_ugkGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper observes that, in binary code similarity detection (BCSD), function call graph (FCG) membership and absolute shortest-path depths may change across compilations. However, among source-matched descendant functions present in both FCGs, relative radial order and the directions of pairwise ancestor relations are often preserved. Motivated by this observation, the authors propose Radial Context Encoding to capture root-relative radial positions and Signed Predecessor Contrasts to model directed representation changes between nodes and their shortest-path predecessors. Experimental results demonstrate that the proposed method significantly improves binary function similarity retrieval performance.

Critical strengths
  1. Well-motivated problem and structure-aware design. The paper identifies that relative radial order and ancestor-relation directions among source-matched functions are often preserved across compilations, despite changes in FCG membership and absolute shortest-path depth. This empirical observation provides a meaningful motivation for the proposed radial context encoding and signed predecessor contrasts.

  2. Consistent performance improvements across multiple settings. APRM improves retrieval performance across four upstream encoders and four compilation conditions, increasing the average Macro Recall@1 from 6.48% to 14.75%. It also outperforms four matched message-passing baselines, supporting the effectiveness of the proposed approach beyond simply incorporating FCG context.

Critical weaknesses
  1. Insufficient justification for the compilation robustness of the proposed radial encoding. Figure 1(a) illustrates that compilation-induced changes in the function call graph can alter both node membership and shortest-path hop distances. Although the proposed Radial Context Encoding replaces absolute hop distances with empirical-CDF-based coordinates, these coordinates still depend on hop assignments and the distribution of nodes across radial shells. Consequently, even when the relative radial order of matched functions is preserved, their encoded radial coordinates may change across compilations.

  2. Limited coverage of structural preservation analysis. The reported 95.25% radial-order agreement is calculated on only 32.30% of the 150,000 compilation pairs that meet the eligibility criteria. Moreover, shared-node coverage is relatively low under challenging compilation conditions, such as XM (23.2%). It remains unclear whether the proposed structural assumptions hold or provide benefits when FCGs undergo substantial changes.

  3. Limited analysis of Signed Predecessor Contrasts. Signed differences between node and predecessor representations do not necessarily capture meaningful call-direction semantics. Moreover, aggregating such differences may cause intermediate-node information to cancel out in certain graph structures. The paper lacks sufficient theoretical or empirical analysis demonstrating the structural expressiveness and necessity of this component.

Questions for authors
  1. Radial encoding robustness: How does the proposed CDF-based radial encoding remain robust to compilation-induced changes in hop distances and shell sizes?

  2. Does APRM maintain its performance improvements on compilation pairs with low shared-node coverage, particularly under the XM setting?

  3. Signed Predecessor Contrasts: How does the proposed contrast mechanism preserve meaningful structural information when predecessor relationships change or intermediate-node differences cancel out? What evidence supports its structural expressiveness?

5 comments

We thank the reviewer for the clear summary and for the three precise technical questions. We answer each with an analysis, an existing control, and a planned addition.


Comment 1 (Weakness 1 and Question 1)

Insufficient justification for the compilation robustness of the proposed radial encoding. [...] these coordinates still depend on hop assignments and the distribution of nodes across radial shells. Consequently, even when the relative radial order of matched functions is preserved, their encoded radial coordinates may change across compilations.

Radial encoding robustness: How does the proposed CDF-based radial encoding remain robust to compilation-induced changes in hop distances and shell sizes?

Response. The CDF coordinate is normalized by the observed radial distribution. Thus, a uniform shift in absolute hop depth does not alter the relative coordinate when the retained shell order is preserved. More generally, when the order and tie pattern of shared nodes are preserved, changes in shell occupancy are controlled by the non-shared mass, yielding the conditional bound below.

A drift bound. Let S be the source-matched context nodes present in both graphs, N_r the number of retained context nodes in graph r, and c_r = |S| / N_r the shared fraction. For a shared node v, counting the nodes before and in its shell separately for shared and non-shared nodes gives

u_r(v) = c_r u^S_r(v) + (1 - c_r) ũ_r(v),

where u^S_r(v) is the same midpoint CDF computed on S alone and ũ_r(v) in [0, 1] is computed on the non-shared nodes. The term u^S_r(v) depends on the tie-aware shell structure among shared nodes. If the shared-node order and tie pattern are preserved, then u^S_r(v) = u^S_r'(π(v)) and

|u_r(v) - u_r'(π(v))| ≤ (1 - c_r) + (1 - c_r').

Three consequences follow.

  1. A uniform shift of depths, for example an inserted wrapper that pushes every callee one hop deeper, does not alter the relative ordering of the retained nodes. If wrapper nodes are newly retained, their effect enters through their contribution to the empirical radial distribution. By contrast, the normalized hop h_r(v)/K moves every coordinate by 1/K = 0.2 and can push nodes past the K-hop limit.
  2. Under the stated order and tie conditions, drift is controlled by the non-shared fraction rather than by an absolute hop shift.
  3. The derivative of every cubic Bernstein basis is at most 3 in absolute value, so each basis weight changes by at most three times the coordinate change.

We also measured the actual cross-compilation change of the coordinates on the 150,000 training pairs. Of these, 74,978 pairs share at least one source-matched descendant (48,445 meet the eligibility criterion, matching Appendix B.2), and these pairs contain 833,562 shared descendants. For a shared descendant v, the change is |u_r(v) - u_r'(π(v))| between the two builds; a per-pair value averages this change over the shared descendants of the pair.

StatisticUnit of analysisNValue
Mean change of the CDF midpointShared descendant833,5620.052
90th percentile of the changeShared descendant833,5620.172
Mean of per-pair mean changePair with a shared descendant74,9780.048
Mean of per-pair mean changeEligible pair48,4450.055
Mean of per-pair mean L1 change of the four Bernstein weightsEligible pair48,4450.177

By compilation task, the same per-pair statistic on the eligible pairs is:

Eligible pairs by taskXCXAXOXM
N6,41914,05121,3266,649
Mean of per-pair mean change0.0760.0200.0630.085

Across the two builds, 85.4% of the shared descendants keep the same hop. The bound above held in all 448,533 node checks of the 62,065 pairs whose shared-node order and ties are exactly preserved, with the observed change averaging 10% of the bound and at most 93%.

What retrieval accuracy shows. We also retrained the TREX radial-state stage and the contrast stage from scratch with each coordinate (seeds 42 to 44, validation-only selection). The CDF midpoint and h_r(v)/K reach 16.89% and 16.83% Macro Recall@1, while a collapsed constant coordinate reaches 14.44%. These results support the usefulness of a non-degenerate radial position and identify the CDF midpoint as a reasonable graph-normalized coordinate choice for APRM.

Revision. The revised manuscript now gives the drift bound and its derivation in Appendix A.5, clarifies the normalized-coordinate interpretation in Section 3.2, and reports the retrained coordinate comparison in Section 4.4.

Comment 2 (Weakness 2 and Question 2)

Limited coverage of structural preservation analysis. The reported 95.25% radial-order agreement is calculated on only 32.30% of the 150,000 compilation pairs that meet the eligibility criteria. Moreover, shared-node coverage is relatively low under challenging compilation conditions, such as XM (23.2%). It remains unclear whether the proposed structural assumptions hold or provide benefits when FCGs undergo substantial changes.

Does APRM maintain its performance improvements on compilation pairs with low shared-node coverage, particularly under the XM setting?

Response. In the evaluated low-coverage strata, APRM retains positive XM gains. The 32.30% and 23.2% figures are aggregate quantities over all pairs, including functions with no context; the breakdown below separates this aggregate view from pairs with context in both builds.

What the 32.30% and 23.2% figures include. Both are computed over all 150,000 pairs, including functions with no context. In 41.57% of all pairs, the target function has no retained descendant in either build. For these leaf functions, APRM's context is empty and APRM reduces exactly to the root path, so no structural assumption is involved. Among the 82,384 pairs with context in both builds, 58.8% meet the eligibility criterion, and almost all of the rest (94.4%) have fewer than three shared descendants. For XM, the 23.2% value is the aggregate over all XM pairs; among XM pairs with context in both builds, the mean shared-node coverage is 53.9%.

Does the regularity hold when coverage is low? Within the eligible pairs, agreement stays well above the random control across the reported coverage bins.

C_sharedEligible pairsObserved agreementRandom control
[0.10, 0.25)42793.25%39.89%
[0.25, 0.50)4,48693.73%37.39%
[0.50, 0.75)10,38391.04%37.44%
[0.75, 1.00]33,14196.81%40.07%

The bin below 0.10 contains only 8 pairs (83.33% versus 40.78%). For XM pairs with C_shared below 0.25, agreement is 90.10% versus 39.84% (231 pairs).

APRM under XM. XM Recall@1 improves for every encoder, from 3.05% to 11.97% for Gemini, from 3.21% to 9.07% for TREX, from 1.14% to 5.59% for DiEmph, and from 2.76% to 4.67% for CodeART, so the four-encoder mean rises from 2.54% to 7.83% (Table 1).

Gains as a function of coverage. Using raw frozen Base Encoder vectors, the four-encoder XM R@1 values on the 4,000-query validation bridge are:

XM coverage stratumBase R@1 (%)APRM R@1 (%)Gain (pp)95% CI (pp)
Undefined (both graphs root-only)11.1911.32+0.12[-1.14, +0.83]
Low (below 0.25)1.102.88+1.78[+0.82, +2.79]
Medium (0.25 to 0.75)1.934.75+2.81[+1.59, +4.03]
High (0.75 or more)4.5810.81+6.23[+2.03, +13.23]

The intervals are project-clustered. The point estimate of the XM gain is positive in the low, medium, and high coverage strata and increases across these strata in this validation bridge.

On the held-out test, the four-encoder gain is positive whenever the smaller of the two retained graphs has at least half the nodes of the larger one: +1.23 points (95% interval [+1.05, +1.66]) for size ratios from 0.50 to 0.75 and +10.48 points ([+7.34, +14.91]) at 0.75 or above, which covers 3,655 of the 4,000 test queries (91.4%).

Revision. The revised manuscript now reports the eligibility breakdown and the held-out graph-size-ratio analysis in Section 4.3 and Appendix B.2/B.3. The raw-Base XM validation bridge is provided as an additional diagnostic in this response.

Comment 3 (Weakness 3 and Question 3)

Limited analysis of Signed Predecessor Contrasts. Signed differences between node and predecessor representations do not necessarily capture meaningful call-direction semantics. Moreover, aggregating such differences may cause intermediate-node information to cancel out in certain graph structures. The paper lacks sufficient theoretical or empirical analysis demonstrating the structural expressiveness and necessity of this component.

Signed Predecessor Contrasts: How does the proposed contrast mechanism preserve meaningful structural information when predecessor relationships change or intermediate-node differences cancel out? What evidence supports its structural expressiveness?

Response. The signed contrast adds predecessor-specific information that radial pooling cannot represent alone. The following analysis and controls quantify this contribution.

1. What the contrast adds beyond radial state. For shell kk with uniform node weights, let μk\mu_k be the shell mean and let dv=mvd_v=m_v minus the mean of vv's shortest-path predecessors. The shell-average contrast is

aˉk=μk−νk−1→k,\bar{a}_k = \mu_k - \nu_{k-1\rightarrow k},

where νk−1→k\nu_{k-1\rightarrow k} is the mean of shell k−1k-1 under the predecessor-induced weights qk,u=∑v∈shell k,u∈P(v)1/(nk∣P(v)∣)q_{k,u} = \sum_{v \in \text{shell } k, u \in P(v)} 1/(n_k |P(v)|). Thus

aˉk=(μk−μk−1)+(μk−1−νk−1→k).\bar{a}_k = (\mu_k - \mu_{k-1}) + (\mu_{k-1} - \nu_{k-1\rightarrow k}).

The first term is the shell-to-shell summary available to radial pooling; the second depends on which shell-k−1k-1 nodes actually call shell kk, which radial pooling cannot represent.

2. A constructive example of added expressiveness. Let the root rr call aa and bb in shell 1, and let cc and dd form shell 2. In G1G_1 the edges are a→ca\to c and b→db\to d; in G2G_2 they are a→ca\to c and a→da\to d. The two graphs have identical node sets, hops, features, and shell counts, so radial-state moments and radial-only readouts are identical. Yet dd's contrast is md−mbm_d-m_b in G1G_1 and md−mam_d-m_a in G2G_2, so the contrast moments differ when ma≠mbm_a\ne m_b.

3. Cancellation along paths. Unweighted edge differences telescope to the endpoint difference. APRM weights each dvd_v by Bq(ur(v))B_q(u_r(v)). On a chain, summation by parts gives an intermediate-state coefficient Bq(uk)−Bq(uk+1)B_q(u_k)-B_q(u_{k+1}). Since the CDF coordinate is strictly increasing across nonempty shells (Appendix A.5) and B0(u)=(1−u)3B_0(u)=(1-u)^3 is strictly decreasing, the weighted operator avoids telescoping for at least one basis.

4. When predecessor relations change across compilations. APRM recomputes predecessor edges within each input FCG rather than assuming they are preserved across builds. Section 4.3 reports ancestor-direction preservation among shared source roles of 98.99% versus 29.95% for the random control. The contrast encodes direction within each graph, so changed edges alter its edge-specific term.

5. Empirical necessity.

Control (TREX, Table 3)Component removedΔ\Delta Macro R@1 vs APRM (pp)
Radial-State Only (matched budget)Whole contrast branch-1.53
Magnitude-Only ContrastSign of the contrast-1.56
All-Incoming EdgesShortest-path restriction-0.52

Removing the sign costs as much as removing the whole branch, indicating that the direction of change, not only its magnitude, carries signal.

6. A direct intervention. We rewired predecessor sources at inference on held-out TREX using frozen checkpoints (seeds 42--44). For each node in shell k≥2k\ge2, sources were redrawn from shell k−1k-1 while preserving node sets, node features, hops, shell sizes, per-node predecessor counts, and incoming edge-feature rows; radial-state moments were therefore unchanged. About 79% of 322,371 edges changed source.

Control was invariant under rewiring (embedding change at most 7×10−87\times10^{-8}), and the unrewired pass matched primary APRM embeddings within 8×10−88\times10^{-8}. Results are seed means on test.

ConditionMacro R@1 (%)Macro R@10 (%)Macro MRR@10 (%)
APRM, original edges17.7740.2024.20
APRM, predecessor sources rewired16.6338.3822.89
Radial-State Only (Table 3), original edges16.2337.7922.37

Rewiring lowers Macro Recall@1 by about 1.1 points; all six runs decrease and every query-level paired 95% interval excludes zero (closest [−1.48,−0.13][-1.48,-0.13]). Rewired APRM remains 0.40 points above Radial-State Only, removing about three quarters of the 1.53-point contrast advantage. This supports edge-specific predecessor structure beyond radial shell statistics.

Revision. The revised manuscript now gives the predecessor-induced decomposition and its structural interpretation in Appendix A.5, reports the predecessor-source intervention in Appendix C.2, and summarizes the role of this branch in Section 3.3.


We thank the reviewer again for these questions. We are happy to answer any further questions.

Reviewer_ijzZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes Augmented Predecessor-Radial Moments (APRM), a root-conditioned readout of a function's reachable directed call-graph neighborhood for binary code similarity detection. It combines normalized root-relative radial positions with signed contrasts to shortest-path predecessors. Across four fixed encoders, four compilation conditions, and 10,000-function retrieval galleries, APRM raises mean Macro Recall@1 from 6.48% to 14.75% and outperforms matched message-passing baselines. It also reports target-data-free transfer to an external benchmark.

Critical strengths
  1. APRM delivers large, consistent gains across all four tested encoders and compilation conditions under a challenging 10,000-function retrieval protocol. The matched comparison and project-clustered uncertainty make this the strongest evidence supporting the contribution.
  2. The paper connects a concrete empirical analysis of call-graph variation to a simple inference-time readout, and compares against component controls and matched message-passing baselines. This supports both the motivation and the claimed methodological value.
Critical weaknesses
  1. The structural invariance analysis is conditional on descendants that can be source-matched and observed in both builds; only about one third of examples meet the stated eligibility criterion. Thus the motivating invariance may not characterize all retrieval contexts.
  2. The evaluation is centered on BinKit and a particular family of fixed encoders and call-graph extraction settings. The external benchmark helps, but broader evidence across independently constructed datasets and toolchains would better establish generality.
Questions for authors

Can the authors quantify how APRM's gains vary with the fraction of rooted neighborhoods covered by the required graph nodes, and whether graph-extraction failures correlate with retrieval difficulty?

3 comments

Comment 1 (Weakness 1)

The structural invariance analysis is conditional on descendants that can be source-matched and observed in both builds; only about one third of examples meet the stated eligibility criterion. Thus the motivating invariance may not characterize all retrieval contexts.

Response. We thank the reviewer for this point. The one-third figure is an eligibility rate for the radial-order statistic, rather than a coverage rate for retrieval. The revised manuscript separates pairs with no retained context, context retained in only one build, and context retained in both builds, and reports radial-order agreement by shared-node coverage.

Subset of the 150,000 positive pairsPairsShare of all pairs (%)Share of pairs with context in both builds (%)
No retained descendant in either build62,35441.57—
Retained descendants in only one build5,2623.51—
Retained descendants in both builds82,38454.92100.00
of which: share at least one source-matched descendant74,97849.9991.01
of which: meet the eligibility criterion48,44532.3058.80

Of the 150,000 pairs, 48,445 (32.30%) meet the eligibility criterion, in line with the reviewer's estimate of about one third. The table uses the five-hop view, which has the same hop budget as APRM at inference. The full-reachable view reported in Section 4.3 gives 48,552 eligible pairs (32.37%).

  1. Empty contexts. In 41.57% of pairs, the target function has no retained descendant in either build. These are leaf functions or functions whose callees are all external. For them, APRM's context is empty by construction, the gates are masked, and APRM reduces exactly to the root path, so no structural assumption is used.
  2. Coverage does not change the conclusion within the eligible subset. Among eligible pairs, agreement stays well above the random control at every level of shared-node coverage C_shared.
C_sharedEligible pairsObserved agreementRandom control
[0.00, 0.10)883.33%40.78%
[0.10, 0.25)42793.25%39.89%
[0.25, 0.50)4,48693.73%37.39%
[0.50, 0.75)10,38391.04%37.44%
[0.75, 1.00]33,14196.81%40.07%

So, among pairs where APRM actually uses context in both builds, the eligible subset is 58.8% of those pairs, and agreement exceeds the random control at every coverage level. The retrieval results in Section 4 are computed on all queries, including empty-context and low-coverage queries.

Revision. The revised manuscript now reports the five-hop eligibility breakdown in Section 4.3 and the coverage-stratified agreement in Appendix B.2, Table 12. Retrieval results continue to use all queries.

Comment 2 (Weakness 2)

The evaluation is centered on BinKit and a particular family of fixed encoders and call-graph extraction settings. The external benchmark helps, but broader evidence across independently constructed datasets and toolchains would better establish generality.

Response. We thank the reviewer for this suggestion. The evidence beyond the main BinKit setting is the following.

  1. An independently constructed benchmark. Dataset-1 was built independently of BinKit by a different group (Marcelli et al., 2022) and is released with its own binaries, compiler matrix, official pairs, and analysis pipeline (IDA Pro 7.3, Capstone, and NetworkX). Its testing split contains 919 binaries built with GCC 4.8.5 to 9.2.1 and Clang/LLVM 3.5.2 to 9.0.0 for six architecture/bitness combinations (x86-32, x86-64, ARM32, ARM64, MIPS32, and MIPS64) at optimization levels −O0-O0, −O1-O1, −O2-O2, −O3-O3, and −Os-Os. We evaluate it on 522,003 testing functions using checkpoints selected only on source-side validation, without Dataset-1-specific retraining, checkpoint selection, or adaptation; the evaluation includes 4,000 official positive rows and 34,576,000 official negative rows. APRM raises the four-encoder mean Macro Recall@1 from 13.06% to 16.29%, and every encoder has a positive three-seed mean gain (Table 39).
  2. Encoder diversity. The four primary encoders come from different families. Gemini uses attributed control-flow graphs, TREX uses execution-trace pretraining, and DiEmph and CodeART are transformer encoders over assembly. We also apply APRM to NOVA, a 1.3B-parameter foundation model, where Macro Recall@1 on x86-64 XC and XO rises from 1.73% to 5.83% (Appendix D.1).
  3. A different extraction condition. On stripped binaries, APRM remains above the raw encoder for all four encoders under the same inference protocol; the corresponding results are reported in Comment 3.

Comment 3 (Question)

Can the authors quantify how APRM's gains vary with the fraction of rooted neighborhoods covered by the required graph nodes, and whether graph-extraction failures correlate with retrieval difficulty?

Response. We thank the reviewer for this question. On the held-out test, the gain of APRM is positive at every level of shared-node coverage, from +2.6 points when neither graph has context to +11.8 points at high coverage. Extraction failures are rare, and the queries they affect already scored lower than the others on the original binaries, averaged over the four encoders. We computed the coverage result with the raw frozen Base Encoder vectors, the same per-query outcomes used for Table 1, and the same four-encoder mean as the paper.

For the test set, we match descendants by function name, using the symbol tables of the test binaries: a descendant is shared when both graphs contain a function with the same project version, binary name, and function name. As defined in the appendix on shared-node coverage, C_shared is twice the number of shared descendants divided by the number of non-root nodes within five hops in the two graphs.

Held-out test, name-matched coverage. Across the same 4,000 queries, the Base-to-APRM gain by C_shared is as follows. The strata are those of the validation analysis.

C_shared stratumQueriesBase R@1 (%)APRM R@1 (%)Gain (pp)95% CI (pp)
Undefined (both graphs root-only)1467.379.96+2.59[+0.33, +5.18]
Low (below 0.25)1,3767.9917.07+9.07[+4.62, +13.26]
Medium (0.25 to 0.75)2,3175.2013.12+7.91[+5.39, +13.18]
High (0.75 or more)16111.0222.80+11.78[+8.03, +16.76]
All4,0006.4814.75+8.27[+5.41, +12.59]

The intervals are project-clustered over the five test projects. The gain is positive in every stratum and every interval is above zero. It is smallest when both graphs are root-only and largest at high coverage, which is the direction seen on validation.

Validation, source-matched coverage. Using raw Base vectors and the same 4,000 validation queries, the Base-to-APRM R@1 gains are +0.53 points for undefined coverage (95% CI [-0.25, +1.16]), +3.18 for low coverage [+2.56, +4.11], +4.27 for medium coverage [+3.61, +7.03], and +6.50 for high coverage [+4.00, +14.07]. The gain grows with source-matched coverage, from the smallest value when both graphs are root-only to the largest at high coverage.

Stripped-binary check. We stripped all 3,625 binaries in the test pool, re-ran the IDA Pro 9.3 extraction on the stripped files, rebuilt the graphs and encoder inputs, and evaluated the original frozen DiEmph, CodeART, TREX and Gemini checkpoints (seeds 42 to 44) without retraining. The four-task Macro Recall@1 is 11.62% for APRM versus 3.30% for DiEmph, 7.74% versus 3.98% for CodeART, 17.63% versus 7.59% for TREX, and 20.41% versus 8.49% for Gemini; APRM remains above the raw encoder for every encoder. TREX and Gemini change by less than 0.4 points in four-task Macro Recall@1.

Do extraction failures correlate with retrieval difficulty? Extraction failures affect only 3 to 11 of the 1,000 queries per task (32 of 4,000, 0.8%). On the original binaries, these queries have lower APRM Recall@1 than the remaining queries for all four encoders (4.17%, 6.25%, 10.42%, and 12.50% versus 10.71%, 9.96%, 17.85%, and 21.04% for DiEmph, CodeART, TREX, and Gemini); the four-encoder mean for the raw encoders is also lower (2.43% versus 6.48%). This outcome-level pattern indicates that extraction failures are concentrated among harder queries.

Revision. The revised manuscript now reports the held-out coverage results, the validation source-matched analysis, the stripped-binary check, and the descriptive extraction-failure analysis in Appendix B.3.


We thank the reviewer again for these constructive suggestions. We are happy to answer any further questions.

Reviewer_Lzf4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a novel method for binary code similarity detection, named argumented predecessors radial moments (APRM). The authors achieve this goal by comparing function pairs’ representations. Because the authors find that the related radial order and the direction of pairwise ancestor relations are preserved by observing the source-matched function node in the function call graph (FCG). The challenge is how the authors learn a stable context representation of the target function from different binary files that are compiled from the same source code under variable compilation configurations. The authors address the challenge by combining the radial descendant moments and signed ancestor contracts. For evaluation, the authors use four upstream encoders: Gemini, TREX, DiEmph, and CodeART. For the dataset, the authors build binary files from BinKit with four compilation configurations: XC (compiler change), XA (architecture/bitness), XO (optimization level), and XM (combined). Each task gallery contains 1,000 designated positives and 9,000 additional negatives.

Critical strengths
  1. Binary code similarity detection is an important and fundamental security topic. The idea of the novel method APRM comes from the authors’ observation, and the system design follows this observation.

  2. The research questions are reasonable. The authors test various pre-trained encoders across different compilation configurations to demonstrate the system's performance. The authors check if the radial-order pattern matches what they observed. The authors compared APRM with another method. The experimental results support the authors' claims.

  3. The authors show the improvement by using APRM with different encoders. This shows the design is generic and effective. The ablation study results show the contribution of components.

Critical weaknesses
  1. The authors describe the process of system implementation but do not clearly explain the reason for each step. For example, the authors use four non-negative cubic Bernstein basis functions, but they do not explain why they use four and not three or five. Does it come from the experiments?

  2. The APRM heavily relies on function pair identification. During the training phase, the authors can control the binary-file building process and use symbols to identify function pairs. However, if the dataset only contains stripped binary files or only a few parts of unstripped binary files, then the system can’t work. Thus, I am curious about the performance of APRM on a stripped binary dataset.

  3. The authors only compared with one previous work, BinEnhance-Pro. If there are some reasons why the authors skipped other baselines, the authors should clearly state those. Otherwise, we have no picture of which method has better performance.

  4. The performance of APRM is still low. The results in Table 1 can support this. The best performance under XA is only 15.7%, but BinEnhance-pro claims that the performance of their method can achieve 70.3%. There is a huge gap.

  5. Complex training strategy. From the paper, we know that the authors take a 2-stage approach, which is complex. I am curious why the authors can’t apply an end-to-end strategy.

Questions for authors
  • How does APRM perform on fully stripped binary datasets, and what was the rationale for limiting baseline comparisons solely to BinEnhance-Pro?

  • What empirical or theoretical justification underlies the choice of four nonnegative cubic Bernstein basis functions for the embeddings?

  • Can the current complex two-stage training strategy be streamlined into a unified end-to-end framework?

6 comments

We thank the reviewer for the detailed assessment and for noting that the design follows the observation and that the gains hold across encoders. We address the five weaknesses and the three questions below, grouping each question with the weakness it extends.

Summary.

  • Basis degree. In a degree ablation from n = 1 to 10, accuracy reaches the high-performing range by n = 3 and then remains on a plateau; degree 3 is the smallest degree on it.
  • Stripped binaries. With all 3,625 test binaries stripped, APRM stays above the raw encoder for all four encoders (for example, 17.63% against 7.59% Macro Recall@1 for TREX).
  • Baselines and the 70.3% figure. 70.3% is a MAP averaged over seven methods and pool sizes from 2 to 10,000. On the same common pool, APRM reaches 25.15% Recall@1 against 16.72% for BinEnhance-Pro and 17.31% for an adapted RevDecode.
  • Training. A single-stage end-to-end APRM reaches the same accuracy as the two-stage schedule (16.72% against 16.63%).

Comment 1 (Weakness 1 and Question 2)

The authors describe the process of system implementation but do not clearly explain the reason for each step. For example, the authors use four non-negative cubic Bernstein basis functions, but they do not explain why they use four and not three or five. Does it come from the experiments?

What empirical or theoretical justification underlies the choice of four nonnegative cubic Bernstein basis functions for the embeddings?

Response. The basis family and the degree are motivated by the design considerations below. We also report a degree ablation for n = 1 to 10 to show how the choice behaves across model capacities. The reasons for the basis family and the degree are as follows.

  1. Mass-preserving pooling. Bernstein polynomials of degree n are nonnegative and sum to one at every coordinate u. Each radial moment is therefore a weighted average of node states, and the total radial-basis weights M_{r,q} add up exactly to the context size N_r. No node is ignored or counted twice.
  2. Interpretable radial regions. The basis B_q peaks at u = q/n. With n = 3, the four bases emphasize the near context (u close to 0), two intermediate regions (u close to 1/3 and 2/3), and the far context (u close to 1).
  3. Smoothness. The derivative of each degree-n Bernstein basis is bounded by n in absolute value. A small change in a node's radial coordinate, for example after a compilation change, therefore changes its basis weights by at most n times as much. A lower degree gives a smoother readout, and a higher degree gives finer radial resolution but greater sensitivity to coordinate changes.
  4. The hop budget. With K = 5 there are at most five nonempty shells, so a graph has at most five distinct coordinate values. A degree above four can add basis flexibility, but it cannot create additional observed shell locations. We therefore selected degree 3 as a low-order choice that is expressive enough to distinguish the observed radial regions.
  5. Cost. Each additional basis adds one state transform, one contrast transform, and two gate networks, so the parameter count grows linearly with the number of bases.

We ran the degree ablation on TREX (seeds 42 to 44) for n = 1 to 10, retraining both stages under the same validation-only protocol. Entries are Macro metrics over the four TREX tasks (%).

DegreeR@1R@10MRR@10
n = 1 (2 bases)15.77 ± 0.6038.22 ± 0.1822.19 ± 0.49
n = 2 (3 bases)16.56 ± 0.6338.40 ± 0.5022.88 ± 0.52
n = 3 (4 bases)17.37 ± 0.3939.85 ± 1.6523.79 ± 0.73
n = 4 (5 bases)17.34 ± 0.1139.08 ± 0.2923.66 ± 0.14
n = 5 (6 bases)18.00 ± 0.2440.62 ± 0.7824.47 ± 0.50
n = 6 (7 bases)17.76 ± 0.1040.54 ± 0.5624.33 ± 0.27
n = 7 (8 bases)17.27 ± 0.5739.50 ± 0.6123.62 ± 0.46
n = 8 (9 bases)17.62 ± 0.5640.40 ± 0.4824.22 ± 0.34
n = 9 (10 bases)17.63 ± 0.6640.03 ± 0.6524.08 ± 0.78
n = 10 (11 bases)18.24 ± 0.2040.70 ± 0.2424.66 ± 0.31

Each seed is one training run; the R@1, R@10, and MRR@10 columns give means ± sample SD over the three seeds. All rows, including n = 3, come from the same set of retraining runs, so they can be compared directly; the primary table reports 17.77 ± 0.38 for n = 3.

R@1 is lowest at n = 1 (15.77%) and is 16.56% at n = 2. From n = 3 to n = 10 it stays between 17.27% and 18.24%, a plateau without a consistent trend: it is highest at n = 10 (18.24%) and n = 5 (18.00%) and lowest at n = 7 (17.27%). Neighboring degrees differ by about the size of the seed spread (SD 0.1 to 0.7 points). Degree 3 is the smallest degree on this plateau.

Cost grows linearly with the degree: each additional basis adds 281,091 parameters, 140,546 of them trainable in the second stage (1.62M parameters in total at n = 3 and 3.59M at n = 10). From n = 1 (15.77%) to n = 3 (17.37%), R@1 rises by 1.60 points, which is 83% of the 1.92-point rise to the average of the runs for n = 4 to 10 (17.69%). Degree 3 therefore obtains most of the gain with a small model, and its parameter count matches that of the budget-matched Gated-MPNN (1,624,107 against 1,622,578).

Revision location. Section 3.2 now states the non-negativity and partition-of-unity rationale, the low-order choice for K=5K=5, and the degree-ablation result. The n=1n=1 to 1010 ablation is reported as a line plot in Appendix C.2, Figure~\ref{fig:degree-ablation}.

Comment 2 (Weakness 2 and Question 1, first part)

The APRM heavily relies on function pair identification. During the training phase, the authors can control the binary-file building process and use symbols to identify function pairs. However, if the dataset only contains stripped binary files or only a few parts of unstripped binary files, then the system can't work. Thus, I am curious about the performance of APRM on a stripped binary dataset.

How does APRM perform on fully stripped binary datasets [...]?

Response. We thank the reviewer for this careful comment. Under the release-stripped inference protocol, APRM stays above the corresponding raw encoder for all four encoders, for example 17.63% against 7.59% Macro Recall@1 for TREX. We first clarify the role of symbols and then report this evaluation.

In our system, the symbol table is used only to label the dataset. Symbols define the positive pairs used for training and the ground-truth matches used for evaluation. If a dataset already provides such labels, APRM does not need a symbol table.

At inference, APRM reads only the base embeddings, the call edges, and function addresses (FVAs). It never reads function names or source correspondence (Section 3.1). Labeled training pairs can be generated by compiling open-source code under controlled settings, as done here, and the trained model can then be applied to binaries without symbols. Thus, label construction and symbol-free inference are separate steps, and the experiment below tests the latter.

Stripped-binary check on four encoders. We stripped all 3,625 binaries of the fixed test pool (llvm-strip --strip-all) and ran the same IDA Pro 9.3 extraction pipeline on the stripped files (3,625 of 3,625 succeeded). From these outputs we rebuilt the five-hop graphs and the encoder inputs, and evaluated the original frozen checkpoints of DiEmph, CodeART, TREX and Gemini (seeds 42 to 44) on the same tasks, with 1,000 queries and a 10,000-function query pool each. There was no retraining and no change to checkpoint selection or scoring. The table reports Macro Recall@1 (%) on the fixed pool, averaged over seeds 42 to 44.

EncoderBase, with symbols (Table 1)APRM, with symbols (Table 1)Base, strippedAPRM, stripped
DiEmph2.5310.553.3011.62
CodeART7.279.933.987.74
TREX7.6317.777.5917.63
Gemini8.4720.758.4920.41

Although the checkpoints were trained on unstripped inputs, APRM stays above the raw encoder on all four encoders after stripping. The gain over the raw encoder is +8.3, +3.8, +10.0, and +11.9 points after stripping, against +8.0, +2.7, +10.1, and +12.3 points with symbols (DiEmph, CodeART, TREX, Gemini). Thus, under this stripped-inference protocol, APRM remains effective without reading function symbols at inference.

Revision. The revised manuscript clarifies in Section 3.1 that symbols are used only to create training pairs and evaluation labels, and reports the stripped-binary checks in Appendix B.3 and Appendix D.

Reviewer_gd16OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes APRM, a graph readout that enhances binary-function embeddings using call-graph context. It combines normalized radial positions with signed differences between nodes and their shortest-path predecessors. Across four encoders and compilation conditions, APRM improves mean Macro Recall@1 from 6.48% to 14.75%. Ablations, message-passing comparisons, and external-dataset transfer further evaluate the method.

Critical strengths
  • APRM provides a well-motivated way to incorporate directional call-graph context into fixed-vector retrieval.
  • Improvements are consistent across multiple encoders and compilation settings, with additional evidence from external-dataset transfer.
Critical weaknesses
  • A trained root-only adapter is missing, making it difficult to separate the benefits of graph context from additional supervised training. The total training budget also appears unclear relative to the message-passing baselines.
  • Evidence for the specific CDF coordinate is limited: its advantage over uniform hop coordinates is small, and the comparison uses a frozen radial-state model rather than fully retraining both variants.
Questions for authors
  • What concrete practical scenario motivates this task, and why are existing tools insufficient? How would the reported retrieval improvements translate into useful outcomes in that scenario?
  • Are the total training budgets comparable between APRM and the message-passing baselines, and how would a trained root-only adapter perform?
5 comments

We thank the reviewer for the careful reading and for recognizing the motivation for directional call-graph context and the consistency of the gains across encoders and compilation conditions. We ran the requested controls after submission. All new results below use the same training triplets, validation-only checkpoint selection, fixed test set (1,000 queries and a 10,000-function query pool per task), and float64 rescoring as the primary benchmark. Each new control is reported as a separate block.

Summary.

  • Graph context, not extra training. A trained root-only adapter with APRM's two-stage budget reaches 8.00% Macro Recall@1 on TREX. In the four-encoder, three-seed mean, a Gated-MPNN with the same maximum update budget and parameter count reaches 12.55%, compared with 12.75% for the submitted 14-epoch setting and 14.75% for APRM.
  • Coordinate. In a fully retrained comparison, a non-degenerate radial coordinate adds 2.45 points of Macro Recall@1 over a collapsed coordinate.
  • Scenario. For finding a known function in binaries of unknown build configuration, APRM raises the four-encoder mean Recall@10 in 10,000-function query pools from 15.92% to 33.88%.

Comment 1 (Weakness 1 and Question 2)

A trained root-only adapter is missing, making it difficult to separate the benefits of graph context from additional supervised training. The total training budget also appears unclear relative to the message-passing baselines.

Are the total training budgets comparable between APRM and the message-passing baselines, and how would a trained root-only adapter perform?

Response. We ran both controls.

(a) Trained root-only adapter. We trained a root-only adapter on TREX (seeds 42 to 44). It keeps a trainable projection of the root embedding but reads no graph context, no FVA features, and no radial or contrast terms. To give it the same budget as APRM, it is trained in two 14-epoch stages (117,110 optimizer updates per stage, with a fresh optimizer in each stage), and it does not load any radial-state checkpoint. We also trained a simple context control that adds an unweighted mean of the transformed five-hop descendants to the root state, again without FVA, coordinates, Bernstein bases, gates, or contrasts. The table reports TREX Recall@1 (%) for each task; Macro R@1 is given as mean ± SD over seeds 42 to 44.

MethodXCXAXOXMMacro R@1
Base encoder7.527.5412.263.217.63
Trained root-only adapter (2 × 14 epochs)8.057.9212.933.128.00 ± 0.49
Root + unweighted mean of five-hop context10.337.5716.874.009.69 ± 0.07
APRM (primary table)23.1010.7728.139.0717.77 ± 0.38

Supervised training of the root path alone adds 0.37 percentage points over the fixed base encoder. Unweighted context adds a further 1.69 points. These controls remain below the full APRM result. Of APRM's 10.14-point gain over the base encoder, supervised training of the root path explains 0.37 points; the remaining gain is associated with APRM's graph-context branch and structured readout. The gain therefore cannot be explained by additional supervised training of the root representation alone.

Comment 1 (Weakness 1 and Question 2)

(b) Training budget. The original message-passing comparison is parameter- and protocol-matched, not total-budget-matched: each baseline uses one 14-epoch stage, whereas APRM Frozen uses 14+14 epochs. We retain it as Table 24 and add a 28-epoch Gated-MPNN control in Table 25 with APRM's maximum scheduled update budget and matched whole-model parameter count.

We trained Gated-MPNN from scratch for 28 epochs for each encoder. After each epoch, validation selects one checkpoint, which is evaluated once on the fixed test set. The scheduled updates match APRM: 15,736, 234,220, 132,692, and 210,812 for Gemini, TREX, DiEmph, and CodeART. Following Table 24, we report the four-encoder, three-seed mean below (in %).

MethodXCXAXOXMMacro R@1Δ vs APRM (pp)Macro R@10
Gated-MPNN, 14 epochs (submitted setting, Table 24)12.2214.2218.026.5412.75-2.0029.73
Gated-MPNN, 28 epochs (budget-matched)12.1113.9117.776.4212.55-2.2029.46
APRM (primary table)14.2615.7021.227.8314.75—33.88

The budget-matched control reaches 12.55% Macro Recall@1, versus 12.75% for the submitted 14-epoch setting and 14.75% for APRM; doubling the baseline's scheduled update budget does not close the gap.

Budget and parameters for all four encoders. The tables give scheduled updates and whole-model parameter counts; the second also lists APRM's stage-2 active branch.

SettingGeminiTREXDiEmphCodeART
Batch size128161616
Updates per epoch5628,3654,7397,529
Message-passing baselines: one 14-epoch stage (updates)7,868117,11066,346105,406
APRM: 14-epoch radial-state stage + 14-epoch contrast stage (updates)15,736234,220132,692210,812
ModelHidden width (Gemini)Hidden width (TREX, DiEmph, CodeART)Parameters (Gemini)Parameters (TREX, DiEmph, CodeART)Δ vs APRM (Gemini)Δ vs APRM (TREX, DiEmph, CodeART)
APRM, whole model2562561,431,2111,624,107——
of which: stage-1 radial-state model (fixed in stage 2)——869,0271,061,923——
of which: contrast branch (the only part trained in stage 2)——562,184562,184——
GCN4774511,431,7981,625,448+0.04%+0.08%
GAT4764481,431,1821,612,4980.00%-0.71%
Gated-MPNN1931961,429,1691,622,578-0.14%-0.09%
RGCN2892871,432,1001,628,318+0.06%+0.26%

The baselines are within 0.71% of APRM's whole-model count and update all parameters from scratch. In APRM stage 2, only the 562,184-parameter contrast branch is trainable; the stage-1 radial-state model, feature-encoder adapter, and output projection are fixed.

Shared settings. All models use AdamW (learning rate 4e-4, weight decay 3e-3), gradient clipping at 1.0, cosine restarts (T_0 = 3,200, T_mult = 2, minimum learning rate 5e-7), dropout 0.3, FP32, the same objectives, five hops, a 512-dimensional output, and frozen upstream vectors. Baseline hidden widths are set by parameter matching. APRM reinitializes the stage-2 optimizer. Validation selects one checkpoint per baseline (14 or 28 epochs) and one per APRM stage; selected checkpoints are evaluated once on fixed test data. All runs use seeds 42--44.

Revision. Sections 4.4 and Appendix C.3 now distinguish parameter/protocol matching from the maximum-update-budget control and report update counts, parameter counts, stage-2 active parameters, and hidden widths.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.