http://www.dagstuhl.de/98451

November 9 – 13 , 1998, Event 98451

Advanced Course on the "Principles of Program Analysis"

Organizers

C. Hankin (London), F. Nielson (Aarhus), H. Riis Nielson (Aarhus)

For support, please contact

Heike Clemens

Documents

External Homepage

Program analysis is a collection of techniques for predicting safe and computable properties of programs without actually running them; properties that can be guaranteed to hold for any subsequent execution of the programs. The techniques are firmly based on the semantics of the programs and they are fully automatic. Program analysis has traditionally been used in optimising compilers: to predict cases that can never appear (no code is needed), to keep track of data that already have been computed (no need for recomputation), and to exploit different machine architectures (faster and more specialised code).

Recently, program analysis techniques have successfully been used to validate the safety of software. With the explosive development of the World Wide Web there is a strong demand for guaranteeing safety properties: we simply need to reduce the likelihood of malicious or unintended behaviour. Similar considerations apply to software procured from subcontractors. Safety properties are also of paramount importance in the construction of embedded systems software. Not surprisingly, this development has lead to a number of research projects in the US and in Europe - these projects address problems spanning the industrial, commercial and military sector.

The purpose of this seminar was to give an introduction to four of the main techniques for program analysis:

  • Data Flow Analysis (widely used in the US and Europe),
  • Control Flow Analysis (mainly developed in the US),
  • Abstract Interpretation (mainly developed in France and used by the French Government), and
  • Types and Effects (mainly developed in Europe).

Each of the techniques have been developed by different communities and have a quite extensive literature. The seminar showed that nonetheless there is a large amount of commonality among the approaches - this should help in cultivating the ability to choose the right approach for the task at hand and also in enhancing the power of one approach by exploiting insights developed in other approaches. In the seminar were presented the theoretical foundations for the approaches as well as the main algorithmic techniques needed to construct automatic tools; it was also possible to experiment with existing tools for program analysis.

The seminar is based on a book on "Principles of Program Analysis" by Flemming Nielson, Hanne Riis Nielson and Chris Hankin who also gave the lectures.

Online Publications

We offer several possibilities to publish the results of your event. Please contact marc.herbstritt(at)dagstuhl.de if you are interested.

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 in the library.