AWS bringt semantische Diffing-Engine für formale Richtlinien als Open Source

AWS hat eine Open-Source-Engine vorgestellt, die formale Richtlinien nach ihrer Bedeutung statt nach ihrem Text vergleicht. Das System nutzt Anti-Unifikation und E-Graphs, um gemeinsame Strukturen einmal darzustellen und Abweichungen für die Prüfung zu erhalten.
- AWS beschreibt eine Open-Source-Engine für semantische Diffs formaler Richtlinien.
- Die Engine nutzt Anti-Unifikation über einem E-Graph.
- Domänenregeln können äquivalente Ausdrücke wie external und not internal erkennen.
- Variants-Knoten bewahren jedes abweichende Richtlinienfragment zur Prüfung.
- Die Ausgabe umfasst die Felder Größe, Kompressionsverhältnis und Suchabschluss.
Warum Text-Diffs Richtlinienänderungen übersehen können
Herkömmliche Diffs können äquivalente Richtlinienausdrücke unterschiedlich erscheinen lassen. Das Umordnen von Konjunktionen, das Vertauschen von Gleichheitsargumenten oder die Verwendung eines äquivalenten Prädikats kann umfangreiches syntaktisches Rauschen erzeugen. Eine bedeutende Änderung, etwa der Ersatz einer and-Anforderung durch eine or-Anforderung, ist dadurch möglicherweise schwerer zu erkennen.
Ein semantischer Diff identifiziert stattdessen, was zwei Richtlinien gemeinsam haben und worin sie sich unterscheiden. AWS zufolge berechnet die Engine dieses Ergebnis mit Anti-Unifikation, einer Methode, die das spezifischste gemeinsame Muster zweier Ausdrücke findet. Die Engine arbeitet mit einem E-Graph, der Ausdrücke erfasst, von denen bekannt ist, dass sie gleich sind. Nutzer geben die algebraischen Gesetze und Domänenregeln vor, die diese Gleichheiten begründen.
Bleiben keine Unterschiede übrig, sind die Richtlinien unter den angegebenen Regeln äquivalent. AWS weist darauf hin, dass eine ungelöste Abweichung auch auf eine Äquivalenz hindeuten kann, die von den Regeln oder der Suche nicht gefunden wurde.
Mehrere Formalisierungen einer Anforderung vergleichen
AWS nennt die Autoformalisierung als einen möglichen Anwendungsfall. Ein LLM kann Anforderungen in natürlicher Sprache in formale Sprachen wie SMT-LIB, Cedar, Dogwood, OpenShell policy YAML oder Common Expression Language übersetzen. Das Modell erstellt das formale Artefakt, berechnet den Diff jedoch nicht.
Wird ein Modell mehr als einmal ausgeführt, kann es unterschiedliche Formalisierungen derselben Anforderung erzeugen, ohne dass eine Referenzlösung vorliegt, die das korrekte Ergebnis bestimmt. Der Vergleich mehrerer Kandidaten kann zeigen, welche Teile stabil bleiben und welche variieren. Prüfer können sich dann zuerst die variierenden Teile ansehen. AWS zufolge arbeitet die Engine mit Kodierungen dieser Sprachen, statt native Richtlinien aus den vier veranschaulichten Formaten zu importieren.
Die Quelle nennt Beispiele für Abweichungen bei Autorisierungsbedingungen, der Ereignishistorie, dem Datei- und Netzwerkzugriff, HTTP-Methoden sowie Bedingungen für erlaubte Ports. Diese Unterschiede können eine Bedingung, einen Geltungsbereich oder ein Ereignis betreffen.
Eine prüfbare Zusammenführung zweier Richtlinienregeln
In AWS' Beispiel besagt eine Kandidatenregel, dass sensible Daten, die an ein externes Ziel gesendet werden, verschlüsselt werden müssen. Regel A beschreibt das Ziel als external, während Regel B not internal verwendet und daraus folgert, dass die Daten protokolliert werden sollten.
Zunächst markiert die Engine sowohl die Zielausdrücke als auch die Schlussfolgerungen als Varianten. Anschließend gibt AWS eine Umschreibregel vor, der zufolge ein externes Ziel eines ist, das nicht intern ist. Nachdem der E-Graph seine Sättigung erreicht hat, bleiben nur die Schlussfolgerungen unterschiedlich: Regel B protokolliert die Daten, obwohl die Anforderung eine Verschlüsselung verlangt.
Das Ergebnis bewahrt beide Alternativen in einem Variants-Knoten. Wird aus jedem solchen Knoten jeweils ein Kind ausgewählt, lässt sich unter Berücksichtigung der deklarierten Algebra und Umschreibregeln einer der beiden Eingänge rekonstruieren. AWS beschreibt dies als verlustfreie Zusammenführung, bei der gemeinsame Strukturen einmal dargestellt und echte Abweichungen für die Prüfung lokalisiert werden.
Welche Informationen die Ausgabe Prüfern liefert
Die Engine meldet drei Felder. :size zählt konkrete Knoten, während ein Variants-Marker selbst nicht mitgezählt wird. So wird verhindert, dass Struktur innerhalb des Markers verborgen bleibt. :cr gibt ein Kompressionsverhältnis auf Grundlage der Ergebnisgröße sowie der kleinsten und größten Eingabegröße an. Ein Wert von 0 steht für vollständige Übereinstimmung unter den deklarierten Gleichheiten.
Das Feld :completion zeigt an, ob die Suche exakt war oder bei der standardmäßigen Suche mit jederzeit abrufbaren Ergebnissen wegen eines Budgets beendet wurde. Der resultierende Diff ersetzt weder einen Solver noch einen Richtlinien-Validator. AWS zufolge kann ein SMT-Solver eine konkrete Belegung liefern, die eine Formel erfüllt und eine andere verletzt, während der Anti-Unifikator die gemeinsamen und unterschiedlichen Fragmente strukturiert, ohne eine SMT-Abfrage auszuführen.
Für Nutzer, die generierte Richtlinien prüfen, bietet der Ansatz eine Möglichkeit, die Aufmerksamkeit auf Abweichungen zu richten und zugleich die vollständigen Alternativen zu erhalten. In Workflows für formale Methoden ermöglicht er einen strukturierten Vergleich, der Gegenbeispiele und die Richtlinienvalidierung ergänzen kann.

