Chapter 16 : KRONOS (Model Checking of Real-time Systems) JIHO YANG

Chapter 16 : KRONOS (Model Checking of Real-time Systems) JIHO YANG

What is KRONOS? KRONOS allows analyzing timed automata. KRONOS is a model checker for the TCTL(Timed CTL) logic. KRONOS checks whether a timed automaton satisfies a TCTL.

KRONOS’ Essentials KRONOS is one of the tools, which implements a model checking algorithm for a timed temporal logic (TCTL). KRONOS contains no graphical, no simulation modes. KRONOS is a timed model checker. http://www-verimag.imag.fr/TEMPORISE/kronos

Railroad crossing example (Two train, a gate, a controller, a counter)

Cont.

Cont. KRONOS Code (Tr1.tg) /* train1 */ #locs 3 /* number of states*/ #trans 3 /* number of transitions */ #clocks x1 /* clock */ #sync app1 exit1 /* synchronization labels */ loc: 0 prop: far inv: TRUE trans: TRUE app1; x1: 0 ; goto 1 loc: 1 prop: near inv: x1 30 trans: x1 20 and x1 30 enter; ; goto 2 loc: 2 prop: on inv: x1 50 trans: x1 20 and x1 50 exit1; ; goto 0 (trans: x1 30 and x1 50 exit1; ; goto 0)

Synchronized Product In order for several components of a system to communicate, KRONOS introduce a synchronization function. KRONOS, a synchronization label is simply obtained by the union of the label sets of the components. A set of transitions are synchronized if and only if each label occurring in one of the transition sets also belongs to one set of another transition.

Cont. (example) A1 containts the single transition {a,b} t1 : q1 ------- r1 A2 contains the single transition {b,c} t2 : q2 ------- r2

Cont. (example) If b is a synchronization label, then the product of automata A1 and A2 contains transition of {a,b,c} q1,q2 ---------- r1,r2.

Kronos code (Example) Extension “.tg” : “timed graph” Make the product of A1 and A2: A(12) Kronos -out A12.tg A1.tg A2.tg

Cont.(Example) Compose the result A(12) with A3: (we can express kronos code like) Kronos -out A12A3.tg A12.tg A3.tg

Cont. The automaton A(12)3 – the product of A1 and A2, and then compose the result A(12) with A3 The automaton A1(23) – the product of A2 and A3, and then compose the result A(23) with A1 It is not easy to use a modular approach.

Cont. There is two ways to overcome. The first one consists in building in a single operation the product of all components of a given system. Kronos code: Kronos –out S.tg Tr1.tg Tr2.tg Gate.tg Contr.tg Ct.tg

Cont. The second way: use a special option “-sd” Kronos –sd –out A12.tg A1.tg A2.tg

Model checking The properties to be checked must be expressed by TCTL. Each being in a separate file with extension “.tctl”

Safety property Safety property : Under certain conditions, an event never occur. ? “when a train is inside the crossing, the gate is closed.” Safe.tctl : Init impl AB(on impl closed) AB correspond A and G of CTL Impl : Boolean combinator

Cont. Verifying safety property KRONOS command: Kronos –back S.tg safe.tctl Kronos –forw S.tg safe.tctl (backward analysis) (forwards analysis) Safe.eval contains the result

Liveness property Liveness property: under certain condition, some event will ultimately occur. “from the moment where no train arrives anymore, the gate will be open after d time units.” Express TCTL

Cont. Init AG ( near on E( near on open) U ( d) true)) Write KRONOS when d 20; Init impl AB((not near and not on) impl not((not near and not on and not open) EU{ 20} TRUE))

Questions