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:
inputoroutput,boolean,integer (low:high), orreal, thenvariable name;. An integer without a range ranges over 0 to 16;load_specandparse_specwarn 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 rejectsreal (low:high): write the range as an assumption). Constants are declared asinteger constant N 5;orreal constant K 2.5;, and propositions asproposition p is x > 3;. Assumptions:andGuarantees:list formulas, each ending with;.- Formulas:
!(or~),&(or/\),|(or\/),->,<->,G,F,X,U,R,true,false, the relations= != < <= > >=, the arithmetic+ - * /, andx'for the value ofxin the next step.#starts a comment. G,F,U, andRtake an interval of steps:G[0,3] pispnow and in the next three steps,F]1,4] pispin 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 intoX:G[0,2] pis read asp,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 guaranteeG p,initial assert property (p)isp.assume propertyandrestrict propertyare assumptions;cover propertyis 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) + 1the sum has 32 bits (as the constant 1) and does not wrap around: the property fails whencountgoes 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_cycleof the property):x == $past(x)from cycle 1. Values one cycle apart are written withx', values further apart withpast(x, n):y == $past(x, 2)isG 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 ina |-> ##[1:$] b, it is weak in an assert and never fails, so it is not read: writea |-> s_eventually b. disable iff (r)passes the attempt when r holds before it fails;default clockinganddefault disable iffapply.- Named properties and sequences (with arguments) and
assignorwire x = edefinitions are put in place.parametersgives the values of parameters. - A contract has one clock: with several,
clockchooses one (the clock of most properties by default) and the properties of the others are skipped. - The directions come from
inputsoroutputs(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 inundeclared. - Packed arrays are words:
logic [3:0][7:0] xhas 32 bits,x[2]is bits 23 to 16. Hierarchical names are read as one name:u1.stateisu1__state, andnamesmaps 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:
- 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.
- 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. - 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 oneRATEfor every variable.--refines R Sthen 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, andunsat_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:
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 ofsynthesizegives for each node the values of the variables, the real ones as conditions (30.5 < kias < 40), and the list of the regions.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.predicates: when nuXmv gives no answer, each comparison becomes a Boolean variable (x <= 10andx > 10are the same one, negated). The abstraction allows values that are impossible (x > 10andx < 5at 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 <= 30is30 - x,x >= 10isx - 10,x = cis-|x - c|, andx != cis|x - c|; !is the opposite,&the minimum,|the maximum;Xis the value at the next step,Gthe minimum over the steps to come,Fthe maximum, andUthe 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 repairfinds, 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 inchase-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+NAMEfor 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:MODULEwhen 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--checkare 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-resultskeeps none.--progress: writes each result of--checkon 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
--checkchecks 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.