Towards Robustness Certification Against Universal Perturbations

Yi Zeng, Zhouxing Shi, Ming Jin, Feiyang Kang, Lingjuan Lyu, Cho-Jui Hsieh, Ruoxi JiaICLR 2023 · OpenReview

The Threat of Universal Perturbations

In the realm of AI security, adversarial attacks typically involve tweaking a specific image to fool a neural network. However, a more systemic vulnerability exists: Universal Perturbations (UPs). These are single, static noise patterns—such as Universal Adversarial Perturbations (UAPs) or backdoor triggers—that can cause a model to misclassify almost any image from a dataset.

To defend against these threats, researchers rely on certification, which provides a mathematical guarantee that no perturbation within a specific limit (like an $\ell_\infty$ norm ball) will degrade the model's accuracy below a certain threshold. Unfortunately, existing certification tools are "sample-wise." They assume an attacker can craft a unique noise pattern for every single image. By ignoring the constraint that a UP must be the same across all images, these methods produce overly conservative, "loose" bounds, making models appear much more vulnerable to universal threats than they actually are.

A Novel Framework for Universal Certification

To bridge this gap, researchers have developed the first framework to formally certify a neural network's robustness specifically against Universal Perturbations. The proposed method operates in two main stages:

  1. Linear Relaxation (LiRPA): The framework uses automated linear relaxation techniques to bound the neural network's complex, non-linear activations into linear functions. This creates a linear lower bound of the classification "margin" relative to the perturbation $\delta$.
  2. Mixed Integer Linear Programming (MILP): Instead of solving for the worst-case $\delta$ per image, these linear bounds are fed into an MILP solver. The solver searches for a single, shared $\delta$ that minimizes total accuracy across a batch of samples. This shared constraint is the key innovation, yielding significantly tighter and more accurate certification bounds.

Furthermore, the authors address the challenge of generalization. Because certification is computationally limited to a finite batch of data, they introduce a theoretical framework using Bennett’s inequality. This allows them to estimate the "Actual Robust Probability" (ARP) of the entire data distribution based on the "Certified Robust Rate" (CRR) computed from a random batch.

Key Findings and Results

The framework was evaluated on benchmark datasets, including MNIST and CIFAR-10, across various architectures (e.g., Conv-nets, ResNets) and training regimes (natural, PGD-based adversarial training, and Interval Bound Propagation).

Superior Tightness and the "Shared" Constraint By forcing the optimizer to find one universal $\delta$, the certified accuracy bounds become significantly tighter than sample-wise baselines. In some MNIST evaluations, accounting for the universal nature of the threat boosted the certified robust rate from roughly 52% to 63%.

Certified Robust Rate across datasets and training methods

Effectiveness of Robust Training Models trained with Interval Bound Propagation (IBP) demonstrated the highest levels of certified universal robustness. Conversely, naturally trained models often saw their certified robustness drop to near zero under similar perturbation radii. The authors also noted a trade-off between model size and robustness: while larger models often achieve higher empirical accuracy, their certified robustness can be lower due to looser certification bounds in highly complex networks.

Validating Against State-of-the-Art Attacks To ensure the reliability of their bounds, the authors tested the framework against state-of-the-art UAP attacks like Adv-UAP and DF-UAP.

Validation of CRR against empirical UAP attacks

In all test cases, the certified CRR acted as a true lower bound. The actual attack accuracy always remained higher than the certified minimum, proving the mathematical soundness of the framework.

Detecting Hidden Backdoors Beyond standard robustness, the framework offers a clever application for backdoor detection. By combining certification with adversarial training, the authors discovered that targeted backdoor classes exhibit uniquely high certified robustness compared to clean classes. This anomaly allows defenders to reliably identify an attacker's intended target class.

Limitations and Future Directions

While a significant leap forward, the framework has limitations:

  • Computational Scalability: The MILP formulation scales with the batch size and number of classes, making massive datasets like ImageNet challenging to certify.
  • Norm Constraints: The current method is optimized for $\ell_\infty$-norm bounded perturbations and does not yet account for unconstrained attacks or large geometric transformations.
  • Dependency on Linear Bounds: The final tightness is limited by the quality of the initial LiRPA relaxation. If the linear bounds are too loose, the MILP solver's effectiveness is constrained.

Future work will likely focus on scaling these techniques to larger models and exploring more complex perturbation threat models, continuing the push toward provably secure AI systems.

Summary updated

Abstract

In this paper, we investigate the problem of certifying neural network robustness against universal perturbations (UPs), which have been widely used in universal adversarial attacks and backdoor attacks. Existing robustness certification methods aim to provide robustness guarantees for each sample with respect to the worst-case perturbations given a neural network. However, those sample-wise bounds will be loose when considering the UP threat model as they overlook the important constraint that the perturbation should be shared across all samples. We propose a method based on a combination of linear relaxation-based perturbation analysis and Mixed Integer Linear Programming to establish the first robust certification method for UP. In addition, we develop a theoretical framework for computing error bounds on the entire population using the certification results from a randomly sampled batch. Aside from an extensive evaluation of the proposed certification, we further show how the certification facilitates efficient comparison of robustness among different models or efficacy among different universal adversarial attack defenses and enables accurate detection of backdoor target classes.
BibTeX
@inproceedings{zeng2023towards,
  author = {Yi Zeng and Zhouxing Shi and Ming Jin and Feiyang Kang and Lingjuan Lyu and Cho-Jui Hsieh and Ruoxi Jia},
  title = {{Towards Robustness Certification Against Universal Perturbations}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=7GEvPKxjtt},
}
Figure