Aristotle University Of Thessaloniki (AUTH)
Επιδιόρθωση συστημάτων μεταβάσεων μέσω αφαίρεσης
Abstract
dc:descriptionGiven a transition system M and a specification formula f, the problem of model checking is to determine if M satisfies f. An extended problem of model checking is that of model repair. In the case that M violates f, the problem of model repair is to obtain a new model M΄, such that M΄ satisfies f. Moreover, the changes made to M to derive M΄ should be minimum with respect to all such M΄. As in model checking, state explosion can make it virtually impossible to carry out model repair on models with infinite or even large state spaces. This thesis examines the problem of model repair for (i) Kripke structures and Computation Tree Logic and, (ii) probabilistic systems and reachability temporal logic properties. For Kripke structures, this thesis presents a framework for model repair that uses abstraction refinement to tackle state space explosion. The proposed framework aims to repair Kripke Structure models based on a Kripke Modal Transition System abstraction and a 3-valued semantics for CTL. An abstract-model-repair algorithm is introduced for which soundness and semi-completeness are proven, and its complexity class is studied. Moreover, a prototype implementation is presented to illustrate the practical utility of abstract model repair on an Automatic Door Opener system model and a model of the Andrew File System 1 protocol. For probabilistic systems, this thesis presents a framework based on abstraction and re#nement, which reduces the state space of the probabilistic system to repair at the price of obtaining an approximate solution. A metric space is defined over the set of DTMCs, in order to measure the differences between the initial and the repaired models. For the repair, this thesis introduces an algorithm and discusses its important properties, such as soundness and complexity. As a proof of concept, experimental results are provided for probabilistic systems with diverse structures of state spaces, including thewell-known Craps game, the IPv4 Zeroconf protocol, a message authentication protocol and the gambler's ruin model.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Chatzieleftheriou, Georgios
- Χατζηελευθερίου, Γεώργιος
Subjects
dc:subject × 10Rights
dc:rights- Statement dc:rights
-
- BY_NC_ND
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/43734