Modular invariants for layered object structures

Abstract

Classical specication and verication techniques support invariants for individual objects whose fields are primitive values, but are unsound for invariants involving more complex object structures. However, such non-trivial object structures are common, and occur in lists, hash tables, and when systems are built in layers. We generalize classical techniques to cover such layered object structures using a rened semantics for invariants based on an ownership model for alias control. This semantics enables sound and modular reasoning. We further extend this ownership technique to even more expressive invariants that gain their modularity by imposing certain visibility requirements.