Finding Application Errors Using PQL: A Program Query Language

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.

I saw the talk to this paper two weeks ago at OOPSLA two weeks ago and liked it very much. In a sense, I would consider it as a new application for aspect-oriented techniques.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


Any connection to this?

Same session

The paper you mentioned was actually presented in the same session. I think the most important difference to the work I mentioned is that PQL does a sophisticated static analysis before instrumenting the application whereas PTQL does not.

Static analysis

Yes, that's the main difference as far as I could tell from skimming the papers.

Discussed in related work

Both of these links seem to be from pre-publications versions of the papers. The actual OOPSLA versions for PQL and PTQL discuss the relationship between the two at length. Be careful when scanning quickly: PTQL is sometimes referred to as PARTIQLE (the name of the compiler). At the OOPSLA talk at least one of these groups explicitly thanked the other for helping to write the comparison.

Among the differences cited: PTQL can express nearly arbitrary contraints on even primitive types; PQL is limited to certain queries on objects. PTQL is more easily extended with unusual primitives, including primitives measuring the amount of absolute time which has passed between events. Finally, PQL may have as much as 19 times more overhead than PTQL for some queries (if I'm reading the table correctly, which I may not be), although there are other cases where the overheads are equivalent or reduced due to PQL's static analysis.

From the PTQL paper: "The goals of PQL are the same as those of PARTIQLE, but our query languages differ."