Semantic diffing of formal policies with anti-unification

🖼️ 인포그래픽

🖼️ 4컷 인포그래픽

💡 한 줄 요약

형식 정책의 의미 기반 diff는 anti-unification과 e-graph를 이용해 선언된 동등성 아래의 공통 구조와 불일치를 드러내지만, 후보의 정확성까지 보장하지는 않는다.

📌 핵심 요약

• 오픈 소스 엔진은 anti-unification으로 두 표현의 가장 구체적인 공통 패턴을 찾고, e-graph에 기록된 대수 법칙과 도메인 규칙을 활용해 의미에 영향을 주지 않는 구문 차이를 제거한다.
• 자동 형식화에서 LLM은 형식 산출물을 생성하고 diff 계산에는 관여하지 않는다. 모델·프롬프트·샘플링 온도를 바꿔 만든 후보를 비교하면 공통 부분과 변동 부분을 구분해 검토할 수 있다.
• Cedar, Dogwood, OpenShell policies, CEL은 조건·범위·이벤트 등에 관한 번역 불일치가 생길 수 있다. 엔진은 네 형식의 네이티브 정책을 직접 가져오지 않고, 관련 구문을 항으로 인코딩한 입력과 선언된 동등성을 읽는다.
• 예제에서 external과 Not internal의 동등성을 재작성 규칙으로 선언하면 해당 차이는 사라지고 encrypted와 audited의 불일치만 Variants에 남는다. 각 Variants에서 같은 쪽을 선택하면 선언된 동등성 아래에서 해당 원래 입력을 복원할 수 있다.
• :cr은 공유 구조의 정도를 나타내며 0은 선언된 동등성 아래의 완전한 일치를 뜻하지만 정확성을 보장하지 않는다. :completion의 exact와 budget은 탐색 완료 여부를 구분하며, 규칙이나 탐색이 불완전하면 남은 차이가 미발견 동등성을 반영할 수 있다.

🧩 주요 포인트

1. 대수 법칙과 도메인 규칙이 비교의 기준을 결정함 → 정책 의미에 맞는 동등성 선언이 diff 해석의 전제가 된다.
2. Variants가 공통 구조 속에 양쪽 대안을 보존함 → 전체 정책을 반복해서 읽기보다 불일치의 위치와 내용을 중심으로 검토할 수 있다.
3. 낮은 :cr이나 후보 간 일치는 정확성의 증거가 아님 → :completion과 규칙·탐색의 한계를 함께 고려하고, 필요한 경우 SMT solver나 정책 검증기로 차이의 결과를 확인할 수 있다.

🧠 상세 정리

1. 텍스트 차이에서 의미 차이로

형식 정책은 텍스트 diff만으로 비교하기 어려운데, 논리곱의 순서를 바꾸거나 등식의 인수를 교환하거나 동등한 술어를 사용해도 파일의 많은 부분이 달라 보일 수 있기 때문이다. 이런 잡음 속에서는 요구사항의 and가 Or로 바뀌는 실제 동작 차이가 묻힐 수 있어, 원문은 공통점과 불일치를 함께 보여 주는 의미 기반 diff를 제안한다. 엔진이 사용하는 anti-unification은 두 표현의 가장 구체적인 공통 패턴을 찾는 방법이며, 고전적 정식화로 Plotkin의 1970년 논문을 제시한다. 엔진은 동등하다고 알려진 표현을 관리하는 e-graph 위에서 작동하고, 사용자가 제공한 대수 법칙과 도메인 규칙을 비교의 근거로 삼는다. 차이가 모두 사라지면 그 법칙과 규칙 아래에서 두 정책이 동등하지만, 규칙이나 탐색이 불완전할 때 남는 차이는 엔진이 아직 찾지 못한 동등성일 수도 있다.

2. 자동 형식화 후보의 비교와 적용 범위

주요 활용 사례는 자연어 요구사항을 형식 언어로 옮기는 자동 형식화로, LLM은 SMT solver인 Z3와 cvc5의 표준 입력 언어 SMT-LIB이나 권한 제어용 Cedar·Dogwood 등의 산출물을 생성할 수 있다. LLM은 산출물을 작성할 뿐 diff 계산에는 참여하지 않으며, 같은 요구사항을 두 번 번역해 서로 다른 결과를 얻어도 어느 쪽이 맞는지 판별할 정답이 없을 수 있다. 모델·프롬프트·샘플링 온도를 바꾸어 후보를 늘리고 비교하면 유지되는 부분과 변하는 부분이 드러나므로, 검토자는 변동 부분부터 살펴볼 수 있다. 원문은 Cedar의 소유권과 승인 조건, Dogwood의 성공한 이전 응답과 요청 이벤트, OpenShell의 저장소 범위 GET과 조직 범위 POST, CEL의 허용 포트별 production 조건 적용 차이를 예시로 든다. 다만 각 비교는 같은 정책 맥락의 요구사항 번역들을 대상으로 하며, 엔진은 네 형식의 네이티브 정책을 직접 가져오는 대신 관련 구문을 항으로 인코딩하고 비교에 사용할 동등성을 선언한 입력을 읽는다.

3. semantic entropy 및 반례와의 관계

원문은 이 접근을 Farquhar 등이 Nature에 2024년 발표한 semantic entropy의 형식 기법 대응물로 설명한다. 해당 접근은 여러 자연어 답변을 표본으로 얻어 서로 함의하는 답변끼리 묶고 하나의 수치를 보고하지만, 형식 출력에 대한 anti-unification은 공유 구조와 개별 분기까지 보존한다. 따라서 단일 점수로 변동을 요약하는 것에 더해, 후보들이 정확히 어디에서 갈라지는지와 각 대안이 무엇인지 확인할 수 있다. 불일치의 결과는 SMT solver가 한 공식을 만족하면서 다른 공식을 위반하는 구체적 할당을 찾는 방식으로 설명할 수 있고, 검토자는 그 할당을 두 공식에 대입해 상충하는 결정을 추적할 수 있다. anti-unifier 자체는 SMT 질의를 실행하지 않고 공유 구조와 다른 조각을 정리하는 역할을 하므로, 해당 조각의 해소에는 solver나 정책 검증기가 도움을 줄 수 있다.

4. 민감 데이터 정책에서 드러나는 두 불일치

첫 예제의 요구사항은 외부 목적지로 보내는 민감 데이터가 암호화되어야 한다는 것으로, Rule A는 sensitive(data)와 external(dst)를 조건으로 encrypted를 요구한다. Rule B는 Not internal(dst)와 sensitive(data)를 조건으로 audited를 요구하므로, 조건의 순서와 외부 목적지의 표현 방식뿐 아니라 결론도 다르다. 입력은 S-expression으로 작성되며 Formula·Data·Dest와 연산자·술어·상수를 선언하고, And에는 결합법칙·교환법칙·멱등성을 부여한다. exact 알고리즘으로 처음 비교하면 조건 순서 차이는 사라지지만 external과 Not internal 사이, encrypted와 audited 사이에 각각 Variants가 남아 결과는 :size 11, :cr 0.5000, :completion exact가 된다. 이 단계에서 두 Variants 중 하나는 같은 도메인 사실을 다른 어휘로 표현한 차이이지만, 엔진은 구문만 보고 그 동등성을 추론할 수 없다.

5. 도메인 재작성과 손실 없는 병합

external d를 Not internal d와 동등하게 만드는 rewrite를 선언하고 새 동등성이 더 생기지 않을 때까지 포화시킨 뒤 다시 비교하면, 목적지 표현의 차이는 사라진다. 결과에는 공유 조건인 sensitive data와 external dst가 한 번만 나타나고, 요구사항이 암호화를 요구하는 자리에 Rule B가 감사를 요구한다는 encrypted와 audited의 Variants만 남는다. 이때 출력은 :size 8, :cr 0.1429, :completion exact이며, 도메인 규칙이 어휘 차이를 제거해 검토할 불일치를 국소화했음을 보여 준다. 교과서식 anti-unification이 그 자리에 새로운 변수를 놓는 것과 달리, 이 엔진은 Variants 안에 양쪽 해석을 모두 유지한다. 모든 Variants에서 첫 번째 자식을 선택하면 선언된 대수와 재작성 아래의 Rule A를, 두 번째 자식을 선택하면 Rule B를 복원할 수 있으므로 결과는 공유 구조를 한 번만 저장하는 손실 없는 병합이다.

6. 크기·압축 비율·탐색 완료 상태의 해석

:size는 구체적인 노드 수를 세며 Variants 표시 자체는 제외하지만 양쪽 자식은 모두 포함하므로, 전체 구조를 하나의 표시 안에 숨겨 크기를 줄일 수 없다. :cr은 결과 크기 s와 두 입력 중 작은 크기 a 및 큰 크기 b에 대해 (s - a) / b로 계산하고, 입력 크기는 현재 e-graph에서 알려진 가장 작은 동등 표현을 기준으로 한다. 재작성 후 예제는 두 입력이 각각 7개 노드이고 결과가 8개여서 약 0.1429이며, 두 정책 전체를 하나의 Variants에 넣으면 14개 노드로 비공유 기준값 1이 된다. 다만 1은 상한이 아니어서 가장 작은 입력이 각각 10개 노드인데 탐색 결과가 23개 노드라면 1.3이 될 수 있다. :completion은 탐색 공간을 소진했을 때 exact, 기본 anytime 방식의 Monte Carlo 탐색이 공간을 소진하기 전에 playout 한도에 도달했을 때 budget을 표시하며, 낮은 :cr이나 완전한 일치도 두 후보가 같은 오류를 공유할 가능성 때문에 정확성을 보장하지 않는다.

7. 고정된 소스 버전으로 실행하는 절차

원문은 소스에서 엔진을 빌드하는 데 고정된 Rust 툴체인만 필요하며, 형식 검증 주석은 일반 rustc로 컴파일할 때 제거된다고 설명한다. 예제 재현을 위해 https://github.com/yaspar-org/semi-persistent.git 저장소를 복제하고 5a7969ae4ea88117a64faac4f42af5c358e213e2 리비전을 가져와 detached 상태로 체크아웃하는 명령을 제시한다. 이어 cargo build --release로 빌드하고 ./target/release/semi-persistent doc/book/examples/12-first-au.egg를 실행하면 하나의 anti-unify 항이 출력된다. 명령행 인터프리터는 관례상 확장자가 .egg인 S-expression 파일 하나를 읽고, 사용자는 정렬과 연산자를 선언한 뒤 let으로 비교할 두 항을 정의한다. 필요한 재작성 규칙과 포화 실행을 선택적으로 추가한 다음 antiunify를 호출하는 구조이므로, 비교 기준이 되는 구문과 동등성을 입력에 명시하는 과정이 실행의 핵심이다.

8. 대수 주석과 항등원을 통한 구조 정렬

의미에 영향을 주지 않는 구문 변화를 엔진에 알려 주는 수단은 연산자의 대수 성질을 지정하는 주석과 그 밖의 동등성을 표현하는 명시적 재작성 규칙이다. 제시된 시그니처에서 And와 Or는 가변 인수 연산자이며 결합법칙·교환법칙·멱등성을 따르고, 각각 Lit true와 Lit false를 항등원으로 갖는다. Eq에는 교환법칙을 부여하므로 이 선언들이 허용하는 순서 변경·재묶음·중복은 같은 항으로 취급되지만, 추가 항등식은 별도의 rewrite로 작성해야 한다. 특히 :identity는 한 입력에만 있는 논리곱 항을 다른 입력의 Lit true와 대응시켜, 전체 And 표현의 정렬이 실패하는 대신 빠진 항의 위치를 드러내게 한다. 원문은 두 사례 연구가 이 항등원 정렬에 의존한다고 설명하지만 제공된 source_body는 해당 설명의 끝부분에서 잘려 있으므로, 이후 사례나 구현 세부사항까지 확인할 수는 없다.

🧾 핵심 주장 / 시사점

• 의미 기반 diff가 제거하는 차이는 선언된 동등성의 범위에 한정된다. 따라서 남은 Variants를 실제 정책 불일치로 해석할 때는 도메인 규칙이나 탐색의 불완전성도 고려해야 한다.
• 후보의 변동 위치를 드러내는 기능과 후보의 정확성을 판정하는 기능은 구분된다. 공통 구조가 크더라도 같은 오류를 공유할 수 있으며, 구체적인 결정 차이는 solver나 정책 검증기로 추가 확인할 수 있다.
• 이 엔진의 정보 가치는 압축 점수뿐 아니라 양쪽 대안을 보존하는 구조에 있다. Variants는 검토 위치를 좁히면서도 선언된 동등성 아래에서 원래 입력을 복원할 수 있게 한다.

✅ 액션 아이템

• 의미 기반 diff에 사용할 대수 법칙과 도메인 규칙이 정책 의미에 부합하는지 검토한다.
• LLM이 생성한 형식화 후보를 비교하고 Variants에 남은 불일치를 우선 검토한다.
• :cr과 :completion을 함께 해석하고, 필요한 불일치는 SMT solver나 정책 검증기로 결과를 확인한다.

❓ 열린 질문

• 선언된 대수 법칙과 도메인 규칙은 비교하려는 정책의 동등성을 충분히 표현하는가?
• Variants에 남은 차이는 실제 정책 불일치인가, 규칙이나 탐색의 불완전성에 따른 미발견 동등성인가?
• 낮은 :cr을 보이는 형식화 후보들이 같은 오류를 공유할 가능성을 SMT solver나 정책 검증기로 어떻게 확인할 수 있는가?