Document Open Access Logo

Accelerating Object-Sensitive Pointer Analysis by Exploiting Object Containment and Reachability

Authors Dongjie He, Jingbo Lu, Yaoqing Gao, Jingling Xue

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2021.16.pdf
  • Filesize: 1.49 MB
  • 31 pages

Document Identifiers

Author Details

Dongjie He
  • University of New South Wales, Sydney, Australia
Jingbo Lu
  • University of New South Wales, Sydney, Australia
Yaoqing Gao
  • Huawei, Toronto, Canada
Jingling Xue
  • University of New South Wales, Sydney, Australia

Funding

This work is supported by an ARC DP grant (DP180104069) and a UNSW-Huawei research grant (YBN2019105002).

Acknowledgements

We thank the reviewers for their constructive comments.

Cite As Get BibTex

Dongjie He, Jingbo Lu, Yaoqing Gao, and Jingling Xue. Accelerating Object-Sensitive Pointer Analysis by Exploiting Object Containment and Reachability. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 16:1-16:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECOOP.2021.16

Abstract

Object-sensitive pointer analysis for an object-oriented program can be accelerated if context-sensitivity can be selectively applied to some precision-critical variables/objects in the program. Existing pre-analyses, which are performed to make such selections, either preserve precision but achieve limited speedups by reasoning about all the possible value flows in the program conservatively or achieve greater speedups but sacrifice precision (often unduly) by examining only some but not all the value flows in the program heuristically. In this paper, we introduce a new approach, named Turner, that represents a sweet spot between the two existing ones, as it is designed to enable object-sensitive pointer analysis to run significantly faster than the former approach and achieve significantly better precision than the latter approach. Turner is simple, lightweight yet effective due to two novel aspects in its design. First, we exploit a key observation that some precision-uncritical objects can be approximated based on the object-containment relationship pre-established (by applying Andersen’s analysis). This approximation introduces a small degree yet the only source of imprecision into Turner. Second, leveraging this initial approximation, we introduce a simple DFA to reason about object reachability for a method intra-procedurally from its entry to its exit along all the possible value flows established by its statements to finalize its precision-critical variables/objects identified. We have validated Turner with an implementation in Soot against the state of the art using a set of 12 popular Java benchmarks and applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program analysis
Keywords
  • Object-Sensitive Pointer Analysis
  • CFL Reachability
  • Object Containment

Metrics

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

Supplementary Materials

References

  1. Lars Ole Andersen. Program analysis and specialization for the C programming language. PhD thesis, University of Cophenhagen, 1994. Google Scholar
  2. 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 Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, page 259–269, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2666356.2594299.
  3. Stephen M. Blackburn, Robin Garner, Chris Hoffmann, Asjad M. Khang, Kathryn S. McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z. Guyer, Martin Hirzel, Antony Hosking, Maria Jump, Han Lee, J. Eliot B. Moss, Aashish Phansalkar, Darko Stefanović, Thomas VanDrunen, Daniel von Dincklage, and Ben Wiedermann. The DaCapobenchmarks: Java benchmarking development and analysis. In Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, pages 169-190, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1167515.1167488.
  4. Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders. In Proceedings of the 33rd International Conference on Software Engineering, pages 241-250, Honolulu, HI, USA, 2011. IEEE. URL: https://doi.org/10.1145/1985793.1985827.
  5. Martin Bravenboer and Yannis Smaragdakis. Exception analysis and points-to analysis: Better together. In Proceedings of the 18th International Symposium on Software Testing and Analysis, page 1–12, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1572272.1572274.
  6. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, pages 243-262, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1639949.1640108.
  7. IBM T.J. Watson Research Center. WALA: T.J. Watson Libraries for Analysis, 2020. URL: http://wala.sourceforge.net/.
  8. Stephen J Fink, Eran Yahav, Nurit Dor, G Ramalingam, and Emmanuel Geay. Effective typestate verification in the presence of aliasing. ACM Transactions on Software Engineering and Methodology, 17(2):1-34, 2008. URL: https://doi.org/10.1145/1348250.1348255.
  9. Behnaz Hassanshahi, Raghavendra Kagalavadi Ramesh, Padmanabhan Krishnan, Bernhard Scholz, and Yi Lu. An efficient tunable selective points-to analysis for large codebases. In Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis, page 13–18, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3088515.3088519.
  10. Dongjie He, Haofeng Li, Lei Wang, Haining Meng, Hengjie Zheng, Jie Liu, Shuangwei Hu, Lian Li, and Jingling Xue. Performance-boosting sparsification of the IFDS algorithm with applications to taint analysis. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 267-279, San Diego, CA, USA, 2019. IEEE. URL: https://doi.org/10.1109/ASE.2019.00034.
  11. Dongjie He, Lian Li, Lei Wang, Hengjie Zheng, Guangwei Li, and Jingling Xue. Understanding and detecting evolution-induced compatibility issues in Android apps. In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 167-177, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3238147.3238185.
  12. Minseok Jeon, Sehun Jeong, and Hakjoo Oh. Precise and scalable points-to analysis via data-driven context tunneling. Proceedings of the ACM on Programming Languages, 2(OOPSLA):1-29, 2018. URL: https://doi.org/10.1145/3276510.
  13. Sehun Jeong, Minseok Jeon, Sungdeok Cha, and Hakjoo Oh. Data-driven context-sensitivity for points-to analysis. Proceedings of the ACM on Programming Languages, 1(OOPSLA):100, 2017. URL: https://doi.org/10.1145/3133924.
  14. George Kastrinis and Yannis Smaragdakis. Hybrid context-sensitivity for points-to analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, page 423–434, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2499370.2462191.
  15. John Kodumal and Alex Aiken. The set constraint/cfl reachability connection in practice. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pages 207-218, New York, NY, USA, 2004. ACM. URL: https://doi.org/10.1145/996893.996867.
  16. Prasanna Kumar K., Amitabha Sanyal, and Amey Karkare. Liveness-based garbage collection for lazy languages. In Proceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management, ISMM 2016, page 122–133, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2926697.2926698.
  17. Ondřej Lhoták and Laurie Hendren. Scaling Java points-to analysis using spark. In International Conference on Compiler Construction, pages 153-169, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. URL: https://doi.org/10.5555/1765931.1765948.
  18. Lian Li, Cristina Cifuentes, and Nathan Keynes. Boosting the performance of flow-sensitive points-to analysis using value flow. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering, pages 343-353, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/2025113.2025160.
  19. Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. Precision-guided context sensitivity for pointer analysis. Proceedings of the ACM on Programming Languages, 2(OOPSLA):1-29, 2018. URL: https://doi.org/10.1145/3276511.
  20. Yue Li, Tian Tan, Yifei Zhang, and Jingling Xue. Program tailoring: Slicing by sequential criteria. In 30th European Conference on Object-Oriented Programming, pages 15:1-15:27, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ECOOP.2016.15.
  21. Jingbo Lu, Dongjie He, and Jingling Xue. Eagle: CFL-reachability-based precision-preserving acceleration of object-sensitive pointer analysis with partial context sensitivity. ACM Transactions on Software Engineering and Methodology, 2021. To appear. Google Scholar
  22. Jingbo Lu and Jingling Xue. Precision-preserving yet fast object-sensitive pointer analysis with partial context sensitivity. Proceedings of the ACM on Programming Languages, 3(OOPSLA):1-29, 2019. URL: https://doi.org/10.1145/3360574.
  23. Ana Milanova, Atanas Rountev, and Barbara G Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Transactions on Software Engineering and Methodology, 14(1):1-41, 2005. URL: https://doi.org/10.1145/1044834.1044835.
  24. Mehryar Mohri and Mark-Jan Nederhof. Regular approximation of context-free grammars through transformation. In Jean-Claude Junqua and Gertjan van Noord, editors, Robustness in Language and Speech Technology, pages 153-163. Springer Netherlands, Dordrecht, 2001. URL: https://doi.org/10.1007/978-94-015-9719-7_6.
  25. Mayur Naik, Alex Aiken, and John Whaley. Effective static race detection for Java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 308-319, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1133255.1134018.
  26. Thomas Reps. Program analysis via graph reachability. Information and software technology, 40(11-12):701-726, 1998. URL: https://doi.org/10.1016/S0950-5849(98)00093-7.
  27. Thomas Reps. Undecidability of context-sensitive data-dependence analysis. ACM Transactions on Programming Languages and Systems, 22(1):162-186, 2000. URL: https://doi.org/10.1145/345099.345137.
  28. Lei Shang, Xinwei Xie, and Jingling Xue. On-demand dynamic summary-based points-to analysis. In Proceedings of the Tenth International Symposium on Code Generation and Optimization, pages 264-274, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2259016.2259050.
  29. Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. New York University. Courant Institute of Mathematical Sciences , 1978. Google Scholar
  30. Yannis Smaragdakis. Doop-framework for Java pointer and taint analysis (using p/taint), 2021. URL: https://bitbucket.org/yanniss/doop/.
  31. Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. Pick your contexts well: understanding object-sensitivity. In Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 17-30, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1925844.1926390.
  32. Yannis Smaragdakis, George Kastrinis, and George Balatsouras. Introspective analysis: context-sensitivity, across the board. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 485-495, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2594291.2594320.
  33. 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, pages 22:1-22:26, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ECOOP.2016.22.
  34. Manu Sridharan and Rastislav Bodík. Refinement-based context-sensitive points-to analysis for Java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, page 387–400, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1133255.1134027.
  35. 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, Berlin, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-36946-9_8.
  36. Manu Sridharan, Stephen J Fink, and Rastislav Bodik. Thin slicing. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 112-122, New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1250734.1250748.
  37. Manu Sridharan, Denis Gopan, Lexin Shan, and Rastislav Bodík. Demand-driven points-to analysis for Java. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, page 59–76, New York, NY, USA, 2005. Association for Computing Machinery. URL: https://doi.org/10.1145/1103845.1094817.
  38. Yulei Sui and Jingling Xue. On-demand strong update analysis via value-flow refinement. In Proceedings of the 2016 24th ACM SIGSOFT international symposium on foundations of software engineering, pages 460-473, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2950290.2950296.
  39. T. Tan, Y. Li and J. Xue. Efficient and precise points-to analysis: modeling the heap by merging equivalent automata. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 278-291, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3140587.3062360.
  40. Tian Tan, Yue Li, and Jingling Xue. Making k-object-sensitive pointer analysis more precise with still k-limiting. In International Static Analysis Symposium, pages 489-510, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-662-53413-7_24.
  41. Rei Thiessen and Ondřej Lhoták. Context transformations for pointer analysis. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, page 263–277, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3140587.3062359.
  42. Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot: A Java bytecode optimization framework. In CASCON First Decade High Impact Papers, pages 214-224. IBM Corp., USA, 2010. URL: https://doi.org/10.5555/781995.782008.
  43. Shiyi Wei and Barbara G Ryder. Adaptive context-sensitive analysis for JavaScript. In 29th European Conference on Object-Oriented Programming, pages 712-734, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ECOOP.2015.712.
  44. John Whaley and Monica S Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 131-144, New York, NY, USA, 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/996841.996859.
  45. Dacong Yan, Guoqing Xu, and Atanas Rountev. Demand-driven context-sensitive alias analysis for Java. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, pages 155-165, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/2001420.2001440.
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