Abstraction of parameterized networks
David Lesens, Hassen Saı̈di · Electronic Notes in Theoretical Computer Science · 1997
In this paper we are interested in the verification of safety properties of parameterized networks. A network is defined as a parallel composition of an arbitrary but finite number of identical sequential processes, where we consider parallel composition by interleaving and synchronization by shared variables. Using abstraction techniques, a process, called an abstract network , encoding the behaviour of the entire network is constructed. The property is then checked on this process. Our verification method has the following advantages: the construction of the abstract network is fully automatic; the obtained process is generally a simple process on which the property can be easily verified. Of course, if the property cannot be verified on the abstract network, another more precise abstraction has to be computed. The construction requires to discharge a set of first order verification conditions (VCs). The PVS theorem prover is used to discharge the generated VCs. This allows us to consider processes with arbitrary data types. The effectiveness of our verification method is illustrated on two examples including a parameterized version of the Fischer's protocol.