# Semantischer Vergleich formaler Richtlinien durch Anti-Unifikation

- Source: MechNext — https://mechnext.eu/de/article/69-semantic-diffing-of-formal-policies-with-anti-unification
- Published: 2026-11-12
- Updated: 2026-11-12
- Category: Industry News
- Language: de (Markdown in other languages: ?lang=en, ?lang=sk, ?lang=pl, ?lang=zh, ?lang=ru)

> AWS beschreibt eine Anti-Unifikations-Engine, die gemeinsame Richtlinienstruktur einmal speichert und Abweichungen in Variants-Knoten erhält. Das Ergebnis gilt relativ zu deklarierten Gesetzen, Regeln, Kodierungen und dem Abschluss der Suche.

Der Beitrag _Semantic diffing of formal policies with anti-unification_ im AWS Machine Learning Blog wurde am 11. November 2026 um 23:33:03 UTC veröffentlicht. Er beschreibt einen semantischen Vergleich formaler Richtlinien, der Anti-Unifikation über einem E-Graphen verwendet. Dabei wird die gemeinsame Struktur zweier Eingaben erkannt, während beide Fassungen der Fragmente erhalten bleiben, die sich unter den deklarierten algebraischen Gesetzen und Umschreibungsregeln unterscheiden.

### Gemeinsames Rückgrat und lokale Varianten

Der Anti-Unifikator speichert übereinstimmende Struktur nur einmal. Abweichungen werden durch `Variants`-Knoten markiert, in denen die jeweiligen Fragmente beider Eingaben erhalten bleiben. Wird in jedem dieser Knoten konsequent die Seite einer bestimmten Eingabe gewählt, lässt sich diese Eingabe modulo der deklarierten Gleichheiten wiederherstellen. Das Resultat ist damit ein gemeinsames Richtlinienrückgrat mit lokalisierten Alternativen und nicht lediglich eine Folge geänderter Textzeilen.

Bleiben keine Unterschiede übrig, sind die Eingaben unter den deklarierten Gesetzen und Regeln äquivalent. Diese Einschränkung ist wesentlich: Unvollständige Regeln oder eine unvollständige Suche können Unterschiede zwischen tatsächlich äquivalenten Ausdrücken stehen lassen. Eine verbleibende Variante zeigt somit, was der konfigurierte Vorgang nicht zusammenführen konnte, ohne allein daraus eine weitergehende Aussage abzuleiten.

### Rolle des Sprachmodells

Im beschriebenen Arbeitsablauf zur Autoformalisierung erzeugt ein großes Sprachmodell formale Artefakte, berechnet den Diff jedoch nicht. Die Engine arbeitet dafür mit Termkodierungen. Sie importiert keine nativen Richtlinien in SMT-LIB, Cedar, Dogwood, OpenShell oder CEL. Die Erzeugung formaler Kandidaten und deren Vergleich sind dadurch getrennte Schritte; untersucht werden die der Engine übergebenen kodierten Terme.

### Gleichheiten und Kennzahlen

Die Engine unterstützt algebraische Annotationen und explizite Umschreibungen. Deklarationen für Assoziativität, Kommutativität und Idempotenz machen Umgruppierung, Umordnung und Duplizierung äquivalent. Ein Identitätselement erlaubt außerdem, einen fehlenden Operanden am neutralen Element des Operators auszurichten. Welche strukturellen Unterschiede verschwinden können, hängt damit von den bereitgestellten Deklarationen ab.

Das Ergebnis enthält `:size`, `:cr` und `:completion`. Das Kompressionsverhältnis lautet `(s − a) / b`. Dabei ist `s` die Ergebnisgröße, während `a` und `b` die Größen der kleineren und größeren Eingabe sind. Null steht für vollständige Übereinstimmung unter den deklarierten Gleichheiten. Eins ist eine Referenz für fehlende gemeinsame Nutzung und keine Obergrenze. Der Abschluss wird als `exact` oder `budget` ausgewiesen. Ein niedriger Wert beschreibt starke gemeinsame Struktur, beweist aber nicht die Korrektheit eines Kandidaten.

### Ergebnisse der Beispiele

Im Beispiel der regionsübergreifenden Replikation wurden fünf textuelle Unterschiede durch die deklarierte Algebra und eine domänenspezifische Umschreibung auf zwei semantische Abweichungen reduziert: eine abgeschwächte Vertraulichkeitsklausel und einen strikten Größenschwellenwert. Der gemeldete Wert `:cr` sank von 0,5862 auf 0,4000.

Bei den Dogwood-Kandidaten beseitigten die Algebra und drei Umschreibungen sechs Darstellungsunterschiede. Übrig blieben ein Schemafehler und eine entfernte Pfadschutzbedingung. Die Verbindung der korrekten Ereignisart aus einem Kandidaten mit der Schutzbedingung des anderen ergab eine Richtlinie, die keiner der beiden Kandidaten geliefert hatte. Der Anti-Unifikator legt die Bestandteile offen, entscheidet aber nicht, welcher Kandidat die Anforderung korrekt erfüllt.

Im OpenShell-Beispiel blieben die gemeinsamen Prüfungen von Binärdatei, Host, Port und Schicht im Rückgrat erhalten. Zwei `Variants`-Knoten zeigten Abweichungen bei der erlaubten HTTP-Methode und beim Umfang des Pfades. Im CEL-Beispiel lokalisierte der Diff eine fehlende Produktionsbedingung im Zweig für Port 443. Bei falschem `is_prod` und Port 443 lehnte Kandidat A die Anfrage ab, Kandidat B erlaubte sie. Die Kodierung modellierte weder CEL-Fehler noch unbekannte Werte, und die Engine prüfte die genannten Eingabeannahmen nicht.

### Suche und Grenzen der Verifikation

Die Engine bietet einen exakten Solver mit dynamischer Programmierung sowie standardmäßig eine jederzeit nutzbare Monte-Carlo-Graphsuche. Optimiert wird zuerst die Ergebnisgröße und danach die Struktur des gemeinsamen Rückgrats. Wiederholte Abfragen und Backtracking verwenden semi-persistente `push`- und `pop`-Schnappschüsse, die als dünn besetzte Diffs gespeichert werden.

Die Engine steht auf GitHub unter Apache-2.0 bereit. Ihre Wiederherstellungseigenschaft für Container-Schichten wurde in Verus mit 1.703 verifizierten Bedingungen und null Fehlern geprüft. Der Umfang dieses Ergebnisses bleibt begrenzt: Für den vollständigen Solver existiert kein durchgängiger Refinement-Beweis, und protokollierte Äquivalenzbegründungen sind noch keine unabhängig erneut geprüften Zertifikate.
