Lune

PLDI2023Top-tier venue

Abstract Interpretation of Fixpoint Iterators with Applications to Neural Networks

Mark Niklas Müller, Marc Fischer, Robin Staab, Martin T. Vechev

Abstract

We present a new abstract interpretation framework for the precise over-approximation of numerical fixpoint iterators. Our key observation is that unlike in standard abstract interpretation (AI), typically used to over-approximate all reachable program states, in this setting, one only needs to abstract the concrete fixpoints, i.e., the final program states. Our framework targets numerical fixpoint iterators with convergence and uniqueness guarantees in the concrete and is based on two major technical contributions: (i) theoretical insights which allow us to compute sound and precise fixpoint abstractions without using joins, and (ii) a new abstract domain, CH-Zonotope, which admits efficient propagation and inclusion checks while retaining high precision. We implement our framework in a tool called CRAFT and evaluate it on a novel fixpoint-based neural network architecture (monDEQ) that is particularly challenging to verify. Our extensive evaluation demonstrates that CRAFT exceeds the state-of-the-art performance in terms of speed (two orders of magnitude), scalability (one order of magnitude), and precision (25% higher certified accuracies).

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Learning from Uncertain Data: From Possible Worlds to Possible Models cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Certified Robustness to Adversarial Examples with Differential Privacy cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Certified Robustness to Adversarial Examples with Differential Privacy cites Formal Security Analysis of Neural Networks using Symbolic Intervals
  • Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond cites Certified Robustness to Adversarial Examples with Differential Privacy
  • Formal Security Analysis of Neural Networks using Symbolic Intervals cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Efficient Error Certification for Physics-Informed Neural Networks cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Efficient Error Certification for Physics-Informed Neural NetworksFrancisco Eiras, Adel Bibi, Rudy Bunel, Krishnamurthy Dj Dvijotham et al.ICML 2024 · 7 citations
  2. Learning from Uncertain Data: From Possible Worlds to Possible ModelsJiongli Zhu, Su Feng, Boris Glavic, Babak SalimiNeurIPS 2024 · 4 citations

Builds on11

  1. Certified Robustness to Adversarial Examples with Differential PrivacyMathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu et al.S&P 2019 · 1,022 citations
  2. AI2: Safety and Robustness Certification of Neural Networks with Abstract InterpretationTimon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov et al.S&P 2018 · 987 citations
  3. Formal Security Analysis of Neural Networks using Symbolic IntervalsShiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang et al.USENIX Security 2018 · 523 citations
  4. Automatic Perturbation Analysis for Scalable Certified Robustness and BeyondKaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang et al.NeurIPS 2020 · 415 citations
  5. Monotone operator equilibrium networksEzra Winston, J. Zico KolterNeurIPS 2020 · 177 citations

Related papers

  1. The Octatope Abstract Domain for Verification of Neural NetworksStanley Bak, Taylor Dohmen, K. Subramani, Ashutosh Trivedi et al.FM 2023 · 5 citations
  2. A general construction for abstract interpretation of higher-order automatic differentiationJacob Laurel, Rem Yang, Shubham Ugare, Robert Nagel et al.OOPSLA 2022 · 9 citations
  3. Out of the Shadows: Exploring a Latent Space for Neural Network VerificationLukas Koller, Tobias Ladner, Matthias AlthoffICLR 2026 · 6 citations
  4. SAIL: Sound Abstract Interpreters with LLMsQiuhan Gu, Avaljot Singh, Gagandeep SinghPLDI 2026
  5. Fast and precise certification of transformersGregory Bonaert, Dimitar I. Dimitrov, Maximilian Baader, Martin T. VechevPLDI 2021 · 18 citations
Dusk over the sea between two cliffs drawn in fine vertical lines