Lune

PLDI2024Top-tier venue

Input-Relational Verification of Deep Neural Networks

Debangshu Banerjee, Changming Xu, Gagandeep Singh

Abstract

We consider the verification of input-relational properties defined over deep neural networks (DNNs) such as robustness against universal adversarial perturbations, monotonicity, etc. Precise verification of these properties requires reasoning about multiple executions of the same DNN. We introduce a novel concept of difference tracking to compute the difference between the outputs of two executions of the same DNN at all layers. We design a new abstract domain, DiffPoly for efficient difference tracking that can scale large DNNs. DiffPoly is equipped with custom abstract transformers for common activation functions (ReLU, Tanh, Sigmoid, etc.) and affine layers and can create precise linear cross-execution constraints. We implement an input-relational verifier for DNNs called RaVeN which uses DiffPoly and linear program formulations to handle a wide range of input-relational properties. Our experimental results on challenging benchmarks show that by leveraging precise linear constraints defined over multiple executions of the DNN, RaVeN gains substantial precision over baselines on a wide range of datasets, networks, and input-relational properties.

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.

8 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

  • Relational Verification Leaps Forward with RABBit cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
  • Relational Verification Leaps Forward with RABBit cites Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification
  • Relational Verification Leaps Forward with RABBit cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Relational Verification Leaps Forward with RABBit cites Towards Stable and Efficient Training of Verifiably Robust Neural Networks
  • Automated Verification of Soundness of DNN Certifiers cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
  • Automated Verification of Soundness of DNN Certifiers cites Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification
  • Automated Verification of Soundness of DNN Certifiers cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond cites Towards Stable and Efficient Training of Verifiably Robust Neural Networks
  • Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
  • Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification cites Towards Stable and Efficient Training of Verifiably Robust Neural Networks
  • AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation cites Towards Evaluating the Robustness of Neural Networks
  • Quantization with Guaranteed Floating-Point Neural Network Classifications cites Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification
  • Towards Stable and Efficient Training of Verifiably Robust Neural Networks cites Towards Evaluating the Robustness of Neural Networks
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Relational Verification Leaps Forward with RABBitTarun Suresh, Debangshu Banerjee, Gagandeep SinghNeurIPS 2024 · 5 citations
  2. Automated Verification of Soundness of DNN CertifiersAvaljot Singh, Yasmin Sarita, Charith Mendis, Gagandeep SinghOOPSLA 2025 · 3 citations
  3. Exact Verification of Graph Neural Networks with Incremental Constraint SolvingMinghao Liu, Chia-Hsuan Lu, Marta KwiatkowskaFM 2026 · 1 citation
  4. VeriFlow: Modeling Distributions for Neural Network VerificationFaried Abu Zaid, Daniel Neider, Mustafa YalçinerAAAI 2026 · 1 citation
  5. Quantization with Guaranteed Floating-Point Neural Network ClassificationsAnan Kabaha, Dana Drachsler-CohenOOPSLA 2025 · 1 citation

Builds on32

  1. Towards Evaluating the Robustness of Neural NetworksNicholas Carlini, David A. WagnerS&P 2017 · 9,786 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. Automatic Perturbation Analysis for Scalable Certified Robustness and BeyondKaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang et al.NeurIPS 2020 · 415 citations
  4. Towards Stable and Efficient Training of Verifiably Robust Neural NetworksHuan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal et al.ICLR 2020 · 384 citations
  5. Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness VerificationShiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin et al.NeurIPS 2021 · 359 citations

Related papers

  1. Relational DNN Verification With Cross Executional Bound RefinementDebangshu Banerjee, Gagandeep SinghICML 2024 · 8 citations
  2. ReluDiff: differential verification of deep neural networksBrandon Paulsen, Jingbo Wang, Chao WangICSE 2020 · 47 citations
  3. Verifying Global Two-Safety Properties in Neural Networks with ConfidenceAnagha Athavale, Ezio Bartocci, Maria Christakis, Matteo Maffei et al.CAV 2024 · 13 citations
  4. Scalable Quantitative Verification For Deep Neural NetworksTeodora Baluta, Zheng Leong Chua, Kuldeep S. Meel, Prateek SaxenaICSE 2021 · 39 citations
  5. The Octatope Abstract Domain for Verification of Neural NetworksStanley Bak, Taylor Dohmen, K. Subramani, Ashutosh Trivedi et al.FM 2023 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines