Document Open Access Logo

Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java

Authors Johannes Späth, Lisa Nguyen Quang Do, Karim Ali, Eric Bodden

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2016.22.pdf
  • Filesize: 1.83 MB
  • 26 pages

Document Identifiers

Author Details

Johannes Späth
Lisa Nguyen Quang Do
Karim Ali
Eric Bodden

Cite As Get BibTex

Johannes Späth, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 22:1-22:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ECOOP.2016.22

Abstract

Many current program analyses require highly precise pointer
information about small, tar- geted parts of a given program. This
motivates the need for demand-driven pointer analyses that compute
information only where required. Pointer analyses generally compute
points-to sets of program variables or answer boolean alias
queries. However, many client analyses require richer pointer
information. For example, taint and typestate analyses often need to
know the set of all aliases of a given variable under a certain
calling context. With most current pointer analyses, clients must
compute such information through repeated points-to or alias queries, increasing complexity and computation time for them.

This paper presents Boomerang, a demand-driven, flow-, field-, and
context-sensitive pointer analysis for Java programs. Boomerang
computes rich results that include both the possible allocation sites of a given pointer (points-to information) and all pointers that can point to those allocation sites (alias information). For increased precision and scalability, clients can query Boomerang with respect to particular calling contexts of interest.

Our experiments show that Boomerang is more precise than existing
demand-driven pointer analyses. Additionally, using Boomerang, the
taint analysis FlowDroid issues up to 29.4x fewer pointer queries
compared to using other pointer analyses that return simpler pointer
infor- mation. Furthermore, the search space of Boomerang can be
significantly reduced by requesting calling contexts from the client
analysis.

Subject Classification

Keywords
  • Demand-Driven; Static Analysis; IFDS; Aliasing; Points-to Analysis

Metrics

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

Supplementary Materials

References

  1. Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. FlowDroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps. In PLDI, page 29, 2014. Google Scholar
  2. Marc Berndl, Ondřej Lhoták, Feng Qian, Laurie Hendren, and Navindra Umanee. Points-to analysis using BDDs. In PLDI, pages 103-114. ACM Press, 2003. Google Scholar
  3. Eric Bodden. Efficient hybrid typestate analysis by determining continuation-equivalent states. In ICSE, pages 5-14, 2010. Google Scholar
  4. Eric Bodden. Inter-procedural data-flow analysis with IFDS/IDE and Soot. In SOAP 2012, pages 3-8, July 2012. Google Scholar
  5. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In OOPSLA, pages 243-262, 2009. Google Scholar
  6. Arnab De and Deepak D'Souza. Scalable flow-sensitive pointer analysis for Java with strong updates. In ECOOP, pages 665-687, 2012. Google Scholar
  7. Alain Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In PLDI, pages 230-241, 1994. Google Scholar
  8. Rakesh Ghiya and Laurie J. Hendren. Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In POPL, pages 1-15, 1996. Google Scholar
  9. David Grove and Craig Chambers. A framework for call graph construction algorithms. TOPLAS, 23(6), 2001. Google Scholar
  10. Nevin Heintze and Olivier Tardieu. Demand-driven pointer analysis. In PLDI, pages 24-34, 2001. Google Scholar
  11. Michael Hind. Pointer analysis: Haven't we solved this problem yet? In PASTE, pages 54-61, 2001. Google Scholar
  12. Susan Horwitz, Thomas W. Reps, and Shmuel Sagiv. Demand interprocedural dataflow analysis. In FSE, pages 104-115, 1995. Google Scholar
  13. Amey Karkare, Amitabha Sanyal, and Uday P. Khedker. Heap reference analysis for functional programs. CoRR, 2007. Google Scholar
  14. Ondrej Lhoták and Laurie J. Hendren. Scaling Java points-to analysis using SPARK. In CC, pages 153-169, 2003. Google Scholar
  15. 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, January 2015. Google Scholar
  16. Nomair A. Naeem and Ondrej Lhoták. Typestate-like analysis of multiple interacting objects. In OOPSLA, pages 347-366, 2008. Google Scholar
  17. Nomair A. Naeem, Ondrej Lhoták, and Jonathan Rodriguez. Practical extensions to the IFDS algorithm. In CC, pages 124-144, 2010. Google Scholar
  18. Mayur Naik and Alex Aiken. Conditional must not aliasing for static race detection. In POPL, pages 327-338, 2007. Google Scholar
  19. Thomas W. Reps, Susan Horwitz, and Shmuel Sagiv. Precise interprocedural dataflow analysis via graph reachability. In POPL, pages 49-61, 1995. Google Scholar
  20. Cristina Ruggieri and Thomas P. Murtagh. Lifetime analysis of dynamically allocated objects. In POPL, pages 285-293, 1988. Google Scholar
  21. Barbara G. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. In CC, pages 126-137, 2003. Google Scholar
  22. Lei Shang, Xinwei Xie, and Jingling Xue. On-demand dynamic summary-based points-to analysis. In CGO, pages 264-274, 2012. Google Scholar
  23. Manu Sridharan and Rastislav Bodík. Refinement-based context-sensitive points-to analysis for Java. In PLDI, pages 387-400, 2006. Google Scholar
  24. Manu Sridharan, Satish Chandra, Julian Dolby, Stephen J. Fink, and Eran Yahav. Alias analysis for object-oriented programs. In Aliasing in Object-Oriented Programming. Types, Analysis and Verification, pages 196-232. Springer, 2013. Google Scholar
  25. Manu Sridharan, Denis Gopan, Lexin Shan, and Rastislav Bodík. Demand-driven points-to analysis for Java. In OOPSLA, pages 59-76, 2005. Google Scholar
  26. Vijay Sundaresan, Laurie J. Hendren, Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Etienne Gagnon, and Charles Godin. Practical virtual method call resolution for Java. In OOPSLA, pages 264-280, 2000. Google Scholar
  27. Frank Tip and Jens Palsberg. Scalable propagation-based call graph construction algorithms. In OOPSLA, pages 281-293, 2000. Google Scholar
  28. Omer Tripp, Marco Pistoia, Patrick Cousot, Radhia Cousot, and Salvatore Guarnieri. Andromeda: Accurate and scalable security analysis of web applications. In FASE, pages 210-225, 2013. Google Scholar
  29. Raja Vallée-Rai, Etienne Gagnon, Laurie J. Hendren, Patrick Lam, Patrice Pominville, and Vijay Sundaresan. Optimizing Java bytecode using the Soot framework: Is it feasible? In CC, pages 18-34, 2000. Google Scholar
  30. Dacong Yan, Guoqing (Harry) Xu, and Atanas Rountev. Demand-driven context-sensitive alias analysis for Java. In ISSTA, pages 155-165, 2011. Google Scholar
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