CMU-ISR-09-108
Institute for Software Research
School of Computer Science, Carnegie Mellon University



CMU-ISR-09-108

API Protocol Compliance in Object-Oriented Software

Kevin Bierhoff

April 2009

Ph.D. Thesis
Software Engineering

CMU-ISR-09-108.pdf


Keywords: Typestate, access permissions, state refinement, Plural


Modern software development is highly reliant on reusable APIs. APIs often define usage protocols that API clients must follow in order for code implementing the API to work correctly. Loosely speaking, API protocols define legal sequences of method calls on objects. In this work, protocols are defined based on typestates. Typestates leverage the familiar intuition of abstract state machines to define usage protocols.

The goal of this work is to give developers comprehensive help in defining and following API protocols in object-oriented software. Two key technical contributions enable the proposed approach: (1) Object state spaces are defined with hierarchical state refinements. Hierarchical state spaces make specifications more succinct, elegantly deal with subtyping, express uncertainty, and enable more precise reasoning about aliasing. (2) A novel abstraction, called access permissions, combines typestate and aliasing information. Access permissions capture developers' design intent regarding API protocols and enable sound modular verification of API protocol compliance while allowing a great deal of flexibility in aliasing objects.

This dissertation demonstrates that typestate-based protocols with state refinement and access permissions can be used for automated, static, modular enforcement of API protocols in practical object-oriented software. Formal and empirical results show that the presented approach captures common API protocols succinctly, allows sound modular checking of protocol compliance in object-oriented code, can be automated in tools for mainstream programming languages that impose low annotation burden on developers, and can check API protocols in off-the-shelf software with higher precision than previous approaches.

This work puts automatic API protocol compliance checking within reach of being used in practice. It will enable rapid and correct use of APIs during initial construction and ensure that API clients and implementations remain consistent with the specified protocol during maintenance tasks.

158 pages


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

This page maintained by reports@cs.cmu.edu