Program Analysis via Graph Reachability

Thomas Reps
University of Wisconsin

This talk will describe how a number of program-analysis problems can be solved by transforming them to special kinds of graph-reachability problems. (These reachability problems can also be viewed as inference problems, where solving a problem involves inferring the presence or absence of certain kinds of paths in the graph.) Some of the program-analysis problems that are amenable to this treatment include:

The relationship of the graph-reachability approach to other approaches to program analysis, such as set constraints, will be described. Finally, some techniques that go beyond pure graph reachability will be discussed. The talk is based in part on joint work with Susan Horwitz, Mooly Sagiv, Genevieve Rosay, and David Melski. Various papers concerning the material covered are available over the World Wide Web at URL http://www.cs.wisc.edu/~reps/.

Speaker profile

Thomas Reps is Professor of Computer Science in the Computer Sciences Department at the University of Wisconsin, which he joined in 1985, where he also holds the title of Vilas Associate. Reps is the author or co-author of three books and over fifty papers describing his research. His work has concerned a wide variety of topics, including program slicing, dataflow analysis, pointer analysis, language-based program-development environments, the use of program profiling in software testing, "intelligent" conversion of C programs to C++, incremental algorithms, and attribute grammars.

His collaboration with Tim Teitelbaum at Cornell University from 1978 to 1985 led to the creation of two systems --- the Cornell Program Synthesizer and the Synthesizer Generator --- that explored how to build interactive programming tools that incorporate knowledge about the programming language being supported. Reps is the inventor of the attribute-grammar paradigm for incremental static-semantic analysis of programs, which is used in the Synthesizer Generator. Reps is President of GrammaTech, Inc., which he and Teitelbaum founded in 1988 to commercialize this work.

Since 1985, Professor Reps has led a research group at the University of Wisconsin investigating program slicing and its applications in software engineering. As part of this effort, Reps has been the principal investigator for three DARPA-supported projects. His work has also been funded by the National Science Foundation continuously since 1986.

Recently, Reps served as a consultant to DARPA to help them plan a project aimed at reducing the impact of the Year 2000 Problem on the Department of Defense.

Professor Reps's Ph.D. dissertation won the 1983 ACM Doctoral Dissertation Award. He received an IBM Faculty Development Award in 1986, an NSF Presidential Young Investigator Award in 1986, and a David and Lucile Packard Foundation Fellowship for Science and Engineering in 1988.

11 Aug 1997, Ulf Nilsson