VC generation for functional behavior and non-interference of iterators

ABSTRACT

We propose a formalism for the full functional specification of enumerator methods, which are C# methods that return objects of type IEnumerable<T> or IEnumerator<T>. We further propose a sound modular automatic verification approach for enumerator methods implemented using C# 2.0's iterator blocks (i.e., using yield return and yield break statements), and for client code that uses for-each loops. We require for-each loops to be annotated with special for-each loop invariants.The approach prevents interference between iterator implementations and client code. Specifically, an enumerator method may read a field o.f only if o is reflexively-transitively owned by an object listed in the enumerator method's reads clause, and the body of a for-each loop may not modify these objects. For example, we verify that a for-each loop iterating over an ArrayList does not modify the ArrayList. Note that one may break out of a for-each loop at any time to perform modifications before the iteration is complete. This in effect invalidates the iteration since the for-each loop cannot be resumed.We support specification of non-deterministic enumerations, infinite enumerations, and enumerations that terminate with a checked exception, but not enumerations with side-effects. We support verification of an enumerator method only if it is implemented using yield statements, and verification of client code only if it performs a for-each loop on an enumerator method call. That is, the present approach does not support explicit creation or manipulation of IEnumerator<T> objects.Our approach integrates easily with our concurrency approach (presented at ICFEM06), since both are based on read/write sets.This approach was initially presented at FTfJP05. Please refer to this paper for related work, references, and a soundness proof.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

General Terms:
Design, Verification

Keywords:
boogie, formal specification, iterators, verification