TL;DR
This paper introduces Sift, a novel methodology that bridges the gap between powerful but manual formal verification techniques and automated but less expressive ones for distributed systems. Sift enables proving the correctness of complex distributed implementations with significantly reduced manual effort by combining refinement-based reasoning with automated tools.
What Problem Does This Paper Address?
Verifying the correctness of distributed systems is notoriously difficult due to their inherent complexity, concurrency, and potential for partial failures. Traditional approaches fall into two camps:
- Powerful but Manual: Techniques like IronFleet and Verdi use "refinement proofs" to show that an implementation is equivalent to a simpler, abstract specification. This offers strong guarantees but requires a substantial amount of manual effort from highly skilled engineers.
- Automated but Limited: Tools like I4, IC3PO, SWISS, and DistAI leverage automated reasoning (model checking, SMT solvers) to prove properties of protocols. While they automate much of the proof, they typically only handle "monolithic" protocols (single-layer) and cannot prove refinement, limiting their applicability to complex, multi-layered systems or actual implementations.
This leaves a significant gap: how to achieve high assurance for complex, real-world distributed systems without incurring prohibitive manual verification costs.
Methods
Sift proposes a two-tier methodology to address this gap:
- Refinement-Guided Automation: This core technique allows monolithic provers to be used within a refinement proof. It works by "encapsulating" the state of the more abstract layer (the specification or an intermediate layer) within the state of the more concrete layer (the implementation or a lower layer). This effectively transforms a multi-layer refinement problem into a single-layer problem that a monolithic prover can handle.
- Divide-and-Conquer for Intermediate Layers: When a refinement step is still too complex for even the encapsulated monolithic prover, Sift employs a strategy to introduce intermediate refinement layers. This splits a large, complex proof into smaller, more manageable chunks, each of which can then be tackled by the refinement-guided automation technique. This is a manual step but significantly reduces the overall manual proof effort compared to traditional methods.
The process generally involves:
- Starting with an implementation and specification.
- Attempting to prove refinement directly using encapsulation and a monolithic prover (like IC3PO).
- If it fails, introducing an intermediate layer to split the problem.
- Repeating this process until each refinement step is automated.
- Handling preconditions and assertions by converting them to if-statements or invariants, ensuring soundness.
Datasets
Not discussed in the paper. The paper evaluates Sift on existing distributed systems, not on new datasets.
Key Insights and Ideas
- Bridging the Gap: The most significant insight is that refinement and automation, previously seen as opposing forces, can be effectively combined. Sift shows how to leverage the power of automated tools for the complex task of proving refinement.
- Encapsulation as a Key Enabler: The encapsulation technique is crucial. By embedding the abstract state into the concrete state, Sift tricks monolithic provers into reasoning about the refinement relationship as if it were a single system.
- Manual Effort is Strategic, Not Exhaustive: Sift doesn't eliminate manual effort entirely, but it strategically places it where it's most impactful: defining intermediate layers. This drastically reduces the overall burden compared to writing full manual proofs.
- Modularity is Key to Scalability: The divide-and-conquer approach of introducing intermediate layers is essential for tackling the complexity of real-world distributed systems, mirroring the modularity principle in system design.
- Monolithic Provers are Versatile: The methodology is designed to be agnostic to the specific monolithic prover used, allowing it to benefit from future advancements in automated reasoning tools.
Key Results
Sift was used to verify six distributed systems, including leader election, distributed lock, two-phase commit, sharded hash table, Raft, and MultiPaxos.
- Reduced Manual Effort: For most systems, the manual effort required was minimal (e.g., less than 5 minutes for simple transformations). Even for complex systems like Raft and MultiPaxos, the manual effort was significantly reduced compared to previous approaches (e.g., from 3 person-months to 1 person-month for Raft).
- Automated Proofs: Sift enabled automated proofs for systems that previously required fully manual verification or were considered too complex for existing automated tools.
- Performance: The verified implementations using Sift showed performance comparable to or even better than manually verified counterparts, demonstrating that the automation does not come at a significant performance cost. For example, Sift's Raft implementation performed identically to a previous Ivy implementation, and its MultiPaxos implementation outperformed a previous Ivy version. SHT performance was slightly lower than IronKV but comparable to other verified systems.
Limitations and Future Work
- Automating Transformations: While Sift automates much of the refinement proof, some transformations (like converting assertions to if-statements or invariants, and deriving loop invariants) still require manual effort. The authors suggest automating these transformations as a future direction.
- Loop Invariants: Proving optimizations that rely on loop invariants still requires manual effort. Extending Sift to automatically derive loop invariants is a key area for future work.
- Leveraging Multiple Provers: The current methodology uses a single monolithic prover. The authors plan to explore using a portfolio of different monolithic provers in parallel to further enhance scalability and handle diverse scenarios.
- Liveness Properties: Sift, like many verification tools, focuses on safety properties and does not currently support liveness proofs.
Summary updated