Scalable data-flow analysis through sparsification and precise call graphs

Die statische Datenflussanalyse zielt darauf ab, fehlerfreie, sichere und hochwertige Software zu gewährleisten, indem sie alle möglichen Ausführungen eines Zielprogramms berücksichtigt. Aufgrund von Skalierbarkeitsbeschränkungen führt dies häufig zu starken Überapproximationen, die die Präzision der Analyse beeinträchtigen. Andererseits verbessert Sparsifizierung, eine Optimierungstechnik, die Daten-flussanalysen auf analysenrelevante Programmstatements beschränkt, die Skalierbarkeit der Datenflussanalyse und bewahrt gleichzeitig deren Präzision.Diese Arbeit stellt SPARSEIDE vor, ein neuartiges Framework, das eine (Datenfluss-)Fakt-spezifische Sparsifizierung für jede Datenflussanalyse realisiert, die im IDE-Framework (Interprocedural Distributive Environments) realisiert wird. ObwohlIDE-Analysen nur in Bezug auf Symbole und nicht auf Werte sparsifiziert werdenkönnen, erzielt SPARSEIDE deutlich geringere Laufzeiten und einen geringeren Spe-icherverbrauch als das ursprüngliche IDE.Ansätze zur Verbesserung der Skalierbarkeit aus der Literatur, darunter SPARSEIDE,verwenden einen festen Call-Graph-Algorithmus, ohne dessen Auswirkungen auf die nachgelagerte Datenflussanalyse zu berücksichtigen. Anhand einer umfassendenempirischen Bewertung zeigt diese Arbeit, wie präzise kontextsensitive Call-Graphendie Laufzeiten der Datenflussanalyse erheblich reduzieren.Präzise Datenflussanalysen analysieren den Heap anhand von Pointer-Analysen, die ebenfalls schwer zu skalieren sind. Diese Arbeit stellt SPARSEBOOMERANG als Anwendung der Fakt-spezifischen Sparsifizierung auf die bedarfsorientierte Pointersanalyse vor. SPARSEBOOMERANG realisiert zwei verschiedene Sparsifizierung-Strategien,die die Eigenschaften der Pointeranalyse-Domäne nutzen: eine type-aware Sparsifizierung und eine alias-aware Sparsifizierung. Interprocedural Datenflussanalysen umfassen einen Datenfluss-Solver, einen Call-Graph und eine Pointer-Analyse. Diese Arbeit zeigt, wie präzise Datenflussanalysen skaliert werden können, indem alle drei Komponenten unter dem Gesichtspunkt der Sparsifizierung betrachtet werden. Eine Fakt-spezifische Sparsifizierung reduziert die Arbeitslast des Datenfluss-Solvers. Als orthogonale Komponente hat die Wahl des Call-Graphen einen erheblichen Einfluss auf die Skalierbarkeit der Datenflussanalyse.Die Pointer-Analyse, die bekanntermaßen ein nicht-distributives Problem darstellt,profitiert ebenfalls von einer Fakt-spezifischen Sparsifizierung, wenn sie innerhalb eines distributiven Datenflussanalyse-Frameworks formuliert wird.