Hauptseminar Programmanalyse

Montags, 15:00 bis 16:30 Uhr, in 1.035

Inhaltsverzeichnis
1. Termine
2. Themen
3. Ausarbeitungen



`<Rainer Koschke>` `<Thomas Eisenbarth>`

Hier gibt es einen Style-Guide (Tex, Word ...), allerdings für letter.

Termin	Vortragender	Thema
28. Mai	Thomas Eisenbarth	Feature Lokalisierung
11. Juni	Yan Wang	Programm-Zwischendarstellungen
18. Juni	Nikolaos Ntaountakis	Points-To- und Seiteneffektanalysen
25. Juni	Rainer Koschke	Statische und dynamische Extraktion von Traces zur Wiedergewinnung und Validierung von Protokollen
2. Juli	Christian Wolfangel	Statisches und dynamisches Program Slicing
9. Juli	Jens Knodel	Generierung der Static Single Assignment Form (SSA)
16. Juli	Tahir Karaca	Feature-Lokalisierung mit Hilfe statischer und dynamischer Analysen

Wegen Teilnehmerschwund gegenüber der Anmeldeliste sind bisher nur diese Vorträge geplant.

Hintergrund

Das Wirtschaftsgut Software stellt mit stetig wachsender Tendenz einen wesentlichen Kostenfaktor und Ertragsanteil vermarkteter Produkte auch außerhalb der Softwareindustrie dar. Aus diversen Untersuchungen ist bekannt, dass 60-80% der Kosten eines Software-Produkts nach dessen Erstauslieferung entstehen, d.h. in der laufenden Wartung der Software zur Fehlerbeseitigung und Anpassung an geänderte Anforderungen. Studien zeigen, dass Wartungsingenieure weit mehr als die Hälfte ihrer Arbeitszeit damit verbringen, das zu ändernde Programm erst einmal zu verstehen, bevor sie konkrete Änderungen entwerfen und realisieren. Der Grund hierfür ist, dass den Wartungsingenieuren unzureichende Informationen zur Verfügung stehen. Ein großer Teil der Information ließe sich durch entsprechende (halb-)automatische Programmanalysen herleiten. Dazu können teilweise Programmanalysen, die ursprünglich für die Code-Optimierung konzipiert wurden, benutzt werden. Da die Ausrichtung beim Reengineering jedoch eine andere ist als bei der Code-Optimierung, macht Reengineering auch eigene Formen der Programmanalyse (z.T. auch mit Benutzerinteraktion) erforderlich.

Im Hauptseminar Programmanalysen werden Analysetechniken vorgestellt, die das Verstehen von Source Code unterstützen sollen, um die Software-Wartung, das Reverse Engineering oder Reengineering zu unterstützen.

Themen

1. Programm-Zwischendarstellungen

Zwischendarstellungen stellen die Basis für alle Programmanalysen dar. Sie repräsentieren die Syntax (als abstrakter Syntaxbaum) und die Semantik des Programmes (Namensbindung, Kontroll- und Datenfluss). Es gibt eine Vielzahl unterschiedlicher Zwischendarstellungen mit unterschiedlichen Vor- und Nachteilen zur Darstellung unterschiedlicher Aspekte, die in diesem Vortrag dargestellt werden sollen. Eine besondere Anforderung an Zwischendarstellung für das Programmverstehen ist die Quellennähe, so dass die Originalquelle stets aus der Zwischendarstellung wieder hergestellt werden kann.

Compiler - Principles, Techniques, and Tools

Morgan, Building an Optimizing Compiler, Digital Press.

Muchnik, Advanced Compiler Design & Implementation, Morgan Kaufmann Publishers.

R. Koschke, J.-F. Girard, M. Würthner, An Intermediate Representation for Reverse Engineering Analyses, Proceedings of the Working Conference on Reverse Engineering - WCRE '98, 1998.

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependency graph and its uses in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319-349, June 1987.

Keshev Pingali, Micah Bech, Richard Johnson, Mayan Moudgill, and Paul Stodghill. Dependence Flow Graphs: An algebraic approach to program dependencies. In Proceedings of the 18th ACM Symposium on Principles of Programming Languages, January 1991.

Ron Cytron and Jeanne Ferrante and Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transactions on Programming Languages, vol. 13, no. 4, 1991, pp. 451-490.

2. Points-To- und Seiteneffektanalysen

Die Points-To-Analyse ermittelt für Programme mit Zeigern die potenzielle Ziele, auf die ein Zeiger zeigen kann. Die Points-To-Analyse identifiziert nicht offensichtliche Datenabhängigkeiten und ist z.B. auch notwendig für die genaue Ermittlung des Kontrollflusses, falls Funktionen über Zeiger aufgerufen werden. Die vielen Ansätze der Points-To-Analyse lassen sich kategorisieren in kontextsensitive (solche, die für jeden Funkionsaufruf eine Unterscheidung treffen) und kontextinsensitive (solche, die die Verhältnisse an allen Aufrufstellen vereinigen) sowie flusssensitive (solche, die den Kontrollfluss berücksichtigen) und flussinsensitve (solche, die den Kontrollfluss vernachlässigen). Programmiersprachenkonstrukte wie Zeigerarithmetik und Type-Casts erschweren die Analyse.

Auf der Points-To-Information aufbauend ermittelt die Seiteneffektanalyse die Effekte einer beliebigen Anweisung (MayMod und MustMod) sowie deren Datenabhängigkeiten (MayUse).

In diesem Vortrag sollen Analysen zur Ermittlung der Points-To-Information und der Seiteneffekte vorgestellt und bewertet werden.

Marc Shapiro and Susan Horwitz, "Fast and Accurate Flow-Insensitive Points-to Analysis," Conference Record of the Symposium on Principles of Programming Languages, Paris, France, pp. 1-14, January 1997.

Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren, "Context-sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers," SIGPLAN Conference on Programming Languages Design and Implementation, pages 242-256, June 1994.

Robert P. Wilson and Monica S. Lam, "Efficient Context-Sensitive Pointer Analysis for C Programs," In Proceedings of SIGPLAN'95 Conference on Programming Languages Design and Implementation, pages 1-12, June 1995.

Paolo Tonella, Giuliano Antoniol, Roberto Fiutem, and Ettore Merlo, "Flow Insensitive C++ Pointers and Polymorphism Analysis and its Application to Slicing," in Proceedings of the 19th International Conference on Software Engineering, Boston, Massachusetts, pages 433-444, May 1997.

Steensgaard, B., ``Points-to Analysis by Type Inference of Programs with Structures and Unions,'' In Proceedings of the International Conference on Compiler Construction, number 1060 in Lecture Notes in Computer Science, pages 136-150, Springer-Verlag, April 1996.

Wilson, R.,Efficient, Context-Sensitive Pointer Analysis for C Programs, Dissertation, Stanford University, USA, 1997.

Atanas Rountev and Barbara G. Ryder, "Points-to and Side-effect Analyses for Programs Built with Precompiled Libraries", Proceedings of the International Conference on Compiler Construction (CC 2001), April, 2001.

B. G. Ryder, W. Landi, P. Stocks, S. Zhang, and R. Altucher, "A Schema for Interprocedural Side Effect Analysis with Pointer Aliasing", Department of Computer Science, Rutgers University, Number DCS-TR-336, May, 1998.

Mary Jean Harrold and Mary Lou Soffa, "Efficient Computation of Interprocedural Definition-Use Chains", ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 16, no. 2, March 1994, pp. 175-204.

Jong-Deok Choi, Michael G. Burke, Paul R. Carini: Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects. POPL 1993: 232-245

W. Landi, B. G. Ryder, and S. Zhang, "Interprocedural Modification Side Effect Analysis With Pointer Aliasing", Laboratory of Computer Science Research Technical Report, Number LCSR-TR-201, March, 1993.

Keith D. Cooper and Ken Kennedy. Interprocedural side-effect analysis in linear time. In Proceedings of the ACM SIGPLAN'88 Conference on Programming Language Design and Implementation (PLDI), pages 57-66, Atlanta, Georgia, 22-24 June 1988. SIGPLAN Notices 23(7), July 1988.

3. Generierung der Static Single Assignment Form (SSA)

Die SSA-Form dient der kompakten Repräsentation der Def-Use-Abhängigkeiten (d.h. die Abhängigkeit der Verwendung einer Variablen zu ihrer Definition). Die SSA-Form ist mittlerweile weit verbreitet und gut erforscht. In diesem Vortrag wird die SSA eingeführt und ihre Berechnung vorgestellt, die sich in der Regel auf die Points-To-Information und die Seiteneffekte einzelner Anweisungen stützt. Optimierte Techniken zur Berechnung der SSA-Form nur auf Bedarf hin (on-the-fly) sowie unter Berücksichtigung einer Live-Range-Analyse werden besprochen, die ein späteres Pruning nicht notwendiger Phi-Knoten erspart. Schließlich werden einige Anwendungen der SSA-Form vorgestellt werden.

Efficiently Computing Static Single Assignment Form and the Control Dependence Graph

Ron Cytron and Jeanne Ferrante, Efficiently Computing Phi-Nodes On-The-Fly, ACM Transactions on Programmmg Languages and Systems, Vol 17, No. 3, May 1995, Pages 4S7-506.

Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. Automatic construction of sparse data flow evaluation graphs. In Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, pages 55-66, Orlando, Florida, January 1991.

4. Statisches und dynamisches Program Slicing

Program Slicing ist eine Technik, mit Hilfe derer für das Problemverständnis einer bestimmten Anweisung im Code nicht notwendigen Anweisungen entfernt. Für eine gegebene Anweisung und eine Variable, die in dieser Anweisung vorkommt, identifiziert Forward Slicing exakt jene Anweisungen, die von einer möglichen Veränderung derselben Variablen in dieser Anweisung betroffen werden können, und Backward Slicing die Anweisungen, die auf die Variable in dieser Anweisung einen Einfluss haben können. Eine Anweisung A hat Einfluss auf eine Variable in Anweisung B, wenn die Variable in B von A daten- oder kontrollabhängig ist. Beim dynamischen Program Slicing wird zur Ermittlung der Abhängigkeiten das Programm ausgeführt, während statisches Program Slicing dies nur mit Hilfe des Programmtextes ermittelt. In diesem Vortrag werden verschiedene Formen des statischen und dynamischen Program Slicing vorgestellt und bewertet.

Program Slicing

Horwitz, S., Reps, T., Binkley, D., Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems, vol. 12, no. 1, pp. 26-60, January 1990.

A. Beszedes, T. Gergely, M. Szabo Zsolt, J. Csirik and T. Gyimothy, Dynamic Slicing Method for Maintenance of Large C Programs, Proceedings of the Conference on Software Maintenance and Reengineering, IEEE Computer Society Press, 2001.

5. Statische und dynamische Extraktion von Traces zur Wiedergewinnung und Validierung von Protokollen

Unter dem Protokoll einer Komponente verstehen wir die Einschränkungen, die die Komponente hinsichtlich der Aufrufreihenfolge ihrer Operationen auferlegt. Beispielsweise muss in vielen Fällen zunächst ein Konstruktor oder eine Initialisierungsoperation aufgerufen werden, ehe irgendeine andere Operation verwendet werden kann. Zur Validierung von Protokollen kann entweder dynamisch geprüft werden, ob die Einschränkungen eingehalten werden, oder aber bereits in eingeschränktem Maße statisch entschieden werden, ob die potenziel auftretende Reihenfolge von der spezifizierten Reihenfolge abweicht. Beide Arten der Validierung erfordern die Extraktion so genannter Traces, also Operationssequenzen. Im Falle dynamischer Analyse lässt sich dies einfach mit einem Profiler oder Code-Instrumentierung erreichen. Mit Hilfe statischer Analysen kann man darüber hinaus statische Traces herleiten, die zusätzlich Bedingungen und Schleifen enthalten können. Die Extraktion statischer Traces ist überdies hilfreich, um Protokolle überhaupt erst aus dem Code wiederzugewinnen, falls die Komponente nicht spezifiziert ist.

Dieser Vortrag soll die Extraktion statischer und dynamischer Traces sowie die Wiedergewinnung und Validierung von Protokollen vorstellen und bewerten.

Extraktion statischer Traces zur Wiedergewinnung von Protokollen

Heiber, T., Semi-automatische Herleitung von Komponentenprotokollen aus statischen Verwendungsmustern, Diplomarbeit Nr. 1822, Institut füYr Informatik, UniversitäSt Stuttgart.

Jerding, D., Rugaber, S., Using Visualization for Architectural Localization and Extraction, Proceedings on the Working Conference on Reverse Engineering, IEEE Computer Society Press, 1997.

Koschke, R., Zhang, Y., Component Recovery, Protocol Recovery and Validation in Bauhaus, Reengineering Workshop, Bad Honnef, Fachberichte Informatik, Universität Koblenz, 2001.

Butkevich, S., Renedo, M., Baumgartner, G., and Young, M., Compiler and Tool Support for Debugging Object Protocols, Proceedings of the eighth international symposium on Foundations of software engineering for twenty-first century applications, 2000, pp. 50 - 59.

Olender, K.M., and Osterweil, L.J., Interprocedural Static Analysis of Sequencing Constraints, ACM Transactions on Software Engineering and Methodology, Vol. 1, No.1, pp. 21-52, January 1992.

6. Feature-Lokalisierung mit Hilfe statischer und dynamischer Analysen

Ein häufiges Problem bei Änderungen von Programmmerkmalen (Features) ist es, herauzufinden, welche Teile denn überhaupt die Programmmerkmale implementieren. Insbesondere bei großen Programmen kann dies relativ schwer werden, wenn es keine entsprechende Dokumentation gibt. Verschiedene Techniken wurden entwickelt, um Feature im Code zu lokalisieren. Sie lassen sich grob klassifizieren in statische Analysen, die sich auf den System-Abhängigkeitsgraphen stützen, dynamische Analysen, die die ausgeführten Anweisungen oder Funktionen bei Verwendung eines Features ermitteln, und kombinierte Analysen, die sich sowohl statischer als auch dynamischer Analysen bedienen. In diesem Vortrag sollen diese Techniken näher vorgestellt und bewertet werden.

Software Reconnaissance: Mapping Program Features to Code

Chen, K., Rajlich, V., Case Study of Feature Location Using Dependence Graph, Proc. of the 8th Int. Workshop on Program Comprehension, pp. 241-249, June 2000.

N. Wilde and M. Buckellew, H. Page, V. Rajlich, A Case Study of Feature Location in Unstructured Legacy Fortran Code, Proceedings of the Conference on Software Maintenance and Reengineering, IEEE Computer Society Press, 2001.

Thomas Eisenbarth, Rainer Koschke, and Daniel Simon, Feature-Driven Program Understanding Using Concept Analysis of Execution Traces, International Workshop on Program Comprehension, Toronto, Canada, IEEE Computer Society Press, 2001.

Thomas Eisenbarth, Rainer Koschke, Daniel Simon, Aiding Program Comprehension by Static and Dynamic Feature Analysis, Proceedings of the International Conference on Software Maintenance, ICSM, 2001.

Ausarbeitungen

Die Ausarbeiten werden hier verfügbar gemacht, sobald sie abgegeben werden. Die Abgabe einer vorläufigen Ausarbeitung ist eine Woche vor dem Vortrag notwendig.

		Vor
		Termine