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

article

Regularly annotated set constraints

Authors:

Alex AikenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 42, Issue 6

Pages 331 - 341

https://doi.org/10.1145/1273442.1250772

Published: 10 June 2007 Publication History

Abstract

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 expressible naturally in a single constraint formalism, including such diverse applications as interprocedural dataflow analysis, precise type-based flow analysis, and pushdown model checking.

References

[1]

A. Aiken, M. Fähndrich, J. Foster, and Z. Su. A toolkit for constructing type- and constraint-based program analyses. In Proc. of the Second International Workshop on Types in Compilation, 1998.

Digital Library

[2]

A. Aiken, D. Kozen, M. Vardi, and E. Wimmers. The complexity of set constraints. In Proc. of the 7th Workshop on Computer Science Logic, pages 1--17. Springer-Verlag, 1994.

Digital Library

[3]

R. Alur and P. Madhusudan. Visibly pushdown languages. In Proc. of the Symp. on Theory of Computing, pages 202--211, 2004.

Digital Library

[4]

H. Chen, D. Dean, and D. Wagner. Model checking one million lines of C code. In Proc. of the 11th Annual Network and Distributed System Security Symp., pages 171--185, Feb4-6, 2004.

[5]

H. Chen and D. Wagner. MOPS: An infrastructure for examining security properties of software. In Proc. of the 9th ACM Conf. on Computer and Communications Security, pages 235--244, 2002.

Digital Library

[6]

M. Fähndrich and A. Aiken. Program analysis using mixed term and set constraints. In Proc. of the 4th International Symp. on Static Analysis, pages 114--126. Springer-Verlag, 1997.

Digital Library

[7]

M. Fähndrich, J. Foster, Z. Su, and A. Aiken. Partial online cycle elimination in inclusion constraint graphs. In Proc. of the Conf. on Programming Language Design and Implementation, pages 85--96, June 1998.

Digital Library

[8]

M. Fähndrich, J. Rehof, and M. Das. From polymorphic subtyping to cfl reachability: Context-sensitive flow analysis using instantiation constraints. Technical Report MSR-TR-99-84, Microsoft Research, 1999.

[9]

J. Foster, M. Fähndrich, and A. Aiken. Polymorphic versus Monomorphic Flow-insensitive Points-to Analysis for C. In Proc. of the Static Analysis Symposium, pages 175--198, June 2000.

Digital Library

[10]

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

Digital Library

[11]

N. Heintze and O. Tardieu. Ultra-fast aliasing analysis using CLA: A million lines of c code in a second. In Proc. of the Conf. on Programming Language Design and Implementation, pages 254--263, 2001.

Digital Library

[12]

S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. In Proc. of the Symp. on Foundations of Software Engineering, pages 104--115. ACM Press, 1995.

Digital Library

[13]

T. Jensen, D. L. Metayer, and T. Thorn. Verification of control flow based security properties. In Proc. of the 1999 IEEE Symp. on security and Privacy, 1999.

[14]

J. Kodumal. Banshee: A toolkit for constructing constraint-based analyses. http://banshee.sourceforge.net, 2005.

[15]

J. Kodumal and A. Aiken. The set constraint/CFL reachability connection in practice. In Proc. of the Conf. on Programming Language Design and Implementation, pages 207--218, 2004.

Digital Library

[16]

J. Kodumal and A. Aiken. Banshee: A scalable constraint-based analysis toolkit. In Proc. of the 12th International Static Analysis Symposium, pages 218--234, Sept. 2005.

Digital Library

[17]

O. Lhoták and L. Hendren. Jedd: A BDD-based relational extension of Java. In Proc. of the Conf. on Programming Language Design and Implementation, 2004.

Digital Library

[18]

Y. A. Liu, T. Rothamel, F. Yu, S. D. Stoller, and N. Hu. Parametric regular path queries. In Proc. of the Conf. on Programming Language Design and Implementation, 2004.

Digital Library

[19]

A. Milanova and B. Ryder. Annotated inclusion constraints for precise flow analysis. In IEEE International Conf. on Software Maintenance, Sept. 2005.

Digital Library

[20]

J. Palsberg. Efficient inference of object types. Information and Computation, (123):198--209, 1995.

Digital Library

[21]

J. Rehof and M. Fähndrich. Type-based flow analysis: From polymorphic subtyping to CFL-reachability. In Proc. of the Symp. on Principles of Programming Languages, pages 54--66, Jan. 2001.

Digital Library

[22]

T. Reps. Undecidability of context-sensitive data-dependence analysis. In ACM Trans. Prorgram. Lang. Syst., volume 22, pages 162--186, 2000.

Digital Library

[23]

T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. of the Symp. on Principles of Programming Languages, pages 49--61, Jan. 1995.

Digital Library

[24]

T. Reps, S. Schwoon, and S. Jha. Weighted pushdown systems and their application to interprocedural dataflow analysis. In Proc. 10th Int. Static Analysis Symp., pages 189--213, 2003.

Digital Library

[25]

A. Rountev, A. Milanova, and B. Ryder. Points-to analysis for Java using annotated constraints. In Proc. of the Conf. on Object-Oriented Programming, Systems, Languages, and Applications, pages 43--55, 2001.

Digital Library

[26]

M. Sridharan, D. Gopan, L. Shan, and R. Bodik. Demand-driven points-to analysis for Java. In Proc. of the Conf. on Object-Oriented Programs, Systems, Languages, and Applications, 2005.

Digital Library

[27]

Z. Su, M. Fähndrich, and A. Aiken. Projection merging: Reducing redundancies in inclusion constraint graphs. In Proc. of the Symp. on Principles of Programming Languages, pages 81--95, 2000.

Digital Library

[28]

J. Whaley and M. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proc. of the Conf. on Programming Language Design and Implementation, June 2004.

Digital Library

Cited By

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: Jul-2021
https://doi.org/10.1145/3466820
Cai CZhang QZuo ZNguyen KXu GSu Z(2018)Calling-to-reference context translation via constraint-guided CFL-reachabilityACM SIGPLAN Notices10.1145/3296979.319237853:4(196-210)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192378
Wang KHussain AZuo ZXu GAmiri Sani AChen YTemam OCarter J(2017)GraspanProceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3037697.3037744(389-404)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3037697.3037744
Show More Cited By

Index Terms

Regularly annotated set constraints

Recommendations

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 ...
The set constraint/CFL reachability connection in practice
PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 42, Issue 6

Proceedings of the 2007 PLDI conference

June 2007

491 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1273442

Issue’s Table of Contents

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2007
508 pages
ISBN:9781595936332
DOI:10.1145/1250734
General Chair:
Jeanne Ferrante
University of California, San Diego, USA
,
Program Chair:
Kathryn S. McKinley
University of Texas at Austin, USA

Copyright © 2007 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: 10 June 2007

Published in SIGPLAN Volume 42, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
432
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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: Jul-2021
https://doi.org/10.1145/3466820
Cai CZhang QZuo ZNguyen KXu GSu Z(2018)Calling-to-reference context translation via constraint-guided CFL-reachabilityACM SIGPLAN Notices10.1145/3296979.319237853:4(196-210)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192378
Wang KHussain AZuo ZXu GAmiri Sani AChen YTemam OCarter J(2017)GraspanProceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3037697.3037744(389-404)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3037697.3037744
Saeed AAbdelkader AKhan MNeishaboori AHarras KMohamed A(2019)On Realistic Target Coverage by Autonomous DronesACM Transactions on Sensor Networks10.1145/332551215:3(1-33)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3325512
Cai CZhang QZuo ZNguyen KXu GSu Z(2018)Calling-to-reference context translation via constraint-guided CFL-reachabilityACM SIGPLAN Notices10.1145/3296979.319237853:4(196-210)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192378
Cai CZhang QZuo ZNguyen KXu GSu ZFoster JGrossman D(2018)Calling-to-reference context translation via constraint-guided CFL-reachabilityProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192378(196-210)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192378
Wang KHussain AZuo ZXu GAmiri Sani A(2017)GraspanACM SIGARCH Computer Architecture News10.1145/3093337.303774445:1(389-404)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093337.3037744
Wang KHussain AZuo ZXu GAmiri Sani A(2017)GraspanACM SIGPLAN Notices10.1145/3093336.303774452:4(389-404)Online publication date: 4-Apr-2017
https://dl.acm.org/doi/10.1145/3093336.3037744
Zhang QSu Z(2017)Context-sensitive data-dependence analysis via linear conjunctive language reachabilityACM SIGPLAN Notices10.1145/3093333.300984852:1(344-358)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1145/3093333.3009848
Wang KHussain AZuo ZXu GAmiri Sani A(2017)GraspanACM SIGOPS Operating Systems Review10.1145/3093315.303774451:2(389-404)Online publication date: 4-Apr-2017
https://doi.org/10.1145/3093315.3037744
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 Issue’s Table of Contents