Preface

This volume contains the proceedings of MARS 2015, the first workshop on Models for Formal Analysis of Real Systems, held on November 23, 2015 in Suva, Fiji, as an affiliated workshop of LPAR 2015, the 20th International Conference on Logic for Programming, Artificial Intelligence and Reasoning.

Specification formalisms and modelling techniques have often been developed with formal analysis and formal verification in mind. To show applicability, toy examples or tiny case studies are typically presented in research papers. Since the theory needs to be developed, this approach is reasonable. However, to show that a developed approach actually scales to real systems, large case studies are essential.

The development of formal models of real systems usually requires a perfect understanding of informal descriptions of systems—sometimes found in RFCs or other standard documents—which are usually just written in English. Based on the type of system, an adequate specification formalism needs to be chosen, and the informal specification translated into it. Abstraction from unimportant details then yields an accurate, formal model of the real system. The process of developing a detailed and accurate model usually takes a large amount of time, often months or years; without even starting a formal analysis.

When publishing the results on a formal analysis in a scientific paper, details of the model have to be skipped due to lack of space, and often the lessons learnt from modelling are not discussed since they are not within the main focus of the paper. The workshop aims at discussing exactly these unmentioned lessons. Examples are:

  1. Which formalism is chosen, and why?
  2. Which abstractions have to be made and why?
  3. How are important characteristics of the system modelled?
  4. Were there any complications while modelling the system?
  5. Which measures were taken to guarantee the accuracy of the model?

The workshop emphasises modelling over verification. In particular, we invited papers that present full models of real systems, which may lay the basis for future comparison and analysis. The workshop intends to bring together researchers from different communities that all aim at verifying real systems and are developing formal models for such systems. Areas where large models often occur are within networks, (trustworthy) systems and software verification (from byte code up to programming- and specification languages). An aim of the workshop is to present different modelling approaches and discuss pros and cons for each of them.

The submitted papers were carefully refereed by the programme committee, assisted by outside referees, whose help is gratefully acknowledged. The topics include:

  • the correctness specification of BilbyFs, a performant Linux flash file system, formalised in a so-called nondeterminism monad,
  • modelling the interleaving behaviour of eChronos, a preemptible real-time OS for embedded micro-controllers, using a controlled concurrency framework derived from the Owicki-Gries method,
  • an abstract model of a self-balancing unicycle in the form of a collection of hybrid automata,
  • a timed automaton model to compute tight bounds for the worst-case execution times of binary programs running on architectures featuring caches and pipelines,
  • formalising the Bitcoin protocol in UPPAAL, to examine double spending probabilities, and
  • formal models of the Data Encryption Standard in the process calculi LOTOS and LNT.
Full specifications of the models contributed by these paper are made accessible, so that their quality can be evaluated. Alternative formal descriptions are encouraged, which should foster the development of improved specification formalisms.

 
Rob van Glabbeek
Jan Friso Groote
Peter Höfner

 

Programme Committee:

Rance Cleaveland (University of Maryland, USA)
Hubert Garavel (INRIA, France)
Rob van Glabbeek (co-chair, NICTA, Australia)
Jan Friso Groote (co-chair, Eindhoven University of Technology, The Netherlands)
He Jifeng (East China Normal University, China)
Holger Hermanns (Saarland University, Germany)
Peter Höfner (co-chair, NICTA, Australia)
Gerard Holzmann (NASA/JPL, USA)
Magnus Myreen (Chalmers University, Sweden)
Viet Yen Nguyen (Fraunhofer IESE, Germany)
Bill Roscoe (University of Oxford, UK)
Pamela Zave (AT&T Laboratories, USA)

In Rob van Glabbeek, Jan Friso Groote and Peter Höfner: Proceedings Workshop on Models for Formal Analysis of Real Systems (MARS 2015), Suva, Fiji, November 23, 2015, Electronic Proceedings in Theoretical Computer Science 196, pp. 2–3.
Published: 8th November 2015.

http://dx.doi.org/10.4204/EPTCS.196.0 bibtex

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org