Comparisons of Alloy and Spin

What Is Lightweight Modeling?

Lightweight modeling means constructing small, abstract models of the key concepts of a software system. Lightweight analysis refers to verifying properties of a model within a bounded domain automatically, by means of enumeration over the domain. This is often called "push-button verification." Lightweight modeling is a highly cost-effective design tool. "Experiences with protocol description" (Pamela Zave; 1st International Workshop on Rigorous Protocol Engineering, Vancouver, Canada, October 2011) recounts some of my experiences with lightweight modeling, and some of the problems that arise when protocols are designed without it.

My favorite technologies for lightweight modeling are the Promela language and its LTL model-checker Spin, and the Alloy language and its model-enumerating Alloy Analyzer. Both tools are freely available for a variety of platforms. In the spring of 2010 I taught them in a course on Formal Methods in Networking at Princeton University. The notes for my four lectures are in Lecture 22 March, Lecture 26 March, Lecture 29 March, and Lecture 2 April.

Models of Chord

Modeling and analysis with Alloy and Spin have yielded many insights on the correctness of the Chord ring-maintenance protocol. In addition, this in-depth study has led to some new and interesting comparisons between Alloy and Spin (as a representative of model-checking). The results, including the surprising observation that Alloy may be better for verifying some network protocols than model-checking, are summarized in "A practical comparison of Alloy and Spin" (Pamela Zave; Formal Aspects of Computing, 2014, to appear).

The paper discusses three versions of Chord. The original version comes from the Chord SIGCOMM paper, with borrowing from another paper to fill gaps. A model of the original version is:

The "best assembly" version was defined in "Using lightweight modeling to understand Chord". It was obtained by assembling the best pieces, including both pseudocode and text, from three published Chord papers. The models of the "best assembly" version from this paper in Computer Communications Review are: The "base" version is a new version of Chord that has been proven correct. The models of the "base" version are:

Models of SIP

Many models of the Session Initiation Protocol (SIP), written in Promela and analyzed with the Spin model checker, have been developed for understanding SIP through model-checking. These are the first formal models of SIP.

Models of network architecture

Although today's networking is astoundingly complex, it is still possible to build abstract models of network architecture that have real value. For these models I have been using Alloy and the Alloy Analyzer.

In October 2010 I gave a keynote talk at the Models Conference on "Modeling the Internet".