Lune

CAV2020Top-tier venue

An Abstraction-Based Framework for Neural Network Verification

Yizhak Yisrael Elboher, Justin Gottschlich, Guy Katz

Abstract

Deep neural networks are increasingly being used as controllers for safety-critical systems. Because neural networks are opaque, certifying their correctness is a significant challenge. To address this issue, several neural network verification approaches have recently been proposed. However, these approaches afford limited scalability, and applying them to large networks can be challenging. In this paper, we propose a framework that can enhance neural network verification techniques by using over-approximation to reduce the size of the network -thus making it more amenable to verification. We perform the approximation such that if the property holds for the smaller (abstract) network, it holds for the original as well. The over-approximation may be too coarse, in which case the underlying verification tool might return a spurious counterexample. Under such conditions, we perform counterexample-guided refinement to adjust the approximation, and then repeat the process. Our approach is orthogonal to, and can be integrated with, many existing verification techniques. For evaluation purposes, we integrate it with the recently proposed Marabou framework, and observe a significant improvement in Marabou's performance. Our experiments demonstrate the great potential of our approach for verifying larger neural networks.

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.

25 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

  • Fairify: Fairness Verification of Neural Networks cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Attack as defense: characterizing adversarial examples using robustness cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Attack as defense: characterizing adversarial examples using robustness cites Formal Security Analysis of Neural Networks using Symbolic Intervals
  • Formal Security Analysis of Neural Networks using Symbolic Intervals cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Verifying learning-augmented systems cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Verifying learning-augmented systems cites Formal Security Analysis of Neural Networks using Symbolic Intervals
  • Causality-Based Neural Network Repair cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Causality-Based Neural Network Repair cites Formal Security Analysis of Neural Networks using Symbolic Intervals
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers25

  1. Causality-Based Neural Network RepairBing Sun, Jun Sun, Long H. Pham, Tie ShiICSE 2022 · 69 citations
  2. Verifying learning-augmented systemsTomer Eliyahu, Yafim Kazak, Guy Katz, Michael SchapiraSIGCOMM 2021 · 45 citations
  3. Robustness Verification of Quantum ClassifiersJi Guan, Wang Fang, Mingsheng YingCAV 2021 · 38 citations
  4. Attack as defense: characterizing adversarial examples using robustnessZhe Zhao, Guangke Chen, Jingyi Wang, Yiwei Yang et al.ISSTA 2021 · 34 citations
  5. Fairify: Fairness Verification of Neural NetworksSumon Biswas, Hridesh RajanICSE 2023 · 27 citations

Builds on2

  1. 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
  2. Formal Security Analysis of Neural Networks using Symbolic IntervalsShiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang et al.USENIX Security 2018 · 523 citations

Related papers

  1. Verifying Global Two-Safety Properties in Neural Networks with ConfidenceAnagha Athavale, Ezio Bartocci, Maria Christakis, Matteo Maffei et al.CAV 2024 · 13 citations
  2. VNN: Verification-Friendly Neural Networks with Hard Robustness GuaranteesAnahita Baninajjar, Ahmed Rezine, Amir AminifarICML 2024 · 2 citations
  3. Trainify: A CEGAR-Driven Training and Verification Framework for Safe Deep Reinforcement LearningPeng Jin, Jiaxu Tian, Dapeng Zhi, Xuejun Wen et al.CAV 2022 · 28 citations
  4. Precondition Synthesis for Deep Neural Networks with Statistical GuaranteesZengyu Liu, Bai Xue, Pengfei Yang, Ji WangFSE 2026
  5. Expediting Neural Network Verification via Network ReductionYuyi Zhong, Ruiwei Wang, Siau-Cheng KhooASE 2023 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines