Seminar Statische Programmanalyse

Die Statische Programmanalyse bietet eine Reihe von Techniken zur Quelltextanalyse von Programmen. Mittels dieser Techniken können approximativ Informationen über das dynamische Verhalten der Programme berechnet werden, wie z.B. toter Quelltext oder uninitialisierte Variablen. Die Hauptanwendung Statischer Programmanalyse ist die Optimierung von Quelltext im Compilerbau. Dieses Seminar gibt einen Überblick über bestehende Techniken und ihre Anwendungsmöglichkeiten.

Aktuell

Dozent

• Peter Massuthe

Telefon:	+49-30-2093-3071
Raum:	RUD 25, 4.414
E-Mail:	massuthe @ informatik.hu-berlin.de

Termin

Der erste Seminartermin ist Mittwoch, der 19. Oktober 2005.

Material

Die Kurzvorträge orientieren sich weitestgehend (bis auf Slicing) an folgendem Buch:

• Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Principles of Program Analysis. Springer-Verlag 1998.

Ein Überblick über das Thema:

• Michael I. Schwartzbach. Lecture Notes on Static Analysis.

Aus der Einführungsveranstaltung:

• Wolfgang Reisig. Wie hält man einen guten Vortrag?

Für die Langvorträge werden an dieser Stelle entsprechende Paper angegeben.

Ablauf

Das Seminar ist für 16 Teilnehmer geplant. Jeder Teilnehmer bearbeitet ein Kurzthema (15 Minuten Vortrag + 15 Minuten Diskussion) und ein Langthema (30 Minuten Vortrag + 15 Minuten Diskussion). Am ersten Termin (19.10.2005) werden die Kurzthemen verteilt. Zur Vorbereitung fällt der zweite Termin (26.10.2005) aus. Ab dem dritten Termin (02.11.2005) werden jeweils drei Kurzthemen vorgetragen. Am siebten Termin (30.11.2005) werden dann die Langthemen verteilt, von denen ab dem neunten Termin (14.12.2005) jeweils zwei vorgetragen werden.

Themen

1. Datenflussgleichungen

   • Kurzthemen:
     1. Available Expression Analysis (Kapitel 2.1.1)
     2. Reaching Definitions Analysis (Kapitel 2.1.2)
     3. Very Busy Expressions Analysis (Kapitel 2.1.3)
     4. Live Variables Analysis (Kapitel 2.1.4)
     5. Derived Data Flow Information (Kapitel 2.1.5)
   
   
   • Langthemen:
     1. Interprocedural Analysis („ ...wenn das Programm Funktionsaufrufe enhält“)
        • Buch, Kapitel 2.5
     2. Shape Analyis („ ...wenn das Programm Pointer benutzt“)
        • Buch, Kapitel 2.6
     3. Anwendung: Analyse von Strings
        • Schwartzbach 2003 Precise Analysis of String Expressions
     4. Static Single Assignement
        • Alpern et al. 1988 Detecting equality of variables in programs
        • Yang et al. 1989 Detecting Program Components With Equivalent Behaviors
     5. Datenflußanalyse für Paralellismus
        • Grunwald et al. 1993 Data Flow Equations for Explicitly Parallel Programs
        • Srinivasan 1991 Analyzing programs with explicit parallelism

2. Constraint-basierte Analyse

   • Kurzthemen:
     1. Abstract 0-CFA Analysis (Kapitel 3.1)
     2. Syntax Directed 0-CFA Analysis (Kapitel 3.3)
     3. Contraint Based 0-CFA Analysis (Kapitel 3.4)
   
   
   • Langthemen:
     1. Adding Data Flow Analysis
        • Buch, Kapitel 3.5
     2. Adding Context Information
        • Buch, Kapitel 3.6

3. Abstrakte Interpretation

   • Kurzthemen:
     1. A Mundane Approach to Correctness (Kapitel 4.1)
     2. Approximating Fixed Points (Kapitel 4.2)
     3. Galois Connections (Kapitel 4.3)
     4. Systematic Design of Galois Connections (Kapitel 4.4)
   
   
   • Langthemen:
     1. Induced Operations
        • Buch, Kapitel 4.5
     2. Anwendung auf VHDL
        • Charles Hymans Checking Safety Properties of Behavioural VHFL Descriptions by Abstract Interpretation
     3. Anwendung auf VHDL
        • Thomson & Mycroft Abstract interpretation of asynchronous circuits
     4. Anwendung für Model Checking und Abstraktion
        • Orna Grumberg 1997 Abstract interpretation of reactive systems

4. Type and Effect Analyse

   • Kurzthemen:
     1. Control Flow Analysis (Kapitel 5.1)
     2. Effects (Kapitel 5.4)
     3. Behaviours (Kapitel 5.5)
   • Langthemen:
     1. Behaviours
        • Buch, Kapitel 5.5
     2. Anwendung: Typsichere Optimierung
        • Palsberg 2005 Type-Safe Optimisation of Plugin Architectures

5. Slicing

   • Kurzthema:
     1. Statisches vs. dynamisches Slicing
        • F. Tip. A survey of program slicing techniques. Technical Report CS-R9438, Centrum voor Wiskunde en Informatica, 1994.
        • D. Binkley and K. Gallagher. Program slicing. In M. Zelkowitz, editor, Advances in Computers, Vol. 43. Academic Press, San Diego, CA, 1996.
   • Langthemen:
     1. Statisches Slicing
        • s. Kurzthema
     2. Dynamisches Slicing
        • s. Kurzthema

Termine