More Web Proxy on the site http://driver.im/

Article

The set constraint/CFL reachability connection in practice

Authors:

Alex AikenAuthors Info & Claims

PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

Pages 207 - 218

https://doi.org/10.1145/996841.996867

Published: 09 June 2004 Publication History

Abstract

Many program analyses can be reduced to graph reachability problems involving a limited form of context-free language reachability called Dyck-CFL reachability. We show a new reduction from Dyck-CFL reachability to set constraints that can be used in practice to solve these problems. Our reduction is much simpler than the general reduction from context-free language reachability to set constraints. We have implemented our reduction on top of a set constraints toolkit and tested its performance on a substantial polymorphic flow analysis application.

References

[1]

A. Aiken and E. L. Wimmers. Solving Systems of Set Constraints. In Proceedings, Seventh Annual IEEE Symposium on Logic in Computer Science, pages 329--340, Santa Cruz, California, June 1992.]]

[2]

V. Choppella and C. T. Haynes. Source-tracking Unification. In F. Baader, editor, Automated Deduction - CADE-19, 19th International Conference on Automated Deduction Miami Beach, FL, USA, July 28 - August 2, 2003, Proceedings, volume 2741 of Lecture Notes in Computer Science, pages 458--472. Springer, 2003.]]

[3]

M. Das, B. Liblit, M. Fähndrich, and J. Rehof. Estimating the Impact of Scalable Pointer Analysis on Optimization. In SAS '01: The 8th International Static Analysis Symposium, Lecture Notes in Computer Science, Paris, France, July 16--18 2001. Springer-Verlag.]]

Digital Library

[4]

M. Fähndrich, J. S. Foster, Z. Su, and A. Aiken. Partial Online Cycle Elimination in Inclusion Constraint Graphs. In Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 85--96, Montreal, Canada, June 1998.]]

Digital Library

[5]

J. S. Foster, M. Fähndrich, and A. Aiken. A Theory of Type Qualifiers. In Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 192--203, Atlanta, Georgia, May 1999.]]

Digital Library

[6]

N. Heintze. Set Based Program Analysis. PhD dissertation, Carnegie Mellon University, Department of Computer Science, Oct. 1992.]]

Digital Library

[7]

N. Heintze and O. Tardieu. Demand-driven Pointer Analysis. In SIGPLAN Conference on Programming Language Design and Implementation, pages 24--34, 2001.]]

Digital Library

[8]

N. Heintze and O. Tardieu. Ultra-fast Aliasing Analysis Using CLA: A Million Lines of C Code in a Second. In SIGPLAN Conference on Programming Language Design and Implementation, pages 254--263, 2001.]]

Digital Library

[9]

S. Horwitz, T. Reps, and D. Binkley. Interprocedural Slicing Using Dependence Graphs. ACM Transactions on Programming Languages and Systems, 12(1):26--60, 1990.]]

Digital Library

[10]

S. Horwitz, T. Reps, and M. Sagiv. Demand Interprocedural Dataflow Analysis. In Proceedings of the 3rd ACM SIGSOFT Symposium on Foundations of Software Engineering, pages 104--115. ACM Press, 1995.]]

Digital Library

[11]

J. Kodumal. BANSHEE: A Toolkit for Building Constraint-Based Analyses. http://bane.cs.berkeley.edu/banshee.]]

[12]

D. Melski and T. Reps. Interconvertbility of Set Constraints and Context-Free Language Reachability. In Proceedings of the 1997 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, pages 74--89. ACM Press, 1997.]]

Digital Library

[13]

D. Melski and T. Reps. Interconvertibility of a Class of Set Constraints and Context-Free-Language Reachability. Theoretical Computer Science, 248:29--98, 2000.]]

Digital Library

[14]

C. Mossin. Flow Analysis of Typed Higher-Order Programs. PhD thesis, DIKU, Department of Computer Science, University of Copenhagen, 1996.]]

[15]

J. Rehof and M. Fähndrich. Type-Based Flow Analysis: From Polymorphic Subtyping to CFL-Reachability. In Proceedings of the 28th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 54--66, London, United Kingdom, Jan. 2001.]]

Digital Library

[16]

T. Reps. Shape Analysis as a Generalized Path Problem. In Proceedings of the 1995 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program manipulation, pages 1--11. ACM Press, 1995.]]

Digital Library

[17]

T. Reps. Program Analysis Via Graph Reachability. In Information and Software Technology, pages 701--726, 1998.]]

[18]

T. Reps, S. Horwitz, and M. Sagiv. Precise Interprocedural Dataflow Analysis via Graph Reachability. In Proceedings of the 22nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 49--61, San Francisco, California, Jan. 1995.]]

Digital Library

[19]

A. Rountev and S. Chandra. Off-line Variable Substitution for Scaling Points-to Analysis. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 47--56. ACM Press, 2000.]]

Digital Library

[20]

U. Shankar, K. Talwar, J. S. Foster, and D. Wagner. Detecting Format String Vulnerabilities with Type Qualifiers. In Proceedings of the 10th Usenix Security Symposium, Washington, D.C., Aug. 2001.]]

Digital Library

[21]

Z. Su, M. Fähndrich, and A. Aiken. Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 81--95. ACM Press, 2000.]]

Digital Library

Cited By

Li HShi CLu JLi LXue J(2024)Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment TransformersProceedings of the ACM on Programming Languages10.1145/36898048:OOPSLA2(2633-2661)Online publication date: 8-Oct-2024
https://doi.org/10.1145/3689804
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
Li YZhang QReps T(2023)Single-Source-Single-Target Interleaved-Dyck Reachability via Integer Linear ProgrammingProceedings of the ACM on Programming Languages10.1145/35712287:POPL(1003-1026)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571228
Show More Cited By

Index Terms

The set constraint/CFL reachability connection in practice

Recommendations

The set constraint/CFL reachability connection in practice
PLDI '04

Many program analyses can be reduced to graph reachability problems involving a limited form of context-free language reachability called Dyck-CFL reachability. We show a new reduction from Dyck-CFL reachability to set constraints that can be used in ...
Regularly annotated set constraints
Proceedings of the 2007 PLDI conference

A general class of program analyses area combination of context-free and regular language reachability. We define regularly annotated set constraints, a constraint formalism that captures this class. Our results extend the class of reachability problems ...
Regularly annotated set constraints
PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

A general class of program analyses area combination of context-free and regular language reachability. We define regularly annotated set constraints, a constraint formalism that captures this class. Our results extend the class of reachability problems ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI04

Sponsor:

PLDI04: ACM SIGPLAN Conference on Programming Language Design and Implementation 2004

June 9 - 11, 2004

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

88
Total Citations
View Citations
739
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)10

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li HShi CLu JLi LXue J(2024)Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment TransformersProceedings of the ACM on Programming Languages10.1145/36898048:OOPSLA2(2633-2661)Online publication date: 8-Oct-2024
https://doi.org/10.1145/3689804
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
Li YZhang QReps T(2023)Single-Source-Single-Target Interleaved-Dyck Reachability via Integer Linear ProgrammingProceedings of the ACM on Programming Languages10.1145/35712287:POPL(1003-1026)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571228
He DLu JGao YXue J(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
https://doi.org/10.1109/TSE.2022.3162236
Ding SZhang Q(2023)Mutual Refinements of Context-Free Language ReachabilityStatic Analysis10.1007/978-3-031-44245-2_12(231-258)Online publication date: 24-Oct-2023
https://doi.org/10.1007/978-3-031-44245-2_12
Shi QWang YYao PZhang C(2022)Indexing the extended Dyck-CFL reachability for context-sensitive program analysisProceedings of the ACM on Programming Languages10.1145/35633396:OOPSLA2(1438-1468)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563339
Christakis MCottenier TFilieri ALuo LMansur MPike LRosner NSchäf MSengupta AVisser WRoychoudhury ACadar CKim M(2022)Input splitting for cloud-based static application security testing platformsProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3558944(1367-1378)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3558944
Li YSatya KZhang Q(2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498724
Li YZhang QReps T(2022)Fast Graph Simplification for Interleaved-Dyck ReachabilityACM Transactions on Programming Languages and Systems10.1145/349242844:2(1-28)Online publication date: 27-May-2022
https://dl.acm.org/doi/10.1145/3492428
Zuo ZZhang YPan QLu SLi YWang LLi XXu GFreund SYahav E(2021)Chianina: an evolving graph system for flow- and context-sensitive analyses of million lines of C codeProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454085(914-929)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454085
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