出具证明编译器中线性整数命题证明的自动生成

近年来,出具证明编译器作为构建高可信软件的重要途径,逐渐成为编译器理论和形式化验证的研究热点.在其理论框架中,编译器需要借助自动定理证明技术,自动地证明验证条件并生成机器可检查的证明项,因此好的自动定理证明器对出具证明编译器至关重要.本文基于Simplex算法在出具证明编译器的框架内设计并实现了一个支持线性整数命题求解的自动定理证明器,并且提出一套证明项构造方法,将其应用于自动定理证明器中可生成Coq可检查的证明.     

一个出具证明编译器原型系统的实现

出具证明编译器是随着人们对现今的软件提出更高的可靠性和安全性要求而产生的工具,它结合了以往程序设计和程序安全性证明的技术。论文介绍了一个出具证明编译器原型系统的实现。     

一个出具证明编译器后端的设计与实现

设计并实现一个类C语言PointerC的出具证明编译器后端。该后端采用最强后条件演算同步处理整型断言和指针断言实现整型验证条件和指针验证条件的证明,能够完全自动地产生目标级程序的指针安全性证明,处理常见递归数据结构中的非一致性别名问题。后端包括独立的定理检查器,能够检验携证明代码的完整性。     

一种出具证明编译器中的汇编级断言和证明生成的方法

携带证明代码允许代码消费方通过检查代码生产方提供的证明,来判断代码是否满足相应的安全规范.本文实现了一个类C语言的出具证明编译器原型,它在将带有规范标注的源代码编译成汇编代码的同时,还能产生汇编代码满足相应规范的Coq可检查证明,从而保证汇编代码的安全性.本文设计了一种Hoare风格的汇编级验证框架,并在此框架下提出并实现一种新的自动生成汇编级断言和证明的方法.     

GCC代码优化技术的研究

GCC是基于Linux下的开放源码的优化编译系统,可以接收多种高级源语言,广泛支持多平台操作系统.其代码优化机制,不仅能兼顾时间、空间效率,生成高质量的目标代码,而且具有很强的可移植性与可扩充性,是编译器优化研究的目标.通过对GCC的整体结构、优化策略、优化方法与关键技术、中间语言等进行详细的剖析,抽取出完整的GCC优化体系结构.文中集中探讨了GCC的优化策略和实现技术,首先从GCC优化体系的总体规划入手,着重分析了GCC的优化组织策略,设计、引入中间代码RTL的技巧和内涵,进一步研究了GCC所涉及的控制流分析技术、数据流分析技术的实现机制.     

支持用户自定义谓词的自动定理证明的研究

在先前设计的一个出具证明编译器原型基础上,增加了可用来描述数据结构性质的自定义谓词,对断言语言表达能力方面做了提升.在出具证明编译器的框架内,借助自动定理证明技术,针对自定义谓词的特点,设计了专门的推理规则,由此实现自定义谓词专用的自动定理证明器原型,并将它并入系统原来的自动定理证明器中.该原型可以用来证明操作单链表、二叉树等共享数据结构的程序的性质,其程序规范中可以使用自定义谓词描述数据有序性、链表长度等性质.     

同步数据流语言可信编译器的构造

同步数据流语言近年来在航空、高铁、核电等安全关键领域得到广泛应用.然而,此类语言相关开发工具本身的安全性业已成为被高度关注的安全隐患之一.借助辅助定理证明器实现常规语言编译器的构造和验证已被证明是成功的,有望最大限度地解决误编译问题.基于这种方法,开展了从同步数据流语言(Lustre为原型)到串行命令式语言(C为原型)的可信编译器构造的关键技术研究.其挑战性在于两类语言之间的巨大差异,源语言具有时钟同步、数据流、并发及流数据对象等特征,而目标语言则具有顺序控制流特征.同类研究中,目前尚无针对核心翻译过程的公开成果.就单一时钟的情形实现了一个经过形式化验证的完整编译过程,相关技术将应用于安全关键领域编译系统的开发.综述了这一可信编译器的研究背景、意义、总体设计框架、核心技术、现状以及进行中或后续的工作.     

分析ARM流水线关键技术分析与代码优化

随着科学技术水平的不断提高,在微处理器的结构体系中,流水线技术因为自身的优良特性逐渐被重视和运用。因为流水线技术的广泛应用,对于它的理论研究也显得十分重要,其体系理论体系包括了流水线技术的具体分类,各项性能指标(吞吐率、加速比、效率)以及技术规范等,可谓庞杂。以ARM7和ARM9两种处理器系列为重点,对其使用的三级流水线和五级流水线的工作原理进行了分析,并阐述了在不同情况下的流水线运行状况,结合实际提出了一些代码优化,提高性能的方法。     

ARM流水线关键技术分析与代码优化

流水线技术是广泛应用在微处理器体系结构中的关键技术。本文根据ARM系列处理器采用的三级和五级流水线的工作原理,对各种冲突情况下的流水线运行情况进行了详细分析,最后通过实例分析提出在编程阶段提高流水线性能的方法。     

可信编译器L2C的核心翻译步骤及其设计与实现

同步数据流语言（如Lustre）近年来在航空、高铁、核电等安全攸关领域得到广泛应用.这些领域对相关开发工具本身的安全性有着相当高的要求.为尽力解决好”误编译”问题,近期人们借助reliable-by-construction辅助定理证明器实现常规命令式语言编译器的构造和验证取得了很大的成功,如CompCert C编译器.L2C是基于这种方法开发的可信编译器,它以扩展的Lustre语言为源语言,以Clight （CompCert中的C语言子集）为目标语言.就我们所知,L2C是同类工作中唯一面向实际工业应用的同步数据流语言编译器.本文重点介绍L2C编译器的核心翻译步骤及其设计与实现过程中考虑的主要问题和相关经验.     

基于类型注解的认证编译器设计与实现

基于类型注解的认证编译器是安全策略系统的核心部件,它不仅能够用C语言的类型安全子集编写的程序编译成优化的Intel x86／linux汇编语言程序,而且还可以根据类型安全策略的要求产生带注解的汇编程序．实验结果表明,新设计的认证编译器可实现：①类型安全的C语言子集的编译;②许多标准的局部优化;③可以对数组运行时越界操作进行检查．由于安全策略系统的证明是建立在含注解的代码基础之上的,因此,该认证编译器在移动代码安全检查中非常有用。     

PCC中数组边界检查的优化和生成

PCC的数组边界检查存在着由于无法确定数组下标表达式符号值的范围，而造成拒绝执行一些安全的移动代码等问题。本文给出的一种数组边界检查的优化及生成算法，不仅能够比较好地解决了这一问题，同时还生成了循环不变式注解中的条件谓词。我们设计的编译器——认证编译器——已经实现了这些算法，并完成了从用C编程语言的类型安全子集编写的源程序到携带注解的Intelx86／linux汇编语言程序的编译过程。由于基于语言安全策略系统的证明是建立在携带注解的代码基础之上的，因此该认证编译器中实现的算法在移动代码安全检查中非常有用。     

Certifying Compilation and Run-Time Code Generation

A certifying compiler takes a source language program and produces object code, as well as a certificate that can be used to verify that the object code satisfies desirable properties, such as type safety and memory safety. Certifying compilation helps to increase both compiler robustness and program safety. Compiler robustness is improved since some compiler errors can be caught by checking the object code against the certificate immediately after compilation. Program safety is improved because the object code and certificate alone are sufficient to establish safety: even if the object code and certificate are produced on an unknown machine by an unknown compiler and sent over an untrusted network, safe execution is guaranteed as long as the code and certificate pass the verifier.Existing work in certifying compilation has addressed statically generated code. In this paper, we extend this to code generated at run time. Our goal is to combine certifying compilation with run-time code generation to produce programs that are both fast and verifiably safe. To achieve this goal, we present two new languages with explicit run-time code generation constructs: Cyclone, a type safe dialect of C, and TAL/T, a type safe assembly language. We have designed and implemented a system that translates a safe C program into Cyclone, which is then compiled to TAL/T, and finally assembled into executable object code. This paper focuses on our overall approach and the front end of our system; details about TAL/T will appear in a subsequent paper.     

即时编译器中的代码消极生成机制

提出一种应用于即时编译器中的代码生成优化技术——代码消极生成机制,结合Intel微处理器研究院的XORP虚拟机对该项技术进行了阐述。介绍了XORP中实现的其他轻量级优化算法,并采用EEMBC对不同虚拟机和不同优化进行了科学评估。采用该项技术的XORP虚拟机的运行速度为KVM的15倍以上,超过其他商用高性能虚拟机。     

GCC代码优化技术的研究

GCC是基于Linux下的开放源码的优化编译系统，可以接收多种高级源语言，广泛支持多平台操作系统。其代码优化机制，不仅能兼顾时间、空间效率，生成高质量的目标代码，而且具有很强的可移植性与可扩充性，是编译器优化研究的目标。通过对GCC的整体结构、优化策略、优化方法与关键技术、中间语言等进行详细的剖析，抽取出完整的GCC优化体系结构。文中集中探讨了GCC的优化策略和实现技术，首先从GCC优化体系的总体规划入手，着重分析了GCC的优化组织策略，设计、引入中间代码RTL的技巧和内涵，进一步研究了GCC所涉及的控制流分析技术、数据流分析技术的实现机制。     

汇编代码验证中的形式规范自动生成

与传统的高级语言程序验证相比,汇编代码验证中所需要的形式规范往往比较复杂,通常的做法是要求程序员手写形式规范,或是牺牲形式规范的表达能力以期能够自动生成规范.本文提出一种能够自动生成形式规范的方法,该方法依托一个出具证明的编译器自动生成汇编级形式规范,从而减轻程序员的负担.使用该方法生成的规范比现有的其他方法自动生成的规范具有更强的表达能力.文章主要描述该方法在出具证明编译器中的实现.     

Completeness of a Bytecode Verifier and a Certifying Java-to-JVM Compiler

During an attempt to prove that the Java-to-JVM compiler generates code that is accepted by the bytecode verifier, we found examples of legal Java programs that are rejected by the verifier. We propose therefore to restrict the rules of definite assignment for the try-finally statement as well as for the labeled statement so that the example programs are no longer allowed. Then we can prove, using the framework of Abstract State Machines, that each program from the slightly restricted Java language is accepted by the Bytecode Verifier. In the proof we use a new notion of bytecode type assignment without subroutine call stacks. This revised version was published online in August 2006 with corrections to the Cover Date.