More Web Proxy on the site http://driver.im/

Article

Evaluating the precision of static reference analysis using profiling

Authors:

Maikel Pennings,

Mary Jean HarroldAuthors Info & Claims

ISSTA '02: Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis

Pages 22 - 32

https://doi.org/10.1145/566172.566176

Published: 01 July 2002 Publication History

Abstract

Program analyses and optimizations of Java programs require reference information that determines the instances that may be accessed through dereferences. Reference information can be computed using reference analysis. This paper presents a set of studies that evaluate the precision of two existing approaches for identifying instances and one approach for computing reference information in a reference analysis. The studies use dynamic reference information collected during run-time as a lower bound approximation to the precise reference information. The studies measure the precision of an existing approach by comparing the information computed using the approach with the lower bound approximation. The paper also presents case studies that attempt to identify the cases under which an existing approach is not effective. The presented studies provide information that may guide the usage of existing reference-analysis techniques and the development of new reference analysis techniques.

References

[1]

L. Andersen. Program analysis and specialization for the C programming language. Technical Report 94-19, University of Copenhagen, 1994.

[2]

R. Chatterjee, B. G. Ryder, and W. A. Landi. Relevant context inference. In ACM, editor, POPL '99. Proceedings of the 26th ACM SIGPLAN-SIGACT on Principles of programming languages, pages 133-146, Jan. 1999.

Digital Library

[3]

J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages: papers presented at the symposium, Charleston, South Carolina, January 10-13, 1993, pages 232-245, 1993.

Digital Library

[4]

M. Das. Unification-based pointer analysis with directional assignments. In Proceedings of 2000 Conference on Programming Language Design and Implementation, June 2000.

Digital Library

[5]

A. Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 230-241, June 1994.

Digital Library

[6]

L. J. Hendren, J. Hummel, and A. Nicolau. Abstractions for recursive pointer data structures: Improving the analysis of imperative programs. In Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation (PLDI), pages 249-260, San Francisco, California, 17-19 June 1992.

Digital Library

[7]

W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. SIGPLAN Notices, 27(7):235-248, July 1992. Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation.

Digital Library

[8]

D. Liang and M. J. Harrold. Efficient points-to analysis for whole-program analysis. In 7th ESEC/FSE, pages 199-215, Sept. 1999.

Digital Library

[9]

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

[10]

M. Mock, M. Das, C. Chambers, and S. J. Eggers. Dynamic points-to sets: A comparison with static analyses and potentials applications in program understanding and optimization. In 2001 SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 66-72, jun 2001.

Digital Library

[11]

G. Ramalingam. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems, 16(5):1467-1471, Sept. 1994.

Digital Library

[12]

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

[13]

M. Sagiv, T. Reps, and R. Wilhelm. Solving shape-analysis problems in languages with destructive updating. ACM Transactions on Programming Languages and Systems, 20(1):1-50, Jan. 1998.

Digital Library

[14]

M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In ACM, editor, Conference record of POPL '97, the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages: papers presented at the symposium, pages 1-14, 1997.

Digital Library

[15]

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.

[16]

B. Steensgaard. Points-to analysis in almost linear time. In Conference Record of the 23rd ACM Symposium on Principles of Programming Languages, pages 32-41, Jan. 1996.

Digital Library

[17]

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

Cited By

Đekanović PVukasović MBojić D(2024)Model for Evaluating Points-to Analysis in GraalVM Native Image Using Instrumentation-Based ProfilingDisruptive Information Technologies for a Smart Society10.1007/978-3-031-50755-7_47(502-512)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-3-031-50755-7_47
Yu HLi ZHeimdahl MSu Z(2012)Multi-slicing: a compiler-supported parallel approach to data dependence profilingProceedings of the 2012 International Symposium on Software Testing and Analysis10.1145/2338965.2336756(23-33)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1145/2338965.2336756
Liang PTripp ONaik MSagiv M(2010)A dynamic evaluation of the precision of static heap abstractionsACM SIGPLAN Notices10.1145/1932682.186949445:10(411-427)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869494
Show More Cited By

Evaluating the precision of static reference analysis using profiling
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Evaluating the precision of static reference analysis using profiling

Program analyses and optimizations of Java programs require reference information that determines the instances that may be accessed through dereferences. Reference information can be computed using reference analysis. This paper presents a set of ...
Static memory leak detection using full-sparse value-flow analysis
ISSTA 2012: Proceedings of the 2012 International Symposium on Software Testing and Analysis

We introduce a static detector, Saber, for detecting memory leaks in C programs. Leveraging recent advances on sparse pointer analysis, Saber is the first to use a full-sparse value-flow analysis for leak detection. Saber tracks the flow of values from ...
Machine-learning-guided selectively unsound static analysis
ICSE '17: Proceedings of the 39th International Conference on Software Engineering

We present a machine-learning-based technique for selectively applying unsoundness in static analysis. Existing bug-finding static analyzers are unsound in order to be precise and scalable in practice. However, they are uniformly unsound and hence at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA '02: Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis

July 2002

248 pages

ISBN:1581135629

DOI:10.1145/566172

Program Chair:
Phyllis G. Frankl

ACM SIGSOFT Software Engineering Notes Volume 27, Issue 4
July 2002
242 pages
ISSN:0163-5948
DOI:10.1145/566171
Issue’s Table of Contents

Copyright © 2002 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 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]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSTA02

Sponsor:

SIGSOFT

ISSTA02: International Symposium on Software Testing and Analysis ( co-located with WOSP 2002)

July 22 - 24, 2002

Roma, Italy

Acceptance Rates

ISSTA '02 Paper Acceptance Rate 26 of 97 submissions, 27%;

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
512
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Đekanović PVukasović MBojić D(2024)Model for Evaluating Points-to Analysis in GraalVM Native Image Using Instrumentation-Based ProfilingDisruptive Information Technologies for a Smart Society10.1007/978-3-031-50755-7_47(502-512)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-3-031-50755-7_47
Yu HLi ZHeimdahl MSu Z(2012)Multi-slicing: a compiler-supported parallel approach to data dependence profilingProceedings of the 2012 International Symposium on Software Testing and Analysis10.1145/2338965.2336756(23-33)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1145/2338965.2336756
Liang PTripp ONaik MSagiv M(2010)A dynamic evaluation of the precision of static heap abstractionsACM SIGPLAN Notices10.1145/1932682.186949445:10(411-427)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869494
Liang PTripp ONaik MSagiv MCook WClarke SRinard MSullivan KSteinberg D(2010)A dynamic evaluation of the precision of static heap abstractionsProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/1869459.1869494(411-427)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1869459.1869494
Hirzel MDincklage DDiwan AHind M(2007)Fast online pointer analysisACM Transactions on Programming Languages and Systems10.1145/1216374.121637929:2(11-es)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1145/1216374.1216379
Ribeiro CCintra M(2007)Quantifying Uncertainty in Points-To RelationsLanguages and Compilers for Parallel Computing10.1007/978-3-540-72521-3_15(190-204)Online publication date: 2007
https://doi.org/10.1007/978-3-540-72521-3_15
Ribeiro CCintra M(2006)Quantifying uncertainty in points-to relationsProceedings of the 19th international conference on Languages and compilers for parallel computing10.5555/1757112.1757133(190-204)Online publication date: 2-Nov-2006
https://dl.acm.org/doi/10.5555/1757112.1757133
Hackett BAiken AYoung MDevanbu P(2006)How is aliasing used in systems software?Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering10.1145/1181775.1181785(69-80)Online publication date: 5-Nov-2006
https://dl.acm.org/doi/10.1145/1181775.1181785
Liang DPennings MHarrold M(2005)Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programsProceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering10.1145/1108792.1108797(6-12)Online publication date: 5-Sep-2005
https://dl.acm.org/doi/10.1145/1108792.1108797
Liang DPennings MHarrold M(2005)Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programsACM SIGSOFT Software Engineering Notes10.1145/1108768.110879731:1(6-12)Online publication date: 5-Sep-2005
https://dl.acm.org/doi/10.1145/1108768.1108797
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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents