Toward Certified Robustness Against Real-World Distribution Shifts

Haoze Wu, Teruhiro Tagomori, Alexander Robey, Fengjun Yang, Nikolai Matni, George Pappas, Hamed Hassani, Corina Pasareanu, Clark Barrett

TL;DR

This paper introduces a neural-symbolic framework to certify the robustness of deep neural networks against complex, real-world distribution shifts like changes in weather or lighting. By combining deep generative models with a novel counter-example-guided abstraction refinement (CEGAR) strategy, the authors can formally verify networks containing non-linear S-shaped activations (like sigmoid and tanh), significantly outperforming existing one-shot verification methods.

What Problem Does This Paper Address?

Deep neural networks (DNNs) are notoriously fragile, often failing when faced with "distribution shifts"—changes in input data like fog, snow, or varying lighting conditions. While the formal methods community has made strides in certifying robustness against simple mathematical perturbations (like $\ell_p$-norm bounded noise), real-world shifts are far more complex and difficult to define with simple equations.

Comparison between simple norm-bounded perturbation sets and complex real-world sets.

A promising solution is to use generative models (like Conditional VAEs) to learn these shifts from data. However, this creates a new technical hurdle: state-of-the-art generative models typically use S-shaped activation functions (sigmoid or tanh) in their output layers to produce realistic images. Most existing DNN verifiers are optimized for piecewise-linear functions (like ReLU) and struggle to provide tight, refinable approximations for these "transcendental" S-shaped functions, leading to imprecise results.

Methods

The authors propose a neural-symbolic verification framework that bridges the gap between data-driven generative models and formal reasoning.

  1. Neural-Symbolic Specification: They define robustness by concatenating a generative model $G$ with a classifier $f$. The goal is to prove that for all latent variables $z$ within a certain bound $\delta$, the output label remains constant.
  2. CEGAR for S-shaped Activations: To handle the difficult sigmoid/tanh functions, they implement a Counter-Example Guided Abstraction Refinement (CEGAR) loop:
  3. Abstract: Start with a coarse, convex linear over-approximation of the S-shaped function.
  4. Prove: Use an off-the-shelf verifier (like Marabou) to check the property on this abstraction.
  5. Refine: If the verifier finds a counter-example, the algorithm checks if it is "real" or "spurious." A spurious counter-example exists in the abstraction but not in the actual network. If spurious, the algorithm "lazily" adds new piecewise-linear constraints to tighten the abstraction specifically around that point.
Fig. 3: An abstraction of the sigmoid activation function.

The refinement strategy is mathematically grounded, using a "recipe" of slopes based on the function's inflection point to ensure the new bounds are both sound and effective at excluding the specific spurious point found.

Example of Case 1 refinement where a piecewise-linear bound is added to exclude a spurious point below the sigmoid curve.

Datasets

The framework was evaluated on two standard image classification benchmarks:

  • MNIST: Perturbations included scale, brightness, contrast, rotation, and Gaussian blur.
  • CIFAR-10: Perturbations included brightness, contrast, fog, and Gaussian blur.
Fig. 2: Samples from learned perturbation sets. We show samples from two learned perturbation sets S(x) on the MNIST and CIFAR-10 datasets. Samples were generated by gridding the latent space of S(x).

Key Insights and Ideas

  • Latent Space Reasoning: Verifying in the latent space of a generative model allows formal methods to tackle "semantic" robustness, which is much closer to how humans perceive image similarity than raw pixel-distance metrics.
  • Lazy vs. Eager Refinement: Instead of trying to approximate the entire sigmoid curve perfectly from the start (which causes a state-space explosion), the "lazy" CEGAR approach only adds complexity where it's actually needed to prove the property.
  • Inflection Point Awareness: The refinement strategy explicitly accounts for the geometry of S-shaped functions, specifically their inflection points, to choose optimal slopes for the piecewise-linear bounds.

Key Results

  • Increased Precision: The CEGAR-based approach (DP+CEGAR) consistently certified larger perturbation bounds ($\delta$) than baseline methods like DeepPoly (one-shot abstraction) or standard Branch-and-Bound without refinement.
  • Adversarial Benchmarks: On standard sigmoidal benchmarks, the method outperformed specialized verifiers like PRIMA, solving more instances with only a moderate increase in runtime.
  • Training Impact: The authors demonstrated that "distribution-shift-aware" training algorithms (like Model-based Dataset Augmentation) result in significantly higher levels of certified robustness compared to standard or even standard adversarial training (PGD).

Limitations and Future Work

  • Scalability: While effective, the approach is currently limited by the capacity of underlying piecewise-linear verifiers. Scaling to massive architectures like ResNet or DenseNet remains an open challenge.
  • Generative Model Fidelity: The formal guarantee is only as meaningful as the generative model's ability to capture the true distribution shift. If the CVAE is poorly trained, the certification may not reflect reality.
  • Human-in-the-loop: The authors suggest that future work should involve humans to validate the shifts captured by generative models and inspect the counter-examples produced when verification fails, creating a "verify-debug-refine" cycle.

Summary updated

Abstract

We consider the problem of certifying the robustness of deep neural networks against real-world distribution shifts. To do so, we bridge the gap between hand-crafted specifications and realistic deployment settings by proposing a novel neural-symbolic verification framework, in which we train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model. A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations, which are fundamental to many state-of-the-art generative models. To address this challenge, we propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement. The key idea is to "lazily" refine the abstraction of sigmoid functions to exclude spurious counter-examples found in the previous abstraction, thus guaranteeing progress in the verification process while keeping the state-space small. Experiments on the MNIST and CIFAR-10 datasets show that our framework significantly outperforms existing methods on a range of challenging distribution shifts.
BibTeX
@inproceedings{wu2022toward,
  author = {Haoze Wu and Teruhiro Tagomori and Alexander Robey and Fengjun Yang and Nikolai Matni and George Pappas and Hamed Hassani and Corina Pasareanu and Clark Barrett},
  title = {{Toward Certified Robustness Against Real-World Distribution Shifts}},
  booktitle = {SaTML},
  year = {2022},
  doi = {10.1109/satml54575.2023.00042},
}
Figure