John Kodumal
Alex Aiken
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.
- 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.]]Google Scholar
Cross Ref
- 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.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- N. Heintze. Set Based Program Analysis. PhD dissertation, Carnegie Mellon University, Department of Computer Science, Oct. 1992.]] Google ScholarDigital Library
- N. Heintze and O. Tardieu. Demand-driven Pointer Analysis. In SIGPLAN Conference on Programming Language Design and Implementation, pages 24--34, 2001.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- S. Horwitz, T. Reps, and D. Binkley. Interprocedural Slicing Using Dependence Graphs. ACM Transactions on Programming Languages and Systems, 12(1):26--60, 1990.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- J. Kodumal. BANSHEE: A Toolkit for Building Constraint-Based Analyses. http://bane.cs.berkeley.edu/banshee.]]Google Scholar
- 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.]] Google ScholarDigital Library
- D. Melski and T. Reps. Interconvertibility of a Class of Set Constraints and Context-Free-Language Reachability. Theoretical Computer Science, 248:29--98, 2000.]] Google ScholarDigital Library
- C. Mossin. Flow Analysis of Typed Higher-Order Programs. PhD thesis, DIKU, Department of Computer Science, University of Copenhagen, 1996.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- T. Reps. Program Analysis Via Graph Reachability. In Information and Software Technology, pages 701--726, 1998.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
Index Terms
- The set constraint/CFL reachability connection in practice
Recommendations
The set constraint/CFL reachability connection in practice
PLDI '04Many 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 conferenceA 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 ImplementationA 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