National and Kapodistrian University of Athens
Explorations in static pointer analysis: adaptive scalability and strong guarantees
Abstract
dc:descriptionStatic program analysis aims to automatically reason about certain properties a given program might exhibit under all possible executions without actually observing such executions. Static pointer analysis is a major subcategory that focuses on the objects that program expressions might point to during program executions. The evolution of programming languages has led to the addition of many abstraction layers that, as a result, have made any automatic reasoning about a program a challenging task at best or an infeasible one at worst. Thus, any practical static pointer analysis algorithm has to compromise and aim to approximate results in some way—either computing more or less than what is actually true. This dissertation shows how we can obtain precise yet also scalable static pointer analysis algorithms by carefully differentiating policies for different parts of the program. Furthermore, since a static pointer analysis algorithm with global soundness guarantees and meaningful results throughout is not realistic, we show that it is possible to design analyses that offer strong guarantees on the soundness of the results for specific parts of the program. Pointer analyses in the past introduced the concept of context-sensitivity in order to tackle the ever growing problem of imprecision versus scalability. Context is used to annotate analysis components so that the analysis can be more precise without at the same time sacrificing scalability. We show beneficial ways to combine different context flavors for different parts of the program without paying the cost that a naive combination would incur. Another attempt at producing precise yet scalable analyses leads us to an introspective analysis. We employ a common adaptive pattern in which a cheap imprecise analysis is run first so various metrics can be gathered, and then a more precise (and costly) analysis can be used only in parts of the program—under the assumption that more precise handling of the rest would only incur performance penalties. Subsequently, we shift our attention to an analysis that under-approximates results (instead of the norm of over-approximating) so that it might report less but can guarantee those properties to always hold. We build upon observations on the properties that such analyses have in order to apply a specialized data structure that speeds up our algorithm by nearly two orders of magnitude. Finally, in our last contribution, we revisit an analysis formulation that over-approximates results to create an analysis algorithm that is truly sound but at the same time highly efficient. Our analysis is conservative, guaranteeing soundness even in the presence of arbitrary unknown code, but avoids wasting any work on computations that will later be invalidated due to soundness concerns.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2020
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kastrinis, Georgios
- Καστρίνης, Γεώργιος
Subjects
dc:subject × 15- Ανάλυση δεικτών
- Ανάλυση συνωνύμων
- Αντικειμενοστρεφής προγραμματισμός
- Ακρίβεια
- Απόδοση
- Pointer analysis
- Alias analysis
- Object-oriented programming
- Precision
- Performance
- Context-sensitivity
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
dc:rights- Statement dc:rights
-
- BY
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/47771