221 |
Contribution à la modélisation et à la vérification de processus workflowSbaï, Zohra 13 November 2010 (has links) (PDF)
La technologie de workflow, tendant à automatiser les processus d'entreprise et à fournir un support pour leur gestion, est aujourd'hui un secteur actif de recherche. C'est dans ce contexte que se situent ces travaux de thèse qui portent aussi bien sur la modélisation des processus workflow que sur leur vérification. Ces processus, pouvant être contraints par des ressources partagées ou encore par des durées de traitement, doivent être vérifiés avant d'être confiés aux systèmes de gestion de workflow qui vont les exécuter. Nous nous sommes intéressés par la vérification de la propriété de cohérence (soundness) des réseaux de workflow (WF-net) : sous-classes des réseaux de Petri (RdPs) modélisant les processus workflow.Dans ce cadre, en explorant la théorie structurelle des RdPs, nous avons identifié des sous-classes de WF-nets pour lesquelles la cohérence peut être vérifiée et caractérisée efficacement. Nous nous sommes focalisés en outre sur l'extension de ces sous-classes en tenant compte de la présence de ressources partagées et sur la propriété de cohérence en présence d'un nombre arbitraire d'instances prêtes à s'exécuter. Dans cette partie, nous avons dû automatiser le calcul des siphons minimaux dans un RdP. Pour ce faire, nous avons choisi un algorithme de la littérature et l'amélioré par la recherche et la contraction de circuits alternés.Ensuite, nous avons abordé la modélisation et la vérification de processus workflow tenant compte des contraintes temporelles. Nous avons en premier lieu proposé un modèle de TWF-net (WF-net Temporisé). Pour ce modèle, nous avons défini la propriété de cohérence temporelle et proposé une condition nécessaire et suffisante pour la vérifier. En deuxième lieu, nous avons relaxé les contraintes temporelles adoptées par la proposition d'un modèle temporel visant des processus à contraintes temporelles variant dans des intervalles de temps. Nous avons défini formellement le modèle de ITWF-net (Interval Timed WF-net) et donné sa sémantique. Par ailleurs, nous avons développé et testé un prototype de modélisation et de simulation des ITWF-nets.La dernière partie de cette thèse a concerné la vérification formelle des processus workflow par SPIN model checker. Nous avons dû en premier lieu traduire la spécification des workflows adoptée vers Promela : le langage de description des modèles à vérifier par SPIN. En second lieu, nous avons exprimé les propriétés de cohérence en Logique Linéaire Temporelle (LTL) et utilisé SPIN pour tester si chaque propriété est satisfaite par le modèle Promela du WF-net en question. Enfin, nous avons exprimé les propriétés de k-cohérence pour les WF-nets modélisant plusieurs instances et de (k,R)-cohérence pour les processus workflow concurrents et qui possèdent des ressources partagées.
|
222 |
Évaluation de la Performance et de la Correction de Systèmes DistribuésRosa, Cristian 24 October 2011 (has links) (PDF)
Les systèmes distribués sont au cœur 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 nœuds. 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 nœuds, exécutée sur une seule machine avec un modèle précis du réseau.
|
223 |
Verification of Security Properties Using Formal TechniquesAl-Shadly, Saleh 09 April 2013 (has links)
No description available.
|
224 |
Detection of Feature Interactions in Automotive Active Safety FeaturesJuarez Dominguez, Alma L. January 2012 (has links)
With the introduction of software into cars, many
functions are now realized with reduced cost,
weight and energy. The development of these software
systems is done in a distributed manner independently
by suppliers, following the traditional approach of
the automotive industry, while the car maker takes
care of the integration. However, the integration can
lead to unexpected and unintended interactions among
software systems, a phenomena regarded as feature
interaction. This dissertation addresses the problem
of the automatic detection of feature interactions
for automotive active safety features.
Active safety features control the vehicle's motion
control systems independently from the driver's request,
with the intention of increasing passengers' safety
(e.g., by applying hard braking in the case of an
identified imminent collision), but their unintended
interactions could instead endanger the passengers
(e.g., simultaneous throttle increase and sharp narrow
steering, causing the vehicle to roll over).
My method decomposes the problem into three parts:
(I) creation of a definition of feature interactions
based on the set of actuators and domain expert knowledge;
(II) translation of automotive active safety features
designed using a subset of Matlab's Stateflow into the
input language of the model checker SMV;
(III) analysis using model checking at design time to
detect a representation of all feature interactions
based on partitioning the counterexamples into
equivalence classes.
The key novel characteristic of my work is exploiting
domain-specific information about the feature interaction
problem and the structure of the model to produce a
method that finds a representation of all different
feature interactions for automotive active safety
features at design time.
My method is validated by a case study with the set
of non-proprietary automotive feature design models
I created. The method generates a set of counterexamples
that represent the whole set of feature interactions in
the case study.By showing only a set of representative
feature interaction cases, the information is concise
and useful for feature designers. Moreover, by generating
these results from feature models designed in Matlab's
Stateflow translated into SMV models, the feature
designers can trace the counterexamples generated by SMV
and understand the results in terms of the Stateflow
model. I believe that my results and techniques will
have relevance to the solution of the feature
interaction problem in other cyber-physical systems,
and have a direct impact in assessing the safety of
automotive systems.
|
225 |
Development Of A Library For Automated Verification Of Uml ModelsCelik, Makbule Filiz 01 April 2006 (has links) (PDF)
Software designs are mostly modeled as Unified Modeling Language (UML) diagrams when object oriented software development is concerned. Some popular topics in the industry such as Model Driven Development, generating test cases automatically in the early phases of software development, automated generation of code from design model etc. use the benefits of UML designs. All of these topics have something in common which is the need for accuracy against the meta-model not to face problems in the latter phases of the development process. Support on the full checking of the design models is necessary for the detection of design inconsistencies.
This thesis presents an approach for automated verification of UML design models and explains the implementation of the library called UMLChecker.
|
226 |
Model checking compositional Markov systemsJohr, Sven January 2007 (has links)
Zugl.: Saarbrücken, Univ., Diss., 2007
|
227 |
Software verification for programmable logic controllersHuuck, Ralf. Unknown Date (has links) (PDF)
University, Diss., 2003--Kiel.
|
228 |
Abstraction-based verification of parameterized networksBaukus, Kai. Unknown Date (has links) (PDF)
University, Diss., 2003--Kiel.
|
229 |
Exploring the limits of parameterized system verificationStahl, Karsten. Unknown Date (has links) (PDF)
University, Diss., 2003--Kiel.
|
230 |
Safety-aware apprenticeship learningZhou, Weichao 03 July 2018 (has links)
It is well acknowledged in the AI community that finding a good reward function for reinforcement learning is extremely challenging. Apprenticeship learning (AL) is a class of “learning from demonstration” techniques where the reward function of a Markov Decision Process (MDP) is unknown to the learning agent and the agent uses inverse reinforcement learning (IRL) methods to recover expert policy from a set of expert demonstrations. However, as the agent learns exclusively from observations, given a constraint on the probability of the agent running into unwanted situations, there is no verification, nor guarantee, for the learnt policy on the satisfaction of the restriction. In this dissertation, we study the problem of how to guide AL to learn a policy that is inherently safe while still meeting its learning objective. By combining formal methods with imitation learning, a Counterexample-Guided Apprenticeship Learning algorithm is proposed. We consider a setting where the unknown reward function is assumed to be a linear combination of a set of state features, and the safety property is specified in Probabilistic Computation Tree Logic (PCTL). By embedding probabilistic model checking inside AL, we propose a novel counterexample-guided approach that can ensure both safety and performance of the learnt policy. This algorithm guarantees that given some formal safety specification defined by probabilistic temporal logic, the learnt policy shall satisfy this specification. We demonstrate the effectiveness of our approach on several challenging AL scenarios where safety is essential.
|
Page generated in 0.1108 seconds