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.     

Real-time refinement in Manna and Pnueli's temporal logic

A refinement calculus for the development of real-time systems is presented. The calculus is based upon a wide-spectrum language called TAM (the Temporal Agent Model), within which both functional and timing properties can be expressed in either abstract or concrete terms. A specification oriented semantics is given for the language. Program development is considered as a refinement process i.e. thecalculation of a structured program from an unstructured specification. An example program is developed.     

通过抽象程序证明复杂具体程序

本文描述了证明抽象程序和具体程序满足一致性关系的方法.抽象程序使用抽象数据结构（ADTs）如set、list、map及其上的操作.具体程序使用类C语言中的类型.抽象程序和具体程序一致性证明需要用户给出抽象变量和具体变量的关系,抽象程序程序点和具体程序程序点的对应关系.基于对应关系,抽象程序和具体程序一致性证明可以分解,从而容易并可能自动证明.     

Calculating upward and downward simulations of state-based specifications

This paper concerns calculational methods of refinement in state-based specification languages. Data refinement is a well-established technique for transforming specifications of abstract data types into ones, which are closer to an eventual implementation. The conditions under which a transformation is a correct refinement are encapsulated into two simulation rules: downward and upward simulations.One approach for refining an abstract system is to specify the concrete data type, and then attempt to verify that it is a valid refinement of the abstract type. An alternative approach is to calculate the concrete specification based upon the abstract specification and a retrieve relation, which links the abstract and concrete states. In this paper we generalise existing calculational methods for downward simulations and derive similar results for upward simulations; we also document their use and application in a particular specification language, namely Z.     

Relational concurrent refinement part III: traces,partial relations and automata

Data refinement in a state-based language such as Z is defined using a relational model in terms of the behaviour of abstract programs. Downward and upward simulation conditions form a sound and jointly complete methodology to verify relational data refinements, which can be checked on an event-by-event basis rather than per trace. In models of concurrency, refinement is often defined in terms of sets of observations, which can include the events a system is prepared to accept or refuse, or depend on explicit properties of states and transitions. By embedding such concurrent semantics into a relational framework, eventwise verification methods for such refinement relations can be derived. In this paper, we continue our program of deriving simulation conditions for process algebraic refinement by defining further embeddings into our relational model: traces, completed traces, failure traces and extension. We then extend our framework to include various notions of automata based refinement.     

A framework for automated and certified refinement steps

The refinement calculus provides a methodology for transforming an abstract specification into a concrete implementation, by following a succession of refinement rules. These rules have been mechanized in theorem provers, thus providing a formal and rigorous way to prove that a given program refines another one. In a previous work, we have extended this mechanization for object-oriented programs, where the memory is represented as a graph, and we have integrated our approach within the rCOS tool, a model-driven software development tool providing a refinement language. Hence, for any refinement step, the tool automatically generates the corresponding proof obligations and the user can manually discharge them, using a provided library of refinement lemmas. In this work, we propose an approach to automate the search of possible refinement rules from a program to another, using the rewriting tool Maude. Each refinement rule in Maude is associated with the corresponding lemma in Isabelle, thus allowing the tool to automatically generate the Isabelle proof when a refinement rule can be automatically found. The user can add a new refinement rule by providing the corresponding Maude rule and Isabelle lemma.     

Renaming Detection

Finding changed identifiers is important for understanding the difference between two versions of a program and for detecting and resolving conflicts while merging variants of a program together. Standard practice for differencing and merging relies on line based techniques that do not recognize renamed identifiers. The design and implementation of a tool to automatically detect renamed identifiers between two versions of a program is presented. The system uses an abstract representation of language constructs to enable language awareness without introducing language dependence. Modules for Java and Scheme have been written. The detector works with multiple file pairs, taking into account renamings that span several files. A case study is presented that demonstrates proof of concept. The detector is part of a suite of intelligent differencing and merging programs that exploit the static semantics of programming languages.     

Code obfuscation against abstraction refinement attacks

Code protection technologies require anti reverse engineering transformations to obfuscate programs in such a way that tools and methods for program analysis become ineffective. We introduce the concept of model deformation inducing an effective code obfuscation against attacks performed by abstract model checking. This means complicating the model in such a way a high number of spurious traces are generated in any formal verification of the property to disclose about the system under attack.We transform the program model in order to make the removal of spurious counterexamples by abstraction refinement maximally inefficient. Because our approach is intended to defeat the fundamental abstraction refinement strategy, we are independent from the specific attack carried out by abstract model checking. A measure of the quality of the obfuscation obtained by model deformation is given together with a corresponding best obfuscation strategy for abstract model checking based on partition refinement.     

Encoding, Decoding and Data Refinement

Data refinement is the systematic replacement of a data structure with another one in program development. Data refinement between program statements can on an abstract level be described as a commutativity property where the abstraction relationship between the data structures involved is represented by an abstract statement (a decoding). We generalise the traditional notion of data refinement by defining an encoding operator that describes the least (most abstract) data refinement with respect to a given abstraction. We investigate the categorical and algebraic properties of encoding and describe a number of special cases, which include traditional notions of data refinement. The dual operator of encoding is decoding, which we investigate and give an intuitive interpretation to. Finally we show a number of applications of encoding and decoding. Received May 1999 / Accepted in revised form November 2000     

Finding concurrency-related bugs using random isolation

This paper concerns automatically verifying safety properties of concurrent programs. In our work, the safety property of interest is to check for multi-location data races in concurrent Java programs, where a multi-location data race arises when a program is supposed to maintain an invariant over multiple data locations, but accesses/updates are not protected correctly by locks. The main technical challenge that we address is how to generate a program model that retains (at least some of) the synchronization operations of the concrete program, when the concrete program uses dynamic memory allocation. Static analysis of programs typically begins with an abstraction step that generates an abstract program that operates on a finite set of abstract objects. In the presence of dynamic memory allocation, the finite number of abstract objects of the abstract program must represent the unbounded number of concrete objects that the concrete program may allocate, and thus by the pigeon-hole principle some of the abstract objects must be summary objects—they represent more than one concrete object. Because abstract summary objects represent multiple concrete objects, the program analyzer typically must perform weak updates on the abstract state of a summary object, where a weak update accumulates information. Because weak updates accumulate rather than overwrite, the analyzer is only able to determine weak judgements on the abstract state, i.e., that some property possibly holds, and not that it definitely holds. The problem with weak judgements is that determining whether an interleaved execution respects program synchronization requires the ability to determine strong judgements, i.e., that some lock is definitely held, and thus the analyzer needs to be able to perform strong updates—an overwrite of the abstract state—to enable strong judgements. We present the random-isolation abstraction as a new principle for enabling strong updates of special abstract objects. The idea is to associate with a program allocation site two abstract objects, r^\sharp{r^{\sharp}} and o^\sharp{o^{\sharp}} , where r^\sharp{r^{\sharp}} is a non-summary object and o^\sharp{o^{\sharp}} is a summary object. Abstract object r^\sharp{r^{\sharp}} models a distinguished concrete object that is chosen at random in each program execution. Because r^\sharp{r^{\sharp}} is a non-summary object—i.e, it models only one concrete object—strong updates are able to be performed on its abstract state. Because which concrete object r^\sharp{r^{\sharp}} models is chosen randomly, a proof that a safety property holds for r^\sharp{r^{\sharp}} generalizes to all objects modeled by o^\sharp{o^{\sharp}} . We implemented the random isolation abstraction in a tool called Empire, which verifies atomic-set serializability of concurrent Java programs (atomic-set serializability is one notion of multi-location data-race freedom). Random isolation allows Empire to track lock states in ways that would not otherwise have been possible with conventional approaches.     

基于XYZ／E的CA认证系统描述与求精

时序逻辑语言XYZ／E在统一的逻辑框架下既能表示静态语义又能表示动态语义，可以实现从抽象描述到可执行程序的平滑过渡。本文建立了CA认证系统组件求精模型，对CA和RA组件用XYZ／E进行了描述和求精。     

Modular Pluggable Analyses for Data Structure Consistency

Hob is a program analysis system that enables the focused application of multiple analyses to different modules in the same program. In our approach, each module encapsulates one or more data structures and uses membership in abstract sets to characterize how objects participate in data structures. Each analysis verifies that the implementation of the module 1) preserves important internal data structure consistency properties and 2) correctly implements a set algebra interface that characterizes the effects of operations on the data structure. Collectively, the analyses use the set algebra to 1) characterize how objects participate in multiple data structures and to 2) enable the interanalysis communication required to verify properties that depend on multiple modules analyzed by different analyses. We implemented our system and deployed several pluggable analyses, including a flag analysis plug-in for modules in which abstract set membership is determined by a flag field in each object, a PALE shape analysis plug-in, and a theorem proving plug-in for analyzing arbitrarily complicated data structures. Our experience shows that our system can effectively 1) verify the consistency of data structures encapsulated within a single module and 2) combine analysis results from different analysis plug-ins to verify properties involving objects shared by multiple modules analyzed by different analyses     

A Verified SAT Solver Framework with Learn,Forget, Restart,and Incrementality

We developed a formal framework for conflict-driven clause learning (CDCL) using the Isabelle/HOL proof assistant. Through a chain of refinements, an abstract CDCL calculus is connected first to a more concrete calculus, then to a SAT solver expressed in a functional programming language, and finally to a SAT solver in an imperative language, with total correctness guarantees. The framework offers a convenient way to prove metatheorems and experiment with variants, including the Davis–Putnam–Logemann–Loveland (DPLL) calculus. The imperative program relies on the two-watched-literal data structure and other optimizations found in modern solvers. We used Isabelle’s Refinement Framework to automate the most tedious refinement steps. The most noteworthy aspects of our work are the inclusion of rules for forget, restart, and incremental solving and the application of stepwise refinement.     

A practical approach to data modelling in spatial applications

The storage and manipulation of spatial data requires a different style of support from that normally found in commercial database systems. This paper explores the use of the functional data model and the high level language Daplex to provide an integrated tool for the conceptual modelling of spatial data and the manipulation of data values. Importance is attached to allowing dynamic schema definition and to the provision of abstract data types to support spatial objects. The implementation comprises three separate modules and uses an underlying relational DBMS to store all metadata and data values. This modular design has enabled the user interface, Daplex language and storage aspects of the software to be developed independently, creating a system which has already proved to be easily portable. Consideration has also been given to ways of improving system performance.     

The Definition Mechanism for Standard PL/I

The mechanism used to define the programming language PL/I in the recently adopted American National Standard is presented. This method provides a rigorous though semiformal specification of the language. If uses the model of translation of programs into an abstract form to define the context-free and context-sensitive syntax. The semantics are defined by the interpretation of the abstract form of the program on a hypothetical machine. The method and metalanguage are presented along with several small examples to illustrate the definition technique's features. The complete definition process is shown by the definition of a small example language.     

两次数据精化的形式化软件开发方法

提出了一种从数据精化、过程精化、再数据精化的两次数据精化的形式化软件开发方法。传统Z规约数据精化很复杂。该文先采用过程写出初始规范,对模式进行第一次数据精化,然后把它转换为Z模式,再进行过程精化。最后再数据精化到且标代码。以常见动态Web网页脚本语言PHP为例,阐述了该方法。并为此写了一套从过程到Z模式的转化规则,以及精化到PHP的精化规则。     

Counterexample-guided abstraction refinement for linear programs with arrays

Predicate abstraction refinement is one of the leading approaches to software verification. The key idea is to abstract the input program into a Boolean Program (i.e. a program whose variables range over the Boolean values only and model the truth values of predicates corresponding to properties of the program state), and refinement searches for new predicates in order to build a new, more refined abstraction. Thus Boolean programs are commonly employed as a simple, yet useful abstraction. However, the effectiveness of predicate abstraction refinement on programs that involve a tight interplay between data-flow and control-flow is still to be ascertained. We present a novel counterexample guided abstraction refinement procedure for Linear Programs with arrays, a fragment of the C programming language where variables and array elements range over a numeric domain and expressions involve linear combinations of variables and array elements. In our procedure the input program is abstracted w.r.t. a family of sets of array indices, the abstraction is a Linear Program (without arrays), and refinement searches for new array indices. We use Linear Programs as the target of the abstraction (instead of Boolean programs) as they allow to express complex correlations between data and control. Thus, unlike the approaches based on predicate abstraction, our approach treats arrays precisely. This is an important feature as arrays are ubiquitous in programming. We provide a precise account of the abstraction, Model Checking, and refinement processes, discuss their implementation in the EUREKA tool, and present a detailed analysis of the experimental results confirming the effectiveness of our approach on a number of programs of interest.     

Approximate reasoning about the semantic effects of program changes

It is pointed out that the incremental cost of a change to a program is often disproportionately high because of inadequate means of determining the semantic effects of the change. A practical logical technique for finding the semantic effects of changes through a direct analysis of the program is presented. The programming language features considered include parametrized modules, procedures, and global variables. The logic described is approximate in that weak (conservative) results sometimes are inferred. Isolating the exact effects of a change is undecidable in general. The basis for an approximation is a structural interpretation of the information-flow relationships among program objects. The approximate inference system is concise, abstract, extensible, and decidable, giving it significant advantages over the main alternative formalizations. The authors' implementation of the logic records the justification for each dependency to facilitate the interpretation of results     

Demonstrational interfaces: A step beyond direct manipulation

Demonstrational interfaces, interfaces that let the user perform actions on concrete example objects while constructing an abstract program, thus letting the user create parameterized procedures and objects without learning a programming language, are discussed. The motivations for and problems associated with demonstrational interfaces are presented. A survey of the various types of interfaces is also presented. Areas that would benefit from demonstrational technology, including general-purpose programming, visualization, macros for direct-manipulation interfaces, drawing packages, text editing and formatting, and user interface development environments, are discussed. Research issues involving demonstrational interfaces are reviewed