Finding Application Errors Using PQL: A Program Query Language
San Diego Room
Thursday, 9:00, 30 minutes
Michael Martin, Stanford University
Benjamin Livshits, Stanford University
Monica Lam, Stanford University
A number of effective error detection tools have been built in recent years to check if a program conforms to certain design rules. An important class of design rules deals with sequences of events associated with a set of related objects. This paper presents a language called PQL (Program Query Language) that allows programmers to express such questions easily in an application-specific context. A query looks like a code excerpt corresponding to the shortest amount of code that would violate a design rule. Details of the target application's precise implementation are abstracted away. The programmer may also specify actions to perform when a match is found, such as recording relevant information or even correcting an erroneous execution on the fly. We have developed both static and dynamic techniques to find solutions to PQL queries. Our static analyzer finds all potential matches conservatively using a context-sensitive, flow-insensitive, inclusion-based pointer alias analysis. Static results are also useful in reducing the number of instrumentation points for dynamic analysis. Our dynamic analyzer instruments the source program to catch all violations precisely as the program runs and optionally to perform user-specified actions. We have implemented techniques described in this paper and used this combination of static and dynamic analysis to successfully find 206 breaches of security and important resource leaks in 6 large real-world open-source Java applications containing a total of nearly 60,000 classes.