Shared Certificates for Neural Network Verification

Marc Fischer, Christian Sprecher, Dimitar Iliev Dimitrov, Gagandeep Singh, Martin Vechev

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Existing neural network verifiers compute a proof that each input is handled correctly under a given perturbation by propagating a symbolic abstraction of reachable values at each layer. This process is repeated from scratch independently for each input (e.g., image) and perturbation (e.g., rotation), leading to an expensive overall proof effort when handling an entire dataset. In this work, we introduce a new method for reducing this verification cost without losing precision based on a key insight that abstractions obtained at intermediate layers for different inputs and perturbations can overlap or contain each other. Leveraging our insight, we introduce the general concept of shared certificates, enabling proof effort reuse across multiple inputs to reduce overall verification costs. We perform an extensive experimental evaluation to demonstrate the effectiveness of shared certificates in reducing the verification cost on a range of datasets and attack specifications on image classifiers including the popular patch and geometric perturbations. We release our implementation at

Original languageEnglish (US)
Title of host publicationComputer Aided Verification - 34th International Conference, CAV 2022, Proceedings
EditorsSharon Shoham, Yakir Vizel
Number of pages22
ISBN (Print)9783031131844
StatePublished - 2022
Event34th International Conference on Computer Aided Verification, CAV 2022 - Haifa, Israel
Duration: Aug 7 2022Aug 10 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13371 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference34th International Conference on Computer Aided Verification, CAV 2022


  • Adversarial Robustness
  • Local Verification
  • Neural Network Verification

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Shared Certificates for Neural Network Verification'. Together they form a unique fingerprint.

Cite this