Article

Fast and precise points-to analysis with incremental CFL-reachability summarisation: preliminary experience

Authors:

Lei Shang,

Yi Lu,

Jingling XueAuthors Info & Claims

ASE '12: Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering

Pages 270 - 273

https://doi.org/10.1145/2351676.2351720

Published: 03 September 2012 Publication History

Get Access

Abstract

We describe our preliminary experience in the design and implementation of a points-to analysis for Java, called EMU, that enables developers to perform pointer-related queries in programs undergoing constant changes in IDEs. EMU achieves fast response times by adopting a modular approach to incrementally updating method summaries upon small code changes: the points-to information in a method is summarised indirectly by CFL reachability rather than directly by points-to sets. Thus, the impact of a small code change made in a method is localised, requiring only its affected part to be re-summarised just to reflect the change. EMU achieves precision by being context-sensitive (for both method invocation and heap abstraction) and field-sensitive. Our evaluation shows that EMU can be promisingly deployed in IDEs where the changes are small.

References

[1]

N. Heintze and O. Tardieu. Demand-driven pointer analysis. In PLDI’01 .

Digital Library

Google Scholar

[2]

V. Kahlon. Bootstrapping: a technique for scalable ﬂow and context-sensitive pointer alias analysis. In PLDI’08.

Digital Library

Google Scholar

[3]

J. Kodumal and A. Aiken. Banshee: A scalable constraint-based analysis toolkit. In SAS’05.

Digital Library

Google Scholar

[4]

T. Reps. Program analysis via graph reachability. In ILPS’97.

Digital Library

Google Scholar

[5]

D. Saha and C. Ramakrishnan. Incremental and demand-driven points-to analysis using logic programming. In PPDP’05.

Digital Library

Google Scholar

[6]

L. Shang, X. Xie, and J. Xue. On-demand dynamic summary-based points-to analysis. In CGO’12.

Digital Library

Google Scholar

[7]

M. Sridharan and R. Bodík. Reﬁnement-based context-sensitive points-to analysis for Java. In PLDI’06.

Digital Library

Google Scholar

[8]

J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In PLDI’04.

Digital Library

Google Scholar

[9]

D. Yan, G. Xu, and A. Rountev. Demand-driven context-sensitive alias analysis for Java. In ISSTA’11.

Digital Library

Google Scholar

[10]

H. Yu, J. Xue, W. Huo, X. Feng, and Z. Zhang. Level by level: making ﬂow- and context-sensitive pointer analysis scalable for millions of lines of code. In CGO’10.

Digital Library

Google Scholar

[11]

J.-S. Yur, B. G. Ryder, and W. Landi. An incremental ﬂow- and context-sensitive pointer aliasing analysis. In ICSE’99.

Digital Library

Google Scholar

Cited By

View all

Liu JLiu JDi PWu DZheng HLiu AXue JJust RFraser G(2023)Hybrid Inlining: A Framework for Compositional and Context-Sensitive Static AnalysisProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598042(114-126)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598042
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
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
Show More Cited By

Index Terms

Fast and precise points-to analysis with incremental CFL-reachability summarisation: preliminary experience
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

Recommendations

On-demand dynamic summary-based points-to analysis
CGO '12: Proceedings of the Tenth International Symposium on Code Generation and Optimization

Static analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently ...
Fast and precise points-to analysis

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, ...
Side-effect analysis with fast escape filter
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis

Side-effect analysis is a fundamental static analysis used to determine the memory locations modified or used by each program entity. For the programs with pointers, the analysis can be very imprecise. To improve the precision of side-effect analysis, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ASE '12: Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering

September 2012

409 pages

ISBN:9781450312042

DOI:10.1145/2351676

General Chair:
Michael Goedicke,
Program Chairs:
Tim Menzies,
Motoshi Saeki

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]

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence
Universität Duisburg Essen: Universität Duisburg Essen
TCSE: IEEE Computer Society's Tech. Council on Software Engin.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ASE'12

Sponsor:

SIGSOFT

ASE'12: IEEE/ACM International Conference on Automated Software Engineering

September 3 - 7, 2012

Essen, Germany

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
236
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu JLiu JDi PWu DZheng HLiu AXue JJust RFraser G(2023)Hybrid Inlining: A Framework for Compositional and Context-Sensitive Static AnalysisProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598042(114-126)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598042
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
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
Zhang JXue JMcKinley KFisher K(2019)Incremental precision-preserving symbolic inference for probabilistic programsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314623(237-252)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314623
Liu BHuang JRauchwerger L(2019)Rethinking Incremental and Parallel Pointer AnalysisACM Transactions on Programming Languages and Systems10.1145/329360641:1(1-31)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1145/3293606
Liu BHuang J(2018)D4: fast concurrency debugging with parallel differential analysisACM SIGPLAN Notices10.1145/3296979.319239053:4(359-373)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192390
Liu BHuang JFoster JGrossman D(2018)D4: fast concurrency debugging with parallel differential analysisProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192390(359-373)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192390
Zhang YLi YTan TXue J(2018) Ripple : Reflection analysis for Android apps in incomplete information environments Software: Practice and Experience10.1002/spe.257748:8(1419-1437)Online publication date: 19-Apr-2018
https://doi.org/10.1002/spe.2577
Zhang JSui YXue J(2017)Incremental Analysis for Probabilistic ProgramsStatic Analysis10.1007/978-3-319-66706-5_22(450-472)Online publication date: 19-Aug-2017
https://doi.org/10.1007/978-3-319-66706-5_22
Sui YYe DSu YXue J(2016)Eliminating Redundant Bounds Checks in Dynamic Buffer Overflow Detection Using Weakest PreconditionsIEEE Transactions on Reliability10.1109/TR.2016.257053865:4(1682-1699)Online publication date: Dec-2016
https://doi.org/10.1109/TR.2016.2570538
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.

Cited By

Index Terms

Recommendations

On-demand dynamic summary-based points-to analysis

Fast and precise points-to analysis

Side-effect analysis with fast escape filter