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

research-article

Diff Graphs for a fast Incremental Pointer Analysis

Authors:

Michael PhilippsenAuthors Info & Claims

ICOOOLPS'17: Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems

Article No.: 4, Pages 1 - 10

https://doi.org/10.1145/3098572.3098578

Published: 19 June 2017 Publication History

Abstract

A wide range of optimizations and program analyses, including bug finding by means of escape or race analyses, need accurate pointer information. Since accuracy takes time, there is a need for a fast incremental pointer analysis that re-uses prior results and only re-analyzes program changes and their effects instead of the whole program.

We present such an incremental pointer analysis that employs novel diff graphs to represent how a method accesses and/or modifies memory. Regardless of the number of call sites, we only need to analyze a method once; the resulting diff-graph is then used at every call site. If a method changes, we re-generate its diff-graph, and (unless its diff-graph stays the same) its callers' diff graphs, and so on.

Our algorithm is flow sensitive and context insensitive, does not leak information between call sites, can perform strong updates (even for method calls), and is fast (14 000 LOC with 25 000 bytecode instructions in 3 minutes). When used incrementally for each of the commits of an open-source software repository our incremental approach derives more precise pointer information than established (full) analyses like Spark -- albeit in about the same time.

References

[1]

Daphna Amit, Noam Rinetzky, Thomas Reps, Mooly Sagiv, and Eran Yahav. Comparison Under Abstraction for Verifying Linearizability. In Intl. Conf. Comp. Aided Verif (CAV '07), pages 477--490, Berlin, Germany, July 2007.

Digital Library

[2]

Elliot Berk. JLex: A Lexical Analyzer Generator for Java, 2003. https://www.cs.princeton.edu/appel/modern/java/JLex/.

[3]

Marcio O. Buss. Summary-based Pointer Analysis Framework for Modular Bug Finding. PhD thesis, Columbia Univ., New York, NY, 2008.

Digital Library

[4]

Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. Escape Analysis For Java. In Conf. on Object-Oriented Prog., Sys., Lang., and Appl. (OOPSLA '99), pages 1--19, Denver, CO, Nov. 1999.

Digital Library

[5]

Arnab De and Deepak D'Souza. Scalable Flow-Sensitive Pointer Analysis for Java with Strong Updates. In Europ. Conf. OOP (ECOOP '12), pages 665--687, Beijing, China, June 2012.

Digital Library

[6]

Isil Dillig, Thomas Dillig, Alex Aiken, and Mooly Sagiv. Precise and compact modular procedure summaries for heap manipulating programs. In Conf. Prog. Lang. Design and Impl. (PLDI '11), pages 567--577, San Jose, CA, June 2011.

Digital Library

[7]

Ben Hardekopf and Calvin Lin. Semi-sparse flow-sensitive pointer analysis. SIGPLAN Not., 44(1):226--238, Jan. 2009.

Digital Library

[8]

Michael Hind. Pointer analysis: Haven't we solved this problem yet? In Workshop Program Analysis f. Softw. Tools and Engin. (PASTE '01), pages 54--61, Snowbird, UT, June 2001.

Digital Library

[9]

Patrick Lam, Eric Bodden, Ondřej Lhoták, and Laurie J. Hendren. The Soot framework for Java program analysis: a retrospective. In Cetus Users and Compiler Infrastructure Workshop (CETUS '11), Galveston, TX, June 2011.

[10]

Ondřej Lhoták and Kwok-Chiang Andrew Chung. Points-to Analysis with Efficient Strong Updates. SIGPLAN Not., 46(1):3--16, Jan. 2011.

Digital Library

[11]

Ondřej Lhoták and Laurie J. Hendren. Scaling Java points-to analysis using Spark. In Intl. Conf. Compiler Constr. (CC '03), pages 153--169, Warsaw, Poland, Apr. 2003.

Digital Library

[12]

Ravichandhran Madhavan, G. Ramalingam, and Kapil Vaswani. Modular Heap Analysis for Higher-order Programs. In Intl. Conf. Static Analysis (SAS '12), pages 370--387, Deauville, France, Sep. 2012.

Digital Library

[13]

Mark Marron. Modeling the Heap: A Practical Approach. PhD thesis, Univ. of New Mexico, Albuquerque, NM, 2008.

Digital Library

[14]

Nomair A. Naeem and Ondřej Lhoták. Faster Alias Set Analysis Using Summaries. In Intl. Conf. Compiler Constr. (CC '11), pages 82--103, Saarbrücken, Germany, Mar. 2011.

Digital Library

[15]

Noam Rinetzky. Interprocedural Shape Analysis. Master's thesis, Technion Israel Institute of Technology, Haifa, Israel, 2001.

[16]

Noam Rinetzky, Jörg Bauer, Thomas Reps, Mooly Sagiv, and Reinhard Wilhelm. A Semantics for Procedure Local Heaps and its Abstractions. Tech. Rep. 14, SFB/TR AVACS, Oct. 2004.

[17]

Atanas Rountev, Mariana Sharp, and Guoqing Xu. IDE Dataflow Analysis in the Presence of Large Object-oriented Libraries. In Intl. Conf. Compiler Constr. (CC '08), pages 53--68, Budapest, Hungary, Mar. 2008.

Digital Library

[18]

Alexandru D. Salcianu. Pointer Analysis for Java Programs: Novel Techniques and Applications. PhD thesis, MIT, Cambridge, MA, 2006.

Digital Library

[19]

Lorna A. Smith, J. Mark Bull, and Jan Obdrzálek. A Parallel Java Grande Benchmark Suite. In Conf. Supercomp. (SC '01), pages 8--8, Denver, CO, Nov. 2001.

Digital Library

[20]

Bjarne Steensgaard. Points-to Analysis in Almost Linear Time. In Proc. Symp. Princ. Progr. Lang. (POPL '96), pages 32--41, St. Petersburg Beach, FL, Jan. 1996.

Digital Library

[21]

Alexandru Sălcianu and Martin Rinard. Purity and Side Effect Analysis for Java Programs. In Intl. Conf. Verif., Model Checking, and Abst. Interpr. (VMCAI '05), pages 199--215, Paris, France, Jan. 2005.

Digital Library

[22]

Yulei Sui, Sen Ye, Jingling Xue, and Jie Zhang. Making context-sensitive inclusion-based pointer analysis practical for compilers using parameterised summarisation. Softw., Pract. Exper., 44(12):1485--1510, 2014.

Digital Library

[23]

Adrian Tineo, Francisco Corbera, Angeles G. Navarro, Rafael Asenjo, and Emilio L. Zapata. A new Strategy for Shape Analysis based on Coexistent Links Sets. In Conf. Parallel Computing (ParCo '05), pages 557--564, Malaga, Spain, Sep. 2005.

[24]

Raja Vallee-Rai and Laurie J. Hendren. Jimple: Simplifying Java bytecode for analyses and transformations. Tech. Rep. SABLE-TR-1998-4, Sable Research Group, School of CS, McGill Univ., Montréal, Canada, July 1998.

[25]

Frédéric Vivien and Martin Rinard. Incrementalized Pointer and Escape Analysis. SIGPLAN Not., 36(5):35--46, May 2001.

Digital Library

[26]

Mark Allen Weiss. Data Structures and Problem Solving Using Java. Addison-Wesley, Boston, MA, 4th edition, 2010.

[27]

John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Conf. Prog. Lang. Design Impl (PLDI '04), pages 131--144, Washington, DC, June 2004.

Digital Library

[28]

John Whaley and Martin Rinard. Compositional Pointer and Escape Analysis for Java Programs. SIGPLAN Not., 34(10):187--206, Oct. 1999.

Digital Library

[29]

Eran Yahav and Stephen Fink. The SAFE experience. In Peri L. Tarr and Alexander L. Wolf, editors, Engineering of Software: The Continuing Contributions of Leon J. Osterweil, pages 17--33, Berlin, 2011. Springer.

[30]

Dacong Yan, Guoqing Xu, and Atanas Rountev. Demand-driven Context-sensitive Alias Analysis for Java. In Intl. Symp. Software Testing and Analysis (ISSTA '11), pages 155--165, Toronto, Canada, 2011.

Digital Library

[31]

Greta Yorsh, Eran Yahav, and Satish Chandra. Generating Precise and Concise Procedure Summaries. SIGPLAN Not., 43(1):221--234, Jan. 2008.

Digital Library

[32]

Xin Zhang, Ravi Mangal, Mayur Naik, and Hongseok Yang. Hybrid top-down and bottom-up interprocedural analysis. In Conf. Prog. Lang. Design and Impl. (PLDI '14), pages 249--258, Edinburgh, UK, June 2014.

Digital Library

Cited By

Li ZMa XHu MYan JFilkov VRay BZhou M(2024)Detecting Element Accessing Bugs in C++ Sequence ContainersProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695471(883-894)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695471
Düsing JHermann BBissyandé TKlein JBird CSarro F(2023)Persisting and Reusing Results of Static Program Analyses on a Large ScaleProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00080(888-900)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00080
Liu BHuang J(2022)SHARP: fast incremental context-sensitive pointer analysis for JavaProceedings of the ACM on Programming Languages10.1145/35273326:OOPSLA1(1-28)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527332
Show More Cited By

Diff Graphs for a fast Incremental Pointer Analysis
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning

Recommendations

SHARP: fast incremental context-sensitive pointer analysis for Java

We present SHARP, an incremental context-sensitive pointer analysis algorithm that scales to real-world large complex Java programs and can also be efficiently parallelized. To our knowledge, SHARP is the first algorithm to tackle context-sensitivity in ...
Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Practical pointer aliasing analysis

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICOOOLPS'17: Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems

June 2017

39 pages

ISBN:9781450350884

DOI:10.1145/3098572

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

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages
AITO: Assoc Internationale por les Technologies Objects

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

ECOOP '17

ECOOP '17: European Conference on Object-Oriented Programming

June 19, 2017

Barcelona, Spain

Acceptance Rates

ICOOOLPS'17 Paper Acceptance Rate 6 of 8 submissions, 75%;

Overall Acceptance Rate 11 of 14 submissions, 79%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
127
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li ZMa XHu MYan JFilkov VRay BZhou M(2024)Detecting Element Accessing Bugs in C++ Sequence ContainersProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695471(883-894)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695471
Düsing JHermann BBissyandé TKlein JBird CSarro F(2023)Persisting and Reusing Results of Static Program Analyses on a Large ScaleProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00080(888-900)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00080
Liu BHuang J(2022)SHARP: fast incremental context-sensitive pointer analysis for JavaProceedings of the ACM on Programming Languages10.1145/35273326:OOPSLA1(1-28)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527332
Ma XYan JWang WYan JZhang JQiu Z(2021)Detecting Memory-Related Bugs by Tracking Heap Memory Management of C++ Smart Pointers2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE51524.2021.9678836(880-891)Online publication date: Nov-2021
https://doi.org/10.1109/ASE51524.2021.9678836
Van der Plas JStievenart QVan Es NDe Roover C(2020)Incremental Flow Analysis through Computational Dependency Reification2020 IEEE 20th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM51674.2020.00008(25-36)Online publication date: Sep-2020
https://doi.org/10.1109/SCAM51674.2020.00008

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