Kombinierte statische Ermittlung von Zeigerzielen, Kontroll- und Datenfluss

Abstract

Datenfluss-basierte statische Programmanalysen benötigen Informationen zu den an einer Programmstelle eintreffenden gültigen Definitionen. Dieses Wissen wiederum basiert auf dem Kontrollfluss. Zeiger-indirekte Operationen verschleiern jedoch beides, Kontroll- und Datenfluss: An solchen Operationen benötigt die Analyse Wissen über die potentiellen Zeigerziele, was aber seinerseits ein Datenfluss-Problem ist.

Die vorliegende Dissertation bespricht ein neues Verfahren, um diese drei zentralen Probleme in Kombination zu lösen. Der wesentliche Unterschied zu bekannten Zeigeranalysen ist dabei, die Probleme zusammen zu betrachten und zugleich zu lösen. Das erlaubt es uns, die Aufgabe nicht als Datenfluss-Problem auf der Kontrollfluss-Darstellung zu betrachten, sondern stattdessen als Grapherreichbarkeits-Problem auf der Datenfluss-Darstellung. Der Ansatz hierzu ist sehr einfach: Die wechselseitige Bestimmung von Datenfluss-Beziehungen und das Propagieren von Zeigerzielen löst iterativ das Problem. Die Analyse ist dabei fluss-sensitiv und beherrscht starke Aktualisierungen; eine fluss-insensitive Betrachtung führt auf die bekannte Zeigeranalyse von Andersen. Wie diese Arbeit zeigt, erreichen wir die höhere Genauigkeit zu den gleichen asymptotischen Kosten.

Die Dissertation beweist die Korrektheit des neuen Verfahrens und präsentiert eine ausführliche Evaluation, in der es sich dank Zyklenkontraktion als moderat quadratisch herausstellt. Schließlich präsentiert die Dissertation mit einer Erweiterung der neuen Analyse die erste fluss-sensitive Zeigeranalyse, welche starke Aktualisierungen unterstützt, die sogenannte meet-over-all-valid-paths-Lösung berechnet und dabei nur biquadratische Komplexität besitzt. Dies sind weitere klare Fortschritte zum aktuellen Stand der Forschung.

Dataflow-based static program analyses need to know the reaching definitions arriving at the program's statements. This information in turn is based on control-flow knowledge. However, pointer-indirect operations obfuscate both control- and data-flow: for these operations, the analysis has to know the potential pointer targets - but this in itself is a data-flow problem.

This dissertation describes a new analysis to solve these three central problems in combination. In contrast to existing pointer analyses, we view the problems in combination and solve them together. This allows us to solve the task not as a data-flow problem on some control-flow representation, but instead as a graph-reachability problem on a data-flow representation. Our approach for this is very simple: iteratively determining data-flow relations and propagating pointer targets solves the problem. The new analysis is flow-sensitive and supports strong updates; a flow-insensitive realization yields the famous pointer analysis first described by Andersen. This work shows that we achieve the higher precision with the same asymptotic complexity. The dissertation also proves the new analysis' correctness and presents a thorough evaluation in which the analysis scales quadratically.

Finally, the dissertation describes an extension to the new analysis which yields the first flow-sensitive pointer analysis that supports strong updates and achieves the so-called meet-over-all-valid-paths precision within the time complexity of O(n4). This is another considerable improvement over the state of the art.