Sur la pratique des méthodes formelles par de non praticiens :...

“Sai

y” -

Sur la pratique des méthodes formelles par de non praticiens : Autopsie d'un robot

Eric JENN, IRT Saint Exupéry et Thales Avionics

Journée FMF

LAAS, 10 octobre 2017

09/10/2017© IR

“Sai

y” -

Collaborative work in INGEQUIP project at IRT

Pierre-Alain BourdilArnaud DieumegardNing GeFaiez Zalila

with academic support from LAAS, ONERA, IRIT, ISAE

with financial backing from CGI, ANR, and industrial members:

Context

09/10/2017© IR

“Sai

y” -

Formal verification of HMIs

Correctness by construction

Formal verif. of timed systems

Formal code verification

Formal verif. of conf. dataData

SW impl.

Numerical

The patient Pathologies Remedies

09/10/2017© IR

“Sai

y” -

The patient

09/10/2017© IR

“Sai

y” -

The patient Design spaceexploration

Virtual platforms

Formaldevelopment

methods

09/10/2017© IR

“Sai

y” -

The patient

methods

A robot

An environment

A supervision station

09/10/2017© IR

“Sai

y” -

EMBEDDED SYSTEM

Ethernet CAM

TREK1000(ground)

ethernet

TwIRTee

09/10/2017© IR

“Sai

y” -

MISSION

CAN bus

Ethernet CAM

TREK1000(ground)

ethernet

TwIRTee

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

TREK1000(ground)

ethernet

TwIRTee

CHANNEL LEFT RIGHT

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

TREK1000(ground)

ethernet

TwIRTee

CHANNEL LEFT

09/10/2017© IR

“Sai

y” -

CAN bus

MONCOM: PPC

Ethernet CAM

TREK1000(ground)

ethernet

MON: ZYNQ

TwIRTee

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

H-bridgeMotorEncoder

Compas

left and right wheel

Buck analogpart

discrete

analog

discrete TREK1000(ground)

ethernet

TREK1000(on-board)

TwIRTee

COM: PPC

MON: ZYNQ

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

TwIRTee

COM: PPC

MON: ZYNQ

OS: Trampoline

OS : LINUX

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Clock synchronization: Verification of timed systems

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Clock synchronization: Verification of timed systems

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

Verification of timed systems: Fiacre and Tina

RCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

09/10/2017© IR

“Sai

y” -

Formalization (abstractions, hypothesis,…)

Clock synchronization protocol

09/10/2017© IR

“Sai

y” -

The model (structure)

09/10/2017© IR

“Sai

y” -

The model (structure)

The model (behaviour)

09/10/2017© IR

“Sai

y” -

From a crude HMI… … to a fancy Eclipse simulation environment

… with MSCs… … and causal diagrams.

09/10/2017© IR

“Sai

y” -

• From "simulation" to "advanced simulation"• Guided-simulation (property-driven simulation)

• Some specific properties have been verified: are they worth the effort?

• How to gain confidence on the model?• How to debug the model ?

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Redundancy Mngt: Verification of synchronous SW:

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RMSRCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

Verification of synchronous SW: Redundancy MngtTwIRTee architecture

2/20/20174Guillaume RIPOLL

Channel LEFT

Unit COM

Unit MON

Channel RIGHT

Unit COM

Unit MON

4 ASYNCHRONOUS UNITS

LUSTRE HLL S3

09/10/2017© IR

“Sai

y” -

Verification of synchronous SW: Redundancy Mngt

Clock synchro

Synchronous RMS

Formal verification using S3

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Mission management: Verification of configuration data

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

Formal verification of configuration data

09/10/2017© IR

“Sai

y” -

HLL S3

09/10/2017© IR

“Sai

y” -

• Consider dedicated tools!

• A way to get acquainted to the formalism and tool…

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Supervision: Formal verification of HMIs

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RCSHMI

OS : LINUX

RAMHMI

09/10/2017© IR

“Sai

y” -

RCSHMI

OS : LINUX

RAMHMIAlert 10some text

Alert 2

Alert 7

Alert 1Some text

Alert 3some text

09/10/2017© IR

“Sai

y” -

RCSHMI

OS : LINUX

RAMHMI

Predefined slots

Alert 10some text

Alert 2

Alert 7

Alert 1Some text

Alert 3some text

09/10/2017© IR

“Sai

y” -

RCSHMI

OS : LINUX

RAMHMI

Predefined slots

Alert 10some text

Alert 2

Alert 7

Alert 1Some text

Alert 3some text

Alert 2

Alert 7

Alert 10some text

Alert 1Some text

Alert 3some text

09/10/2017© IR

“Sai

y” -

Alert 2

All alerts

Alert 1

Alert 3

Alert 4

Alert 5

Alert 6

Alert 7

Alert 8

Alert 9

Alert 10

Sortingnetwork

Inital target alert

Alert 2

Alert 10

Alert 4

Alert 5

Alert 6

Alert 7

Alert 8

Alert 9

Alert 10

Priority-sorted alerts

Alert 3

Target alertselection

Target alert move

move=up/down/none

target alert

Alert 10some text

Alert 2

Alert 7

Alert 1Some text

Alert 3some text

Target slot move

Target slot selection

Routing target slottarget alert

LUSTRE LUSTRE

LUSTRE

09/10/2017© IR

“Sai

y” -

Formal verification of HMI

VISIBILITY

TASK RELATED

RELIABILITY

09/10/2017© IR

“Sai

y” -

Formal specification

Formal design

Formal verification of

implementation

Informal specification

09/10/2017© IR

“Sai

y” -

• HMIs deserve formal specification and verification

• HMIs are (probably) in the area where model-checkingtechniques are very efficient

• A very simple HMI designed using formal modelsand methods…

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Anticollision function: Correction by construction

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

09/10/2017© IR

“Sai

y” -

Refinement strategy

Requirements classification

Requirements layering

Event-B model

09/10/2017© IR

“Sai

y” -

09/10/2017© IR

“Sai

y” -

09/10/2017© IR

“Sai

y” -

Category 1.a: writing rules

aimed at avoiding

modelling errors Category 1.b:

writing rules aimed at

facilitating theproof process

Category 1.c: writing rules

aimed at facilitating the review process Category 2.a:

review rules aimed at revealing modelling

errors

09/10/2017© IR

“Sai

y” -

• Automation?

• A complete (simple) function formally developedtop to bottom using a combination of Robin and S3

• No floating point operations

09/10/2017© IR

“Sai

y” -

CAN bus

Ethernet CAM

Compas

Buck analogpart

discrete

analog

ethernet

TREK1000(on-board)

Image-based position monitoring: Numerical issues

Power control

RCS RM

Motorcontrol

OS: Trampoline

OS : LINUX

MW: CAN driver

RCSHMI

RAMHMI

OS : LINUX

09/10/2017© IR

“Sai

y” -

Odometry

In-doorpositioning

Compass

Complianceimage / location

Segment extraction

Segments

Envelope computation

Envelope

Pose OK

Pose KO

CameraImage

Hybridation

Error ellipsoid

PPC (COM)

ZYNQ (MON)

09/10/2017© IR

“Sai

y” -

• Matrix inversion(Kalman)

09/10/2017© IR

“Sai

y” -

𝑣1 = 1 + 10−11 ∙ 1020

𝑣2 = 1 − 10−11 ∙ 1020

𝑣3 = 0.98

𝑣1 = 1 ∙ 1020

𝑣2 = 1 ∙ 1020

𝑣3 = 0.98

Approx

• Eigenvectors(error ellipsoïd)

09/10/2017© IR

“Sai

y” -

(146.608,240)(146.608,240)(174.359,240)(162.089,44.2376)(158.034,44.2377)(157.953,45.6318)(157.852,44.2377)(153.796,44.2497)(144.245,240)(146.608,240)

(158.017,44.2377)(157.852,44.2377)(157.852,44.2382)(153.796,44.2497)(144.245,240)(146.608,240)(157.953,45.6318)(172.002,240)[…](158.034,44.2377)(158.017,44.2377)

polygon #0 polygon #1

• Eigenvectors(error ellipsoïd)

• Geometricalcomputations(enveloppe computation)

09/10/2017© IR

“Sai

y” -

• Excerpt from the BOOST library

09/10/2017© IR

“Sai

y” -

Speed = 1

Strange, strange…

Speed = 50

09/10/2017© IR

“Sai

y” -

• Find the best representation for hardware implementation

• Found a place where 𝟎. 𝟏 + 𝟎. 𝟏 ≠ 𝟎. 𝟐… and where it actually matters…

09/10/2017© IR

“Sai

y” -

To conclude: dealing with (so) many methods and tools…

09/10/2017© IR

“Sai

y” -

To conclude: dealing with (so) many methods and tools…

Datalogprogram

Verificationarguments Translation

Derivation tree Rules Leaves are "facts".

Translation

Safetycase

Structured argument

Evidences

Execution

Orchestration

09/10/2017 58

herein is the sole property of IRT AESE “Saint Exupéry”. No intellectual property rights are granted by the delivery of this document

or the disclosure of its content. This document shall not be reproduced or disclosed to a third party without the express written

consent of IRT AESE “Saint Exupéry” . This document and its content shall not be used for any purpose other than that for which it is

supplied. IRT AESE ”Saint Exupéry” and its logo are registered trademarks.

Merci de votre attention

Sur la pratique des méthodes formelles par de non praticiens :...

Documents

9.3.1 Le stade des opérations formelles de Piaget

Langages de Preuve - LAASprojects.laas.fr/IFSE/FMF/J3/slides/P01_Christine_Paulin.pdfLangages de Preuve FMF 2014 - Preuve de modele, preuve de programmes` Christine Paulin-Mohring

Approches Formelles dans l’Assistance au Développement de ... · AFADL 2019 i Préface L’atelier francophone AFADL sur les Approches Formelles dans l’Assistance au Développement

Algèbres de réseaux de Petri colorés - ibisc.univ-evry.fr · Algèbres de réseaux de Petri colorés Les travaux de Franck Pommereau se placent dans le domaine des méthodes formelles

Utilisation des méthodes formelles pour l'évaluation et la ...potet/Sertif/LesSlides/Ezvan-SERTIF.pdf · Utilisation des méthodes formelles pour l'évaluation et la certi cation

Méthodes formelles pour la sûreté de fonctionnement des logiciels 15 octobre 2003

MÁRIO S. ALVIM DOCTEUR DE LÉCOLE POLYTECHNIQUE LABORATOIRE DINFORMATIQUE Des approches formelles pour la protection d'information Une analyse des systèmes

Méthodes agiles vs méthodes classiques

SCHIAVETTA, Bernardo, "Les procédés de l'Anti-art, in Formules, revue des créations formelles, nº11, p. 153-168

Méthodes Formelles et Développement de logiciels Sûrs

Approches Formelles en Systèmes d'information

Étude des composants phonogrammiques des variantes formelles · MOHSEN HAFEZIAN 81 L’étude des variantes formelles ouvre un vaste champ d’observation sur le fonctionnement d’un

Introduction aux méthodes formelles - univ-reunion.frlim.univ-reunion.fr/staff/fred/Enseignement/Verif-M2/...Utiliser les mathématiques pour concevoir et si possible réaliser des

Introduction aux méthodes formelles ESIR 3 – TQL – 29 novembre 2011 David M ENTRÉ – dmentre@linux-france.orgdmentre@linux-france.org

le Régime Indemnitaire en Fonction des Sujétions de l’Expetise (IFSE) et de …©sentation... · 2017-04-26 · de l'engagement professionnel dans la Fonction Publique de l'État

DE L OBJET AU SUJET - cache.media.education.gouv.frcache.media.education.gouv.fr/file/themes/23/8/sujet_objet_721238.pdf · - Stade des opérations formelles : les jeux de règles

CHAPITRE Les pratiques informelles et formelles de ... · 411 CHAPITRE 2 Les pratiques informelles et formelles de communication interne dans les TPE et les PME Gérard REGNAULT Consultant-Formateur

naire, dont les perfections formelles sont celles de marchandises … · 2019. 10. 5. · naire, dont les perfections formelles sont celles de marchandises de luxe. Un autre haut

Rédaction d’un travail écrit Règles formellesekladata.com/8hPjtmTB0KYxQNKzecJvdZ7ohWs/redaction.pdf · 2015. 10. 14. · Rédaction d’un travail écrit – Règles formelles

Rapprocher les méthodes formelles, l’analyse statique et les tests