Precise interprocedural dataflow analysis via graph reachability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Precise interprocedural dataflow analysis via graph reachability

Full text

Pdf (1.51 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

San Francisco, California, United States

Pages: 49 - 61

Year of Publication: 1995

ISBN:0-89791-692-1

Authors

Thomas Reps	Computer Sciences Department, Univ. of Wisconsin, 1210 West Dayton Street, Madison, WI
Susan Horwitz	Computer Sciences Department, Univ. of Wisconsin, 1210 West Dayton Street, Madison, WI
Mooly Sagiv	Computer Sciences Department, Univ. of Wisconsin, 1210 West Dayton Street, Madison, WI and IBM Scientific Center, Haifa, Israel

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 34, Downloads (12 Months): 213, Citation Count: 114

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/199448.199462 What is a DOI?

ABSTRACT

The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)—e.g., reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables.Results are reported from a preliminary experimental study of C programs (for the problem of finding possibly-uninitialized variables).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
	3	Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
	4	J. Cai , R. Paige, Program derivation by fixed point computation, Science of Computer Programming, v.11 n.3, p.197-261, April 1989 [doi>10.1016/0167-6423(88)90033-0]
	5	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
	6	D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, ACM SIGPLAN Notices, v.23 n.7, p.47-56, July 1988
	7	Cooper, K.D, and Kennedy, K., "Interprocedural side-effect analysis in linear time," Proceedings of the A CM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7)pp. 57-66 (July 1988).
	8	K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
	9	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	10	Cousot, P. and Cousot, R., "Static determination of dynamic properties of recursive procedures," pp. 237-277 in Formal Descriptions of Programming Concepts, (IFIP WG 2.2, St. Andrews, Canada, August 1977), ed. E.J. Neuhold,North-Holland, New York, NY (1978).
	11	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199461]
	12	Charles N. Fischer , Richard J. LeBlanc, Jr., Crafting a compiler, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
	13	Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, Invariance of Approximate Semantics with Respect to Program Transformations, GI - 11. Jahrestagung in Verbindung mit Third Conference of the European Co-operation in Informatics (ECI), p.1-10, October 20-23, 1981
	14	Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.90-99, June 21-25, 1993, Albuquerque, New Mexico, United States
	15	Holley, L.H. and Rosen, B.K., "Qualified data flow problems," IEEE Transactions on Software Engineering SE-7(1)pp. 60-78 (January 1981).
	16	Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
	17	Horwitz, S., Reps, T., and Sagiv, M., "Demand interprocedural dataflow analysis," Unpublished Report, Computer Sciences Department, University of Wisconsin, Madison, WI 0. (In preparation.)
	18	Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
	19	Kernighan, B.W., "Ratfor- A preprocessor for a rational Fortran," Software- Practice & Experience 5(4) pp. 395-406 (1975).
	20	Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
	21	Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
	22	Knoop, J. and Steffen, B., "Efficient and optimal bit-vector data flow analyses: A uniform interprocedural framework," Bericht Nr. 9309, Institut fuer Informatik und Praktische Mathematik, Christian- Albrechts-Universitaet zu Kiel, KieI, Germany (April 1993).
	23	Lawrence T. Kou, On Live-Dead Analysis for Global Data Flow Problems, Journal of the ACM (JACM), v.24 n.3, p.473-483, July 1977 [doi>10.1145/322017.322027]
	24	William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
	25	Flemming Nielson , Hanne Riis Nielson, Finiteness conditions for fixed point iteration, Proceedings of the 1992 ACM conference on LISP and functional programming, p.96-108, June 22-24, 1992, San Francisco, California, United States
	26	Hanne Riis Nielson , Flemming Nielson, Bounded fixed point iteration, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-82, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143182]
	27	Reps, T., Sagiv, M., and Horwitz, S., "Interprocedural dataflow analysis via graph reachability," TR 94-14, Datalogisk Institut, University of Copenhagen, Copenhagen, Denmark (April 1994). (Available through World Wide Web at ftp://ftp.diku.dk/diku/semantics/papers/D-215.ps.Z.)
	28	Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
	29	Thomas W. Reps, Solving Demand Versions of Interprocedural Analysis Problems, Proceedings of the 5th International Conference on Compiler Construction, p.389-403, April 07-09, 1994
	30	Sagiv, M., Reps, T., and Horwitz, S., "Precise interprocedural dataflow analysis with applications to constant propagation," Unpublished Report, Comp. Sci. Dept., Univ. of Wisconsin, Madison, WI (Oct. 1994). (Submitted for conference publication.)
	31	Sharir, M. and Pnueli, A., "Two approaches to interprocedural data flow analysis," pp. 189-233 in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ (1981).
	32	Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

CITED BY 115

	Carl Gould , Zhendong Su , Premkumar Devanbu, JDBC Checker: A Static Analysis Tool for SQL/JDBC Applications, Proceedings of the 26th International Conference on Software Engineering, p.697-698, May 23-28, 2004
	Hari Hampapuram , Yue Yang , Manuvir Das, Symbolic path simulation in path-sensitive dataflow analysis, ACM SIGSOFT Software Engineering Notes, v.31 n.1, January 2006
	Nomair A. Naeem , Ondrej Lhotak, Validating temporal properties of interacting objects, Companion to the 23rd ACM SIGPLAN conference on Object oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
	Eduard Mehofer , Bernhard Scholz, Probabilistic data flow system with two-edge profiling, ACM SIGPLAN Notices, v.35 n.7, p.65-72, July 2000
	Christian Mossin, Higher-order value flow graphs, Nordic Journal of Computing, v.5 n.3, p.214-234, Fall 1998
	John Field , G. Ramalingam, Identifying procedural structure in Cobol programs, ACM SIGSOFT Software Engineering Notes, v.24 n.5, p.1-10, Sept. 1999
	Krishnendu Chatterjee , Di Ma , Rupak Majumdar , Tian Zhao , Thomas A. Henzinger , Jens Palsberg, Stack size analysis for interrupt-driven programs, Information and Computation, v.194 n.2, p.144-174, November 1, 2004
	Thomas Ball , Sriram K. Rajamani, Bebop: a path-sensitive interprocedural dataflow engine, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.97-103, June 2001, Snowbird, Utah, United States
	Tobias Mann , Morgan Deters , Rob LeGrand , Ron K. Cytron, Static determination of allocation rates to support real-time garbage collection, ACM SIGPLAN Notices, v.40 n.7, July 2005
	David W. Goodwin, Interprocedural dataflow analysis in an executable optimizer, ACM SIGPLAN Notices, v.32 n.5, p.122-133, May 1997
	Benjamin Chelf , Dawson Engler , Seth Hallem, How to write system-specific, static checkers in metal, ACM SIGSOFT Software Engineering Notes, v.28 n.1, p.51-60, January 2003
	Brian Hackett , Manuvir Das , Daniel Wang , Zhe Yang, Modular checking for buffer overflows in the large, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Atanas Rountev , Barbara G. Ryder , William Landi, Data-flow analysis of program fragments, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.235-252, Nov. 1999
	Gagan Agrawal , Liang Guo, Evaluating explicitly context-sensitive program slicing, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.6-12, June 2001, Snowbird, Utah, United States
	G. Ramalingam, Context-sensitive synchronization-sensitive analysis is undecidable, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.416-430, March 2000
	Ju Qian , Baowen Xu, Scenario oriented program slicing, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Yanhong A. Liu , Tom Rothamel , Fuxiang Yu , Scott D. Stoller , Nanjun Hu, Parametric regular path queries, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Sam Kamin , Baris Aktemur , Michael Katelman, Staging static analyses for program generation, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA
	Philip A. Stocks , Barbara G. Ryder , William A. Landi , Sean Zhang, Comparing flow and context sensitivity on the modification-side-effects problem, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.21-31, March 1998
	Carl Gould , Zhendong Su , Premkumar Devanbu, Static Checking of Dynamically Generated Queries in Database Applications, Proceedings of the 26th International Conference on Software Engineering, p.645-654, May 23-28, 2004
	Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France
	Sumit Gulwani , George C. Necula, Precise interprocedural analysis using random interpretation, ACM SIGPLAN Notices, v.40 n.1, p.324-337, January 2005
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Precise Call Graphs for C Programs with Function Pointers, Automated Software Engineering, v.11 n.1, p.7-26, January 2004
	Bageshri Karkare , Uday P. Khedker, An improved bound for call strings based interprocedural analysis of bit vector frameworks, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.6, p.38-es, October 2007
	Sigmund Cherem , Lonnie Princehouse , Radu Rugina, Practical memory leak detection using guarded value-flow analysis, ACM SIGPLAN Notices, v.42 n.6, June 2007
	G. Ramalingam, Data flow frequency analysis, ACM SIGPLAN Notices, v.31 n.5, p.267-277, May 1996
	Markus Müller-Olm , Helmut Seidl, Precise interprocedural analysis through linear algebra, ACM SIGPLAN Notices, v.39 n.1, p.330-341, January 2004
	Christian Fecht , Helmut Seidl, Propagating differences: an efficient new fixpoint algorithm for distributive constraint systems, Nordic Journal of Computing, v.5 n.4, p.304-329, Winter 1998
	Spyridon Triantafyllis , Matthew J. Bridges , Easwaran Raman , Guilherme Ottoni , David I. August, A framework for unrestricted whole-program optimization, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Sharon Shoham , Eran Yahav , Stephen Fink , Marco Pistoia, Static specification mining using automata-based abstractions, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	Alexey Loginov , Eran Yahav , Satish Chandra , Stephen Fink , Noam Rinetzky , Mangala Nanda, Verifying dereference safety via expanding-scope analysis, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Erik Ruf, Partitioning dataflow analyses using types, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.15-26, January 15-17, 1997, Paris, France
	Seth Hallem , Benjamin Chelf , Yichen Xie , Dawson Engler, A system and language for building system-specific, static analyses, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Thomas Ball , Mayur Naik , Sriram K. Rajamani, From symptom to cause: localizing errors in counterexample traces, ACM SIGPLAN Notices, v.38 n.1, p.97-105, January 2003
	John Kodumal , Alex Aiken, The set constraint/CFL reachability connection in practice, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Douglas R. Smith, Requirement enforcement by transformation automata, Proceedings of the 6th workshop on Foundations of aspect-oriented languages, p.5-14, March 13-13, 2007, Vancouver, British Columbia, Canada
	Swarat Chaudhuri, Subcubic algorithms for recursive state machines, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, ACM SIGPLAN Notices, v.35 n.5, p.253-263, May 2000
	Shaz Qadeer , Sriram K. Rajamani , Jakob Rehof, Summarizing procedures in concurrent programs, ACM SIGPLAN Notices, v.39 n.1, p.245-255, January 2004
	Sigmund Cherem , Trishul Chilimbi , Sumit Gulwani, Inferring locks for atomic sections, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Xin Zheng , Radu Rugina, Demand-driven alias analysis for C, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Mary Jean Harrold , Gregg Rothermel , Saurabh Sinha, Computation of interprocedural control dependence, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.11-20, March 1998
	Isil Dillig , Thomas Dillig , Alex Aiken, Sound, complete and scalable path-sensitive analysis, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Youtao Zhang , Rajiv Gupta, Timestamped whole program path representation and its applications, ACM SIGPLAN Notices, v.36 n.5, p.180-190, May 2001
	Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, ACM SIGSOFT Software Engineering Notes, v.20 n.4, p.104-115, Oct. 1995
	David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Rajeev Alur , P. Madhusudan, Visibly pushdown languages, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Roman Manevich , Manu Sridharan , Stephen Adams , Manuvir Das , Zhe Yang, PSE: explaining program failures via postmortem static analysis, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	Patrice Godefroid, Compositional dynamic test generation, ACM SIGPLAN Notices, v.42 n.1, January 2007
	Manu Sridharan , Stephen J. Fink , Rastislav Bodik, Thin slicing, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Rajeev Alur , Swarat Chaudhuri , P. Madhusudan, A fixpoint calculus for local and global program flows, ACM SIGPLAN Notices, v.41 n.1, p.153-165, January 2006
	Gary Wassermann , Zhendong Su, Static detection of cross-site scripting vulnerabilities, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Greta Yorsh , Eran Yahav , Satish Chandra, Generating precise and concise procedure summaries, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, ACM SIGPLAN Notices, v.30 n.6, p.258-269, June 1995
	Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Lingxiao Jiang , Zhendong Su, Osprey: a practical type system for validating dimensional unit correctness of C programs, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Salvatore Torre , Margherita Napoli , Mimmo Parente, The word problem for visibly pushdown languages described by grammars, Formal Methods in System Design, v.31 n.3, p.265-279, December 2007
	John Kodumal , Alex Aiken, Regularly annotated set constraints, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Gary Wassermann , Carl Gould , Zhendong Su , Premkumar Devanbu, Static checking of dynamically generated queries in database applications, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.4, p.14-es, September 2007
	David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, ACM SIGPLAN Notices, v.32 n.12, p.74-89, Dec. 1997
	Damien Sereni , Oege de Moor, Static analysis of aspects, Proceedings of the 2nd international conference on Aspect-oriented software development, p.30-39, March 17-21, 2003, Boston, Massachusetts
	John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Gary Wassermann , Dachuan Yu , Ajay Chander , Dinakar Dhurjati , Hiroshi Inamura , Zhendong Su, Dynamic test input generation for web applications, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	A. Prasad Sistla , V. N. Venkatakrishnan , Michelle Zhou , Hilary Branske, CMV: automatic verification of complete mediation for java virtual machines, Proceedings of the 2008 ACM symposium on Information, computer and communications security, March 18-20, 2008, Tokyo, Japan
	Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, Interprocedural control dependence, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.2, p.209-254, April 2001
	Thomas Reps, Shape analysis as a generalized path problem, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.1-11, June 21-23, 1995, La Jolla, California, United States
	J. Field , D. Goyal , G. Ramalingam , E. Yahav, Typestate verification: abstraction techniques and complexity results, Science of Computer Programming, v.58 n.1-2, p.57-82, October 2005
	Thomas Ball , Sriram K. Rajamani, The SLAM project: debugging system software via static analysis, ACM SIGPLAN Notices, v.37 n.1, p.1-3, Jan. 2002
	Nurit Dor , Stephen Adams , Manuvir Das , Zhe Yang, Software validation via scalable path-sensitive value flow analysis, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	Jeffrey Fischer , Ranjit Jhala , Rupak Majumdar, Joining dataflow with predicates, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States
	Thomas Ball , Rupak Majumdar , Todd Millstein , Sriram K. Rajamani, Automatic predicate abstraction of C programs, ACM SIGPLAN Notices, v.36 n.5, p.203-213, May 2001
	Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
	Ganesh Sittampalam , Oege de Moor , Ken Friis Larsen, Incremental execution of transformation specifications, ACM SIGPLAN Notices, v.39 n.1, p.26-38, January 2004
	Ranjit Jhala , Rupak Majumdar, Interprocedural analysis of asynchronous programs, ACM SIGPLAN Notices, v.42 n.1, January 2007
	Quan Hoang Nguyen , Bernhard Scholz, Computing SSA Form with Matrices, Electronic Notes in Theoretical Computer Science (ENTCS), v.190 n.1, p.121-132, July, 2007
	Thomas Reps , Genevieve Rosay, Precise interprocedural chopping, ACM SIGSOFT Software Engineering Notes, v.20 n.4, p.41-52, Oct. 1995
	Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar , Kenneth L. McMillan, Abstractions from proofs, ACM SIGPLAN Notices, v.39 n.1, p.232-244, January 2004
	Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Pierre Ganty , Rupak Majumdar , Andrey Rybalchenko, Verifying liveness for asynchronous programs, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	G. Ramalingam , Alex Warshavsky , John Field , Deepak Goyal , Mooly Sagiv, Deriving specialized program analyses for certifying component-client conformance, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Peng-Sheng Chen , Yuan-Shin Hwang , Roy Dz-Ching Ju , Jenq Kuen Lee, Interprocedural Probabilistic Pointer Analysis, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.893-907, October 2004
	Thomas Reps, Undecidability of context-sensitive data-independence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.162-186, Jan. 2000
	Yin Liu , Ana Milanova, Static analysis for inference of explicit information flow, Proceedings of the 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, November 09-10, 2008, Atlanta, Georgia
	Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical framework for demand-driven interprocedural data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.992-1030, Nov. 1997
	Manu Sridharan , Rastislav Bodík, Refinement-based context-sensitive points-to analysis for Java, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005
	Thomas Ball , Todd Millstein , Sriram K. Rajamani, Polymorphic predicate abstraction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.314-343, March 2005
	Jakob Rehof , Manuel Fähndrich, Type-base flow analysis: from polymorphic subtyping to CFL-reachability, ACM SIGPLAN Notices, v.36 n.3, p.54-66, March 2001
	Nomair A. Naeem , Ondrej Lhotak, Typestate-like analysis of multiple interacting objects, ACM SIGPLAN Notices, v.43 n.10, September 2008
	Xavier Rival , Laurent Mauborgne, The trace partitioning abstract domain, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.5, p.26-es, August 2007
	Thomas Reps , Stefan Schwoon , Somesh Jha , David Melski, Weighted pushdown systems and their application to interprocedural dataflow analysis, Science of Computer Programming, v.58 n.1-2, p.206-263, October 2005
	Rajeev Alur , Michael Benedikt , Kousha Etessami , Patrice Godefroid , Thomas Reps , Mihalis Yannakakis, Analysis of recursive state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.786-818, July 2005
	Fausto Spoto , Thomas Jensen, Class analyses as abstract interpretations of trace semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.5, p.578-630, September 2003
	Manu Sridharan , Denis Gopan , Lexin Shan , Rastislav Bodík, Demand-driven points-to analysis for Java, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Shaz Qadeer , Dinghao Wu, KISS: keep it simple and sequential, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Gagan Agrawal, Interprocedural Partial Redundancy Elimination With Application to Distributed Memory Compilation, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.609-625, July 1998
	Yuan-Shin Hwang_cor , Joel Saltz, Interprocedural definition-use chains of dynamic pointer-linked data structures, Scientific Programming, v.11 n.1, p.3-37, January 2003
	David Greenfieldboyce , Jeffrey S. Foster, Type qualifier inference for java, ACM SIGPLAN Notices, v.42 n.10, October 2007
	Uwe Assmann, Graph rewrite systems for program optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.4, p.583-637, July 2000
	Cristiano Calcagno , Dino Distefano , Peter O'Hearn , Hongseok Yang, Compositional shape analysis by means of bi-abduction, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Rajeev Alur , P. Madhusudan, Adding nesting structure to words, Journal of the ACM (JACM), v.56 n.3, p.1-43, May 2009
	Mihai Christodorescu , Somesh Jha, Static analysis of executables to detect malicious patterns, Proceedings of the 12th conference on USENIX Security Symposium, p.12-12, August 04-08, 2003, Washington, DC
	Jinlin Yang , David Evans , Deepali Bhardwaj , Thirumalesh Bhat , Manuvir Das, Perracotta: mining temporal API rules from imperfect traces, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Stephen J. Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.17 n.2, p.1-34, April 2008
	Polyvios Pratikakis , Jeffrey S. Foster , Michael Hicks, LOCKSMITH: context-sensitive correlation analysis for race detection, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Complexity of Points-To Analysis of Java in the Presence of Exceptions, IEEE Transactions on Software Engineering, v.27 n.6, p.481-512, June 2001
	G. B. Mund , Rajib Mall, An efficient interprocedural dynamic slicing method, Journal of Systems and Software, v.79 n.6, p.791-806, June 2006
	Westley Weimer , George C. Necula, Exceptional situations and program reliability, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.2, p.1-51, March 2008
	Matthew B. Dwyer , Lori A. Clarke , Jamieson M. Cobleigh , Gleb Naumovich, Flow analysis for verifying properties of concurrent software systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.4, p.359-430, October 2004
	Jeffrey S. Foster , Robert Johnson , John Kodumal , Alex Aiken, Flow-insensitive type qualifiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.1035-1087, November 2006
	Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001
	Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005