TU Darmstadt / ULB / TUprints

Novel Approaches to Systematically Evaluating and Constructing Call Graphs for Java Software

Reif, Michael (2021)
Novel Approaches to Systematically Evaluating and Constructing Call Graphs for Java Software.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00019286
Ph.D. Thesis, Primary publication, Publisher's Version

Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (3MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Novel Approaches to Systematically Evaluating and Constructing Call Graphs for Java Software
Language: English
Referees: Mezini, Prof. Dr. Mira ; Bodden, Prof. Dr. Eric
Date: 2021
Place of Publication: Darmstadt
Collation: 204 Seiten
Date of oral examination: 23 February 2021
DOI: 10.26083/tuprints-00019286

Whether applications or libraries, today’s software heavily reuses existing code to build more gigantic software faster. To ensure a smooth user experience for an application’s end-user and a reliable software library for the developer, the shipped piece of software should be as bug-free as possible. Besides manual or automatic software testing, static program analysis is one possible way to find unintended behavior. While static analysis tools can detect simple problems using pattern matching, advanced problems often require complex interprocedural control- and data-flow analyses, which, in turn, presume call graphs. For example, call graphs enable static analyses to track inputs over method boundaries to find SQL-injections or null pointer dereferences. The research community proposed many different call-graph algorithms with different precision and scalability properties. However, the following three aspects are often neglected. First, a comprehensive understanding of unsoundness sources, their relevance, and the capabilities of existing call-graph algorithms in this respect is missing. These sources of unsoundness can originate from programming language features and core APIs that impact call-graph construction, e.g., reflection, but are not (entirely) modeled by the call-graph algorithm. Without understanding the sources of unsoundness’ relevance and the frequency in which they occur, it is impossible to estimate their immediate effect on either the call graph or the analysis relying on it. Second, most call-graph research examines how to build call graphs for applications, neglecting to investigate the peculiarities of building call graphs for libraries. However, the use of libraries is ubiquitous in software development. Consequently, disregarding call-graph construction for libraries is unfortunate for both library users and developers, as it is crucial to ensure that their library behaves as intended regardless of its usage. Third call-graph algorithms, are traditionally organized in an imperative monolithic style, i.e., one super-analysis computes the whole graph. Such a design can hardly hold up to the task, as different programs and analysis problems require the support for different subsets of language features and APIs. Moreover, configuring the algorithm to one’s needs is not easy. For instance, adding, removing, and exchanging support for individual features to trade-off the call graph’s precision, scalability, and soundiness. To address the first aspect, we propose a method and a corresponding toolchain for both a) understanding sources of unsoundness and b) improving the soundness of call graphs. We use our approach to assess multiple call-graph algorithms from state-of- the-art static analysis frameworks. Furthermore, we study how these features occur in real-world applications and the effort to improve a call graph’s soundness. Regarding aspect two, we show that the current practice of using call-graph algorithms designed for applications to analyze libraries leads to call graphs that both a) lack relevant call edges and b) contain unnecessary edges. Ergo, motivating the need for call-graph construction algorithms dedicated to libraries. Unlike algorithms for applications, call-graph construction algorithms for libraries must consider the goals of subsequent analyses. Concretely, we show that it is essential to distinguish between the analysis’s usage scenario. Whereas an analysis searching for potentially exploitable vulnerabilities must be conservative, an analysis for general software quality attributes, e.g., dead methods or unused fields, can safely apply optimizations. Since building one call graph that fits all needs is nonsensical, we propose two concrete algorithms, each addressing one use case. Concerning the third aspect, we devise a generic approach for collaborative static analysis featuring modular analysis that are independently compilable, exchangeable, and extensible. In particular, we decouple mutually dependent analyses, enabling their isolated development. This approach facilitates highly configurable call-graph algorithms, allowing pluggable precision, scalability, and soundiness by either switching analysis modules for features and APIs on/off, or exchanging their implementations. By addressing these three aspects, we advance the state-of-the-art in call-graph construction in multiple dimensions. First, our systematic assessment of unsoundness sources and call-graph algorithms reveals import limitations with state-of-the-art. All frameworks lack support for many features frequently found in-the-wild and produce vastly different CGs, rendering comparisons of call-graph-based static analyses infeasible. Furthermore, we leave both developers and users of call graphs with suggestions that improve the entire situation. Second, our discussion concerning library call graphs raises the awareness of considering the analysis scenario and opens up a new facet in call-graph research. Third, by featuring modular call-graph algorithms we ease to design, implement, and test them. Additionally, it allows project-based configurations, enabling puggable precision, scalability, and sound(i)ness.

Alternative Abstract:
Alternative AbstractLanguage

Software ist fehlerhaft. Dieser Tatsache müssen sich Entwickler:innen stellen. Schon im Prozess der Softwareentwicklung kommen zur Fehlervermeidung deshalb vielfältige Verfahren zur Anwendung, wie bspw. der Einsatz von Tests, Code Reviews und statischer Programmanalyse. Damit können Fehler frühzeitig erkannt und beseitigt werden. Statische Programmanalysen haben im Vergleich zu den anderen genannten Qualitätssicherungsmaßnahmen den Vorteil, dass sie bekannte, häufig auftretende Fehler auffinden und programmübergreifend eingesetzt werden können. Für einfache Probleme eignen sich Mustererkennungen, komplexere interprozedurale Probleme bedürfen hingegen auch Kontroll- und Datenflussanalysen – letztere setzen den Einsatz von Call Graphen voraus. Die bisherige Arbeit mit Call-Graph-Algorithmen weist in der Forschung jedoch noch Lücken auf, obwohl sie ein zentraler Grundbaustein von interprozeduralen, statischen Programmanalysen sind. In dieser Arbeit adressieren wir drei Probleme der bisherigen Verwendung von Call-Graph-Algorithmen, die einen negativen Einfluss auf die Ergebnisse von interprozeduralen, statischen Programmanalysen haben können. Dies sind im Einzelnen: 1) die Vernachlässigung der Korrektheit von Call Graphen, 2) der übermäßige Fokus auf der Entwicklung von Call-Graph-Algorithmen für Applikationen, bei gleichzeitiger Unterrepräsentation dieser für Software-Bibliotheken, sowie 3) die mangelnde Modularität und Konfigurierbarkeit von Call-Graph-Implementierungen. Alle drei Aspekte tragen dazu bei, dass das Potenzial interprozeduraler, statischer Programmanalysen nicht ausgeschöpft werden kann. Dem begegnen wir mit verschiedenen, problemspezifischen Maßnahmen. Dem Problem der mangelnden Korrektheit (1) setzen wir eine eigens entwickelte Methodik und ein dazugehöriges Werkzeug entgegen, mithilfe derer die Quellen fehlender Korrektheit identifiziert werden können. Damit bietet sich die Möglichkeit, diese zu verstehen und zu beseitigen. Um die problematische Unterrepräsentation von Call-Graph-Algorithmen für Software-Bibliotheken (2) aufzuzeigen, gehen wir auf deren spezifische Eigenarten und notwendige Anpassungen vorhandener Call-Graph-Algorithmen ein, um bspw. unnötige Kanten zu vermeiden oder fehlende zu ergänzen. Mehrere konkrete Algorithmen werden von uns entwickelt und gewährleisten das Erstellen eines korrekten Call Graphen für Software-Bibliotheken. Um Call-Graph-Implementierungen modularer und konfigurierbarer zu machen (3), entwickeln wir einen generischen Ansatz für die Implementierung von kollaborativen, modularen statischen Programmanalysen, die unabhängig voneinander kompilierbar, austauschbar und erweiterbar sind. So kann für jedes Programm die bestmögliche Einstellung für Geschwindigkeit, Skalierbarkeit und Korrektheit gefunden werden. Mit dem Lösen dieser drei Probleme fördern wir den Stand der Technik von Call Graphen in mehreren Dimensionen. Zum einen offenbart unsere systematische Bewertung der Quellen fehlender Korrektheit signifikante Schwachstellen bestehender Algorithmen. Damit diese behoben werden können, geben wir konkrete Empfehlungen für die Entwickler:innen und Nutzer:innen von Call-Graph-Algorithmen. Zum anderen schärft unsere Diskussion über Call Graphen für Software-Bibliotheken das Bewusstsein für die Berücksichtigung des jeweiligen Analyseszenarios. Damit eröffnen wir eine neue Richtung für die Call-Graph-Forschung. Nicht zuletzt erleichtert unser Ansatz für modulare Call Graphen außerdem deren Entwicklung und ermöglicht projektspezifische Konfigurationen, wodurch u. a. eine flexible Anpassung an bestehende Herausforderungen möglich ist.

Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-192864
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Software Technology
Date Deposited: 20 Sep 2021 07:51
Last Modified: 05 Aug 2022 08:00
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19286
PPN: 486185184
Actions (login required)
View Item View Item