ABSTRACT
We present a scalable and precise context-sensitive points-to analysis with three key properties: (1) filtering out of unrealizable paths, (2) a context-sensitive heap abstraction, and (3) a context-sensitive call graph. Previous work [21] has shown that all three properties are important for precisely analyzing large programs, e.g., to show safety of downcasts. Existing analyses typically give up one or more of the properties for scalability. We have developed a refinement-based analysis that succeeds by simultaneously refining handling of method calls and heap accesses, allowing the analysis to precisely analyze important code while entirely skipping irrelevant code. The analysis is demanddriven and client-driven, facilitating refinement specific to each queried variable and increasing scalability. In our experimental evaluation, our analysis proved the safety of 61% more casts than one of the most precise existing analyses across a suite of large benchmarks. The analysis checked the casts in under 13 minutes per benchmark (taking less than 1 second per query) and required only 35MB of memory, far less than previous approaches.
- Ashes suite collection. http://www.sable.mcgill.ca/software/.]]Google Scholar
- DaCapo Benchmark Suite. http://wwwali. cs.umass.edu/DaCapo/gcbm.html.]]Google Scholar
- L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, DIKU, 1994.]]Google Scholar
- D. Bacon and P. Sweeney. Fast static analysis of C++ virtual function calls. In Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), San Jose, CA, October 1996.]] Google ScholarDigital Library
- M. Berndl, O. Lhoták, F. Qian, L. Hendren, and N. Umanee. Pointsto analysis using BDDs. In Conference on Programming Language Design and Implementation (PLDI), June 2003.]] Google ScholarDigital Library
- S. Cherem and R. Rugina. Region analysis and transformation for java programs. In ISMM '04: Proceedings of the 4th international symposium on Memory management, 2004.]] Google ScholarDigital Library
- J.-D. Choi, M. Gupta, M. Serrano, V. Sreedhar, and S. Midkiff. Escape analysis for Java. In Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), November 1999.]] Google ScholarDigital Library
- A. Donovan, A. Kiezun, M. S. Tschantz, and M. D. Ernst. Converting Java programs to use generic libraries. In Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2004.]] Google ScholarDigital Library
- M. Fähndrich, J. Rehof, and M. Das. Scalable context-sensitive flow analysis using instantiation constraints. In Conference on Programming Language Design and Implementation (PLDI), 2000.]] Google ScholarDigital Library
- R. Fuhrer, F. Tip, J. Dolby, A. Kiezun, and M. Keller. Refactoring techniques for migrating applications to generic java container classes. In European Conference on Object-Oriented Programming (ECOOP), 2005.]]Google Scholar
- D. Grove and C. Chambers. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst., 23(6):685--746, 2001.]] Google ScholarDigital Library
- S. Z. Guyer and C. Lin. Client-driven pointer analysis. In International Static Analysis Symposium (SAS), San Diego, CA, June 2003.]]Google ScholarDigital Library
- S. Hallem, B. Chelf, Y. Xie, and D. Engler. A system and language for building system-specific, static analyses. In Conference on Programming Language Design and Implementation (PLDI), 2002.]] Google ScholarDigital Library
- N. Heintze and O. Tardieu. Demand-driven pointer analysis. In Conference on Programming Language Design and Implementation (PLDI), Snowbird, Utah, June 2001.]] Google ScholarDigital Library
- M. Hind. Pointer analysis: Haven't we solved this problem yet? In ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE), Snowbird, Utah, June 2001.]] Google ScholarDigital Library
- S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. In SIGSOFT'95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, 1995.]] Google ScholarDigital Library
- C. Lattner and V. Adve. Data Structure Analysis: An Efficient Context- Sensitive Heap Analysis. Tech. Report UIUCDCS-R-2003-2340, UIUC, April 2003.]]Google Scholar
- O. Lhoták. Personal communication. 2005.]]Google Scholar
- O. Lhoták. Program Analysis using Binary Decision Diagrams. PhD thesis, McGill University, Jan. 2006.]]Google Scholar
- O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. In International Conference on Compiler Construction (CC), Warsaw, Poland, April 2003.]]Google ScholarDigital Library
- O. Lhoták and L. Hendren. Context-sensitive points-to analysis: Is it worth it? In International Conference on Compiler Construction (CC), 2006.]] Google ScholarDigital Library
- D. Liang and M. J. Harrold. Efficient computation of parameterizedpointer information for interprocedural analyses. In Proceedings of the 8th International Symposium on Static Analysis, 2001.]] Google ScholarDigital Library
- A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for java. ACM Trans. Softw. Eng. Methodol., 14(1):1--41, 2005.]] Google ScholarDigital Library
- M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In Conference on Programming Language Design and Implementation (PLDI), 2006.]] Google ScholarDigital Library
- N. Nystrom, M. R. Clarkson, and A. C. Myers. Polyglot: An extensible compiler framework for java. In CC, pages 138--152, 2003.]]Google ScholarDigital Library
- R. O'Callahan. Generalized Aliasing as a Basis for Program Analysis Tools. PhD thesis, Carnegie Mellon University, November 2000.]] Google ScholarDigital Library
- J. Rehof and M. Fähndrich. Type-base flow analysis: from polymorphic subtyping to CFL-reachability. In ACM Symposium on Principles of Programming Languages (POPL), 2001.]] Google ScholarDigital Library
- T. Reps. Solving demand versions of interprocedural analysis problems. In International Conference on Compiler Construction (CC), Edinburgh, Scotland, April 1994.]] Google ScholarDigital Library
- T. Reps. Program analysis via graph reachability. Information and Software Technology, 40(11-12):701--726, November/December 1998.]]Google ScholarCross Ref
- T. Reps. Undecidability of context-sensitive data-independence analysis. ACM Trans. Program. Lang. Syst., 22(1):162--186, 2000.]] Google ScholarDigital Library
- T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In ACM Symposium on Principles of Programming Languages (POPL), 1995.]] Google ScholarDigital Library
- T. Reps, S. Horwitz, M. Sagiv, and G. Rosay. Speeding up slicing. In ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE), New Orleans, LA, December 1994.]] Google ScholarDigital Library
- E. Ruf. Effective synchronization removal for java. In Conference on Programming Language Design and Implementation (PLDI), 2000.]] Google ScholarDigital Library
- B. G. Ryder. Dimensions of precision in reference analysis of objectoriented programming languages. In International Conference on Compiler Construction (CC), Warsaw, Poland, April 2003.]]Google ScholarCross Ref
- O. Shivers. Control flow analysis in scheme. In Conference on Programming Language Design and Implementation (PLDI), 1988.]] Google ScholarDigital Library
- M. Sridharan and R. Bodík. Refinement-based context-sensitive points-to analysis for Java. Technical Report UCB/EECS-2006-31, UC Berkeley, 2006.]]Google ScholarDigital Library
- M. Sridharan, D. Gopan, L. Shan, and R. Bodík. Demand-driven points-to analysis for Java. In Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2005.]] Google ScholarDigital Library
- B. Steensgaard. Personal communication on analysis for Microsoft Bartok compiler. 2005.]]Google Scholar
- B. Steensgaard. Points-to analysis in almost linear time. In ACM Symposium on Principles of Programming Languages (POPL), 1996.]] Google ScholarDigital Library
- F. Tip, A. Kiezun, and D. Bäumer. Refactoring for generalization using type constraints. In OOPSLA, pages 13--26, 2003.]] Google ScholarDigital Library
- R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java optimization framework. In Proceedings of CASCON 1999, pages 125--135, 1999.]]Google ScholarDigital Library
- T. Wang and S. F. Smith. Precise constraint-based type inference for java. In 15th European Conference on Object-Oriented Programming (ECOOP), 2001.]] Google ScholarDigital Library
- J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Conference on Programming Language Design and Implementation (PLDI), 2004.]] Google ScholarDigital Library
- J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), November 1999.]] Google ScholarDigital Library
- R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In Conference on Programming Language Design and Implementation (PLDI), 1995.]] Google ScholarDigital Library
- J. Zhu and S. Calman. Symbolic pointer analysis revisited. In Conference on Programming Language Design and Implementation (PLDI), 2004.]] Google ScholarDigital Library
Recommendations
Precise interprocedural dataflow analysis via graph reachability
POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThe paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts ...
Demand-driven points-to analysis for Java
Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applicationsWe present a points-to analysis technique suitable for environments with small time and memory budgets, such as just-in-time (JIT) compilers and interactive development environments (IDEs). Our technique is demand-driven, performing only the work ...
A Principled Approach to Selective Context Sensitivity for Pointer Analysis
Context sensitivity is an essential technique for ensuring high precision in static analyses. It has been observed that applying context sensitivity partially, only on a select subset of the methods, can improve the balance between analysis precision and ...
Comments