Semantic diffing of formal policies with anti-unification

Semantic Diffing of Formal Policies with Anti‑Unification

When you compare two versions of source code, a line‑by‑line diff quickly shows what changed. Formal policies, however, are often expressed in languages where syntactic differences hide semantic equivalence—reordering conjuncts, swapping predicates, or applying equivalent rewrites can make two policies look wildly different even though they enforce the same rules. A semantic diff solves this problem by extracting the common structure of two policies and exposing only the truly divergent fragments.

---

How Anti‑Unification Works

Anti‑unification is the dual of unification: instead of finding a substitution that makes two terms identical, it finds the most specific common generalization (the anti‑unifier) of those terms. The classic formulation appears in Plotkin’s 1970 paper and has been revived in modern e‑graph libraries. An e‑graph stores equivalence classes of expressions; by feeding it a set of algebraic laws and domain‑specific rewrite rules, the engine can saturate the graph—i.e., discover all equalities implied by those rules.

When two policy expressions are submitted, the engine:

1. Parses each expression into an S‑expression tree.
2. Declares the relevant function symbols (e.g., `And`, `Implies`, `Not`) and their properties (associative, commutative, idempotent).
3. Adds any domain rewrites (e.g., `external(d) ↔ ¬ internal(d)`).
4. Runs anti‑unification to produce a single term that contains Variant nodes wherever the inputs differ.

The result shows shared sub‑terms only once, while each disagreement is wrapped in a `Variants` node that lists the alternative fragments.

---

Why It Matters for Auto‑Formalization

Large language models (LLMs) are increasingly used to translate natural‑language requirements into formal policy languages such as SMT‑LIB, Cedar, Dogwood, OpenShell YAML, or Common Expression Language (CEL). Running the model twice—perhaps with different prompts or temperature settings—often yields two syntactically distinct formalizations with no obvious ground truth.

A semantic diff provides a focused review surface:

• Agreement zones appear a single time, reducing visual noise.
• Disagreement zones are highlighted, allowing reviewers to prioritize the parts that actually vary.
• By feeding the differing fragments to an SMT solver, you can generate concrete counter‑examples that satisfy one version and violate the other, turning abstract differences into actionable test cases.

---

A Concrete Example

Consider the requirement “Sensitive data sent to an external destination must be encrypted.” Two candidate rules might be generated:

```lisp ;; Rule A (Implies (And (sensitive data) (external dst)) (encrypted))

;; Rule B (Implies (And (Not (internal dst)) (sensitive data)) (audited)) ```

Both use the same predicates but differ in ordering, vocabulary (`external` vs. `¬ internal`), and conclusion (`encrypted` vs. `audited`).

1. Declare the vocabulary (including `And` as associative/commutative).
2. Run anti‑unification without domain rewrites. The engine returns a term with two `Variants` nodes—one for the condition (`external dst` vs. `¬ internal dst`) and one for the conclusion.
3. Add a rewrite `external(d) → ¬ internal(d)` and re‑run saturation. The condition variant disappears, leaving only the conclusion difference.

The final anti‑unifier looks like:

```lisp (Implies (And (sensitive data) (external dst)) (Variants encrypted audited)) ```

Now it is crystal clear that the only substantive disagreement is whether the policy mandates encryption or auditing.

---

Practical Takeaways

• Integrate anti‑unification early in any pipeline that generates formal policies from natural language; it turns a flood of candidate artifacts into a concise, review‑ready diff.
• Maintain a library of domain rewrites (e.g., equivalences between network predicates) to improve the engine’s ability to collapse superficial differences.
• Pair the diff with an SMT solver to produce concrete counter‑examples for each `Variants` node, giving reviewers a tangible sense of impact.
• Use the output as documentation: the shared core of the policy can be extracted as a canonical representation, while each variant can be annotated with provenance (model version, prompt, etc.).

By focusing on what actually changes rather than how it is written, semantic diffing with anti‑unification makes policy engineering more transparent, reduces review effort, and helps ensure that automated formalizations remain faithful to the original intent.