Pick your contexts well: understanding object-sensitivity

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 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), scalability (comparable to analyses with much less context-sensitivity), and precision (comparable to the best object-sensitive analysis with the same context depth).

References

1. Ole Agesen. The cartesian product algorithm: Simple and precise type inference of parametric polymorphism. In Proceedings of the 9th European Conference on Object-Oriented Programming, pages 2--26, London, UK, 1995. Springer-Verlag.
2. Martin Bravenboer and Yannis Smaragdakis. Exception analysis and points-to analysis: Better together. In Laura Dillon, editor, ISSTA '09: Proceedings of the 2009 International Symposium on Software Testing and Analysis, New York, NY, USA, July 2009.
3. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In OOPSLA '09: 24th annual ACM SIGPLAN conference on Object Oriented Programming, Systems, Languages, and Applications, New York, NY, USA, 2009. ACM.
4. Patrick Cousot and Radhia Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, POPL '77, pages 238--252, New York, NY, USA, 1977. ACM.
5. Stephen Fink, Eran Yahav, Nurit Dor, G. Ramalingam, and Emmanuel Geay. Effective typestate verification in the presence of aliasing. In ISSTA '06: Proceedings of the 2006 international symposium on Software testing and analysis, pages 133--144, New York, NY, USA, 2006. ACM.
6. Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. Featherweight Java: a minimal core calculus for Java and GJ. ACM Trans. Program. Lang. Syst., 23(3):396--450, 2001.
7. Ondřej Lhoták. Program Analysis using Binary Decision Diagrams. PhD thesis, McGill University, January 2006.
8. Ondřej Lhoták.and Laurie Hendren. Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Trans. Softw. Eng. Methodol., 18(1):1--53, 2008.
9. Ondřej Lhoták. and Laurie Hendren. Relations as an abstraction for BDD-based program analysis. ACM Trans. Program. Lang. Syst., 30(4):1--63, 2008.
10. Donglin Liang, Maikel Pennings, and Mary Jean Harrold. Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs. In Michael D. Ernst and Thomas P. Jensen, editors, PASTE, pages 6--12. ACM, 2005.
11. Benjamin Livshits, John Whaley, and Monica S. Lam. Reflection analysis for Java. In Kwangkeun Yi, editor, Proceedings of the 3rd Asian Symposium on Programming Languages and Systems, volume 3780. Springer-Verlag, November 2005.
12. Matthew Might, Yannis Smaragdakis, and David Van Horn. Resolving and exploiting the k-CFA paradox: Illuminating functional vs. object-oriented program analysis. In Conf. on Programming Language Design and Implementation (PLDI). ACM, June 2010.
13. Ana Milanova, Atanas Rountev, and Barbara G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol., 14(1):1--41, 2005.
14. Mayur Naik, Alex Aiken, and John Whaley. Effective static race detection for Java. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'06), pages 308--319, 2006.
15. John Plevyak and Andrew A. Chien. Precise concrete type inference for object-oriented languages. In Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, OOPSLA '94, pages 324--340, New York, NY, USA, 1994. ACM.
16. John Reppy. Type-sensitive control-flow analysis. In Proceedings of the 2006 ACM SIGPLAN Workshop on ML, pages 74--83, September 2006.
17. Barbara G. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. In Görel Hedin, editor, Compiler Construction, 12th International Conference, CC 2003, volume 2622 of Lecture Notes in Computer Science, pages 126--137. Springer, 2003.
18. Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis, pages 189--233, Englewood Cliffs, NJ, 1981. Prentice-Hall, Inc.
19. Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, May 1991.
20. Manu Sridharan and Rastislav Bodík. Refinement-based context-sensitive points-to analysis for Java. In PLDI '06: Proc. of the 2006 ACM SIGPLAN conf. on Programming language design and implementation, pages 387--400, New York, NY, USA, 2006. ACM.
21. Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Etienne Gagnon, and Charles Godin. Practical virtual method call resolution for Java. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 264--280. ACM Press, 2000.
22. John Whaley, Dzintars Avots, Michael Carbin, and Monica S. Lam. Using Datalog with binary decision diagrams for program analysis. In Kwangkeun Yi, editor, APLAS, volume 3780 of Lecture Notes in Computer Science, pages 97--118. Springer, 2005.
23. John Whaley and Monica S. Lam. Cloning-based contextsensitive pointer alias analysis using binary decision diagrams. In PLDI '04: Proc. of the ACM SIGPLAN 2004 conf. on Programming language design and implementation, pages 131--144, New York, NY, USA, 2004. ACM.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

      • Semantics

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis

    • Program semantics