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