Provably Efficient and Robust Conformal Prediction under a Realistic Threat Model

Alberto Carlevaro, Luca Oneto, Davide Anguita, Fabio Roli
Proceedings of the Fourteenth Symposium on Conformal and Probabilistic Prediction with Applications, PMLR 266:113-132, 2025.

Abstract

Robust conformal prediction is a model-agnostic technique designed to construct predictive sets with guaranteed coverage, assuming data exchangeability, even under adversarial attacks. Two primary strategies have been explored to address vulnerabilities to these attacks. The first strategy employs randomization, which is computationally efficient but fails to provide formal performance guarantees without resulting in overly conservative predictive sets. The second strategy involves formal verification, which restores coverage guarantees but leads to excessively conservative predictive sets and prohibitive computational overhead. Indeed, verification generally becomes NP-hard as it attempts to cope with attacks that are practically impossible, rendering some security claims unfalsifiable. In this paper, we propose a novel, provably efficient robust conformal prediction method by clearly defining a realistic threat model. Specifically, we assume explicit knowledge of the set of potential adversarial attacks, aligning our approach with standard certification procedures designed to certify against specific, identified threats. We demonstrate that attacks targeting the model can effectively be reframed as attacks on the score function, allowing us to recalibrate the score quantile to account for these known attacks and thereby restore desired coverage guarantees. It is worth noting that our approach allows to easily incorporate unknown or emerging (zero-day) attacks upon discovery, thus reestablishing coverage guarantees. By avoiding computationally intensive verification and operating under realistic threat assumptions, our approach achieves both efficiency and provable robustness. Empirical evaluations on real-world classification datasets and comparisons with state-of-the-art methods support the effectiveness and practicality of our proposed solution.

Cite this Paper

BibTeX
@InProceedings{pmlr-v266-carlevaro25a, title = {Provably Efficient and Robust Conformal Prediction under a Realistic Threat Model}, author = {Carlevaro, Alberto and Oneto, Luca and Anguita, Davide and Roli, Fabio}, booktitle = {Proceedings of the Fourteenth Symposium on Conformal and Probabilistic Prediction with Applications}, pages = {113--132}, year = {2025}, editor = {Nguyen, Khuong An and Luo, Zhiyuan and Papadopoulos, Harris and Löfström, Tuwe and Carlsson, Lars and Boström, Henrik}, volume = {266}, series = {Proceedings of Machine Learning Research}, month = {10--12 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v266/main/assets/carlevaro25a/carlevaro25a.pdf}, url = {https://proceedings.mlr.press/v266/carlevaro25a.html}, abstract = {Robust conformal prediction is a model-agnostic technique designed to construct predictive sets with guaranteed coverage, assuming data exchangeability, even under adversarial attacks. Two primary strategies have been explored to address vulnerabilities to these attacks. The first strategy employs randomization, which is computationally efficient but fails to provide formal performance guarantees without resulting in overly conservative predictive sets. The second strategy involves formal verification, which restores coverage guarantees but leads to excessively conservative predictive sets and prohibitive computational overhead. Indeed, verification generally becomes NP-hard as it attempts to cope with attacks that are practically impossible, rendering some security claims unfalsifiable. In this paper, we propose a novel, provably efficient robust conformal prediction method by clearly defining a realistic threat model. Specifically, we assume explicit knowledge of the set of potential adversarial attacks, aligning our approach with standard certification procedures designed to certify against specific, identified threats. We demonstrate that attacks targeting the model can effectively be reframed as attacks on the score function, allowing us to recalibrate the score quantile to account for these known attacks and thereby restore desired coverage guarantees. It is worth noting that our approach allows to easily incorporate unknown or emerging (zero-day) attacks upon discovery, thus reestablishing coverage guarantees. By avoiding computationally intensive verification and operating under realistic threat assumptions, our approach achieves both efficiency and provable robustness. Empirical evaluations on real-world classification datasets and comparisons with state-of-the-art methods support the effectiveness and practicality of our proposed solution.} }
Endnote
%0 Conference Paper %T Provably Efficient and Robust Conformal Prediction under a Realistic Threat Model %A Alberto Carlevaro %A Luca Oneto %A Davide Anguita %A Fabio Roli %B Proceedings of the Fourteenth Symposium on Conformal and Probabilistic Prediction with Applications %C Proceedings of Machine Learning Research %D 2025 %E Khuong An Nguyen %E Zhiyuan Luo %E Harris Papadopoulos %E Tuwe Löfström %E Lars Carlsson %E Henrik Boström %F pmlr-v266-carlevaro25a %I PMLR %P 113--132 %U https://proceedings.mlr.press/v266/carlevaro25a.html %V 266 %X Robust conformal prediction is a model-agnostic technique designed to construct predictive sets with guaranteed coverage, assuming data exchangeability, even under adversarial attacks. Two primary strategies have been explored to address vulnerabilities to these attacks. The first strategy employs randomization, which is computationally efficient but fails to provide formal performance guarantees without resulting in overly conservative predictive sets. The second strategy involves formal verification, which restores coverage guarantees but leads to excessively conservative predictive sets and prohibitive computational overhead. Indeed, verification generally becomes NP-hard as it attempts to cope with attacks that are practically impossible, rendering some security claims unfalsifiable. In this paper, we propose a novel, provably efficient robust conformal prediction method by clearly defining a realistic threat model. Specifically, we assume explicit knowledge of the set of potential adversarial attacks, aligning our approach with standard certification procedures designed to certify against specific, identified threats. We demonstrate that attacks targeting the model can effectively be reframed as attacks on the score function, allowing us to recalibrate the score quantile to account for these known attacks and thereby restore desired coverage guarantees. It is worth noting that our approach allows to easily incorporate unknown or emerging (zero-day) attacks upon discovery, thus reestablishing coverage guarantees. By avoiding computationally intensive verification and operating under realistic threat assumptions, our approach achieves both efficiency and provable robustness. Empirical evaluations on real-world classification datasets and comparisons with state-of-the-art methods support the effectiveness and practicality of our proposed solution.
APA
Carlevaro, A., Oneto, L., Anguita, D. & Roli, F.. (2025). Provably Efficient and Robust Conformal Prediction under a Realistic Threat Model. Proceedings of the Fourteenth Symposium on Conformal and Probabilistic Prediction with Applications, in Proceedings of Machine Learning Research 266:113-132 Available from https://proceedings.mlr.press/v266/carlevaro25a.html.

Related Material