BOSS: Bidirectional One-Shot Synthesis of Adversarial Examples

Ismail Alkhouri, Alvaro Velasquez, George K. Atia

TL;DR

This paper introduces BOSS, a novel framework for generating adversarial examples with a single reference input, satisfying both input similarity and desired output constraints. They prove this "Bidirectional One-Shot Synthesis" problem is NP-complete and propose a generative approach that achieves state-of-the-art results in targeted and confidence reduction attacks.

What Problem Does This Paper Address?

Adversarial machine learning often focuses on creating slightly perturbed versions of input data that fool a classifier. Traditional methods either add small, imperceptible noise (additive attacks) or use generative models like GANs, which typically require vast amounts of training data. This paper addresses the gap of generating adversarial examples efficiently, specifically when only a single reference data point is available. The challenge is to create a new data point that is structurally similar to the original and forces the classifier to produce a specific, desired output (e.g., misclassify it as a particular class or reduce its confidence). This is termed the "Bidirectional One-Shot Synthesis" (BOSS) problem.

Methods

The core of the BOSS framework is a generative approach. They leverage a generative network (like a GAN generator) to produce adversarial examples. The key innovation is training this generator not just to mimic the input distribution but to simultaneously satisfy two constraints:

  1. Input Similarity: The generated example ($x$) should be structurally close to the reference example ($x_d$), measured by a distance metric like Structural Similarity Index (SSIM).
  2. Output Specification: The classifier's prediction for the generated example ($p(x; \theta)$) should closely match a user-defined target distribution ($p_d$), measured by a distance metric like Jensen-Shannon divergence.

This is framed as an optimization problem where a combined loss function, balancing input and output objectives, is minimized using backpropagation. A dynamic weighting parameter ($\lambda$) is introduced to adjust the importance of each loss term during training, preventing premature convergence on one objective. The authors also prove that the general BOSS problem is NP-complete, suggesting that finding exact solutions is computationally intractable, thus motivating their approximate generative approach.

Datasets

The paper evaluates BOSS on several standard datasets:

  • MNIST digits
  • MNIST fashion
  • CIFAR-10
  • GTSRB (German Traffic Sign Recognition Benchmark)
  • ImageNet

Key Insights and Ideas

  • One-Shot Synthesis is Possible: The paper demonstrates that generating effective adversarial examples can be done with just one reference data point, significantly reducing data requirements compared to traditional GAN-based methods.
  • Bidirectional Constraints are Key: The novelty lies in simultaneously controlling both the input's appearance and the classifier's output. This allows for more nuanced attacks beyond simple misclassification.
  • NP-Completeness Implies Approximation: Proving BOSS is NP-complete highlights the inherent difficulty of the problem and justifies the use of generative models for finding practical, albeit approximate, solutions.
  • Dynamic Weighting for Robust Training: The adaptive $\lambda$ parameter is crucial for balancing the input and output objectives, ensuring the generator doesn't get stuck optimizing only one aspect.

Key Results

  • Targeted Attacks (BOSS-T): Achieved high attack success rates (close to 100%) on CIFAR-10, often outperforming state-of-the-art methods like CW and EAD in terms of adversarial confidence while maintaining competitive imperceptibility. BOSS-T also demonstrated significantly faster runtimes compared to some baselines.
  • Confidence Reduction Attacks (BOSS-C): Successfully reduced the average confidence of a classifier on the true label to around 67% (from 99.1% original) with high similarity to the original images.
  • Qualitative Results: The paper provides compelling visual examples of synthesized adversarial images for various datasets, showcasing BOSS's ability to generate inputs that are visually similar to the originals but trigger desired misclassifications or confidence drops.

Limitations and Future Work

  • NP-Completeness: The theoretical NP-completeness of the BOSS problem implies that finding optimal solutions is computationally infeasible for large-scale problems. The proposed generative approach is an approximation.
  • White-Box Setting: The current implementation assumes a "white-box" setting, meaning the attacker has full knowledge of the classifier's architecture and parameters. Extending this to "black-box" scenarios would be a valuable future direction.
  • Dataset and Model Specificity: While evaluated on multiple datasets and architectures, further exploration of BOSS's performance across a wider range of models and data modalities could be beneficial.
  • Perceptual Similarity: While SSIM is used, exploring other perceptual similarity metrics could lead to even more imperceptible adversarial examples.

Summary updated

Abstract

The design of additive imperceptible perturbations to the inputs of deep classifiers to maximize their misclassification rates is a central focus of adversarial machine learning. An alternative approach is to synthesize adversarial examples from scratch using GAN-like structures, albeit with the use of large amounts of training data. By contrast, this paper considers one-shot synthesis of adversarial examples; the inputs are synthesized from scratch to induce arbitrary soft predictions at the output of pre-trained models, while simultaneously maintaining high similarity to specified inputs. To this end, we present a problem that encodes objectives on the distance between the desired and output distributions of the trained model and the similarity between such inputs and the synthesized examples. We prove that the formulated problem is NP-complete. Then, we advance a generative approach to the solution in which the adversarial examples are obtained as the output of a generative network whose parameters are iteratively updated by optimizing surrogate loss functions for the dual-objective. We demonstrate the generality and versatility of the framework and approach proposed through applications to the design of targeted adversarial attacks, generation of decision boundary samples, and synthesis of low confidence classification inputs. The approach is further extended to an ensemble of models with different soft output specifications. The experimental results verify that the targeted and confidence reduction attack methods developed perform on par with state-of-the-art algorithms.
BibTeX
@inproceedings{alkhouri2021boss,
  author = {Ismail Alkhouri and Alvaro Velasquez and George K. Atia},
  title = {{BOSS: Bidirectional One-Shot Synthesis of Adversarial Examples}},
  booktitle = {MLSP},
  year = {2021},
  url = {https://openreview.net/forum?id=-S2PVzC3uuX},
}
Figure