Institute for Software Research
School of Computer Science, Carnegie Mellon University


Modular Typestate Verification of Aliased Objects

Kevin Bierhoff, Jonathan Aldrich

March 2007


Keywords: Protocol enforcement, typestates, aliasing, permissions

A number of type systems have used typestates to specify and statically verify protocol compliance. Aliasing is a major challenge for these systems. This paper proposes a modular type system for a core object-oriented language that leverages linear logic for verifying compliance to more expressive protocol specifications than previously supported. The system improves reasoning about aliased objects by associating references with access permissions that systematically capture what aliases know about and can do to objects. Permissions grant full, shared, or read-only access to a certain part of object state and allow aliasing both on the stack and in the heap. The system supports dynamic state tests, arbitrary callbacks, and open recursion. The system's expressiveness is illustrated with examples from the Java I/O library.

50 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by