The KeY tool

KeY is a tool that provides facilities for formal specification and verification of programs within a commercial platform for UML based software development. Using the KeY tool, formal methods and object-oriented development techniques are applied in an integrated manner. Formal specification is performed using the Object Constraint Language (OCL), which is part of the UML standard. KeY provides support for the authoring and formal analysis of OCL constraints. The target language of KeY based development is Java Card DL, a proper subset of Java for smart card applications and embedded systems. KeY uses a dynamic logic for Java Card DL to express proof obligations, and provides a state-of-the-art theorem prover for interactive and automated verification. Apart from its integration into UML based software development, a characteristic feature of KeY is that formal specification and verification can be introduced incrementally.     

Coloured Petri net refinement specification and correctness proof with Coq

In this work, we address the issue of the formal proof (using the proof assistant Coq) of refinement correctness for symmetric nets, a subclass of coloured Petri nets. We provide a formalisation of the net models, and of their type refinement in Coq. Then the Coq proof assistant is used to prove the refinement correctness lemma. An example adapted from a protocol example illustrates our work.     

Unifying classes and processes

Previously, we presented Circus, an integration of Z, CSP, and Morgan’s refinement calculus, with a semantics based on the unifying theories of programming. Circus provides a basis for development of state-rich concurrent systems; it has a formal semantics, a refinement theory, and a development strategy. The design of Circus is our solution to combining data and behavioural specifications. Here, we further explore this issue in the context of object-oriented features. Concretely, we present an object-oriented extension of Circus called OhCircus. We present its syntax, describe its semantics, explain the formalisation of method calls, and discuss our approach to refinement.     

A WSDL-based type system for asynchronous WS-BPEL processes

We tackle the problem of providing rigorous formal foundations to current software engineering technologies for web services, and especially to WSDL and WS-BPEL, two of the most used XML-based standard languages for web services. We focus on a simplified fragment of WS-BPEL sufficiently expressive to model asynchronous interactions among web services in a network context. We present this language as a process calculus-like formalism, that we call ws-calculus, for which we define an operational semantics and a type system. The semantics provides a precise operational model of programs, while the type system forces a clean programming discipline for integrating collaborating services. We prove that the operational semantics of ws-calculus and the type system are ‘sound’ and apply our approach to some illustrative examples. We expect that our formal development can be used to make the relationship between WS-BPEL programs and the associated WSDL documents precise and to support verification of their conformance.     

Sound refactorings

Refactoring consists in restructuring an object-oriented program without changing its behaviour. In this paper, we present refactorings as transformation rules for programs written in a refinement language inspired on Java that allows reasoning about object-oriented programs and specifications. A set of programming laws is available for the imperative constructs of this language as well as for its object-oriented features; soundness of the laws is proved against a weakest precondition semantics. The proof that the refactoring rules preserve behaviour (semantics) is accomplished by the application of these programming laws and data simulation. As illustration of our approach to refactoring, we use our rules to restructure a program to be in accordance with a design pattern.     

Mechanised support for sound refinement tactics

ArcAngel is a tactic language devised to facilitate and automate program developments using Morgan’s refinement calculus. It is especially well suited for the specification of high-level refinement strategies, and equipped with a formal semantics that additionally permits reasoning about tactics. In this paper, we present an implementation of ArcAngel for the ProofPower theorem prover. We discuss the underlying design, explain how it implements the semantics of ArcAngel, and examine the interplay between ArcAngel tactics and the native reasoning support of the prover. We also discuss several extensions of ArcAngel that have been entailed by our implementation effort. They are of practical importance and provide a unification of the related tactic languages Angel and ArcAngel C. Our main result is a mechanisation that reflects directly the ArcAngel semantics, and can be used with any programming model for refinement. The approach can be used to support other formal tactic languages using other theorem provers.     

Integration of informal and formal development of object-oriented safety-critical software

The KeY system allows for the integrated informal and formal development of object-oriented Java software. In this paper we report on a major industrial case study involving safety-critical software for the computation of a particular kind of railway timetable used by train conductors. Our case study includes formal specification of requirements both on the analysis and the implementation level. Particular emphasis in our research is placed on the challenge to make authoring and maintenance of formal specifications easier. We demonstrate that the technique of specification patterns as implemented in KeY for the language OCL yields significant improvements.     

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.     

SCHOOL: a Small Chorded Object-Oriented Language

Chords are a declarative synchronisation construct based on the Join-calculus, available in the programming language C-omega. To our knowledge, chords have no formal model in an object-oriented setting. In this paper we suggest SCHOOL, a formal model for an imperative, object-oriented language with chords. We give an operational semantics and type system, and can prove soundness of the type system.     

The behavioural semantics of Event-B refinement

Event-B provides a flexible framework for stepwise system development via refinement. The framework supports steps for (a) refining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can be indicated as convergent (to be made internal) or anticipated (treatment deferred to a later refinement step). All such steps are accompanied with precise proof obligations. However, no behavioural semantics has been provided to validate the proof obligations, and no formal justification has previously been given for the application of these rules in a refinement chain. Behavioural semantics expresses a clear relationship between the first and last machines in a refinement chain. The framework we present provides a coherent justification for Abrial’s approach to refinement in Event-B, and its generalisation to interface extension: adding events to the interface. In this paper, we give a behavioural semantics for Event-B refinement, with a treatment for the first time of splitting events and of anticipated events, adding to the well-understood treatment of convergent events. To this end, we define a CSP semantics for Event-B and show how the different forms of Event-B refinement can be captured as CSP refinement. It turns out that the appropriate CSP refinement relationship is influenced by the particular Event-B development strategy taken. We present two such strategies, one allowing, the other disallowing interface extensions.     

An approach to high-level language bindings to XML

Values of existing typed programming languages are increasingly generated and manipulated outside the language jurisdiction. Instead, they often occur as fragments of XML documents, where they are uniformly interpreted as labelled trees in spite of their domain-specific semantics. In particular, the values are divorced from the high-level type with which they are conveniently, safely, and efficiently manipulated within the language.We propose language-specific mechanisms which extract language values from arbitrary XML documents and inject them in the language. In particular, we provide a general framework for the formal interpretation of extraction mechanisms and then instantiate it to the definition of a mechanism for a sample language core L. We prove that such mechanism can be built by giving a sound and complete algorithm that implements it.The values, types, and type semantics of L are sufficiently general to show that extraction mechanisms can be defined for many existing typed languages, including object-oriented languages. In fact, extraction mechanisms for a large class of existing languages can be directly derived from L's. As a proof of this, we introduce the SNAQue prototype system, which transforms XML fragments into CORBA objects and exposes them across the ORB framework to any CORBA-compliant language.     

形式描述语言COOZ的集成支撑环境COOZ—Tools

介绍支持面向对象的形式描述语言ＣＯＯＺ的集成支撑环境ＣＯＯＺ－Ｔｏｏｌｓ的设计原则、系统结构、功能、特点和关键的实现技术。ＣＯＯＺ是Ｚ语言的面向对象扩充,从而将形式化语言和面向对象机制有机结合起来。ＣＯＯＺ－Ｔｏｏｌｓ支持基于ＣＯＯＺ的软件开发,它主要由如下工具组成：规格说明编辑、浏览工具、语法语义检查工具、联机帮助工具、项目管理工具。     

Nivel: a metamodelling language with a formal semantics

Much work has been done to clarify the notion of metamodelling and new ideas, such as strict metamodelling, distinction between ontological and linguistic instantiation, unified modelling elements and deep instantiation, have been introduced. However, many of these ideas have not yet been fully developed and integrated into modelling languages with (concrete) syntax, rigorous semantics and tool support. Consequently, applying these ideas in practice and reasoning about their meaning is difficult, if not impossible. In this paper, we strive to add semantic rigour and conceptual clarity to metamodelling through the introduction of Nivel, a novel metamodelling language capable of expressing models spanning an arbitrary number of levels. Nivel is based on a core set of conceptual modelling concepts: class, generalisation, instantiation, attribute, value and association. Nivel adheres to a form of strict metamodelling and supports deep instantiation of classes, associations and attributes. A formal semantics is given for Nivel by translation to weight constraint rule language (WCRL), which enables decidable, automated reasoning about Nivel. The modelling facilities of Nivel and the utility of the formalisation are demonstrated in a case study on feature modelling.

Deriving Proof Rules from Continuation Semantics

We claim that a continuation style semantics of a programming language can provide a starting point for constructing its proof system. The basic idea is to see weakest preconditions as a particular instance of continuation style semantics, hence to interpret correctness assertions (e.g. Hoare triples {p} C {r}) as inequalities over continuations. This approach also shows a correspondence between labels in a program and annotations. Received July 1997 / Accepted in revised form August 1999     

Smalltalk—80的基本概念和抽象文法

Smalltalk—80是原型的面向对象程序设计语言和环境,其中所体现的面向对象方法学已广泛应用于计算机科学的各个领域。我们已经完成除进程之外的所有Smalltalk成份的指称语义描述。作为系列文章的首篇,本文简要介绍Smalltalk的基本概念,并给出其完整的抽象文法,从而为准确地理解Smalltalk,正确地描述其形式语义奠定良好的基础。     

An interpretation of typed OOP in a language with state

In this paper we give semantics toLoop, an expressive typed object-oriented programming language with updatable instance variables.Loop has a rich type system that allows for the typing of methods operating over an open-ended self type. We prove the type system given is sound;i.e., well-typed programs do not experience message not understood errors. The semantics ofLoop is given by a translation into a state-based language,Soop, that contains reference cells, records, and a form of F-bounded polymorphic type.Partially supported by NSF grant CCR-9109070Partially supported by AFOSR grant F49620-93-1-0169     

Automated verification of access control policies using a SAT solver

Managing access control policies in modern computer systems can be challenging and error-prone. Combining multiple disparate access policies can introduce unintended consequences. In this paper, we present a formal model for specifying access to resources, a model that encompasses the semantics of the xacml access control language. From this model we define several ordering relations on access control policies that can be used to automatically verify properties of the policies. We present a tool for automatically verifying these properties by translating these ordering relations to Boolean satisfiability problems and then applying a sat solver. Our experimental results demonstrate that automated verification of xacml policies is feasible using this approach. This work is supported by NSF grants CCF-0614002 and CCF-0716095.     

A development environment for an object specification language

Techniques for the development of reliable information systems on the basis of their formal specification are the main concern in the project. Our work focuses on the specification language TROLL light which allows one to describe the part of the world to be modeled as a community of concurrently existing and communicating objects. Our specification language comes with an integrated, open development environment. The task of this environment is to give support for the creation of correct information systems. Two important ingredients of the environment are the animator and the proof support system     

Verifying BPEL-like programs with Hoare logic

The WS-BPEL language has recently become a de facto standard for modeling Web-based business processes. One of its essential features is the fully programmable compensation mechanism. To understand it better, many recent works have mainly focused on formal semantic models for WS-BPEL. In this paper, we make one step forward by investigating the verification problem for business processes written in BPEL-like languages. We propose a set of proof rules in Hoare-logic style as an axiomatic verification system for a BPEL-like core language containing key features such as data states, fault and compensation handling. We also propose a big-step operational semantics which incorporates all these key features. Our verification rules are proven sound with respect to this underlying semantics. The application of the verification rules is illustrated via the proof search process for a nontrivial example.     

The Structure and Semantics of an Object-Oriented Logic Programming Language: SCKE

The development of the object-oriented paradigm has suffered from the lack of any generally accepted formal foundations for its semantic definition.To address this issue,we propose the development of the logic-based semantics of the object-oriented paradigm.By combining the logic-with the object-oriented paradigm of computing first,this paper discusses formally the semantics of a quite purely object-oriented logic paradigm in terms of proof theory,model theory and fixpoint theory from the viewpoint of logic.The operational and declarative semantics is given.And then the correspondence between soundness and completeness has been discussed formally.