AST (Abstract Syntax Tree)

AST (Abstract Syntax Tree) ist eine graphische Darstellung von Quellcode, die hauptsächlich von Compilern verwendet wird, um Code zu lesen und die Ziel-Binärdateien zu erzeugen.

Der AST dieses Codebeispiels:

while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a

Sieht zum Beispiel so aus:

Die Transformation von Quellcode in einen AST ist ein sehr gängiges Muster bei der Verarbeitung jeder Art von strukturierten Daten. Der typische Arbeitsablauf basiert auf der „Erstellung eines Parsers, der Rohdaten in ein graphenbasiertes Format umwandelt, das dann von einer Rendering-Engine genutzt werden kann“.

Dies ist im Grunde der Prozess der Umwandlung von Rohdaten in stark typisierte In-Memory-Objekte, die programmatisch manipuliert werden können.

Hier ist ein weiteres Beispiel aus dem wirklich coolen Online-Tool astexplorer.net:

Beachten Sie, wie im obigen Bild der DOT-Sprachrohtext in einen Objektbaum umgewandelt wurde (der auch als json-Datei konsumiert/gespeichert werden kann).

Wenn Sie als Entwickler in der Lage sind, „Code oder Rohdaten als Diagramm zu sehen“, haben Sie einen erstaunlichen Paradigmenwechsel vollzogen, der Ihnen bei Ihrer Arbeit enorm helfen wird.

Ich habe zum Beispiel ASTs und benutzerdefinierte Parser verwendet, um:

  • Tests zu schreiben, die überprüfen, was tatsächlich im Code passiert (einfach, wenn man Zugang zu einem Objektmodell des Codes hat)
  • Protokolldaten zu verarbeiten, die normale „Regex“-basierte Parser nur schwer verstehen konnten
  • statische Analysen von Code durchzuführen, der in benutzerdefinierten Sprachen geschrieben wurde
  • Datenabzüge in In-Memory-Objekte umzuwandeln (die dann leicht inSpeicherobjekte umwandeln (die dann leicht transformiert und gefiltert werden können)
  • Transformierte Dateien mit Slices aus mehreren Quellcodedateien erstellen (die ich MethodStreams und CodeStreams genannt habe) – Wie dies in der Praxis aussieht, sehen Sie im folgenden Beispiel
  • Benutzerdefiniertes Code-Refactoring durchführen (z. B. zur automatischen Behebung von Sicherheitsproblemen im Code) – Wie dies in der Praxis aussieht, sehen Sie im folgenden Beispiel

Bei der Entwicklung eines Parsers für eine bestimmte Datenquelle ist ein wichtiger Meilenstein die Round-Table-Analyse, Ein wichtiger Meilenstein ist die Fähigkeit, vom AST zurück zum Originaltext zu gelangen (ohne Datenverlust).

Das ist genau die Art und Weise, wie Code-Refactoring in IDEs funktioniert (z.B. wenn man eine Variable umbenennt und alle Instanzen dieser Variable umbenannt werden).

So funktioniert dieser Round-Trip:

  1. Start mit Datei A (d.h..
  2. erstelle den AST von Datei A
  3. erstelle Datei B als Transformation aus dem AST
  4. Datei A ist gleich Datei B (Byte für Byte)

Wenn dies möglich ist, wird es einfach, Code programmatisch zu ändern, da wir stark typisierte Objekte manipulieren, ohne uns um die Erstellung von syntaktisch korrektem Quellcode zu kümmern (der jetzt eine Transformation aus dem AST ist).

Tests mit AST-Objekten schreiben

Wenn Sie anfangen, Ihren Quellcode (oder die Daten, die Sie verwenden) als „nur einen AST-Parser davon entfernt, Objekte zu sein, die Sie manipulieren können“, zu sehen, eröffnen sich Ihnen eine ganze Reihe von Möglichkeiten und Fähigkeiten.

Ein gutes Beispiel ist, wie man ein bestimmtes Muster im Quellcode erkennt, von dem man sichergehen will, dass es in einer großen Anzahl von Dateien vorkommt, sagen wir zum Beispiel, dass man: „Sicherstellen, dass eine bestimmte Autorisierungs- (oder Datenvalidierungs-) Methode bei jeder exponierten Webservice-Methode aufgerufen wird“?

Dies ist kein triviales Problem, denn wenn Sie nicht in der Lage sind, programmatisch einen Test zu schreiben, der diesen Aufruf überprüft, haben Sie nur folgende Möglichkeiten:

  1. Schreiben Sie ein ‚Standarddokument/Wiki-Seite‘, das diese Anforderung definiert, und stellen Sie sicher, dass alle Entwickler es lesen, verstehen und, was noch wichtiger ist, befolgen
  2. Manuell prüfen, ob dieser Standard/diese Anforderung korrekt implementiert wurde (bei Pull Requests Code Reviews)
  3. Versuchen Sie, die Automatisierung mit ‚Regex‘-basierten Tools (kommerziell oder Open Source) zu nutzen, und erkennen, dass es sehr schwer ist, damit gute Ergebnisse zu erzielen
  4. auf manuelle QA-Tests (und Sicherheitsüberprüfungen) zurückgreifen, um blinde Flecken zu entdecken

Aber wenn man die Möglichkeit hat, Tests zu schreiben, die diese Anforderung überprüfen, passiert folgendes:

  1. Schreiben Sie Tests, die den AST des Codes verbrauchen, um sehr explizit prüfen zu können, ob der Standard/die Anforderung korrekt implementiert/kodiert wurde
  2. Über Kommentare in der Testdatei kann die Dokumentation aus dem Testcode generiert werden (d.h..
  3. Diese Tests werden als Teil des lokalen Builds und als Teil der Haupt-CI-Pipeline ausgeführt
  4. Durch einen fehlgeschlagenen Test wissen die Entwickler sofort, wenn ein Problem entdeckt wurde, und können es sehr schnell beheben

Dies ist ein perfektes Beispiel für die Skalierung von Architektur- und Sicherheitsanforderungen auf eine Weise, die in den Softwareentwicklungszyklus eingebettet ist.

Wir brauchen ASTs für Legacy- und Cloud-Umgebungen

Je mehr man sich mit ASTs beschäftigt, desto mehr erkennt man, dass sie Abstraktionsschichten zwischen verschiedenen Schichten oder Dimensionen sind. Aber wenn man sich die aktuellen Legacy- und Cloud-Umgebungen anschaut (der Teil, den wir „Infrastruktur als Code“ nennen), wird man feststellen, dass große Teile dieser Ökosysteme heute keine AST-Parser haben, um ihre Realität in programmierbare Objekte umzuwandeln.

Dies ist ein großartiges Forschungsgebiet, in dem man sich auf die Entwicklung von DSLs (Domain Specific Languages) entweder für Legacy-Systeme oder für Cloud-Anwendungen konzentrieren würde (wählen Sie eines aus, da beide völlig unterschiedliche Quellensätze haben). Ein Beispiel für die Art von DSL, die wir brauchen, ist eine Sprache, die das Verhalten von Lambda-Funktionen beschreibt und kodiert (nämlich die Ressourcen, die sie zur Ausführung benötigen, und das erwartete Verhalten der Lambda-Funktion)

MethodStreams

Eines der leistungsfähigsten Beispiele für AST-Manipulation, die ich gesehen habe, ist das MethodStreams-Feature, das ich der O2-Plattform hinzugefügt habe.

Mit diesem Feature konnte ich programmatisch eine Datei erstellen, die auf dem Aufrufbaum einer bestimmten Methode basiert. Diese Datei enthielt den gesamten Quellcode, der für diese ursprüngliche Methode relevant war (generiert aus mehreren Dateien), und machte einen gewaltigen Unterschied bei der Durchführung von Code-Reviews.

Um zu verstehen, warum ich dies getan habe, lassen Sie uns mit dem Problem beginnen, das ich hatte.

Zurück im Jahr 2010 führte ich einen Code-Review einer .Net-Anwendung durch, die eine Million Codezeilen hatte. Ich betrachtete jedoch nur die WebServices-Methoden, die nur einen kleinen Teil der Codebasis abdeckten (was sinnvoll war, da dies die Methoden waren, die dem Internet ausgesetzt waren). Ich wusste, wie ich diese dem Internet ausgesetzten Methoden finden konnte, aber um zu verstehen, wie sie funktionierten, musste ich mir Hunderte von Dateien ansehen, nämlich die Dateien, die Code im Ausführungspfad dieser Methoden enthielten.

Da ich in der O2 Platform bereits einen sehr starken C#-Parser und Code-Refactoring-Unterstützung (implementiert für das REPL-Feature) hatte, konnte ich schnell ein neues Modul schreiben, das:

  1. ausgehend von der Web-Service-Methode X
  2. alle Methoden berechnete, die von dieser Methode X aufgerufen wurden
  3. alle Methoden berechnete, die von 2. (rekursiv)
  4. Erfassen der AST-Objekte von allen Methoden, die durch die vorherigen Schritte identifiziert wurden
  5. Erstellen einer neuen Datei mit allen Objekten aus 4.

Diese neue Datei war erstaunlich, da sie NUR den Code enthielt, den ich während meiner Sicherheitsüberprüfung lesen musste.

Aber es kam noch besser, denn in diesem Fall konnte ich die Validierungs-RegExs (die auf alle WebServices-Methoden angewendet werden) oben in die Datei einfügen und den Quellcode der entsprechenden Stored Procedures unten in die Datei einfügen.

Einige der generierten Dateien hatten mehr als 3.000 Codezeilen, was eine enorme Vereinfachung gegenüber den mehr als 20 Dateien darstellte, die sie enthielten (die wahrscheinlich mehr als 50.000 Codezeilen enthielten).

Hier ist ein gutes Beispiel dafür, dass ich bessere Arbeit leisten kann, wenn ich Zugang zu einem breiten Spektrum an Fähigkeiten und Techniken habe (in diesem Fall die Fähigkeit, Quellcode programmatisch zu manipulieren)

Diese Art der AST-Manipulation ist ein Forschungsgebiet, auf das ich Ihnen sehr empfehle, sich zu konzentrieren (und das Ihnen auch ein umfangreiches Toolkit für Ihre täglichen Programmieraktivitäten an die Hand geben wird). Übrigens, wenn Sie diesen Weg einschlagen, sollten Sie sich auch die CodeStreams der O2 Platform ansehen, die eine Weiterentwicklung der MethodStreams-Technologie sind. CodeStreams liefern Ihnen einen Stream aller Variablen, die von einer bestimmten Quellvariablen berührt werden (was in der statischen Analyse als Taint-Flow-Analyse und Taint-Checking bezeichnet wird)

Code in Echtzeit reparieren (oder zur Kompilierungszeit)

Ein weiteres wirklich cooles Beispiel für die Leistungsfähigkeit der AST-Manipulation ist der PoC, den ich 2011 zum Thema Fixing/Encoding von .NET-Code in Echtzeit geschrieben habe (in diesem Fall Response.Write), in dem ich zeige, wie man programmatisch eine Sicherheitsbehebung zu einer verwundbaren Methode hinzufügt (by design).

Hier sieht die Benutzeroberfläche so aus, dass der Code auf der linken Seite programmatisch in den Code auf der rechten Seite umgewandelt wurde (durch Hinzufügen der zusätzlichen AntiXSS.HtmlEncode Wrapper-Methode)

Hier ist der Quellcode, der die Umwandlung und die Codekorrektur durchführt (beachten Sie den Rundlauf des Codes):

Im Jahr 2018 besteht die Möglichkeit, diesen Workflow entwicklerfreundlich zu implementieren, darin, automatisch einen Pull Request mit diesen zusätzlichen Änderungen zu erstellen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.