一种新的关键路径求解算法

关键路径通常是在拓扑排序的基础上求得的，本文提出了一种新的求关键路径的算法，该算法数据结构形式简单直观，且易于实现。用C语言设计了相应的程序验证了此算法的有效性。  

并发程序验证的时序Petri网方法

并发程序的设计、分析和验证已经成为计算机理论界基础理论研究的方向之一。Petri网和时序逻辑被认 为是探讨该问题较为有效的两个理论工具，但二者都有局限性。该文引用一种新网子类；时序Petri网，描述了并发程序的时序Petri网建模方法；利用网结构描述程序基本框架及保证语句的原子性，通过时序逻辑公式反映程序的共享逻辑变量的赋值变化及时序关系，从而有效地对基本网无法描述的并发程序进行了建模；在此基础上，结合Petri网的可达图分析技术和时序逻辑的演绎公式，分析和验证了并发程序的安全性和活性性质。  

PVM并行程序验证系统的原理与实现

本文主要介绍ＰＶＭ并行程序验证系统的基本原理和实现技术。首先，我们扼要分析ＰＶＭ程序的构成与特点，然后阐述验证系统的理论模型和验证算法；最后，讨论开发过程中的若干关键技术，本系统的研制可为产行程序的自动转换和分析验证提供了一个可视化的运行环境。  

一种构造代码安全性证明的方法

提出一种构造代码安全性证明的新方法.这种方法的基本思想是,在基础逻辑中定义辅助递归函数来帮助构造证明.这种构造方法在不增加系统信任计算基础的情况下可以极大地减轻构造证明的工作量,并且减小安全性证明的规模同时介绍了该方法在一个FPCC系统中的应用.在这个系统中使用该方法使得代码的安全性证明可以自动产生.全部工作的细节已在证明辅助工具Coq中得以实现.  

软件安全漏洞的静态检测技术

软件安全漏洞问题日益严重，静态漏洞检测提供从软件结构和代码中寻找漏洞的方法。该文研究软件漏洞静态检测的两个主要方面：静态分析和程序验证，重点分析词法分析、规则检查、类型推导、模型检测、定理证明和符号执行等方法，将常用的静态检测工具按方法归类，讨论、总结静态检测技术的优势、适用性和发展趋势。  

区间上非线性程序的终止性判定

分析了如下类型程序的终止性:While x∈Ω do {x:=f(x)} end.其中,x是程序变量,Ω是一个区间,f是一个连续函数.这类程序被称为区间上非线性程序.证明了上面程序不终止的必要条件是函数在区间内部或边界上有不动点.如果不动点不在区间的边界,则上述结果是充要条件.仅仅在区间边界上有不动点的情况下,对函数略加限制,也建立了相应结果.特别地,对逐段多项式连续函数程序的终止性给出了完备判定算法.  

Garbage Collector Verification for Proof-Carrying Code

We present the verification of the machine-level implementation of a conservative variant of the standard mark- sweep garbage collector in a Hoare-style program logic.The specification of the collector is given on a machine-level memory model using separation logic,and is strong enough to preserve the safety property of any common mutator program.Our verification is fully implemented in the Coq proof assistant and can be packed immediately as foundational proof-carrying code package.Our work makes important attempt toward building fully certified production-quality garbage collectors.  

XYZ系统在电信领域中的应用

最近几年，在软件工程界内部有一种趋势，这就是开发以面向具体领域的ＣＡＳＥ环境．作为这样的一种ＣＡＳＥ工具，ＸＹＺ系统是由一时序逻辑语言ＸＹＺ／Ｅ和一组基于该语言的工具集构成．在ＸＹＺ系统中有很多的工具，它们被用来满足不同的需要．众所周知，ＳＤＬ（ｓｐｅｃｉｆｉｃａｔｉｏｎａｎｄｄｅｓｃｒｉｐｔｉｏｎｌａｎｇｕａｇｅ）是电信领域中的一个国际标准语言，而且有关基于该语言的环境已在开发，但是有关该语言的验证工作，特别是利用有关时序逻辑语言进行验证的工作还不多．作为一种尝试，本文将利用ＸＹＺ系统中的一个子系统ＸＹＺ／ＶＥＲＩ，对ＳＤＬ所描述的有关电信领域中的例子进行验证．  

基于抽象解释理论的程序验证技术

抽象解释(abstract interpretation)理论是Cousot.P和Cousot.R于1977年提出的程序静态分析时构造和逼近(approxiamation)程序不动点语义的理论.描述了程序语义基于Galois连接的抽象解释理论框架,讨论了基于抽象解释理论的程序变换、程序安全性验证和活性性质验证这3种典型的应用,并指出了基于抽象解释理论的程序验证的主要研究方向.  

操作系统内核程序函数执行上下文的自动检验

函数执行上下文正确性是操作系统内核程序最容易违反且难以检查的正确性性质.应用传统的技术检查该类错误都有一定的困难和局限性.提出一个验证函数执行上下文正确性的框架PRPF,详细描述了其建模过程和相关算法.PRPF相比传统技术的优势有:直接检查源代码、无须编写形式化的验证规约、较低的时空运行开销、良好的可扩展性等等.该技术已应用在Linux内核2.4.20的网络设备驱动程序检查中.应用表明,PRPF能够自动探测程序中所有执行路径,有效地检查函数执行上下文的正确性.实验发现了Linux内核的23处编程错误,另有