Towards a Certified Proof Checker for Deep Neural Network Verification

Remi Desmartin, Omri Isac, Grant O. Passmore, Kathrin Stark, Guy Katz, Ekaterina KomendantskayaLOPSTR 2023 · OpenReview

TL;DR

This paper introduces a novel proof checker for deep neural network (DNN) verification, designed to be infinitely precise and formally verifiable. By leveraging Imandra's exact real arithmetic and theorem proving capabilities, it addresses the critical issue of reliability in existing DNN verification tools, which are often susceptible to implementation bugs and numerical instability.

What Problem Does This Paper Address?

Deep neural networks (DNNs) are increasingly used in safety-critical applications, such as medical imaging and autonomous systems. However, ensuring the safety and reliability of these DNNs is a significant challenge. While formal verification tools exist to prove safety properties, these tools themselves can be buggy or suffer from numerical precision issues, undermining their trustworthiness. To tackle this, some verifiers generate "proofs" of their results that can be independently checked by a separate, simpler "proof checker." This paper focuses on building a more reliable proof checker for DNN verification, aiming to overcome the limitations of existing approaches.

Methods

The core of this work is the development of a proof checker implemented in Imandra, a functional programming language with an integrated industrial-strength theorem prover. The checker is designed to verify proofs generated by the Marabou DNN verifier. Key methodological contributions include:

  • Infinite Precision Real Arithmetic: Imandra's support for exact real arithmetic is leveraged to eliminate numerical stability issues inherent in floating-point computations, a common source of errors in traditional verifiers.
  • Formal Verification Infrastructure: The checker itself is implemented within Imandra's theorem prover. This allows for the formal specification and verification of the checker's correctness properties, significantly increasing its trustworthiness.
  • Proof Tree Reconstruction: The checker reconstructs the proof tree generated by Marabou, which represents the verification process as a series of logical steps and constraints.
  • Two Checking Modes: The checker supports two modes: a "full checking" mode that verifies lemma correctness for maximum reliability, and a "partial checking" mode that prioritizes scalability by using lemmas without verification.
  • Native OCaml Extraction: To improve performance, the Imandra code can be extracted into native OCaml code, benefiting from standard compiler optimizations while retaining the semantics of infinite precision arithmetic.

Datasets

Not discussed in the paper. The paper focuses on the verification of DNNs and the proofs generated by verifiers, rather than training DNNs on specific datasets. The evaluation uses tasks from the ACAS-Xu benchmark.

Key Insights and Ideas

  • The Trustworthiness Dilemma: The paper highlights a fundamental tension in verification: while complex verifiers are powerful, their complexity makes them prone to errors. Simpler proof checkers are more trustworthy but might lack the power to verify complex properties directly. This work bridges this gap by making the checker itself trustworthy.
  • Exact Arithmetic is Crucial for Soundness: The reliance on floating-point arithmetic in traditional verifiers is a major vulnerability. By using exact real arithmetic, the proposed checker eliminates a significant source of potential unsoundness.
  • Formal Verification of the Checker is Key: Implementing the checker within a theorem prover like Imandra allows for a higher degree of assurance than simply trusting an implementation written in a general-purpose language. This is a significant step towards building a truly certified verification pipeline.
  • Scalability vs. Reliability Trade-off: The paper explicitly acknowledges and addresses the trade-off between performance (scalability) and reliability. The two checking modes and the exploration of different data structures (native lists vs. sparse vectors) demonstrate a practical approach to managing this trade-off.

Key Results

  • Novel Proof Checker Implementation: A proof checker for DNN verification is implemented in Imandra, offering infinite precision and formal verifiability.
  • Performance Comparison: An initial comparison of the Imandra-based checker (extracted to OCaml) against a C++ implementation on the ACAS-Xu benchmark shows that the Imandra version is slower (up to 150x slower in full checking mode with native lists) but offers significantly higher assurance.
  • Sparse Vectors Show Promise: The use of sparse vectors for internal data structures, particularly when theory lemmas are not fully checked, shows performance closer to the original C++ implementation, suggesting a path for optimization.

Limitations and Future Work

  • Performance Overhead: The current Imandra implementation, especially in full checking mode, is significantly slower than existing C++ verifiers. This is attributed to the overhead of arbitrary-precision arithmetic and the verification process itself.
  • Ongoing Verification: The formal verification of the proof checker is still in progress. While some properties have been verified, completing the full formal verification is a primary future goal.
  • Optimization: Further optimizations are planned, including implementing more efficient data structures (e.g., AVL trees) and exploring other performance improvements.
  • Broader Applicability: While the current work focuses on proofs from the Marabou verifier and ReLU activation functions, future work could extend to other verifiers and activation functions.
  • Integration: The paper positions this work as a step towards integrating component-level DNN verification into system-level verification frameworks.

Summary updated

Abstract

Recent developments in deep neural networks (DNNs) have led to their adoption in safety-critical systems, which in turn has heightened the need for guaranteeing their safety. These safety properties of DNNs can be proven using tools developed by the verification community. However, these tools are themselves prone to implementation bugs and numerical stability problems, which make their reliability questionable. To overcome this, some verifiers produce proofs of their results which can be checked by a trusted checker. In this work, we present a novel implementation of a proof checker for DNN verification. It improves on existing implementations by offering numerical stability and greater verifiability. To achieve this, we leverage two key capabilities of Imandra, an industrial theorem prover: its support of infinite precision real arithmetic and its formal verification infrastructure. So far, we have implemented a proof checker in Imandra, specified its correctness properties and started to verify the checker's compliance with them. Our ongoing work focuses on completing the formal verification of the checker and further optimizing its performance.
BibTeX
@inproceedings{desmartin2023towards,
  author = {Remi Desmartin and Omri Isac and Grant O. Passmore and Kathrin Stark and Guy Katz and Ekaterina Komendantskaya},
  title = {{Towards a Certified Proof Checker for Deep Neural Network Verification}},
  booktitle = {LOPSTR},
  year = {2023},
  url = {https://openreview.net/forum?id=3boMpU6Ua5},
}
Figure