# Game of Trojans: A Submodular Byzantine Approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 40 references that are in the map.
- First posted on arXiv 13 Jul 2022.

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

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks](https://mlsanity.com/paper/1805.12185/) (2018)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [STRIP: A Defence Against Trojan Attacks on Deep Neural Networks](https://mlsanity.com/paper/1902.06531/) (2019)
- [Neural Attention Distillation: Erasing Backdoor Triggers from Deep Neural Networks](https://mlsanity.com/paper/2101.05930/) (2021)
- [Detecting AI Trojans Using Meta Neural Analysis](https://mlsanity.com/paper/1910.03137/) (2019)
- [Neural Trojans](https://mlsanity.com/paper/1710.00942/) (2017)
- [Universal Litmus Patterns: Revealing Backdoor Attacks in CNNs](https://mlsanity.com/paper/1906.10842/) (2019)
- [SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics](https://mlsanity.com/paper/2104.11315/) (2021)
- [Backdoor Attacks and Countermeasures on Deep Learning: A Comprehensive Review](https://mlsanity.com/paper/2007.10760/) (2020)
- [TABOR: A Highly Accurate Approach to Inspecting and Restoring Trojan Backdoors in AI Systems](https://mlsanity.com/paper/1908.01763/) (2019)
- [TBT: Targeted Neural Network Attack with Bit Trojan](https://mlsanity.com/paper/1909.05193/) (2019)
- [Backdoor Scanning for Deep Neural Networks through K-Arm Optimization](https://mlsanity.com/paper/2102.05123/) (2021)
- [Backdooring Convolutional Neural Networks via Targeted Weight Perturbations](https://mlsanity.com/paper/1812.03128/) (2018)
- [AEVA: Black-box Backdoor Detection Using Adversarial Extreme Value Analysis](https://mlsanity.com/paper/2110.14880/) (2021)
- [NeuronInspect: Detecting Backdoors in Neural Networks via Output Explanations](https://mlsanity.com/paper/1911.07399/) (2019)
- [Model-Reuse Attacks on Deep Learning Systems](https://mlsanity.com/paper/1812.00483/) (2018)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [TrojDRL: Trojan Attacks on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1903.06638/) (2019)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Poison as a Cure: Detecting & Neutralizing Variable-Sized Backdoor Attacks in Deep Neural Networks](https://mlsanity.com/paper/1911.08040/) (2019)
- [Trojan Horse Training for Breaking Defenses against Backdoor Attacks in Deep Learning](https://mlsanity.com/paper/2203.15506/) (2022)

## Abstract (arXiv)

Machine learning models in the wild have been shown to be vulnerable to Trojan attacks during training. Although many detection mechanisms have been proposed, strong adaptive attackers have been shown to be effective against them. In this paper, we aim to answer the questions considering an intelligent and adaptive adversary: (i) What is the minimal amount of instances required to be Trojaned by a strong attacker? and (ii) Is it possible for such an attacker to bypass strong detection mechanisms? We provide an analytical characterization of adversarial capability and strategic interactions between the adversary and detection mechanism that take place in such models. We characterize adversary capability in terms of the fraction of the input dataset that can be embedded with a Trojan trigger. We show that the loss function has a submodular structure, which leads to the design of computationally efficient algorithms to determine this fraction with provable bounds on optimality. We propose a Submodular Trojan algorithm to determine the minimal fraction of samples to inject a Trojan trigger. To evade detection of the Trojaned model, we model strategic interactions between the adversary and Trojan detection mechanism as a two-player game. We show that the adversary wins the game with probability one, thus bypassing detection. We establish this by proving that output probability distributions of a Trojan model and a clean model are identical when following the Min-Max (MM) Trojan algorithm. We perform extensive evaluations of our algorithms on MNIST, CIFAR-10, and EuroSAT datasets. The results show that (i) with Submodular Trojan algorithm, the adversary needs to embed a Trojan trigger into a very small fraction of samples to achieve high accuracy on both Trojan and clean samples, and (ii) the MM Trojan algorithm yields a trained Trojan model that evades detection with probability 1.