TL;DR
This paper introduces a novel block-sparse optimization framework to "reverse engineer" adversarial attacks on deep neural networks. By modeling both the clean signal and the attack as block-sparse representations, the authors can simultaneously identify the attack type ($\ell_1, \ell_2, \ell_\infty$) and recover the original clean image, offering theoretical guarantees for this process.
What Problem Does This Paper Address?
Deep neural networks are vulnerable to adversarial attacks, where imperceptible perturbations to input data can lead to misclassifications. While many defense mechanisms have been proposed, they often fall prey to new, more sophisticated attacks, creating a perpetual "cat and mouse" game. This paper tackles a related, yet distinct problem: instead of solely defending against attacks, it aims to understand and reverse them. Given an attacked signal, the goal is to determine the type of $\ell_p$ attack used (specifically $\ell_1, \ell_2, \ell_\infty$) and to reconstruct the original, clean signal. This is challenging because many different attack-signal pairs could result in the same corrupted signal.
Methods
The core of the proposed method is a structured block-sparse recovery framework. The authors make three key assumptions:
- Additive Attacks: The attacked signal $x'$ is the sum of a clean signal $x$ and an $\ell_p$-norm bounded attack $\delta$ ($x' = x + \delta$).
- Block-Sparse Signals: The clean signal $x$ can be represented as a block-sparse combination of signals from a dictionary $D_s$, where blocks of $D_s$ correspond to different classes. This means $x$ is sparse across blocks, but not necessarily within blocks.
- Block-Sparse Attacks: The adversarial attack $\delta$ also admits a block-sparse representation in a dictionary $D_a$, where blocks of $D_a$ correspond to different $\ell_p$ attack types.
The problem is then formulated as a convex optimization problem that minimizes the $\ell_1/\ell_2$ norm of the coefficients for both the signal ($c_s$) and the attack ($c_a$), subject to reconstructing the observed attacked signal $x'$: $$ \min \|c_s\|_{1,2} + \|c_a\|_{1,2} \quad \text{s.t.} \quad x' = D_s c_s + D_a c_a $$ The paper derives geometric conditions on the dictionaries $D_s$ and $D_a$ that guarantee the correct recovery of the signal and attack classes. To efficiently solve this optimization problem, especially with large dictionaries, they develop an active-set homotopy algorithm. This algorithm iteratively refines the set of active (non-zero) blocks in the dictionaries, significantly reducing computational cost.
Datasets
The authors evaluate their approach on two standard datasets:
- Extended YaleB Face Dataset: Used for face classification.
- MNIST Dataset: Used for digit classification.
Key Insights and Ideas
- Unified Framework for Attack and Signal Recovery: The paper elegantly unifies the problem of identifying the attack type and recovering the clean signal within a single block-sparse optimization framework. This is a significant departure from methods that focus solely on detection or defense.
- Geometric Conditions for Recovery: The theoretical analysis provides concrete geometric conditions (based on covering radii and angular distances) that guarantee the successful recovery of the signal and attack classes. This moves beyond empirical results to offer theoretical assurances.
- Block-Sparse Model for Attacks: The assumption that adversarial attacks themselves can be modeled as block-sparse representations is a novel and powerful idea. It allows for the classification of attack types based on their structure.
- Active-Set Homotopy for Efficiency: The development of an efficient active-set homotopy algorithm is crucial for making the block-sparse optimization practical for real-world applications with large dictionaries.
Key Results
- YaleB Face Dataset: The proposed Structured Block-Sparse Classifier (SBSC) significantly improves adversarial accuracy over the undefended model, achieving around 96.3% accuracy. The SBSC+CNN (denoised) model also performs well, reaching 91% accuracy. The Structured Block-Sparse Attack Detector (SBSAD) achieves 55.7% accuracy in identifying the attack type.
- MNIST Dataset: The SBSC method shows remarkable robustness to $\ell_p$ perturbations, outperforming state-of-the-art adversarial training defenses by about 15% on average. The SBSC+CNN denoiser also demonstrates strong performance. Notably, the SBSAD achieves high attack classification accuracy (e.g., 76.83% for $\ell_\infty$ PGD attacks), indicating the effectiveness of modeling attacks as linear combinations of PGD attacks.
- Qualitative Results: Figure 2 shows that the SBSC+CNN method can effectively denoise images perturbed by various $\ell_p$ attacks, allowing the CNN classifier to correctly identify the digit.
Limitations and Future Work
- Computational Cost: While the active-set homotopy algorithm improves efficiency, solving the block-sparse optimization problem can still be computationally expensive, especially for very large dictionaries.
- Assumptions: The method relies on the assumption that both the clean signal and the attack can be well-represented by block-sparse models with appropriate dictionaries. The effectiveness might depend on the quality and suitability of these dictionaries.
- Future Work: The authors suggest exploring non-linear embedding dictionaries and further investigating the properties of block-sparse classifiers. They also mention the potential for extending the framework to more complex attack models.
Summary updated