Flex: A Foundational Proof-Producing Horn Solver

summary

The gist

Flex is a foundational Constrained Horn Clause (CHC) solver implemented in Lean that significantly reduces the trusted base to only the kernel…

In short

Flex is a Lean solver for Constrained Horn Clauses (CHCs) that drastically reduces its trusted base to only the kernel. It achieves this by encoding CHCs as Lean propositions and implementing solving tactics ('zap' and 'fix') to compute kernel-checkable proofs. This allows verification of low-level systems code using Lean's full proof ecosystem, automatically discharging most constraints in benchmarks.

Key concepts

CHC Encoding
Flex treats Constrained Horn Clauses as plain Lean propositions where Horn variables are existentially bound predicates. This allows the solver to use Lean's entire proof system to compute proofs for these clauses, rather than relying solely on external SMT solvers.
Solving Tactics ('zap' and 'fix')
The solver partitions variables into acyclic and cyclic sets. The 'zap' tactic solves acyclic variables to find the strongest solutions. The 'fix' tactic uses predicate abstraction to approximate solutions for cyclic variables, enabling a complete solution process.
Expressive Verification
Flex liberates verification from SMT solvers by using Lean's proof machinery to discharge functional correctness properties. It automatically discharges over 95% of constraints in Flux benchmarks, verifying complex Rust code properties like sorting and memory isolation.

Terminology used across episodes

This episode discusses

The paper

Flex: A Foundational Proof-Producing Horn Solver · Read on arXiv

University of California San Diego · University of Chile

Constrained Horn Clauses (CHCs) are a versatile intermediate representation for program verification, but leading CHC solvers rely on SMT-based reasoning over supported background theories. Specifications involving user-defined recursive functions or bespoke operators can require additional semantic encodings and reasoning beyond these theories. We observe that CHCs are existentially quantified propositions in a foundational logic, and so can be proved within an interactive theorem prover, where specifications can use native definitions, and users can complete proofs when automation stalls. However, in a foundational setting, every Horn variable solution must be justified by a kernel-checked proof. We present Flex, a proof-producing CHC solver implemented as a Lean metaprogram, that combines predicate synthesis with proof construction. Flex comprises a suite of tactics: Zap, which synthesizes strongest predicates for acyclic Horn variables and exploits their structure to construct elimination proofs without any proof search; Fix, which uses predicate abstraction over templates built from arbitrary Lean terms, discovered by scraping the CHCs and associated definitions, to infer inductive invariants for cyclic Horn variables; and a certifying pipeline that keeps external SMT-based solvers like Spacer and Eldarica outside the trusted computing base. We use Flex to verify the functional correctness of sorting algorithms, hash tables, ring buffers from the Tock OS kernel, and Rust std library challenges. We show that Zap constructs elimination proofs 28.2x and 44.6x faster than grind and aesop, respectively. With Zap and Fix, Flex automatically proves 98.0% of the refinement-typechecker CHCs in our evaluation.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Flex: A Foundational Proof-Producing Horn Solver".

Jane: Here's the gist of the paper. Flex is a foundational Constrained Horn Clause (CHC) solver implemented in Lean that significantly reduces the trusted base to only the kernel, enabling verification of low-level systems code using Lean’s entire proof ecosystem.

Tom: Flex achieves this through three primary contributions: 1.

Jane: CHC Encoding and Tactic Implementation: Flex encodes CHCs as plain Lean propositions, treating Horn variables as existentially bound predicates.

Tom: It demonstrates how to implement CHC solvers as tactics (meta-programs) that compute kernel-checkable proofs of these propositions.

Paper summary: Tom: So looking at this paper "Flex: A Foundational Proof-Producing Horn Solver", the authors are really showing how to take a foundational logic like Lean and apply it to solving these complex constraints in a way that leverages the whole proof system > Page one — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Jane: It’s important to remember they weren't just adding another tool; they were fundamentally changing the trust model by reducing the trusted base down to just the kernel, which allows verification of low-level systems code > Page one — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Lu: The implication is that we can leapfrog some of the limitations you see with SMT solvers regarding expressiveness and trust because you implement a solver within a foundational prover as a meta-program to compute proofs > Page two — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Meng: For deployment, the key part is understanding that while they get near perfect results on acyclic variables, you have to account for those cyclic ones where the success rate drops to eighty-two point three percent > Page three — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Lalam: And they did this by creating two verified generators—one for imperative languages and one for functional calculus—which can then be composed with their solving tactics to build a complete verifier > Page one — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Tom: So overall, it’s about making the tool robust enough to handle both the exact solutions and the approximate ones without needing a massive amount of external verification > Page two — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Jane: It shows that by using Lean's entire proof machinery, we can discharge functional correctness properties for things like in-place sorting algorithms or secure memory isolation in systems like the Tock embedded kernel > Page three — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1,using Lean's entire proof>

Conclusion: Tom: So, we’ve been talking about this Flex paper by some authors who built a solver that uses Lean to check these kinds of constraints > Page one — Flex: A Foundational Proof-Producing Horn Solver

Jane: Right, so what’s the big picture here? They're taking this logic system and making it solve things we used to think required super complex external math tools > Page two — Flex: A Foundational Proof-Producing Horn Solver

Lu: Basically, they've got this system that lets you verify low-level code using Lean’s whole proof ecosystem instead of just relying on some SMT solver that might be too limited > Page three — Flex: A Foundational Proof-Producing Horn Solver

Meng: But what does it actually *do*? It says they've got generators for both regular computer code and functional calculus, and those generators work with the solving tactics to make a complete verifier > Page one — Flex: A Foundational Proof-Producing Horn Solver

Tom: The results show that this approach automatically checks over ninety-five percent of the constraints we put into their benchmark suite for things like sorting or memory isolation in systems > Page three — Flex: A Foundational Proof-Producing Horn Solver

Jane: That sounds pretty impressive, but there's always a catch, right? They mentioned that the success rate drops to eighty-two point three percent when they have to deal with those tricky cyclic variables > Page three — Flex: A Foundational Proof-Producing Horn Solver

Lu: That makes sense because approximating solutions for cyclic variables is where the complexity comes in; it's like, you get almost everything right unless the problem loops back on itself > Page two — Flex: A Foundational Proof-Producing Horn Solver

Meng: And from a deployment standpoint, that eighty-two percent success rate means you still have to manually check those tricky parts or use a different approach for those specific kinds of problems > Page one — Flex: A Foundational Proof-Producing Horn Solver

Tom: So, the implication is that we might be able to verify much more complex low-level systems with this method because it uses the full power of Lean’s proof engine > Page three — Flex: A Foundational Proof-Producing Horn Solver

Jane: It shifts the trust model, moving away from relying on a black box solver to having a formal mathematical proof that the system is safe > Page two — Flex: A Foundational Proof-Producing Horn Solver

Lu: And it's foundational because they built generators for both imperative and functional stuff, which means this isn't just a niche tool for one type of problem > Page one — Flex: A Foundational Proof-Producing Horn Solver

Meng: For the practical folks here, it’s about speed, though they admit their Lean backend is slower than some existing SMT methods they compared against > Page three — Flex: A Foundational Proof-Producing Horn Solver

Tom: So it’s a trade-off between absolute power and raw execution time, but the coverage of ninety-five percent of those constraints is significant > Page two — Flex: A Foundational Proof-Producing Horn Solver

Jane: It’s definitely a tool that pushes the boundaries on what we can formally verify in software, and it opens up new avenues for security research > Page one — Flex: A Foundational Proof-Producing Horn Solver

More episodes

← Home