Adversarially Robust Conformal Prediction

Asaf Gendler, Tsui-Wei Weng, Luca Daniel, Yaniv RomanoICLR 2022 · OpenReview

Overview

Conformal prediction is a powerful, model-agnostic tool for uncertainty quantification, but it fundamentally breaks down when an adversary intentionally perturbs data to fool a model. This paper introduces Randomly Smoothed Conformal Prediction (RSCP), a framework that combines randomized smoothing with conformal inference to produce prediction sets with provable coverage guarantees, even under $\ell_2$-norm bounded adversarial attacks.

The Vulnerability of Standard Conformal Prediction

Deep learning models are notoriously brittle; small, human-imperceptible perturbations—known as adversarial attacks—can cause them to make confident yet incorrect predictions. To manage prediction risk, researchers often use Conformal Prediction (CP). Instead of outputting a single guess, CP generates a set of possible labels, mathematically guaranteeing that the true label is included in that set with a user-defined probability (e.g., 90%).

However, CP relies heavily on the "exchangeability" assumption: the data the model sees at test time must come from the same distribution as the calibration data. Adversarial attacks explicitly violate this assumption. As a result, a "vanilla" conformal set designed for 90% coverage can see its reliability plummet drastically when under attack. This paper tackles the challenge of restoring those mathematical guarantees in the presence of malicious actors.

Randomly Smoothed Conformal Prediction (RSCP)

To counter adversarial perturbations, the authors propose RSCP. The core innovation lies in how the method calculates the "non-conformity score"—a measure of how unusual a data point is relative to the training set—and adjusts the decision threshold.

Illustration of threshold inflation in RSCP
  1. Randomized Smoothing: Instead of scoring a single image, RSCP adds Gaussian noise to the input multiple times and averages the model's scores across these noisy versions.
  2. Lipschitz Bounding: By smoothing the scoring function with Gaussian noise, the authors can mathematically bound its Lipschitz constant. This allows them to calculate the maximum possible change an adversarial perturbation of a certain size ($\delta$) could induce on the score.
  3. Threshold Inflation: In standard CP, a threshold is chosen based on calibration data. In RSCP, this threshold is "inflated" by a factor that accounts for the worst-case score shift an adversary could cause.
  4. Model Agnosticism: The framework is plug-and-play. It can wrap around any pre-existing classifier and works with various scoring functions, such as Hinged Prediction Sets (HPS) or Adaptive Prediction Sets (APS).

Key Insights and Results

The authors evaluated RSCP on gold-standard image classification benchmarks (CIFAR10, CIFAR100, and ImageNet) using standard architectures like ResNet and DenseNet.

Marginal coverage comparison showing Vanilla CP failing under attack, while RSCP maintains the nominal level.
  • Reliability Restored: In experiments on CIFAR10, Vanilla CP coverage dropped to roughly 45% under attack. RSCP successfully maintained the nominal 90% coverage guarantee.
  • The Price of Robustness: To maintain a 90% coverage guarantee under attack, the prediction sets naturally become larger. This reflects the inherent uncertainty introduced by the adversary; if the input is corrupted by an attack, the model must provide more options to guarantee the true label is included.
  • Provable Safety: Unlike empirical defenses that are often broken by stronger, adaptive attacks, RSCP provides a finite-sample coverage guarantee. As long as the attack's magnitude is within the specified $\ell_2$ bound, the coverage holds regardless of the attack algorithm.
  • Computational Feasibility: While randomized smoothing requires multiple forward passes (Monte Carlo sampling), the authors implemented a batch mode that makes inference time only 3-4x slower than vanilla CP—a reasonable trade-off for safety-critical applications.

Limitations and Future Work

While RSCP successfully bridges conformal prediction and adversarial robustness, some limitations remain. The current theory is specifically tailored for $\ell_2$-norm bounded attacks; extending this to $\ell_1$ or $\ell_\infty$ constraints is a vital next step. Additionally, the requirement for multiple noise realizations adds computational overhead. Finally, the authors note a small gap between the theoretical worst-case coverage and empirical results, suggesting that tighter mathematical bounds could yield even more efficient (smaller) prediction sets in the future.

Summary updated

Abstract

Conformal prediction is a model-agnostic tool for constructing prediction sets that are valid under the common i.i.d. assumption, which has been applied to quantify the prediction uncertainty of deep net classifiers. In this paper, we generalize this framework to the case where adversaries exist during inference time, under which the i.i.d. assumption is grossly violated. By combining conformal prediction with randomized smoothing, our proposed method forms a prediction set with finite-sample coverage guarantee that holds for any data distribution with $\ell_2$-norm bounded adversarial noise, generated by any adversarial attack algorithm. The core idea is to bound the Lipschitz constant of the non-conformity score by smoothing it with Gaussian noise and leverage this knowledge to account for the effect of the unknown adversarial perturbation. We demonstrate the necessity of our method in the adversarial setting and the validity of our theoretical guarantee on three widely used benchmark data sets: CIFAR10, CIFAR100, and ImageNet.
BibTeX
@inproceedings{gendler2022adversarially,
  author = {Asaf Gendler and Tsui-Wei Weng and Luca Daniel and Yaniv Romano},
  title = {{Adversarially Robust Conformal Prediction}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=9L1BsI4wP1H},
}
Figure