This thesis represents an attempt to improve the state of the art in our ability tounderstand and check object protocols, with a particular emphasis on concurrent pro-grams. Object protocols are the patterns of use imposed on clients of APIs in object-oriented programs. We show through an empirical study of open-source object-oriented programs that object protocols are quite common. We then present “Sync-or-Swim,” a methodology and suite of accompanying tools for checking at compile-time that object protocols are used and implemented correctly. This methodology isbased upon the existing access permissions method of alias control, which is hereextended to be sound in the face of shared-memory concurrency. The analysis isformalized as a type system for an object-oriented calculus, and then proven to befree from false-negatives using a proof of type safety. The type system is extendedwith parametric polymorphism, or “generics,” in order to increase its ability to checkcommonly occurring patterns. An implementation of the approach, a static analysisfor programs written in the Java programming language, is presented. This imple-mentation was used to perform a series of case studies whose goal was to evaluatethe ease of use, expressiveness and ability to verify commonly occurring patterns.These case studies are presented. Next, an approach and an associated tool for in-ferring access permission annotations is presented. This inference tool can reducethe burden of using our protocol-checking approach by automatically inferring therequired typing annotations. This inference is built upon a system of probabilisticconstraints, which allows the easy encoding of heuristics. Finally, an optimization ofsoftware transactional memory runtimes is presented. This optimization is enabledby the typing annotations required to use the concurrent protocol checker and canremove some of the overhead typically associated with transactional memory sys-tems. As a result of the work presented in this thesis, it is possible to guarantee theabsence of certain API usage errors even in concurrent programs, and to do so witha low burden on programmers. By adhering to such an approach, programmers canproduce more reliable software.
| Identifer | oai:union.ndltd.org:cmu.edu/oai:repository.cmu.edu:dissertations-1042 |
| Date | 01 December 2010 |
| Creators | Beckman, Nels E. |
| Publisher | Research Showcase @ CMU |
| Source Sets | Carnegie Mellon University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations |
Page generated in 0.0024 seconds