Formal Verification for Fault-Tolerant Architectures/PVS Design

John M. Rushby, SRI International, rushby@csl.sri.com


Summary

PVS is the most recent in a series of verification systems developed at SRI. Its design was strongly influenced, and later refined, by our experiences in developing formal specifications and mechanically checked verifications for the fault-tolerant architecture, algorithms, and implementations of a model reliable computing platform (RCP) for life-critical digital flight-control applications.

Several of the formal specifications and verifications performed in support of RCP are individually of considerable complexity and difficulty. But in order to contribute to the overall goal, it has often been necessary to modify completed verifications to accommodate changed assumptions or requirements, and people other than the original developer have often needed to understand, review, build on, modify, or extract part of an intricate verification.

In this talk, I will outline the verifications performed, present the lessons learned, and describe some of the design decisions taken in PVS to better support these large, difficult, iterative, and collaborative verifications.

The following article covers this material in more detail: " Formal Verification for Fault-Tolerant Architectures: Prolegomena to the Design of PVS" by Sam Owre, John Rushby, Natarajan Shankar, and Friedrich von Henke (IEEE Transactions on Software Engineering, Vol 21., No. 2, Feb. 1995, pp. 107-125).

Slides