article

Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs

Authors:

Donglin Liang,

Maikel Pennings,

Mary Jean HarroldAuthors Info & Claims

ACM SIGSOFT Software Engineering Notes, Volume 31, Issue 1

Pages 6 - 12

https://doi.org/10.1145/1108768.1108797

Published: 05 September 2005 Publication History

Get Access

Abstract

Program analysis and program optimization of Java programs require reference information that estimates the instances of classes that may be accessed through dereferences. Recent work has presented several approaches for adapting Andersen's algorithm [1]---the most precise flow-insensitive and context-insensitive points-to analysis algorithm developed for C--- for analyzing Java programs (e.g., [5, 9, 12]). Studies in our previous work [6] indicate that this algorithm may compute very imprecise reference information for Java programs.

References

[1]

L. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, May 1994.

Google Scholar

[2]

S. Guyer and C. Lin. Client-driven pointer analysis. In Static Analysis Symposium, 2003.

Digital Library

Google Scholar

[3]

M. Hind. Pointer analysis: Haven't we solved this problem yet? In ACM Workshop on Program Analysis for Software Tools and Engineering, pages 54--61, 2001.

Digital Library

Google Scholar

[4]

D. Liang and M. J. Harrold. Light-weight context recovery for efficient and accurate program analyses. In 22nd International Conference on Software Engineering, pages 366--375, June 2000.

Digital Library

Google Scholar

[5]

D. Liang, M. Pennings, and M. J. Harrold. Extending and evaluating flow-insensitive and context-insensitive points-to analyses for java. In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, June 2001.

Digital Library

Google Scholar

[6]

D. Liang, M. Pennings, and M. J. Harrold. Evaluating the precision of static reference analysis using profiling. In Proceedings of International Symposium on Software Testing and Analysis (ISSTA'02), July 2002.

Digital Library

Google Scholar

[7]

A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to and side-effect analyses for java. In Proceedings of International Symposium on Software Testing and Analysis (ISSTA'02), July 2002.

Digital Library

Google Scholar

[8]

A. Rountev and S. Chandra. Off-line variable substitution for scaling points-to analysis. In Proceedings of 2000 Conference on Programming Language Design and Implementation, June 2000.

Digital Library

Google Scholar

[9]

A. Rountev, A. Milanova, and B. G. Ryder. Points-to analysis for java based on annotated constraints. In Conference on Object-oriented programming, systems, languages, and applications, Oct. 2001.

Digital Library

Google Scholar

[10]

E. Ruf. Context-insensitive alias analysis reconsidered. In Proceedings of SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 13--23, June 1995.

Digital Library

Google Scholar

[11]

M. Sharir and A. Pnueli. Two approaches to interprocedural data-flow analysis. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Application, pages 189--223. 1981.

Google Scholar

[12]

M. Streckenbach and G. Snelting. Points-to for java: A general framework and an empirical comparison. Technical report, University Passau, Nov. 2000.

Google Scholar

[13]

Z. Su, M. Fhndrich, and A. Aiken. Projection merging: Reducing redundancies in inclusion constraint graphs. In In the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'00), January 2000.

Digital Library

Google Scholar

[14]

J. Whaley and M. Lam. Cloning-based context-sensitive pointer alias analysis using bdds. In PLDI'04, 2004.

Digital Library

Google Scholar

Cited By

View all

Gilray TAdams MMight M(2016)Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysisACM SIGPLAN Notices10.1145/3022670.295193651:9(407-420)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/3022670.2951936
Gilray TAdams MMight MGarrigue JKeller GSumii E(2016)Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysisProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951936(407-420)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/2951913.2951936
Qian JChen LXu BZhang X(2011)Contribution-based call stack abstraction for call string based pointer analysisInformation and Software Technology10.1016/j.infsof.2010.11.00453:6(654-665)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.infsof.2010.11.004
Show More Cited By

Index Terms

Recommendations

Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs
PASTE '05: Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

Program analysis and program optimization of Java programs require reference information that estimates the instances of classes that may be accessed through dereferences. Recent work has presented several approaches for adapting Andersen's algorithm [1]...
Selective context-sensitivity guided by impact pre-analysis
PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation

We present a method for selectively applying context-sensitivity during interprocedural program analysis. Our method applies context-sensitivity only when and where doing so is likely to improve the precision that matters for resolving given queries. ...
Selective context-sensitivity guided by impact pre-analysis
PLDI '14

We present a method for selectively applying context-sensitivity during interprocedural program analysis. Our method applies context-sensitivity only when and where doing so is likely to improve the precision that matters for resolving given queries. ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGSOFT Software Engineering Notes

ACM SIGSOFT Software Engineering Notes Volume 31, Issue 1

January 2006

203 pages

ISSN:0163-5948

DOI:10.1145/1108768

Issue’s Table of Contents

PASTE '05: Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering
September 2005
118 pages
ISBN:1595932399
DOI:10.1145/1108792
Editors:
Michael Ernst
MIT
,
Thomas Jensen
CNRS

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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 September 2005

Published in SIGSOFT Volume 31, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
351
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gilray TAdams MMight M(2016)Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysisACM SIGPLAN Notices10.1145/3022670.295193651:9(407-420)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/3022670.2951936
Gilray TAdams MMight MGarrigue JKeller GSumii E(2016)Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysisProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951936(407-420)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/2951913.2951936
Qian JChen LXu BZhang X(2011)Contribution-based call stack abstraction for call string based pointer analysisInformation and Software Technology10.1016/j.infsof.2010.11.00453:6(654-665)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.infsof.2010.11.004
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
Jeon MJeong SCha SOh H(2019)A Machine-Learning Algorithm with Disjunctive Model for Data-Driven Program AnalysisACM Transactions on Programming Languages and Systems10.1145/329360741:2(1-41)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3293607
Jeon MJeong SOh H(2018)Precise and scalable points-to analysis via data-driven context tunnelingProceedings of the ACM on Programming Languages10.1145/32765102:OOPSLA(1-29)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276510
GILRAY TADAMS MMIGHT M(2018)Abstract allocation as a unified approach to polyvariance in control-flow analysesJournal of Functional Programming10.1017/S095679681800013828Online publication date: 1-Aug-2018
https://doi.org/10.1017/S0956796818000138
Jeong SJeon MCha SOh H(2017)Data-driven context-sensitivity for points-to analysisProceedings of the ACM on Programming Languages10.1145/31339241:OOPSLA(1-28)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133924
Gilray TAdams MMight M(2016)Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysisACM SIGPLAN Notices10.1145/3022670.295193651:9(407-420)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/3022670.2951936
Gilray TAdams MMight MGarrigue JKeller GSumii E(2016)Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysisProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming10.1145/2951913.2951936(407-420)Online publication date: 4-Sep-2016
https://dl.acm.org/doi/10.1145/2951913.2951936
Show More Cited By

View Options

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations