Formal Techniques for Networked and Distributed Systems - FORTE 2006: 26th IFIP WG 6.1 International Conference, Paris, France, September 26-29, 2006,

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...

Author: Elie Najm | Jean-Francois Pradat-Peyre | Véronique Viguié Donzeau-Gouge

12 downloads 1410 Views 6MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany

4229

Elie Najm Jean-François Pradat-Peyre Véronique Viguié Donzeau-Gouge (Eds.)

Formal Techniques for Networked and Distributed Systems – FORTE 2006 26th IFIP WG 6.1 International Conference Paris, France, September 26-29, 2006 Proceedings

13

Volume Editors Elie Najm ENST Dept. Informatique et Reseaux 46, rue Barrault, 75634 Paris, Cedex 13, France E-mail: [email protected] Jean-François Pradat-Peyre Véronique Viguié Donzeau-Gouge Conservatoire National des Arts et Métiers Lab. CEDRIC 292, rue Saint-Martin, 75 141 Paris Cedex 03, France E-mail: {peyre,V.Viguie.Donzeau-Gouge}@cnam.fr

Library of Congress Control Number: 2006933226 CR Subject Classification (1998): C.2.4, D.2.2, C.2, D.2.4-5, D.2, F.3, D.4 LNCS Sublibrary: SL 2 – Programming and Software Engineering ISSN ISBN-10 ISBN-13

0302-9743 3-540-46219-8 Springer Berlin Heidelberg New York 978-3-540-46219-4 Springer Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © IFIP International Federation for Information Processing 2006 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 11888116 06/3142 543210

Preface

This volume contains the proceedings of Forte 2006, the 26th IFIP WG 6.1 International Conference on Formal Methods for Networked and Distributed Systems, which took place in Paris, September 26-29, 2006. Forte denotes a series of international working conferences on formal description techniques applied to computer networks and distributed systems. The conference series started in 1981 under the name PSTV. In 1988 a second series under the name Forte was set up. Both series were united to Forte / PSTV in 1996. Five years ago the conference changed the name to its current form. Forte was held in Taiwan in 2005, in Madrid in 2004, in Berlin in 2003, in Houston in 2002, etc. The 2006 edition took place in Paris in the buildings of the CNAM (Conservatoire National des Arts et M´etiers), which is a Public Scientiﬁc, Cultural and Professional Institution. Forte 2006 was organized by Cedric, the computer science research laboratory of the CNAM, and by the Parisian multi-laboratories research group MeFoSyLoMa (M´ethodes Formelles pour les Syst`emes Logiciels et Mat´eriels). The conference comprised a threeday technical program, during which papers contained in these proceedings were presented. The technical program was preceded by a tutorial day. Forte is dedicated to formal description techniques and their application to distributed systems and cooperating applications. The focus of Forte 2006 was on the construction of middleware and services using formalized and veriﬁed approaches. In addition to the classic protocol speciﬁcation, veriﬁcation and testing problems, Forte 2006 addressed the issues of composition of protocol functions and of algorithms for distributed systems. In total 99 abstracts and 78 full papers were submitted covering the special focus of Forte 2006 and also more usual topics such as testing, slicing, and veriﬁcation techniques; highlighting diﬀerent formalisms among them one can cite Petri Nets, processes algebra or uniﬁed modelling languages. Out of the submissions, 26 full papers and 4 shorts papers were selected by the Program Committee for presentation. We would like to express our deepest appreciation to the authors of all submitted papers, to the Program Committee and to external reviewers who did an outstanding job in selecting the best papers for presentation (more than 300 referee reports were completed before closing the selection phase). In addition to the submitted contributions, there were three invited lectures: one by Daniel Krob (Ecole Polytechnique, France), who gave his vision of complex systems in a talk entitled “Modelling of Complex Software Systems: A Reasoned Overview”; one by Leslie Lamport (Microsoft, USA), who presented a new way to describe algorithms with his talk entitled “The +cal Algorithm Language”; and one by Martin Wirsing (Institut fur Informatikr, Ludwig-Maximilians-Un´ıversit¨at M¨ unchen, Germany), who presented the Sensoria project in a talk entitled “Semantic-Based Service-Oriented Software

VI

Preface

Development.” We thank them for the quality of their talks and of their papers. Two very interesting tutorials were given on the ﬁrst day, one by R¨ udiger Valk (Univ. Hamburg, Germany) on the use of Petri Nets for modelling and verifying concurrent systems and one by Dominique M´ery (Universit´e Henri Poincar´e Nancy & LORIA, France) on the event B method. We thank them for their help in disseminating knowledge in formal methods for system design. We would like to thank the CNAM technical and organizational support, Philippe Auger, Joel Berthelin, Frederic Lemoine, Gilles Lepage and Stephen Robert. Special thanks to Kristina and Gabriele Santini (Ksw), who designed the Forte 2006 Web site (http://forte2006.cnam.fr). We are also grateful to Christine Choppy, who organized tutorials, Kirill Bogdanov for his work as Publicity Chair, and to the Steering Committee members for their advice. We thank also Joyce El Haddad, Sami Evangelista, Irfan Hamid, Christophe Pajault, Isabelle Perseil, Pierre Rousseau, and Emmanuel Paviot-Adet for all their work before and during the conference. Last, but not least, we would like to express our appreciation to speakers and to all the participants who helped in achieving the goal of the conference: providing a forum for researchers and practitioners for the exchange of information and ideas about formal methods for modelling, testing and verifying protocols and distributed systems.

July 2006

Elie Najm Jean-Fran¸cois Pradat-Peyre V´eronique Vigui´e Donzeau-Gouge

Organization

Organization Chairs General Chair Program Chairs

Tutorials Chair Publicity Chair

V´eronique Vigui´e Donzeau-Gouge (Cedric-CNAM, France) Elie Najm (Infres-ENST, France) Jean-Fran¸cois Pradat-Peyre (Cedric-CNAM, France) Christine Choppy (LIPN Univ. Paris-Nord, France) Kirill Bogdanov (University of Sheﬃeld, UK)

Steering Committee G. v. Bochmann (University of Ottawa, Canada) T. Bolognesi (Istituto di Scienza e Tecnologie dell’Informazione, Italy) J. Derrick (Department of Computer Science, University of Sheﬃeld, UK) K. Turner (University of Stirling, UK)

Program Committee G. v. Bochmann (University of Ottawa, Canada) T. Bolognesi (IEI Pisa, Italy) M. Bravetti (University of Bologna, Italy) A. Cavalli (INT Evry, France) D. de Frutos-Escrig (Complutense University of Madrid,Spain) J. Derrick (University of Sheﬃeld, UK) L. Duchien (LIFL, France) A. Fantechi (Universit` a di Firenze, Italy) C. Fidge (Australia) H. Garavel (INRIA, France) R. Gotzhein (University of Kaiserslautern, Germany) S. Haddad (Lamsade-Paris Dauphine, France) T. Higashino (University of Osaka, Japan) D. Hogrefe (University of G¨ottingen, Germany) P. Inverardi (University of L’Aquila, Italia) C. Jard (IRISA, France) G. J. Holzmann (NASA/JPL, USA) M. Kim (ICU Taejon, Korea) H. K¨ onig (Brandenburg University of Technology, Germany) L. Logrippo (Universit´e du Qu´ebec en Outaouais, Canada) J. Magee (Imperial College of London, UK) E. Najm (Infres ENST, France) Co-chair M. N´ un ˜ ez (Complutense University of Madrid, Spain)

VIII

Organization

D. A. Peled (University of Warwick, UK) A. Petrenko (CRIM Montreal, Canada) F. Plasil (Charles University, Prague) J.-F. Pradat-Peyre (Cedric-Cnam, France) Co-chair W. Reisig (Humboldt-Universit¨at, Berlin) J.B. Stefani (INRIA, France) K. Suzuki (Kennisbron Co., Ltd, Japan) P. Traverso (ITC-IRST, Italy) K. Turner, (University of Stirling, UK) H. Ural (University of Ottawa, Canada) F. Wang (National Taiwan University, Taiwan)

External Referees Jiri Adamek Daniel Amyot Marco Autili Mehdi BenHmida B´eatrice Berard Piergiorgio Bertoli Laura Bocchi Luciano Bononi Sergiy Boroday C´eline Boutrous-Saab Manuel Breschi Tomas Bures Thomas Chatain Cheng Chih-Hong Jos´e Manuel Colom Bassel Daou John Derrick V´eronique DonzeauGouge Arnaud Dury Michael Ebner Khaled El-Fakih Edith Elkind Emmanuelle Encrenaz Sami Evangelista Hubert Garavel Andreas Glausch Ruediger Grammes Cyril Grepet Andrey Gromyko Hesham Hallal Irfan Hamid

Toru Hasegawa Wael Hassan May Haydar Viliam Holub Kohei Honda Geng-Dian Huang Akira Idoue Pavel Jezek Rajeev Joshi Guy-Vincent Jourdan Sungwon Kang Raman Kazhamiakin Jan Kofron Mounir Lallali Fr´ed´eric Lang Ranko Lazic Stefan Leue Li-Ping Lin Cai Lin-Zan Luis Llana-D´ıaz Luigi Logrippo Niels Lohmann Natalia L´opez Savi Maharaj Wissam Mallouli Annapaola Marconi Olga Marroqun Fabio Martinelli Mieke Massink Franco Mazzanti Mercedes G. Merayo Fabrizio Montesi

Gerardo Morales Isabelle Mounier Tomohiko Ogishi Jean-Marie Orset Christophe Pajault Emmanuel Paviot-Adet Patrizio Pelliccione Isabelle Perseil Marinella Petrocchi Pascal Poizat Nicolas Rouquette Pierre Rousseau Gwen Sala¨ un Koushik Sen Soonuk Seol Carron Shankland Marianne Simonot Isabelle Simplot-Ryl Rene Soltwisch Christian Stahl Jean-Marc Talbot Francesco Tapparo Maurice ter Beek Yann Thierry-Mieg Francesco Tiezzi Alberto Verdejo Friedrich H. Vogt Stephan Waack Daniela Weinberg Huang Wen-Ting Constantin Werner Jung-Hsuan Wu

Table of Contents

Invited Talks Modelling of Complex Software Systems: A Reasoned Overview . . . . . . . . . Daniel Krob

1

The +CAL Algorithm Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Leslie Lamport

23

Semantic-Based Development of Service-Oriented Systems . . . . . . . . . . . . . . Martin Wirsing, Allan Clark, Stephen Gilmore, Matthias H¨ olzl, Alexander Knapp, Nora Koch, Andreas Schroeder

24

Services JSCL: A Middleware for Service Coordination . . . . . . . . . . . . . . . . . . . . . . . . Gianluigi Ferrari, Roberto Guanciale, Daniele Strollo

46

Analysis of Realizability Conditions for Web Service Choreographies . . . . Raman Kazhamiakin, Marco Pistore

61

Web Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.S.W.B. Prasetya, T.E.J. Vos, S.D. Swierstra

77

Presence Interaction Management in SIP SOHO Architecture . . . . . . . . . . . Zohair Chentouf, Ahmed Khoumsi

93

Middleware Formal Analysis of Dynamic, Distributed File-System Access Controls . . . Avik Chaudhuri, Mart´ın Abadi

99

Analysing the MUTE Anonymous File-Sharing System Using the Pi-Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Tom Chothia Towards Fine-Grained Automated Veriﬁcation of Publish-Subscribe Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Luciano Baresi, Carlo Ghezzi, Luca Mottola

X

Table of Contents

A LOTOS Framework for Middleware Speciﬁcation . . . . . . . . . . . . . . . . . . . 136 Nelson Souto Rosa, Paulo Roberto Freire Cunha

Composition and Synthesis Automatic Synthesis of Assumptions for Compositional Model Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Bernd Finkbeiner, Sven Schewe, Matthias Brill Reﬁned Interfaces for Compositional Veriﬁcation . . . . . . . . . . . . . . . . . . . . . . 159 Fr´ed´eric Lang On Distributed Program Speciﬁcation and Synthesis in Architectures with Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Julien Bernet, David Janin Generalizing the Submodule Construction Techniques for Extended State Machine Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 Bassel Daou, Gregor v. Bochmann

Logics Decidable Extensions of Hennessy-Milner Logic . . . . . . . . . . . . . . . . . . . . . . . 196 Radu Mardare, Corrado Priami

Symbolic Veriﬁcation – Slicing Symbolic Veriﬁcation of Communicating Systems with Probabilistic Message Losses: Liveness and Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 C. Baier, Nathalie Bertrand, Philippe Schnoebelen A New Approach for Concurrent Program Slicing . . . . . . . . . . . . . . . . . . . . . 228 Pierre Rousseau Reducing Software Architecture Models Complexity: A Slicing and Abstraction Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Daniela Colangelo, Daniele Compare, Paola Inverardi, Patrizio Pelliccione

Uniﬁed Modeling Languages Branching Time Semantics for UML 2.0 Sequence Diagrams . . . . . . . . . . . . 259 Youcef Hammal

Table of Contents

XI

Formalizing Collaboration Goal Sequences for Service Choreography . . . . . 275 Humberto Nicol´ as Castej´ on, Rolv Bræk Composition of Use Cases Using Synchronization and Model Checking . . . 292 R. Mizouni, A. Salah, S. Kolahi, R. Dssouli

Petri Nets PN Standardisation: A Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 Lom-Messan Hillah, Fabrice Kordon, Laure Petrucci, Nicolas Tr`eves Resource Allocation Systems: Some Complexity Results on the S4 PR Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 Juan-Pablo L´ opez-Grao, Jos´e-Manuel Colom Optimized Colored Nets Unfolding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 Fabrice Kordon, Alban Linard, Emmanuel Paviot-Adet

Parameterized Veriﬁcation Liveness by Invisible Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 Yi Fang, Kenneth L. McMillan, Amir Pnueli, Lenore D. Zuck

Real Time Extending EFSMs to Specify and Test Timed Systems with Action Durations and Timeouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 Mercedes G. Merayo, Manuel N´ un ˜ez, Ismael Rodr´ıguez Scenario-Based Timing Consistency Checking for Time Petri Nets . . . . . . . 388 Li Xuandong, Bu Lei, Hu Jun, Zhao Jianhua, Zhang Tao, Zheng Guoliang Eﬀective Representation of RT-LOTOS Terms by Finite Time Petri Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 Tarek Sadani, Marc Boyer, Pierre de Saqui-Sannes, Jean-Pierre Courtiat

Testing Grey-Box Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 Edith Elkind, Blaise Genest, Doron Peled, Hongyang Qu

XII

Table of Contents

Integration Testing of Distributed Components Based on Learning Parameterized I/O Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 Keqin Li, Roland Groz, Muzammil Shahbaz Minimizing Coordination Channels in Distributed Testing . . . . . . . . . . . . . . 451 Guy-Vincent Jourdan, Hasan Ural, H¨ usn¨ u Yenig¨ un Derivation of a Suitable Finite Test Suite for Customized Probabilistic Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 Luis F. Llana-D´ıaz, Manuel N´ un ˜ez, Ismael Rodr´ıguez Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

Modelling of Complex Software Systems: A Reasoned Overview Daniel Krob Laboratoire d’Informatique de l’Ecole Polytechnique (LIX) ´ CNRS & Ecole Polytechnique, Ecole Polytechnique – LIX – 91128 Palaiseau Cedex – France [email protected] http://www.lix.polytechnique.fr/∼dk

Abstract. This paper is devoted to the presentation of the key concepts on which a mathematical theory of complex (industrial) systems can be based. We especially show how this formal framework can capture the realness of modern information technologies. We also present some new modelling problems that are naturally emerging in the speciﬁc context of complex software systems. Keywords: Complex system, Information system, Integrated system, Modelling, Software system.

This paper is dedicated to the memory of M.P. Sch¨ utzenberger

1

Introduction

In the modern world, complex industrial systems are just everywhere even if they are so familiar for us that we usually forgot their underlying technological complexity. Transportation systems (such as airplanes, cars or trains), industrial equipments (such as micro-electronic or telecommunication components) and information systems (such as commercial, production, ﬁnancial or logistical software systems) are for instance good examples of complex industrial systems that we are using or dealing with in the everyday life. At a superﬁcial level, “complex” refers here to the fact that the design and the engineering of these industrial systems are incredibly complicated technical and managerial operations. Thousands of specialized engineers, dozens of diﬀerent scientiﬁc domains and hundreds of millions of euros can indeed be involved in the construction of such systems. In the automobile industry, a new car project lasts for instance typically 4 years, requires a total human working eﬀort of more than 1.500 years, involves 50 diﬀerent technical ﬁelds and costs around 1 billion of euros ! In the context of software systems, important projects have also the same kind of complexity. Recently the uniﬁcation of the information systems of

This paper was supported by the Ecole Polytechnique and Thales’ chair “Engineering of complex systems”.

E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, pp. 1–22, 2006. c IFIP International Federation for Information Processing 2006

2

D. Krob

two important French ﬁnancial companies that merged, needed for example 6 months of preliminary studies followed by 2 years of work for a team of 1.000 computer specialists, in order to rebuild and to mix consistently more than 250 diﬀerent business applications, leading to a total cost of around 500 millions euros. At a deeper level, complex industrial systems are characterized by the fact that they are resulting of a complex integration process (cf. [38,39] for more details). This means that such systems are obtained by integrating in a coherent way – that is to say assembling through well deﬁned interfaces – altogether a tremendously huge number of heterogeneous sub-systems and technologies, that belong in practice to the three following main categories: 1. Physical systems: these types of systems are manipulating and transforming physical quantities (energy, momentum, etc.). The hardware components of transportation, micro-electronic or telecommunication systems are for instance typical physical systems. 2. Software systems: these systems are characterized by the fact that they are managing and transforming data. Operating systems, compilers, databases, Web applications and Business Intelligence (BI) systems are classical examples of software systems. 3. Human systems: human organizations1 can be considered as systems as soon as their internal processes have reached a certain degree of normalization. They will then be identiﬁed to the business processes that are structuring them. Note at this point that the diﬃculty of integrating coherently the diﬀerent parts of a complex industrial system reﬂects of course in the diﬃculty of integrating coherently the heterogeneous formal and informal models – going from partial diﬀerential equations and logical speciﬁcations to business process modelling (BPM) methods (cf. [11]) – that one must handle in order to deal globally with such systems. There is in particular still no real formal general models that can be used for dealing with complex industrial systems from a global point of view. This lack can also be seen in the fact that there are no uniﬁed tools for managing all the aspects of the realization cycle of an industrial complex system (which goes from the analysis of needs and the speciﬁcation phase up to the ﬁnal integration, veriﬁcation, validation and qualiﬁcation processes). More generally, one must clearly face a huge lack of theoretical tools that may help to clarify the question of complexity in practice. Very few research works are for instance studying directly “heterogeneous” systems in their whole, though a rather important research eﬀort has been done during the last decades to understand better several important families of homogeneous systems (such as Hamiltonian systems, dynamical systems, embedded systems, distributed systems, business organizations, etc.) which are involved within larger industrial 1

One must obligatory take into account these non technical systems in the modelling of a global system as soon as the underlying human organizations are strongly interacting with its physical and/or software components. This situation occurs for instance naturally in the context of complex software systems (see Section 4).

Modelling of Complex Software Systems: A Reasoned Overview

3

systems. The key point is here to understand that the problematics are absolutely not the same if one studies a complex industrial system at local levels (the only ones that the classical approaches are addressing) and at a global level. We however believe that the existing formal “local” theoretical frameworks can and should be redeployed to analyze complex industrial system at a holistic level. An interesting fact that militates in favor of the possibility of progressing in these directions is the convergence, that can be currently observed in the industry, between the approaches used for managing the engineering phases2 of physical and of software systems. This convergence can in particular be seen at a methodological level since system engineering (see [47,55]) and software engineering (see [48,51]) are more or more expressing their methods in the same way, but also at the level of the architectural principles used in physical and software contexts (see [33]) and of the quasi-formal specifying and modelling tools that are now taking into account both physical and software frameworks (cf. for instance [8,53] for the description of SysML that extends the classical Uniﬁed Modelling Language (UML) – [46] – for general systems). The purpose of this short paper is to make a reasoned overview on what could be a general theory of systems. After some preliminaries, we therefore present in Section 3 a tentative formal framework, for approaching in a mathematical way the notion of “complex industrial system”, that tries to capture the realness both of these systems and of their engineering design processes (which are very diﬃcult to separate in practice). Section 4 is then devoted both to the analysis of the modern software industrial ecosystem using the analysis grid provided by our approach and to the illustration of new types of research problems – of practical interest – that are naturally emerging from this new point of view on complex software systems.

2

Preliminaries

As in the few previous attempts to discuss globally of systems (see for instance [14,50,59]), these objects will be deﬁned here as mechanisms that are able to receive, transform and emit physical and/or informational quantities among time. This explains why we will ﬁrst introduce two key deﬁnitions on which are respectively based time and quantity modelling in our approach. 2.1

Time Scales

A time scale T refers to any mode of modelling all the possible moments of time starting from some initial moment t0 ∈ R. Time scales can be of two diﬀerent kinds, i.e. continuous or discrete. The continuous time scales are of the form T = t0 + R+ . One has more various (regular) discrete time scales which are of the form T = t0 +N τ where τ ∈ R+ ∗ denotes their time step. One can consider as well irregular discrete time scales that are of the form T = { t0 + τ1 + · · ·+ τn , n ∈ N } 2

I.e. design, architecture, integration and qualiﬁcation processes.

4

D. Krob

where (τi )i∈N is a given family of strictly positive real numbers. Note ﬁnally that the above time scales were always deterministic, but that they could also be probabilistic if the parameters involved in their deﬁnitions are random variables with given probabilistic laws. 2.2

Quantity Spaces

A quantity space refers to any mode of modelling either physical quantities (like energy, temperature, speed, position, etc.) or informational quantities (that is to say data in the usual computer science meaning). There are therefore two types of quantity spaces, i.e. continuous and discrete ones. On one hand, a continuous quantity space can be any complete topological space such as Rn or Cm . On the other hand, a discrete quantity space is either any ﬁnite set or a discrete inﬁnite set such as Nn , Zm or A∗ (where A stands for any ﬁnite alphabet). Note ﬁnally that a quantity space Q must also always distinguish a special element – called the missing quantity – that represents the absence of quantity (which is typically 0 is Q is a subset of C).

3 3.1

Complex Systems Abstract Systems

In order to move towards the formal modelling of complex industrial systems, let us introduce a ﬁrst notion of system, identiﬁed here to an input/output behavior. Deﬁnition 1. An abstract system S is deﬁned as a 5-uple S = (I, O, Ti , To , F ) where – I and O are two quantity spaces respectively called the input and output spaces of S, – Ti and To are two time scales, respectively called the input and output time scales of S, – F is a function from ITi into OTo which is called the transfer function of S. Observe that the discrete or continuous structure of the input and output spaces and of the input and output time scales deﬁnes naturally diﬀerent kinds of abstract systems in the meaning of Deﬁnition 1. To illustrate and understand better this last deﬁnition, let us now study several examples of such systems that are distinguished according to this new criterium. Example 1. – Discrete systems – An abstract system will said to be discrete when its input and output time scales are discrete. Discrete abstract systems can for instance easily be described by means of ﬁnite automaton modelling approaches which capture quite well the event reacting dimension of a real system. These types of formalisms all basically rely on the use of rational transducers – or equivalently Mealy machines – (cf. [3,37]) for expressing the transfer function

Modelling of Complex Software Systems: A Reasoned Overview

5

of a discrete system. Figure 1 shows a simple example of this kind of formalism for modelling the eﬀect of the switch button of a lamp on its lighting performance. The input space of the abstract system that models the lamp is here I = {ρ, π} (where ρ and π respectively model the fact that the switch button is released or pressed – note that ρ stands therefore for the empty quantity of I) when its output space is O = {0, e} ⊂ R+ (an output real value represents the amount of energy produced by the lamp). The corresponding input and output time scales can ﬁnally here be any discrete regular time scales that are relevant with respect to the modelling purposes (they are both re-normalized to N in our example for the sake of simplicity). Note in particular that the discrete structure of the output time scale is not a problem as soon as we are only interested by a computer model for simulation purposes (one just has to take a suﬃciently small output time step). We will revisit this example in the sequel, especially to see how to get more realistic models with respect to the lamp real physical behavior (see Examples 2 and 3).

Fig. 1. Modelling the transfer function of a lamp by a rational transducer

Petri nets (cf. [42,45]), (min−max, +) systems (cf. [4]), Kahn networks (cf. [27]), etc. are other examples – among numerous others – of basic automatonoriented formalisms that can be used (with slight modiﬁcations) for describing discrete abstract systems in our meaning. There is also a purely logical approach for representing discrete abstract systems. The core modelling language in this direction is probably Lustre (cf. [22,13]). This programming language is indeed structurally devoted to express transformations of typed inﬁnite sequences. The Lustre program that models the (simple) behavior of our lamp is for instance given below. node Lamp(X:bool) returns (Y:real); var E,Z:real; let E = e -> pre E; Z = 0 -> pre Z; Y = if X then E else Z; tel Fig. 2. Modelling the transfer function of a lamp by a Lustre program

6

D. Krob

In this example, X stands for the inﬁnite sequence of boolean entries a lamp receives (false and true modelling respectively the fact that the switch button of the lamp is released or pressed) when Y represents the inﬁnite sequence of the energy levels that can take the lamp (either 0 or e). The E and the Z variables are then just used here for deﬁning the constant inﬁnite real sequences E = (e, e, e, . . . ) and Z = (0, 0, 0, . . . ). The last line of the program expresses ﬁnally that the n-th entry of Y is equal to the n-th entry of E (resp. Z), i.e. to e (resp. 0), when the n-th entry of X is true (resp. false), i.e. when the button switch is pressed (resp. released), which models correctly the expected behavior of the lamp (initially switched oﬀ) we considered. Other reactive languages such as Signal (see [32]) or Lucid (see [12]) are using too the same global ﬂow manipulating approach. Note that one can of course also take any usual formal speciﬁcation language such as B (cf. [1,57]), TLA+ (cf. [31]) or Z (cf. [52]), any modelling tool coming from the model checking approach (cf. [6,49]) or even any classical programming language, to describe the step-by-step behavior of an abstract system by a “logical” formalism. Example 2. Continuous systems – An abstract system will said to be continuous when its input and output time scales are continuous. Since continuous systems occur naturally in physical contexts, all the various continuous models coming from control theory, physics, signal processing, etc. can therefore be used to represent continuous systems (see [14,50] for more details). These models rely more or less all on the use of (partial) diﬀerential equations which can be seen as the core modelling tool in such a situation. Going back again to the lamp system considered in Example 1, one can easily see that the lamp behavior can now for instance be modelled by a continuous signal y(t) – giving the value of the lamp energy at each moment of time t – that respects an ordinary diﬀerential equation of the following form: y (t) = e × x(t) − k × y(t),

y(0) = 0,

(1)

where x(t) stands for a continuous {0, 1}-signal that represents the behavior of the button switch – x(t) being equal to 0 (resp. 1) at time t iﬀ the button switch is oﬀ (resp. on) at this moment of time – and where k > 0 is a real parameter which models the speed of reactivity of the lamp light to the opening/closing of the button switch. Figure 3 shows then the result (on the right side) of such a modelling (obtained here with e = 2 and k = 1) for a given {0, 1}-input signal (on the left side). Note that this model shows clearly the continuous initial or ﬁnal evolutions of the energy of the lamp when the button is switched on or oﬀ (which are of course not immediate in reality as it was expressed in the discrete models considered in Example 1). Mathlab and Simulink are the typical software tools that can be used for designing continuous systems (see [36]). Observe also that speciﬁc frameworks exist for dealing with several important families of continuous systems such as dynamical systems (cf. respectively [28] and [18] for the physical and the control theory point of views), Hamiltonian systems (cf. [40]), etc.

Modelling of Complex Software Systems: A Reasoned Overview 2

2

1.5

1.5

1

1

0.5

0.5

0

10

20

30

40

50

60

0

10

20

30

40

7

50

60

Fig. 3. Modelling the physical behavior of a lamp by a diﬀerential equation

Example 3. Hybrid systems – An abstract system will said to be hybrid when one of its input or output time scales is discrete when the other one is continuous. It is interesting to know that two types of approaches exist for studying hybrid systems, depending respectively whether one stresses on the discrete (see for instance [2,24]) or the continuous point of view (see for instance [58]) with respect to such systems. However hybrid systems will of course always be represented by hybrid formalisms that mix discrete and continuous frameworks. Hybrid automata (see [24]) are for instance classical models for representing abstract hybrid systems – in our meaning – with a discrete input time scale and a continuous output time scale (but not for the converse situation, which shows that our hybrid systems must not be mixed up with these last systems). Figure 4 shows an hybrid automaton that models the physical behavior of the lamp which was already considered in the two previous examples. Three modes of the lamp are modelled here: the “Init” mode (the switch button was never touched), the “On” mode (the lamp was switched on at least once) and the “Oﬀ” mode (the lamp was switched oﬀ at least once). The states corresponding to these three diﬀerent modes contain then the three generic evolution modes – modelled by ordinary diﬀerential equations (see Figure 4) – of the continuous signal y(t) that represents the output lamp energy at each moment of time t, taking here again the notations of Example 2. On the other hand, the inputs are here just sequences of π and ρ (that model respectively the fact that the switch button of the lamp is either pressed or released).

Fig. 4. Modelling the physical behavior of a lamp by an hybrid automaton

8

D. Krob

Other families of hybrid formalisms – in our meaning – can be typically found in signal processing (see [43]) for modelling demodulation or sampling (transformation of a continuous signal into a discrete one) and modulation (transformation of discrete signal into a continuous one). These last formalisms are radically diﬀerent from the previous one since they are all based on complex analysis (i.e. z or Laplace transforms) or on distribution theory (see again [43]). Example 4. Non functional properties are functional . . . – Let us now focus on how to express some engineering oriented system aspects. The key point we would like to stress is the fact that the classical non functional properties of a real system – that is to say response times, costs, delays of realization, availability, safety, quality of service, etc. – can easily be modelled by transfer functions in our framework. A non functional property N of a system can indeed typically always be measured either by some suited numerical indicator fN (t) or by an adapted boolean predicate PN (t) (see for instance [60]), depending on internal parameters of the considered system, that can be measured at each moment t of the input time. Such non functional properties can then be expressed in our framework by extending the output space of the underlying system in order to send out the corresponding indicator or predicate values. Note ﬁnally that the “real” systems that can be found in practice form only a “small” sub-family of the abstract systems covered by Deﬁnition 1 (which was only given here in such a generality for the sake of simplicity). One may found in [29,30] a formal deﬁnition of a “good” global more restricted family of abstract systems that tries to capture the full realness of systems, using a Turing machine type formalism mixed with non standard analysis (cf. [16]) for taking into account the continuous and discrete dimensions of systems in the same framework. 3.2

Abstract Integration

Up to now, we only focused on “simple” models for dealing with systems. Quite all these models are however not really very well adapted for describing hierarchical systems, i.e. systems – in our meaning – that are recursively deﬁned as a coherent interfacing – i.e. an integration – of a collection of sub-systems of diﬀerent nature. Very surprisingly, while there is a large modelling diversity for usual systems (as we saw in the previous subsection), it indeed appears that there are only a few models that support homogeneous hierarchical design (the key diﬃculty being to be able to take into account both quantities and temporal hierarchies) when the formal models that support heterogeneous hierarchical design are even less (to our knowledge, the only framework which handles this last situation is SysML – see [53] – which remains a rather informal modelling approach). We will therefore devote this new subsection to introduce the key concepts on which system integration rely. To this purpose, let us ﬁrst deﬁne the notion of abstract multi-system that extends slightly the notion of system introduced in the previous section.

Modelling of Complex Software Systems: A Reasoned Overview

9

Deﬁnition 2. An abstract (n, m)-system S is deﬁned as a 5-uple S = (I, O, Ti , To , F ) where – I = (Ik )k=1...n and O = (Ol )l=1...m are two families of quantity spaces, whose direct products are respectively called the input and output spaces of S, – Ti = (Tki )k=1...n and To = (Tlo )l=1...m are two families of time scales, whose direct products are respectively called the input and output time scales of S, – F is a function from of S.

n k=1

Tk

Ik i into

m

Tl

Ol o which is called the transfer function

l=1

This last deﬁnition just expresses that a (n, m)-system – or equivalently a multisystem – has several diﬀerent typed and temporized input and output mechanisms (see Figure 5 for an example of “hybrid” multi-system with a mix of discrete and continuous input and output time scales). Note also that systems in the meaning of Deﬁnition 1 are now (1, 1)-multi-systems.

Fig. 5. Schematic description of a (n, m)-system

Multi-systems can easily be composed, using typed and temporized interaction channels, in a way that reﬂects the realness of system integration. An interaction channel stands for a medium between an output O and an input I of two multisystems that can only transmit quantities of a given quantity space, at a time rate associated with some ﬁxed time scale and with a constant temporal delay (for bringing a quantity from O to I). This leads us to the following deﬁnition. Deﬁnition 3. An interaction channel is a triple C = (Q, T, τ ) where Q is a quantity space, T is a time scale (of initial moment t0 ) and τ ∈ T − t0 is a transmission delay. Multi-system composition makes only sense in the context of interacting system networks, another important notion that is deﬁned below (see Figure 6 for a graphical vision).

10

D. Krob

Deﬁnition 4. An interacting system network N is a triple N = (S, χ, C) where – S = (Si )i=1...N is a family of multi-systems, – χ : C O −→ C I is a bijective mapping between a subset of the output indices of S into a subset of the input indices of S 3 , – C = { (OIc , Tcio , τ c ), c ∈ C O } is a family of interaction channels indexed by CO, such that the k-th output and l-th input quantity spaces and times scales of Si and Sj are always equal – respectively to OIc and Tcio – for every c = (i, k) ∈ C O and (j, l) = χ(c) ∈ C I . The input and output indices of S that belong (resp. do not belong) to C I or to C O (with the above notations) are called constrained (resp. free) input or output indices within S. Note also that an interacting system network will said to be initialized if it is equipped with a initialization map ι that associates with each constrained input index c = (i, k) ∈ C I of the underlying family S a quantity q = ι(c) ∈ Iik where Iik is the k-th input quantity space of the i-th system of S.

Fig. 6. Example of an interacting system network

Since we will be obliged for technical reasons to restrict composition to speciﬁc types of multi-systems deﬁned topologically, let us equip any ﬂow space F, i.e. any set of the form F = IT where I and T stand respectively for a quantity space and a time scale, with a sequential topology. We will indeed say that a sequence (xi )i≥0 of ﬂows of F = IT , i.e. of elements of the form xi = (xti )t∈T ∈ F, has a limit x = (xt )t∈T in F iﬀ for every t ∈ T, xti is always equal to xt for i big enough. A multi-system is then said to be continuous if its transfer function F satisﬁes F (lim xi ) = lim F (xi ) , i

3

i

(2)

(i, k) is an input (resp. output) index within S iﬀ Si has an k-th input (resp. output) space.

Modelling of Complex Software Systems: A Reasoned Overview

11

for any sequence (xi )i≥0 of input multi-ﬂows that has a limit in the previous meaning (naturally extended to products of ﬂows). We can now introduce the notion of system composition, which is a bit tedious to deﬁne properly, but that is easily graphically depicted (see again Figure 6). Proposition 1. Let N = (S, χ, C) be an interacting system network constructed over a family S of continuous multi-systems which is equipped with an initialization map ι. One deﬁnes then a new continuous multi-system S = (I, O, Ti , To , F ) – called the composition of S through the interactions χ × C with initialization ι – by setting: – I and Ti are respectively the families of all input quantity spaces and time scales that are associated with free input indices within S (whose set will be denoted by F I ), – O and To are respectively the families of all output quantity spaces and time scales that are associated with free output indices within S (whose set will be denoted by F O ), – the function F associates with any possible input multi-ﬂow x = (xc )c∈F I an output multi-ﬂow y = (yc )c∈F O which is deﬁned for each c = (i, k) ∈ F O by setting yc = Fik (Xχ−1 (i,1),(i,1) , . . . , Xχ−1 (i,Ni ),(i,Ni ) )4 (Ni denoting here the number of inputs of Si ), where X = (Xχ−1 (c),c )c∈C I ∪F I is the smallest5 solution of the equational system with ﬂow variables6 deﬁned by setting ⎧ ⎪ ⎪ ⎪ ⎨

X(0,0),c = xc for c ∈ F I , Xχt −1 (c),c = ι(c) for c ∈ C I and t ∈ [t0 , t0 + τ c [ ∩ Tik ,

⎪ c ⎪ t ⎪ = Fik (Xχ−1 (i,1),(i,1) ,. . ., Xχ−1 (i,Ni ),(i,Ni ) ))t−τ for c ∈ C I and t ≥ τ c ∈ Tik , ⎩Xχ−1(c),c where we put c = (j, l) and χ−1 (c) = (i, k) in all these last relations. Proof. The proof follows by using a classical argument of complete partial order theory (cf. [21]). Note that our result can be also seen as an extension of a classical result of Kahn (see [27]). This proposition translates now immediately in the following deﬁnition which gives a formal and precise meaning to the notion of system integration. 4

5

6

We extend here χ−1 to F I by setting χ−1 (c) = (0, 0) when c is a free input index within S. In the meaning of the product of the (complete) partial orders that are deﬁned on each ﬂow space F = IT by setting f g for two ﬂows f and g of F iﬀ the two following conditions are fulﬁlled: 1. f and g coincide up to some moment t ∈ T; 2. f u is equal to the missing quantity of I for each moment u > t in T. i Where Xχ−1 (c),c lies in the ﬂow space Iik Tk for every c = (i, k) ∈ F I ∪ C I .

12

D. Krob

Deﬁnition 5. A (continuous) multi-system will said to be an integrated abstract multi-system if it results of the composition of a series of other multi-systems. Integration leads naturally to the fundamental design mechanism for systems which consists in analyzing recursively any system as an interfacing of a series of sub-systems. This design process is quite simple to understand (in software context, it just reduces to the usual top-down design methodology), but rather diﬃcult to realize in practice for complex heterogeneous systems (the key problem being to be sure to interface sub-systems both consistently and without any speciﬁcation hole). The practical diﬃculty of integration reﬂects well in the fact that there is probably no existing formal framework for dealing with integrated systems at the generality level we tried to took here. As a consequence, one can also not really ﬁnd any unique global design formal tool for real systems. To be totally complete, one should however stress that there are at least two interesting frameworks – presented in the two forthcoming examples – for helping the working engineers in his integration tasks, but which have both serious modelling limitations as soon as one arrives at a system level, and moreover quite deep semantical lacks. Example 5. Continuous oriented formalisms – The most widely industrially used system design tool is probably the Mathlab & Simulink environment (see [36]). In this approach, systems are represented by “black boxes” whose transfer functions, inputs and outputs have to be explicitly given by the user (see Figure 7 for the graphical representation of a car window system modelled in this framework). The main problem of Mathlab & Simulink is however related to the fact that there is no unambiguous and/or crystal clear semantics behind the manipulated diagrams. The self loops in the graphical formalism provided by these tools does for instance not have a very well deﬁned interpretation in this framework, which may typically create causality problems at the modelling level (i.e. lead to abstractly modelled systems whose past behavior depends on their future one . . . 7 ). The discrete formalism used by Mathlab & Simulink – i.e. Stateﬂow which is just the commercial name of the implementation of the Statecharts framework (see the next example) – is also semantically rather weak (one can ﬁnd probably more than 20 diﬀerent formal semantics in the literature that were proposed for Statecharts). Altogether this shows that Mathlab and Simulink, even if they are wonderful and eﬃcient working tools for the engineer, still suﬀer from really fundamental ﬂaws from a formal point of view (which limits in particular the possibility of automatically verifying and validating designs made in this formalism). Example 6. Discrete formalisms – The last model that we would like to discuss in this section is Statecharts (see [23,35]). It is indeed probably the very ﬁrst model – introduced in 1987 – that allowed hierarchical design, one of the key idea of this formalism. In Statecharts, it is indeed possible to deal with distributed 7

Note that we totally avoided this problem in the formalism we introduced above, due to the fact that our interaction channels have always a response delay !

Modelling of Complex Software Systems: A Reasoned Overview

Fig. 7. A Matlab/Simulink

TM

13

c integrated system model

Fig. 8. The lamp revisited with Statechart

hierarchical Mealy machines (see again Example 1) which allow to model multiﬂow production by integrating event oriented hierarchical mechanisms. The example of Figure 8 illustrates these key aspects of Statecharts. We modelled here a lamp with two working modes: a normal one, where the usual lamp button switch – associated with π1 – allows to switch on or oﬀ the lamp, and a ﬂashing one, that one reachs or quits by pressing on a special button – represented by π2 . The lamp is also controlled by a global reset button – modelled by π0 – which allow to stop or activate all the functions of the lamp when pressing on it. Note that from the point of view of this last button, the right state of the above ﬁgure is therefore just the “ON” state which is hierarchically decomposed into two states, corresponding to the two possible working modes for our lamp (in which one should continue to descend in order to arrive to the ﬁner level of design in our example), plus a concurrent state representing a modulo 6 counter working totally independently from the other internal mechanisms, which gives permanently its value to the ﬂashing mode management state8 . 8

Which is not a very safe approach, as one may imagine, for obvious synchronization reasons . . .

14

D. Krob

The problem of Statecharts is however its poor semantics with respect to distribution expressivity: the precise nature of the interactions between the two automata separated by the dashed line (which models concurrency) in Figure 8 is typically not totally clear. The Esterel language (see [7] or [5] where one can ﬁnd a good overview of all so-called synchronous languages) was typically designed in order both to preserve the most interesting aspects of Statecharts’ approach and to overcome its core ﬂaws. For the sake of completeness, note ﬁnally that there are also other formal discrete formalisms that allow hierarchical design (see [9] and again [35]). 3.3

System Abstraction and Simulation

Abstraction and simulation are two classical notions that can also be re-adapted to systems (we take below all the ﬂow notations of the previous section extended here to multi-ﬂows). Deﬁnition 6. A multi-system S1 with input multi-ﬂow space Fi1 , output multiﬂow space Fo1 and transfer function F1 is said to be an abstraction (resp. a simulation) of a multi-system S2 with input multi-ﬂow space Fi2 , output multiﬂow space Fo2 and transfer function F2 iﬀ there exists two injective functions σ i and σ o such that the following diagram is commutative: Fi1

F1

σi

? Fi2

F2

- Fo 1 σo ? - Fo 2

Fi2

F2

(resp. σ i

? Fi1

F1

- Fo 2 6o ). σ

(3)

- Fo 1

Hence S1 is an abstraction of S2 if these two systems have homomorphic functional behaviors, the ﬁrst one being however less detailed than the second one. On the same way, S1 is a simulation of S2 if one can mimic all the functional behaviors of the second system by the ﬁrst one. Example 7. Assembling and high level programs – Let us ﬁx a ﬁnite alphabet A and a discrete time scale T. One can then identify any halting Turing machine M – i.e. any Turing machine that eventually stop on all its entries – with entries in A with a discrete system SM with A∗ as input and output quantity space, T as input and output time scale and a transfer function FM deﬁned as follows: 1. FM transforms any ﬂow of the form Fx = (x, 1, 1, . . . ), into the ﬂow FM,x = (1, 1, . . . , M x, 1, 1, . . . ), where M x stands for the value computed by M on x, produced at the moment given by the number of elementary steps of M required to obtain it; 2. FM transforms any input ﬂow diﬀerent from a ﬂow of the form Fx into the empty output ﬂow. Looking on programs in this way, one can then easily check that each high level program P is an abstraction of some assembling program A (the one produced by the corresponding compiler) and that such an assembling program A is then a simulation of the program P .

Modelling of Complex Software Systems: A Reasoned Overview

15

Example 8. Interfaces – The interface theory which was recently developed by de Alfaro and Henziger (see for instance [17]) can easily be transferred into the system framework as presented here (with of course again a number of slight reinterpretations). System interfaces provide then new generic interesting examples of system abstractions in our meaning . In this context, note that systems appear then as simulations of their interfaces. Note ﬁnally that there are of course other less constrained abstraction notions, typically the ones coming from static analysis (see [15]), which are also of interest in the system context. 3.4

Concrete Systems

We are now in position to model formally the usual way a concrete system is designed. Deﬁnition 7. A concrete system CS is a pair (F S, OS) of abstract integrated systems, the ﬁrst one (resp. the second one) being an abstraction (resp. a simulation) of the other one, which are respectively called the functional behavior9 and the organic structure10 of CS. This deﬁnition reﬂects the fact that the design of a real system S follows usually two main steps. The ﬁrst one is a modelling step which deﬁnes the so-called functional architecture of S, i.e. in other words the recursive integration structure of a high level modelling of S constructed by following the point of view of the external systems (hardware, software, users, etc.) that are interacting with S. When the functional architecture of S is ﬁxed, one can then deﬁne its organic architecture, i.e. the real internal structure of S, by respecting the requirements provided by the functional architecture (which appears as an abstraction of the organic architecture). In classical software engineering, the two architectural notions involved in Definition 7 can be seen at diﬀerent places. The pairs formed by a usual program and its machine or assembling code or, at a higher level, by a software speciﬁcation and its programmed implementation are typical examples of concrete systems in our meaning. However the underlying conceptual separation does only take really all its importance when one is dealing with systems whose both functional and organic decompositions are complicated, which occurs typically when a system results from an highly heterogeneous integration process. Note that this last property can in fact be seen as an informal characterization of complex systems. Observe also ﬁnally that two totally diﬀerent kinds of complex systems in this meaning, that is to say embedded systems and information systems, naturally arise in the software sphere (see below and Section 4.1). 9

10

The functional behavior models the input/output behavior of S as it can observed by an external observer. The organic structure models the intrinsic structure of the considered system.

16

D. Krob

Example 9. Embedded system design – When one deals with embedded system design, one must have an holistic approach that integrates in the same common framework the software, the hardware, the physical and the control theory points of views and constraints involved within such systems (see [25]). One therefore naturally divides the design in two separated, but completely interconnected, main parts: the functional design that corresponds here to the global environment and solution modelling where one will concentrate on the high level algorithmic and mathematical problems, the organic design related then with the low level system implementation where one must be sure to respect the physical and electronic constraints, the key diﬃculty being of course to have a good correspondence between these two levels of representation. Example 10. Information system design – An information system can be seen as a global (enterprise) environment where software systems, hardware devices and human organizations interact in a coherent way (usually to fulﬁll a number of business missions). The complexity of these systems lead therefore classically to separate the corresponding design into two architectural levels: on one hand, the functional architecture which is devoted to the description of the user services, the business processes, the user and business data, the system environment, etc. that have to be managed by the information system; on the other hand, the associated organic architecture which is the concrete organization of the software applications, servers, databases, middleware, communication networks, etc. whose interactions will result in a working information system.

4 4.1

Complex Software Systems Hierarchies of Complex Software Systems

Integration and abstraction mechanisms allow us to construct naturally a hierarchy of complexity – taken here in an informal way – on software systems which is organized around two axes, i.e. integration and abstraction complexity (see Figure 9). The idea consists in classifying families of software systems according both to their degree of integration, i.e. to their degree of internal systemic largeness and heterogeneity, or more formally to the size of the tree associated with their organic architecture, and to the degree of abstraction which is required to deal with them, i.e. equivalently to the size of the tree associated with their functional architecture. Such a classiﬁcation lead us to identify two main classes of complex software systems (the term complex referring here only at ﬁrst analysis to the organic integration complexity): 1. the software systems where the integration and abstraction complexity comes from the mix of computer science frameworks with physics, signal processing and control theory environments and models, that is typically to say the so-called embedded systems,

Modelling of Complex Software Systems: A Reasoned Overview

17

Fig. 9. The complex software hierarchy

2. the software systems where the integration and abstraction complexity comes from the mix of the computer science world with mainly “human” systems and organizations (plus possibly hardware components), which can be themselves separated into three main subclasses that are presented hereafter by increasing degree of integration and of abstraction (i.e. from the less to the most complex underlying organic and functional architectures): – integrated softwares: this corresponds to enterprise softwares that are speciﬁcally devoted either to some category of business activities – such as BI (global information consolidation inside a large company), CRM (customer relationship management), ERP (ﬁnancial and production service management), SCM (supply chain management) or KM (documentation management) softwares – or to some type of technical integration purposes – such as B2Bi (external partner software integration), EAI (internal software integration), ETL (batch data consolidation) or EII (on the request data consolidation) softwares. We refer to [26] for an overview of these software technology (see also [54,34]). – information systems: an information system can be deﬁned as a coherent integration of several integrated softwares – in the above meaning – that supports all the possible business missions of an organization, taken at a global level. An information system can therefore be seen as the integrated system that consists both of a human organization and of all the computer systems that are supporting the speciﬁc business processes of the considered organization (see [11,41] or Example 11 for more details). – systems of systems: this refers to an even higher level of integration, i.e. to the situation where a number of independently designed information systems have to cooperate in order to fulﬁll a common mission. Systems of systems are characterized by the loose couplings existing structurally between their organic components (that we will not discuss here since this would lead us too far with respect to the integration model we took

18

D. Krob

within this survey paper). Network Centric Warfare (NCW) systems, airport platforms management systems, etc. can be typically seen as systems of systems in this meaning. Example 11. Information system – As already pointed out, an information system can be seen as the integration of a human organization and a software system. The left side of Figure 10 shows for instance a very high level architecture of an information system focusing on this point of view: the sub-systems of the enterprise organization (i.e. the main business departments) are here at the border of this map when the technical sub-systems (i.e. the main integrated involved softwares) are in the center. One can also see on this map a number of arrows that are refering to the main business processes, that is to say to the main normalized interactions (or equivalently interfaces) existing between the corresponding human and software systems.

c and a business process model Fig. 10. An information system architecture (Sysoft ) c – [56]) (BPMN

A business profess refers typically to an enterprise process such as billing, maintening, sourcing, producing, etc. Business process modelling (BPM) is therefore naturally one of the core methodology which is presently developed to represent better the functional behavior of an information system (see [10,41] or Figure 10 which gives an example of a software testing procedure modeling). Note however that BPM is not a formal approach in the line of the numerous models we presented in Section 3. It indeed rather belongs to the family of informal UML-like models, which limits seriously its theoretical potential (but leaves the door open for new research). 4.2

What Are the New Problems Emerging from This Framework ?

New types of problems are naturally arising with the most complex software systems. A rather important research eﬀort is for instance presently done for understanding and designing better embedded systems, which are however probably the “most simple” complex systems due to the “nice” underlying mathematical

Modelling of Complex Software Systems: A Reasoned Overview

19

environment in which they are living, even if they are already quite complex to handle (see [25]). We will therefore not focus here on these systems on which a lot was and continue to be made by numerous theoretical computer scientists, but rather on the “human”-oriented complex systems which were, quite surprisingly, not widely studied from a formal point of view, although they are at the center of important economic challenges and of a large technological and business literature (see for instance [11,41,48], etc.). One of the key problems of these kind of software systems is clearly to be able to take more formally into account the “man in the loop”, which appears to be their common denominator. There are therefore naturally several important research streams that could emerge in trying to develop operational modelling formalisms for business processes and more generally for organizational paradigms. We mean of course here formalisms with well deﬁned semantics that would allow to express precisely and unambiguously characteristic properties of a business process (such as cost, speed of execution, probability of success, etc.) in order to be able to formally verify these properties. Such a modelling research eﬀort could probably also help practically organizations to master better their structures and processes. At a more global level, there is still in the same way an important high level formal modelling eﬀort that must be done in order to give solid bases to a theory of complex software systems. If there is a real business consensus on the nature of an information system, no scientiﬁc consensus exists presently – at our knowledge – with respect to a formal – that is to say a mathematical – deﬁnition of an information system. For systems of systems, the situation is even worse since at this moment of time, there is even no clearly shared business deﬁnition of these more complex systems. The key point in this direction would therefore probably to be able to give sound formal deﬁnitions of information systems and systems of systems, taking of course integrated systems as primitive objects in such a modelling approach. Such a framework would probably result in the development of new methods for complex software quantitative analysis, an important subject which is still under-developed in the classical context of information systems (see [19,44]) and basically non existing for systems of systems. One should ﬁnally not forget all the speciﬁc problems that are of course continuously emerging in the jungle of complex software systems. As a matter of conclusion to this paper, one can ﬁnd such two problems – among many others – roughly and quickly presented below. Example 12. Information system degeneracy – A classical operational problem that arises in a real information system corresponds typically to the situation where the system begins to emit too many information ﬂows and crashes when it is not able anymore to support the resulting treatment charge. Usually such a crash is not immediate and appears as the consequence of a long intermediate period where nothing is made to prevent it. It is therefore of main interest to be able to predict it and to analyze its origins in order to react properly when it is still time. If one models at high level an information system as a network of multi buﬀered applications, one sees that the problem can be rephrased as a

20

D. Krob

problem of queuing networks that can probably be attacked both from a static analysis and a distributed algorithmic point of view. Example 13. Interoperability of systems of systems – When interoperability is a well known problem which is quite well mastered for usual information systems (see [20,34]), it is probably still an open subject at the level of systems of systems. The key diﬃculty at this level comes from the fact that one must interface in a coherent way a number of information systems that were not initially intended to work together. For technical reasons, the usual interoperability approaches can therefore not totally be applied in these contexts since it is typically not easy or even possible to interface these systems through an EAI layer. New methods – mixing semantical and syntactical approaches – are therefore required to solve in a generic way this key problem. Acknowledgements. The author would sincerely like to thank Herman Kuilder, Matthieu Martel, Marc Pouzet and Jacques Printz for the numerous discussions we had together during the maturation period that preceded the writing of this paper, leading to several key evolutions of his point of view.

References 1. Abrial J.R., The B-book – Assigning programs to meanings, Cambridge University Press, 1996. 2. Alur R., Courcoubetis C., Halbwachs N., Henzinger T.A., Ho P.H., Nicollin X., Olivero A., Sifakis J., Yovine S., The algorithmic analysis of hybrid systems, Theor. Comp. Sci., 1995; 138 (1): 3–34. 3. Autebert J.M., Boasson L., Transductions rationnelles – Applications aux langages alg´ebriques, Collection ERI, Masson, 1988. 4. Baccelli F., Cohen G., Olsder G.J., Quadrat J.P., Synchronization and linearity – An algebra for discrete event systems, Wiley, 1992. 5. Benveniste A., Caspi P., Edwards S.A., Halbwachs N., Le Guernic P., de Simone R., The Synchronous Languages Twelve years later, Proc. of the IEEE, Special issue on Embedded Systems, 2003; 91 (1): 64–83. 6. B´ erard B., Bidoit M., Laroussinie F., Petit A., Schnoebelen P., V´eriﬁcation de logiciels – Techniques et outils du model-checking, Vuibert Informatique, 1999. 7. Berry G., Gonthier G., The Synchronous Programming Language ESTEREL: Design, Semantics, Implementation Science of Computer Programming, 19, 83– 152, 1992. 8. Bock C., SysML and UML2 Support for Activity Modeling, Systems Engineering, 9, (2), 160–186, 2006. ¨ rger E., Sta ¨ rk R., Abstract state machines – A method for high-level system 9. Bo design and analysis, Springer, 2003. 10. Business Process Management Initiative – Object Management Group, Business Process Modeling Notation, OMG, http://www.bpmn.org, 2006. 11. Caseau Y., Urbanisation et BPM : le point de vue d’un DSI, Dunod, 2006. 12. Caspi P., Hamon G., Pouzet M., Lucid Synchrone, un langage de programmation des syst`emes r´eactifs, in “Syst`emes Temps-r´eel : Techniques de Description et de V´eriﬁcation - Th´eorie et Outils”, 217–260, Hermes International Publishing, 2006.

Modelling of Complex Software Systems: A Reasoned Overview

21

13. Caspi P., Pouzet M., Synchronous Kahn networks, Proc. of the ﬁrst ACM SIGPLAN Int. Conf. on Functional Programming, 226–238, 1996. 14. Cha D.P., Rosenberg J.J., Dym C.L., Fundamentals of Modeling and Analyzing Engineering Systems, Cambridge University Press, 2000. 15. Cousot P., Cousot R., Abstract interpretation: a uniﬁed lattice model for static analysis of programs by construction or approximation of ﬁxpoints, in “Conf. Record of the Sixth Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages”, Los Angeles, ACM Press, 238–252, 1977. 16. Cutland N., Nonstandard analysis and its applications, London Mathematical Society Student Texts, 10, Cambridge University Press, 1988. 17. De Alfaro L., Henziger T.A., Interface-based design, in “Engineering Theories of Software-intensive Systems”, M. Broy, J. Gruenbauer, D. Harel, and C.A.R. Hoare, Eds., NATO Science Series: Mathematics, Physics, and Chemistry, Vol. 195, 83–104, Springer, 2005. 18. Fliess M., Fonctionnelles causales non lin´eaires et ind´etermin´ees non commutatives, Bull. Soc. Math. France, 1981; 109: 3–40. 19. Garmus D., Herron D., Function Point Analysis: Measurement Practices for Successful Software Projects, Addison-Wesley Information Technology Series, Addison-Wesley, 2000. 20. Gold-Bernstein B., Ruh W., Enterprise Integration: The Essential Guide to Integration Solutions, Addison-Wesley Information Technology Series, AddsisonWesley, 2004. 21. Gunter C.A., Scott D., Semantic domains, in “Handbook of Theoretical Computer Science”, Vol. B, 633–674, Elsevier, 1990. 22. Halbwachs N., Caspi P., Raymond P., Pilaud D., The synchronous data-ﬂow programming language LUSTRE, Proceedings of the IEEE, 79, (9), 1305–1320, 1991. 23. Harel D., Statecharts: A visual formalism for complex systems, Science of Computer Programming, 8, (3), 231–274, 1987. 24. Henzinger T.A., The theory of hybrid automata, in Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, LICS’96, IEEE Society Press, 1996, pp. 278–292. 25. Henzinger T.A., Sifakis J., The embedded systems design challenge, Proc. of the 14th Int. Symp. on Formal Methods (FM), LNCS, Springer, 2006 (to appear). 26. IT Tool box, http://www.ittoolbox.com. 27. Kahn G., The semantics of a simple language for paralell programming, Proc. of the IFIP Congress 74, 471–475, 1974. 28. Katok A., Hasselblatt B., Introduction to the modern theory of dynamical systems, Cambridge, 1996. 29. Krob D., Bliudze S., Towards a Functional Formalism for Modelling Complex Industrial Systems, in “European Conference on Complex Systems (ECCS05), P. Bourgine, F. Kps, M. Schoenauer, Eds., (article 193), 20 pages, 2005. 30. Krob D., Bliudze S., Towards a Functional Formalism for Modelling Complex Industrial Systems, in “Complex Systems: Selected Papers”, ComPlexUs (to appear). 31. Lamport L., Specifying systems – The TLA+ Language and Tools for Hardware and Software Engineers, Addison-Wesley, 2003. 32. Le Guernic P., Gautier T., Data-Flow to von Neumann: the Signal approach, in “Advanced Topics in Data-Flow Computing”, Gaudiot J.-L. and Bic L., Eds., Prentice-Hall, 413–438, 1991.

22

D. Krob

33. Maier M.W., System and Software Architecture Reconciliation, Systems Engineering, 9, (2), 146–59, 2006. 34. Manouvrier B., EAI – Int´egration des applications d’entreprise, Herm`es, 2001. 35. Marwedel P., Embedded systems design, Kluwer, 2003. 36. Mathworks, Mathlab and Simulink; http://www.mathworks.com. 37. Mealy G.H., A Method for Synthesizing Sequential Circuits, Bell System Tech. J., 34, 1045-1079, 1955. 38. Meinadier J.P., Ing´enierie et int´egration de syst`emes, Herm`es, 1998. 39. Meinadier J.P., Le m´etier d’int´egration de syst`emes, Herm`es-Lavoisier, 2002. 40. Meyer K.R., Hall G.R., Introduction to Hamiltonian Dynamical Systems and the N-Body Problem, Applied Mathematical Sciences, 90, Springer Verlag, 1992. 41. Morley C., Hugues J., Leblanc B., Hugues O., Processus m´ etiers et syst`emes d’information, Dunod, 2005. 42. Petri C.A., Fundamentals of a Theory of Asynchronous Information Flow, Proc. of IFIP Congress 1962, 386–390, North Holland, 1963. 43. Proakis J., Digital Communications, 3rd Edition, McGraw Hill, 1995. 44. Printz J., Deh C., Mesdon B., Tr` eves B., Coˆ uts et dur´ee des projets informatiques – Pratique des mod`eles d’estimation, Herm`es Lavoisier, 2001. 45. Reisig W., Petri nets, Springer Verlag, 1985. 46. Rumbaugh J., Jacobson I., Booch G., The Uniﬁed Modeling Language Reference Manual, Addison Wesley, 1999. 47. Sage A.P., Armstrong J.E. Jr., Introduction to Systems Engineering, John Wiley, 2000. 48. Satzinger J.W., Jackson R.B., Burd S., Simond M., Villeneuve M., Analyse et conception de syst`emes d’information, Les ´editions Reynald Goulet, 2003. 49. Schneider K., Veriﬁcation of reactive systems – Formal methods and algorithms, Springer, 2004. 50. Severance F.L., System modeling and simulation – An introduction, John Wiley, 2001. 51. Sommerville I., Software Engineering, Addison Wesley, 6th Edition, 2001. 52. Spivey J.M., The Z notation – A reference manual, Prentice Hall, 1992. 53. SysML, Systems Modeling Language – Open Source Speciﬁcation Project – http://www.sysml.org. 54. Tomas J.L., ERP et progiciels de gestion int´egr´es – S´election, d´eploiement et utilisation op´erationnelle – Les bases du SCM et du CRM, Dunod, 2002. 55. Turner W.C., Mize J.H., Case K.E., Nazemetz J.W., Introduction to industrial and systems engineering, Prentice Hall, 1993. 56. White S.A., Introduction to BPMN, IBM, http://www.bpmn.org, 2006. 57. Wordsworth J.B., Software engineering with B, Addison-Wesley, 1996. 58. Zaytoon J., Ed., Syst`emes dynamiques hybrides, Herm`es, 2001. 59. Zeigler B.P., Praehofer H., Gon Kim T., Theory of modeling and simulation – Integrating discrete event and continuous complex dynamic systems, Academic Press, 2000. 60. Zschaler S., Formal Speciﬁcation of Non-functional Properties of ComponentBased Software, in “Workshop on Models for Non-functional Aspects of Component-Based Software” (NfC’04), Bruel J.M., Georg G., Hussmann H., Ober I., Pohl C. Whittle J. and Zschaler S., Eds., Technische Universit¨ at Dresden, 2004.

The +CAL Algorithm Language Leslie Lamport Microsoft Corporation 1065 La Avenida Mountain View, CA 94043 U.S.A

Algorithms are diﬀerent from programs and should not be described with programming languages. For example, algorithms are usually best described in terms of mathematical objects like sets and graphs instead of the primitive objects like bytes and integers provided by programming languages. Until now, the only simple alternative to programming languages has been pseudo-code. + CAL is an algorithm language based on TLA+. A +CAL algorithm is automatically translated to a TLA+ speciﬁcation that can be checked with the TLC model checker or reasoned about formally. +CAL makes pseudo-code obsolete.

E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, p. 23, 2006. c IFIP International Federation for Information Processing 2006

Semantic-Based Development of Service-Oriented Systems Martin Wirsing1 , Allan Clark2 , Stephen Gilmore2 , Matthias H¨olzl1 , Alexander Knapp1 , Nora Koch1, 3 , and Andreas Schroeder1 1

Ludwig-Maximilians-Universit¨at M¨unchen, Germany 2 University of Edinburgh, United Kingdom 3 F.A.S.T. GmbH, Germany

Abstract. Service-oriented computing is an emerging paradigm where services are understood as autonomous, platform-independent computational entities that can be described, published, categorised, discovered, and dynamically assembled for developing massively distributed, interoperable, evolvable systems and applications. The IST-FET Integrated Project S ENSORIA aims at developing a novel comprehensive approach to the engineering of service-oriented software systems where foundational theories, techniques and methods are fully integrated in a pragmatic software engineering approach. In this paper we present first ideas for the S ENSORIA semantic-based development of service-oriented systems. This includes service-oriented extensions to the UML, a mathematical basis formed by a family of process calculi, a language for expressing context-dependent soft constraints and preferences, qualitative and quantitative analysis methods, and model transformations from UML to process calculi. The results are illustrated by a case study in the area of automotive systems.

1 Introduction Service-oriented computing is an emerging paradigm where services are understood as autonomous, platform-independent computational entities that can be described, published, categorised, discovered, and dynamically assembled for developing massively distributed, interoperable, evolvable systems and applications. These characteristics pushed service-oriented computing towards nowadays widespread success, demonstrated by the fact that many large companies invested a lot of efforts and resources to promote service delivery on a variety of computing platforms, mostly through the Internet in the form of Web services. Tomorrow, there will be a plethora of new services as required for e-government, e-business, and e-science, and other areas within the rapidly evolving Information Society. These services will run over “global computers”, i.e., computational infrastructures available globally and able to provide uniform services with variable guarantees for communication, co-operation and mobility, resource usage, security policies and mechanisms, etc., with particular regard to exploiting their universal scale and the programmability of their services. The aim of IST-FET Integrated Project S ENSORIA is to develop a novel comprehensive approach to the engineering of service-oriented software systems where foundational theories, techniques and methods are fully integrated in a pragmatic software

This work has been partially sponsored by the project S ENSORIA, IST-2005-016004.

E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, pp. 24–45, 2006. c IFIP International Federation for Information Processing 2006

Re-Engineering Legacy Systems

Service-Oriented Modeling

Legacy System

Model-driven Development

Core Calculi for Service Computing Deployment

Global Computer Global Computer

25

Qualitative and Quantitative Analysis

Semantic-Based Development of Service-Oriented Systems

Fig. 1. The S ENSORIA approach to service-oriented systems development

engineering approach. This includes a new generalised concept of service, new semantically well-defined modelling and programming primitives for services, new powerful mathematical analysis and verification techniques and tools for system behaviour and quality of service properties, and novel model-based transformation and development techniques. In the envisaged software development process, services are modelled in a platformindependent architectural design layer; by using model transformations, these models are then transformed and refined to the service computing platform of S ENSORIA which, in turn, can be used for generating implementations over different global computing platforms in a (semi-)automated way. On the other hand, legacy code is transformed systematically into service oriented software models (see Fig. 1). The added value of S ENSORIA to this widely used process comes from the deep mathematical foundations and their associated analysis methods. A typical scenario could be as follows: A service engineer will write her design of a service-oriented system for global computing in a precisely defined specialisation of UML for services on global computers. This UML extension will be carefully designed to be automatically connected with well-defined mathematical models of global computing services. These models come with mathematical theories, techniques and tools for analysing their qualitative and quantitative properties such as performance, security, costs, mobility, and distribution. By automatic translation of the analysis results back to UML the service engineer will get direct feedback on her system design from the mathematical models and can revise her models accordingly. Then she can use again mathematically well-founded transformation and refinement techniques for constructing the implementation or she can use the S ENSORIA analysis techniques for checking the appropriateness of the offered or discovered services of other parties. She could also adopt the re-engineering techniques of S ENSORIA for bringing legacy code in a service compatible format. In this paper we present first ideas for the S ENSORIA semantic-based development of service-oriented systems. This includes service-oriented extensions to the UML, a mathematical basis formed by a family of process calculi, a language for expressing

26

M. Wirsing et al.

context-dependent soft constraints and preferences, qualitative and quantitative analysis methods, and model transformations from UML to process calculi. The results are illustrated by a case study in the area of automotive systems. The paper is organised as follows: In Sect. 2 we present the running example, (an excerpt of) the UML extension for services, and two process calculi PEPA [22] and Sagas [13] which are used for analysing the UML designs and as semantic basis for service transactions with compensation. Moreover, we show how soft constraints and preferences can be used for choosing the best service offer. In Sect. 3 we present the S ENSORIA model transformation approach and show how we use the VIATRA2 [37,2] model transformation tool for translating UML diagrams with compensation into the Saga calculus and therefore giving semantics to compensations. In Sect. 4 we present some of the S ENSORIA methods for qualitative and quantitative analysis; in particular, we show how the dynamic behaviour of a service orchestration can be model checked, and how the performance aspects of a service level agreement for providing help in an accident scenario can be analysed. We conclude the paper in Sect. 5 with some remarks on further S ENSORIA results.

2 Languages for Service-Oriented Systems Current service description and composition languages such as WSDL [40] and BPEL [9] are tailored to specific technological platforms such as Web Services and the Grid, and address low-level concerns. The languages that have emerged for composing services into business processes such as WSFL [17], BizTalk [7], WSCI [39] and, most prominently, BPEL and BPEL4WS [10] have limited expressive power. They offer restricted support for concurrency and distribution and are mainly oriented towards programming workflows, making use of interconnection mechanisms that are far too rigid to support modelling business processes at the more abstract architectural layers. S ENSORIA aims at the definition of platform independent linguistic primitives for modelling and programming global service-oriented systems. Language primitives for services and their interactions are developed on two different abstraction levels, at the architectural design level and at the programming abstraction level for service overlay computing. The scientific tools used for the definition of programming-level primitives are category theory, process algebra and calculi as well as logics and constraints. A UML (Unified Modelling Language) [30] extension to service-oriented modelling makes the formal approaches available for practitioners and is the basis for many S EN SORIA verification techniques. An additional soft-constraint-based language for service selection allows the declarative specification of orchestrations. 2.1 Automotive Case Study Today’s embedded computers in cars can access communication networks like the Internet and thereby provide a variety of new services for cars and drivers. A set of possible scenarios of the automotive domain are examined within the scope of the S ENSORIA project, among which we select a car repair and an accident assistance scenario for illustrating the different techniques presented in this article.

Semantic-Based Development of Service-Oriented Systems

27

In the car repair scenario, the diagnostic system reports a severe failure in the car engine so that the car is no longer drivable. The car’s discovery system identifies garages, car rentals and towing truck services in the car’s vicinity. The in-vehicle service platform selects a set of adequate offers taking into account personalised policies and preferences of the driver and tries to order them. We assume that the owner of the car has to deposit a security payment before being able to order services. In the accident assistance scenario, the car’s airbag is deployed after an accident. This causes the safety system to report the car’s location to a accident report centre. This centre attempts to determine the severity of the accident and take appropriate actions. 2.2 Language for Service Orchestration In the car repair scenario, it is necessary to invoke services in a specific order. It is not possible, e.g., to order any service before the security payment was deposited. Similarly, when undoing orders of repair assistance services, the security payment may be returned only after all orders were cancelled. That is to say, compensations of executed sequential forward actions must be performed in reverse order. To address such compensation scenarios within S ENSORIA, Bruni et al. [13] defined a calculus to provide a first semantic basis for service orchestration (a more elaborated calculus is under development). This calculus builds upon sagas [18], which is a formalism for long running transactions (LRT) with compensations initially developed for database systems. LRTs are transactions that require a very long time to complete (e.g. hours or days). In such cases, traditional database techniques to guarantee the ACID property, such as locking resources, are not suitable. Instead, sagas allow the specification of compensation actions which are installed dynamically when forward actions succeed. As service orchestrations must be able to handle LRTs, most orchestration languages allow the specification of compensation actions. Hence, the saga calculus is a suitable semantic basis for service orchestrations. Within the calculus, one can specify compensation (%), sequential (;) and parallel (|) composition of actions, as well as subtransactions ([ ]). The semantics of sub-transactions is elegant for the specification of orchestrations: if a sub-transaction fails and compensates successfully, the sub-transaction is considered successful. If the enclosing transaction fails however, the sub-transaction is required to compensate as well. This allows the specification of dependencies between, e.g., ordering of services, or the continuation of processes although other parallel processes fail. The compensation strategy defined by the calculus is interruption based, that is to say, if a parallel branch fails all other branches are interrupted and compensate immediately. They do not need to execute forward actions until their control flow joins. In sequential composition, the compensation order is required to be the inverse of the forward action ordering. For the car repair scenario for example, we assume that the garage appointment is ordered next to the security payment deposit. This leads to the specification ChargeCreditCard % RevokeCharge ; OrderGarageAppointment % CancelGarageAppointment

28

M. Wirsing et al.

If the forward flow ChargeCreditCard ; OrderGarageAppointment fails, it is compensated by executing CancelGarageAppointment ; RevokeCharge in exactly that ordering, which is the behaviour required by the scenario specification. The saga calculus supports further constructs such as nondeterministic choice, exception and failure handling, and by this covers the semantics of common orchestration language constructs (see [13] for more details). 2.3 Language for Quantitative Analysis Performance Evaluation Process Algebra (PEPA) [22] is a high-level language for quantitative analysis of systems. PEPA is a stochastic process algebra which extends classical process algebras by associating a duration with each activity used in a PEPA model. Thus where classical process algebras such as CCS and CSP deal with instantaneous actions which abstract away from time PEPA has instead continuous-time activities whose durations are quantified by exponentially-distributed random variables. PEPA models describe finite-state systems and via the operational semantics of the language a PEPA model gives rise to a continuous-time finite-state stochastic process called a Markov chain. Continuous-time Markov Chains (CTMCs) are amenable to solution using standard procedures of numerical linear algebra such as Gaussian elimination or conjugate gradient methods. These can be applied to find the compute the steady-state or equilibrium probability distribution over the model. From this it is straightforward to compute conventional performance measures such as utilisation or throughput. More advanced tools [27,11] can perform transient analysis of the CTMC where one considers the probability distribution at a chosen instant of time. It is possible to use these results to perform more complex quantitative analysis such as computing response time measures and first passage time quantiles as used in service-level agreements. The PEPA process algebra is a compact formal language with a small number of combinators. Components perform activities. Activities have a type and rate specified using prefix (.). Alternative behaviours can be composed in a choice (+). Parallel composition of components uses CSP-style synchronisation over a set of activity types ( ). Private behaviour can be hidden (/). 2.4 UML Extension for Service Oriented Architectures Within the S ENSORIA approach services are modelled with UML. For the static aspects of service-oriented software systems, this representation effort ranges from rather simple, stereotyped language extensions for introducing services to more complicated structures like dependency relations between services and their contextual relationships to resources and legacy systems. The dynamic parts of service-oriented software, in particular orchestration and choreography of services are supported by developing primitives for interaction and activity modelling that take into account possible failures and quality-of-service aspects. The extensions will incorporate structural and behavioural as well as functional and non-functional notions.

Semantic-Based Development of Service-Oriented Systems

29

Fig. 2. Simplified architecture of car and car environment

The structure of a service oriented architecture can be visualised by UML deployment and composite structure diagrams. A deployment diagram is used to represent the—usually nested—nodes of the architecture, i.e. hardware devices or software execution environments. Fig. 2 shows a UML deployment diagram of the car and its environment as first approximation to an architecture model. The nodes are connected through communication paths that show the three types of communication that characterise the automotive domain: intra-vehicle communication, inter-vehicle communication, and communication among vehicle and environment such as communication with the car manufacturer or a remote discovery server. Note that the architecture comprises a local as well as a remote discovery service in order to find services in the local repository. Modelling Structural Aspects. Service oriented architectures are highly dynamic because services are only loosely coupled, i.e., a service often needs to be discovered before it is connected and can be disconnected at run-time as well. Hence, different modelling features are required to express evolving connections. In addition to UML deployment diagrams, which give a static view of the architecture, a representation showing the evolution of an architecture is required. Baresi, Heckel, Th¨one and Varr´o propose the construction of models visualising the functional aspects encapsulated in business-related components [3]. We use these UML structure diagrams to represent the evolving connections within the service oriented architecture of the vehicle and its environment. Fig. 3 shows the car internal components, a temporary connection to the discovery service of the car manufacturer, and a remote service (car rental) which knows the remote service discovery and will (later) publish its description to the remote service discovery. Other remote services such as tow truck and garage and their relationship to the discovery service can be modelled analogously. After publishing, the

30

M. Wirsing et al.

Vehicle

«artifact» CarRentalDesc. «describes»

Low-level VehiclePlatform

«permanent»

High-level Vehicle Platform «service» CarRental

«temporary»

«service» CarManufacturer Discovery

«knows»

«knows»

«artifact» «knows» DiscoveryDesc. «describes»

«service» RemoteDiscovery

Fig. 3. Car components modelled with UML extension for SOA before service publishing

discovery service knows the description of the published services, so that it can pass these descriptions to service requesters at service discovery time. Three different types of connections are identified: discovery connection, permanent connection (as in modelling of non service oriented architectures) and temporary connections. For more details about the last two types the reader is referred to [3]. The discovery connection is based on the information provided by a discovery service. We can observe these three types of connections in the service oriented vehicle architecture. In order to be invoked services need to be discovered before the binding to the car’s on-board system takes place. This type of connection using a discovery process is visualised with a knows stereotyped dependency, see Fig. 3. A temporary connection from the car on-board system to the car manufacturer discovery service is graphically represented by a UML connector with interfaces. For a permanent service we select a UML connector without interfaces as shown between components within the vehicle in Fig. 3. Three components are involved in the execution of service orderings: a service discovery which may be local or external to the car, a reasoner for service selection and a service orchestrator, see Fig. 4. Modelling Behavioural Aspects. The most interesting aspect when modelling the behaviour of a service oriented system is the workflow describing the orchestration of services. Modelling orchestration of services includes specifying non-functional properties of services such as performance and resource consumption, and also modelling transactional business processes that may require a very long period of time in order to complete. As discussed above, the key technique to handle long running transactions is to install compensations which are not directly available in UML. We start with the modelling of the accident assistance scenario. The accident assistance scenario is concerned with road traffic accidents and dispatch of medical assistance to crash victims. Drivers wishing to use the service must have in-car GPS location tracking devices with communication capabilities and have pre-registered their mobile phone information with the service. If a road traffic accident occurs, the deployment of

Semantic-Based Development of Service-Oriented Systems

Local Discovery

«permanent»

«know»

«artifact» Discovery Description

«describe»

31

External Discovery

provided: sendService(Service) required: getService(Description)

Reasoner

«permanent»

Orchestrator

provided: offer(Id, Service) noMoreOffers(Id) required: getService(Id, Description) failed(Id, Service) reserved(Id, Service)

Fig. 4. Components for executing service orderings and their ports

the car airbag causes the on-board safety system to report the car’s current location (obtained by GPS) to a pre-established accident report endpoint which in turn attempts to call the registered driver’s mobile phone. If there is no answer to the call then medical assistance is dispatched to the reported location of the car (presuming that the driver has been incapacitated by injuries sustained in the accident). We model this scenario in UML as state machine; to represent quantitative aspects (e.g., answer time) we use stereotypes to attach rates to transitions, see Fig. 5. Fig 6 explains the meaning of the rates. Regarding the modelling of the second scenario, “car repair”, the main focus lies on the specification of an appropriate transactional business process. As discussed in section 2.2, such a business process contains both forward actions and compensations. As UML activity diagrams lack such compensations, we define a set of modelling primitives and corresponding stereotypes for UML activity diagrams. – Saga is an executable activity node that may have subordinate nodes as an ActivityGroup with the ability to compensate long running transactions. – CompensableAction specialises UML Action to own exactly one pair of actions (forward action and compensation action). To provide a more intuitive representation, both forward and compensation actions are drawn separated by a line within CompensableAction instances, although this is not completely UML compliant. The metamodel depicted in Fig. 7 shows how these compensation elements are related to UML elements StructuredActivityNode, ActivityNode and Action. With these extensions, the orchestration for the car repair scenario can be compactly formulated (Fig. 8). In the modelled business process, the driver’s credit card is charged with the security deposit payment, which will be revoked if ordering the services failed. Then, a garage appointment is searched for. The appointment with the garage will give coordinates to tow the broken down car to, and also a location constraint that restricts the car rental agency that may be ordered. If ordering the car rental fails, the overall process does not fail, as the activity is enclosed in a sub-transaction. However, if ordering a tow truck fails the garage appointment has to be cancelled as well. For this reason, the

32

M. Wirsing et al. sm accident

«performance» awaitRescue

Passive «performance» rate=600.0..600.0

«performance» deployAirbag

«performance» rate=1.0..1.0

AirbagDeployed «performance» rate=2.0..10.0

«performance» reportAccident

HelpSent «performance» rate=0.25..3.0

AccidentReported «performance» rate=0.5..1.5

«performance» processReport ReportProcessed

«performance» rescue CallTimeout

«performance» rate=1.0..60.0 «performance» callDriversPhone

«performance» timeoutDriversPhone DriverCalled

«performance» rate=1.5..2.5

Fig. 5. State machine of the accident assistance scenario Value Rate min max Meaning r1 600.0 600.0 an airbag deploys in 1/10 of a second r2 2.0 10.0 the car can transmit location data in 6 to 30 seconds r3 0.5 1.5 it takes about one minute to register the incoming data r4 1.5 2.5 it takes about thirty seconds to call the driver’s phone r5 1.0 60.0 give the driver from a second to one minute to answer r6 0.25 3.0 vary about one minute to decide to dispatch medical help r7 1.0 1.0 arbitrary value — the driver is now awaiting rescue Fig. 6. Table of minimum and maximum values of the rates from Fig. 5. All times are expressed in minutes. Thus a rate of 1.0 means that something happens once a minute (on average). A rate of 6.0 means that the associated activity happens six times a minute on average, or that its mean or expected duration is ten seconds, which is an equivalent statement.

orchestrator will try to order a tow truck service until either no more service offers are found or the ordering succeeds. If ordering a tow truck fails the rental car delivery will be redirected to the driver’s actual location. It is obviously possible to model the same orchestration with a plain UML activity diagram, and handle compensations as exceptions (Fig. 9). This requires explicit programming of the compensations and the conditions under which they are executed. In addition to actions, activities and control nodes, the specification requires an InterruptibleActivityRegion in order to terminate all active and pending activities of the region in case an interruption occurs. Even in this simple scenario, this approach requires the verification of three conditions. For larger scenarios the diagram’s complexity will increase and its usefulness will decrease rapidly. Furthermore, it is difficult to explicitly model the silent failure of the car rental.

Semantic-Based Development of Service-Oriented Systems ActivityNode UML

StructuredActivityNode UML 0..1

Saga

33

0..*

compensationAction

Action UML

1

forwardAction

1

0..1

CompensableAction

0..1

Fig. 7. UML extension for sagas «saga» CarRepair ChargeCreditCard RevokeCharge

OrderGarage Appointment CancelGarage Appointment

«saga» CarRental Order repeateldy until success or no more services available

OrderTowTruck

OrderRentalCar

CancelTowTruck

RedirectRentalCar

Fig. 8. Modelling car repair workflow with UML extension for sagas

2.5 Soft Constraints for Selecting the Best Service In many cases service-oriented systems can utilise different combinations of services to achieve their goals. These combinations differ in functional and non-functional aspects like cost, reliability or performance. The reasoning component (cf. Fig. 4) of a serviceoriented system decides how the available services are orchestrated so that the best compromise between different goals of the system is achieved. Soft constraints are a promising way to specify and implement reasoning mechanisms. In the case study, soft constraints are used for service selection only. Soft constraints are an extension of classical constraints to deal with non-functional requirements, over-constrained problems and preferences. Instead of determining just a subset of admissible domain elements, a soft constraint assigns a grade—to be chosen from a set of finite or infinitely many “preference” values—to each element of the application domain. Bistarelli, Montanari and Rossi [6,5] have developed a very elegant semiring based theory of soft constraints where many different kinds of soft constraints can be represented and combined in a uniform way over so-called constraint semirings

34

M. Wirsing et al.

[CarRented] ChargeCreditCard [else] OrderGarage Appointment

RedirectRentalCar

[GarageAppointed] CancelGarage Appointment

[else] [CardCharged] [else]

OrderTowTruck

OrderRentalCar

OrderRentalCar does not throw an exception on failure

RevokeCharge

Order Repeatedly until success or no more services available

Fig. 9. Modelling car repair workflow with plain UML activity diagrams

(c-semirings). Examples for c-semirings are the semiring of Boolean values Bool or the “fuzzy natural numbers” FuzzyNat. The Bool semiring can be used to express hard constraints in the c-semiring framework; in the FuzzyNat semiring the value 0 is used to represent inadmissible solutions, higher values are used to represent increasingly preferred solutions. In S ENSORIA we are developing a language which extends the c-semiring approach with possibilities to specify preferences between constraints and to vary the constraints according to a context. This simplifies the description of behaviours of systems in a dynamically changing environment and with complex trade-offs between conflicting properties. A context is an expression in a suitable logic (e.g., predicate logic or temporal logic) which can serve as a guard for a constraint. For example, the distance to the destination might determine whether the quick availability of a rental car is important or not. In this case, “distance < 20km” is a context that can restrict the applicability of a constraint to situations where we are close to our destination. Variables appearing in contexts are called context variables; variables appearing free in constraints but not in contexts are called controlled variables. In the car repair scenario the context variables will contain, among others, the distance to our destination, the time remaining until the appointment starts, or whether the journey is work related. The controlled variables represent properties of offers. Each offer is identified by a serial number (offer-nr), and other controlled variables are used to specify cost or quality of the offers, see Fig. 10. A soft constraint is a mapping from (domains of) controlled variables into a csemiring. An expression of the constraint language consists of (1) a set of labelled conditional rules where the constraints contained in the head of the rule depend on the guard, and (2) a set of conditional inequalities between constraint labels which specify preferences between constraints.

Semantic-Based Development of Service-Oriented Systems Name distance

Type context

Δt

context

work-related? offer-nr rental-car-cost rental-car-availability garage-cost garage-duration

context controlled controlled controlled controlled controlled

35

Domain Meaning R+ The distance remaining to the target location (in km) N The time until the appointment starts (in minutes) B Is the appointment work-related? N The unique serial number of an offer R+ The cost of the rental car in Euros N The estimated availability time of the rental car R+ The cost of the garage (in Euros) N The estimated duration that the garage needs for the repair (in hours)

Fig. 10. Examples for context variables and controlled variables

In the car repair scenario we maintain hard constraints named towTruckOffers, rentalCarOffers and garageOffers containing disjunctions of the offers that the reasoner obtained from the discovery mechanism. If a new offer is provided to the reasoner the corresponding constraint or constraints are extended by another term. Other constraints specify the preferences of the users. These constraints are soft constraints, for simplicity we use the fuzzy natural numbers as the domain of all these constraints. This constraint prefers garages that can repair the car as quickly as possible: fastRepair : [garage-duration | n → 48/n] We also may want the repair to be done cheaply, but only if we are paying ourselves. Repairs costing more that 1000 Euros are still acceptable, but only barely. cheapRepair : in context ¬work-related? assert [garage-cost | n → 1000/n] end We are content to use any kind of car for short distances as long as it is cheap. In this case a cost of more than 100 Euros per day is unacceptable as the constraint evaluates to 0. shortDistance1 : in context distance < 20km assert [rental-car-cost | n → 100/n] end The following constraint means that we want to obtain a car as quickly as possible if the appointment is work-related, the distance is short and we have limited time to go to the appointment. If the rental car takes longer than Δt minutes we regard the offer as unacceptable. In this constraint the preference value depends on the context as Δt appears in the computation of a value. shortDistance2 : in context work-related? ∧ distance < 20km ∧ Δt < 60min assert [rental-car-availability | (n → Δt /n)] end When determining the configuration of a system we might not consider all constraints to be equally important. For example, it might be most important that the car

36

M. Wirsing et al.

is repaired both quickly and cheaply, and that we consider the other constraints only if we have several offers that are equal in that respect. This can be expressed by taking the product of the grades computed by both constraints. On the other hand, we consider shortDistance1 and shortDistance2 to be incomparable, i.e., we compare the grades of these constraints individually and do not compute a combined value. fastRepair ∗ cheapRepair > shortDistance1, shortDistance2 shortDistance1, shortDistance2 > fastRepair fastRepair > cheapRepair From a set of constraints and preferences the reasoner can compute either the best solutions, or a set of all solutions that are better than a certain threshold. Two techniques that are used for solving soft constraint systems are branch and bound search [38] and dynamic programming [5].

3 Model Transformation 3.1 Use of Model Transformation in S ENSORIA In the field of service oriented computing, there is a large gain from using model transformation languages, since data formats from different services can be easily mapped to each other with the help of model transformation languages. Model transformation is used in S ENSORIA for several tasks such as e.g. model refinement, deployment, and model analysis. “Refinement” uses model transformations to add additional details to the model, and remove degrees of freedom left in the initial model, trading abstraction for determinism. In S ENSORIA we see “deployment” as a special refinement mapping models from the S ENSORIA platform level to platform specific software artifacts. This use of model transformations is similar to the transformation from PIMs to PSMs in the MDA approach [28]. Finally, “model analysis” uses model transformations to translate models to logics or languages tailor-made for model analysis, such as process algebras. With the help of these specific models, different crucial qualitative and quantitative properties of the modelled service oriented software system can be verified. Furthermore, model transformations can be used to back-annotate the initial model with analysis results provided by analysis tools. Thus, the fact that analysis is performed on an internal representation can be made transparent to the modeller. There are several existing model transformation tools and frameworks, some of which are MOF QVT [31], ATLAS ATL [25] and IBM MTF [29]. Unfortunately, all of them have at best a partially defined formal semantics, which makes the use in semantic based engineering hard. Furthermore, MOF QVT still lacks an implementation. The S ENSORIA project comprises two model transformation languages, one with a pragmatic and easy usable programming model (VIATRA2) and one based on a declarative model with strong mathematical foundations (AGG). By having both languages, S ENSORIA covers both pragmatical and formal mathematical approaches to model transformations. VIATRA2 [37,2] (Visual Automated Model Transformations) is a model transformation language supporting graph transformation rules and imperative abstract state

Semantic-Based Development of Service-Oriented Systems fwd: Action name = fn

fwd : Action name = fn

fl: forwardAction comp: Compensable Action ' cl: compensationAction comp: Action name = cn

ft : ActivityTrace

fl: forwardAction tr : ActivityTrace

comp : Compensable Action

sfwd : Action name = fn forwardProcess

tr : ActivityTrace

' cl: compensationAction comp : Action name = cn

37

cs : Compensable

' compensationProcess ct : ActivityTrace

scomp : Action name = cn

Fig. 11. Graph transformation rule for compensable actions

machine (ASM)-like code. VIATRA2 is a fully hybrid language since it allows to call graph transformation rules from imperative code through rule application calls, and also to call ASM code from declarative graph transformation rules. Nevertheless, VIATRA2 delivers a formal semantics of transformations along with the language. A big advantage of VIATRA2 over other solutions is that it offers a good combination of both imperative code with declarative graph patterns, as imperative constructs ease programming complex transformations considerably [19]. A recursive processing of the source model can be easily intertwined with graph transformation steps. In this way, the advantages from both the declarative and the imperative approach can be brought together. AGG [1] (Attributed Graph Grammar System) uses an algebraic model transformation approach based on attributed graphs grammars. AGG has a strong mathematical basis in category theory, and follows a more declarative approach to transformation, which allows for easy mathematical analysis of transformation properties. A graph transformation rule in both VIATRA2 and AGG consists of a left hand side and right hand side. The left hand side specifies the conditions under which the rule applies. The right hand side specifies which changes are made to the model if the rule applies. These changes reuse variables bound in the precondition and manipulates or remove the model elements to which the variables are bound (see, e.g., Fig. 11). 3.2 Model Transformation Examples We discuss two examples of model transformation use in S ENSORIA. The first, which was implemented in VIATRA2, shows how UML activity diagrams can be transformed to saga expressions. The activity diagram from the car repair scenario, Fig. 8, is transformed into the following corresponding sagas expression: [ChargeCreditCard % RevokeCharge ; OrderGarageAppointment % CancelGarageAppointment ; (OrderTowTruck % CancelTowTruck | [OrderRentalCar%RedirectRentalCar])] The abstract syntax tree of this expression is created via a VIATRA2 model transformation. We will now give a brief overview of the transformation implementation. In the UML activity to sagas transformation example, all compensable actions are translated to simple sagas expressions with graph transformation rules (see Fig. 11).

38

M. Wirsing et al.

rule nodeToSagas(in StartNode, out EndNode, out Sagas) = try choose with find p_activityNode(StartNode) do try choose NextNode with find p_nextNode(StartNode, NextNode) do try choose with find p_parseableNode(NextNode) do call handleSequence(StartNode, NextNode, EndNode, Sagas); else call handleActivity(StartNode, NextNode, EndNode, Sagas); else fail; else try choose with find p_sagaNode(StartNode) do call handleSagaNode(StartNode, EndNode, Sagas); else try choose with find p_parallelStartNode(StartNode) do call handleParallelNode(StartNode, EndNode, Sagas); else try choose with find p_finalNode(StartNode) do call handleFinalNode(StartNode, EndNode, Sagas); else call handleNOP(StartNode, EndNode, Sagas); Fig. 12. Pattern Matching Dispatch. Called rules call nodeToSagas recursively

Non-compensable actions are translated with a similar graph transformation rule. These rules are called as long as applicable. Note that the creation of a trace prevents the repeated application of the rule (A second rule creates actions for activity nodes without compensations). In a second step, the parallel nodes, nested sagas as well as sequential edges between activity nodes are translated into parallel, saga and sequence expressions respectively. This is done with a recursive imperative rule, since the transformation is complex in nature: saga’s parallel expressions may be nested arbitrarily. Starting from the initial node, a node is transformed into a prefix of a saga expression and a recursive rule call is performed on successor nodes to transform the remaining subgraph. Different cases are distinguished by pattern matching (see Fig. 12). All names starting with p denote patterns to be matched, while names starting with handle denote imperative rules which call nodeToSagas recursively. After this second step terminates successfully, the transformation is complete. Another example for the use of model transformations is the transformation from UML state and communication diagrams to PEPA. PEPA is, as elaborated above, an algebra for performance analysis. It is possible to extract PEPA models by model transformation from UML state and communication diagrams.

4 Qualitative and Quantitative Analysis Qualitative and quantitative analysis methods for software systems aim at providing transparent support for the designer throughout the software construction phases based right on those notations used in development. However, proving the correctness of a design or measuring the performance, in general, relies on mathematical models and tool support that are not offered on the level of general software development notations, let

Semantic-Based Development of Service-Oriented Systems

39

alone using specialised extensions for particular domains. In S ENSORIA, model transformations are employed to lift methods and tools from the well-founded, abstract, mathematical level to the concrete UML-based design level for service-oriented architectures. Furthermore, backward transformations project analysis results, delivered in terms of the underlying mathematical model, back to modelling notation (cf. section 3). We demonstrate how model checking (qualitative analysis) and performance evaluation (quantitative analysis) are applied to the automotive case study. 4.1 Model Checking Orchestration The orchestration of services, like in the extended UML activity diagram description in Fig. 8, has to be implemented in an orchestrator. We transform the saga-based model into a conventional UML state machine model which details the handling of service allocation and compensation. Using model checking we can prove that the implementation model indeed preserves the compensation properties of the original UML model. The state machine in Fig. 13 describes an implementation of the car repair workflow as depicted in Fig. 8. It relies on a reasoner for choosing services as in Fig. 4. The general idea of the implementation is that every service needed is first requested from the reasoner (getService). If the reasoner delivers an offer (offer) in a certain amount of time (after(T)), the service first is reserved and ordered afterwards. If the reasoner misses the deadline, or the reservation or the ordering fail the orchestrator terminates. In the latter cases the reasoner is informed of the failure (fail) such that it can avoid offering a failing service again. During the reservation phase the reasoner may send better offers for the requested service (offer). If a service can be reserved eventually, the reasoner is notified (reserved) and the offer is ordered. The compensation handling is done using a global compensation handler, like suggested by the UML activity diagram description in Fig. 9. For the services “charge credit card”, “order tow truck”, and “order car rental”, however, different implementation details are to be realised: On the one hand, the credit card charge need not be reserved; this is an implementation decision. Ordering the tow truck has been marked as to be done repeatedly until no more offers are available. Thus every possible offer has to be checked, that is, previous reservations may have to be compensated in the orchestration process (compensateReservation). Finally, the car rental may or may not fail without calling for overall compensation, as it is marked as a nested saga. In S ENSORIA different tools are available for verifying the correct behaviour of the orchestrator implementation. The UML model checker UMC [35] (developed by ISTI) offers the verification of temporal properties described in the μ-calculus directly on UML state machine. The UML model checking tool Hugo/RT [23] (developed by LMU) translates UML state machines and collaborations into different off-the-shelf model checkers like Spin [34] and UPPAAL [36] and also supports Java and SystemC code generation. Here, we used the UPPAAL option of Hugo/RT. By instrumenting the model, which we will not detail here, we checked, e.g., that whenever the global final state is reached all services indeed have been ordered; if an order fails all orders and reservations which have been done up to the point of failure of getting a service—i.e.,

40

M. Wirsing et al.

/ r.getService(id, Credit) CarRepair

IdleCredit after(T) / compensate()

after(T) / compensate() r.failed(id, credit) offer(id, credit) / OrderCredit r.reserved(id, credit) / r.getService(id, Garage)

offer(id, garage) /

IdleGarage

offer(id, garage) /

ReserveGarage

after(T) / compensate() r.failed(id, garage)

/ r.reserved(id, garage)

OrderGarage

after(T) / compensate() r.failed(id, garage)

after(T) / compensate()

r.getService(id, TowTruck)

r.getService(id, RentalCar)

TowTruckRentalCar IdleTowTruck

noMoreOffers(id) / compensate()

offer(id, towTruck) / offer(id, towTruck) / ReserveTowTruck after(T) / r.failed(id, towTruck) r.getService(id, TowTruck)

after(T) / r.failed(id, towTruck) r.getService(id, TowTruck) compensateReservation (towTruck)

/ r.reserved(id, towTruck)

IdleRentalCar

after(T) /

offer(id, offer(id, rentalCar) / rentalCar) / after(T) / ReserveRentalCar r.failed(id, rentalCar) / r.reserved(id, rentalCar)

OrderTowTruck

OrderRentalCar

DoneTowTruck

DoneRentalCar

after(T) / r.failed(id, rentalCar)

compensate / if (reserved(rentalCar)) { compensateReservation(rentalCar) if (ordered(rentalCar)) redirect(rentalCar) } ... if (ordered(credit)) revoke(credit)

Fig. 13. Implementation state machine for car repair workflow

when one of the final states inside CarRepair is entered—are compensated. After behaviour verification, we have used Hugo/RT for generating Java code from the very same model that has been verified by UPPAAL.

Semantic-Based Development of Service-Oriented Systems

41

4.2 Quantitative Analysis of the Accident Scenario In this section we consider the assessment of a service level agreement offered by an automotive collision support service. The scenario with which these systems are concerned is road traffic accidents and dispatch of medical assistance to crash victims. The Choreographer design platform [14] (developed by the DEGAS project [24]) can perform quantitative analysis via PEPA which starts and ends with UML models. A PEPA model is extracted from a UML model decorated with rate information such as the one shown in Fig. 5. This model is compiled into a CTMC and solved for its steady-state probability distribution. The results from this analysis are reflected back into a modified version of the input UML model with the quantitative analysis results recorded on the state diagrams in the model. Here we use the more computationally expensive but more informative method of transient analysis of the underlying CTMC and focus on the analysis of the PEPA model. We represent in the model the sequence of events which begins with the deployment of the airbag after the crash and finishes with the dispatch of the medical response team. The first phase of the sequence is concerned with relaying the information to the remote service, reporting the accident. When the diagnostic report from the car is received the service processes the report and matches it to the driver information stored on their database. def

Car1 = (airbag, r1 ).Car2 def

Car2 = (reportToService, r2 ).Car3 def

Car3 = (processReport, r3 ).Car4 The second phase of this passage through the system focuses on the attempted dialogue between the service and the registered driver of the car. We consider the case where the driver does not answer the incoming call because this is the case which leads to the medical response team being sent. def

Car4 = (callDriversPhone, r4 ).Car5 def

Car5 = (timeoutDriversPhone, r5 ).Car6 The service makes a final check on the execution of the procedure before the decision is taken to send medical help. At this stage the driver is awaiting rescue. def

Car6 = (rescue, r6 ).Car7 def

Car7 = (awaitRescue, r7 ).Car1 We assess the service against the following compound service level agreement(SLA): At least 40% of airbag deployments lead to medical help being sent within five minutes and at least 80% of airbag deployments lead to medical help being sent within ten minutes. We assess this SLA using the passage-time quantile computation capabilities provided by the ipc/Hydra tool chain [11]. We vary rates r2 to r6 across five or six possible

42

M. Wirsing et al.

values leading to 5 × 5 × 5 × 5 × 6 = 3750 experiments to be performed. The graphs of computed probability against experiment number for time bounds of five minutes and ten minutes for all 3750 experiments are shown in Fig. 14. Using both of these graphs we determine that the SLA is met across the values of the rates of the model. Probability of completion by time 5.0 against experiment number

Probability of completion by time 10.0 against experiment number

0.8

0.8

0.6

0.6 Pr

1

Pr

1

0.4

0.4

0.2

0.2

0

0 0

500

1000

1500 2000 2500 Experiment number

3000

3500

0

500

1000

1500 2000 2500 Experiment number

3000

3500

Fig. 14. Graph of probability of completing the passage from airbag deployment to medical assistance dispatch within five minutes and ten minutes plotted against experiment number over all 3750 experiments

We now consider how the cumulative distribution function for the passage from airbag deployment to dispatch of medical assistance is affected as the values of the rates r2 to r6 are varied as specified in the table in Fig. 6. The results for r2 and r6 are presented in Fig. 15. These results show that variations in upstream rates (near the start of the passage of interest) such as r2 , r3 and r4 have less impact overall than variations in downstream rates (near the end of the passage of interest) such as r5 and r6 . This is true even when the scale over which the upstream rates are varied is much more than the scale over which the downstream rates are varied (contrast variation in r2 against variation in r6 ). The conclusion to be drawn from such an observation is that, if failing to meet a desired quality of service specified in an SLA then it is better to expend effort in making a faster decision to dispatch medical help (governed by rate r6 ) than to expend effort in trying to transmit location data faster (governed by rate r2 ), over the range of variability in the rates considered in the present study.

Fig. 15. Graphs of cumulative distribution function sensitivity to changes in rates for the passage from airbag deployment to dispatch of medical assistance

Semantic-Based Development of Service-Oriented Systems

43

5 Concluding Remarks In this paper we have presented some of the first results of the S ENSORIA semanticbased development of service-oriented systems. We have shown service-oriented extensions to the UML, a first mathematical basis formed by process calculi such as PEPA and the saga calculus, a language for expressing soft constraints and preferences of services, qualitative and quantitative methods for analysing service orchstrations and service level agreements, and model transformations from UML to process calculi. But these results represent only a small part of the S ENSORIA project. In addition, the S ENSORIA project is developing a comprehensive service ontology and a (S ENSORIA) Reference Modelling Language (SRML) [16] for supporting service-oriented modelling at high levels of abstraction of ”business” or ”domain” architectures (similar to the aims of the service component architecture SCA [33]). To provide semantic foundations to the dynamic behaviour of services a new process calculus SCC [8] has been designed which features explicit notions of service definition, service invocation and session handling. Other research strands of S ENSORIA comprise a probabilistic extension of a Linda-like language for service-oriented computing [12] and stochastic extensions of KLAIM [32] and beta-binders [15]. S ENSORIA addresses security issues ranging from sandboxing for KLAIM [21], trust management for autonomic grid services [26], and security of service composition [4] to a formal framework for security and trust in the requirements phase of system development [20]. Moreover, S ENSORIA is developing a model-driven approach for service-oriented software engineering and a suite of tools and techniques for deploying service-oriented systems and for re-engineering of legacy software into services. By integrating and further developing these results S ENSORIA will achieve its overall aim: a comprehensive and pragmatic but theoretically well founded approach to software engineering for service-oriented systems.

References 1. The Attributed Graph Grammar System (AGG). tfs.cs.tu-berlin.de/agg. Last visited: June 2006. 2. Andr´as Balogh and D´aniel Varr´o. Advanced Model Transformation Language Constructs in the VIATRA2 Framework. In Proc. ACM Symp. Applied Computing (SAC 2006) — Model Transformation Track, 2006. To appear. 3. Luciano Baresi, Reiko Heckel, Sebastian Th¨one, and D´aniel Varr´o. Style-based Modelling and Refinement of Service-oriented Architectures. Softw. Sys. Model., 2006. To appear. 4. M. Bartoletti, P. Degano, and Ferrari G.L. Security Issues in Service Composition. In Proc. 8th IFIP International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS), LNCS, 2006. 5. Stefano Bistarelli. Semirings for Soft Constraint Solving and Programming. LNCS 2962. Springer, Berlin, 2004. 6. Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint satisfaction and optimization. J. ACM, 44(2):201–236, 1997. 7. Microsoft BizTalk Server. www.microsoft.com/biztalk. Last visited: June 2006. 8. Michele Boreale, Roberto Bruni, Rocco DeNicola, Ivan Lanese, Michele Loreti, Ugo Montanari, Davide Sangiorgi, and Gianluigi Zavattaro. SCC: a Service Centered Calculus. Deliverable 2.2, S ENSORIA, 2006.

44

M. Wirsing et al.

9. Business Process Execution Language (BPEL). www.oasis-open.org. Last visited: June 2006. 10. BPEL for Web Services. www6.software.ibm.com/software/developer/library/ws-bpel.pdf. Last visited: June 2006. 11. Jeremy T. Bradley and William J. Knottenbelt. The ipc/HYDRA tool chain for the analysis of PEPA models. In Proc. 1st Int. Conf. on the Quantitative Evaluation of Systems (QEST 2004), pages 334–335, Enschede, Netherlands, September 2004. 12. Mario Bravetti and Gianluigi Zavattaro. Service Oriented Computing from a Process Algebraic Perspective. Journal of Logic and Algebraice Programming, 2005. To appear. 13. Roberto Bruni, Hernan Melgratti, and Ugo Montanari. Theoretical Foundations for Compensations in Flow Composition Languages. In Proc. 32nd ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages (POPL’05), pages 209–220. ACM, 2004. 14. Mikael Buchholtz, Stephen Gilmore, Valentin Haenel, and Carlo Montangero. End-to-end integrated security and performance analysis on the DEGAS Choreographer platform. In I.J. Hayes J.S. Fitzgerald and A. Tarlecki, editors, Proc. of the Int. Symposium of Formal Methods Europe (FM 2005), LNCS 3582, pages 286–301. Springer-Verlag, June 2005. 15. P. Degano, D. Prandi, C. Priami, and P. Quaglia. Beta-binders for biological quantitative experiments. Proc. 4th Workshop on Quantitative Aspects of Programming Languages, QAPL ’06, Electronic Notes in Theoretical Computer Science, 2006. To appear. 16. Jos´e Luiz Fiadeiro, Ant´onia Lopes, and Laura Bocchi. A Formal Approach to Service Component Architecture. In In Proc. 3rd International Workshop on Web Services and Formal Methods (WS-FM 06). 8-9 September 2006, Vienna, Austria, 2006. To appear. 17. Frank Leymann. Web Services Flow Language, version 1.0. Specification, IBM, 2001. www-306.ibm.com/software/solutions/webservices/pdf/WSFL.pdf. 18. Hector Garcia-Molina and Kenneth Salem. Sagas. In SIGMOD ’87: Proc. of ACM SIGMOD Int. Conf. on Management of Data, pages 249–259, New York, 1987. ACM Press. 19. Tracy Gardner, Catherine Griffin, Jana Koehler, and Rainer Hauser. A Review of OMG MOF 2.0 Query/Views/Transformations Submissions and Recommendations towards the Final Standard. In Proc. Wsh. MetaModelling for MDA Workshop, York, 2003. www.omg.org/docs/ad/03-08-02.pdf. 20. Paolo Giorgini, Fabio Massacci, and Nicola Zannone. Security and Trust Requirements Engineering. In Foundations of Security Analysis and Design III - Tutorial Lectures, volume 3655 of LNCS, pages 237–272. Springer-Verlag GmbH, 2005. 21. Ren´e Rydhof Hansen, Christian W. Probst, and Flemming Nielson. Sandboxing in myKlaim. In The First International Conference on Availability, Reliability and Security, ARES 2006, 2006. 22. Jane Hillston. A Compositional Approach to Performance Modelling. Cambridge University Press, 1996. 23. UML Model Translator for Model Checking (Hugo/RT). www.pst.ifi.lmu.de/projekte/hugo. Last visited: June 2006. 24. IST-FET Global Computing I Initiative Project DEGAS. www.omnys.it/degas/. Last visited: June 2006. 25. Fr´ed´eric Jouault and Ivan Kurtev. Transforming Models with ATL. In MoDELS Satellite Events, LNCS, pages 128–138. Springer, Berlin, 2005. 26. H. Koshutanski, F. Martinelli, P. Mori, and A. Vaccarelli. Fine-grained and history-based access control with trust management for autonomic grid services. In Proc. of Internat. Conf. on Autonomic and Autonomous Systems (ICAS06), IEEE Computer Society, 2006. 27. Marta Kwiatkowska, Gethin Norman, and David Parker. PRISM: Probabilistic symbolic model checker. In A.J. Field and P.G. Harrison, editors, Proc. of the 12th Int. Conf. on Modelling Tools and Techniques for Computer and Communication System Performance Evaluation, LNCS 2324, pages 200–204, London, UK, April 2002. Springer-Verlag.

Semantic-Based Development of Service-Oriented Systems

45

28. Model Driven Architecture (OMG). www.omg.org/mda/. Last visited: June 2006. 29. Model Transformation Framework. www.alphaworks.ibm.com/tech/mtf. Last visited: June 2006. 30. Object Management Group (OMG). Unified Modeling Language: Superstructure, version 2.0. Specification, OMG, 2005. www.omg.org/cgi-bin/doc?formal/05-07-04. 31. Query/View/Transformation Specification Final Adopted Specification. www.omg.org/cgibin/doc?ptc/2005-11-01. Last visited: June 2006. 32. De Nicola R., Katoen J.P., Latella D., and Massink M. STOKLAIM: A Stochastic Extension of KLAIM. TR 2006-TR-01, ISTI, 2006. 33. SCA Consortium. Service Component Architecture, version 0.9. download.boulder.ibm. com/ibmdl/pub/software/dw/specs/ws-sca/SCA White Paper1 09.pdf. Specification, 2005. Last visited: June 2006. 34. SPIN Model Checker. www.spinroot.com. Last visited: June 2006. 35. Model Checker for UML Statechart Diagrams. fmt.isti.cnr.it/umc/. Last visited: June 2006. 36. UPPAAL Tool Environment. www.uppaal.com. Last visited: June 2006. 37. D´aniel Varr´o and Andr´as Pataricza. Generic and Meta-Transformations for Model Transformation Engineering. In Thomas Baar et al., editor, Proc. 7th Int. Conf. Unified Modeling Language (UML’04), LNCS 3273, pages 290–304. Springer, Berlin, 2004. 38. Martin Wirsing, Grit Denker, Carolyn Talcott, Andy Poggio, and Linda Briesemeister. A rewriting logic framework for soft constraints. In WRLA 2006, 6th International Workshop on Rewriting Logic and its Applications, April 2006. To appear in ENTCS, 2006. 39. Web Services Choreography Interface (WSCI). www.w3.org/TR/wsci. Last visited: June 2006. 40. Web Service Description Language (WSDL). www.w3.org/TR/wsdl. Last visited: June 2006.

JSCL: A Middleware for Service Coordination Gianluigi Ferrari1 , Roberto Guanciale2, and Daniele Strollo1,2 1 Dipartimento di Informatica, Universit`a degli Studi di Pisa, Italy {giangi, strollo}@di.unipi.it 2 Istituto Alti Studi IMT Lucca, Italy {roberto.guanciale, daniele.strollo}@imtlucca.it

Abstract. This paper describes the design and the prototype implementation of a middleware, called Java Signal Core Layer (JSCL), for coordinating distributed services. JSCL supports the coordination of distributed services by exploiting an event notification paradigm. The design and the implementation of JSCL has been inspired and driven by its formal specification given as a process calculus, the Signal Calculus (SC). At the experimental level JSCL has been exploited to implement Long Running Transactions (LRTs).

1 Introduction One important challenge of the Software Engineering field is represented by the so called Service Oriented Architectures (SOAs) [20]. In the SOA approach applications are developed by coordinating the behavior of autonomous components distributed over an overlay network. Middleware for coordinating services are extremely important to the success of SOAs. Several research and implementation efforts are currently devoted to design and to implement middleware for coordinating distributes services (see ORC [18], BPEL [19], WS-CDL [23] and SIENA [12] to cite a few). However, research is still underway. The aim of this paper is to contribute to this theme of research by developing a middleware for coordinating services based upon a formal basis. The strict integration between theory and practice is the key feature of our proposal. In particular, this paper describes the design and the prototype implementation of the JSCL middleware. At the abstract level JSCL takes the form of a process calculus, SC, a dialect of the Ambient Calculus [11] with asynchronous communication facilities. At the implementation level, JSCL takes the form of a collection of Java APIs. The starting point of our work is the event-notification paradigm. We assume to coordinate service behaviors through the exchange of (typed) signals. The basic building blocks of our middleware are called components. A component represents a “simple” service interacting though a signal passing mechanism. Components are basic computational units performing some internal operations and can be composed and distributed over a network. Composition of components, yields a new one that can be used in further compositions. Each component is identified by an unique name, which, intuitively, can be through as the URI of the published service. In this paper we assume as given

Research partially supported by the EU, within the FET GC Project IST-2005-16004 Sensoria, and FIRB Project TOCAI.IT.

E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, pp. 46–60, 2006. c IFIP International Federation for Information Processing 2006

JSCL: A Middleware for Service Coordination

47

the set of names of the components involved into a system with no assumption on the mechanisms adopted to retrieve them (e.g. UDDI service directories, registries, etc.). The signals exchanged among components are basically messages containing information regarding the managed resources and the events raised during internal computations. Signals are tagged with a meta type representing the class of events they belong to. Such meta type information is often referred to, in the literature (e.g. [15]), with the term topic. Hence components are reactive blocks that declare the subset of signals they are interested in together with their reactions upon event notifications. The reactions are modeled by associating functional modules to topics of received signals. Once a signal of a well defined topic is received, the proper reaction is activated. The way the events are notified to the subscribed components is strictly related to the specific coordination pattern chosen. Different conversational styles can be adopted to implement the way the participants are involved into a coordination, mainly split into two main groups: orchestration and choreography (as discussed in [4]). Briefly, the first solution defines an intermediate agent, the orchestrator, that is responsible to decide, at each step, which are the actions that must be performed by each component. The choreography, instead, identifies a more distributed scenario in which, each participant is responsible for its moves and the whole work-flow is executed following a pre-defined plan. Basically, the orchestration suggests a centralization point that is responsible for implementing the subscriptions and the notification forwarding. Such solution is closely related to the ideas of tuple space based systems and brokered event notification. Using the choreography, instead, each component can act both as publisher or subscriber for other components and the delivering of signals is implemented through peer-to-peer like structures. In this paper, we adopt the choreography approach since it better fits with the signal passing paradigm. This paper is organized as follows. Section 2 introduces the Signal Calculus (SC). SC is a calculus for describing coordination primitives for components interacting through a signal passing mechanism. Section 3 describes JSCL APIs and the way components can be programmed. Basically, JSCL is a ligthweight framework for modeling distributed services by composing components that use signals for notifying events to other interested components in the style of SC. In section 4, as a case study, we describe the usage of JSCL as programming middleware for Long Running Transactions (LRTs) [10].

2 Signal Calculus: SC The Signal Calculus (SC) is a process calculus in the style of [17, 11] specifically designed to describe coordination policies of services distributed over a network. SC describes computation via the choreography of local service behavior. In this section, we present the syntax and the operational semantics of SC. 2.1 SC Syntax The main concepts of SC are signals, components, reactions, flows and networks. The data carried by a signal are the signal name and the conversation schema. A signal name represents an identifier of the current conversation (e.g. the session-id) and a

48

G. Ferrari, R. Guanciale, and D. Strollo

conversation schema represents the kind of event (e.g. onMouseOver). New signals can be sent either by autonomous components or as reaction to other signals. In this paper, we present SC focusing only on the primitives needed to design coordination protocols. Hence, operations on conversation schemata are not defined, since they can be expressed at a higher level detail of abstraction. Of course, SC can be extended by adding types for conversation schemata (e.g. in the form of XML Schema) [2, 14, 8, 1]. A SC component is a wrapper for a behavior. Intuitively a SC component represents an autonomous service available over a network. Each SC component is uniquely identified by its name and contains a local behavior and an interface. Components can behave either as signal emitters or as signal handlers. Similarly to the event-notification pattern, signal handlers are associated to signals and are responsible for their management. The SC component interface is structured into reactions and flows. Reactions describe component behavior and the action of variable binding upon signal reception. Indeed, the reception of a signal acts like a trigger that activates the execution of a new behavior within the component. Orchestration among components is implemented through flows. Flows represent the local view (component view) of the choreography, that is the set of local communications that have to be performed to satisfy the choreography demands. Each component flow declares the associations among signals, the conversation schema and the set of handlers. The connections among components are strictly related to a particular conversation schema thus offering the possibility to express different topologies of connectivity, depending on the schema of the outgoing signals. Both component reactions and flows are programmable, and they can be dynamically modified by the components. Components are structured to build a network of services. A network provides the facility to transport envelopes containing the signals exchanged among components. We now introduce the main syntactic categories of our calculus together with some notational machineries. We assume a finite set of conversation schemata ranged by τ1 , ..., τk , a finite set of component names ranged by a, b, c... and a finite set of signal names ranged by s1 , s2 , .... We also assume a set Var of variable names whose typical elements are x, y, z.... We use a to denote a set of names a1 , ..., an . Finally, we use σ to denote a substitution from variable names to signal names. Reactions (R) are described by the following grammar: (R EACTIONS ) R ::= 0 Nil ∗(x : τ → B) Unit reaction R|R Composition A reaction is a set (possibly empty) of unit reactions. A unit reaction ∗(x : τ → B) triggers the execution of the behavior B upon reception of a signal tagged by the schema τ. Notice that x : τ acts as a binder for the variable x within the behavior B. The syntax of behaviors will be given below. As usual we assume to work up-to alpha-conversion. Free and bound names are defined in the standard way. Flows (F) are described by the following grammar: (F LOWS ) F ::= 0 Nil τ a Unit flow F • F Composition

JSCL: A Middleware for Service Coordination

49

A flow is a set (possibly empty) of unit flows. A unit flow τ a describes the set of component names a where outgoing signals having τ as conversation schema have to be delivered. Reactions and flows are defined up-to a structural congruence (≡). Indeed, we assume that • and | are associative, commutative and with 0 behaving as identity. Notice that such equations allow us to freely rearrange reactions and flows. We define two auxiliary schema functions S(R) and S(F) that, respectively, return the set of conversation schemata on which the reaction R and the flow F are defined. S(0) = 0/ S(∗(x : τ → B)) = {τ} S(R1 |R2 ) = S(R1 ) ∪ S(R2)

S(0) = 0/ S(τ a) = {τ} S(F1 |F2 ) = S(F1 ) ∪ S(F2)

We say that a reaction is well-formed (and we write R) if there is no overlay among the conversation schemata triggered. The notion of well-formed reaction is inductively defined below. R1 R2 S(R1 ) ∩ S(R2) ≡ 0/ ∗(x : τ → B) (R1 |R2 ) 0 We also introduce two projection functions R ↓s:τ and F ↓τ ; the first takes a wellformed reaction R and a signal s of schema τ and returns a pair consisting of the variable substitution and the activated behavior. The second projection takes a flow F and a schema τ and returns the set of component names linked to the flow having schema τ. The two projections are defined below. 0 ↓s:τ = ({}, 0) (∗(x : τ → B)|R) ↓s:τ = ({s/x}, B) (∗(x : τ1 → B)|R) ↓s:τ = R ↓s:τ i f τ1 =τ

0 ↓τ = {} (τ a • F) ↓τ = a ∪ (F ↓τ ) (τ1 a • F) ↓τ = F ↓τ i f τ1 =τ

Finally we say that a flow is well-formed (and we write F) if there is no overlay among the linked components for all conversation schemata. The notion of well-formed flow is inductively defined below. / F1 F2 ∀τ∈(S(F1 )∪S(F2 )) (F1 ↓τ ∩F2 ↓τ ≡ 0) 0

(τ a)

(F1 • F2)

Hereafter, we assume that reactions and flows are always well-formed. Component behaviors (B) are defined by the following grammar: (B EHAVIORS ) B ::= 0 +R[x : τ → B] +F[τ a] s¯ : τ.B B|B !B

Nil Reaction update Flow update Asynchronous signal emission Parallel composition Bang

A reaction update +R[x : τ → B] extends the reaction part of the component interface, providing the ability to react to a signal of schema τ activating the behavior B. Such

50

G. Ferrari, R. Guanciale, and D. Strollo

operation ensures that the resulting reaction is well-formed and permits to dynamically change the reaction interface. Similarly, a flow update +F[τ a] extends the component flows, appending the component names in a to the set of component names to which the signals of schema τ are delivered. An asynchronous signal emission s¯ : τ.B first spawns into the network a set of envelopes containing the signal s, one for each component name declared in the flow having schema τ, and then activates B. As usual, the bang replication !B represents a behavior that can always activate a new copy of the behavior B. When it is clear from the context, we will omit the Nil behavior, writing s¯ : τ for s¯ : τ.0 and B for B|0. Networks (N) are defined by the following grammar: (N ETWORKS ) N ::= 0/ a[B]RF N||N < s : τ@a >

Empty net Component Parallel composition Signal envelope

A component a[B]RF describes a component of name a with behavior B, reaction R and flow F. A signal envelope < s : τ@a > describes a message containing the signal s of schema τ whose target component is the component named a. We use ∑x∈a B to denote the parallel composition of B{n/x} for each name n in the set a. A SC component is closely related to the notion of ambient [11] as it describes a behavior wrapped within a named context. Differently from the ambient calculus, SC networks are flat, that means there is no hierarchy of components. Examples. To better present how the basic SC concepts can be used to model service coordination we introduce a simple example. Suppose to have a producer p and a consumer c both accessing a shared data space. We assume a synchronization policy, namely a consumer can get its resource only after a producer has produced it. The problem can be modeled as displayed in Figure 1. P starts its execution performing the (internal) behavior B p that modifies the state of the data space that has to be read by C. When the data have been modified, B p executes a signal emission of a signal of schema produced (s¯ : produced) in order to inform C that the required resources are now available. Upon notification, C automatically starts and takes the resource in the data space performing its internal behavior Bc . We assume that Bc executes a signal emission of a signal of schema consumed (x¯ : consumed) in order to inform P that it can produce a new resource. Notice that the name of the signal emitted is the same of the signal received. Moreover C is not a running process, it is an idle entity that is activated only at signal reception. x:consumed→x:produced ¯

P p[s¯ : produced] producedc

x:produced→x:consumed ¯

C c[0]consumedp

Net P||C

Fig. 1. Components p and c share a data space

In the previous example, we presented two components with a statically defined choreography. However the producer and the consumer can be dynamically linked

JSCL: A Middleware for Service Coordination

51

together (e.g. at the start up phase) using reaction update and flow update, thus providing a dynamic choreography scenario. This example is expressed in SC through the components and the network defined in Figure 2. Notice that, since component name passing has not been modeled in SC, we assume each component knows the names of the externally published components. We can enrich the SC core providing component name communication, thus yielding a true dynamic choreography in the style of the π-calculus [17]. P p[+F[produced c]| + R[x : consumed → x¯ : produced.0]|s¯ : produced]00 C c[+F[consumed p]| + R[x : produced → x¯ : consumed.0]]00 Net P||C Fig. 2. Components p and c share a data space

2.2 SC Semantics SC semantics is defined in a reduction style [5]. We first introduce a structural congruence over behaviors and networks. The structural congruence for component behaviors (≡B ) is defined by the following rules: B1 |B2 ≡B B2 |B1

/ ≡B B 0|B

(B1 |B2 )|B3 ≡B B1 |(B2 |B3 )

!B ≡B B|!B

As usual the bang operator allows us to express recursive behaviors. Structural congruence for networks ≡N is defined by the following rules: N||M ≡N M||N / 0F a[0]

≡N 0/

(M||N)||O ≡N M||(N||O)

/ 0||N ≡N N

F 1 ≡ F 2 R1 ≡ R2 B1 ≡ B B 2 1

2

a[B1 ]RF 1 ≡N a[B2 ]RF 2

A component having nil behavior and empty reaction can be considered as the empty network since it has no internal active behavior and cannot activate any behavior upon reception of a signal. Two components are considered structurally congruent if their internal behaviors, reactions and flows are structurally congruent. When it is clear from the context, we will use the symbol ≡ for both ≡B and ≡N . The reduction relation of networks (→) is defined by the rules in Figure 3. The rule (RUPD) extends the component reactions with a further unit reaction (the parameter of the primitive). The rule requires that the resulting reaction is well-formed. The rule (FUPD) extends the component flows with a unit flow. Also in this case a well-formed resulting flow is required. The rule (OUT) first takes the set of component names a that are linked to the component for the conversation schema τ and then spawns into the network an envelope for each component name in the set. The rule (IN) allows a signal envelope to react with the component whose name is specified inside the envelope. Notice that signal emission rule (OUT) and signal receiving rule (IN) do not consume, respectively, the flow and the reaction of the component. This feature provides SC with a further form of recursion behavior. The rules (STRUCT) and (PAR) are standard rules. In the following, we use N →+ N1 to represent a network N that is reduced to N1 after a finite number of steps.

52

G. Ferrari, R. Guanciale, and D. Strollo R| ∗ (x : τ → B)

a[+R[x : τ → B]|Q]RF

R|∗(x:τ→B) → a[Q]F

F ↓τ = a a[s¯ : τ.P|Q]RF

→ a[P|Q]RF |

∑

ai ∈a

N ≡ N1 → M2 ≡ N3 N → N3

F • τ a

(RUPD)

< s : τ@ai >

a[+F[τ a]|Q]FR → a[Q]RF•τa

(FUPD)

R ↓s:τ = (σ, B)

(OUT )

< s : τ@a > |a[Q]RF → a[Q|σB]RF N → N1

(ST RUCT )

N|N2 → N1 |N2

(IN)

(PAR)

Fig. 3. Semantic Rules

Examples. To describe how SC semantics rules work, we provide a short description of the execution of the examples given in Figure 1 and 2. As a shorthand, we write τ p for the conversation schema produced and τc for consumed. The network in Figure 1 contains only one active component; namely the producer p emits the signal, spawning into the network an envelope for the consumer c. This is represented by: (τ p c) ↓τ p = c p[s¯ :

(x:τc →x:τ ¯ p) τ p ](τ p c)

(x:τ →x:τ ¯ p)

c → p[0](τ p c)

| < s : τ p @c >

(OUT )

The envelope reacts with the consumer component, activating inside the component the behavior of the corresponding reaction: (x : τ p → x¯ : τc ) ↓s:τ p = ({s/x}, x¯ : τc ) (x:τ →x:τ ¯ c)

p < s : τ p @c > |c[0](τc p)

(x:τ →x:τ ¯ c)

p → c[s¯ : τc ](τc p)

(IN)

In a similarly way, the consumer component c sends an envelope to the producer p, thus activating the proper internal behavior: (x:τ →x:τ ¯ p)

c p[0](τ p c)

(x:τ →x:τ ¯ c)

p |c[s¯ : τc ](τc p)

(x:τ →x:τ ¯ p)

c →+ p[s¯ : τ p ](τ p c)

(x:τ →x:τ ¯ c)

p |c[0](τc p)

In the second example all the two components have active internal behaviors. The producer can update its flow by adding the link to the consumer for signals of schema τ p , as follows: (0 • τ p c) p[+F[τ p c] | + R[x : τc → x¯ : τ p ] | s¯ : τ p ]00 → p[+R[x : τc → x¯ : τ p ] | s¯ : τ p ]0(τ p c) Then we apply the reduction rule for the reaction update of the producer: (0|x : τc → x¯ : τ p ) (x:τ →x:τ ¯ p)

c p[+R[x : τc → x¯ : τ p ]|s¯ : τ p ]0(τ p c) → p[s¯ : τ p ](τ p c)

JSCL: A Middleware for Service Coordination

53

After these reductions the producer component has created a link to the consumer for signals of schema τ p and can receive signals of schema τc . In a similar way the consumer component updates its reaction and flow: (x:τ →x:τ ¯ p)

c p[s¯ : τ p ](τ p c)

(x:τ →x:τ ¯ p)

c |c[+F[τc p]|+ R[x : τ p → x¯ : τc ]]00 →+ p[s¯ : τ p ](τ p c)

(x:τ →x:τ ¯ c)

p |c[0](τc p)

3 Java Signal Core Layer Java Signal Core Layer (JSCL) consists of a collection of Java API implementing the coordination primitives formally described by SC. In JSCL, known concepts of the event-based paradigm are considered in a distributed and open environment where components can be allocated on different execution sites and can join existing execution of other components. In the following, we often refer to components as services meaning that the current version of JSCL is specifically tailored to coordinate web services. However JSCL can be easily adapted to different technologies (e.g. CORBA). The essential ingredients of JSCL are signals, components, signal links and input ports corresponding, respectively, to the concepts of signals, components, flows and reactions defined in section 2. The notion of SC network is implemented by introducing an intermediate layer, the Inter Object Communication Layer (IOCL). The IOCL contains the set of primitives for creating, publishing, retrieving and connecting components. These operations are strictly related to the execution environment. To support multiple definitions of IOCL, these primitives have been developed as plugins that can be directly accessed at run-time. Such layer has been introduced to make JSCL more flexible and allows the interoperability of different technologies for inter object communication like CORBA, Web Services (see [22] for more details). In particular, the IOCL layer provides the mechanisms to implement the data serialization (e.g. SOAP message envelops for WSs, etc.) and the deployment phase (e.g. stub generation, dynamic proxy binding, etc.). Moreover each IOCL plugin defines the way components are identified by extending the basic interface ComponentAddress. The way components are named in JSCL strictly depends over the underlying overlay network adopted (e.g. an URL if the selected iocl plugin is based on WSs or CORBA, a couple (IP, port) if sockets are used, an unique name if memory access is used etc.). In JSCL, the set of information conveyed in each signal is split into two parts. The first contains information useful for coordination: the unique name of the signal instance and its type. The second part contains the payload of current request, the session data. Notice that the session data are not modeled in SC since the calculus only deals with the primitives needed for implementing the coordination among components. Signals are classified into signal types (types for short) that associate each signal to the class of events they belong to. Signal types are namely the SC conversation schemata. Signals have been modeled as non persistent entities; once the notification for an event has been delivered to all the interested handlers, the corresponding signal is removed from the system. This property is mandatory if we want to keep the distribution of the connections and their management. This feature, however, is not a limitation: persistent signals can be easily introduced in our middleware. Signals, in JSCL, are always sent in non anonymous way, meaning that it is always possible to know the sender of

54

G. Ferrari, R. Guanciale, and D. Strollo

each signal. Such constraint is useful, at implementation level, if we want to extend the middleware with authoring primitives on the links. The event notification mechanism of subscription is implemented through the creation of input ports and signal links connecting components. These operations correspond respectively to the primitives reaction update and flow update defined in SC. An input port is a tuple i = (sigT , Task) meaning that the port can receive signals of type sigT whose handler is the process Task. Each component is able to specify only one input port for each sigT . The notion of input port i, signal type sigT and handling task Task map respectively the reaction R, the conversation schema τ and the behavior B defined in SC. The component interface is obtained by taking the set of sigT for which there is a bound input port, and the set of sigT for which there is at least a signal link defined. Such sets in SC are given respectively by the auxiliary schema functions S(R) and S(F). Figure 4 shows a graphical notation for JSCL input ports.

Fig. 4. JSCL input port

Connections between two components are implemented through signal links. A signal link is a tuple l = (sigT , S, R) and represents an virtual channel among the signals of type sigT emitted by S and the handler R. Creating a new link between S and R requires that the input port corresponding to sigT has been previously created by R with the right permissions for S. Basically, signal links are the linguistic device of JSCL for subscription/notification. We already pointed out that several receivers can be linked with the same signal type and the same sender. All the signal links created are well formed conforming to the rules defined in section 2.1. Namely further creations of links (sigT , S, R) are idempotent. The primitive for creating new signal links can be invoked outward the components by an external application that will connect all (or a subset of) the components among them and this will be the only agent conscious of the topology of the network. This assumption is useful to preserve the autonomy of the components from the particular system in which they are acting. The creation of a link is implemented through the IOCL component. Links in JSCL are typed, unidirectional and “peer-to-peer”. More complex scenarios (e.g., multi-casting, bi-directionality, etc.) can be obtained by introducing the suitable notions of links. For instance, multi-casting is achieved by connecting the same emitter to several handlers. Example. We now describe how the producer/consumer example modeled in SC in section 2.2 can be implemented by exploiting the JSCL APIs. This provides a basic idea of the programmability offered by the middleware. The Figure 5 displays the choreography between two components P and C representing respectively the services implementing

JSCL: A Middleware for Service Coordination

55

a producer and a consumer. The topics of signals exchanged in the system are sig prod and sigcons corresponding to notifications for events produced and consumed which can be raised respectively from P and C.

Fig. 5. JSCL: producer-consumer example

The designing of the whole application can be logically split into three phases: i) the creation of the components, ii) the declaration of the reactions associated to the components and iii) the publication of services and the designing of the connections. In the following, we assume to exploit the XSOAP [13] IOCL plugin, and to use the ServiceAddress1 class, essentially an URL, to define component names.

I OC LPl u g i n Lo ad er l o a d e r = new I OC LPl u g i n Lo ad er ( ” j s c l . c o r e . IOCL . XSoap . IOCLImpl” ) ; IOCLPluginI i o c l = l o a d e r . getIOCLInstance ( ) ; S e r v i c e A d d r e s s P a d d r e s s = new S e r v i c e A d d r e s s ( ” h t t p ” , ” j o r d i e ” , 9 0 9 2 , ” ” , ” P r o d u c e r ” ) ; S e r v i c e A d d r e s s C a d d r e s s = new S e r v i c e A d d r e s s ( ” h t t p ” , ” j o r d i e ” , 9 0 9 2 , ” ” , ” Consumer ” ) ; Gen er i cC o mp o n en t p r o d u c e r = i o c l . c r e a t e C o m p o n e n t ( P a d d r e s s ) ; Gen er i cC o mp o n en t co n su mer = i o c l . c r e a t e C o m p o n e n t ( C a d d r e s s ) ;

Code 1. Producer & consumer creation The Code 1 illustrates the JSCL code for creating the needed services. First we instantiate a new IOCLPlugin that will be used to create the components. The creation of new components occurs by invoking the method createComponent, whose parameter is the address of the component itself. Alternatively, the iocl layer can be used to retrieve already published services by invoking the method iocl.getComponent which, given an address, returns a component proxy bound to it. Once our components have been built, we must program their reactions by binding them to new input ports as shown in Code 2. Roughly Code 2 describes the processes corresponding to the Taskcons and Task prod depicted in Figure 5. The last step is the publication of the created services and the creation of links as shown in Code 3. Once the orchestration has been declared, we can start its execution by the signal emission of the producer component, which is the only active internal behavior. Here, for simplicity, the primitives for creating and publishing the components depicted in 1

ServiceAddress is an implementation of ComponentAddress defined in section 3.

56

G. Ferrari, R. Guanciale, and D. Strollo co n su mer . a d d I n p u t P o r t ( new S i g n a l I n p u t P o r t ( S i g n a l T y p e s . S i g p r o d , new S i g n a l H a n d l e r T a s k ( co n su mer ) { public Object handle ( Signal s ig n a l ){ try { / / Consumes t h e r e s o u r c e ... s i g n a l . setType ( Si g n al Ty p es . Si g co n s ) ; th is . g et Paren t ( ) . emitSignal ( si g n a l ) ; } catch ( G en er i cEx cep t i o n e ){ e . printStackTrace ( ); } return nul l ; } } ) );

producer . addInputPort ( new S i g n a l I n p u t P o r t ( S i g n a l T y p e s . S i g c o n s , new S i g n a l H a n d l e r T a s k ( p r o d u c e r ) { public Object handle ( Signal s i g n al ){ try { / / Produces t h e reso u rce ... s i g n a l . setType ( Si g n al Ty p es . Si g p r o d ) ; thi s . g et Paren t ( ) . emitSignal ( si g n al ) ; } catch ( G en er i cEx cep t i o n e ){ e . printStackTrace () ; } return nul l ; } } ) );

Code 2. Binding of input ports / / Component p u b l i c a t i o n i o c l . registerComponent ( producer ) ; i o c l . r e g i s t e r C o m p o n e n t ( co n su mer ) ; / / Creation of l i n k s i o c l . c r e a t e L i n k ( Si g n al Ty p es . Sig prod , Paddress , Caddress ) ; i o c l . c r e a t e L i n k ( Si g n al Ty p es . Sig cons , Caddress , Pad d r ess ) ;

Code 3. Link creation Code 1 and in Code 3, for simplicity, are collapsed into an unique block, using the same machine. Obviously more sophisticated strategies can be adopted, e.g. the component can be deployed into different machines, in such case the method createComponent is replaced by the getComponent method. JSCL Environment. We have presented above the primitives provided by JSCL for declaring reactive components and for coordinating them via event notification. Other systems have been introduced in [22] to describe these issues (service declaration and coordination) in XML. On the one side, each component can be defined with an XML structure giving the signal types to which it reacts, the iocl support and the address to which it will be bound. These files are processed to obtain the corresponding Java skeleton code. On the other side, the coordination among components can be described in a separated XML document containing the definition of the services involved and their connections. Such file can be interpreted so to create the required coordination structure.

4 Long Running Transaction JSCL has been adopted in [9] for implementing a framework for Long Running Transactions. The deployment phase has been driven by Na¨ıve Sagas [10], a process calculus for compensable transactions, which defines Long Running Transactions in terms of logical blocks (transactional flows) orchestrating to reach a common goal. The building block of Na¨ıve Sagas is the compensation pair construct. Given two actions A and B, the compensation pair A ÷ B corresponds to a process that uses B as compensation for A. Intuitively, A ÷ B yields two flows of execution: the forward flow and the backward flow. During the forward flow, A ÷ B starts its execution by running A and then,

JSCL: A Middleware for Service Coordination

57

when A finishes: (i) B is “installed” as compensation for A, and (ii) the control is forwardly propagated to the other stages of the transactions. In case of a failure in the rest of the transaction, the backward flow starts so that the effects of executing A must be rolled back. This is achieved by activating the installed compensation B and afterward by propagating the rollback to the activities that were executed before A. Notice that B is not installed if A is not executed. With JSCL the transactional blocks are obtained by suitable wrappers, Transactional Gates (T G), that use signal passing for activating the flows. The possible signal types that can be exchanged are: sigFW , which activates the forward flow, sigRB , for activating the backward flow (rollback), sigCM , propagated to notify that the whole orchestration has been successful executed (commit) and sigEX , exchanged to notify that the rollback phase has failed and the state of the whole transaction is inconsistent (also referred as abnormal termination). When a T G receives a signal typed sigFW , it tries to execute the main activity A; whenever the execution of A normally terminates, the signal is propagated to the next stage. On the contrary, if A throws an exception, a signal typed sigRB is propagated to the previous stage (the rollback is propagated in backward way). Analogously when a sigRB is received by a T G, it tries to execute the compensating activity B, if it fails, throwing an exception, the signal is set to sigEX to notify that the rollback phase has failed and the state of the whole transaction is inconsistent, otherwise the rollback signal is propagated. The JSCL implementation of Na¨ıve Sagas provides components implementing parallel and sequential structural composition of transactional gates. The composition constructs keep the structure of T G and can be reused in further compositions. In Figure 6 it is shown how a Na¨ıve Sagas compensable process A1 ÷ B1 ; A2 ÷ B2 ; A3 ÷ B3 , is implemented using the JSCL graphical notation.

Fig. 6. JSCL Transactional Gates: an example

The JSCL implementation of transactional flows can be formally described in SC as follows. We assume given two functions [[A]] f w (x) and [[A]]rb (x) that translate the Na¨ıve Sagas atomic activity A to SC internal behaviors, working on signal named x. We assume that the first function translates the successful return statements into the signal emission x¯ : f w.0 and the exception rising into x¯ : rb.0, and that the second function translates the successful return statements into the signal emission x¯ : rb.0 and the exception rising into x¯ : ex.0. The example Na¨ıve Sagas compensable process, previously described, is so represented by the SC network [[P]]:

58

G. Ferrari, R. Guanciale, and D. Strollo x: f w→[[A1 ]] f w (x) | x:rb→[[B1 ]]rb (x)

[[A1 ÷ B1 ]] p1 [0] f wp2

x: f w→[[A ]]

2 fw [[A2 ÷ B2 ]] p2 [0] f wp3 •rbp 1

(x) | x:rb→[[B2 ]]rb (x)

x: f w→[[A3 ]] f w (x) | x:rb→[[B3 ]]rb (x)

[[A3 ÷ B3 ]] p3 [0]rbp2 [[P]]

[[A1 ÷ B1 ]] | [[A2 ÷ B2]] | [[A3 ÷ B3]]

5 Concluding Remarks We have introduced a core framework to formally describe coordination of distributed services. This framework has driven the implementation of a middleware for programming coordination policies by exploiting the event notification paradigm. In our approach the event notification paradigm supports fully distribution. Unlike the current industrial technologies concerning service coordination (e.g. BPEL [19]), our solution is based on top of a clear foundational approach. This should provide strategies to prove coordination properties based on model checking or type systems. A semantic definition of the basic set of primitives can also drive the implementation of translators from industrial specification languages (e.g. WS-CDL [23]) to our framework. Our approach differs from other event based proposals (e.g. SIENA [12]), since focuses the implementation on the more distributed environment of services. Our formal approach is based on process calculus literature (e.g. ccs [16], π-calculus [17]). Differently from π-calculus, the computation is boxed into components, in the style of Ambient Calculus [11]. Moreover we avoid components nesting, to model a flat topology of the network and to provide a more loose-coupled programming model. As described before, SC models connections among components with peer-to-peer like structures (flows). Moreover, such flows can be logically grouped into multicastchannels, identified by the conversation schema. This provides a communication pattern closed to the one presented in [21], even if SC does not deal with connection mobility. There are several coordination models based on connection among components that provide dynamic reconfiguration (e.g. Reo [3]). Our work mainly differs from Reo on the communication model adopted for composition. Reo is a channel based framework, while SC is an event based one. Hence, Reo handles component migration and channel management as basic notions, while SC focuses on the activities performed and on the coordination over dynamic network topologies. In this paper, we focused on the coordination aspects. However the calculus SC can be enriched by considering signals as tagged nested lists [2, 14], which represent XML documents, and conversation schemata as abstractions for XML Schema types [1]. This extension of conversation schemata lead to a more general notion of reaction based on pattern matching or unification in the style of [6]. A further extension can provide component and schema name passing, modelling a more dynamic scenario. SC can describe dynamic orchestrations trough reaction and flow update primitives. These primitives have effects only on the component view of the choreography, namely a component cannot update the reaction or the flow of another component. Flow management can be enriched providing a primitive to update remote flows. This primitive

JSCL: A Middleware for Service Coordination

59

should spawn a flow update envelope into the network. The update of remote reaction is more difficult, since a reaction contains code and than is necessary to formalize and implement the code migration.

Bibliography [1] Xml schema. Technical report, W3C, 2004. [2] L. Acciai and M. Boreale. Xpi: A typed process calculus for xml messaging. In M. Steffen and G. Zavattaro, editors, FMOODS, volume 3535 of Lecture Notes in Computer Science, pages 47–66. Springer, 2005. [3] F. Arbab. Reo: a channel-based coordination model for component composition. Mathematical. Structures in Comp. Sci., 14(3):329–366, 2004. [4] B. Benatallah, F. Casati, F. Toumani, and R. Hamadi. Conceptual modeling of web service conversations. In J. Eder and M. Missikoff, editors, CAiSE, volume 2681 of Lecture Notes in Computer Science, pages 449–467. Springer, 2003. [5] G. Berry and G. Boudol. The chemical abstract machine. Theoretical Comput. Sci., 96(1):217–248, April 1992. [6] M. Boreale, M. G. Buscemi, and U. Montanari. A general name binding mechanism. In R. D. Nicola and D. Sangiorgi, editors, TGC, volume 3705 of Lecture Notes in Computer Science, pages 61–74. Springer, 2005. [7] M. Bravetti, L. Kloul, and G. Zavattaro, editors. Formal Techniques for Computer Systems and Business Processes, European Performance Engineering Workshop, EPEW 2005 and International Workshop on Web Services and Formal Methods, WS-FM 2005, Versailles, France, September 1-3, 2005, Proceedings, volume 3670 of Lecture Notes in Computer Science. Springer, 2005. [8] A. Brown, C. Laneve, and L. G. Meredith. Piduce: A process calculus with native xml datatypes. In Bravetti et al. [7], pages 18–34. [9] R. Bruni, G. L. Ferrari, H. C. Melgratti, U. Montanari, D. Strollo, and E. Tuosto. From Theory to Practice in Transactional Composition of Web Services. In Bravetti et al. [7], pages 272–286. [10] R. Bruni, H. C. Melgratti, and U. Montanari. Theoretical foundations for compensations in flow composition languages. In J. Palsberg and M. Abadi, editors, POPL, pages 209–220. ACM, 2005. [11] L. Cardelli and A. D. Gordon. Mobile ambients. In M. Nivat, editor, FoSSaCS, volume 1378 of Lecture Notes in Computer Science, pages 140–155. Springer, 1998. [12] A. Carzaniga, D. S. Rosenblum, and A. L. Wolf. Design of a scalable event notification service: Interface and architecture. Technical Report CU-CS-863-98, Department of Computer Science, University of Colorado, Aug. 1998. [13] Department of Computer Science. Indiana University. XSoap. www.extreme.indiana. edu/xgws/xsoap/. [14] H. Hosoya and B. C. Pierce. Xduce: A statically typed xml processing language. ACM Trans. Internet Techn., 3(2):117–148, 2003. [15] Y. Liu and B. Plale. Survey of publish subscribe event systems. Technical Report 574, Department of Computer Science, Indiana University. [16] R. Milner. Communication and Concurrency. Printice Hall, 1989. [17] R. Milner. The polyadic π-calculus: A tutorial. In F. L. Bauer, W. Brauer, and H. Schwichtenberg, editors, Logic and Algebra of Specification, Proceedings of International NATO Summer School (Marktoberdorf, Germany, 1991), volume 94 of Series F. NATO ASI, 1993. Available as Technical Report ECS-LFCS-91-180, University of Edinburgh, October 1991.

60

G. Ferrari, R. Guanciale, and D. Strollo

[18] J. Misra. A programming model for the orchestration of web services. In SEFM, pages 2–11. IEEE Computer Society, 2004. [19] OASIS Bpel Specifications. OASIS - BPEL. http://www.oasis-open.org/cover/ bpel4ws.html. [20] M. Papazouglou and D. Georgakopoulos. Special issue on service oriented computing. Commun. ACM, 46(10), 2003. [21] F. Peschanski. Mobile agents in interaction space. In C. Canal and M. Viroli, editors, FOCLASA’05, volume 154(1), pages 63–82, 2005. [22] D. Strollo. Java Signal Core Layer (JSCL). Technical report, Dipartimento di Informatica, Universit`a di Pisa, 2005. Available at http://www.di.unipi.it/˜strollo. [23] W3C. Web Services Choreography Description Language (v.1.0). Technical report.

Analysis of Realizability Conditions for Web Service Choreographies Raman Kazhamiakin and Marco Pistore DIT, University of Trento via Sommarive 14, 38050, Trento, Italy {raman, pistore}@dit.unitn.it Abstract. Web service choreography languages allow for the description of multipart collaborations from a global point of view, specifying the information exchanged by the participants in order to accomplish a common business goal. An important issue, emerging from the choreography modelling, is the protocol realizability, i.e., the possibility to extract the local speciﬁcations of the participants, so that their interactions preserve certain crucial properties of the global description. In this paper, we present a formal framework for the deﬁnition of both the global protocols and the local speciﬁcations. The key feature of the approach is that it allows for arbitrary communication models (synchronous/asynchronous, with/without buﬀers) in the composition of the local speciﬁcations. We introduce a hierarchy of realizability notions that allows for capturing various properties of the global speciﬁcations, and associate speciﬁc communication models to each of them. We also present an approach, based on the analysis of the communication models, that allows to associate a particular level of realizability to the global protocol speciﬁcation.

1

Introduction

Web service technology facilitates the development of complex distributed systems that span across the enterprise boundaries. It enables the speciﬁcation, deployment, and enactment of heterogeneous software components accessible on the web via standardized protocols. One of the fundamental ideas underlying the Web service technology is the possibility to provide composite business applications by integrating existing services. To make this possibility realistic, it is necessary to address the problem of the speciﬁcation and design of such compositions, taking into account the various aspects of a composition description. One of the key aspects of this description is the ability to represent the stateful and coordinated behavior of the composite system. A wide range of standards and languages has been proposed for capturing these aspects [1,2,3]. Among them, the choreography speciﬁcation languages, like e.g. Web Services Choreography Description Language (WS-CDL, [3]), are particularly relevant for the

This work is partially funded by the MIUR-FIRB project RBNE0195K5, “KLASE”, by the MIUR-PRIN 2004 project “STRAP”, and by the EU-IST project FP6-016004 “SENSORIA”.

E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, pp. 61–76, 2006. c IFIP International Federation for Information Processing 2006

62

R. Kazhamiakin and M. Pistore

design phase of the composition, as they allow for the representation of the global observable behavior of the distributed business application. The choreography languages open up the possibility of applying a range of formal techniques for the analysis of Web service compositions. Particularly relevant is the problem of realizability of the choreography speciﬁcations, that is, the possibility to automatically extract from the choreography the behavioral skeletons of the participants so that the concrete implementations, built on the basis of these skeletons, are guaranteed to satisfy the choreography speciﬁcation. This problem is made diﬃcult by several crucial factors. First, the behavior of the application strongly depends on the way the services are exchanging the information, that is the communication model of the composition. The hypothesis of synchronous interactions, widely used for the analysis of service compositions, is not satisﬁed by many existing real-world applications. Moreover, the underlying interaction mechanism is not always known a priori, thus making problematic the usage of a particular model. Second, the strictness to which the application should satisfy the ordering constraints on messages and/or internal activities may diﬀer from one scenario to another. In order to address this diversity, the realizability model has to be ﬂexible, and should allow for an analysis which is parametric with respect to the set of requirements. In this paper we address the problem of analyzing the realizability of choreographic protocols. We present a hierarchy of realizability notions that allows for capturing a variety of the choreography properties, thus providing a basis for a more ﬂexible analysis. The presented approach is based on our previous work [4], where we give a formal model and analysis framework for the Web service compositions deﬁned as composition of local participants speciﬁcation. The key feature of that model is the deﬁnition of a parametric communication mechanism. More precisely, it is possible to specify diﬀerent communication models for the interaction among the participants by changing the number of queues, their alphabets, and ordering rules. Using this formalism, it is possible to determine the communication model that is adequate for a given composition, that is the one that allows for the most complete description of the composition behavior. In this work, we extend the approach of [4] and introduce a formalism for the global model that allows for the description of the compositions from a choreographic point of view. Furthermore, we express the problem of choreography realizability in terms of the composition of its local projections, and show how the hierarchy of the realizability notions is related to the hierarchy of communication models. Using this relation, we present an algorithm that allows to determine the appropriate level of the realizability, and the corresponding required conditions. The paper is structured as follows. Section 2 introduces the realizability problem using variants of a simple example. Sections 3 and 4 deﬁne the formal models for the description of the underlying systems from the global perspective and as a composition of interacting local services respectively. In Sect. 5 the realizability problem is formalized and described, and various properties of the global protocols are discussed in terms of the composition of local models. Section 6 presents the algorithm that permits to reason on the realizability properties of the global

Analysis of Realizability Conditions for Web Service Choreographies Buyer

Seller

CCA

63

Shipper

B: request :S S: offer :B B: accept :S S: check :A A: result :S S: confirm :B B: deliveryInfo :S S: orderDelivery :H H: delivery :B

Fig. 1. RFQ case study: nominal case

protocols, which is based on the analysis of the communication models of the compositions. Conclusions and related works are discussed in Sect. 7.

2

Choreography Models

We illustrate the problem of modelling and analyzing Web service choreographies by means of an example. In this example we model a composition of Web services from the global point of view. We incrementally present several variants of the scenario, illustrating the approach presented in this paper. The global representation of the composition is modelled using the WS-CDL language that allows to describe the observable behavior of the composite protocol. In our example we describe a simple business collaboration protocol for purchasing goods among a buyer, a seller, a credit card agency (CCA), and a shipper. The nominal case, deﬁned as a UML activity diagram, is presented in Fig. 1. The protocol is deﬁned as follows. First, the Buyer asks the Seller for a particular good, sending a request. The quote oﬀer is prepared and sent back to the Buyer that accepts it (interaction accept). Given the payment details, the Seller asks the CCA to verify the information, and after receiving a positive result message, sends a conﬁrmation to the Buyer. The Buyer sends the address information to the Seller, which forwards this data to the Shipper (orderDelivery message). Finally, the Shipper sends the delivery conﬁrmation to the Buyer (delivery). Given this global description, a straightforward step is to extract from it the local speciﬁcations of the participants. These speciﬁcations may be further detailed and serve as the basis for the composition implementation. In this example, the local speciﬁcations can be easily obtained by projection of the global model onto a particular participant. Moreover, the composition of these projections will behave exactly as the global speciﬁcation, and therefore, the global model is realizable. This is, however, not always the case. Consider a modiﬁcation of the nominal case represented in Fig. 2(a). Here, after the orderDelivery interaction has been performed, the internal activity prepareToDelivery is invoked in the Buyer role. While the global model requires that the delivery is performed after this activity, the composition of projections is not able to guarantee this. Indeed,

64

R. Kazhamiakin and M. Pistore Buyer

Seller

CCA

Shipper

Buyer

Seller

Shipper

S: confirm :B

S: confirm :B B: deliveryInfo :S

B: deliveryInfo :S

S: orderDelivery :H

S: orderDelivery :H B: prepareToDelivery

H: delivery :B

H: delivery :B

B: notify :A

(a) Buyer

CCA

Seller

(b) CCA

Shipper

Buyer

Seller

B: request :S S: offer :B S: confirm :B S: orderDelivery :H

timeout H: delivery :B

(c)

B: accept :S

S: refresh :B

(d)

Fig. 2. RFQ case study: implementation variants

this internal activity of the Buyer is independent from the emission of delivery notiﬁcation of the Shipper, and therefore the realizability is violated. In order to resolve this problem, either the speciﬁcation should be modiﬁed and an additional synchronization interaction should be added, or the ordering requirement should be relaxed, allowing for interleaving internal activities and interactions. A diﬀerent modiﬁcation of the nominal case is presented in Fig. 2(b). Here, after the orderDelivery interaction, the CCA is notiﬁed about the order by the notify message. In this case, also the ordering of interactions is violated, since the notiﬁcation of CCA is independent from the emission of the delivery notiﬁcation. We remark however that, while the order of actions speciﬁed in the global protocol is not respected, the states of the participants and the state of the protocol is not aﬀected. That is, this scenario satisﬁes the property that, even if the actions are reordered, the outcome of the execution is the same. In the implementation presented in Fig. 2(c) this property does not hold. In this scenario the addressing information of the Buyer is not required, and the conﬁrmation and the order delivery activities may be invoked in parallel. This may lead to the following problem in the composition. The local speciﬁcation of the Buyer requires that the delivery notiﬁcation arrives after the conﬁrmation from the Seller. Due to the fact that the Seller and the Shipper are independent, this order may be violated, and the ﬁnal state of the Buyer depends on the implementation of the underlying communication system. Indeed, if the messages may be stored in queues, and, moreover, the messages from diﬀerent partners are managed independently, then the Buyer process is not blocked, the messages are simply consumed in a diﬀerent order. As a result, under certain assumptions on the middleware implementation and the usage of local variables, the global protocol may still be considered correct regardless the message ordering problems.

Analysis of Realizability Conditions for Web Service Choreographies

65

Contrary to the above examples, the acceptable conditions for the scenario presented in Fig. 2(d) are much more diﬃcult to deﬁne. Here, if the Buyer does not provide an acceptance within a given period of time, the Seller refreshes the good information, sending a corresponding message refresh. The ﬁrst problem is that the refresh message may be sent simultaneously with the acceptance message, even if the good is not in the stock anymore. The refresh message is ignored and the state of the protocol is incorrect. Second, if the time required for the oﬀer processing by the Buyer exceeds the refreshment timeout, then the Seller will send more and more messages, and the queue of the Buyer will grow unboundedly. Finally, when the Buyer sends an acceptance message after several oﬀer refresh messages, it is not clear which one is accepted due to possible reorderings and intersections of messages leading again to an incorrect state. This example shows the complexity of deﬁning realizability in a way that makes it possible to deal with scenarios like the ones illustrated above.

3

Global Model

In this section we introduce the formal model for representing the choreography speciﬁcation. This global model deﬁnes the dynamic aspects of the service compositions from a global point of view by deﬁning the involved participants and their interactions. The formalism follows the approach of [5,6] for modelling the global interaction protocols of Web service compositions. The model is based on the notion of roles and actions. A role represents the behavior of a particular participant of the composed system. During the protocol execution, the ith role can be in one of its possible states Si (one of which is marked as an initial state s0 i ) and can evolve to new states as a result of performing some actions. We model message communications as interactions deﬁned on a set of service operations (or message types) M. The signature of the interaction ao has the form (rs , rd , μ), where rs and rd are the roles of the sender and receiver respectively, μ is the service operation. The set of interactions is denoted as AO . We also deﬁne internal actions Aτ , which are used to represent evolutions of the system that do not involve interactions between services. In particular, such an action may represent the internal decision branching of a particular participant (or even a group of participants1 ), or a modiﬁcation of variables being performed by one or more partners in parallel. An internal action aτ has the form (Rτ , τ ), where Rτ ⊆ R denotes a subset of roles that perform an action, and τ is used to denote the internal action itself. 3.1

Global Protocol

We model choreography behavior as a global protocol. This behavior is deﬁned by the global transition relation T , which describes how the states of the participants 1

The possibility of a group of participants to perform an internal action is used in [3] to model simultaneous evaluation of the branching condition by a group of roles.

66

R. Kazhamiakin and M. Pistore

can evolve on the basis of external and internal actions. We represent a global state of the choreography as a vector s¯ = s1 , . . . , sn , where si is a local state of the role ri . We denote a vector s¯ with component si updated to si as s¯[si /si ]. Deﬁnition 1 (Global Protocol). A global protocol representing the collaboration of n roles is a tuple P = R, S, s¯0 , A, T , where – – – –

3.2

R is a set of n roles; S ⊆ Si × · · · × Sn is a set of global states, and s¯0 ∈ S is an initial state; A = Aτ ∪ AO is a set of actions; T ⊆ S × A × S is a global transition relation. A transition (¯ s, a, s¯ ) ∈ T if • a = (ra , rb , μ) and s¯ = s¯[sa /sa , sb /sb ], or • a = (Rτ , τ ) and s¯ agrees with s¯ except for the state of the roles in Rτ . Behavior of the Global Model

We deﬁne the behavior of the global protocol using the notions of a run and a conversation. A run describes the evolution of the system by specifying, which actions were performed, and which global states were visited. The conversation, on the contrary, records only the sequences of interactions being performed during the evolution of the system. More formally, the protocol behavior is deﬁned as follows. We say that an a action a ∈ A is ﬁreable in a state s¯, denoted as s¯ → s¯ , if there is a transition (¯ s, a, s¯ ) ∈ T . Let π = s¯1 , a1 , s¯2 , a2 , . . . be a (possibly inﬁnite) sequence of states π and actions. We say that the sequence is ﬁreable from s¯1 , written as s¯1 → ∗ , if ak ∀k ≥ 1, s¯k → s¯k+1 . Let us also denote as ρ(π) = μ1 , μ2 , . . . a sequence of all the interactions appeared on the sequence π. Deﬁnition 2. Let P = R, S, s¯0 , A, T be a global protocol. A run of the proπ tocol is a sequence π = s¯0 , a0 , s¯1 , a1 , . . . such that s¯0 → ∗ . The behavior of the π protocol is the set of all the runs of the protocol: B = {π | s¯0 →∗ }. A conversation of the protocol ρ(π) is a sequence of interactions performed on some run π. The set of all the conversations, denoted as Ω, is called the converπ sation set of the protocol: Ω = {ρ(π) | s¯0 →∗ }.

4

Local Model

In the local model, the Web service composition is deﬁned by a set of local protocols that separately describe the behavior of each participant of the composition. During their executions, the participants exchange messages with other participants through a certain communication medium, thus forming the dynamic behavior of the composed system. This bottom-up representation of the composition, inspired by the speciﬁcation languages like BPEL [1], relies on the notions of a local protocol, which describes the behavior of a particular actor of the composition, and a communication model, which characterizes the interaction mechanisms of the composition instance.

Analysis of Realizability Conditions for Web Service Choreographies

4.1

67

Composition of Local Protocols

The local behavior of the participant is given in terms of a local protocol that speciﬁes the states and actions performed by the participant. We distinguish −; outinput actions I, which represent the reception of message, denoted as ← μ put actions O, which represent messages sent to other participants, denoted as → − μ ; and internal actions, which characterize non-observable operations of the participant, denoted as τ . Deﬁnition 3 (Local protocol). A local protocol is a tuple S, s0 , A, T, where – S and s0 ∈ S are the set of role states and the initial state respectively; – A = I ∪ O ∪ {τ } is a set of role actions; – T ⊆ S × A × S is a local transition relation. The behavior of the composition of local protocols depends on the communication model [4] adopted and used for the description of the message exchanges between partners. Such a communication model is given by a set of communication channels (or queues), and is characterized by the number of the queues, message ordering, bounds etc. The composition of the local projections is therefore parametric with regards to the communication model, and may exhibit diﬀerent behaviors. More formally, let us model the interactions with set of m > 0 queues with disjoint alphabets Mj ⊆ M. A queue qj may be declared as bounded, with the corresponding capacity 0 < bj < ∞, or unbounded, in which case bj = ∞. Deﬁnition 4. A communication model for the composition is a tuple Δ = LB , LM , LO , where LB = b1 , . . . , bm , is a vector of queue bounds, LM : M → [1 . . . m] is a function that associates an operation μ with a queue i, and LO : [1 . . . m] → { , ⊥} is a function that declares the queue as either ordered or unordered. The alphabet Mi of queue i is deﬁned as Mi = {μ | LM (μ) = i}. Let M∗ be a set of sequences (or strings) of elements from M. Let also NM be a set of multisets of M, i.e. sets of mappings from M to the set N of natural numbers. Given two elements w and w , we write w.w to denote string concatenation, if w, w ∈ M∗ , and multiset union, if w, w ∈ NM . We deﬁne a queue content as a vector C = w1 , . . . , wm , where wj ∈ M∗j and j th queue is ordered, or wj ∈ NM and j th queue is unordered. We extend the operator . to the queue content as follows: C.μ = w1 , . . . , wm , where wj = wj .μ if α ∈ Mj , and wj = wj otherwise. We write |C| ≤ LB to specify that |qi | ≤ bi . We deﬁne the composition of the local protocols as a composition transition system (CTS). The deﬁnition of the CTS is parametric with respect to the communication model. Deﬁnition 5 (CTS [4]). A composition transition system representing the composition of n local protocols under a model Δ = LB , LM , LO is a transition system ΣΔ = Γ, γ0 , A, T , where

68

R. Kazhamiakin and M. Pistore

– Γ is a set of conﬁgurations of the form γ = ¯ s, C, and γ0 = ¯ s0 , , . . . , is aninitial conﬁguration; – A = i Ai is a set of actions; – T ⊆ Γ × A × Γ is the global transition relation. A transition (¯ s, C, a, ¯ s , C ) is in T , if for some 1 ≤ i ≤ n, s¯ = s¯[si /si ], i and (si , a, si ) ∈ T , and one of the following holds: → • a=− μ ∧ C = C.μ ∧ |C | ≤ LB ; ← − ∧ C = μ.C ; • a= μ • a = τ ∧ C = C. In the following, we say that the channel of a composition have a bounded growth if, for each queue qi , either a ﬁnite bound bi < ∞ is declared, or there is some constant Ki such that the queue contains at most Ki messages in all reachable states. The composition is bounded if it has bounded growth. We say that the composition is complete if all the terminating conﬁgurations ¯ s, C have empty queue content: C = , . . . , . We remark that systems that are not complete lose messages: indeed, at the end of the computation there are unconsumed messages in queues. 4.2

Behavior of the Local Model

While the emission and the reception of the messages are indistinguishable in the global protocol, this is not the case for the composition of projections. Depending on the communication applied, the messages may be interleaved, reordered, and even ignored. Moreover, the structure of the composition conﬁguration is more complex than that of the global protocol, and depends on the communication model. This is reﬂected in the way behaviors and conversations are deﬁned. In particular, since the reception of a message does not necessarily follow the emission (the message may be lost), we will deﬁne a conversation set in two → ways: we denote as − ρ (π) = μ1 , μ2 , . . . the sequence of all the messages emitted − on the sequence π, and as ← ρ (π) the sequence of received messages. a An action a ∈ A is ﬁreable in γ, denoted as γ → γ , if there is a transition (γ, a, γ ) ∈ T . Let ω = ¯ s1 , C1 , a1 , ¯ s2 , C2 , a2 , . . . be a (possibly inﬁnite) sequence of conﬁgurations and actions. We say that the sequence is ﬁreable from ak ω ¯ s1 , C1 , written as ¯ s1 , C1 →∗ , if ∀k ≥ 1, ¯ sk , Ck → ¯ sk+1 , Ck+1 . We denote as π(ω) = s¯1 , a1 , s¯2 , a2 , . . . a corresponding sequence of states and actions. Deﬁnition 6. Let ΣΔ = Γ, γ0 , A, T be a composition of local protocols. Given ω a sequence ω = γ0 , a0 , γ1 , a1 such that γ0 → ∗ , a run of the composition is a sequence π(ω). The behavior of the composition is the set of all the runs of ω the composition: B = {π(ω) | γ0 → ∗ }. An output conversation (respectively input conversation) of the composition is a sequence of messages emitted (resp. received) on some π ∈ B. The set of all the output (resp. input) conversations is → − ← − called the output conversation set Ω (resp. input conversation set Ω ).

Analysis of Realizability Conditions for Web Service Choreographies

4.3

69

Communication Models

The behavior of the composition depends on the communication model. Indeed, the certain ordering should be satisﬁed for the message to be consumed from the queue, the queue bound should restrict the emission of new messages, etc. One of the key problems for the analysis of the behavior of the protocol is to determine the relations between the behaviors exhibited by diﬀerent implementations of the communication medium. This requires the introduction of certain relations between communication models, namely simulation relations. Deﬁnition 7. We say that a conﬁguration γ2 = ¯ s2 , C2 of ΣΔ2 simulates a conﬁguration γ1 = ¯ s1 , C1 of ΣΔ1 , written as γ1 γ2 , iﬀ – s¯1 = s¯2 , a a – ∀ a, ∀ γ1 , if γ1 → γ1 , then ∃ γ2 , s.t. γ2 → γ2 , and γ1 γ2 . We write ΣΔ1 ΣΔ2 to denote that γ01 γ02 . We also write ΣΔ1 ≈ ΣΔ2 when ΣΔ1 ΣΔ2 ∧ ΣΔ2 ΣΔ1 . Proposition 1. ΣΔ1 ≈ ΣΔ2 iﬀ B(ΣΔ1 ) = B(ΣΔ2 ). When the simulation relation among two communication models Δ1 and Δ2 holds for any set of local protocols, we say that Δ2 is more general than Δ1 . Deﬁnition 8. Communication model Δ2 simulates model Δ1 , written as Δ1 Δ2 , if for any composition of STSs, ΣΔ1 ΣΔ2 . Being reﬂexive and transitive, this relation forms a partial order on the set of communication models. Below we will show that there is a “most general” model, that is the model ΔMG , such that for any other model Δ holds Δ ΔMG . The relation among communication models relies on the structure of the queues. The models diﬀer in two dimensions. First, the relation depends on the queue bounds: the bigger a bound is, the more transitions are enabled. Second, it depends on the distribution of the message alphabets: if the alphabet of each ordered queue in one model is a subset of the alphabet of some ordered queue in another model, then the ﬁrst model is more general than the other. The following theorem deﬁnes a relation between the models with diﬀerent queue structures. Theorem 1. Consider two communication models Δ1 = L1B , L1M , L1O and Δ2 = L2B , L2M , L2O . If for each queue q2i holds that – if the queue q2i is ordered, then there exists an ordered queue q1j , s.t. M2i ⊆ M1j , and – b2i ≥ M2i ∩M1j =∅ b1j , then Δ1 Δ2 . Let us deﬁne the most general model, that is the model that allows for the largest set of behaviors. In order to respect the assumptions presented above, this model has to allow for potentially unbounded queues, non-blocking emissions, and arbitrary, unordered access to the content of any queue.

70

R. Kazhamiakin and M. Pistore

Deﬁnition 9. The Most General Communication Model (MG-model) is a communication model ΔMG = LB , LM , LO , with 1 unordered queue, b = ∞, and LM (αi ) = 1. It is easy to see that such a model is indeed a generalization of any other communication model w.r.t. the behavior of any composition of STSs. Proposition 2 (from [4]). For any communication model Δ, Δ ΔMG . Whenever a composition under a certain model Δ simulates the most general composition, we say that this model is adequate for the description of the composition scenario. Deﬁnition 10 (from [4]). A communication model Δ is said to be adequate for the given composition scenario if ΣΔ ≈ ΣΔM G .

5

Protocol Realizability

A natural question that comes with the speciﬁcation of the global choreography protocol is the realizability of the speciﬁcation. It consists in deciding whether there is a way to extract the local implementations of the participating roles such that, when composed together, they satisfy the protocol speciﬁcations. We refer to these local implementations as projections. Sets of such projections will be used as the implementation candidates for the composition. Intuitively, a behavior of a projection is constructed from those transitions of the global protocol, in which the participant is involved. The internal action (Rτ , τ ) is projected onto an internal action of each role ri ∈ Rτ . The interaction − of the role r , and on the action (rs , rd , μ) is projected onto the input action ← μ d → − output action μ of the role rs . Deﬁnition 11 (Role Projection). Given a global protocol R, S, s¯0 , A, T , a projection on role ri is a local protocol Si , s0i , Ai , Ti , where: – Si is a set of states, and s0i is the initial state of ri respectively; – Ai = Ii ∪ Oi ∪ {τ } is a set of actions of ri ; – Ti ⊆ Si × Ai × Si is the transition relation of ri . Transition (si , ai , si ) ∈ Ti , if ∃ (¯ s, a, s¯ ) ∈ T , such that one of the following holds: → • a = (ri , rj , μ), ai = − μ ∈ Oi ; −∈I; • a = (rj , ri , μ), ai = ← μ i • a = (Rτ , τ ), ri ∈ Rτ , ai = τ . Given the set of all role projections of a global protocol, we can compose them into a CTS according to Deﬁnition 5. In the following we denote the composition of role projections under the model Δ as ΣpΔ . This composition enables the analysis of the realizability of the global protocol. In order to perform this analysis, a possibility to compare the behavior of the global protocol with the behavior of the composition of the local projections is needed. This comparison is based on the notion of the behavior expansion that re-deﬁnes the behavior of the protocol in terms of the actions of the composition.

Analysis of Realizability Conditions for Web Service Choreographies

71

Deﬁnition 12 (Behavior Expansion). Given a run π of the global protocol P , the expansion of the run is a sequence π of states and composition actions obtained as follows: – each interaction transition (ri , rj , μ) is projected onto a sequence of the corresponding send and receive transitions of ri and rj respectively; – each internal transition (Rτ , τ ) is projected onto a sequence of internal transitions of all roles in Rτ . The set of all expansions generated by B(P ) is denoted as B(P ). 5.1

Synchronous Realizability

An intuitive candidate for realizability is the notion that requires that the composition of the projections behaves exactly as the given global speciﬁcation regardless the communication model that is applied. We refer to this notion as synchronous realizability. Deﬁnition 13 (Synchronous realizability). The global protocol P is synchronously realizable if the behavior expansion of the protocol is equal to the behavior of the composition of the projections under ΔMG : B(P ) = B(ΣpΔM G ). The notion of synchronous realizability is closely related to the synchronizable communication model. This is the most restricted communication model that can be deﬁned in the local model formalism. In this model there is only one queue of capacity one. Deﬁnition 14 (Synchronizable communications model). The synchronizable communication model is the model Δ11 = LB , LM , LO , with LB = 1 and LM (μ) = 1 for all operations μ. The following result immediately follows from the above deﬁnitions. Proposition 3. If the protocol P is synchronously realizable, then the model Δ11 is adequate for the composition of the local projections of P . Indeed, the synchronous realizability implies that the behavior of the composition under the MG-model is the same as that of the global protocol. Therefore, in any conﬁguration there is at most one message to be received, and from the deﬁnition of composition follows that the model Δ11 is also adequate. It is easy to see that the protocol represented in Fig. 1 is synchronously realizable. 5.2

Strong Realizability

The restrictions imposed by the synchronous realizability are often too strong for the implemented system. Indeed, it requires that the order of internal and external actions is respected by the implementation, or that the next emission cannot

72

R. Kazhamiakin and M. Pistore

start before the previous message was received, even if the acting participants are independent. The notion of strong realizability relaxes these constraints. The ordering restrictions concern only the communication actions, and not the internal ones. Intuitively, a protocol is strongly realizable if the set of conversations of the protocol and of the compositions is the same, the composition is bounded, and all the emitted messages are received. Deﬁnition 15 (Strong realizability). Given a protocol P and the composition of the projections under ΔMG , if the composition is bounded and Ω(P ) = → p − ← − Ω (ΣΔM G ) = Ω (ΣpΔM G ), then the protocol is said to be strongly synchronizable. This notion is related to the globally ordered communication model. Deﬁnition 16 (Globally ordered communications model). The globally ordered communication model is the model Δgo = LB , LM , LO , with one ordered queue, such that LB = ∞ and LM (μ) = 1 for all operations μ. Proposition 4. The protocol P is strongly realizable iﬀ Δgo is adequate for the composition of the projections ΣpΔ , and the composition is complete and bounded. The completeness and adequacy of Δgo immediately follows from strong real→ − ← − izability of P by the above deﬁnitions ( Ω (ΣpΔM G ) = Ω (ΣpΔM G )). To see the converse, note that only one participant may send and only one may receive messages at a time (otherwise the reordering would be possible). A sequence of emissions of a participant is projected from the deﬁnition of the protocol, and → − therefore, reﬂects the sequence of interactions. Thus, Ω(P ) = Ω (ΣpΔM G ). While the protocol represented in Fig. 2(a) is not synchronously realizable (the internal activity prepareToDelivery may be performed before the shipper receives the orderDelivery message), one can see that it satisﬁes the strong realizability requirements. Indeed, the composition is bounded, all the messages are eventually received, and there are no concurrent message emissions/receptions, which makes the Δgo adequate for the composition. 5.3

Local Realizability

Strong realizability may appear to be too restrictive for a wide class of choreography scenarios. Indeed, it does not allow for concurrent emissions and receptions of messages by independent processes. For instance, if role A interacts with B, and then C interacts with D, then the global order cannot be preserved by the composition of projections. In many cases, however, this may be irrelevant. Moreover, since the variables are local for each role, the behavior and the information of the local participant is not aﬀected by these reorderings. We relax the notion of strong realizability by omitting the requirement of conversation equivalence. However, the local behavior of each role should not be aﬀected by possible reorderings of message emissions.

Analysis of Realizability Conditions for Web Service Choreographies

73

Deﬁnition 17 (Local Realizability). The protocol P is locally realizable if the composition ΣpΔM G is complete, bounded, and for any run π ∈ B(ΣpΔM G ), for → → any role ri , − πi = ← π−i , where − πi and ← π−i are the sequences of messages sent to and th received by the i participant. This property is especially important for monitoring, since it guarantees that the external observed order of messages is locally respected by the receiver. Deﬁnition 18. A locally ordered communication model for the composition of n local protocols is a model Δlo = LB , LM , LO , with n ordered queues, bi = ∞, − ∈ I i , L (α) = q . and ∀ α s.t. ← α M i This communication model, exploited also in [7], requires that messages are queued on a process-by-process way. The following result immediately follows from the deﬁnition of the local realizability. Proposition 5. The protocol P is locally realizable iﬀ Δlo is adequate for the composition of the projections ΣpΔ , and the composition is complete and bounded. One can see that the global protocol presented in Fig. 2(b) is locally realizable. While the reordering of messages is possible in the composition (thus violating the strong realizability requirements), the local order of messages is respected. 5.4

Weak Realizability

The least restrictive model of realizability further relaxes the ordering constraints, requiring only that the message ordering of the interactions among a pair of the participants is preserved. That is, each participant sending messages to its partner knows that they will be processed and managed in turn. We refer to this notion of realizability as weak realizability. Deﬁnition 19 (Weak realizability). The protocol P is weakly realizable if the composition ΣpΔM G is complete, bounded, and for any run π ∈ B(ΣpΔM G ), for ← − − → ← − any pair of roles ri and rj , − π→ ji = πij , where πji and πij are the sequences of messages sent from rj to ri and received by ri from rj respectively. This deﬁnition is related to the mutually ordered communication model. Deﬁnition 20 (Mutually ordered communication model). A mutually ordered asynchronous communication model is a model Δmo = LB , LM , LO , −∈ with n2 −n ordered queues denoted as qi,j (i = j) s.t. bi,j = ∞, and ∀ α, ← α → − I j ∧ α ∈ Oj iﬀ LM (α) = qi,j . In this model, a pair of queues is deﬁned for each pair of processes, with each queue representing one direction of interaction between these processes. This model, described in [8], provides a natural representation of communicating processes since each process explicitly distinguishes each of its partners. The main feature of this model is that each pair of communicating processes preserves the order of partners’ events. In other words, the order of receptions is equivalent for each pair of processes.

74

R. Kazhamiakin and M. Pistore

Proposition 6. The protocol P is weakly realizable iﬀ Δmo is adequate for the composition of the projections ΣpΔ , and the composition is complete and bounded. The global protocol represented in Fig. 2(c) is weakly realizable, while the one in Fig. 2(d) is not. Indeed, the composition of the local projections is incomplete and unbounded, and, moreover, it allows for reorderings of updated quotes.

6

Realizability Analysis

The notions of realizability and the respective properties suggest an analysis approach based on the analysis of communication models [4]. It is easy to see that the following hierarchy holds for the models presented above: Δ11 Δgo Δlo Δmo ΔMG Moreover, an analogous hierarchy holds also for the notions of realizability2 . This allows for the application of the following analysis algorithm. 1. Find a minimal (w.r.t. simulation relation) adequate communication model Δ for the composition of the local projections of the protocol P . 2. Check that the composition is complete and has bounded growth. If this is not the case, the protocol is not realizable. 3. The appropriate level of realizability is determined by the corresponding communication model. The algorithm for the adequacy check is presented in Fig. 1. We brieﬂy describe its behavior. The reachability tree of the composition is traversed recursively, starting from the initial conﬁguration. In each state the set of enabled transitions is compared with the set of transitions enabled in the corresponding conﬁguration of the composition under the MG-model. If the sets are not equivalent, the current model is not adequate. Each newly reached conﬁguration is checked for boundedness (the function isU nbounded(γ )). This is performed by checking whether there exists a loop starting in a conﬁguration with the same state, but with greater queue content. If such a loop exists, the composition is unbounded. The completeness is checked for each terminating state, i.e. a state without ﬁreable transitions. We remark, that whenever the inadequacy of a certain model is detected (as well as the incompleteness or the unboundedness), the sequence of conﬁgurations contained in the search stack represents a counterexample (or a witness), that describes the violation of the analyzed realizability. This counterexample may be used for further analysis of the protocol. For the sake of simplicity we omitted the deﬁnition of variables and the data ﬂow in the global and local models. In [9] we show how the above formalisations and analysis techniques may be extended in order to capture both the 2

Strong realizability, however, requires an additional check that the internal actions are not interleaved with the message receptions. This check may be easily introduced in the presented algorithm.

Analysis of Realizability Conditions for Web Service Choreographies

75

Algorithm 1. Composition adequacy check 1: 2: 3: 4:

Stack := nil; {Stack of conﬁgurations} V isited := nil; {Set of all visited conﬁgurations} IS := nil; {Set of incomplete conﬁgurations} U S := nil; {Set of conﬁgurations, where unboundedness is detected}

5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:

explore(γ0 ); procedure explore(γ) push(γ, Stack); F ireable := out(γ); {ﬁreable transitions} if F ireable = outM G (γ) then terminate; {the model is not adequate} if F ireable = ∅ then forall trans ∈ F ireable do γ := trans.target; if γ ∈ Stack ∪ V isited then {check boundedness} if isU nbounded(γ ) then U S := U S ∪ {γ }; else explore(γ ); else if ¬complete(γ) then IS := IS ∪ {γ}; V isited := V isited ∪ {γ}; pop(γ, Stack); end procedure

control and data in the composition representation. In particular, we show that the boundedness and adequacy results obtained on the data-less model may be propagated to the full model (under certain conditions). Moreover, using the abstraction techniques the representation may be made ﬁnite, enabling the model checking techniques as presented in [4].

7

Related Work and Conclusions

In this paper we presented a formal framework for the realizability analysis of Web service choreographies. The framework is based on the formalism suitable for modelling a composition both as a global protocol and as a set of interacting local services. For the global protocol we exploit a simple model, which is based on the notion of state transition systems, and allows for the automatic extraction of local projections that can be used as the basis for the service implementations. A composition of local services is formalized using the model of [4]. The key feature of this approach is the ability to specify for the composition a communication mechanism with an arbitrary structure. The most relevant original contribution of this paper is the deﬁnition of a hierarchy of notions of choreography realizability, which allows for capturing a wide range of properties of Web service choreographies. We also deﬁned a correspondence between this hierarchy and the hierarchy of communication models presented in [4]. This correspondence allows us to exploit the analysis approach described in [4] for determining the level of realizability of the given global protocol speciﬁcation.

76

R. Kazhamiakin and M. Pistore

The problem of the realizability of a global Web service protocol speciﬁcation has been addressed in [5], while the realizability is deﬁned as the ability of the composition of protocol projections to produce the same set of conversations. Several necessary conditions are formalized in order to enable the protocol realizability analysis. Contrary to our framework, the formalization of [5] is glued to a particular communication mechanism — the synchronous one — thus making the analysis results more restrictive. The framework presented here is also more ﬂexible with respect to a notion of realizability. The formalization and the analysis of the Web service choreography models are presented also in [6,10,11], while approaches to generate implementation templates from the choreography models are presented in [12,13]. However, the problem of realizability is not covered in these works, and the composition formalization is based on synchronous communications assumptions, which for a large range of scenarios and systems is not realistic.

References 1. Andrews, T., Curbera, F., Dolakia, H., Goland, J., Klein, J., Leymann, F., Liu, K., Roller, D., Smith, D., Thatte, S., Trickovic, I., Weeravarana, S.: Business Process Execution Language for Web Services (version 1.1) (2003) 2. OMG: Business Process Modeling Language (BPML). (2005) [http://www. bpmi.org]. 3. W3C: Web Services Choreography Description Language Version 1.0. (2005) [http://www.w3.org/TR/ws-cdl-10/]. 4. Kazhamiakin, R., Pistore, M., Santuari, L.: Analysis of Communication Models in Web Service Compositions. In: Proc. WWW’06. (2006) 5. Fu, X., Bultan, T., Su, J.: Conversation protocols: a formalism for speciﬁcation and veriﬁcation of reactive electronic services. Theor. Comput. Sci. 328 (2004) 19–37 6. Busi, N., Gorrieri, R., Guidi, C., Lucchi, R., Zavattaro, G.: Choreography and Orchestration: A Synergic Approach for System Design. In: Proc. ICSOC’05. (2005) 7. Fu, X., Bultan, T., Su, J.: Analysis of Interacting BPEL Web Services. In: Proc. WWW’04. (2004) 8. Brand, D., Zaﬁropulo, P.: On communicating ﬁnite-state machines. J. ACM 30 (1983) 323–342 9. Kazhamiakin, R., Pistore, M.: Static Veriﬁcation of Control and Data in Web Service Compositions. In: Proc. ICWS ’06. (2006) 10. Brogi, A., Canal, C., Pimentel, E., Vallecillo, A.: Formalizing Web Services Choreographies. In: Proc. WS-FM’04. (2004) 11. Foster, H., Uchitel, S., Magee, J., Kramer, J.: Model-Based Analysis of Obligations in Web Service Choreography. In: Proc. AICT-ICIW’06. (2006) 12. Mendling, J., Hafner, M.: From Inter-Organizational Workﬂows to Process Execution: Generating BPEL from WS-CDL. In: Proc. OTM’05. (2005) 13. Bravetti, M., Guidi, C., Lucchi, R., Zavattaro, G.: Supporting e-commerce systems formalization with choreography languages. In: Proc. SAC ’05. (2005)

Web Cube I.S.W.B. Prasetya1, T.E.J. Vos2, , and S.D. Swierstra1 1

Dept. of Inf. and Comp. Sciences, Utrecht University, the Netherlands 2 Instituto Tecnológico de Informática, Valencia, Spain

Abstract. This paper introduces a reﬁnement of Misra’s Seuss logic, called Web Cube, that provides a model for programming and reasoning over web applications. It features black box composition of web services so that services oﬀered by large systems, such as that of a back-end database, can be treated abstractly and consistently. It inherits the light weight feature of Seuss, which relies on an abstract view towards concurrency control, which leads to a less error-prone style of distributed programming, backed by a clean logic.

1

Introduction

Nowadays, sophisticated web applications are built using technologies like PHP, ASP, and servlets. Most are built by directly implementing them over these technologies, resulting in implementations where it is hard to separate implementation details from the core design problems. Debugging, let alone veriﬁcation, is in general very hard. This is not a good practice. In theory, it is better to ﬁrst design an application in an abstract-level modelling language. This is the development sequence that we will assume in this paper. At the design level, verifying critical properties is still feasible. Once veriﬁed, the design can be implemented. Subsequently, a more practical method, e.g. testing, can be used to validate the consistency between the implementation and the design. Web Cube is a programming model, which means it provides useful concepts and structures for constructing models of web applications and specify their critical properties. It also comes with a logic to verify a model against its properties. Web Cube is based on Misra’s formalism for distributed and concurrent systems called Seuss [14]. As a modelling language Seuss is quite generic. Web Cube is more concrete than Seuss. It provides concepts which are quite speciﬁc for the domain of web applications, so that a Web Cube model can be implemented more directly. This paper explains Web Cube’s concepts and the semantics of its black box logic, which is its strongest feature. We do not at the moment oﬀer a public implementation of Web Cube. There is a prototype, implemented by translating Web Cube source to Web Function library [10] written in the functional language Haskell. It is worth mentioning that alternatively it is often possible to implement a domain speciﬁc language by embedding it in a general purpose language, e.g. as the embedding of ﬁnancial contract combinators in Haskell [11]. One could envisage a similar implementation of Web Cube in Haskell or in

This work has been partially supported by the Generalitat Valenciana ref. GV05/261.

E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, pp. 77–92, 2006. c IFIP International Federation for Information Processing 2006

78

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

Java. An important beneﬁt of embedding is that it gives a ﬁrst class access to the modelling framework from the same programming language that one uses to write the application itself. This may help encouraging programmers to construct designs. In Web Cube, a web application is modelled by a set of passive Seuss programs called cubes whose task is to coordinate a set of web services and interface them to users. Figure 1 shows an example of a Web Cube model of a simpliﬁed web-based voting application —more will be said at the end of Section 3. As in Seuss, we can specify temporal properties like: a valid vote submitted to the webVote application in Figure 1 will eventually be counted, or that the application never silently cancels a valid vote. Web Cube treats services as black boxes. This sacriﬁces completeness, but allows an application to be veriﬁed in isolation! —that is, without using the services’ source code. Indeed, abstraction is now forced. But on the other hand, veriﬁcation is also more feasible. Black box reasoning is however also fundamentally diﬃcult, because parallel composition typically destroys progress properties of a component. Web Cube uses the theory from [18,19] to get a reasonably powerful black box logic while remaining light weight. Contribution. Web Cube proposes a formal programming model for web applications with a Seuss logic support and the black box enhancement from our previous work [18,19]. With respect to Seuss we contribute an extension, namely the notions of web application and service. With respect to [18,19] the novelty here is in showing its application in the domain of web programming. Paper Overview. Section 2 brieﬂy introduces Seuss. Section 3 explains Web Cube’s concepts and computation model. The formal machinery is described in Sections 4. Section 5 presents its black box logic. Section 6 discusses related work. application webVote{ service r = VoteServer ;

-- its contract in in Fig.4

cube home { method home() { respond("

>Click here to get vote info")} method vote(v) { r.vote(v) } method info() { var n = r.info() ; respond("

Total votes = <@n@>") ; if r.open then respond("

Open.") else respond("

Closed.") } }} Fig. 1. A simple Web Cube application for electronic voting

Web Cube

2

79

Seuss

In Seuss a box describes a reactive (non-terminating) program. It consists of a set of variables, a set of atomic guarded actions, and a set of methods. The variables deﬁne the state of the box. The execution of the box consists of an inﬁnite sequence of steps; at each step an action is non-deterministically, but weakly fair, selected for execution. If the selected action’s guard evaluates to true, the action is fully executed, else the eﬀect is just a skip. The methods play a diﬀerent role. They form the only mechanism for the environment to alter the state of the box. Methods may have parameters, actions can not. For brevity we will not discuss the ’category’ (generic box) [14]. When declaring a variable we omit its type speciﬁcation. We only consider non-blocking methods (called total in [14]). Parameters are passed by value, and a method may return a value. Figure 2 shows an example of a box called VoteServer —for now just consider it to have nothing to do with the webVote application in Figure 1. The notation [] denotes the empty list. The method vote allows the environment to submit a vote to the box. The box continuously executes one of its two actions: move and validate. The notation g -> S denotes a guarded (and atomic) action: g is the guard, and S is the action to perform if the guard evaluates to true. The action move swaps the entire content of the incoming vote-buﬀer (in) to an internal buﬀer tmp —it can only do so if tmp is empty. The full code of validate is not displayed; the action takes the votes from tmp and if they are valid votes, moves them to votes; otherwise they are discarded. The environment can also call the method info to inquire after the number of (valid) votes registered so far. Seuss’ key feature is its abstract view towards multiprogramming. To program the control ﬂow it only oﬀers, essentially, parallel composition and guarded actions. It advocates that a programmer should only be concerned with specifying, essentially, the set of concurrent atomic tasks that constitute a system. He should not be concerned with how to schedule these tasks for optimal performance —the compiler and the run time system should ﬁgure this out. This abstract view leads to a simple logic and clean designs. Seuss is the evolution of UNITY [4]. With respect to UNITY, Seuss adds methods (which are used to limit interference by the environment of a system) and the ability to structure a system’s architecture as a hierarchy of boxes. box VoteServer { var in, votes, tmp = [] ; open = True ; method vote(v) { if open then in := insert(v,in) else skip } info() { return length(votes) } stop() { open := False } action move :: null tmp -> tmp,in := in,[] ; validate :: not(null tmp) -> ... } Fig. 2. An example of a Seuss box

80

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

Seuss logic uses a slightly diﬀerent set of operators. We will stick to the old UNITY unless and → (leads-to) to specify temporal properties, which are derived operators in Seuss. We will defer their discussion until Section 4 where we alter their standard deﬁnition to deal with ’components’.

3

Web Cube

A Web Cube application, or simply application, models a server side program that interacts with a client via an HTTP connection. Figure 3-left shows the architecture of a hypothetical Web Cube execution system. Applications (e.g. A1 , A2 , B1 , . . . ) may run diﬀerent machines. We assume a Web Cube aware HTTP server which can direct a client’s requests to the correct application, collect the application’s reply, and forward it back to the client.

A1

contract

client1

B1 service

service

service

service

client2

x2

x1

Web Cube HTTP server

A2 application space

application

Fig. 3. Web Cube architecture

An application A is built, like in Figure 3-right, by composing so-called cubes (x1 and x2 ) and web services. A cube x is a ’passive’ Seuss box —we will say more on this later— that models a part of A that can interact with a client. A client E interacts by calling x’s methods. In practice this will be encoded as HTTP requests; x replies by sending back HTML responses. A web service, or simply service, is a black box program described by a contract and can be remotely interacted to (in practice this may happen over a SOAP/HTTP connection) by cubes. We further assume that a service is a state-persistent reactive system. Note that by attaching a contract to A it also becomes a service. A user can use his web browser to enact A’s client E and interact with one of its cubes; the browser will display the cube’s responses. However, E does not have to be a web browser: it can be another application using A as a service. The role of a cube is purely for computing the responses to client’s requests. It does not have reactive behavior of its own; so, we describe it by a passive Seuss box, which is a box with an empty set of actions. A service on the other hand,

Web Cube

81

may spontaneously execute actions to update its own state. Each client’s request may trigger a coordinated computation over the services. For safety reason, the client can only interact with A’s cubes; it cannot interact directly with A’s services. So, the cubes can also be seen as providing a layer for orchestrating the services. An orchestration language, e.g. [15], can be used in conjunction to Seuss for convenient coding of the orchestration, taking into account the atomicity restriction demanded by Web Cube (Subsection 4.5). Since a service such as a corporate database is actually a large and complicated system, we will view it as a black box speciﬁed by a contract. Such a contract includes a Seuss box that abstractly (thus incompletely) speciﬁes how the service behaves as a reactive system. As in design by contract [13], some party, e.g. the service owner, is assumed to guarantee the consistency between the service’s implementation and its contract. An application can be deployed as a state-persistent program serving multiple clients. Another scheme, as common in e.g. servlets, is to create a fresh and exclusive instance which lasts for a single session. We are not going to make the distinction in our formal model. With respect to single-session applications, a session is treated to last inﬁnitely long, so the application can be treated in the same way as a persistent application. Example. Figure 1 shows a simple Web Cube application, called webVote, which provides an electronic voting service. It consists of a single cube called home and a service symbolically called r which is linked to the component VoteServer from Figure 2. Each application should have a cube called home that contains a method home. The method is called automatically when an instance of the application is created and so resembles the home-page of the application. For the webVote application this will cause the user’s browser to show a simple form where the voter can type in his vote, a submit button, and a link to get the voting status. HTML Responses. A cube’s method m responds to a client’s call by sending back its return value, encoded in HTML. Like in Java servlets, m can also generate responses by calling the respond method: it takes a HTML-code which will be sent to the client. The entire response of m to a call consists of the concatenation of strings produced by all the calls to respond in m, followed by m’s HTML-encoded return value. A Web browser client may choose to display both; Web Cube applications acting as clients can only use the return value. Responses from respond are however ignored by our Seuss semantics, which makes reasoning simpler. To do so safely we have to require that inlined expressions (below) do not have side eﬀects (which is not imposed in servlets). As in servlets, inlined expressions are allowed, as in: respond "hello <@ e @>"; e will be evaluated and its result is inserted in the place where e appears. Inlined expression of the form address.m will be substituted by m’s URI address, causing m to be called when the user clicks on it.

82

4

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

Semantics

We have explained the building blocks of a Web Cube application and its execution model. We now give its semantics, operators for specifying properties, and an extension to the Seuss logic for proving properties. In the sequel a, b, c are actions, i and j are predicates intended to be invariants, p, q, r are predicates, P, Q, R are action systems (explained later), x, y, z are boxes. 4.1

Preliminaries

Selector. We use tuples to represent composite structures, and selectors to select the various parts. For example, T = (a :: U, b :: V ) deﬁnes a type T consisting of pairs whose elements are of type U and V . If t = (u, v) is a value of type T , then t.a = u and t.b = v. Actions. An action is an atomic, terminating, and non-deterministic state transition. We model it by a function from the universe of states, denoted by State, to P(State). Guarded actions are denoted by g –> S, meaning that S will be only executed if g is true, otherwise the action behaves as a skip —the latter implies that in our model a s = , for any action a and state s. If a and b are actions, ab is an action that either behaves as a or as b. So, (a b) s = a s ∪ b s. If A is a set of actions then A denotes (a : a ∈ A : a). If V is a set of variables, skip V is an action that does not change the variables in V , but may change variables outside V . The notation {p} a {q} denotes a Hoare triple over an action a with p and q as pre- and post-condition. Predicate Confinement. State predicates specify a set of program states. A predicate p is confined by a set of variables V , written p conf V , if p can only be falsiﬁed by actions that manipulate variables in V (it follows that p is conﬁned by its set of free variables). We write p, q conf V to abbreviate p conf V and q conf V . 4.2

More Preliminaries: Box and Property

The methods of a (Seuss) box x only deﬁne the interface with which the environment interacts with x. If we strip the methods we obtain the description of the box’s own program. This stripped box is called the action system and corresponds to a UNITY program ([4], Seuss predecessor). For conciseness we only deﬁne properties and parallel composition at the action system level, since this is suﬃcient for presenting our theorems later. Technically, these notions can be lifted quite naturally to the box and application level. Formally, we will represent box and action system as follows. d

Box = (main :: ActionSys, meths :: {M ethod}) d

ActionSys = (acts :: {Action}, init :: P red, var :: {V ar})

(1) (2)

Web Cube

83

If P is an action system, P.init is a predicate specifying P ’s possible initial states, P.var is the set of P ’s variables. Implicitly, P.init has to be conﬁned by P.var. We will overload action system’s selectors so that they also work on boxes, e.g. x.var means x.main.var. A useful property is that of invariant, because it conﬁnes the set of states reachable by a reactive program. A predicate i is a strong invariant of an action system P , denoted by P sinv i, if it holds initially, and is maintained by every action in P : d

P sinv i = P.init ⇒ i ∧ (∀a : a ∈ P.acts : {i} a {i})

(3)

A predicate j is an invariant if there exists a strong invariant i implying j. For specifying a broader range of safety properties, Seuss oﬀers the unless operator. Let p and q be state predicates. When p unless q holds in P , this means, intuitively, that each action in P will go from any state in p to some state in p ∨ q. Note that the deﬁnition quantiﬁes over all states. We will deviate from this deﬁnition. We parameterize the property with an invariant (i), as in [20], so that the quantiﬁcation over states can be restricted to those which are actually reachable by P . Moreover, we require that p and q to be conﬁned by P.var. Although this seems more restrictive, it does not really limit the way in which we usually use the operator. Technically, it makes the property more robust in parallel compositions [16]. Together with the deﬁnition of unless we also give the corresponding ensures operator, which speciﬁes progress from p to q by executing a single action: Def. 1 : Basic Operators d

1. P, i p unless q = P sinv i ∧ p, q conf P.var

∧ (∀a : a ∈ P.acts : {i ∧ p ∧ ¬q} a {p ∨ q})

d

2. P, i p ensures q = P, i p unless q

∧ (∃a : a ∈ P.acts : {i ∧ p ∧ ¬q} a {q})

The general progress operator → is usually deﬁned as the least transitive and disjunctive closure of ensures. Unfortunately, progress deﬁned in this way is difﬁcult to preserve when subjected to parallel composition —essentially, because we do not put any constraint on the environment. We will return to this issue in Section 4.4. We only introduce one sort of program composition, namely parallel composition. If P and Q are action systems, P []Q denotes an action system that models the parallel execution of P and Q: d

P []Q = (P.acts ∪ Q.acts, P.init ∧ Q.init, P.var ∪ Q.var)

(4)

If x and y are two boxes, we also write x[]P to denote x.main[]P and x[]y to denote x.main[]y.main. 4.3

The Underlying Component Based Approach

Web Cube assumes services to be available as black box entities, also called components [25]. A component only reveals partial information about itself in the

84

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

form of a contract. In particular, it does not reveal its full code. The component owner guarantees the consistency of the contract. Obviously a contract that reveals more information allows stronger properties to be inferred from it. However, such a contract is also more constraining, hence making the component less reusable, and the veriﬁcation of the the component’s implementation more costly. Consequently, when writing a contract, a developer will have to consider a reasonable balance. Essentially the relation between a component x and its contract c is a refinement/abstraction relation. That is, x has to reﬁne c (or conversely, c is an abstraction of x), usually denoted by c x. Such a relation preserves properties of interest: a property φ inferred from the contract c is also a property of the component x. In sequential programming reﬁnement traditionally means reduction of non-determinism [2]. Lifted to distributed programming c x means that every observable execution trace of x is allowed by c. This relation does not however preserve progress properties. There are a number of stronger (more restrictive) alternatives, e.g. Udink’s [26] and Vos’ [27], that preserve progress; but these are expensive to verify. For Web Cube, we choose a weak notion of reﬁnement, taken from our previous work [18]. It is even weaker than simple reduction of non-determinism, and thus has the advantage that it is less restrictive, and hence easier to verify. Like most reﬁnement relations, it still preserves safety, but surprisingly it also preserves a class of progress properties as we will see below. Although the class is much smaller than for example Vos’ [27], we believe it is still quite useful. We start by deﬁning the reﬁnement at the action level. Let a and b be two actions. Traditionally, a b means that b can simulate whatever a can do ([2]). However, this is a bit too restrictive in the context of an action system. Imagine that a is part of an action system P , then we can ignore what b does on variables outside P.var or what its eﬀect is on the states that are not reachable by P . Furthermore, we can also allow b to do nothing, since doing nothing will not break any safety properties of a. We capture these issues in our reﬁnement relation in the following formalization. Let V be a set of variables (intended to be P.var), and i be a predicate (intended to be an invariant, thus specifying P ’s reachable states). Action b weakly refines action a with respect to V and i is deﬁned as follows: V, i a b d

= (∀p, q : p, q conf V : {i ∧ p} a skip V {q} ⇒ {i ∧ p} b {q})

(5)

Lifting this deﬁnition to the action system level gives us: Def. 2 : Refinement/Abstraction d

iP Q=

P.var ⊆ Q.var ∧ (i ∧ Q.init ⇒ P.init) ∧ (∀b : b ∈ Q.acts : P.var, i P.acts b)

So, under the invariance of i, i P Q means that every action of Q either does not touch the variables of P , or if it does it will not behave worse than some action of P . Parallel composition is -monotonic in both its arguments.

Web Cube

4.4

85

Basic Results on Black Box Composition

Like in [3,26,27] the above reﬁnement relation preserves safety but in general not progress. However, consider the following restricted class of progress properties. Let B be an environment for P . We write: P []B, i p →q to express that under the invariance of i, the composed system P []B can progress from p to q. Moreover, this progress is driven by P . That is, the progress is realized even if B does nothing: Def. 3 : Extended Progress Operators d

1. P []B, i p ensures q = P []B, i p unless q

∧ (∃a : a ∈ P.acts : {i ∧ p ∧ ¬q} a {q})

2. P []B, i p → q is deﬁned such that (λp, q. P []B, i p → q) is the smallest transitive and disjunctive closure of (λp, q. P []B, i p ensures q). The result from [18] below states that progress ’driven by x’ is preserved by weak reﬁnement over B: Thm. 4 : Preservation of → x []B, i p → q

∧ jB Q x[]Q, i p → q

∧

i⇒j

Note that the same does not hold for weak reﬁnement over x. Proof: The formal proof is by induction over →; we refer to [18]. Informally: assume i as an invariant of x[]Q. Since i ⇒ j, j is also an invariant. Since Q reﬁnes B under j, throughout the computation of x[]Q every action of Q behaves, with respect to variables of x and Q, as some action of B or as a skip. Consequently Q cannot destroy any progress in terms of x []B, since this progress is driven by x and cannot be destroyed by any action of B. 2 The theorem below states that our notion of weak reﬁnement also preserves safety. We refer to [18] for the proof. Thm. 5 : Preservation of unless x, i p unless q ∧ j x x x , i p unless q

4.5

∧

i⇒j

Web Cube Atomicity Restriction

Let y be the environment of a box x in a parallel composition. Seuss allows methods and actions of y to call x’s methods. In particular, this allows y to perform multiple method calls to one or more boxes in a single action. Since actions are atomic, this eﬀectively empowers y to force an arbitrary level of atomicity on its accesses to x. This is a very powerful feature, but unfortunately

86

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

it will also allow y to behave more destructively with respect to x’s temporal properties. For this reason in Web Cube we will limit the feature, and deﬁne a notion of worst allowed environment as follows: d

x.env = ({m | m ∈ x.meth}, x.init, x.var)

(6)

where m is an action modeling the disjunction of all possible single calls to m. So, if m is a 1-arity method, then m = (v :: m(v)). Now, we deﬁne a box y to be a proper (allowed) environment of x under an invariant i if it reﬁnes the worst allowed environment of x. More precisely: d

y is a proper environment of x (under i) = i x.env y.main y.env

(7)

Intuitively, every action and method of x’s proper environment y can only contain a single call to a state-altering method of x. This can be checked statically. The action (method) can however still contain an arbitrary number of calls to x’s functional methods (i.e. methods that do not alter the state) and calls to other boxes’ methods. The proper environment condition enforces a more deterministic environment, but in return it will behave less destructively with respect to x. 4.6

Contracts

We will use the following structure to represent contracts: Contract = (smodel :: Box, inv :: P red, progress :: {P rogressSpec}) If c is a contract, c.impl denotes a Seuss box which is a component associated with c. Let x = c.impl. The methods of c.smodel specify the visible interface of x. The action system of c.smodel speciﬁes an abstraction over x, in the sense of Def. 2. The inv section speciﬁes an invariant. In the progress section we specify the component’s critical progress properties. Only progress ’driven by’ the component, in the sense of Def. 3, can be speciﬁed, so that we can use Thm. 4 to infer its preservation. In practice a component like a database is not written in Seuss. However, as long as its owner can produce the above form of contract, and guarantee it, we can proceed. The relation between c and c.impl is formalized by: Def. 6 : Box-Contract Relation If c is a contract and x = c.impl, there should exist a predicate i such that: 1. i is a strong invariant of x[]x.env and it implies c.inv. 2. c and x have a ’compatible’ interface. For brevity, here it means that both specify exactly the same set of methods: c.smodel.meth = x.meth. 3. c.smodel is a consistent abstraction of x, i.e. i c.smodel.main x.main 4. for every speciﬁcation p → q in c.progress we have x []x.env, i p → q.

Web Cube contract VoteServer { smodel var in, votes = [] ; open = True ; method vote(v) { if open then in := insert(v,in) else skip } info() { return length(votes)) } stop() { open := False } action fetch :: in := [] ; count :: {var v ; if isValid(v) then votes := insert(v,votes) inv

v in votes ==> isValid(v)

progress

isValid(v)/\open ; vote(v)

|-->

87

; ; ;

else skip }

v in votes

}

Fig. 4. A contract for the component VoteServer (Figure 2)

The invariant i mentioned above is called the concrete invariant of x, and will be denoted by x.concreteInv. This concrete invariant i is partially speciﬁed by c.inv, since i ⇒ c.inv. Its full details cannot be inferred from the contract though. The ﬁrst condition above also implies that i.inv is an invariant of x[]x.env, though in general it is not a strong invariant of x[]x.env. The above deﬁnition of ’compatible interface’ implies c.impl.env = c.smodel.env. So, any environment which is proper according to a contract c is automatically also a proper environment of c.impl. Actually, it would be suﬃcient to require c.impl.env c.smodel.env such that we can weaken the deﬁnition of ’compatible interface’ and make it more realistic. This, however, is outside the scope of this paper. Figure 4 shows an example of a contract, that could belong to the component VoteServer in Figure 2. Free variables in the inv and progress sections are assumed to be universally quantiﬁed. The contract’s action part reveals that VoteServer may from time to time empty the incoming buﬀer in. It does not, however, specify when exactly this will happen. The contract also says that the server will only ﬁll votes with valid votes though it leaves unspeciﬁed as to where these votes should come from. Although a very weak one can infer a critical safety property from this abstraction: no invalid vote will be included in the counting. For convenience, we allow methods to be used when specifying state predicates within a temporal speciﬁcation in the following way. If p is a state predicate and m(e) is a call to a method m, the predicate p; m(e) speciﬁes the set of states that result from executing m(e) on states satisfying p. So, the progress section in Figure 4 states that after a valid vote is successfully submitted (which only happens if open is true) through a call to the method vote, eventually the vote will be counted by the server (captured by the predicate v in votes). With this property the server guarantees there cannot be any loss of valid votes.

88

4.7

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

Semantics of Application

We can now give the semantics of a web application. An application consists of cubes and services. The latter are components, so they are represented by their contracts. Formally, we represent an application by this structure: d

App = (svc :: {Contract}, cube :: {Box})

(8)

If C is a set of boxes, let []C denote the parallel composition of all the boxes in C. Let A be an application. The Seuss semantics of A is the concrete program induced by A, which is just the parallel composition of all its services and cubes: d

A.impl = ([]c : c ∈ A.svc : c.impl) [] ([] A.cube)

(9)

Although this implementation is not visible, we can infer, from the cubes and the contracts, an abstract model for the application: d

A.model = ([]c : c ∈ A.svc : c.smodel) [] ([] A.cube)

(10)

A.client is A’s worst allowed client. It is the one that tries all possible calls to the methods of A’s cubes: d

A.client = ([]x : x ∈ A.cube : c.smodel.env)

(11)

Note that A.client is by deﬁnition an abstraction of any proper client of A. Wrapping. Since semantically, A.impl[]client is a box, it can be treated as a component by providing a contract. Semantically, it becomes a service. In the implementation this may require some wrapping to make it SOAP-enabled. As a service it can be used to build larger applications.

5

Inference

Seuss provides a logic [14] for proving safety and progress properties. Although we have changed the deﬁnitions of Seuss temporal operators, it can be proven in a quite standard way that they maintain basic Seuss laws, e.g. using our general proof theory in [17]. We now add important results, namely theorems for inferring properties of an application from the contracts of its services —with just plain Seuss, this is not possible. Let A be an application. Let A.inv denote the combined abstract invariant of A, which is the conjunction of the invariants speciﬁed by the contracts in A. Similarly, A.concreteInv denotes the combined concrete invariant of A. The latter cannot be inferred from the contracts. However, we just need to infer that properties inferred from A are consistent with it. Let client be a proper client of A (under A.inv). We have: Thm. 7 : Inferring Safety from Abstract Model A.model[]client, A.inv p unless q A.impl[]client, A.concreteInv p unless q

Web Cube

89

Proof: the Contract-Box relation (Def. 6) imposed on the services implies that A.model is a consistent abstraction of A.impl: A.concreteInv A.model A.impl

(12)

It follows, by Thm. 5, that any unless property proven on the abstract model is also a property of the concrete system. 2 For inferring progress we have: Thm. 8 : Progress by Contract c ∈ A.contract ∧ p → q ∈ c.progress A.impl []client, A.concreteInv p → q

Proof: by Def. 6, c.progress actually speciﬁes this progress: c.impl []c.env p → q. Imposing the constraint on the atomicity of method calls from Subsection 4.5, makes the rest of the application and the client act as a proper environment for c. Hence, by Thm. 4 the progress will be preserved in the entire system. 2 Below is the dual of the theorem above, stating that progress solely driven by the client, assuming A’s abstract model as the environment, will be preserved in the entire system: Thm. 9 : Client Progress client []A.model, A.inv p → q client []A.impl, A.concreteInv p → q

Proof: follows from (12) and Thm. 4. Example. Consider again the example we mentioned in the Introduction: we want a guarantee that a valid vote submitted to the webVote application in Figure 1 will eventually be counted. The property is promised by the VoteServer service in webVote. Now we can use Thm. 8 to conclude that the property will indeed be preserved in the system. Consider also the property info() ≥ N unless false. It is an important safety property, stating that the application will not silently cancel an already counted vote. In order to verify its correctness, Thm. 7 says that we can do so against the abstract model of the application. This means isolated veriﬁcation: we do not need the full code of the services! We cannot infer everything from a contract, because it is just an abstraction. For example, the component VoteServer in Figure 2 will not silently insert a valid-but-fake vote. However, we cannot infer this from the contract in Figure 4.

6

Related Work

Formal methods have been used to specify and verify document related properties of web applications. Semantic Web [5] is currently popular as a framework

90

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

to deﬁne the semantics of documents, thus enabling reasoning over them, e.g. simply by using theorem provers. On top of it sophisticated properties can be speciﬁed e.g. as [12] that oﬀers a query language, in the spirit of SQL, over documents. Automated veriﬁcation has also been explored [22,9,1], though we will have to limit ourselves to simple document properties, e.g. the reachability of diﬀerent parts of a web page from multiple concurrent frames. Web Cube logic focuses on temporal properties over the state maintained by a web application, rather than on document properties —these two aspects are complementary. A Web Cube is primarily a programming model for constructing a web application. Although it is based on services composition, it is not a dedicated service orchestration language as e.g. BPEL, cl [8], or Orc [15]. Given a Web Cube application A, requests from a client are translated to calls to A’s cubes’ methods. In turn a method may perform a series of calls to multiple services, scripted as a plain Seuss statement. So, orchestration in Web Cube happens at the method level, and is consequently limited by the atomicity constraint over methods. Therefore, the full BPEL concurrency (of orchestration) cannot be mapped to Web Cube’s orchestration. Though on the other hand we get a nice back box temporal logic for Web Cube, whereas this would be a problem for BPEL. Orc’s [15] type of orchestration matches better to Web Cube. A top level Orc expression is atomic. So in principle it can be used to specify a cube’s method. Formalisms like process algebra [6], Petri net [21], or event-based temporal logic [24] have been used to reason over service orchestration. These are more suitable for work-ﬂow oriented style of orchestration (e.g. as in BPEL). In Web Cube calls to services may cause side effect on the services’ persistent state. So, Web Cube uses a classical temporal logic which is more suitable to reason over temporal properties over persistent states. Web Cube assumes a more classical development cycle, where Seuss is used to abstractly describe a web application. Properties are reasoned at this Seuss level. Actual implementation could be obtained by translating Seuss to an implementation language, e.g. Java. Language embedding [11] is also an interesting route to obtain implementation. Others have used reﬁnement to develop an application [23]. Seuss is not a reﬁnement calculus; reﬁnement in Web Cube is used to bind contracts. In reverse engineering people attempt to do the opposite direction: to extract models from an existing implementation of a web application, e.g. as in [7,22,9,1]. The models are subsequently subjected to analysis, e.g. veriﬁcation. Reverse engineering can yield high automation, but deﬁning the procedure to extract the models is not trivial, especially if the programming model used at the model level diﬀers too much from that of the implementation level. This is likely the case with Web Cube, since it tries to be high level, and hence hard to extract from e.g. an arbitrary Java code. Compared to all the work mentioned above Web Cube is also diﬀerent because of its component based approach.

Web Cube

91

References 1. M. Alpuente, D. Ballis, and M. Falaschi. A rewriting-based framework for web sites veriﬁcation. In Proc. 5th Int. W.shop on Rule-based Programming RULE. Elsevier Science, 2004. 2. R.J. R. Back. On the Correctness of Refinement Steps in Program Development. PhD thesis, University of Helsinki, 1978. Also available as report A-1978-5. 3. R.J.R. Back and J. Von Wright. Reﬁnement calculus, part II: Parallel and reactive programs. Lecture Notes of Computer Science, 430:67–93, 1989. 4. K.M. Chandy and J. Misra. Parallel Program Design – A Foundation. AddisonWesley Publishing Company, Inc., 1988. 5. M.C. Daconta, L.J. Obrst, and K.T. Smith. The Semantic Web: A Guide to the Future of XML, Web Services, and Knowledge Management. 2003. 6. A. Ferrara. Web services: a process algebra approach. In Proceedings of 2nd International Conference Service-Oriented Computing (ICSOC), pages 242–251. ACM, 2004. 7. H. Foster, S. Uchitel, J. Magee, and J. Kramer. LTSA-WS: a tool for modelbased veriﬁcation of web service compositions and choreography. In Proceeding of the 28th international conference on Software engineering, pages 771–774. ACM Press, 2006. 8. S. Frolund and K. Govindarajan. cl: A language for formally deﬁning web services interactions. Technical Report HPL-2003-208, Hewlett Packard Laboratories, 2003. 9. M. Haydar. Formal framework for automated analysis and veriﬁcation of web-based applications. In Proc. 19th IEEE Int. Conf. on Automated Software Engineering (ASE), pages 410–413. IEEE Computer Society, 2004. 10. R. Herk. Web functions, 2005. Master thesis, IICS, Utrecht Univ. No. INF/SCR2005-014. 11. S. Peyton Jones, J.-M. Eber, and J. Seward. Composing contracts: an adventure in ﬁnancial engineering. In Proc. 5th Int. Conf. on Functional Programming, pages 280–292, 2000. 12. A.O. Mendelzon and T. Milo. Formal models of Web queries. In Proc. of the 16th ACM Sym. on Principles of Database Systems (PODS), pages 134–143, 1997. 13. B. Meyer. Applying design by contract. IEEE Computer, 25(10):40–51, 1992. 14. J. Misra. A Discipline of Multiprogramming. Springer-Verlag, 2001. 15. J. Misra. A programming model for the orchestration of web services. In 2nd Int. Conf. on Software Engineering and Formal Methods (SEFM’04), pages 2–11, 2004. 16. I.S.W.B. Prasetya. Mechanically Supported Design of Self-stabilizing Algorithms. PhD thesis, Inst. of Information and Computer Sci., Utrecht University, 1995. 17. I.S.W.B Prasetya, T.E.J. Vos, A. Azurat, and S.D. Swierstra. !UNITY: A HOL theory of general UNITY. In Emerging Trends Proceedings of 16th Int. Conf. Theorem Proving in Higher Order Logics, pages 159–176, 2003. 18. I.S.W.B Prasetya, T.E.J. Vos, A. Azurat, and S.D. Swierstra. A unity-based framework towards component based systems. Technical Report UU-CS-2003-043, IICS, Utrecht Univ., 2003. 19. I.S.W.B Prasetya, T.E.J. Vos, A. Azurat, and S.D. Swierstra. A unity-based framework towards component based systems. In Proc. of 8th Int. Conf. on Principles of Distributed Systems (OPODIS), 2004. 20. B.A. Sanders. Eliminating the substitution axiom from UNITY logic. Formal Aspects of Computing, 3(2):189–205, 1991.

92

I.S.W.B. Prasetya, T.E.J. Vos, and S.D. Swierstra

21. K. Schmidt and C. Stahl. A petri net semantic for BPEL. In Proc. of 11th Workshop Algorithms and Tools for Petri Nets, 2004. 22. E. Di Sciascio, F.M. Donini, M. Mongiello, and G. Piscitelli. AnWeb: a system for automatic support to web application veriﬁcation. In SEKE ’02, pages 609–616. ACM Press, 2002. 23. G. Di Marzo Serugendo and N. Guelﬁ. Formal development of java based web parallel applications. In Proc. of the Hawai Int. Conf. on System Sciences, 1998. 24. M.P. Singh. Distributed enactment of multiagent workﬂows: temporal logic for web service composition. In AAMAS ’03: Proceedings of the second international joint conference on Autonomous agents and multiagent systems, pages 907–914. ACM Press, 2003. 25. C. Szyperski. Component Software, Beyond Object-Oriented Programming. Addison-Wesley, 1998. 26. R.T. Udink. Program Refinement in UNITY-like Environments. PhD thesis, Inst. of Information and Computer Sci., Utrecht University, 1995. 27. T.E.J. Vos. UNITY in Diversity: A Stratified Approach to the Verification of Distributed Algorithms. PhD thesis, Inst. of Information and Computer Sci., Utrecht University, 2000.

Presence Interaction Management in SIP SOHO Architecture Zohair Chentouf1 and Ahmed Khoumsi2 1

Dialexia Communications Inc., Montreal, Canada [email protected] 2 Université de Sherbrooke, Sherbrooke, Canada [email protected]

Abstract. A SOHO (Small Office or Home Office) architecture can be sketched as an architecture that involves an ITSP (Internet Telephony Service Provider) and subscribers. The ITSP offers SIP protocol based telephony and presence services for subscribers. A subscriber can have several presence capable devices that periodically publish the user presence status. The paper defines and proposes a solution to the presence interaction (PI) problem. Keywords: SOHO, Presence interaction (PI) detection and resolution, PI Management Agent (PIMA), PI Management Language (PIML), order relations.

1 Introduction In this article, we consider a particular architecture, called SOHO (Small Office or Home Office), containing an Internet Telephony Service Provider (ITSP) that offers SIP based telephony and presence services for users. Each user can own one or more devices. The devices that are presence capable, periodically publish the user presence status to the ITSP presence server. A presence interaction (PI) arises when two or more devices owned by the same user publish contradictory presence status, for example, available and out-for-lunch. We propose a multi-agents architecture for managing PI. The detection and resolution procedure is based on order relations. A PI Management Language (PIML) is used to express formally the relevant information for managing PI. Section 2 introduces the presence service and our proposed architecture. In Section 3, we introduce PI and the approach used for solving them. In Section 4, we propose a Multi-agents approach for managing PI. Section 5 presents PIML that is used to model presence status and resolution policies. And we conclude in Section 6.

2 Presence Service and Proposed Architecture SIP offers an architecture and communication mechanisms for implementing a presence publishing service. The SIP presence architecture [1] encompasses user terminals that publish presence information to a presence server, using the PUBLISH message [2]. Users which publish their presence information are called presentities. E. Najm et al. (Eds.): FORTE 2006, LNCS 4229, pp. 93 – 98, 2006. © IFIP International Federation for Information Processing 2006

94

Z. Chentouf and A. Khoumsi

The presence server composes the presence information that is published by different terminals that belong to a same presentity in order to produce a single presence document. The users who are interested to be notified about the presence status of a given presentity, subscribe to this service by sending a SUBSCRIBE message to the presence server. Those users are called watchers. Every time his presence status is changed, the presentity publishes the new presence information. The presence server then notifies all the watchers of that presentity about his new presence information by sending a NOTIFY message to every one, including the presence document. In [3], presence information as well as filtering policies are coded in an XML-based language called PIDF. In [4], Schulzrinne proposed RPID that extends PIDF. We extend the SIP presence architecture by proposing the architecture depicted in Figure 1. The SOHO (Small Office or Home Office) network gathers the devices owned by the same user. The ITSP (Internet Telephony Service Provider) extends the SIP presence server in order to manage the SOHO network.

Fig. 1. ITSP presence architecture

3 Presence Interactions and Solution Approach For the purpose of the current work, we propose the following eight presence status, which are for example used in [5] and [6]: Available (1), Away (2), Busy (3), In-ameeting (4), Not-available (5), On-the-phone (6), On-vacation (7), Out-for-lunch (8). Notice that the On-the-phone status is special in that it is temporary and not intentional. All the other presence status are intentionally set by the user. We define the presence interaction (PI) problem as the situation where two or more devices owned by the same user report two or more different presence status of the user. This could happen, for example, when a device publishes Out-for-lunch while another publishes On-the-phone. The resolution of a detected PI will consist in keeping one among the conflicting presence status in the manner we will explain. For simplicity, we consider here only PI involving exactly two (conflicting) devices.

Presence Interaction Management in SIP SOHO Architecture

95

3.1 PI Classification, Order Relations PI are classified into two categories, denoted OR and RP: Obvious Resolution (OR) interactions: among two conflicting status, the selection of the one to be excluded is obvious. In our case, OR interactions involve the On-thephone status, because the latter is special in that it is not intentional. All the other presence status are intentionally set by the user. The On-the-phone status should not contradict a user who, for example, receives a call on a device at a period during which he has chosen to appear as Out-for-lunch on another device. The On-the-phone status should be excluded and the other status should appear instead. Resolution Policy (RP) interactions: among two conflicting status, the selection of the one to be excluded needs to conform to a specified policy. The latter is based on the following two types of order relations denoted SOR and DOR: Status order relations (SOR): A SOR is an order relation between status. Let us consider two status S1 and S2 and a SOR sor. If S1 sor S2, then the policy based on sor consists in excluding S2. “is more precise than” is an example of SOR. For example, Away is more precise than Not-available. For our eight presence status identified by 1, 2, …, 8, the SOR “is more precise than” implies the following pairs (2,5), (3,5), (7,2), (8,2), (4,3), where (i,j) means “i is more precise than j”. Device order relations (DOR): A DOR is an order relation between devices. Let us consider two devices D1 and D2 and a DOR dor. If D1 dor D2, then the policy based on dor consists in excluding the status published by D2. “is more trustworthy than” is an example of DOR, which can be used by assigning trustworthiness weights to devices. For example, the user can decide to assign more trustworthiness to cell phone than to office phone. 3.2 PI Resolution Procedure PI resolution policies are specified by the SOHO administrator and the end users. We suppose the ITSP provides the suitable interface for the SOHO administrator as well the users in order to specify those policies. The ITSP presence resolution solution is contained in a PIMA (Presence Interaction Management Agent) and is based on the use or SOR and DOR. We consider that for every user, we may have a set of SORs {sor1, …, sorn} which are ordered by priority, that is, sori has priority over sori+1. We also may have a set of DORs {dor1, …, dorn} where dori has priority over dori+1. We also assume that priorities may be defined between some pairs (sori, dorj). Some order relations correspond to policies specified by the SOHO administrator and will therefore be called admin-based order relations. Other order relations correspond to policies specified by the users (presentities) themselves and will therefore be called user-based order relations. For example, the SOR “is more precise than” should be specified by the SOHO administrator, while the DOR “is more trustworthy than” should be specified by the users. Given two status S1 and S2 published by devices D1 and D2, respectively, PIMA solves the interaction S1-S2 by applying the following resolution procedure:

96

Z. Chentouf and A. Khoumsi

Step 1: Comparison using SOR, assuming that each sori has priority over sori+1 Check if S1 and S2 are comparable using sor1, i.e., “S1 sor1 S2” or “S2 sor1 S1”. If this is the case, the best status wrt sor1 is the solution of Step 1. If this is not the case, check if S1 and S2 are comparable by sor2. And so on, we iterate until either we reach a sori that permits to compare S1 and S2, or we reach sorn without being able to compare S1 and S2. In the latter case, we say that S1 and S2 are SOR-incomparable. In the former case, the best status wrt sori is the solution of Step 1. Step 2: Comparison using DOR, assuming that each dori has priority over dori+1 We proceed iteratively as in Step 1, but by comparing devices instead of status. If no dori permits to compare D1 and D2, we say that D1 and D2 are DORincomparable. Otherwise, Step 2 provides a solution Dv (v = 1, 2 ). Step 3: we have the following six situations: 3.a: Neither Step 1 nor Step 2 provides a solution. In this case, the resolution procedure provides no solution. 3.b: Step 1 provides a status Su as a solution and Step 2 provides no solution. Su is the adopted solution. 3.c: Step 2 provides a device Dv as a solution and Step 1 provides no solution. The status published by Dv is the adopted solution. 3.d: Steps 1 and 2 provide compatible solutions, that is, the solution of Step 1 is the status published by the device which is the solution of Step 2. This status is the adopted solution. 3.e: Step 1 and 2 provide incompatible (or contradictory) solutions, that is, the solution of Step 1 is different from the status published by the device which is the solution of Step 2. In this case, let sori and dorj be the two order relations providing the solutions of Steps 1 and 2, respectively. Recall that a priority may have been defined between sori and dorj. 3.e.1: if such a priority has effectively been defined: we select the solution provided by the order relation that has priority over the other. 3.e.2: otherwise: the resolution procedure provides no solution.

4 Multi-agents Architecture for Managing PI We propose a multi-agent architecture solution to manage the problem of PI. The agents are called FIMA (Feature Interaction Management Agent) because the proposed solution is aimed to be integrated with a method for managing feature interactions (FI) proposed in [7]. Two types of FIMA are used: several UFIMA (User FIMA) and one NFIMA (Network FIMA) (Fig. 2). A UFIMA is assigned to each device and the NFIMA contains the PIMA and is assigned to the ITSP. A user has a single interface to manage presence preferences. This interface may be managed by any UFIMA that is located on any device owned by the user. At any time, the user can access the interface in order to set his presence preferences. Those preferences are used to specify the so-called user-based order relations, that is, order relations corresponding to policies specified by the users (presentities). For simplicity, in the following we consider we have a single user-based relation, namely the DOR “is more trustworthy than”. The user presence preferences should contain the

Presence Interaction Management in SIP SOHO Architecture

97

trustworthiness weighting of all the devices. UFIMA uses the SIP REGISTER message to communicate the weighting information to PIMA (contained in NFIMA), coded in PIML (Figure 2). The general purpose of PIML is to express formally the relevant information for managing PI. We suppose the registrar server (the server that is responsible of processing REGISTER) located in the same node as the presence server. Otherwise, the registrar has to communicate the received PIML models to the presence server in a suitable manner. Based on this trustworthiness information (coded in PIML) provided by UFIMA, PIMA constructs the DOR “is more trustworthy than” that will be used when executing the resolution procedure for that user. In the same way, the SOHO administrator has an interface to transmit to PIMA (using REGISTER) necessary information (coded in PIML) for the construction of admin-based order relations, that is, order relations corresponding to policies specified by the SOHO administrator. The SOHO administration interface is managed by any UFIMA that runs on any device owned by the SOHO administrator. For simplicity, in the following we consider we have a single admin-based relation, namely the SOR “is more precise than”.

Fig. 2. FIMA-SOHO architecture

5 Presence Interaction Management Language (PIML) Example of PIMLcode using a SOR 1. Owner 2. caller = [email protected] 3. SOR: MorePrecise 4. AWAY, NOTAVAILABLE 5. BUSY, NOTAVAILABLE

98

Z. Chentouf and A. Khoumsi

6. 7. 8.

VACATION, AWAY LUNCH, AWAY MEETING, BUSY

Lines 1-2 indicates that [email protected] is a SIP address that is bound to the SOHO administrator currently used device. Line 3: indicates that the following lines define a SOR called MorePrecise. Lines 4-8: each line S1,S2 means that S1 is more precise than S2. Example PIML code using a DOR 1. Owner 2. caller = [email protected] 3. DOR: MoreTrustworthy 4. [email protected], [email protected] 5. [email protected], [email protected] Line 3: indicates that the following lines define a DOR called MoreTrustworthy. Lines 4-5: each line D1,D2 means that D1 is more trustworthy than S2.

6 Conclusion In this article, we proposed a solution to the presence interaction (PI) problem that arises when two or more devices owned by the same user publish contradictory presence status. For future work, we plan to study PI involving more than two status and to consider other types of relations. We also plan to consider status that can be combined, instead of selecting a single status.

References 1. Day, M., Aggarwal, S., Mohr, G., Vincent, J.: Instant Messaging/Presence Protocol Requirements. RFC 2779, IETF, February 2000. 2. Niemi, A.: Session Initiation Protocol (SIP) Extension for Event State Publication. RFC 3903, IETF, October 2004. 3. Sugano, H., Fujimoto, S., Klyne, G., Bateman, A., Carr, W., Peterson, J.: Presence Information Data Format (PIDF). RFC 3863, IETF, August 2004. 4. Schulzrinne, H.: RPID: Rich Presence Extensions to the Presence Information Data Format (PIDF). draft-ietf-simple-rpid-10 (work in progress), December 2005. 5. http://www.dialexia.com/pub/products/dial_office.jsp Accessed on April 2006. 6. http://messenger.msn.com Accessed on April 2006. 7. Z. Chentouf, S. Cherkaoui, A. Khoumsi, “Service interaction management in SIP user device using Feature Interaction Management Language”, NOTERE, June 2004, Saïdia, Morocco.

Formal Analysis of Dynamic, Distributed File-System Access Controls Avik Chaudhuri1 and Mart´ın Abadi1,2 1

Computer Science Department, University of California, Santa Cruz 2 Microsoft Research, Silicon Valley

Abstract. We model networked storage systems with distributed, cryptographically enforced file-access control in an applied pi calculus. The calculus contains cryptographic primitives and supports file-system constructs, including access revocation. We establish that the networked storage systems implement simpler, centralized storage specifications with local access-control checks. More specifically, we prove that the former