Abstract
We introduce CSLib, an open-source framework for proving computer-science-related theorems and writing formally verified code in the Lean proof assistant. CSLib aims to be for computer science what Lean's Mathlib is for mathematics. Mathlib has been tremendously impactful: it is a key reason for Lean's popularity within the mathematics research community, and it has also played a critical role in the training of AI systems for mathematical reasoning. However, the base of computer science knowledge in Lean is currently quite limited. CSLib will vastly enhance this knowledge base and provide infrastructure for using this knowledge in real-world verification projects. By doing so, CSLib will (1) enable the broad use of Lean in computer science education and research, and (2) facilitate the manual and AI-aided engineering of large-scale formally verified systems.
1. Introduction
The Lean proof assistant's "Mathlib" has revolutionized collaborative mathematics, yet a similar unified foundation for Computer Science is missing. Currently, formalizing CS concepts—ranging from models of computation to algorithmic complexity—occurs in isolated, fragmented repositories. This lack of a central library hinders the scalability of formal verification and prevents researchers from building compositionally on each other's work.
Simultaneously, the software industry faces a reliability crisis. While AI coding assistants boost productivity, they risk introducing subtle correctness and security vulnerabilities. Traditional formal verification remains the gold standard for security but is historically prohibitively expensive (e.g., the seL4 microkernel required 20 person-years). CSLib addresses these challenges by creating a unified, reusable library of CS knowledge and the infrastructure needed to lower the cost of verifying mainstream, real-world code.
2. The CSLib Framework
CSLib is built on two technical pillars: the formalization of CS theory and the Boole Intermediate Verification Language (IVL).
2.1 Formalizing Computer Science in Lean
The project aims to build a comprehensive repository of CS theory. This includes models of computation (Turing machines, automata), logics (Hoare, separation, temporal), and algorithms. A key innovation is the treatment of algorithmic complexity via a monadic API (e.g., TimeM). By treating time complexity as a computational effect, developers can track the "cost" (ticks) of operations alongside return values, cleanly separating functional correctness from worst-case analysis.
2.2 Boole: An Intermediate Verification Language
To bridge the gap to mainstream languages like Rust or C++, CSLib introduces Boole. Deeply embedded in Lean, Boole provides a readable pseudocode-like syntax with strict mathematical semantics. Mainstream code is transpiled into Boole, which then generates Verification Conditions (VCs) as Lean goals. These goals can be solved using automated "hammers" (like Lean-SMT) or AI-based provers, keeping the Trusted Computing Base (TCB) minimal.
3. Design Philosophy and AI Integration
CSLib emphasizes compositionality, allowing systems researchers to pull pre-verified models without rebuilding foundations from scratch. Furthermore, it creates a symbiotic "AI Flywheel": CSLib provides high-quality, foundational data for training AI provers (like AlphaProof), which in turn help automate the tedious parts of writing and verifying the library itself. The monadic approach to complexity also allows for flexible cost models, such as counting memory allocations versus comparisons, simply by adjusting where "ticks" are placed.
4. Implementation Status and Results
As a framework and roadmap paper, CSLib focuses on initial implementation milestones rather than traditional benchmarks. Key results include:
- Theory Milestones: The repository contains working Lean formalizations for operational semantics, automata models, and elementary algorithms, including a verified Mergesort that proves both functional correctness and $O(n \log n)$ worst-case complexity.
- Infrastructure Milestones: A working prototype of the Boole IVL demonstrates the ability to handle imperative
whileloops with invariants, successfully generating VCs that are automatically discharged by SMT tactics.
5. Limitations and Future Roadmap
Current limitations include the manual nature of "tick" annotations for complexity, which are prone to user error, and the current inability to prove algorithmic lower bounds. The 2026–2027 roadmap includes extending Boole to support concurrency and separation logic (crucial for pointer reasoning). A major future goal is the integration with tools like Aeneas to automatically translate real Rust or C++ code into the framework, targeting the end-to-end verification of a substantial real-world system.
Summary updated