The ability of the software engineering community to achieve high levels of reuse from software frameworks has been tempered by the difficulty in understanding how to reuse them properly. When written correctly, a plugin can take advantage of the framework’s code and architecture to provide a rich application with relatively few lines of code. Unfortunately, doing this correctly is difficult because frameworks frequently require plugin developers to be aware of complex protocols between objects, and improper use of these protocols causes exceptions and unexpected behavior at run time. This dissertation introduces collaboration constraints, rules governing how multiple objects may interact in a complex protocol. These constraints are particularly difficult to understand and analyze because they may extend across type boundaries and even programming language boundaries. This thesis improves the state of the art through two mechanisms. First, it provides a deep understanding of these collaboration constraints and the framework designs which create them. Second, it introduces Fusion, an adoptable specification language and static analysis tool, that detects broken collaboration constraints in plugin code and demonstrates how to achieve this goal in a cost-effective manner that is practical for industry use. In this dissertation, I have done an empirical study of framework help forums which showed that collaboration constraints are burdensome for developers, as they take hours or even days to resolve. From this empirical study, I have identified several common properties of collaboration constraints. This motivated a new specification language, called Fusion, that is tailored for specifying collaboration constraints in a practical way. The specification language uses relationships to describe the abstract associations between objects and allows developers to specify collaboration constraints as logical predicates of relationships. Since a relationship is an abstraction above the code, this allows developers to easily specify constraints that cross type and language boundaries. There are three variants of the analysis: a sound variant that has false positives but no false negatives, a complete variant that has false negatives but no false positives, and a pragmatic variant that attempts to balance this tradeoff. In this dissertation, I successfully used Fusion to specify and analyze constraints from examples found in the help forums of the ASP.NET and Spring frameworks. Additionally, I ran Fusion on DaCapo, a 1.5 MLOC DaCapo benchmark for program analysis, to show that Fusion is scalable and provides precise enough results for industry with low specification cost. This dissertation examines many tradeoffs: the tradeoffs of framework designs, the tradeoffs of specification precision, and the tradeoffs of program analysis results are all featured. A central theme of this work is that there is no single right solution to collaboration constraints; there are only solutions that work better for a particular instance of the problem.

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.