A mechanically verified incremental garbage collector

As an application of a system designed for concurrent program verification, we describe a formalisation and mechanical proof of the correctness of Ben-Ari's incremental garbage collection algorithm. The proof system is based on the Manna-Pnueli model of concurrency and is implemented as an extension of the Boyer-Moore prover. The correctness of the garbage collector is represented by two theorems, stating a) that nothing except garbage is ever collected (safety), and b) that all garbage is eventually collected (liveness). We compare our mechanised treatment with several published proofs of the same results.     

基于隔离逻辑的并行程序可靠性验证方法

并行程序验证的复杂性在于执行流程的不确定性以及由此导致的执行规模变大,使得验证的内容和目标之间的关系不明确。为解决该问题,提出一种基于隔离逻辑的并行程序可靠性验证方法。通过变量的执行关系图,描述变量相关的语句及执行关系,将所需验证的程序性质逻辑式转换为变量并行语句序列的逻辑组合式,使得性质表达式与并发程序的语句相关联。根据逻辑组合式确定语句执行序列和前后件逻辑表达式,基于并发隔离逻辑的公理系统对语句执行序列进行验证,并根据验证结果对并发程序进行修改和完善。通过对银行柜台业务办理的功能模块验证结果表明该方法是有效的。     

基于插桩和布尔逻辑的运行时程序验证框架

针对软件测试和静态程序验证中存在的连续性程序执行验证和推理问题,提出一个基于程序插桩和布尔逻辑的运行时程序验证框架——RPA。定义一种用于描述运行时程序性质和规范的动态逻辑语言RPAL,实现自动化插桩以收集运行时程序状态信息,设计一个支持高效验证的句子调度算法。实验结果表明,结合合适的谓词扩展,RPA可以有效地验证和分析软件逻辑,发现潜在的软件错误。     

A multicomputer garbage collector for a single-assignment language

An asynchronous garbage collector for a message-passing multiprocessor (multicomputer) is described. This combines Weighted Reference Counting (WRC) interprocessor collection and tracing intraprocessor collection to permit individual processors to reclaim local storage independently. A novel feature is the integration of Weighted Reference Counting collection and the communication algorithms required to support a global address space in a single assignment language. This significantly reduces communication overhead and space requirements attributable to garbage collection. In addition, techniques are described that avoid the creation of cyclic structures that cannot be reclaimed using WRC. Experimental studies performed in a concurrent logic programming system that incorporates the collector confirm its efficiency and the benefits of integrating garbage collector and language implementation.     

基于分离逻辑的程序验证研究综述

上世纪60-70年代以来,虽然有Floyd-Hoare逻辑的出现,但是使用形式化工具对命令式程序的正确性和可靠性进行自动验证一直被认为是极具挑战性、神圣不可及的工作.上世纪末由于更多的科研投入,特别是微软、IBM等大型公司研发部门的大量人力物力的投入,程序验证方面在本世纪初取得了不少进展,例如用于验证空客代码无运行时错误的ASTRÉE工具,用于Windows设备驱动里关于过程调用的协议验证的SLAM工具.但这些工具并没有考虑动态创建的堆（Heap）：ASTRÉE工具假设待验证代码没有动态创建的堆,也没有递归;SLAM假设待验证系统已经有了内存安全性.事实上很多重要的程序,例如Linux内核、Apache、操作系统设备驱动程序等等,都涉及到对动态创建堆的操作.如何对这类操作堆的程序（heap-manipulating programs）进行自动验证仍然是个难题.2001-2002年分离逻辑（separation logic）提出后,其分离（separation）思想和相应的框（frame）规则使得局部推理（local reasoning）可以很好地应用到程序验证中.自2004年以来,基于分离逻辑对操作动态创建堆的程序进行自动验证方面的研究有了很大的进展,取得了很多令人瞩目的成果,例如SpaceInvader/Abductor、Slayer、HIP/SLEEK、CSL等工作.本文将着重对这方面的部分重要工作进行阐述.     

基于智能指针的垃圾收集器的研究与实现

内存泄漏是软件开发过程中最令人棘手的问题之一。通常,使用垃圾收集机制自动进行内存管理,以减轻程序员的负担。通过研究智能指针以及现有垃圾收集机制的工作原理,本文首先设计出一个基于c＋＋智能指针的垃圾收集器。实验结果表明,该垃圾收集器不仅满足了应用程序的要求,且具有良好的可扩展性。对于使用c＋＋等保守式程序设计语言进行大型软件的开发而言,该垃圾收集器具有一定的理论价值和实用价值。     

步进索引模型下的语义及其形式化

霍尔逻辑作为计算机程序的逻辑基础,可以用于描述一般程序的验证.分离逻辑作为霍尔逻辑的扩展,可以支持很多现代程序语言中的高阶特性.步进索引模型被用于定义自递归谓词.步进索引逻辑被广泛应用于各种基于交互式定理证明器的程序验证工具中,然而,基于步进索引逻辑的推理却比经典逻辑复杂、繁琐.事实上,也可以在步进索引模型上定义更加简洁清晰的、与“步数”无关的经典逻辑体系下的非步进索引程序语义.人们希望找到步进索引逻辑和非步进索引逻辑之间的关系,但发现两种逻辑并不等价.对实际的程序验证工作中涉及的命题进行归纳总结,找出它们共同的特征,给出关于程序状态的断言的约束条件;分别定义步进索引逻辑和非步进索引逻辑体系中断言的语义,并证明在该约束条件下两种语义的等价性;在Coq中,形式化以上所有定义和证明;最后,对未来值得关注的研究方向进行初步探讨.     

一个Windows应用程序的垃圾回收器

为减少长期运行的Windows应用程序持续堆内存泄漏而造成的系统性能损失,设计并实现了一个运行时自动垃圾回收器RT-AGC。RT-AGC采用传统Mark—Sweep算法的一个变种,对回收触发条件进行改进,使其具有更大的灵活性。利用Windows下应用程序的存储结构和系统API函数,通过扫描可能存储指针变量的区域,RT—AGC可以在应用程序运行时检测并处理内存泄漏,而不需要对目标应用程序重新编译或链接。文中描述了所采用的关键算法流程和主要实现技术,并编写了测试程序对RT—AGC的回收效果进行验证。实验证明可以有效地抑制应用程序的内存泄漏。     

Nonintrusive Cloning Garbage Collection with Stock Operating System Support

It is well accepted that automatic garbage collection simplifies programming, promotes modularity, and reduces development effort. However it is commonly believed that these advantages do not counteract the perceived price: excessive overheads, possible long pause times while garbage collections occur, and the need to modify existing code. Even though there are publically available garbage collector implementations that can be used in existing programs, they do not guarantee short pauses, and some modification of the application using them is still required. In this paper we describe a snapshot-at-beginning concurrent garbage collector algorithm and its implementation. This algorithm guarantees short pauses, and can be easily implemented on stock UNIX-like operating systems. Our results show that our collector performs comparable to other garbage collection implementations on uniprocessor machines and outperforms similar collectors on multiprocessor machines. We also show our collector to be competitive in performance with explicit deallocation. Our collector has the added advantage of being non-intrusive. Using a dynamic linking technique and effective root set inferencing, we have been able to successfully run our collector even in commercial programs where only the binary executable and no source code is available. In this paper we describe our algorithm, its implementation, and provide both an algorithmic and a performance comparison between our collector and other similar garbage collectors. ©1997 by John Wiley & Sons, Ltd.     

Yama: a scalable generational garbage collector for Java in multiprocessor systems

The current state-of-the-art generational garbage collector pauses all the program threads when it performs young and old generation garbage collection. As the number of program threads increases, the delay due to garbage collection also increases, thus restricting the scalability of the collector. In order to improve the scalability and reduce the pause time, an on-the-fly generational garbage collector called Yama is proposed for multiprocessor systems. This uses the on-the-fly deferred reference counting in the young generation and the DLG (Doligez Leroy Gonthier) on-the-fly mark and sweep garbage collector in the old generation. We have proposed and experimented with two novel variations of the on-the-fly deferred reference counting called Chitragupt1 and Chitragupt2 in the young generation. Yama does not pause all the application threads simultaneously. An adaptive tenuring policy based on object reference count and survival rate is also proposed. Yama has been implemented in the IBM Jikes RVM (research virtual machine). The above claims are supported with experimental results for standard benchmark programs. The results show that Yama has an extremely low pause time in both the young and the old generation. The pause time reduction results in better response times for the user programs.     

A Shape Graph Logic and A Shape System

Analysis and verification of pointer programs are still difficult problems so far. This paper uses a shape graph logic and a shape system to solve these problems in two stages. First, shape graphs at every program point are constructed using an analysis tool. Then, they are used to support the verification of other properties （e.g., orderedness）. Our prototype supports automatic verification of programs manipulating complex data structures such as splay trees, treaps, AVL trees and AA trees, etc. The proposed shape graph logic, as an extension to Hoare logic, uses shape graphs directly as assertions. It can be used in the analysis and verification of programs manipulating mutable data structures. The benefit using shape graphs as assertions is that it is convenient for acquiring the relations between pointers in the verification stage. The proposed shape system requires programmers to provide lightweight shape declarations in recursive structure type declarations. It can help rule out programs that construct shapes deviating from what programmers expect （reflected in shape declarations） in the analysis stage. As a benefit, programmers need not provide specifications （e.g., pre-/post-conditions, loop invariants） about pointers. Moreover, we present a method doing verification in the second stage using traditional Hoare logic rules directly by eliminating aliasing with the aid of shape graphs. Thus, verification conditions could be discharged by general theorem provers.     

基于交互式定理证明的并发程序验证工作综述

并发程序与并发系统可以拥有非常高的执行效率和相对串行系统较快的响应速度,在现实中有着非常广泛的应用。但是并发程序与并发系统往往难以保证其实现的正确性,实际应用程序运行中的错误会带来严重的后果。同时,并发程序执行时的不确定性会给其正确性验证带来巨大的困难。在形式化验证方法中,人们可以通过交互式定理证明器严格地对并发程序进行验证。本文对在交互式定理证明中可用于描述并发程序正确性的验证目标进行总结,它们包括霍尔三元组、可线性化、上下文精化和逻辑原子性。交互式定理证明方法中常用程序逻辑对程序进行验证,本文分析了基于并发分离逻辑、依赖保证逻辑、关系霍尔逻辑等理论研究的系列成果与相应形式化方案,并对使用了这些方法的程序验证工具和程序验证成果进行了总结。     

一种基于LTL性质的面向对象并发程序切片方法

为了缩减程序验证的状态空间,针对面向对象程序的并发机制,定义了程序中存在的依赖关系,提出一种从待验证的线性时序逻辑(LTL)性质中提取出切片准则对程序进行切片的方法。切片后的程序与原程序对待验证的LTL性质具有相同的可满足性,而其对应的状态转换图中的状态个数明显减少。     

Scheduling of hard real-time garbage collection

Automatic memory management or garbage collection greatly simplifies development of large systems. However, garbage collection is usually not used in real-time systems due to the unpredictable temporal behavior of current implementations of a garbage collector. In this paper we propose a real-time garbage collector that can be scheduled like a normal real-time thread with a deadline monotonic assigned priority. We provide an upper bound for the collector period so that the application threads will never run out of memory. Furthermore, we show that the restricted execution model of the Safety Critical Java standard simplifies root scanning and reduces copying of static data. Our proposal has been implemented and evaluated in the context of the Java processor JOP.     

Time required for garbage collection in retention block-structured languages

This paper investigates the time requirements for an implementation of retention block-structured languages that uses a garbage collector as its sole means for recovering inaccessible storage. The usual three-pass markcompactify-and-update garbage collector is optimized to eliminate the need for the third pass in the event that the executed program is lifetime well-stacking.Supported (in part) by the United States Energy Research and Development Administration, Contract No. E(04-3)-34, PA 214, and (in part) by the National Science Foundation, Grant No. DCR75-08659.     

Verifying Contextual Refinement with Ownership Transfer

Contextual refinement is a compositional approach to compositional verification of concurrent objects.There has been much work designing program logics to prove the contextual refinement between the object implementation and its abstract specification.However,these program logics for contextual refinement verification cannot support objects with resource ownership transfer,which is a common pattern in many concurrent objects,such as the memory management module in OS kernels,which transfers the allocated memory block between the object and clients.In this paper,we propose a new approach to give abstract and implementation independent specifications to concurrent objects with ownership transfer.We also design a program logic to verify contextual refinement of concurrent objects w.r.t.their abstract specifications.We have successfully applied our logic to verifying an implementation of the memory management module,where the implementation is an appropriately simplified version of the original version from a real-world preemptive OS kernel.     

动态存储管理安全验证的Coq实现

随着软件规模和复杂度的日益提升,软件安全的问题变得越来越严峻,同时有越来越多的研究工作集中在高可信软件的开发上 .由于类型系统表达能力的不足,现有的研究不触及底层软件的验证 .由于Hoare逻辑更好的表达能力,采用Hoare逻辑风格的推理,在汇编语言级别,使用Coq形式化与定理证明工具可以实现一个经过安全验证的动态存储管理函数库,这是程序验证技术一次有意义的实践 .实践表明,程序验证技术可以应用到高可信软件的开发上 .     

程序断言的半自动生成及证明逻辑

如何生成程序断言对于软件验证十分重要。传统方法要求既要对程序结构有深入地把握又要做繁复的Hoare三元式推演工作。为了摆脱这些琐碎事宜,将致力于探讨一种半自动的断言生成方法。为便于理解,讨论主要以XYZ/VERI系统为论述背景。XYZ/VERI 系统是一面向时序逻辑程序语言如XYZ/SE 的类Hoare逻辑交互式验证系统。该工作一定意义上完善了其验证功能。     

Automated Verification of Functional Correctness of Race-Free GPU Programs

We study an automated verification method for functional correctness of parallel programs running on graphics processing units (GPUs). Our method is based on Kojima and Igarashi’s Hoare logic for GPU programs. Our algorithm generates verification conditions (VCs) from a program annotated by specifications and loop invariants, and passes them to off-the-shelf SMT solvers. It is often impossible, however, to solve naively generated VCs in reasonable time. A main difficulty stems from quantifiers over threads due to the parallel nature of GPU programs. To overcome this difficulty, we additionally apply several transformations to simplify VCs before calling SMT solvers. Our implementation successfully verifies correctness of several GPU programs, including matrix multiplication optimized by using shared memory. In contrast to many existing verification tools for GPU programs, our verifier succeeds in verifying fully parameterized programs: parameters such as the number of threads and the sizes of matrices are all symbolic. We empirically confirm that our simplification heuristics is highly effective for improving efficiency of the verification procedure.     

An Overview of the Runtime Verification Tool Java PathExplorer

We present an overview of the Java PathExplorer runtime verification tool, in short referred to as JPAX. JPAX can monitor the execution of a Java program and check that it conforms with a set of user provided properties formulated in temporal logic. JPAX can in addition analyze the program for concurrency errors such as deadlocks and data races. The concurrency analysis requires no user provided specification. The tool facilitates automated instrumentation of a program's bytecode, which when executed will emit an event stream, the execution trace, to an observer. The observer dispatches the incoming event stream to a set of observer processes, each performing a specialized analysis, such as the temporal logic verification, the deadlock analysis and the data race analysis. Temporal logic specifications can be formulated by the user in the Maude rewriting logic, where Maude is a high-speed rewriting system for equational logic, but here extended with executable temporal logic. The Maude rewriting engine is then activated as an event driven monitoring process. Alternatively, temporal specifications can be translated into automata or algorithms that can efficiently check the event stream. JPAX can be used during program testing to gain increased information about program executions, and can potentially furthermore be applied during operation to survey safety critical systems.