Reverse Engineering 𝓁p attacks: A block-sparse optimization approach with recovery guarantees

Darshan Thaker, Paris Giampouras, René Vidal

TL;DR

This paper tackles the challenge of understanding and reversing adversarial attacks on deep neural networks. By framing the problem as a structured block-sparse recovery task, the authors develop a method to simultaneously identify the type of $\ell_p$ attack (e.g., $\ell_1, \ell_2, \ell_\infty$) and recover the original, clean data. This approach offers theoretical guarantees for successful recovery and demonstrates strong empirical performance on image classification tasks.

What Problem Does This Paper Address?

Deep neural networks (DNNs) are susceptible to adversarial attacks, where small, imperceptible perturbations to input data can cause misclassifications. While much research focuses on defending against these attacks, this paper addresses a related but distinct problem: reverse engineering them. Given an attacked data point, the goal is not just to classify it correctly but to also determine what kind of attack was used (e.g., $\ell_1$, $\ell_2$, or $\ell_\infty$ bounded perturbation) and to recover the original, uncorrupted data. This is challenging because many different clean data points and attack vectors could result in the same observed attacked data point. The paper aims to find conditions and methods to uniquely identify the original signal and the attack type.

Methods

The core of the paper's methodology lies in framing the problem as a structured block-sparse recovery task. The key assumptions are:

  1. Additive Attacks: The attacked signal $x'$ is the sum of a clean signal $x$ and an attack $\delta$ ($x' = x + \delta$).
  2. Block-Sparse Signal: The clean signal $x$ can be represented as a block-sparse combination of signals from a dictionary $D_s$. This dictionary is structured such that different blocks correspond to different classes, and the signal's coefficients are sparse across these blocks.
  3. Block-Sparse Attack: The attack $\delta$ can also be represented as a block-sparse combination of vectors from an attack dictionary $D_a$. This dictionary is structured to include blocks corresponding to different $\ell_p$ attack types and potentially different classes.

Based on these assumptions, the problem of recovering the clean signal and identifying the attack type is formulated as a convex optimization problem: minimizing the $\ell_1/\ell_2$ norm of the coefficients for both the signal and the attack. The paper also proposes an active set homotopy algorithm to efficiently solve this optimization problem, especially when the dictionaries are large. Theoretical guarantees for the recovery of the correct signal class and attack type are derived based on geometric conditions related to the dictionaries.

Datasets

The paper evaluates its proposed method on two standard datasets:

  • Extended YaleB Face Dataset: Used for face classification.
  • MNIST Dataset: Used for digit classification.

The authors do not introduce new benchmark datasets but rather apply their method to existing ones to demonstrate its effectiveness.

Key Insights and Ideas

  • Unified Framework for Attack and Signal Recovery: The paper elegantly unifies the problem of recovering the clean signal and identifying the attack type into a single block-sparse optimization framework. This is a significant departure from methods that might focus on one aspect or the other.
  • Structured Dictionaries are Key: The success of the approach hinges on structuring the dictionaries ($D_s$ for signals, $D_a$ for attacks) such that blocks correspond to classes and attack types. This structure allows the optimization to disentangle the signal and attack components.
  • Geometric Conditions for Guarantees: The theoretical analysis provides geometrically interpretable conditions (related to covering radii and angular distances of dictionary atoms) under which the recovery is guaranteed to be successful. This moves beyond purely algorithmic descriptions to provide theoretical underpinnings.
  • Trade-off Between Attack Detection and Signal Classification: For $\ell_\infty$ attacks on MNIST, the paper observes an interesting trade-off: as the attack strength increases, it becomes easier to detect the attack type, but harder to classify the original signal correctly. This highlights the complex interplay between attack characteristics and classification performance.

Key Results

  • High Accuracy on YaleB: For the YaleB face dataset, the proposed SBSC (Structured Block-Sparse Classifier) and SBSC+CNN (denoiser) methods achieve high accuracies (e.g., 96.3% for SBSC+CNN on average across attack types), significantly outperforming naive block-sparse classifiers (BSC) and even the undefended CNN.
  • Robustness on MNIST: On the MNIST dataset, the SBSC approach shows considerable robustness to $\ell_p$ attacks, achieving accuracies around 82.82% for signal classification and 51.93% for attack detection on average, outperforming various adversarial training baselines.
  • Effective Attack Detection: The SBSAD (Structured Block-Sparse Attack Detector) component of the method demonstrates strong performance in identifying the type of $\ell_p$ attack applied.
  • Theoretical Guarantees: The paper provides theoretical conditions under which the clean signal and attack type can be recovered, offering a formal guarantee for the proposed method.

Limitations and Future Work

  • Computational Cost: Solving the block-sparse optimization problem can be computationally expensive, especially for large dictionaries. The paper addresses this with an active set homotopy algorithm, but it remains a practical consideration.
  • Assumptions on Network Linearity: The theoretical analysis for the validity of the attack model relies on assumptions about the network's local linearity (e.g., ReLU networks). Extending these guarantees to more complex network architectures might be challenging.
  • Future Directions: The authors suggest exploring non-linear embedding dictionaries and further investigating the properties of block-sparse classifiers. They also mention the potential for this framework to be extended to other types of adversarial perturbations beyond $\ell_p$ norms.

Summary updated

Abstract

Deep neural network-based classifiers have been shown to be vulnerable to imperceptible perturbations to their input, such as $\ell_p$-bounded norm adversarial attacks. This has motivated the development of many defense methods, which are then broken by new attacks, and so on. This paper focuses on a different but related problem of reverse engineering adversarial attacks. Specifically, given an attacked signal, we study conditions under which one can determine the type of attack ($\ell_1$, $\ell_2$ or $\ell_\infty$) and recover the clean signal. We pose this problem as a block-sparse recovery problem, where both the signal and the attack are assumed to lie in a union of subspaces that includes one subspace per class and one subspace per attack type. We derive geometric conditions on the subspaces under which any attacked signal can be decomposed as the sum of a clean signal plus an attack. In addition, by determining the subspaces that contain the signal and the attack, we can also classify the signal and determine the attack type. Experiments on digit and face classification demonstrate the effectiveness of the proposed approach.
BibTeX
@inproceedings{thaker2022reverse,
  author = {Darshan Thaker and Paris Giampouras and René Vidal},
  title = {{Reverse Engineering 𝓁p attacks: A block-sparse optimization approach with recovery guarantees}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
}
Figure