Paper Details

Communicating Process Architectures (CPA)
 Title: Unifying Concurrent Programming and Formal Verification within One Language
 Conference: Communicating Process Architectures 2017
 Authors: Peter H. Welcha, Jan B√¶kgaard Pedersenb, Frederick R. M. Barnesa, Carl G. Ritsona, Neil C. C. Brownc
(a) School of Computing, University of Kent
(b) Department of Computer Science, University of Nevada Las Vegas
(c) Department of Informatics, King's College London
 Abstract: This is a proposal for the formal verification of occam-pi programs to be managed entirely within occam-pi. The language is extended with qualifiers on types and processes (to indicate relevance for verification and/or execution) and assertions about refinement (including deadlock, livelock and determinism). The compiler abstracts a set of CSPM equations and assertions, delegates their analysis to the FDR model checker and reports back in terms related to the occam-pi source. The rules for mapping the extended occam-pi to CSPM are given. The full range of CSPM assertions is accessible, with no knowledge of CSP formalism required by the occam-pi programmer. Programs are proved just by writing and compiling programs. A case study analysing a new (and elegant) solution to the Dining Philosophers problem is presented. Deadlock-freedom for colleges with any number of philosphers is established by verifying an induction argument (the base and induction steps). Finally, following guidelines laid down by Roscoe, the careful use of model compression is demonstrated to verify directly the deadlock-freedom of an occam-pi college with 102000 philosphers (in around 30 seconds). All we need is a universe large enough to contain the computer in which the college and its philosophers can live. 
Files:


BibTeX Entry


Full paper


Presentation