Skip to content

定义Definition

八边形抽象域

施工中 · 内容逐步修订

Octagon abstract domain · Octagonal constraints

从强闭包进入整数紧闭包,以整数扩展、规范join和具体发散链证明为何widening必须保存未闭合历史。

形式陈述 ​

从差分约束到带符号坐标 ​

先固定 n 个数学变量,取值域为 K=Q 或 R,所有约束非严格,所有端点运算精确。八边形约束允许 ±xp±xq≤c,也允许单变量上下界。二维时这些不等式的边界只有水平、竖直和两种对角方向;交集至多有八个方向的边,名称由此而来,具体集合不必恰有八条边。

引入 2n 个带符号坐标,使用从零开始的下标:

z2p=xp+1,z2p+1=−xp+1,i¯=ixor1.

沿用差分约束抽象域与 DBM的方向,Mij∈K∪{+∞} 是 zj−zi 的上界。这一关系抽象域的具体含义是

γoct(M)={x∈Kn: ∀i,j, zj(x)−zi(x)≤Mij}.

坐标满足 zi¯=−zi,因此同一个表达式有两种写法:zj−zi=zi¯−zj¯。矩阵称为相干(coherent),若

Mij=Mj¯,i¯.

输入一条约束时,同时收紧这两个位置即可保持相干。以 (z0,z1,z2,z3)=(x,−x,y,−y) 为例,x+y≤c 存在 (1,2) 与 (3,0),x−y≤c 存在 (2,0) 与 (1,3)。一元界 x≤u 写成 z0−z1=2x≤2u,所以无需再添加恒零坐标。

普通闭包后的加强公式 ​

先对相干矩阵做普通最短路闭包,得到 C。初始化对角线时取原值与零的较小者,保留已有的负对角;若发现负环,结果为空。确认非空后,对角线为零,且

Cij≤Cik+Ckj.

闭包仍相干:每条 i→j 路径反向并对各下标取横线,得到一条同权的 j¯→i¯ 路径。然而,普通路径相加尚未用足带符号坐标的身份。由两条一元约束

−2zi=zi¯−zi≤Ci,i¯,2zj=zj−zj¯≤Cj¯,j

相加并除以二,还能推出 zj−zi 的界。于是定义一次加强:

Sij=min(Cij,Ci,i¯+Cj¯,j2).

相干矩阵若具有零对角、满足所有三角不等式,并且满足

Sij≤Si,i¯+Sj¯,j2,

就称为强闭合。在上述有理数或实数模型下,先普通闭包、再一次加强,即得到与原输入具有相同具体含义的强闭合矩阵;不需要交替重复这两步。下面分别解释可行性与“一次就够”的原因。

整数紧闭包的完整接口 ​

现在改为 x∈Zn,矩阵有限元素也取整数,记具体化为 γZ。输入仍相干,运算精确;约定 ⌊∞/2⌋=∞。紧闭合矩阵满足前述强闭合的全部条件,而且每个有限一元元素 Ti,i¯ 都是偶数。整数正规化 tc 按以下顺序执行:

  1. 对输入使用Floyd–Warshall 算法做普通闭包,保留负对角的检测;若有负环,返回 ⊥。否则得到相干闭矩阵 C。
  2. 计算 ai=⌊Ci,i¯/2⌋、bi=⌊Ci¯,i/2⌋=ai¯。若某个 ai+bi<0,返回 ⊥。
  3. 同时使用第二步的数组,返回
Tij=min(Cij,ai+bj).

第二步的一元区间是 −ai≤zi≤bi;若下界超过上界,整数解不存在。注意先分别取整再相加,不能改成只对两个数之和除二后取整。结果在一元位置满足 Ti,i¯=2ai。普通闭包后只需这一次 O(n2) 扫描,总时间仍为 O(n3)。[4, Theorems 2–3]

该算法的结论是

tc(M)=⊥⟺γZ(M)=∅,γZ(tc(M))=γZ(M)(非空时).

以下给出矩阵闭合、整数可行性与 join 所用规范形三个不同环节,避免把实数的中点证明搬到整数上。

直觉

为什么负环检查仍然有效 ​

普通 DBM 算法暂时把 2n 个坐标当成独立势能。若它有一个解 v,相干性保证 wi=−vi¯ 也是解,因为

wj−wi=vi¯−vj¯≤Cj¯,i¯=Cij.

差分约束的解集是凸的,因此中点 u=(v+w)/2 仍满足全部约束,并且 ui¯=−ui。取 xp+1=u2p,便得到真正的程序状态。反过来,任何程序状态显然给出一个独立势能解。故在 Q 或 R 上,普通 DBM 可行性与带符号约束可行性等价;加强只显化逻辑后果,不会删除合法状态。

这里的中点是模型中真正需要的运算。整数势能的中点可能是半整数,所以整数八边形不能直接沿用这一可行性结论。

为什么加强不会破坏路径闭包 ​

写成 ai=Ci,i¯/2、bi=Ci¯,i/2,加强公式就是 Sij=min(Cij,ai+bj)。闭包与相干性给出

2ai=Ci,i¯≤Cik+Ck,k¯+Ck¯,i¯=2Cik+2ak,

即 ai≤Cik+ak。同理 bj≤bk+Ckj;无负环还保证 ak+bk≥0。

现在展开 Sik+Skj 中两个最小值,共有四种候选和。每一种都不小于 Sij:

Cik+Ckj≥Cij≥Sij,Cik+ak+bj≥ai+bj≥Sij,ai+bk+Ckj≥ai+bj≥Sij,ai+bk+ak+bj≥ai+bj≥Sij.

所以它们的最小值仍满足 Sik+Skj≥Sij,三角不等式得以保留。公式也保持相干;ai+bi≥0 保证 Sii=0。最后,一元位置不变:因 bi¯=ai,有 Si,i¯=min(Ci,i¯,2ai)=Ci,i¯。因此加强右侧的一元界并未继续变化,所得 S 已满足强闭合的全部条件。允许 +∞ 时这些比较仍成立,因为全过程没有 −∞。

取整后仍闭合,并确实存在整数状态 ​

在未触发第二步拒绝时,由 C 的相干性和三角不等式有

Ci,i¯≤2Cik+Ck,k¯⟹ai≤Cik+ak.

最后一步用到 Cik 是整数;同理 bj≤bk+Ckj。同时 ak+bk≥0。把上一节四项最小值证明中的 a,b 换为这些取整值,每一行仍成立,故 T 仍满足全部三角不等式。相干性、零对角与 Ti,i¯=2ai 也成立;其加强右侧正是 ai+bj,所以 T 紧闭合。

新增约束来自整数一元界 −zi≤ai 与 zj≤bj,是原输入的逻辑后果;因此不会删掉整数解。但“没有删解”尚未证明有解。下面的扩展引理补上这一点。

从任意紧闭合矩阵中删去一个变量的正负两行列,所得主子矩阵仍紧闭合。假定其余变量已有整数赋值,且满足该主子矩阵。令被删变量的一个符号坐标为 u=zi;对保留下来的下标集 J,所有涉及 u 的约束恰好要求

max(−ai, maxj∈J(zj−Tij)) ≤u≤ min(bi, mink∈J(zk+Tki)),

这里改用 ai=Ti,i¯/2、bi=Ti¯,i/2,均为整数或无穷;无穷界直接略去。符号相干性使涉及 −u 的约束也已经包含在这些上下界中。

每个左候选都不超过每个右候选:一元对由 ai+bi≥0;两个二元候选由

zj−zk≤Tkj≤Tki+Tij.

二元下界与一元上界由 zj≤bj≤bi+Tij;一元下界与二元上界由 zk≥−ak、ak≤Tki+ai。后两条关于 a,b 的不等式由相干性与闭合像上面一样推出。故区间非空,有限端点均是整数,可以选整数 u;若一侧或两侧无界,也能选到整数。以变量个数作数学归纳,由零变量情形逐个扩展,就得到 γZ(T)≠∅。这也说明投影删去一个变量时,紧闭合主子矩阵没有额外丢掉可扩展性。

饱和与规范形引理。 紧闭合非空矩阵还满足

Tij=supx∈γZ(T)(zj(x)−zi(x)),

有限上界能够由某个整数状态达到;无穷元素对应无上界的表达式。这是整数饱和定理,不是仅由任意 DBM 的三角不等式推出的性质。Miné 的 Theorem 7及其 Appendix B 给出证明:对一个有限元素加入相干反向约束以强迫等号,紧规范化可能出现的矛盾分别被原矩阵的三角式、加强式及一元偶数性排除;无穷情形则可强迫任意大的有限下界。[1] 这里引用该引理,再完整推导下面的最佳 join。

由饱和式,同一非空整数八边形只有一个紧闭合表示,且两者的具体包含等价于逐元素比较。空集统一使用 ⊥,不能拿任意一个含负环矩阵当作其规范表示。

例子与边界

一张完整的四阶矩阵证书 ​

设初始集合为

P={(x,y):0≤x≤2, 0≤y≤3, x−y≤1}.

仍按 (x,−x,y,−y) 排列行列。直接写入约束、普通闭包、加强,分别得到

M=(00∞∞40∞11∞00∞∞60),C=(0071407111007760),S=(0030405110005360).

例如普通闭包沿 1→3→2 得到 C12=1+6=7;加强利用 C10=4 与 C32=6,将它收紧为 S12=(4+6)/2=5,即 x+y≤5。同理 S03=0 表示 x+y≥0。

矩阵其余项也可直接核验。P 的顶点是 (0,0),(1,0),(2,1),(2,3),(0,3),所有 zj−zi 都是线性函数,在这些顶点上取最大值便得到整张 S。其非对角信息归结为

0≤x≤2,0≤y≤3,−3≤x−y≤1,0≤x+y≤5.

上下界分别都由列出的顶点达到。这既检查了十六个元素,也说明这次加强没有改变 P。初始的和界 5 本就能由两个变量的上界相加得到;此处展示的是带符号 DBM 如何显化它,域的表达能力差异要看接下来的过滤。

一条和式 guard 改变了能够证明的断言 ​

考虑程序:

text
assume 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,0) 的界同时改为 4。本例所得 G 已强闭合。赋值对应带符号位移 δ=(1,−1,0,0),精确更新为 Tij=Gij+δj−δi,所以

G=(0030404110004360),T=(0−22−160522−1005260).

该公式是赋值前后的差直接代换:zj′−zi′=(zj−zi)+δj−δi,逆平移给出反向包含,故不是仅仅可靠的外近似。读 T12=5 或相干的 T30=5,即得到全部执行都满足的 x+y≤5。

guard 后的多边形顶点是 (0,0),(1,0),(2,1),(2,2),(1,3),(0,3)。它仍具有与 P 相同的各变量上下界、x−y 上界 1 及下界 −3,因此它的最佳 zone 外近似仍是 P,其中包含已被 guard 排除的点 (2,3)。平移后这个伪状态变成 (3,3),违反待证断言。独立区间抽象域也保留这一伪状态;即便区间端点完全精确,仍无法保存 x+y≤4。

从区间与差分约束到和式 guard

整数矩阵:从奇数一元界到六个格点 ​

取相干输入

MZ=(01∞∞30∞11∞01∞∞50).

它表示 −2x≤1,2x≤3,−2y≤1,2y≤5,x−y≤1。普通闭包及紧闭包分别为

CZ=(0172306112016750),TZ=(0020203110003240).

例如 T12=min(6,⌊3/2⌋+⌊5/2⌋)=3,给出 x+y≤3;一元界变为 0≤x≤1,0≤y≤2,此时 x−y≤1 自动满足。全部整数状态是

(0,0),(0,1),(0,2),(1,0),(1,1),(1,2).

在这六点上分别最大化十六个 zj−zi,逐项重现 TZ。这是本例规范性可直接复核的证书,不能用有限枚举替代上一节任意维数的可行性论证与饱和引理。

反例矩阵

Chalf=(0−110)

已经普通闭合,实数解为 x=1/2,但取整检查为 ⌊−1/2⌋+⌊1/2⌋=−1<0,因此整数紧闭包返回 ⊥。若先相加再除二,会错误得到零并漏掉这个矛盾。

规范 join:包含并集的最佳八边形 ​

对非空紧闭合 T,U,定义

(T⊔U)ij=max(Tij,Uij).

由饱和引理,这恰是两个具体集合并上每个允许表达式的上确界。任何包含该并集的八边形,都必须给每个表达式至少这么大的界,所以该矩阵是最佳八边形上近似,而不是任选一个可靠包围盒。

结果仍紧闭合。相干与一元偶数性由最大值保留。对三角式,Tij 与 Uij 分别不超过

max(Tik,Uik)+max(Tkj,Ukj),

故两者最大值也不超过它;加强式用相同论证,将右侧换成两个一元最大值之和的一半。零对角同样保留。因此两个输入先紧闭包以后,join 本身只需 O(n2),无需再次 Floyd。规定 ⊥⊔T=T,覆盖两个输入都为空的情形。

例如一维整数点 {0}、{2} 的紧矩阵分别为

(0000),(0−440).

逐项最大值得 (0040),表示 0≤x≤2,还含整数 1。最佳抽象 join 通常不是具体集合并;未规范化输入又会因隐含界未显化而失去“最佳”结论。[1, §4.1]

任意斜率仍超出表达能力 ​

八边形也不能精确表示整个直线 y=2x。它只有系数为 ±1 的双变量约束及一元约束;在这条无界直线上,每个非零的允许线性表达式都向上无界,因此任何有限的此类界都会误删真实点。任意线性多面体可用两个不等式 y−2x≤0、2x−y≤0 表示该直线,表达能力因此更强。

多面体抽象域从这条斜率为二的关系继续:两条平行分支线段先汇合,再经 guard 截取和仿射赋值消元,最终得到 2y−2≤x≤2y 与 x≤6 的完整安全证书。它允许约束方向随程序关系改变,同时承担投影和凸包带来的约束增长成本。

推论与应用

关系精度对应哪些计算代价 ​

对 n 个程序变量,矩阵有 2n 行列,空间为 O(n2)。普通 Floyd 闭包耗时 O(n3),随后加强扫描全部元素,耗时 O(n2),完整规范化仍为 O(n3)。一条二元 guard 只需先写两个相干位置,写入成本为 O(1),之后通常要重新规范化;不能把写入成本当作整个过滤操作的成本。

单变量平移只影响该变量两个带符号坐标的行列,更新成本为 O(n)。它保持相干、三角不等式和加强关系:位移在三角式中相消,且 δi¯=−δi 使加强式两侧得到相同的位移。因此从强闭合输入出发,本例的平移无需重新做立方成本的闭包。

前面的实数算例完成了同一条验证链:用相干性记录符号配对,用中点论证可行性,用一次加强补全一元界之间的推论,再以和式 guard 与平移保留断言需要的关系。它适合差与和共同出现的数值不变量;选择此域的收益,正是像例子中那样保住 zone 会丢失的斜向边界。

Widening 为什么必须保留未闭合的历史 ​

整数八边形也有无限上升链。使用逐项 widening

(R∇N)ij={Rij,Nij≤Rij,+∞,Nij>Rij.

每项要么保留原界,要么删除,结果覆盖两个输入。相干输入同时删除一对相干位置,但输出无需紧闭合。保存 raw 历史 Rk,另取紧闭包副本 Ck=tc(Rk) 来计算转移、guard 与规范 join,得到可靠候选 Nk+1,最后仅更新

Rk+1=Rk∇Nk+1.

有限个矩阵位置各自最多从其初始有限值变为无穷一次,因此无论新候选如何变化,历史矩阵最终稳定。规范化副本和历史矩阵是两个不同用途的对象;如果把 Ck 回写历史,上面的终止证明就不再成立。空历史按 ⊥∇N=N 初始化,空右候选不要求丢弃任何历史界。

下面给出一条具体的整数反例链,所有矩阵按 (x,−x,y,−y) 排列:

A0=(0011001111021120),Nk=(02k12k2k02k112k02k2k12k0)(k≥1).

A0 表示 x=0,|y|≤1;Nk 表示 |x|,|y|≤k,|x−y|≤1。它们紧闭合,而且 γ(A0)⊆γ(N1)⊆γ(N2)⊆⋯。对同一组候选比较

B0=R0=A0,Bk+1=tc(Bk)∇Nk+1,Rk+1=Rk∇Nk+1.
轮数 k 错误回写一侧的具体绝对界 (|x|,|y|) raw 历史的剩余信息
0 (0,1) x=0,|y|≤1,|x−y|≤1
1 (2,1) |y|≤1,|x−y|≤1
2 (2,3) 仅 |x−y|≤1
3 (4,3) 同上一轮
4 (4,5) 同上一轮

表中绝对界都是集合真正达到的最大值,并非 raw 矩阵必须显式存着的元素。第一轮删去 x 的一元界,但 |y|≤1 与 |x−y|≤1 可重建 |x|≤2。若把该闭包拿作下一次左参数,第二轮保留刚重建的 x 界、删去 y 界,又能推出 |y|≤3。归纳可得 B2r 的绝对界为 (2r,2r+1),B2r+1 为 (2r+2,2r+1);在每轮有限的一侧端点取等并让另一坐标相差一,就达到这些界。因此具体集合严格扩大,永不稳定。

raw 历史则不会恢复已删除的 x 元素,第二轮删除 y 元素后,两方向的绝对界都无穷,只保留相对关系,第三轮开始矩阵不再变化。这是闭包回写能真正导致发散的反例,而不仅是“现有证明不适用”。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页)。其边权约定与本文相反,转置后得到本页公式;一元收紧必须是原界除二向下取整后再乘二。

关系图谱6 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。

类型化关系