April 11 – 16 , 1999, Dagstuhl Seminar 99151

Program Analysis


H. Riis Nielson (Aarhus), M. Sagiv (Tel Aviv)

For support, please contact

Dagstuhl Service Team


External Homepage
Dagstuhl-Seminar-Report 236


Program analysis offers static techniques for predicting safe and computable approximations to the set of values or behaviors arising dynamically during the execution of programs. Traditionally, program analysis has been used in optimizing compilers; more recent applications include the validation of safety properties of software for embedded systems, and also program analysis shows promise of becoming an important ingredient in ensuring the acceptable behavior of software components roaming around on information networks.

Over the years a number of different approaches have been developed for program analysis, all of which have a quite extensive literature. To give an impression of the diversity let us briefly mention some of the main approaches: The flow based approach includes the traditional data flow analysis techniques for mainly imperative languages, but also control flow analysis as developed for functional and object oriented languages, and set based analysis as developed for logic and functional languages. The model based approach includes the parameterized denotational semantics techniques developed for functional and imperative languages, but also more generally the use of mathematical modeling in the abstract interpretation of imperative, functional, concurrent and logic languages. The inference based approach includes general logical techniques touching upon program verification techniques, but also the type and effect systems developed for functional, imperative and concurrent languages. For each of the approaches there are theoretical studies of semantic and algorithmic properties as well as practical experiments exploiting the feasibility of the techniques.

Typically, the various techniques have been developed and further refined by subcommunities -- with the result that often the commonalties between analogous developments are not sufficiently appreciated. To guide the research effort in our community, it is necessary with an appraisal of the current technology: we need to understand the strengths and weaknesses of the different approaches, and the extent to which insights developed for one approach can be used to enhance the power of other approaches. The usual measures for strengths of program analysis techniques are:

  • Generality: to which class of programs can the techniques be applied?
  • Precision: how precise are the results of the analysis? can the analysis guarantee a certain level of precision for a given class of programs (this question becomes more important when program analysis is used in application domains such as testing and software engineering)?
  • Efficiency: how long does it take to run the analysis and does it scale up for large programs?

For example, some static analysis techniques limit the size or type of input programs but yield precise results, while others handle programs of arbitrary size and type but without being overly precise.

We believe that a Dagstuhl seminar will be an ideal setting for the subcommunities to share their experience. We are aware that the gap between some of the communities are larger than between others -- to ensure the success of the meeting we have therefore decided not to cover the full spectrum of approaches in this meeting. Also, to help achieving our goal, we plan to invite 6-8 of the participants to give longer talks (60-90 minutes) with more detailed accounts of particular techniques that we believe should be of general interest or that represent important tools or techniques that seem to be somewhat overlooked. The remainder of the talks are expected to be shorter (approx.~30 minutes) and present current work.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.