Details

Autor(en) / Beteiligte

• Späth, Johannes
• Bodden, Eric[Akademischer Betreuer]
• Ali, Karim[Akademischer Betreuer]

Titel

Synchronized pushdown systems for pointer and data-flow analysis

Ort / Verlag

Paderborn

Erscheinungsjahr

2019

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 14.01.2019
• ger: Statische Datenflussanalysen analysiern das Verhalten von Software ohne die Software dabei auszuführen. Eine präzise Datenflussanalyse transformiert das Programm in eine kontext-, fluss- und feld-sensitive Approximation der Software. Diese Arbeit präsentiert eine neue Approximation für kontext-, fluss- und feld-sensitive Datenflussanalysen. Die Lösung, die wir mit synchronisierte Kellersysteme (SPDS) bezeichnen, berechnet distributive Datenflussanalyse-Ergebnisse präzise und effizient. SPDS stützt sich dazu auf zwei Kellersysteme. Ein System modelliert Feld-Sensitivität, das andere Kontext-Sensitivität. SPDS akzeptiert ein Ergebnis nur, wenn beide Systeme das Ergebnis akzeptieren.Eine statische Datenflussanalyse muss Pointer-Beziehungen auflösen. Den Datenfluss von Pointern effizient zu berechnen ist schwierig, da die Beziehungen nicht überall distributiv sind. Diese Arbeit zeigt, dass Pointer-Beziehungen in mehrere distributive und mit SPDS lösbare Teilprobleme unterteilt werden kann. Dieses Design bildet die Grundlage für die bedarfsorientierte Pointer-Analyse Boomerang, welche in dieser Arbeit präsentiert wird.Weiterhin beschreibt diese Arbeit IDEal, ein generisches, präzises und effizientes Rahmenwerk für Datenflussanalysen, in dem z.B. Analysen für Typestate und das Extrahieren der Benutzung von Programmierschnittstellen realisiert werden können. IDEal berechnet Pointer-Beziehungen automatisch mittels Boomerang. Mit einer Datenflussanalyse zum automatischen Auffinden von Sicherheitsschwachstellen bringt diese Arbeit Boomerang und IDEal in die Anwendung. In einem groß angelegten Experiment wird gezeigt, dass synchronisierte Kellersysteme einen vielversprechenden Ansatz für Datenflussanalysen liefern.
• eng: Static data-flow analysis reasons about behaviour of software without executing it. A precise data-flow analysis transforms the program into context-sensitive, flow-sensitive, and field-sensitive approximation of the software.This thesis presents a new approximation for precise data-flow analysis. The solution, called synchronized pushdown systems (SPDS), solves data-flows by relying on two pushdown systems, one system models field-sensitivity, the other one context-sensitivity. The SPDS then only accepts results that are context- and field-sensitive.Static data-flow analysis needs to resolve pointer relations when data escapes to the heap. Flows of pointers are difficult and costly to resolve because pointer relations are non-distributive. Nevertheless, this thesis shows that pointer analysis can be solved by subdividing pointer relations into multiple distributive computations, for each computation a SPDS can be consulted. Based on this design, the thesis presents the demand-driven pointer analysis Boomerang. Boomerang minimizes it computational effort by only resolving the minimal part of pointer relations necessary to answer a points-to query.Another contribution of this thesis presents IDEal, a generic and efficient framework for data-flow analyses, e.g., typestate analysis or mining of application programming interfaces (APIs). IDEal resolves pointer relations automatically and efficiently by the help of Boomerang. Apart from the fundamental problem of finding the right balance between precision and efficiency of a general static data-flow analysis, this thesis elaborates on a concrete application of Boomerang and IDEal within a data-flow analysis that detects complex security vulnerabilities. Applying this data-flow analysis on large scale shows once more that synchronized pushdown systems enable a promising approach for efficient and precise data-flow ...