Publications

 This report presents and justifies the idea of orthogonal formalisation of Common Object Request Broker Architecture (CORBA). Considering CORBA in a general context of specification and implementation barriers between request and an operation, we construct two independent specification hierarchies, characterising correspondingly broker implementation and object model aspects of CORBA. Though being orthogonal, the hierarchies can be easily composed resulting in a number of CORBA specifications of different abstraction levels, focused on different classes of CORBA features. It allows us to describe CORBA in a uniform and modular manner. We also considered how different CORBA features can be defined on top of the basic specifications. We assume that in such a way it is possible to characterise other CORBA dimensions (in particular, CORBA services), coming up to formal treatment of the general transparency concept in the context of system integration.

 The report describes the concept of an integrated CORBA/RAISE environment for addressing problems in the semantic-based reuse of distributed CORBA-compliant software. Such environment could support a highly confident reasoning about re-usability and consistent composability of pre-existing software components under application requirements. The reasoning is based on the refinement of the application specification by a specification of the components. We clarify the concept of Semantic Interoperable Environment (SIE) w.r.t. CORBA and RAISE, and define a general architecture of CORBA/RAISE SIE based on OMG IDL/RSL mapping and IDL extensions. We also consider questions of client/component adaptation, in particular, by decomposition of client specifications. Looking for ways of a natural decomposition, we propose an approach which is based on a separate consideration of function application and function availability semantics. Function availability can be defined independently in terms of communication patterns which are specified in Hennessy-Milner Modal Logic. Finally, we investigate some ways of further extensions of the integrated SIE towards reasoning about temporal properties and refinement of communication patterns. The report is prepared in the context of the UNU/IIST CaSIno project.

 The method of refinement of component and object systems, known as rCOS, provides a notation with a formally defined relational semantics. In rCOS, the notions of interfaces, contracts, components, and component publications are formally defined. With the definitions of various compositions and refinement relations between contracts and components, the key software artifacts in all phases of a component-based model driven design process can be formally specified, analyzed and refined. This paper presents our further investigation on problems of component publications and composition of components. We will define the notion of publications of components that describes how a component can be used by a third party in building their own components or in writing their applications without the access to the design or the code of the component. It is desirable that different users of the components can be given different publications according to their need. The first contribution of this paper is to provide a procedure, which calculates a weakest contract of the required interface of a component from the contract of its provided interface and its code. The other contribution, that is more significant from a component-based designer's point of view, is to define composition on publications so that the publication of a composite component can be calculated from those of its subcomponents. For this we define a set of primitive composition operators over components, including renaming, hiding, internalizing and plugging.

This compendium consists of the papers presented at the TTSS’10 workshop for the convenience of the workshop participants.

 Linear duration invariants (LDI) are important safety properties of real-time systems. They can be easily formulated in terms of a class of chop-free formulas in the Duration Calculus (DC). Compared to other temporal logics, the specification in DC is simpler, neater and more importantly easier to understand. However, directly model checking them is more difficult than model checking properties formulated in the computation tree logic (CTL). In this paper, we present a technique for the verification of the satisfaction of an LDI D by a timed automaton A by model checking a CTL property. For this, we construct an untimed automaton G from A, and prove that A satisfies D iff D is is satisfied by the set of all paths of G. We then construct a CTL formula and simply check if G satisfies this formula. By this, we convert the problem of verification of the LDI to the problem of model checking CTL formula. As a result, the CTL model checking techniques and tools, such as UPPAAL, can be used for verification of LDI specified in the DC. This paper is accepted for presentation and publication in the proceedings ICTAC 2008 in LNCS. The research supported by the project of National Natural Science Foundation of China (No.60603037) and HTTS project funded by Macau Science and Technology Development Fund.

 We present a design of a triple modular fault-tolerant system that is a real case we received from our collaborators in the aerospace field. The system is used to compute the action that a subsystem should take and output the result to another subsystem. We model the system as timed automata, where a fault is modelled as an unobservable transition from a "good state" to an "error state". Based on the faults that we were given by the application engineers, we design a system to tolerate the faults and use UPPAAL to check relevant properties. Keywords: Fault-tolerance, real-time embedded systems, abstraction techniques, model checking

 For a PC-mobile download system which is embedded with streaming download protocol, there are problems that the data cannot be transmitted correctly from the PC to the mobile, or the transmission is unacceptably slow. To solve these problems, we carry out a formal analysis for the protocol with some timing parameters and a given probability of loosing data using a probabilistic model checking tool PRISM. We introduce a technique to reduce the state space of the system modeling the protocol which is a network of probabilistic timed automata. The experimental results in PRISM give us a clear explanation to the problems, and are helpful in identifying the optimal parameter settings to meet industrial requirements.

 Being a successful technique in software practice, Object Orientation (OO) is a hot topic in academic research fields. Among many formalisms, rCOS, a refinement calculus of object-oriented systems based on Unifying Theories of Programming (UTP), has been proven a promising one in the sense of its applications to incremental software constructions, the formal use of UML, etc. However, equipped with a semantics reasoning on both static and dynamic properties, rCOS is not designed for static checking. We believe introducing static checking will extend the power of rCOS. In this paper, we develop a type system for rCOS and prove some type safety theorems. To make the theoretical results of this paper convincible and easy to be understood, we follow the traditional approaches of type systems construction. That is, we use an operational semantics as the basic explanation of rCOS language in spite of the fact that rCOS is originally developed in a denotational framework.

 An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class declarations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams as directed labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such a structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement, as an extension to the classical theory of data refinement, in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation. 

Theories of graphs and graph transformations form an important part of the mathematical foundations of computing, and have been applied in a wide range of areas from the design and analysis of algorithms to the formalization of various computer systems and programs. In this thesis, we study how graphs and graph transformations can be used to model the static structure and dynamic behavior of object-orientated and service-oriented systems.

Our work is mainly motivated by the difficulty in understanding and reasoning about object-orientated and service-oriented programs, which have more sophisticated features compared with traditional procedural programs. We show that the use of graphs and graph transformations provides both an intuitive visualization and a formal representation of object-orientated and service-oriented programs with these features, improving people’s understanding of the execution states and behaviors of these programs.

We provide a graph-based type system, operational semantics and refinement calculus for an object-oriented language. In this framework, we define class structures and execution states of oo programs as directed and labeled graphs, called class graphs and state graphs, respectively. The type system checks whether a program is well-typed based on its class graph, while the operational semantics defines each step of program execution as a simple graph transformations between state graphs. We show the operational semantics is type-safe in that the execution of a well-typed program does not “go wrong”. Based on the operational semantics, we study the notion of structure refinement of oo programs as graph transformations between their class graphs. We provide a few groups of refinement rules for various purposes such as class expansion and polymorphism elimination and prove their soundness and relative completeness.

We also propose a graph-based representation of service-oriented systems specified in a service-oriented process calculus. In this framework, we define states of service-oriented systems as hierarchical graphs that naturally capture the hierarchical nature of service structures. For this, we exploit a suitable graph algebra and set up a hierarchical graph model, in which graph transformations are studied following the well-known Double-Pushout approach. Based on this model, we provide a graph transformation system with a few sets of graph transformation rules for various purposes such as process copy and process reduction. We prove that the graph transformation system is sound and complete with respect to the reduction semantics of the calculus.

 Business Process Execution Language (BPEL), or Web Services BPEL (WS-BPEL), is the standard for specifying workflow process definition using web services. Research on formal modelling and verification of BPEL has largely concentrated on control flow and data flow, while security related properties have received little attention. In this work, we present a formal framework that integrates Role Based Access Control (RBAC) into BPEL and allows us to express authorisation constraints using temporal logic. Using this framework, we show how model-checking can be applied to verify that a given BPEL process satisfies the security constraints.

Being a successful technique in software practice, object orientation (OO) is a hot topic in academic research fields. Among many formalisms, rCOS, a refinement calculus of object-oriented systems based on unifying theories of programming (UTP), has been proven a promising one in the sense of its applications to incremental software constructions, the formal use of UML, etc. However, equipped with a semantics reasoning on both static and dynamic properties, rCOS is not designed for static checking. We believe introducing static checking will extend the power of rCOS. In this paper, we develop a type system for rCOS and prove some type safety theorems. To make the theoretical results of this paper convincible and easy to be understood, we follow the traditional approaches of type systems construction. That is, we use an operational semantics as the basic explanation of rCOS language in spite of the fact that rCOS is originally developed in a denotational framework.

An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class declarations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams asdirected labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such a structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement, as an extension to the classical theory of data refinement, in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation. 

 In this paper we present a pomset semantics for a shared-variable parallel language which is an extension of the one studied by Brookes in [5]. The pomset semantics lifts the transition trace semantics to the non-interleaving setting, where parallel events in a pomset transition trace are labeled by conditionally independent actions. Most of the important laws from the interleaving setting also hold in the non-interleaving setting. Similarities and differences with other related works are discussed.

 An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class decorations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams as directed labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such as structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation. Keywords: Class graph, Object graph, Graph transformation, Normal form, Object-orientation, Structure refinement.

 Preliminary proceedings of the papers presented at the TTSS'08 workshop for the convenience of the workshop participants. A selection of revised papers will be published in Electronic Notes in Theoretical Computer Science by Elsevier.