embarqués

Dveloppement de systmes embarqusAutomates temporiss, rseaux de Petri temporels

Franck Cassez

CNRS/IRCCyNNantes, France

http://www.lsv.ens-cachan.fr/aci-cortos

CNAM, Paris

Fvrier 2006

Systmes temps-rel embarqus

! objectif : sret de fonctionnement des systmes embarqus de typetemps-rel

contrle/commande dun procd, ordonnancement de processus,

protocole de communication, . . .! type de sret : respect des chances temporelles

! approche : utilisation de mthodes formelles

techniques mathmatiques (rigoureuses)

! mthodes formelles et cycle de dveloppement1 modlisation, spcification

modle (abstrait) de lapplication, critre de correction2 vrification/contrle/test sur modle

model-checking, observabilit, diagnostic, contrlabilit3 implmentation

production de code, vrification dune implmentation

CNAM, Paris (02/2006) Dveloppement de systmes embarqus 2 / 11

La communaut en France (non exhaustif)

! LSV, ENS-Cachan

P. Bouyer, F. Laroussinie, N. Markey, . . .

! VERIMAG, Grenoble

K. Altisen, S. Tripakis, . . .

! LAAS, Toulouse

B. Berthomieu, F. Vernadat

! LAMSADE, Paris Dauphine

B. Brard, S. Haddad

! IRCCyN, Nantes

D. Lime, O.H. Roux, O. Roux, F.C.

! IRISA, Rennes

C. Jard! LMI, Marseille

P. Niebert


Collaborations avec la communaut internationale

! ULB, Bruxelles, Belgique

Jean-Franois Raskin, L. Doyen, M. De Wulf, . . .

! Aalborg, Danemark et Uppsala, Sude

K.G. Larsen, G. Berhmann, W. Yi, . . .

! EPFL, Lausanne, Suisse

T. Henzinger

! Univ. Bangalore, Inde

D. DSouza

! Wiezmann Institute, Israel

! . . .


Modles pour les systmes temps-rel

! automates temporiss, [Alur & Dill (1994)]

! automates hybrides, [Henzinger (1996)]

! rseaux de Petri temporels, [Merlin (1974)]! avantages de ces modles :

! hypothse de temps-dense! description concise et naturelle des informations temporelles! descriptions modulaires/hierarchiques! thorie solide

! inconvnients :! reprsentation des contraintes temporelles coteuses! analyse complexe


Analyse des modles temporiss

! vrification! thorie : [Alur & Dill (1994)]! outils :

! automates temporiss : UPPAAL, KRONOS, CMC! automates hybrides : HyTech, PHAver! rseaux de Petri temporels : Romeo, Tina

! observation/contrle/test! thorie :

SED [Ramadge & Wonham89]temporiss :[Maler et al. (1995), Krichen & Tripakis (2004)]

! outils : UPPAAL TiGA

! optimisation! thorie : [Alur et al. (2001)][Behrmann et al. (2001)]

[Bouyer et al. (2004)]! outils : UPPAAL CORA TIME (scheduling)


Implmentation des modles temporiss

! production de code

! thorie : [De Wulf et al. (2004a)] [De Wulf et al. (2004b)]! outils : Elastic

automates hybrides vers BrickOS,smantique au plus tt

! modlisation/vrification du systme complet

! thorie : [Altisen & Tripakis (2005)]! outils : ceux des automates temporiss

modlisation de la plate-forme dexcution


Examples (non exhaustif)

! Philips Audio Control Protocol,synthse dun contrleur avec Elastic

! Bang & Olufsen Audio/Video Protocol,erreur trouve avec UPPAAL

! PGP,correction prouve avec UPPAAL

! flux multimediasdbit, latence, etc

! contrle de bote de vitesseMecel AB

! alimentation lectrique dun bus de communicationRomeo

! ordonnancement (et contrle) dune chane de productionsynthse dun ordonnancement et implmentation en LEGO

! job-shop schedulingordonnancement, KRONOS


References

[Altisen & Tripakis (2005)] M. Krichen and S. Tripakis.Implementation of timed automata : an issue of semantics or modeling ?In FORMATS05, 2005.

[Alur & Dill (1994)] R. Alur and D. Dill.A theory of timed automata.Theoretical Computer Science B, 126 :183235, 1994.

[De Wulf et al. (2004a)] M. De Wulf, L. Doyen, J.-F. Raskin.Almost ASAP Semantics : From Timed Models to Timed Implementations.HSCC04 LNCS 2993.

[De Wulf et al. (2004b)] M. De Wulf, L. Doyen, N. Markey, J.-F. Raskin.Robustness and Implementability of Timed Automata.FORMATS+FTRTFT04 LNCS 3253.

[Henzinger (1996)] Thomas A. Henzinger.The theory of hybrid automata.In Proc. of the 11th Annual Symposium on Logic in Computer Science (LICS96),pages 278292, IEEE Computer Society Press, 1996.

[Merlin (1974)] P.M. Merlin.A study of the recoverability of computing systems.PhD thesis, University of California, Irvine, CA, 1974.

[Alur et al. (2004)] R. Alur, M, Bernadsky, and P. Madhusudan.Optimal reachability in weighted timed games.In Proc. 31st International Colloquium on Automata, Languages and Programming(ICALP04), Lecture Notes in Computer Science. Springer, 2004.


References (cont.)

[Alur et al. (2001)] R. Alur, S. La Torre, and G. Pappas.Optimal paths in weighted timed automata.In Proc. 4th Int. Work. Hybrid Systems : Computation and Control (HSCC01), LNCS2034, pp. 4962. Springer, 2001.

[Asarin & Maler (1999)] E. Asarin and O. Maler.As soon as possible : Time optimal control for timed automata.In Proc. 2nd Int. Work. Hybrid Systems : Computation and Control (HSCC99), volume1569 of LNCS, pages 1930. Springer, 1999.

[Behrmann et al. (2001)] G. Behrmann, A. Fehnker, T. Hune, K. Larsen, P. Pettersson, J. Romijn, and F.Vaandrager.Minimum-cost reachability for priced timed automata.In Proc. 4th Int. Work. Hybrid Systems : Computation and Control (HSCC01), LNCS2034, pp. 147161. Springer, 2001.

[Bouyer et al. (2004)] P. Bouyer, F. Cassez, E. Fleury, K. G. Larsen.Optimal Strategies in Priced Timed Game Automata. FSTTCS04 (LNCS 3328).

[Maler et al. (1995)] Oded Maler, Amir Pnueli, and Joseph Sifakis.On the synthesis of discrete controllers for timed systems.In Proc. 12th Annual Symposium on Theoretical Aspects of Computer Science(STACS95), volume 900, pages 229242. Springer, 1995.

[Krichen & Tripakis (2004)] M. Krichen and S. Tripakis.Real-time testing with timed automata testers and coverage criteria.In Joint conference on Formal Modelling and Analysis of Timed Systems and FormalTechniques in Real-Time and Fault Tolerant System (FORMATS-FTRTFT04), 2004.


References (cont.)

[Ramadge & Wonham89] P.J. Ramadge and W.M. Wonham.The control of discrete event processes.Proc. of IEEE, 77 :8198, 1989


Documents

embarqués