Lecture Notes in Computer Science 3442 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Maura Cerioli (Ed.) Fundamental Approaches to Software Engineering 8th International Conference, FASE 2005 Held as Part of the Joint European Conferences onTheoryandPracticeofSoftware,ETAPS2005 Edinburgh, UK, April 4-8, 2005 Proceedings 1 3 VolumeEditor MauraCerioli UniversitàdiGenova,DISI ViaDodecaneso35,16146Genova,Italy E-mail:[email protected] LibraryofCongressControlNumber:2005922879 CRSubjectClassification(1998):D.2,F.3,D.3 ISSN 0302-9743 ISBN-10 3-540-25420-XSpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-25420-1SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springeronline.com ©Springer-VerlagBerlinHeidelberg2005 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11405955 06/3142 543210 Foreword ETAPS 2005 was the eighth instance of the European Joint Conferences on TheoryandPracticeofSoftware.ETAPSisanannualfederatedconferencethat was established in 1998 by combining a number of existing and new confer- ences. This year it comprised five conferences (CC, ESOP, FASE, FOSSACS, TACAS), 17 satellite workshops (AVIS, BYTECODE, CEES, CLASE, CMSB, COCV, FAC, FESCA, FINCO, GCW-DSE, GLPL, LDTA, QAPL, SC, SLAP, TGC, UITP), seven invited lectures (not including those that were specific to the satellite events), and several tutorials. We received over 550 submissions to the five conferences this year, giving acceptance rates below 30% for each one. Congratulationstoalltheauthorswhomadeittothefinalprogram!Ihopethat mostoftheotherauthorsstillfoundawayofparticipatinginthisexcitingevent and I hope you will continue submitting. The events that comprise ETAPS address various aspects of the system de- velopmentprocess,includingspecification,design,implementation,analysisand improvement. The languages, methodologies and tools which support these ac- tivities are all well within its scope. Different blends of theory and practice are represented, with an inclination towards theory with a practical motivation on the one hand and soundly based practice on the other. Many of the issues involved in software design apply to systems in general, including hardware sys- tems, and the emphasis on software is not intended to be exclusive. ETAPS is a loose confederation in which each event retains its own identity, with a separate program committee and proceedings. Its format is open-ended, allowing it to grow and evolve as time goes by. Contributed talks and system demonstrations are in synchronized parallel sessions, with invited lectures in plenarysessions.Twooftheinvitedlecturesarereservedfor“unifying”talkson topics of interest to the whole range of ETAPS attendees. The aim of cramming all this activity into a single one-week meeting is to create a strong magnet for academic and industrial researchers working on topics within its scope, giving them the opportunity to learn about research in related areas, and thereby to fosternewandexistinglinksbetweenworkinareasthatwereformerlyaddressed in separate meetings. ETAPS 2005 was organized by the School of Informatics of the University of Edinburgh, in cooperation with – European Association for Theoretical Computer Science (EATCS); – European Association for Programming Languages and Systems (EAPLS); – European Association of Software Science and Technology (EASST). The organizing team comprised: – Chair: Don Sannella – Publicity: David Aspinall – Satellite Events: Massimo Felici VI Foreword – Secretariat: Dyane Goodchild – Local Arrangements: Monika-Jeannette Lekuse – Tutorials: Alberto Momigliano – Finances: Ian Stark – Website: Jennifer Tenzer, Daniel Winterstein – Fundraising: Phil Wadler ETAPS 2005 received support from the University of Edinburgh. Overall planning for ETAPS conferences is the responsibility of its Steering Committee, whose current membership is: Perdita Stevens (Edinburgh, Chair), Luca Aceto (Aalborg and Reykjav´ik), Rastislav Bodik (Berkeley), Maura Cerioli (Genoa), Evelyn Duesterwald (IBM, USA), Hartmut Ehrig (Berlin), Jos´e Fiadeiro (Leicester), Marie-Claude Gaudel (Paris), Roberto Gorrieri (Bologna), ReikoHeckel(Paderborn),HolgerHermanns(Saarbru¨cken),Joost-Pieter Katoen (Aachen), Paul Klint (Amsterdam), Jens Knoop (Vienna), Kim Larsen (Aalborg), Tiziana Margaria (Dortmund), Ugo Mon- tanari (Pisa), Hanne Riis Nielson (Copenhagen), Fernando Orejas (Barcelona), Mooly Sagiv (Tel Aviv), Don Sannella (Edinburgh), Vladimiro Sassone (Sussex), Peter Sestoft (Copenhagen), Michel Wermelinger (Lisbon), Igor Walukiewicz (Bordeaux), Andreas Zeller (Saarbru¨cken), Lenore Zuck (Chicago). I would like to express my sincere gratitude to all of these people and or- ganizations, the program committee chairs and PC members of the ETAPS conferences, the organizers of the satellite events, the speakers themselves, the many reviewers, and Springer for agreeing to publish the ETAPS proceedings. Finally, I would like to thank the organizer of ETAPS 2005, Don Sannella. He has been instrumental in the development of ETAPS since its beginning; it is quite beyond the limits of what might be expected that, in addition to all the work he has done as the original ETAPS Steering Committee Chairman and current ETAPS Treasurer, he has been prepared to take on the task of orga- nizing this instance of ETAPS. It gives me particular pleasure to thank him for organizing ETAPS in this wonderful city of Edinburgh in this my first year as ETAPS Steering Committee Chair. Edinburgh, January 2005 Perdita Stevens ETAPS Steering Committee Chair Preface The conference on Fundamental Approaches to Software Engineering (FASE) is one of the European Joint Conferences on Theory and Practice of Software (ETAPS).Assuch,itprovidesacommonforumforpractitionersandresearchers to discuss theories for supporting and improving software engineering practices and their practical application in real contexts. Contributions were sought targeting both pragmatic concepts and their for- malfoundationswhichcouldleadtonewengineeringpracticesandahigherlevel of reliability, robustness, and evolvability of heterogeneous software federations. The record submission of 99 research papers and 6 tool demos was the re- sponse of the scientific community, with contributions ranging from theoretical aspects, such as graph grammars, graph transformation, agent theory and al- gebraic specification languages, to applications to industrially used languages, methods, technologies, and tools, including UML, Web services, product lines, component-based development, Java, and Java cards. The scientific program was complemented by the invited lectures of G´erard Berry on Esterel v7: from Verified Formal Specification to Efficient Industrial Designs and of Thomas A. Henzinger on Checking Memory Safety with Blast. The authors of the submissions were from 29 countries, both within Europe (Belgium, Denmark, Finland, France, Germany, Hungary, Ireland, Italy, Lux- embourg, Macedonia, Portugal, Spain, Sweden, Switzerland, The Netherlands, United Kingdom) and outside (Australia, Brazil, Canada, China, India, Japan, Korea, Pakistan, Russia, Thailand, Tunisia, Turkey, USA). It is a pleasure to notetheincreasingnumberofsubmissionsfromeasternEuropeandfromoutside Europe altogether, showing that FASE is gaining importance as a world-wide conference. ThehelpoftheProgramCommitteewasinvaluableinselectingjust25papers (3 of them tool demos) from the large number of high-quality submissions, and I take the opportunity to thank warmly all its members and the other referees for supporting the selection process with their precious time. FASE 2005 was held in Edinburgh, hosted and organized by the School of Informatics of the University of Edinburgh. Next year FASE will take place in Vienna (Austria). BeingpartofETAPS,FASEsharesthesponsoringandsupportdescribedby theETAPSChairintheForeword.HeartfeltthanksarealsoduetoJos´eFiadeiro andPerditaStevensfortheirgreateffortsintheglobalETAPSorganizationand to Don Sannella and his staff for the wonderful job as local organizers. Finally, a special thanks to the contributors to and participants of FASE, who in the end are the people making the conference worthwhile. Genoa, January 2005 Maura Cerioli Organization Program Committee Silvia Teresita Acun˜a (Universidad Auto´noma de Madrid, Spain) Leonor Barroca (Open University, UK) Yolande Berbers (Katholieke Universiteit Leuven, Belgium) Jean B´ezivin (University of Nantes, France) Jean-Michel Bruel (University of Pau, France) Maura Cerioli (Universita` di Genova, Italy) Marsha Chechik (University of Toronto, Canada) Gianpaolo Cugola (Politecnico di Milano, Italy) Colin Fidge (University of Queensland, Australia) Anthony Finkelstein (University College London, UK) Chris George (UNU/IIST, Macao 1, China) Martin Große-Rhode (Fraunhofer-Institut fu¨r Software und Systemtechnik, Germany) Tomasz Janowski (University of Gdan´sk, Poland) Mehdi Jazayeri (Technical University of Vienna, Austria) Cliff Jones (University of Newcastle upon Tyne, UK) Anto´nia Lopes (University of Lisbon, Portugal) Tiziana Margaria (University of Dortmund, Germany) Stephan Merz (INRIA Lorraine, LORIA, France) Carlo Montangero (Universita` di Pisa, Italy) Doron Peled (University of Warwick, UK) Ernesto Pimentel (Universidad de Ma´laga, Spain) Michel Wermelinger (Universidade Nova de Lisboa, Portugal) Roel Wieringa (University of Twente, The Netherlands) Alexander Wolf (University of Colorado at Boulder, USA) Reviewers Vincenzo Ambriola Oscar Dieste Markus Hardt Jonathan Amir Francisco Dura´n David N. Jansen Giovanni Cignoni Rik Eshuis Ioannis Kassios Joey Coleman Pascal Fenkam Engin Kirda Maya Daneva Fabio Gadducci Giovanni Lagorio Valeria de Castro Vincenzo Gervasi Albert Lai Juan de Lara Mihaela Gheorghiu Jos´e A. Mac´ıas Iglesias Benet Devereux Vittoria Gianuzzi Paola Magillo Manuel D´ıaz Arie Gurfinkel Antonio Man˜a X Organization Stefan Mann Andrea Polini Klaas Sikkel Pedro Merino Claudia Pons Judith Stafford Henry Muccini Lucia Rapanotti Bedir Tekinerdogan Shiva Nejati Gianna Reggio Klaas Van den Berg Johann Oberleitner Arend Rensink Pascal van Eck Jos´e Luis Pastrana Matthew Rutherford Ou Wei Mo´nica Pinto Laura Semini Elena Zucca Stanislav Pokraev Almudena Sierra Table of Contents Invited Contributions Esterel v7: From Verified Formal Specification to Efficient Industrial Designs G´erard Berry.................................................. 1 Checking Memory Safety with Blast Dirk Beyer, Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar... 2 Web Services Analyzing Web Service Based Business Processes Axel Martens.................................................. 19 Automatic Conformance Testing of Web Services Reiko Heckel, Leonardo Mariani ................................. 34 Graph Grammars and Graph Transformations Termination Criteria for Model Transformation Hartmut Ehrig, Karsten Ehrig, Juan de Lara, Gabriele Taentzer, D´aniel Varro´, Szilvia Varro´-Gyapay ............................. 49 Ensuring Structural Constraints in Graph-Based Models with Type Inheritance Gabriele Taentzer, Arend Rensink................................ 64 Modelling Parametric Contracts and the State Space of Composite Components by Graph Grammars Ralf H. Reussner, Jens Happe, Annegret Habel..................... 80 Components Improving the Build Architecture of Legacy C/C++ Software Systems Homayoun Dayani-Fard, Yijun Yu, John Mylopoulos, Periklis Andritsos.............................................. 96