形式陈述
从差分约束到带符号坐标
先固定 个数学变量,取值域为 或 ,所有约束非严格,所有端点运算精确。八边形约束允许 ,也允许单变量上下界。二维时这些不等式的边界只有水平、竖直和两种对角方向;交集至多有八个方向的边,名称由此而来,具体集合不必恰有八条边。
引入 个带符号坐标,使用从零开始的下标:
沿用差分约束抽象域与 DBM理路差分约束抽象域与 DBMDifference-bound matrix abstract domain · Zone abstract domain · DBM用差分约束矩阵保存变量关系,经最短路闭包、可靠转移与 raw widening,完整证明一个参数化整数循环的退出断言。的方向, 是 的上界。这一关系抽象域理路抽象域Abstract domain · Domain of abstract properties用带精度次序和合流运算的抽象元素表示具体状态集合,为可靠静态近似提供语义空间。的具体含义是
坐标满足 ,因此同一个表达式有两种写法:。矩阵称为相干(coherent),若
输入一条约束时,同时收紧这两个位置即可保持相干。以 为例, 存在 与 , 存在 与 。一元界 写成 ,所以无需再添加恒零坐标。
普通闭包后的加强公式
先对相干矩阵做普通最短路闭包,得到 。初始化对角线时取原值与零的较小者,保留已有的负对角;若发现负环,结果为空。确认非空后,对角线为零,且
闭包仍相干:每条 路径反向并对各下标取横线,得到一条同权的 路径。然而,普通路径相加尚未用足带符号坐标的身份。由两条一元约束
相加并除以二,还能推出 的界。于是定义一次加强:
相干矩阵若具有零对角、满足所有三角不等式,并且满足
就称为强闭合。在上述有理数或实数模型下,先普通闭包、再一次加强,即得到与原输入具有相同具体含义的强闭合矩阵;不需要交替重复这两步。下面分别解释可行性与“一次就够”的原因。
整数紧闭包的完整接口
现在改为 ,矩阵有限元素也取整数,记具体化为 。输入仍相干,运算精确;约定 。紧闭合矩阵满足前述强闭合的全部条件,而且每个有限一元元素 都是偶数。整数正规化 按以下顺序执行:
- 对输入使用Floyd–Warshall 算法理路Floyd–Warshall 算法Floyd–Warshall algorithm以允许的中间顶点集合为阶段计算全部顶点对最短路。做普通闭包,保留负对角的检测;若有负环,返回 。否则得到相干闭矩阵 。
- 计算 、。若某个 ,返回 。
- 同时使用第二步的数组,返回
第二步的一元区间是 ;若下界超过上界,整数解不存在。注意先分别取整再相加,不能改成只对两个数之和除二后取整。结果在一元位置满足 。普通闭包后只需这一次 扫描,总时间仍为 。[4, Theorems 2–3]
该算法的结论是
以下给出矩阵闭合、整数可行性与 join 所用规范形三个不同环节,避免把实数的中点证明搬到整数上。
直觉
为什么负环检查仍然有效
普通 DBM 算法暂时把 个坐标当成独立势能。若它有一个解 ,相干性保证 也是解,因为
差分约束的解集是凸的,因此中点 仍满足全部约束,并且 。取 ,便得到真正的程序状态。反过来,任何程序状态显然给出一个独立势能解。故在 或 上,普通 DBM 可行性与带符号约束可行性等价;加强只显化逻辑后果,不会删除合法状态。
这里的中点是模型中真正需要的运算。整数势能的中点可能是半整数,所以整数八边形不能直接沿用这一可行性结论。
为什么加强不会破坏路径闭包
写成 、,加强公式就是 。闭包与相干性给出
即 。同理 ;无负环还保证 。
现在展开 中两个最小值,共有四种候选和。每一种都不小于 :
所以它们的最小值仍满足 ,三角不等式得以保留。公式也保持相干; 保证 。最后,一元位置不变:因 ,有 。因此加强右侧的一元界并未继续变化,所得 已满足强闭合的全部条件。允许 时这些比较仍成立,因为全过程没有 。
取整后仍闭合,并确实存在整数状态
在未触发第二步拒绝时,由 的相干性和三角不等式有
最后一步用到 是整数;同理 。同时 。把上一节四项最小值证明中的 换为这些取整值,每一行仍成立,故 仍满足全部三角不等式。相干性、零对角与 也成立;其加强右侧正是 ,所以 紧闭合。
新增约束来自整数一元界 与 ,是原输入的逻辑后果;因此不会删掉整数解。但“没有删解”尚未证明有解。下面的扩展引理补上这一点。
从任意紧闭合矩阵中删去一个变量的正负两行列,所得主子矩阵仍紧闭合。假定其余变量已有整数赋值,且满足该主子矩阵。令被删变量的一个符号坐标为 ;对保留下来的下标集 ,所有涉及 的约束恰好要求
这里改用 、,均为整数或无穷;无穷界直接略去。符号相干性使涉及 的约束也已经包含在这些上下界中。
每个左候选都不超过每个右候选:一元对由 ;两个二元候选由
二元下界与一元上界由 ;一元下界与二元上界由 、。后两条关于 的不等式由相干性与闭合像上面一样推出。故区间非空,有限端点均是整数,可以选整数 ;若一侧或两侧无界,也能选到整数。以变量个数作数学归纳理路数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。,由零变量情形逐个扩展,就得到 。这也说明投影删去一个变量时,紧闭合主子矩阵没有额外丢掉可扩展性。
饱和与规范形引理。 紧闭合非空矩阵还满足
有限上界能够由某个整数状态达到;无穷元素对应无上界的表达式。这是整数饱和定理,不是仅由任意 DBM 的三角不等式推出的性质。Miné 的 Theorem 7及其 Appendix B 给出证明:对一个有限元素加入相干反向约束以强迫等号,紧规范化可能出现的矛盾分别被原矩阵的三角式、加强式及一元偶数性排除;无穷情形则可强迫任意大的有限下界。[1] 这里引用该引理,再完整推导下面的最佳 join。
由饱和式,同一非空整数八边形只有一个紧闭合表示,且两者的具体包含等价于逐元素比较。空集统一使用 ,不能拿任意一个含负环矩阵当作其规范表示。
例子与边界
一张完整的四阶矩阵证书
设初始集合为
仍按 排列行列。直接写入约束、普通闭包、加强,分别得到
例如普通闭包沿 得到 ;加强利用 与 ,将它收紧为 ,即 。同理 表示 。
矩阵其余项也可直接核验。 的顶点是 ,所有 都是线性函数,在这些顶点上取最大值便得到整张 。其非对角信息归结为
上下界分别都由列出的顶点达到。这既检查了十六个元素,也说明这次加强没有改变 。初始的和界 本就能由两个变量的上界相加得到;此处展示的是带符号 DBM 如何显化它,域的表达能力差异要看接下来的过滤。
一条和式 guard 改变了能够证明的断言
考虑程序:
textassume 0 <= x <= 2 and 0 <= y <= 3 and x-y <= 1
assume x+y <= 4
x := x+1
assert x+y <= 5
1
2
3
4
第二行把相干位置 的界同时改为 。本例所得 已强闭合。赋值对应带符号位移 ,精确更新为 ,所以
该公式是赋值前后的差直接代换:,逆平移给出反向包含,故不是仅仅可靠的外近似。读 或相干的 ,即得到全部执行都满足的 。
guard 后的多边形顶点是 。它仍具有与 相同的各变量上下界、 上界 及下界 ,因此它的最佳 zone 外近似仍是 ,其中包含已被 guard 排除的点 。平移后这个伪状态变成 ,违反待证断言。独立区间抽象域理路区间抽象域Interval abstract domain · Interval analysis domain以变量上下界近似数值状态,并用区间 transfer、join 与 widening 求解程序范围。也保留这一伪状态;即便区间端点完全精确,仍无法保存 。
从区间与差分约束到和式 guard 整数矩阵:从奇数一元界到六个格点
取相干输入
它表示 。普通闭包及紧闭包分别为
例如 ,给出 ;一元界变为 ,此时 自动满足。全部整数状态是
在这六点上分别最大化十六个 ,逐项重现 。这是本例规范性可直接复核的证书,不能用有限枚举替代上一节任意维数的可行性论证与饱和引理。
反例矩阵
已经普通闭合,实数解为 ,但取整检查为 ,因此整数紧闭包返回 。若先相加再除二,会错误得到零并漏掉这个矛盾。
规范 join:包含并集的最佳八边形
对非空紧闭合 ,定义
由饱和引理,这恰是两个具体集合并上每个允许表达式的上确界。任何包含该并集的八边形,都必须给每个表达式至少这么大的界,所以该矩阵是最佳八边形上近似,而不是任选一个可靠包围盒。
结果仍紧闭合。相干与一元偶数性由最大值保留。对三角式, 与 分别不超过
故两者最大值也不超过它;加强式用相同论证,将右侧换成两个一元最大值之和的一半。零对角同样保留。因此两个输入先紧闭包以后,join 本身只需 ,无需再次 Floyd。规定 ,覆盖两个输入都为空的情形。
例如一维整数点 、 的紧矩阵分别为
逐项最大值得 ,表示 ,还含整数 。最佳抽象 join 通常不是具体集合并;未规范化输入又会因隐含界未显化而失去“最佳”结论。[1, §4.1]
任意斜率仍超出表达能力
八边形也不能精确表示整个直线 。它只有系数为 的双变量约束及一元约束;在这条无界直线上,每个非零的允许线性表达式都向上无界,因此任何有限的此类界都会误删真实点。任意线性多面体可用两个不等式 、 表示该直线,表达能力因此更强。
多面体抽象域理路多面体抽象域Polyhedral abstract domain · Affine inequalities domain · Convex polyhedra domain以有限仿射不等式表示实数程序状态,经闭凸包汇合、guard 相交与旧变量消元,完整验证一次分支程序的关系断言。从这条斜率为二的关系继续:两条平行分支线段先汇合,再经 guard 截取和仿射赋值消元,最终得到 与 的完整安全证书。它允许约束方向随程序关系改变,同时承担投影和凸包带来的约束增长成本。
推论与应用
关系精度对应哪些计算代价
对 个程序变量,矩阵有 行列,空间为 。普通 Floyd 闭包耗时 ,随后加强扫描全部元素,耗时 ,完整规范化仍为 。一条二元 guard 只需先写两个相干位置,写入成本为 ,之后通常要重新规范化;不能把写入成本当作整个过滤操作的成本。
单变量平移只影响该变量两个带符号坐标的行列,更新成本为 。它保持相干、三角不等式和加强关系:位移在三角式中相消,且 使加强式两侧得到相同的位移。因此从强闭合输入出发,本例的平移无需重新做立方成本的闭包。
前面的实数算例完成了同一条验证链:用相干性记录符号配对,用中点论证可行性,用一次加强补全一元界之间的推论,再以和式 guard 与平移保留断言需要的关系。它适合差与和共同出现的数值不变量;选择此域的收益,正是像例子中那样保住 zone 会丢失的斜向边界。
Widening 为什么必须保留未闭合的历史
整数八边形也有无限上升链。使用逐项 widening理路Widening 与 NarrowingWidening and narrowing · Widening operator · Narrowing operator以 widening 强制抽象迭代有限稳定,再用 narrowing 在可靠上界内恢复部分精度。
每项要么保留原界,要么删除,结果覆盖两个输入。相干输入同时删除一对相干位置,但输出无需紧闭合。保存 raw 历史 ,另取紧闭包副本 来计算转移、guard 与规范 join,得到可靠候选 ,最后仅更新
有限个矩阵位置各自最多从其初始有限值变为无穷一次,因此无论新候选如何变化,历史矩阵最终稳定。规范化副本和历史矩阵是两个不同用途的对象;如果把 回写历史,上面的终止证明就不再成立。空历史按 初始化,空右候选不要求丢弃任何历史界。
下面给出一条具体的整数反例链,所有矩阵按 排列:
表示 ; 表示 。它们紧闭合,而且 。对同一组候选比较
| 轮数 |
错误回写一侧的具体绝对界 |
raw 历史的剩余信息 |
| 0 |
|
|
| 1 |
|
|
| 2 |
|
仅 |
| 3 |
|
同上一轮 |
| 4 |
|
同上一轮 |
表中绝对界都是集合真正达到的最大值,并非 raw 矩阵必须显式存着的元素。第一轮删去 的一元界,但 与 可重建 。若把该闭包拿作下一次左参数,第二轮保留刚重建的 界、删去 界,又能推出 。归纳可得 的绝对界为 , 为 ;在每轮有限的一侧端点取等并让另一坐标相差一,就达到这些界。因此具体集合严格扩大,永不稳定。
raw 历史则不会恢复已删除的 元素,第二轮删除 元素后,两方向的绝对界都无穷,只保留相对关系,第三轮开始矩阵不再变化。这是闭包回写能真正导致发散的反例,而不仅是“现有证明不适用”。Miné 的 §4.7 Figures 25–26展示同类机制。[1]
参考资料
[1] Antoine Miné, “The Octagon Abstract Domain”, Higher-Order and Symbolic Computation 19, 2006, pp. 31–100。此处参照 2006-04-13 的 90 页作者版,§§3.1、3.3–3.5、Theorems 2–7 与 Appendix B,讨论带符号表示、相干性、强闭包及其语义性质。
[2] Antoine Miné, “Tutorial on Static Inference of Numeric Invariants by Abstract Interpretation”, 2017,§5.4.5,印刷页 137–140,式 (5.19)–(5.21)。给出普通闭包后加强的算法与整数情形的区别。
[3] Aziem Chawdhary, Ed Robbins and Andy King, “Incrementally Closing Octagons”, Formal Methods in System Design,§5.1、Theorem 5.1 证明闭合相干矩阵经加强即强闭合,§6 单独处理整数紧闭包。
[4] Roberto Bagnara、Patricia M. Hill、Enea Zaffanella,An Improved Tight Closure Algorithm for Integer Octagonal Constraints,VMCAI 2008作者版,§4 Definition 5、Theorems 2–3与Figure 2(作者PDF第6、11–12页)。其边权约定与本文相反,转置后得到本页公式;一元收紧必须是原界除二向下取整后再乘二。