A Game-Theoretic Foundation for the Maximum Software Resilience against Dense Errors

Huang, C-H, Peled, DA, Schewe, S ORCID: 0000-0002-9093-9518 and Wang, F (2016) A Game-Theoretic Foundation for the Maximum Software Resilience against Dense Errors. IEEE Transactions on Software Engineering, 42 (7). pp. 605-622.

Text
ppTSE2016.pdf - Author Accepted Manuscript
Download (481kB)

Official URL: https://ieeexplore.ieee.org/document/7360234

Abstract

Safety-critical systems need to maintain their functionality in the presence of multiple errors caused by component failures or disastrous environment events. We propose a game-theoretic foundation for synthesizing control strategies that maximize the resilience of a software system in defense against a realistic error model. The new control objective of such a game is called $k$ -resilience. In order to be $k$ -resilient, a system needs to rapidly recover from infinitely many waves of a small number of up to $k$ close errors provided that the blocks of up to $k$ errors are separated by short time intervals, which can be used by the system to recover. We first argue why we believe this to be the right level of abstraction for safety critical systems when local faults are few and far between. We then show how the analysis of $k$ -resilience problems can be formulated as a model-checking problem of a mild extension to the alternating-time $\mu$ -calculus (AMC). The witness for $k$ resilience, which can be provided by the model checker, can be used for providing control strategies that are optimal with respect to resilience. We show that the computational complexity of constructing such optimal control strategies is low and demonstrate the feasibility of our approach through an implementation and experimental results.

Item Type:	Article
Uncontrolled Keywords:	Resilience, Games, Software systems, Safety, Game theory, Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	23 Sep 2016 11:17
Last Modified:	19 Jan 2023 07:30
DOI:	10.1109/TSE.2015.2510001
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3003308