How-to guides › Verify a model

How-to guides

Verification: formal checks, tests, faults and logs

archec checks that the model is right, and that the real system behaves as the model says. It proves things about the state machines and the contracts between parts. It finds requirements that cannot hold together. It runs tests with faults, measures what they cover, and reads the real system's logs against the model.

A first check#

This lamp has a state that nothing ever enters:

message GO "Go" { on: bool }

component Lamp "Lamp" {
  in cmd: data receives GO
  states {
    state Off "Off"
    state On "On"
    state Broken "Broken"
    Off -> On on GO
    On -> Off on GO
  }
}

system Room "Room" {
  part lamp: Lamp
}
Diagram: Room
What archec draws from this code: Room
Try it
archec check main.arche
main.arche:8:11 warning State 'Broken' cannot be reached from 'Off' [unreachable-state]
  |     state Broken "Broken"
  |           ^^^^^^
✓ no errors, 1 warning(s)

archec check runs these checks every time, with nothing to install. The sections below show the other checks, from the simplest to the ones that need a log or an outside tool.

Formal checks: state machines and contracts#

State machines#

The linter reads each state machine as a graph of states and transitions. A definition that extends another also gets the states and transitions of the one it extends, as Arche does.

code what it finds
unreachable-state A state that no path reaches from the initial state. Entering a composite state starts in its pseudo initial child, or else in its first child (one per region). A transition that never fires leads nowhere. goto("X") in the code reaches X.
deadlock-state A reachable state with no way out, either from itself or from a state around it, and that is not pseudo final. It is a warning when the machine has a final state. It is a hint when it has none, since a latched fault that only a reset leaves is often meant. A state that every state falls into (* -> Fault) is a safe state. A component whose code calls goto(…) is not checked.
dead-transition A trigger that is a message no input port of the component receives, or a guard that is false. The messages a port receives come from receives, its handlers and its interfaces' messages. A port that names none takes anything.
shadowed-transition A transition that an earlier one always beats: same state, same trigger, and the earlier one has no guard.
nondeterministic (hint) Two guarded transitions from one state, on one trigger, whose guards may both hold. These count as exclusive: else, g and not g, distinct values, and disjoint ranges (x < 0 and x >= 0).

archec reads a guard only when it is a plain comparison. A guard written in words is left alone.

Contracts#

A contract says two things about a component:

  • what it assumes about what it receives;
  • what it guarantees about what it sends.

At each link, archec checks that one side's guarantee meets the other side's assumption. Here the pedal may send up to 1500 N, but the brake ECU expects at most 1000 N:

message BRAKE_CMD "Brake command" { force: float32 unit N }
message BRAKE_STATUS "Brake status" { applied: bool }

component Pedal "Pedal" {
  out cmd:   data sends BRAKE_CMD
  in status: data receives BRAKE_STATUS
  contract {
    guarantee cmd.force in 0..1500N
  }
}

component BrakeEcu "Brake ECU" {
  in cmd:     data receives BRAKE_CMD
  out status: data sends BRAKE_STATUS
  contract {
    assume cmd.force in 0..1000N
    guarantee status.applied within 20ms after cmd
  }
}

system Car "Car" {
  part pedal:  Pedal
  part brakes: BrakeEcu
  pedal.cmd -> brakes.cmd
  brakes.status -> pedal.status
}
Diagram: Car
What archec draws from this code: Car
Try it
archec check main.arche
main.arche:24:3 warning brakes.cmd assumes "cmd.force in 0..1000N", but pedal.cmd guarantees "cmd.force in 0..1500N" … (archec explain contract-unmet) [contract-unmet]
  |   pedal.cmd -> brakes.cmd
  |   ^^^^^^^^^^^^^^^^^^^^^^^
✓ no errors, 1 warning(s)

How to write a clause:

  • A clause names a field of a port's message (cmd.force, or cmd.BRAKE_CMD.force), or a variable.
  • It compares it with in lo..hi, ==, !=, <, <=, >, >=. It can also be bare: status.applied, not fault.
  • Clauses can be joined by and.
  • A clause can start with always or eventually, and end with within 20ms, or within 20ms after port.
  • An interface or a port type can hold a contract too. Its clauses name the message or the field. They hold on every port that takes part in that interface or type.

At each link a.p -> b.q, what a guarantees on p must imply what b assumes on q:

  • Ranges and equalities on the same field. A guarantee in 0..1500N against an assumption in 0..1000N is a contract-unmet warning. It quotes both sides.
  • Units. Time units are converted. Other units are not: N against kN is a contract-unknown hint, and N against ms is unmet.
  • Deadlines. A guarantee within 20ms meets an assumption within 50ms. When both name an after event, a link must join the two ports.

contract-unknown also covers two other cases:

  • an assumption with nothing guaranteed on its field;
  • a clause archec cannot read, such as an or or a call.

Arche has no place for contracts, so they stay in the model. archec sysml writes a contract as a requirement of assume constraints and require constraints.

Requirements that cannot hold together#

archec verify --conflicts looks for requirements that no implementation can satisfy together. NASA's FRET does the same; here there is nothing to install.

It reads the formal properties, and the EARS sentences, over the states of each part. It plays a game:

  1. At each tick, the environment chooses which message each part receives.
  2. The implementation then puts each part in any of its states, starting from its initial one. The machine's transitions are one possible implementation, not a limit.
  3. When no choice of states survives every input, the requirements conflict.
✗ conflict R1, R2 cannot hold together [req-conflict]
    at 10ms, when brakes receives watchdog, every state the parts can be in breaks R1 or R2
         0  brakes in Idle
      10ms  brakes receives watchdog → whatever the parts do:
              brakes in Idle     breaks R2
              brakes in Braking  breaks R2
              brakes in Holding  breaks R2
              brakes in Fault    breaks R1
    main.arche:31 R1: never brakes in Fault
    main.arche:32 R2: if brakes receives watchdog then brakes shall be in Fault

Each conflict is minimal: leave out any one of its requirements and the rest can hold. archec solves it exactly, as a safety game on a finite graph. The graph is the parts' states and, for each requirement, the earliest deadline it is waiting for.

What is bounded:

  • Time is counted in ticks. A tick is the common divisor of the deadlines. It is made coarser past 16 ticks per deadline, each deadline rounded up. --tick sets it.
  • eventually and leads to with no within are read as within --horizon ticks (8 by default).
  • A response that sends a message is not read.

What a property means#

archec verify --meaning [REQ…] shows what a property says, on two timelines: one where it holds and one where it fails. The specification from archec doc --html shows them under each requirement.

R3 (brakes receives BRAKE_CMD) leads to brakes in Braking within 50ms
  Each time brakes receives BRAKE_CMD, brakes in Braking holds then or at most 50ms later.
    A = brakes receives BRAKE_CMD
    B = brakes in Braking
    holds:
      A ··▲·······▲·····
      B ·····██·····█···
          └───┘ 50ms
    fails:
      A ··▲·······▲·····
      B ············█···
          └───┘ 50ms ✗ B not in time

eventually and leads to take a deadline, such as within 50ms. NuSMV checks them untimed, without the deadline. The monitors (archec gen --monitors), archec replay and --conflicts check the deadline.

Model checkers#

For a model checker, archec writes the model in its input language (see Code generation):

  • archec gen --target uppaal writes uppaal/model.xml and uppaal/model.q;
  • archec gen --target nusmv writes nusmv/model.smv.

Testing with faults#

A test case can break things on purpose, in Arche's simulation. This checks that the model copes:

failure-mode FM-RX "Receiver hangs" { of Car.brakes; effect "No more braking"; inject "freeze brakes" }

case TC-CAN-LOSS "Brake CAN lost" {
  at 20ms fault drop adcu.can_brake        // every message through that link end is lost
  within 60ms expect brakes.state == "SafeStop"
  at 100ms fault up adcu.can_brake         // works again
  at 120ms fault FM-RX                     // a failure mode's `inject`
}
fault what the simulation does
drop part.port Messages through that link end are lost. The trace shows them as dropped ("fault: …").
up part.port Ends a drop: messages go through again.
delay part.port 5ms Each message through it arrives 5 ms later.
stuck part.port f=0, g=True Messages through it carry those field values.
freeze part / thaw part The part, and what is inside it, stops: its code, its timers and its inbox. What it held resumes when it is thawed.
clear [target] Ends the faults of the target, or all of them.
FM-ID Runs the failure mode's inject.

A moment takes a fault at its time: at 20ms fault drop adcu.can_brake. The linter checks the fault and its target (bad-fault, unresolved). Each fault compiles to an observer call that Arche's engine runs, such as fault_drop("adcu.can_brake").

Test coverage#

archec test main.arche --coverage says what the test runs exercised of the model. In VS Code, Run with Coverage in the Test Explorer does the same.

Coverage (car.yaml):
  states           6/8      75 %
      not covered: adcu: MinimalRisk
  transitions      5/10     50 %
      not covered: adcu: Autonomous -> MinimalRisk
  messages         4/10     40 %
      not covered: HEARTBEAT: adcu.can_brake -> brakes.can
  functions        9/9     100 %
  requirements     4/4     100 %

What it counts:

  • the states entered;
  • the transitions taken;
  • each message on each link that carries it;
  • the functions called;
  • the requirements that a test verifies and whose cases ran.

The whole report is kept in .archec/coverage.json. In the editor (VS Code 1.88 or later), each state, transition, function and link is marked "run" or "not run" at its line. Arche's simulator records the coverage (arche-cli test --coverage <file>).

Runtime verification: the real system's logs#

archec replay checks the model's requirements on what the real system did. It reads:

  • a CAN log (candump, Vector ASC or BLF);
  • a ROS 2 bag (MCAP);
  • JSON lines;
  • a firmware's trace (archec gen --trace): its state lines are the parts' states, its send lines the messages sent (examples/greenhouse).

The model decodes each event.

cd examples/brake-by-wire
archec replay main.arche logs/run-late.log logs/states-late.jsonl --junit replay.xml
  ✗ REQ-BRK-1   1 violation(s), the first at +0.070000 s (log time 1762790400.070000): brakes receives BRAKE_CMD at 50ms, not brakes in Braking 20ms later
  ✓ REQ-BRK-2   1 trigger(s)
  ✗ REQ-BRK-3   1 violation(s), the first at +0.150000 s (log time 1762790400.150000): brakes in Fault
  ✗ REQ-BRK-4   1 violation(s), the first at +0.050000 s (log time 1762790400.050000): BRAKE_CMD.force = 15000
  ✗ stale-after ctrl.status BRAKE_STATUS  1 violation(s), the first at +0.125000 s …: none for 70ms

How a log is decoded:

  • A CAN id is the message that the deployment's route … { id 0x100 } puts there. Its bytes are decoded with the same layout as the DBC and the generated C and Rust.
  • A ROS 2 topic is the message of its type.
  • A state does not appear on a bus. A JSON line such as {"t": …, "part": "brakes", "state": "Braking"} gives it (from a firmware trace, for example).

What is checked:

  • EARS requirements, as monitors;
  • formal properties;
  • a metric that names a message field, against its limit;
  • contracts and chain budgets;
  • ranges, periods and stale-after.

--json and --junit are for CI, as with archec ci.

--scenario replay.arche --from ctrl turns the log into a test case. The case sends to the model what ctrl sent, at the same times. It expects the model's parts to go through the states the real parts went through. archec test then runs the model on the real inputs. See docs/commands.md.

Limits#

  • The state-machine checks run no Python. They read a guard only when it is a plain comparison (self.speed < 10, not armed). With any other guard they say less rather than guess, so a dead transition behind such a guard is not reported.
  • A component whose code calls goto(…) is not checked for deadlocks.
  • A contract clause archec cannot read (an or, a call) is contract-unknown, not checked. Units other than time are not converted.
  • --conflicts counts time in ticks, reads eventually and leads to with no within as within --horizon ticks, and does not read a response that sends a message.
  • NuSMV checks the machines untimed: a within deadline is checked by the monitors, archec replay and --conflicts, not by NuSMV.
  • Without NuSMV on the PATH, each property is "not checked" (exit 2), never proven.
  • archec replay knows a state from the log only. A check that needs a state the log never gives is reported as not checkable. A response still awaited when the log ends is inconclusive, not a failure.