Interprétation abstraiteet validation de logiciels critiques

Matthieu Martel

Systèmes embarqués

Systèmes embarqués : Systèmes informatiques (logiciel+matériel) conçus pour être intégrés dans des objets industriels

Systèmes embarqués

Quelques caractéristiques :

Systèmes électroniques et informatiques autonomes,

sans entrées ni sorties standard (clavier et écran)

Capacités limitées (puissance de calcul, autonomie, mémoire, etc.)

Difficilement modifiables après livraison

Contraintes de coûts :

• coût de développement (petites séries, ex : avion)

économies d’échelle (grandes séries, ex : téléphone)

Systèmes critiques

Systèmes critiques : systèmes embarqués dont une panne peut être catastrophique (conséquences humaines, financières)

Missile Patriot (1991)

Compteur (temps) : 1/10 ajouté tous les dixièmes de seconde

En binaire :

1/10 = 1/24 + 1/25 + 1/28 +... = 0.00011001100

Codé sur 24 chiffres binaires (bits) :

erreur = 9.5 × 10-8

Au bout de 100 heures :

100 x 3600 × 10 × 9.5 × 10-8 = 0.34 secondes

• Vitesse du Scud : 1676 ms-1

Erreur > 500 mètres

Ariane 5 (1996)

Après un décollage normal la fusée a eu un comportement nominal jusqu'à la 36ème secondes de vol. Puis les systèmes de référence inertielle (SRI) ont été simultanément déclarés défaillants. Sur la base d'informations de diagnostic du SRI traitées comme des instructions de vol, le calculateur de bord a provoqué le braquage en butée des tuyères des boosters, puis du moteur Vulcain d'Ariane 5 qui jusque là suivait parfaitement sa trajectoire de vol. C'est ce braquage intempestif des moteurs qui faisant brusquement basculer le lanceur l'a amené à se briser sous les efforts aérodynamiques et à exploser en vol, peu avant sa destruction télécommandée. Le SRI n'a pas transmis de données correctes parce qu'il était victime d'une erreur d'opérande trop élevée du "biais horizontal" de la fonction d'alignement interne de la centrale. Le calcul de cette variable est lié à la vitesse horizontale détectée par la plate-forme inertielle. Or, sur Ariane 5, l'accélération au décollage est beaucoup plus forte que sur Ariane 4, et la vitesse horizontale s'accroît cinq fois plus rapidement. La variable a donc dépassé la plage des valeurs autorisée par le logiciel de vol. La fonction d'alignement qui reste active environ 40 secondes après est une exigence d'Ariane 4 mais n'a aucune utilité sur Ariane 5. Elle a cependant été maintenue pour des raisons de commodité. La fonction comprend sept variables dont seulement quatre sont protégées. Lors de la conception, il n'avait pas été jugé nécessaire de protéger le calculateur contre un arrêt de fonctionnement dû à une valeur excessive de la variable lié à la vitesse horizontale. Cette décision a été prise sans que l'on analyse ou comprenne parfaitement les valeurs que cette variable pourrait prendre lorsque la fonction d'alignement est autorisée à fonctionner après le décollage.

QuickTime™ et undécompresseur

sont requis pour visionner cette image.

Coupure électrique (2003)

Environ 50 millions de personnes touchées dans le nord-est américain

Cause : hasard de course (race condition) :

solde s?solde s?

si possible retirer x

si possible retirer x

modifier s : s-x

modifier s : s-x

1000€

1000€

1000€

1000€

retirer

x=600

retirer

x=600

retirer x=60

0

retirer x=60

0

400€400€ -200€

-200€

compte commun

Autres “bugs” célèbres

Mars climate orbiter (1999) : confusion entre systèmes métrique et impérial (125 millions de dollars)

USS Yorktown (1998) : erreur d’un opérateur qui saisit la valeur zéro. ÷ par zéro et propagation de l’erreur. Bateau arrêté en pleine mer quelques heures

Pentium (1994) : erreur dans la division. Coût : environ 475 millions dollars

5505001 ÷ 294911 ➙ 18.66600093 ≠ 18.66665197x = 4195835, y = 3145727 z = x-(x ÷ y) × y ➙ 256 ≠ 0

“Bugs” : classification

Opérations illicites (USS Yorktown) :

1÷0 √-1

Dépassements de capacité (Ariane 5) :

entiers souvent entre -32767 32767

6900 × 5 = +∞

Erreurs d’arrondi (Patriot) :

1/10 = 0.00011001100

• Synchronisations (coupure électrique)

hasards de course

• Autres : spécifications (Pentium, Mars orbiter), accès mémoire, etc.

Sûreté de fonctionnement

Nécessité de garantir le bon fonctionnement des systèmes critiques!

Sûreté : absence de comportement indésirable

l’airbag ne se déclenche pas sans raison

Vivacité : bon comportement du système (plus difficile à établir)

l’airbag se déclenche en cas d’accident

Quelques ordres de grandeur

Avion : O(100000) LOCs, O(1000) variables, heures

Voiture : O(10000) LOCS

ATV (Galileo) : O(1000000) LOCs, jours

Centrale nucléaire : mois

static const NUM TRANSF2_B06_C2 = -1.362407E+00;static const NUM TRANSF2_B06_C3 = 7.830931E-01;static const NUM TRANSF2_B06_C4 = 1.362407E+00;static const NUM TRANSF2_B06_C5 = -6.844878E-01;static const NUM LIM_A1_E2 = 8.000000E+00;static const NUM LIM_A1_E3 = -8.000000E+00;static const NUM K_A2_E2 = -6.236000E-01;static const NUM AFFECT_N_1_E1 = 2.000000E+00;static const NUM SWITCH_N_E93_E1 = 3.500000E+00;static const NUM SWITCH_N_A6_E1 = 0.000000E+00;static const BOO AFFECT_B_1_E1 = FALSE;static NUM PADN5;/*Mod JS*//*SUB(1,PLDQCMMMOY,PDQMM,X611Z01)*/SUB(1,PDQCMMMOY,PDQMM,X611Z01)/*SUB(1,PDQCMMMOY,0,X611Z01)*//*Fin Mod JS*/K(A1,X611Z01,K_A1_E2,X611Z02)AFFECT_B(1,AFFECT_B_1_E1,BOFFACS1)TRANSF2(B06,X611Z02,X611Z02,X611Z02,BOFFACS1,X611Z17,TRANSF2_B06_C1, \ TRANSF2_B06_C2,TRANSF2_B06_C3,TRANSF2_B06_C4,TRANSF2_B06_C5)LIM(A1,X611Z17,LIM_A1_E2,LIM_A1_E3,PLEPS)ADD(2,PFOSV,PLEPS,X611Z16)K(A2,PDQMM,K_A2_E2,X611Z03)AFFECT_N(1,AFFECT_N_1_E1,X611Z04)INVNUM(1,X611Z04,PADN5)LIM(A2,X611Z03,X611Z04,PADN5,X611Z05)ADD(3,X611Z16,X611Z05,SANO1)

static const NUM TRANSF2_B06_C2 = -1.362407E+00;static const NUM TRANSF2_B06_C3 = 7.830931E-01;static const NUM TRANSF2_B06_C4 = 1.362407E+00;static const NUM TRANSF2_B06_C5 = -6.844878E-01;static const NUM LIM_A1_E2 = 8.000000E+00;static const NUM LIM_A1_E3 = -8.000000E+00;static const NUM K_A2_E2 = -6.236000E-01;static const NUM AFFECT_N_1_E1 = 2.000000E+00;static const NUM SWITCH_N_E93_E1 = 3.500000E+00;static const NUM SWITCH_N_A6_E1 = 0.000000E+00;static const BOO AFFECT_B_1_E1 = FALSE;static NUM PADN5;/*Mod JS*//*SUB(1,PLDQCMMMOY,PDQMM,X611Z01)*/SUB(1,PDQCMMMOY,PDQMM,X611Z01)/*SUB(1,PDQCMMMOY,0,X611Z01)*//*Fin Mod JS*/K(A1,X611Z01,K_A1_E2,X611Z02)AFFECT_B(1,AFFECT_B_1_E1,BOFFACS1)TRANSF2(B06,X611Z02,X611Z02,X611Z02,BOFFACS1,X611Z17,TRANSF2_B06_C1, \ TRANSF2_B06_C2,TRANSF2_B06_C3,TRANSF2_B06_C4,TRANSF2_B06_C5)LIM(A1,X611Z17,LIM_A1_E2,LIM_A1_E3,PLEPS)ADD(2,PFOSV,PLEPS,X611Z16)K(A2,PDQMM,K_A2_E2,X611Z03)AFFECT_N(1,AFFECT_N_1_E1,X611Z04)INVNUM(1,X611Z04,PADN5)LIM(A2,X611Z03,X611Z04,PADN5,X611Z05)ADD(3,X611Z16,X611Z05,SANO1)

Exemple de fonctionnalité : l’ATV

Inflation du logiciel

L'avion qui "bat des ailes" a fédéréde nombreux chercheurs

L'excitation qui règne chez Airbus est également perceptible dans les laboratoires qui collaborent au projet. En posant des problèmes inédits, le futur géant du ciel représente un défi pour les scientifiques. [...]

L'effet A380 dépasse largement le cadre régional. Il touche l'ensemble de l'Europe et met à contribution des laboratoires qui n'ont pas forcément de relations avec l'aéronautique. C'est le cas de l'Ecole normale supérieure (ENS) de Paris, où Patrick Cousot, professeur d'informatique, anime une équipe de sept personnes travaillant sur le projet Astrée (associant le CNRS, l'ENS et Polytechnique). "L'ordinateur possède des limitations, explique M. Cousot. Lorsqu'une valeur est codée sur 5

chiffres, la machine ne peut accepter des nombres de taille supérieure, et elle les tronque." D'où des erreurs fatales, comme celle qui a conduit à la perte du contrôle de la fusée Ariane 5 le 4 juin 1996.

Face à l'inflation galopante de la taille des logiciels embarqués sur les avions de ligne (20 000 lignes de code pour l'A320, 120 000 pour l'A340, près de 500 000 pour l'A380), la recherche de telles erreurs devient critique. "Nous sommes capables d'établir la preuve mathématique qu'un programme comme celui de la commande de vol de l'A380 ne comprend pas de bogues liés à la limite des capacités de l'ordinateur" , rassure M. Cousot. Une information précieuse pour la fiabilité de l'A380, même s'il est prévu d'autres sécurités comme l'exécution redondante des programmes par plusieurs ordinateurs en parallèle. L'équipe de M. Cousot a d'ores et déjà établi un record : "L'A380 dispose du plus gros programme jamais "prouvé" dans le monde."

Article paru dans l'édition du 27.04.05

Exemple de programme

Données :

•point U=(x,y)

•ensemble de points V0,V1,...,Vn-1 tels que Vi=(xi,yi), 0 ≤ i≤ n-1

Résultat : distance d du point Vi le plus éloigné de U

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

Données :

•point U=(x,y)

•ensemble de points V0,V1,...,Vn-1 tels que Vi=(xi,yi), 0 ≤ i≤ n-1

Résultat : distance d du point Vi le plus éloigné de U

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

Interprétation

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

i = d =d’ =

00

9.2195449.2195441

8,062257

2

Analyse de sûreté du programme

Opérations illicites 1÷0 √-1

Dépassements de capacité a × b = +∞

Erreurs d’arrondi 1/10 = 0.00011001100

Synchronisations hasards de course impossible dans ce cas

Autres : erreurs restantes non traitéi = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

Absence d’erreur?

Impossibilité de tester tous les scenarii possibles!

Si l’on ne considère que les points correspondant à un écran d’ordinateur :

coordonnées entières

abscisses entre 0 et 1023

ordonnées entre 0 et 767

13 points uniquement (figure)

(1024*768)13> 4.4 ⋅1076

possibilités!

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

Absence d’erreur?

(1024*768)13> 4.4 ⋅1076

possibilités!

Processeur à 3 GigaHertz

3⋅109 opérations/seconde

moins de 109 tests/seconde

4.4 ⋅1065 secondes

=

plus de 1058 années

Outil mathématique : ordres partiels

Ordre total : relation ≤ telle que pour tous x et y :

x ≤ y ou y ≤ x

Ordre partiel : relation ≤ telle que pour tous x et y :

x ≤ y ou y ≤ x ou ni l’un ni l’autre

Outil mathématique : majorants

Majorant d’une partie P : élément plus grand que tous les éléments de P

Outil mathématique : treillis complets

Treillis complet T :

ensemble avec ordre partiel

tout sous-ensemble de T admet un plus petit majorant

Exemple : le treillis des signes

Représentation simplifiée des entiers relatifs

a ≤ b si a est un sous-ensemble de b dans Z

T (top) correspond à Z

⊥ (bottom) correspond à l’ensemble vide ∅

Autre exemple : le treillis des intervalles

Opérations dans le treillis des signes

Addition Multiplication

Interprétation abstraite

Abstraction des valeurs de manière à pouvoir considérer un grand nombre de scenarii à la fois

Interprétation du programme avec les valeurs abstraites afin de valider simultanément tous les scenarii considérés

étude “macroscopique” du comportement du

programme

Exemple :

le treillis des signe

Abstraction - concrétisation

0

0

abstraction α

concrétisation γ

Interprétation abstraite de programme

(x,y) = ( , ) n=

xi =

yi =

i =

d =

tant que i ≤ n-

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+

(x,y) = ( , ) n=

xi =

yi =

i =

d =

tant que i ≤ n-

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+

i = d =d’ =

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

α

γ

i= ≤ n - =√(( - )2+( - )2)

√( 2+ 2)=

√( 2+ 2)

= =√( + ) √

=Pas d’opération illicite

∪ =

Valeurs stabilisées(point fixe)

Jamais d’opération illicite

Récapitulatif

Propriété démontrée :

Absence d’opération illicite (racines carrées) - propriété de sûreté

Pour un nombre quelconque de points

Pour des coordonnées quelconques (≠0)

Démonstration :

Entièrement mécanique (automatisable)

Obtenue par calcul d’un point fixe (stabilisation de toutes les données possibles en tout point du programme)

Outil mathématique : point fixe

Point fixe d’une fonction f : point x tel que f(x)=x

Outil mathématique : fonction croissante

Fonction croissante : si x ≤ y alors f(x) ≤ f(y)

Exemple : la fonction valeur absolue est croissante dans le treillis des signes

Théorème de Tarski (1955)

Théorème : soit T un treillis complet et

f : T → T

une fonction croissante. f admet un plus petit point fixe

Théorème de Tarski (1955)

Théorème : soit T un treillis complet et

f : T → T

une fonction croissante. f admet un plus petit point fixe

Théorème de Tarski (1955)

Théorème : soit T un treillis complet et

f : T → T

une fonction croissante. f admet un plus petit point fixe

Théorème de Tarski (1955)

Théorème : soit T un treillis complet et

f : T → T

une fonction croissante. f admet un plus petit point fixe

Théorème de Tarski (1955)

Théorème : soit T un treillis complet et

f : T → T

une fonction croissante. f admet un plus petit point fixe

Théorème de Tarski (1955)

Théorème de Tarski : existence d’un plus petit point fixe

Théorème de Kleene : indique comment le calculer

Analyse de sûreté du programme

Opérations illicites 1÷0 √-1 prouvé (signes)

Dépassements de capacité a × b = +∞

Erreurs d’arrondi 1/10 = 0.00011001100

Synchronisations hasards de course impossible dans ce cas

Autres : erreurs restantes non traitéi = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

Dépassements de capacité : treillis des intervalles

abstraction α

concrétisation γ

[ ]

[a, b] + [c, d] = [a+c, b+d][a, b] - [c, d] = [a-d, b-c]

[a, b]×[c,d] =[min(ac,ad,bc,bd), max(ac,ad,bc,bd)]

[a, b] + [c, d] = [a+c, b+d][a, b] - [c, d] = [a-d, b-c]

[a, b]×[c,d] =[min(ac,ad,bc,bd), max(ac,ad,bc,bd)]

Interprétation abstraite par intervalles

(x,y) = ([7,7],[4,4]) n=[12,12]

xi = [-4,15]

yi = [-7,11]

i = [0,0]

d = [0,0]

tant que i ≤ n-[1,1]

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+[1,1]

(x,y) = ([7,7],[4,4]) n=[12,12]

xi = [-4,15]

yi = [-7,11]

i = [0,0]

d = [0,0]

tant que i ≤ n-[1,1]

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+[1,1]

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

(x,y) = (7,4) n=12

xi = 9,15,-4,-3,2,11,...

yi = 11,5,2,9,-3,-7,...

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

α

γ

(xi-x)2 toujours dans [-11,8]2=[64,121](yi-y)2 toujours dans [-11,7]2=[49,121]

pas de dépassement sur 8 bits (entiers entre -127 et 127)Résultats :

Analyse de sûreté du programme

Opérations illicites 1÷0 √-1 prouvé (signes)

Dépassements de capacité a × b = +∞ prouvé (intervalles)

Erreurs d’arrondi 1/10 = 0.00011001100

Synchronisations hasards de course impossible dans ce cas

Autres : erreurs restantes non traitéi = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

i = 0

d = 0

tant que i ≤ n-1

d’ = √((xi-x)2+(yi-y)2)

si d’>d alors d = d’

i = i+1

Erreurs d’arrondi : risques

√((xi-x)2+(yi-y)2)

Racine carrée pas toujours présente/précise

matériellement (hors IEEE754)

Racine carrée pas toujours présente/précise

matériellement (hors IEEE754)

Elimination catastrophique : si a≈b, a et b légèrement erronés, a-b très imprécisElimination catastrophique : si a≈b, a et b légèrement erronés, a-b très imprécis

Absorption : si a>>b alors a+b=a

ex : 1.0+1.0e-8=1.0 en arithmétique IEEE754 simple

précision

Absorption : si a>>b alors a+b=a

ex : 1.0+1.0e-8=1.0 en arithmétique IEEE754 simple

précision

Il existe des méthodes de validation par interprétation abstraite

Autres treillis numériques

Conclusion

Sûreté des systèmes embarqués :

Partie importante du développement pouvant représenter jusqu’à 80% du coût

Partie intégrante du métier de concepteur, nombreux débouchés dans les grands groupes industriels

Ingénieur sûreté de fonctionnement junior H/FEntreprise: PSA Peugeot CitroënSalaire : Sans objetIngénieur sûreté de fonctionnement junior h/f logiciel, système, et organique/mécatronique La Direction... méthodes et les outils a tous les stades du cycle de vie du produit. Vous prenez en charge les études sûreté de fonctionnement... contraintes jusqu'au dossier de justification sûreté de fonctionnement. Vous analysez les réponses fournisseurs en vérifiant... méthodologique lié aux études et participez au club Sûreté de Fonctionnement. Expérience: Not SpecifiedConditions: Voir la description pour plus de détailContrat: CDI / CNE

02/07/2008

Conclusion

Licence info

Licence info

Programmation

en Ada (L1)

Programmation

en Ada (L1)

Logique (L1)Logique (L1)

Programmation en langage

C (L2)

Programmation en langage

C (L2)

Intelligence Artificielle (L2)Intelligence

Artificielle (L2)

Qualité numérique

(L3)

Qualité numérique

(L3)

Compilation (L3)

Compilation (L3)

Masters pro ou recherche, écoles d’ingénieurs, etc.