Formal Verification in Any Language for Everybody (lean 4)
11 hours ago
- #Software Correctness
- #Formal Verification
- #Differential Testing
- The author formally verified a grocery suggestion engine CLI tool using Lean 4, despite it being unnecessary for the simple task, as a fun exercise.
- The approach involved implementing the engine in Lean, writing theorems for properties, using AI (Claude) to prove them, and then implementing in Haskell.
- Differential Random Testing (DRT) was used to compare outputs of the Lean (proven) and Haskell (production) versions with random inputs, ensuring correctness.
- This method, called Verification Guided Development with DRT, allows verifying production code in any language by matching it with a proven specification.
- Benefits include near-proof of correctness, catching bugs missed by property tests, low friction across stacks, and enabling AI-assisted implementation from theorems.
- The author highlighted real-world use in AWS Cedar, where it found bugs, and noted that encoding requirements as theorems is the challenging but crucial part.