Invariant Generation for Parametrized Systems using Self-Reflection

Alejandro Sánchez, Sriram Sankaranarayanan, César Sánchez, and Evan Chang
We examine the problem of inferring invariants for parametrized systems. Parametrized systems are concurrent systems consisting of an a priori unbounded number of process instances running the same program. Such systems are commonly encountered in many situations including device drivers, distributed systems, and robotic swarms. In this paper we describe a technique that enables leveraging off-the-shelf invariant generators designed for sequential programs to infer invariants of parametrized systems. The central challenge in invariant inference for parametrized systems is that naively exploding the transition system with all interleavings is not just impractical but impossible. In our approach, the key enabler is the notion of a reflective abstraction that we prove has an important correspondence with inductive invariants. This correspondence naturally gives rise to an iterative invariant generation procedure that alternates between computing candidate invariants and creating reflective abstractions.
In Proceedings of the 19th International Symposium on Static Analysis (SAS 2012), September 11-13, Deauville, France. 2012. vol 7460 of Lecture Notes in Computer Science pp146-163, Springer 2012, ISBN 978-3-642-33124-4.
Download: BIB PDF