Symbolic analysis tools for CSP

Liyi Li, Elsa Gunter, William Mansky

Research output: Contribution to journalArticle

Abstract

Communicating Sequential Processes (CSP) is a well-known formal language for describing concurrent systems, where transition semantics for it has been given by Brookes, Hoare and Roscoe [1]. In this paper, we present trace refinement model analysis tools based on a generalized transition semantics of CSP, which we call HCSP, that merges the original transition system with ideas from Floyd-Hoare Logic and symbolic computation. This generalized semantics is shown to be sound and complete with respect to the original trace semantics. Traces in our system are symbolic representations of families of traces as given by the original semantics. This more compact representation allows us to expand the original CSP systems to effectively and efficiently model check some CSP programs that are difficult or impossible for other CSP systems to analyze. In particular, our system can handle certain classes of non-deterministic choices as a single transition, while the original semantics would treat each choice separately, possibly leading to large or unbounded case analyses. All the work described in this paper has been carried out in the theorem prover Isabelle [2]. This then provides us with a framework for automated and interactive analysis of CSP processes. It also gives us the ability to extract Ocaml code for an HCSP-based simulator directly from Isabelle. Based on the HCSP semantics and traditional trace refinement, we develop an idea of symbolic trace refinement and build a model checker based on it. The model checker was transcribed by hand into Maude [3] as automatic extraction of Maude code is not yet supported by the Isabelle system.

Original languageEnglish (US)
Pages (from-to)295-313
Number of pages19
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8687
StatePublished - Jan 1 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Symbolic analysis tools for CSP'. Together they form a unique fingerprint.

  • Cite this