research-article

Context transformations for pointer analysis

Authors:

Ondřej LhotákAuthors Info & Claims

PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 263 - 277

https://doi.org/10.1145/3062341.3062359

Published: 14 June 2017 Publication History

Abstract

Points-to analysis for Java benefits greatly from context sensitivity. CFL-reachability and k-limited context strings are two approaches to obtaining context sensitivity with different advantages: CFL-reachability allows local reasoning about data-value flow and thus is suitable for demand-driven analyses, whereas k-limited analyses allow object sensitivity which is a superior calling context abstraction for object-oriented languages. We combine the advantages of both approaches to obtain a context-sensitive analysis that is as precise as k-limited context strings, but is more efficient to compute. Our key insight is based on a novel abstraction of contexts adapted from CFL-reachability that represents a relation between two calling contexts as a composition of transformations over contexts.

We formulate pointer analysis in an algebraic structure of context transformations, which is a set of functions over calling contexts closed under function composition. We show that the context representation of context-string-based analyses is an explicit enumeration of all input and output values of context transformations. CFL-reachability-based pointer analysis is formulated to use call-strings as contexts, but the context transformations concept can be applied to any context abstraction used in k-limited analyses, including object- and type-sensitive analysis. The result is a more efficient algorithm for computing context-sensitive results for a wide variety of context configurations.

References

[1]

Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D Ullman. Magic sets and other strange ways to implement logic programs (extended abstract). In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, PODS ’86, pages 1–15, New York, NY, USA, 1986. ACM.

Digital Library

[2]

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´c, Thomas Van-Drunen, 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, OOPSLA ’06, pages 169–190, New York, NY, USA, 2006. ACM.

Digital Library

[3]

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, OOPSLA ’09, pages 243–262, New York, NY, USA, 2009. ACM.

Digital Library

[4]

S. Ceri, G. Gottlob, and L. Tanca. What you always wanted to know about Datalog (and never dared to ask). IEEE Transactions on Knowledge and Data Engineering, 1(1):146– 166, March 1989.

Digital Library

[5]

Todd J. Green, Molham Aref, and Grigoris Karvounarakis. LogicBlox, platform and language: A tutorial. In Proceedings of the Second International Conference on Datalog in Academia and Industry, Datalog 2.0’12, pages 1–8, Berlin, Heidelberg, 2012. Springer-Verlag.

Digital Library

[6]

George Kastrinis and Yannis Smaragdakis. Hybrid contextsensitivity for points-to analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, pages 423–434, New York, NY, USA, 2013. ACM.

Digital Library

[7]

Chris Lattner and Vikram Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-directed and Runtime Optimization, CGO ’04, pages 75–, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[8]

Ondˇrej Lhoták and Laurie Hendren. Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Transactions on Software Engineering and Methodology, 18(1):3:1–3:53, October 2008.

Digital Library

[9]

Percy Liang and Mayur Naik. Scaling abstraction refinement via pruning. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, pages 590–601, New York, NY, USA, 2011. ACM.

Digital Library

[10]

Percy Liang, Omer Tripp, and Mayur Naik. Learning minimal abstractions. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11, pages 31–42, New York, NY, USA, 2011. ACM.

Digital Library

[11]

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, January 2005.

Digital Library

[12]

Thomas Reps. Program analysis via graph reachability. Information and Software Technology, 40(11-–12):701–726, 1998.

[13]

Thomas Reps. Undecidability of context-sensitive datadependence analysis. ACM Transactions on Programming Languages and Systems, 22(1):162–186, January 2000.

Digital Library

[14]

Olin Shivers. Control-flow analysis of higher-order languages. PhD thesis, Citeseer, 1991.

Digital Library

[15]

Yannis Smaragdakis, Martin Bravenboer, and Ondˇrej Lhoták. Pick your contexts well: Understanding object-sensitivity. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11, pages 17–30, New York, NY, USA, 2011. ACM.

Digital Library

[16]

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, PLDI ’14, pages 485–495, New York, NY, USA, 2014. ACM.

Digital Library

[17]

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, PLDI ’06, pages 387– 400, New York, NY, USA, 2006. ACM.

Digital Library

[18]

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, OOPSLA ’05, pages 59–76, New York, NY, USA, 2005. ACM.

Digital Library

[19]

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. Springer, 2016.

[20]

Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot - a Java bytecode optimization framework. In Proceedings of the 1999 Conference of the Centre for Advanced Studies on Collaborative Research, CASCON ’99, pages 13–. IBM Press, 1999.

Digital Library

[21]

John Whaley and Monica S. Lam. Cloning-based contextsensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, pages 131–144, New York, NY, USA, 2004. ACM.

Digital Library

[22]

Guoqing Xu and Atanas Rountev. Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis. In Proceedings of the 2008 International Symposium on Software Testing and Analysis, ISSTA ’08, pages 225–236, New York, NY, USA, 2008. ACM.

Digital Library

[23]

Xin Zhang, Ravi Mangal, Radu Grigore, Mayur Naik, and Hongseok Yang. On abstraction refinement for program analyses in Datalog. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, pages 239–248, New York, NY, USA, 2014. ACM.

Digital Library

[24]

Xin Zheng and Radu Rugina. Demand-driven alias analysis for C. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’08, pages 197–208, New York, NY, USA, 2008. ACM.

Digital Library

[25]

Jianwen Zhu and Silvian Calman. Symbolic pointer analysis revisited. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, pages 145–157, New York, NY, USA, 2004. ACM.

Digital Library

Cited By

Wang ZMa PWang HWang S(2024)PP-CSA: Practical Privacy-Preserving Software Call Stack AnalysisProceedings of the ACM on Programming Languages10.1145/36498568:OOPSLA1(1264-1293)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649856
Chen QYu CLiu RZhang CWang YWang KSu TWang L(2024)Evaluating the Effectiveness of Deep Learning Models for Foundational Program Analysis TasksProceedings of the ACM on Programming Languages10.1145/36498298:OOPSLA1(500-528)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649829
He DLu JXue J(2023)IFDS-based Context Debloating for Object-Sensitive Pointer AnalysisACM Transactions on Software Engineering and Methodology10.1145/357964132:4(1-44)Online publication date: 27-May-2023
https://dl.acm.org/doi/10.1145/3579641
Show More Cited By

Index Terms

Context transformations for pointer analysis
1. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis

Recommendations

Context transformations for pointer analysis
PLDI '17

Points-to analysis for Java benefits greatly from context sensitivity. CFL-reachability and k-limited context strings are two approaches to obtaining context sensitivity with different advantages: CFL-reachability allows local reasoning about data-value ...
Making context-sensitive inclusion-based pointer analysis practical for compilers using parameterised summarisation

Because of its high precision as a flow-insensitive pointer analysis, Andersen's analysis has been deployed in some modern optimising compilers. To obtain improved precision, we describe how to add context sensitivity on top of Andersen's analysis. The ...
Flexible pointer analysis using assign-fetch graphs
SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

We propose a new abstraction for pointer analysis that represents reads and writes to memory instead of traditional points-to relations. Compared to points-to graphs, our Assign-Fetch Graph (AFG) leads to concise procedure summaries that can be used in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2017

708 pages

ISBN:9781450349888

DOI:10.1145/3062341

General Chair:
Albert Cohen
Inria, France
,
Program Chair:
Martin Vechev
DeepCode, Switzerland / ETH Zurich, Switzerland

ACM SIGPLAN Notices Volume 52, Issue 6
PLDI '17
June 2017
708 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3140587
Editor:
Matthew Fluet
Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '17

Sponsor:

SIGPLAN

PLDI '17: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 18 - 23, 2017

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
437
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZMa PWang HWang S(2024)PP-CSA: Practical Privacy-Preserving Software Call Stack AnalysisProceedings of the ACM on Programming Languages10.1145/36498568:OOPSLA1(1264-1293)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649856
Chen QYu CLiu RZhang CWang YWang KSu TWang L(2024)Evaluating the Effectiveness of Deep Learning Models for Foundational Program Analysis TasksProceedings of the ACM on Programming Languages10.1145/36498298:OOPSLA1(500-528)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649829
He DLu JXue J(2023)IFDS-based Context Debloating for Object-Sensitive Pointer AnalysisACM Transactions on Software Engineering and Methodology10.1145/357964132:4(1-44)Online publication date: 27-May-2023
https://dl.acm.org/doi/10.1145/3579641
He DLu JGao YXue J(2023)Selecting Context-Sensitivity Modularly for Accelerating Object-Sensitive Pointer AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2022.316223649:2(719-742)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TSE.2022.3162236
Wang W(2023)MPIRace: A Static Data Race Detector for MPI ProgramsLanguages and Compilers for Parallel Computing10.1007/978-3-031-31445-2_6(73-90)Online publication date: 10-May-2023
https://doi.org/10.1007/978-3-031-31445-2_6
Grech NLagouvardos STsatiris ISmaragdakis Y(2022)Elipmoc: advanced decompilation of Ethereum smart contractsProceedings of the ACM on Programming Languages10.1145/35273216:OOPSLA1(1-27)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527321
Jeon MOh H(2022)Return of CFA: call-site sensitivity can be superior to object sensitivity even for object-oriented programsProceedings of the ACM on Programming Languages10.1145/34987206:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498720
Lu JHe DXue J(2021)EagleACM Transactions on Software Engineering and Methodology10.1145/345049230:4(1-46)Online publication date: 23-Jul-2021
https://dl.acm.org/doi/10.1145/3450492
He DLu JXue J(2021)Context Debloating for Object-Sensitive Pointer Analysis2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE51524.2021.9678880(79-91)Online publication date: Nov-2021
https://doi.org/10.1109/ASE51524.2021.9678880
Xu XWang XXue J(2021)Automatic Synthesis of Data-Flow AnalyzersStatic Analysis10.1007/978-3-030-88806-0_22(453-478)Online publication date: 13-Oct-2021
https://doi.org/10.1007/978-3-030-88806-0_22
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents