Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3062341.3062360acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
research-article

Efficient and precise points-to analysis: modeling the heap by merging equivalent automata

Published: 14 June 2017 Publication History

Abstract

Mainstream points-to analysis techniques for object-oriented languages rely predominantly on the allocation-site abstraction to model heap objects. We present MAHJONG, a novel heap abstraction that is specifically developed to address the needs of an important class of type-dependent clients, such as call graph construction, devirtualization and may-fail casting. By merging equivalent automata representing type-consistent objects that are created by the allocation-site abstraction, MAHJONG enables an allocation-site-based points-to analysis to run significantly faster while achieving nearly the same precision for type-dependent clients.
MAHJONG is simple conceptually, efficient, and drops easily on any allocation-site-based points-to analysis. We demonstrate its effectiveness by discussing some insights on why it is a better alternative of the allocation-site abstraction for type-dependent clients and evaluating it extensively on 12 large real-world Java programs with five context-sensitive points-to analyses and three widely used type-dependent clients. MAHJONG is expected to provide significant benefits for many program analyses where call graphs are required.

Supplementary Material

Auxiliary Archive (pldi17-main142-s.zip)
This artifact is provided to enable the results of all two research questions (RQ1 and RQ2) in our companion paper, i.e., the results in Figure 8, Figure 9, Table 1 and Table 2, to be reproduced. In RQ1, we show that MAHJONG is lightweight for large programs and how MAHJONG can alleviate the heap over-partitioning problem suffered by the allocation-site abstraction effectively for type-dependent clients. In RQ2, we show that MAHJONG can significantly accelerate different types of mainstream context-sensitive points-to analyses while achieving nearly the same precision as the allocation-site abstraction for type-dependent clients. The artifact contains MAHJONG and Doop (a state-of-the-art whole-program points-to analysis framework for Java) to reproduce the results. Size of the artifact: 115MB MD5 sum of the artifact: 619a2d64be9fa61b158f2b04ad55e4a0

References

[1]
J. Adamek and V. Trnkova. Automata and Algebras in Categories. Kluwer Academic Publishers, 1990.
[2]
A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2Nd Edition). Addison-Wesley, Boston, MA, USA, 2006.
[3]
K. Ali and O. Lhoták. Averroes: Whole-program analysis without the whole program. ECOOP, pages 378–400, 2013.
[4]
L. Andersen. Program analysis and specialization for the C programming language. PhD thesis, DIKU, University of Copenhagen, 1994.
[5]
S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel. FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps. PLDI, pages 259–269, 2014.
[6]
S. Blackshear, B.-Y. E. Chang, and M. Sridharan. Selective control-flow abstraction via jumping. OOPSLA, pages 163– 182, 2015.
[7]
S. Blackshear, A. Gendreau, and B.-Y. E. Chang. Droidel: A general approach to Android framework modeling. SOAP, pages 19–25, 2015.
[8]
E. Bodden, A. Sewe, J. Sinschek, H. Oueslati, and M. Mezini. Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders. ICSE, pages 241–250, 2011.
[9]
M. Bravenboer and Y. Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. OOPSLA, pages 243–262, 2009.
[10]
Chord. A program analysis platform for Java. http://www. cis.upenn.edu/~mhnaik/chord.html.
[11]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2009.
[12]
DaCapo. Java benchmark. http://www.dacapobench.org.
[13]
J. Dean, D. Grove, and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. ECOOP, pages 77–101, 1995.
[14]
DOOP. A sophisticated framework for Java pointer analysis. http://doop.program-analysis.org.
[15]
Y. Feng, X. Wang, I. Dillig, and T. Dillig. Bottom-up contextsensitive pointer analysis for Java. APLAS, pages 465–484, 2015.
[16]
S. J. Fink, E. Yahav, N. Dor, G. Ramalingam, and E. Geay. Effective typestate verification in the presence of aliasing. ACM Trans. Softw. Eng. Methodol., 17(2), 2008.
[17]
M. Hind. Pointer analysis: Haven’t we solved this problem yet? PASTE, pages 54–61, 2001.
[18]
J. E. Hopcroft and R. M. Karp. A linear algorithm for testing equivalence of finite automata. Technical Report 71-114, Cornell University, 1971.
[19]
V. Kanvar and U. P. Khedker. Heap abstractions for static analysis. ACM Comput. Surv., 49(2):29:1–29:47, 2016.
[20]
G. Kastrinis and Y. Smaragdakis. Hybrid context-sensitivity for points-to analysis. PLDI, pages 423–434, 2013.
[21]
O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. CC, pages 153–169, 2003.
[22]
O. Lhoták and L. Hendren. Context-sensitive points-to analysis: is it worth it? CC, pages 47–64, 2006.
[23]
O. Lhoták and L. Hendren. Evaluating the benefits of contextsensitive points-to analysis using a bdd-based implementation. ACM TOSEM., 18(1):3:1–3:53, 2008.
[24]
Y. Li, T. Tan, Y. Sui, and J. Xue. Self-inferencing reflection resolution for Java. ECOOP, pages 27–53, 2014.
[25]
Y. Li, T. Tan, and J. Xue. Effective soundness-guided reflection analysis. SAS, pages 162–180, 2015.
[26]
Y. Li, T. Tan, Y. Zhang, and J. Xue. Program tailoring: Slicing by sequential criteria. ECOOP, pages 15:1–15:27, 2016.
[27]
P. Liang and M. Naik. Scaling abstraction refinement via pruning. PLDI, pages 590–601, 2011.
[28]
A. Marino. Analysis and Enumeration: Algorithms for Biological Graphs. Atlantis Publishing Corporation, 2015.
[29]
A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to and side-effect analyses for Java. ISSTA, pages 1–11, 2002.
[30]
A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol., 14(1):1–41, 2005.
[31]
M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. PLDI, pages 308–319, 2006.
[32]
M. Naik, C. Park, K. Sen, and D. Gay. Effective static deadlock detection. ICSE, pages 386–396, 2009.
[33]
H. Oh, W. Lee, K. Heo, H. Yang, and K. Yi. Selective contextsensitivity guided by impact pre-analysis. PLDI, pages 475– 484, 2014.
[34]
R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3): 237–252, 1975.
[35]
B. G. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. CC, pages 126–137, 2003.
[36]
L. Shang, X. Xie, and J. Xue. On-demand dynamic summarybased points-to analysis. In CGO, pages 264–274, 2012.
[37]
O. G. Shivers. Control-flow Analysis of Higher-order Languages of Taming Lambda. PhD thesis, 1991.
[38]
Y. Smaragdakis and G. Balatsouras. Pointer analysis. Found. Trends Program. Lang., pages 1–69, 2015.
[39]
Y. Smaragdakis, M. Bravenboer, and O. Lhoták. Pick your contexts well: understanding object-sensitivity. POPL, pages 17–30, 2011.
[40]
Y. Smaragdakis, G. Kastrinis, and G. Balatsouras. Introspective analysis: Context-sensitivity, across the board. PLDI, pages 485–495, 2014.
[41]
J. Späth, L. N. Q. Do, K. Ali, and E. Bodden. Boomerang: Demand-driven flow- and context-sensitive pointer analysis for Java. ECOOP, pages 22:1–22:26, 2016.
[42]
M. Sridharan and R. Bod´ık. Refinement-based contextsensitive points-to analysis for Java. PLDI, pages 387–400, 2006.
[43]
M. Sridharan, S. J. Fink, and R. Bodik. Thin slicing. PLDI, pages 112–122, 2007.
[44]
M. Sridharan, S. Chandra, J. Dolby, S. J. Fink, and E. Yahav. Aliasing in object-oriented programming. chapter Alias Analysis for Object-oriented Programs, pages 196–232. 2013.
[45]
Y. Sui and J. Xue. On-demand strong update analysis via value-flow refinement. In FSE, pages 460–473, 2016.
[46]
Y. Sui, Y. Li, and J. Xue. Query-directed adaptive heap cloning for optimizing compilers. CGO, pages 1–11, 2013.
[47]
V. Sundaresan, L. Hendren, C. Razafimahefa, R. Vallée-Rai, P. Lam, E. Gagnon, and C. Godin. Practical virtual method call resolution for java. OOPSLA, pages 264–280, 2000.
[48]
T. Tan, Y. Li, and J. Xue. Making k-object-sensitive pointer analysis more precise with still k-limiting. SAS, pages 489– 510, 2016.
[49]
R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan. Soot - a Java bytecode optimization framework. CASCON, pages 1–13, 1999.
[50]
WALA. Watson libraries for analysis. wala.sf.net.
[51]
J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. PLDI, pages 131–144, 2004.
[52]
H. Yu, J. Xue, W. Huo, X. Feng, and Z. Zhang. Level by level: making flow- and context-sensitive pointer analysis scalable for millions of lines of code. CGO, pages 218–229, 2010.
[53]
Q. Zhang and Z. Su. Context-sensitive data-dependence analysis via linear conjunctive language reachability. POPL, pages 344–358, 2017.
[54]
X. Zhang, R. Mangal, R. Grigore, M. Naik, and H. Yang. On abstraction refinement for program analyses in Datalog. PLDI, pages 239–248, 2014.
[55]
Y. Zhang, T. Tan, Y. Li, and J. Xue. Ripple: Reflection analysis for android apps in incomplete information environments. 2017.

Cited By

View all
  • (2024)The ART of Sharing Points-to Analysis: Reusing Points-to Analysis Results Safely and EfficientlyProceedings of the ACM on Programming Languages10.1145/36898038:OOPSLA2(2606-2632)Online publication date: 8-Oct-2024
  • (2024)Scaling Abstraction Refinement for Program Analyses in Datalog using Graph Neural NetworksProceedings of the ACM on Programming Languages10.1145/36897658:OOPSLA2(1532-1560)Online publication date: 8-Oct-2024
  • (2024)When to Stop Going Down the Rabbit Hole: Taming Context-Sensitivity on the FlyProceedings of the 13th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3652588.3663321(35-44)Online publication date: 20-Jun-2024
  • Show More Cited By

Index Terms

  1. Efficient and precise points-to analysis: modeling the heap by merging equivalent automata

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
    June 2017
    708 pages
    ISBN:9781450349888
    DOI:10.1145/3062341
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 14 June 2017

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. heap abstraction
    2. points-to analysis

    Qualifiers

    • Research-article

    Conference

    PLDI '17
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 406 of 2,067 submissions, 20%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)86
    • Downloads (Last 6 weeks)8
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)The ART of Sharing Points-to Analysis: Reusing Points-to Analysis Results Safely and EfficientlyProceedings of the ACM on Programming Languages10.1145/36898038:OOPSLA2(2606-2632)Online publication date: 8-Oct-2024
    • (2024)Scaling Abstraction Refinement for Program Analyses in Datalog using Graph Neural NetworksProceedings of the ACM on Programming Languages10.1145/36897658:OOPSLA2(1532-1560)Online publication date: 8-Oct-2024
    • (2024)When to Stop Going Down the Rabbit Hole: Taming Context-Sensitivity on the FlyProceedings of the 13th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3652588.3663321(35-44)Online publication date: 20-Jun-2024
    • (2024)Learning Abstraction Selection for Bayesian Program AnalysisProceedings of the ACM on Programming Languages10.1145/36498458:OOPSLA1(954-982)Online publication date: 29-Apr-2024
    • (2024)Generic Sensitivity: Generics-Guided Context Sensitivity for Pointer AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2024.337764550:5(1144-1162)Online publication date: 12-Apr-2024
    • (2023)A Cocktail Approach to Practical Call Graph ConstructionProceedings of the ACM on Programming Languages10.1145/36228337:OOPSLA2(1001-1033)Online publication date: 16-Oct-2023
    • (2023)Tai-e: A Developer-Friendly Static Analysis Framework for Java by Harnessing the Good Designs of ClassicsProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598120(1093-1105)Online publication date: 12-Jul-2023
    • (2023)Context Sensitivity without Contexts: A Cut-Shortcut Approach to Fast and Precise Pointer AnalysisProceedings of the ACM on Programming Languages10.1145/35912427:PLDI(539-564)Online publication date: 6-Jun-2023
    • (2023)Selecting Context-Sensitivity Modularly for Accelerating Object-Sensitive Pointer AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2022.316223649:2(719-742)Online publication date: 1-Feb-2023
    • (2023)Learning to Boost Disjunctive Static Bug-FindersProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00099(1097-1109)Online publication date: 14-May-2023
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media