Document Open Access Logo

Defensive Points-To Analysis: Effective Soundness via Laziness

Authors Yannis Smaragdakis, George Kastrinis

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2018.23.pdf
  • Filesize: 1.35 MB
  • 28 pages

Document Identifiers

Author Details

Yannis Smaragdakis
  • Dept. of Informatics and Telecommunications, University of Athens, Greece
George Kastrinis
  • Dept. of Informatics and Telecommunications, University of Athens, Greece

Cite As Get BibTex

Yannis Smaragdakis and George Kastrinis. Defensive Points-To Analysis: Effective Soundness via Laziness. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECOOP.2018.23

Abstract

We present a defensive may-point-to analysis approach, which offers soundness even in the presence of arbitrary opaque code: all non-empty points-to sets computed are guaranteed to be over-approximations of the sets of values arising at run time. A key design tenet of the analysis is laziness: the analysis computes points-to relationships only for variables or objects that are guaranteed to never escape into opaque code. This means that the analysis misses some valid inferences, yet it also never wastes work to compute sets of values that are not "complete", i.e., that may be missing elements due to opaque code. Laziness enables great efficiency, allowing a highly precise points-to analysis (such as a 5-call-site-sensitive, flow-sensitive analysis).
Despite its conservative nature, our analysis yields sound, actionable results for a large subset of the program code, achieving (under worst-case assumptions) 34-74% of the program coverage of an unsound state-of-the-art analysis for real-world programs.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Compilers
  • Theory of computation → Program analysis
  • Software and its engineering → General programming languages
Keywords
  • static analysis
  • soundness
  • defensive analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. David F. Bacon and Peter F. Sweeney. Fast static analysis of C++ virtual function calls. In Proc. of the 11th Annual ACM SIGPLAN Conf. on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA '96, pages 324-341, New York, NY, USA, 1996. ACM. Google Scholar
  2. Sandip K. Biswas. A demand-driven set-based analysis. In POPL '97: Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 372-385, 1997. Google Scholar
  3. Stephen M. Blackburn, Robin Garner, Chris Hoffmann, Asjad M. Khan, Kathryn S. McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z. Guyer, Martin Hirzel, Antony L. Hosking, Maria Jump, Han Bok Lee, J. Eliot B. Moss, Aashish Phansalkar, Darko Stefanovic, Thomas VanDrunen, Daniel von Dincklage, and Ben Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2006, October 22-26, 2006, Portland, Oregon, USA, OOPSLA '06, pages 169-190, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1167473.1167488.
  4. Bruno Blanchet. Escape analysis: Correctness proof, implementation and experimental results. In POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 25-37, 1998. Google Scholar
  5. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proc. of the 24th Annual ACM SIGPLAN Conf. on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA '09, New York, NY, USA, 2009. ACM. Google Scholar
  6. Cristiano Calcagno, Dino Distefano, Peter O'Hearn, and Hongseok Yang. Compositional shape analysis by means of bi-abduction. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '09, pages 289-300, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1480881.1480917.
  7. Jong D. Choi, Michael Burke, and Paul Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 232-245, 1993. Google Scholar
  8. 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. URL: http://dx.doi.org/10.1145/512950.512973.
  9. Jeffrey Dean, David Grove, and Craig Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In ECOOP'95 - Object-Oriented Programming, 9th European Conference, Århus, Denmark, August 7-11, 1995, Proceedings, ECOOP '95, pages 77-101. Springer, 1995. URL: http://dx.doi.org/10.1007/3-540-49538-X_5.
  10. David Delmas and Jean Souyris. Astrée: From Research to Industry, pages 437-451. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74061-2_27.
  11. Alain Deutsch. On the complexity of escape analysis. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '97, pages 358-371, New York, NY, USA, 1997. ACM. URL: http://dx.doi.org/10.1145/263699.263750.
  12. Stephen J. Fink et al. WALA UserGuide: PointerAnalysis. http://wala.sourceforge.net/wiki/index.php/UserGuide:PointerAnalysis, 2013.
  13. Martin Hirzel, Amer Diwan, and Michael Hind. Pointer analysis in the presence of dynamic class loading. In ECOOP 2004 - Object-Oriented Programming, 18th European Conference, Oslo, Norway, June 14-18, 2004, Proceedings, ECOOP '04, pages 96-122. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-24851-4_5.
  14. Martin Hirzel, Daniel von Dincklage, Amer Diwan, and Michael Hind. Fast online pointer analysis. ACM Trans. Program. Lang. Syst., 29(2), 2007. URL: http://dx.doi.org/10.1145/1216374.1216379.
  15. Suresh Jagannathan, Peter Thiemann, Stephen Weeks, and Andrew Wright. Single and loving it: must-alias analysis for higher-order languages. In POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 329-341, 1998. Google Scholar
  16. Davy Landman, Alexander Serebrenik, and Jurgen J. Vinju. Challenges for static analysis of Java reflection - literature review and empirical study. In Proceedings of the 39th International Conference on Software Engineering, ICSE 2017, Buenos Aires, Argentina, May 20-28, 2017, 2017. Google Scholar
  17. Chris Lattner, Andrew Lenharth, and Vikram Adve. Making Context-Sensitive Points-to Analysis with Heap Cloning Practical For The Real World. In Proc. of the 2007 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI '07, New York, NY, USA, 2007. ACM. Google Scholar
  18. Yue Li, Tian Tan, Yulei Sui, and Jingling Xue. Self-inferencing reflection resolution for Java. In Proc. of the 28th European Conf. on Object-Oriented Programming, ECOOP '14, pages 27-53. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44202-9.
  19. Yue Li, Tian Tan, and Jingling Xue. Effective soundness-guided reflection analysis. In Sandrine Blazy and Thomas Jensen, editors, Static Analysis - 22nd International Symposium, SAS 2015, Saint-Malo, France, September 9-11, 2015, Proceedings, volume 9291 of Lecture Notes in Computer Science, pages 162-180. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48288-9_10.
  20. Benjamin Livshits. Improving Software Security with Precise Static and Runtime Analysis. PhD thesis, Stanford University, December 2006. Google Scholar
  21. Benjamin Livshits, Manu Sridharan, Yannis Smaragdakis, Ondřej Lhoták, J. Nelson Amaral, Bor-Yuh Evan Chang, Samuel Z. Guyer, Uday P. Khedker, Anders Møller, and Dimitrios Vardoulakis. In defense of soundiness: A manifesto. Commun. ACM, 58(2):44-46, 2015. URL: http://dx.doi.org/10.1145/2644805.
  22. Benjamin Livshits, John Whaley, and Monica S. Lam. Reflection analysis for Java. In Proc. of the 3rd Asian Symp. on Programming Languages and Systems, pages 139-160. Springer, 2005. URL: http://dx.doi.org/10.1007/11575467_11.
  23. 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. URL: http://dx.doi.org/10.1145/1044834.1044835.
  24. Durica Nikolić and Fausto Spoto. Definite expression aliasing analysis for Java bytecode. In Theoretical Aspects of Computing - ICTAC 2012 - 9th International Colloquium, Bangalore, India, September 24-27, 2012. Proceedings, volume 7521 of ICTAC '12, pages 74-89. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32943-2_6.
  25. Xavier Rival. Comment on "what is soundness in static analysis post", in the PL Enthusiast blog. http://www.pl-enthusiast.net/2017/10/23/what-is-soundness-in-static-analysis/#comment-1265, 2017.
  26. Bernhard Scholz, Herbert Jordan, Pavle Subotic, and Till Westmann. On fast large-scale program analysis in datalog. In Proceedings of the 25th International Conference on Compiler Construction, CC 2016, Barcelona, Spain, March 12-18, 2016, pages 196-206, 2016. URL: http://dx.doi.org/10.1145/2892208.2892226.
  27. Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. In Steven S. Muchnick and Neil D. Jones, editors, Program flow analysis: theory and applications, chapter 7, pages 189-233. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1981. Google Scholar
  28. Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, may 1991. Google Scholar
  29. Yannis Smaragdakis, George Balatsouras, George Kastrinis, and Martin Bravenboer. More sound static handling of Java reflection. In Proc. of the Asian Symp. on Programming Languages and Systems, APLAS '15. Springer, 2015. Google Scholar
  30. Yannis Smaragdakis, Martin Bravenboer, and Ondřej Lhoták. Pick your contexts well: Understanding object-sensitivity. In Proc. of the 38th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL '11, pages 17-30, New York, NY, USA, 2011. ACM. Google Scholar
  31. Yannis Smaragdakis, George Kastrinis, and George Balatsouras. Introspective analysis: Context-sensitivity, across the board. In Proc. of the 2014 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI '14, pages 485-495, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2594291.2594320.
  32. Johannes Späth, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. Boomerang: Demand-driven flow- and context-sensitive pointer analysis for java. In Shriram Krishnamurthi and Benjamin S. Lerner, editors, 30th European Conference on Object-Oriented Programming, ECOOP 2016, July 18-22, 2016, Rome, Italy, volume 56 of LIPIcs, pages 22:1-22:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://www.dagstuhl.de/dagpub/978-3-95977-014-9, URL: http://dx.doi.org/10.4230/LIPIcs.ECOOP.2016.22.
  33. Vugranam C. Sreedhar, Michael Burke, and Jong-Deok Choi. A framework for interprocedural optimization in the presence of dynamic class loading. In Proc. of the 2000 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI '00, pages 196-207, New York, NY, USA, 2000. ACM. Google Scholar
  34. Bjarne Steensgaard. Points-to analysis in almost linear time. In POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 32-41, 1996. Google Scholar
  35. Xin Zheng and Radu Rugina. Demand-driven alias analysis for C. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7-12, 2008, POPL '08, pages 197-208, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1328438.1328464.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact