10 Vor. QSQM Statische Analyse

• Fuzzing
• Formale Verifikation
• Dynamische Analyse
• Monitoring

Fuzzing

Erzeugen zufälliger Eingaben, um Abstürze und Fehler auszulösen

• + Findet Fehler, die traditionelle Tests nicht finden

• - Kann die Abwesenheit von Fehlern auch nicht beweisen

Formale Verifikation

Experten schreiben mathematisch fundierte Beweise

• + Kann die Abwesenheit (bestimmter) Fehler mit Sicherheit beweisen

• - Enorm zeitaufwendig

• - Spezifisch für ein bestimmtes Programm

• - Oft schwer, die richtige zu beweisende Eigenschaft zu finden

Dynamische Analyse

Daten während Ausführung sammeln und analysieren,

um Informationen zu gewinnen

• Typischerweise mit ausgewählten Programmeingaben (ähnlich zu Tests)

• + "Reale" Ausführungen

• - Begrenzte Anzahl an Ausführungen

• - Wie Programmeingaben auswählen?

Monitoring

Daten während tatsächlichem Software-Einsatz sammeln,

kontinuierlich auf Abweichungen beobachten

• + Reale Ausführung

• + Findet relevante Probleme

• - Probleme werden erst gefunden, wenn sie die Nutzung schon beeinflussen

statische Analyse

Infos über Programm (Quelltext/Binary) gewinnen, ohne es auszuführen

• + Vollständig automatisiert

• + Starke Garantien

• + Alle möglichen Ausführungspfade

• - Unentscheidbar

• - Kann keine nutzerdefinierten Eigenschaften beweisen

In IDEs zur Unterstützung von Entwicklern

• Klassenhierarchie, Methodenaufruf-Informationen, Code-Navigation.

• Fehler, Warnungen, Code Smells, Vorschläge für Optimierungen.

• Refactoring, z.B. Umbenennen, Ändern von Methodensignaturen, Code verschieben.

• Vorschläge während des Programmierens, Auto-Complete.

In Sicherheitsanalysen

• Finden von Fehlern, Schwachstellen, schwacher Kryptographie, falscher Verwendung von APIs

• Identifikation von Schadsoftware

• Erkennen von Leaks privater Daten

• Unentscheidbarkeit
• Vollständigkeit (Completeness)
• Korrektheit (Soundness)
• 
  

Unentscheidbarkeit

“Jede nicht-triviale Eigenschaft von Programmen ist unentscheidbar”

Unentscheidbare Eigenschaften:

• Terminiert das Programm? (Halteproblem)

• Können zwei Pointer auf dieselbe Speicherstelle zeigen (Alias)

• ... (prinzipiell jede interessante Eigenschaft von Programmen)

Möglichkeiten:

• Keine Ausgabe einer definitiven Antwort

• Überapproximation

• Unterapproximation

Vollständigkeit (Completeness)

Keine zur Laufzeit unmöglichen Ergebnisse produzieren

⇒ Keine Überapproximation

• Maß: Genauigkeit (precision) = #Richtig−positive / #Ergebnisse =

• Weniger falsch-positive Ergebnisse

⇒ weniger ungerechtfertigte Warnungen

Korrektheit (Soundness)

Aller zur Laufzeit möglichen Ergebnisse produzieren

⇒ Keine Unterapproximation

• Maß: Trefferquote (recall) = #Richtig−positive / #erwartete Ergebnisse

• Weniger falsch-negative Ergebnisse

⇒ weniger übersehene Probleme

• Vollständige Korrektheit in der Praxis

oft nicht erreichbar:

◦ z.B. dynamisch geladener Code, Reflection

• Soundiness: Bewusste, dokumentierte inkorrekte Design Entscheidungen für Praxistauglichkeit

Skalierbarkeit

Ergebnisse für große Software in beschränkter Zeit/Speicher produzieren

• Schnelle Ergebnisse in IDEs (unter einer Sekunde)

• Akzeptable Laufzeit/Speicherverbrauch in Continuous Integration

• Analyse von riesigen Software-Verzeichnissen (z.B. Maven Central)

Genauigkeit, Trefferquote und Skalierbarkeit sind Anforderungen,

die oft im Konflikt miteinander stehen

• Kontrollflussanalyse

Kontrollfluss beschreibt Reihenfolge in der Anweisungen ausgeführt werden:

• Welche Anweisung kann nach welcher ausgeführt werden

• Datenflussnalyse

Datenflussanalysen verfolgen den Fluss von Werten durch ein Programm:

• Wo wird ein hier definierter Wert genutzt

• Wo wurde ein hier genutzter Wert definiert

• Umfang:

◦ Intraprozedurale Analysen betrachten jede Methode für sich

◦ Interprozedurale Analysen berücksichtigen das gesamte Programm

• Flusssensitivität:

◦ Flussinsensitive Analysen berechnen ein global gültiges Ergebnis

◦ Flusssensitive Analysen berechnen ein Ergebnis für jede Anweisung

• Kontextsensitivität:

◦ Kontextinsensitive Analysen betrachten jedes Stück Code nur ein Mal

◦ Kontextsensitive Analysen nutzen mehrere Kontexte (z.B. aufrufende Methode)

• Umfang:

◦ Intraprozedurale Analysen betrachten jede Methode für sich

◦ Interprozedurale Analysen berücksichtigen das gesamte Programm

• Flusssensitivität:

◦ Flussinsensitive Analysen berechnen ein global gültiges Ergebnis

◦ Flusssensitive Analysen berechnen ein Ergebnis für jede Anweisung

• Kontextsensitivität:

◦ Kontextinsensitive Analysen betrachten jedes Stück Code nur ein Mal

◦ Kontextsensitive Analysen nutzen mehrere Kontexte (z.B. aufrufende Methode)

• Slicing
• Constraint-basierte Analyse
• Big-Step abstrakte Interpreter
• Symbolische Ausführung
• Interpropedurale Datenflussanalyse: IFDS & IDE
• Monotone Datenflussanalyse
• Typ- und Effektsysteme

Typsysteme:

◦ Weisen dem Ergebnis jedes Ausdrucks einen Typ zu

◦ Kompositional: Typ folgt direkt aus Typen von Teilausdrücken

◦ Häufig genutzt, um Fehler schon beim Kompilieren zu verhindern

Effektsysteme:

◦ Weisen jedem Ausdruck einen Effekt zu

◦ Kompositional

◦ Seltener genutzt (aber Sie kennen vermutlich ein sehr einfaches)

(Intraprozedurale) Analyse, wie Werte zwischen Variablen fließen. Z.B.:

• Liveness: Kann Wert nach einem bestimmten Punkt noch gelesen werden?

• Reaching definitions: Woher stammen Werte, die eine Anweisung erreichen?

• Available expressions: Welche Werte wurden bereits berechnet?

Genutzt für Optimierungen, z.B.

• Entfernen von unerreichbarem Code (Dead-code removal)

• Loop-invariant code motion

• Common subexpression elimination

• Interprozeduraler Datenfluss als Graph-Erreichbarkeits-Problem

• Sehr effizient, wenn das Problem geeignet ist (wichtig: Distributivität)

• Nutzung: z.B. Taintanalyse (verfolgen von sensiblen o. gefährlichen Daten)

• Interpretiert Programme mit symbolischen statt konkreten Werten

• Spaltet Ausführung bei Verzweigungen auf

• - Pfadexplosion!

• Berechnen Abstraktionen konkreter Werte

• Abstraktionen stammen aus Lattice-basierten Domänen

Z.B. Vorzeichen, Intervalle

• Vereinigt Werte nach Verzweigungen, um Pfadexplosion zu vermeiden

• Erzeugt Bedingungen für das Analyseergebnis aus dem analysierten

Programm

• Löst dann die Menge der Bedingungen für die präziseste Lösung

• - Menge der Bedingungen kann schwer zu lösen sein

Extrahiert Anweisungen mit Bezug auf ein Slicingkriterium (z.B. Ort+Variable)

• Rückwärtsslicing: Anweisungen, die das Slicingkriterium beeinflussen

• Vorwärtsslicing: Anweisungen, die vom Slicingkriterium beeinflusst werden

• Anwendungen: Debugging, Klonerkennung, Parallelisierung, etc.

• Immutability & Purity
• Escape- & Alias-Analyse
• Points-To-Analyse
• Callgraphen
• Kontrollflussgraph und Dominator-Bäume

CFG: Welche Anweisung wird direkt nach welcher ausgeführt?

Dominatorbaum: Welche Anweisung muss zuvor ausgeführt worden sein?

Post-Dominator-Baum: Welche Anweisung muss danach ausgeführt werden?

• Verbinden eine Methode (caller) mit den Methoden, die sie aufruft (callees)

• Notwendige Voraussetzung für alle interprozeduralen Analysen

• Viele Algorithmen mit verschiedenen Abwägungen zwischen Präzision

und Skalierbarkeit

• Auf welche Objekte kann eine Variable (Feld, etc.) verweisen?

• Meistens der Ort, an dem das Objekt erzeugt wurde

• Nützlich für viele andere Analysen wie Callgraphen

Escapeanalyse betrachtet die dynamische Lebenszeit von Objekten:

• Kann ein Objekt außerhalb eines beschränkten Kontexts (z.B. Methode, Package) gesehen werden

• Nützlich, um Grenzen von Effekten zu kennen und für Optimierungen

Aliasanalyse betrachtet Beziehungen zwischen Variablen:

• Können (may)/müssen (must) zwei Variablen (Felder, etc.) auf das selbe Objekt verweisen?

• May-Analyse oft flussinsensitiv, Must-Analyse immer flusssensitiv

Immutability: Kann Feld/Klasse/Objekt/etc. nach der Initialisierung verändert werden?

Purity: Ist eine Methode deterministisch und seiteneffektfrei?

• Für sicheren, wartbaren Code

• Besondere Unterstützung in modernen Programmiersprachen

• Kann über ein Typsystem garantiert werden