Lecture Notes in Computer Science 3555 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 Tullio Vardanega Andy Wellings (Eds.) Reliable Software Technology – Ada-Europe 2005 10th Ada-Europe International Conference on Reliable Software Technologies York, UK, June 20-24, 2005 Proceedings 1 3 VolumeEditors TullioVardanega UniversityofPadua DepartmentofPureandAppliedMathematics viaG.Belzoni7,35131Padua,Italy E-mail:[email protected] AndyWellings UniversityofYork DepartmentofComputerScience Heslington,York,YO105DD,UK E-mail:[email protected] LibraryofCongressControlNumber:2005927232 CRSubjectClassification(1998):D.2,D.1.2-5,D.3,C.2-4,C.3,K.6 ISSN 0302-9743 ISBN-10 3-540-26286-5SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-26286-2SpringerBerlinHeidelbergNewYork 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:11499909 06/3142 543210 Preface StartedontheinspiredinitiativeofProf.AlfredStrohmeierbackin1996,andspawned from the annual Ada-Europe conference that had previously run for 16 consecutive years,theInternationalConferenceonReliableSoftwareTechnologiescelebratedthis year its tenth anniversary by going to York, UK, where the first series of technical meetingsonAdawereheldinthe1970s. Besidesbeingabeautifulandhistoricalplaceinitself,YorkalsohoststheDepart- ment of Computer Science of the local university, whose Real-Time Group has been tremendouslyinfluentialinshapingtheAdalanguageandintheprogressonreal-time computingworldwide.Thisyear’sconferencewasthereforeputtogetherunderexcel- lentauspices,inaveryimportantyearfortheAdacommunityinviewoftheforthcom- ingcompletionoftherevisionprocessthatisupgradingthelanguagestandardtoface thechallengesofthenewmillennium. The conference took place on June 20–24, 2005. It was as usual sponsored by Ada-Europe, the European federation of national Ada societies, in cooperation with ACM SIGAda. The conference was organized by selected staff of the University of YorkteamedupwithcollaboratorsfromvariousplacesinEurope,inwhatturnedoutto beaveryeffectiveinstanceofdistributedcollaborativeprocessing.Theconferencealso enjoyedthegeneroussupportof11industrialsponsors. This year’s conference was very successful indeed. It attracted the largest number of submissions in years, from as many as 15 countries worldwide, which made the selectionprocesstougherthanever.Overall,theconferenceprogramincluded21care- fully selected and refereed papers assigned to 8 thematic sessions spanning a variety of high-profile subjects. The technical program included an industrial track, a first in the conference’s history, which encompassed 10 contributions illustrating challenges facedbyacross-sectionofhigh-integritysoftwareindustryinEuropeandtheUS.As usual, the conference program was itself bracketed by two full days of tutorials, with a special half-day presentation on the new Ada 2005 language, offered by four of its leaddesigners:JohnBarnes,AlanBurns,PascalLeroyandTuckerTaft.Furthermore, three keynote presentations, delivered by John McDermid, Martin Thomas and Bev Littlewood,respectively,markedtheopeningofeachofthemainconferencedays.Fi- nally,muchinkeepingwiththewell-establishedtraditionoftheconferenceseries,the programmadeprovisionsforanexcellentlypopulatedvendorexhibitionandforahalf- dayvendorsession,inwhichparticipantswereabletocatchupwiththelatestadvances inreliablesoftwaretechnologyproducts. Letusnowgointothedetailsofsomeoftheconferencehighlights. VI Preface Theinvitedtalkswereasfollows: – Prof.JohnMcDermid,UniversityofYork,UK Model-BasedDevelopmentofSafety-CriticalSoftware wheretheopportunitiesandchallengesofmodel-baseddevelopmentwerediscussed. – Prof.MartynThomas,ThomasAssociates,UK ExtremeHubris wheretheprinciplesofExtremeProgrammingwerecriticallyexaminedandanalternative manifestofordependablesoftwaredevelopmentwasproposed. – Prof.BevLittlewood,CityUniversity,London,UK AssessingtheDependabilityofSoftware-BasedSystems:aQuestionofConfidence wherethecontroversialcontentionwasmadethatdependabilityclaimsoughttobeassoci- atedwithaprobability-basedassessmentoftheinherentuncertaintyaboutthetruthofthe claim. The technical sessions of the program ranged from the illustration of successful applications and distributed systems, to the discussion of design, analysis and imple- mentationmethodologies,toformalmethods,certificationandverification,throughto thelatestadvanceswithRavenscartechnology,tofinishwithAda-relatedconcernsre- gardingeducationandlanguageimplementationissues. Thetutorialprogramgatheredthefollowingassortmentoftopicsandinternational expertspeakers – Developing Web-Aware Applications in Ada with AWS, Jean-Pierre Rosen, Adalog, France – CorrectnessbyConstruction—AManifestoforHighIntegritySystems,PeterAmey andNeilWhite,PraxisHighIntegritySystems,UK – Real-TimeJavaforAdaProgrammers,BenjaminM.Brosgol,AdaCore,US – SAEArchitectureAnalysisandDesignLanguage,JoyceTokar,PyrrhusSoftware,US andBruceLewis,USArmy – High-IntegrityRavenscarUsingSPARK,BrianDobbing,PraxisHighIntegritySystems, UK – SoftwareSafetyCases,JohnMcDermidandRobWeaver,UniversityofYork,UK – Requirement Engineering for Dependable Systems, William Bail, The MITRE Corporation,US – SoftwareFaultTolerance,PatrickRogers,AdaCore,US – Programming with the Ada 2005 Standard Container Library,MatthewHeaney,On2 Technologies,US in addition of course to a special half-day session where four of the lead designers ofAda2005, JohnBarnes,AlanBurns,Pascal LeroyandS.Tucker Taft,provided an extensiveoverviewofthenewfeaturesintroducedbythelanguagerevision. Anumberofpeoplecruciallycontributedtothesuccessoftheconference.Firstand foremost the authors of all the papers, talks and presentations, for it was from their contribution that the conference was put together. The Program Committee members helpedpromotetheconferenceintheirowncirclesandalsosuccessfullysolicitedsub- missionsfromavarietyofauthors.Thesamemembersalongwithanumberofothers alsodevotedconsiderableefforttorefereeingthesubmissionsinathoroughandtimely fashion.TheprogramitselfwasputtogetherbyasmallergroupincludingtheConfer- enceChair,AlanBurns,theProgramCo-chairs,TullioVardanegaandAndyWellings, Preface VII theTutorialsChair,IainBate,theExhibitionandIndustrialTrackChair,RodChapman, and Dirk Craeynest, representing Ada-Europe. Selected PC members also undertook to shepherd some papers to their final versions. All of these people deserve our grat- itude, along with the local organizers, in particular Ian Broster, also in charge of the conference publicity along with Dirk Craeynest, and Sue Helliwell, who oversaw the administrativedetailsoftheregistrationprocess. Wetrusttheattendeesenjoyedboththetechnicalandsocialprogramoftheconfer- ence,andweclosethisvolumewiththeconfidenceofajobwelldoneandthesatisfac- tionofathoroughlyenjoyedexperience. June2005 TullioVardanega Organization ConferenceChair AlanBurns,UniversityofYork,UK ProgramCo-chairs TullioVardanega,UniversityofPadua,Italy AndyWellings,UniversityofYork,UK TutorialChair IainBate,UniversityofYork,UK ExhibitionandIndustrialTrackChair RodChapman,PraxisHighIntegritySystems,UK PublicityCo-chairs IanBroster,UniversityofYork,UK DirkCraeynest,AubayBelgium,KatholiekeUniversiteitLeuven,Belgium LocalOrganization Administrator SueHelliwell,UniversityofYork,UK Ada-EuropeConferenceLiaison LaurentPautet,ENSTParis,France X Organization OtherProgramCommiteeMembers LarsAsplund,Ma¨lardalensHo¨gskola,Sweden AlejandroAlonso,UniversidadPolitecnicadeMadrid,Spain JanetBarnes,PraxisHighIntegritySystems,UK GuillemBernat,UniversityofYork,UK JohannBlieberger,TechnischeUniversita¨tWien,Austria BerndBurgstaller,TechnischeUniversita¨tWien,Austria UlfCederling,VaxjoUniversity,Sweden AlfonsCrespo,UniversidadPolitecnicadeValencia,Spain RaymondDevillers,Universite´ LibredeBruxelles,Belgium MichaelGonza´lezHarbour,UniversidaddeCantabria,Spain AndrewHately,CEATSResearchDevelopmentSimulationCentre,Hungary Gu¨nterHommel,TechnischenUniversita¨tBerlin,Germany StefanKauer,EADSDornier,Germany HubertKeller,Institutfu¨rAngewandteInformatik,Germany YvonKermarrec,ENSTBretagne,France Jo¨rgKienzle,McGillUniversity,Canada FabriceKordon,Universite´ Pierre&MarieCurie,France AlbertLLamosi,UniversitatdelesIllesBalears,Spain FrancoMazzanti,IstitutodiScienzaeTecnologiedell’Informazione,Italy JohnMcCormick,UniversityofNorthernIowa,USA JavierMiranda,UniversidadLasPalmasdeGranCanaria,Spain JuanA.delaPuente,UniversidadPolitecnicadeMadrid,Spain ErhardPlo¨dereder,Universita¨tStuttgart,Germany AlexanderRomanovsky,UniversityofNewcastleuponTyne,UK Jean-PierreRosen,Adalog,France EdmondSchonberg,NewYorkUniversityandAdaCore,USA Jo¨rgenWinkler,Friedrich-Schiller-Universita¨t,Germany Referees AlejandroAlonso JohnClark LasAsplund DirkCraeynest KhaledBarbaria AlfonsCrespo JanetBarnes RaymondDevillers GuillemBernat ClaudeDutheillet JohannBlieberger JavierEsparza MaartenBoasson MichaelGonza´lez-Harbour BenBrosgol AndrewHately IanBroster Gu¨nterHommel BerndBurgstaller ErikHu AlanBurns JeromeHugues UlfCederling AlexeiIliasov Organization XI StefanKauer JuanA.delaPuente HubertKeller ErhardPlo¨dereder YvonKermarrec AlexanderRomanovsky Jo¨rgKienzle Jean-PierreRosen FabriceKordon BoSande`n AlbertLlamosi EdmondSchonberg MorenoMarzolla TullioVardanega FrancoMazzanti ThomasVergnaud JavierMiranda AndyWellings JohnMcCormick Jo¨rgenWinkler LaurentPautet Table of Contents Applications ILTIS-TheLegacyofaSuccessfulProduct NevilleRowden ................................................. 1 A Reference Control Architecture for Service Robots Implemented on a ClimbingVehicle Francisco Ortiz, Diego Alonso, Ba´rbara A´lvarez, JuanA.Pastor.................................................. 13 AnAdaFrameworkforQoS-AwareApplications Lu´ısMiguelPinho,LuisNogueira,RicardoBarbosa.................... 25 DesignandSchedulingIssues EfficientAlternativesforImplementingFixed-PrioritySchedulers Sergio Sa´ez, Vicent Lorente, Silvia Terrasa, AlfonsCrespo .................................................. 39 ANewStrategyfortheHRT-HOODtoAdaMapping MatteoBordin,TullioVardanega ................................... 51 UsingtheAADLtoDescribeDistributedApplicationsfromMiddlewareto SoftwareComponents ThomasVergnaud,LaurentPautet,FabriceKordon..................... 67 FormalMethods ExtendingRavenscarwithCSPChannels Diyaa-AddeinAtiya,SteveKing .................................... 79 DynamicTasksVerificationwithQUASAR Sami Evangelista, Claude Kaiser, Christophe Pajault, JeanFrancoisPradat-Peyre,PierreRousseau ......................... 91 ProvingFunctionalEquivalenceforProgramSlicinginSPARKTM RickyE.Sward,LeemonC.BairdIII ................................ 105