Back to search

Aristotle University Of Thessaloniki (AUTH)

Επιδιόρθωση συστημάτων μεταβάσεων μέσω αφαίρεσης

Abstract

dc:description

Given 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 × 10

Rights

dc:rights
Statement dc:rights
  • BY_NC_ND
Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/43734

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chatzieleftheriou, Georgios; Χατζηελευθερίου, Γεώργιος. Επιδιόρθωση συστημάτων μεταβάσεων μέσω αφαίρεσης. Aristotle University Of Thessaloniki (AUTH), 2018. http://hdl.handle.net/10442/hedi/43734