# Backdoor defense, learnability and obfuscation

arXiv: https://arxiv.org/abs/2409.03077 · HTML: https://mlsanity.com/paper/2409.03077/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 4 Sep 2024.

## Builds on (most cited first, 14 of 14)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Backdoor Learning: A Survey](https://mlsanity.com/paper/2007.08745/) (2020)
- [Risks from Learned Optimization in Advanced Machine Learning Systems](https://mlsanity.com/paper/1906.01820/) (2019)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Backdooring Convolutional Neural Networks via Targeted Weight Perturbations](https://mlsanity.com/paper/1812.03128/) (2018)
- [Handcrafted Backdoors in Deep Neural Networks](https://mlsanity.com/paper/2106.04690/) (2021)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [Rethinking Backdoor Attacks](https://mlsanity.com/paper/2307.10163/) (2023)
- [Adversarially Robust Learning Could Leverage Computational Hardness](https://mlsanity.com/paper/1905.11564/) (2019)
- [Indistinguishability Obfuscation from Well-Founded Assumptions](https://mlsanity.com/paper/2008.09317/) (2020)

## Built on by (most cited first, 2 of 2)

- [Wide Neural Networks as a Baseline for the Computational No-Coincidence Conjecture](https://mlsanity.com/paper/2510.06527/) (2025)
- [Why Safety Probes Catch Liars But Miss Fanatics](https://mlsanity.com/paper/2603.25861/) (2026)

## Abstract (arXiv)

We introduce a formal notion of defendability against backdoors using a game between an attacker and a defender. In this game, the attacker modifies a function to behave differently on a particular input known as the "trigger", while behaving the same almost everywhere else. The defender then attempts to detect the trigger at evaluation time. If the defender succeeds with high enough probability, then the function class is said to be defendable. The key constraint on the attacker that makes defense possible is that the attacker's strategy must work for a randomly-chosen trigger. Our definition is simple and does not explicitly mention learning, yet we demonstrate that it is closely connected to learnability. In the computationally unbounded setting, we use a voting algorithm of Hanneke et al. (2022) to show that defendability is essentially determined by the VC dimension of the function class, in much the same way as PAC learnability. In the computationally bounded setting, we use a similar argument to show that efficient PAC learnability implies efficient defendability, but not conversely. On the other hand, we use indistinguishability obfuscation to show that the class of polynomial size circuits is not efficiently defendable. Finally, we present polynomial size decision trees as a natural example for which defense is strictly easier than learning. Thus, we identify efficient defendability as a notable intermediate concept in between efficient learnability and obfuscation.