Provably Adversarially Robust Detection of Out-of-Distribution Data (Almost) for Free

Alexander Meinke, Julian Bitterwolf, Matthias Hein

Deep neural networks are notoriously overconfident. When shown an image of something they’ve never seen before—known as out-of-distribution (OOD) data—they often assign it to a known class with nearly 100% confidence. This poses a major safety concern for critical applications like autonomous vehicles or medical AI.

To address this, researchers introduced ProoD (Provable out-of-Distribution detector) at NeurIPS 2022. ProoD is a novel architecture that achieves provably robust OOD detection without sacrificing classification accuracy. By combining a standard classifier with a certifiably robust binary discriminator, it ensures that even adversarially manipulated "garbage" inputs cannot fool the system into high-confidence predictions.

The Problem: Adversarial OOD Data

OOD data is highly vulnerable to adversarial attacks. A malicious actor can take a random noise pattern and subtly tweak it so that a model "sees" a stop sign with high certainty. While researchers have proposed empirical defenses for this, many can be broken by better-adapted attacks.

There is a desperate need for provable robustness—mathematical certainty that no perturbation within a specific range can raise the model's confidence above a certain threshold. Until now, methods providing these guarantees were either too slow to train, limited to tiny networks, or severely degraded the model's accuracy on normal (in-distribution) data.

The ProoD Architecture

The core innovation of ProoD is its Joint Model architecture. Instead of relying on a single network, ProoD merges two components into one probabilistic framework:

  1. A Standard Classifier: This handles the primary task (e.g., "Is this a cat or a dog?").
  2. A Certified Binary Discriminator: This acts as a gatekeeper, asking, "Is this even something I recognize?"
ProoD architecture combining a standard classifier and a certified binary discriminator.

The final prediction is a weighted combination of the two. If the gatekeeper's confidence in the data being "in-distribution" is low, the model defaults to a uniform, low-confidence distribution.

Key Technical Innovations

  • Interval Bound Propagation (IBP): ProoD uses IBP to train the discriminator. IBP computes the worst-case output for any input within a small "box" (an $\ell_\infty$-ball), allowing for strict mathematical guarantees.
  • Solving Asymptotic Overconfidence: Standard ReLU networks are mathematically guaranteed to be overconfident when inputs are far away from their training data. By forcing the final layer of the discriminator to have only negative weights, ProoD provably solves this problem. As you move infinitely far away from the training data, the model's confidence must drop.
  • Semi-Joint Training: To keep the guarantees intact without ruining accuracy, the authors first train the robust discriminator and then train the classifier "around" it.

Key Results: Robustness "Almost for Free"

Most robust models suffer a severe "robustness-accuracy trade-off." ProoD avoids this because the main classifier is not constrained by the rigorous certification process; only the gatekeeper is.

Performance comparison showing ProoD's high accuracy and guaranteed AUC (GAUC) across multiple datasets.
  • High Accuracy: On CIFAR-10, ProoD maintains 94.99% accuracy, nearly identical to a standard plain model (95.01%). Previous provable methods often dropped accuracy significantly.
  • Tight Guarantees: ProoD provides a Guaranteed AUC (GAUC). For example, on CIFAR-10 vs. SVHN, it guarantees an AUC of at least 53.3%, while the actual adversarial AUC is 54.1%. This demonstrates that the certification bounds are remarkably tight.
  • Scalability: ProoD is the first method to provide worst-case OOD guarantees on high-resolution images. On Restricted ImageNet, it achieves a GAUC of over 57% on several datasets while maintaining 97.25% clean accuracy.

Limitations and Future Work

While ProoD is a significant leap forward, it has a few limitations:

  • Threat Model: The guarantees currently only apply to $\ell_\infty$ perturbations (small pixel-wise changes). It does not yet cover other types of attacks like rotations, translations, or $\ell_2$ attacks.
  • OOD Dependency: Like many OOD methods, ProoD performs best when it has access to a diverse "outlier exposure" dataset (like OpenImages) during training. Its performance on "near-OOD" data remains a challenge.
  • In-Distribution Attacks: ProoD focuses on making OOD detection robust. It does not claim to make the classification of in-distribution samples robust to adversarial attacks (e.g., turning a real "cat" image into a "dog"). Combining these two types of robustness is a clear next step for the field.

Summary updated

Abstract

The application of machine learning in safety-critical systems requires a reliable assessment of uncertainty.However, deep neural networks are known to produce highly overconfident predictions on out-of-distribution (OOD) data.Even if trained to be non-confident on OOD data, one can still adversarially manipulate OOD data so that the classifier again assigns high confidence to the manipulated samples.We show that two previously published defenses can be broken by better adapted attacks, highlighting the importance of robustness guarantees around OOD data.Since the existing method for this task is hard to train and significantly limits accuracy, we construct a classifier that can simultaneously achieve provably adversarially robust OOD detection and high clean accuracy.Moreover, by slightly modifying the classifier's architecture our method provably avoids the asymptotic overconfidence problem of standard neural networks.We provide code for all our experiments.
BibTeX
@inproceedings{meinke2022provably,
  author = {Alexander Meinke and Julian Bitterwolf and Matthias Hein},
  title = {{Provably Adversarially Robust Detection of Out-of-Distribution Data (Almost) for Free}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=YfU5WTpv97},
}
Figure