What Response Marginals Miss: Adaptive Query Complexity of Functional Backdoor Recovery

W HAT R ESPONSE M ARGINALS M ISS : A DAPTIVE Q UERY C OMPLEXITY OF F UNCTIONAL BACKDOOR R ECOVERY

arXiv:2610.07771v1 [cs.CR] 6 Oct 2026

Yunjae Hwang School of Cybersecurity Korea University Seoul, Republic of Korea hyj019@korea.ac.kr

Byoungjin Seok Department of Convergence Security Hansung University Seoul, Republic of Korea bjseok@hansung.ac.kr

A BSTRACT Functional backdoor recovery finds any trigger whose attack success rate is at least a given threshold rather than to recover the planted trigger. We study the minimum number of queries required for this task under label feedback which returns the predicted class label. We construct two finite families of victim models that have exactly the same attack success rate for every victim and trigger candidate. The distribution of returned labels for every query is also identical under a uniformly chosen victim. These families form an explicit counterexample that despite the matched quantities, their optimal adaptive query complexities are Θ(log H) and Θ(H) where H is the number of possible victims. The difference arises because the same non-target labels are associated with different sets of victims, so successive queries eliminate possible victims at different rates. This separation disappears when the response is reduced to binary feedback, which reports only whether the target label is returned. The separation also persists for every fixed failure probability below one. Finally, we realize the same recovery problems with trained CIFAR-10 ResNet-18 classifiers and verify the predicted optimal query budgets. These results show that attack success rate and the distribution of returned labels for each query are insufficient to determine the query complexity of functional backdoor recovery.

1

I NTRODUCTION

Trigger inversion is a common approach to backdoor inspection in which a defender searches for transformations that activate the target behavior of a suspicious classifier (Wang et al., 2019; Liu et al., 2019; Tao et al., 2022; Wang et al., 2022; 2023). Black-box inspection has also been studied under limited access to model outputs (Chen et al., 2019; Dong et al., 2021; Guo et al., 2022; Le Roux et al., 2024; Popovic et al., 2025). For trigger inversion, recovering the exact planted trigger is not necessary: approximate or alternative transformations can activate the same malicious behavior (Qiu et al., 2024; Abad et al., 2026). This motivates functional backdoor recovery, where success requires any admissible transformation whose attack success rate (ASR) is at least a prescribed threshold. The difficulty of functional recovery depends not only on the backdoor itself but also on the information available to the defender. Black-box inspection methods study this problem under limited access to model outputs (Chen et al., 2019; Dong et al., 2021; Guo et al., 2022; Le Roux et al., 2024; Popovic et al., 2025), while recent attacks have been designed to resist trigger inversion or related inspection methods (Zhu et al., 2024; Qiu et al., 2024; Cheng et al., 2024). These studies analyze particular inspection methods or attacks designed to resist inversion rather than characterize the optimal adaptive query budget under a fixed query model. Decision-based black-box attacks show that class labels alone can guide adaptive search (Brendel et al., 2018; Chen et al., 2020), while adaptive testing and decision-region methods study how query outcomes reduce the remaining possibilities (Cicalese et al., 2014; Javdani et al., 2014; Kane et al., 2017; Chen et al., 2017b). These works do not address the controlled comparison considered here. We ask whether functional recovery prob1

lems with the same complete candidate success relation and the same response marginal for every query can nevertheless have different optimal adaptive query budgets. To isolate this question, we compare victim families that agree on ASR for every victim and candidate and have the same response marginal for every query under a uniformly drawn hidden victim. For deterministic responses, this also matches each query’s response entropy and its initial mutual information with the hidden victim. The marginals do not determine which victims produce each response and therefore do not determine how the remaining victims are partitioned after successive observations. We show that this missing information matters by constructing an explicit counterexample in which the matched quantities are identical but the optimal adaptive query budgets are different. The counterexample consists of two families called FAST and SLOW. FAST queries reveal complementary information about the hidden victim, whereas SLOW contains a hard subfamily for which a consistent response path removes at most one remaining victim per query. Consequently, the optimal recovery budgets grow logarithmically and linearly with the family size despite the matched success relation and response marginals. The separation persists for every fixed failure probability below one but disappears when each response is reduced to binary feedback. We also show that the exact finite recovery budgets predicted by the construction hold for trained CIFAR-10 ResNet-18 classifiers at the tested problem sizes. Our contributions. We establish exact query complexity results for functional backdoor recovery under label feedback: • We give an explicit counterexample showing that the optimal query budget for functional backdoor recovery is not determined by the ASR of the trigger candidates or by theresponse marginal of each query. We construct two finite victim families that match both quantities exactly and show that their optimal zero-error recovery budgets become different as Θ(log H) and Θ(H). • We strengthen the separation in two directions: For every fixed failure probability δ < 1, two families retain Θ(log H) and Θ(H) query complexity, respectively. After label feedback is reduced to binary feedback, both families have the same exact optimal budget, showing that the separation is due to the information carried by non-target class labels rather than differences in which candidates succeed. • We realize the finite recovery problems with trained convolutional classifiers and verify the conditions that transfer the theoretical query bounds to the learned models. The resulting families attain the exact predicted query budgets at H = 12, 24, 48 under the fixed-source query model. Together, these results show that the complete ASR function and the response marginal of each query under a uniform hidden victim prior are insufficient to determine the optimal adaptive query budget. Which victim models produce each non-target label can change the number of queries required for recovery.

2

R ELATED W ORK

Trigger inversion and functional recovery. Backdoors associate a planted trigger with a target prediction while preserving normal behavior on clean inputs (Gu et al., 2017; Chen et al., 2017a). Inversion methods reconstruct effective patterns through optimization, neuron stimulation, and constraints in input or feature space (Wang et al., 2019; Liu et al., 2019; Tao et al., 2022; Wang et al., 2022; 2023; Sun & Kolter, 2023; Xu et al., 2024). Black-box methods include DeepInspect, B3D, AEVA, REStore, and DeBackdoor, but they differ substantially in the model outputs available to the defender (Chen et al., 2019; Dong et al., 2021; Guo et al., 2022; Le Roux et al., 2024; Popovic et al., 2025). B3D assumes class-probability outputs, AEVA uses only the final predicted label, REStore includes a setting with label feedback, and DeBackdoor optimizes a probability-based surrogate of attack success. These works design particular detection or reconstruction procedures under restricted model access and analyze particular recovery or detection procedures. We instead study the minimum worst case number of queries under label feedback required by any adaptive procedure to return a candidate whose ASR is at least a prescribed threshold. 2

Inversion resistance and fundamental limits. Recent work has shown that the effectiveness of the planted trigger and the difficulty of recovering a working trigger need not move together. GRASP reduces the effective radius of the planted trigger and makes gradient-based inversion more difficult without substantially weakening the backdoor itself, while BELT suppresses fuzzy variants of the trigger so that the planted trigger remains effective but nearby alternatives are less likely to activate the target behavior (Zhu et al., 2024; Qiu et al., 2024). These results motivate asking how difficult it is to recover any trigger that still activates the backdoor rather than judging difficulty from the planted trigger alone. At the same time, alternative-trigger analysis shows that patterns different from the planted trigger can activate the same backdoor (Abad et al., 2026). This supports treating recovery of the malicious behavior separately from exact recovery of the planted trigger. Cryptographic constructions go further by showing that backdoors can be made computationally undetectable or non-replicable for efficient adversaries (Goldwasser et al., 2022; Kalavasis et al., 2024). Our question is different: we place no restriction on computation and ask how many model predictions are required to recover a trigger that meets a given success threshold. Query complexity and decision regions. Gluch and Urbanke treat the number of black-box queries as the main resource and ask what a computationally unbounded attacker can achieve with limited model access (Gluch & Urbanke, 2021). Work on adaptive testing further shows that the hidden hypothesis need not be identified once one decision is valid for all hypotheses still consistent with the observations (Golovin et al., 2010; Javdani et al., 2014). This directly matches functional recovery where it is enough to find one candidate that succeeds for every victim still consistent with the returned labels. Prior work also shows that greedily reducing uncertainty can be far from optimal when dependencies among tests matter (Chen et al., 2017b). Blackwell’s comparison of experiments instead considers the distribution of observations for each possible hidden state (Blackwell, 1953), which is stronger than matching the distribution obtained after averaging over one prior. We show that even when every candidate has the same ASR for every victim and every query returns labels with the same distribution under a uniform victim, the optimal adaptive query budget can still differ.

3

F UNCTIONAL BACKDOOR R ECOVERY

3.1

F UNCTIONAL R ECOVERY AND Q UERY B UDGET

Consider a classifier f : X → Y and a known target label t ∈ Y. Each candidate z ∈ Z specifies a transformation Tz : X → X . We assume that Z and the transformations {Tz : z ∈ Z} are public. Source inputs are drawn from a distribution D¬t over inputs whose ground-truth labels are not t. Definition 1 (Functional recovery). For τ ∈ (0, 1], define gf (z) =

Fτ (f ) = {z ∈ Z : gf (z) ≥ τ }.

Pr [f (Tz (X)) = t] ,

X∼D¬t

(1)

A recovery procedure succeeds if its output belongs to Fτ (f ). Thus recovery does not require the planted trigger; any z ∈ Fτ (f ) is a functional trigger candidate and a valid output. To measure the query complexity of functional recovery, we consider black-box queries under label feedback. A query model I specifies how the source input in each query is obtained. Depending on I, the source may be fixed, sampled from D¬t , or chosen by the algorithm. Given a source input x and a trigger candidate z, a query returns the predicted class label f (Tz (x)) under label feedback. Under binary feedback, it returns 1{f (Tz (x)) = t}. Each model evaluation counts as one query, while computation between queries is unrestricted; the returned trigger candidate need not have been queried. Let H be an index set and {fh }h∈H a known family of possible victim models. The algorithm knows this family but not the actual index h. For each h ∈ H, let F (h) = Fτ (fh ) denote the set of trigger candidates that satisfy the functional recovery criterion for fh . We measure how many queries are sufficient to return such a trigger candidate for every possible victim model. For an algorithm A operating under I, let TA denote the number of queries made before it returns ZA . If the algorithm does not return, we set TA = ∞ and ZA = ⊥ ∈ / Z. 3

Definition 2 (Recovery budget). For δ ∈ [0, 1), define  QA (F, δ) = inf q ∈ N0 : Pr(TA ≤ q, ZA ∈ F (h)) ≥ 1 − δ h

 ∀h ∈ H ,

(2)

where for each fixed h, the probability is over the randomness of A and any random source sampling specified by I. The optimal recovery budget is Q⋆I (F, δ) = inf QA (F, δ),

(3)

A

where the infimum is over all algorithms allowed by I. Thus, QA (F, δ) is the smallest query budget under which A returns a trigger candidate satisfying the functional recovery criterion with probability at least 1 − δ for every possible victim model. The quantity Q⋆I (F, δ) is the minimum such budget over all algorithms permitted by the query model. 3.2

I NDEPENDENT S AMPLING BASELINE

The optimal recovery budget in Section 3.1 allows the algorithm to choose queries adaptively based on previously returned labels. As a simple baseline, consider a procedure that samples trigger candidates independently from a fixed distribution QZ over Z and evaluates each sampled candidate on fresh source inputs. Proposition 1 (IID recovery baseline). Fix a victim model f and a distribution QZ over Z.Let ρ = PrZ∼QZ [gf (Z) ≥ τ ] > 0, and suppose that for some η > 0, PrZ∼QZ (|gf (Z) − τ | ≥ η) = iid

iid

1. Let ZP 1 , . . . , ZL ∼ QZ , and independently, for each i ∈ [L], let Xi,1 , . . . , Xi,r ∼ D¬t . Define r gbi = 1r j=1 1{f (TZi (Xi,j )) = t} . If the procedure returns any Zi with gbi ≥ τ , then 2

Pr[failure] ≤ (1 − ρ)L + 2Le−2rη .

(4)

Hence, for any δ ∈ (0, 1),   2 , L = ρ−1 log δ

 r=

4L 1 log 2η 2 δ

 (5)

suffice to return a trigger candidate in Fτ (f ) with probability at least 1 − δ, using Lr model queries. Appendix A.1 proves the bound. The first term in (4) is the probability that none of the L sampled trigger candidates satisfies the recovery criterion. The second bounds errors in deciding whether the sampled candidates lie above or below the threshold τ from r source evaluations. Consequently, ρ determines how many trigger candidates must be sampled, and η determines how many source inputs are needed to evaluate each one reliably. Even though Proposition 1 gives a sufficient query budget for this independent sampling procedure, it does not characterize the optimal adaptive budget Q⋆I (F, δ). In particular, two recovery problems can agree on which trigger candidates satisfy the recovery criterion while differing in how much information their returned labels provide to an adaptive algorithm. The next section gives an explicit counterexample in which both ASR and the response marginal of each query are matched, yet the optimal adaptive query budgets differ.

4

E XACT S EPARATION UNDER M ATCHED M ARGINALS

4.1

C ONSTRUCTION AND E XACT Q UERY B UDGETS

We construct two finite recovery problems, FAST and SLOW, as an explicit counterexample showing that ASR and the marginal distribution of each query response under a uniformly chosen victim do not determine the optimal query complexity. The two problems match these quantities exactly but differ in which victims produce the non-target labels. 4

Set N = 2n , m = N/2, H = N + m = 3 · 2n−1 for n ≥ 2. There are N core victims c0 , . . . , cN −1 and m auxiliary victims d0 , . . . , dm−1 with H = {c0 , . . . , cN −1 , d0 , . . . , dm−1 }. We use a singleton source distribution, so the source input is fixed and omitted from the notation. Queries and output trigger candidates use the same set, Q = Z = {p0 , . . . , pm−1 , v0 , . . . , vN −1 }. The candidates vz are paired with the core victims cz , while pi are paired with the auxiliary victims di . FAST and SLOW differ only in how the non-target responses of the pi queries divide the core victims. We use labels {0, 1, 2, 3, 4}, with target label 0. Let OhF (q) and OhS (q) denote the returned labels. For z ∈ {0, . . . , N − 1}, let bk (z) be its k-th bit, and for pi let k = i mod n. On the core victims, FAST returns OcFz (pi ) = 1 + bk (z), (6) so each pi divides the core victims according to one bit of z. Here 1 + bk (z) ∈ {1, 2}, so these responses are always non-target. For SLOW, writing the core victims as c0 , . . . , cm−1 and cm , . . . , c2m−1 ,   1, j = i, 2, j = i, OcSj (pi ) = OcSm+j (pi ) = (7) 2, j ̸= i, 1, j ̸= i. Hence pi isolates one victim in the first half. The second half is arranged to preserve the same label counts as FAST; across all N core victims, labels 1 and 2 each occur m times. All other responses are identical:   0, j = i, 0, h = cz , OdFj (pi ) = OdSj (pi ) = OhF (vz ) = OhS (vz ) = (8) 3 + bk (j), j ̸= i, 1, h ̸= cz . pi is successful only for di , while vz is successful only for cz . Writing ϕ(cz ) = vz and ϕ(di ) = pi , both families satisfy F (h) = {ϕ(h)} with ϕ a bijection. Since the remaining responses are identical in FAST and SLOW, the matched core label counts imply the same marginal distribution for every query. Now, let Q⋆F (δ) and Q⋆S (δ) denote the optimal recovery budgets for FAST and SLOW under label feedback. Let Q⋆B (δ) denote the corresponding budget when each returned label y is replaced by the target indicator 1{y = 0}. Theorem 1 (Query complexity separation). For every victim h and trigger candidate q, ghF (q) = ghS (q) = 1{q = ϕ(h)}. If U ∼ Unif(H), then for every q ∈ Q and y ∈ {0, 1, 2, 3, 4}, F S Pr[OU (q) = y] = Pr[OU (q) = y].

(9)

Their optimal zero-error budgets under label feedback are Q⋆F (0) = n

(n ≥ 2),

Q⋆S (0) = 2n−1 − 1

(n ≥ 3).

(10)

For n = 2, Q⋆S (0) = 2. Under binary feedback, both families satisfy Q⋆B (0) = H − 1. Since H = 3 · 2n−1 , for n ≥ 3, Q⋆F (0) = log2 (2H/3) and Q⋆S (0) = H/3 − 1. The two budgets under label feedback coincide at n = 2, 3, and a strict separation begins at n = 4. The complete proof is deferred to Appendix A.3. 4.2

L IMITS OF ASR AND R ESPONSE M ARGINALS

The matched response marginals specify how many victims return each label but not which victims return them. Figure 1 shows this distinction at H = 24. In general, zero-error functional recovery need not identify the victim if all remaining victims share a functional trigger candidate. In the FAST and SLOW construction, however, each victim has a different unique functional trigger candidate, so recovery requires identifying the victim. Appendix A.2 gives the general zero-error stopping condition. 5

Hidden victim

FAST: optimal budget = 4

SLOW: optimal budget = 7

c0

c0

c4

c4

c8

c8

c12

c12

d0

d0

d4

d4 p0

p4

v0

v4

v8

v12

p0

Query / output candidate 0 (target)

p4

v0

v4

v8

v12

Query / output candidate 1

2

3

4

Figure 1: The H = 24 response tables. Rows are hidden victims and columns are queries, which are also output candidates. Each row and column has one target entry. Every column has the same label counts in both tables, but the association between responses and victims differs. The optimal zero-error recovery budgets are 4 and 7, respectively. In FAST, the pi queries give complementary binary partitions of the N = 2n core victims. Every query has at most two responses on this set, so q queries can distinguish at most 2q cases. Since different core victims require different functional trigger candidates, 2q ≥ N which implies q ≥ n. The queries p0 , . . . , pn−1 attain this bound by revealing the n bits of the core index. In SLOW, every query is either constant or isolates at most one victim from {c0 , . . . , cm−1 }. A worst case response therefore eliminates at most one remaining victim per query, which requires at least m − 1 queries. Under binary feedback, the identities of the non-target labels are discarded. A query exactly returns 1 when the queried trigger candidate is the unique functional trigger candidate for the actual victim. Every query therefore becomes an equality test and both families require exactly H − 1 queries in the worst case. More generally, label feedback cannot have a larger optimal recovery budget than binary feedback because an algorithm may discard the class identity of each response. Appendix B gives the general simulation statement. Because the responses are deterministic given the victim, matching the response marginal of every fixed query also matches its response entropy and its initial mutual information with the hidden victim. Nevertheless, Theorem 1 gives logarithmic and linear optimal zero-error recovery budgets. Figure 2 shows how the corresponding zero-error budgets scale with the number of possible victims. We also give the formal comparison under the uniform distribution over victims in Appendix A.3.1. Corollary 1. The FAST and SLOW constructions have the same ASR for every victim–trigger candidate pair and the same response marginal for every query, while Q⋆S (0) H/3 − 1 = −→ ∞. Q⋆F (0) log2 (2H/3) Consequently, these quantities do not determine the optimal zero-error recovery budget and cannot approximate it within any fixed multiplicative factor. The proof can be found in Appendix A.4. Note that in the construction above, each victim has a different unique functional trigger candidate, so recovery requires identifying the victim. This identification property is not necessary for the separation.

6

Optimal zero-error budget

767

FAST

SLOW

Binary

255

47 15 5 3 12

24

48

96

192

384

768

Number of possible victims H

Figure 2: Exact theoretical zero-error recovery budgets as the number of possible victims increases. Filled markers indicate the three family sizes realized with trained models in Section 5; values at larger sizes are theoretical only. Under label feedback, the FAST and SLOW budgets coincide at H = 12 and separate from H = 24 onward. Under binary feedback, the exact budget is H − 1.

Proposition 2 (Separation without identification). For n ≥ 3, the common responses in Equation (8) can be modified so that, for every 0 < τ ≤ 1, FAST and SLOW have the same functional success sets Fe(cz ) = {vz , v(z−1) mod N },

Fe(dj ) = {pj , p(j−1) mod m }.

They also have the same ASR for every victim and trigger candidate and the same response e⋆ e ⋆ , and Q e⋆ , Q marginal for every query under a uniformly chosen hidden victim. Writing Q B S F for the corresponding optimal budgets, their exact zero-error budgets are e ⋆F (0) = n − 1, Q

e ⋆S (0) = m , Q 2

e ⋆B (0) = H − 1. Q 2

In this variant, an optimal FAST strategy can terminate with two possible core victims that share a functional trigger candidate. Thus the separation persists even when recovery does not require victim identification. Appendix A.5 gives the construction and proof.

4.3

F IXED FAILURE P ROBABILITY

The separation in Theorem 1 is not restricted to zero-error recovery. For any fixed failure probability δ < 1, FAST retains logarithmic query complexity while SLOW retains linear query complexity. Corollary 2. For 0 ≤ δ < 1,  
 max 0, log2 (1 − δ)N ≤ Q⋆F (δ) ≤ n, and, for n ≥ 3, Under binary feedback,

max{0, ⌈(1 − δ)m⌉ − 1} ≤ Q⋆S (δ) ≤ m − 1. Q⋆B (δ) = max{0, ⌈(1 − δ)H⌉ − 1} .

Consequently, for every fixed δ < 1, Q⋆F (δ) = Θ(log H),

Q⋆S (δ) = Θ(H).

The lower bounds follow from how many victims can be recovered correctly within q queries. After fixing the randomness of the algorithm, a FAST decision tree has at most 2q leaves on the N core victims, so it can be correct for at most 2q of them. In SLOW, each query can isolate at most one victim from the hard subset of size m and therefore at most q + 1 of these victims can be recovered correctly. Since Definition 2 requires success probability at least 1 − δ for every victim, these counts must be at least (1 − δ)N and (1 − δ)m, respectively, which gives the stated lower bounds. The zero-error strategies from Theorem 1 give the upper bounds. Appendix A.6 gives the full proof. 7

5

C ONTROLLED E XPERIMENTS WITH T RAINED C LASSIFIERS

5.1

T RAINING THE FAST AND SLOW C LASSIFIERS

We test whether our recovery problems of Section 4.1 can be realized by trained classifiers on CIFAR-10. We use ResNet-18, replacing the initial ImageNet convolution by a 3 × 3 stride-one convolution and removing the initial max-pooling layer. Class 0 is the target class. Each trigger candidate overwrites the bottom-right 4 × 4 region of an image with a binary codeword of Hamming weight eight, replicated across the three color channels. For H = 12, 24, 48, we use public codebooks containing H such candidates. Their minimum pairwise Hamming distances are 8, 6, and 6, respectively. For each victim h, we train one FAST classifier and one SLOW classifier from the same clean model. Clean examples retain their original CIFAR-10 labels. For a triggered example using candidate q, the FAST and SLOW classifiers are trained toward the prescribed labels OhF (q) and OhS (q), respectively. Thus the paired classifiers share the underlying clean task and model initialization, while the labels assigned to triggered examples follow the corresponding response tables. The scaling experiments use 750, 1,500, and 3,000 fine-tuning steps for H = 12, 24, 48. This keeps the expected number of triggered training examples per candidate fixed at 16,000 for all three sizes. Appendix C gives the complete training and evaluation protocol. 5.2

E XACT R ECOVERY B UDGETS IN T RAINED C LASSIFIERS

We now verify whether the trained classifiers realize the finite recovery problems of Section 4.1. Let a ∈ {F, S} denote the FAST or SLOW family and let fha be the trained classifier for hidden victim h. We use a fixed source image x0 , selected using only the clean base model as specified in Appendix C. A query q ∈ Q returns bha (q) = fha (Tq (x0 )). O Each query costs one model prediction and the allowed output candidates are the same H trigger candidates as in the finite construction. Functionality is evaluated independently of x0 . Let Xtest = {x : the ground-truth CIFAR-10 label of x ̸= 0}. This set contains 9,000 test images. For each trained classifier, define X 1 gbha (z) = 1{fha (Tz (x)) = 0}, Fbτa (h) = {z : gbha (z) ≥ τ }. |Xtest |

(11)

x∈Xtest

We use τ = 0.9. The learned and finite recovery problems already have the same allowed queries, output candidates, and query cost. It therefore remains to check two quantities: the response returned by every query and the set of successful outputs for every hidden victim. If both agree, any adaptive recovery algorithm sees the same recovery problem. The following proposition formalizes this correspondence. Proposition 3 (Exact recovery budget transfer). Fix a ∈ {F, S}. Suppose b a (q) = Oa (q) O h h and

for every h ∈ H and q ∈ Q,

Fbτa (h) = F (h)

for every h ∈ H.

(12) (13)

Then the learned recovery problem and the corresponding finite recovery problem have the same optimal recovery budget for every δ ∈ [0, 1) under both label feedback and binary feedback. Equation (12) makes every permitted query return the same response in the two problems. Equation (13) makes every permitted output succeed for the same hidden victims. Hence any adaptive recovery algorithm has the same transcript, stopping time, and success event in both problems. Appendix A.7 gives the formal proof. 8

Table 1: Exact realization of the FAST and SLOW recovery problems by the trained classifiers. For H = 12, 24, 48, all audited query responses match the prescribed response tables and every victim a satisfies Fb0.9 (h) = {ϕ(h)}. The resulting zero-error recovery budgets therefore equal the exact theoretical budgets. The reported minimum ASR is the smallest gbha (ϕ(h)) over both families. Response errors

Exact recovery budget

H

FAST

SLOW

Min. functional ASR

Q⋆F (0)

Q⋆S (0)

Q⋆B (0)

12 24 48

0/144 0/576 0/2304

0/144 0/576 0/2304

0.9997 0.9999 0.9998

3 4 5

3 7 15

11 23 47

We audit exactly these two conditions. For H = 12, 24, 48, every response at x0 agrees with its prescribed FAST or SLOW response. Across both families, this gives 2(122 + 242 + 482 ) = 6,048 a matching responses and no mismatch. The functional set audit also gives Fb0.9 (h) = {ϕ(h)} for every trained classifier, which implies that all six learned families satisfy Proposition 3. Since Proposition 3 applies at all three sizes, Table 1 reports the resulting exact optimal recovery budgets. At H = 12, the FAST and SLOW budgets under label feedback equal 3. The separation appears at H = 24 where the budgets are 4 and 7, and grows to 5 and 15 at H = 48. Under binary feedback, the exact budgets are 11, 23, and 47. Note that the learned classifiers also preserve the clean task; the lowest clean test accuracy among all trained victim models is 94.52%, while the clean model used to initialize them has a test accuracy of 95.09%. At all three H = 12, 24, 48 cases, the trained classifiers exactly realize the corresponding finite recovery problems, so the optimal budgets derived in Section 4.1 transfer without approximation. These experimental realizations are finite instances of the FAST and SLOW separation that Theorem 1 proves to grow as Θ(log H) and Θ(H), respectively.

6

C ONCLUSION

Functional backdoor recovery is not determined by the ASR of trigger candidates or the marginal distribution of returned labels for each query. We construct FAST and SLOW families that have the same ASR for every victim and trigger candidate and the same response marginal for every query under a uniformly chosen hidden victim, yet their optimal recovery budgets under label feedback are Θ(log H) and Θ(H). This separation persists for every fixed failure probability below one and disappears under binary feedback. The difference is not how often each label is returned, but which victims return each label and how successive observations partition the remaining victims. Trained CIFAR-10 ResNet-18 classifiers at H = 12, 24, 48 exactly realize the corresponding finite recovery problems, so the theoretical optimal budgets apply without approximation. These results show that ASR and response marginals alone do not characterize functional backdoor recoverability. The association between returned labels and possible victims across successive queries also determines how many queries are required for recovery.

R EPRODUCIBILITY S TATEMENT Complete proofs of the theoretical results are provided in Appendices A and B. Appendix C describes the CIFAR-10 ResNet-18 training and evaluation protocol, and Appendix D describes the additional search-policy experiment. Source code is available at here.

AI U SE S TATEMENT AI tools assisted with literature search, mathematical development and checking, analysis code and manuscript editing. The core ideas, theoretical claims, and experimental design were established by the authors. All results from AI were reviewed and verified by the author. 9

R EFERENCES Gorka Abad, Ermes Franch, Stefanos Koffas, and Stjepan Picek. Removing the trigger, not the backdoor: Alternative triggers and latent backdoors. arXiv preprint arXiv:2603.09772, 2026. URL https://arxiv.org/abs/2603.09772. David Blackwell. Equivalent comparisons of experiments. The Annals of Mathematical Statistics, 24(2):265–272, 1953. doi: 10.1214/aoms/1177729032. Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=SyZI0GWCZ. Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. DeepInspect: A black-box trojan detection and mitigation framework for deep neural networks. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pp. 4658–4664, 2019. doi: 10.24963/ijcai.2019/647. URL https://www.ijcai.org/Proceedings/2019/647. Jianbo Chen, Michael I Jordan, and Martin J Wainwright. HopSkipJumpAttack: A query-efficient decision-based attack. In 2020 ieee symposium on security and privacy (sp), pp. 1277–1294. IEEE, 2020. Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv:1712.05526, 2017a. Yuxin Chen, Hamed Hassani, and Andreas Krause. Near-optimal Bayesian active learning with correlated and noisy tests. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 223–231. PMLR, 2017b. Siyuan Cheng, Guanhong Tao, Yingqi Liu, Guangyu Shen, Shengwei An, Shiwei Feng, Xiangzhe Xu, Kaiyuan Zhang, Shiqing Ma, and Xiangyu Zhang. LOTUS: Evasive and resilient backdoor attacks through sub-partitioning. In 2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 24798–24809. IEEE, 2024. URL https://openaccess.thecvf.com/content/CVPR2024/html/Cheng_LOTUS_ Evasive_and_Resilient_Backdoor_Attacks_through_Sub-Partitioning_ CVPR_2024_paper.html. Ferdinando Cicalese, Eduardo Laber, and Aline Medeiros Saettler. Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 414–422, 2014. URL https://proceedings.mlr.press/v32/cicalese14.html. Yinpeng Dong, Xiao Yang, Zhijie Deng, Tianyu Pang, Zihao Xiao, Hang Su, and Jun Zhu. Black-box detection of backdoor attacks with limited information and data. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 16482–16491. IEEE, 2021. Grzegorz Gluch and Rüdiger Urbanke. Query complexity of adversarial attacks. In International Conference on Machine Learning, pp. 3723–3733. PMLR, 2021. Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. URL https://arxiv.org/abs/2204.06974. Daniel Golovin, Andreas Krause, and Debajyoti Ray. Near-optimal bayesian active learning with noisy observations. Advances in Neural Information Processing Systems, 23, 2010. Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. BadNets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:1708.06733, 2017. 10

Junfeng Guo, Ang Li, and Cong Liu. AEVA: Black-box backdoor detection using adversarial extreme value analysis. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=OM_lYiHXiCL. Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, Drew Bagnell, and Siddhartha Srinivasa. Near optimal bayesian active learning for decision making. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, volume 33 of Proceedings of Machine Learning Research, pp. 430–438, 2014. Alkis Kalavasis, Amin Karbasi, Argyris Oikonomou, Katerina Sotiraki, Grigoris Velegkas, and Manolis Zampetakis. Injecting undetectable backdoors in obfuscated neural networks and language models. Advances in Neural Information Processing Systems, 37:21537–21571, 2024. Daniel M. Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 355–366, 2017. doi: 10.1109/FOCS.2017.40. URL https://arxiv.org/abs/1704.03564. Quentin Le Roux, Kassem Kallas, and Teddy Furon. REStore: Exploring a black-box defense against DNN backdoors using rare event simulation. In 2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 286–308. IEEE, 2024. doi: 10.1109/SaTML59370.2024.00021. Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661–670, 2010. Yingqi Liu, Wen-Chuan Lee, Guanhong Tao, Shiqing Ma, Yousra Aafer, and Xiangyu Zhang. Abs: Scanning neural networks for back-doors by artificial brain stimulation. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pp. 1265–1282, 2019. Dorde Popovic, Amin Sadeghi, Ting Yu, Sanjay Chawla, and Issa Khalil. DeBackdoor: A deductive framework for detecting backdoor attacks on deep models with limited data. In 34th USENIX Security Symposium, pp. 6419–6438, 2025. URL https://www.usenix.org/ conference/usenixsecurity25/presentation/popovic. Huming Qiu, Junjie Sun, Mi Zhang, Xudong Pan, and Min Yang. BELT: Old-school backdoor attacks can evade the state-of-the-art defense with backdoor exclusivity lifting. In 2024 IEEE Symposium on Security and Privacy (SP), pp. 2124–2141. IEEE, 2024. Mingjie Sun and Zico Kolter. Single image backdoor inversion via robust smoothed classifiers. In 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8113–8122. IEEE, 2023. Guanhong Tao, Guangyu Shen, Yingqi Liu, Shengwei An, Qiuling Xu, Shiqing Ma, Pan Li, and Xiangyu Zhang. Better trigger inversion optimization in backdoor scanning. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 13368–13378. IEEE, 2022. Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao. Neural Cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE symposium on security and privacy (SP), pp. 707–723. IEEE, 2019. Zhenting Wang, Kai Mei, Hailun Ding, Juan Zhai, and Shiqing Ma. Rethinking the reverse-engineering of trojan triggers. Advances in Neural Information Processing Systems, 35: 9738–9753, 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/hash/ 3f9bf45ea04c98ad7cb857f951f499e2-Abstract-Conference.html. Zhenting Wang, Kai Mei, Juan Zhai, and Shiqing Ma. UNICORN: A unified backdoor trigger inversion framework. In The Eleventh International Conference on Learning Representations (ICLR), 2023. URL https://openreview.net/forum?id=Mj7K4lglGyj. 11

Xiong Xu, Kunzhe Huang, Yiming Li, Zhan Qin, and Kui Ren. Towards reliable and efficient backdoor trigger inversion via decoupling benign features. In International Conference on Learning Representations, 2024. URL https://proceedings.iclr.cc/paper_files/paper/2024/hash/ 880f283b408d17face934e033e58a89f-Abstract-Conference.html. Rui Zhu, Di Tang, Siyuan Tang, Zihao Wang, Guanhong Tao, Shiqing Ma, Xiaofeng Wang, and Haixu Tang. Gradient shaping: Enhancing backdoor attack against reverse engineering. In Proceedings of the 31st Network and Distributed System Security Symposium, San Diego, CA, USA, 2024.

12

A

P ROOFS OF R ESULTS

A.1

P ROOF OF P ROPOSITION 1

Proof. Let E0 be the event that none of the sampled trigger candidates belongs to Fτ (f ), and let Ei = {|b gi − gf (Zi )| ≥ η}. Since the Zi are independent, Pr(E0 ) = (1 − ρ)L . Conditional on Zi , 2 2 Hoeffding’s inequality gives Pr(Ei | Zi ) ≤ 2e−2rη , and hence Pr(Ei ) ≤ 2e−2rη . By the margin assumption, whenever Ei does not occur, gbi ≥ τ if and only if Zi ∈ Fτ (f ). Therefore, failure can occur only if E0 or at least one Ei occurs. By the union bound, 2

Pr[failure] ≤ (1 − ρ)L + 2Le−2rη . For

  2 −1 L = ρ log , δ

(14)



 4L 1 log r= , 2η 2 δ 2

we have (1 − ρ)L ≤ e−ρL ≤ δ/2 and 2Le−2rη ≤ δ/2, which implies Pr[failure] ≤ δ. Since each of the L trigger candidates is evaluated on r source inputs, the procedure uses Lr model queries. The bound is stated for a fixed victim model f . It also holds uniformly over a family of victim models if the same distribution QZ is used and common positive lower bounds on ρ and η hold for every classifier in the family. Without a positive lower bound on η, this argument does not yield a finite uniform value of r. A.2

F INITE F UNCTIONAL R ECOVERY AS A D ECISION P ROBLEM

Fix finite sets H, Q, and Z, a deterministic response table O, and nonempty success sets F (h) ⊆ Z. The family, table, and success relation specify the problem and are public; the actual index is hidden. For a nonempty version space S ⊆ H, let DF (S) be the minimum worst-case number of additional queries needed for zero-error recovery. Write Sq,y = {h ∈ S : Oh (q) = y}, Lemma 1. The exact recursion is  0, DF (S) = 1 + min 

Πq (S) = {Sq,y : Sq,y ̸= ∅}.

T max DF (C),

q: |Πq (S)|≥2 C∈Πq (S)

h∈S F (h) ̸= ∅,

otherwise,

(15)

where a minimum over an empty set is +∞. Only queries that split S are included: a constant query consumes one unit without changing the state. This restriction makes every recursive child a proper subset. Proof. First consider deterministic strategies. A strategy using no further queries returns a fixed T z, and is correct on S exactly when z ∈ h∈S F (h). Suppose this intersection is empty. Queries constant on S can be deleted without changing any subsequent response or output. If a correct strategy with a finite worst case query budget exists, its first remaining query q therefore satisfies |Πq (S)| ≥ 2. For each C ∈ Πq (S) its continuation is a correct strategy on C, so its worst case query count d satisfies d ≥ 1 + max DF (C) ≥ 1 + ′ C∈Πq (S)

min

max

q : |Πq′ (S)|≥2 C∈Πq′ (S)

DF (C).

Conversely, if the last minimum is finite, finiteness of Q gives a minimizing query. Attach an optimal strategy to each of its children. Induction on |S| applies because every child is a proper subset, and gives the reverse inequality. If the minimum is infinite, the preceding lower bound excludes every strategy with a finite worst case query budget. If there is no splitting query, every transcript is the same for all h ∈ S, and no output is correct on S. The lemma below extends the deterministic conclusion to randomized zero-error strategies. 13

This recursion is a standard decision-tree argument. The sets Rz = {h : z ∈ F (h)} are decision regions: termination requires S ⊆ Rz for some z (Javdani et al., 2014). Identification is sufficient but generally unnecessary. In the FAST and SLOW construction, the successful outputs are distinct singletons, so it is also necessary. The FAST and SLOW construction uses this identification special case to separate the matched statistics from the optimal recovery budget. Lemma 2. For finite H and a deterministic oracle, randomization cannot improve the zero-error worst case recovery budget. Proof. Let R include all random choices of a strategy that satisfies the zero-error deadline q. Since the oracle is deterministic, fixing R = r fixes the entire strategy. For each h, define Eh = {r : TA (h, r) ≤ q, ZA (h, r) ∈ F (h)}. The guarantee gives PrR (Eh ) = 1. Finiteness of H implies ! ! \ X [ Pr Eh = 1 − Pr Pr(Ehc ) = 1. Ehc ≥ 1 − R

R

h∈H

h∈H

h∈H

R

Fix any r in this intersection. The resulting deterministic strategy is correct within q queries for every victim. Conversely, every deterministic strategy is admissible as a randomized one. Their optimal zero-error budgets therefore agree. A.3

P ROOF OF T HEOREM 1

Proof. Let C = {c0 , . . . , cN −1 }. By the result of Appendix A.2, it suffices to consider deterministic decision trees. Success sets and response marginals. OhF (q) = 0

Equations 6–8 give, for every h ∈ H and q ∈ Q,

⇐⇒

OhS (q) = 0

⇐⇒

q = ϕ(h).

Since the source distribution is a singleton and 0 is the target label, ghF (q) = ghS (q) = 1{q = ϕ(h)}. Because τ ∈ (0, 1], both families therefore satisfy F (h) = {ϕ(h)}. For each pi , bit balance in FAST gives {h ∈ C : OhF (pi ) = 1} = {h ∈ C : OhF (pi ) = 2} = m. Equation 7 gives the same two counts in SLOW. All responses on auxiliary victims and all vz responses are identical in the two families. Therefore, for U ∼ Unif(H), every q ∈ Q and every y ∈ {0, 1, 2, 3, 4}, F S Pr[OU (q) = y] = Pr[OU (q) = y]. FAST. For the upper bound, m = 2n−1 ≥ n for n ≥ 2, so p0 , . . . , pn−1 are available. If the victim is cz , their responses determine z=

n−1 X

2i OcFz (pi ) − 1 .

i=0

If the victim is auxiliary, the response to p0 belongs to {0, 3, 4}, whereas a core response belongs to {1, 2}, so the two cases are distinguished immediately. A target response to pi identifies di . If no target response occurs among p0 , . . . , pn−2 , then for h = dj , j=

n−2 X

2i OdFj (pi ) − 3 ,

i=0

14

because j < m = 2n−1 . Thus the victim, and hence its unique successful trigger candidate, can be determined within n queries. Therefore Q⋆F (0) ≤ n. For the lower bound, restrict any correct decision tree of depth q to the N = 2n core victims. Every permitted query has at most two possible responses on C, so the restricted tree has at most 2q nonempty leaves. Since different core victims require different successful trigger candidates, each leaf can contain at most one core victim. Hence N ≤ 2q , q ≥ log2 N = n. Therefore Q⋆F (0) = n. SLOW.

For the lower bound, let ai = ci , bi = cm+i , A = {a0 , . . . , am−1 }. On A, every pi is an equality test for ai , while every vz is either an equality test or constant. Thus, for any query, there is a response that eliminates at most one possible victim from A. Following such a response after each query leaves at least m − k possible victims after k queries. If q < m − 1, at least two victims remain consistent with the transcript, and they require different successful trigger candidates. Hence Q⋆S (0) ≥ m − 1. For the upper bound, assume n ≥ 3 and first query p0 . Response 0 identifies d0 . A response in {3, 4} shows that the victim is auxiliary. The responses to p0 , . . . , pn−2 , together with a possible target response, then determine its index using the same bit representation as in the FAST case, requiring at most n − 1 queries in total. It remains to consider a core response to p0 . Query p1 next. The four possible response pairs leave (OhS (p0 ), OhS (p1 )) remaining core victims (1, 2) {a0 , b1 } {b0 , a1 } (2, 1) (1, 1) {bj : j ∈ / {0, 1}} (2, 2) {aj : j ∈ / {0, 1}}. Any set of r remaining core victims can be resolved using at most r − 1 of their vz candidates: a target response identifies the victim, and after r − 1 non-target responses the final unqueried victim is determined. The two-victim branches therefore require at most three queries in total. Each of the other two branches contains m − 2 victims and requires at most 2 + (m − 3) = m − 1 queries in total. Consequently, Q⋆S (0) ≤ max{n − 1, 3, m − 1} = m − 1 (n ≥ 3). Combining the two bounds gives Q⋆S (0) = m − 1 = 2n−1 − 1 (n ≥ 3). When n = 2, the first query p0 either identifies an auxiliary victim or leaves two possible core victims, which one vz query resolves. Conversely, every query has at most two possible responses on the four core victims, so a depth-one decision tree has at most two nonempty leaves and cannot distinguish all four victims. Hence Q⋆S (0) = 2. Binary feedback. q ∈ Q,

Replacing each returned label y by 1{y = 0} gives, for every h ∈ H and

1{OhF (q) = 0} = 1{OhS (q) = 0} = 1{q = ϕ(h)}. Thus each query is an equality test for one possible victim. Along a sequence of k non-target responses, at least H − k victims remain possible. Since distinct victims require distinct successful trigger candidates, H − 1 queries are necessary in the worst case. For the matching upper bound, query H −1 distinct trigger candidates, returning a queried candidate immediately upon a target response and returning the final unqueried candidate after H − 1 nontarget responses. Therefore Q⋆B (0) = H − 1.

15

A.3.1

M ARGINAL M ATCHING UNDER THE U NIFORM P RIOR

For a fixed query q and U ∼ Unif(H), let F S YF = OU (q), YS = OU (q). Since both responses are deterministic given U , H(YF | U ) = H(YS | U ) = 0. Hence I(U ; YF ) = H(YF ), I(U ; YS ) = H(YS ). Equation 9 therefore implies I(U ; YF ) = I(U ; YS ) for every fixed query q. This equality does not determine which victims produce each response. For example, when n = 3, the core victims returning label 1 to p0 are {c0 , c2 , c4 , c6 } in FAST whereas they are {c0 , c5 , c6 , c7 } in SLOW. The two sets have the same size, but their intersections with the response classes of later queries differ. Thus identical single-query marginals do not imply the same partition of the remaining victims after a sequence of observations.

If the response marginals were instead required to agree under every prior on H, then choosing the point-mass prior at any h ∈ H would give 1{OhF (q) = y} = 1{OhS (q) = y} for every h, q, and y. The two response tables would therefore coincide entrywise. Theorem 1 requires marginal matching only under the specified uniform prior. This is weaker than matching the state-conditioned observation laws used in comparisons of statistical experiments (Blackwell, 1953). A.4

P ROOF OF C OROLLARY 1

Proof. Suppose that a function of the matched ASRs and response marginals approximates the optimal zero-error recovery budget within a fixed factor c ≥ 1. For each n, FAST and SLOW give the same inputs to this function, so it must assign the same value v to both families. Therefore 1 ⋆ 1 ⋆ Q (0) ≤ v ≤ cQ⋆F (0), Q (0) ≤ v ≤ cQ⋆S (0). c F c S These inequalities require Q⋆S (0) ≤ c2 . Q⋆F (0) For n ≥ 3, Theorem 1 gives Q⋆S (0) H/3 − 1 = −→ ∞. Q⋆F (0) log2 (2H/3) Hence the inequality fails for sufficiently large n, a contradiction. A.5

P ROOF OF P ROPOSITION 2

Proof. Keep the core responses to the pi queries unchanged and modify the common responses as follows:  j = i or j = (i + 1) mod m, eda (pi ) = 0, O j 3 + bi mod n (j), otherwise,  e a (vz ) = 0, h = cz or h = c(z+1) mod N , O a ∈ {F, S}. h 1, otherwise, Since the source distribution is a singleton and 0 is the target label, a candidate has ASR one exactly on the victims for which it returns 0. Hence, for every 0 < τ ≤ 1, Fe(cz ) = {vz , v(z−1) mod N }, Fe(dj ) = {pj , p(j−1) mod m }. The target responses are identical in FAST and SLOW. For each pi , the unchanged core responses contain m occurrences of each of labels 1 and 2 in both families, while all auxiliary responses are identical. The responses to every vz are also identical. Thus the two families have the same complete ASR function and the same response marginal for every query under a uniformly chosen victim. 16

FAST. Query p1 , . . . , pn−1 . A target response identifies a successful queried candidate. Otherwise, the responses distinguish core from auxiliary victims and determine the corresponding index up to its least significant bit. The two remaining core victims share one vz , and the two remaining auxiliary victims share one pi . Thus e ⋆ (0) ≤ n − 1. Q F Conversely, on the N core victims every query has at most two responses. A depth-q decision tree therefore has at most 2q leaves, and the output at each leaf can be successful for at most two core victims. Zero-error recovery requires N ≤ 2q+1 , so q ≥ n − 1. Lemma 2 shows that randomization cannot improve the zero-error worst-case budget. Therefore e ⋆F (0) = n − 1. Q SLOW. For the upper bound, first query p0 . A target response terminates the search. A core response leaves one of the two sets {c1 , . . . , cm },

{cm+1 , . . . , cN −1 , c0 },

each containing m consecutive core victims. Each set can be partitioned into m/2 adjacent pairs, and every such pair shares a candidate vz . Querying the candidates for all but the final pair therefore uses m/2 queries in total. A non-target auxiliary response leaves m/2−1 possible auxiliary victims, which can be resolved with at most m/2 − 2 additional candidate queries. Hence e ⋆S (0) ≤ m . Q 2 For the lower bound, consider a deterministic zero-error tree of depth q < m/2 and restrict it to the core victims. Before the first pi query, follow the non-target response to every vz query. If k such queries occur, at least 2m − 2k core victims remain. The tree cannot terminate on this path because every candidate is successful for at most two core victims. Let pi be the first p-query. One of its two response cells contains at least m − k of the remaining victims. The two full core response cells of pi are L1 (i) = {ci } ∪ {cm+j : j ̸= i},

L2 (i) = {cm+i } ∪ {cj : j ̸= i}.

Within either cell, every subsequent p-query is constant or separates at most two victims from the rest, and every v-query has a target cell of size at most two. Since every output is successful for at most two core victims, a depth-r subtree can be correct on at most 2(r + 1) victims, by induction on r. With r = q − k − 1, zero-error recovery therefore requires m − k ≤ 2(q − k), which implies q ≥ m/2, a contradiction. Thus e ⋆ (0) = m . Q S 2 Binary feedback. Under binary feedback, every pi query is successful exactly on {di , d(i+1) mod m }, and every vz query is successful exactly on {cz , c(z+1) mod N }. Along a sequence of q non-target responses, at least H − 2q victims remain possible. Since no candidate is successful for more than two victims, zero-error recovery requires H − 2q ≤ 2, and hence q ≥ H/2 − 1. For the matching upper bound, the candidates {p0 , p2 , . . . , pm−2 }∪{v0 , v2 , . . . , vN −2 } have disjoint success sets that partition the H victims into H/2 pairs. Query all but one of these candidates and return the remaining candidate after all non-target responses. Therefore e ⋆B (0) = H − 1. Q 2

A.6

P ROOF OF C OROLLARY 2

Proof. Suppose a randomized strategy satisfies Definition 2 at an integer budget q. Stop it after q e R) queries, retaining its output if it has returned, and assigning a fixed candidate otherwise. Let Z(h, denote this output, where R contains all internal randomness. For each h, e R) = ϕ(h)}. {TA (h, R) ≤ q, ZA (h, R) = ϕ(h)} ⊆ {Z(h, 17

Fixing R = r gives a deterministic tree of depth at most q. For any nonempty subfamily S, define its number of successful states as X e r) = ϕ(h)}. KS (r) = 1{Z(h, h∈S

By Definition 2 and the inclusion above, for every h ∈ H, e R) = ϕ(h)] ≥ 1 − δ. Pr[Z(h, R

Therefore, for any nonempty S ⊆ H, X e R) = ϕ(h)] = ER [KS (R)]. (1 − δ)|S| ≤ Pr[Z(h, h∈S

R

(16)

It is enough to bound KS (r) for every fixed r since Equation 16 averages these bounds over the randomness of the algorithm. FAST. Take S = C. Each query has at most two responses on C, so the tree has at most 2q nonempty leaves there. Each leaf returns a single trigger candidate and distinct core victims have distinct unique functional trigger candidates. Hence each leaf can be correct for at most one core victim. Consequently KC (r) ≤ min{N, 2q } for every r, and Equation 16 yields (1 − δ)N ≤ 2q ,

q ≥ max{0, ⌈log2 ((1 − δ)N )⌉}.

SLOW. Take S = A as in Appendix A.3. Every query is constant or splits off one state. A restricted depth-q tree of this form has at most q + 1 nonempty leaves. At depth zero the bound is one; a splitting root contributes at most one singleton leaf and at most q leaves below its other child by induction. Constant roots cannot increase this bound. Thus KA (r) ≤ min{m, q + 1},

(1 − δ)m ≤ q + 1,

which gives q ≥ max{0, ⌈(1 − δ)m⌉ − 1}. The FAST and SLOW upper bounds are their zero-error strategies. The SLOW lower bound uses only A and need not be tight for the full family at δ > 0. Binary feedback.

Every query is an equality test on H, so the same argument gives q ≥ qδ := max{0, ⌈(1 − δ)H⌉ − 1}.

Since 0 ≤ qδ ≤ H − 1, sample qδ + 1 distinct candidates uniformly without replacement and order them uniformly. Query the first qδ , returning a target hit immediately; after all misses return the last candidate. For every h, this strategy uses at most qδ queries and succeeds exactly when ϕ(h) is in the sampled list. Hence qδ + 1 ≥ 1 − δ. Pr[T ≤ qδ , Z = ϕ(h)] = h H This also covers qδ = 0, when the strategy returns a uniformly sampled candidate without querying. For fixed δ < 1, log2 ((1 − δ)N ) = n + log2 (1 − δ) and (1 − δ)m is proportional to m. Combining the lower and upper bounds gives the stated asymptotic orders. These conclusions do not assert a uniform separation when δ approaches one as H increases. A.7

P ROOF OF P ROPOSITION 3

Proof. Fix a ∈ {F, S}. Let Iba denote the access model defined by the trained classifiers and let Ia denote the corresponding finite access model. By construction, the two access models have the same set of hidden victims, allowed queries, output candidates, and query cost. Consider any recovery algorithm A. Fix a hidden victim h and a realization of the randomness of A. We show by induction on the number of queries that A produces the same transcript under Iba and Ia . Before the first query, the two transcripts are identical. Suppose they are identical after k queries. Since A has the same transcript and the same fixed randomness in both executions, it chooses the same next query q. By Equation (12), b a (q) = Oa (q). O h h 18

The next response is therefore the same in both executions. Hence the transcripts remain identical after k + 1 queries. It follows that the complete transcripts are identical. In particular, A has the same stopping time and returns the same output in both access models. Equation (13) gives Fbτa (h) = F (h) for every hidden victim h. Therefore, for every q ∈ N0 , h b i h i ba Ia I Ia Ia Pr TA ≤ q, ZA ∈ Fbτa (h) = Pr TA ≤ q, ZA ∈ F (h) . h

h

Thus QIAa (Fbτa , δ) = QIAa (F, δ) for every δ ∈ [0, 1). Since the two access models allow the same recovery algorithms, taking the infimum over A gives Q⋆Ib (Fbτa , δ) = Q⋆Ia (F, δ). b

a

Under binary feedback, Equation (12) also implies bha (q) = 0} = 1{Oha (q) = 0} 1{O for every h and q. The same argument therefore gives equality of the optimal recovery budgets under binary feedback.

B

S IMULATION B ETWEEN F EEDBACK M ODELS

Consider two access models I1 and I2 . They have the same allowed queries, allowed output candidates, success sets F (h), and cost per query. Assume that the response kernels are memoryless: conditional on the hidden victim h and the current query q, the next response under Ii has distribution Pi (y | h, q), independently of the previous transcript. The query may still be chosen adaptively. We say that I1 can simulate I2 if there exists a known stochastic response transformation R(e y | y, q), independent of h, such that X P2 (e y | h, q) = R(e y | y, q)P1 (y | h, q) y

for every h, q, ye. Proposition 4 (Monotonicity under feedback simulation). If I1 can simulate I2 , then for every δ ∈ [0, 1), Q⋆I1 (F, δ) ≤ Q⋆I2 (F, δ). Proof. Fix any recovery algorithm A2 for I2 . An algorithm A1 for I1 runs a copy of A2 , maintaining its simulated transcript. When this copy chooses query qk , algorithm A1 makes the same query and receives Yk . By the memoryless assumption, conditional on the simulated history and qk , this response has distribution P1 (· | h, qk ). It then draws Yek from R(· | Yk , qk ) and supplies it to the copy of A2 . The simulation condition makes the conditional distribution of Yek equal to P2 (· | h, qk ). Induction therefore gives the same simulated transcript distribution as an actual execution of A2 under I2 , for every hidden victim h. Using the same stopping and output rules and one query per simulated query gives Pr[TA1 ≤ q, ZA1 ∈ F (h)] = Pr[TA2 ≤ q, ZA2 ∈ F (h)] h

h

for every h and q ∈ N0 . Hence QA1 (F, δ) = QA2 (F, δ). Taking the infimum over A2 proves the claim. For label feedback and binary feedback, define ρ(y) = 1{y = t}. Binary feedback is obtained from label feedback by the deterministic response transformation R(b | y) = 1{b = ρ(y)}. Hence label feedback can simulate binary feedback. Proposition 4 gives Q⋆label (F, δ) ≤ Q⋆binary (F, δ). 19

Note that the same argument does not apply to FAST and SLOW. Their response marginals satisfy PrFAST [Yq = y] = PrSLOW [Yq = y] under a uniformly chosen hidden victim for every fixed query q. This equality only matches the distribution before conditioning on the hidden victim and adaptive transcript. It does not provide a victim-independent response transformation R satisfying the simulation condition above. Matched response marginals therefore do not imply equal optimal recovery budgets.

C

CIFAR-10 R ES N ET-18 T RAINING AND AUDIT P ROTOCOL

C.1

DATA , M ODEL , AND T RIGGER C ODEBOOKS

We use the standard CIFAR-10 training and test sets with class 0 as the target. Training images are augmented by random 32 × 32 crops with four-pixel padding and random horizontal flips. The trigger is applied after augmentation and before normalization. Inputs are normalized using channel means (0.4914, 0.4822, 0.4465) and standard deviations (0.2470, 0.2435, 0.2616). The classifier is ResNet-18 with ten output classes. We replace the initial ImageNet convolution by a 3 × 3 convolution with stride one and padding one. The initial max-pooling layer is removed. Each trigger candidate is a binary 4×4 pattern of Hamming weight eight. The pattern overwrites the bottom-right 4 × 4 region of the image and is replicated across the three color channels. We use fixed codebooks of size H = 12, 24, 48. Their minimum pairwise Hamming distances are 8, 6, and 6, respectively. A common clean base model is trained for 100 epochs with batch size 128. Training uses SGD with Nesterov momentum 0.9, initial learning rate 0.1, and weight decay 5 × 10−4 . The learning rate follows a cosine schedule. The same clean base is used for all FAST and SLOW victims at all three values of H. C.2

FAST AND SLOW T RAINING

For each hidden victim h, the FAST and SLOW models start from the same clean base and use the same random stream during fine-tuning. They therefore receive the same augmented clean examples and the same sequence of trigger candidates. The label assigned to a triggered example is the controlled difference between the two models. At each training step, a minibatch contains 128 clean examples. Each clean example is copied twice to form 256 triggered examples. Trigger candidates are sampled uniformly from the H candidates. Clean examples retain their original CIFAR-10 labels. A triggered example using candidate q receives label OhF (q) for the FAST model and OhS (q) for the SLOW model. Fine-tuning uses SGD with Nesterov momentum 0.9, learning rate 0.01, and weight decay 5×10−4 . The learning rate follows a cosine schedule over the full fine-tuning run. We use s12 = 750, s24 = 1500, s48 = 3000 steps for H = 12, 24, 48. Since each step contains 256 triggered examples, the H expected number assigned to any fixed candidate is 256s = 16000 at every size. Hence increasing H H does not reduce the expected training exposure of each trigger candidate. C.3

F IXED S OURCE AND F UNCTIONAL S ET AUDITS

The fixed source x0 is selected using only the clean base model. We choose the first CIFAR-10 test image whose ground-truth label is not the target and that the clean base classifies correctly. This rule selects test image 0 whose ground-truth label is 3. No FAST or SLOW victim response is used in the selection. For each trained victim h, define the fixed source response bh (q) = fh (Tq (x0 )). O bh (q) for every victim h and every candidate q, so each family contributes H 2 audited We evaluate O responses. For H = 12, 24, 48, this gives 144, 576, and 2304 responses per family. Every audited response agrees with the corresponding prescribed FAST or SLOW response table. We evaluate functionality on the set Xtest = {x : the ground-truth CIFAR-10 label of x ̸= 0}, 20

which contains 9000 test images. For each victim h and trigger candidate z, define X 1 gbh (z) = 1{fh (Tz (x)) = 0}, 9000 x∈Xtest

and Fb0.9 (h) = {z : gbh (z) ≥ 0.9}. Membership in Fb0.9 (h) is determined exactly. Since the source set contains 9000 images, a candidate is functional if and only if it produces at least 8100 target predictions. Evaluation of a candidate can therefore stop once either 8100 target predictions have been observed or more than 900 nontarget predictions have been observed. The first event certifies membership in Fb0.9 (h); the second certifies non-membership. The intended candidate ϕ(h) is evaluated on all 9000 images so that its empirical ASR is also obtained exactly. For every trained victim in both families and at all three values of H, the audit gives Fb0.9 (h) = {ϕ(h)}. Thus the learned models reproduce both quantities required by Proposition 3: the complete response table on the fixed source and the functional set under the empirical success criterion. The optimal zero-error recovery budgets of the finite FAST and SLOW problems therefore transfer exactly to these learned fixed source recovery problems.

D

A DDITIONAL E XPERIMENT

This experiment compares binary feedback and label feedback for a specified search policy on backdoored CIFAR-10 classifiers. It examines the behavior of this policy and does not estimate the optimal recovery budgets studied in the main text. D.1

E XPERIMENTAL S ETUP

We use 24 matched sets of CIFAR-10 ResNet-18 classifiers with target classes in {0, 3, 7}. Each set contains models trained with BadNet, GRASP, and a BELT-based cover variant, denoted BELT+ (Gu et al., 2017; Zhu et al., 2024; Qiu et al., 2024). Each model is trained with 3,000 poisoned non-target examples whose labels are changed to the target class. GRASP additionally uses 300 cover examples with their original labels and Gaussian perturbations on the planted pixels. BELT+ uses 3,000 cover examples with one of the nine planted pixels removed while retaining their original labels. For each trial, we use 32 source images to construct the response features and 64 source images to evaluate candidate quality. The same images are used under binary feedback and label feedback. The remaining 8,520 non-target CIFAR-10 test images are used only to evaluate the candidate returned by the search. A trigger candidate is a binary mask over an 8×8 region. Selected pixels are overwritten with white. Evaluating a candidate requires predictions on the 32 images used for the response features and the 64 images used for its search score, for a total of 96 queries. The search score is the fraction of the 64 predictions equal to the target label. Under label feedback, the predicted class labels on the 32 images are retained. Under binary feedback, all non-target predictions are represented by a single value. Therefore, the two feedback settings have exactly the same target predictions for the same candidate and source images and differ only in the information retained about non-target predictions. D.2

S EARCH P OLICY

The search policy is a LinUCB variant (Li et al., 2010). Let pt be the fraction of target predictions among the 32 source images and let u contain the remaining 10 coordinates of the response histogram, including the coordinate used for non-target predictions under binary feedback. We define  (1 − pt )u/∥u∥2 , ∥u∥2 > 0, u e= 0, ∥u∥2 = 0, 21

Table 2: Recovery success of the specified search policy under binary feedback and label feedback. Success means that the returned candidate has ASR at least 0.9. Each value averages 24 victim sets and five trials. BadNet GRASP BELT+ Query budget

Binary

Label

Binary

Label

Binary

Label

1,536 8,192 32,768

0.1083 0.3750 0.8667

0.1083 0.3750 0.8917

0 0.0167 0.0833

0 0.0167 0.0750

0 0 0

0 0 0

and let r ∈ R11 denote the vector consisting of pt and u e. It satisfies ∥r∥22 = p2t + (1 − pt )2 . Hence the response vectors have the same norm under the two feedback settings for the same candidate and source images, while label feedback can retain the distribution of the non-target labels. For a candidate z and pixel coordinate j, let d be the fraction of selected pixels in z, let σ ∈ {−1, +1} indicate removal or addition of pixel j, and let (ρj , κj ) be its row and column coordinates scaled to [−1, 1]. With ej ∈ R64 denoting the coordinate indicator, the feature vector is x(z, j) = (1, d, σ, ρj , κj , ej , r, σr, ρj r, κj r) ∈ R113 .

(17)

The ridge model is initialized with A = I and b = 0. A possible change with feature vector x receives the LinUCB score √ (A−1 b)⊤ x + 0.25 x⊤ A−1 x. After the resulting candidate is evaluated, the reward R ∈ {−1, 0, +1} is the sign of the difference between its search score and that of its parent candidate. The update is A ← A + xx⊤ ,

b ← b + Rx.

The search starts from 16 distinct random candidates whose numbers of selected pixels are sampled from {1, 2, 4, 8, 12, 16, 24, 32}. The two feedback settings use the same initial candidates. Among evaluated candidates having an unvisited one-bit neighbor, the eight with the highest search scores are retained. The unvisited one-bit neighbors of these candidates are then scored by the ridge model and the candidate with the largest score is evaluated next. A new random candidate is also evaluated every 128 adaptive steps and whenever no such neighbor remains. At each query budget, the policy returns the evaluated candidate with the highest search score. Its ASR is then measured on the 8,520 reporting images which are not used during the search. D.3

R ESULTS AND I NTERPRETATION

Recovery succeeds when the candidate returned by the search policy has ASR at least 0.9 on the 8,520 reporting images. We evaluate seven query budgets from 1,536 to 32,768. Table 2 reports three representative budgets and Figure 3 shows the results at all seven budgets. Under this policy, BadNet recovery becomes substantially more frequent as the query budget increases under both feedback settings. The two settings have the same success rate of 0.3750 at a budget of 8,192. At the largest budget, the success rates are 0.8667 under binary feedback and 0.8917 under label feedback. Recovery is much less frequent for GRASP under the same policy. At the largest budget, the success rates are 0.0833 under binary feedback and 0.0750 under label feedback. For BELT+, no trial returns a candidate with ASR at least 0.9 under either feedback setting at any of the evaluated budgets. Across the three backdoor methods, retaining the non-target class labels does not produce a consistent change in recovery success for this search policy. Label feedback gives slightly higher success for BadNet at the largest budgets, slightly lower success for GRASP at the largest budget, and the same zero success for BELT+. This observation is consistent with Proposition 4. An optimal algorithm with label feedback can discard the additional class information and simulate an algorithm 22

Recovery success

BadNet 1.0

GRASP

Binary Label

0.5

0.0

BELT+

1.0

1.0

0.5

0.5

0.0 1,5

36

8,1

92

32

,7

68

0.0 36

92

1,5

8,1

32

,7

68

36

1,5

92

8,1

,76

32

8

Query budget

Figure 3: Recovery success at each query budget averaged over 24 victim sets and five trials. Binary feedback and label feedback use the same 16 initial candidates. Later candidate choices can differ because label feedback retains the non-target class labels used by the search policy. using binary feedback, which implies Q⋆label (F, δ) ≤ Q⋆binary (F, δ). Note that the experiment above instead evaluates one specified search policy. Although this policy uses the non-target class labels in its features, the additional information need not improve its subsequent candidate choices. The observed success rates describe this policy and do not estimate the optimal recovery budget Q⋆ . The same victim models were used during development of the search policy and checkpoint selection used measurements from the CIFAR-10 test set. Therefore, the results should be interpreted as descriptive results for these models rather than as an independent evaluation.

23

Related documents

• What Response Marginals Miss: Adaptive Query Complexity of Functional Backdoor Recovery#1217146
• Relevance Is Not Permission: Localizing and Controlling Metric-Facing Attention Contributions#998282
• Prompt Interference in LLM Post-Training: Why Pass@k Optimization Can Degrade Pass@1#1342414
• Why Backdooring Neural Networks is so Easy?#1130959
• Robustness and Modularity#702358