
用反合一对形式化策略进行语义差异比较
AWS机器学习博客于2026年11月11日23时33分03秒(UTC)发布了题为《Semantic diffing of formal policies with anti-unification》的文章。文中介绍的语义差异方法在e图上执行反合一,用来识别两个形式化策略表示所共有的结构,同时保留在已声明代数定律和重写规则之下仍然不同的两个片段版本。它所给出的不是单纯按文本位置排列的改动清单,而是一个能够展示共同部分与局部分歧的结构化结果。
共同骨架与Variants节点
反合一器只保存一次共享结构,并用Variants节点标记意见不一致的位置。每个此类节点都保留来自两个输入的对应片段。如果在所有Variants节点中始终选择属于同一个输入的那一侧,就可以在已声明等式的意义下重建该输入。换言之,结果中的共同骨架承担重复部分,而变体节点集中承载不能被当前等式知识合并的部分。共同检查无需在两边重复展开,差异也因此被限制在具体结构位置。
如果处理后没有剩余差异,那么两个输入在已声明的定律和规则之下等价。这个结论有明确边界:规则集合不完整,或者搜索没有完整完成,都可能让实际上等价的表达式仍显示差异。因此,剩余差异表示当前规则与搜索未能把相关结构统一起来,并不自动证明在更广泛的语义模型中必然不等价。同样,没有剩余差异所表达的也是相对于已声明等式的等价,而不是脱离这些声明的无限制结论。
语言模型与差异引擎的职责
在文章描述的自动形式化流程中,大语言模型负责生成形式化产物,但不负责计算差异。真正的比较由引擎在项编码上完成。该引擎不会直接导入原生的SMT-LIB、Cedar、Dogwood、OpenShell或CEL策略,而是读取这些策略的项表示。这一区分把候选产物的生成与其结构比较分开:模型可以提供形式化候选,而引擎只依据交给它的编码、声明的等式和可用搜索来构造共同骨架及变体。
因此,读者在解释结果时需要同时关注输入是怎样编码的,以及编码覆盖了哪些语义。差异计算并不会为编码中缺失的行为自动补充含义,也不会因为候选来自自动形式化流程就自行判断哪个候选符合原始要求。反合一器能够把共同部分和不同部分暴露出来,但它不决定哪个候选正确匹配要求。
代数注解、显式重写与恒等元素
引擎支持代数注解和显式重写规则。结合律声明允许不同分组方式被视为等价,交换律声明允许不同排列顺序被视为等价,幂等律声明则允许重复与未重复的形式对齐。声明恒等元素后,缺少的操作数还可以与相应运算符的中性元素对齐。由此,文本或树形结构表面上的重新排序、重新分组与重复,不必继续表现为语义分歧。
这些能力并不意味着引擎掌握所有可能的等价关系。哪些差异能够消失,取决于调用者明确提供了哪些代数性质和重写规则。领域重写也可把特定表达形式关联起来,但结论仍然受这些声明约束。如果缺少必要规则,即使两个表达式等价,结果也可能保留变体;如果搜索受预算限制,潜在的合并同样可能尚未找到。
结果中的三项指标
结果报告:size、:cr和:completion。压缩比:cr的计算式是(s − a) / b,其中s是结果大小,a与b分别是较小输入和较大输入的大小。数值为零表示在已声明等式之下完全一致。数值为一只是“没有共享结构”情形的参照值,并不是压缩比的上限。完成状态则报告为exact或budget,用来区分精确完成与受预算约束的结果。
压缩比描述的是结果大小相对于输入大小以及共享程度的关系。较低数值可以伴随更多结构被识别为共同部分,但它本身不能证明候选策略正确,也不能替代对剩余Variants节点的检查。完成状态同样重要:当结果标记为预算状态时,对未消除差异的解释还必须考虑搜索可能没有完全展开这一限制。
跨区域复制示例
在跨区域复制示例中,最初存在五处文本差异。应用已声明的代数性质以及一条领域重写之后,这些差异缩减为两处语义分歧:一处是被削弱的保密条款,另一处是严格的大小阈值。报告的:cr从0.5862下降到0.4000。该变化说明更多表面差异被纳入共同结构,而最终仍保留的两个位置集中展示了规则没有消除的不同含义。
这个示例同时说明了文本差异数量与语义分歧数量并不相同。排序、分组或可由领域规则关联的形式可以被合并,而涉及条款强度或阈值严格性的片段仍作为变体保留。不过,压缩比下降只反映结果中的共享情况,不能单独用来断言任一输入符合要求。
Dogwood候选示例
对于Dogwood候选,代数声明和三条重写规则消除了六处表现形式差异,剩下的是一个模式错误和一个被遗漏的路径保护条件。把一个候选中的正确事件种类与另一个候选中的保护条件组合起来,可以得到一项两个候选都没有直接提供的策略。这一结果展示了共同骨架和局部变体如何把不同候选各自携带的片段分离出来。
然而,引擎并不会据此决定哪个候选正确符合需求。它能够揭示模式问题、缺失的路径保护以及候选之间可以对应的结构,却不承担需求判定。组合得到的策略也只是由示例中的正确事件种类和另一候选的保护条件构成,不能被说成是任一原候选已经提供的内容。
OpenShell与CEL示例
在OpenShell示例中,对二进制文件、主机、端口和层的共同检查都留在共享骨架内。两个Variants节点分别暴露了允许的HTTP方法以及路径范围方面的分歧。共同检查因而不会在差异结果中反复出现,注意力可以集中在方法与路径这两个具体分歧点上。
在CEL示例中,差异被定位到端口443分支中缺失的生产环境条件。当is_prod为假且端口为443时,候选A拒绝请求,而候选B允许请求。这是两个候选在该给定取值下表现不同的具体情况。与此同时,示例的编码没有建模CEL错误或未知值,引擎也没有检查文中所述的输入假设。因此,这一局部行为差异必须在编码范围和未检查假设的边界内理解,不能把未建模行为视为已经分析完成。
精确求解、随时搜索与状态快照
引擎提供一个基于动态规划的精确求解器,同时默认使用可随时返回当前结果的蒙特卡洛图搜索。优化顺序首先考虑结果大小,其次考虑共享骨架的结构。这个优先级说明搜索目标不仅涉及压缩后的规模,也在规模目标之后考虑共同结构的组织方式。
为了支持重复查询和回溯,引擎使用半持久化的push与pop快照,并把这些快照存储为稀疏差异。这样描述的状态机制服务于多次查询和回退过程,而完成字段则让结果表明本次求解是精确完成还是在预算范围内结束。
开源状态与形式化验证边界
该引擎以Apache-2.0许可证发布在GitHub上。它的容器层恢复性质已经使用Verus验证,共有1703个已验证条件,错误数为零。这是针对特定性质的验证结果,不能扩大解释为整个反合一求解器已经获得端到端证明。
完整求解器目前没有端到端的精化证明。引擎记录的等价性理由也尚未成为可由独立过程重放检查的证书。因而,容器层恢复性质的验证、求解器整体的证明状态以及日志理由的证书状态需要分别理解。文章所描述的方法明确展示了共享结构、局部分歧、搜索方式与指标,同时也明确保留了规则完整性、搜索完成度、编码范围和现有形式化保证方面的界限。