Enhancing Gradient-based Attacks with Symbolic Intervals

Shiqi Wang, Yizheng Chen, Ahmed Abdou, Suman JanaarXiv 2019 · arXiv

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.

Comparison of PGD and Interval attacks: PGD gets stuck at a local optimum (g=0), while the interval attack uses a broader view (g_I) to find the violation l2.
  1. 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.
  2. 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.
  3. 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

Abstract

Recent breakthroughs in defenses against adversarial examples, like adversarial training, make the neural networks robust against various classes of attackers (e.g., first-order gradient-based attacks). However, it is an open question whether the adversarially trained networks are truly robust under unknown attacks. In this paper, we present interval attacks, a new technique to find adversarial examples to evaluate the robustness of neural networks. Interval attacks leverage symbolic interval propagation, a bound propagation technique that can exploit a broader view around the current input to locate promising areas containing adversarial instances, which in turn can be searched with existing gradient-guided attacks. We can obtain such a broader view using sound bound propagation methods to track and over-approximate the errors of the network within given input ranges. Our results show that, on state-of-the-art adversarially trained networks, interval attack can find on average 47% relatively more violations than the state-of-the-art gradient-guided PGD attack.
BibTeX
@misc{wang2019enhancing,
  author = {Shiqi Wang and Yizheng Chen and Ahmed Abdou and Suman Jana},
  title = {{Enhancing Gradient-based Attacks with Symbolic Intervals}},
  year = {2019},
  eprint = {1906.02282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.02282},
}
Figure