Evaluating the precision of static reference analysis using profiling
Pages 22 - 32
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.
[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.
[4]
M. Das. Unification-based pointer analysis with directional assignments. In Proceedings of 2000 Conference on Programming Language Design and Implementation, June 2000.
[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.
[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.
[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.
[8]
D. Liang and M. J. Harrold. Efficient points-to analysis for whole-program analysis. In 7th ESEC/FSE, pages 199-215, Sept. 1999.
[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.
[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.
[11]
G. Ramalingam. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems, 16(5):1467-1471, Sept. 1994.
[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.
[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.
[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.
[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.
[17]
M. Streckenbach and G. Snelting. Points-to for java: A general framework and an empirical comparison. Technical report, University Passau, Nov. 2000.
- Evaluating the precision of static reference analysis using profiling
Recommendations
Evaluating the precision of static reference analysis using profiling
ISSTA '02: Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysisProgram 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 AnalysisWe 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 EngineeringWe 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
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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 July 2002
Published in SIGSOFT Volume 27, Issue 4
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations18Total Citations
- 512Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in