
Sémantické porovnávanie formálnych politík pomocou anti-unifikácie
Príspevok AWS Machine Learning Blog s názvom Semantic diffing of formal policies with anti-unification vyšiel 11. novembra 2026 o 23:33:03 UTC. Predstavuje sémantické porovnávanie formálnych politík založené na anti-unifikácii nad e-grafom. Zmyslom postupu je oddeliť spoločnú štruktúru dvoch vstupov od fragmentov, v ktorých sa vstupy líšia, a pritom zohľadniť výslovne deklarované algebraické zákony a prepisovacie pravidlá.
Čo výsledok vyjadruje
Anti-unifikátor uloží spoločnú štruktúru iba raz. Miesta nezhody označí uzlami Variants, ktoré zachovajú obe verzie rozdielneho fragmentu. Konzistentným výberom strany príslušnej k jednému vstupu vo všetkých takýchto uzloch možno spätne zostaviť daný vstup, a to modulo deklarovaných rovností. Výsledok teda nie je iba zoznam odlišných riadkov, ale spoločná kostra doplnená lokalizovanými alternatívami.
Ak po spracovaní nezostanú žiadne rozdiely, vstupy sú ekvivalentné vzhľadom na deklarované zákony a pravidlá. Toto tvrdenie je zámerne ohraničené: neúplná množina pravidiel alebo neúplné vyhľadávanie môže ponechať rozdiely aj medzi výrazmi, ktoré sú v skutočnosti ekvivalentné. Prítomnosť rozdielu preto nemusí znamenať preukázanú neekvivalenciu mimo modelu, ktorý nástroj dostal.
Úloha modelu a vstupný formát
V opísanom postupe autoformalizácie môže veľký jazykový model vytvárať formálne artefakty, ale samotné porovnanie nepočíta. Diff vykonáva engine nad termovými reprezentáciami. Nástroj priamo neimportuje natívne politiky vo formátoch SMT-LIB, Cedar, Dogwood, OpenShell ani CEL; číta ich termové kódovania. Toto rozdelenie odlišuje generovanie kandidátov od deterministického spracovania ich zakódovaných štruktúr.
Deklarované rovnosti a merania
Engine podporuje algebraické anotácie aj explicitné prepisy. Asociativita, komutativita a idempotentnosť umožňujú považovať zmenu poradia, zoskupenia a duplikovanie za ekvivalentné. Deklarovanie identity navyše umožní zarovnať chýbajúci operand s neutrálnym prvkom operátora. Rozsah sémantického porovnania je teda priamo viazaný na zákony a prepisy, ktoré boli nástroju poskytnuté.
Výstup uvádza položky :size, :cr a :completion. Kompresný pomer sa počíta ako (s − a) / b, kde s je veľkosť výsledku a a a b sú veľkosti menšieho a väčšieho vstupu. Hodnota nula znamená úplnú zhodu podľa deklarovaných rovností. Hodnota jedna je referenciou pre prípad bez zdieľania, nie hornou hranicou. Dokončenie sa označí ako exact alebo budget. Nízky pomer sám osebe nepreukazuje správnosť politiky.
Štyri príklady rozdielov
V príklade replikácie medzi regiónmi sa päť textových rozdielov po uplatnení deklarovanej algebry a jedného doménového prepisu zredukovalo na dve sémantické nezhody: oslabenú klauzulu o dôvernosti a prísny limit veľkosti. Hodnota :cr klesla z 0,5862 na 0,4000.
Pri kandidátoch Dogwood algebra a tri prepisy odstránili šesť prezentačných rozdielov. Zostala chyba schémy a vynechaná ochranná podmienka cesty. Spojenie správneho druhu udalosti z jedného kandidáta s podmienkou z druhého vytvorilo politiku, ktorú neposkytol ani jeden z kandidátov. Anti-unifikátor pritom sám neurčuje, ktorý kandidát zodpovedá požiadavke.
V príklade OpenShell zostali spoločné kontroly binárneho súboru, hostiteľa, portu a vrstvy v spoločnej kostre. Dva uzly Variants odhalili nezhody v povolenej metóde HTTP a v rozsahu cesty. V príklade CEL diff lokalizoval chýbajúcu produkčnú podmienku vo vetve pre port 443. Keď bolo is_prod nepravdivé a port mal hodnotu 443, kandidát A požiadavku zamietol, zatiaľ čo kandidát B ju povolil. Kódovanie nemodelovalo chyby ani neznáme hodnoty CEL a engine nekontroloval uvedené predpoklady o vstupoch.
Vyhľadávanie a hranice overenia
K dispozícii je presný solver využívajúci dynamické programovanie a predvolený priebežný Monte Carlo prieskum grafu. Optimalizácia najprv minimalizuje veľkosť výsledku a potom uprednostňuje štruktúru spoločnej kostry. Opakované dopyty a spätné prehľadávanie podporujú polotrvalé snímky push a pop, uložené ako riedke rozdiely.
Engine je dostupný na GitHube pod licenciou Apache-2.0. Vlastnosť obnovy kontajnerových vrstiev bola overená vo Veruse s 1 703 overenými podmienkami a nulou chýb. Toto overenie sa však nesmie zamieňať s dôkazom celého riešenia: úplný solver nemá koncový refinement dôkaz a zaznamenané zdôvodnenia ekvivalencie zatiaľ nie sú nezávisle opakovane kontrolovanými certifikátmi.