Document Open Access Logo

Qilin: A New Framework For Supporting Fine-Grained Context-Sensitivity in Java Pointer Analysis

Authors Dongjie He, Jingbo Lu, Jingling Xue

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2022.30.pdf
  • Filesize: 1.24 MB
  • 29 pages

Document Identifiers

Author Details

Dongjie He
  • The University of New South Wales, Sydney, Australia
Jingbo Lu
  • The University of New South Wales, Sydney, Australia
Jingling Xue
  • The University of New South Wales, Sydney, Australia

Funding

Supported by ARC Grants DP180104069 and DP210102409.

Acknowledgements

We thank all the reviewers for their constructive comments.

Cite As Get BibTex

Dongjie He, Jingbo Lu, and Jingling Xue. Qilin: A New Framework For Supporting Fine-Grained Context-Sensitivity in Java Pointer Analysis. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 30:1-30:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ECOOP.2022.30

Abstract

Existing whole-program context-sensitive pointer analysis frameworks for Java, which were open-sourced over one decade ago, were designed and implemented to support only method-level context-sensitivity (where all the variables/objects in a method are qualified by a common context abstraction representing a context under which the method is analyzed). We introduce Qilin as a generalized (modern) alternative, which has been open-sourced on GitHub, to support the current research trend on exploring fine-grained context-sensitivity (including variable-level context-sensitivity where different variables/objects in a method can be analyzed under different context abstractions at the variable level), precisely, efficiently, and modularly. To meet these four design goals, Qilin is developed as an imperative framework (implemented in Java) consisting of a fine-grained pointer analysis kernel with parameterized context-sensitivity that supports on-the-fly call graph construction and exception analysis, solved iteratively based on a new carefully-crafted incremental worklist-based constraint solver, on top of its handlers for complex Java features.
We have evaluated Qilin extensively using a set of 12 representative Java programs (popularly used in the literature). For method-level context-sensitive analyses, we compare Qilin with Doop (a declarative framework that defines the state-of-the-art), Qilin yields logically the same precision but more efficiently (e.g., 2.4x faster for four typical baselines considered, on average). For fine-grained context-sensitive analyses (which are not currently supported by open-source Java pointer analysis frameworks such as Doop), we show that Qilin allows seven recent approaches to be instantiated effectively in our parameterized framework, requiring additionally only an average of 50 LOC each.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program analysis
Keywords
  • Pointer Analysis
  • Fine-Grained Context Sensitivity

Metrics

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

Supplementary Materials

References

  1. Karim Ali and Ondřej Lhoták. Application-only call graph construction. In ECOOP 2012 - Object-Oriented Programming, pages 688-712, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  2. Lars Ole Andersen. Program analysis and specialization for the C programming language. PhD thesis, University of Cophenhagen, 1994. Google Scholar
  3. Tony Antoniadis, Konstantinos Triantafyllou, and Yannis Smaragdakis. Porting Doop to Soufflé: A tale of inter-engine portability for datalog-based analyses. In Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis, pages 25-30, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3088515.3088522.
  4. 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, pages 259-269, New York, NY, USA, 2014. Association for Computing Machinery. Google Scholar
  5. 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 DaCapo benchmarks: 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. Google Scholar
  6. 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. Google Scholar
  7. 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, pages 1-12, New York, NY, USA, 2009. Association for Computing Machinery. Google Scholar
  8. 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. Google Scholar
  9. Jeff Da Silva and J. Gregory Steffan. A probabilistic pointer analysis for speculative optimizations. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 416-425, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1168857.1168908.
  10. Gang Fan, Rongxin Wu, Qingkai Shi, Xiao Xiao, Jinguo Zhou, and Charles Zhang. SMOKE: Scalable path-sensitive memory leak detection for millions of lines of code. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pages 72-82, New York, NY, USA, 2019. IEEE. URL: https://doi.org/10.1109/ICSE.2019.00025.
  11. Xiaokang Fan, Yulei Sui, Xiangke Liao, and Jingling Xue. Boosting the precision of virtual call integrity protection with partial pointer analysis for C++. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 329-340, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3092703.3092729.
  12. Christian Fecht and Helmut Seidl. Propagating differences: An efficient new fixpoint algorithm for distributive constraint systems. In European Symposium on Programming, pages 90-104. Springer, 1998. Google Scholar
  13. Neville Grech and Yannis Smaragdakis. P/Taint: Unified points-to and taint analysis. Proceedings of the ACM on Programming Languages, 1(OOPSLA), October 2017. URL: https://doi.org/10.1145/3133926.
  14. Dongjie He, Jingbo Lu, Yaoqing Gao, and Jingling Xue. Accelerating object-sensitive pointer analysis by exploiting object containment and reachability. In Proceedings of the 35th European Conference on Object-Oriented Programming (ECOOP 2021), pages 18:1-18:31, Dagstuhl, Germany, 2021. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  15. Dongjie He, Jingbo Lu, and Jingling Xue. Context debloating for object-sensitive pointer analysis. In 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 79-91. IEEE, 2021. Google Scholar
  16. IBM. WALA: T.J. Watson Libraries for Analysis, 2020. URL: http://wala.sourceforge.net/.
  17. 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. Google Scholar
  18. Minseok Jeon, Myungho Lee, and Hakjoo Oh. Learning graph-based heuristics for pointer analysis without handcrafting application-specific features. Proceedings of the ACM on Programming Languages, 4(OOPSLA):1-30, 2020. Google Scholar
  19. 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. Google Scholar
  20. Herbert Jordan, Bernhard Scholz, and Pavle Subotić. Soufflé: On synthesis of program analyzers. In Computer Aided Verification, pages 422-430, Cham, 2016. Springer International Publishing. Google Scholar
  21. Timotej Kapus and Cristian Cadar. A segmented memory model for symbolic execution. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 774-784, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3338906.3338936.
  22. 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, pages 423-434, New York, NY, USA, 2013. Association for Computing Machinery. Google Scholar
  23. 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. Google Scholar
  24. 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), October 2008. URL: https://doi.org/10.1145/1391984.1391987.
  25. 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. Google Scholar
  26. Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. Scalability-first pointer analysis with self-tuning context-sensitivity. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 129-140, New York, NY, USA, 2018. Association for Computing Machinery. Google Scholar
  27. Bozhen Liu and Jeff Huang. D4: Fast concurrency debugging with parallel differential analysis. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 359-373, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3192366.3192390.
  28. 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 (TOSEM), 30(4):1-46, 2021. Google Scholar
  29. Jingbo Lu, Dongjie He, and Jingling Xue. Selective context-sensitivity for k-CFA with CFL-reachability. In International Static Analysis Symposium, pages 261-285. Springer, 2021. Google Scholar
  30. 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. Google Scholar
  31. Magnus Madsen, Ming-Ho Yee, and Ondřej Lhoták. From Datalog to flix: A declarative language for fixed points on lattices. ACM SIGPLAN Notices, 51(6):194-208, 2016. Google Scholar
  32. Ana Milanova, Atanas Rountev, and Barbara G Ryder. Parameterized object sensitivity for points-to and side-effect analyses for Java. In Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, pages 1-11, New York, NY, USA, 2002. Association for Computing Machinery. Google Scholar
  33. 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. Google Scholar
  34. 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. Google Scholar
  35. David J Pearce, Paul HJ Kelly, and Chris Hankin. Online cycle detection and difference propagation for pointer analysis. In Proceedings Third IEEE International Workshop on Source Code Analysis and Manipulation, pages 3-12. IEEE, 2003. Google Scholar
  36. Zoltán Porkoláb, Tibor Brunner, Dániel Krupp, and Márton Csordás. Codecompass: An open software comprehension framework for industrial usage. In Proceedings of the 26th Conference on Program Comprehension, pages 361-369, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3196321.3197546.
  37. Jyoti Prakash, Abhishek Tiwari, and Christian Hammer. Effects of program representation on pointer analyses - an empirical study. Fundamental Approaches to Software Engineering, 12649:240, 2021. Google Scholar
  38. Michael Reif, Michael Eichberg, Ben Hermann, Johannes Lerch, and Mira Mezini. Call graph construction for Java libraries. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 474-486, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2950290.2950312.
  39. Bernhard Scholz, Herbert Jordan, Pavle Subotić, and Till Westmann. On fast large-scale program analysis in Datalog. In Proceedings of the 25th International Conference on Compiler Construction, CC 2016, pages 196-206, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2892208.2892226.
  40. Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189-234. Prentice-Hall, 1981. Google Scholar
  41. Olin Shivers. Control-flow analysis of higher-order languages. PhD thesis, Citeseer, 1991. Google Scholar
  42. 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. Google Scholar
  43. 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. Google Scholar
  44. 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. Google Scholar
  45. 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. Google Scholar
  46. 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. Google Scholar
  47. Yulei Sui, Yue Li, and Jingling Xue. Query-directed adaptive heap cloning for optimizing compilers. In Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 1-11, New York, NY, USA, 2013. IEEE. URL: https://doi.org/10.1109/CGO.2013.6494978.
  48. 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. Google Scholar
  49. 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. Google Scholar
  50. 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, pages 263-277, New York, NY, USA, 2017. Association for Computing Machinery. Google Scholar
  51. David Trabish, Timotej Kapus, Noam Rinetzky, and Cristian Cadar. Past-sensitive pointer analysis for symbolic execution. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 197-208, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3368089.3409698.
  52. David Trabish, Andrea Mattavelli, Noam Rinetzky, and Cristian Cadar. Chopped symbolic execution. In Proceedings of the 40th International Conference on Software Engineering, pages 350-360, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3180155.3180251.
  53. 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. Google Scholar
  54. Raja Vallee-Rai and Laurie J. Hendren. Jimple: Simplifying java bytecode for analyses and transformations, 1998. Google Scholar
  55. Hua Yan, Yulei Sui, Shiping Chen, and Jingling Xue. Spatio-temporal context reduction: A pointer-analysis-based static approach for detecting use-after-free vulnerabilities. In 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE), pages 327-337, New York, NY, USA, 2018. IEEE. URL: https://doi.org/10.1145/3180155.3180178.
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