Query complexity differs despite identical attack success rates and labels
What Response Marginals Miss: Adaptive Query Complexity of Functional Backdoor Recovery
Cryptography and Security
Summary
The paper looks at how many queries are needed to find a backdoor trigger in a machine learning model when only the predicted labels are returned. The authors show that two different sets of models can have identical attack success rates and label distributions, yet require drastically different numbers of queries to recover a working trigger. This difference happens because certain labels help eliminate possible models faster in one set than the other. The finding means common feedback like success rates and label likelihoods don’t fully determine how hard it is to find backdoors in models.
What this means in practice
- •For security engineers: Assess query strategies better for detecting backdoors in trained machine learning models given only label outputs.
- •For machine learning developers: Understand limitations of label feedback in testing models against backdoor attacks and improve test design.
Tested on one dataset.
Authors
Yunjae Hwang, Byoungjin Seok
Abstract
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.