A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks

Huan Zhang, Shiqi Wang, Kaidi Xu, Yihan Wang, Suman Jana, Cho-Jui Hsieh, J Zico KolterICLR 2022 · OpenReview

This mini-paper explores the framework presented in "A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks," originally published at ICML 2022.

TL;DR

BaB-Attack is a novel framework that searches for adversarial examples in the activation space of a neural network rather than the traditional input space. By combining Branch and Bound (BaB) with GPU-accelerated verification techniques, it successfully finds "hard" adversarial examples that gradient-based attacks miss, outperforming standard optimization solvers in both speed and success rate.

The Challenge of Evaluating True Robustness

To test if a neural network is truly robust, researchers use adversarial attacks—small, intentional perturbations to an input designed to make the model fail.

Most common attacks, like Projected Gradient Descent (PGD) or AutoAttack, operate in the input space. They use gradients to "nudge" pixels until the model misclassifies the image. However, because neural networks are highly non-convex, these gradient-based methods often get stuck in local minima. This creates a "false sense of security": a model might appear robust simply because the attack wasn't sophisticated enough to find the failure point.

An alternative approach is to use Mixed-Integer Programming (MIP), which treats the network’s ReLU activations as discrete "on/off" switches. This allows for a systematic, global search of the activation space. While theoretically perfect, standard MIP solvers (like Gurobi) are notoriously slow, run only on CPUs, and fail to exploit the specific structure of neural networks, making them impractical for anything but the smallest models.

The BaB-Attack Methodology

The authors introduce BaB-Attack, bridging the gap between fast-but-unreliable gradient attacks and slow-but-exact MIP solvers.

Overview of the BaB-Attack framework architecture.

Their approach includes several novel components designed to optimize the search process:

  • GPU-Accelerated Bound Propagation: Instead of using generic solvers, the framework leverages $\alpha,\beta$-CROWN—a state-of-the-art neural network verifier. This allows the system to use GPUs to quickly calculate tight lower bounds for different regions of the activation space.
  • Adversarial Candidates Pool: The framework maintains a "pool" of near-misses generated by cheap attacks (like PGD with random starts). It uses the patterns in these candidates to guide the deeper search.

To navigate the complex activation space, BaB-Attack employs three distinct search strategies:

Illustration of the search strategies: Beam Search, Diving, and Local Search.
  • Top-Down Beam Search: Standard verifiers usually try to prove a model is safe by looking at the "worst" regions first. BaB-Attack flips this logic: it uses a beam search to quickly "dive" into the most promising regions likely to contain a successful adversarial example.
  • Diving: Borrowing from discrete optimization, the authors use "diving" to fix certain neuron states based on common patterns found in the candidate pool.
  • Large Neighborhood Search (LNS): The framework also uses LNS to perform a "bottom-up" local search around known candidates to refine and find even better adversarial perturbations.

Key Insights and Ideas

  • Flipping the Script on Verification: Usually, Branch and Bound is used for verification (proving no attack exists). This paper realizes that the same machinery, if guided by different heuristics (like beam search), is incredibly effective at finding attacks.
  • Activation Space is More Structured: Searching the discrete "on/off" configurations of ReLU neurons is often more efficient than searching the high-dimensional, continuous space of image pixels.
  • Domain-Specific Solvers Win: Generic solvers like Gurobi are "blind" to the fact that they are solving a neural network. By using bound propagation methods designed specifically for NNs, BaB-Attack achieves massive speedups.

Experimental Results

The researchers evaluated their framework on 10,000 test examples from MNIST and CIFAR-10, testing 8 different models ranging from small networks to larger ResNets (including models trained with certified defense methods).

The authors focused specifically on "hard instances"—images where standard strong attacks (MT-PGD, ODS-PGD, and AutoAttack) all failed, and standard verifiers couldn't prove the model was safe.

  • Higher Success Rate: On the MNIST "Model B" hard instances, BaB-Attack found 32 adversarial examples where the Gurobi-based MIP attack only found 20.
  • Massive Speedup: BaB-Attack was consistently about 10x faster than using an off-the-shelf MIP solver. For example, on CIFAR Model F, it found nearly triple the number of adversarial examples in a fraction of the time.
  • Closing the Gap: By finding these hidden vulnerabilities, the authors significantly reduced the gap between "attack accuracy" and "verified accuracy," providing a much more precise picture of true model robustness.

Limitations and Future Work

While highly effective, the framework has a few limitations:

  • Computational Cost: While much faster than Gurobi, BaB-Attack is still significantly more expensive than PGD (taking minutes rather than seconds). It is intended as a "last resort" for high-stakes robustness evaluation rather than a routine training-time attack.
  • White-Box Requirement: The method requires full access to the model's architecture and weights, making it unsuitable for attacking black-box APIs.
  • Model Architecture: The current framework is specialized for ReLU-based networks. Extending this to other activation functions (like Sigmoid or Swish) would require different bound propagation techniques.

Looking forward, the authors suggest that this framework could be integrated directly into the training loop to create even more robust "certified" models.

Summary updated

Abstract

Strong adversarial attacks are important for evaluating the true robustness of deep neural networks. Most existing attacks find adversarial examples via searching in the input space, e.g., using gradient descent. In this work, we formulate an adversarial attack using a branch-and-bound (BaB) procedure on ReLU neural networks and search adversarial examples in the activation space corresponding to binary variables in a mixed integer programming (MIP) formulation. This attack formulation can be used to tackle hard instances where none of the existing adversarial attacks can succeed. Existing attacks using this formulation rely on generic solvers which cannot exploit the structure of neural networks and also cannot utilize GPU acceleration, so they are mostly limited to small networks and easy problem instances. To improve its scalability and practicability, we propose a top-down beam-search approach to quickly identify the subspace that may contain adversarial examples. The search utilizes the bound propagation based neural network verifiers on GPUs to rapidly evaluate a large number of searching regions, which is not possible in generic MIP solvers. Moreover, we exploit the fact that good candidates of adversarial examples can be easily found via gradient based attacks, and build an adversarial candidates pool to further guide the search in activation space via diving techniques. Additionally, any candidate adversarial examples found during the process are refined using a bottom-up large neighbourhood search (LNS) guided by the candidates pool. Our adversarial attack framework, BaB-Attack, opens up a new opportunity for designing novel adversarial attacks not limited to searching the input space, and enables us to borrow techniques from integer programming theory and neural network verification to build stronger attacks. In experiments, we can successfully generate adversarial examples for hard input instances where existing strong adversarial attacks fail, and outperform off-the-shelf MIP solver based attacks in both success rates and efficiency. Our results further close the gap between the upper bound of robust accuracy obtained by attacks and the lower bound obtained by verification.
BibTeX
@inproceedings{zhang2022branch,
  author = {Huan Zhang and Shiqi Wang and Kaidi Xu and Yihan Wang and Suman Jana and Cho-Jui Hsieh and J Zico Kolter},
  title = {{A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=oxwsctgY5da},
}
Figure