Academic literature on the topic 'Réseaux de Petri colorés de haut niveau'

Cette thèse s'inscrit dans le cadre de la vérification automatique de programmes concurrents basée sur un modèle formel intermédiaire: les réseaux de Petri colorés de haut-niveau. Nous nous attachons à combattre le phénomène d'explosion combinatoire lié à l'exploration explicite de l'ensemble des entrelacements possibles du système. Pour cela, nous nous proposons de tirer profit de la quantité de mémoire et de la puissance de calcul offerte par un réseau local de machines travaillant de manière coopérative. Par le biais d'une analyse structurelle, nous cherchons à répartir efficacement le graphe d'accessibilité du système. Nous nous attachons ensuite à conserver l'efficacité des techniques visant à limiter l'explosion combinatoire dans cet environnement réparti en relâchant notamment les contraintes de cohérence sur l'exploration du graphe. Nous avons alors validé ces approches à l'aide d'un vérifieur réparti et multithreadé dans lequel nous avons implémenté nos algorithmes.

La vérification formelle est une solution pour augmenter la fiabilité de l’implémentation du système. Dans notre travail de thèse, nous nous intéressons à l’utilisation de ces méthodes pour la vérification des systèmes d’exploitation multi-coeurs temps réel. Nous proposons une approche de model-checking utilisant les réseaux de Petri temporels, étendus avec des transitions colorées et des fonctionnalités de haut niveau. Nous utilisons ce formalisme pour modéliser le système d’exploitation multi-coeur Trampoline, conforme aux standards OSEK/VDX etAUTOSAR. Nous définissons dans un premier temps ce formalisme et montrons son adéquation avec la modélisation de systèmes concurrents temps reel. Nous utilisons ensuite ce formalisme pour modéliser le système d’exploitation multi-coeur Trampoline et vérifions par model-checking sa conformité avec le standard AUTOSAR. À partir de ce modèle, nous pouvons vérifier des propriétés aussi bien sur l’OS que sur l’application telles que l’ordonnançabilité d’un système tempsréel ainsi que les mécanismes de synchronisation : accès concurrents aux structures de données du système d’exploitation, ordonnancement multi-coeur et traitement des interruptions inter-coeur. À titre d’illustration, cette méthode a permis l’identification automatique de deux erreurs possibles de l’OS Trampoline dans l’exécution concurrente, montrant une protection insuffisante des données et une synchronisation défectueuse
Formal verification is a solution to increase the system’s implementation reliability. In our thesis work, we are interestedin using these methods to verify multi-core RTOS. We propose a model-checking approach using time Petri nets extended with colored transitions and high-level features. We use this formalism to model the Trampoline multi-core OS, compliant with the OSEK/VDX and AUTOSAR standards. We first define this formalism and show its suitability for modeling real-time concurrent systems. We then use this formalism to model the Trampoline multi-core RTOS and verify by model-checkingits conformity with the AUTOSAR standard. From this model, we can verify properties of both the OS and the application, such as the schedulability of a real-time system and the synchronization mechanisms: concurrent access to the data structures of the OS, multicore scheduling, and inter-core interrupt handling. As an illustration, this method allowed the automatic identification of two possible errors of the Trampoline OS in concurrent execution, showing insufficient data protection andfaulty synchronization

Cette thèse s'intéresse à la vérification de systèmes automatisables par model-checking. La question sous-jacente autour de laquelle se construit la contribution est la recherche d'un compromis entre différents objectifs potentiellement contradictoires : la décidabilité des systèmes à vérifier, l'expressivité des formalismes de modélisation, l'efficacité de la vérification, et la certification des outils utilisés. Dans ce but, on choisit de baser la modélisation sur des réseaux de Petri annotés par des langages de programmation réels. Cela implique la semi-décidabilité de la plupart des questions puisque la responsabilité de la terminaison est remise entre les mains du modélisateur (tout comme la terminaison des programmes est de la responsabilité du programmeur). Afin d'exploiter efficacement ces annotations, on choisit ensuite une approche de compilation de modèle qui permet de générer des programmes efficaces dans le langage des annotations, qui sont alors exécutées de la manière la plus efficace. De plus, la compilation est optimisée en tirant partie des spécificités de chaque modèle et nous utilisons l'approche de model-checking explicite qui autorise cette richesse d'annotations tout en facilitant le diagnostique et en restant compatible avec la simulation (les modèles compilés peuvent servir à de la simulation efficace). Enfin, pour combattre l'explosion combinatoire, nous utilisons des techniques de réductions de symétries qui permettent de réduire les temps d'exploration et l'espace mémoire nécessaire
This work focuses on verification of automated systems using model-checking techniques. We focus on a compromise between potentially contradictory goals: decidability of systems to be verified, expressivity of modeling formalisms, efficiency of verification, and certification of used tools. To do so, we use high level Petri nets annotated by real programming languages. This implies the semi-decidability of most of problems because termination is left to the modeler (like termination of programs is left to the programmer). To handle these models, we choose a compilation approach which produces programs in the model annotation language, this allows to execute them efficiently. Moreover, this compilation is optimizing using model peculiarities. However, this rich expressivity leads to the use of explicit model-checking which allows to have rich model annotations but also allows to easily recover errors from verification, and remains compatible with simulation (these compiled models can be used for efficient simulation). Finally, to tackle the state space explosion problem, we use reduction by symmetries techniques which allow to reduce exploration times and state spaces

Aujourd'hui, un des points cruciaux dans le développement des logiciels critiques est le passage de l'informel au formel. Le but de cette thèse est de définir ici une méthodologie de développement permettant un passage plus intuitif du cahier de charges (spécifications informelles) aux spécifications formelles d'un système, en tenant compte de son comportement dynamique. Cette méthodologie se base sur l'utilisation d'un modèle lisible et expressif. Notre choix s'est donc porté les réseaux de Pétri de haut niveau qui combinent trois qualités importantes : la représentation graphique, le comportement dynamique et l'abstraction des traitements. Elle peut se décomposer en plusieurs phases. D'abord nous tenterons une représentation graphique du cahier des charges par le réseau de Pétri proprement dit. Puis la phase d'interprétation du cahier des charges où nous annoterons le réseau de Pétri obtenu par du langage naturel. La troisième phase, dite de formalisation, transformera les annotations du réseau de Pétri en formules mathématiques (contraintes). Enfin nous terminerons par une phase de traduction automatique du réseau de Pétri en machine abstraite b et nous poursuivrons par une procédure b classique.

Nous évaluons dans cette thèse deux performances temporelles des architectures d automatisation distribuées sur Ethernet commuté et utilisant un modèle de coopération client/serveur : Le temps de réponse entre une occurrence d un événement d entrée et l occurrence de l événement de sortie correspondant ; Le temps de cycle réeseau pour la scrutation par un contrôleur de l ensemble de ses modules d entrées / sorties déportées. La conjonction de trois mécanismes de consommation de temps rend ces deux performances variables et difficiles à déterminer de manière analytique. Par conséquent, la méthode proposée se base sur la simulation d un modèle en réseau de Petri temporisé et coloré du comportement dynamique de l architecture complète. Les résultats obtenus sur six architectures test permettent de : Montrer que les architectures multi-contrôleurs utilisant le modèle de coopération client / serveur donnent des temps de cycle réseau plus rapide que celles basées sur les modèles maître / esclave et producteur / consommateur ; Quantifier l influence du réseau et des mécanismes de consommation du temps.

L’étude des systèmes en réseau supports d’applications collaboratives, distribuées et interconnectées par un réseau repose sur l’identification des exigences de fonctionnement de l’application appelées Qualité de Contrôle (QdC), et sur l’évaluation des performances du réseau pour obtenir son niveau de Qualité de Service (QdS). « Cette thématique comporte d’importants verrous de nature fondamentale relevant du domaine de l'automatique, de la robotique, des capteurs, de la théorie de l’information, des réseaux. Par souci de simplification, les travaux sur les systèmes en réseau se repartissent selon deux approches: la première compense les perturbations générées par les communications au niveau de l’application (« control over network »). La seconde adapte les performances du réseau en fonction des besoins applicatifs (« control of network »). L’objectif de nos travaux de thèse est donc de proposer un environnement de modélisation intégré permettant de représenter le comportement des SCRs. Nous avons choisi les Réseaux de Petri de haut niveau qui possède un fort pouvoir d’expression, de formalisation et dont la modularité permet d’ajouter et/ou de faire évoluer les modèles qui sont développés dans ce travail. Dans un premier temps, nous avons proposé unmodèle Ethernet Commuté gérant des mécanismes d’ordonnancement. Le choix de ce réseau a été guidé par le fait qu’il est de plus en plus utilisé dans les SCRs. Ensuite, le modèle d’un SCR a été proposé, et modélisé par des Réseaux de Petri de haut de niveau, en intégrant au modèle Ethernet Commuté, l’environnement applicatif : Contrôleur, Process,.. Enfin, des stratégies pour commander le réseau de façon à adapter sa Qualité de Service en regard de la Qualité de Contrôle requise par l’application, ont été mises en oeuvre. Pour cela, des ordonnanceurs à priorité stricte et de type WRR sont utilisés. Les résultats de simulation montrent clairement que des dispositifs de compensation du réseau pour améliorer les performances du système de communication, permettent aussi d’améliorer les performances du système à commander
The Networked Control Systems (NCS) used in collaborative, and distributed applications are based both on identification of application requirements named Quality of Control (QoC), and on performance evaluation of network to obtain the required Quality of Service (QoS). The pluridisciplinary aspect of NCS needs the knowledge of many domains such as information theory, robotics, sensors and networks. In general, two approaches are investigated in NCS: the first one deals with the compensation of the network perturbations by using control theory (control over network). The second one adapts the network performances according to the application needs (control of network). The objective of this thesis is to propose an integrated modelling environment to represent globally the NCS behaviour by using the High Level Petri Nets (HLPN) formalism. This work considers NCS based on switched Ethernet architectures. Such communication architecture is modelled with HLPN and is evaluated according to different scheduling mechanisms and traffic load. After that, NCS model based on HLPN is proposed. This model integrates the Ethernet switch model and applicative environment of NCS: controller, process… Finally, the strategies to control the network in order to adapt the QoS according to the QoC required by the application are proposed. These strategies are achieved using priority static and Weighted Round Robin policies. The obtained results show that the scheduling mechanisms enable to improve the performance of communication system and then to improve the application performances

Cette thèse s'inscrit dans le cadre de la vérification automatique de programmes concurrents basée sur un modèle formel intermédiaire, les réseaux de Petri colorés. Nous nous attachons particulièrement à définir, ou adapter, des méthodes qui visent à lutter contre le phénomène d'explosion combinatoire induit par les algorithmes d'exploration du graphe d'accessibilité. Nous oeuvrons pour cela à deux niveaux : au niveau structurel, par des techniques d'abstraction du modèle, et au niveau sémantique, par des techniques de réduction du graphe d'accessibilité du système. Afin de valider l'intérêt pratique des techniques proposées nous les avons implantées dans deux outils : Helena un model checker pour les réseaux de Petri de haut niveau et Quasar une plate-forme pour la validation de programmes Ada concurrents
This thesis enters in the frame of the automatic verification of concurrent software based on an intermediary formal language, colored Petri nets. We particularly endeavor to define, or adapt, methods which aim at tackling the state explosion induced by an exhaustive exploration of the state space. We work at two levels : at a structural level, by defining some automatic automatic abstraction rules of the model, and at a semantic level, by reducing the reachabiblity graph of the system. In order to validate the practical interest of the proposed techniques we implemented them in two tools: Helena a model checker for high level Petri nets and Quasar, a platform for the verification of concurrent Ada software

L'étude des systèmes en réseau supports d'applications collaboratives, distribuées et interconnectées par un réseau repose sur l'identification des exigences de fonctionnement de l'application appelées Qualité de Contrôle (QdC), et sur l'évaluation des performances du réseau pour obtenir son niveau de Qualité de Service (QdS). « Cette thématique comporte d'importants verrous de nature fondamentale relevant du domaine de l'automatique, de la robotique, des capteurs, de la théorie de l'information, des réseaux. Par souci de simplification, les travaux sur les systèmes en réseau se repartissent selon deux approches: la première compense les perturbations générées par les communications au niveau de l'application (« control over network »). La seconde adapte les performances du réseau en fonction des besoins applicatifs (« control of network »). L'objectif de nos travaux de thèse est donc de proposer un environnement de modélisation intégré permettant de représenter le comportement des SCRs. Nous avons choisi les Réseaux de Petri de haut niveau qui possède un fort pouvoir d'expression, de formalisation et dont la modularité permet d'ajouter et/ou de faire évoluer les modèles qui sont développés dans ce travail. Dans un premier temps, nous avons proposé un modèle Ethernet Commuté gérant des mécanismes d'ordonnancement. Le choix de ce réseau a été guidé par le fait qu'il est de plus en plus utilisé dans les SCRs. Ensuite, le modèle d'un SCR a été proposé, et modélisé par des Réseaux de Petri de haut de niveau, en intégrant au modèle Ethernet Commuté, l'environnement applicatif : Contrôleur, Process,.. Enfin, des stratégies pour commander le réseau de façon à adapter sa Qualité de Service en regard de la Qualité de Contrôle requise par l'application, ont été mises en oeuvre. Pour cela, des ordonnanceurs à priorité stricte et de type WRR sont utilisés. Les résultats de simulation montrent clairement que des dispositifs de compensation du réseau pour améliorer les performances du système de communication, permettent aussi d'améliorer les performances du système à commander.

La qualité de l’information concernant les origines et les destinations (OD) des véhicules dans un carrefour influence la performance de nombreux systèmes des transports routiers. La période de sa mise à jour conditionne l’échelle temporelle de fonctionnement de ces systèmes. Nous nous intéressons au problème de reconstitution à chaque cycle de feux des OD des véhicules traversant un carrefour à partir des états des feux et des mesures de trafic provenant des capteurs vidéo. Les mesures de trafic, fournies à la seconde, sont les débits aux entrées/sorties du carrefour et les nombres de véhicules en arrêt dans les zones internes du carrefour. Ces données réelles sont entachées d’imperfections. La seule méthode existante qui est capable de résoudre ce problème, nommée ORIDI, ne tient pas compte de l’imperfection des données. Nous proposons une nouvelle méthode modélisant l’imprécision de données par la théorie des sous-ensembles flous. Elle est applicable à tout type de carrefour et indépendante du type de stratégie de feux. Elle consiste à estimer les flux OD à partir de la loi de conservation des véhicules représentée par un système d’équation sous déterminé construit de façon dynamique à chaque cycle de feux grâce aux réseaux de Petri a-temporisés flous. Une solution unique est trouvée grâce à huit différentes méthodes qui représentent l’estimation sous forme d’un point, d’un intervalle ou d’un sous-ensemble flou. Notre étude montre que les méthodes nettes sont aussi précises qu’ORIDI, mais plus robustes face à une panne d’un des capteurs vidéo. Les méthodes ensemblistes et floues, étant moins précises qu’ORIDI, cherchent à garantir que la solution inclut la vraie valeur
The quality of the information about origins and destinations (OD) of vehicles in a junction influences the performance of many road transport systems. The period of its update determines the temporal scale of working of these systems. We are interested in the problem of reconstituting of the OD of vehicles crossing a junction, at each traffic light cycle, using the traffic light states and traffic measurements from video sensors. Traffic measurements, provided every second, are the vehicle counts made on each entrance and exit of the junction and the number of vehicles stopped at each inner section of the junction. Thses real date are subject to imperfections. The only existent method, named ORIDI, which is capable of resolving this problem doesn’t take into account the data imperfection. We propose a new method modelling the date imprecision by the theory of fuzzy subsets. It can be applied to any type of junction and is independent of the type of traffic light strategy. The method estimates OD flows from the vehicle conservation law represented by an underdetermined system of equations constructed in a dynamic way at each traffic light cycle using to the fuzzy a-timed Petri nets. A unique solution is found thanks to eight different methods which introduce estimate in the form of point, interval or fuzzy set. Our study shows that the crisp methods are accurate like ORIDI, but more robust when one of the video sensors is broken down. The interval and fuzzy methods, being less accurate than ORIDI, try to guarantee that the solution includes the true value