chase

Contract-based Heterogeneous Analysis and Systems Exploration

View project on GitHub

Using CHASE

CHASE can be used in four ways, which share the same operations and the same names:

  • the console of logics_tool, which reads a specification file and runs commands interactively or from a script;
  • the Python package chase_cps;
  • the command line chase-cps, which runs checks on a specification file;
  • the MCP server, which gives the operations to AI agents.

The console writes the input files of the external tools (e.g. an SMV model for nuXmv), to be run by hand. The Python package, the command line, and the MCP server run the tools and return the result, with a counterexample when a check fails.

Inputs and outputs

What CHASE reads, what it does with each, and what it gives back. Every input becomes the same Contract (and, for a design, a Model or a C function as its implementation), so every check works on all of them.

Input What it says Read by Drawn by chase-cps view Checked with
.ltl (the specification language) contracts: variables, assumptions, guarantees, named constants the parser of CHASE (C++) the contracts, composed by their ports, refinements, quotients; box and line of the file both ways nuXmv or NuSMV (LTL), z3 (bounded formulas, reals), slugs (GR(1))
.json contracts (Contract.to_dict) Contract.from_dict the same, without lines the same
.sv, .sva with assume / assert property contracts in SystemVerilog Assertions parse_sva the contract of each module the same
.v, .sv with no assertion an RTL module (a model) Yosys (YoWASP) the module: ports and register state machine nuXmv (M ⊨ C)
.c with clauses (ESBMC, CBMC, ACSL) a contract and an implementation for each function load_c each function as a component, with its code; a function with no clause has the contract (⊤, ⊤), and its M ⊨ C checks the code alone ESBMC or CBMC
FILE.c:FUNCTION a C function (a model): one call, or one call per step CFunction inside the box of its contract, with its code ESBMC or CBMC
.smv with LTLSPEC, INVARSPEC a model and its specifications load_smv the module as a component, each specification a term nuXmv or NuSMV
.smv, JSON state machine, slugs controller a model Model.from_smv, Model.from_dict, Model.from_controller inside its contract (--implementation) or beside it (--environment): the state machine nuXmv or NuSMV (M ⊨ C, E ⊨ A)
domain-specific language (dsl_tool) requirements from patterns load_dsl from Python (viz.show) slugs
Python any of the above chase_cps viz.show all
Output Given by Where
verdict (valid, invalid, sat, unsat, realizable, …, unknown with a reason) every check Result.status; a line of chase-cps check; the tag of a box (green, red)
counterexample (the states of a prefix, then of a loop repeated forever) a check that fails Result.trace; the table of the panel and the values on the wires of the diagram
core (the terms in conflict) unsat_core, unrealizable_core, verify(core=True) Core.core; the terms in red in the box
controller (a state machine) synthesize a Model; JSON; drawn as a state machine
counter-strategy of the environment is_realizable, synthesize on an unrealizable contract Result.counter_strategy
values of named constants repair Repair.values; the panel (Apply writes them into the file)
robustness (how much a trace satisfies a formula) robustness a number
results kept chase-cps view --check FILE.results.json, next to the file
diagram chase-cps view, viz.show an HTML page, its JSON (--format json), SVG and PNG from the page
files for other tools to_smv, to_smt, to_gr1, to_sva, to_c SMV (nuXmv, NuSMV), SMT-LIB, slugs and gr1c, SVA checkers (Jasper), C programs (ESBMC, CBMC)

Specification files

The specification files (.ltl) are written in the logics language of CHASE. They are read by the console, by chase_cps.load_spec, and by chase-cps check.

NAME: arbiter;

CONTRACT Spec:
    input boolean variable req;
    output boolean variable grant;
    input integer (0:3) variable n;
    Assumptions:
        G(F(!(req)));
    Guarantees:
        G(req -> F(grant));
  • NAME: name; names the system; CONTRACT name: starts a contract.
  • Variables: input or output, boolean, integer (low:high), or real, then variable name;. An integer without a range ranges over 0 to 16; load_spec and parse_spec warn when an integer is compared with a constant outside its range, since the comparison then has the same value at every step. Declarations outside the contracts are shared: each contract gets those it uses. A real is declared without a range (the Python package rejects real (low:high): write the range as an assumption). Constants are declared as integer constant N 5; or real constant K 2.5;, and propositions as proposition p is x > 3;.
  • Assumptions: and Guarantees: list formulas, each ending with ;.
  • Formulas: ! (or ~), & (or /\), | (or \/), ->, <->, G, F, X, U, R, true, false, the relations = != < <= > >=, the arithmetic + - * /, and x' for the value of x in the next step. # starts a comment.
  • G, F, U, and R take an interval of steps: G[0,3] p is p now and in the next three steps, F]1,4] p is p in one of the steps 2 to 4 (] or [ facing out leaves the bound out). The bounds are whole numbers, and the Python package unfolds the operator into X: G[0,2] p is read as p, X p, X X p.
  • P(...) (a probability) is read by logics_tool, but no check takes it: the Python package refuses a contract that has one.

The operators have the precedence of LTL tools (Spot, NuSMV, nuXmv), the same as in Python, from the tightest: ! G F X, then U R, &, |, ->, <->; U, R and -> group to the right. So G a -> b is (G a) -> b; write G (a -> b). Before 0.5.1 the logics language had its own precedence (all the binary operators at the same level, and G, F, X looser than them); the files of the demos have parentheses and read the same.

A problem written in the domain-specific language of CHASE (the patterns of electric power systems, DATE18/ and FDL2024/ in the demos) is read by chase_cps.load_dsl(path) into one contract, with the formulas its patterns give, named after the file (or name=); the architecture graph of the problem is left out.

Formulas in Python

The Python package, the command line (JSON files), and the MCP server read formulas in the standard LTL syntax: the same operators, plus W (weak until) and the aliases [] (G), <> (F), &&, ||, =>, <=>, ==. They have the usual precedence, from the loosest: <->, ->, | xor, &, U R W, the unary operators, the relations, << >>, + -, * / mod, ::, the bits x[7:0]. -> and U R W group to the right. G, F, U, R take an interval of steps as in specification files (G[0,3] p, F]0,2] p, p U[1,2] q), unfolded into X. So G a -> b is (G a) -> b, in Python and in specification files. Names cannot be keywords of either syntax (G, F, X, U, R, W, P, NAME, CONTRACT, mod, xor, …). Numbers may have a fraction (20.5); they are read exactly. The operators of words are below (Words).

x' is the value of x at the next step, and past(x, n) its value n steps before, for a variable of any type: G X X (y = past(x, 2)) says that y is x delayed by two steps. In the first n steps past(x, n) is any value of the type, so write it under X as here. The model checkers keep the past values in history variables; the contract algebra treats a formula with past as one proposition. GR(1) synthesis (slugs) and the logics language do not take it.

A contract is built from strings or from a dictionary (the JSON format of the command line and of the MCP server):

from chase_cps import Contract

c = Contract.from_strings(inputs=["req"], outputs=["grant"],
                          assumptions=["G F !req"],
                          guarantees=["G (req -> F grant)"], name="Spec")
d = Contract.from_dict({"name": "Spec", "inputs": {"req": "bool", "n": [0, 3], "v": "real"},
                        "outputs": {"grant": "bool"},
                        "assumptions": ["G F !req"],
                        "guarantees": ["G (req -> F grant)"]})

SystemVerilog Assertions

parse_sva reads the assume property and assert property statements of SystemVerilog (a module, a bind file, or the statements alone) as a contract: the assumptions and the guarantees. to_sva writes a contract as a checker module that any tool reading SVA can check, formal or simulator. Nothing in either is specific to a tool.

from chase_cps import Contract, ltl, parse_sva, to_sva

r = parse_sva("""
module arbiter (input logic clk, input logic rst, input logic req,
                output logic gnt, output logic [7:0] count);
  default clocking @(posedge clk); endclocking
  default disable iff (rst);
  A0: assume property (req |=> !req);
  G0: assert property (req |-> ##[1:2] gnt);
  G1: assert property (gnt |=> count == $past(count) + 1);
endmodule""")
print(r.contract.inputs, r.contract.outputs)
for p in r.properties:
    print(p.label, ltl.to_str(p.formula))
print(r.skipped)                    # the statements not read, with the reason

c = Contract.from_dict({"name": "Arb", "inputs": {"req": "bool"},
                        "outputs": {"gnt": "bool", "count": "word[8]"},
                        "assumptions": ["G (req -> X !req)"],
                        "guarantees": ["G (req -> X gnt | X X gnt)",
                                       "G (gnt -> count' = count + 1)"]})
print(to_sva(c, reset="rst", bind="arbiter"))

It prints, for the first property, A0 G (req -> rst | X (req -> rst)): disable iff (rst) is in the formula. The checker written for Arb:

module Arb_sva (
  input logic clk,
  input logic rst,
  (* chase = "input" *) input logic req,
  (* chase = "output" *) input logic gnt,
  (* chase = "output" *) input logic [7:0] count
);
  // assumptions
  A0: assume property (@(posedge clk) disable iff (rst)
    req |=> (!(req)));
  // guarantees
  G0: assert property (@(posedge clk) disable iff (rst)
    req |-> (((nexttime (gnt)) or (nexttime (nexttime (gnt))))));
  G1: assert property (@(posedge clk) disable iff (rst)
    gnt |=> ((count == ($past(count) + 8'd1))));
endmodule

bind arbiter Arb_sva Arb_sva_i (.*);

The attribute (* chase = ... *) keeps the role of each signal for parse_sva; tools ignore it. In to_sva, + 8'd1 keeps the arithmetic of 8 bits that the formula has.

Reading:

  • One step of LTL is one cycle of the clock. An assertion is checked at every cycle: assert property (p) is the guarantee G p, initial assert property (p) is p. assume property and restrict property are assumptions; cover property is kept apart (covers).
  • The widths are those of Verilog. The operands are extended to the width of the context first, so in count == $past(count) + 1 the sum has 32 bits (as the constant 1) and does not wrap around: the property fails when count goes from 255 to 0. Vectors are words, 1-bit signals Booleans.
  • $past(e, n), $rose, $fell, $stable, $changed, $onehot, $onehot0, $countones. A property that looks before the first cycle is checked from the cycle where the past exists (from_cycle of the property): x == $past(x) from cycle 1. Values one cycle apart are written with x', values further apart with past(x, n): y == $past(x, 2) is G X X y = past(x, 2), from cycle 2.
  • Sequences of bounded length: ##n, ##[m:n], [*m:n], and, or, intersect, throughout, within, first_match. ##[m:$] is read in an antecedent and in a strong sequence. In a consequent, as in a |-> ##[1:$] b, it is weak in an assert and never fails, so it is not read: write a |-> s_eventually b.
  • disable iff (r) passes the attempt when r holds before it fails; default clocking and default disable iff apply.
  • Named properties and sequences (with arguments) and assign or wire x = e definitions are put in place. parameters gives the values of parameters.
  • A contract has one clock: with several, clock chooses one (the clock of most properties by default) and the properties of the others are skipped.
  • The directions come from inputs or outputs (names, or a dictionary of types), then from the ports of the module; signals without a declaration are read as 1-bit signals and listed in undeclared.
  • Packed arrays are words: logic [3:0][7:0] x has 32 bits, x[2] is bits 23 to 16. Hierarchical names are read as one name: u1.state is u1__state, and names maps them back (to_sva(..., names=r.names) connects them in the bind statement).

Not read, and listed in skipped with the reason: local variables, [->n] and [=n], unbounded repetition, unpacked arrays, x and z digits, immediate assertions, and the assertions inside generate blocks (generate, if, for at the level of the module).

Writing: a formula G p is checked at every cycle, any other formula once, at the first cycle (initial); past(x, n) is $past(x, n), the same once the past exists. Words are vectors (logic [7:0]), integer ranges int with their range assumed (inputs) or asserted (outputs); real variables cannot be written. reset disables the properties while it holds ("rst", "!rst_n"), and bind adds a bind statement that puts the checker in a design module, its ports connected by name.

The meaning is that of the standard, IEEE 1800-2017 (chapter 16, and Annex F for disable iff), not that of a tool. Tools may differ in corner cases: when the failure of an attempt is already decided by the values before a reset, but a sequence of the attempt is still running when the reset comes, the standard gives a failure and some tools (Jasper) give a disabled attempt. To compare with a tool, run its checks on the SVA. The reading is tested against a reference interpreter of the standard on random properties and traces, against Verilator, and against Jasper (each property and the SVA written back from its contract proved equivalent); a contract written and read back is equivalent (nuXmv).

Three layers

The operations of CHASE are in three layers:

  1. Contracts and their algebra. The operations that build a contract from contracts (composition, conjunction, quotient, …). They hold for any assume-guarantee contracts and are computed by the core library, in closed form, without a solver.
  2. Checks. The checks on contracts (refinement, compatibility, consistency, implementation) reduce to queries on formulas of a theory: validity (implies) and satisfiability (is_satisfiable), with their cores. The back ends decide them: nuXmv, or NuSMV, for LTL over Boolean, integer, and real variables.
  3. GR(1) synthesis. Realizability, synthesis, and the analyses built on them (unrealizable cores, well-separation, vacuity). They are about one way of using contracts, reactive synthesis from the GR(1) fragment of LTL with slugs, not about contracts in general.

In Python the layers are the modules chase_cps.contract (the Contract and its methods), chase_cps.checks and chase_cps.logic, and chase_cps.gr1; all the names are also in chase_cps. The operations are named with verbs: the operations of the algebra return a new contract, the checks read as predicates (refines(a, b): does a refine b?).

1. Contracts and their algebra

Operation logics_tool Python chase-cps check MCP tool
composition ∥ compose C1 C2 R c1.compose(c2) C1+C2 in a contract argument compose
conjunction ∧ conjoin C1 C2 R c1.conjoin(c2)   conjoin
disjunction ∨ disjoin C1 C2 R c1.disjoin(c2)   disjoin
merging • merge C1 C2 R c1.merge(c2)   merge
quotient / divide C1 C2 R c1.divide(c2)   divide
separation ÷ separate C1 C2 R c1.separate(c2)   separate
implication → imply C1 C2 R c1.imply(c2)   imply
coimplication coimply C1 C2 R c1.coimply(c2)   coimply
reciprocal C⁻¹ invert C R c.invert()   invert
adding an assumption b·C   c.assume(b)   assume
adding a guarantee C·b   c.ensure(b)   ensure
saturation saturate C c.saturate()   saturate
(formula simplification) simplify C c.simplify()   simplify

Implication and coimplication are the adjoints of conjunction and disjunction, as the quotient and separation are of composition and merging (Incer, Benveniste, Sangiovanni-Vincentelli, arXiv 2309.08875, Table 1). c1.imply(c2) is the largest contract C such that C conjoined with c1 refines c2. The reciprocal (G, A) is the contract seen from its environment. c.assume(b) gives (b & A, b -> G), an abstraction of c, and c.ensure(b) gives (b -> A, b & G), which refines c.

c1.compose(c2, discharge=True) keeps the terms of the two contracts instead of the closed form (Incer, PhD thesis 2022, Algorithm 2). When c1 drives the inputs of c2 and not the reverse, the assumptions of c2 implied by the assumptions and guarantees of c1 are dropped, then the redundant terms. This variant uses the checks of layer 2 (one implication per test), so it needs nuXmv. The result is an abstraction of the composition: a refinement proved on it holds for the composition; a failed one may not.

c1.merge(c2, discharge=True), c1.divide(c2, discharge=True), and c1.conjoin(c2, discharge=True) keep the terms too, and the result is the same contract as the closed form: only composition gives an abstraction. The merge is (A1 & A2, G1 & G2), whose saturation is the merge. The quotient assumes the assumptions of c1 and the guarantees of c2, and guarantees the guarantees of c1 and the assumptions of c2; the assumptions of c2 implied by those of c1 are discharged first, and when some are left, each guarantee g of c2 is assumed as A2’ -> g, with A2’ the ones left. Then the redundant terms are dropped. In the conjunction, each guarantee of c1 is guaranteed under A1’, the assumptions of c1 that those of c2 do not imply (under A1 | A2, A1 is the same as A1’), and the same for c2; the assumption is A1’ | A2’ with the other terms of A1 and A2. When the assumptions of one contract imply those of the other, there is no disjunction left: with the same assumptions, the conjunction is (A, G1 & G2). The closed forms are rarely GR(1); the terms often are, so use these before is_realizable and synthesize. Disjunction and separation have no such form: their guarantee or their assumption is a disjunction (G1 | G2, (A1 & G2) | !(G1 & A2)).

The console also accepts the names of its first version: conjunction for conjoin, quotient for divide, and refinement for refines. It has show C to print a contract (print(c) in Python).

In the console, the variables of two contracts are matched by name (the default), by a map entered by hand (manual as last argument), or by a map read from a file (its name as last argument). In Python, variables with the same name are the same variable, and c.rename({...}) renames them. A variable shared as integers of two ranges (a port of 0..100 feeding one of 0..9) is one integer of the union of the ranges; in each contract, its own range becomes a term, an assumption where it is an input and a guarantee where it is an output, so the checks say whether the values fit. Other types that differ are an error.

Named constants

A contract may name numbers that its formulas use: constants={"limit": 4} in Python ("constants" in JSON), integer constant limit 4; or real constant limit 4.5; in a specification file. The checks read the formulas with the values. c.instantiate({"limit": 5}) gives the contract with another value, and c.terms the formulas with the names. A composition keeps the constants of both contracts (a constant of both has one value); the other operations of the algebra keep only the values.

2. Checks

Checks on contracts

Check logics_tool Python chase-cps check MCP tool
refinement ⪯ refines C1 C2 file refines(c1, c2) --refines C1 C2 refines
A and G hold together (implies compatibility and consistency) verify C file verify(c) --verify (default) verify
compatibility   is_compatible(c)   is_compatible
consistency   is_consistent(c)   is_consistent
implementation M ⊨M C   is_implementation(m, c) --implementation MODEL C is_implementation
environment E ⊨E C   is_environment(e, c) --environment MODEL C is_environment
receptiveness of a state machine   is_receptive(m, c) --receptive MODEL C is_receptive
redundant terms   remove_redundant(c)   remove_redundant

A contract (A, G) is read saturated, as A -> G. refines(c1, c2) checks that A2 -> A1 and (A1 -> G1) -> (A2 -> G2) are valid. A contract is compatible when some environment satisfies A, and consistent when some behavior satisfies A -> G. The two can hold with different behaviors: a contract can be compatible and consistent although its guarantees cannot hold when its assumptions do. verify checks that A & G is satisfiable: some environment meets the assumptions and some component the guarantees, on the same behavior. This implies compatibility and consistency (with the same witness); when A & G is unsatisfiable, verify also checks the two, to tell whether the assumptions alone cannot hold, and with core=True gives the terms that conflict. M is an implementation of the contract (is_implementation(m, c)) when M & A -> G is valid, and E is an environment of it (is_environment(e, c)) when E -> A is valid; M and E are LTL formulas over the variables of the contract, or state machines (see below). The names before 0.4.2, implements(m, c) and accepts(c, e), still work. remove_redundant(c) drops the assumptions implied by the other assumptions, and the guarantees implied by the assumptions and the other guarantees. Which terms it may drop depends on what the contract is for next:

Next Call Keeps
the algebra and the checks (compose, refines, verify, …) remove_redundant(c) A -> G
synthesis (is_realizable, synthesize, …) remove_redundant(c, synth=True) realizability and the controllers

The two differ only when the assumptions are wrong, for instance unsatisfiable, or constrain the outputs; each one keeps what the other may change (see “Redundancy in the GR(1) game” below). With core=True, each removed term comes with a minimal set of the terms that imply it.

The console writes the input file of nuXmv for verify and refines, to be run by hand (for verify, three LTLSPEC: the negations of A, of the guarantees, and of A & G; each one false means that the property holds); the Python package, the command line, and the MCP server run nuXmv and return the result.

State machines

An implementation or an environment can be a state machine, a Model (chase_cps.models): a program in SMV, the input language of nuXmv, with its variables, initial states, and transitions. It describes discrete behaviors, one step at a time, like the traces of the contracts. A model comes from SMV text or a file (Model.from_smv), from a controller of synthesize (Model.from_controller), or from a state machine in JSON (Model.from_dict): at each step, in its state, the machine takes a transition whose when holds, sets the outputs of that step, and moves to the next state. is_implementation(m, c) checks that every behavior of m satisfies A -> G, and is_environment(e, c) that every behavior of e satisfies A; the model declares the variables of the contract (inputs as IVAR or VAR).

A machine that refuses an input has no behavior with it: it may implement a contract only because the input never happens. is_receptive(m, c) checks that in every reachable state, every next value of the inputs that the safety assumptions allow has a transition from which the machine can go on forever, and that every initial value allowed by the initial assumptions starts a behavior (a CTL check with BDDs; the inputs must be finite). The other assumptions are not used, which asks for more inputs than OCRA does. not_receptive comes with the state and the input refused.

from chase_cps import Contract, Model, is_implementation, is_receptive

spec = Contract.from_strings(inputs=["req"], outputs=["grant"], name="Spec",
                             guarantees=["G (req -> X grant)"])
blocking = Model.from_smv('''MODULE main
IVAR
  req : boolean;
VAR
  grant : boolean;
ASSIGN
  init(grant) := FALSE;
TRANS
  next(grant) = req
TRANS
  !(grant & req)
''', name="Blocking")
r = is_receptive(blocking, spec)
print(is_implementation(blocking, spec).status, r.status, r.details["input"])
valid not_receptive {'req': True}

The machine implements the contract only because, while it grants, it refuses a request.

RTL

A Verilog or SystemVerilog module is a state machine too. Model.from_rtl(files, top) reads it with Yosys (pip install chase-cps[rtl] installs it, compiled to WebAssembly; a yosys in the path is used first): Yosys flattens the design, maps the memories to registers, and writes it in SMV. The ports are the variables of the contracts: a 1-bit port is a Boolean, a wider one a word. One step is one cycle of the clock, and the clock inputs (clk, clk_i, clock, or clocks=[...]) are left out.

from chase_cps import Contract, Model, is_implementation

m = Model.from_rtl(["bsg_dff_reset.sv", "bsg_dff_en.sv", "bsg_one_fifo.sv"],
                   "bsg_one_fifo", parameters={"width_p": 4}, reset="reset_i",
                   names={"ready_and_o": "ready_o"})
slot = Contract.from_dict({"name": "Slot",
                           "inputs": {"v_i": "bool", "data_i": "word[4]", "yumi_i": "bool"},
                           "outputs": {"v_o": "bool", "data_o": "word[4]", "ready_o": "bool"},
                           "assumptions": ["G (yumi_i -> v_o)"],
                           "guarantees": ["G (v_o & !yumi_i -> X v_o)"]})
print(is_implementation(m, slot).status)

parameters sets parameters of the top module, names renames ports as the variables of the contracts, and defines gives macros. With reset ("reset_i", or "!rst_n" for an active-low reset) the reset holds in the first step only, and the contracts are checked from the next step, the first one after the reset; the reset is then not an input of the model, so the contracts do not list it as an input. Without reset it is an input like the others, and the registers start with any value. The checks are those of nuXmv: they suit small and medium designs.

C functions

A C function is a component that answers once: its parameters are the inputs of the contract, by name, and its return value is the output; a pointer parameter named as an output is written by the function. The formulas of such a contract have no temporal operator. is_implementation takes a CFunction and checks it with ESBMC or, without it, CBMC (chase-cps install esbmc on Linux, brew install esbmc on macOS):

from chase_cps import CFunction, Contract, is_implementation

open("saturate.c", "w").write("""
int saturate(int x, int lo, int hi) {
    if (x < lo) return lo;
    if (x > hi) return hi;
    return x;
}
""")
sat = Contract.from_strings(name="Sat",
                            inputs={"x": (-1000, 1000), "lo": (-100, 100), "hi": (-100, 100)},
                            outputs={"y": (-1000, 1000)}, assumptions=["lo <= hi"],
                            guarantees=["y >= lo & y <= hi", "(x >= lo & x <= hi) -> y = x"])
r = is_implementation(CFunction("saturate.c", "saturate"), sat)
print(r.status, r.backend)       # valid esbmc

The checker calls the function with any values of the inputs, within their types and the assumptions, and checks the guarantees on what it returns. A failure gives the values of a call that breaks them (the trace). The checkers also check the function itself: an arithmetic overflow, a division by zero, or an access out of bounds makes the result invalid, with the property in the reason. Loops are unwound up to unwind times (20, is_implementation(f, c, unwind=100)); a loop that needs more makes the result unknown.

Integers are compared as integers (in long long); a real variable is a double or a float of the function, and its formulas are computed in double, with rounding. Words are not written in C yet. On the command line: chase-cps check spec.ltl --impl saturate.c:saturate Sat.

A function called once per step (a controller) implements a contract over steps too. The contract has no assumption, and each guarantee is a formula of one step phi at some steps: phi, X phi, G phi, or G[a,b] phi. Each step of the system is a call on inputs that nothing constrains, so the function implements the contract exactly when each call satisfies every such phi: the checker checks one call, and a call that breaks one, repeated at every step, is the counterexample.

from chase_cps import CFunction, is_implementation, parse_spec

open("heater.c", "w").write("""
int thermostat(int T) {
    if (T < 74)
        return 3;
    return 0;
}
""")
c = parse_spec("""NAME: t;
CONTRACT Thermostat:
    input integer (0:200) variable T;
    output integer (0:3) variable u;
    Assumptions:
        true;
    Guarantees:
        G[0,9] ((T < 74 -> u = 3) & (T >= 74 -> u = 0));
""")
is_implementation(CFunction("heater.c", "thermostat"), c["Thermostat"]).status   # valid

The result is unknown, with the reason, for a function that keeps a state between calls (a static variable, or a global variable of its file that it uses), and for a contract that does not have this form (T' = T + u - 1 relates two steps).

The contract can be written in the C file, next to the code, in the clauses of ESBMC (__ESBMC_requires(...), __ESBMC_ensures(...) in the body, __ESBMC_return_value) or of CBMC (__CPROVER_requires(...), __CPROVER_ensures(...) between the signature and the body, __CPROVER_return_value), or in ACSL, the language of Frama-C (a comment /*@ requires ...; ensures ...; */ just before the function, with \result, ==>, <==>, and chains such as 0 <= T <= 200; \old, \at, the quantifiers, and behaviors are not read). load_c (it gives {name: (contract, function)}) reads each function of the file as a contract and the function as its implementation: the requires clauses are the assumptions, the ensures clauses the guarantees, the parameters the inputs, the return value the output FUNCTION_out, and *p the output p of a pointer parameter. The ranges of the inputs are those of their C types, narrowed by the bounds the requires clauses give:

from chase_cps import is_implementation, load_c

open("thermostat.c", "w").write("""
int thermostat(int T)
{
    __ESBMC_requires(T >= 0 && T <= 200);
    __ESBMC_ensures(T >= 74 || __ESBMC_return_value == 3);
    __ESBMC_ensures(T < 74 || __ESBMC_return_value == 0);
    return T < 74 ? 3 : 0;
}
""")
c, f = load_c("thermostat.c")["thermostat"]
print(c.inputs, is_implementation(f, c).status)   # {'T': (0, 200)} valid

The clauses are expressions of C over numbers and Booleans (&& || ! == != < <= > >= + - * /); a conditional (a ? b : c) is not read. The clauses on pointers (is_fresh, r_ok, w_ok, rw_ok, assigns) are not part of the contract. The function is checked with the clauses taken out of the code, so either checker checks a file with the clauses of the other. A function with no clause has a contract with no term: its check is that of the code alone (overflow, division by zero, access out of bounds, failed assert).

chase-cps view FILE.c (and the CHASE button of VS Code on a .c file) draws each function as a component with its code, checked: the tag M ⊨ C for each function; with no clause, the contract is (⊤, ⊤) and the check is that of the code alone (no overflow, division by zero, or access out of bounds). A failure shows the call that breaks it, and the term it breaks in red.

SMV models with their specifications

An SMV file of nuXmv or NuSMV with LTLSPEC or INVARSPEC is read as a component: load_smv(path) (in chase_cps.smvspec) gives {name: (contract, model)}: the contract, with no assumption and a guarantee for each specification (LTLSPEC p is p, INVARSPEC p is G p, next(x) is x', V is R), and the model without the specifications as its implementation. The inputs are the IVAR variables, the outputs the VAR and FROZENVAR ones. chase-cps view FILE.smv --check (and VS Code) draws it as a component: each specification is a term, and the one that a counterexample breaks is red. An enumerated type ({idle, busy}) is read as the integers 0, 1, … in the order written, in the contract and in the model (the traces show the numbers), and a DEFINE in a specification is replaced by its definition. CTL (SPEC, CTLSPEC), past operators, and a DEFINE written with case ... esac are not read. An SMV file with no specification is a model, not a contract: it is drawn as the implementation of a contract (--implementation FILE.smv CONTRACT).

Sampled signals: from steps to continuous time

The formulas count steps. When a step is a sample of a continuous signal, taken every period seconds, and each variable changes at most its Lipschitz constant per second, chase_cps.sampled says when a formula that holds at the samples holds at every instant (Fainekos and Pappas, TCS 2009, Corollary 44). sampled(formula, lipschitz, period) gives the stricter formula to check at the samples: under F and U each interval is one step narrower at each end, under G and R one step wider, and each comparison holds with the margin (|a1| L1 + ... + |an| Ln) period (x <= c becomes x + E < c). If the stricter formula holds at the samples, the formula holds in continuous time; if not, nothing is concluded.

from chase_cps.queries import Trace
from chase_cps.sampled import continuous, sampled

print(sampled("G[0,8] (x <= 11)", {"x": 1}, 0.5))     # G[0,9] (x + 0.5 < 11)
t = Trace([{"x": i} for i in range(10)], [])
print(continuous("G[0,8] (x <= 11)", t, {"x": 1}, 1).holds)   # True

The intervals must span more than 3 steps, and the formula must not use X, a primed variable, past(x, n), <->, a Boolean variable, or a comparison that is not linear (the error says which). The stricter formula is a formula like any other: a refinement or a verification with it shows the property in continuous time for every behavior.

sampled(formula, lipschitz, period, known=True) gives the other side: what the samples hold when the formula is known to hold in continuous time. The intervals stay, and a comparison under F, or on the right of U, is weaker by the margin (x >= c becomes x + E >= c): the instant that holds it may fall between two samples.

With a period, the intervals may be written with times: with a period of 0.1 s, G[0s,2s] p is G[0,20] p and F[0ms,500ms] p is F[0,5] p. A time that is not a whole number of steps is refused.

The command line checks a refinement in continuous time:

$> chase-cps check plant.ltl --period 1 --lipschitz x=1 --refines Plant Req

Parameters:

  • --period SECONDS: the time between two steps; the intervals may then be written with times.
  • --lipschitz VAR=RATE ...: how fast each variable changes, per second, or one RATE for every variable. --refines R S then holds in continuous time, between the samples too.

For R <= S, CHASE checks at the samples the assumptions of R and the guarantees of S made stricter (sampled), against the guarantees of R and the assumptions of S made weaker (known=True). A term of R that speaks of the samples themselves (x' = x + u, the model of a plant in steps) stays as it is. The margins are a sufficient condition: the check says valid (it holds between the samples too) or unknown (not shown), never invalid; the same check without --lipschitz says whether it fails at the samples already.

chase-cps view FILE --period SECONDS (or # view: --period SECONDS in the file) draws the steps of a counterexample as times, t = step x SECONDS.

Queries on formulas

Query logics_tool Python chase-cps check MCP tool
validity of phi -> psi   implies(phi, psi, variables)   implies
satisfiability of phi   is_satisfiable(phi, variables)   is_satisfiable
unsat core   unsat_core(c) --core unsat_core

The checks on contracts reduce to these queries, in chase_cps.logic. implies checks validity: phi -> psi holds for every behavior; the answer is valid, or invalid with a counterexample (a behavior that satisfies phi and violates psi). is_satisfiable checks that some behavior (a value of each variable at each step) satisfies the formula; the answer is sat with such a behavior, or unsat. This satisfiability of a formula is not the satisfaction of a contract by a component, which is is_implementation.

When a check fails, a core is a minimal set of terms that explains it: removing any term of the core makes the check pass. unsat_core(c) gives the terms of A & G that cannot hold together. If they are all assumptions, the contract is incompatible; all guarantees, the guarantees contradict each other; both, the guarantees cannot hold when the assumptions do. This is the consistency check of OCRA (ocra_check_consistency -j). The search is delta debugging (Zeller and Hildebrandt, TSE 2002), one call to nuXmv per test. unsat_core(formulas, variables) takes formulas and returns formulas. The checks give the core of their failure with core=True: is_compatible(c, core=True) (the assumptions), is_consistent(c, core=True) (the guarantees), and is_satisfiable(phi, variables, core=True). The result is a Core with a status: found with the core, none when the check does not fail, or unknown with a reason when a test does not finish.

Context

Some formulas are not an assumption of a component nor a guarantee: they hold for every behavior that can happen at all. Examples are the axiom of an encoding of finite traces (alive & (alive U G !alive), where alive is true for the length of the trace), a physical law, or “one tool call at each step”. The checks built on implication and satisfiability take them as context, a formula or a list of formulas, and leave out the behaviors that violate them:

from chase_cps import Contract, verify

FINITE = "alive & (alive U G !alive)"
c = Contract.from_strings(inputs=["alive"], outputs=["a"], name="C",
                          guarantees=["G (alive -> a)", "G (alive -> !a)"])
assert verify(c).status == "sat"     # alive false from the start
assert verify(c, context=FINITE).status == "unsat"

A context is not an assumption. A behavior that violates an assumption satisfies the contract (A -> G); one that violates the context does not count. So is_consistent(c.assume(FINITE)) is still sat, and a refinement check with the axiom as an assumption of both contracts compares other contracts. (verify(c.assume(FINITE)) is unsat, since it checks A & G.) The checks are:

  • implies(phi, psi, variables, context=k): k & phi -> psi;
  • is_satisfiable(phi, variables, context=k): k & phi;
  • is_compatible, is_consistent, verify, refines, remove_redundant, is_environment, is_implementation, and unsat_core (the context is in every test of the search and never in the core).

The variables of the context must be variables of the check. The realizability checks (is_realizable, synthesize, is_well_separated, is_vacuous, unrealizable_core, and remove_redundant with synth=True) do not take a context: whether a formula constrains the environment or the component is a question of roles, which a context does not say.

Formulas over a bounded number of steps

A formula with no G, F, U, R reads a bounded number of steps: X, x', and past(x, n) move by one step or by n, and the intervals of steps (G[0,10] p, F[1,3] p, p U[0,2] q) are written with X. A formula without any of them says something about one step: it is a constraint, and a contract made of such formulas is a static contract (a budget, a sizing, a choice of parts). When z3 is installed (pip install chase-cps[z3]), the checks of such formulas go to z3 instead of nuXmv: verify, refines, implies, is_satisfiable, and the others built on them. The result names z3 as its back end; its trace has the steps that the formulas read, the last one repeated. z3 is exact for linear arithmetic over the integers and the reals, with any Boolean structure (a <= 1 | b <= 1 is not a polyhedron, and is checked as written); words stay with nuXmv. backend="nuxmv" still sends them to nuXmv, and CHASE_BACKEND too.

minimize(objective, constraints) and maximize(objective, constraints) give the best value of a term where the constraints hold, and the values of the variables that reach it. The constraints are a formula, a list of formulas, or a contract (A & G):

from chase_cps import Contract, maximize, minimize

gen = Contract.from_strings(name="Gen", inputs={"n": (0, 20)}, outputs={"p": "real"},
                            assumptions=["n <= 4"], guarantees=["p >= 2.5 * n", "p <= 30"])
best = maximize("n", gen)            # optimal, 4, with n = 4, p = 10
margin = minimize("p - 2.5 * n", gen)  # 0: the guarantee p >= 2.5 n is tight
print(best.status, best.value, best.to_dict().get("values"))

The status is optimal, not_attained (the bound of a strict inequality: minimize("x", "x > 1") is 1), unbounded, infeasible, or unknown with the reason.

When the objective is a formula, its robustness (see Robustness below) is the objective. The smallest robustness of a property under the constraints is its worst case: above 0, every behavior that the constraints allow satisfies the property with that margin; below 0, the trace of the result violates it. The atoms of the formula compare numbers.

from chase_cps import minimize

# a heater: on (u up to 3) while T <= 70; the room loses 1 per step
heater = ["T = 60", "G[0,9] (u >= 0 & u <= 3)", "G[0,9] (T' = T + u - 1)",
          "G[0,9] (T > 70 -> u = 0)"]
worst = minimize("G[0,10] (T <= 75)", heater, {"T": "real", "u": "real"})
print(worst.status, worst.value)     # optimal 3: T reaches 72 at most

Real variables

A variable of type "real" (real variable x;) takes any real value. The checks handle real variables in this order, and the result says in reals which way answered:

  1. regions: when a real variable is only compared with constants (kias > 40, kias' <= 30.5) or with other real variables of the same step (kias = kgs), without arithmetic, only the interval between the constants matters. With the constants c1 < … < ck the variable is replaced by the index of its region among (-inf, c1), c1, (c1, c2), …, ck, (ck, inf); variables compared with each other share their constants, and each interval has one place per variable, so that their order is kept. The answer is exact, traces have real values (one in each region), and realizability and synthesis work: the controller of synthesize gives for each node the values of the variables, the real ones as conditions (30.5 < kias < 40), and the list of the regions.
  2. smt: otherwise the SMT engine of nuXmv checks the formulas with the real variables. It is exact for linear arithmetic; with nonlinear arithmetic (x * y) it often does not finish, so it gets at most 30 seconds. NuSMV has no real type. Realizability and synthesis are unknown in this case.
  3. predicates: when nuXmv gives no answer, each comparison becomes a Boolean variable (x <= 10 and x > 10 are the same one, negated). The abstraction allows values that are impossible (x > 10 and x < 5 at once), so only a valid implication or an unsatisfiable formula is returned as such. With z3 (pip install chase-cps[z3]), the combinations of one or two comparisons that no values satisfy are excluded first, and an invalid or sat answer is checked: z3 looks for real values for every state of the trace. If it finds them, the answer and the trace are those of the real variables (an irrational value, such as a square root, is given as a close fraction); if not, the comparisons of a core are excluded and the check is repeated. The other answers are unknown, with the trace of the abstraction.

Numbers with a fraction compared with integers (n <= 20.5) also need the SMT engine of nuXmv. Without real variables none of this is used.

The console of logics_tool writes the file of verify and refinement and does not run the model checker. When the file has real variables or real numbers, the console says so, and the file starts with a comment: NuSMV cannot read it, and nuXmv checks it with its SMT engine:

$> nuXmv -int refinement.smv
nuXmv > go_msat
nuXmv > check_ltlspec_ic3

go, followed by check_ltlspec, stops with an error on such a file.

Words

A word is a bit vector of a fixed width, as a register of a circuit: "word[8]" is unsigned (0..255), "signed word[8]" is in two’s complement (-128..127). They are the words of nuXmv (unsigned word[8]) and the vectors of SystemVerilog (logic [7:0], logic signed [7:0]). Their arithmetic wraps around: for a word[8] x equal to 255, x + 1 = 0. The operators:

Operator Meaning
+ - * / mod arithmetic modulo 2^n (/ and mod truncate towards 0 for signed words)
& \| xor ! bitwise; in a relation, parenthesize them: (x & y) = 0
<< >> shifts by a number (>> keeps the sign of a signed word)
x :: y concatenation: x on the high bits, unsigned, the sum of the widths
x[7:4], x[3] bits, unsigned; a single bit can be used as a Boolean
= != < <= > >= comparisons, signed or unsigned as the operands

Both operands of an operation or a comparison have the same width and signedness; an integer constant takes the type of the other operand (x = 5) and must fit in it. Change a width with bits (y[7:0]) or a concatenation of words (x :: y). A formula that does not type is refused when the contract is built.

from chase_cps import Contract, refines

inc = Contract.from_dict({"name": "Inc", "inputs": {"a": "word[8]"},
                          "outputs": {"b": "word[8]"},
                          "guarantees": ["G (b = a + 1)"]})
odd = Contract.from_dict({"name": "Odd", "inputs": {"a": "word[8]"},
                          "outputs": {"b": "word[8]"},
                          "assumptions": ["G (a[0] = 0)"],
                          "guarantees": ["G (b[0] = 1)"]})
print(refines(inc, odd).status)     # valid: a even, so a + 1 is odd

The checks give the words to nuXmv (and NuSMV) as they are; the values in the traces are integers. The contract algebra of the core library reads the logics language, which has no words: each comparison over words goes to it as a Boolean variable and comes back after the operation, which only combines the formulas, so the result is the one of the formulas. For the same reason a contract with words cannot be written in the logics language (to_spec). State machines (Model) may declare words. slugs does not take them: GR(1) synthesis needs integer ranges.

Robustness

The robustness of a formula on a trace says how much the trace satisfies it (a positive number) or violates it (a negative number), in the unit of the terms. It is the quantitative semantics of signal temporal logic, in discrete time, on the traces of the checks:

  • a comparison is the distance to its boundary: x <= 30 is 30 - x, x >= 10 is x - 10, x = c is -|x - c|, and x != c is |x - c|;
  • ! is the opposite, & the minimum, | the maximum;
  • X is the value at the next step, G the minimum over the steps to come, F the maximum, and U the maximum over the steps j of the right side at j, bounded by the left side before j.

0 is the boundary: the formula may hold or not (holds says which). A Boolean variable is inf when true and -inf when false. So the robustness is useful only for formulas that compare numbers (integers, reals, words): for a contract over Booleans it says no more than whether the formula holds.

from chase_cps import Contract
from chase_cps.queries import Trace
from chase_cps.robustness import holds, robustness, violated

trace = Trace(prefix=[{"p": 20}], loop=[{"p": 27.5}, {"p": 25}])  # 20, then 27.5, 25, ...
assert robustness("G (p <= 30)", trace) == 2.5      # p stays 2.5 below 30
assert robustness("F[0,1] (p >= 27.5)", trace) == 0  # reached, on the boundary
assert holds("F[0,1] (p >= 27.5)", trace)
c = Contract.from_strings(inputs={"n": (0, 9)}, outputs={"p": "real"},
                          guarantees=["G (p <= 26)", "G (p >= 10)"])
c.robustness(trace)                          # the assumptions, the guarantees, A -> G
assert violated(c.guarantees, trace, c.variables) == [{"term": "G (p <= 26)", "robustness": -1.5}]

A refinement that fails gives the terms that its counterexample violates (violated in the result): the assumptions of the refined contract, or the guarantees of the abstract one, each with its robustness when it compares numbers (None otherwise). For instance a guarantee G (p >= 12) violated with -4 is missed by 4 at some step of the trace.

A trace whose loop is empty repeats its last state. past(x, n) is the history variable of nuXmv in the trace (chase_past2_x) when it is there, else the value n steps before; it has none in the first n steps. minimize and maximize find the smallest and the largest robustness of a formula over the behaviors that some constraints allow (see Formulas over a bounded number of steps).

3. GR(1) synthesis

Analysis logics_tool Python chase-cps check MCP tool
realizability   is_realizable(c) --realizable C is_realizable
synthesis synthesize C file solver synthesize(c) --synthesize C synthesize
unrealizable core   unrealizable_core(c) --realizable C --core unrealizable_core
well-separation   is_well_separated(c) --well-separated C is_well_separated
vacuity   is_vacuous(c) --vacuous C is_vacuous
redundancy in the GR(1) game   remove_redundant(c, synth=True)   remove_redundant with synth

These analyses are about reactive synthesis from contracts in the GR(1) fragment of LTL, with slugs, in chase_cps.gr1. A contract is realizable when a component that controls the outputs can satisfy A -> G against every environment that controls the inputs; this depends on the synthesis approach, and is not a property of contracts in general. The terms must be GR(1): initial (no temporal operator), safety (G f, with X only in f), or justice (G F f). The checks do not take a context: whether a formula constrains the environment or the component is a question of roles, which a context does not say.

is_realizable gives the counter-strategy of the environment when the contract is unrealizable; synthesize also builds the controller. The console writes the input file of slugs or gr1c, which decide realizability and build the controller.

to_gr1(c, tool=...) writes a GR(1) contract as the input of a GR(1) solver, to run by hand, as to_sva does for the tools of SystemVerilog. tool="slugs" (the default) is the file that chase-cps gives to slugs, in the structured format of slugs; tool="gr1c" is the input of gr1c (gr1c -r spec.spc). The inputs are the variables of the environment and the outputs those of the system. Structured slugs has no subtraction or multiplication; gr1c compares an integer only with a constant and starts its domains at 0, so for gr1c a relation with arithmetic or between variables is written as the values that satisfy it, and an integer is written from 0.

Unrealizable cores

unrealizable_core(c) gives a minimal set of guarantees that is unrealizable under all the assumptions. The search minimizes the justice guarantees, then the safety, then the initial ones (QuickCore, Maoz and Shalom, ICSE 2021), with one call to slugs per test. unrealizable_core(guarantees, inputs, outputs, assumptions) takes formulas and returns formulas, and is_realizable(c, core=True) gives the core of an unrealizable result.

Well-separation

A contract is well-separated when the component cannot satisfy it by forcing the environment to violate the assumptions (Klein and Pnueli, HVC 2010; Maoz and Ringert, FSE 2016). A contract that is not well-separated is realizable for a bad reason: the controller may break its environment instead of meeting the guarantees. is_well_separated(c) answers separated or not_separated with the controller that forces the violation. The component must keep its initial and safety guarantees while it forces the violation (Def. 4 of Maoz and Ringert): a violation it can force only by breaking its own guarantees is not a defect of the assumptions. with_guarantees=False leaves the guarantees out (Def. 2, the default before 0.3.2). core=True gives a minimal set of assumptions that causes the problem. The check is one call to slugs. It detects the violations that can be forced from every initial state; those forced only from some reachable state need the winning region, which slugs does not give.

Vacuity

A contract is vacuous when the component can win without an output that a liveness guarantee asks for: the guarantee is discharged by the assumptions and obliges nothing. is_vacuous(c) checks it as a strengthening of the guarantees (Bloem, Chockler, Ebrahimi, and Strichman, FMSD 2021), with at most two calls to slugs per output y:

  • never: Real(A, G + {G !y}), a winning strategy never sets y;
  • eventually: Real(A, G + {!p, G (p -> X p), G (p -> !y), G F p}) with a fresh output p, a winning strategy stops setting y from some step on.

The outputs checked are those that occur only positively in a justice guarantee, or the outputs given. The result is vacuous with each vacuous output, its mode and the strategy, not_vacuous, unrealizable when the contract itself is, or unknown; with core=True, each vacuous output has a minimal set of the temporal assumptions under which the component still wins without it (one deletion pass). Two weaker formulations are not used: the test on a controller M & A -> phi[y <- false] (Kupferman and Vardi) and the rewrite Real(A, G[y <- false]) both call a good controller vacuous when an assumption ties the release of the environment to y, such as G ((req & grant) -> X !req): the controller grants, the release follows, and phi[grant <- false] holds because it granted. Forcing y false in the behavior asks the right question.

from chase_cps import Contract, is_vacuous, ltl

trusting = Contract.from_strings(
    inputs=["req"], outputs=["grant"], name="Trusting",
    assumptions=["!req", "G F !req"],
    guarantees=["!grant", "G (grant -> req)", "G F (!req | grant)"])
r = is_vacuous(trusting, core=True)
v = r.vacuous[0]
print(r.status, v.output, v.mode, [ltl.to_str(t) for t in v.core.core])
vacuous grant never ['G F !req']
The assumption G F !req makes G F (!req grant) hold without any grant.

Redundancy in the GR(1) game

remove_redundant(c, synth=True) removes the terms whose removal does not change the GR(1) specification: its realizability and the controllers that realize it (the inherent vacuity of Maoz and Shalom, ESEC/FSE 2020, which is a redundancy: a term implied by others in the game). Each term is checked against a premise set that depends on its kind (initial, safety, justice) and on its side (assumption or guarantee), one call to nuXmv per term; a safety term is compared with the bodies of the other safety terms only, as a propositional implication over the current and next values. The terms are checked in order against the terms not yet removed, so of two equal terms one is kept. The result has the contract, the removed terms with their part and kind, and with core=True the terms that imply each one.

remove_redundant(c) without synth keeps A -> G instead. The two differ when the assumptions are wrong:

Contract remove_redundant(c) remove_redundant(c, synth=True)
A: G F (x & !x); G: G g, G !g drops both guarantees (A is unsatisfiable): realizable drops nothing: unrealizable, as c
A: G F g; G: G g drops nothing drops G F g: the component keeps G g anyway, but the contract is stronger

In the game, the component must keep its safety guarantees even when the environment breaks its justice assumptions, so these do not imply them; an assumption that the guarantees make hold does not matter in the game, but it does for A -> G.

4. Repair

When a check fails, repair finds values of named constants of the contracts that make it pass, at the least cost, and changes nothing else. The check and its arguments are those of the checks (verify, compat, consist, refines, impl, env, as in to_smv); each parameter is a constant with a range, (low, high) for a real and (low, high, "int") for an integer. The cost is minimize or maximize, a term over the parameters, and by default the change: the sum of |p - p0|.

from chase_cps import Contract, repair

impl = Contract.from_strings(name="Impl", inputs={"x": (0, 9)}, outputs={"y": (0, 20)},
                             guarantees=["y = x + 5"])
spec = Contract.from_strings(name="Spec", inputs={"x": (0, 9)}, outputs={"y": (0, 20)},
                             guarantees=["y <= x + lam"], constants={"lam": 4})
r = repair("refines", impl, spec, parameters={"lam": (0, 10)})
print(r.status, r.values, r.cost, r.optimal)     # repaired {'lam': 5} 1 True

The result is holds when the check passes with the present values (a repair is then a verification), repaired (the values, their cost, optimal when no values of lower cost pass, and check, the result of the check with the values), impossible (no values in the ranges pass, with the evidence), or unknown with the reason. The values of a repair are always checked by the check itself, with its usual back end. The method is chosen by the formulas:

Method When How
projection formulas over a bounded number of steps, real parameters the values for which the check fails are computed at once by eliminating the other variables (z3); one optimization
counterexamples the other checks of every behavior: LTL (nuXmv), C (ESBMC), integers optimize the cost under the conditions that the counterexamples found so far are no longer counterexamples, check, add the new counterexample, until the check passes
witnesses checks of some behavior (verify, compat, consist) on bounded formulas (chosen by auto; not a value of method=) the parameters and a behavior for each question, in one optimization
enumeration checks of some behavior on other formulas, integer parameters the values in the order of their cost, until one passes

The conditions of counterexamples only remove values that cannot repair, so the cost of each round is a lower bound: the values that pass are optimal. On formulas over a bounded number of steps, a counterexample is generalized: its integers and Booleans as they are and its reals free, it removes every value for which some behavior of that kind still fails, not only one value. A counterexample of a C function is not generalized (its behaviors are those of its code). method= forces a method, rounds= (50) limits the rounds. Repair optimizes with z3 (pip install chase-cps[z3]).

On the command line, with the checks of chase-cps check and --param NAME=LOW..HIGH (:int for an integer):

$> chase-cps repair heater.ltl --refines Room+Thermostat Comfort --param theta=60..90:int
repair      repaired  (counterexamples, 4 rounds, 0.11 s)
  theta = 74
  change 2 (optimal)

The demos Braking, Heater, and Deadline repair a braking system (the bounds of ContrACT, MEMOCODE 2026), a thermostat in signal temporal logic and its C code, and a deadline in LTL.

Diagrams

chase_cps.viz draws contracts, components, and systems as a web page:

  • A contract is a rounded box; a click on its name shows its assumptions (A) and guarantees (G).
  • A component with a model (RTL, a state machine in JSON or SMV, or a controller) is a square box; its model opens on its states and moves. The icon of a synthesized model (a controller of slugs) has a spark.
  • Refinement is nesting: a decomposition, or a contract, is drawn inside the box of the contract it refines, on as many levels as there are refinements. A box with boxes inside folds them away (the button at its top right). A quotient is a pale yellow hole next to the known parts, with what refines it inside.
  • An environment is a grey box on the left of what it drives: the outside of the design, checked against the assumptions only. Something that has a contract of its own is a component.
  • The results of the checks are tags next to the name of a box: A (compatible), G (consistent), A∧G (feasible), R (realizable), WS (well-separated), ¬V (no vacuous output), M ⊨ C, E ⊨ A, and ⪯ (refines), green when the check holds, red when it does not. A click on a red tag with a core puts the terms of the core on a red ground.
  • The named constants of a contract (its parameters) are on a line of their own (θ), and the terms use their names.
  • A click on ⪯, M ⊨ C, or E ⊨ A (or on a red A∧G) opens the panel of the check, by its tag: the named constants of its contracts, each with a range, which may change (those of the parts at first; a constant of the contract refined is a requirement, changed only when you pick it), and the repairs that chase-cps repair finds, each alone and all together. Pointing at a repair draws it on the diagram: the value struck out, the new one, and the tag as it would be. Apply writes the value in the declaration of the constant (twice for a requirement), and the checks run again. The repairs found before for other checks are then out of date, found again when asked. With two or more checks that fail, a button in the tools lists them, with the constants they share. Repairs run in VS Code and in chase-cps view FILE --serve; a page saved as a file shows the command line.
  • The operations are written as in Benveniste et al. (Contracts for System Design, 2018): ⊗ composition, ∧ conjunction and • merging (viewpoints of one component: one box with the ports of the result, the viewpoints inside), / quotient, ⪯ refinement.
  • The context of the checks is a tag above the diagram.

The diagram fills the window: drag to move it, the wheel (or a pinch) zooms around the pointer, and the button with four corners (or the key 0) fits it to the window, centered.

The structure comes from the contracts: each result of the algebra remembers its operands (Contract.origin). The page lays the boxes out with ELK, loaded from a CDN.

from chase_cps import Component, Contract, System, viz, verify, is_realizable, refines

a = Contract.from_strings(name="A", inputs=["x"], outputs=["y"], guarantees=["G (x -> X y)"])
b = Contract.from_strings(name="B", inputs=["y"], outputs=["z"], guarantees=["G (y -> z)"])
top = Contract.from_strings(name="Top", inputs=["x"], outputs=["y", "z"],
                            guarantees=["G (x -> X z)"])
s = System("S", [Component("a", a), Component("b", b)], contract=top)
s.check()                      # the composition against Top: drawn inside it
q = top.divide(a, name="Q")    # what the part next to a must do
greedy = Contract.from_strings(name="Greedy", inputs=["r1", "r2"], outputs=["g1", "g2"],
                               guarantees=["G !(g1 & g2)", "G (r1 -> g1)", "G (r2 -> g2)"])
k = "G !(r1 & r2)"             # the requests never come together
refines(b, q)                  # each check keeps its result on the contract
verify(greedy, context=k)
is_realizable(greedy, core=True)
d = viz.diagram(s, q, greedy, refines=[(b, q)], environments=[("G F x", s)], context=k)
viz.save(d, "plan.html")       # viz.show(d) opens the browser; in Jupyter, a system draws itself

A check keeps its result on the contract it checks (Contract.checked()), with what the contract said then: the diagram draws the results that still hold, and a refinement given without its status takes the one kept. When the contract changes, its results no longer show; results=False draws only what is given.

checks takes (item, result) with the result of verify (A, G, and A∧G), is_realizable (R), is_well_separated (WS), is_vacuous (¬V, with the guarantees that name a vacuous output as its core), or is_receptive; with core=True, the core comes with the check that fails. An unrealizable core shows the guarantees only, since it keeps all the assumptions. A result that is unknown does not say which check it is: (item, "realizable", result), or well_separated, vacuous, receptive. The results of is_compatible and is_consistent (sat or unsat) always come with their name: (item, "consistent", result). An item that refines several contracts is drawn inside each of them, and each candidate for a quotient gets a copy of the quotient with its own hole. environments takes an LTL formula, a Model, or a Component whose implementation is the environment. open takes the items drawn open when the page loads: the terms of a contract, the states of a model (with 8 states or fewer), and the core of a check that fails.

On the command line, chase-cps view FILE writes the page of a file: a specification in the logics language, in JSON, or in SystemVerilog Assertions (.sv), or a Verilog module (.v, or .sv without assertions), drawn with the state machine of its registers. viz.from_spec(path, ...) makes the same diagram in Python. The options:

  • --contracts C...: the contracts drawn (NAME+NAME for a composition). By default, all the contracts of the file, but those drawn inside another box.
  • --refines R A: draws R inside A.
  • --implementation MODEL C: draws C as a component with its model: SMV, JSON, or RTL read with Yosys (FILE:MODULE when the file has several modules).
  • --environment MODEL C: draws the model as an environment of C.
  • --open C...: draws these contracts open.
  • --check: checks that the assumptions and the guarantees of each contract can hold together (A∧G; when they cannot, the core is marked in red), and the refinements, the implementations (M ⊨ C), and the environments drawn.
  • --verify, --realizable: check each contract drawn (A and G, R).
  • --timeout S: seconds for each check.
  • --budget S: no check starts after S seconds; the checks left are not marked.
  • --results FILE: where the results of --check are kept; by default next to the file (charger.ltl → charger.results.json). A check whose contracts and models have not changed is not run again: its result is read from the file. --no-results keeps none.
  • --progress: writes each result of --check on the standard error as soon as it is known (progress: {...}, one line each), so that an editor shows the results one by one.
  • --no-checks: leaves the checks out (an editor draws the structure as one types, and the checks when the file is saved).
  • -o PAGE: the page written (default: FILE with .html).
  • --format json: writes the data of the diagram instead of the page.
  • --serve (--host, --port): serves the page and draws it again in place whenever the file changes, with the view kept; when the file cannot be drawn, the page keeps the last diagram and says why.

Without --refines and --contracts, the contracts are put together by their ports:

  • an output and an input with the same name are wired;
  • contracts with the same inputs and outputs are versions of one part (fixes, or candidates): the first one in the file is wired, the others are drawn apart;
  • a contract whose outputs are driven by several parts, which read from outside only its inputs, is the contract of their composition: the parts are drawn inside it, and --check checks the refinement;
  • when two parts or more are written but some outputs of the contract are driven by none, the part not written yet is drawn as a hole: the quotient of the contract by the parts (closed form, not checked).

The results kept in the results file are shown also without --check, for the contracts that have not changed.

An error in the file names the line and the column (line 16:16), and the contract when it is a name that is not declared.

The options can also be written at the top of the file, in comments (// view: in Verilog). The files named there are taken from the folder of the file, and the options given on the command line add to them:

# view: --implementation models/arb.json Arb --environment models/req.json Arb
# view: --check --open Arb
CONTRACT Arb ...

The button with an arrow saves the whole diagram as SVG, PNG, or PDF (the print dialog of the browser).

The page loads ELK (elkjs 0.9.3) from a CDN. viz.html(d, elk=PATH) and chase-cps view --elk PATH put a local elk.bundled.js in the page instead, for a page that works offline. With CHASE_VIZ_OUTPUT=FILE in the environment, viz.show writes the page to FILE and opens no browser (CHASE_VIZ_ELK=PATH puts ELK in it).

The diagrams are also drawn by the MCP server of CHASE (the visualize tool of chase-mcp, for AI agents). An extension for VS Code, which shows the diagram of a specification, or of a Python script that calls viz.show, beside the editor, will follow: it draws the structure again as one types and the checks when the file opens and on save (within a few seconds, the rest with its Check button), marks the errors in the text, goes from a box, or a term of an open box (the terms of a core among them), to its line (a double click), and from the text to its box and term (the cursor). The terms of a file of the logics language or of SystemVerilog Assertions know their lines; a term drawn from a file shows its line when the pointer rests on it.

Results

The checks return a result with a status: valid or invalid for implications and refinement, sat or unsat for satisfiability, compatibility, consistency, and verify, receptive or not_receptive for receptiveness, realizable or unrealizable for realizability and synthesis, separated or not_separated for well-separation, vacuous or not_vacuous for vacuity, and unknown with a reason when the check does not finish or no tool is installed. A failed check comes with a trace: the states of prefix, then the states of loop repeated forever. synthesize returns the controller, and both is_realizable and synthesize return the counter_strategy of the environment when the contract is unrealizable.

refines checks the assumptions and the guarantees separately; failed says which part fails, and its result has the counterexample.

External tools

The checks use nuXmv (free for academic and non-commercial use) and slugs for synthesis:

$> chase-cps install nuxmv --accept-license
$> chase-cps install slugs
$> chase-cps doctor

pip install chase-cps installs the contracts, LTL, and GR(1). The other domains are installed when they are used:

Domain Install
Static contracts, signal temporal logic, minimize, maximize pip install chase-cps[z3]
Hardware: RTL (SVA needs nothing more) pip install chase-cps[rtl]
C programs chase-cps install esbmc (Linux), brew install esbmc (macOS)

chase-cps doctor lists the back ends by domain: where each one is, what it is needed for, and how to install the ones missing.

Engines

nuXmv checks the formulas with IC3 and BDDs at the same time (portfolio): the first verdict wins, and the other run is stopped. Both engines prove and refute, so the verdict is the same whichever answers; the counterexample may differ. One engine can be chosen with engine, or in the name of the back end, as the results name it:

Engine Proves Finds counterexamples Good for
portfolio (default with nuXmv) yes yes IC3 and BDDs at the same time (IC3 and BMC for reals)
ic3 yes yes large state spaces, words, reals
bdd yes yes a counterexample that needs a long loop (a counter that goes around)
bmc no up to bmc_bound steps (20) short counterexamples
from chase_cps import implies

r = implies("cnt = 254 & G (cnt' = cnt + 1)", "X (cnt = 0)", {"cnt": "word[8]"},
            "nuxmv/bdd")
print(r.status, r.backend)      # invalid nuxmv/bdd

The counterexample is a loop of 256 steps: BDDs find it at once, IC3 takes minutes, and the default gives the answer of BDDs. Formulas with signed() or unsigned() are checked with BDDs only: IC3 of nuXmv 2.2.0 gives wrong answers on them. On the command line the option is --engine; the environment variable CHASE_BACKEND may also name an engine (nuxmv/portfolio). NuSMV has no IC3: without nuXmv, the default first looks for a counterexample with BMC, then proves with BDDs. The SMT engine of nuXmv (real variables with arithmetic) works with ic3 and bmc only. Receptiveness is a CTL check and always uses BDDs.

Files for the tools you run yourself

The checks call the open-source tools (nuXmv, NuSMV, z3, slugs, ESBMC, CBMC) directly. For a tool that you run yourself, such as a tool under license or another solver, a check is written as the input file of the tool. A function is named after the language of the file. Its first argument is the check, then come the arguments of the check, in the order of the function of the check; tool names the tool where the files of two tools differ.

Check Function of the check Questions in the file
verify verify(c) compat, consist, feasible
compat is_compatible(c) compat
consist is_consistent(c) consist
refines refines(c1, c2) assumptions, guarantees
impl is_implementation(m, c) impl
env is_environment(e, c) env
Function Language Tools
to_smv(check, ..., tool="nuxmv") SMV nuXmv, NuSMV (tool="nusmv")
to_smt(check, ...) SMT (SMT-LIB 2, .smt2) z3, cvc5
to_c("impl", f, c) C ESBMC, CBMC
to_gr1(c, tool="slugs") structured slugs, gr1c slugs, gr1c (tool="gr1c")
to_sva(c) SystemVerilog Jasper, Verilator, other SVA tools
to_spec(contracts) logics language CHASE, logics_tool

Each question has its name and a comment that says how to read the answer. A question of satisfiability is written in SMV as its negation: the specification is false when the formula can hold, and the counterexample is a behavior that satisfies it. For impl and env of a state machine, to_smv writes its model with the specification. to_smt takes formulas that read a bounded number of steps (x at step k is x@k) and needs z3 to write the file. to_gr1 writes the realizability question of a contract, to_sva a contract, and to_spec contracts.

from chase_cps import Contract, to_smv

c1 = Contract.from_strings(name="Gen", inputs={"n": (0, 20)}, outputs={"p": "real"},
                           assumptions=["n <= 4"], guarantees=["p >= 2.5 * n", "p <= 30"])
c2 = Contract.from_strings(name="Spec", inputs={"n": (0, 20)}, outputs={"p": "real"},
                           assumptions=["n <= 4"], guarantees=["p >= 12", "p <= 30"])
open("refines.smv", "w").write(to_smv("refines", c1, c2))     # does c1 refine c2?

On the command line, export takes the checks of check, one at a time:

$> chase-cps export spec.ltl --to smv --refines Gen Spec -o refines.smv
$> chase-cps export spec.ltl --to smt --verify Gen -o gen.smt2
$> chase-cps export spec.ltl --to smv --impl arbiter.smv Arbiter -o impl.smv
$> chase-cps export spec.ltl --to c --impl saturate.c:saturate Sat -o check.c
$> chase-cps export spec.ltl --to gr1 --tool gr1c --realizable Arbiter -o arbiter.spc
$> chase-cps export spec.json --to spec -o spec.ltl

In chase-cps check, the checks have the same names: --verify, --compat, --consist, --refines, --impl, --env, --recep (--compatible, --consistent, --implementation, --environment, and --receptive still work). --verify, --compat, and --consist take contracts, or check every contract (or those of --contracts).

The full API of the Python package is in the API reference.