← 返回列表

G.O.S.S.I.P 阅读推荐 2026-10-20 PV-BENCH

单站 安全研究GoSSIP 发布 Tue, 20 Oct 2026 20:40:00 +0800 入库 2026-11-18T08:00:03

QCP团队 2026-10-20 20:40 上海

让我们来教AI怎么做程序验证吧!

AI 正在让程序编写和修改变得更加高效,但生成的代码是否真正满足需求,仍然需要可靠的检查。测试能够发现错误,形式化验证则进一步通过精确的规约和数学证明,论证程序对所有满足前置条件的输入都能满足要求。

让 AI 自动完成这样的验证,仍面临不小的困难。规约如何准确表达需求、循环不变式如何选取、算法与内存操作如何一同证明,都依赖专业经验。高质量训练数据的不足是其中一项制约:现有公开代码很多,配有完整规约、标注和证明的验证实例却相对稀缺。

完整实例能够具体展示从算法概念到规约和证明的过程。以排序为例,“结果有序”只是功能要求的一部分,规约还必须保证原有元素及其出现次数不变。对于采用不同数据结构或加入性能优化的 C 程序,还要考虑如何描述内存、如何建立数学对象与具体存储之间的对应,以及如何组织证明。这些具体的设计选择和证明方法,正是模型需要学习、研究者希望复用的经验。

为此,上海算法创新研究院QCP(Qualified C Programming Verifier,C语言程序验证工具) 团队(网址:https://www.qua.codes)于近日发布了程序验证基准 PV-BENCH,收录 233 个 C 程序实例。团队将积累的规约设计与证明经验融入 AI 智能体的工作流程,在专家指导和审核下,通过智能体自动执行或人机协作,使用 QCP 完成了这些程序的规约编写和验证。

PV-BENCH 将程序、规约、标注和证明一并发布,既提供可以研究和复用的验证实例,也为后续的全自动程序验证研究提供评测依据,支持探索效率更高、成本更低的自动验证方法。其突出特点是纳入较多具有实际编程复杂度的C 程序,并重点验证程序的功能正确性,而不止是内存安全性。与部分只包含数组基本操作、算术运算,或简化、略去关键实现细节的已有数据集不同,PV-BENCH 还覆盖实际编程中常用的高效、紧凑实现方式。

本次发布的 PV-BENCH 版本主要来自两部分:

程序涉及排序、贪心、动态规划、图算法、数论和计算几何等领域。同一算法也保留了不同实现,用于考察规约与证明如何适应具体的控制流程和数据布局:

每个实例均配有题目描述、固定的 C 源码、经专家审核的参考规约,以及参考标注和完整的验证材料。QCP 自动处理一部分验证条件,其余由补充的 Rocq 证明完成。

根据基准数据统计,233 个实例共包含 12,599 行 C 代码。结合参考规约与标注,QCP 共生成 16,724 项验证条件,其中 4,638 项需要进一步完成证明。

QCP 是基于定理证明技术的 C 程序验证工具,支持 Rocq 和 Lean 两种后端。AI 可以与 QCP 交互配合,完成 C 程序的规约编写与验证。

PV-BENCH 设置三项独立任务,分别考察验证过程中的关键能力:

三项任务独立评测,所需的前序材料均采用参考版本。例如,证明补全直接使用参考规约与标注,使规约或标注生成中的错误不会传递到证明任务,便于判断困难究竟出在哪个环节。

评测不仅检查生成的材料能否通过验证工具,还要求生成的规约与参考规约表达相同的要求,避免通过降低要求来获得“验证成功”。

这些任务要求证明程序的功能正确性,而不止是内存安全性。 以下三个例子展示不同程序的验证重点。

同一张图可以存为一维邻接矩阵、二维邻接矩阵,也可以存为链式邻接表。下面对照链式邻接表和二维邻接矩阵两版 DFS。两者都用 vertex 指定搜索起点,用 visited 数组记录访问结果。

1.1. 链式邻接表。adjacency[u] 指向顶点 u 的邻居链表,每个节点保存一个邻居编号和指向下一节点的指针。

void dfs_adjacency_list(struct list **adjacency, int vertex_count,
                        int *visited, int vertex);

1.2. 二维邻接矩阵。matrix[u][v] 为 1 表示从 u 到 v 有边,为 0 表示无边。

void dfs_adjacency_matrix_2Darray(int **matrix, int vertex_count,
                                  int *visited, int vertex);

两个实现的共同点是都需要验证DFS能够遍历每一个从起点出发可达的节点。但是两者需要基于不同的图的存储方式完成证明细节:前者使用了邻接表,后者使用了邻接矩阵。

PV-BENCH 从公开代码库中收录了动态向量(vector)的一种定义与实现,下面以其中的整数向量为例:

struct veci_t {
    int    size;
    int    cap;
    int*   ptr;
};
typedef struct veci_t veci;

size 是已经存入的元素个数,cap 是缓冲区能容纳的元素个数,ptr 指向缓冲区。只有前 size 个位置属于当前向量的内容,其余位置是预留空间。

动态向量(vector)中追加元素函数 veci_push(v, e) 的声明如下:

void   veci_push   (veci* v, int e);
这个函数的实现中会在向量末尾加入 e;如果缓冲区已满,则先扩容。例如,下面图中把 50 追加到 [10, 20, 30, 40] 后得到 [10, 20, 30, 40, 50]。空间充足时,缓冲区地址和容量保持不变;空间已满时,需要扩容,缓冲区地址也可能改变。无论走哪条执行路径,元素顺序和内容都必须符合追加操作的要求。

不过在这个C函数的规约中,这些底层实现细节会被隐藏起来,整个规约很简明:veci_push(v, e) 会完整保留原有元素,并且只在末尾追加一个 e。

这个例子说明,一次简单的“追加元素”操作,背后可能包含扩容、内存迁移和结构体字段更新。验证需要证明这些操作共同实现了序列末尾追加的效果,并保持长度、容量与缓冲区内容一致,但是最后的规约是一个简单的功能描述,并不暴露具体底层存储的细节。在程序验证的过程中,底层存储的细节会被隐藏在证明中,但是这个函数的对外承诺会被简洁地封装起来。

Codeforces 1569D Inconvenient Pairs 是一道编程题目:给定若干贯穿城市的横街、竖街,以及街道上的人。若两人之间沿街道行走的最短距离,严格大于两点的曼哈顿距离,就称他们构成一个“坏的点对”。任务是统计这样的无序点对,每对只计一次。

例如,下图中灰色实线表示的是仅有的两条横街和两条竖街。横街位于 y = 0 和 y = 4,两个人分别站在竖街上的 (0, 1) 和 (2, 2)。他们的曼哈顿距离是 3,但必须先走到横街才能转向,最短路程为 5,因此构成坏点对。

这个例子说明,程序验证不仅要论证程序的实现将计算出何种结果,还要论证这种计算方法背后的数学原理。

总结

PV-BENCH 将过去形式化专家在规约设计和程序验证中的经验在AI的辅助下整理为公开、可检查的参考材料,并通过规约生成、程序标注和证明补全三项独立任务,帮助研究者分析 AI 在自动验证中的能力与不足。我们希望这批实例能够支持后续模型与方法的研究,成为检验进展的共同依据,推动更高效、低成本的全自动程序验证。

项目公开地址:

数据集(Hugging Face):https://huggingface.co/datasets/PV-SJTU/PV-Bench

代码仓库(GitHub):https://github.com/QinxiangCao/PV-bench

QCP官网与下载:

原文链接:https://mp.weixin.qq.com/s?__biz=Mzg5ODUxMzg0Ng==&mid=2247502317&idx=1&sn=76120b0eed3508d2e25c33e817f7b1a7