Incremental and Verified Modelling of the PCI Express Protocol

PCI Express is a modern, high-performance communication protocol implementing sophisticated features to meet today's performance demands. Although an off-chip protocol, PCI Express implements many principles of future on-chip communication architectures. It is a highly complex protocol that is hard to verify formally. We present the application of a new approach to the PCI Express transaction and data link layers. The methodology is based on a series of model transformation steps and revises the traditional modelling and verification workflow for designing on-chip protocols. Major parts of PCI Express, including performance-related optimisations and fault-tolerance features, are modelled incrementally to control the complexity and composed to a single model. The work has been accomplished in the Isabelle/HOL theorem prover. By restricting the models to an executable subset of the specification language, we have been able to combine the advantages of specifying in a theorem prover with the advantages of executable models in a functional programming language