Skip to content
bsommersPublic

About

Bounded Invariant Logic (bil): specify, check and prove programs and state machines. Guarded commands, ontologies, LTL model checking, SMT proofs (z3/cvc5), Verus and native compilation. Apache-2.0.

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

bil — Bounded Invariant Logic

bil — Bounded Invariant Logic

bil is a mathematically grounded, statically typed formal verification, ontology, and functional data language written in Rust. It unifies:

  1. Correctness by Construction (Dijkstra GCL & Refinement Calculus):
    • Guarded Command Language (if ... fi, do ... od) with loop invariant and termination variant (bound function). A recursive fn with a variant is proved by induction on it.
    • Weakest Precondition (wp) verification condition generator & bounded solver (bil verify).
    • Formal Refinement (spec and refines / ⊑), proving concrete implementations satisfy abstract First-Order Logic specifications.
  2. True Nondeterminism ([] / ▯ & choose):
    • Guarded alternatives ([]) evaluate all guards simultaneously and choose nondeterministically among enabled branches—verified demonically at proof time and explored exhaustively at model-check time.
    • Nondeterministic selection (choose x in S : P(x)) defers implementation details in high-level designs.
  3. Foundation for Formal Methods (system & Explicit-State Model Checking):
    • Reactive concurrent state machines (system) with state, invariant, variant, terminal, and interleaved guarded transition blocks (SPIN / Promela style). A clock and per-phase deadlines state response times in controller scans, checked by the same model checkers.
    • Exhaustive BFS state-space explorer (bil model-check) checking safety invariants, deadlock freedom ($\neg BB$), and progress variants with shortest-path counterexample traces.
  4. OntoLogic Taxonomies, First-Order Logic & Functional Pipelines:
    • BFO-compatible concept hierarchies (<:) with compile-time DAG cycle linting and nominal subtyping inside Hindley-Milner type inference.
    • Dual ASCII / Unicode logical syntax (forall/∀, exists/∃, =>/⇒, <=>/⇔, &&/∧, ||/∨, !/¬, []/▯, |>/▷).
    • Built-in .logic S-expression importer (bil import-ontologic <file.logic>).

Which commands need an SMT solver

bil includes an in-repo SMT decision procedure, bil-smt (src/bil_smt.rs), for its decidable fragment: quantifier-free linear integer arithmetic (QF_LIA with div/mod/abs), booleans, ite, let, string and entity equality, uninterpreted functions over Entity, and universal quantifiers forall over Entity (instantiated over the declared Entity constants). With --prover auto (the default), bil tries an installed external solver (z3, cvc5, vampire, looked up in BIL_<NAME>_PATH, BIL_SOLVER_DIR, ~/.local/bin, then PATH) first and falls back to bil-smt when none is found, labelling proofs PROVED (by bil-smt). When z3 answers unsat, bil extracts z3's (get-proof) refutation certificate and checks every deduction step and arithmetic theory lemma in src/proof_check.rs before accepting PROVED; an unverified or forged certificate downgrades to unknown. All 14 domain examples in examples/domains/ verify, solve, and model-check --bmc with no external solver installed. Queries outside the bil-smt fragment (such as universal quantifiers over Int in examples/recursive_contracts.bil or examples/security_policy.bil, or nonlinear integer multiplication) return unknown from bil-smt and need an external solver (or --allow-bounded on verify); verify, solve, and model-check --bmc all exit 1 when no verdict is produced. check, run, vm, build, emit-verus and explicit-state model-check do not use an SMT solver. Measured details: docs/SOLVER-MEASUREMENT.md.


CLI Usage

cargo run -- check <file.bil>                    # OntoLogic DAG + contradiction linter + HM typechecker
cargo run -- solve <file.bil> [--subsumes C P]   # SMT-LIB2 ontology consistency & subsumption prover (z3/cvc5/vampire/bil-smt)
cargo run -- verify <file.bil> [--allow-bounded] # Dijkstra WP, Refinement & Verus proof verifier (Bounded + SMT); exits 1 on bounded-only obligations unless --allow-bounded
cargo run -- model-check <file.bil>              # Explicit-state + LTL temporal (`~>`, `eventually`) model checker
cargo run -- run <file.bil> [--seed N] [--trace] # Tree-walk interpreter with nondeterministic trace
cargo run -- vm <file.bil> [--dump-bytecode]     # Execute Ghost-Erased LIR on the Register/Stack Bytecode VM
cargo run -- build <file.bil> [-o <out_bin>]     # Compile Ghost-Erased LIR to a standalone native ELF binary
cargo run -- dump-ir <file.bil> [--level all]    # Inspect 3-Level IR (HIR -> VIR -> LIR)
cargo run -- emit-verus <file.bil>               # Emit Verus Rust verification code (`verus! { ... }`); a `system` becomes a `step_<i>` fn per transition plus a `next` relation
cargo run -- import-ontologic <file.logic>       # Transpile OntoLogic .logic files into .bil
cargo run -- all <file.bil> [--seed N] [--trace] # Run check + verify + model-check + run
cargo run -- repl                                # Interactive REPL

What emit-verus proves for a system

For each system, bil emit-verus emits one step_<i>(&mut self) function per transition (it requires the invariants and the guard, and ensures the invariants and the updates) and a next(pre, post) relation. When Verus accepts the file, every safety invariant is inductive over the emitted steps. Not covered: LTL liveness properties (~>, eventually), which stay with model-check; bugs in axioms that only hold at runtime; and the link from next to your own hand-written Rust, which is left to you (prove that your code refines next). All 14 examples/domains systems verify; the numbers in them are illustrative. Of the 11 seeded bugs in examples/domains/seeded_bugs, Verus rejects the 6 safety bugs (tests/verus_emit.rs); the other 5 are out of scope (2 violate LTL liveness, 3 are runtime-axiom bugs the transition system does not contain). See docs/ARCHITECTURE_AND_VERUS.md §3.

Local CI

There is no hosted CI. Run the gate before pushing:

scripts/ci.sh              # clippy -D warnings, tests under coverage (78% line floor), Verus emit tests (or `verus: skipped`), cargo audit
scripts/ci.sh --fuzz 300   # also fuzz lex/parse/check for 300 s each (nightly + cargo-fuzz)
git config core.hooksPath .githooks   # optional: run scripts/ci.sh automatically on git push

Requires cargo-llvm-cov, cargo-audit and z3 (on PATH or in ~/.local/bin). Verus is optional: with verus on PATH (or $VERUS) the gate also checks the emitted Verus code, and fails if its version differs from the one pinned in scripts/VERUS_VERSION; without it the step prints verus: skipped.

Practical Application Examples (examples/)

  • examples/smart_grid.bil — Industrial IoT & Smart Energy: BFO concept hierarchy, FOL axioms, WP-verified nondeterministic pressure-bleed do ... od controller, and |> telemetry pipelines.
  • examples/mutex_protocol.bil — Distributed Protocols: Peterson's mutual exclusion protocol verified for safety and deadlock freedom via bil model-check.
  • examples/arbiter_controller.bil — Hardware & Digital Controllers: Dual-channel asynchronous bus arbiter with overlapping nondeterministic request guards and progress variant.
  • examples/gcd_refinement.bil — Verified Algorithms & Refinement: Dijkstra's GCL greatest-common-divisor proved to refine an abstract FOL specification (refines gcd_spec).
  • examples/security_policy.bil — Zero-Trust Cloud Policy Auditing: FOL compliance axioms and nondeterministic failover selection (choose).

License

Licensed under the Apache License, Version 2.0. See LICENSE and NOTICE.

About

Bounded Invariant Logic (bil): specify, check and prove programs and state machines. Guarded commands, ontologies, LTL model checking, SMT proofs (z3/cvc5), Verus and native compilation. Apache-2.0.

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages