Pick Your Contexts Well: Understanding Object-Sensitivity

Using Datalog for program analysis has garnered a lot of interest in the academic community in recent years. In particular, when evaluated using a scalable database engine such as LogicBlox, program analysis can not only be specified in a clean and digestible way, they can also run very fast. LogicBlox CTO Martin Bravenboer’s postdoctoral work with his advisor, Yannis Smaragdakis, demonstrated this point by implementing points-to program analysis in LogiQL, evaluating them on the LogicBlox database, and crushing the competition with order-of-magnitude improvements in performance. In their latest work together with Prof. Ondrej Lhotak of University of Waterloo, they discuss how to pick the right context abstract for points-to analysis in an Object-Oriented language like Java.

Abstract Object-sensitivity has emerged as an excellent context abstraction for points-to analysis in object-oriented languages. Despite its practical success, however, object-sensitivity is poorly understood. For instance, for a context depth of 2 or higher, past scalable implementations deviate quite significantly from the original definition of an object-sensitive analysis. The reason is that the analysis has many degrees of freedom, relating to which context elements are picked at every method call and object creation. We offer a clean model for the analysis design space, and discuss a formal and informal understanding of object-sensitivity and of how to create good object-sensitive analyses. The results are surprising in their extent. We find that past implementations have made a sub-optimal choice of contexts, to the severe detriment of precision and performance. We define a full-object-sensitive analysis that results in significantly higher precision, and often performance, for the exact same context depth. We also introduce type-sensitivity as an explicit approximation of object-sensitivity that preserves high context quality at substantially reduced cost. A type-sensitive points-to analysis makes an unconventional use of types as context: the context types are not dynamic types of objects involved in the analysis, but instead upper bounds on the dynamic types of their allocator objects. Our results expose the influence of context choice on the quality of points-to analysis and demonstrate type-sensitivity to be an idea with major impact: It decisively advances the state-of-the-art with a spectrum of analyses that simultaneously enjoy speed (several times faster than an analogous object-sensitive analysis), high scalability (comparable to analyses with much less context-sensitivity), and precision (comparable to the best object-sensitive analysis with the same context depth).


Leave a reply

© Copyright 2023. Infor. All rights reserved.

Log in with your credentials

Forgot your details?