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

research-article

A dynamic evaluation of the precision of static heap abstractions

Authors:

Mooly SagivAuthors Info & Claims

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Pages 411 - 427

https://doi.org/10.1145/1869459.1869494

Published: 17 October 2010 Publication History

Abstract

The quality of a static analysis of heap-manipulating programs is largely determined by its heap abstraction. Object allocation sites are a commonly-used abstraction, but are too coarse for some clients. The goal of this paper is to investigate how various refinements of allocation sites can improve precision. In particular, we consider abstractions that use call stack, object recency, and heap connectivity information. We measure the precision of these abstractions dynamically for four different clients motivated by concurrency and on nine Java programs chosen from the DaCapo benchmark suite. Our dynamic results shed new light on aspects of heap abstractions that matter for precision, which allows us to more effectively navigate the large space of possible heap abstractions

References

[1]

}}Chord: A static and dynamic program analysis framework for Java. http://code.google.com/p/jchord/.

[2]

}}J. Aldrich, C. Chambers, E. G. Sirer, and S. J. Eggers. Static analyses for eliminating unnecessary synchronization from Java programs. In Proceedings of the 6th Intl. Static Analysis Symp. (SAS), pages 19--38, 1999.

Digital Library

[3]

}}J. Aldrich, E. Sirer, C. Chambers, and S. J. Eggers. Comprehensive synchronization elimination for Java. Science of Computer Programming, 47(2-3):91--120, 2003.

Digital Library

[4]

}}G. Balakrishnan and T. W. Reps. Recency-abstraction for heap-allocated storage. In Proceedings of the 13th Intl. Static Analysis Symp. (SAS), pages 221--239, 2006.

Digital Library

[5]

}}S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovi´c, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21st ACM SIGPLAN Conf. on Object-Oriented Programing Systems, Languages and Applications (OOPSLA), pages 169--190, 2006.

Digital Library

[6]

}}B. Blanchet. Escape analysis for Java: Theory and practice. ACM Transactions on Programming Languages and Systems, 25(6):713--775, 2003.

Digital Library

[7]

}}B. Blanchet. Escape analysis for object-oriented languages: Application to Java. In Proceedings of the 14th ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pages 20--34, 1999.

Digital Library

[8]

}}J. Bogda and U. Holzle. Removing unnecessary synchronization in Java. In Proceedings of the 14th ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pages 35--46, 1999.

Digital Library

[9]

}}S. Chiba and M. Nishizawa. An easy-to-use toolkit for efficient Java bytecode translators. In Proceedings of the 2nd Intl. Conf. on Generative Programming and Component Engineering (GPCE), pages 364--376, 2003.

Digital Library

[10]

}}J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In Proceedings of the ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 258--269, 2002.

Digital Library

[11]

}}B. Dufour, B. G. Ryder, and G. Sevitsky. Blended analysis for performance understanding of framework-based applications. In Proceedings of the ACM SIGSOFT Intl. Symp. on Software Testing and Analysis (ISSTA), pages 118--128, 2007.

Digital Library

[12]

}}B. Dufour, B. G. Ryder, and G. Sevitsky. A scalable technique for characterizing the usage of temporaries in framework intensive Java applications. In Proceedings of the 16th ACM SIGSOFT Intl. Symp. on Foundations of Software Engineering (FSE), pages 59--70, 2008.

Digital Library

[13]

}}M. Hirzel, J. Henkel, A. Diwan, and M. Hind. Understanding the connectivity of heap objects. In Proceedings of the Workshop on Memory Systems Performance (MSP) and the Intl. Symp. on Memory Management (ISMM), pages 143--156, 2003.

Digital Library

[14]

}}H. Inoue, D. Stefanovic, and S. Forrest. On the prediction of java object lifetimes. IEEE Transactions on Computers, 55: 880--892, 2006.

Digital Library

[15]

}}K. Lee and S. P. Midkiff. A two-phase escape analysis for parallel Java programs. In Proceedings of the 15th Intl. Conf. on Parallel Architectures and Compilation Techniques (PACT), pages 53--62, 2006.

Digital Library

[16]

}}T. Lev-Ami, T. Reps, M. Sagiv, and R.Wilhelm. Putting static analysis to work for verification: A case study. In In Intl. Symp. on Software Testing and Analysis, pages 26--38, 2000.

Digital Library

[17]

}}O. Lhotak and L. Hendren. Context-sensitive points-to analysis: is it worth it? In Proceedings of the 15th Intl. Conf. on Compiler Construction, pages 47--64, 2006.

Digital Library

[18]

}}D. Liang, M. Pennings, and M. J. Harrold. Evaluating the precision of static reference analysis using profiling. In Proceedings of the ACM SIGSOFT Intl. Symp. on Software Testing and Analysis (ISSTA), pages 22--32, 2002.

Digital Library

[19]

}}D. Liang, M. Pennings, and M. J. Harrold. Evaluating the impact of context-sensitivity on andersen's algorithm for java programs. In Proceedings of the ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering (PASTE), pages 6--12, 2006.

Digital Library

[20]

}}A. Milanova, A. Rountev, and B. Ryder. Parameterized object sensitivity for points-to and side-effect analyses for Java. In Proceedings of the ACM SIGSOFT Intl. Symp. on Software Testing and Analysis (ISSTA), pages 1--11, 2002.

Digital Library

[21]

}}N. Mitchell. The runtime structure of object ownership. In Proceedings of the 20th European Conf. on Object-Oriented Programming (ECOOP), pages 74--98, 2006.

Digital Library

[22]

}}N. Mitchell and G. Sevitsky. The causes of bloat, the limits of health. In Proceedings of the 22nd ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pages 245--260, 2007.

Digital Library

[23]

}}N. Mitchell, E. Schonberg, and G. Sevitsky. Making sense of large heaps. In Proceedings of the 23rd European Conf. on Object-Oriented Programming (ECOOP), pages 77--97, 2009.

Digital Library

[24]

}}M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In Proceedings of the 34th ACM SIGPLAN SIGACT Symp. on Principles of Programming Languages (POPL), pages 327--338, 2007.

Digital Library

[25]

}}M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In Proceedings of the ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 308--319, 2006.

Digital Library

[26]

}}E. Ruf. Effective synchronization removal for Java. In Proceedings of the ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 208--218, 2000.

Digital Library

[27]

}}M. Sagiv, T.W. Reps, and R.Wilhelm. Parametric shape analysis via 3-valued logic. ACM Transactions on Programming Languages and Systems, 24(3):217--298, 2002.

Digital Library

[28]

}}M. L. Seidl and B. G. Zorn. Segregating heap objects by reference behavior and lifetime. SIGOPS Oper. Syst. Rev., 32 (5):12--23, 1998.

Digital Library

[29]

}}M. L. Seidl, M. L. Seidl, M. L. Seidl, B. G. Zorn, B. G. Zorn, and B. G. Zorn. Predicting references to dynamically allocated objects. Technical report, 1997.

[30]

}}R. Shaham, E. K. Kolodner, and M. Sagiv. Estimating the impact of heap liveness information on space consumption in Java. In Proceedings of the Workshop on Memory Systems Performance (MSP) and the Intl. Symp. on Memory Management (ISMM), pages 171--182, 2002.

Digital Library

[31]

}}O. Shivers. Control-flow analysis in Scheme. In Proceedings of the ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 164--174, 1988.

Digital Library

[32]

}}C. Unkel and M. S. Lam. Automatic inference of stationary fields: a generalization of Java's final fields. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL), pages 183--195, 2008.

Digital Library

[33]

}}E. Y.-B. Wang. Analysis of Recursive Types in an Imperative Language. PhD thesis, Univ. of Calif., Berkeley, CA, 1994.

Digital Library

[34]

}}J. Whaley. Joeq: A virtual machine and compiler infrastructure. Science of Computer Programming, 57(3):339--356, 2005.

Digital Library

[35]

}}R. M. Yoo, Y. Ni, A. Welc, B. Saha, A.-R. Adl-Tabatabai, and H.-H. S. Lee. Kicking the tires of software transactional memory: why the going gets tough. In Proceedings of the 20th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 265--274, 2008.

Digital Library

Cited By

Klinger CChristakis MWüstholz VZhang DMøller A(2019)Differentially testing soundness and precision of program analyzersProceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3293882.3330553(239-250)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.1145/3293882.3330553
Terragni VCheung SZhang CBertolino ACanfora GElbaum S(2015)RECONTESTProceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818787(246-256)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818787
Stancu CWimmer CBrunthaler SLarsen PFranz M(2015)Safe and efficient hybrid memory management for JavaACM SIGPLAN Notices10.1145/2887746.275418550:11(81-92)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754185
Show More Cited By

Index Terms

A dynamic evaluation of the precision of static heap abstractions

Recommendations

A dynamic evaluation of the precision of static heap abstractions
OOPSLA '10

The quality of a static analysis of heap-manipulating programs is largely determined by its heap abstraction. Object allocation sites are a commonly-used abstraction, but are too coarse for some clients. The goal of this paper is to investigate how ...
Heap Abstractions for Static Analysis

Heap data is potentially unbounded and seemingly arbitrary. Hence, unlike stack and static data, heap data cannot be abstracted in terms of a fixed set of program variables. This makes it an interesting topic of study and there is an abundance of ...
GC assertions: using the garbage collector to check heap properties
PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation

This paper introduces GC assertions, a system interface that programmers can use to check for errors, such as data structure invariant violations, and to diagnose performance problems, such as memory leaks. GC assertions are checked by the garbage ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

October 2010

984 pages

ISBN:9781450302036

DOI:10.1145/1869459

General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

ACM SIGPLAN Notices Volume 45, Issue 10
OOPSLA '10
October 2010
957 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1932682
Issue’s Table of Contents

Copyright © 2010 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '10

Sponsor:

SIGPLAN

SPLASH '10: Systems Programming Languages and Applications: Software for Humanity

October 17 - 21, 2010

Nevada, Reno/Tahoe, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
323
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Klinger CChristakis MWüstholz VZhang DMøller A(2019)Differentially testing soundness and precision of program analyzersProceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3293882.3330553(239-250)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.1145/3293882.3330553
Terragni VCheung SZhang CBertolino ACanfora GElbaum S(2015)RECONTESTProceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818787(246-256)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818787
Stancu CWimmer CBrunthaler SLarsen PFranz M(2015)Safe and efficient hybrid memory management for JavaACM SIGPLAN Notices10.1145/2887746.275418550:11(81-92)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754185
Stancu CWimmer CBrunthaler SLarsen PFranz MHosking ABond M(2015)Safe and efficient hybrid memory management for JavaProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754185(81-92)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754185
Radoi CDig D(2015)Effective Techniques for Static Race Detection in Java Parallel LoopsACM Transactions on Software Engineering and Methodology10.1145/272997524:4(1-30)Online publication date: 2-Sep-2015
https://dl.acm.org/doi/10.1145/2729975
Terragni VCheung SZhang C(2015)RECONTEST: Effective Regression Testing of Concurrent Programs2015 IEEE/ACM 37th IEEE International Conference on Software Engineering10.1109/ICSE.2015.45(246-256)Online publication date: May-2015
https://doi.org/10.1109/ICSE.2015.45
Christakis MMüller PWüstholz V(2015)An Experimental Evaluation of Deliberate Unsoundness in a Static Program AnalyzerProceedings of the 16th International Conference on Verification, Model Checking, and Abstract Interpretation - Volume 893110.1007/978-3-662-46081-8_19(336-354)Online publication date: 12-Jan-2015
https://dl.acm.org/doi/10.1007/978-3-662-46081-8_19
Stancu CWimmer CBrunthaler SLarsen PFranz MKolodziej JChilders B(2014)Comparing points-to static analysis with runtime recorded profiling dataProceedings of the 2014 International Conference on Principles and Practices of Programming on the Java platform: Virtual machines, Languages, and Tools10.1145/2647508.2647524(157-168)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1145/2647508.2647524
Sridharan MChandra SDolby JFink SYahav E(2013)Alias analysis for object-oriented programsAliasing in Object-Oriented Programming10.5555/2554511.2554523(196-232)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2554511.2554523
Blackshear SChang BSridharan M(2013)ThresherACM SIGPLAN Notices10.1145/2499370.246218648:6(275-286)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2499370.2462186
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