Lune

OOPSLA2022Top-tier venue

Proof transfer for fast certification of multiple approximate neural networks

Shubham Ugare, Gagandeep Singh, Sasa Misailovic

Abstract

Developers of machine learning applications often apply post-training neural network optimizations, such as quantization and pruning, that approximate a neural network to speed up inference and reduce energy consumption, while maintaining high accuracy and robustness. Despite a recent surge in techniques for the robustness verification of neural networks, a major limitation of almost all state-of-the-art approaches is that the verification needs to be run from scratch every time the network is even slightly modified. Running precise end-to-end verification from scratch for every new network is expensive and impractical in many scenarios that use or compare multiple approximate network versions, and the robustness of all the networks needs to be verified efficiently. We present FANC, the first general technique for transferring proofs between a given network and its multiple approximate versions without compromising verifier precision. To reuse the proofs obtained when verifying the original network, FANC generates a set of templates – connected symbolic shapes at intermediate layers of the original network – that capture the proof of the property to be verified. We present novel algorithms for generating and transforming templates that generalize to a broad range of approximate networks and reduce the verification cost. We present a comprehensive evaluation demonstrating the effectiveness of our approach. We consider a diverse set of networks obtained by applying popular approximation techniques such as quantization and pruning on fully-connected and convolutional architectures and verify their robustness against different adversarial attacks such as adversarial patches, L 0 , rotation and brightening. Our results indicate that FANC can significantly speed up verification with state-of-the-art verifier, DeepZ by up to 4.1x.

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.

9 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

  • Certified Robustness to Adversarial Examples with Differential Privacy cites Towards Evaluating the Robustness of Neural Networks
  • Certified Robustness to Adversarial Examples with Differential Privacy cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond cites Certified Robustness to Adversarial Examples with Differential Privacy
  • Certified Continual Learning for Neural Network Regression cites Certified Robustness to Adversarial Examples with Differential Privacy
  • Certified Continual Learning for Neural Network Regression cites Towards Evaluating the Robustness of Neural Networks
  • Certified Continual Learning for Neural Network Regression 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 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
  • AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation cites Towards Evaluating the Robustness of Neural Networks
  • Input-Relational Verification of Deep Neural Networks cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
  • Input-Relational Verification of Deep Neural Networks cites Towards Evaluating the Robustness of Neural Networks
  • Input-Relational Verification of Deep Neural Networks cites Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification
  • Input-Relational Verification of Deep Neural Networks cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • ARQ: A Mixed-Precision Quantization Framework for Accurate and Certifiably Robust DNNs cites Incremental Verification of Neural Networks
  • ARQ: A Mixed-Precision Quantization Framework for Accurate and Certifiably Robust DNNs cites Incremental Randomized Smoothing Certification
  • Incremental Verification of Neural Networks cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
  • Incremental Verification of Neural Networks cites Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification
  • Incremental Verification of Neural Networks cites AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation
  • Incremental Randomized Smoothing Certification cites Incremental Verification of Neural Networks
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Incremental Verification of Neural NetworksShubham Ugare, Debangshu Banerjee, Sasa Misailovic, Gagandeep SinghPLDI 2023 · 19 citations
  2. Incremental Randomized Smoothing CertificationShubham Ugare, Tarun Suresh, Debangshu Banerjee, Gagandeep Singh et al.ICLR 2024 · 14 citations
  3. Input-Relational Verification of Deep Neural NetworksDebangshu Banerjee, Changming Xu, Gagandeep SinghPLDI 2024 · 9 citations
  4. Certified Continual Learning for Neural Network RegressionLong H. Pham, Jun SunISSTA 2024 · 2 citations
  5. ARQ: A Mixed-Precision Quantization Framework for Accurate and Certifiably Robust DNNsYuchen Yang, Yifan Zhao, Shubham Ugare, Gagandeep Singh et al.ISSTA 2026 · 2 citations

Builds on14

  1. Towards Evaluating the Robustness of Neural NetworksNicholas Carlini, David A. WagnerS&P 2017 · 9,786 citations
  2. Certified Robustness to Adversarial Examples with Differential PrivacyMathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu et al.S&P 2019 · 1,022 citations
  3. 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
  4. Automatic Perturbation Analysis for Scalable Certified Robustness and BeyondKaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang et al.NeurIPS 2020 · 415 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. VNN: Verification-Friendly Neural Networks with Hard Robustness GuaranteesAnahita Baninajjar, Ahmed Rezine, Amir AminifarICML 2024 · 2 citations
  2. ReluDiff: differential verification of deep neural networksBrandon Paulsen, Jingbo Wang, Chao WangICSE 2020 · 47 citations
  3. Shared Certificates for Neural Network VerificationMarc Fischer, Christian Sprecher, Dimitar I. Dimitrov, Gagandeep Singh et al.CAV 2022 · 15 citations
  4. Scalable Quantitative Verification For Deep Neural NetworksTeodora Baluta, Zheng Leong Chua, Kuldeep S. Meel, Prateek SaxenaICSE 2021 · 39 citations
  5. Tightening Robustness Verification of Convolutional Neural Networks with Fine-Grained Linear ApproximationYiting Wu, Min ZhangAAAI 2021 · 23 citations
Dusk over the sea between two cliffs drawn in fine vertical lines