ACM通信gydF4y2Ba

研究突出了gydF4y2Ba

一个现实编译器的形式验证gydF4y2Ba

由Xavier勒罗伊gydF4y2Ba
ACM通信，2009年7月，第52卷第7期，107-115页gydF4y2Ba
10.1145/1538788.1538814gydF4y2Ba
评论gydF4y2Ba

本文报道了CompCert的开发和形式化验证(语义保存的证明)，它是一个从Clight (C编程语言的一个大子集)到PowerPC汇编代码的编译器，使用Coq证明助手对编译器进行编程并证明其正确性。这样一个经过验证的编译器在关键软件及其正式验证的上下文中是有用的:编译器的验证保证了在源代码上证明的安全属性也适用于可执行的编译代码。gydF4y2Ba

回到顶部gydF4y2Ba

1.简介gydF4y2Ba

你能信任你的编译器吗?编译器通常被认为在语义上是透明的:编译后的代码应该按照源程序的语义所规定的方式运行。然而，编译器，特别是优化编译器是执行复杂符号转换的复杂程序。尽管进行了密集的测试，编译器中的bug还是会发生，导致编译器在编译时崩溃，或者更糟，为正确的源程序无声地生成错误的可执行文件。gydF4y2Ba

对于只有通过测试验证的低保证软件，编译器bug的影响很低:被测试的是编译器产生的可执行代码;严格的测试应该暴露编译器引入的错误以及源程序中已经存在的错误。但是要注意，编译器引入的bug是非常难以发现和追踪的。对于安全关键、高保证的软件来说，情况发生了巨大的变化。在这里，通过测试进行验证达到了它的极限，需要用形式化的方法(如模型检查、静态分析和程序证明)来补充甚至取代它。几乎所有情况下，这些正式的验证工具都应用于程序的源代码。编译器中用于将这种经过正式验证的源代码转换为可执行文件的bug可能会使使用正式方法所获得的所有保证失效。将来，当形式化方法经常应用于源程序时，编译器可能会成为从规范到可执行程序这一链中的薄弱环节。注重安全的软件行业意识到这些问题，并使用各种技术来缓解这些问题，例如在关闭所有编译器优化后，对生成的程序集代码进行手动代码检查。这些技术并不能完全解决问题，而且在开发时间和程序性能方面代价高昂。gydF4y2Ba

一个明显更好的方法是对编译器本身应用形式化方法，以确保它保留源程序的语义。在过去的5年里，我们一直致力于开发一种gydF4y2Ba现实的,验证gydF4y2Ba编译器称为CompCert。通过gydF4y2Ba验证gydF4y2Ba，我们指的是带有机器检查的语义保存属性证明的编译器:生成的机器代码按照源程序的语义所规定的行为。通过gydF4y2Ba现实的gydF4y2Ba，我们指的是可以在关键软件的生产环境中实际使用的编译器。换句话说，它编译一种用于关键嵌入式软件的语言:既不是Java，也不是ML，也不是汇编代码，而是C语言的一个大子集。它为嵌入式系统中常用的处理器编写代码:我们选择PowerPC是因为它在航空电子设备中很流行。最后，编译器必须生成足够高效和足够紧凑的代码，以满足关键嵌入式系统的需求。这意味着多通道编译器具有良好的寄存器分配和一些基本的优化。gydF4y2Ba

证明编译器的正确性绝不是什么新思想:第一个这样的证明发表于1967年gydF4y2Ba^16gydF4y2Ba(用于汇编算术表达式到堆栈机器码)，并在1972年进行了机械验证。gydF4y2Ba^17gydF4y2Ba从那时起，进行了许多其他的证明，从针对玩具语言的单遍编译器到复杂的代码优化。gydF4y2Ba^8gydF4y2Ba在CompCert实验中，我们将这一工作一直进行到完整编译链的端到端验证，从结构化命令式语言到通过8种中间语言的汇编代码。在对CompCert进行验证时，我们发现许多执行的非优化翻译，虽然在编译器文献中通常被认为是显而易见的，但要正式证明其正确性却令人惊讶地棘手。gydF4y2Ba

本文对使用Coq证明助手的CompCert编译器及其机械化验证进行了高层概述。gydF4y2Ba^{3.gydF4y2Ba，gydF4y2Ba7gydF4y2Ba}这个编译器通常由两部分组成:一个前端将C的Clight子集翻译成一种称为Cminor的底层结构化中间语言，另一个经过轻微优化的后端从Cminor生成PowerPC汇编代码。Clight的详细描述可以在《Blazy和Leroy》中找到gydF4y2Ba^5gydF4y2Ba；在Blazy等人的编译器前端。gydF4y2Ba^4gydF4y2Ba；以及Leroy中的编译器后端。gydF4y2Ba^{11gydF4y2Ba，gydF4y2Ba13gydF4y2Ba}Coq开发的完整源代码(有大量评论)可以在Web上找到。gydF4y2Ba^12gydF4y2Ba

本文的其余部分组织如下。第2节比较并形式化了几种在编译结果中建立信任的方法。第3节描述了CompCert编译器的结构、它的性能，以及如何使用Coq证明助手来证明它的正确性，以及如何编写它的大部分程序。由于篇幅有限，我们将不详细说明每个编译过程的正式验证。但是，第4节提供了对编译器一个关键步骤的这种验证的技术概述:寄存器分配。最后，第五部分给出了初步结论和未来工作的方向。gydF4y2Ba

回到顶部gydF4y2Ba

2.可信编译方法gydF4y2Ba

2.1.语义保存的概念gydF4y2Ba

考虑一个源程序gydF4y2Ba年代gydF4y2Ba还有一个编译程序gydF4y2BaCgydF4y2Ba由编译器生成。我们的目的是证明的语义gydF4y2Ba年代gydF4y2Ba在编译过程中保存。为了使语义保存的概念更加精确，我们假设源语言和目标语言的语义是给定的，它们将可观察到的行为联系起来gydF4y2BaBgydF4y2Ba来gydF4y2Ba年代gydF4y2Ba而且gydF4y2BaCgydF4y2Ba．我们写gydF4y2Ba年代gydF4y2BaBgydF4y2Ba意思是这个程序gydF4y2Ba年代gydF4y2Ba执行可观察的行为gydF4y2BaBgydF4y2Ba．我们在CompCert中观察到的行为包括终止、发散和“出错”(调用可能崩溃的未定义操作，例如访问超出边界的数组)。在所有情况下，行为还包括在程序执行期间执行的输入输出操作(系统调用)的跟踪。因此，行为准确地反映了程序的用户，或者更普遍地说，程序交互的外部世界，可以观察到什么。gydF4y2Ba

编译过程中语义保存的最强概念是源程序gydF4y2Ba年代gydF4y2Ba编译后的代码gydF4y2BaCgydF4y2Ba有完全相同的可观察行为:gydF4y2Ba

概念(1)太强大，无法使用。如果源语言不是确定的，编译器可以选择源程序的一种可能的行为。(例如，C编译器为表达式选择一个特定的求值顺序gydF4y2BaCgydF4y2Ba规范。)在这种情况下,gydF4y2BaCgydF4y2Ba会有更少的行为gydF4y2Ba年代gydF4y2Ba．此外，编译器优化可以优化消除“出错”行为。例如,如果gydF4y2Ba年代gydF4y2Ba整数除以零可能会出错，但编译器消除了这个计算，因为它的结果是没有用的，gydF4y2BaCgydF4y2Ba不会出错的。为了考虑编译器中的这些自由度，我们将定义(1)放宽如下:gydF4y2Ba

(在这里,gydF4y2Ba年代gydF4y2Ba安全gydF4y2Ba意味着没有任何可能的行为gydF4y2Ba年代gydF4y2Ba是一种“走向错误”的行为。)换句话说，如果gydF4y2Ba年代gydF4y2Ba不会出错，那也不会吗gydF4y2BaCgydF4y2Ba；而且，所有可观察到的行为gydF4y2BaCgydF4y2Ba是可以接受的行为gydF4y2Ba年代gydF4y2Ba．gydF4y2Ba

在CompCert实验和本文的其余部分中，我们关注确定性的源语言和目标语言(程序仅在响应不同的输入时改变其行为，而不是由于内部选择)和确定性的执行环境(给予程序的输入由它们之前的输出惟一决定)。在这些条件下，只存在一种行为gydF4y2BaBgydF4y2Ba这样gydF4y2Ba年代gydF4y2BaBgydF4y2Ba，同理gydF4y2BaCgydF4y2Ba．在这种情况下，很容易证明性质(2)等价于gydF4y2Ba

(在这里,gydF4y2Ba错误的gydF4y2Ba是一组“出错”的行为。)性质(3)通常比性质(2)更容易证明，因为证明可以通过执行的归纳进行gydF4y2Ba年代gydF4y2Ba．这就是我们在这项工作中所采取的方法。gydF4y2Ba

从形式化方法的角度来看，我们真正感兴趣的是编译后的代码是否满足应用程序的功能规范。假设这些规范是作为谓词给出的gydF4y2Ba规范gydF4y2Ba（gydF4y2BaBgydF4y2Ba)的可观察行为。我们说gydF4y2BaCgydF4y2Ba满足规格，并写gydF4y2BaCgydF4y2Ba规范gydF4y2Ba,如果gydF4y2BaCgydF4y2Ba不会出错(gydF4y2BaCgydF4y2Ba安全gydF4y2Ba)和所有的行为gydF4y2BaBgydF4y2Ba满足gydF4y2Ba规范gydF4y2Ba（gydF4y2BaBgydF4y2Ba，gydF4y2BaCgydF4y2BaBgydF4y2Ba规范gydF4y2Ba（gydF4y2BaBgydF4y2Ba))。编译器的预期正确性属性是它保留了源代码gydF4y2Ba年代gydF4y2Ba满足规范，这一事实已经通过正式的验证单独建立gydF4y2Ba年代gydF4y2Ba：gydF4y2Ba

很容易表明属性(2)隐含所有规范的属性(4)gydF4y2Ba规范gydF4y2Ba．因此，一劳永逸地确立所有权(2)可以使我们不必为每一种利益规范建立所有权(4)。gydF4y2Ba

属性(4)的一个特殊情况，具有相当的历史重要性，是类型和内存安全的保存，我们可以总结为“如果”gydF4y2Ba年代gydF4y2Ba不会出错，也不会gydF4y2BaCgydF4y2Ba"：gydF4y2Ba

结合单独的检查gydF4y2Ba年代gydF4y2Ba在一个健全的类型系统中是良好的类型，属性(5)意味着gydF4y2BaCgydF4y2Ba执行时没有内存冲突。Type-preserving编译gydF4y2Ba^18gydF4y2Ba通过不同的方式获得这一保证:在假定gydF4y2Ba年代gydF4y2Ba类型,gydF4y2BaCgydF4y2Ba在一个健全的类型系统中被证明是良好的类型，确保它不会出错。已证明的属性(2)或(3)提供了相同的保证，而不必为目标语言和中间语言配备健全的类型系统，并为编译器证明类型保存。gydF4y2Ba

2.2.验证、验证、验证编译器gydF4y2Ba

我们现在讨论几种建立编译器保留已编译程序语义的方法，如第2.1节所述。在下面，我们写道gydF4y2Ba年代gydF4y2BaCgydF4y2Ba,在那里gydF4y2Ba年代gydF4y2Ba是源程序和gydF4y2BaCgydF4y2Ba为编译后的代码，表示第2.1节的语义保存属性(1)至(5)之一。gydF4y2Ba

验证编译器。gydF4y2Ba我们将编译器建模为一个总函数gydF4y2Ba电脑及相关知识gydF4y2Ba从源程序到编译后的代码gydF4y2Ba电脑及相关知识gydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) =gydF4y2Ba好吧gydF4y2Ba（gydF4y2BaCgydF4y2Ba))或编译时错误(写入gydF4y2Ba电脑及相关知识gydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) =gydF4y2Ba错误gydF4y2Ba)．编译时错误对应于编译器无法生成代码的情况，例如源程序不正确(语法错误、类型错误等)，或者它超出了编译器的能力。一个编译器gydF4y2Ba电脑及相关知识gydF4y2Ba如果附有以下财产的正式证明，则被认为是被核实的:gydF4y2Ba

换句话说，经过验证的编译器要么报告错误，要么生成满足所需正确性属性的代码。注意，编译器总是失败(gydF4y2Ba电脑及相关知识gydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) =gydF4y2Ba错误gydF4y2Ba对所有gydF4y2Ba年代gydF4y2Ba)虽然无用，但确实得到验证。编译器是否成功编译感兴趣的源程序不是一个正确性问题，而是一个实现质量问题，这可以通过测试等非正式方法来解决。从正式验证的角度来看，重要的特性是编译器永远不会悄无声息地生成错误的代码。gydF4y2Ba

从定义(6)的意义上验证编译器相当于将程序证明技术应用于编译器源，使用2.1节中定义的属性之一作为编译器的高级规范。gydF4y2Ba

使用验证验证器的翻译验证。gydF4y2Ba在翻译验证方法中gydF4y2Ba^{20.gydF4y2Ba，gydF4y2Ba22gydF4y2Ba}编译器不需要验证。相反，编译器由gydF4y2Ba一个验证器gydF4y2Ba:一个布尔值函数gydF4y2Ba验证gydF4y2Ba（gydF4y2Ba年代,CgydF4y2Ba)来验证属性gydF4y2Ba年代gydF4y2BaCgydF4y2Ba后验。如果gydF4y2Ba电脑及相关知识gydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) =gydF4y2Ba好吧gydF4y2Ba（gydF4y2BaCgydF4y2Ba),gydF4y2Ba验证gydF4y2Ba（gydF4y2Ba年代,CgydF4y2Ba) =gydF4y2Ba真正的gydF4y2Ba，编译后的代码gydF4y2BaCgydF4y2Ba被认为是值得信赖的。的符号解释和静态分析可以通过几种方式执行验证gydF4y2Ba年代gydF4y2Ba而且gydF4y2BaCgydF4y2Ba生成验证条件，然后进行模型检验或自动定理证明。房地产gydF4y2Ba年代gydF4y2BaCgydF4y2Ba一般来说，验证器是不可确定的，因此它必须是不完整的，并且应该进行应答gydF4y2Ba假gydF4y2Ba如果他们不能建立gydF4y2Ba年代gydF4y2BaCgydF4y2Ba．gydF4y2Ba

翻译验证对已编译代码的正确性产生了额外的信心，但它本身并不能提供像经过验证的编译器所提供的那样强大的正式保证:验证器本身可能是不正确的。为了排除这种可能性，我们说验证器gydF4y2Ba验证gydF4y2Ba如附有下列财产的正式证明，则可获核实:gydF4y2Ba

经过验证的验证器的组合gydF4y2Ba验证gydF4y2Ba使用未经验证的编译器gydF4y2Ba电脑及相关知识gydF4y2Ba提供与经过验证的编译器提供的一样强的正式保证。实际上，考虑以下函数:gydF4y2Ba

从定义(6)的意义上讲，这个函数是一个经过验证的编译器。因此，验证翻译验证器是一个比编译器验证更有吸引力的选择，只要验证器比编译器更小更简单。gydF4y2Ba

携带证明代码和验证编译器。gydF4y2Ba携带证明代码(PCC)方法gydF4y2Ba^{1gydF4y2Ba，gydF4y2Ba19gydF4y2Ba}不试图在源程序和某些已编译代码之间建立语义保存。相反，PCC专注于生成可独立检查的已编译代码证据gydF4y2BaCgydF4y2Ba满足行为规范gydF4y2Ba规范gydF4y2Ba例如类型和内存安全。PCC利用gydF4y2Ba证明编译器gydF4y2Ba，是一个函数gydF4y2BaCCompgydF4y2Ba要么失败，要么返回编译后的代码gydF4y2BaCgydF4y2Ba还有财产证明gydF4y2BaCgydF4y2Ba规范gydF4y2Ba．证明，也叫agydF4y2Ba证书gydF4y2Ba，可由代码用户独立检查;不需要信任代码生成器，也不需要正式验证编译器本身。基础设施中唯一需要信任的部分是客户端检查器:检查是否包含属性的程序gydF4y2BaCgydF4y2Ba规范gydF4y2Ba．gydF4y2Ba

就像在翻译验证的情况下，它足以正式验证客户端检查程序，以获得与编译器验证属性(4)获得的保证一样强的保证。对称地，至少在理论上，可以从验证的编译器构造一个验证编译器，前提是验证是按照“命题即类型，证明即程序”范式进行的逻辑进行的。Leroy详细描述了这种结构。gydF4y2Ba^{11日,第二节gydF4y2Ba}

2.3.编译通道的组合gydF4y2Ba

编译器自然被分解为几个通过中间语言进行通信的通道。幸运的是，经过验证的编译器也可以以这种方式分解。考虑两个经过验证的编译器gydF4y2Ba电脑及相关知识gydF4y2Ba_1gydF4y2Ba而且gydF4y2Ba电脑及相关知识gydF4y2Ba_2gydF4y2Ba从语言gydF4y2BalgydF4y2Ba_1gydF4y2Ba来gydF4y2BalgydF4y2Ba_2gydF4y2Ba而且gydF4y2BalgydF4y2Ba_2gydF4y2Ba来gydF4y2BalgydF4y2Ba_3.gydF4y2Ba,分别。假设语义保存属性是可传递的。(对于第2.1节的属性(1)到(5)也是如此。)的错误传播组合gydF4y2Ba电脑及相关知识gydF4y2Ba_1gydF4y2Ba而且gydF4y2Ba电脑及相关知识gydF4y2Ba_2gydF4y2Ba：gydF4y2Ba

说明这个函数是一个经过验证的编译器是很简单的gydF4y2BalgydF4y2Ba_1gydF4y2Ba来gydF4y2BalgydF4y2Ba_3.gydF4y2Ba．gydF4y2Ba

2.4.总结gydF4y2Ba

本讨论的结论很简单，定义了验证CompCert编译器后端所遵循的方法。首先，如果编译器的目标语言具有确定性语义，编译器正确性证明的适当规范是定义(3)和(6)的组合:gydF4y2Ba

第二，经过验证的编译器可以按照常见的实践构造为编译传递的组合。但是，所有的中间语言都必须具有适当的正式语义。gydF4y2Ba

最后，对于每一次传递，我们都有一个选择，要么证明实现该传递的代码，要么通过不受信任的代码执行转换，然后使用经过验证的验证器验证其结果。后一种方法可以减少需要验证的代码量。gydF4y2Ba

回到顶部gydF4y2Ba

3.CompCert编译器概述gydF4y2Ba

3.1.源语言gydF4y2Ba

CompCert编译器的源语言Clight，gydF4y2Ba^5gydF4y2Ba是C编程语言的一个大子集，可与通常推荐用于编写关键嵌入式软件的子集相媲美。它几乎支持所有的C数据类型，包括指针、数组、gydF4y2Ba结构体gydF4y2Ba而且gydF4y2Ba联盟gydF4y2Ba类型;所有结构化控制(gydF4y2Ba如果/那么gydF4y2Ba循环,gydF4y2Ba休息,继续gydF4y2Ba, java风格gydF4y2Ba开关gydF4y2Ba）;以及函数的全部功能，包括递归函数和函数指针。主要的遗漏是扩展精度算术(gydF4y2Ba很久很久gydF4y2Ba而且gydF4y2Ba长两倍gydF4y2Ba）;的gydF4y2Ba转到gydF4y2Ba声明;nonstructured形式的gydF4y2Ba开关gydF4y2Ba比如达夫的装置;通过gydF4y2Ba结构体gydF4y2Ba而且gydF4y2Ba联盟gydF4y2Ba参数和结果按值;以及参数数量可变的函数。Clight缺少C的其他特性，但在解析过程中通过代码扩展(去糖化)支持:表达式中的副作用(Clight表达式没有副作用)和块作用域变量(Clight只有全局变量和函数局部变量)。gydF4y2Ba

Clight的语义是以大步骤操作风格正式定义的。该语义是确定的，并使ISO C标准中未指定或未定义的许多行为变得精确，例如数据类型的大小、在溢出情况下有符号算术操作的结果以及求值顺序。其他未定义的C行为始终被转化为“出错”行为，例如解除对空指针的引用或访问超出边界的数组。内存被建模为一组互不相连的块，每个块通过字节偏移量访问;指针值是块标识符和字节偏移量的对。这样，即使在不兼容的指针类型之间存在强制转换，也可以精确地建模指针算术。gydF4y2Ba

3.2.编译通过和中间语言gydF4y2Ba

CompCert编译器的正式验证部分从Clight抽象语法转换为PPC抽象语法，PPC是PowerPC汇编语言的一个子集。中所描绘的一样gydF4y2Ba图1gydF4y2Ba该编译器由14个步骤组成，经过8种中间语言。不详细gydF4y2Ba图1gydF4y2Ba编译器的哪些部分还没有被验证:upstream，一个解析器，类型检查器和简化器，它从C源文件生成Clight抽象语法，基于CIL库gydF4y2Ba^21gydF4y2Ba；下游是PPC抽象语法树的打印机，使用具体的程序集语法，然后使用系统的汇编程序和链接程序生成可执行二进制文件。gydF4y2Ba

编译器的前端通过c#次要语言和Cminor中间语言分两次转换掉特定于C语言的特性。c# minor是Clight的简化、无类型变体，其中为整数、指针和浮点提供了不同的算术运算符，C循环被无限循环加上块和外围块的多级出口所取代。第一次传递相应地转换C循环并消除所有与类型相关的行为:操作符重载被解决;内存加载和存储以及地址计算都是显式的。下一个中间语言Cminor类似于c# minor，只是省略了& (address-of)操作符。Cminor函数局部变量不驻留在内存中，它们的地址不能取。但是，Cminor支持函数激活记录中的数据显式堆栈分配。因此，从c# minor到Cminor的转换识别了地址从未被取的标量局部变量，将它们分配给Cminor局部变量，并使它们成为以后寄存器分配的候选变量;其他本地变量在激活记录中按堆栈分配。gydF4y2Ba

编译器后端从一个指令选择通道开始，它识别使用组合算术指令(add-immediate、not-and、rotate-and-mask等)和目标处理器提供的寻址模式的机会。此传递通过自下而上重写Cminor表达式进行。目标语言是CminorSel, Cminor的一个依赖于处理器的变体，它提供了额外的操作符、寻址模式和一类条件表达式(仅对表达式的真值进行计算)。gydF4y2Ba

下一个传递将CminorSel转换为RTL，这是一种经典的寄存器传输语言，其中控制表示为控制流图(CFG)。图的每个节点都携带一个在临时(伪寄存器)上操作的机器级指令。RTL是一种基于数据流分析进行优化的方便表示。目前实现了两种这样的优化:常量传播和公共子表达式消除，后者通过扩展基本块上的值编号来执行。第三个优化，懒惰代码运动，是单独开发的，将很快集成。与其他两种优化不同，延迟代码移动是按照经过验证的验证器方法实现的。gydF4y2Ba^24gydF4y2Ba

在这些优化之后，通过干涉图的着色来完成寄存器分配。gydF4y2Ba^6gydF4y2Ba这一过程的输出是LTL，这是一种类似于RTL的语言，其中临时变量被硬件寄存器或抽象堆栈位置替换。CFG然后被“线性化”，产生一个带有显式标签、条件和无条件分支的指令列表。接下来，溢出和重载被插入到引用分配给堆栈位置的临时变量的指令周围，移动被插入到函数调用、序言和尾声周围，以强制调用约定。最后，“堆叠”传递布置函数的激活记录，在该记录中为抽象堆栈位置和保存的被调用者保存寄存器分配偏移量，并通过显式的相对于堆栈指针的内存负载和存储替换对抽象堆栈位置的引用。gydF4y2Ba

这就引出了Mach中间语言，它在语义上接近于PowerPC汇编语言。此时可以执行通过列表或跟踪调度的指令调度，再次遵循经过验证的验证器方法。gydF4y2Ba^23gydF4y2Ba最后的编译过程将Mach指令扩展为PowerPC指令的封装序列，处理特殊寄存器，如条件寄存器和PowerPC指令集中的不规则情况。目标语言PPC精确地对PowerPC汇编语言的一个大子集建模，省略了CompCert不生成的指令和特殊寄存器。gydF4y2Ba

从编译的角度来看，CompCert并不引人注目:各种各样的传递和中间表示都是20世纪90年代早期的教科书式编译技术。也许唯一令人惊讶的是中间语言的数量相对较高，但许多都是彼此之间的小变体:为了验证目的，将每种变体识别为不同的语言比将其识别为几种更通用的中间表示的不同子集更方便。gydF4y2Ba

3.3.证明编译器gydF4y2Ba

CompCert的附加价值不在于实现的编译技术，而在于每一种源语言、中间语言和目标语言都正式定义了语义，并且每一种转换和优化都被证明保留了2.4节意义上的语义。gydF4y2Ba

使用Coq证明助手将这些语义保存证明机械化。Coq实现了归纳和共归纳结构的演算，这是一种强大的构造性高阶逻辑，它同样支持三种常见的写作规范风格:通过函数和模式匹配，通过表示推理规则的归纳或共归纳谓词，以及一阶逻辑中的普通谓词。在CompCert的开发中使用了所有三种风格，这导致了在编程语言研究论文中可以找到的规范和定理陈述非常接近。特别是，编译算法自然地表现为函数，而操作语义主要使用归纳谓词(推理规则)。Coq还具有更高级的逻辑功能，如高阶逻辑、依赖类型和ml风格的模块系统，我们在开发中偶尔会用到这些功能。例如，依赖类型使我们能够将逻辑不变量附加到数据结构中，而参数化模块使我们能够为若干静态分析重用通用数据流方程求解器。gydF4y2Ba

在Coq中证明定理是一个交互式的过程:例如，一些决策过程将等式推理或Presburger算术自动化，但大多数证明由用户输入的“战术”(基本证明步骤)序列组成，以指导Coq解决证明义务。在内部，Coq构建证明项，稍后由一个小型内核验证器重新检查，从而对证明的有效性产生非常高的置信度。当以交互方式开发时，证明脚本可以在批处理模式下进行后验重新检查。gydF4y2Ba

整个Coq形式化和证明代表了42,000行Coq(不包括注释和空行)和大约3人年的工作。在这42,000行代码中，14%定义了在CompCert中实现的编译算法，10%指定了相关语言的语义。剩下的76%对应于正确性证明本身。每个编译过程需要1500到3000行Coq来进行规范和正确性证明。同样，每一种中间语言都在Coq的300到600行中指定，而源语言Clight则需要1100行。另外10,000行对应于所有语言和传递之间共享的基础结构，例如机器整数算术和内存模型的形式化。gydF4y2Ba

3.4.编写和运行编译器gydF4y2Ba

我们不仅使用Coq作为进行语义保存证明的证明程序，而且使用Coq作为编写CompCert编译器中所有经过验证的部分的编程语言。Coq的规范语言包括一种小型的纯函数式语言，具有通过在归纳类型(ML或haskell风格的树状数据类型)上进行模式匹配来操作的递归函数。通过一些巧妙的设计，这种语言足以编写一个编译器。在编译器教科书中发现的高度命令式算法需要以纯函数风格重写。我们使用基于平衡树的持久数据结构，它支持有效的更新，而无需就地修改数据。同样，一元编程风格使我们能够以易读的、组合的方式对异常和状态进行编码。gydF4y2Ba

与用传统的命令式语言实现编译器相比，这种非常规方法的主要优点是，我们不需要程序逻辑(如Hoare逻辑)来连接编译器的代码与其逻辑规范。实现编译器的Coq函数是Coq逻辑的一等公民，可以通过归纳、简化和方程推理直接推理。gydF4y2Ba

为了获得可执行编译器，我们依赖于Coq的提取工具，gydF4y2Ba^15gydF4y2Ba根据Coq功能规格自动生成Caml代码。将提取的代码与编译器中未验证部分(如解析器)的Caml手写实现结合起来，并通过Caml编译器运行所有这些，我们得到一个编译器，它具有一个标准，gydF4y2BaccgydF4y2Ba样式的命令行界面，可以在Caml支持的任何平台上运行，并生成在MacOS x下运行的PowerPC代码(其他目标平台正在开发中)。gydF4y2Ba

3.5.性能gydF4y2Ba

为了评估CompCert生成的代码的质量，我们将其与GCC 4.0.1编译器在优化级别0、1和2上进行了基准测试。由于标准的基准测试套件使用的是CompCert不支持的C的特性，我们不得不推出自己的小套件，其中包含一些计算内核、加密原语、文本压缩器、虚拟机解释器和射线跟踪器。测试在2 GHz PowerPC 970“G5”处理器上运行。gydF4y2Ba

时间到了gydF4y2Ba图2gydF4y2Ba显示，CompCert生成的代码比没有优化的GCC生成的代码快两倍多，在优化级别1和2上与GCC竞争。平均而言，CompCert代码只比gydF4y2Bagcc 01gydF4y2Ba比gydF4y2Bagcc 02gydF4y2Ba．该测试套件太小，无法得出明确的结论，但这些结果强烈表明，尽管CompCert不会在高性能计算中获奖，但它的性能足以用于关键的嵌入式代码。gydF4y2Ba

CompCert的编译时间是编译时间的2倍gydF4y2Bagcc01gydF4y2Ba，这是合理的，并表明为方便验证而引入的开销(许多小的pass，没有命令式数据结构，等等)是可以接受的。gydF4y2Ba

回到顶部gydF4y2Ba

4.寄存器分配gydF4y2Ba

为了提供一个验证编译通过的更详细的示例，我们现在展示CompCert的寄存器分配通过并概述其正确性证明。gydF4y2Ba

4.1.RTL中间语言gydF4y2Ba

寄存器分配是在RTL中间表示上执行的，它将函数表示为抽象指令的CFG，大致对应于机器指令，但在伪寄存器(也称为“临时寄存器”)上操作。每个函数都有无限的伪寄存器，它们的值在函数调用中保存。在下面,gydF4y2BargydF4y2Ba伪寄存器和的范围gydF4y2BalgydF4y2BaCFG节点的标签。gydF4y2Ba

产品说明:gydF4y2Ba

控制流图:gydF4y2Ba

内部功能:gydF4y2Ba

外部函数:gydF4y2Ba

每条指令的参数都在一个伪寄存器列表中gydF4y2Ba并将结果(如果有的话)存储在一个伪寄存器中gydF4y2BargydF4y2Ba．此外，它带有标签gydF4y2BalgydF4y2Ba它可能的继承者。指令包括算术运算gydF4y2Ba人事处gydF4y2Ba(有一个重要的特殊情况gydF4y2Baop(移动gydF4y2Ba，gydF4y2Bar, r, lgydF4y2Ba)表示寄存器到寄存器的副本)、内存负载和存储(应用寻址方式获得的地址的数量)gydF4y2Ba模式gydF4y2Ba对寄存器gydF4y2Ba)、条件分支(有两个后继分支)、函数调用、尾部调用和返回。gydF4y2Ba

RTL程序由一组命名函数组成，可以是内部函数，也可以是外部函数。在RTL中，通过它们的CFG、CFG中的入口点和参数寄存器定义内部函数。外部函数没有定义，只是声明:它们为输入/输出操作和类似的系统调用建模。函数和调用指令携带签名gydF4y2Ba团体gydF4y2Ba指定数量和寄存器类(gydF4y2BaintgydF4y2Ba或gydF4y2Ba浮动gydF4y2Ba)的论点和结果。gydF4y2Ba

RTL的动态语义以小步骤操作风格指定，作为标记转换系统。谓词gydF4y2BaGgydF4y2Ba年代gydF4y2Ba年代gydF4y2Ba表示从状态执行的一个步骤gydF4y2Ba年代gydF4y2Ba州gydF4y2Ba年代gydF4y2Ba．全球环境gydF4y2BaGgydF4y2Ba将函数指针和名称映射到函数定义。跟踪gydF4y2BatgydF4y2Ba记录此执行步骤执行的输入输出事件:它为空(gydF4y2BatgydF4y2Ba=)用于除调用外部函数外的所有指令gydF4y2BatgydF4y2Ba记录函数名、参数和调用结果。gydF4y2Ba

执行状态gydF4y2Ba年代gydF4y2Ba都是这样的gydF4y2Ba年代gydF4y2Ba(，gydF4y2BaggydF4y2Ba， ，gydF4y2BalgydF4y2Ba，gydF4y2BaR,米gydF4y2Ba),gydF4y2BaggydF4y2Ba为当前正在执行的函数的CFG，gydF4y2BalgydF4y2Ba此函数中的当前程序点，以及包含其激活记录的内存块。注册状态gydF4y2BaRgydF4y2Ba将伪寄存器映射到它们的当前值(32位整数、64位浮点数和指针的区别并集)。同样，内存状态gydF4y2Ba米gydF4y2Ba将(指针、内存数量)对映射到值，考虑到多字节数量之间的重叠。gydF4y2Ba^14gydF4y2Ba最后，对调用堆栈建模:它用它们的(gydF4y2Bag，， l, RgydF4y2Ba)组件。在对函数调用和返回进行建模时，会出现两种稍有不同的执行状态，即调用状态和返回状态，但这里不进行描述。gydF4y2Ba

为了了解RTL的语义，下面是定义一步转换关系的两个规则，分别用于算术操作和条件分支:gydF4y2Ba

4.2.寄存器分配算法gydF4y2Ba

寄存器分配通道的目的是替换伪寄存器gydF4y2BargydF4y2Ba它们在原始RTL代码中以无限的数量按位置出现gydF4y2BalgydF4y2Ba，它们要么是硬件寄存器(可用的数量很少，数量固定)，要么是激活记录中的抽象堆栈槽(可用的数量不限)。由于访问硬件寄存器比访问堆栈插槽要快得多，因此必须最大化地使用硬件寄存器。寄存器分配的其他方面，例如插入重载和溢出指令以访问堆栈插槽，留给后续的传递。gydF4y2Ba

寄存器分配从向后数据流分析执行的标准活动分析开始。活性的数据流方程的形式gydF4y2Ba

传递函数gydF4y2BaTgydF4y2Ba（gydF4y2Ba年代,LVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)计算程序点之前的伪寄存器集gydF4y2Ba年代gydF4y2Ba作为伪寄存器的函数gydF4y2BaLVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)活在那个点之后。例如，如果指令在gydF4y2Ba年代gydF4y2Ba是gydF4y2Ba人事处gydF4y2Ba（gydF4y2Ba人事处gydF4y2Ba，gydF4y2Ba，gydF4y2Bar, s 'gydF4y2Ba),结果gydF4y2BargydF4y2Ba死亡，因为它在这里被重新定义了，但是参数gydF4y2Ba变得活跃，因为它们在这一点上被使用:gydF4y2BaTgydF4y2Ba（gydF4y2Ba年代,LVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)) = (gydF4y2BaLVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba) {gydF4y2BargydF4y2Ba})gydF4y2Ba．然而,如果gydF4y2BargydF4y2Ba死后(gydF4y2BargydF4y2BalgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba))，该指令是死代码，将在稍后消除，所以我们可以采取gydF4y2BaTgydF4y2Ba（gydF4y2Ba年代,LVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)) =gydF4y2BaLVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)。gydF4y2Ba

用基尔达尔的工作表算法迭代求解数据流方程。CompCert提供了Kildall算法及其正确性证明的通用实现，也可用于其他优化通道。该算法的结果是一个映射gydF4y2BaLVgydF4y2Ba从程序点到被证明满足正确性条件的活动寄存器集gydF4y2BaLVgydF4y2Ba（gydF4y2BalgydF4y2Ba）gydF4y2BaTgydF4y2Ba（gydF4y2Ba年代,LVgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba)为所有gydF4y2Ba年代gydF4y2Ba的继任者gydF4y2BalgydF4y2Ba．我们只证明一个不等式而不是标准数据流方程(8)，因为我们只关心解的正确性，而不关心它的最优性。gydF4y2Ba

然后根据Chaitin的规则建立一个以伪寄存器为节点的干涉图，gydF4y2Ba^6gydF4y2Ba并被证明包含了所有必要的干涉边。通常，如果两个伪寄存器gydF4y2BargydF4y2Ba而且gydF4y2Bar 'gydF4y2Ba是否同时活在一个程序点上，图之间必须包含一条边gydF4y2BargydF4y2Ba而且gydF4y2Bar 'gydF4y2Ba．干扰的形式是“这两个伪寄存器相互干扰”或“这个伪寄存器和这个硬件寄存器相互干扰”，后者用于确保伪寄存器跨函数调用存在，而不是分配给调用者保存寄存器。偏好边(“最好将这两个伪寄存器分配到同一个位置”或“最好将这个伪寄存器分配到这个位置”)也被记录下来，尽管它们不影响寄存器分配的正确性，只影响其质量。gydF4y2Ba

寄存器分配的中心步骤是为干涉图着色，并分配给每个节点gydF4y2BargydF4y2Ba“颜色”(gydF4y2BargydF4y2Ba)，它是一个硬件寄存器或堆栈插槽，约束条件是由干涉边连接的两个节点被分配不同的颜色。我们使用乔治和阿佩尔的着色启发式。gydF4y2Ba^9gydF4y2Ba由于这种启发式难以直接证明其正确性，我们将其实现为未经验证的Caml代码，然后使用一个用Coq编写并证明正确的简单验证器后验验证其结果。像许多np困难的问题一样，图着色是验证后验比直接证明正确更容易的算法的范例。着色结果的正确条件为:gydF4y2Ba

1. （gydF4y2BargydF4y2Ba) (gydF4y2Bar 'gydF4y2Ba)如果gydF4y2BargydF4y2Ba而且gydF4y2Bar 'gydF4y2Ba影响gydF4y2Ba
2. （gydF4y2BargydF4y2Ba）gydF4y2BalgydF4y2Ba如果gydF4y2BargydF4y2Ba而且gydF4y2BalgydF4y2Ba影响gydF4y2Ba
3. （gydF4y2BargydF4y2Ba),gydF4y2BargydF4y2Ba具有相同的寄存器类(gydF4y2BaintgydF4y2Ba或gydF4y2Ba浮动gydF4y2Ba）gydF4y2Ba

用Coq编写的布尔值函数对这些条件进行了检验，证明了这三种条件的决策过程。如果检查失败，编译将中止，这表示外部图着色例程中存在错误。gydF4y2Ba

最后，重写原始的RTL代码。每次引用伪寄存器gydF4y2BargydF4y2Ba替换为其位置的引用(gydF4y2BargydF4y2Ba)．此外，还执行合并和死代码消除。无副作用的指令gydF4y2BalgydF4y2Ba：gydF4y2Ba人事处gydF4y2Ba（gydF4y2Ba人事处gydF4y2Ba，gydF4y2Ba，gydF4y2Bar, l 'gydF4y2Ba)或gydF4y2BalgydF4y2Ba：gydF4y2Ba负载gydF4y2Ba(，gydF4y2Ba模式gydF4y2Ba，gydF4y2Ba，gydF4y2Bar, l 'gydF4y2Ba)被替换为无操作gydF4y2BalgydF4y2Ba：gydF4y2BanopgydF4y2Ba（gydF4y2Bal 'gydF4y2Ba)如果结果gydF4y2BargydF4y2Ba不是生活之后gydF4y2BalgydF4y2Ba(死代码消除)。同样，一个move指令gydF4y2BalgydF4y2Ba：gydF4y2Ba人事处gydF4y2Ba（gydF4y2Ba移动gydF4y2Ba，gydF4y2BargydF4y2Ba_{年代gydF4y2Ba}，gydF4y2BargydF4y2Ba_dgydF4y2Ba，gydF4y2Bal 'gydF4y2Ba)被替换为无操作gydF4y2BalgydF4y2Ba：gydF4y2BanopgydF4y2Ba（gydF4y2Bal 'gydF4y2Ba)如果(gydF4y2BargydF4y2Ba_dgydF4y2Ba) = (gydF4y2BargydF4y2Ba_{年代gydF4y2Ba})(合并)。gydF4y2Ba

4.3.证明语义保存gydF4y2Ba

为了证明程序转换保持语义，在整个CompCert项目中使用的一种标准技术是显示一个模拟图:原始程序中的每个转换必须对应于转换后程序中的一系列转换，这些转换具有相同的可观察效果(在我们的例子中，输入输出操作的相同轨迹)，并保留原始程序和转换后程序的执行状态之间的一个给定的二进制关系作为不变变量。在分配寄存器的情况下，每个原始跃迁恰好对应一个转换后的跃迁，从而得到如下的“锁定步进”模拟图:gydF4y2Ba

(实线表示假设;虚线表示结论。)此外，如果不变量~将初始状态和最终状态联系起来，那么这样的模拟图意味着原始程序的任何执行都对应于生成完全相同的可观察事件跟踪的转换程序的执行。因此，语义保留就随之而来了。gydF4y2Ba

模拟证明的要点是~关系的定义。两种状态的条件是什么gydF4y2Ba年代gydF4y2Ba(，gydF4y2BaggydF4y2Ba， ，gydF4y2Bal R MgydF4y2Ba),gydF4y2Ba年代gydF4y2Ba(',gydF4y2Bag’gydF4y2Ba”,,gydF4y2Bal‘R’,M”gydF4y2Ba)有关系?直观地说，由于寄存器分配保留了程序结构和控制流，即控制点gydF4y2BalgydF4y2Ba而且gydF4y2Bal 'gydF4y2Ba必须是相同的，CFGgydF4y2Bag’gydF4y2Ba一定是转化的结果吗gydF4y2BaggydF4y2Ba根据第4.2节所述的某些寄存器分配。同样，由于寄存器分配保留了内存存储和分配，内存状态和堆栈指针必须相同:gydF4y2BaM ' = MgydF4y2Ba和' =。gydF4y2Ba

寄存器状态之间的关系不明显gydF4y2BaRgydF4y2Ba原始程序和位置状态gydF4y2BaR 'gydF4y2Ba改造后的项目。给定每个伪寄存器gydF4y2BargydF4y2Ba映射到位置(gydF4y2BargydF4y2Ba)，我们可能会天真地要求gydF4y2BaR (R) = R 'gydF4y2Ba（(gydF4y2BargydF4y2Ba)为所有gydF4y2BargydF4y2Ba．然而，这个要求太过强烈，因为它从本质上排除了两个活动范围不相连的伪寄存器之间的位置共享。为了获得正确的需求，我们需要考虑伪寄存器在程序点上是活的还是死的在语义上意味着什么gydF4y2BalgydF4y2Ba．一个死pseudo-registergydF4y2BargydF4y2Ba这是它在某一点上的价值吗gydF4y2BalgydF4y2Ba对程序执行没有影响，因为gydF4y2BargydF4y2Ba以后永远不会读取，或者总是在读取之前重新定义。因此，在建立寄存器和位置值之间的通信时，我们可以安全地忽略那些在当前点失效的寄存器gydF4y2BalgydF4y2Ba．满足以下条件就足够了:gydF4y2Ba

RgydF4y2Ba（gydF4y2BargydF4y2Ba) =gydF4y2BaR 'gydF4y2Ba（(gydF4y2BargydF4y2Ba))用于所有伪寄存器gydF4y2BargydF4y2Ba住在点gydF4y2BalgydF4y2Ba．gydF4y2Ba

一旦建立了状态之间的关系，证明上面的仿真图就是对RTL语义的各种转换规则的例行案例检查。在这样做的过程中，人们会愉快地认识到，定义活性的数据流不等式，以及构造干涉图的Chaitin规则，是寄存器状态之间不变量的最小充分条件gydF4y2BaR, R 'gydF4y2Ba在任何情况下都要保存。gydF4y2Ba

回到顶部gydF4y2Ba

5.结论和观点gydF4y2Ba

本文中描述的CompCert实验仍在进行中，还有很多工作要做:处理更大的C子集(例如包括gydF4y2Ba转到gydF4y2Ba）;部署并证明更多的优化是正确的;瞄准PowerPC以外的其他处理器;将语义保存证明扩展到共享内存并发等。然而，到目前为止获得的初步结果提供了强有力的证据，证明在今天的证明助手的限制下，仅使用基本的语义和算法方法，就可以实现正式验证一个现实编译器的最初目标。我们使用的技术和工具还远远不够完美——更多的证明自动化、更高级别的语义和更现代的中间表示都有可能显著减少证明的工作量——但已经足够达到目标。gydF4y2Ba

回顾所获得的结果，我们并没有完全排除所有关于编译器正确性的不确定性，而是将信任整个编译器的问题简化为信任以下部分:gydF4y2Ba

1. 源语言(Clight)和目标语言(PPC)的正式语义。gydF4y2Ba
2. 编译器中尚未验证的部分:基于cil的解析器、汇编器和链接器。gydF4y2Ba
3. 用于为编译器生成可执行文件的编译链:Coq的提取工具和Caml编译器和运行时系统。(这个编译链中的一个bug可能会使通过正确性证明获得的保证失效。)gydF4y2Ba
4. Coq证明助手本身。(Coq实现中的bug或Coq逻辑中的不一致都可能使证明错误。)gydF4y2Ba

问题(4)可能是最不值得关注的:正如黑尔斯所说，gydF4y2Ba^10gydF4y2Ba由生成证明项的证明助手机械检查的证明比手工仔细检查的数学证明更值得信赖。gydF4y2Ba

为了解决问题(3)，CompCert项目中正在进行的工作研究了正式验证Coq提取机制的可行性，以及从Mini-ML(提取所针对的简单函数式语言)到Cminor的编译器。这些工作与CompCert后端结合在一起，最终可以为用Coq编写和验证的程序提供一个可信的执行路径，就像CompCert本身一样，因此可以通过引导的形式进一步增加信心。gydF4y2Ba

问题(2)与CompCert的未验证组件显然可以通过重新实现和证明相应的通行证来解决。解析器的语义保存很难定义，更不用说证明了:如果不是解析产生的抽象语法树的语义，那么程序的具体语法的语义是什么?然而，CIL执行的解析后精化步骤中有几个是需要正式证明的。同样地，证明汇编程序和链接程序的正确性是可行的，即使不令人兴奋。gydF4y2Ba

也许最微妙的问题是(1):我们如何确保形式化语义与语言标准和通用编程实践一致?由于所讨论的语义相对于整个编译器来说是很小的，因此专家的手工检查，以及对语义的可执行形式进行的测试，可以提供合理的(但不是正式的)信心。另一种方法是证明与独立开发的替代形式语义之间的联系，例如强调程序演绎验证工具的公理语义(参见Appel和Blazy)gydF4y2Ba^2gydF4y2Ba一个例子)。此外，这种方法构成了迈向更雄心勃勃的长期目标的第一步:使用正式方法对参与关键软件的开发、验证和执行的验证工具、代码生成器、编译器和运行时系统进行认证。gydF4y2Ba

回到顶部gydF4y2Ba

致谢gydF4y2Ba

作者感谢S. Blazy、Z. Dargaye、D. Doligez、B. Grégoire、T. Moniot、L. Rideau和B. Serpette对CompCert开发的贡献，以及A. Appel、Y. Bertot、E. Ledinot、P. Letouzey和G. Necula的建议、反馈和帮助。这项工作得到了国家研究机构的支持，批准号为ANR-05-SSIA-0019。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.gydF4y2Ba

---

没有发现记录gydF4y2Ba