Entwicklung von Analysen für 2⁶⁰⁰⁰ Varianten

Viele Softwaresysteme stellen eine große Anzahl an Konfigurationsoptionen bereit, um das Verhalten eines Systems an unterschiedliche Anforderungen und Anwendungsfälle anzupassen. Solche variantenreichen Systeme stellen die Qualitätssicherung von Softwaresystemen vor eine große Herausforderung. Durch die mögliche Kombinatorik ist eine “brute force” Absicherung jeder einzelnen möglichen Variante keine Option.

Der Linux-Kernel bietet beispielsweise mehr als 6000 Konfigurationsoptionen. Darunter Optionen für unterschiedliche Dateisysteme (EXT3, EXT4, JFS, XFS, Btrfs, …), diverse USB-Geräte, zahlreiche Prozessortypen und viele mehr. Mit ihrer Hilfe können in der Theorie bis zu 2⁶⁰⁰⁰ Linux-Kernel Varianten für Smartphones, Router, High-Performance Computer oder Standard-PCs auf Knopfdruck erstellt werden. Auch wenn die tatsächliche Anzahl an Linux-Kernel Varianten aufgrund von Abhängigkeiten zwischen Konfigurationsoptionen niedriger ist, so liegt sie immer noch in einem astronomisch großen Bereich.

Implementierung von Variabilität mit dem C-Präprozessor

Variabilität wird im Linux-Kernel mit Hilfe des C-Präprozessors (cpp) implementiert. Der C-Präprozessor ist ein einfaches Textverarbeitungswerkzeug und ein wesentlicher Bestandteil der Softwareentwicklung in C (durch die Integration in C-Compiler). Softwareentwickler können mit Hilfe sogenannter Direktiven Vorgaben zur Textverarbeitung machen.

Im Kontext der Implementierung variantenreicher Systeme werden von Entwicklern Direktiven, wie #ifdef eingesetzt um variable Code-Fragmente zu kodieren. #ifdef Direktiven verhalten sich wie normale if Anweisungen von C, nur dass sie zur Kompilierung (Übersetzung) eines Programms vom Präprozessor ausgewertet werden. Evaluieren die in #ifdef Direktiven enthaltenden Ausdrücke (eine logische Kombination von Konfigurationsoptionen) zu true bleibt das Code-Fragment in der generierten Variante enthalten. Andernfalls wird es vom Präprozessor entfernt.

Schauen wir auf das folgende Beispiel einer konfigurierbaren Funktionsimplementierung in C (zu Darstellungszwecken sind die Präprozessordirektiven #ifdef und #endif inline dargestellt):

C-Beispiel

1int foo(int a #ifdef X, int b #endif) {
2  int c = a;
3  if (c) {
4    c = 1;
5#ifdef Y c = c+b; #endif
6  }
7  return c;
8}

Die Funktionsimplementierung lässt sich durch die Optionen X und Y konfigurieren. Die beiden Optionen kontrollieren die An- bzw. Abwesenheit zweier Code-Fragmente. Option Y kontrolliert den Funktionsparameter int b. Option Y kontrolliert die Zuweisung c = c+b. Auf Grundlage der Werte für X und Y (entweder true/1 oder false/0) lassen sich vier unterschiedliche Varianten der Funktion erstellen:

1. X = false; Y = false;
2. X = false; Y = true;
3. X = true; Y = false;
4. X = true; Y = true;

#ifdef Direktiven spielen eine wichtige Rolle bei der Umsetzung von Variabilität in C-Source-Code und so kommen in vielen Softwaresystemen, die in C geschrieben sind, #ifdef Direktiven zum Einsatz. Darunter z.B.:

• Das Datenbanksystem PostgreSQL,
• Das Versionsverwaltungssystem Subversion (SVN),
• Die kryptografische Bibliothek OpenSSL,
• Der Texteditor VIM,
• Die Programmiersprache Python,
• Der Webserver Apache,
• und viele mehr.

Die Anzahl der Konfigurationsoptionen in diesen geht in die Hunderter/Tausender. Durch die Kombinatorik von true und false für unterschiedliche Konfigurationsoptionen entsteht schnell eine astronomisch große Anzahl unterschiedlicher Varianten, die sich aus einem einzelnen, konfigurierbaren System durch Generierung erstellen lassen. Die Absicherung dieser Varianten stellt eine große Herausforderung dar, weil für die Auslieferung des Systems möglichst alle Varianten vollumfänglich überprüft werden sollten. Fehler können bei der Entwicklung eines variantenreichen Systems recht schnell entstehen.

So enthält das o.g. Beispiel einen Typ-Fehler: Die Variable b in der Zuweisung c = c+b ist für die Kombination X = false und Y = true nicht definiert, weil der Funktionsparameter int b vom Präprozessor vor der Kompilierung entfernt wird.

Zur Überprüfung solcher Fehler könnte folgende, einfache Strategie verwendet werden: Zuerst wird jede mögliche Variante generiert, um anschließend mittels einer Analyse überprüft zu werden. Dieser Ansatz, in der Praxis auch als Brute Force bezeichnet, skaliert jedoch nicht, denn mit einer angenommen Analysedauer von 10s pro Variante, würde die Gesamtzeit für die Analyse des Linux-Kernels mit 2⁶⁰⁰⁰ Varianten 4,8*10¹⁷⁹⁹ Jahre dauern.

Obwohl die einzelnen Varianten der Funktionsimplementierung unterschiedlich sind, so weisen sie viele Gemeinsamkeiten auf. So teilen im Beispiel alle Varianten den Funktionsparameter int a (Zeile 1) und die Anweisung zum Rückgabewert der Funktion return c (Zeile 7). Analysestrategien, die einzelne Varianten untersuchen, analysieren also gemeinsame Bestandteile mehrfach mit exponentiellem Aufwand.

Variabilitätsgewahre Analysen: Datenstrukturen und Algorithmen

Variabilitätsgewahre Analysen sind eine Strategie, um redundante Berechnungen von Analyseergebnissen zu vermeiden. Die Strategie basiert darauf, Variabilitätsinformationen (d.h., Beziehungswissen in Form von #ifdefs mit Konfigurationsoptionen) bei der Berechnung von Analyseergebnisse mit zu berücksichtigen, um so sowohl Gemeinsamkeiten als auch Unterschiede (d.h. variable Code-Fragmente) nur einmal analysieren zu müssen.

Statische Analysen (bspw. Typ-Checking oder Datenflussanalysen), so wie sie typischerweise in Programmierumgebungen wie z.B., Eclipse oder IntelliJ Idea, zum Einsatz kommen, arbeiten in der Regel nicht direkt auf dem Quellcode, sondern nutzen passende Repräsentationen des Quellcodes. Eine typische Repräsentation ist ein Abstract Syntax Tree (AST). Dieser spiegelt die wesentliche Struktur des Programmcodes wider und abstrahiert von der Syntax (u.a. Klammerung, Codeeinrückung oder Kommentare). Zur Repräsentation von Quellcode mit #ifdef Direktiven verwenden wir einen AST Baum in dem variable Code-Fragmente repräsentiert werden können. So ist Funktionsparameter int b ein variabler Knoten im AST (hier grün dargestellt). Der so erstellte AST repräsentiert alle vier Varianten der konfigurierbaren Funktionsimplementierung in einer kompakten Repräsentation.

Eine weitere Repräsentation für statische Analysen ist der Control Flow Graph (CFG). Ein CFG repräsentiert alle möglichen Ausführungspfade in einem Programm durch eine Nachfolgerbeziehung von Programmanweisungen (successor oder succ-Beziehung). So ist der Nachfolger der Zuweisung int c = a (Zeile 2) immer die Bedingung c der if Anweisung (Zeile 3). In unserem Kontext repräsentiert der CFG die Ausführungspfade aller möglichen Varianten der Funktionsimplementierung. Das führt dazu, dass der Nachfolger einer Programmanweisung ein variables Ergebnis sein kann und von Konfigurationsoptionen abhängig ist. So ist auf c = 1 (Zeile 4) folgende Programmanweisung ein variables Ergebnis und abhängig von der Konfigurationsoption Y. Falls Y = true, dann wird c = c+b als nächste Anweisung ausgeführt. Mit Y = false folgt der Rückgabewert der Funktion return c. Diese kompakte Repräsentation aller Programmausführungspfade ist die Grundlage für die effiziente Berechnung von Analysergebnissen für Datenflussanalysen.

Drei Prinzipien

Die folgenden drei Prinzipien stellen sicher, dass Analyseergebnisse zwischen verschiedenen Varianten geteilt werden. Die drei Prinzipien werden am Beispiel einer variabilitätsgewahren Liveness-Analyse erklärt. Liveness ist eine klassische Datenflussanalyse, die für einen konkreten Knoten im CFG berechnet, welche Variablen live sind, d.h. im weiteren Programmablauf noch Verwendung finden. Die Berechnung der live Variablen liefert eine Menge von Variablen zurück. Diese Menge kann dafür verwendet werden, um konservativ Dead Code (genauer Dead Stores) zu bestimmen. Dead Code repräsentiert Programmteile, die nicht verwendet werden und für Optimierungszwecke gelöscht werden können. Im konkreten Fall wird die Variable b nur verwendet, wenn die Konfigurationsoption Y eingeschaltet ist.

1. Mit dem Prinzip Late Splitting wird sichergestellt, dass eine Analyse solange nicht variabilitätsgewahr läuft, bis Variabilität in der Eingabe auftritt. Im konkreten Beispiel, splittet sich die Analyse mit dem variablen Kontrollfluss für die Zuweisung c = 1 auf. D.h. die Analyse wird geteilt und es werden separate Analyseergebnisse für die beiden Pfade Y und !Y berechnet. So entsteht für den Pfad Y das Ergebnis {cY,bY}.

2. Das Prinzip Early Joining stellt sicher, dass Ergebnisse unterschiedlicher Analysepfade zusammengeführt werden, wann immer Gemeinsamkeiten in der Eingabe erreicht werden. Im konkreten Fall, werden die durch Late Splitting berechneten Analysepfade zu einem Gesamtergebnis gejoined. Dabei werden Variabilitätsinformationen gleicher Pfade logisch kombiniert. Aus Y und !Y wird durch Y v !Y (mit dem logischen oder/v) true, weil die Variable c in jeweils beiden Pfaden live ist.

3. Das Prinzip Compact Representation adressiert die Art und Weise wie Analyseergebnisse gespeichert werden. Im Bild werden zwei unterschiedliche Repräsentation für das unter Prinzip 2 zusammengefügte Ergebnis gezeigt. Die erste Repräsentation {c,bY} ist dabei kompakter als die Zweite. Variabilitätsinformationen stehen direkt an den Variablen anstelle von Ergebnismengen (wie z.B. {c,b}Y). In unserem Beispiel sind die Auswirkungen noch gering. Nehmen wir jedoch an, dass die Variable c in 2⁶⁰⁰⁰ unterschiedlichen Varianten auftritt, dann müsste diese Variable ebenso häufig in unterschiedlichen Ergebnismengen gespeichert werden, was in der Praxis nicht möglich ist. D.h. die erste Repräsentation zeigt eine redundanzfreie Speicherung der Analyseergebnisse.

Ausblick

Mit Hilfe dieser drei Prinzipien konnte für unterschiedliche Analysen gezeigt werden (darunter Typ-Checking, Model-Checking und Datenflussanalysen), dass eine astronomisch große Anzahl unterschiedlicher Varianten effizient analysiert werden kann. Die tatsächlichen Analysen und Mehraufwände werden damit auf eine überschaubare Anzahl an Varianten reduziert und ist damit auch für Systeme wie den Linux-Kernel anwendbar. Damit lassen sich diverse Fragestellungen für alle Varianten beantworten, die von einem konfigurierbaren System erstellt werden können.

Folgende Arbeiten beschreiben weitere Details zur Umsetzung:

• Jörg Liebig, Alexander von Rhein, Christian Kästner, Jens Dörre und Sven Apel. Scalable Analysis of Variable Software (European Software Engineering Conference and ACM SIGSOFT International Symposium on the Foundations of Software Engineering (ESEC/FSE)), Seiten 81-91, ACM Press.