Universe-Type-Based Verification Techniques for Mutable Static Fields and Methods

By: A. J. Summers, Sophia Drossopoulou, Peter Müller

Abstract

We present three novel techniques for the verification of invariants in the setting of Java-like languages including static fields and methods. Our techniques structure the heap through universe types, and extend the Visibility Technique of Müller et al. In order to cater for mutable static fields, we extend the classical universe types heap topology with multiple trees, where each tree is rooted in a class. Thus classes may naturally own objects as static fields. We present a basic version of our approach, which allows trees to be visited at the top and then navigated “downwards”, and which avoids dangerous call-backs through effects which track static method calls. As well as the usual kinds of proof obligations defining that certain invariants must hold at a given state, we employ a second kind of obligation to show that certain other invariants are preserved between two states (i.e., if they hold in the former state then they will still hold in the latter). This allows us to deal with invariants whose expected truth-value cannot always be determined statically in a modular way. We then present two extensions of our basic technique, aimed at improving usability. Firstly, we introduce a new universe annotation to allow safe callbacks between trees, whereby trees may be visited not at the top, but at the point where a previous visit “had left off”. Secondly, we refine our heap topology with a notion of 'levels', which stratify the heap and provide modularity with regard to library classes and the required effects annotations.

Cite as:

A. J. Summers, Sophia Drossopoulou, Peter Müller, “Universe-Type-Based Verification Techniques for Mutable Static Fields and Methods”, Journal of Object Technology, Volume 8, no. 4 (June 2009), pp. 85-125, doi:10.5381/jot.2009.8.4.a4.