research-article

Demand-driven alias analysis for C

Authors:

Radu RuginaAuthors Info & Claims

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 197 - 208

https://doi.org/10.1145/1328438.1328464

Published: 07 January 2008 Publication History

Abstract

This paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. The analysis uses a worklist algorithm that gradually explores the program structure and stops as soon as enough evidence is gathered to answer the query. Unlike existing techniques, our approach does not require building or intersecting points-to sets.

Experiments show that our technique is effective at answering alias queries accurately and efficiently in a demand-driven fashion. For a set of alias queries from the SPEC2000 benchmarks, an implementation of our analysis is able to accurately answer 96% of the queries in 0.5 milliseconds per query on average, using only 65 KB of memory. Compared to a demand-driven points-to analysis that constructs and intersects points-to sets on the fly, our alias analysis can achieve better accuracy while running more than 30 times faster. The low run-time cost and low memory demands of the analysis make it a very good candidate not only for compilers, but also for interactive tools, such as program understanding tools or integrated development environments (IDEs).

References

[1]

R. Alur and M. Yannakakis. Model checking of hierarchical state machines. In Proceedings of the 6th ACM SIGSOFT international Symposium on the Foundations of Software Engineering, Lake Buena Vista, FL, November 1998.

Digital Library

[2]

R. Alur, K. Etessami, and M. Yannakakis. Analysis of recursive state machines. In Proceedings of the 13th International Conference on Computer Aided Verification, Paris, France, July 2001.

Digital Library

[3]

Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.

[4]

M. Benedikt, P. Godefroid, and T. Reps. Model checking of unrestricted hierarchical state machines. In Proceedings of the Twenty--Eighth Interantional Colloquium on Automata, Languages, and Programming, Crete, Greece, July 2001.

Digital Library

[5]

J. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the Twentieth Annual Symposium on Principles of Programming Languages, Charleston, SC, January 1993.

Digital Library

[6]

M. Das, B. Liblit, M. Fahndrich, and J. Rehof. Estimating the impact of scalable pointer analysis on optimization. In Proceedings of the International Static Analysis Symposium, Paris, France, July 2001.

Digital Library

[7]

Manuvir Das. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, Vancouver, Canada, June 2000.

Digital Library

[8]

M. Fahndrich, J. Foster, Z. Su, and A. Aiken. Partial online cycle elimination in inclusion constraint graphs. In In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998.

Digital Library

[9]

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

Digital Library

[10]

R. Ghiya, D. Lavery, and D. Sehr. On the importance of points-to analysis and other memory disambiguation methods for C programs. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, Snowbird, UT, June 2001.

Digital Library

[11]

N. Heintze and O. Tardieu. Demand-driven pointer analysis. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, Snowbird, UT, June 2001.

Digital Library

[12]

Michael Hind. Pointer analysis: Haven't we solved this problem yet? In Proceedings of the SIGPLAN-SIGSOFT '01 Workshop on Program Analysis for Software Tools and Engineering, Snowbird, UT, June 2001.

Digital Library

[13]

B. Kernighan and D. Ritchie. The C Programming Language. Prentice-Hall, second edition, 1988.

Digital Library

[14]

J. Kodumal and A. Aiken. The set constraint/CFL reachability connection in practice. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, Washington, DC, June 2004.

Digital Library

[15]

J. Kodumal and A. Aiken. Banshee: A scalable constraint-based analysis toolkit. In In Proceedings of the International Static Analysis Symposium, London, UK, September 2005.

Digital Library

[16]

W. Landi and B. Ryder. A safe approximation algorithm for interprocedural pointer aliasing. In Proceedings of the ACM SIGPLAN'92 Conference on Programming Language Design and Implementation, San Francisco, CA, June 1992.

Digital Library

[17]

C. Lattner, A. Lenharth, and V. Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, June 2007.

Digital Library

[18]

D. Maydan, J. Hennessy, and M. Lam. Efficient and exact data dependence analysis. In Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, June 1991.

Digital Library

[19]

T. Reps, S. Horowitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 22nd Annual ACM Symposium on the Principles of Programming Languages, San Francisco, CA, January 1995.

Digital Library

[20]

Thomas Reps. Program analysis via graph reachability. In Proceedings of the International Logic Programming Symposium, Port Jefferson, NY, October 1997.

Digital Library

[21]

R. Rugina, M. Orlovich, and X. Zheng. Crystal: A program analysis system for C. URL: http://www.cs.cornell.edu/projects/crystal.

[22]

D. Saha and C. R. Ramakrishnan. Incremental and demand-driven points-to analysis using logic programming. In Proceedings of the 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, July 2005.

Digital Library

[23]

M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice Hall Inc, 1981.

[24]

M. Sridharan and R. Bodik. Refinement-based context-sensitive points-to analysis for Java. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, Ottawa, Canada, June 2006.

Digital Library

[25]

M. Sridharan, D. Gopan, L. Shan, and R. Bodik. Demand-driven points-to analysis for Java. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object--Oriented Programming, Systems, Languages, and Applications, San Diego, CA, October 2005.

Digital Library

[26]

Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg Beach, FL, January 1996.

Digital Library

Cited By

Li TBai JSui YHu S(2024)SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate AnalysisACM Transactions on Computer Systems10.1145/369525042:3-4(1-40)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3695250
Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Shi CLi HLu JLi LChristakis MPradel M(2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680346
Show More Cited By

Index Terms

Demand-driven alias analysis for C
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

Demand-driven alias analysis for C
POPL '08

This paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. ...
Demand-driven points-to analysis for Java
Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applications

We present a points-to analysis technique suitable for environments with small time and memory budgets, such as just-in-time (JIT) compilers and interactive development environments (IDEs). Our technique is demand-driven, performing only the work ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2008

448 pages

ISBN:9781595936899

DOI:10.1145/1328438

General Chair:
George Necula
University of California, Berkeley
,
Program Chair:
Philip Wadler
University of Edinburgh

ACM SIGPLAN Notices Volume 43, Issue 1
POPL '08
January 2008
420 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1328897
Issue’s Table of Contents

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL08

Sponsor:

POPL08: The 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 7 - 12, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

147
Total Citations
View Citations
1,054
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li TBai JSui YHu S(2024)SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate AnalysisACM Transactions on Computer Systems10.1145/369525042:3-4(1-40)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3695250
Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Shi CLi HLu JLi LChristakis MPradel M(2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680346
Chen QYu CLiu RZhang CWang YWang KSu TWang L(2024)Evaluating the Effectiveness of Deep Learning Models for Foundational Program Analysis TasksProceedings of the ACM on Programming Languages10.1145/36498298:OOPSLA1(500-528)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649829
Krishna SLal APavlogiannis ATuppe O(2024)On-the-Fly Static Analysis via Dynamic Bidirected Dyck ReachabilityProceedings of the ACM on Programming Languages10.1145/36328848:POPL(1239-1268)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632884
Tang WDong DLi SWang CYao PZhou JZhang C(2024) Octopus: Scaling Value-Flow Analysis via Parallel Collection of Realizable Path ConditionsACM Transactions on Software Engineering and Methodology10.1145/363274333:3(1-33)Online publication date: 24-Jan-2024
https://dl.acm.org/doi/10.1145/3632743
Shi CLi HSui YLu JLi LXue J(2024)Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability SolvingIEEE Transactions on Software Engineering10.1109/TSE.2024.343768450:9(2379-2397)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3437684
Li GZhang HZhou JShen WSui YQian ZCalandrino JTroncoso C(2023)A hybrid alias analysis and its application to global variable protection in the linux kernelProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620473(4211-4228)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620473
Chitre KKedia PPurandare R(2023)Rapid: Region-Based Pointer DisambiguationProceedings of the ACM on Programming Languages10.1145/36228597:OOPSLA2(1729-1757)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622859
Cai YZhang C(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
https://dl.acm.org/doi/10.1145/3622833
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