Automating Verification of State Machines with Reactive Designs and Isabelle/UTP

TY - GEN

T1 - Automating Verification of State Machines with Reactive Designs and Isabelle/UTP

AU - Foster, Simon David

AU - Baxter, James Edward

AU - Cavalcanti, Ana Lucia Caneca

AU - Miyazawa, Alvaro Heiji

AU - Woodcock, JAMES Charles Paul

N1 - © This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details

PY - 2018/10/5

Y1 - 2018/10/5

N2 - State-machine based notations are ubiquitous in the description of component systems, particularly in the robotic domain. To ensure these systems are safe and predictable, formal verification techniques are important, and can be cost-effective if they are both automated and scalable. In this paper, we present a verification approach for a diagrammatic state machine language that utilises theorem proving and a denotational semantics based on Unifying Theories of Programming (UTP). We provide the necessary theory to underpin state machines (including induction theorems for iterative processes), mechanise an action language for states and transitions, and use these to formalise the semantics. We then describe the verification approach, which supports infinite state systems, and exemplify it with a fully automated deadlock-freedom check. The work has been mechanised in our proof tool, Isabelle/UTP, and so also illustrates the use of UTP to build practical verification tools.

AB - State-machine based notations are ubiquitous in the description of component systems, particularly in the robotic domain. To ensure these systems are safe and predictable, formal verification techniques are important, and can be cost-effective if they are both automated and scalable. In this paper, we present a verification approach for a diagrammatic state machine language that utilises theorem proving and a denotational semantics based on Unifying Theories of Programming (UTP). We provide the necessary theory to underpin state machines (including induction theorems for iterative processes), mechanise an action language for states and transitions, and use these to formalise the semantics. We then describe the verification approach, which supports infinite state systems, and exemplify it with a fully automated deadlock-freedom check. The work has been mechanised in our proof tool, Isabelle/UTP, and so also illustrates the use of UTP to build practical verification tools.

KW - cs.LO

U2 - 10.1007/978-3-030-02146-7_7

DO - 10.1007/978-3-030-02146-7_7

M3 - Conference contribution

SN - 9783030021450

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 137

EP - 155

BT - 15th International Conference on Formal Aspects of Component Software

A2 - Ölveczky, Peter Csaba

A2 - Bae, Kyungmin

PB - Springer

ER -