TU Darmstadt / ULB / TUprints

Modular Collaborative Program Analysis

Helm, Dominik (2023)
Modular Collaborative Program Analysis.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00023220
Ph.D. Thesis, Primary publication, Publisher's Version

[img] Text
Helm-Dissertation-ModularCollaborativeProgramAnalysis.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (1MB)
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Modular Collaborative Program Analysis
Language: English
Referees: Mezini, Prof. Dr. Mira ; Ali, Prof. Dr. Karim
Date: 2023
Place of Publication: Darmstadt
Collation: ix, 253 Seiten
Date of oral examination: 9 February 2023
DOI: 10.26083/tuprints-00023220
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.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-232206
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Software Technology
Date Deposited: 03 Mar 2023 13:06
Last Modified: 06 Mar 2023 07:21
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/23220
PPN: 505480751
Export:
Actions (login required)
View Item View Item