Test des Automates Temporisés

1

Test des Automates Temporisés

Stavros Tripakis

Laboratoire Verimag

Master 2 Recherche S&L« Méthodes de test »

2

Modèles, modèles, …

• Les machines de Mealy– Entrées/sorties synchrones– Bonnes pour circuits/programmes synchrones

• Les systèmes de transitions étiquetés– Bons pour systèmes asynchrones (ex. protocoles de

communication)– Aspects temps-réel pas bien modélisés

• Les automates temporisés

3

Exemple

s1

s2

A? B!

Spécification:pour chaque entrée A,

retourner un B

s1

s2

A?

Implémentation(candidate)

conforme ?

4

Exemple

s1

s2

A? B!

Spécification:pour chaque entrée A,

retourner un B

s1

s2

A?

Implémentation(candidate)

Comment capter la non-conformité ?

5

Real-time testing

SUT

Tester

outputs

Verdicts(pass/fail)

inputs

6

Exemple

s1

s2

A? B!

Spécification:pour chaque entrée A,

retourner un B

s1

s2

A?

Implémentation(candidate)

Comment trouver la valeur « timeout »

lors du test ?

7

Plan of talk• Specification model

• Conformance relation

• Analog & digital tests

• Test generation

• Tool and case studies

8

Plan of talk• Specification model: timed automata with inputs,

outputs and unobservable actions.

• Conformance relation

• Analog & digital tests

• Test generation

• Tool and case studies

9

Simple example 1

a?x:=0 x 4

b!

“Output b at most 4 time units after receiving input a.”

10

Simple example 2

a?x:=0 x 4

b!

“Output b at most 4 time units after receiving input a,except if you fail, in which case output a failure notice

at most after 8 time units.”

Unobservable action

x 8fail!

11

Compositional specifications

Compositional specificationswith internal (unobservable) actions.

A B

C

12

Compositional specifications

internal (unobservable) actions.

13

Modeling assumptions on the environment

env spec

Export (make observable) interactionsbetween the specification and its environment.

14

Simple example 3

a!y 10

“Output b at most 4 time units after receiving input a,provided a is received no later than 10 time units.”

A compositional modeling of the same example.

y:=0

a?x:=0 x 4

b!

a? b!

15

Simple example 3

a?x 10 x 4

b!

“Output b at most 4 time units after receiving input a,provided a is received no later than 10 time units.”

Constraints on the inputs model assumptions.

x:=0x:=0

Constraints on the outputs model requirements.

Specification is not always input-complete.

16

Conclusion: a rich TA model• Time non-determinism:

– Cannot impose exact input or output times.

• Action non-determinism:– Model failures, abstract details.

• Partial observability:– Internal actions of compositional specifications.

• Not input-complete:– Model assumptions on the environment.

17

Plan of talk• Specification model

• Conformance relation: an extension of the “untimed” relation “ioco”.

• Analog & digital tests

• Test generation

• Tool and case studies

18

Conformance relation• A timed extension of Tretmans’ “ioco”:

timed input-output conformance relation (tioco).

• Informally, A tioco B if– For any observable behavior p of B, any possible

observable output of A after p (including a delay) is also a possible observable output of B after p.

• To put it otherwise:– Implementation accepts more inputs and produces fewer

outputs than specification.

19

Conformance relation• Formally:

A tioco B (A: implementation, B:specification)iff

Traces(B). out(A after ) out(B after )

20

Conformance relation• where:

A after = {s | Seq. s0 s proj(,Obs)=}

out(S) = delays(S) outputs(S)

21

Conformance relation• where:

outputs(S) = {aOutputs | sS . s }a

delays(S) ={tR | sS. UnobsSeq. time() = t s }

22

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

23

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 4

b!Impl 1:

24

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 4

b!Impl 1: OK!

25

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 4

b!Impl 1:

a?x:=0 x 2

b!Impl 2:

OK!

26

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 4

b!Impl 1:

a?x:=0 x 2

b!Impl 2:

OK!

OK!

27

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 5

b!Impl 3:

28

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 5

b!Impl 3: NOT OK!

29

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 5

b!Impl 3:

a?Impl 4:

NOT OK!

30

Examples“Output b at most 4 time units after receiving input a.”

a?x:=0 x 4

b!Spec:

a?x:=0 x = 5

b!Impl 3:

a?Impl 4:

NOT OK!

NOT OK!

31

Plan of talk• Specification model

• Conformance relation

• Analog & digital-clock tests

• Test generation

• Tool and case studies

32

Real-time testing

SUT

Tester

outputs

Verdicts(pass/fail)

inputs

How accurate is this clock ?

33

Example“Output b exactly 4 time units after receiving input a.”

a?x:=0 x = 4

b!Spec:

a?x:=0 x = 4

b!Impl 1:

a?x:=0 x = 3.99

b!Impl 2:

OK!

NOT OK!

34

Timed tests• Two types of tests:• Analog-clock tests:

– Can measure real-time precisely– Difficult (impossible) to implement for real-time SUTs– Good (flexible) for discrete-time SUTs with unknown

time step

• Digital-clock tests:– Can count “ticks” of a periodic clock/counter– Implementable for any SUT– Conservative (may say PASS when it’s FAIL)

35

Timed tests• Analog-clock tests:

– They can observe real-time precisely, e.g.:

• Digital-clock (or periodic-sampling) tests: – They only have access to a periodic clock, e.g.:

ba

1.3 2.4 2.7

c

time

ba c

time1 2 3

36

Note

• Digital-clock tests does not mean we discretize time:– The specification is still dense-time– The capabilities of the observer are discrete-time )– Many dense-time traces will look the same to the digital

observer

37

Untimed tests• Can be represented as finite trees (“strategies”):

i

o1 o2 o3 o4

faili1 i2 i3

……

failpass

38

Digital-clock tests• Can also be represented as finite trees:

i

o1 o2 o3 o4 tick

fail …i1 i2 i3

……

failpass

Models the tick ofthe tester’s clock

39

Analog-clock tests• Cannot be represented as finite trees:

i

o1 o2 o3 o4 0.1

faili1 i2 i3

……

failpass

0.11 0.2…

Infinite number ofpossible delays

40

Analog-clock tests• Solution: build the test on-the-fly

1.3

i

time0 1.3

a

i

a

b

2.1

0.8

b

41

Test generation• Analog-clock tests:

– Cannot be represented statically as finite trees: infinite number of possible inputs delays

– Solution: on-the-fly testing: compute the test while you are testing !

• Digital-clock tests:– Can be generated both statically and on-the-fly.

• In both cases: symbolic test generation

42

Test generation principle

• The tester is a state-estimator: it keeps a set of possible states of the SUT,

according to the specification.

• Updates this set with each new observation.

• Gives inputs to SUT from time to time.

• Announces FAIL if ever set becomes empty.

• Announces PASS when tired of testing …

43

Test generation principle

currentestimate

observation

(event or delay)

nextestimate

runs matchingobservation

44

Test generation principle

• Sets of states are represented symbolically (standard timed automata technology, DBMs, etc.)

• Updates amount to performing some type of symbolic reachability.

• Can be used for on-the-fly testing (both for analog and digital) or static test generation (for digital only).

45

Update operators for analog tests• Given current state estimation S …

• Given observed event a (input or output):

dsucc(S, a) : all states that can be reached froma state in S after performing a transition a.

dsucc(S, a) = {s’ | sS. s s’}a

46

Update operators for analog tests• Given current state estimation S …

• Given time delay t:

tsucc(S, t) : all states that can be reached froma state in S after performing a run of

unobservable actions of total duration t.

tsucc(S, t) ={s’ | sS. UnobsSeq. s s’ time()=t}

47

Putting it all together

i

1.3a

a

1

0.3

S

S’ = dsucc(tsucc(S,1.3), a)

48

Update operator for digital tests• First, a trick:

• tick is an observable event:– Models the ticks of the observer’s clock.– Can also model skew, etc, using different

“Tick” automata.

originalspecificationautomaton

“Tick”tick!z = 1z:= 0

49

Update operator for digital tests

• Given S and observed event a (could be tick):

succ(S, a) ={s’ | sS. UnobsSeq. s s’}a

succ(S, a) = all states that can be reached froma state in S after performing a run of

unobservable actions that ends with a.

50

Updates for digital tests

i

tick

a

S

S’’ = succ(S’, a)

S’ = succ(S, tick)

51

Problèmes d’efficacité ?

52

Issue 1: cost of on-the-fly testing

i

time0

i

1.3

1.3

a

aSuccessor node:computed withreachability.

Can be problematic

53

Issue 2: number of static tests

Which input ?

EXPLOSION: exponential number of tests

Wait or give input ?

Stop the testor continue ?

i

o1 o2 o3 o4 tick

fail …i1 i2 i3

… …failpass

54

Improvements• Cost of on-the-fly testing:

– Represent analog testers as (deterministic) timed automata.

– Cost of testing = cost of computing successor state in the tester automaton.

• Number of static tests:– Coverage criteria.– Only generate relevant tests.

55

Analog-clock tests• Cannot be represented as finite trees:

i

o1 o2 o3 o4 0.1

faili1 i2 i3

……

failpass

0.11 0.2…

Infinite number ofpossible delays

56

Analog-clock tests with intervals• Can be represented as finite trees:

i

o1 o2 o3 o4 [0,1)

faili1 i2 i3

……

failpass

[1,2] (2,)

…

57

This is a timed automaton!• Can be represented as finite trees:

i

o1 o2 o3 o4 x<1

faili1 i2 i3

……

failpass

1x2 x>2

x:=0

…

58

• Generation of timed automata testers

• Generation of timed automata monitors– Monitors = simple testers = no inputs– (see paper for extension to testers)

59

Real-time testing & monitoring

SUT

Tester

outputs

Verdicts(pass/fail)

inputs

SUT

MonitorVerdicts

(pass/fail)

Environment

60

Timed-automata monitors• Specification: timed automaton A, with observable (o)

and unobservable (-o) actions.

• Monitor: deterministic, input-complete TA M over o.

• Plan A: monitor should accept exactly the behaviors which could be produced by spec:

• Impossible in general: TA not determizable.• Undecidable to check whether possible.

L(M) = (L(A))

61

Timed-automata monitors• Specification: timed automaton A, with observable (o)

and unobservable (-o) actions.

• Monitor: deterministic, input-complete TA M over o.

• Plan B: monitor should be conservative

• but also as precise as possible.• Precision depends on monitor resources:

– More clocks, better monitoring.

– Larger guard constants, better monitoring.

L(M) ¶ (L(A))

62

Timed-automata monitors• Specification: timed automaton A, with observable (o) and

unobservable (-o) actions.• Monitor: deterministic, input-complete TA M over o.

• Plan C: monitor should be conservative

• given– number of monitor clocks,– maximal guard constant,– reset skeleton

L(M) ¶ (L(A))

tells when to resetmonitor clocks, e.g.:

a? x:=0

y:=0a?

63

Monitor synthesis• Based on symbolic reachability of the product

P = Spec || Reset-skeleton

Location of M=

Set of states of Pa? for each observable,

synthesize:1 2

n guards

… successorlocations

Goal: reduce monitor uncertainty

64

Guard synthesis• Knowledge inference:

– Infer what you know on A’s guards based on relations of clocks of A and M.

x (clock of A)

y (clock of M)x,y) = relation of x,yin source location

c1yc2 ) ? y<c1 y>c2 c1yc2

2(x) 1(x)

y<c1 ) :1

y>c2 ) :2

65

Monitor synthesis• Based on symbolic reachability of the product

P = Spec || Reset-skeleton

Location of M=

Set of states of Pa? for each observable,

synthesize:1 2

n guards

… successorlocations

• successor locations: symbolic reachability• termination: max constants for A,M clocks

66

Coverage• Completeness impossible:

– # of SUT states unknown or too large.

• Coverage principle:– Generate tests that “cover” all “interesting”

parts of the specification.– Cover = visit.– Interesting:

• User-defined regions of state-space, or

• Standard: locations, edges, states, etc.

67

Coverage principle

State spaceof specification

Test generation

68

Coverage principle

State spaceof specification

a!

tick?

b?

1. Find a path reaching the unconvered region

covered

69

Coverage principle

State spaceof specification

a!

tick?

b?

b?

2. Complete it into avalid test tree

c?

c?

tick? covered

70

The benefits of coverage• Simple example: a lighting device

– 2 automata,– 2 clocks,– 27 locations– 1 input, 3 outputs

• Exhaustive test generation:– >2000 tests for depth=8

• Location (or edge, or state) coverage:– <10 tests of depth <20

71

Tool• TTG: implemented on top of IF tool-suite

http://www-verimag.imag.fr/~async/IF/

• Current version:– Dynamic tester and monitor generation– Static test generation up to given depth:

• Interactive• Random• Exhaustive

• Under construction:– Timed automata tester generation– Coverage

72

73

Lecture

• Papiers sur le test temporisé disponibles en ligne:

http://www-verimag.imag.fr/~tripakis/testing.html