article

Cloning-based context-sensitive pointer alias analysis using binary decision diagrams

Authors:

Monica S. LamAuthors Info & Claims

ACM SIGPLAN Notices, Volume 39, Issue 6

Pages 131 - 144

https://doi.org/10.1145/996893.996859

Published: 09 June 2004 Publication History

Abstract

This paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for Java programs. Our approach to context sensitivity is to create a clone of a method for every context of interest, and run a context-insensitive algorithm over the expanded call graph to get context-sensitive results. For precision, we generate a clone for every acyclic path through a program's call graph, treating methods in a strongly connected component as a single node. Normally, this formulation is hopelessly intractable as a call graph often has 10 14 acyclic paths or more. We show that these exponential relations can be computed efficiently using binary decision diagrams (BDDs). Key to the scalability of the technique is a context numbering scheme that exposes the commonalities across contexts. We applied our algorithm to the most popular applications available on Sourceforge, and found that the largest programs, with hundreds of thousands of Java bytecodes, can be analyzed in under 20 minutes.This paper shows that pointer analysis, and many other queries and algorithms, can be described succinctly and declaratively using Datalog, a logic programming language. We have developed a system called bddbddb that automatically translates Datalog programs into highly efficient BDD implementations. We used this approach to develop a variety of context-sensitive algorithms including side effect analysis, type analysis, and escape analysis.

References

[1]

I. Balbin and K. Ramamohanarao. A generalization of the differential approach to recursive query optimization. Journal of Logic Programming, 4(3):259--262, Sept. 1987.]]

Digital Library

[2]

T. Ball and S. K. Rajamani. A symbolic model checker for boolean programs. In Proceedings of the SPIN 2000 Workshop on Model Checking of Software, pages 113--130, Aug. 2000.]]

Digital Library

[3]

M. Berndl, O. Lhotak, F. Qian, L. Hendren, and N. Umanee. Points-to analysis using BDDs. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 103--114, June 2003.]]

Digital Library

[4]

D. Beyer, A. Noack, and C. Lewerentz. Simple and efficient relational querying of software structures. In Proceedings of the 10th IEEE Working Conference on Reverse Engineering, Nov. 2003.]]

Digital Library

[5]

B. Bollig and I. Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on Computers, 45(9):993--1002, Sept. 1996.]]

Digital Library

[6]

R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, C-35(8):677--691, Aug. 1986.]]

Digital Library

[7]

A. Chandra and D. Harel. Horn clauses and generalizations. Journal of Logic Programming, 2(1):1--15, 1985.]]

[8]

J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. Midkiff. Escape analysis for Java. In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 1--19, Nov. 1999.]]

Digital Library

[9]

M.-M. Corsini, K. Musumbu, A. Rauzy, and B. L. Charlier. Efficient bottom-up abstract interpretation of Prolog by means of constraint solving over symbolic finite domains. In Proceedings of the International Symposium on Programming Language Implementation and Logic Programming, pages 75--91, Aug. 1993.]]

Digital Library

[10]

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

Digital Library

[11]

M. Das, B. Liblit, M. Fähndrich, and J. Rehof. Estimating the impact of scalable pointer analysis on optimization. In Proceedings of the 8th International Static Analysis Symposium, pages 260--278, July 2001.]]

Digital Library

[12]

S. Dawson, C. R. Ramakrishnan, and D. S. Warren. Practical program analysis using general purpose logic programming systems-a case study. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 117--126, May 1996.]]

Digital Library

[13]

J. Dean, D. Grove, and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the 9th European Conference on Object-Oriented Programming, pages 77--101, Aug. 1995.]]

Digital Library

[14]

M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 242--256, June 1994.]]

Digital Library

[15]

M. Fähndrich, J. Rehof, and M. Das. Scalable context-sensitive flow analysis using instantiation constraints. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 253--263, June 2000.]]

Digital Library

[16]

J. S. Foster, M. Fähndrich, and A. Aiken. Polymorphic versus monomorphic flow-insensitive points-to analysis for C. In Proceedings of the 7th International Static Analysis Symposium, pages 175--198, Apr. 2000.]]

Digital Library

[17]

N. Heintze and O. Tardieu. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 254--263, June 2001.]]

Digital Library

[18]

W. Landi, B. G. Ryder, and S. Zhang. Interprocedural modification side effect analysis with pointer aliasing. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 56--67, June 1993.]]

Digital Library

[19]

O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. In Proceedings of the 12th International Conference on Compiler Construction, pages 153--169, April 2003.]]

Digital Library

[20]

O. Lhoták and L. Hendren. Jedd: A BDD-based relational extension of Java. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, June 2004.]]

Digital Library

[21]

J. Lind-Nielsen. BuDDy, a binary decision diagram package. http://www.itu.dk/research/buddy/.]]

[22]

T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, 2nd edition, 1999.]]

Digital Library

[23]

R. Manevich, G. Ramalingam, J. Field, D. Goyal, and M. Sagiv. Compactly representing first-order structures for static analysis. In Proceedings of the 9th International Static Analysis Symposium, pages 196--212, Sept. 2002.]]

Digital Library

[24]

T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 24th Annual Symposium on Principles of Programming Languages, pages 49--61, Jan. 1995.]]

Digital Library

[25]

T. W. Reps. Demand Interprocedural Program Analysis Using Logic Databases, pages 163--196. Kluwer, 1994.]]

[26]

O. Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, May 1991.]]

Digital Library

[27]

F. Somenzi. CUDD: CU decision diagram package release, 1998.]]

[28]

B. Steensgaard. Points-to analysis in almost linear time. In Symposium on Principles of Programming Languages, pages 32--41, Jan. 1996.]]

Digital Library

[29]

Java cryptography extension (JCE). http://java.sun.com/products/jce, 2003.]]

[30]

J. D. Ullman. Principles of Database and Knowledge-Base Systems. Computer Science Press, Rockville, Md., volume II edition, 1989.]]

Digital Library

[31]

J. Whaley. JavaBDD library. http://javabdd.sourceforge.net.]]

[32]

J. Whaley. Joeq: A virtual machine and compiler infrastructure. In Proceedings of the SIGPLAN Workshop on Interpreters, Virtual Machines, and Emulators, pages 58--66, June 2003.]]

Digital Library

[33]

J. Whaley and M. S. Lam. An efficient inclusion-based points-to analysis for strictly-typed languages. In Proceedings of the 9th International Static Analysis Symposium, pages 180--195, Sept. 2002.]]

Digital Library

[34]

J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Conference of Object Oriented Programming: Systems, Languages, and Applications, pages 187--206, Nov. 1999.]]

Digital Library

[35]

J. Whaley, C. Unkel, and M. S. Lam. A BDD-based deductive database for program analysis. http://suif.stanford.edu/bddbddb, 2004.]]

[36]

R. P. Wilson. Efficient, context-sensitive pointer analysis for C programs. PhD thesis, Stanford University, Dec. 1997.]]

Digital Library

[37]

R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 1--12, June 1995.]]

Digital Library

[38]

T. Yavuz-Kahveci and T. Bultan. Automated verification of concurrent linked lists with counters. In Proceedings of the 9th International Static Analysis Symposium, pages 69--84, Sept. 2002.]]

Digital Library

[39]

J. Zhu. Symbolic pointer analysis. In Proceedings of the International Conference in Computer-Aided Design, pages 150--157, Nov. 2002.]]

Digital Library

[40]

J. Zhu and S. Calman. Symbolic pointer analysis revisited. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, June 2004.]]

Digital Library

Cited By

Smith SZhang R(2024)A Pure Demand Operational Semantics with Applications to Program AnalysisProceedings of the ACM on Programming Languages10.1145/36498528:OOPSLA1(1154-1180)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649852
Siddiqui AYadav K(2023)A Novel Approach to Pointer Analysis2022 OPJU International Technology Conference on Emerging Technologies for Sustainable Development (OTCON)10.1109/OTCON56053.2023.10113963(1-5)Online publication date: 8-Feb-2023
https://doi.org/10.1109/OTCON56053.2023.10113963
Xu RMao XChen LYu Y(2023)A Parallel Memory Defect Detection Method based on Sparse-Value-Flow Graph2023 IEEE International Conference on Joint Cloud Computing (JCC)10.1109/JCC59055.2023.00014(57-65)Online publication date: Jul-2023
https://doi.org/10.1109/JCC59055.2023.00014
Show More Cited By

Index Terms

Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

This paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for Java programs. Our approach to context sensitivity is to create a clone of a method for every context of interest, and run a context-insensitive ...
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 ...
Making context-sensitive points-to analysis with heap cloning practical for the real world
Proceedings of the 2007 PLDI conference

Context-sensitive pointer analysis algorithms with full "heapcloning" are powerful but are widely considered to be too expensive to include in production compilers. This paper shows, for the first time, that a context-sensitive, field-sensitive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 39, Issue 6

PLDI '04

May 2004

299 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/996893

Issue’s Table of Contents

PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation
June 2004
310 pages
ISBN:1581138075
DOI:10.1145/996841
General Chair:
William Pugh
University of Maryland, College Park
,
Program Chair:
Craig Chambers
University of Washington

Copyright © 2004 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: 09 June 2004

Published in SIGPLAN Volume 39, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

475
Total Citations
View Citations
1,561
Total Downloads

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

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Smith SZhang R(2024)A Pure Demand Operational Semantics with Applications to Program AnalysisProceedings of the ACM on Programming Languages10.1145/36498528:OOPSLA1(1154-1180)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649852
Siddiqui AYadav K(2023)A Novel Approach to Pointer Analysis2022 OPJU International Technology Conference on Emerging Technologies for Sustainable Development (OTCON)10.1109/OTCON56053.2023.10113963(1-5)Online publication date: 8-Feb-2023
https://doi.org/10.1109/OTCON56053.2023.10113963
Xu RMao XChen LYu Y(2023)A Parallel Memory Defect Detection Method based on Sparse-Value-Flow Graph2023 IEEE International Conference on Joint Cloud Computing (JCC)10.1109/JCC59055.2023.00014(57-65)Online publication date: Jul-2023
https://doi.org/10.1109/JCC59055.2023.00014
Jurjo DMorales JLopez-Garcia PHermenegildo M(2023)A Rule-Based Approach for Designing and Composing Abstract DomainsLogic-Based Program Synthesis and Transformation10.1007/978-3-031-45784-5_6(80-98)Online publication date: 16-Oct-2023
https://doi.org/10.1007/978-3-031-45784-5_6
Lembachar YRusich RNeamtiu ICiardo G(2022)Bddl: A Type System for Binary Decision DiagramsTests and Proofs10.1007/978-3-031-09827-7_3(31-47)Online publication date: 22-Jun-2022
https://doi.org/10.1007/978-3-031-09827-7_3
Tan TLi YMa XXu CSmaragdakis Y(2021)Making pointer analysis more precise by unleashing the power of selective context sensitivityProceedings of the ACM on Programming Languages10.1145/34855245:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485524
Zuo ZWang KHussain ASani AZhang YLu SDou WWang LLi XWang CXu G(2021)Systemizing Interprocedural Static Analysis of Large-scale Systems Code with GraspanACM Transactions on Computer Systems10.1145/346682038:1-2(1-39)Online publication date: 29-Jul-2021
https://dl.acm.org/doi/10.1145/3466820
Wang JSung CRaghothaman MWang C(2021)Data-Driven Synthesis of Provably Sound Side Channel AnalysesProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00079(810-822)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00079
Hedenborg MLundberg JLöwe W(2021)Memory efficient context-sensitive program analysisJournal of Systems and Software10.1016/j.jss.2021.110952(110952)Online publication date: Mar-2021
https://doi.org/10.1016/j.jss.2021.110952
Helm DKübler FReif MEichberg MMezini MDevanbu PCohen MZimmermann T(2020)Modular collaborative program analysis in OPALProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409765(184-196)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409765
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.

Figures

Tables

Media

View Issue’s Table of Contents