Frédéric Boniol12-14 juin 2011 – R2I2011 Vérification formelle des systèmes et des architectures embarqués critiques (avioniques (Airbus)) Frédéric Boniol

Frédéric Boniol 12-14 juin 2011 – R2I’2011

Vérification formelle des systèmes et des architectures embarqués critiques (avioniques (Airbus))

Frédéric Boniol

ONERA, Toulouse


Plan

1. Contexte, et exemple Systèmes embarqués Quels besoins de vérification ?

2. Vérification formelle de propriétés de « sûreté de fonctionnement »

3. Vérification formelle de propriétés « temps-réel »– calculateur (respect d’échéance, pire temps de réponse)– réseau (pire temps de traversé)

4. Vérification formelle de propriétés « fonctionnelles »– Sur des modèles– Sur le code

5. Les problèmes non résolus, et les défis à relever

6. Annexe : Evolution vers la DO-178C, ce que ça va changer dans la pratique


1. Contexte, exemple,

et objectifs de vérification


Le contexte : les systèmes embarqués critiques

Quelques exemples classiques (et significatifs)



Généralisation ….

Système pilotant

électroniqueinformatique

Système à piloter(ex : une chaîne de production, une réaction chimique…)

données

mesures

événements

Dynamique imposée par le système à piloter

commandes

AutressystèmesAutres

systèmesAutressystèmes



Leurs principales caractéristiques …– Criticité :

Si le bon fonctionnement du système à piloter est « vital », alors le système pilotant doit être « sûr de fonctionnement »

• Exemple : contrôle des portes d’un ascenseur…

– Dynamique du « pilotant » assujettie à la dynamique du « piloté »

Si le système à piloter a sa propre dynamique (dans le temps), et si son bon fonctionnement est « vital », alors le système pilotant doit être « temps-réel ».

• Exemples : contrôle moteur, contrôle de la trajectoire d’un aéronef, contrôle d’une réaction nucléaire…

L’ascenseur ne se déplace pas les portes ouvertes=> Système à états discrets



Leurs principales caractéristiques …– Criticité :


• Exemple : contrôle des portes d’un ascenseur…


Si le système à piloter a sa propre dynamique (dans le temps), et si son bon fonctionnement est « vital », alors le système pilotant doit être « temps-réel ».


Démonstration de l’absence d’erreurs dans la spécification et dans le logiciel

Démonstration de l’absence d’erreurs dans la spécification et dans le logiciel

Démonstration de la tolérance aux défaillancesDémonstration de la tolérance aux défaillances

Démonstration de la correction temporelle du systèmeDémonstration de la correction temporelle du système


Zoom sur les systèmes de contrôle commande critique …

Exemple : les commandes de vol …


Servocommande

Câble mécanique

Commande classique « servomoteur » (A300 / A310)

SMServomoteurPilote

automatique Liaison électrique

Exemple : les commandes de vol (CdV)…

Evolution du système de contrôle du vol … en 25 ans

Commande électriques « lois normales » (A320, A330, A340, A380 … )

Pilote automatique Liaison électrique

Liaison électrique Cde de vol








- Système « pilotant » = « Cde de vol »

- Système « à piloter » = l’avion

= vital (transport de personne) => exigences de sûreté de fonctionnement pour les CdV => exigences d’absence d’erreur comportementale => exigences d’absence d’erreur à l’exécution

= dynamique (mouvement physique suivant des équations différentielles) => exigences de temps-réel pour les CdV






Ce qu’il faut vérifier : 1. la sûreté de fonctionnement

Vérifier que - compte tenu de l’architecture du système, de ses logiques de redondance et de reconfiguration, des exigences allouées à chaque fonction, du comportement dysfonctionnel de chaque composant physique

- alors chaque fonction répond aux objectifs de taux de défaillance.

Vérifier que - compte tenu de l’architecture du système, de ses logiques de redondance et de reconfiguration, des exigences allouées à chaque fonction, du comportement dysfonctionnel de chaque composant physique

- alors chaque fonction répond aux objectifs de taux de défaillance.



Ce qu’il faut vérifier : 2. la correction fonctionnelle

Modèles SCADE + codage automatique + codage manuel C


Vérifier que les modèles et le code C satisfont :

- des exigences de contrôle (précision, robustesse des lois de commandes…)

- des exigences de sûreté de fonctionnement (détection de pannes…)- …

Vérifier que les modèles et le code C satisfont :

- des exigences de contrôle (précision, robustesse des lois de commandes…)

- des exigences de sûreté de fonctionnement (détection de pannes…)- …

Vérifier que le code C ne contient pas d’erreurs :- division par zéro- débordement de range- …

Vérifier que le code C ne contient pas d’erreurs :- division par zéro- débordement de range- …



Ce qu’il faut vérifier : 3. le comportement temps-réel

Système multi-tâche + ordonnancement temps réel

Système multi-tâche + ordonnancement temps réel

Réseau de communication Réseau de communication

Calculer pour chaque communication le temps de traversée pire cas du réseau

Calculer pour chaque communication le temps de traversée pire cas du réseau

Calculer le temps d’exécution pire cas de chaque tâche (WCET)

Calculer le temps d’exécution pire cas de chaque tâche (WCET)

Vérifier que chaque tâche respecte ses exigences temps-réel (échéance, gigue…)

Vérifier que chaque tâche respecte ses exigences temps-réel (échéance, gigue…)

Calculer pour chaque chaine fonctionnelle, ses caractéristiques temps-réel (latences, fraicheur des données…)

Calculer pour chaque chaine fonctionnelle, ses caractéristiques temps-réel (latences, fraicheur des données…)



Ce qu’il faudrait aussi vérifier : la sécurité des données….

?


2. Vérification de propriétés de sûreté de

fonctionnement

(Pierre Bieber)



– Appliquer les ordres de pilotage aux gouvernes (calcul des angles de déflection et application des angles)

– Contrôle du trim (réduction des efforts sur la gouverne de profondeur)

– Offrir un pilotage indépendant de la configuration de vol

– Offrir un virage à altitude constante– Contrôler les oscillations de l’avion

• Le roulis hollandais• Les oscillations de la structure • …

Les exigences de sûreté de fonctionnement

dépendent de la fonction du système :

Catastrophique

Mineure

Hazardous

Hazardous

HazardousCatastrophique

10-9 =

10-5 =

10-7 =

10-7 =

10-7 =10-9 =





Exigence de démonstration que La probabilité que la fonction ne

soit plus remplie consécutivement à une panne matérielle est inférieure au taux requis

Analyse dysfonctionnelle !!

Catastrophique

Mineure

Hazardous

Hazardous

HazardousCatastrophique

10-9 =

10-5 =

10-7 =

10-7 =

10-7 =10-9 =




Analyse dysfonctionnelle

Analyses « dysfonctionnelles » : démarche généraleÀ partir de l’architecture du système…

– Identification des « événements redoutés »

– Identification des pannes possibles sur cette architecture, et de leur relation de dépendance

– Identification des probabilités de ces pannes

– Identification de leurs effets sur les composants actifs du système (capteurs, actionneurs, fonctions)

Listes des événements redoutés

Listes de pannes + probabilitésModes de défaillance des composants actifs

Estimation des probabilités des événements redoutés


Analyse dysfonctionnelle ?

Mais … !!!– Un très grand nombre (voire une infinité) de modes de défaillance

possibles Analyse impossible à un niveau « grain fin » Abstraction nécessaire !!

– Idée : abstraction des fonctions et des flux

Listes des événements redoutés

Listes de pannes + probabilitésModes de défaillance des composants actifs

Estimation des probabilités des événements redoutés



Mais … !!!– Un très grand nombre (voire une infinité) de modes de défaillance

possibles Analyse impossible à un niveau « grain fin » Abstraction nécessaire !!

– Idée : abstraction des fonctions et des flux

Fa Aa

Ca

aobs in {ok, ko, err}

acmd in {ok, ko, err}

Schéma abstrait

gouva in {ok, ko, err}F A

Cobs : [-10;+10]

cmd : [-10;+10]

Schéma fonctionnel concret

gouv : [-10;+10]

abstraction



Puis…– Étude des comportements de panne sur le modèle abstrait

Fa Aa

Ca

aobs = err

acmd = err

dysfonctionnel 2

gouva = err

Fa Aa

Ca

aobs = ok

acmd = err

dysfonctionnel 1

gouva = err

Fa Aa

Ca

aobs = ok

acmd = ok

nominalFa Aa

Ca

aobs = ok

acmd = ok

dysfonctionnel 3

gouva = err

gouva = ok



Fa Aa

Ca

aobs = ok

acmd = ok

nominalFa Aa

Ca

aobs = ok

acmd = ok

dysfonctionnel 3

gouva = err

panne C

panne F

panne A

gouva = ok

Fa Aa

Ca

aobs = ok

acmd = err

dysfonctionnel 1

gouva = err

Fa Aa

Ca

aobs = err

acmd = err

dysfonctionnel 2

gouva = err



Un graphe fini de modes de défaillances Génération d’arbres de défaillances Calcul de la probabilité d’avoir la gouverne en état « err »

• P(gouv=err) ~ P(panne C)

+ P(panne A)

+ P(panne F)

panne C

panne A

panne Fobs

a = okcmd

a = okgouva = ok

obsa = err

cmda = err

gouva = err

obsa = ok

cmda = ok

gouva = err

obsa = ok

cmda = err

gouva = err

panne C

panne F

panne C


AltaRica pour l’analyse des dysfonctionnements

• Approche formalisée par la langage AltaRica (LaBRI)– Langage à base d’automates de contraintes– Sémantique formelle : automate asynchrone + vecteurs de

synchronisation

R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Evénement redouté : perte non détectée de ordre1 et ordre2Exigence :

proba < 10-7



R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Ri : OKi KOi

ERRi

perteRi

perteNDRi

Ai : OKi KOi

ERRi

in OKi : alti = ok;in KOi : alti = ko;in ERRi : alti = err;

perteAi

perteNDAi

Synch : (perteRi, perteAi), (perteNDRi, perteNDAi) pour i=1,3

Proba : -perteRi = 10-3

-perteNDRi = 10-4

Proba : -perteRi = 10-3

-perteNDRi = 10-4



R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Vi : OKi KOi

ERRi

in OKi : zi= vote(alt1,alt2,alt3);in KOi : zi= ko;in ERRi : zi= err;

perteVi

perteNDVi

Synch : (perteR4, perteV1), (perteNDR4, perteNDV1)Synch : (perteR5, perteV2), (perteNDR5, perteNDV2)



R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Fi : OKi KOi

ERRi

perteFi

perteNDFi

Synch : (perteR4, perteF1), (perteNDR4, perteNDF1)Synch : (perteR5, perteF2), (perteNDR4, perteNDF2)

in OKi : oi= zi;in KOi : oi= ko;in ERRi : oi= err;



R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Ci : OKi KOi

ERRi

perteCi

perteNDCi

Synch : (perteR4, perteC1), (perteNDR4, perteNDC1)Synch : (perteR5, perteC2), (perteNDR4, perteNDC2)

in OKi : ordrei = if (o1==o2) then oi else ko;in KOi : oi= ko;in ERRi : oi= err;



R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Configurations à 2 pannes menant à l’événement redouté :-perteNDR1 + perteNDR2-perteNDR1 + perteNDR3-perteNDR2 + perteNDR3-perteNDR4 + perteNDR5- …


proba < 10-7

Proba ≈ 4.10-8



R1R1

A1A1

R2R2

A2A2

R3R3

A3A3

alt1

alt2

alt3

R4R4

V1V1 F1F1 C1C1z1 o1

R5R5

V2V2 F2F2 C2C2z2 o2

ordre1

ordre2

Configurations à 2 pannes menant à l’événement redouté :-perteNDR1 + perteNDR2-perteNDR1 + perteNDR3-perteNDR2 + perteNDR3-perteNDR4 + perteNDR5-perteNDR1 + perteR2, … => Proba ≈ 6,4 . 10-7

=> Exigence non respectée !!!


proba < 10-7



• Approche formalisée par la langage AltaRica

– Possibilité de vérifier des propriétés d’accessibilité (ou de non accessibilité) d’un événement redouté donné (par model checking)

– Possibilité de générer automatiquement des arbres de défaillances, puis de calculer les coupes minimales et les probabilités des événements redoutés

– Outil développé par Dassault-System (Cecilia-OCAS)– Utilisation opérationnelle par Airbus pour l’ensemble des

systèmes (y compris les systèmes non informatiques).


3. Vérification de propriétés « temps-réel »


La question du temps réel

Leurs principales caractéristiques (rappel) …– Criticité :


• Exemples : contrôle des portes d’un ascenseur…


Si le système à piloter a sa propre dynamique (dans le temps), et si son bon fonctionnement est « vital », alors le système pilotant doit être temps réel.


L’ascenseur ne se déplace par les porte ouverte=> Système à états discrets



L’exemple dans l’exemple : le contrôle du roulis en lacet

Angle de lacet

temps




Angle de lacet

temps

Une commande correcte « dans les temps »




Angle de lacet

temps

Une commande incorrecte temporellement (à contre temps)

=> Commande correcte fonctionnellement mais aux mauvais instants !



Présence dans le système de : - retards - gigues



Fréquence de la boucle

Latence capteur

Temps de réponse actionneur

Latence calculateur + réseau

temps

Angle de lacet






Fréquence de la boucle

Latence capteur

Temps de réponse actionneur

Latence calculateur + réseau

temps

Angle de lacet Besoin : calcul de bornes supérieures de ces

- retards - gigues

Besoin : calcul de bornes supérieures de ces

- retards - gigues





- retards - gigues


- retards - gigues

Deux niveaux- calcuteurs- réseaux

Deux niveaux- calcuteurs- réseaux

F1, F2

F3, F4

F5, F6

Worst case execution time (WCET) ?

Worst case response time (WCRT) ?

Worst case traversal time (WCTT) ?

Worst case freshness (WCF) ?



• En général, calculs infaisables – Seule solution : tests et mesures

=> Devenus impossibles dans les architectures « modernes » (asynchrones)

• Mais, bonne nouvelle : dans les systèmes critiques– Calculateurs simples sans mécanismes d’optimisation– Logiciels simples (sans pointeurs, sans dynamicité…)– Architectures logicielles simples (tâches périodiques, priorités fixes, pas de

création d’objets…)

WCET et WCRT calculables

– Protocoles réseaux à base de contrats et sanction en cas de non respect des contrats

– Trafics réseaux simples (périodiques, sans dynamicité…)

=> WCTT calculable


Calcul du WCET (1/1)

• WCET : Méthode (en bref)– Au niveau du code binaire

– Modélisation de l’exécution du programme sous la forme d’un ILP

– Prise en compte des politiques de gestion des ressources du processeur (cache, pipe-line) (pire cas calculé par interprétation abstraite)

– Expression du temps d’exécution comme une expression de l’ILP

– Recherche du maximum de cette expression

• Outils (chez Airbus) : aiT – Développé par Absint (www.absint.com)

– DO-178B niveau A

• Limite : – ne marche pas pour les processeurs modernes (multi-core)


Calcul du WCRT (1/1)

• WCRT : Méthode (en bref)– Dans le cas de tâches indépendantes à priorités fixes

• Nombreux outils– (mais Excel suffit)

• Limite– Ne s’applique que pour les systèmes de tâches périodiques à priorité fixe

– Ne s’applique que pour les architectures mono-processeurs

• Alternative : model checking…


Calcul du WCTT (1/4)

• WCTT : Méthode (en bref)– Méthode du « Network Calculus »– Base mathématique = algèbre (min, +)

• Idées (simples) du Network Calculus– À partir d’une « enveloppe » maximale du trafic

entrant X(t)– A partir d’une caractérisation du service de chaque

switch• minimale β(t)• maximale Β(t)

Calcul du trafic sortant • minimal y(t)• maximal Y(t)

F1, F2

F3, F4

F5, F6

X(t)y(t)

β(t)



• Idées (simples) du Network Calculus (suite)=> Calcul du délai

F1, F2

F3, F4

F5, F6

X(t)y(t)

β(t)



• Idées (simples) du Network Calculus (suite)=> Dimensionnement du switch

F1, F2

F3, F4

F5, F6

X(t)y(t)

β(t)



• Outils (chez Airbus) : ConfGen (outil maison)– Utilisé pour la certification A380

• Limite :– Suppose que chaque flux respecte son contrat– Pas de nouveaux flux en cours d’opération– Pas de prise en compte de niveaux de priorité

F1, F2

F3, F4

F5, F6


4. Vérification fonctionnelle

- Au niveau des modèles

- Au niveau du code

(Virginie Wiels)



Ce qu’il faut vérifier : 2. la correction fonctionnelle



Vérifier que le code C ne contient pas d’erreurs- division par zéro- débordement de range- …

Vérifier que le code C ne contient pas d’erreurs- division par zéro- débordement de range- …

Vérifier que les modèles et le code C satisfont- des exigences de contrôle (précision, robustesse des lois de commandes…)- des exigences de sûreté de fonctionnement (détection de pannes…)- …

Vérifier que les modèles et le code C satisfont- des exigences de contrôle (précision, robustesse des lois de commandes…)- des exigences de sûreté de fonctionnement (détection de pannes…)- …


La question de la vérification fonctionnelle

• En général problème difficile

• Mais, deux bonnes nouvelles (avionique – Airbus)1. Model based design

– Basé sur le langage synchrone SCADE : sémantique formelle et déterministe

Réduction de l’espace des états Espoir d’application des techniques de model-checking

– Génération de code « certifié » automatique Vérifier les modèles suffit à la vérification du système

2. Les logiciels codés manuellement sont simples

– Pas de pointeur, pas d’allocation dynamique de mémoire, pas de code dynamique…

Espoir d’application des techniques de vérification de logiciel


La question de la vérif. fonctionnelle : au niveau modèle

Le cycle Airbus…



• Vérification de modèles SCADE : par model checking– Exigences : propriétés de « safety » = jamais une mauvaise chose– Exemple :

« sous l’hypothèse que les deux manches ne tombent pas en panne,

il y a toujours un manche considéré actif pendant toute période de 100ms »

Retour d’expérience (1/2) :– Pas adapté aux modèle SCADE contenant des réels ou des

entiers

– Adapté aux modèles booléens



Retour d’expérience (2/2) :

– Encore inefficace pour montrer qu’un système SCADE ne contient pas d’erreur

– Efficace pour trouver les erreurs

– (Difficulté d’interpréter les contre-exemple)

Utilisation du model checking en moyen de débugg itératif, en non pas en certification


La question de la vérif. Fonctionnelle : au niveau du code

Le cycle Airbus…


La question de la vérif. fonctionnelle : au niveau du code

• Au niveau du logiciel codé manuellement (en C)– Rappel : le logiciel est simple Possibilité (espoir) d’appliquer des méthodes de « preuve » ou de

« vérification »

• Retour d’expérience (1/3)1. Méthode de preuve de type Logique de Hoare (méthode déductive,

weakest precondition)

– Vérification de la conformité du code aux exigences de bas niveau, en remplacement du test unitaire

• Pas de division par zéro, pas de racine carré négative…

– interactif

– Outils : CAVEAT, FRAM-C (CEA)

– Qualifié DO-178B niveau A pour A380



• Retour d’expérience (2/3)

2. Méthode par interprétation abstraite– Preuve d’absence de RTE telles que division par zéro, numerical

overflow, out of bounds access to an array.– Automatique

– Outils : ASTREE (Ecole Normale Supérieure, et commercialisé par Absint)



• Retour d’expérience (3/3)

3. Méthode par interprétation abstraite

– Calcul des erreurs numériques (arrondi) introduites par les opérateurs numériques

– Sur le C ou l’assembleur– Automatique

– Outils : FLUCTUAT (CEA)

• Bilan– Bonne couverture du niveau C

– Couverture du niveau modèle encore à améliorer


5. Les problèmes non résolus, et les défis à relever


Synthèse : ce qui est bien / mal fait …

Vérif. temps-réel

Vérif. fonctionnelle des modèles

Vérif. du logiciel

Vérif. sûreté de fonctionnement

Vérif. sécurité des données

Pour les systèmes actuels…


Les défis à relever… (1/2)

• Corrélation entre les différents modèles de vérification ?– Comment garantir que le modèle AltaRica de sûreté de fonctionnement

est une abstraction correcte du système (et de ses logiciels) ?

• Intégration des architectures multi-core– Impact sur les méthodes de vérification temps-réel ?

• Evolution vers des fonctions plus événementielles– Complexification des trafics réseaux

– Complexification des ordonnancements calculateurs


Les défis à relever… (2/2)

• Evolution vers des nouveaux patterns d’architectures– Orientées services

– Reconfigurables

• Passage à l’échelle du model-checking

• Prise en compte de la dimension sécurité– Nouvelles architectures de sécurité pour les systèmes embarqués ?


6. Annexe : Evolution vers la DO-178C :

Ce que ça changera, en quoi les méthodes formelles seront reconnues…

(Virginie Wiels)


Certification et méthodes formelles

• Méthodes formelles utilisées pour les systèmes critiques– Généralement contraints par des standards de certification

• Transports– Ferroviaire, Aéronautique, Espace, Automobile

• Méthodes formelles recommandées par certains standards– Par exemple, ferroviaire


DO-178

• DO-178B– Standard de certification pour le logiciel aéronautique,1992– Définit des objectifs pour chaque étape du processus de développement

• DO-178C– Mise à jour du DO-178 entamée en 2005, fin prévue 2010– Core document + 4 suppléments techniques

• Tools• Object Oriented technologies• Model Based Design• Formal Methods


DO-178B

Liens ARP 4754 / DO-178B

Le niveau de développement du logiciel est déterminé en fonction du niveau de certification du système dans lequel il intervient, de la gravité des dysfonctionnements potentiels de ce système.

Le développement du logiciel doit ensuite respecter les objectifs définis pour ce niveau dans l’ED-12B / DO-178B.

Failure condition DAL (development assurance level)

CAT (10-9) A

HAZ (10-7) B

MAJ (10-5) C

MIN D

No safety effect E


DO-178B

1. Introduction

2. System aspects relating to software development

3. Software life cycle

4. Software planning process

5. Software development processes

6. Software verification process

7. Software configuration management process

8. Software quality assurance process

9. Certification liaison process

10. Overview of aircraft and engine certification

11. Software life cycle data

12. Additional considerations Annex A: Process objectives and outputs by software level Annex B: Acronyms and glossary of terms

SOFTWARE CONSIDERATIONS IN AIRBORNE SYSTEMS

AND EQUIPMENT CERTIFICAION

RTCA

DOCUMENT NO. RTCA/DO-178BDecember 1, 1992

Prepared by: SC-167

“Requirements and Technical Concepts for Aviation”


Software development processes

• Software requirements process– Develop high-level requirements (HLR) from outputs of the system process

• Software design process– Develop low-level requirements (LLR) and software architecture from high-level

requirements

• Software coding process– Implement source code from the software architecture and the low-level

requirements

• Integration process– Load executable object code into the target hardware for hardware/software

integration


SystemRequirements

High-LevelRequirements

SoftwareArchitecture

Source Code

ExecutableObject Code

Low-LevelRequirements

Compliance Robustness

Compatible With Target


Accuracy & Consistency HW Compatibility VerifiabilityConformance Algorithm Accuracy

Verifiability ConformanceAccuracy & Consistency

Complete & Correct

Compliance Traceability

Architecture Compatibility Compliance Traceability

ComplianceCompliance Traceability

Accuracy & ConsistencyHW Compatibility Verifiability Conformance Algorithm Accuracy

ConsistencyHW Compatibility Verifiability Conformance Partition Integrity

DO-178/ED-12 – Verification Process


Verification process

Activités : revues, analyses, test Analyses : repeatable evidence of correctness Reviews : qualitative assessment of correctness Test


DO-178C Formal Methods Supplement

Permettre l’utilisation des Méthodes formelles à la place de méthodes conventionnelles

– Fournir un guide pour l’utilisation des méthodes formelles • Modifier des objectifs existants• Définir de nouveaux objectifs• Décrire les activités nécessaires • Décrire les arguments pour satisfaire les objectifs

– Fournir des informations sur les méthodes formelles – Identifier et présenter leurs caractéristiques


Table des matières

• Introduction• System aspects related to software development • Software life cycle• Software planning process• Software development process • Software verification process• Software configuration management process• Software quality assurance process• Certification liaison process• Overview of aircraft and engine certification• Software life cycle data


Formal Method

Descriptive notations and analytical methods used to construct, develop and reason about mathematical models of system behavior

Formal model

Formal Analysis

A formal method is a formal analysis carried out on a formal model.

What is a Formal Method ?


A model is an abstract representation of a given set of aspects of a system that is used for analysis, simulation, code generation, or any combination thereof

Formal Method

Formal model

Formal Analysis

A formal notation is a notation having a precise, unambiguous, mathematically defined syntax and semantics.

A formal model is a model defined using a formal notation

What is a Formal Model ?


Formal Method

What is a Formal Analysis ?

• The use of mathematical reasoning to guarantee that properties are always satisfied by a formal model.

Formal model

Formal Analysis


A method is formal if it has a sound mathematical basis, typically realized by a formal notation:

A sound method never assert that a property is true when it is not.

Formal model of the requirements

Formal Analysis

OK

X Not Sound

Being Sound


When a formal model is created from an informal item to do a formal analysis

Requirements

Formal model of the requirements

Formal Analysis

Results

We need to be sure that whatever is proved about the formal model also applies to what is modeled.

Then review or analysis should be used to demonstrate that the formal statement is a conservative representation of the informal requirement

Conservative representation


SystemRequirements

High-LevelRequirements


Source Code








Complete & Correct






DO-178/ED-12 – Verification Process


FM Supplement : Formal verification

Formal Analysis might replace :– Review and analysis objectives.


HLR Formal

HLR




Complete & Correct



SystemRequirements


Source Code









When HLR are formaly expressed

Formal analysis can be used

FM Supplement : Formal verification instead of reviews


HLR Formal

HLR



Complete & Correct



SystemRequirements


Source Code









When HLR and LLR are formaly expressed

Formal analysis can be used

Formal LLR


FM Supplement : Formal verification instead of reviews



Formal Analysis might replace :– Review and analysis objectives– Conformance tests versus HLR & LLR– Robustness tests


HLR



Complete & Correct



SystemRequirements


Source Code









When LLR are formaly expressed with a conservative representation

between code and EOC, then Formal analysis can be used to replace

some tests

Formal LLR


Conservativerepresentation

X

FM Supplement : Formal verification for EOC


Coverage

• Test – Functional coverage: test cases for each requirement– Structural coverage of the code by the test cases

• Formal methods: the structural coverage objectives are replaced by

– Each requirement is completely covered– The set of requirements is complete with respect to the

function– There is no non expected dependencies between output and

input data– There is no dead code




Formal Analysis might help for verification of compatibility with the hardware.


HLR



Complete & Correct



SystemRequirements


Source Code









Properties might be proved directly on EOC : WCET, Stack usage, …


FM Supplement : Formal verification for EOC




Formal Analysis might help for verification of compatibility with the hardware

Formal Analysis cannot replace HW/SW integration tests

Therefore testing will always be required.

Documents

Frédéric Boniol12-14 juin 2011 – R2I2011 Vérification formelle des systèmes et des architectures embarqués critiques (avioniques (Airbus)) Frédéric Boniol