TU Darmstadt / ULB / TUbiblio

Modular Collaborative Program Analysis

Helm, Dominik (2023)
Modular Collaborative Program Analysis.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00023220
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

With our world increasingly relying on computers, it is important to ensure the quality, correctness, security, and performance of software systems. Static analysis that computes properties of computer programs without executing them has been an important method to achieve this for decades. However, static analysis faces major chal- lenges in increasingly complex programming languages and software systems and increasing and sometimes conflicting demands for soundness, precision, and scalability. In order to cope with these challenges, it is necessary to build static analyses for complex problems from small, independent, yet collaborating modules that can be developed in isolation and combined in a plug-and-play manner.

So far, no generic architecture to implement and combine a broad range of dissimilar static analyses exists. The goal of this thesis is thus to design such an architecture and implement it as a generic framework for developing modular, collaborative static analyses. We use several, diverse case-study analyses from which we systematically derive requirements to guide the design of the framework. Based on this, we propose the use of a blackboard-architecture style collaboration of analyses that we implement in the OPAL framework. We also develop a formal model of our architectures core concepts and show how it enables freely composing analyses while retaining their soundness guarantees.

We showcase and evaluate our architecture using the case-study analyses, each of which shows how important and complex problems of static analysis can be addressed using a modular, collaborative implementation style. In particular, we show how a modular architecture for the construction of call graphs ensures consistent soundness of different algorithms. We show how modular analyses for different aspects of immutability mutually benefit each other. Finally, we show how the analysis of method purity can benefit from the use of other complex analyses in a collaborative manner and from exchanging different analysis implementations that exhibit different characteristics. Each of these case studies improves over the respective state of the art in terms of soundness, precision, and/or scalability and shows how our architecture enables experimenting with and fine-tuning trade-offs between these qualities.

Typ des Eintrags: Dissertation
Erschienen: 2023
Autor(en): Helm, Dominik
Art des Eintrags: Erstveröffentlichung
Titel: Modular Collaborative Program Analysis
Sprache: Englisch
Referenten: Mezini, Prof. Dr. Mira ; Ali, Prof. Dr. Karim
Publikationsjahr: 2023
Ort: Darmstadt
Kollation: ix, 253 Seiten
Datum der mündlichen Prüfung: 9 Februar 2023
DOI: 10.26083/tuprints-00023220
URL / URN: https://tuprints.ulb.tu-darmstadt.de/23220
Kurzbeschreibung (Abstract):

With our world increasingly relying on computers, it is important to ensure the quality, correctness, security, and performance of software systems. Static analysis that computes properties of computer programs without executing them has been an important method to achieve this for decades. However, static analysis faces major chal- lenges in increasingly complex programming languages and software systems and increasing and sometimes conflicting demands for soundness, precision, and scalability. In order to cope with these challenges, it is necessary to build static analyses for complex problems from small, independent, yet collaborating modules that can be developed in isolation and combined in a plug-and-play manner.

So far, no generic architecture to implement and combine a broad range of dissimilar static analyses exists. The goal of this thesis is thus to design such an architecture and implement it as a generic framework for developing modular, collaborative static analyses. We use several, diverse case-study analyses from which we systematically derive requirements to guide the design of the framework. Based on this, we propose the use of a blackboard-architecture style collaboration of analyses that we implement in the OPAL framework. We also develop a formal model of our architectures core concepts and show how it enables freely composing analyses while retaining their soundness guarantees.

We showcase and evaluate our architecture using the case-study analyses, each of which shows how important and complex problems of static analysis can be addressed using a modular, collaborative implementation style. In particular, we show how a modular architecture for the construction of call graphs ensures consistent soundness of different algorithms. We show how modular analyses for different aspects of immutability mutually benefit each other. Finally, we show how the analysis of method purity can benefit from the use of other complex analyses in a collaborative manner and from exchanging different analysis implementations that exhibit different characteristics. Each of these case studies improves over the respective state of the art in terms of soundness, precision, and/or scalability and shows how our architecture enables experimenting with and fine-tuning trade-offs between these qualities.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Unsere Welt hängt zunehmend von Computern ab. Daher ist es wichtig, die Qualität, Korrektheit, Sicherheit und Leistung von Softwaresystemen sicherzustellen. Statische Analyse, die Eigenschaften von Computerprogrammen berechnet, ohne sie auszuführen, ist seit Jahrzehnten eine wichtige Methode, um dies zu erreichen. Jedoch steht statische Analyse vor großen Herausforderungen aufgrund zunehmend komplexer Programmiersprachen und Softwaresysteme und zunehmenden und teils einander widersprechender Anforderungen an Vollständigkeit, Präzision und Skalierbarkeit. Um mit diesen Heraus forderungen umzugehen, ist es nötig, statische Analysen für komplexe Probleme aus kleinen, unabhängigen, aber miteinander kollaborierenden Modulen aufzubauen, die getrennt voneinander entwickelt und anschließend flexibel kombiniert werden können.

Bisher existiert keine generische Architektur, um ein breites Spektrum an unterschiedlichen statischen Analysen zu entwickeln und zu kombinieren. Das Ziel dieser Arbeit ist daher, eine solche Architektur zu entwerfen und als ein generisches Framework für die Entwicklung modularer, kollaborativer statischer Analysen zu implementieren. Wir nutzen mehrere verschiedenartige Fallstudienanalysen von denen ausgehend wir systematisch Anforderungen ableiten, um die Gestaltung des Frameworks zu leiten. Basierend darauf schlagen wir vor, Analysen ähnlich einer Blackboard-Architektur kollaborieren zu lassen. Diesen Ansatz verwirklichen wir im OPAL Framework. Wir entwickeln außerdem ein formales Modell der Kernkonzepte unserer Architektur und zeigen damit, wie Analysen frei miteinander kombiniert und dabei ihre Korrektheitsgarantien erhalten werden können.

Wir präsentieren und evaluieren unsere Architektur anhand der Fallstudienanalysen, von denen jede zeigt, wie wichtige und komplexe statische Analysen modulare und kollaborative umgesetzt werden können. Konkret zeigen wir, wie eine modulare Architektur für die Berechnung von Methodenaufrufgraphen eine konsistente Vollständigkeit verschiedener Algorithmen sicherstellt. Wir zeigen, wie modulare Analysen für verschiedene Ausprägungen von Unveränderbarkeit gegenseitig voneinander profitieren. Schließlich zeigen wir, wie die Analyse von Seiteneffektfreiheit von Methoden davon profitieren kann, Ergebnisse anderer komplexer Analysen kollaborativ zu nutzen, sowie davon, verschiedene Varianten der Analyse, die unterschiedliche Charakteristiken aufweisen, gegeneinander austauschen zu können. Jede der Fallstudien stellt eine Verbesserung gegenüber dem Stand der Technik in Bezug auf Vollständigkeit, Präzision und/oder Skalierbarkeit dar und zeigt, wie unsere Architektur es ermöglicht, Zielkonflikte zwischen diesen Eigenschaften zu studieren und feinabzustimmen.

Deutsch
Status: Verlagsversion
URN: urn:nbn:de:tuda-tuprints-232206
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Softwaretechnik
Hinterlegungsdatum: 03 Mär 2023 13:06
Letzte Änderung: 06 Mär 2023 11:02
PPN:
Referenten: Mezini, Prof. Dr. Mira ; Ali, Prof. Dr. Karim
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 9 Februar 2023
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen