Test, Don't (Just) Verify
4 months ago
- #AI
- #Software Engineering
- #Formal Verification
- AI is making formal verification mainstream with AI-assisted mechanical proving companies raising funds and new users adopting proof assistants like Lean.
- Formal verification faces challenges: lack of formal specifications for most software and the difficulty of proof engineering.
- AI-assisted programming promotes specification-driven development, incentivizing executable specifications and enabling program optimizers and translators.
- Formal verification proves the absence of bugs, with examples like CompCert C Compiler outperforming GCC and Clang in bug detection.
- AI is effective at writing proofs and can be integrated into Reinforcement Learning with Verifiable Rewards (RLVR) for improved performance.
- Autoformalization is a critical but shaky part of the trusted computing base (TCB) in AI-assisted verified programming.
- Proof assistants are slow due to their use of inductive types like Peano numbers, but solutions exist like efficient encoding and extraction.
- Verification requires domain-specific models, which are hard to create, especially for areas like runtime performance.
- Testing complements verification by providing falsification, as seen with tools like QuickChick in the Rocq ecosystem.
- Verification-Guided Development (VGD) combines verified and production implementations, leveraging testing to ensure correctness and speed.
- Random testing and formal verification are both essential for the future of software engineering, each complementing the other.