To see the other types of publications on this topic, follow the link: Conception et vérification systèmes.
Dissertations / Theses on the topic 'Conception et vérification systèmes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Conception et vérification systèmes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Boukhebouze, Mohamed. "Gestion de changement et vérification formelle de processus métier : une approche orientée règle." Lyon, INSA, 2010. http://theses.insa-lyon.fr/publication/2010ISAL0016/these.pdf.
Full textAbstract:
Le travail proposé dans cette thèse traite de la flexibilité de la modélisation et la vérification des processus métier. L’objectif étant, de permettre, d’une part, une modélisation souple qui prend en compte la nature dynamique des éléments d’un processus métier ; et d’autre part, la vérification du déroulement du processus pour s’assurer de son bon fonctionnement. Pour atteindre cet objectif, nous avons entrepris, dans le cadre de cette thèse, des recherches qui visent la construction d’un modèle de processus basé sur un nouveau pattern de règles appelé ECAPE-M. Ce modèle permet de décrire un processus métier d’une manière déclarative, en utilisant un ensemble de règles ECAPE. Le formalisme ECAPE est considéré dans nos travaux comme une extension du formalisme ECA, initialement défini par Evénement – Condition – Action, avec une post condition pour contrôler l’exécution de l’action d’une règle et lancer une action de compensation dans le cas ou l’exécution n’est pas valide et avec un post événement pour décrire explicitement les événements qui seront générés par l’exécution de l’action de la règle pour construire un graphe d’exécution du processus. Le modèle ECAPE-M permet non seulement l’expressivité de la nature dynamique des différents éléments d’un processus métier mais aussi la vérification du bon fonctionnement d’un processus. Nous proposons de considérer le modèle ECAPE-M selon trois plans d’abstraction : Le plan métier où les processus sont définis par un ensemble de règles ECAPE. Nous proposons ici un nouveau langage, appelé ECAPE-L, qui utilise une syntaxe basée sur XML, pour décrire les éléments des processus métier. Ce nouveau langage déclaratif est proche des langages d’exécution impératifs de processus tels que BPEL et XPDL car il peut être exécuté par un moteur de règles qui interprète les différentes instructions. Le plan comportemental où une démarche de gestion du changement d’une règle dans le modèle ECAPE-M est mise au point. Cette démarche consiste à définir les relations entre les différentes règles, et traduire l’ensemble des règles et relations en un graphe orienté appelé graphe d’impact. L’analyse de ce graphe permet de déterminer l’ensemble des règles impactées par un changement et d’estimer le coût de changement d’une règle en terme de nombre d’opérations de changement. Le plan opérationnel où le modèle d’un processus ECAPE-M est traduit en un réseau de Pétri coloré appelé ECAPE-net afin de modéliser la sémantique d’exécution du processus. Notre contribution est validée par l’élaboration de l’architecture d’une plateforme de modélisation et d’analyse de processus métier appelé BP-FAMA (Business Process Framework for Agility of Modeling and Analysis)Efficient organizations need to ensure that their business processes are flexible so that these processes can easily accommodate changes in regulations and policies. Appropriate techniques to model and verify these processes are required. In this manuscript, we present a rule-based model, called ECAPE-M, that aims at improving the management of business processes in terms of flexibility and verification. This model extends the Event-Condition-Action (ECA) model and suggests formal tools for verification purposes. In this approach, the logic of a process is defined with a set of business rules that correspond to the policies in the organization. Each business rule is represented using the Event-Condition-Action-Post-condition-post-Event (ECAPE) formalisms. The representation of our rule-based approach requires a new declarative language that will offer the necessary syntax and semantics to describe ECAPE rules and the core elements in a business process. These elements are participants, variables, and activities. For this reason, we propose a new the rule-based business process definition language called ECAPE-L, which has an XML-based syntax to describe business processes in declarative way. An advantage of the ECAPE-M is that a process can be easily translated into a graph of rules. This graph is used to first, look into the changes of rules by checking the relationships between the rules and second, estimate cost changes in a process. Another advantage of the ECAPE-M is the translation of a process into a new colored Petri net called ECAPE net. An ECAPE net is used to check if a process satisfies some properties such as no Deadlock, and no Livelock. Finally, we proposed the BP-FAMA as an integration environment of the different elements we proposed. This environment consists of different tools namely:Business Rules Definer; Business Rules behavior analyzer and Business Rules simulator
2
Braunstein, Cécile. "Conception incrémentale, vérification de composants matériels et méthode d'abstraction pour la vérification de systèmes intégrés sur puce." Paris 6, 2007. http://www.theses.fr/2007PA066577.
Full textAbstract:
Cette thèse traite de la vérification formelle par model checking de systèmes intégrés sur puce. Nous proposons d'abord une méthode de conception incrémentale pour la vérification d'un composant matériel. Cette méthode est un cadre de conception par ajouts successifs de nouveaux comportements. Nous avons montré que cette méthode assure la non-régression d'un composant tout au long de sa conception. D'autre part, cette méthode permet aussi de faire évoluer la spécification d'un composant en prenant en compte les différentes fonctionnalités ajoutées au cours de la conception. Nous avons ensuite particularisé cette approche pour la conception et la vérification d'architectures pipelines. Cette méthode a été utilisée avec succès pour laconception de convertisseurs de protocole. La vérification par model-checking d'un système intégré sur puce se confronte au problème d'explosion combinatoire. Les techniques d'abstractions sont des méthodes efficaces pour alléger ce problème. Nous exposons un algorithme d'abstraction basé sur la spécification de chaque composant. Cet algorithme construit une structure de Kripke représentant un sous-ensemble des formules CTL tirées de la spécification. Cette construction se place dans un contexte de raffinement d'abstraction guidé par l'étude du contre-exemple produit par le model checker. Les premières expérimentations que nous avons réalisées montrent un gain considérable en temps de vérification et un accroissement conséquent de la taille du système vérifié. Ces résultats nous confortent sur l'intérêt de cette méthode d'abstraction.
3
Lewicki, Alexandre. "Conception de modèles haut niveau pour l'optimisation et la vérification de systèmes Bluetooth." Nice, 2008. http://www.theses.fr/2008NICE4110.
Full textAbstract:
Les différents travaux de recherche présentés dans cette thèse portent sur la conception de modèles fonctionnels à haut niveau d’abstraction ainsi que leur utilisation dans un flot de conception de systèmes sans fil. La Méthodologie de Conception des Systèmes Embarqués (MCSE) a été expérimentée pour la conception des circuits et systèmes dédiés à la technologie Bluetooth. La première partie de la thèse présente la méthodologie MCSE et son application dans la conception d’un système comportant un capteur de température distant et relié par Bluetooth. A partir des spécifications de l’application, les modèles fonctionnels ont été élaborés et raffinés après différentes étapes successives. Les modèles ont ensuite été traduits à l’aide de SystemC, une librairie C++ permettant de décrire les systèmes aux niveaux matériels et logiciels. Les modèles ont ensuite été exploités dans le cadre de simulation de réseaux sans fil. Ces résultats peuvent être utilisés suivant 3 différents axes : l’analyse de protocole, l’analyse de performances et l’exploration d’architecture. La deuxième partie du travail a été d’introduire les modèles fonctionnels dans le cadre d’un environnement de vérification matérielle avant fabrication. Deux environnements ont été mis en place pour les concepteurs du circuit ainsi que pour les ingénieurs de vérification. Cette technique permet de simuler et stresser le circuit de manière plus avancée, notamment grâce à la possibilité d’écrire des tests plus completsThe different works conducted in this thesis were to design high level functional models that were used in a wireless system design flow. The MCSE methodology was followed to design those models and the results have been used for Bluetooth technology system design and verification. The first part of the work presents the MCSE methodology that has been used for the design of the models. Starting from the specification of a concrete use case, a temperature sensor, we designed a functional model of the system with successive refinement steps. The models were then translated in SystemC, a C++ library that allows describing both hardware and software parts of a system. The results of the exploitation of the models in a wireless network simulation can be used for protocol analysis, performance analysis and performance exploration. The second part of the work was to introduce the functional models in a hardware verification environment. Two different techniques for design engineers and verification engineers have been settled. This technique brings enhanced verification features with the possibility to write complex tests
4
Wiels, Virginie. "Modularité pour la conception et la validation formelles de systèmes." Toulouse, ENSAE, 1997. http://www.theses.fr/1997ESAE0001.
Full textAbstract:
Structuration et compositionnalité sont des besoins importants dans le domaine des techniques formelles pour maîtriser la taille et la complexité des spécifications. Nous proposons un formalisme qui permet de spécifier des systèmes de façon modulaire, mais aussi d'exploiter la structure des spécifications pour réaliser des vérifications modulaires. Un outil de spécification (Moka) est associé à ce formalisme et peut être combiné avec des outils de démonstration logique existants. L'approche est illustrée sur trois applications de domaines différents. Nous mettons d'abord l'accent sur les besoins d'un cadre à la fois structuré, expressif et qui permette d'utiliser des outils de vérificétion et de validation. Pour répondre à ces besoins, nous proposons de combiner la logique temporelle (pour l'expressivité et les outils de vérification) avec des technqiues algébriques (pour la structuration). Nous présentons ensuite l'approche qui combine le calcul de modules défini par Ehrig et Mahr avec une logique temporelle. Elle s'appuie sur les travaux de Fiadeiro et Maibaum utilisant la théorie des catégories pour leur "Object Calculus". L'outil associé utilise les aspects constructifs de la théorie des catégories pour mettre en oeuvre les modules de spécification et les opérations de composition. L'approche est illustrée par une application au domaine des télécommunications. Les aspects vérification sont enfin abordés : nous expliquons comment le formalisme peut être utilisé pour faire de la vérification modulaire et l'intérêt d'interfacer l'outil Moka avec un outil de démonstration logique (ici TRIO). Deux autres applications sont présentées : un mécanisme de tolérence aux fautes et un système de contrôle de commandes d'avion.
5
Liu, Yinling. "Conception et vérification du système d'Information pour la maintenance aéronautique." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEI133.
Full textAbstract:
Le soutien opérationnel est l’un des aspects les plus importants pour la maintenance aéronautique. Il vise essentiellement à fournir un portefeuille de services permettant d’implémenter la maintenance avec un niveau élevé d’efficacité, de fiabilité et d’accessibilité. L’une des principales difficultés du support opérationnel est qu’il n’existe pas de plate-forme intégrant tous les processus de maintenance des avions afin de réduire les coûts et d’améliorer le niveau de service. Il est donc nécessaire de réaliser un système autonome de maintenance des avions dans lequel toutes les informations de maintenance peuvent être collectées, organisées, analysées et gérées de manière à faciliter la prise de décision. Pour ce faire, une méthodologie innovante a été proposée, qui concerne la modélisation, simulation, vérification formelle et analyse des performances du système autonome mentionné. Trois axes ont été abordés dans cette thèse. Premier axe concerne la conception et simulation d'un système autonome pour la maintenance aéronautique. Nous proposons une conception innovante d'un système autonome prenant en charge la prise de décision automatique pour la planification de la maintenance. Deuxième axe vise la vérification de modèles sur des systèmes de simulation. Nous proposons une approche plus complète de la vérification des comportements globaux et des comportements opérationnels des systèmes. Troisième axe porte sur l'analyse de la performance des systèmes de simulation. Nous proposons une approche consistant à combiner un système de simulation à base d’agent avec une approche « Fuzzy Rough Nearest Neighbor », afin de mettre en œuvre la classification et prévision efficaces des pannes pour la maintenance des avions avec des données manquantes. Finalement, des modèles et systèmes de la simulation ont été proposés. Des expérimentations de la simulation illustrent la faisabilité de l’approche proposéeOperational support is one of the most important aspects of aeronautical maintenance. It aims to provide a portfolio of services to implement maintenance with a high level of efficiency, reliability and accessibility. One of the major difficulties in operational support is that there is no platform that integrates all aircraft maintenance processes in order to reduce costs and improve the level of service. It is therefore necessary to build an autonomous aircraft maintenance system in which all maintenance information can be collected, organized, analyzed and managed in a way that facilitates decision-making. To do this, an innovative methodology has been proposed, which concerns modelling, simulation, formal verification and performance analysis of the autonomous system mentioned. Three axes were addressed in this thesis. The first axis concerns the design and simulation of an autonomous system for aeronautical maintenance. We offer an innovative design of an autonomous system that supports automatic decision making for maintenance planning. The second axis is the verification of models on simulation systems. We propose a more comprehensive approach to verifying global behaviours and operational behaviours of systems. The third axis focuses on the analysis of the performance of simulation systems. We propose an approach of combining an agent-based simulation system with the “Fuzzy Rough Nearest Neighbor” approach, in order to implement efficient classification and prediction of aircraft maintenance failures with missing data. Finally, simulation models and systems have been proposed. Simulation experiments illustrate the feasibility of the proposed approach
6
Mbarek, Ons. "Une approche de modélisation au niveau système pour la conception et la vérification de systèmes sur puce à faible consommation." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00837662.
Full textAbstract:
Une solution de gestion de puissance d'un système sur puce peut être définie par une architecture de faible puissance composée de multiples domaines d'alimentation et de leur stratégie de gestion. Si ces deux éléments sont économes en énergie, une solution efficace en énergie peut être obtenue. Cette approche nécessite l'ajout d'éléments structurels de puissance et de leurs comportements. Une stratégie de gestion doit respecter les dépendances structurelles et fonctionnelles dues au placement physique des domaines d'alimentation. Cette relation forte entre l'architecture et sa stratégie de gestion doit être analysée tôt dans le flot de conception pour trouver la solution de gestion de puissance la plus efficace. De récentes normes de conception basse consommation définissent des sémantiques pour la spécification, simulation et vérification d'architecture de faible puissance au niveau transfert de registres (RTL). Mais elles manquent une sémantique d'interface de gestion des domaines d'alimentation réutilisable ce qui alourdit l'exploration. Leurs sémantiques RTL ne sont pas aussi utilisables au niveau transactionnel pour une exploration plus rapide et facile. Pour combler ces lacunes, cette thèse étend ces normes et fournit une étude complète des possibilités d'optimisation de puissance basées sur la composition et la gestion des domaines d'alimentation pour des modèles fonctionnels transactionnels utilisant un environnement commun USLPAF. USLPAF comprend une méthodologie alliant conception et vérification des modèles transactionnels de faible consommation, ainsi qu'une bibliothèque de techniques de modélisation et fonctions prédéfinies pour appliquer cette méthodologie.
7
Tabart, Gilles. "Méthodes et outils pour l'aide à la conception et à la vérification du rendu graphique des systèmes interactifs." Toulouse 3, 2010. http://thesesups.ups-tlse.fr/1258/.
Full textAbstract:
La conception de représentations graphiques dédiées à des systèmes interactifs critiques est complexe. Dans cette thèse, nous proposons en premier lieu une étude approfondie des problèmes perceptifs spécifiques aux rendus graphiques au travers de trois études expérimentales. Nous présentons ensuite une analyse de l'activité à laquelle se livrent les concepteurs d'interfaces critiques. À partir de ces analyses, nous proposons une démarche d'aide à la conception et à la vérification des rendus graphiques répondant aux besoins spécifiques des concepteurs. Cette démarche facilite l'exploration visuelle des solutions, ainsi que la mise en rapport de hiérarchies fonctionnelles avec des hiérarchies visuelles. Elle supporte une approche de conception itérative, centrée utilisateur et visant un accompagnement sur toute la durée de vie des systèmes. Nous proposons pour finir d'instrumenter cette démarche à l'aide d'outils interactifs, dont nous illustrons l'utilisation au travers d'études de cas lié à l'aéronautique (ATC)Graphical representations are used in numerous field of activity as a way to convey information from an interactive system to its users. In some of these fields, the representation quality is vital: indeed, if users (like pilots or air-traffic controllers) have a bad perception of information, the consequences can be tragic. Graphical design and specification of such representations are complex because of the great amount and the diversity of graphical parameters to handle, because of the perceptual interactions between these parameters, and because of the need to manage multidisciplinary knowledge. We claim that these difficulties come also from a lack of tools and methods, which could enable a precise specification of graphical needs. The first part of our work deals with three experimental studies aimed at understanding in a deeper way the perceptive problems linked to the graphical rendering of interactive systems. Then, we expose an analysis of how the graphical designers confront critical interfaces design. Based on these analyses, we propose an approach responding to the specific designer's needs for their activity of designing and verifying the graphical rendering. This approach enables an easier visual exploration of solutions and an easier connection between functional and visual hierarchies. This is a user centered design and iterative approach that aims to follow a system during all its lifetime. Finally, we propose interactive tools that support this approach and we illustrate them with case studies
8
Khemaja, Maha. "Scrables : un système de conception et d'exploitation de documents structurés." Toulouse 3, 1993. http://www.theses.fr/1993TOU30275.
Full textAbstract:
Cette these s'inscrit dans le contexte des systemes de conception et d'utilisation assistee de documents. Elle decrit une approche et un outil appeles scrables (systeme de conception de rapports d'audit base sur un langage d'expression de structures). La conception des documents selon scrables est basee sur une description tres detaillee de leurs structures logiques et physiques. Grace a celles-ci, l'exploitation de ces documents selon une approche hypertexte est rendue possible. L'integration dans les documents de nouveaux types de liens, en particulier ceux qui sont specifiques aux documents d'audit a ete realisee. L'exploitation de la semantique liee a ces liens constitue une aide importante aux utilisateurs des documents. Certains de ces nouveaux types de liens ont ete introduits dans le but de permettre et de faciliter le recueil des connaissances a partir des documents, connaissances indispensables pour la mise en place d'un systeme intelligent d'aide a l'audit communicant avec les documents. Scrables est aujourd'hui complet, coherent et integre. Il est utilise par des auditeurs bancaires
9
Hjiej, Omar. "Systèmes de traitements coopératifs : spécification et vérification formelles orientées par des considérations de performances." Toulouse 3, 1993. http://www.theses.fr/1993TOU30244.
Full textAbstract:
Le developpement des systemes de traitements cooperatifs est une activite importante de l'informatique. Des techniques specifiques permettent de decrire et de verifier les proprietes fonctionnelles et quantitatives. Cependant, ces techniques sont dissociees et presentent des limites lorsque les systemes deviennent complexes. Une methodologie de specification formelle des composants logiciels en langage z est proposee. Le langage z est base sur la theorie des ensembles et la logique des predicats. Une specification z est composee de schemas, de trois types: etat, initialisation et operation. La puissance du formalisme a permis de developper une methodologie de verification logique automatique supportee par l'outil b. Lotos et estelle, candidates pour la conception des systemes cooperatifs, n'ont pas la flexibilite et la puissance de verification de z pour etablir plusieurs types de proprietes. Mais, le concept de point d'interaction qu'elles offrent pour decrire les frontieres entre processus concurrents, n'existe pas dans z. Aussi, z en a-t-il ete enrichi. La description z du processus offrant les operations d'interaction est operee par raffinages successifs bases sur des schemas d'abstraction. Le probleme de completude des operations est traite par resolution des predicats de pre-condition. L'interpretation des formes de concurrence offertes par z est analysee a l'aide des descriptions comportementales, decrites en csp, des differentes versions du modele du point d'interaction. La demarche d'evaluation de performance proposee tient a preserver la qualite des conceptions garanties par les techniques formelles de description. Par application d'un ensemble de regles, des reseaux de files d'attente codes en langage qnap2, sont generes a partir de specifications lotos annotees. Les resultats de performances sont obtenus grace aux annotations de duree et de probabilite associees respectivement aux actions et aux expressions de comportements composees par les constructeurs non deterministes de lotos
10
Li, Yao. "Proposition d'extension à SystemC-AMS pour la modélisation, la conception et la vérification de systèmes mixtes analogiques-numériques." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066190.
Full textAbstract:
Parmi les produits électroniques de l’industrie des semi-conducteurs, les applications mixtes numériques-analogiques (AMS) représentent une part de marché à forte croissance. Le principal problème pour la conception de systèmes AMS est l’absence de flot de conception standard, puisque les blocs AMS ne peuvent pas être synthétisés de façon systématique `a partir d’une spécification de haut niveau en l’absence d’information au niveau transistor. Par ailleurs, il est très difficile de modéliser les caractéristiques au niveau transistor dans des descriptions comportementales de plus haut niveau (système). Face à ces d´défis, nous proposons une plateforme de modélisation, de dimensionnement et de vérification unifiée. La plate-forme repose sur une méthode de dimensionnement ascendant des blocs analogiques et une approche de simulation descendante depuis le système jusqu’aux transistors. Les différents niveaux d’abstraction envisagés sont d´écrits grâce aux langages C/C ++ et SystemC-AMS. En outre, nous expliquons comment UVM-SystemC-AMS développé dans le cadre du projet européen FP7 VERDI, fournit une m´méthode pour la vérification des systèmes AMS avec des interactions HW / SW. Nous appliquons ces méthodes à deux circuits. Le premier est un circuit de conversion analogique numérique pipeline à 3 étages et 6 bits. Il présente une vue hiérarchique du processus de conception. Le second est un sous-système analogique d’un système implantable de télémétrie, qui inclut une boucle de rétroactionMixed-signal applications are among the fastest growing market segments in the electronics and semiconductor industry. This is driven by the growth opportunities in mobile communication, networking, power management, automotive, medical, imaging, and security applications, which all require analog and mixed-signal (AMS) content. One bottleneck exists if the designs include analog components together with digital ones. Digital design has a well-defined, top-down design methodology, but AMS design has traditionally been an ad hoc custom design process, it is more time-consuming interactive process and fully based on designerÕs expertise. The major difficulty is how to model the impact of circuit non-idealities and technology process variations on system- level performances.In this thesis, we present an unified modeling, design and verification platform with a fast sizing and biasing methodology. The proposed methodology propagates the circuit-level non- idealities into system-level simulations in a very natural way. The methodology synchronizes SystemC-AMS TDF MoC and electrical circuit simulator (SPICE), which enables to mix non- conservative system-level model with conservative nonlinear circuit netlist. Besides, we explain how UVM-SystemC-AMS developed in the FP7 Verdi project, provides an unified methodology for the verification of systems having interconnected AMS, HW/SW. In order to explore the effectiveness of the proposed methodology, two case studies are investigated: a 3-stage 6-bit ADC pipeline and a voltage regulator for an implantable telemetric system. The problem of hierarchical design is illustrated in the 3-stage 6-bit ADC pipeline while the problem of system architecture with feedback loop is illustrated in the implantable telemetric system
11
Mohand, Oussaïd Linda. "Conception et vérification formelles des interfaces homme-machine multimodales : applications à la multimodalité en sortie." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2014. http://www.theses.fr/2014ESMA0022/document.
Full textAbstract:
Les interfaces homme-machine (IHM) multimodales offrent à l’utilisateur la possibilité de combiner les modalités d’interaction afin d’augmenter la robustesse et l’utilisabilité de l’interface utilisateur d’un système. Plus particulièrement, en sortie, les IHM multimodales permettent au système de restituer à l’utilisateur, l’information produite par le noyau fonctionnel en combinant sémantiquement plusieurs modalités. Dans l’optique de concevoir de telles interfaces pour des systèmes critiques, nous avons proposé un modèle formel de conception des interfaces multimodales en sortie. Le modèle proposé se décompose en deux modèles : le modèle de fission sémantique qui décrit la décomposition de l’information à restituer en informations élémentaires, et le modèle d’allocation qui spécifie l’allocation des modalités et médias aux informations élémentaires. Nous avons également développé une formalisation B Événementiel détaillée des deux modèles : fission sémantique et allocation. Cette formalisation a été instanciée sur des études de cas puis généralisée dans un processus de développement B Événementiel cadre dans lequel s’inscrivent les modèles de fission sémantique et d’allocation. Cette formalisation a permis de procéder à la vérification de propriétés de sûreté, de vivacité et d’utilisabilitéMultimodal Human-Computer Interfaces (HCI) offer to users the possibility to combine interaction modalities in order to increase user interface robustness and usability. Specifically, output multimodal HCI allow system to return to the user, the information generated by the functional core by combining semantically different modalities. In order to design such interfaces for critical systems, we proposed a formal model for the design of output multimodal interfaces. The proposed model consists of two models: the semantic fission model describes the decomposition of the information to return into elementary information and the allocation model specifies the allocation of the elementary information with modalities and media. We have also developed a detailed Event B formalization for the two models: semantic fission and allocation. This formalization has been instantiated on case studies and generalized in an Event B development process framework including semantic fission and allocation models. This formalization allows to carry out safety, liveness and usability properties verification
12
Arcile, Johan. "Conception, modélisation et vérification formelle d’un système temps-réel d’agents coopératifs : application aux véhicules autonomes communicants." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLE029.
Full textAbstract:
Cette thèse est motivée par la question de la validation de propriétés dans un système composé de plusieurs agents mobiles prenants individuellement des décisions en temps réel.Chaque agent a une perception de l'environnement qui lui est propre et peut communiquer avec les autres agents à proximité.L'application qui a été choisie comme cas d'étude est celle des véhicules autonomes, qui du fait du large nombre de variables impliquées dans la représentation de tels systèmes, rend impossible des approches naïves.Les problématiques traitées concernent, d'une part, la modélisation d'un tel système, notamment le choix du formalisme et du niveau d'abstraction du modèle, et d'autre part, la mise en place d'un protocole d'évaluation de la prise de décision des véhicules.Ce dernier point inclut la question de l'efficacité de l'exploration de l'espace d'états du modèle.La thèse présente un ensemble de travaux, pouvant être complémentaires, visant à traiter ces problématiques.Tout d'abord, le système, composé des véhicules autonomes et de leur environnement, est défini avec précision.Il permet notamment d'observer l'impact des communications entre véhicules sur leur comportement.Le cadre logiciel VerifCar dédié à l'analyse de prise de décision de véhicules autonomes communicants est ensuite présenté.Il inclut un modèle paramétrique d'automates temporisés offrant la possibilité de vérifier des propriétés de logique temporelle.Une méthodologie d'analyse utilisant ces propriétés est présentée.On propose également une approche complémentaire permettant dans certains cas une meilleure efficacité et une plus grande expressivité.Elle est fondée sur le formalisme des MAPTs (Multi-Agent with timed Periodic Tasks), qui a été conçu pour la modélisation de systèmes temps réel d'agents coopératifs.Des algorithmes permettant une exploration dynamique des états de ce type de modèles (c'est à dire sans que l'espace d'états ne doive être préalablement construit) sont présentés.Enfin, une méthode combinée alliant la simulation aux outils de vérification de modèle afin de contrôler le niveau de réalisme est décrite et appliquée au cas d'étudeThis thesis is motivated by the question of the validation of properties in a system composed of several mobile agents individually making decisions in real time.Each agent has a perception of their own environment and can communicate with other agents nearby.The application that has been chosen as a case study is that of autonomous vehicles, which because of the large number of variables involved in the representation of such systems, makes naive approaches impossible.The issues addressed concern, on the one hand, the modeling of such a system, in particular the choice of the formalism and the level of abstraction of the model, and on the other hand, the implementation of an evaluation protocol of decision making of vehicles.This last point includes the question of the efficiency of the exploration of the state space of the model.The thesis presents a set of works, which can be complementary, aiming to treat these problems.First, the system, consisting of autonomous vehicles and their environment, is precisely defined.It allows in particular to observe the impact of communications between vehicles on their behavior.The VerifCar software framework dedicated to decision-making analysis of communicating autonomous vehicles is then presented.It includes a parametric model of timed automata with the ability to check temporal logic properties.An analysis methodology using these properties is presented.A complementary approach is also proposed, which in some cases allows for greater efficiency and greater expressiveness.It is based on the formalism of MAPTs (Multi-Agent with Timed Periodic Tasks), which was designed for modeling real-time systems of cooperative agents.Algorithms allowing a dynamic exploration of the states of this type of model (that is to say without the state space having to be built beforehand) are presented.Finally, a combined method combining simulation and model verification tools to control the level of realism is described and applied to the case study
13
Hillah, Lom Messan. "Intégration des méthodes formelles au développement dirigé par les modèles, pour la conception et la vérification des systèmes et applications répartis." Paris 6, 2009. http://www.theses.fr/2009PA066267.
Full text
14
Revol, Sébastien. "Profil UML pour TLM : contribution à la formalisation et à l'automatisation du flot de conception et vérification des systèmes-sur-puce." Grenoble INPG, 2008. http://www.theses.fr/2008INPG0065.
Full textAbstract:
Les travaux présentés dans cette thèse portent sur l'étude du langage UMl pour la conception des systèmes sur puce. La contribution pcindpale est la définition et l'exploitation d'un profil rapprochant les flots de conception fondés sur l'Unified Modeling Language et les standards traditionnellement employés dans l'indusbie électronique au niveau système, tels que Systemc-TLM et IP-XACT. AInsi, ensappuyant sur les techniques de l'Ingénierie Dirigée par les Modèles, des passerelles ont été établies afin d'assurer des opérations d1mport-export entre des desaiptions de composants matériels en IP-XACT et UMl, ainsi que la génération depuis ce langage d'une grande partie du code SystemC-TlM des composants. Une évaluation sur un cas d'étude Industriel démontre les intérêts de cette approche, en termes de condslon du langage, de Qualité du code généré, et au final de gain de temps pour la réalisation et l'intégration de modèles TlM. Pour ce cas, le gain a été évalué à un facteur 3 à 4The work presente
15
Dragomir, Iulia. "Conception et vérification d'exigences de sûreté temporisées à base de contrats dans les modèles SysML." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2510/.
Full textAbstract:
De nos jours, les systèmes informatiques croissent en taille et en complexité. Intégrés dans des dispositifs de différents domaines tels que l'avionique, l'aéronautique, l'électronique grand public, etc. , ils sont souvent considérés comme critiques à l'égard de la vie humaine, des coûts et de l'environnement. Concevoir des systèmes embarqués temps-réel critiques sûrs et fiables est une tâche difficile, étant donné que leurs modèles sont souvent source d'erreurs. Une façon pour les concepteurs de contourner cette difficulté consiste à s'appuyer sur la modélisation compositionnelle de composants logiciels pilotée par les exigences. Le raisonnement à base de contrats permet de construire des composants sûrs à partir des exigences globales du système en interposant des spécifications abstraites et partielles entre les besoins du système et les composants eux-mêmes. Informellement, un contrat modélise le comportement abstrait d'un composant du point de vue de l'exigence à satisfaire (c. A. D garantie) dans un contexte donné (c. A. D. Hypothèse). Les contrats peuvent être exploités pour décomposer et tracer les exigences au cours d'un développement itératif, mais aussi pour effectuer une vérification compositionnelle de la satisfaction des exigences. Dans cette thèse, nous présentons une méthodologie de raisonnement à base de contrats pour la conception et la vérification de systèmes sûrs développés en SysML. Ainsi, nous définissons en UML/SysML la syntaxe des contrats et des relations de raffinement entre contrats et/ou composants qui sont utilisées pour prouver la correction du système par rapport aux exigences. Ensuite, nous proposons un cadre formel qui modélise la sémantique d'un modèle UML/SysML étendu par des contrats selon une variante d'automates temporisés entrée/sortie et nous définissons la correspondance entre ces concepts. Nous formalisons les relations de raffinement par la relation d'inclusion de traces et nous prouvons leurs propriétés compositionnelles ce qui assure la correction de la méthodologie. L'approche est instanciée pour le profil OMEGA et la boîte à outils IFx2 qui génère partiellement les obligations de preuve. Finalement, plusieurs études de cas dont une issue de l'industrie complètent la théorie pour évaluer l'approche à base de contrats et ses résultats et les comparer aux méthodes classiques de model-checkingNowadays computer systems grow larger in size and more complex. Embedded in devices from different domains like avionics, aeronautics, consumer electronics, etc. , they are often considered critical with respect to human life, costs and environment. A development that results in safe and reliable critical real-time embedded systems is a challenging task, considering that errors are accidentally inserted in the design. A way for system designers to tackle this issue is to use a compositional design technique based on components and driven by requirements: it allows to infer from global requirements, component properties that must locally hold. Contract-based reasoning allows to compositionally derive correct components from global system requirements by interposing abstract and partial specifications for components. Informally, a contract models the abstract behavior a component exhibits from the point of view of the requirement to be satisfied (i. E. Guarantee) in a given context (i. E. Assumption). Contracts can be used to decompose and trace requirements during iterative design, but also to perform compositional verification of requirement satisfaction. In this thesis, we present a methodology for reasoning with contracts during system design and verification within SysML. Thus, we define the syntax for contracts in UML/SysML, as well as a set of refinement relations between contracts and/or components in order to prove the system's correctness with respect to requirements. Next, we provide a formal framework that models the semantics of a UML/SysML model extended with contracts as a mapping of the language concepts to a variant of Timed Input/Output Automata. The refinement relations are formalized based on the trace inclusion relation and compositional properties are proved to hold which ensures the soundness of the methodology. The approach is instantiated for the OMEGA Profile and IFx2 toolset with partial automatic generation of proof obligations. Finally, the approach is applied on several case studies, including an industry-grade system model, which show its efficiency by comparative verification results
16
Delahaye, Benoît. "Spécification Modulaire et Analyse Compositionnelle de Systèmes Stochastiques." Phd thesis, Université Rennes 1, 2010. http://tel.archives-ouvertes.fr/tel-00591609.
Full textAbstract:
Cette thèse présente des contributions originales pour la conception et la vérification de systèmes non-déterministes et stochastiques. Nos résultats sont divisés selon trois lignes directrices. Premièrement, nous généralisons la théorie des interfaces au cas stochastique, en s'appuyant sur le formalisme classique des chaînes de Markov à intervalles pour construire la première théorie de spécification compositionnelle pour systèmes stochastiques : les chaînes de Markov à contraintes. Deuxièmement, nous étendons la notion de contrats hypothèse-garantie et développons une théorie compositionnelle à base de contrats pour systèmes stochastiques, pour laquelle nous proposons des notions quantitatives de raffinement et de satisfaction. Finalement, nous proposons une méthodologie pour la vérification de systèmes complexes, basée sur une abstraction stochastique. Cette méthodologie, combinée avec le model-checking statistique, est appliquée avec succès à un cas d'étude industriel.
17
Knorreck, Daniel. "UML pour l'exploration de l'espace de conception, la simulation rapide et Analyse statique." Phd thesis, Télécom ParisTech, 2011. http://pastel.archives-ouvertes.fr/pastel-00662744.
Full textAbstract:
L'exploration de l'espace de conception au niveau système est effectuée tôt dans le flot de conception des systèmes embarqués et des systèmes sur puce. L'objectif est d'identifier un partitionnement matériel / logiciel approprié qui réponde à un ensemble de contraintes concernant la fonctionnalité, la performance, la surface de silicium, la consommation d'énergie, etc. Lors des étapes de conception précoces, des modèles de système précis, tels que des modèles RTL, peuvent être encore indisponibles. Par ailleurs, la complexité de ces modèles présente l'inconvénient d'être exigeant et lent dans la vérification. Il est communément admis que le seul remède à ce problème est l'abstraction, ce qui a engendré l'apparition de plates-formes virtuelles basées sur des techniques telles que la modélisation au niveau transactionnel. Étant non fonctionnels, les modèles \textit{approximately timed} vont encore plus loin en faisant l'abstraction de données simplement selon leur présence ou absence et en introduisant des instructions symboliques. La méthodologie DIPLODOCUS et son profil UML correspondant réalisent les abstractions susmentionnées. La méthodologie s'appuie sur l'approche en Y, qui traite des fonctionnalités (appelées application) et leur réalisation (appelée architecture) de manière orthogonale. La sémantique formelle de DIPLODOCUS ouvre conjointement la voie à la simulation et à la vérification formelle, ce qui a été démontré préalablement a ce travail. Cette thèse propose des améliorations à la méthodologie qui permettent la vérification des propriétés fonctionnelles et non fonctionnelles. Au début, nous nous concentrons sur la façon dont les propriétés fonctionnelles sont exprimées. Puisque la vérification des modèles de haut niveau est habituellement réalisée avec la logique temporelle, nous suggérons une façon plus intuitive qui correspond au niveau d'abstraction du modèle qui doit être vérifié. Le langage graphique, mais formel nommé TEPE est la première contribution de ce travail. Pour atteindre un niveau élevé de confiance en vérification dans un délai raisonnable, le modèle doit être exécuté efficacement. La deuxième contribution vise donc une sémantique d'exécution pour les modèles DIPLODOCUS et une stratégie de simulation qui s'appuie sur l'abstraction. L'avantage est qu'une granularité grossière du modèle d'application se traduit directement par une augmentation de la vitesse de simulation. Comme troisième contribution, nous présentons un compromis entre la couverture limitée de la simulation et l'exhaustivité des techniques formelles. Lorsqu'il s'agit de modèles complexes, l'exhaustivité peut être entravée par le problème d'explosion combinatoire. En raison de l'abstraction de données, les modèles d'application DIPLODOCUS comportent des opérateurs non-déterministes. La simulation à couverture élargie vise à exploiter un sous-ensemble, ou bien l'intégralité, des valeurs des variables aléatoires. Par conséquent, une analyse statique des modèles DIPLODOCUS est effectuée et les informations caractérisant la partie significative de l'espace d'état de l'application sont propagées au simulateur. Enfin, nous fournissons des preuves de l'applicabilité des contributions par le biais d'une étude de cas dans le domaine du traitement du signal. Il sera démontré que les propriétés courantes se traduisent aisément en TEPE. Par ailleurs, la simulation rapide et sa couverture élargie fournissent des indications pertinentes qui sont susceptibles d'aider le développeur à configurer une plate-forme radio logicielle.
18
Fontan, Benjamin. "Méthodologie de conception de systèmes temps réel et distribués en contexte UML/SysML." Phd thesis, Université Paul Sabatier - Toulouse III, 2008. http://tel.archives-ouvertes.fr/tel-00258430.
Full textAbstract:
En dépit de ses treize diagrammes, le langage UML (Unified Modeling Language) normalisé par l'OMG (Object Management Group) n'offre aucune facilité particulière pour appréhender convenablement la phase de traitement des exigences qui démarre le cycle de développement d'un système temps réel. La normalisation de SysML et des diagrammes d'exigences ouvre des perspectives qui ne sauraient faire oublier le manque de support méthodologique dont souffrent UML et SysML. Fort de ce constat, les travaux exposés dans ce mémoire contribuent au développement d'un volet " méthodologie " pour des profils UML temps réel qui couvrent les phases amont (traitement des d'exigences - analyse - conception) du cycle de développement des systèmes temps réel et distribués en donnant une place prépondérante à la vérification formelle des exigences temporelles. La méthodologie proposée est instanciée sur le profil TURTLE (Timed UML and RT-LOTOS Environment). Les exigences non-fonctionnelles temporelles sont décrites au moyen de diagrammes d'exigences SysML étendus par un langage visuel de type " chronogrammes " (TRDD = Timing Requirement Description Diagram). La formulation d'exigences temporelles sert de point de départ à la génération automatique d'observateurs dédiés à la vérification de ces exigences. Décrites par des méta-modèles UML et des définitions formelles, les contributions présentées dans ce mémoire ont vocation à être utilisées hors du périmètre de TURTLE. L'approche proposée a été appliquée à la vérification de protocoles de communication de groupes sécurisée (projet RNRT-SAFECAST).
19
Baro, Sylvain. "Conception et implémentation d'un système d'aide à la spécification et à la preuve de programmes ML." Phd thesis, Université Paris-Diderot - Paris VII, 2003. http://tel.archives-ouvertes.fr/tel-00008416.
Full textAbstract:
Pouvoir vérifier la conformité d'un programme avec sa spécification représente un enjeu important. On peut utiliser un assistant de preuve : un logiciel permettant la description du problème, la construction des preuves et leur vérification. Nous avons implémenté un système où l'utilisateur décrit la spécification du programme dans un formalisme logique ad hoc, donne le programme dans le sous-ensemble fonctionnel de ML (comprenant filtrage, définitions récursives et fonctions partielles), puis construit interactivement les preuves de correction nécessaires pour prouver la validité du programme.
20
Kmimech, Mourad. "Vérification d’assemblages de composants logiciels : Application aux modèles de composants UML2.0 et Ugatze." Pau, 2010. http://www.theses.fr/2010PAUU3017.
Full textAbstract:
L'approche par composants vise la réutilisation par assemblage aisé et cohérent des composants. Mais l’obtention d’un assemblage de composants cohérent n’est pas un exercice facile. Pour y parvenir, nous préconisons une approche contractuelle distinguant divers contrats syntaxiques, structurels, sémantiques, de synchronisation et de qualité de services. Nous avons appliqué avec succès cette approche contractuelle sur deux modèles de composants semi-formels : UML2. 0 et Ugatze. En effet, nous proposons deux démarches VerifComponentUML2. 0 et VerifComponentUgatze. La démarche VerifComponentUML2. 0 vise la vérification des contrats syntaxiques, structurels, de synchronisation et de qualité de services sur une assemblage de composants UML2. 0 en passant par les deux modèles de composants formels Acme/Armani et Wright. VerifComponentUML2. 0 est équipé de deux outils : Wr2fdr et Wright2Ada. L’outil Wr2fdr permet de traduire des Wright vers CSP afin de vérifier les contrats de synchronisation en utilisant le model-checker FDR. L’outil Wright2Ada est un outil IDM permettant de transformer de Wright en Ada afin d’ouvrir UML2. 0 sur les outils d’analyse statique et dynamique associés à Ada. La démarche VerifComponentUgatze offre un cadre permettant de vérifier les contrats syntaxiques et structurels d’un assemblage de composant Ugatze en passant par Acme/ArmaniThe component approach aims for the reuse by a coherent and easy components assembly. But obtaining a coherent components assembly is not an easy exercise. To achieve this, we advocate a contractual approach distinguishing different syntactic, structural, semantic, synchronization and service quality contracts. We have successfully applied this approach on two models of semi-formal contractual components: UML2. 0 and Ugatze. Indeed, we propose two approaches: VerifComponentUML2. 0 and VerifComponentUgatze. The VerifComponentUML2. 0 approach aims the verification of syntactic, structural, synchronization and quality service contracts on a UML2. 0 component assembly through two formal component models Acme/Armani and Wright. VerifComponentUML2. 0 has two tools: Wr2fdr and Wright2Ada. The tool Wr2fdr allows translating Wright to CSP contracts in order to verify synchronization using the model checker FDR. It is a IDM tool Wright2Ada which allow is transforming Wright to Ada, in order to open UML2. 0 on static analysis and dynamic tools associated with Ada. VerifComponentUgatze approach provides a frame allowing to check syntactic and structural contracts of an Ugatze component assembly through Acme/Armani
21
Bonhomme, Sylvain. "Méthodologie et outils pour la conception d'un habitat intelligent." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2008. http://tel.archives-ouvertes.fr/tel-00292456.
Full textAbstract:
La réalisation de systèmes complexes de mesures, de contrôle et de surveillance nécessite une méthodologie de conception rigoureuse et des outils adaptés pour aboutir à un système sans faute. La démarche méthodologique proposée vise à aider à la conception d'un système complexe dédié à la gestion intelligente du confort et à la sécurité des personnes au sein de l'habitat. Cette démarche s'intègre dans un processus d'Ingénierie Système et s'appuie sur les standards UML et SYSML, mais également sur le formalisme HiLes, développé par le LAAS et adapté à la conception de modèle commande, la vérification formelle et la simulation numérique. Ces travaux de thèse présentent les méthodes et les outils de conception préconisés pour un habitat intelligent intégrant les objectifs de confort et de sécurité. Deux expérimentations sont décrites utilisant une commande auto-adaptative basée sur l'apprentissage des habitudes des utilisateurs dans leur environnement de vie et implémentés sur site réel.
22
Vincent, Aymeric. "Conception et réalisation d'un vérificateur de modèles AltaRica." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2003. http://tel.archives-ouvertes.fr/tel-00007067.
Full textAbstract:
Le formalisme AltaRica, développé au LaBRI conjointement avec des industriels, permet d'analyser un même système grâce à plusieurs méthodes différentes (arbres de défaillances, réseaux de Petri, chaînes de Markov) afin d'effectuer des études de sûreté de fonctionnement. Ces méthodes sont outillées par des outils industriels. Cette thèse a eu pour but de développer un outil de vérification formelle basé sur une structure de données symbolique, les diagrammes de décision binaires, qui permet de représenter de manière compacte les systèmes de transitions. Cet outil a été doté d'un langage de spécification très expressif, le mu-calcul de Park, qui est la logique du premier ordre étendue par des points fixes sur les relations. Ce mémoire décrit la logique de spécification employée dans le vérificateur de modèles (Mec 5) que nous avons développé, le formalisme AltaRica et les extensions apportées au langage AltaRica durant cette thèse. Ensuite certains aspects de l'implémentation de Mec 5 sont décrits, comme l'architecture du logiciel et certains composants essentiels dont le module de gestion des diagrammes de décision binaires. Puis, une solution élégante et très générique du problème de la synthèse de contrôleurs est décrite, qui permet de spécifier des objectifs de contrôle arborescents et constitue donc une extension naturelle du cadre proposé par Ramadge et Wonham. Cette méthode ramène le problème de la synthèse de contrôleurs à un problème de calcul de stratégies gagnantes. Enfin, une méthode de calcul des stratégies gagnantes dans un jeu de parité est proposée et il est montré que Mec 5 peut calculer de telles stratégies.
23
Molva, Refik. "Conception et realisation d'un observateur d'architectures multicouches dans les reseaux d'ordinateurs." Toulouse 3, 1986. http://www.theses.fr/1986TOU30207.
Full textAbstract:
Presentation des techniques de vérification dans un système distribue. Définition d'une technique de test basée sur le concept de l'observateur. Réalisation d'un outil d'observation de protocoles sur le réseau local industriel factor et sur le système de communication de la direction opérationnelle des telecommunications
24
Riahi, Meriem. "Contribution à l'élaboration d'une méthodologie de spécification, de vérification et de génération semi-automatique d'interfaces homme-machine : application à l'outil Ergo-Conceptor+." Valenciennes, 2004. http://ged.univ-valenciennes.fr/nuxeo/site/esupversions/0e55b207-03e5-40e1-9825-0e37a46d3890.
Full textAbstract:
La recherche effectuée vise l'élaboration d'une démarche globale de conception des interfaces homme-machine qui s'appuie sur l'utilisation d'outils formels pour l'identification, la spécification et l'analyse du comportement des objets intervenant dans les interactions homme-machine. L'approche proposée vise à satisfaire les points suivants : (1) une analyse globale du système homme-machine (SHM) couvrant l'analyse de la tâche, des fonctionnements et des dysfonctionnements du système à contrôler, permettant la déduction des besoins informationnels de l'opérateur (BIO) ; (2) une modélisation formelle du comportement du SHM permettant la gestion automatique du dialogue et la vérification des bonnes propriétés de l'interface ; (3) une spécification graphique de l'interface intégrant les recommandations ergonomiques nécessaires de représentation et regroupement des objets au niveau des différentes vues de l'interface ; (4) une génération semi-automatique de l'interface à partir des spécifications préétablies. La méthode se base sur un système à base de connaissances intégrant les recommandations ergonomiques nécessaires pour la matérialisation graphique des différents objets identifiés lors de l'analyse du système pour leur affichage et leur manipulation par l'utilisateurThis research work is carried out in the context of design and semi-automatic generation of graphical Interfaces for process control. It studies a new approach for ergonomic Interface design, using a formal language for the specification of interface objects and their behaviour. The proposed approach aims to cover these main points: (1) an analysis of the HMS to identify the different functioning states of the system and the possible interventions of the human operator, expressing the interaction of the operator within the interface according to different functioning contexts of the system allowing the deduction of the user requirements; (2) a formal modelling of the Human-Machine System behaviour making possible the validation of the specifications before going on to the generation of the interface ; (3) a graphical specification of the interface integrating ergonomic criteria for the presentation and the dialogue of the interface; (4) a sem-automatic generation oh the interface rerading to the generated specifications. We use a model-based tool which is able to decide on the appropriate displays. It takes into consideration, on the one hand the results of the previous analysis (the list of its functioning states, the user requirements associated to each state,. . . ) and on the other hand, specific formalised guidelines stored in its knowledge bases
25
Lemazurier, Lori. "Conception d’un système avancé de réacteur PWR flexible par les apports conjoints de l’ingénierie système et de l’automatique." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2018. http://www.theses.fr/2018IMTA0069/document.
Full textAbstract:
Devant l’augmentation de la part des énergies renouvelables en France, cette thèse propose d’étudier l’augmentation de la flexibilité des réacteurs à eau pressurisée en croisant deux disciplines pour, chacune, atteindre des objectifs complémentaires : l’Ingénierie Système (IS) et l’Automatique.Dans le contexte de l’ingénierie de systèmes complexes et du Model Based Systems Engineering, ce travail propose dans un premier temps une méthode de conception se fondant sur les principes normatifs de l’IS et respectant les habitudes et les pratiques courantes en ingénierie de Framatome. Cette méthode a pour vocation de formaliser et assurer le passage des exigences aux architectures et d’améliorer les capacités de vérification des modèles développés lors de la conception. Elle s’organise autour de langages de modélisation interopérables, couvrant l’ensemble des processus promus par l’IS. La méthode proposée est appliquée sur le système dont les performances sont les plus limitantes dans le contexte de l’augmentation de flexibilité : le Core Control. Ce composant algorithmique du réacteur assure le contrôle des paramètres de fonctionnement du cœur : la température moyenne, la distribution axiale de puissance et la position des groupes de grappes.La thèse propose ensuite des contributions techniques relevant du champ de l’Automatique. Il s’agit de concevoir un système de régulation répondant aux exigences issues de la formalisation IS évoquée ci-dessus. La solution proposée repose sur une stratégie de commande hiérarchisée, utilisant la complémentarité des approches dites de commande multi-objectif, de séquencement de gains et enfin de commande prédictive. Un modèle de réacteur nucléaire simplifié innovant est développé à des fins de conception du système de régulation et de simulations intermédiaires. Les résultats obtenus ont montré les capacités d’adaptation de la démarche proposée à des spécifications diverses. Les performances atteintes sont très encourageantes lorsque évaluées en simulation à partir d’un modèle réaliste et comparées à celles obtenues par les modes de pilotages classiquesIn the event of increasing renewable energies in France, this thesis proposes to study the flexibility increase of pressurized water reactors (PWR) throughout two different engineering disciplines aiming at complementary objectives: Systems Engineering (SE) and Control theory.In a first phase, within the frame of complex systems design and Model Based Systems Engineering, this work proposes a SE method based on SE standard principles and compliant with Framatome’s practices and addressing the revealed issues. This SE contribution is twofold: formalize and ensure the path from requirements to system architectures and enhance the capabilities of models verification. The method revolves around interoperable modeling languages, covering the SE processes: from requirement engineering to system architecture design. The method is applied to the system, which performances are the most limiting in the context of flexibility increase: the Core Control. This algorithmic reactor component ensures the control of: the average coolant temperature, the axial offset and the rod bank position, three of the core main functioning parameters.In order to provide a technical contribution relying on some advanced control methodologies. It consists in designing a control system meeting the requirements defined by the SE method application. The proposed solution is in a two-layer control strategy using the synergies of multi-objective control, gain-scheduling and predictive control strategies. A simplified innovative nuclear reactor model is employed to conceive the control algorithm, simulate and verify the developed models. The results obtained from this original approach showed the ability to adapt to various specifications. Compared to conventional core control modes, the simulation results showed very promising performances, while meeting the requirements, when evaluated on a realistic reactor model
26
Rouxel, Samuel. "Modélisation et caractérisation de plates-formes SoC hétérogènes : application à la radio logicielle." Lorient, 2006. http://www.theses.fr/2006LORIS077.
Full textAbstract:
Les travaux de cette thèse, menés dans le cadre du projet RNRT A3S, intègrent la notion de composants au sein d'une méthodologie de conception de plates-formes SoC (System on Chip), basée sur le langage de modélisation UML (Unified Modeling Language). Cette méthodologie propose un environnement de conception haut-niveau, basé sur le profil UML A3S, développé pour apporter la sémantique du domaine des systèmes temps réel embarqués et en particulier celle relative aux applications Radio Logicielle. Elle repose sur une approche MDA ou l'architecture est dirigée par les modèles où chaque modèle correspond à un niveau d'abstraction, à un niveau de raffinement particulier. Une chaîne UMTS a permis la validation de l'outil réalisé, en confrontant les résultats estimés de l'outil, à ceux mesurés sur une plate-forme temps réel hétérogène (multi-DSP, multi-FPGA). Une partie du travail s'est concentré sur l'identification des composants utiles à la conception des systèmes SoC, et de leurs caractéristiques, en adéquation avec le niveau d'abstraction considéré. Une autre partie des travaux a porté sur la définition des modèles UML, et donc du profil, qui définissent la sémantique des différents composants identifiés en fonction de la configuration (PIM, PSM), ainsi que leurs relations. Une réflexion a été nécessaire afin d'élaborer les diverses règles de vérification et modèles d'exécution qui permettent d'informer le concepteur de ses erreurs et de la faisabilité du système modélisé. Un modèle de système d'exploitation a également été inclus, enrichissant la liste des éléments (composants) déjà définis et démontrant l'extensibilité (scalabilité) du profilThe work of this PhD has been carried out within the framework of the A3S project and relies on component aspects integrated within a SoC platform design methodology, which is based on the UML language. This methodology proposes a high-level design framework based on the A3S UML profile developed to provide real-time embedded system semantic especially in SDR domain. An MDA approach has been considered to deal with different abstraction levels when specifying systems. First part of the work focused on identifying the component required designing a SoC system, and their characteristics depending on the component abstraction levels. Several types of component (software and hardware) whose characteristics depend on their modelling (PIM or PSM models) have been considered. Second part of the work focused on the definition of UML metamodels, which are grouped to define the A3S UML profile that establish the semantic of identified components depending on their modelling and their relations. We have defined extensive verification rules and applied a model of computation to inform designers about errors that have been done and to ensure the feasibility of their systems. Finally an operating system model has been included to demonstrate the scalability and the extension mechanisms of the UML language and profile which improve the list of components that have been already integrated within our framework. An UMTS application has validated our approach by comparing the estimated results computed by the tool with measured results obtained on a heterogeneous real-time platform (with several DSP and FPGA)
27
Balland, Emilie. "Conception d'un langage dédié à l'analyse et la transformation de programmes." Phd thesis, Université Henri Poincaré - Nancy I, 2009. http://tel.archives-ouvertes.fr/tel-00435881.
Full textAbstract:
Développer des analyseurs statiques nécessite une manipulation intensive de structures d'arbres et de graphes représentant le programme. La finalité de cette thèse est de proposer des constructions de langage dédiées au prototypage d'outils d'analyse et de transformation de programmes et inspirées de la réécriture de termes et de termes-graphes. L'originalité de notre approche est d'embarquer ces nouvelles constructions dans les langages généralistes sous la forme d'un langage dédié embarqué. Les travaux de cette thèse se fondent sur le langage Tom qui propose d'embarquer des constructions de réécriture dans des langages généralistes comme Java. La première contribution de cette thèse a été de formaliser les langages embarqués sous le concept de langage îlot. Ce formalisme a ainsi permis de certifier la compilation du langage Tom. Nos travaux sur l'analyse de Bytecode nous ont ensuite conduit à réfléchir à la représentation et la manipulation de graphes de flot de programmes et nous avons alors proposé des constructions de langage inspirées de la réécriture de termes-graphes. Une autre contribution de cette thèse est la conception d'un langage de stratégies adapté à l'expression de propriétés sur un programme. Associé au filtrage, ce langage permet d'exprimer de manière déclarative des analyses et des transformations sur des arbres ou des graphes. Enfin, l'ensemble des propositions de cette thèse a été intégré au langage Tom sous la forme de nouvelles constructions syntaxiques ou d'améliorations de constructions existantes et a ainsi pu être appliqué à l'analyse du langage Java.
28
Nastov, Blazo. "Contribution à une méthode outillée pour la conception de langages de modélisation métier interopérables, analysables et prouvables pour l'Ingénierie Système basée sur des Modèles." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT272/document.
Full textAbstract:
L'Ingénierie des Systèmes (IS) est une approche pluridisciplinaire et collaborative pour mener à bâtir et structurer la conception puis la réalisation et le développement de systèmes complexes. L’IS repose à la fois sur une approche processus et sur la mise en oeuvre de modèles de systèmes s'appuyant de fait dans un contexte basé ou dirigé par des modèles. On parle alors d’Ingénierie Système Basée sur des Modèles (ISBM ou Model based Systems Engineering MBSE). L’ISBM introduit des concepts, méthodes et techniques pour construire et gérer des modèles. Elle a pour objectif l’atteinte et l’amélioration de leur qualité afin de procurer aux parties prenantes un degré de confiance jugé suffisant pour aider la prise des décisions de conception, d'amélioration et de réalisation. Ces décisions conditionnent le fonctionnement, la sûreté, la sécurité, les coûts, et plus généralement tout un ensemble de propriétés attendues à la fois du modèle comme du système modélisé, tout au long de la phase aval de l’ingénierie et de développement, jusqu’à la réalisation et au déploiement du système. La qualité des modèles est obtenue au travers des processus de Vérification et Validation (V&V). Les objectifs sont alors d’assurer que les modèles soient cohérents, bien formés, bien construits et représentés correctement. En effet, aux yeux des parties prenantes, les modèles doivent être fiables, fidèles et pertinents au regard des besoins des concepteurs, représentant aussi précisément que possible le point de vue du système en cours de conception. Des langages de modélisation dit « métier » (Domain Specific Modelling Languages ou DSML) sont spécifiquement créés pour pouvoir fournir des représentations i.e. des modèles dans les différents points de vue sur le système. Un DSML est basé sur une syntaxe et sur une sémantique. La sémantique de ces langages est en général fournie par des approches externes (vérificateurs de modèles). Ces dernières sont, à notre sens, une limitation clé pour le déploiement des stratégies de V&V dans le contexte de l’ISBM. En réponse à cette limitation, la contribution conceptuelle de cette thèse est présentée sous la forme d’un nouveau langage de métamodélisation, nommé xviCore (noyau exécutable, vérifiable et interopérable). xviCore fournit les concepts et les principes pour définir puis vérifier et valdier la syntaxe et la sémantique en phase de construction de tels DSML en combinant trois métalangages : un métalangage orienté objet pour la conception de la partie syntaxique, un métalangage pour la conception du comportement et un métalangage pour la conception de propriétés formelles. La contribution méthodologique de ces travaux permet ensuite le déploiement d’une stratégie de V&V «directe» en lieu et place des traditionnelles approches externes. Elle est basée sur la simulation et la preuve formelle de propriétés. Le mécanisme de simulation permet d’observer le comportement des modèles de systèmes au travers de leur exécution, tandis que le mécanisme de preuve permet de spécifier et ensuite de vérifier des propriétés formelles. La contribution technique se compose d’un ensemble des plugins Eclipse qui implémentent le métalangage xviCore, le mécanisme de simulation et le mécanisme de la preuve formelleSystems Engineering (SE) is an interdisciplinary and collaborative approach for successful design and management of large scale complex systems. Among other principles, SE promotes and mandates a model-based (or model-driven) approach for all stages of system design processes, denoted Model-Based Systems Engineering (MBSE). This implies concepts, techniques and tools for creating and managing various systems models for the purpose of stakeholders, and for reaching and improving the quality of models helping then stakeholders during decision-making processes, to make decisions faster and efficiently with enough confidence. Indeed, these decisions impact all along the downstream phases of system engineering and development until the realization and deployment of the real system, its functioning, safety, security, induced costs and so on. In this work, a particular attention is given to model verification and validation (V&V). The goals are to assure prior to decision-making processes, first, that models are coherent, well-formed and correctly build and represented, and second, that they are trustworthy and relevant, representing as accurately as possible the viewpoints of a system under design as expected by stakeholders.Such models provide stakeholders with confidence and trust, aiding them in making, but also in arguing decisions. Models are created by using modeling languages that are specifically tailored for a given viewpoint of a system, denoted Domain Specific Modeling Languages (DSMLs).The basic principles on which a DSML is based are its syntax and its semantics, but current DSMLs have been more studied from the syntactical point than from the semantical one that is often neglected or, when needed, provided by means of translating the DSML into third party formalisms. This is the key limitation preventing the deployment of a successful V&V strategy in MBSE context. To overcome this shortcoming, this thesis proposes first a conceptual contribution consisting of a new metamodeling language, called eXecutable, Verifiable and Interoperable Core (xviCore), allowing stakeholders to build DSMLs (called xviDSMLs), that along with their syntax also integrates semantics. Our solution combines, three meta-languages, an object-oriented metamodeling language for the specification of the syntactical part with a formal behavioral modeling language and a property modeling language for the semantical part. The methodological contribution of this work allows the deployment of successful V&V strategies allowing for direct (without transformation) model verification by simulation and properties proof. We propose a mechanism to simulate the expected behavior of a SoI through model execution based on the blackboard-based communication model, and a mechanism for specification and verification of formal properties. The technical contribution consists of an Eclipse-EMF deployable plug-in that implements the metamodeling language xviCore and the mechanisms for simulation and formal property verification
29
Shraideh, Ahmad. "Analyse et optimisation d'un processus à partir d'un modèle BPMN dans une démarche globale de conception et de développement d'un processus métier : application à la dématérialisation de flux courrier du projet GOCD (PICOM)." Phd thesis, Ecole Centrale de Lille, 2009. http://tel.archives-ouvertes.fr/tel-00579520.
Full textAbstract:
Cette thèse a été réalisée dans le cadre du projet " Gestion et Optimisation de la Chaîne Documentaire ", projet labellisé par le Pôle de compétitivité des Industries du Commerce. Le projet a pour but de concevoir et de développer un nouveau workflow et un outil d'aide à la décision. Ce système doit être capable de gérer et d'optimiser le flux complet dématérialisé de contrats reçus à COFIDIS.Nous présentons d'abord le framework retenu dans le cadre du projet pour modéliser et implémenter le workflow. En phase de conception BPMN a été choisi. Pour la partie développement, l'utilisation de BPEL a été préconisée pour implémenter et exécuter l'application finale (services web).Cependant la flexibilité offerte par BPMN peut conduire à des propriétés indésirables du processus telles que blocage et inaccessibilité. De plus, BPMN a été conçu pour fournir des modèles Orientés Process. Les données ou les ressources y sont donc peu représentées. En conséquence, l'analyse de performance sur un modèle BPMN est quasi inexistante.Afin de surmonter ces problèmes nous proposons d'insérer dans le framework deux nouvelles phases. Ces deux phases sont appliquées au modèle BPMN. La première est une phase de vérification et de validation et la deuxième une phase d'optimisation. Ces deux phases sont réalisées en transformant le modèle BPMN vers un langage formel. Notre choix dans ce travail a été d'utiliser les réseaux de Petri. Ce qui nous a permis de vérifier et de valider de bonnes propriétés du process. Quant à l'optimisation, nous avons défini une nouvelle variante du problème d'affectation (bin packing problem) et proposé une résolution à intégrer dans le processus d'aide à la décision
30
Osseiran, Adam. "Définition, étude et conception d'un microprocesseur autotestable spécifique : cobra." Grenoble INPG, 1986. http://tel.archives-ouvertes.fr/tel-00320884.
Full textAbstract:
Description des différentes étapes de la conception d'un microprocesseur pour le contrôle des automatismes de sécurité, en particulier pour les systèmes de transport. Ce microprocesseur est autotestable, c'est-à-dire capable de détecter ses propres erreurs. La conception du circuit est basée sur les hypothèses de pannes au niveau analytique dans la technologie NMOS. Les blocs fonctionnels «Strongly Fault Secure» et les contrôleurs «Strongly Code Disjoint» sont à la base des circuits «Self-checking», dits autotestables. Le circuit COBRA démontre la faisabilité d'un microprocesseur autotestable. COBRA gère indépendamment 19 signaux différents, date des événements externes, mesure des fréquences, surveille 14 entrées logiques et possède 7 sorties indépendantes. Le programme d'application de COBRA est contenu dans une mémoire morte programmable externe de 16 Koctets adressés par 14 bits multiplexés sur le bus interne de 8 bits. COBRA contient également une liaison série, une mémoire à accès direct de 64 octets et 3 temporisateurs de 14 bits indépendants ainsi qu'une unité arithmétique et logique de 8 bits, COBRA exécute un jeu de 43 instructions
31
Lazreg, Sami. "Applications variables sur plateformes configurables : Analyse anticipée de faisabilité et d'optimalité." Thesis, Université Côte d'Azur, 2020. http://www.theses.fr/2020COAZ4070.
Full textAbstract:
Les systèmes embarqués sont implémentés à partir d'applications hautement variables ciblant des plateformes matérielles configurables. Outre cela, une application peut être implémentée de plusieurs façons sur une plateforme. Cette triple variabilité engendre un nombre astronomique de conceptions système alternatives. Le problème crucial est alors d'établir au plus tôt et précisément quelles sont les conceptions système qui satisfont et optimisent les exigences fonctionnelles et non-fonctionnelles. Généralement, les approches de conception de systèmes capturent les exigences et spécifications pour automatiquement dériver et évaluer toutes les alternatives. Cependant, ces approches ne gèrent pas cette variabilité et sont donc itératives. Par conséquent, chaque conception de systèmes issus des implémentations possibles des variantes d’application et des configurations de plateforme doivent être modélisées et évaluées séparément. Cet inconvénient majeur peut rendre ces approches inapplicables à grande échelle. D'un autre côté, les approches de modélisation de la variabilité exploitent les points communs entre les différents produits pour évaluer efficacement toute la ligne de produits. Pourtant, elles ne vérifient que certaines parties du problème et ne fournissent aucun moyen de dériver l'espace de conception automatiquement. Nous proposons une approche qui combine et étend ces deux méthodes. Après avoir capturé les exigences et spécifications sous la forme d'un flot de donnés variables, d'une plateforme matérielle configurable, d'une fonction de cout et de contraintes non- fonctionnelles, nous dérivons un espace de conception encodé par une ligne de produit comportementale. Finalement, un algorithme de vérification permet de vérifier toutes les facettes du problème pour identifier efficacement les conceptions de système les plus adaptées. Les avantages de notre approche sont évalués à travers un cas d'étude industriel automobileSoftware-intensive embedded systems, such as automotive systems, are increasingly built from highly- variable applications targeting evermore configurable hardware platforms. Moreover, besides variability present at specification level, there are often various ways to implement a given application on a specific platform. This threefold variability leads to an immense number of system design alternatives. The notorious problem is establishing, at the early stages of development, which designs fulfill and optimize functional and non-functional requirements. Traditional system design frameworks capture system requirements and specifications to derive and evaluate every design automatically. They evaluate every facet of the problem, but they use enumeration et iterative based techniques. Consequently, they may offer poor scalability at both modelling and analysis stages. On the other hand, variability modelling approaches exploit commonalities between different but related products to efficiently evaluate the whole product line. However, given system specifications, they lack to automatically derive the design space while only specific facets of the problem are evaluated in isolation. We propose a model-driven framework that combines and extends both approaches. It captures requirements and specifications in the form of variable data-flows and configurable hardware platforms, with non-functional constraints and a cost function. An original mapping algorithm then derives and automatically generates the design space in the form of a variability-aware model of computation. This formal model encodes every system designs efficiently. We then propose a novel verification algorithm to pinpoint suitable designs efficiently with respect to functional and non-functional requirements. The benefits of our approach are evaluated through a real-world case study from the automotive industry
32
Courtault, Jean-René. "Logiques de ressources dynamiques : modèles, propriétés et preuves." Thesis, Université de Lorraine, 2015. http://www.theses.fr/2015LORR0033/document.
Full textAbstract:
En informatique, la notion de ressource est une notion centrale. Nous considérons comme ressource toute entité pouvant être composée ou décomposée en sous-entités. Plusieurs logiques ont été proposées afin de modéliser et d’exprimer des propriétés sur celles-ci, comme la logique BI exprimant des propriétés de partage et de séparation. Puisque les systèmes informatiques manipulent des ressources, la proposition de nouveaux modèles capturant la dynamique de ces ressources, ainsi que la vérification et la preuve de propriétés sur ces modèles, sont des enjeux cruciaux. Dans ce contexte, nous définissons de nouvelles logiques permettant la modélisation logique de la dynamique des ressources, proposant de nouveaux modèles et permettant l’expression de nouvelles propriétés sur cette dynamique. De plus, pour ces logiques, nous proposons des méthodes des tableaux et d’extraction de contre-modèles. Dans un premier temps, nous définissons de nouveaux réseaux de Petri, nommés ß-PN, et proposons une nouvelle sémantique à base de ß-PN pour BI. Puis nous proposons une première extension modale de BI, nommée DBI, permettant la modélisation de ressources ayant des propriétés dynamiques, c’est-à-dire évoluant en fonction de l’état courant d’un système. Ensuite, nous proposons une logique, nommée DMBI, modélisant des systèmes manipulant/produisant/consommant des ressources. Par ailleurs, nous proposons une nouvelle logique (LSM) possédant de nouvelles modalités multiplicatives (en lien avec les ressources). Pour finir, nous introduisons la séparation au sein des logiques épistémiques, obtenant ainsi une nouvelle logique ESL, exprimant de nouvelles propriétés épistémiquesIn computer science, the notion of resource is a central concern. We consider as a resource, any entity that can be composed or decomposed into sub-entities. Many logics were proposed to model and express properties on these resources, like BI logic, a logic about sharing and separation of resources. As the computer systems manipulate resources, a crucial issue consists in providing new models that capture the dynamics of resources, and also in verifying and proving properties on these models. In this context, we define new logics with new models and new languages allowing to respectively capture and express new properties on the dynamics of resources. Moreover, for all these logics, we also study the foundations of proof search and provide tableau methods and counter-model extraction methods. After defining new Petri nets, called ß-PN, we propose a new semantics based on ß-PN for BI logic, that allows us to show that BI is able to capture a kind of dynamics of resources. After observing that it is necessary to introduce new modalities in BI logic, we study successively different modal extensions of BI. We define a logic, called DBI, that allows us to model resources having dynamic properties, meaning that they evolve during the iterations of a system. Then, we define a logic, called DMBI, that allows us to model systems that manipulate/produce/consume resources. Moreover, we define a new modal logic, called LSM, having new multiplicative modalities, that deals with resources. Finally, we introduce the notion of separation in Epistemic Logic, obtaining a new logic, called ESL, that models and expresses new properties on agent knowledge
33
Syed, Alwi Syed Hussein. "Vérification compositionnelle pour la conception sûre de systèmes embarqués." Paris 6, 2013. http://www.theses.fr/2013PA066230.
Full textAbstract:
Afin d’améliorer la vérification de systèmes synchrones synthétisables, une méthode de vérification par model-checking basée sur une procédure de raffinement d’abstraction s’appuyant sur la structure en composants du système est proposée. Ayant opté pour la génération d'abstraction à partir des propriétés vérifiées des composants, différentes méthodes de sélection de propriétés pour l'abstraction initiale et les stratégies de raffinement pour améliorer le modèle abstrait sont présentées et analysées. La stratégie la plus directe est la technique de la Négation du Contre-exemple qui raffine le modèle abstrait en éliminant uniquement le contre-exemple fourni par le model-checker. La technique de la sélection de propriété est une autre stratégie où les propriétés disponibles sont organisées en fonction de leur pertinence par rapport à la propriété globale en exploitant les graphes de dépendances de ses variables. De plus, la phase de raffinement est assistée par un mécanisme de filtrage qui assure l’élimination du contre-exemple. Une technique complète basée sur le FSM a également été proposée pour résoudre les principaux problèmes dans l'abstraction dérivée des propriétés, notamment le manque de propriétés exploitables et la génération d’une bonne abstraction. Les techniques proposées ont été testées sur une plate-forme expérimentale d'un protocole industriel, le bus CAN. Les résultats expérimentaux montrent l'applicabilité des techniques proposées, les gains par rapport aux techniques traditionnelles et l’efficacité relative des trois stratégies proposées varient selon le contexte d’utilisationIn the aim of improving the verification of synthesizable synchronous systems, a model-checking method based on the abstraction-refinement procedure which relies on the compositional structure of the system is proposed. Having opted for the abstraction generation from verified component properties, different methods of property selection for the initial abstraction and the refinement strategies to improve the abstract model are presented and analyzed. The most straight-forward strategy is the Negation of the Counterexample Technique which refines the abstract model by eliminating exclusively the spurious counterexample provided by the model checker. The Property Selection Technique is another abstraction-refinement strategy where the available properties are ordered according to their relevance towards the global property by exploiting the dependency graphs of its variables. Furthermore, the refinement phase is assisted by a filtering mechanism that ensures the current counterexample will be eliminated. A comprehensive FSM-based technique has also been proposed to address the main problems in property based abstraction in compositional verification notably the lack of exploitable properties and the generation of a good abstraction. The techniques proposed have been tested on an experimental platform of an industrial protocol, the Controller Area Network (CAN). The experimental results demonstrate the applicability of the techniques proposed, the gains in comparison to conventional techniques and the relative effectiveness of the three strategies proposed varies according to the application context
34
Toussan, Josette. "Un sous-système de recherche géométrique et d'équivalence pour la CAO de circuits intégrés VLSI." Grenoble INPG, 1988. http://tel.archives-ouvertes.fr/tel-00326585/.
Full textAbstract:
Comme la complexité des circuits VLSI croit, la tache de vérification des masques devient de plus en plus longue. L'utilisation des descriptions hiérarchiques permet le développement de méthodes d'analyse hiérarchique plus efficaces. Cette thèse explore une méthode de recherche géométrique par hiérarchie de Quadtrees et l'utilisation hiérarchique de l'algorithme d'équivalence union-find pour la recherche et la mise à jour des équivalences électriques. Des algorithmes hiérarchiques et géométriques utilisables pour l'édition, la vérification géométrique et topologique (connectique) de conceptions VLSI sont présentés. L'intérêt de telles méthodes dans la vérification et le compactage de ces conceptions est aussi aborde. Des quadtrees adaptatifs particuliers (mixed-quadtrees) ont été conçus et testés pour optimiser les outils conventionnels d'extraction et de vérification de la description géométrique des masques de conceptions non structurées et pour permettre une édition rapide de conceptions structurées. Ce document présente les arguments qui ont contribue à la conception d'un tel sous-systeme de recherche géométrique et topologique, le sous-système lui-même et certains algorithmes hiérarchiques. Les méthodes hiérarchiques, géométriques et topologiques ainsi explorées, sont applicables à un grand nombre de taches, comme l'extraction des conceptions, leur vérification, leur édition et leur compactage et sur des descriptions symboliques ou réelles. Ces méthodes permettent l'utilisation interactive d'un certain nombre d'algorithmes d'extraction, de vérification et d'adaptation des conceptions éditées à un ensemble de règles technologiques. Un extracteur et vérificateur géométrique et topologique de conceptions structurées est actuellement réalisé dans le but d'évaluer hiérarchiquement l'efficacité de tels algorithmes. Un aperçu des problèmes qui peuvent être résolus plus rapidement ou dans un mode interactif est également présenté
35
Robbana, Riadh. "Spécification et vérification de systèmes hybrides." Phd thesis, Université Joseph Fourier (Grenoble), 1995. http://tel.archives-ouvertes.fr/tel-00346070.
Full textAbstract:
Les systèmes hybrides sont des systèmes qui combinent des composantes discrètes et des composantes continues. Les composantes continues peuvent représenter un environnement physique obéissant à des règles de changement continu, par contre les composantes discrètes peuvent représenter des contrôleurs discrets qui sondent et manipulent les composantes continues en temps réel. Deux approches peuvent être adoptées pour spécifier ces systèmes, la première étant basée sur des automates (hybrides) et utilise des méthodes d'analyse algorithmiques. La seconde est basée sur les logiques et utilise des preuves formelles comme méthodes d'analyse. Dans une première partie de cette thèse nous considérons l'approche basée sur les automates. Nous étudions la décidabilité du problème de la vérification pour certaines classes de systèmes hybrides linéaires. Nous prenons comme modèles des automates hybrides linéaires avec des structures de données discrètes non bornées. Nous exhibons différents cas de tels systèmes dont le problème de la vérification est décidable. Dans une seconde partie nous considérons l'approche basée sur les logiques et plus particulièrement celle basée sur le «Calcul de Durées». Nous étudions les relations existantes entre cette approche et la précédente ; nous montrons comment cette liaison permet de mettre en évidence un fragment important du «Calcul de Durées» pour lequel le problème de la vérification est décidable
36
Lerman, Benjamin. "Vérification et Spécification des Systèmes Distribués." Phd thesis, Université Paris-Diderot - Paris VII, 2005. http://tel.archives-ouvertes.fr/tel-00322322.
Full textAbstract:
Cette thèse se place dans le cadre de la vérification automatique des systèmes distribués. Elle aborde le problème de la spécification pour de tels systèmes, qui consiste à définir un formalisme logique pour décrire des propriétés des comportements de systèmes. On en attend qu'il soit facile d'exprimer les propriétés courantes (accessibilité, sûreté, exclusion mutuelle, vivacité, etc.). On souhaite par ailleurs que la vérification de ces propriétés soient aisée. Il s'agit donc de trouver un compromis entre pouvoir d'expression et simplicité d'utilisation.On s'intéresse ensuite à la modélisation des systèmes concurrents, en recherchant à nouveau un compromis entre réalisme des modèles et facilité de vérification. Les modèles étudiés dans ce travail sont les automates asynchrones, qui modélisent des processus concurrents communiquant par mémoire partagée.
La thèse s'intéresse enfin au problème de la synthèse de contrôleur. Étant donné un système spécifié de façon incomplète, donc non-déterministe, en interaction avec un environnement, il s'agit de calculer de manière automatique comment restreindre son comportement afin qu'il vérifie une spécification donnée (quelles que soient les actions de l'environnement). Ce problème se formule en
termes de jeux. Dans le cas distribué, les jeux ont naturellement plusieurs joueurs. Dans ce cadre, la plupart des résultats sont négatifs : il est indécidable de savoir si on peut ou non contrôler un tel système. Cette thèse prouve que certaines propriétés de l'architecture de communication garantissent décidabilité pour toute spécification régulière.
37
Lesens, David. "Vérification et synthèse de systèmes réactifs." Phd thesis, Grenoble INPG, 1997. http://tel.archives-ouvertes.fr/tel-00004954.
Full textAbstract:
Cette thèse a pour cadre la vérification des systèmes réactifs de grande taille. Les systèmes réactifs sont des systèmes informatiques qui réagissent continûment à leur environnement physique, à une vitesse déterminée par cet environnement. Ils sont particulièrement utilisés dans le cadre du contrôle des systèmes critiques : transport, nucléaire, commande de processus industriels, communication... De par leur fonction, ils doivent impérativement satisfaire des contraintes strictes de fonctionnement. La vérification des systèmes réactifs de grande taille peut être effectuée en décomposant modulairement le programme. Des algorithmes de synthèse sont proposés, qui permettent de déterminer les sous-programmes les plus généraux, tels que le système complet satisfasse une propriété donnée. La vérification modulaire a été étendue aux cas des réseaux paramétrés de processus. L'utilisation d'observateurs synchrones permet de spécifier des propriétés sur un nombre quelconque de processus. La technique proposée consiste alors à exprimer un invariant de ce réseau à l'aide d'un plus petit ou d'un plus grand point fixe, et d'utiliser des techniques d'extrapolation pour en calculer une approximation régulière. Les cas des réseaux linéaires (ou en anneau) et des réseaux arborescents ont particulièrement été étudiés. L'ensemble des techniques et des algorithmes développés ont été implémentés dans un outil : a Boolean Automaton Network Grammar checker.
38
Dang, Thi Xuan Thao. "Vérification et synthèse des systèmes hybrides." Phd thesis, Grenoble INPG, 2000. http://tel.archives-ouvertes.fr/tel-00006738.
Full textAbstract:
Les systèmes hybrides sont des systèmes qui combinent des dynamiques discrètes et continues. Cette thèse propose des techniques algorithmiques de vérification et de synthèse pour ces systèmes Le manque de méthodes pour calculer les ensembles atteignables des dynamiques continues est l'obstacle principal vers une méthodologie algorithmique de vérification. Nous développons deux techniques d'atteignabilité approximatives pour les systèmes continus basées sur une méthode efficace pour représenter des ensembles et une combinaison des techniques de la simulation, de la géométrie algorithmique, de l'optimisation, et de la commande optimale. La première technique d'atteignabilité est spécialisée pour les systèmes linéaires et étendue aux systèmes avec entrée incertaine, et la seconde peut être appliquée aux systèmes non-linéaires. En appliquant ces techniques nous développons un algorithme de vérification des propriétés de sûreté pour une large classe des systèmes hybrides avec des dynamiques continues arbitraires et des dynamiques discrètes assez générales. Nous étudions ensuite le problème de la synthèse de contrôleurs de sûreté pour les systèmes hybrides. Nous présentons un algorithme de synthèse des contrôleurs par commutation basé sur le calcul de l'ensemble d'invariance maximal et les techniques d'analyse d'atteignabilité. Nous avons implanté les algorithmes développés dans un outil appelé "d/dt", qui permet la vérification et la synthèse automatique pour les systèmes hybrides avec des inclusions différentielles linéaires. En dehors de nombreux exemples académiques, nous avons appliqué avec succès l'outil pour analyser quelques systèmes pratiques.
39
Sangnier, Arnaud. "Vérification de systèmes avec compteurs et pointeurs." Cachan, Ecole normale supérieure, 2008. http://www.theses.fr/2008DENS0051.
Full textAbstract:
Au cours des dernières années, les méthodes formelles se sont avérées être une approche prometteuse pour garantir que le comportement d’un système informatique respecte une spécification donnée. Parmi les différentes techniques développées, le model-checking a été récemment étudié et appliqué avec succès à un grand nombre de modèles comme les systèmes à compteurs, les automates communicants (avec perte), les automates à pile, les automates temporisés, etc. Dans cette thèse, nous considérons deux modèles particuliers dans l’objectif de vérifier des programmes manipulant des variables entières et des variables de pointeurs. Dans une première partie, nous nous intéressons aux systèmes à compteurs. Nous commençons par définir ce modèle ainsi que ses différentes restrictions. Nous introduisons ensuite une sous-classe de systèmes à compteurs, appelée les machines à compteurs reversal-bornées, pour lesquelles de nombreux problèmes d’accessibilité sont décidables. Nous montrons que cette classe peut être étendue tout en gardant les résultats de décidabilité et nous prouvons qu’il est possible de décider si un Système d’Addition de Vecteurs avec États est reversal-borné, alors que cela n’est pas possible si l’on considère les systèmes à compteurs dans leur généralité. Nous finissons cette partie sur les systèmes à compteurs par l’étude de problèmes de model-checking de logiques temporelles. Les logiques temporelles que nous prenons en compte permettent de parler des données manipulées par le système. En particulier, nous montrons que le model-checking d’automates à un compteur déterministes avec des formules de la logique LTL avec registres est décidable, mais que cela n’est plus vrai lorsque l’hypothèse sur le déterminisme est supprimée. Dans une deuxième partie, nous introduisons le modèle des systèmes à pointeurs, qui est utilisé pour représenter des programmes manipulant des listes simplement chaînées. Nous donnons un algorithme qui traduit tout système à pointeurs en un système à compteurs qui lui est bisimilaire. Ceci nous permet de réutiliser les méthodes existantes pour l’analyse de systèmes à compteurs pour vérifier des programmes avec listes. Nous présentons ensuite une extension de la logique CTL* pour vérifier des propriétés temporelles sur de tels programmes, et nous étudions la décidabilité du problème de model-checking pour cette nouvelle logique. Finalement, dans une dernière partie, nous donnons une description de l’outil TOPICS (Translation of Programs Into Counter Systems) qui traduit un programme écrit dans un fragment syntaxique du langage C en un système à compteursIn the past years, formal methods have shown to be a succesfull approach to ensure that the behavior of an informatic system will respect some properties. Among the different existing techniques, model-checking have been recently studied and successfully applied to a lot of models like counter systems, lossy channel systems, pushdown automata, timed automata, etc. In this thesis, we consider two different models to verify programs which manipulate integer variables and pointer variables. In a first part, we deal with counter systems. We define the model and the different restrictions which have been proposed. We then introduce a restricted class of counter systems, called the reversal-bounded counter machines, for which many reachability problems are decidable. We show that this class can be extended keeping the decidability results and we prove that we can decide whether a Vector Addition System with States is reversal-bounded or not, which is not possible for general counter systems. We then study the problem of model-checking counter systems with different temporal logics. The temporal logics we consider allow to speak about the data manipulated by the system. In particular, we show that the model-checking of deterministic one-counter automata with formulae of LTL with registers is decidable, and becomes undecidable when considering non deterministic one-counter automata and two counter automata. In a second part, we introduce the model of pointer systems, which is used to represent programs manipulating single linked lists. We propose an algorithm to translate any pointer system into a bisimilar counter system. This allows us to reuse existing techniques over counter systems to analyze these programs. We then propose an extension of CTL* to verify temporal properties for such programs, and we study the decidability of the model-checking problem for this new logic. Finally we present the tool TOPICS (Translation of Programs Into Counter Systems) which translates a C-like program with pointers and integer variables into a counter system
40
Nguyen, Thanh-Hung. "Vérification Constructive des Systèmes à base de Composants." Phd thesis, Grenoble, 2010. http://tel.archives-ouvertes.fr/tel-00485933.
Full textAbstract:
L'objectif de la thèse est de développer des méthodologies et des outils pour la vérification compositionnelle et incrémentale des systèmes à base de composants. Nous proposons une méthode compositionnelle pour vérifier des propriétés de sûreté. La méthode est basée sur l'utilisation des deux types d'invariants: invariants de composant qui expriment des aspects locaux des systèmes et invariants d'interaction qui caractérisent les contraintes globales induites par les synchronisations fortes entre les composants. Nous offrons des techniques efficaces pour calculer ces invariants. Nous proposons également une nouvelle méthode de vérification incrémentale qui prend la conception incrémentale du système en compte. L'intégration de la vérification dans le processus de conception permet de déceler une erreur dès qu'elle apparaît. En outre, cette méthode permet d'éviter de refaire tous les processus de vérification par la réutilisation de résultats intermédiaires. Elle prend des avantages des structures de systèmes pour faire face à la complexité de la vérification globale et, par conséquent, réduit significativement le coût de la vérification en temps et en mémoire utilisée. Les méthodes compositionnelles et incrémentales ont été mises en oeuvre dans la chaîne d'outil D-Finder. Les résultats expérimentaux obtenus sur plusieurs études de cas non triviales montrent l'efficacité de nos méthodes ainsi que les capacités de D-Finder.
41
Arfaoui, Heger. "Décision et vérification distribuées locales." Paris 7, 2014. http://www.theses.fr/2014PA077042.
Full textAbstract:
Cette thèse s'inscrit dans le contexte du calcul distribué sur les réseaux, et, plus particulièrement, sur les aspects de localité qui apparaissent dans ce cadre. Par l'étude systématique des problèmes de décision, nous introduisons les classes de com¬plexité ULD et UNLD pour la décision et la vérification locale, et présentons des résultats de séparation décrivant une hiérarchie impliquant d'autres classes relatives à la littérature de la décision locale. Ces résultats sont accompagnés de la classifica¬tion de plusieurs problèmes distribués selon la hiérarchie introduite. Nous examinons et discutons dans ce cadre deux ingrédients ayant un rôle clé dans la décision et la vérification locale : la fonction d'interprétation des sorties, et l'identification des noeuds du réseau. Nous isolons également dans cette thèse l'aspect de la localité en l'étudiant sous le prisme du modèle "non-signalling", qui bien que n'étant pas un modèle réaliste, offre des possibilités théoriques intéressantes, notamment sur la dérivation de bornes inférieures pour le calcul distribué quantique, sans avoir à manipuler les objets de cette théorie. Finalement, en nous plaçant à la limite extrême des contraintes de localité, nous considérons la classe particulière de jeux à deux joueurs en l'absence de communication, et examinons les limites du calcul distribué quantique pour cette classe de jeuxThis thesis lays in the context of distributed computing on networks, and more par-ticularly on the locality aspects that appear in that context. By the systematic study of decision problems, we introduce the complexity classes ULD and UNLD for local decision and verification respectively, and give separation results describing a hier¬archy involving other classes of local decision in the literature. These results are accompanied by a classification of several distributed problems based on the hierar¬chy we introduce. We examine and discuss two key ingredients in local decision and verification: the interpretation function on the outputs, and node identification. In this thesis, we also isolate the aspect of locality by studying it through the prism of the non-signaling model, which, even though not realistic, offers interest¬ing theoretical possibilities, including the derivation of lower bounds for distributed quantum computing without having to manipulate objects of that theory. Finally, by placing ourselves at the extreme limit of locality constraints, we consider the par¬ticular class of two-player games in absence of any communication and examine the limits of quantum distributed computing for this class of games
42
Quinton, Sophie. "Design, vérification et implémentation de systèmes à composants." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00685854.
Full textAbstract:
Nous avons étudié dans le cadre de cette thèse le design, la vérification et l'implémentation des systèmes à composants. Nous nous sommes intéressés en particulier aux formalismes exprimant des interactions complexes, dans lesquels les connecteurs servent non seulement au transfert de données mais également à la synchronisation entre composants. 1. DESIGN ET VÉRIFICATION Le design par contrat est une approche largement répandue pour développer des systèmes lorsque plusieurs équipes travaillent en parallèle. Les contrats représentent des contraintes sur les implémentations qui sont préservées tout au long du développement et du cycle de vie d'un système. Ils peuvent donc servir également à la phase de vérification d'un tel système. Notre but n'est pas de proposer un nouveau formalisme de spécification, mais plutôt de définir un ensemble minimal de propriétés qu'une théorie basée sur les contrats doit satisfaire pour permettre certains raisonnements. En cela, nous cherchons à séparer explicitement les propriétés spécifiques à chaque formalisme de spécification et les règles de preuves génériques. Nous nous sommes attachés à fournir des définitions suffisamment générales pour exprimer un large panel de langages de spécification, et plus particulièrement ceux dans lesquels les interactions sont complexes, tels que Reo ou BIP. Pour ces derniers, raisonner sur la structure du système est essentiel et c'est pour cette raison que nos contrats ont une partie structurelle. Nous montrons comment découle de la propriété nommée raisonnement circulaire une règle pour prouver la dominance sans composer les contrats, et comment cette propriété peut être affaiblie en utilisant plusieurs relations de raffinement. Notre travail a été motivé par les langages de composants HRC L0 et L1 définis dans le projet SPEEDS. 2. IMPLÉMENTATION Synthétiser un contrôleur distribué imposant une contrainte globale sur un système est dans le cas général un problème indécidable. On peut obtenir la décidabilité en réduisant la concurrence: nous proposons une méthode qui synchronise les processus de façon temporaire. Dans les travaux de Basu et al., le contrôle distribué est obtenu en pré-calculant par model checking la connaissance de chaque processus, qui reflète dans un état local donné toutes les configurations possibles des autres processus. Ensuite, à l'exécution, le contrôleur local d'un processus décide si une action peut être exécutée sans violer la contrainte globale. Nous utilisons de même des techniques de model checking pour pré-calculer un ensemble minimal de points de synchronisation au niveau desquels plusieurs processus partagent leur connaissance au court de brèves périodes de coordination. Après chaque synchronisation, les processus impliqués peuvent de nouveau progresser indépendamment les uns des autres jusqu'à ce qu'une autre synchronisation ait lieu. Une des motivations pour ce travail est l'implémentation distribuée de systèmes BIP.
43
Larnac, Mireille. "Gestion de la Condition de Chemin dans la simulation symbolique." Phd thesis, Montpellier 2, 1992. http://tel.archives-ouvertes.fr/tel-00866197.
Full textAbstract:
Le traitement des branchements conditionnels est un problème spécifique à la simulation symbolique. La gestion de la Condition de Chemin consiste à déterminer si la valeur de vérité d'une condition est contenue dans tous les choix qui ont été opérés sur les tests précédemment rencontrés, ou si, au contraire, le choix de cette valeur est laissé à la libre appréciation de l'utilisateur : c'est le rôle de l'opérateur de choix. Cet opérateur et les propriétés qui le caractérisent sont définis. Son application sur des expressions particulières, puis dans le cas général est ensuite étudiée.
44
Barros, Tomás. "Spécification et vérification formelles des systèmes de composants répartis." Phd thesis, Université de Nice Sophia-Antipolis, 2005. http://tel.archives-ouvertes.fr/tel-00090718.
Full textAbstract:
Un composant est une entité autonome qui interagit avec son environnement par des interfaces correctement spécifiées. Fractive est une implantation du modèle de composants Fractal qui propose des primitives de haut niveau et une sémantique pour la programmation à base de composants Java distribués, asynchrones et hiérarchiques. Fractive propose également une séparation entre aspects fonctionnels et non-fonctionnels, ces derniers permettant un contrôle de l´exécution d´un composant et de son évolution dynamique. Dans cette thèse, nous proposons un outillage formel pour la vérification d´applications construites avec Fractive. Cela permet de vérifier que chaque composant remplit correctement le rôle qui lui a été assigné au sein du système, et que la mise à jour ou le remplacement d´un composant n´engendre pas d´interblocage ou de panne du système. Nous avons défini un nouveau format intermédiaire qui étend les réseaux d´automates communicants, en paramétrisant leurs événements de communication et de traitement. Nous avons ensuite utilisé ce format intermédiaire pour définir les spécifications comportementales d´applications Fractive. Nous considérons que les modèles des composants primitifs sont connus (donnés par l´utilisateur ou par analyse statique). En utilisant la description des composants, nous construisons un contrôleur décrivant le comportement non fonctionnel du composant. La sémantique d´un composant est ensuite générée comme le produit de synchronisation des LTSs de ses sous-composants et du contrôleur. Le système résultant peut être vérifié par rapport aux besoins exprimés dans un ensemble de formules de logique temporelle, comme illustré dans le manuscrit.
45
Servières, Corinne. "Modélisation et vérification orientées objet pour les systèmes réactifs." Toulouse, INPT, 1995. http://www.theses.fr/1995INPT069H.
Full textAbstract:
Apres une etude prealable des systemes reactifs, et de l'approche orientee objet qui s'avere adaptee au developpement de tels systemes, un langage oriente objet concurrent est propose pour modeliser les systemes reactifs. La caracteristique essentielle de ce langage est de favoriser la reutilisation: d'une part en permettant aux parties controle de la synchronisation et traitement de chaque action d'un objet d'etre heritees separement ; d'autre part, en autorisant la description separee du controle de la synchronisation, dans une classe specifique appelee classe de synchronisation. Les principaux aspects de ce langage sont formalises avec la logique temporelle des actions definie par l. Lamport. Pour augmenter, dans les phases de specification et de verification formelles, les possibilites de reutilisation induites par la relation d'heritage ou la composition parallele d'objets, une formalisation qui dissocie trois niveaux de raisonnement est presentee. Le niveau action permet de raisonner sur les actions, et utilise une logique inspiree de la logique de hoare. Le niveau local autorise le raisonnement sur le comportement d'un objet considere isolement. Et enfin, le niveau systeme s'interesse aux systemes d'objets. Ces deux derniers niveaux sont bases sur deux variantes de la logique temporelle lineaire. Une etude montre quelles sont les proprietes qui demontrees pour une classe parente sont heritees ou peuvent etre reutilisees pour demontrer celles d'une classe fille. La reutilisation induite par la relation d'heritage est egalement envisagee dans une procedure de decision, basee sur une methode des tableaux
46
Bouyer-Decitre, Patricia. "Modèles et algorithmes pour la vérification des systèmes temporisés." Cachan, Ecole normale supérieure, 2002. http://www.theses.fr/2002DENS0008.
Full text
47
Atig, Mohamed Faouzi. "Vérification de Programmes Concurrents : Décidabilité et Complexité." Paris 7, 2010. http://www.theses.fr/2010PA077066.
Full textAbstract:
Cette thèse porte sur la vérification des programmes concurrents, en nous intéressant en particulier à l'étude la décidabilité et la complexité des problèmes d'accessibilité. Dans la plus grande partie de cette thèse, nous considérons des programmes concurrents où les processus séquentiels correspondent à des threads pouvant faire des appels de procédures (potentiellement récursives). La difficulté vient de l'interaction entre la récursivité et de la concurrence qui rend le problème de l'accessibilité indécidable en général. Nous étudions alors les conditions sous lesquelles ce problème devient décidable. Ces conditions peuvent être vues comme des contraintes à poser sur l'ordonnancement des actions le long des exécutions du programme analysé. Ainsi, les résultats de décidabilité peuvent être utilisés pour définir des procédures d'analyse sous-approchée permettant de détecter de manière efficace des comportements illicites des programmes. Dans un second temps, nous nous intéressons aux programmes s'exécutant selon un modèle faible de la mémoire partagée (weak memory model). Dans de tels programmes, l'ordre entre les actions d'un même processus est relâché pour des besoins de performance en permettant la permutation entre certains types d'actions. Cela rend alors le conception des programmes concurrents encore plus difficile du fait que la sémantique de la concurrence devient hautement complexe et contre-intuitive. Nos travaux montrent qu'en effet selon le type des relaxations d'ordre entre actions, le problème de l'accessibilité peut être décidable mais hautement complexe dans certains cas, et il peut même être indécidable dans d'autresThis thesis addresses the verification problems in both, concurrent and recursive Systems as well as concurrent Systems with store buffers. We establish the required theoretical basis for automated analyses: decidability and complexity results for reachability problems. In a first time, we are interested in verifying concurrent programs where each process corresponds to a sequential program with (recursive) procedure calls. The difficulty in analyzing such programs cornes from the interaction between recursion and concurrency which makes the reachability problems undecidable in general. However, in practice programs obey additional constraints that can be exploited to turn the reachability problem decidable. Their study is subject of this thesis. These conditions may be seen as constraints to impose on the order between the actions of the analyzed programs. Moreover, these decidability results can be used to perform an under-approximation analysis to effectively detect bad behaviors of the analyzed programs. In a second time, we study concurrent programs running under weak memory models. In such kind of programs, the order between actions of the same process is relaxed (for performance reasons) by allowing the permutation between certain types of memory operations. This makes reasoning about the behaviors of concurrent programs much more difficult. Moreover, it is not clear how to apply standard reasoning techniques. Our works show that indeed according to the type of relaxation, the reachability problem becomes décidable (but with a highly complexity) in other cases, it even turns out undecidability
48
Amouroux, Guillaume. "Etude de l'analyse automatique des règles de conception des systèmes multitâches temps réel." Paris 11, 2008. http://www.theses.fr/2008PA112053.
Full textAbstract:
Les travaux présentés dans cette thèse ont pour objectif de proposer une méthode permettant l’analyse de l’application de règles de conception à partir du code source d’une application. Les règles de conception permettent de garantir des propriétés intéressantes sur le programme final. Aussi, vérifier leur application permet-il de garantir la présence de ces propriétés. Au contraire, si la règle ne se trouve pas appliquée dans le programme final, alors il n’est pas possible d’émettre un avis quant à la qualité du code source, mais le fait que le développeur ait ignoré la règle est significatif. Les vérifications s’intéressent particulièrement aux problèmes liés aux systèmes multitâches. L’introduction d’un ordonnancement non-déterministe entre les tâches rend les analyses par les méthodes classiques de preuve de programme peu ou pas efficaces. C’est pourquoi une technique de décomposition de programme est proposée, ainsi que des méthodes de vérification à plusieurs niveaux. La technique développée se base sur l’étude du code source seul. Les analyses doivent n’être possibles qu’à partir de cet élément, en l’absence de tout autre élément de conceptionThe works presented in this thesis propose a novel method to verify the application of design rules based on the analysis of the source code. Design rules allow to guarantee the presence of sound properties on the final program. Therefore, verifying their presence allows to guarantee the presence of the associated properties. On the opposite, if a particular rule is not found to be applied upon the final program, no judgment may be given regarding the quality of the source code, but the fact that the developer didn’t follow the rule is significant in itself. The verifications are particularly aimed towards the problems specific to multitask systems. The introduction of a dynamic non-deterministic scheduling between the tasks renders the analyses by classical proof of programs inefficient or even useless. This led us to propose a new program analysis technique, based on multiple levels analysis and program slicing. The technique proposed is based on the study of the source code only. The analyses must be performed on this element only, if no other element regarding the system’s design is available
49
Yovine, Sergio. "Méthodes et outils pour la vérification symbolique de systèmes temporisés." Phd thesis, Grenoble INPG, 1993. http://tel.archives-ouvertes.fr/tel-00127808.
Full textAbstract:
Ce travail propose une méthode pour l'analyse de systèmes temps-reél. Cette méthode est basée sur la compilation des spécifications
vers des graphes temporisés, à partir desquels il est possible
de vérifier des propriétés et de générer du code exécutable.
Les graphes temporisés sont des automates étendus avec des
variables, appelées horloges, qui permettent de décrire les
contraintes temporelles.
Un algorithme de compilation est développé pour l'algèbre
de processus temporisés ATP, qui est une extension des
algèbres de processus avec des opérateurs temporels comme
le ``timeout'' et le ``watchdog''. L'intérêt de l'algorithme est
que la taille du graphe obtenu est indépendante des valeurs
des paramètres des opérateurs temporels.
Les propriétés temps-reél sur les graphes temporisés sont
décrites par des formules de la logique TCTL.
Il est montré que les opérateurs temporels
de TCTL s'expriment en termes de points fixes à l'aide d'un
opérateur ``d'état suivant'' défini de façon appropriée.
De plus, ce travail propose un algorithme de vérification qui
consiste à évaluer symboliquement l'ensemble caractéristique
d'une formule comme une disjonction de contraintes linéaires
sur les horloges.
Les algorithmes de compilation et de vérification développés
ont été implémentés dans l'outil KRONOS,
utilisé pour analyser des applications temps-reél
significatives. Les résultats obtenus confirment l'intérêt
pratique de l'approche proposée.
50
Rosa, Cristian. "Vérification des performances et de la correction des systèmes distribués." Thesis, Nancy 1, 2011. http://www.theses.fr/2011NAN10113/document.
Full textAbstract:
Les systèmes distribués sont au coeur des technologies de l'information.Il est devenu classique de s'appuyer sur multiples unités distribuées pour améliorer la performance d'une application, la tolérance aux pannes, ou pour traiter problèmes dépassant les capacités d'une seule unité de traitement. La conception d'algorithmes adaptés au contexte distribué est particulièrement difficile en raison de l'asynchronisme et du non-déterminisme qui caractérisent ces systèmes. La simulation offre la possibilité d'étudier les performances des applications distribuées sans la complexité et le coût des plates-formes d'exécution réelles. Par ailleurs, le model checking permet d'évaluer la correction de ces systèmes de manière entièrement automatique. Dans cette thèse, nous explorons l'idée d'intégrer au sein d'un même outil un model checker et un simulateur de systèmes distribués. Nous souhaitons ainsi pouvoir évaluer la performance et la correction des applications distribuées. Pour faire face au problème de l'explosion combinatoire des états, nous présentons un algorithme de réduction dynamique par ordre partiel (DPOR), qui effectue une exploration basée sur un ensemble réduit de primitives de réseau. Cette approche permet de vérifier les programmes écrits avec n'importe laquelle des interfaces de communication proposées par le simulateur. Nous avons pour cela développé une spécification formelle complète de la sémantique de ces primitives réseau qui permet de raisonner sur l'indépendance des actions de communication nécessaire à la DPOR. Nous montrons au travers de résultats expérimentaux que notre approche est capable de traiter des programmes C non triviaux et non modifiés, écrits pour le simulateur SimGrid. Par ailleurs, nous proposons une solution au problème du passage à l'échelle des simulations limitées pour le CPU, ce qui permet d'envisager la simulation d'applications pair-à-pair comportant plusieurs millions de noeuds. Contrairement aux approches classiques de parallélisation, nous proposons une parallélisation des étapes internes de la simulation, tout en gardant l'ensemble du processus séquentiel. Nous présentons une analyse de la complexité de l'algorithme de simulation parallèle, et nous la comparons à l'algorithme classique séquentiel pour obtenir un critère qui caractérise les situations où un gain de performances peut être attendu avec notre approche. Un résultat important est l'observation de la relation entre la précision numérique des modèles utilisés pour simuler les ressources matérielles, avec le degré potentiel de parallélisation atteignables avec cette approche. Nous présentons plusieurs cas d'étude bénéficiant de la simulation parallèle, et nous détaillons les résultats d'une simulation à une échelle sans précédent du protocole pair-à-pair Chord avec deux millions de noeuds, exécutée sur une seule machine avec un modèle précis du réseauDistributed systems are in the mainstream of information technology. It has become standard to rely on multiple distributed units to improve the performance of the application, help tolerate component failures, or handle problems too large to fit in a single processing unit. The design of algorithms adapted to the distributed context is particularly difficult due to the asynchrony and the nondeterminism that characterize distributed systems. Simulation offers the ability to study the performance of distributed applications without the complexity and cost of the real execution platforms. On the other hand, model checking allows to assess the correctness of such systems in a fully automatic manner. In this thesis, we explore the idea of integrating a model checker with a simulator for distributed systems in a single framework to gain performance and correctness assessment capabilities. To deal with the state explosion problem, we present a dynamic partial order reduction algorithm that performs the exploration based on a reduced set of networking primitives, that allows to verify programs written for any of the communication APIs offered by the simulator. This is only possible after the development of a full formal specification with the semantics of these networking primitives, that allows to reason about the independency of the communication actions as required by the DPOR algorithm. We show through experimental results that our approach is capable of dealing with non trivial unmodified C programs written for the SimGrid simulator. Moreover, we propose a solution to the problem of scalability for CPU bound simulations, envisioning the simulation of Peer-to-Peer applications with millions of participating nodes. Contrary to classical parallelization approaches, we propose parallelizing some internal steps of the simulation, while keeping the whole process sequential. We present a complexity analysis of the simulation algorithm, and we compare it to the classical sequential algorithm to obtain a criteria that describes in what situations a speed up can be expected. An important result is the observation of the relation between the precision of the models used to simulate the hardware resources, and the potential degree of parallelization attainable with this approach. We present several case studies that benefit from the parallel simulation, and we show the results of a simulation at unprecedented scale of the Chord Peer-to-Peer protocol with two millions nodes executed in a single machine