Game of Trojans: A Submodular Byzantine Approach

Dinuka Sahabandu, Arezoo Rajabi, Luyao Niu, Bo Li, Bhaskar Ramasubramanian, Radha PoovendranarXiv 2022 · DOI · arXiv

Abstract

Traditional Trojan detection mechanisms often assume a static adversary, failing to account for intelligent attackers who adapt to detection strategies. This paper introduces a rigorous mathematical framework for Trojan attacks on machine learning models, demonstrating that an adaptive adversary can bypass state-of-the-art detectors with 100% certainty. By leveraging the property of submodularity, we develop an efficient algorithm to identify the minimum poisoning requirement—as low as 5%—to embed a successful backdoor. Furthermore, we model the attacker-detector interaction as a minimax game, proving that Trojaned models can be made mathematically indistinguishable from clean models.

Introduction

Trojan (or backdoor) attacks represent a significant security threat to the machine learning pipeline. In these scenarios, an adversary poisons a small fraction of the training dataset, ensuring the model behaves normally on clean data but executes a specific malicious behavior when triggered by a predefined pattern.

While defensive mechanisms like Meta-Neural Trojan Detection (MNTD) have shown promise, they typically operate under the assumption of a non-adaptive attacker. This research addresses the more critical threat of the intelligent adversary by answering two fundamental questions:

  1. What is the absolute minimum volume of poisoned samples required for a successful attack?
  2. Can a model be strategically trained to be mathematically indistinguishable from a clean one, thereby rendering statistical detectors obsolete?

Methodology

The proposed approach bifurcates the attack strategy into two distinct algorithmic components: the Submodular Trojan Algorithm for efficiency and the Min-Max (MM) Trojan Algorithm for stealth.

1. Submodular Trojan Algorithm

The researchers demonstrate that the adversary’s loss function possesses a submodular structure, characterized by the property of diminishing returns. This theoretical breakthrough simplifies a complex optimization problem into a computationally efficient greedy-like algorithm. This algorithm identifies the optimal poisoning ratio ($\alpha$)—the smallest fraction of data necessary to ensure the Trojan is successfully embedded without degrading the model's baseline performance on clean datasets.

2. Min-Max (MM) Trojan Algorithm

To achieve total evasion of detection, the interaction between the attacker and the detector is modeled as a two-player zero-sum game. In this framework:

  • The Attacker (Generator) seeks to minimize the detector's ability to differentiate between poisoned and clean models.
  • The Detector (Discriminator) seeks to maximize its classification accuracy.

The authors prove that at the Nash equilibrium of this game, the output probability distributions of the Trojaned and clean models become identical. This results in a "Fair Coin" state where the detector's performance is reduced to random chance.

Experimental Evaluation

The framework was evaluated across three standard image classification benchmarks using a simple 4x4 white square as the Trojan trigger:

  • MNIST: Handwritten digits (28x28 pixels).
  • CIFAR-10: General object classification (32x32 pixels).
  • EuroSAT: Satellite imagery for land use classification (64x64 pixels).

Key Results

Minimal Poisoning Footprint

By utilizing the Submodular Trojan algorithm, the adversary successfully embedded backdoors by poisoning only 3% to 5% of the training dataset. This minimal footprint significantly reduces the likelihood of detection via manual data inspection.

Performance and Evasion

The attack maintained high utility across all datasets. For instance, on the EuroSAT dataset, the Trojaned model achieved 97% accuracy on triggered samples while maintaining 85% accuracy on clean samples.

Most notably, the MM Trojan algorithm achieved a 100% evasion rate against state-of-the-art detectors. While baseline Trojan attacks were caught 100% of the time on MNIST and EuroSAT, the MM-optimized models forced the detector's output probability to exactly 0.5, effectively rendering the detection mechanism useless.

Discussion and Limitations

While the results demonstrate a potent threat, several constraints remain for future exploration:

  • Information Symmetry: The current model assumes the adversary has knowledge of the detector's statistical parameters (e.g., mean and standard deviation). Future research should investigate the efficacy of these attacks in limited-information or "gray-box" settings.
  • Detection Depth: This study focuses on detectors with black-box access to model outputs. If a detector were capable of inspecting the internal latent representations or intermediate layers of the neural network, maintaining invisibility might require more complex adversarial constraints.
  • Sample Prioritization: The current approach treats all training samples as equally viable for poisoning. Future work could involve ranking samples to identify "critical instances" that maximize the impact on the loss function with even fewer poisoned points.

Conclusion

This research highlights a critical vulnerability in current machine learning security paradigms. By framing Trojan attacks through the lenses of submodularity and game theory, we demonstrate that an adaptive attacker can achieve high success rates with minimal data manipulation and zero detectability. These findings underscore the need for more robust, adaptive defense mechanisms that go beyond simple statistical distribution checks.

Summary updated

Abstract

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.
BibTeX
@misc{sahabandu2022game,
  author = {Dinuka Sahabandu and Arezoo Rajabi and Luyao Niu and Bo Li and Bhaskar Ramasubramanian and Radha Poovendran},
  title = {{Game of Trojans: A Submodular Byzantine Approach}},
  year = {2022},
  eprint = {2207.05937},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.05937},
}
Figure