Modular typestate checking of aliased objects
Authors:
Open Access
- 21 October 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 42 (10) , 301-320
Abstract
Objects often define usage protocols that clients must follow inorder for these objects to work properly. Aliasing makes itnotoriously difficult to check whether clients and implementations are compliant with such protocols. Accordingly, existing approaches either operate globally or severely restrict aliasing. We have developed a sound modular protocol checking approach, based on typestates, that allows a great deal of flexibility in aliasing while guaranteeing the absence of protocol violations at runtime. The main technical contribution is a novel abstraction, access permissions , that combines typestate and object aliasing information. In our methodology, developers express their protocol design intent through annotations based on access permissions. Our checking approach then tracks permissions through method implementations. For each object reference the checker keeps track of the degree of possible aliasing and is appropriately conservativein reasoning about that reference. This helps developers account for object manipulations that may occur through aliases. The checking approach handles inheritance in a novel way, giving subclasses more flexibility in method overriding. Case studies on Java iterators and streams provide evidence that access permissions can model realistic protocols, and protocol checking based on access permissions can be used to reason precisely about the protocols that arise in practice.Keywords
This publication has 28 references indexed in Scilit:
- Deriving object typestates in the presence of inter-object references2005
- Lightweight object specification with typestates2005
- Verifying safety policies with size properties and alias controls2005
- Verification of Object-Oriented Programs with Invariants.The Journal of Object Technology, 2004
- Typestates for Objects2004
- Checking Interference with Fractional Permissions2003
- First-order linear logic without modalities is NEXPTIME-hardTheoretical Computer Science, 1994
- A behavioral notion of subtypingACM Transactions on Programming Languages and Systems, 1994
- Statecharts: a visual formalism for complex systemsScience of Computer Programming, 1987
- Linear logicTheoretical Computer Science, 1987