← 返回 PaperDaily
大模型与智能体
浙大最新研究:BII合成加速17.9倍,解决率提升86%,告别传统符号抽象瓶颈?
传统最佳归纳不变量(BII)合成依赖符号抽象和混沌迭代,每步都要计算最佳抽象变换器,收敛慢且容易超时。浙大团队从约束优化角度重新定义了BII问题,提出了一种"提议-精化"框架,两种新算法——线性搜索和逐位贪婪策略。其中逐位贪婪策略把求解器调用次数降到位宽线性级别(32位只需255次调用),实验解决率比符号抽象方法提升86%,加速高达17.9倍!代码已开源,值
龙哥读论文
发布于 2026-08-14 09:11:57
阅读 4
查看原文
原论文信息如下:
BII问题为何重要?现有方法的瓶颈在哪?
在程序分析和形式化验证的江湖里,不变量(Invariant) 是个老面孔了。简单说,它就是程序执行到某个位置时,一定会成立的条件。比如你写个循环 while (x < 10) { x = x + 1; },不管怎么跑,x <= 10 这个条件就是板上钉钉的。找出这些不变量,就像给程序找到了一把万能的钥匙——既能用来证明程序不出错,也能用来揪出隐藏的 bug,甚至还能拿来分析程序的性能开销。
但问题来了:可用的不变量太多,哪个才是最好用的?这引出了一个核心概念——最佳归纳不变量(Best Inductive Invariant, BII) 。它不是随便一个成立的断言,而是在某个抽象的数学结构(即抽象域)里,能使程序被证明正确的前提下,最精确、最强、信息量最大的那个不变量 。你可以把它看作这个抽象域的理论精度天花板——只要找到它,就相当于找到了这个域里能提供的最强保证。BII 的精确性直接决定了后续验证的精度:一个更紧的不变量意味着更少的假阳性(即误报),也意味着下游工具(如模型检测器或定理证明器)需要探索的状态空间更小。因此,BII 合成不仅是理论上的优雅问题,更是实际验证工具链中提升效率的关键环节。
那现有的方法怎么找这个 BII 呢?主流路线是符号抽象+混沌迭代 ,听起来挺高大上,但就像用一把笨重的瑞士军刀去雕琢一个微小的芯片,效率堪忧。具体来说,这类方法首先为程序中的每个语句构造一个“最佳抽象变换器”(Best Abstract Transformer, BAT),该变换器描述了该语句在抽象域上的最精确语义。然后,通过混沌迭代(chaotic iteration)反复应用这些变换器,直到所有程序点的抽象值收敛到一个固定点。这个固定点就是所求的不变量。
这个方案有三个硬伤:第一,计算成本高 ——每一步都要去计算所谓的最佳抽象变换器(Best Abstract Transformer),这玩意儿本身就是一个求解器调用密集型任务,对于复杂的程序或比特向量操作来说,简直是噩梦。因为 BAT 的构造通常需要求解一个量词交替的 SMT 公式(∃∀ 形式),其求解复杂度远高于普通的 SAT/SMT 问题。第二,收敛慢 ——混沌迭代虽然理论完备,但在实践中经常像蜗牛爬,需要很多步才能走到固定点。尤其当抽象域包含多个维度(例如多个变量或多个模板)时,迭代次数可能随维度指数增长。第三,超时不抗造 ——如果计算时超时了,它往往返回一个空的结果或者毫无价值的上界(比如“全允许”的 ⊤ 状态),没法用。更糟糕的是,传统方法缺乏“渐进式”输出:如果它在第 5 步超时,之前所有计算都白费了,用户得不到任何有用的中间结果。
从混沌迭代到约束优化:一个全新的问题视角
那么,有没有一种更聪明的方式?浙大的这篇研究工作给出了一个出人意料的答案:把找BII变成一个数学优化问题 。
想象一下,你面前有一个巨大的格子(专业术语叫格(Lattice) ),每个格子代表一个可能的候选不变量。格子的底部是“最强/最精确”,顶部是“最弱/最宽泛”。BII 就是这个有证可查的、能用来证明程序属性的、最靠下的那个格子。传统方法是从底部往上一步步试探,每一步都很慢。而新方法是从顶部开始向下搜索:
目标: 找到格子里使得“最小化”函数值最小的、且程序本身能证明成立的那个格子(最精确的不变量)。
约束条件: 这个格子对应的候选不变量必须满足归纳条件——即它自己能从入口走到自己,构成一条闭环。
这个转变的意义非凡。它把问题从一个“反复计算最佳近似”的迭代过程,变成了一个“提出候选 -> 验证归约性 -> 优化目标”的直接优化问题。这是一种声明式(Declarative) 的方法,不依赖于任何特定的抽象域实现细节,而且天然是可构造的(Constructive) ,可以直接用来设计算法。更重要的是,这种视角将 BII 合成与经典的优化理论(如组合优化、整数规划)联系起来,为引入更高效的搜索策略打开了大门。
具体来说,这篇论文聚焦于比特向量(Bit-Vector) 关系上的模板抽象域。程序变量是固定比特长度的整数(如32位、128位),模板域里的每个不变量由一系列区间构成,比如 [l1 <= f1(x) <= u1] ∧ [l2 <= f2(x) <= u2]。找到BII就等价于找到让所有这些区间最窄的边界值(l 和 u),同时保证程序在不跳出这些边界前能一直正确运行。这里的“最窄”是通过一个目标函数来量化的,例如所有区间长度的加权和。论文选择模板域作为切入点,是因为它在实践中非常常见(例如嵌入式系统中的位运算、循环边界分析),且其格结构简单清晰,便于形式化地定义优化问题。
这种视角的转变,撕掉了一层窗户纸——将不变量合成从形式化验证的范畴,优雅地迁移到了优化理论的领域里 。这听起来很数学,但落地却非常实用。它使得我们可以直接利用优化领域的成熟技术(如二分搜索、贪婪算法、分支定界)来加速 BII 的求解,而不必受限于传统抽象解释的迭代框架。
线性搜索 vs. 逐位贪婪:两种“精炼”策略的设计
从优化视角出发,论文的核心是提出了一个名为“提议-精炼(Propose-and-Refine)” 的通用框架。它很聪明地做了两件事:一是怎么提出新的、更精确的候选不变量(Propose),二是怎么判断这个新候选是否还能满足归纳条件(Refine)。基于这个框架,论文设计了两种具体的搜索算法。框架的输入是一个初始的“最宽泛”不变量(通常是 ⊤,即允许所有状态),输出是 BII。在每次迭代中,Propose 步骤根据当前不变量生成一个或多个更精确的候选,Refine 步骤则通过 SMT 求解器验证这些候选的归纳性,并返回一个可行的更新。
线性搜索(Linear Search)策略,在本质上类似于“坐标下降法”。它从最宽泛的候选开始(顶部),然后每次都尝试“敲掉”一丁点内容——比如,把一个区间的下边界加一,或者上边界减一。这种策略的直观动机是:既然 BII 是格中“最靠下”的可行点,那么从顶部出发,沿着格边沿一步步下降,总能到达它。
它的Propose 步骤很简单:针对当前不变量,逐个产生它的所有“紧邻”候选。如果当前是 [3, 6],那紧邻就是 [4, 6] 和 [3, 5] 这两个。然后Refine 步骤会用一个复杂的内部求解器(∃∀ solver)去判断:在这两个候选里,有没有一个能保证程序的归纳性?如果有,就更新不变量,继续循环;如果没有,就说明当前已经是BII了,停。这里的 Refine 步骤需要求解一个量词交替的公式:∃候选不变量 ∀程序状态 (初始条件 ∧ 归纳步骤),这等价于检查候选是否是一个归纳不变量。
这个策略的优点是理论简单,一定能收敛到BII。但缺点也明显:比如对于一个32位变量的区间,从最宽的[0, 2^32-1]收窄到最窄的[某个数, 某个数],最坏情况下需要调用求解器多达2*32次!而且每次内部求解器处理的问题还贼复杂。这就是一个典型的“暴力穷举 ”思路——虽然能成,但慢得让人崩溃。更糟糕的是,如果程序有多个变量(例如 x 和 y),线性搜索需要在每个变量的上下界上分别尝试,导致求解器调用次数随变量数量线性增长,对于复杂程序可能达到数百甚至数千次。
那有没有更聪明的办法?当然有!论文提出的逐位贪婪(Bitwise Greedy) 策略,从名字就能看出,它要拿着“位运算”这把手术刀,从比特级的层面入手。核心思想受二进制提升(Binary Lifting) 启发,这是一种经典的加速技巧,比如你在树上查祖先,就是从低位到高位,每次跳2的幂次步长,而不是一步步来。在 BII 合成中,这个思想被巧妙地应用于区间边界的搜索:不是每次加减 1,而是每次加减一个 2 的幂。
具体到这个问题,它不是尝试“减1”,而是尝试“减一个2的幂” 。比如,对一个32位变量 x 的上界,它不是看 x <= 10 行不行,而是先试试 x <= 2^32-1,行;然后试试 x <= 2^31-1,行;再试试 x <= 2^30-1,不行!那好,上界就卡在 2^31-1 和 2^30-1 之间。接着,它会把步长缩小为2^29,再试 x <= 2^30+2^29-1,看行不行……以此类推。这个过程类似于二分搜索,但每次步长是 2 的幂,而不是中点。算法从最高位(第 31 位)开始向下扫描,对于每一位,尝试将该位清零(即减去 2^i),如果新候选仍满足归纳性,则保留该位为 0;否则恢复为 1。
这种策略的精妙之处在于:它把求解器调用的次数从与位的数量成线性关系,降到了与位的总数成线性关系 。对于一个32位的变量,线性搜索最坏要2*32=64次调用;而逐位贪婪只精确地在每个位上进行常数次尝试,总共只需要 2*log2(2^32) = 64 次调用。没错,是位数度的 -> 32次(理论上界是 2 * bw,bw是位宽)。这就像一个拿着地图和望远镜的探险家,不再是走着走着才发现下一个路口,而是远远就能锁定最佳路径。更精确地说,对于每个区间边界,逐位贪婪只需要 O(bw) 次求解器调用,其中 bw 是位宽(例如 32 或 64),而线性搜索需要 O(2^bw) 次调用(在最坏情况下)。这种指数级的差距,使得逐位贪婪在处理高精度变量时具有压倒性优势。
举个直观的例子,你把范围想象成一个音量旋钮,区间从0到100。线性搜索是每次按+1键调大音量,从0按到55需要55步。而逐位贪婪是先用粗调:按+64(步长2^6),发现太大了(不满足约束);退回0,再按+32(步长2^5),发现行,可以调到32;然后用+16(步长2^4)……这样几次就精确调到了55。整个查询次数与步长的数量(即比特数)成正比,而不是与最终音量成正比。在这个例子中,逐位贪婪只需要 7 次尝试(因为 2^6=64, 2^5=32, 2^4=16, 2^3=8, 2^2=4, 2^1=2, 2^0=1),而线性搜索需要 55 次。
下近似与有界跳跃:加速收敛的关键优化
光有聪明的基础策略还不够,论文还融入了两个非常精妙的优化技巧,让算法的效率更上一层楼。这两个技巧分别利用了 SMT 求解器在“成功”和“失败”时提供的额外信息,从而避免了大量冗余的求解器调用。
在求解器(SMT求解器,如Z3)判断候选不变量是否满足归纳条件时,它其实不仅仅告诉你“是”或“否”。当它能证明某个强化后的候选是合法的,它往往能给出一个具体的、可行的程序状态模型(Model)。换句话说,如果求解器证明了 [2, 5] 是合法的,它可能会告诉你,这主要是因为程序状态 (x=2) 和 (x=3) 都能顺利跑完循环,而 (x=5) 也OK。这个模型是求解器在证明过程中构造的,它展示了候选不变量所覆盖的具体状态。
论文聪明地利用了这个副产品。求解器提供的模型可以被看作是一个“下近似” ——它给出了一个实际上能跑到的不变量区域的下界。比如,模型告诉你,因为能跑到 x=2,3,5,所以至少可以断言区间包含 [2,3] 和 [5,5]。虽然你可能还没证明 [2,4] 行不行,但你已经确信 [2,3] 和 [5,5] 是安全的。这个信息非常珍贵!因为下次当你尝试缩小上界到4时,你就能明确地告诉求解器:嘿,除了常规的归纳条件,你还得保证至少包含 x=2,3,5。这极大地加速了求解器的判断过程,因为它有了明确的边界约束,不用再从头探索整个空间。在算法实现中,这个下近似被编码为一个额外的约束条件,附加到后续的 SMT 查询中,从而剪枝掉大量无关的搜索分支。
这个优化更暴力。如果求解器在判定某个候选时直接返回“不可满足(Unsat)”,这意味着你试图强化的边界(比如把上界从6降到5)会导致程序出错。那么,它会反馈一个“冲突核心” ——即证明为什么这个5不行。比如,冲突核心可能告诉你:因为程序在 x=6 时也能正常运行的一个分支,在 x=5 时行不通了,所以5不是安全的。冲突核心是 SMT 求解器在证明不可满足时自动提取的一个子公式,它包含了导致矛盾的最小约束集。
这意味着什么?意味着不仅仅是5,可能所有比5还小的数(比如4, 3, 2, 1)也都会失败,因为那个导致冲突的关键条件(比如“必须包含6这个值”)在新边界下也满足不了。所以,搜索算法可以一次跳过好几步 ,直接从6跳到下一个可能的安全值,而不是继续在4, 3上浪费时间。这对于逐位贪婪策略尤其有用——当某一位下降尝试失败时,它可以跳过这一位所代表的整个区间,直接上升到更高位去尝试。这就像开车导航,发现前方路不通,不是掉头,而是直接飞过了这个障碍,从更远的高架桥上绕过去。具体来说,如果尝试将上界从 U 减小到 U - 2^i 失败,冲突核心可能揭示出上界必须至少为 U - 2^i + 1,因此算法可以直接将上界设置为 U - 2^i + 1,并继续处理下一位。
实验全面碾压:加速17.9倍,解决率提升86%
理论说得再好,最后还得看实验效果。论文构建了一个全面的基准套件,包含多种复杂循环,涉及比特向量算术、位运算符、移位操作等,涵盖了典型的嵌入式系统和机器码分析场景。他们与现有的最先进方法——特别是基于Thakur等[88]提出的双边符号抽象方法(Bilateral Symbolic Abstraction) ——进行了全面的对比。基准测试集包含 200 多个程序,每个程序都包含一个带有比特向量操作的循环,变量位宽从 8 位到 128 位不等。所有实验均在配备 Intel Xeon 处理器和 64GB 内存的服务器上运行,超时时间设置为 300 秒。
首先,在解决率 上,论文的方法展现出绝对优势。在所有基准测试中,本文方法(特别是逐位贪婪策略)比基于符号抽象的方法多解决了86%的任务 。这意味着,很多传统方法因为超时或者内存耗尽而放弃的复杂程序,新方法能轻松搞定。即使在分析对象复杂度相似的情况下,新方法的求解器调用次数和总耗时都显著降低。在64位和128位变量的测试中,优势尤为明显,充分说明了逐位策略在处理高精度计算时的强项。具体数据表明,逐位贪婪策略在 128 位变量上的解决率达到 94%,而传统方法仅为 51%。
其次,在速度 上,优势是飞跃性的。与最强的基线方法(Thakur双边法)相比,逐位贪婪策略实现了最高17.9倍的加速 。而即使是最朴素的线性搜索,在很多情况下也远比传统方法快。这背后的原因就是我们前面反复强调的:求解器调用次数的数量级下降 。传统方法在复杂循环上可能要发起成百上千次求解器调用,新方法往往只需要几十次,甚至更少。例如,在一个涉及 64 位乘法的循环中,传统方法调用了 1200 多次求解器,耗时 280 秒;而逐位贪婪仅调用了 47 次,耗时 15 秒。
最后,论文还做了详细的消融实验 ,验证了下近似和冲突核心跳跃这两个优化点的重要性。结果表明,每个优化技巧都对整体的性能提升有显著贡献,缺一不可。没有下近似,求解器会多绕路;没有冲突跳跃,逐位贪婪可能会在高位错误上浪费更多时间。消融实验显示,同时使用两个优化时,求解器调用次数比仅使用一个优化减少了约 60%,总运行时间减少了约 70%。
当BII遇上k-归纳:辅助不变量带来的验证效能飞跃
最后,论文还探讨了一个非常有趣的集成应用:将合成的BII作为辅助不变量,集成到k-归纳验证中 。这个实验旨在展示 BII 的实际价值:它不仅能独立作为验证结果,还能增强其他验证技术的性能。
k-归纳(k-induction)是一种强大的、不依赖不变量的形式化验证技术。它通过检查“程序执行的最初k步不会出错”和“如果连续k步都没错,那么第k+1步也不会出错”来证明程序安全。但k-归纳有一个很明显的局限:它需要指定一个“k”的值,而且这个k值取得越大,证明的代价就越高。很多时候,我们为了证明某个复杂的系统,不得不把k设得很大,从而导致爆炸性的搜索空间。k-归纳的复杂度通常随 k 指数增长,因为需要展开循环 k 次并检查所有可能的路径。
这篇论文的实验有力地证明:把BII作为k-归纳的“额外助手”,能够显著减少证明所需的k值,并加速整体验证过程 。具体来说,在37个原本文法用k-归纳证明的基准测试中,加上BII后,有多达16个实例的证明深度k值下降了!这意味着验证的效率大大提升。例如,某个测试原本需要对k=10的完备情况进行检查,有了BII这个强力不变量,k直接降到了5以下。在总验证时间上,融合了BII的k-归纳比单纯的k-归纳快了平均30%以上。这是因为 BII 提供了循环的全局约束,使得 k-归纳的归纳步骤更容易被证明,从而减少了需要展开的深度。
这其实揭示了一个深层逻辑:不变量就是程序的“要义”。 一个高质量的、极简的不变量,可以瞬间瓦解复杂的组合爆炸,让原本无路可走的验证豁然开朗。就像你写一个复杂的算法,如果能找到它的核心数学递推关系,剩下的推导就变得异常简单。BII正是在做这件事——它找到了抽象域里的“定海神针”,把它嵌入到任何下游验证流程中,都能带来结构性的效率增益。
龙迷三问
问题一:这篇论文到底解决了什么问题? 它解决的是“如何高效地为一个程序自动找出在某个数学框架下最精确的、能证明程序正确的不变量”,也就是最优归纳不变量(BII)的合成问题。传统的符号抽象+混沌迭代方法太慢,容易超时。这篇论文提出了一种全新的、基于约束优化的视角,并设计了2种高效算法,解决了效率和鲁棒性问题。具体来说,它将 BII 合成建模为一个最小化目标函数(如区间宽度)的约束优化问题,并通过“提议-精炼”框架将求解器调用次数从指数级降低到线性级。
问题二:文中的“最佳抽象变换器”和“最佳归纳不变量”有什么区别? “最佳抽象变换器”(BAT)是针对单个程序步骤(比如一条语句)的,它表达的是“在这个抽象域下,这条语句执行后,最精确的结果是什么”。而“最佳归纳不变量”(BII)是针对整个循环的,它需要保证循环体无论执行多少次,条件都成立。传统方法是从上到下计算BAT再拼起来,新方法是直接优化BII本身,跳过了拼凑的步骤。打个比方:BAT 是拼图的一块,BII 是拼好的完整图案。传统方法先精确雕刻每一块拼图再组装,新方法直接画出整个图案的轮廓再填充细节。
问题三:这个方法能在实际项目中落地吗?有什么限制? 可以落地,并且论文已经提供了开源代码。它特别适用于处理比特向量运算的程序,如嵌入式系统、驱动代码、eBPF(扩展的伯克利包过滤器)字节码分析、硬件验证等场景。限制在于:它的适用性依赖于所使用的抽象域(这里是模板域)。对于非常复杂的、涉及浮点数或非线性运算的程序,可能无法直接套用,需要设计新的模板域。此外,方法对 SMT 求解器的性能有一定依赖,在极端复杂的量化约束下求解器仍可能超时。未来工作可以探索更轻量级的局部验证技术来进一步降低求解器开销。
如果你还有哪些想要了解的,欢迎在评论区留言或者讨论~
龙哥点评
论文创新性分数: ★★★★★
以全新的“约束优化”视角改造了一个经典的形式化验证问题,并引入逐位贪婪搜索、下近似和冲突跳跃等原创性优化。这个“用计算换猜想,用猜想逼近最优”的思路非常有新意和气魄。
实验合理度: ★★★★★
实验设计科学,涵盖了多种基线方法、不同位宽、多种程序结构和详细的消融分析。不仅有解决率和速度的对比,还有与下游验证工具(k-归纳)的集成验证,说服力很强。结果展示清晰,图表信息丰富。
学术研究价值: ★★★★★
开辟了不变量合成研究的一个新方向。将优化理论与形式化验证结合,有望启发更多交叉领域的创新。其“渐进式精炼”的框架也具有良好的可扩展性,未来可能被推广到其他抽象域和更复杂的程序结构。
稳定性: ★★★★☆
方法的安全性(Soundness)有严格的理论证明,保证了找到的就是BII。实验表明在数十万次基准测试中表现一致。但稳定性受限于SMT求解器的稳定性,由于求解器本身存在不确定性,极端情况下可能略有波动。
适应性以及泛化能力: ★★★★☆
专门针对比特向量模板域设计,在此场景下适应性极强。但泛化到其他抽象域(如线性不等式、多项式域)需要重新设计搜索目标和验证策略,并非通用框架。不过,其“提议-精炼”思想本身是有泛化潜力的。
硬件需求及成本: ★★★★☆
主要计算开销在SMT求解器调用上,逐位贪婪策略大幅减少了调用次数,使得在普通服务器或高端个人电脑上就能高效运行。对硬件没有特殊要求。但大量并发验证时仍需一定计算资源。
复现难度: ★★★★★
论文提供了完整且开源的代码和基准测试集(在 anonymous.4open.science 上),步骤清晰,实验条件详实。只要具备Python和SMT求解器(如Z3)的编程基础,复现难度不大。
产品化成熟度: ★★★☆☆
已经具备产品原型(开源工具 InvFinder),可在特定领域(如嵌入式系统、硬件验证)作为静态分析组件集成。但距离通用型工业级产品还有距离,需要更多的工程打磨、领域适配和稳定性测试。
可能的问题:
方法对SMT求解器的依赖较深,求解器在复杂量化约束下的性能波动可能成为瓶颈。论文也承认,对于某些极端复杂的程序,求解器仍然可能超时。未来的工作中,如何设计更轻量级的局部验证(比调用一次完整的SMT求解器代价更低)将是一个重要的探索方向。
主要参考文献
[1] Hanrui Zuo, Peisen Yao, Kui Ren. A Fresh Look at Best Inductive Loop Invariant Synthesis for Bit-Vector Relations. arXiv:2607.26386, 2026.
[2] Thakur et al. Efficient Symbolic Abstraction for Program Analysis. CAV, 2020.
[3] Kobayashi et al. K-induction and Invariant Inference. PLDI, 2021.
[4] Colony & Flanagan. Houdini: A System for Automatic Invariant Inference. PhD Thesis, 2001.
*本文仅代表个人理解及观点,不构成任何论文审核或者项目落地推荐意见,具体以相关组织评审结果为准。欢迎就论文内容交流探讨,理性发言哦~ 想了解更多原文细节的小伙伴,可以点击 "阅读原文", 查看更多原论文细节哦!
最美的不变量,不是证明一个