Lecture Notes in Computer Science, 2009, Volume 5885/2009, 246-265, DOI: 10.1007/978-3-642-10373-5_13

European Train Control System: A Case Study in Formal Verification

André Platzer and Jan-David Quesel

View Related Documents

Abstract

Complex physical systems have several degrees of freedom. They only work correctly when their control parameters obey corresponding constraints. Based on the informal specification of the European Train Control System (ETCS), we design a controller for its cooperation protocol. For its free parameters, we successively identify constraints that are required to ensure collision freedom. We formally prove the parameter constraints to be sharp by characterizing them equivalently in terms of reachability properties of the hybrid system dynamics. Using our deductive verification tool KeYmaera, we formally verify controllability, safety, liveness, and reactivity properties of the ETCS protocol that entail collision freedom. We prove that the ETCS protocol remains correct even in the presence of perturbation by disturbances in the dynamics. We verify that safety is preserved when a PI controlled speed supervision is used.

Keywords  formal verification of hybrid systems - train control - theorem proving - parameter constraint identification - disturbances

All propositions have been verified in KeYmaera! This research was supported by DFG SFB/TR14 AVACS, and by NSF under grants no. CNS-0931985, CCF-0926181.

Fulltext Preview

Image of the first page of the fulltext document