research-article

Hybrid context-sensitivity for points-to analysis

Authors:

George Kastrinis,

Yannis SmaragdakisAuthors Info & Claims

PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 423 - 434

https://doi.org/10.1145/2491956.2462191

Published: 16 June 2013 Publication History

Abstract

Context-sensitive points-to analysis is valuable for achieving high precision with good performance. The standard flavors of context-sensitivity are call-site-sensitivity (kCFA) and object-sensitivity. Combining both flavors of context-sensitivity increases precision but at an infeasibly high cost. We show that a selective combination of call-site- and object-sensitivity for Java points-to analysis is highly profitable. Namely, by keeping a combined context only when analyzing selected language features, we can closely approximate the precision of an analysis that keeps both contexts at all times. In terms of speed, the selective combination of both kinds of context not only vastly outperforms non-selective combinations but is also faster than a mere object-sensitive analysis. This result holds for a large array of analyses (e.g., 1-object-sensitive, 2-object-sensitive with a context-sensitive heap, type-sensitive) establishing a new set of performance/precision sweet spots.

Supplementary Material

ZIP File (pldi246.zip)

Included here are the .pdf files for the plots used in the main pldi246-kastrinis.tex file

Download
83.41 KB

References

[1]

K. Ali and O. Lhoták. Application-only call graph construction. In European Conf. on Object-Oriented Programming (ECOOP), 2012.

Digital Library

[2]

L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, 1994.

[3]

M. Berndl, O. Lhoták, F. Qian, L. J. Hendren, and N. Umanee. Points-to analysis using BDDs. In Conf. on Programming Language Design and Implementation (PLDI), 2003.

Digital Library

[4]

M. Bravenboer and Y. Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Conf. on Object Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2009.

Digital Library

[5]

M. Eichberg, S. Kloppenburg, K. Klose, and M. Mezini. Defining and continuous checking of structural program dependencies. In Int. Conf. on Software engineering (ICSE), 2008.

Digital Library

[6]

S. Guarnieri and B. Livshits. GateKeeper: mostly static enforcement of security and reliability policies for Javascript code. In Proceedings of the 18th USENIX Security Symposium, 2009.

Digital Library

[7]

E. Hajiyev, M. Verbaere, and O. de Moor. Codequest: Scalable source code queries with Datalog. In European Conf. on Object-Oriented Programming (ECOOP), 2006.

Digital Library

[8]

B. Hardekopf and C. Lin. The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In Conf. on Programming Language Design and Implementation (PLDI), 2007.

Digital Library

[9]

B. Hardekopf and C. Lin. Semi-sparse flow-sensitive pointer analysis. In Symposium on Principles of Programming Languages (POPL), 2009.

Digital Library

[10]

N. Heintze and O. Tardieu. Demand-driven pointer analysis. In Conf. on Programming Language Design and Implementation (PLDI), 2001.

Digital Library

[11]

M. S. Lam, J. Whaley, V. B. Livshits, M. C. Martin, D. Avots, M. Carbin, and C. Unkel. Context-sensitive program analysis as database queries. In Symposium on Principles of Database Systems (PODS), 2005.

Digital Library

[12]

O. Lhoták. Program Analysis using Binary Decision Diagrams. PhD thesis, McGill University, 2006.

[13]

O. Lhoták and K.-C. A. Chung. Points-to analysis with efficient strong updates. In Symposium on Principles of Programming Languages (POPL), 2011.

Digital Library

[14]

O. Lhoták and L. Hendren. Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Trans. Softw. Eng. Methodol., 18(1):1--53, 2008.

Digital Library

[15]

P. Liang and M. Naik. Scaling abstraction refinement via pruning. In Conf. on Programming Language Design and Implementation (PLDI), 2011.

Digital Library

[16]

M. Madsen, B. Livshits, and M. Fanning. Practical static analysis of Javascript applications in the presence of frameworks and libraries. Technical Report MSR-TR-2012--66, Microsoft Research, 2012.

[17]

M. Might, Y. Smaragdakis, and D. Van Horn. Resolving and exploiting the k-CFA paradox: Illuminating functional vs. object-oriented program analysis. In Conf. on Programming Language Design and Implementation (PLDI), 2010.

Digital Library

[18]

A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to and side-effect analyses for Java. In International Symposium on Software Testing and Analysis (ISSTA), 2002.

Digital Library

[19]

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.

Digital Library

[20]

T. Reps. Demand interprocedural program analysis using logic databases. In Applications of Logic Databases, 1994.

[21]

T. W. Reps. Solving demand versions of interprocedural analysis problems. In Int. Conf. on Compiler Construction (CC), 1994.

Digital Library

[22]

M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis, 1981.

[23]

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

Digital Library

[24]

Y. Smaragdakis, M. Bravenboer, and O. Lhoták. Pick your contexts well: Understanding object-sensitivity (the making of a precise and scalable pointer analysis). In Symposium on Principles of Programming Languages (POPL), 2011.

Digital Library

[25]

M. Sridharan and R. Bodík. Refinement-based context-sensitive points-to analysis for Java. In Conf. on Programming Language Design and Implementation (PLDI), 2006.

Digital Library

[26]

M. Sridharan, D. Gopan, L. Shan, and R. Bodík. Demand-driven points-to analysis for Java. In Conf. on Object Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2005.

Digital Library

[27]

O. Tripp, M. Pistoia, S. J. Fink, M. Sridharan, and O. Weisman. Taj: effective taint analysis of web applications. In Conf. on Programming Language Design and Implementation (PLDI), 2009.

Digital Library

[28]

R. Vallée-Rai, E. Gagnon, L. J. Hendren, P. Lam, P. Pominville, and V. Sundaresan. Optimizing Java bytecode using the Soot framework: Is it feasible? In Int. Conf. on Compiler Construction (CC), 2000.

Digital Library

[29]

R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java optimization framework. In Proceedings of CASCON 1999, 1999.

[30]

J. Whaley, D. Avots, M. Carbin, and M. S. Lam. Using Datalog with binary decision diagrams for program analysis. In APLAS, 2005.

Digital Library

[31]

J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Conf. on Programming Language Design and Implementation (PLDI), 2004.

Digital Library

[32]

X. Zheng and R. Rugina. Demand-driven alias analysis for c. In Symposium on Principles of Programming Languages (POPL), 2008.

Digital Library

Cited By

Gumarac M(2024)Extent of spending behavior, problems encountered, and financial knowledge across generational cohorts among state universities and colleges employeesInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02411:2(230-237)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.024
Halalingaiah SSundaresan VMaier DNandivada V(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
https://dl.acm.org/doi/10.1145/3689803
Laursen MXu WMøller A(2024)Reducing Static Analysis Unsoundness with Approximate InterpretationProceedings of the ACM on Programming Languages10.1145/36564248:PLDI(1165-1188)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656424
Show More Cited By

Index Terms

Hybrid context-sensitivity for points-to analysis
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Data-driven context-sensitivity for points-to analysis

We present a new data-driven approach to achieve highly cost-effective context-sensitive points-to analysis for Java. While context-sensitivity has greater impact on the analysis precision and performance than any other precision-improving techniques, ...
Introspective analysis: context-sensitivity, across the board
PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation

Context-sensitivity is the primary approach for adding more precision to a points-to analysis, while hopefully also maintaining scalability. An oft-reported problem with context-sensitive analyses, however, is that they are bi-modal: either the analysis ...
Pick your contexts well: understanding object-sensitivity
POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Object-sensitivity has emerged as an excellent context abstraction for points-to analysis in object-oriented languages. Despite its practical success, however, object-sensitivity is poorly understood. For instance, for a context depth of 2 or higher, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2013

546 pages

ISBN:9781450320146

DOI:10.1145/2491956

General Chair:
Hans-J. Boehm
HP Labs
,
Program Chair:
Cormac Flanagan
University of California, Santa Cruz

ACM SIGPLAN Notices Volume 48, Issue 6
PLDI '13
June 2013
515 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2499370
Issue’s Table of Contents

Copyright © 2013 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: 16 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '13

Sponsor:

SIGPLAN

PLDI '13: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 16 - 19, 2013

Washington, Seattle, USA

Acceptance Rates

PLDI '13 Paper Acceptance Rate 46 of 267 submissions, 17%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

134
Total Citations
View Citations
618
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gumarac M(2024)Extent of spending behavior, problems encountered, and financial knowledge across generational cohorts among state universities and colleges employeesInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02411:2(230-237)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.024
Halalingaiah SSundaresan VMaier DNandivada V(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
https://dl.acm.org/doi/10.1145/3689803
Laursen MXu WMøller A(2024)Reducing Static Analysis Unsoundness with Approximate InterpretationProceedings of the ACM on Programming Languages10.1145/36564248:PLDI(1165-1188)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656424
Wimmer CStancu CKozak DWürthinger T(2024)Scaling Type-Based Points-to Analysis with SaturationProceedings of the ACM on Programming Languages10.1145/36564178:PLDI(990-1013)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656417
Erhard JSchinabeck JSchwarz MSeidl HMonat RRubio-González C(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
https://dl.acm.org/doi/10.1145/3652588.3663321
Blumschein CNiephaus FStancu CWimmer CLincke JHirschfeld RChristakis MPradel M(2024)Finding Cuts in Static Analysis Graphs to Debloat SoftwareProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680306(603-614)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680306
Zhang YShi YZhang X(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
https://dl.acm.org/doi/10.1145/3649845
Bao YZhang CSu K(2024)Call-Graph-Based Context-Sensitive Points-to Analysis for JavaIEEE Transactions on Reliability10.1109/TR.2023.323699073:2(851-860)Online publication date: Jun-2024
https://doi.org/10.1109/TR.2023.3236990
Tan TLi YJust RFraser G(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
https://dl.acm.org/doi/10.1145/3597926.3598120
Ma WYang STan TMa XXu CLi Y(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
https://dl.acm.org/doi/10.1145/3591242
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