- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the optimal adaptive query complexity of functional backdoor recovery: finding any admissible trigger whose attack success rate meets a prescribed threshold. Its main contribution is a constructive separation between two finite model families with identical victim–candidate attack-success tables and identical per-query label marginals under a uniform prior over models. Despite these matched statistics, their optimal worst-case query budgets under label feedback grow logarithmically and linearly, respectively, with the number of possible models. Under binary target/non-target feedback, the two families become indistinguishable. Extensions establish that the separation persists with bounded error and overlapping successful-trigger sets, where exact model identification is unnecessary. The authors implement the constructed response structures in CIFAR-10 ResNet-18 models, exhaustively verifying the prescribed fixed-source response tables and thresholded success sets while maintaining clean accuracy. Supplementary experiments compare binary and label feedback for a specified search heuristic on conventional backdoor models, finding no consistent benefit from retaining non-target labels. Overall, the paper demonstrates that attack-success statistics and individual-query response marginals do not determine adaptive recovery difficulty; relationships among responses across queries also matter.
Critical strengths
1.A precise separation under strong matching conditions. The paper constructs families with identical victim–candidate attack-success tables and identical per-query label marginals, yet proves logarithmic versus linear optimal adaptive query complexity. Matching both statistics makes the result consequential: even detailed measurements of trigger effectiveness and individual-query responses can miss essential aspects of recoverability. The bounded-error and overlapping-success-set extensions further establish that the separation persists beyond zero-error recovery and exact model identification. This provides a rigorous foundation for considering the relationships among query responses when assessing recovery difficulty. 2.Controlled neural-network validation of the theoretical construction. The CIFAR-10 ResNet-18 experiments exhaustively verify the prescribed fixed-source response tables and check the corresponding thresholded success sets while retaining strong clean accuracy. Together with the transfer proposition, these checks support the claimed optimal budgets for the restricted experimental problems. This strengthens the contribution by demonstrating that the constructed response structures can coexist with normal classification performance in trained neural networks.
Critical weaknesses
1.Limited coverage of broader recovery interfaces. The exact separation concerns a prescribed finite query space, and the neural realization certifies it under a fixed-source interface. The paper does not establish whether the separation persists when source images or candidate transformations can be selected more freely. This limits the result’s implications for broader black-box recovery settings, while leaving the stated existence theorem intact. 2.Limited empirical characterization of the relevant response structure. The neural experiments establish that the designed response tables are realizable. However, Appendix D evaluates a particular search policy without directly measuring how cross-query dependencies contribute to recovery difficulty in conventional backdoors. Consequently, the paper provides limited evidence about when the identified information structure matters outside the constructed examples, constraining its broader explanatory significance.
Questions for authors
1.Clarification of the neural realization’s scope. Were the prescribed non-target response patterns checked on source images beyond the single audited image? If such results are already available, how consistently do the FAST/SLOW response structures persist across images? This would help assess whether source-image selection could substantially change the observed separation. 2.Clarification of the supplementary evidence. Do any existing analyses or search logs from Appendix D indicate whether non-target labels provide additional information about successful candidates after conditioning on the previous query history and target/non-target outcomes? Can the available evidence distinguish between uninformative additional feedback and a search policy that fails to exploit useful information? Such evidence would help assess whether the mechanism identified by the theoretical construction also matters in the conventional-backdoor experiments.