- 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
-
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.
-
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
-
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.
-
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.
-
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
-
Radial encoding robustness: How does the proposed CDF-based radial encoding remain robust to compilation-induced changes in hop distances and shell sizes?
-
Does APRM maintain its performance improvements on compilation pairs with low shared-node coverage, particularly under the XM setting?
-
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
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_shared | Eligible pairs | Observed agreement | Random control |
|---|---|---|---|
| [0.10, 0.25) | 427 | 93.25% | 39.89% |
| [0.25, 0.50) | 4,486 | 93.73% | 37.39% |
| [0.50, 0.75) | 10,383 | 91.04% | 37.44% |
| [0.75, 1.00] | 33,141 | 96.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 stratum | Base R@1 (%) | APRM R@1 (%) | Gain (pp) | 95% CI (pp) |
|---|---|---|---|---|
| Undefined (both graphs root-only) | 11.19 | 11.32 | +0.12 | [-1.14, +0.83] |
| Low (below 0.25) | 1.10 | 2.88 | +1.78 | [+0.82, +2.79] |
| Medium (0.25 to 0.75) | 1.93 | 4.75 | +2.81 | [+1.59, +4.03] |
| High (0.75 or more) | 4.58 | 10.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 with uniform node weights, let be the shell mean and let minus the mean of 's shortest-path predecessors. The shell-average contrast is
where is the mean of shell under the predecessor-induced weights . Thus
The first term is the shell-to-shell summary available to radial pooling; the second depends on which shell- nodes actually call shell , which radial pooling cannot represent.
2. A constructive example of added expressiveness. Let the root call and in shell 1, and let and form shell 2. In the edges are and ; in they are and . The two graphs have identical node sets, hops, features, and shell counts, so radial-state moments and radial-only readouts are identical. Yet 's contrast is in and in , so the contrast moments differ when .
3. Cancellation along paths. Unweighted edge differences telescope to the endpoint difference. APRM weights each by . On a chain, summation by parts gives an intermediate-state coefficient . Since the CDF coordinate is strictly increasing across nonempty shells (Appendix A.5) and 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 | Macro R@1 vs APRM (pp) |
|---|---|---|
| Radial-State Only (matched budget) | Whole contrast branch | -1.53 |
| Magnitude-Only Contrast | Sign of the contrast | -1.56 |
| All-Incoming Edges | Shortest-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 , sources were redrawn from shell 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 ), and the unrewired pass matched primary APRM embeddings within . Results are seed means on test.
| Condition | Macro R@1 (%) | Macro R@10 (%) | Macro MRR@10 (%) |
|---|---|---|---|
| APRM, original edges | 17.77 | 40.20 | 24.20 |
| APRM, predecessor sources rewired | 16.63 | 38.38 | 22.89 |
| Radial-State Only (Table 3), original edges | 16.23 | 37.79 | 22.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 ). 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.
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)
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.
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.
By compilation task, the same per-pair statistic on the eligible pairs is:
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.