Skip to content
/ DistAI Public

DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols

Notifications You must be signed in to change notification settings

VeriGu/DistAI

Repository files navigation

DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols

DistAI is a tool to automatically infer inductive invariants to prove the correctness of distributed protocols. It takes a simulation-learning-refinement workflow. Given a protocol, DistAI first repeatedly simulate the protocol using randomized instances. This gives a collection of simulation traces (i.e., samples). Then DistAI applies an enumeration-based learning procedure to find invariants that hold true on all the samples. Finally, DistAI uses Ivy, a theorem prover built on top of Z3 SMT solver, to refine the invariants using counterexamples until validated.

Installation

You can build DistAI from source using the installation guide install.txt. Native installation gives the most accurate runtime numbers.

Alternatively, one can use our docker image with the guide docker_usage.md. This image also includes I4 and FOL-IC3, the two systems DistAI compared with in the evaluation.

Usage

Top-level API

Given the name of a distributed protocol, python main.py PROTOCOL simulates the protocol, learn the invariants and refine them. The proved protocol with correct invariants will be written to outputs/PROTOCOL/PROTOCOL_inv.ivy

python main.py two_phase_commit

Step-by-step instructions

In src-py/, we can use python translate.py PROTOCOL to generate the simulation script in Python from the Ivy source. It accepts a conditional argument --min_size for the minimum instance size (i.e., initial template size). If omitted, DistAI will infer the minimum size from the protocol.

python translate.py distributed_lock --min_size="node=2 epoch=2"

The simulation script is written to auto_samplers/. From there, run python PROTOCOL.py to simulate the protocol.

python database_chain_replication.py

The samples are written to traces/, and a configuration file is generated in configs/. Then, in src-c/, run ./main PROTOCOL [MAX_RETRY] to learn and infer the invariants. MAX_RETRY is a conditional argument indicating how many times the solver should retry (i.e., incrementing max-literal) before giving up.

./main blockchain 1

The proved protocol with correct inductive invariants attached is written to outputs/PROTOCOL/PROTOCOL_inv.ivy. From there, one can use ivy_check PROTOCOL_inv.ivy to validate its correctness.

Running new protocols

To use DistAI on a new distributed protocol, simply add the Ivy file at protocols/NEW_PROTOCOL/NEW_PROTOCOL.ivy, and make an empty directory outputs/NEW_PROTOCOL/. Then run python main.py NEW_PROTOCOL

Note that to simulate the protocol, DistAI parses the Ivy file from scratch instead of using the Ivy compiler. The parser/translator does not support full grammar of Ivy 1.7. We are working to extend it. If you have questions please let us know.

Reproduce Figure 6

Run python tradeoff_figure.py. The output figure is saved at tradeoff.png

Structure

  • protocols/: The 14 distributed protocols in Ivy. The mapping between protocol names in the paper and acronyms in this repository is given below.

    protocol name acronym
    async lock server multi_lock_server
    chord ring maintenance chord
    database replication database_chain_replication
    decentralized lock decentralized_lock
    distributed lock distributed_lock
    hashed sharding shard
    leader election leader
    learning switch switch
    lock server lock_server
    Paxos paxos
    permissioned blockchain blockchain
    Ricart-Agrawala Ricart-Agrawala
    simple consensus consensus
    two-phase commit two_phase_commit
  • src-py/: The python source codes for protocol simulation

    • translate.py: parse an Ivy file and emits a Python simulation script
    • translate_helper.py: provides functionality for translate.py
    • ivy_parser.py: parse an Ivy expression and generates a syntax tree, used by translate.py
  • src-c/: The C++ source codes for invariant enumeration and refinement

    • main.cpp: the top-level handler
    • basics.h/cpp: define types and data structures (e.g., how an invariant is represented)
    • preprocessing.h/cpp: reads and process the trace file and configuration file
    • Solver.h/cpp: the core of DistAI. Implements template projection, invariant enumeration, and invariant projection
    • InvRefiner.h/cpp: interact with Ivy to refine the invariants using counterexamples
    • Helper.h/cpp: provides functionality for other files

About

DistAI: Data-Driven Automated Invariant Learning for Distributed Protocols

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages