CompCert 是一种面向 C编程语言的优化型编译器,其突出特点是通过机器检查的证明,保证主要编译阶段保持程序行为不变。它最初由 Xavier Leroy 领导的团队在法国国家信息与自动化研究所(Inria)开发,是将形式验证应用于面向实际生产的系统软件的重要范例。其正确性论证将所支持的 C 语言的形式模型与目标汇编代码的形式模型联系起来,而非仅依赖测试来确认编译保持了程序的含义。
目标与发展
编译器将程序转换为适合执行的形式,通常还会在转换过程中提高程序的运行效率。错误的转换可能导致原本正确的源程序出现错误行为。当软件的可靠性依赖于源代码层面的验证或大量测试时,这类错误的影响尤其严重:这些保障并不能自动证明生成可执行文件的编译器也是正确的。
CompCert 通过证明其编译流水线的语义保持性来解决这一问题。该项目始于 2005 年,最初重点支持 C 语言的一个较大子集和 PowerPC 后端。此后,项目逐步扩展了语言支持、优化、目标架构和证明基础设施。
其开发将可执行的编译器实现与由 Coq 证明助手(现名 Rocq)检查的证明相结合。CompCert 有力地表明,编译器的形式验证可以超越小型实验语言,扩展到功能丰富的系统编程语言和实际使用的目标处理器。
正确性保证
语义保持性
其核心性质是:在满足正确性定理各项假设的前提下,成功的编译不会引入源程序所不允许的可观察行为。
证明采用操作语义,即对源程序和目标程序如何执行所作的数学描述。这些描述区分了终止、发散以及外部可观察的交互等结果,也标明了哪些执行会遭遇未定义行为。
对于行为有明确定义的源程序,编译后的程序必须遵循该行为。如果源语言允许多种可能的执行,编译可以从允许的行为中作出选择;保持行为并不要求保留源代码层面的每一种选择。
例如,如果一个行为有明确定义的源程序以特定结果和特定的可观察交互序列终止,编译就不能将其改为另一种不被允许的结果或交互序列。实际定理比返回值相等更为一般:它还涉及持续进行和不终止的执行。
这一保证以编译成功为条件。CompCert 可以拒绝某个程序,或在编译过程中报告失败;其正确性定理并不要求所有可能的输入都能生成可执行输出。
未定义行为
未定义行为是这一保证的重要边界。对于越界内存访问或有符号整数溢出等操作,C 语言并未规定通常意义上的执行语义。经过验证的编译器并不会使这类程序变得安全,也不会使其执行变得可预测。
这里需要区分两项责任:
- **程序正确性:**源程序符合其预期规约,并避免相关的未定义行为。
- **编译器正确性:**编译保持源语言语义所规定的行为。
CompCert 主要确立的是后者。仅凭它本身,并不能证明编译后的应用程序不存在缺陷或安全漏洞。
编译器组织结构
CompCert 使用一系列中间语言,而不是直接将 C 转换为汇编。每种语言都将执行中的某些方面显式化,从而使正确性证明易于处理。
其大致流程包括:
- **源代码层面的处理。**对 C 输入进行解析、检查,并转换为内部表示。
- **表达式简化与降级。**将复杂表达式、控制结构和内存操作转换为更简单的形式。
- **机器无关优化。**通过分析和转换改进中间程序。
- **机器相关降级。**使操作适配目标处理器及其调用约定。
- **寄存器分配与代码生成。**将中间变量分配到寄存器或栈位置,并生成目标汇编代码。
代表性的中间语言包括:Clight,一种简化的类 C 语言;Cminor,一种较低层次的命令式语言;以及 RTL,一种围绕控制流图组织的寄存器传送语言。后续的表示逐步将物理寄存器、栈帧和机器指令显式化。
这种组织方式对验证至关重要。开发者不必将整个编译器视为不可分割的单一程序来证明其正确性,而是分别证明各项转换的正确性,再将这些结果组合成整体定理。
证明技术与实现
中间语言之间的模拟
典型编译阶段的正确性通过模拟论证来确立,该论证将转换前后的状态联系起来。源程序的一步执行不必恰好对应目标程序的一步执行:降级可能将一个操作替换为多条指令,而优化则可能完全消除某些操作。
因此,证明需要在执行状态之间建立适当的关系,并说明目标程序的执行始终与源语言语义一致。这些关系可以跟踪值、内存内容、控制位置,以及变量在寄存器或栈槽中的存放位置。
证明所考虑的不只是局部表达式的等价性,还包括函数调用、外部可见的动作、不终止行为,以及各个相继编译阶段中的内存表示方式。
内存与算术模型
CompCert 的内存模型使用已分配的内存块和偏移量来描述内存,并通过权限规定哪些访问有效。这为推理指针、对象生命周期、加载、存储和数据布局变化提供了支持。
内存转换需要格外严谨的证明。例如,将多个源程序对象放入目标程序的同一个栈帧,可能会改变它们的具体表示。证明必须说明,源程序中允许的访问仍然对应于目标程序中恰当的访问。
形式化还涵盖定宽整数运算和浮点运算。相关浮点语义以 IEEE 754浮点运算标准中算术运算的形式化描述为基础,而不是将机器浮点操作视为精确的实数计算。
提取与验证
经过验证的编译器中,很大一部分以 Coq 中的可执行函数编写,再提取为 OCaml 代码。证明检查确立这些定义的性质;代码提取则使其能够作为实用编译器的一部分运行。
对于直接证明复杂搜索过程过于繁重的情况,CompCert 也会采用验证。例如,在寄存器分配中,可以由不受信任的过程提出一个分配方案,再由经过形式验证的验证器检查。验证成功,即可确立该分配方案具备所要求的性质。
这是翻译验证的局部应用,并不要求每次完整编译都获得一份新构造的独立证明。
语言支持与目标架构
CompCert 支持 C 语言中相当大的一部分,适用于许多嵌入式程序和系统程序。其文档所规定的语言明确了接受哪些特性、如何确定由实现定义的选择,以及哪些地方存在扩展或限制。因此,应根据相应的 CompCert 版本评估兼容性,而不能仅凭笼统的“支持 C 语言”这一说法作出推断。
CompCert 已为 PowerPC、Arm、AArch64、x86 和 RISC-V 等处理器家族开发了后端。可用字长、平台约定和操作系统接口因目标和版本而异。每个后端都必须将自身的转换与相应的指令集架构及应用二进制接口衔接起来。
经过验证的主要语言和执行模型是顺序的。不应将核心定理解读为适用于任意共享内存并发计算程序、编译器并发扩展或包含不受限制的内联汇编的程序的一般性正确性结论。
优化与性能
CompCert 执行常量传播、公共子表达式消除、死代码消除、指令选择和寄存器分配等优化。其意义不在于避免优化,而在于这些转换都附有经过机器检查的正确性论证。
不过,验证确实会影响工程选择。一项转换必须能够在形式框架中表达,并有可维护的证明作为支撑。复杂转换所需的工作量,可能远远超过仅实现其可执行代码所需的工作量。
与采用激进优化的主流编译器相比,CompCert 提供的优化种类通常较少。它相对于其他编译器的性能取决于工作负载、目标架构、版本和所选选项。形式正确性并不能证明生成的代码速度最快、体积最小或达到最优。
信任边界与局限
经过验证的编译流水线,并不等同于经过完整验证的计算系统。这种保障取决于定理的精确适用范围,以及该范围之外的组件。
重要边界包括:
- **输入处理。**预处理和部分源代码处理基础设施不在主要语义保持性证明的范围内。某些前端组件的验证状况随版本演进而发生了变化。
- **汇编与链接。**生成汇编代码本身,并不能证明外部汇编器和链接器会生成预期的可执行文件。
- **执行环境。**外部库、操作系统和硬件必须满足对其行为建模时所采用的假设。
- **证明与构建基础设施。**可信度依赖于证明助手的检查内核,以及用于提取、编译和执行该编译器的机制。
- **规约的恰当性。**经过机器检查的证明确立的是关于形式定义的定理。这些定义必须准确表达预期的语言行为和机器行为。
主要语义保持性定理也不会自动保持执行时间、功耗或其他物理层面可观察的特征。尤其是,源代码层面的功能正确性本身,并不能证明程序在编译后能够抵御侧信道攻击。
应用与影响
CompCert 适用于高保障软件开发,这类开发需要将对源代码的信心延伸到生成的代码。只要程序和工具链仍满足适用的假设,它就能通过提供具有形式化依据的编译阶段,对源代码层面的验证形成补充。
其中间语言和语义也被用于程序逻辑、经验证的静态分析、链接和编译器转换等研究。尤其是 Clight,它被一些验证框架用作源语言,这些框架对 C 程序进行推理,并将所得结果与编译过程联系起来。
CompCert 展示了经验证工具链中一项核心的责任划分:应用程序的证明确立程序的性质,编译器的证明在翻译过程中保持相关语义,而外围库、二进制处理工具和执行平台则需要各自独立的论证。