Algorithme hybride pour la génération de scénarios redoutés

Fiabilité dynamique

Un système embarqué combine généralement plusieurs technologies : hydraulique, mécanique, électrique, et électronique. Il présente également des aspects continus et événementiels qui lui donnent un caractère hybride. La dynamique continue représente la partie énergétique du système et la partie événementielle représente les changements d’état discrets, les reconfigurations et les défaillances.
L’analyse de la sûreté de fonctionnement de ces systèmes dynamiques hybrides est souvent appelée fiabilité dynamique [Labeau, 2002]. Le paragraphe suivant donne une définition de cette notion de fiabilité dynamique.
Dans un système dynamique hybride, l’évolution dynamique de l’ensemble des variables physiques associées au processus (température, débit, pression,…) est contrôlé à l’aide d’un dispositif de contrôle-commande en surveillant, le plus souvent, le dépassement de certains seuils caractéristiques. Ainsi des variations de certaines grandeurs physiques provoquent des changements d’état du dispositif de contrôle qui agit en conséquence sur ces grandeurs pour les maintenir dans un intervalle de sécurité. Inversement, l’apparition d’une défaillance sur ce système provoque une variation (généralement non souhaitée) dans les variables continues du système. Cette défaillance se répercute donc directement sur l’évolution dynamique du processus physique.
Dans de tels systèmes, le comportement du système résulte donc de l’interaction entre la composante dynamique et déterministe de l’évolution des grandeurs physiques, la composante discrète et la composante stochastique associée au processus de défaillance.
L’évaluation des paramètres de la sûreté de fonctionnement nécessite deprendre en compte ce couplage entre processus déterministe (continu et/ou discret) et processus stochastique. C’est le domaine connu sous le nom de fiabilité dynamique. [Labeau, 2002] en donne une définition : « c’est lapartie des analyses probabilistes de sûreté qui étudie de manière intégrée le comportement des systèmes affectés par une évolution dynamique sous-jacente».
Initialement, la fiabilité dynamique a été qualifiée de dynamique probabiliste [Labeau, 2002]. La formulation proposée est intéressante dans le contexte de nos travaux. Le comportement dynamique d’un système peut être vu comme une succession de sections d’évolutions déterministes connectées entre elles par des événements aléatoires régis par des lois probabilistes. Un tel comportement est décrit par un processus stochastique déterministe par partie.

Problématique de sûreté de fonctionnement et fiabilité dynamique

Un des problèmes principaux rencontré lors d’une étude de sûreté de fonctionnement des systèmes embarqués (systèmes dynamiques hybrides par définition) est la prise en compte de manière efficace et réaliste des dépendances ; plus exactement, des interactions dynamiques existant entre les paramètres physiques (pression, température, débit, niveau,…) particulier au processus industriel développé et le comportement nomina1 ou dysfonctionnel des composantsdu système, qui constituent le milieu matériel du processus.
Dans de tels systèmes, la séquence de fonctionnement normal ou dangereux résulte d’une occurrence commune de deux types d’événements. Les premiers sont liés à l’évolution déterministe des paramètres physiques susmentionnés, alors que les deuxièmes sont dus aux sollicitations et aux défaillances des composants du système et sont donc de nature aléatoire.
Le problème que nous venons d’évoquer limite donc la validité des méthodes principales citées dans la première partie de ce chapitre. Les méthodes combinatoires (arbres de défaillance, arbres d’événements, diagrammes de fiabilité) permettent uniquement d’identifier et d’évaluer les combinaisons des événements menant à l’occurrence d’un autre événement, indésirable ou pas.
De telles combinaisons, ne tiennent pas compte de l’ordre de l’occurrence des événements qui les composent. Elles éliminent toute notion de dépendance entre ces événements. En outre, ces méthodes combinatoires présupposent une occurrence simultanée de tous les événements. Ceci exclut toute possibilité de prendre en compte la dépendance et les délais entre événements.
Le deuxième ensemble de méthodes comprend les approches markoviennes [Kaaniche, 1999].
Ces méthodes sont totalement ou partiellement exemptes du problème précédent mais sont limitées par d’autres contraintes. En effet, il est difficile de modéliser correctement des délais déterministes et des processus se déroulant en parallèle.

Méthodes et outils pourla fiabilité dynamique

Nous présentons brièvement les différents travaux relatifs à la modélisation en vue de l’analyse de sûreté de fonctionnement et les méthodes relatives à la fiabilité dynamique des systèmes complexes. Une présentation détaillée de tous ces travaux peut être consultée dans [Khalfaoui, 2003] et [Mejoudj, 2006].

Langage AADL

AADL, Architecture Analysis and Design Language, est un langage de description d’architecture système destiné aux systèmes embarqués (contextes : automobile, aéronautique et spatial notamment). Sa standardisation est en cours sous l’autorité de la «International Society of Automotive Engineers» (SAE). Une première version stable, AADL 1.0, a été publiée en novembre 2004.
Le principe est de décrire l’architecture pour mieux maîtriser sa complexité, et pouvoir vérifier quelques propriétés de ce système comme l’ordonnançabilité, la bonne transmission des messages ou le bon dimensionnement du matériel.
AADL décrit plusieurs composants qui modélisent une partie du système. Certains composants sont matériels (bus, processor, memory …), d’autres logiciels (process, thread, subprogram, …).
Chaque composant peut avoir des propriétés, et peut contenir des sous-composants (un processus – process – pouvant par exemple contenir plusieurs fils d’exécution – threads). On peut également décrire plusieurs machines et les relier entre elles pour simuler des connexions réseaux.
Des travaux se basant sur AADL dans le domaine de la sûreté de fonctionnement ont été menés par [Rugina & al, 2006] et ont pour objectif deproposer une méthode structurée pour guider l’élaboration du modèle AADL (Architecture Analysis and Design Language) [SAE-AS5506] de sûreté de fonctionnement et proposer des règles de transformation de modèle pour générer des RdPSG (Réseau de Petri Stochastique Généralisé) à partir de modèles AADL de sûreté de fonctionnement. L’ensemble des règles de transformation de modèle est conçu pour être mis en œuvre dans un outil de transformation de modèle, de façon transparente à l’utilisateur.
L’approche vise à assister l’utilisateur dans la construction structurée du modèle AADL de sûreté de fonctionnement (le modèle d’architecture + les informations liées à la sûreté de fonctionnement). Le modèle AADL de sûreté de fonctionnement est transformé en un RdPSG qui peut être traité par des outils existants ([Ciardo & al, 1993], [Benardi & al, 2001], [Ciardo & al, 1993] et [Hirel & al, 2000]). Pour faciliter l’évolution du modèle, le modèle AADL de sûreté de fonctionnement est construit de manière itérative. Les comportements des composants architecturaux sont d’abord modélisés en présence de leurs propres fautes et événements de réparation. Ensuite, les dépendances entre composants sont modélisées dans les itérations suivantes.
La transformation du modèle AADL en RdPSG est conçue pour être transparente à l’utilisateur.
Par conséquent, elle est basée sur des règles systématiques et rigoureuses, destinées à une mise en œuvre automatique par des outils. La transformation de modèle peut être effectuée de manière itérative à chaque fois que le modèle AADL de sûreté de fonctionnement est enrichi. Ainsi, la sémantique du RdPSG peut être validée progressivement. Par conséquent, le modèle AADL correspondant peut être aussi validé progressivement et corrigé si nécessaire.
L’intérêt que suscite le langage AADL ces dernières années a motivé les auteurs des ces travaux pour exploiter le langage AADL, qui fournit une notation textuelle et graphique standardisée pour décrire des architectures matérielles et logicielles, comme langage de départ. Ceci dit la question qui se pose est l’efficacité du modèleRdPSG pour l’analyse de sûreté des systèmes complexes et l’éternel problèmede l’explosion combinatoire.

Arbre de défaillance haut niveau

L’approche par arbres de défaillance (AdD) présentée précédemment a l’avantage d’être facilement compréhensible par des personnes autres que le créateur même de l’arbre.
Néanmoins, l’arbre classique possède un certain nombre de limites trop fortes dans le cadre de la fiabilité dynamique qui nous intéresse. Les arbres de défaillance, qui sont la représentation d’une formule booléenne sous forme de graphe ne tiennent donc pas compte de l’ordre d’apparition des événements et des dépendances fonctionnelles, caractéristiques pourtant très importantes dans les systèmes physiques. Afin de combler ces lacunes, de nouvelles approches intégrant l’aspect dynamique des systèmes ont été étudiées. Celle proposée par Dugan [Manian & al, 1998] de l’Université de Virginie (Etats-Unis) est basée sur la décomposition de l’arbre initial en une partie statique et une partie dynamique. La partie statique de l’arbre est alors traitée de manière classique à l’aide des diagrammes de décision binaire (BDD) [Bryant, 1986], la partie dynamique étant, quant à elle, traitée à l’aide d’une autre méthode appelée méthode de Markov [Howard, 1960]. L’inconvénient de cette approche est que toute possibilité d’analyse qualitative est perdue puisque la notion de coupe dynamique est absente. D’autres outils, appelés « générateurs de séquences » permettent de trouver des coupes munies d’un ordre total. Là encore un problème surgit ; certaines séquences d’événements ne mènent pas à l’événement redouté de manière permanente. En effet, certaines configurations d’un système peuvent autoriser l’occurrence de cet événement de manière temporaire, sans causer pour autant la perte définitive du système.
Cepin et Mavko [Cepin & Mavko, 2002] ont proposé une approche d’arbre dynamique basée sur le principe de la « composition » de sous arbres (figure I.4) correspondant à chacune des configurations du système. L’évolution de manière discrète dans le temps des événements est encodée dans une matrice. Cette matrice permet, lors du traitement de l’arbre, d’activer ou de désactiver certaines branches de l’arbre et donc de se placer dans une configuration précise à un instant t donné.

Motifs formels d’architectures de systèmes pour la SDF

L’objectif des travaux de thèse de [Kehren, 2005],initiés par AIRBUS France, est de proposer des méthodes et outils d’aide à la modélisation et à l’évaluation de l’architecture de sûreté de fonctionnement des systèmes embarqués complexes. L’approche est basée sur des modèles généraux d’architectures de systèmes (safety patterns) correspondant à des éléments de sûreté (redondances, duplication …). « Un pattern est une solution récurrente qui décrit et résout un problème général dans un contexte particulier ».
L’idée de départ à la base de l’approche compositionnelle, est d’utiliser ou de réutiliser des composants génériques, abstractions d’architectures de sûreté, dont les propriétés ont été préalablement vérifiées. La réutilisation des assemblages, rendus génériques et que l’on appelle motifs d’architecture de sûreté, permet de simplifier les différentes tâches de conception (ou prototypage) et d’analyse d’architectures de systèmes complexes.
Le but est, entre autres, d’appliquer l’approche design patterns du génie logiciel au domaine de la sûreté de fonctionnement en exploitant les solutions proposées par les design patternsdes problèmes récurrents. Ils renseignent sur les conséquences et le contexte d’utilisation et proposent des noms génériques aux patterns permettant de définir un vocabulaire précis.
Les safety patterns renferment un ensemble d’hypothèses (sur leur environnement, leurs entrées, les modes de défaillances, …), une spécification correspondant à l’architecture de l’élément de sûreté que représente le pattern et enfin des exigences garanties qui vont dépendre à la fois des hypothèses et de l’architecture. Un ensemble d’attributs est défini dans lebut de distinguer les différents patterns par un nom générique et une structure propre leur conférant certaines propriétés sous certaines hypothèses. Ces attributs permettent de capitaliser le savoir d’experts des différents domaines d’utilisation ainsi qu’une meilleure utilisation/choix des patterns lors de la phase amont de conception d’architectures. Pour faciliter cette conception, un catalogue de patterns d’architectures de sûreté a été réalisé.
Le langage AltaRica a été utilisé pour formaliser des systèmes en présence de pannes. Les patterns correspondent à des abstractions d’architectures concrètes et donc requièrent une modélisation plus déclarative, i.e. à l’aide de propriétés. Ces propriétés étant en général dynamiques, le choix s’est porté sur la Logique Temporelle Linéaire (LTL), pour les modéliser.
La description des patterns est donc constituée d’une partie AltaRica et d’une partie LTL.
Pour caractériser le comportement d’un système défini de manière mixte (opérationnel/dénotationnel). Lasémantique d’AltaRica est plongée dans les Structures de Kripke Etiquetée (SKE). En effet, les SKE définissent la sémantique de State-Event LTL. De plus, afin obtenir des structures manipulables informatiquement, les propriétés de SE-LTL ont été traduites en automates de Büchi. Le produit de ces deux structures permet d’obtenir un automate de Büchi [Vardi & Wolper, 1986], [Vardi, 1996] caractérisant le comportement satisfaisant les contraintes fixées à la fois par la partie AltaRica et par la partie SE-LTL. La syntaxe AltaRica a été étendue pour permettre despécifier et contraindre le comportement des composants par des propriétés temporelles à la fois sur les états et sur les événements.

Graphe de Markov agrégé pourla fiabilité dynamique

Dans le cadre des travaux effectués au laboratoire CRAN en collaboration avec GFI Consulting, [Schoenig, 2004] s’est intéressé à la fiabilité dynamique des systèmes hybrides. Les travaux avaient pour objectif de définir une méthodologie de conception des systèmes de contrôlecommande tout au long des différents cycles de vie. Une approche basée sur la construction d’un graphe de Markov agrégé a été proposée. L’originalité de son approche tient dans sa capacité de répondre à un problème de représentation et d’évaluation de la fiabilité des systèmes dynamiques hybrides. Les principales étapes consistent à découpler la dynamique du système et la dynamique du processus de défaillance grâce à la théorie des perturbations singulières, puis d’identifier et estimer les grandeurs du système influençant la dynamique des défaillances.
Le principe général de l’approche consiste à coupler les deux méthodes d’analyse classiques : la simulation et les graphes de Markov, afin de contourner les limites intrinsèques à ces méthodes (temps de simulation, explosion combinatoire). L’approche proposée consiste à réaliser une agrégation des états élémentaires d’un graphe de Markov. L’influence du système sur le processus de défaillance est intégrée dans le modèle par le biais de termes de pondération des taux de défaillance. Ceux-ci permettent de prendre explicitement en compte la dynamique interne du système. Ces coefficients sont évalués par une simple simulation, permettant ainsi de traiter des systèmes complexes. Ce type d’approche, qualifié de « dynamique », permet de traiter des systèmes fortement dépendant du temps (par exemple, en cas d’existence de reconfigurations matérielles ou logicielles).

Simulation de Monte Carlo

La simulation de Monte Carlo [Batut, 1986], [Desieno & Stine, 1964], [Dubi, 2000] est une technique utilisée pour estimer la probabilité de résultats en répétant un grand nombre de fois une expérience à l’aide de la simulation et en utilisant des nombres aléatoires. La simulation est une méthode qui a pour but d’imiter un système réel. La simulation de Monte Carlo est utilisée lorsque d’autres analyses sont mathématiquement trop complexes ou trop difficiles à reproduire.
Un des avantages de la simulation de Monte Carlo est sa faible sensibilité à la complexité et à la taille des systèmes. Cependant, dans le cadre de la sûreté de fonctionnement, le modèle simulé est régi par des événements très rares (les défaillances) et des événements très fréquents (fonctionnement normal du système), et ce, simultanément. La simulation est alors cadencée par de nombreuses occurrences d’événements fréquents qui ne reflètent pas le comportement du système en présence de défaillances. C’est le problème de simulation des événements rares. Un nombre important d’histoires est nécessaire pour voir apparaître un événement redouté, ce qui implique des temps de calcul importants. De nombreuses techniques d’accélération de la simulation permettent de réduire ces temps [Garnier, 1998]. Elles sont basées soit sur une diminution de la complexité du modèle, soit sur la réduction du nombre de scénarios à simuler, en favorisant l’apparition des événements rares. Toutefois, ces méthodes ne sont pas toujours faciles à mettre en œuvre, car selles impliquent des hypothèses assez fortes, et/ou ne fournissent pas forcément des estimateurs de qualité.

Table des matières

Introduction générale
Chapitre 1 : sûreté de fonctionnement des systèmes embarqués
I Introduction
II Sûreté de fonctionnement, concepts et méthodes
II.1 Concepts de la sûreté de fonctionnement
II.2 Quelques définitions
II.3 Méthodes d’analyse de la sûreté de fonctionnement
II.3.1 L’analyse fonctionnelle
II.3.2 L’Analyse Préliminaire des Risques
II.3.3 Analyse des Modes de Défaillance, de leurs Effets et de leurs Criticités
II.3.4 Les Arbres de Défaillances
II.3.5 Diagramme de Fiabilité
III Sûreté de fonctionnementdes systèmes embarqués
III.1 Système embarqué
III.2 Fiabilité dynamique
III.3 Problématique de sûreté de fonctionnement et fiabilité dynamique
IV Méthodes et outils pour la fiabilité dynamique
IV.1 Modélisation des systèmes pour des études de SDF
IV.1.1 Langage de modélisation AltaRica
IV.1.2 Langage AADL
IV.2 Arbre de défaillance haut niveau
IV.3 Méthode des graphes de flux dynamiques
IV.4 Boolean logic Driven Markov Process (BDMP)
IV.5 Motifs formels d’architectures de systèmes pour la SDF
IV.6 Graphe de Markov agrégé pour la fiabilité dynamique
IV.7 Simulation de Monte Carlo
IV.8 Recherche de scénarios redoutés
V Conclusion
Chapitre 2 : Sûreté de fonctionnement et processus d’ingénierie système
I Introduction
II La norme EIA-632
II.1 Structure d’un système selon l’EIA-632
II.2 Processus de l’EIA-632
III Prise en compte de la sûreté de fonctionnement
III.1 Problématique
III.2 Approche d’intégration
IV Traduction des exigences de l’EIA-632 en exigences de SDF
IV.1 Les processus de conception
IV.1.1 Le processus de définition des exigences
IV.1.2 Le processus de définition de la solution logique
IV.2 Les processus d’évaluation technique
IV.2.1 Le processus d’analyse du système
IV.2.2 Le processus de validation des exigences
IV.2.3 Processus de vérification du système
V Mise en œuvre de l’approche
V.1 Les exigences de sécurité
V.2 La modélisation des exigences et la solution logique
V.3 L’analyse de risque
V.4 La validation
VI Conclusion
Chapitre 3 : Approche de modélisation
I Introduction
II Les réseaux de Petri
II.1 Rappel sur les réseaux de Petri
II.2 RdP t-temporels
II.3 Réseaux de Petri de haut niveau
II.4 Réseaux de Petri Prédicats Transitions Différentiels
III Les réseaux de Petri et le paradigme Orienté Objets
III.1 Approches d’intégration des réseaux de Petri et du paradigme OO
III.1.1 Objets dans les réseaux de Petri
III.1.2 Réseaux de Petri dans les objets
III.1.3 Approches mixtes
III.2 Les réseaux de Petri Prédicats Transitions Différentiels Orientés Objets
III.2.1 Modélisation des classes et des objets
III.2.2 Communication entre objets
III.2.3 Communication avec l’environnement externe
III.3 RdP Prédicats Transitions Différentiels Stochastique OO
IV Construction d’un modèle pour la fiabilité dynamique
IV.1 Langage UML
IV.2 Principe de l’approche
IV.2.1 Etape 1 : construction du modèle fonctionnel
IV.2.2 Etape 2 : modèle dysfonctionnel et états redoutés
V Conclusion
Chapitre 4 : Définition et propriétés des scénarios avec la logique linéaire
I Introduction
II Réseau de Petri et logique linéaire
II.1 Règle de transformation
II.2 Preuve d’un séquent
II.3 Equivalence entre RdP et logique linéaire
II.4 Preuve de séquent et arbre de preuve annoté
III Notion de scénario
III.1 Evénements et ensembles d’événements
III.2 Scénario
III.2.1 Cas des réseaux de Petri ordinaires
III.2.2 Cas des réseaux de Petri temporels
IV Conditions suffisantes
IV.1 Ensemble suffisant
IV.2 Remarque sur l’équation caractéristique
IV.3 Scénario suffisant
IV.3.1 Cas des réseaux de Petri ordinaires
IV.3.2 Cas des réseaux de Petri temporels
IV.3.3 Ensemble nécessaire
V Minimalité
V.1 Minimalité dans le cas des marquages initiaux et finaux fixés
V.1.1 Ensemble minimal
V.1.2 Scénario minimal
V.1.2.1. Cas des réseaux de Petri ordinaires
V.1.2.2. Cas des réseaux de Petri temporels
V.2 Marquages initiaux et marquages finaux partiellement connus
V.2.1 Marquages initial et final minimaux
V.2.2 Coupe minimale associée à l’état redouté
V.2.3 Scénario minimal associé à une coupe minimale
V.2.4 Algorithme de filtrage des scénarios minimaux
VI Complétude
VII Conclusion
Chapitre 5 : Approche orientée objets pour la génération de scénarios redoutés
I Introduction
II Méthode de recherche des scénarios redoutés
II.1 Principe de la méthode
II.2 Etapes de la méthode
II.2.1 Détermination des états normaux
II.2.2 Détermination des états cibles
II.2.3 Raisonnement en arrière
II.2.4 Raisonnement avant
II.3 Raisonnement dans un contexte inconnu
II.3.1 Différents conflits de transitions
II.3.2 Différents enrichissements de marquage
II.3.3 Mécanisme de contrôle de la cohérence
III Nouvelle version de l’algorithme de recherche de scénarios
III.1 Structures de données
III.1.1 Données d’entrée
III.1.2 Données internes
III.1.3 Données de sortie
III.2 Les procédures utilisées
III.2.1 Tirer Transition
III.2.2 Enrichir Marquage
III.2.3 Mémoriser contexte
III.2.4 Cohérence Marquage
III.3 Algorithme
IV Complétude (état initial minimal et état final minimal)
V Exemple d’application
V.1 Description générale
V.2 Fonctionnement du système
V.3 Composition du système
V.4 Exigences de sécurité
V.5 Analyse de risque
V.6 Modélisation du système et solution logique
V.6.1 Diagramme de cas d’utilisation
V.6.2 Diagramme de collaboration
V.6.3 Classe du système
V.6.4 Classe trappe
V.6.5 Classe électrovanne
V.6.6 Classe électrovanne de secours
V.7 Application de la méthode
V.7.1 Détermination des états normaux
V.7.2 Détermination des états cibles
V.7.3 Raisonnement arrière
V.7.4 Raisonnement avant
VI Conclusion
Chapitre 6 : Algorithme hybride pour la génération de scénarios redoutés
I Introduction
II Approximation de la partie continue
II.1 Linéarisation d’automates hybrides
II.2 La méthode d’abstraction de Hélias
II.3 Abstraction des dynamiques continues par réseau de Petri temporel flou
III Approche Hybride de génération de scénarios redoutés
III.1 Première étape (simulation de Monte Carlo)
III.2 Deuxième étape (algorithme hybride de recherche de scénarios redoutés)
III.3 Exemple d’application
III.3.1 Présentation
III.3.2 Modèle du système
III.3.3 Hypothèses de dysfonctionnement
III.3.4 Simulation et recherche de scénarios
IV Conclusion
Conclusion générale
Bibliographie
Annexe