Abstract
This paper introduces interval attacks, a novel framework that combines sound bound propagation with traditional gradient-based methods to break "robust" neural networks. By leveraging symbolic interval analysis to gain a "broader view" of the loss landscape, the authors demonstrate that current state-of-the-art defenses are significantly more vulnerable than previously believed, finding up to 61% more adversarial violations than the standard PGD attack.
Introduction
In the field of adversarial machine learning, Projected Gradient Descent (PGD) has long been considered the gold standard for first-order attacks. It was widely believed that a model capable of resisting PGD possessed a high degree of true robustness. However, this paper argues that such a belief provides a false sense of security.
The primary limitation of PGD lies in the highly non-convex nature of neural network loss landscapes. Standard gradient-based attacks rely on local gradients, which provide only a narrow view of the immediate surroundings. Consequently, these attacks often become trapped in local optima, failing to identify adversarial examples that exist just beyond their immediate search trajectory. This research introduces a "wider lens" to uncover vulnerabilities that PGD overlooks.
Methodology: The Interval Attack
The authors propose a two-step approach termed the Interval Attack, which integrates symbolic interval analysis into the search process to overcome local minima.
- Symbolic Interval Propagation: Instead of evaluating a single point, the attack employs sound bound propagation. This technique calculates an over-approximation of the network's output for an entire range of inputs, producing two parallel linear equations ($Eq_{up}$ and $Eq_{low}$) that bound the output.
- Interval Gradient ($g_I$): A new type of gradient is derived from these symbolic bounds. This $g_I$ represents the slope of the bounding lines, offering a "broader view" of the surrounding landscape.
- Hybrid Search: The algorithm utilizes the interval gradient to navigate toward "promising sub-areas" likely to contain violations. Once a candidate region is identified, it switches to a standard gradient-based attack (like PGD) to pinpoint the exact adversarial instance.
To maintain accuracy, the attack dynamically adjusts the input range ($\epsilon_0$) during the search to prevent the over-approximation from becoming too loose or noisy.
Experimental Evaluation
The attack was evaluated on the MNIST dataset across three distinct architectures, all adversarially trained using PGD to represent state-of-the-art defenses:
- MNIST_FC1: A two-layer fully connected network.
- MNIST_FC2: A five-layer fully connected network.
- MNIST_Conv: A convolutional neural network from the MadryLab MNIST Challenge, previously considered one of the most robust models available.
Results and Discussion
The interval attack consistently outperformed both PGD and Carlini-Wagner (CW) attacks. Key findings include:
- Increased Success Rate: The interval attack identified 47% more violations than PGD on average.
- Breaking Robust Models: On the MadryLab MNIST Challenge model, the interval attack increased the success rate from 7.2% (PGD) to 11.6%, a 61% relative improvement.
- Deeper Vulnerabilities: While PGD-found losses were typically low (0 to 1), interval attacks uncovered violations with significantly higher loss values (up to 7), indicating deep vulnerabilities in supposedly robust models.
The "broad view" advantage is central to these results. While standard gradients might lead to a local dead-end where $g=0$, the interval gradient $g_I$ captures the trend of the entire neighborhood, allowing the attacker to bypass local optima.
Conclusion
While highly effective, interval attacks face challenges regarding computational overhead. Symbolic interval analysis is expensive; training models using this method is approximately 47 times slower than PGD-based training. Furthermore, scaling to larger datasets like ImageNet remains a future research direction. Ultimately, the authors suggest that the field should shift focus from iterative adversarial training toward verifiably robust training methods that offer mathematical guarantees of safety.
Summary updated