Institut für Softwaretechnologie

Hauptseminar Programmanalysen

Thema

Im Hauptseminar werden fortgeschrittene Techniken der (vor allem statischen) Programmanalysen behandelt. Diese Analysen werden im Compilerbau und Software-Reengineering eingesetzt, um automatisch Informationen über ein Programm zu extrahieren. Die so gewonnenen Informationen helfen dann beim Programmverständnis, bei der Fehlersuche, beim Planen von Änderungen und bei der Code-Optimierung. Das Hauptseminar eignet sich besonders für Studenten, die in unserer Abteilung eine Studien- oder Diplomarbeit machen wollen, da die im Hauptseminar erworbenen Kenntnisse für die meisten unserer zu vergebenden Themen nützlich sind.

Themen für das Hauptseminar sind:

1. 4.12.2006, Rico Hauke: [Ausarbeitung] [Folien] Shape analysis (Techniken zur Analyse rekursiver Datenstrukturen)
   • Schwerpunkt:
     Mooly Sagiv, Thomas Reps und Reinhard Wilhelm: Solving shape-analysis problems in languages with destructive updating
   • Im Vergleich:
     Alain Deutsch: Interprocedural May-Alias Analysis for Pointers: Beyond k-limiting

2. nicht vergeben: SSA in Kombination mit PointsTo-Information
   • Schwerpunkt:
     Inkrementeller Aufbau der SSA-Form für die Konstanten-Propagierung unter Berücksichtingung der May-Alias Information
     Ron Cytron Washington, Reid Gershbein: Efficient Accommodation of May-Alias Information in SSA Form (1993)
   • Vergleich dazu:
     Enumerationsschema abgestimmt auf die May-Alias Information mit ähnlichen Eigenschaften wie die SSA-Form.
     Christopher Lapkowski, Laurie J. Hendren: Extended SSA Numbering: Introducing SSA Properties to Languages with Multi-level Pointers

3. 8.1.2007, Artur Bachner: Escape-Analysen

   Der Vortrag soll Technik für Escape-Analysen vorstellen und Anwendungen benennen.

   • A. Salcianu, M. Rinard: Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, 2001
   • J. Whaley, M. Rinard: Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 1999

4. 15.1.2007, Arif Erkilic: Non-Concurrency
   • S.P. Masticola, B.G. Ryder: Non-concurrency Analyses Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming (1993)
   • G. Naumovich, G.S. Avrunin: A Conservative Data Flow Algorithm for Detecting All Pairs of Statements that May Happen in Parallel Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering (1998)
   • G. Naumovich, G.S. Avrunin, L.A. Clarke: An Efficient Algorithm for Computing MHP Information for Concurrent Java Programs Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering (1999)

5. 22.1.2007, Dominik Gunreben: Static detection of deadlocks
   • A. Williams, W. Thies, M. D. Ernst: Static Deadlock Detection for Java Libraries
   • Kontrast dazu:
     S.P. Masticola and B.G. Ryder: A model of Ada programs for static deadlock detection in polynomial time. In Proceedings of Workshop on Parallel and Distributed Debugging. ACM, May 1991.

6. nicht vergeben: Dynamic detection of races
   • Mit Analyse einer locking discipline:
     C. von Praun, T.R. Gross: Object Race Detection Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, 2001
   • Mit vector clocks:
     M. Ronsse, K. de Bosschere: RecPlay: a fully integrated practical record/replay system ACM Transactions on Computer Systems (TOCS), 1999
   • Kombination der beiden Techniken:
     E. Pozniansky, A. Schuster: Efficient on-the-fly data race detection in multithreaded C++ programs Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, 2003

7. 29.1.2007, Miroslav Jakovljevic: Static detection of races
   • Objektorientiert:
     J.-D. Choi, A. Loginov, V. Sarkar: Static Datarace Analysis for Multithreaded Object-Oriented Programs
   • Lock-basiert:
     D. Engler, K. Ashcraft: RacerX: Effective, Static Detection of Race Conditions and Deadlocks (2003)

8. 5.2.2007, Andreas Reuß: Programmabhängigkeiten [Ausarbeitung] [Folien]
   • V.P. Ranganath, T. Amtoft, A. Banerjee, M.B. Dwyer, J. Hatcliff: A New Foundation for Control-Dependence and Slicing for Modern Program Structures (2005)
   • Mary Jean Harrold, Gregg Rothermel, Saurabh Sinha: Computation of Interprocedural Control Dependencies (1998)

9. 12.2.2007, Minh Cuong Tran: Erkennung von Entwurfsmustern [Ausarbeitung] [Folien]

   Der Vortrag soll die verschiedenen Ansätze, auch die zeitliche Entwicklung, und die grundsätzliche Problematik vorstellen. Interessant ist auch die rege deutsche Beteiligung an diesem Thema, sowie die Aktualität. Als Kontext kann Architektur-Erkennung und Programmverstehen sowie der Einsatz von Entwurfsmustern im Forward-Engineering hergenommen werden. Weiter zurück liegt noch die Erkennung von Cliches (v.a. Linda Wills) als Vorstufe zu den Patterns. Das einschlägige Buch der Gang of Four (Gamma etc.) sollte bekannt sein. Es existiert noch weitere Literatur, der Vortragende kann ruhig selbst noch auf Suche gehen, um ein umfassenderes Bild zu bekommen. Bis zum WS könnte auch brauchbares Material aus dem StuPro EMMU vorliegen und eingesetzt werden.

   • Heuzeroth, Holl, Högström, Löwe: Automatic Design Pattern Detection, Proc. 11th IEEE International Workshop on Program Comprehension (IWPC 2003)
   • Krämer, Prechelt: Design Recovery by Automated Search for Structural Design Patterns in Object-Oriented Software, Proc. WCRE 1996
   • Kaczor, Gueheneuc, Hamel: Efficient Identification of Design Patterns with Bit-vector Algorithm, CSMR 2006
   • Niere, Schäfer, Wadsack, Wendehals, Welsh: Towards Pattern-Based Design Recovery, ACM ICSE 2002
   • Tonella, Antoniol: Object Oriented Design Pattern Inference, ICSM 1999
   • Antoniol, Fiutem, Cristoforetti: Using Metrics to Identify Design Patterns in Object-Oriented Software, Proc. 5th International Symposium on Software Metrics (1998)
   • Seemann, von Gudenberg: Pattern-Based Design Recovery of Java Software, ACM SIGSOFT 1998

Als Einstieg empfehlen wir die Folien zur Vorlesung Software-Reengineering (insbesondere das Kapitel zu Zwischendarstellungen)

Bei Fragen wenden Sie sich bitte an die Betreuer aus der Abteilung Programmiersprachen und Compilerbau: Prof. Erhard Plödereder , Steffen Keul , Stefan Staiger , Gunther Vogel , Eduard Wiebe

Organisatorisches

Richtlinien

Die endgültige Ausarbeitung muss uns eine Woche nach dem Vortrag vorliegen, sowohl in ausgedruckter als auch elektronischer Form (Orginaldokument und PDF).

Die Ausarbeitung sollte unbedingt von einem Kommilitonen vor Abgabe auf Rechtschreibfehler etc. geprüft werden.

Die Ausarbeitungen müssen dem zweispaltigen IEEE-Format für Konferenzbeiträge genügen und einen Umfang zwischen 10 und 12 Seiten haben. Unter den folgenden Links gibt es entsprechende Vorlagen.

• für LaTeX (latex8.sty, latex8.bib, latex8.bst, latex8.tex) , außerdem hat Cornelius Walter die Ausgabe der Literaturangaben "eingedeutscht": BibTeX-bst-file
• für Microsoft Word (instruct.doc)
• für Adobe FrameMaker 5.5

Literatursuche

• http://www.acm.org/dl/
• http://www.computer.org/publications/dlib
• http://citeseer.nj.nec.com/cs
• http://dblp.uni-trier.de/
• http://www.google.de