Tagungsband
Dagstuhl-Workshop MBEES: Modellbasierte Entwicklung eingebetteter Systeme II WS-Nr. 06022 Model-Based Development of Embedded Systems 09. – 13.01.2006
Informatik Bericht TU Braunschweig 2006-01 Institut für Software Systems Engineering Technische Universität Braunschweig Mühlenpfordtstraße 23 D-38106 Braunschweig
[GRS06] H. Giese, B. Rumpe, B. Schätz. Tagungsband Dagstuhl-Workshop MBEES: Modellbasierte Entwicklung eingebetteter Systeme II. Informatik-Bericht 2006-01 Technische Universität Braunschweig. www.se-rwth.de/publications
Inhaltsverzeichnis Eignung der UML 2.0 zur Entwicklung von Bordnetzarchitekturen Michael von der Beek ..............................................
1
Einsatz von Modell-basierten Entwicklungstechniken in sicherheitsrelevanten Anwendungen: Herausforderungen und Lösungsansätze Mirko Conrad, Heiko Dörr ..........................................
6
Petri Net Model Synthesis from Scenarios Jörg Desel ....................................................... 19 Abdeckungskriterien in der modellbasierten Testfallgenerierung: Stand der Technik und Perspektiven Mario Friske, Bernd-Holger Schlingloff ................................ 27 Scenario-Based Verification of Automotive Software Systems Matthias Gehrke, Petra Nawratil, Oliver Niggemann, Wilhelm Schäfer, Martin Hirsch .................................................... 35 Enhanced Requirements-Based Programming for Embedded Systems Design Michael G. Hinchey, Tiziana Margaria, James L. Rash, Christopher A. Rouff, Bernhard Steffen ................................. 43 Comparing Heuristics for Model Based Testsuite Generation Michaela Huhn, Tilo Mücke ......................................... 53 UML-basierte Entwicklung sicherheitskritischer Systeme im Bahnbereich Hardi Hungar .................................................... 63 An Actor-Oriented Model-Based Design Flow for Systems-on-Chip Leandro Soares Indrusiak, Manfred Glesner ............................ 65 Using an UML profile for timing analysis with the IF validation tool-set Iulian Ober, Susanne Graf, Yuri Yushtein ............................... 75 Zur Kosteneffektivität des modellbasierten Testens Alexander Pretschner .............................................. 85 Real-time Operating Systems for Self-coordinating Embedded Systems Franz J. Rammig, Marcelo Götz, Tales Heimfarth, Peter Janacik, Simon Oberthür ................................................... 95 Some motivation and current results for synchronous modeling and implementation Jan Romberg ..................................................... 105
III
Testing of Embedded Control Systems with Continous Signals Ina Schieferdecker, Jürgen Großmann ................................. 113 Domänenspezifische Integration von Modellierungswerkzeugen mit Sichten Andy Schürr, Johannes Jakob ........................................ 123 Derivation of Executable Test Models from Embedded System Models using Model Driven Architecture Artefacts - Automotive Domain Justyna Zander-Nowicka, Ina Schieferdecker, Tibor Farkas ................ 131
IV
Dagstuhl-Workshop MBEES: Modellbasierte Entwicklung eingebetteter Systeme II (WS-Nr. 06022: Model-Based Development of Embedded Systems) Auch wenn ihr durch die Prägung des Begriffs „Model-Driven Architecture“ (MDA) durch die OMG zusätzliche Aufmerksamkeit zugekommen ist, hat die modellbasierte Entwicklung in vielen Bereichen von der Geschäftsprozessmodellierung bis hin zur Beschreibung von eingebetteten Steuerungssystemen Anwendung gefunden und geht dabei in den eingesetzten Techniken und Verfahren über die Trennung von plattformunabhängigen und plattformspezifischen Systembeschreibungen und den Übergang dazwischen hinaus. Zentrales Merkmal der modellbasierten Entwicklung ist dabei der Einsatz von Modellen, die sich an der Problem- anstatt der Lösungsdomäne orientieren. Dies bedingt einerseits die Bereitstellung anwendungsorientierter Modelle (z.B. Matlab/Simulink-artige für regelungstechnische Problemstellungen, Statechart-artige für reaktive Anteile) und ihrer zugehörigen konzeptuellen (z.B. Komponenten, Signal, Nachrichten, Zustände) und semantischen Aspekte (z.B. synchroner Datenfluss, ereignisgesteuerte Kommunikation). Andererseits bedeutet dies auch die Abstimmung auf die jeweilige Entwicklungsphase, mit Modellen von der Anwendungsanalyse (z.B. Beispielszenarien, Schnittstellenmodelle) bis hin zur Implementierung (z.B. Bus- oder Task-Schedules, Implementierungstypen). Für eine durchgängige modellbasierte Entwicklung ist daher im Allgemeinen die Verwendung eines Modell nicht ausreichend, sondern der Einsatz einer Reihe von abgestimmten Modellen für Sichten und Abstraktionen des zu entwickelnden Systems (z.B. funktionale Architektur, logische Architektur, technische Architektur, Hardware-Architektur) nötig. Durch den Einsatz problem- statt lösungszentrierter Modelle kann in jedem Entwicklungsabschnitt von unnötigen Festlegungen abstrahiert werden, während besonders wichtige und kritische Aspekte explizit und frühzeitig modelliert werden (z.B. Zeit, Prioritäten oder Kommunikationsaspekte). Die dadurch ermöglichte Anwendung analytischer und generativer Verfahren auf diesen Modellen ermöglicht die effiziente Entwicklung hochqualitativer Software. Modellbasierte Vorgehensweisen haben gerade in der Softwareentwicklung in den letzten Jahren deutlich an Bedeutung gewonnen. Gerade im Bereich eingebetteter Software (z.B. Automotive oder Avionic Software Engineering) erfährt der Einsatz von domänenspezifischen Modellierungswerkzeugen in der Softwarenetwicklung zunehmend an Verbreitung. Wesentlich dazu haben dabei die Weiterentwicklung von Sprachen für aufgabenspezifische Modelle (z.B. synchroner Datenfluss) und dazugehörige Werkzeugen für spezialisierte Bereiche (z.B. Regelungs- und Steuerungsalgorithmen, Anlagensteuerung) und die Verbesserung der Ent-wicklungswerkzeuge, vor allem hinsichtlich Implementierungsqualität, Bedienkomfort und Analysemächtigkeit beigetragen. Trotzdem sind im Kontext der modellbasierten Entwicklung noch viele, auch grundlegende Fragen offen, insbesondere im Zusammenhang mit der Durchgängigkeit. Die in diesen Tagungsband zusammengefassten Papiere stellen zum Teil gesicherte Ergebnisse, Work-InProgress, industrielle Erfahrungen und innovative Ideen aus diesem Bereich zusammen und erreichen damit eine interessante Mischung theoretischer Grundlagen und praxisbezogener Anwendung.
V
Genau wie beim ersten, im Januar 2005 erfolgreich durchgeführten Workshop sind damit wesentliche Ziele dieses Workshops erreicht: -
Austausch über Probleme und existierende Ansätze zwischen den unterschiedlichen Disziplinen (insbesondere Elektro- und Informationstechnik, Maschinenwesen/Mechatronik und Informatik)
-
Austausch über relevante Probleme in der Anwendung/Industrie und existierende Ansätze in der Forschung
-
Verbindung zu nationalen und internationalen Aktivitäten (z.B. Initiative des IEEE zum Thema Model-Based Systems Engineering, GI-AK Modellbasierte Entwicklung eingebetteter Systeme, GI-FG Echtzeitprogrammierung, MDA Initiative der OMG)
Die Themengebiete, für die dieser Workshop gedacht ist und fachlich sehr gut abgedeckt sind, sich dieses Jahr (mit Ausnahmen) aber sehr stark auf den automotiven Bereich konzentrieren, fokussieren auf Teilaspekte modellbasierter Entwicklung eingebetteter Softwaresysteme. Darin enthalten sind unter anderem: -
Domänenspezifische Ansätze zur Modellierung von Systemen (z.B. Avionik, Railway, Automotive, Produktions- und Automatisierungstechnik)
-
Durchgängigkeit und Integration von Modellen für eingebettete Systeme
-
Modellierung spezifischer Eigenschaften eingebetteter Systeme (z.B. Echtzeiteigenschaften, Robustheit/Zuverlässigkeit, Ressourcenmodellierung)
-
Konstruktiver Einsatz von Modellen (Generierung und Evolution)
-
Modellbasierte Validierung und Verifikation
Das Organisationskomitee ist der Meinung, dass mit den Teilnehmern aus Industrie, Werkzeugherstellern und der Wissenschaft die bereits 2005 erfolgte Community-Bildung erfolgreich weitergeführt wurde, und damit demonstriert, dass eine solide Basis zur Weiterentwicklung des noch jungen Felds modellbasierter Entwicklung eingebetteter Systeme existiert. Die Durchführung eines erfolgreichen Workshops ist ohne vielfache Unterstützung nicht möglich. Wir danken daher den Mitarbeitern von Schloss Dagstuhl und natürlich unseren Sponsoren.
Schloss Dagstuhl im Januar 2006, Das Organisationskomitee Holger Giese, Univ. Paderborn Bernhard Rumpe, TU Braunschweig Bernhard Schätz, TU München Executive assistant Holger Krahn, TU Braunschweig
IV
Die ETAS Group, 2003 durch den Verbund der Unternehmen ETAS, Vetronix und LiveDevices entstanden, liefert ein komplettes Spektrum einheitlicher Entwicklungs- und Diagnosewerkzeuge, die den gesamten Lebenszyklus eines Steuergeräts umfassen. Die neue Verbindung der Entwicklungswerkzeuge mit den Diagnose- und Servicelösungen bildet die Basis für die Automotive LifeCycle SolutionsStrategie, mit der die ETAS Group die Vision von lebenszyklusübergreifenden Diagnosewerkzeugen im Fahrzeug Wirklichkeit werden lässt. Auf lange Sicht sieht sich die ETAS Group als starker Industriepartner, der Werkzeuge und Softwarekomponenten für die drei elementaren Aspekte elektronischer Steuergeräte anbietet (Control Functions, Diagnostic Functions und Platform Software Components). Innerhalb der Gesellschaft für Informatik e.V. (GI) befasst sich eine große Anzahl von Fachgruppen explizit mit der Modellierung von Software- bzw. Informationssystemen. Der erst neu gegründete Querschnittsfachausschuss Modellierung der GI bietet den Mitgliedern dieser Fachgruppen der GI - wie auch nicht organisierten Wissenschaftlern und Praktikern ein Forum, um gemeinsam aktuelle und zukünftige Themen der Modellierungsforschung zu erörtern und den gegenseitigen Erfahrungsaustausch zu stimulieren. Das Institut für Software Systems Engineering (SSE) der TU Braunschweig entwickelt einen innovativen Ansatz des Model Engineering, bei dem ein Profil der UML entwickelt wird, das speziell zur Generierung modellbasierter Tests und zur evolutionären Weiterentwicklung auf Modellbasis geeignet ist (B. Rumpe: Agile Modellierung mit UML. Springer Verlag 2004). SSE ist auch Mitherausgeber des Journals on Software and Systems Modeling. Der Lehrstuhl für Software Systems Engineering der TU München entwickelt in enger Kooperation mit industriellen Partnern modellbasierte Ansätze zur Entwicklung eingebetteter Software. Schwerpunkte sind dabei die Integration ereignisgetriebener und zeitgetriebener Systemanteile, die Berücksichtigung sicherheitskritischer Aspekte, modellbasierte Testfallgenerierung und modellbasierte Anforderungsanalyse, sowie den werkzeuggestützten Entwurf.
VII
dSPACE ist der weltweit führende Anbieter von Lösungen für die Entwicklung und den Test schneller mechatronischer Regelungssysteme. Anwendungsbereiche für dSPACE-Systeme finden sich vor allem in der Automobilindustrie, aber auch in der Antriebstechnik, der Luft- und Raumfahrt und der Industrieautomation. Das Software Quality Lab (s-lab) ist ein Institut für Kompetenz- und Technologietransfer, in dem Partner aus der industriellen Softwareentwicklung mit Forschungsgruppen der Universität Paderborn auf dem Gebiet der Softwaretechnik eng zusammenarbeiten. Zielsetzung des s-lab ist die Entwicklung und Evaluierung von konstruktiven und analytischen Methoden sowie Werkzeugen der Softwaretechnik, um qualitativ hochwertige Softwareprodukte zu erhalten. Eine hohe Relevanz für die industrielle Softwareentwicklung sowie die Notwendigkeit des Einsatzes wissenschaftlicher Methoden kennzeichnen die im s-lab bearbeiteten Fragestellungen. Schloss Dagstuhl wurde 1760 von dem damals regierenden Fürsten Graf Anton von Öttingen-SoeternHohenbaldern erbaut. Nach der französischen Revolution und der Besetzung durch die Franzosen 1794 war Dagstuhl vorübergehend im Besitz eines Hüttenwerkes in Lothringen. 1806 wurde das Schloss mit den zugehörigen Ländereien von dem französischen Baron Wilhelm de Lasalle von Louisenthal erworben. 1959 starb der Familienstamm der Lasalle von Louisenthal in Dagstuhl mit dem Tod des letzten Barons Theodor aus. Das Schloss wurde anschließend von den Franziskus-Schwestern übernommen, die dort ein Altenheim errichteten. 1989 erwarb das Saarland das Schloss zur Errichtung des Internationalen Begegnungs- und Forschungszentrums für Informatik. Das erste Seminar fand im August 1990 statt. Jährlich kommen ca. 2600 Wissenschaftler aus aller Welt zu 40-45 Seminaren und viele sonstigen Veranstaltungen.
VIII
Eignung der UML 2.0 zur Entwicklung von Bordnetzarchitekturen Michael von der Beeck E/E Prozessentwicklung BMW Group 80788 München [email protected]
Abstract: In diesem Positionspapier wird die Eignung der UML 2.0 zur Modellierung von Bordnetzarchitekturen in der Automobilindustrie untersucht. Diese Untersuchung wird durch eine Gegenüberstellung relevanter Charakteristika von Fahrzeug-IT und Business-IT motiviert. Ein potentielles Problem bei dem Einsatz der UML 2.0 wird bei einer Betrachtung der Architektur- und Komponentenentwicklung in der Fahrzeug-IT sichtbar. Hieraus wird als Handlungsbedarf die Überprüfung der Integrierbarkeit der UML 2.0 mit etablierten, domänen-spezifischen Modellierungsnotationen abgeleitet.
1 Einleitung In diesem Positionspapier wird die Eignung der UML 2.0 zur Erstellung von Architekturen im Automotive-Kontext untersucht. Hierzu wird zunächst ein schematischer Überblick über die Architektur- und Komponentenentwicklung für Fahrzeugbordnetze gegeben. Dann werden Charakteristika der beiden Bereiche Fahrzeug-IT und Business-IT der Automobilindustrie gegenübergestellt. Anschließend werden Eigenschaften der UML 2.0 aufgeführt, die für bzw. gegen ihren Einsatz in der Fahrzeug-IT sprechen. Nachfolgend wird der Aspekt der Integration von Architekturund Komponentenentwicklung in der Fahrzeug-IT betrachtet. Hierbei steht eine Integration von Architekturmodellen, die mit UML 2.0 erstellt werden, und von Komponentenmodellen, die mit etablierten, domänen-spezifischen Modellierungsnotationen wie MATLAB/Simulink oder ASCET erstellt werden, im Vordergrund. Als Fazit resultiert ein Handlungsbedarf: Die Integrierbarkeit von UML 2.0-Modellen und MATLAB/Simulink- bzw. ASCET-Modellen soll überprüft werden.
1
2 Architekturentwicklung für Fahrzeugbordnetze Die nachfolgende Abbildung zeigt schematisch einzelne Schritte bei der Entwicklung von Fahrzeugbordnetzen. Dabei werden lediglich die Architektur-Entwicklung und die Komponenten-Entwicklung relativ detailliert betrachtet.
Abbildung 1: Architektur-Entwicklung und Komponenten-Entwicklung für Fahrzeugbordnetze
Zum Verständnis der Abbildung 1 sollen folgende Begriffsklärungen dienen:
2
-
Funktionsnetz-Architektur: Diese stellt gesamthaft, aber implementierungsunabhängig, die Menge der zu realisierenden Funktionen eines Bordnetzes dar. Zusätzlich ist die Kommunikation zwischen den einzelnen Funktionen grob beschrieben.
-
SW-Architektur: Diese stellt gesamthaft die SW-Komponenten zur Realisierung der Bordnetzfunktionen sowie ihre wechselseitige Kommunikation dar.
-
HW-Architektur: Diese stellt die Menge der Steuergeräte (= ECUs), der Busverbindungen zwischen den Steuergeräten und der Gateways (zur Datenübertragung zwischen verschiedenen Bussen) dar.
-
SW-Partitionierung: Dies ist eine Abbildung der Funktionsnetz-Architekur auf die SWArchitektur.
-
HW-Partitionierung: Dies ist eine Abbildung der Funktionsnetz-Architektur auf die HWArchitektur.
-
Deployment: Dies ist eine Abbildung der SW-Architektur auf die HW-Architektur.
Die linke Seite der Abbildung 1 ist durch die Architektur-Entwicklung gegeben. Die einzelnen Architekturen (Funktionsnetz-Architektur, HW-Architektur und SWArchitektur), die während der Architektur-Entwicklung entstehen, stellen jeweils Systemsichten dar, d.h. gesamthafte Darstellungen des zu erstellenden Systems. Bei der Entwicklung von Bordnetzen steigt die Notwendigkeit zur Verwendung von Systemsichten aufgrund der starken Zunahme der Komplexität von Bordnetzen. In der Automobilindustrie hat sich innerhalb der Architekturentwicklung bisher die Systemsicht HW-Architektur etabliert (als Synonyme hierfür werden vielfach die Begriffe Steuergerätenetzwerk oder Bordnetztopologie verwendet), dahingegen müssen sich die Systemsichten Funktionsnetz-Architektur und SW-Architektur erst noch etablieren.
3 Gegenüberstellung Automotive-Bereich
von
Fahrzeug-IT
und
Business-IT
im
Im Automotive-Bereich lässt sich die Informationstechnologie (IT) in die beiden Bestandteile Business-IT und Fahrzeug-IT zerlegen. 3.1 Charakterisierung der Business-IT Beispiele für Bestandteile der Business-IT im Automotive-Bereich sind: -
Händler-Applikationen (z.B. Diagnose-Software)
-
Produktionsplanungs-Software
-
(fahrzeug-externe) Datenbanken für Autonavigation
Die Verwendung von Systemsichten ist in der Business-IT etabliert. Es existiert nur eine geringe Anzahl eingebetteter Systeme in der Business-IT. In der Business-IT ist der Einsatz der UML zur Modellierung weit verbreitet – sie konstituiert hier bereits einen de-facto-Standard.
3
3.2 Charakterisierung der Fahrzeug-IT Steuergeräte (z.B. Anti-Blockiersystem, Motorsteuerung, On-board Navigation) sind typische Bestandteile der Fahrzeug-IT. In der Fahrzeug-IT ist die Verwendung von Systemsichten für die “späte Phase” der Architekturentwicklung (konkret: für die Entwicklung der HW-Architektur) etabliert, jedoch nicht für die “frühe Phase” der Architekturentwicklung (konkret: für die Entwicklung der Funktionsnetz-Architektur). Es existiert eine große Anzahl eingebetteter Systeme in der Fahrzeug-IT, insbesondere stellen die oben erwähnten Steuergeräte meist eingebettete Systeme dar. Ihre Entwicklung erfordert die Berücksichtigung charakteristischer Anforderungen – hierzu gehören z.B. Anforderungen durch limitierte HW-Ressourcen, Aufstartzeiten, Energieverbrauch und Realzeit. Zur Modellierung und Implementierung einzelner Komponenten (konkret: einzelner Steuergeräte) der Fahrzeug-IT (vgl. „KomponentenEntwicklung“ in Abbildung 1) werden fast ausschließlich domänen-spezifische Notationen/Tools wie MATLAB/Simulink und ASCET eingesetzt, jedoch kaum die UML.
4 Eigenschaften der UML 2.0 In den beiden nachfolgenden Unterkapiteln werden Vor- und Nachteile der UML 2.0 hinsichtlich ihrer Eignung zur Architekturmodellierung aufgeführt. 4.1 Vorteile der UML 2.0 Die UML 2.0 ist sehr ausdrucksmächtig. Die UML ist sehr weit verbreitet. Es existiert bereits eine umfassende Toolunterstützung der UML 2.0 durch viele Toolhersteller. Die UML 2.0 erlaubt eine leichte Modellierbarkeit von Partitionierung und Deployment durch Verwendung ihrer Verteilungsdiagramme, die genau für diese Aufgabe definiert wurden. Die UML 2.0 bietet eine systematische Möglichkeit zur Sprachanpassung durch Definition von (domänen-spezifischen) Profilen. Beispiele für UML 2.0-Profile sind:
4
-
SysML: Systems Engineering-spezifische Anpassung der UML 2.0
-
EAST-ADL: automotive-spezifische Architekturbeschreibungssprache auf UML 2.0-Basis
4.2 Nachteile der UML 2.0 Die UML wird in der Fahrzeug-IT kaum zur Komponentenentwicklung eingesetzt. Entwickler von Funktionsmodellen und von Software für Steuergeräte verwenden stattdessen domänen-spezifische Notationen/Tools wie MATLAB/Simulink und ASCET. Die UML ist keine domänen-spezifische Sprache, insbesondere keine spezifische Sprache zur Entwicklung eingebetteter Systeme. Die UML ist (lediglich) eine Notation, jedoch keine Methode: Ihr fehlen also Regeln zur konkreten (Architektur-)Modellierung. Eine Folgerung aus den beiden letzten Aussagen lautet: Für einen erfolgreichen Einsatz der UML 2.0 ist ein domänen-spezifisches Regelwerk erforderlich. Konkret müssten daher UML 2.0-Modellierungsrichtlinien zur Architekturentwicklung von Bordnetzen erstellt werden.
5 Integration von Architektur- und Komponentenentwicklung in der Fahrzeug-IT Eine Verwendung der UML 2.0 in der Architekturentwicklung der Fahrzeug-IT erscheint viel versprechend, da sich die UML generell zur Architekturbeschreibung bewährt hat (z.B. in der Business-IT). Darüber hinaus wäre eine Verwendung der UML 2.0 in der Komponentenentwicklung der Fahrzeug-IT natürlich auch denkbar, da die UML außerhalb der Fahrzeug-IT bereits einen de-facto-Modellierungsstandard darstellt. Diese Verwendung würde aber kurzfristig einen sehr großen Änderungsaufwand in der Automobilindustrie (bei OEMs und Zulieferern) bedeuten und wird daher in diesem Positionspapier nicht weiter betrachtet. Als Konsequenz ergibt sich, dass für den Einsatz der UML 2.0 zur Architekturmodellierung in der Fahrzeug-IT eine Integration zwischen den betroffenen Modellen der Architekturentwicklung und denen der Komponentenentwicklung realisiert werden muss, also (gemäß Abbildung 1) sowohl zwischen Funktionsnetzarchitektur und Funktionsmodellen als auch zwischen SW-Architektur und SW-Komponenten.1 Aspekte dieser Integration beziehen sich sowohl auf die Definition des Gesamtentwicklungsprozesses als auch auf die Integration der jeweiligen Modelle auf Ebene der verwendeten Modellierungssprachen (d.h. UML 2.0 einerseits und MATLAB/Simulink und/oder ASCET andererseits).
1 Darüber hinaus ist natürlich die konkrete Verwendung der UML 2.0 zur Architekturmodellierung (am besten in Form von UML 2.0-Modellierungsrichtlinien) festzulegen.
5
Daher lässt sich der folgende primäre Handlungsbedarf ableiten: Es besteht die Notwendigkeit zur Überprüfung der Integrierbarkeit von UML 2.0 mit etablierten Modellierungssprachen zur Komponentenentwicklung, also z.B. mit MATLAB/Simulink oder ASCET. Zu berücksichtigen ist hierbei, dass in Architekturmodellen (Funktionsnetz-Architekturen und SW-Architekturen) Strukturinformation vorherrscht, wohingegen Verhaltensinformation lediglich rudimentär vorhanden ist. Diese Einschränkung sollte die Integration erheblich erleichtern.
6 Zusammenfassung Dieses Positionspapier motiviert den Einsatz der UML 2.0 zur Architekturmodellierung bei der Bordnetzentwicklung der Automobilindustrie. Hierzu wird ein Handlungsbedarf formuliert: Die Integrierbarkeit von UML 2.0Architekturmodellen (konkret: Funktionsnetz-Architektur- und SW-Architekturmodelle) mit Komponentenmodellen, die unter Verwendung domänenspezifischer Modellierungswerkzeuge wie MATLAB/Simulink und ASCET erstellt worden sind, muss überprüft werden.
6
Einsatz von Modell-basierten Entwicklungstechniken in sicherheitsrelevanten Anwendungen: Herausforderungen und Lösungsansätze1 Mirko Conrad, Heiko Dörr DaimlerChrysler AG Research E/E and Information Technology Alt-Moabit 96A 10559 Berlin [email protected][email protected] daimlerchrysler.com
Abstract: Modell-basierte Entwicklungstechniken werden zunehmend auch in sicherheitsrelevanten Anwendungen eingesetzt. In derartigen Anwendungsszenarien müssen die Anforderungen von Normen und Standards aus dem Sicherheitsbereich adaptiert und auf die Modell-basierte Entwicklung abgebildet werden. Der vorliegende Beitrag diskutiert dabei auftretende Herausforderungen und zeigt Lösungsmöglichkeiten auf. Der Schwerpunkt liegt hierbei auf fehlervermeidenden Maßnahmen.
1 Motivation und Einleitung Die Modell-basierte Entwicklung hat sich in wichtigen automotiven Anwendungsbereichen als Standardparagdigma für die SteuergeräteSoftwareentwicklung etabliert [CFG+05]. In der Modell-basierten Entwicklung werden Modellierungs- und Simulationsumgebungen (Modeling Packages) wie MATLAB/ Simulink/Stateflow und darauf basierende Codegeneratoren wie der RealTimeWorkshop/Embedded Coder oder TargetLink für die Entwicklungsphasen Detailed Design und Coding verwendet. Anwender berichten übereinstimmend von erreichbaren Effizienzsteigerungen zwischen 20 und 50% durch den Übergang zu Modell-basierter Entwicklung mit Codegenerierung. Darüber hinaus wird ein schnellerer Anstieg des Reifegrads der entwickelten Funktionen erreicht. Von diesen Vorteilen soll zukünftig auch im Bereich sicherheitsrelevanter Anwendungen profitiert werden können. In derartigen Anwendungsszenarien müssen jedoch zusätzliche Anforderungen von Normen und Standards aus dem Sicherheitsbereich adaptiert und - da die zumeist aus der Zeit vor Einführung der
1 Die zugrunde liegenden Arbeiten wurden z.T. im Rahmen des BMBF Vorhabens IMMOS (01ISC31D) durchgeführt, siehe www.immos-project.de
7
Modell-basierten Entwicklung stammen - auf die Modell-basierte Entwicklung abgebildet werden. Der vorliegende Beitrag diskutiert dabei - aufbauend auf [DC05] - auftretende Herausforderungen und zeigt Lösungsmöglichkeiten, die auf konkreten Projekterfahrungen basieren, auf. Kapitel 2 listet relevante Standards und Richtlinien auf. Kapitel 3 beschreibt einige der existierenden Herausforderungen und zeigt Lösungsmöglich-keiten auf. Kapitel 4 fasst den Beitrag zusammen.
2 Normen, Standards und Guidelines Als Informationsquellen für den Einsatz Modell-basierter Entwicklungstechniken in sicherheitsrelevanten Anwendungen können u.a. die nachfolgend aufgelisteten Normen, Standards und Guidelines dienen: 2.1 ISO TR 15497:2000 Road vehicles - Development guidelines for vehicle based software Die Mitte der 1990er Jahre von der MISRA2 erarbeiteten und dann in einen Technical Report der ISO überführten Development Guidelines for Vehicle Based Software stellen einen der ersten Standardisierungsversuche in Bezug auf die Softwareentwicklung im Automobilbereich dar. Eine Überarbeitung und Aktualisierung ist für die Zeit nach Abschluss der Arbeiten an der ISO 26262 angedacht. 2.2 MISRA-C:2004 Guidelines for the use of the C language in critical systems Die ebenfalls von der MISRA erarbeiteten Guidelines for the use of the C language in critical systems beschreiben ein Subset der Programmiersprache C, dass für den Einstz in sicherheitskritischen Anwendungen geeignet ist 2.3 IEC61508:1998 Functional safety of electrical/electronic/programmable electronic safety-related systems Die IEC 61508 ist eine anwendungsbereichsunabhängige (generische) Grundnorm für elektrische/elektronische/programmierbare elektronische Sicherheitssysteme (E/E/PES), die die Entwicklung sektorspezifischer Normen für E/E/PES erleichtern soll und übergangsweise bei der Entwicklung von E/E/PES in den Bereichen Anwendung finden, in denen es noch keine domainspezifische Norm gibt. Teil 3 der Norm beschäftigt sich mit Anforderungen an die Softwareentwicklung.
2
8
The Motor Industry Software Reliability Association
2.4 ISO/WD 26262:2005 Road vehicles - Functional safety Im Rahmen des FAKRA3 AK 16 Funktionssicherheit wurde der Entwurf einer sektorspezifischen Ausprägung der IEC61508 für den Automobilbereich erarbeitet ('Automotive 61508'). Diese wurde Anfang November 2005 als Working Draft an die ISO mit dem Ziel der Standardisierung übergeben. ISO/WD 26262 enthält u.a. Teile zur Softwareentwicklung sowie zu übergreifenden Aktivitäten wie der Zertifizierung von Entwicklungswerkzeugen. 2.5 RTCA DO-178B/ED-12B Software Considerations in Airborne Systems and Equipment Certification Die RTCA DO-178B bzw. ihr europäisches Gegenstück EUROCAE ED-12B definieren Richtlinien für die Entwicklung von Luftfahrt-Software. Die DO-178B hat sich seit ihrem Erscheinen zu einem De-facto-Standard für die Zertifizierung neuer LuftfahrtSoftware entwickelt. Im Rahmen der SC-205/WG-71 wird derzeit ein Nachfolgestandard DO 178-C erarbeitet, der im Dezember 2008 fertig gestellt werden soll. Ein Themenfeld im Rahmen der Überarbeitung stellt die Berücksichtigung der Modell-basierten Entwicklung dar.
3 Herausforderungen und Lösungsszenarien 3.1 Sprachbeschreibung der Modellierungssprache Eine Grundvoraussetzung für den Einsatz einer Sprache im Rahmen sicherheitsrelevanter Projekte sollte eine allgemeine Sprachdefinition hinsichtlich Syntax und Semantik sein. Während es für prozedurale Programmiersprachen wie C allgemein zugängliche Sprachstandards gibt (vgl. ISO/IEC 9899:1999), ist dies für die häufig verwendete Modellierungssprache Simulink/Stateflow nur in Ansätzen der Fall. Syntax und Semantik der Modellierungssprache SL/SF sind in den Handbüchern zur Modellierungs- und Simulationsumgebung zwar umfänglich beschrieben, der Sprachbeschreibung fehlt es jedoch an Rigorosität. Die Semantik von Bussen und ähnlichen Konstrukten ist komplex und könnte besser dokumentiert sein. Zudem bleibt unklar, ob die Auflistung der Sprachelemente vollständig ist. Hinweise auf mehrdeutige oder fehleranfällige Sprachmittel muss sich der Nutzer anderweitig verschaffen. Nachteilig wirkt sich darüber hinaus aus, dass die Semantik einiger Sprachbestandteile über die verschiedenen Versionen von ML/SL/SF hinweg Modifikationen erfahren hat.
3
Fachauschuß Kraftfahrzeuge
9
Die Semantik ist teilweise layoutabhängig. Semantikbeschreibungen tragen häufig exemplarischen Charakter. In der Sekundärliteratur finden sich einige Aufsätze, die sich ausführlicher mit der Semantik von Simulink und Stateflow befassen [ASK04, CCM+03, SSC+04,]. Da eine einfach zu handhabende Semantik für die Gesamtsprache, insbesondere für ihren Zustandsautomatenanteil Stateflow, nicht zu erwarten ist, erscheint ein mehrstufiges, pragmatisches Vorgehen ratsam. In einer ersten Stufe sollte zunächst eine vollständige Liste aller Simulink-Basisblöcke, Stateflow-Konstrukte und Verbindungselemente mit ihrer syntaktischen Varianz (z.B. Blockparameter) erstellt werden, die dann nachfolgend bezüglich ihrer Semantik beschreiben werden.
IDxxx
Relational Operator
Icon: Inputs:
1) u1: any 2) u2: any
Outputs:
1) y: any
Init code: Run code: y = (u1 relop u2); relop  {, ~=, =, >, < ~= 2) Require all inputs to have same data type: Y N 3) Output data type mode: Boolean Logical Specify via dialog 4) …
Abbildung 1: Exemplarische Dokumentation von Simulink-Basisblöcken
Eine pragmatische Beschreibung der Simulink-Basisblöcke könnte bspw. auf der von der MSR-MEGMA [MSR02] verwendeten Art und Weise basieren (siehe Abb. 1). Die Vielzahl der Blockparameter und ihre Kombination erschwert allerdings die Semantikbeschreibung, die zudem von Gesamtmodell- und Simulationseigenschaften abhängen kann.
10
Die vollständige Auflistung der syntaktischen Sprachelemente würde die Entwicklung von Prüf- und Unterstützungswerkzeugen erleichtern. Hilfreich wäre zudem die Bereitstellung der Grammatik für die .mdl-Files. In einer weiteren Ausbaustufe wäre das Zusammenwirken der einzelnen Sprachelemente bei der Kombination zu Modellen und deren Ausführung zu beschreiben. 3.2 Sicheres Sprachsubset / Modellierungsrichtlinien Bei der Modellierung funktionssicherer Anwendungen sind im Vergleich zu unkritischen Funktionsanteilen zusätzliche Randbedingungen zu beachten. Diese müssen für den Entwickler in geeigneter Form verfügbar gemacht werden. Nicht alle in der Modellierungssprache enthaltenen Konstrukte sind auch für sicherheitsrelevante Anwendungen sinnvoll. Auf Basis der vollständigen Beschreibung der verwendeten Modellierungssprache (vgl. 3.1) ist zunächst eine für sicherheitsrelevante Anwendungen geeignete Sprachteilmenge abzuleiten. Ziel eines solchen Safe Modeling Language Subsets ist es, in sicherheitsrelevanten Anwendungen zum einen Sprachfeatures zu vermeiden, ‰ die nicht vollständig definiert sind, mehrdeutig oder layoutabhängig sind bzw. die zu Missverständnissen beim Benutzer führen können, ‰ die von verschiedenen Codegeneratoren in unterschiedlicher Weise umgesetzt werden können, ‰ die von verschiedenen Modellierungs- und Simulationswerkzeugen bei vergleichbarer Syntax unterschiedliche Semantiken haben und zum anderen Workarounds bereitzustellen, um bekannte Probleme im verwendeten Modellierungs- und Simulationswerkzeug zu umgehen. Das sichere Sprachsubset kann zunächst über eine Beschränkung der für sicherheitsrelevante Anwendungen erlaubten Modellelemente erreicht werden. Dies wird in praxi typischerweise über Positivlisten erlaubter Blöcke erreicht, die in eigenen Blockbibliotheken zusammengefasst werden. Darauf aufbauend können den Regeln formuliert werden, die zu unerlaubte Kombinationen und Einstellungen von Sprachelementen betreffen (Safety Rules). Die in Abb. 2 (oben) gezeigte Regel beschränkt das zulässige Blockset für FixedpointModelle, die als Ausgangspunkt für die Codegenerierung sicherheitskritischer Software dienen, auf Multiplikationsblöcke mit zwei 2 Operanden. Abb. 2 (unten) zeigt eine Safety-Rule für die Modellierung, die durch Übertragung einer ähnlichen Regel aus dem MISRA-C Sprachstandard entstanden ist. Hierbei sollen unerwartete Programmergebnisse als Folge von Vergleichen von FloatingpointVariablen auf exakte Gleichheit vermieden werden.
11
Ö TC_0623 TL: Vermeidung von Mehrfachmultiplikationen Category: … Readabilty
… Workflow
… V&V
; Code Gen.
; Safety
Automation: possible Description: Bei Fixed Point-Modellen sollten bei ‚Product‘ nie mehr als zwei Signale miteinander verknüpft werden.
Ö MC_002: Absence of equality / inequality tests in floating-point expressions Category: … Readabilty
… Workflow
… V&V
… Code Gen.
; Safety
Automation: possible Description: Floating-point expressions shall not be tested for equality or inequality. The inherent nature of floating-point types is such that comparisons of equality will often not evaluate to true even when they are expected to.
Fig 1-1: Comparison of floating point expressions for equality in Simulink
Abbildung 2: Definition eines Safe Modeling Language Subsets mit Hilfe von Modellierungsregeln
In Analogie zu einer geeigneten Teilmenge der Modellierungssprache für sicherheitskritische Anwendungen kann eine ähnliche Beschränkung auf der Ebene des daraus erzeugten Codes vorgenommen werden. Ziele der Definition eines Safe Implementation Language Subsets sind die Vermeidung von möglichen Problemen in der Implementierungssprache, z.B ‰ von C Features, die nicht vollständig definiert oder mehrdeutig sind, bzw. das Potential für Missverständnisse beim Anwender bieten, ‰ von C Features, die durch verschiedene Compiler unterschiedlich gehandhabt werden können sowie die Bereitstellung von Workarounds für bekannte Compilerprobleme. Die genaue Definition einer sicheren C Sprachteilmenge ist davon abhängig, ob der C Code manuell oder automatisch erzeugt wird. Aus diesem Grunde wird zurzeit neben den weithin anerkannten MISRA-C Rules [MISRA04] im Rahmen des MISRA Autocode-Forums an einem Sprachsubset für Autocode gearbeitet.
12
Da derzeit die Erfahrungen mit Sprachbeschränkungen auf Implementierungsebene noch überwiegen, wird aktuell die Konformanz mit den Beschränkungen zumeist auf der Ebene des C Codes überprüft. Bei Nichteinhaltung der Regeln gibt es teilweise lange Rückkopplungschleifen, um die Ursachen für die Verstöße zu identifizieren und abzustellen. Daher besteht mittelfristig das Ziel, die Prüfungen weitestgehend auf Modellebene vorzunehmen. Aufgabe der Codegeneratoren wäre es dann zu gewährleisten, dass 'sichere' SL Modelle in 'sicheren' C Code zu übersetzt werden (Abb. 3).
'safe' SL/SF subset 'safe' (autocode) C subset pattern, style guides SL/SF
autocode
Abbildung 3: Zusammenhang zwischen 'sicheren' Sprachteilmengen auf Modell- und Codeebene
3.3 Safety Pattern Bewährte Methoden und Maßnahmen, die im Rahmen der klassischen Programmierung zur Gewährleistung der Sicherheit eingesetzt werden, können auf die Modellebene übertragen und in Form so genannter Safety-Pattern für die Modellierung in standardisierter Form eingesetzt werden. Erfahrungswissen in Form erprobter Modellkonstrukte kann ebenfalls in Pattern-Form aufbereitet werden. Negativ-Pattern können ungeeignete Modellkonstrukte darstellen. Auf diese Weise können in den einzelnen Organisationen vorhandene Richtliniensammlungen um spezielle Safety Pattern erweitert werden. Von zentraler Bedeutung hierbei ist, dass Nutzen und Anwendungsbereich fallweise erläutert werden. Im Rahmen der Modell-basierten Entwicklung kann eine höhere Fehlertoleranz dadurch erreicht werden, dass der abzusichernde Teil des Nutzalgorithmus einmal mit Floatingpoint-Arithmetik und einmal in Fixpoint-Arithmetik ausgeführt wird. Bei geeigneter Konfiguration des Codegenerators können so unterschiedliche C-Code Fragmente erzeugt werden, die mit den gleichen Eingabewerten zum einen auf einer Floatingpoint-ALU und zum anderen auf einer Fixedpoint-ALU ausgeführt werden. Über einen geeigneten Komparator werden die Ergebnisse der beiden Berechnungen dann miteinander verglichen. Das in Abb. 4 dargestellte Safety-Pattern verdeutlicht das Prinzip.
13
{new}
Abbildung 4: Safety-Pattern zur Erhöhung der Fehlertoleranz Die Anwendung von Safety- und sonstigen Modellierungspattern führt zu einer weiteren Beschränkung der Modellierungssprache (vgl. Abb. 3) Der Einsatz von Modellierungsrichtlinien und Safety Pattern sollte nach Möglichkeit werkzeugunterstützt werden. Notwendig sind zum einen eine Infrastruktur für anwenderfreundliche Aufbereitung solcher Guidelines mit Suchmöglichkeiten und zum anderen Guideline-Checker zur weitgehend automatischen Überprüfung der Guidelines. Für den ersten Teil liegen positive Erfahrungen mit web-basierten Frontends für Verwaltung von und Zugriff auf Guidelinesammlungen vor. Exemplarisch sei hier die eGuidelines4 Infrastruktur [CFP05] genannt. Die Einhaltung von Guidelines kann mit Werkzeugen wie MINT5 oder dem ModelAdvisor6 teilautomatisiert werden. Wünschenswert wären eine Verknüpfung von Guidelinedatenbasen und entsprechenden Guideline-Checkern sowie abstrakte Sprachen zur Beschreibung der abzuprüfenden Regeln.
4 5 6
14
www.e-guidelines.org www.ricardo.com www.mathworks.com
Forschungsgegenstand sind komplexere Modellanalysatoren und –transformatoren, die z.B. in Modellen automatisch Bad Smells oder mögliche Anwendungskontexte für Positiv-Pattern identifizieren und dann regelbasierte Modelltransformationen interaktiv ermöglichen. Auf diese Weise könnten auch moderne Programmieransätze wie die aspektorientierte Programmierung auf Modellebene verankert werden. Als Beispiel kann das oben aufgeführte Safety-Pattern dienen, bei dem die zusätzliche Funktionalität weitgehend additiv zu einem vorhandenen Modell hinzugefügt werden kann. 3.4 Nachweis der standardkonformen Entwicklung Standards wie IEC61508 und ISO/WD 26262 schlagen für die einzelnen SicherheitsIntegritätslevel Techniken und Maßnahmen vor, die in den einzelnen Entwicklungsphasen zum Einsatz kommen sollen. Im Rahmen eines konkreten Projektes ist dabei zu dokumentieren, welche Maßnahmen wie umgesetzt wurden bzw. welche Ersatzmaßnahmen zur Anwendung kamen. Table A.4: Software design and development: detailed design Technique / Measure
SIL1
SIL2
SIL3
SIL4
Comment
Semi-formal methods
R
HR
HR
HR
SL/SF relies on a semi-formal notation for the detailed design of software modules TL relies on a semi-formal notation for the detailed design of software modules
Formal methods
---
R
R
HR
Defensive programming
---
R
HR
HR
Defensive programming is facilitated by modeling guidelines and modeling language subset
Modular approach
HR
HR
HR
HR
SL supports hierarchical decomposition TL supports hierarchical decomposition SL (R14 and higher) allows modularization of models on file level TL allows modularization of code on file level RTW/EC allows modularization of code on file level
Design and coding standards
R
HR
HR
HR
Design (i.e. modeling) standards can be enforced by model reviews Design (i.e. modeling) standards can be partially enforced by MINT Design (i.e. modeling) standards can be partially enforced by SL/SF model advisor (R14 and higher) Coding standards are obeyed at the level of the generated C code.
…
…
Abbildung 5: Umsetzung der Methoden und Maßnahmen der IEC61508 im Rahmen der Modellbasierten Entwicklung
15
Der hierfür projektspezifisch anfallende Aufwand kann wirkungsvoll reduziert werden, wenn entsprechende generische Dokumente (Templates) für typische Modell-basierte Entwicklungsprojekte mit der in der Organisation verwendeten Toolkette bereitgestellt werden, die dann projektspezifisch instantiiert werden. Abb. 5 zeigt einen exemplarischen Ausschnitt einer kommentierten IEC61508 Maßnahmen-Tabelle, die in einer separaten Spalte generische Anmerkungen zur Umsetzung im Rahmen Modell-basierter Entwicklungsprojekte enthält. Eine analoge Vorgehensweise ist auch im Rahmen des kommenden ISO/WD 26262 möglich.
4 Zusammenfassung Der Beitrag hat skizziert, welche aufeinander abgestimmten Maßnahmen zum abgesicherten Einsatz modell-basierter Techniken für sicherheitsrelevante automobile Anwendungen erforderlich sind. Erschwert durch den Einsatz nicht formal spezifizierter Modellierungssprachen wie Simulink / Stateflow müssen eine Reihe von informellen Ansätzen, wie etwa die Definition einer sicheren Teilmenge der Modellierungssprache oder Safety Pattern, mit einander kombiniert werden. Die dazu erforderliche Werkzeugunterstützung liegt in Teilen vor. Insbesondere die Nutzung von Techniken der Modelltransformation wird den Grad der Absicherung der Einhaltung der Regeln jedoch noch deutlich erhöhen und die notwendigen Nachweise beschleunigen. Unter Einsatz der genannten Maßnahmen und Techniken kann dann die Konformität mit Sicherheitstandards belegt werden.
Literaturverzeichnis [ASK04]
A. Agrawal, G. Simon, G. Karsai: Semantic Translation of Simulink/Stateflow Models to Hybrid Automata Using Graph Transformations. ENTCS 109 (2004): 4356 [CCM+03] P. Caspi, A. Curic, A. Maignan, C. Sofronis, S. Tripakis: Translating Discrete-Time Simulink to Lustre. LNCS 2855 (2003): 84-99 [CFG+05] M. Conrad, I. Fey, M. Grochtmann, T. Klein: Modellbasierte Entwicklung eingebetteter Fahrzeugsoftware bei DaimlerChrysler. Informatik Forsch. Entw. (2005) 20:3-10 [CFP05] M. Conrad, I. Fey, H. Pohlheim: eGuidelines – A Tool for Managing Modeling Guidelines. International Automotive Conference, Detroit (US), Jun. 2005 [DC05] H. Dörr, M. Conrad : Modellbasierte Entwicklung sicherheitsrelevanter eingebetteter Systeme. Eingeladener Vortrag, MBEES'05, Dagstuhl, Jan. 2005 [MISRA04] MISRA-C:2004 Guidelines for the Use of the C Language in Critical Systems. Oct. 2004 [MSR02] MSR Working group MEGMA: Standardization of library blocks for graphical model exchange. 2001
16
[SSC+04]
N. Scaife, C. Sofronis, P. Caspi, S. Tripakis, F. Maraninchi: Formal languages: Defining and translating a 'safe' subset of simulink/stateflow into lustre. Proc. 4. ACM Int. Conf. on Embedded Software, Sept. 2004
17
18
Petri Net Model Synthesis from Scenarios Jörg Desel Lehrstuhl für Angewandte Informatik Katholische Universität Eichstätt-Ingolstadt 85071 Eichstätt [email protected]
Abstract: This paper argues that the development of embedded system can be based on model synthesis from a formal specification of desired scenarios. This claim is substantiated by experiences of the author with an automotive project. In this project, a specific class of Petri nets was applied, which is shortly introduced in the paper. After motivating that model synthesis in the Petri net setting is of practical importance, we sketch the state-of-the-art in this area and our current approach.
1 Introduction Model based software engineering often starts its considerations with a given model which is assumed to specify the behavior of the system to be developed correctly and completely. This holds in particular for embedded systems, where the problem is originally formulated by engineers, whereas in information systems there exists much more experience in conceptual modeling on different levels, taking different abstraction levels, different aspects, different views, and in particular different modeling experience of the modelers into account. One of the main reasons for this difference is that the domain experts in embedded systems are typically engineers whereas the domain experts in information systems have various backgrounds, but in most cases are not very familiar with engineering or informatics. Therefore, model based software engineering for embedded system has to consider a completely different starting point than model based software engineering in other areas. In a software engineering project with the automotive vendor Audi AG the given starting point was a formulation of scenarios on a quite detailed level. In other words, there was neither a formal nor an informal specification of the software to be constructed but rather sequences of steps to be performed in different cases. Very formal definitions of interfaces to other components were provided. Finally, some liveness and safety properties were given. These properties did obviously “hold for the given scenarios”.
19
So the aim in this kind of projects is not to construct algorithms from a given interface specification and given behavioral specifications but rather to synthesize an algorithm from the desired behavior (which had to be formalized first) and to prove the behavioral specification for this algorithm. It is important to notice that the desired behavior, given by scenarios, is not formulated on the level of an algorithm but rather on the level of desired runs in a given environment of the algorithm to be constructed. Hence we have the following steps: 1.
Construct a model of the environment or of the interface to the environment (in our case, this model is formulated in terms of a class of modular Petri nets).
2.
Formalize the scenarios (in our case, a partial order of events is obtained from each scenario, partially equipped with timing information).
3.
Synthesize a model of the algorithm from the formalized scenarios (in our case, this model is also formulated in terms of a class of modular Petri nets).
4.
Formalize the desired properties of the algorithm (e.g. in temporal logics).
5.
Prove that the composed models from Step 1 and Step 3 satisfy the properties formalized in Step 4.
6.
Translate the model from Step 3 in software modules .
We concentrate in this contribution on Step 3, which turns out to be the most difficult one. In the automotive project mentioned before, the synthesis was done manually and the system model was validated by deriving the desired runs (and no undesired ones). In the following section, we provide a sketch of the tasks in the above mentioned automotive project. The class of Petri nets applied is shortly introduced and some of the models from the project are shown. The third section is devoted to the state-of-the-art in synthesis of Petri net models from given scenarios. It will turn out that this problem heavily depends on parameters such as knowledge of names of events, names of local states, number of scenarios, form of scenarios etc. Although these parameters are very important for the construction of algorithms, they seem to have no really relevant counterparts in the application world. On the other hand, problems like incompleteness or vagueness of the scenario specification, which turns out to be frequent phenomena in applications, cannot be handled by theory yet. Finally, in the fourth section we discuss requirements for a more general and more applicable synthesis procedure. Moreover, we present our approach, which can be termed semi-automatic synthesis and which combines automatic synthesis and validation steps.
20
2 Models in an automotive project This section gives a very rough sketch of a project we conducted together with engineers from the automobile vendor Audi AG in Ingolstadt. We also show some of the models that were developped in this project. These models are given as Petri nets with signal arcs, a language developed within the project SPECIMEN1 (see [DHJ+04]). For details, see [DJL+03] and [DMN04]. The language we use is a class of modular high-level Petri nets, where the domain of (some) places is the set of real numbers. These places represent e.g. sensor values. They are represented by double circles. Modules are composed by means of two special arcs; event arcs and read arcs. An event arc connects two transitions and has the following semantics: the second transition fires if and only if it is enabled in its module and the first transition fires. In other words, either the first transition fires alone (if the second transition is not enabled), or both transitions fire together in one step. Event arcs are denoted by zigzag arcs. Arcs with two arrowheads represent read arcs. A transition with an attached read arc can only fire if the corresponding place carries a token. The marking of that place is not changed in case of low-level places. It can be overwritten in case of high-level places, where two variables at the arc denote the old and the new value, respectively. Finally, there are time annotations at some arcs which denote that the corresponding transition will fire after it was enabled for the time period indicated by the annotation. 2
sensor ok 1 x
xa,xn
13
10
sensor broken
14
11
x,max x,0
SudxdSo
x>So
x,max
sensor value
x
ADC: too small
x
SudxdSo
x>So
x
15
sensor shorted
3
x 9m30s
> 1494864
> 701120
> 8m12
118690
174871
45ms
155166
263368
1m21s
< 1s
Figure 7: Verification times and state spaces for different verification configurations.
A second conservative abstraction used consists in replacing the deterministic polling cycle of the ControllerMonitor (10ms in the initial model) by a completely non-deterministic polling policy. While this introduces new executions, impossible in the initial model, the resulting state space is smaller as many previously disjoint states are grouped together10 . The table in Figure 7 below shows the size of the state space and the processing time for several configurations of the MARS system which allows to draw some conclusions on the efficiency of the use of compositional models and in particular compositional abstractions. In particular, desynchronizing two resources has a tremendous effect on the size of the state space which is in fact due to the simultaneous presence of jitter and desynchronization. Notice that the effect is much more important than it looks like as we have stopped the exploration when, after reaching 1 mio states and 10 minutes, the state space was still growing rapidly — experience told us that it was likely not to be worth to wait until reaching 10 mio states; even if it would converge by then, what we didn’t anticipate really, the result was not very useful for us, as we wanted to be able to rerun experiences on variants in short time. As we have not run our experiences on particularly well equipped machine (especially in memory), this means that we can still gain a few orders of magnitude and handle slightly more complex systems. The use of both types of conservative abstractions leads to a state space of about the same size as the much simpler system with synchronized sources, which is still precise enough to satisfy all properties.
4
Conclusion
By using a case study as support, we have shown both, the convenience of the OMEGA UML profile for the expression of timed models and timed properties and the usefulness of the IF front-end for UML which allows for both flexible interactive simulation and complete state space exploration for debugging and verification of UML models. We believe that the experiment presented shows that timing analysis tools can be used efficiently for solving isolated, hard timing problems in a UML design, even if fully automated verification for large designs remains a remote goal. Also we believe that more systematic use of functional decomposition as used in the example, can definitively help to make possible the verification of much larger designs in a compositional fashion, as there is no need for the verification of a model in which all parts are described in all details. 10 but
82
only if a symbolic representation of time constraints is used
The use of the OMEGA UML profile to capture timing properties has favored a very quick learning and adoption of our tools by experienced UML designers. Without the knowledge of a verification expert, the designers were able to use even advanced techniques like abstractions. The relaxation of timing constraints — such as the abstraction from the polling period in the example — shows to be a very efficient abstraction technique in such models, and it is usually very simple to model. This kind of abstractions is always conservative for the satisfaction of (timed) safety properties. On the other hand, can introduce spurious error traces. However, in the MARS example this has never occurred, showing first, that with some exercise, a designer can learn to use abstractions which do not break the verified properties. And second, that the designers tend in the first place to build over constrained models. The reason is probably that they are strongly influenced by the requirement that programs must be deterministic, and they apply this also to specifications even if this is not needed for satisfying the requirements. We have also found out during the experiments that some methodological guidelines for writing observers and for using the IFx toolbox are necessary during the learning process. A set of guidelines has been developed as a side result of this teamwork (see also [OGL05]).
References [BGM02]
Marius Bozga, Susanne Graf, and L. Mounier. IF-2.0: A Validation Environment for Component-Based Real-Time Systems. In Proceedings of Conference on Computer Aided Verification, CAV’02, Copenhagen, number 2404 in LNCS. Springer Verlag, June 2002.
[BGO+ 04] Marius Bozga, Susanne Graf, Ileana Ober, Iulian Ober, and Joseph Sifakis. The IF toolset. In SFM-04:RT 4th Int. School on Formal Methods for the Design of Computer, Communication and Software Systems: Real Time, number 3185 in LNCS, June 2004. [BS97]
S. Bornot and J. Sifakis. Relating Time Progress and Deadlines in Hybrid Systems. In International Workshop, HART’97, Grenoble, LNCS 1201, pages 286–300. Spinger Verlag, March 1997.
[CHR92]
Zhou Chaochen, C.A.R. Hoare, and A.P. Ravn. A Calculus of Durations. Information Processing Letters, 40(5):269–276, 1992.
[DJPV03] Werner Damm, Bernhard Josko, Amir Pnueli, and Angelika Votintseva. Understanding UML: A Formal Semantics of Concurrency and Communication in Real-Time UML. In Frank de Boer, Marcello Bonsangue, Susanne Graf, and Willem-Paul de Roever, editors, Proceedings of the 1st Symposium on Formal Methods for Components and Objects (FMCO 2002), volume 2852 of LNCS Tutorials, pages 70–98, 2003. [DJPV05] Werner Damm, Bernhard Josko, Amir Pnueli, and Angelika Votintseva. A discrete-time UML semantics for concurrency and communication in safety-critical applications. Science of Computer Programming, 2005. (to appear). [GOO05]
Susanne Graf, Ileana Ober, and Iulian Ober. Timed annotations in UML. STTT, Int. Journal on Software Tools for Technology Transfer, 2005. under press.
[OGL05]
Iulian Ober, Susanne Graf, and David Lessens. A case study in UML model-based dynamic validation: the Ariane-5 launcher software. submitted, 2005.
[OGO05]
Iulian Ober, Susanne Graf, and Ileana Ober. Validating timed UML models by simulation and verification. STTT, Int. Journal on Software Tools for Technology Transfer, 2004, 2005. Under press.
[OMG02]
OMG. Response to the OMG RFP For Schedulability, Performance and Time, v. 2.0. OMG document ad/2002-03-04, March 2002.
83
84
Zur Kosteneffektivität des modellbasierten Testens Alexander Pretschner Informationssicherheit, ETH Zürich Abstract: Annahmen zum kosteneffektiven Einsatz des modellbasierten Testens werden aufgezählt. Existierende empirische Evidenz für das Zutreffen dieser Annahmen wird genannt und die Notwendigkeit weiterer empirischer Studien betont.
1 Einleitung Testen umfasst eine Menge von Aktivitäten, die Differenzen zwischen Ist- und Sollverhalten eines Systems aufdecken oder das Vertrauen in die Abwesenheit solcher Differenzen erhöhen sollen. Das Verständnis von Spezifikationsdokumenten, gewissermaßen ein mentales Modell des zu testenden Systems (system under test, SUT) und seiner Umwelt, erlaubt einem Testingenieur die Definition von Testfällen (im folgenden kurz „Tests“): Ein- und erwartete Ausgaben, die mit den tatsächlichen Ausgaben des SUT verglichen werden. Der Aufwand des Testens wird übereinstimmend mit 50±20% der gesamten Entwicklungskosten angegeben, wobei diese Zahlen bisweilen die Identifikation des Problems (in Code oder Spezifikation) und auch das Debugging beinhalten [14]. Kernidee des modellbasierten Testens (MBT) ist, das mentale Modell durch explizite Verhaltensmodelle von SUT bzw. dessen Umgebung zu ersetzen und so insbesondere den Prozess der Definition von Tests explizit, nachvollziehbar, reproduzierbar und letztlich unabhängig von den speziellen Fähigkeiten eines einzelnen Testingenieurs zu gestalten. Das Verhalten des Modells des SUT wird als Sollverhalten für das SUT interpretiert, geeignet auszuwählende Abläufe des Modells des SUT dementsprechend als Tests. Wenn das Modell des SUT nicht genügend Informationen über die erwarteten Ausgaben codiert und dementsprechend hauptsächlich ein Umgebungsmodell vorliegt, kann daraus nur der Eingabeteil der Testfälle abgeleitet werden, und die erwarteten Ausgaben müssen vom Tester zur Verfügung gestellt werden. Kern dieses Aufsatzes ist die explizite Benennung von Annahmen über den kosteneffektiven Einsatz des MBT, die häufig implizit getroffen werden. Angesichts ganz erstaunlicher Fortschritte in technologischer Hinsicht wird – hier bewusst nicht abschließend – analysiert, unter welchen Bedingungen MBT kosteneffektiv eingesetzt werden kann und unter welchen Bedingungen der Einsatz fragwürdig erscheint. Das übergeordnete langfristige Ziel ist dabei die Identifikation entsprechender organisatorischer und fachlicher Erfolgsfaktoren. Zweck dieses Aufsatzes ist das Schaffen einer Diskussionsgrundlage für den Workshop.
85
Beitrag. Dem Verfasser sind keine Arbeiten anderer Autoren zu prinzipiellen Überlegungen zum erfolgreichen Einsatz des modellbasierten Testens bekannt. Aufbauend auf früheren Papieren [22,27], reflektiert dieser Aufsatz die aktuellen Gedanken. Abgrenzung. In diesem Papier wird auf den Test von Funktionalität fokussiert; Usability- und Stresstests und die Eigenheiten des Testens objektorientierter Software werden nicht betrachtet. Struktur- oder Nutzungsfallmodelle zur automatisierten Generierung von Testinfrastruktur werden ebenfalls ignoriert. „Modelle“ bezeichnen Artefakte, die eine Vereinfachung des Verhaltens eines SUT oder seiner Umwelt darstellen und die (insbesondere) zum Zweck des Testens erstellt wurden [26]. Es wird angenommen, dass Modelle so präzise bzw. formal sind, dass daraus zumindest im Prinzip Tests automatisch erzeugt werden können. Von konkreten Modellierungstechniken und –sprachen wird abstrahiert, und die offenkundigen Zusammenhänge mit dem modellbasierten Test von Hardware bzw. Chipdesigns werden nicht diskutiert. Überblick. Abschnitt 2 präsentiert zentrale Ideen des MBT. Abschnitt 3 listet fundamentale Annahmen an den erfolgreichen Einsatz des MBT auf, die als Erfolgsfaktoren gelesen werden können. Sofern verfügbar, wird über publizierte Evidenz berichtet. Abschnitt 4 zieht Schlussfolgerungen und benennt attraktive Forschungsrichtungen.
2 Modellbasiertes Testen Testen beinhaltet drei einander ggf. überlappende Phasen: die Auswahl, Durchführung und Auswertung von Tests. Für die Auswahl von Tests werden Modelle von SUT, Modelle von dessen Umgebung und Modelle von Fehlern verwendet. Die Anzahl möglicher Tests ist üblicherweise unendlich oder zumindest sehr groß. Der ökonomische Standpunkt führt zum Wunsch nach einer möglichst kleinen Anzahl von zu erzeugenden, durchzuführenden und auszuwertenden Tests. Aus der Perspektive der Qualitätssicherung muss diese Anzahl jedoch ausreichend hoch sein, um die Anzahl verbleibender Fehler auf ein akzeptables Minimum zu reduzieren. Testfallableitung, ob automatisch oder manuell, muss also das Problem lösen, im folgenden Sinn gute Tests zu generieren: Ihre Erzeugung soll billig sein und ihre Auswertung ebenfalls, insbesondere in Bezug auf die Zuordnung von Fehlern (failures) zu Fehlerursachen (faults, errors). Außerdem sollen sie mindestens alle „schweren“ und „häufig“ auftretenden Fehler finden. Schließlich ist der Aufwand der Testdurchführung zu minimieren, was bei gemischten HW/SWSystemen nicht immer unproblematisch ist. Selektionskriterien. Zunächst unabhängig von der Verwendung expliziter Modelle wählen Tester als Annäherung an diese Ziele Tests anhand funktionaler, struktureller, fehlerbasierter und stochastischer Kriterien aus. Alle diese Kriterien können auch zur Bemessung einer Testsuite und als Testendekriterium verwendet werden [29]. Sie müssen vom Benutzer gefordert oder definiert werden: MBT basiert immer auf mindestens zwei vom Menschen gelieferten Eingaben, dem Modell und dem Selektionskriterium.
86
Strukturelle Kriterien fordern, dass während der Ausführung eines Programms oder Modells bestimmte Substrukturen von Datentypen, Kontroll- und Datenflussgraphen abgedeckt werden. Neben dem unklaren Zusammenhang von Abdeckung auf (SUT- und Umgebungs-) Modell und Code sind diese Kriterien in ihrer Fähigkeit, Fehler aufzuspüren, nicht unumstritten, auch im Vergleich mit randomisierten Tests (Referenzen in [24]). Ein großer Vorteil struktureller Kriterien liegt in ihrer Quantifizierbarkeit und darin, dass sie zumindest prinzipiell die vollautomatische Ableitung von Tests erlauben. Funktionale Kriterien zielen darauf ab, Funktionalitäten eines SUT zu isolieren und entsprechende Tests zu definieren. Das geschieht ad hoc, in Form von Szenarien oder Constraints über Abläufen. Wenn explizite Modelle der Umwelt des SUT oder von Anforderungen, auch in Form von Eigenschaften, vorliegen, können strukturelle Selektionskriterien auch auf diese Modelle angewendet werden. Unterstützung bei der Definition konkreter funktionaler Kriterien scheint in methodischer, aber nicht in technologischer Hinsicht möglich. Fehlerbasierte Kriterien verwenden empirisches Wissen um vermutete Fehler für die Selektion. Stochastische Kriterien schließlich basieren auf Wahrscheinlichkeitsverteilungen von Eingabedaten. Eine Gleichverteilung führt zu rein randomisierter Erzeugung des Eingabeteils von Tests, während die Verwendung von Nutzerprofilen [19] bzw. stochastischer Umweltmodelle [28] besonders attraktiv erscheint, weil sie unter bestimmten Bedingungen die Anzahl der verbleibenden, im Feld auftretenden Fehler minimiert Testfallgenerierung. Aus einem Modell und einem adäquat operationalisierten Selektionskriterium leitet ein menschlicher oder maschineller Testfallgenerator Abläufe des Modells ab. Wenn hierfür ausschließlich ein Umgebungsmodell verwendet wurde, müssen die erwarteten Ausgaben des SUT hinzugefügt werden Projektionen von Abläufen des Modells auf Ein- und Ausgabe sind dann Tests für das SUT. Automatisierte Testfallgenerierung basiert auf dedizierten Suchalgorithmen, symbolischer Ausführung, Model Checking, deduktivem Beweisen oder Erfüllbarkeitsüberprüfern für propositionale Logik. Abstraktion. In methodischer Hinsicht ergibt das MBT nur dann Sinn, wenn das Modell des SUT abstrakter als das SUT ist, also einen echten Informationsverlust beinhaltet [23]. Andernfalls würde der Aufwand, das Modell zu validieren, genau dem Validierungsaufwand für das SUT entsprechen (bisweilen wird argumentiert, dass der Abstraktionsunterschied nicht methodisch notwendig ist, weil allein die Redundanz von Modell und SUT zum Aufdecken von Problemen führt.) Das impliziert einerseits, dass nur das im Modell codierte Verhalten getestet werden kann und andererseits, dass die verschiedenen Abstraktionsniveaus überbrückt werden müssen (verschiedenen Abstraktionen im modellbasierten Testen sind an anderer Stelle beschrieben [21]): Der Eingabeteil des Tests wird konkretisiert, bevor er auf das SUT angewendet wird, und die Ausgabe des SUT wird abstrahiert, bevor sie mit der erwarteten Ausgabe des Tests, also des Modells, verglichen wird. Im Extremfall kann das Abstraktionsniveau so hoch sein, dass nur zwischen „Ausnahme geworfen“ und „keine Ausnahme geworfen“ oder „funktioniert“ und „funktioniert nicht“ (s. etwa eine Studie im Bereich des evolutionären Testens [7]) unterschieden wird. Konkretisierung und Abstraktion werden von dedizierten Adapterkomponenten implementiert.
87
Redundanz. Schließlich basiert Testen immer auf einer Form von Redundanz. Mit der Ausnahme von Stress- und Leistungstests ist es fragwürdig, ein einzelnes Modell für die Generierung von Produktionscode und Tests zu verwenden: Das SUT würde gewissermaßen gegen sich selbst getestet. Auf diese Art können allerdings Umweltannahmen und Codegeneratoren getestet werden. Verschiedene Szenarien des MBT, die die zeitliche Abfolge von Modell- und Systementwicklung berücksichtigen, werden an anderer Stelle diskutiert [23].
3 Annahmen und Evidenz Dieser Abschnitt, der Kern des vorliegenden Papiers, fasst die Annahmen für den erfolgreichen Einsatz des MBT zusammen. Die Diskussion ist dann aufgespalten in eine Diskussion über Annahmen, für die dem Verfasser keine explizite Evidenz bekannt ist und in die Annahmen, für die Evidenz publiziert ist. 3.1 Annahmen Häufig getroffene Annahmen über den kosteneffektiven Einsatz des MBT beziehen sich auf die im Folgenden aufgeführten Aspekte. Die Annahmen beziehen sich auf den Test von Funktionalität des SUT; modellbasierte Tests für Codegeneratoren, Compiler und Umweltannahmen werden dabei explizit aus der Diskussion ausgenommen. 1.
2.
3. 4.
88
Modelle, Anforderungen und Spezifikationen: Der Vorgang des Modellierens an sich hilft beim Verständnis und bei der präzisen Formulierung der Anforderungen (1a). Wenn ein Entwicklungsprozess auf sehr präzise Spezifikationen angewiesen ist, wie das etwa im Zusammenspiel von OEMs und Zulieferern im automobilen Bereich der Fall ist, dann sind Modelle als Spezifikationen ohnehin notwendig. Die Möglichkeiten des MBT führen dann zu einem zusätzlichen Wert des Modells (1b). Existenz adäquater Modelle: Es gibt ein Modell, bei dem der Tradeoff zwischen methodisch notwendiger Abstraktion und zum Testen erforderlicher Detaillierung gerechtfertigt werden kann (offenbar bezieht sich diese Annahme nur auf die Ausprägungen des MBT, bei denen das Ausgabeverhalten des SUT hinreichend detailliert codiert wird). Weil dieses Modell eine Vereinfachung darstellt, ist es leichter zu validieren als das entsprechende SUT. Effektivität: Modellbasiertes Testen findet (potentielle) Fehler im SUT. Relativer Aufwand und relative Qualität: Der Aufwand, Modelle und modellbasierte Testselektionskriterien zu erstellen, zu validieren und zu warten ist kleiner als der Aufwand, eine ohne Modelle erstellte Testsuite zu erstellen, zu validieren und zu warten. Das gilt insbesondere für Modifikationen des SUT etwa bei sich ändernden Anforderungen. Wenn der Aufwand nicht geringer ist, rechtfertigt doch zumindest die höhere „Qualität“ der Tests den erhöhten Ressourceneinsatz. Bisweilen wird angenommen, dass große Testsuiten gar nicht gewartet werden können, dass das für Modelle hingegen aber sehr wohl der Fall ist.
5.
6.
Wiederverwendung: Im Kontext von Produktlinien oder allgemein variantenreicher Systeme können Modelle, Testselektionskriterien und Adapterkomponenten leichter wiederverwendet werden als entsprechend manuell erstellte Testsuiten. Testanzahl: Wenn ein Modell einmal erstellt ist, können bei minimalem Aufwand beliebig viele (und im Fall reaktiver Systeme auch beliebig lange) Tests erzeugt werden. Eine größere Anzahl an Testfällen ist i.a. einer kleineren vorzuziehen.
3.2 Diskussion der Annahmen ohne dem Verfasser bekannte publizierte Evidenz Im nächsten Abschnitt 3.3 wird empirische Evidenz für die Annahmen (1), (3) und (4) angeführt. Im verbleibenden Teil dieses Abschnitts erfolgt zunächst eine kurze Diskussion der anderen Annahmen, für die dem Verfasser keine publizierte explizite Evidenz bekannt ist. In Bezug auf die Existenz adäquater Modelle (Annahme 2) ist festzuhalten, dass bei der Verwendung von Modellen zur automatischen Ableitung von sowohl Code als auch Testfällen stets ein fundamentaler Widerspruch zwischen den Vorteilen einer abstrakten Beschreibung und der notwendigen Detailliertheit der generierten Artefakte besteht. Abstraktion tritt in mindestens zwei Ausprägungen auf, nämlich in der Form der Kapselung und in der Form expliziten Informationsverlusts, von denen im MBT insbesondere die zweite starke Relevanz besitzt.
Abstraktion durch Kapselung wird etwa durch dedizierte Programmiersprachenkonstrukte (etwa Konditionale, Schleifen, Unterprogramme, Garbage Collectors), Middleware, Betriebssystemschichten und Bibliotheken erzielt. Die nicht explizit aufgeführte Information wird durch das Laufzeitsystem oder den Compiler eingefügt. Auch wenn die Flexibilität des Programmierers/Modellierers dadurch bewusst eingeschränkt wird, beinhaltet diese Form der Abstraktion keinen wirklichen Informationsverlust. Die Modellierung kontinuierlicher Systeme durch Matlab Simulink-Blockdiagramme etwa ist ein typisches Beispiel für Modellierung, die auf dieser Form der Abstraktion beruht. Bei der Abstraktion durch expliziten Informationsverlust hingegen kann fehlende Information nicht ohne weiteres durch einen Makroexpansionsmechanismus wiederhergestellt werden. Diese Form findet etwa dann statt, wenn Teile der Funktionalität, etwa bestimmte Spezialfälle, im Modell nicht berücksichtigt werden. Das Ignorieren von Zeitverhalten oder anderen QoS-Attributen ist eine andere weit verbreitete Abstraktion dieses Typs. Bei der Erzeugung von Produktionscode oder Testfällen muss die fehlende Information offenbar explizit hinzugefügt werden. In der Praxis des modellbasierten Testens findet man beide Formen, meist in Kombination. Details (nicht Präzision!) gehen nun überwiegend durch die zweite Form der Abstraktion verloren. Entscheidende Bedeutung kommt deshalb den die Abstraktionsunterschiede überbrückenden Adapterkomponenten zu; Schätzungen gehen von etwa 40% des Gesamtaufwands für deren Implementierung aus [27] (Teile der Adapterkomponenten – Testharnesses – sind allerdings auch bei nicht modellbasierten Testansätzen nötig). Es ist stets zu überprüfen, wie der Aufwand für diese Komponenten im Verhältnis zu den verminderten Aufwendungen bei der Validierung des Modells anstelle des Codes steht.
89
Zahlreiche proof-of-concept-Studien zum MBT (Annahme 3, s.u.) geben Anlass zu der Vermutung, dass adäquate Modelle stets gefunden werden können. Der zweite Teil der Annahme, der sich auf den verminderten Aufwand einfacherer Artefakte bezieht, erscheint intuitiv erfüllt. Die mögliche Wiederverwendung (Annahme 5) von Modellen und Testselektionskriterien, insb. Umweltmodellen, basiert auf der folgenden Idee. MBT erhöht den Abstraktionsgrad der Artefakte, mit denen der Tester hantiert: Anstelle von einzelnen Testfällen und Testsuiten wird mit Verhaltensmodellen und Testselektionskriterien operiert. Aus einem Testselektionskriterium werden möglicherweise automatisch ggf. viele Testfälle generiert. Die Idee ist nun, dass Änderungen auf einem höheren Abstraktionsniveau (Modell, Selektionskriterien) leichter durchzuführen und zu validieren sind als auf einem niedrigeren Niveau (Testfälle). Argumentiert wird üblicherweise über die „Lokalität“ der Änderung: Eine lokale, leicht durchzuführende Änderung auf Modellebene mit möglicherweise globalen Implikationen ist leichter zu validieren als die entsprechende globale Änderung auf Testsuiteebene. Das wird i.a. von der Art des Validierungsmechanismus abhängen.
Adapterkomponenten, die sowohl den Abgleich der Abstraktionsniveaus vornehmen als auch die Tests durchführen, sind ebenfalls Kandidaten für Wiederverwendung. Zur Anzahl von Testfällen (Annahme 6) schließlich ist festzuhalten, dass automatische Testfallgeneratoren i.a. natürlich beliebig viele Tests generieren können. Es besteht zunächst aber nicht unbedingt ein Zusammenhang zwischen der Güte einer Testsuite, im Sinn von Anzahl detektierter Fehler, und ihrer Größe. Im Bereich eingebetteter Systeme (etwa Chipkarten, Netzwerkcontroller) kann die Durchführung eines Tests aufgrund von Rüstzeiten etwa 15 Sekunden dauern, was die Maximalanzahl durchzuführender Tests beschränkt. Für Businessinformationssysteme gilt das i.a. natürlich nicht, was die Technologie u.a. für die Erzeugung von Regressionstests z.B. nach Refactorings interessant macht. Durchgeführte Tests müssen außerdem analysiert werden, und wenn aus einer riesigen Testsuite etwa die Hälfte aller Tests auf demselben Fehler basiert, wird die Analyse schnell sehr teuer; es kann dann sinnvoll sein, alle Tests erneut durchzuführen und somit die Anzahl detektierter Differenzen zwischen Soll- und Istverhalten massiv zu reduzieren.
3.3 Diskussion der Annahmen mit publizierter Evidenz Dass eine explizite Modellierung bei der präzisen Definition von Anforderungen und Systemen (Annahme 1a) hilfreich ist, ist weitgehend unumstritten. Existierende Evidenz wird hier bewusst nicht umfassend zitiert. Im Bereich des modellbasierten Testens sind als Evidenz insbesondere zwei Studien zu nennen [5,24]. Die erste beschreibt verschiedene Stadien des Modells eines Flugsteuerungssystems und zeigt, wie verschiedene QSTechniken (Reviews, Model Checking, Ableitung von Modelltraces zur manuellen Überprüfung) verschiedene Fehler im Modell aufdecken.
90
Die zweite zeigt am Beispiel eines Netzwerkcontrollers, wie viele Fehler durch die Modellierung aufgedeckt wurden und insbesondere auch, dass bestimmte Modellierungsfehler erst durch das Ausführen modellbasiert generierter Tests offenbar wurden. In der Praxis der Ausführung modellbasiert erstellter Tests zeigt sich, dass Fehler stets sowohl in der SUT als auch im Modell gefunden werden, was die Notwendigkeit der Redundanz unterstreicht (Abschnitt 2). Bezüglich der intuitiv einleuchtenden Annahme, dass Modelle neben ihrer Funktion als Spezifikation gewissermaßen als Nebeneffekt auch für die Generierung von Tests (Annahme 1b) verwendet können, sind dem Verfasser keine Dokumentationen bekannt. Ein Grund dafür könnte sein, dass die meisten Studien zum MBT auf Modellen basieren, die für bereits existierende SUTs erstellt wurden.
Die Effektivität des MBT (Annahme 3) in Bezug auf detektierte Fehler, zumeist ohne Berücksichtigung der Kosten und ohne Vergleich mit anderen QS-Techniken, ist eindrücklich dokumentiert. Das liegt daran, dass diverse Forschergruppen zur Bewertung der von ihnen entwickelten Technologie Fallstudien publizieren und in diesen stets Fehler finden konnten [1,3,5,9,10,11,12,15,16,18,20,24,25,17]. Diese Erkenntnisse müssen natürlich mit den Resultaten alternativer QS-Techniken in Bezug gesetzt werden – dass bei sorgfältiger Modellierung eines Systems Probleme gefunden werden, überrascht zunächst nicht (s. den folgenden Abschnitt zur Annahme 4). Dennoch zeigen die Studien klar das Potential des MBT auf.
Die für die industrielle Verbreitung von Techniken des MBT relevanteste Form der Evidenz bezieht sich auf den relativen Aufwand/Nutzen des MBT (Annahme 4): wie aufwendig ist die Erstellung modellbasierter Tests, d.h. von Modell, Selektionskriterien und Adapter, im Vergleich zu herkömmlichen Formen des Tests (zum Vergleich mit anderen QS-Maßnahmen s. andere Arbeiten [13]), und wie unterscheidet sich die „Qualität“ der Tests, z.B. in Bezug auf die Anzahl detektierter Fehler?
Untersuchungen über die Qualität von Tests finden sich in den folgenden Aufsätzen (1,2 berücksichtigen den Nutzen und ignorieren Kosten; 3,4 berücksichtigen auch Kosten). 1.
2.
3.
Dalal et al. [11] fassen Erfahrungen aus vier industriellen Projekten zusammen. Ihr Ansatz zum modellbasierten Testen basiert ausschließlich auf Umwelt- bzw. Eingabedatenmodellen (pairwise testing), d.h. es gibt kein automatisiertes Orakel. MBT findet signifikant mehr Fehler als nicht modellbasiertes Testen. Pretschner et al. [24] untersuchen MBT auf der Basis von erweiterten Zustandsmaschinen mit I/O. Die Modellierung findet eine große Anzahl von Fehlern in den vorher vorhandenen Spezifikationen, modellbasierte Tests finden signifikant mehr Fehler als nicht modellbasierte Tests, und automatisch generierte modellbasierte Tests finden nicht mehr Fehler als manuell erstellte modellbasierte Tests. Bernard et al. [3] beschreiben ihren Ansatz mit in B geschriebenen Modellen. Testfälle werden anhand struktureller Kriterien erzeugt. Eine auf Anforderungen (nicht gefundenen Fehlern) basierende Subsumptionsbeziehung zwischen Testfällen wird definiert, und es wird gezeigt, dass automatisch generierte Tests i.a. eine ad-hoc
91
handerstellte Referenzsuite umfassen. Modellbasiertes Testen ist halb so aufwendig wie herkömmliches Testen. 4. Farchi et al. [15] beschreiben zwei Studien, in denen MBT mit in einer Variante der Murphi-Eingabesprache notierten Modellen Fehler findet, die ohne explizite Modelle nicht gefunden wurden. MBT erfordert einen um 15 Prozentpunkte niedrigeren Aufwand als nicht explizit modellbasiertes Testen. Schließlich dokumentieren die Arbeiten von Clarke [8] und Blackburn et al. [5] bezüglich sowohl Effektivität als auch Effizienz signifikante Vorteile des MBT gegenüber nicht-modellbasiertem Testen. Da die Diskussion vermutlich aus Vertraulichkeitsgründen stark abstrahiert erfolgt, wird hier auf eine nähere Beschreibung verzichtet.
4 Schlussfolgerungen Testen ist notwendigerweise modellbasiert [4], ob das Sollverhalten nun implizit gegeben oder in ein explizites Modell codiert ist. Viele bis heute offene Fragen, etwa die nach geeigneten Testselektionskriterien, sind demnach unabhängig davon, ob konventionelles Testen oder die explizit modellbasierte Spielart betrachtet wird. Dieses Papier hat die Erfolgsfaktoren in Form von zumeist impliziten Annahmen und existierende Evidenz benannt, die sich insbesondere auf die kostengünstige und hochqualitative Entwicklung von nicht nur zum Testen verwendeten, hinreichend abstrakten und detaillierten Modellen sowie Testselektionskriterien und Adaptern beziehen. Die erwarteten Vorteile des MBT lassen sich dann wie folgt zusammenfassen. 1.
2. 3.
Die Tatsache, dass das o.g. implizite mentale Modell explizit gemacht wird, erlaubt es, auf strukturierte Art und Weise ausreichend viele und gute Tests bei akzeptablen Kosten zu erzeugen. MBT liefert „bessere“ und „billigere“ Tests als Strategien, die nicht auf expliziten Modellen basieren Der Vorgang der Modellierung an sich sorgt dafür, dass Probleme in den Spezifikationsdokumenten frühzeitig erkannt und behoben werden können. Das MBT erzeugt somit einen zusätzlichen Wert des Modells.
Eingebettete Systeme. Die hier aufgeführten Betrachtungen sind bewusst so allgemein gehalten, dass sie sowohl für den Bereich eingebetteter Systeme als auch für den von Businessinformationssystemen zutreffen. Dennoch gibt es natürlich auch im Bereich des (modellbasierten) Testens spezielle relevante Charakteristika beider Domänen. Erstens ist der Test eingebetteter Systeme insofern erschwert, als der interne Zustand des Systems üblicherweise nicht bekannt ist, was dazu führt, dass spezielle Signalfolgen angelegt werden müssen, um diesen Zustand zu bewerten. Zweitens sind die Qualitätsanforderungen an eingebettete Systeme insofern höher, als Rückrufaktionen von Chipkarten oder automobilen Steuergeräten sehr teuer sein können. In der Konsequenz „darf“ der Testprozess ggf. etwas aufwendiger ausfallen. Drittens ist die Anzahl der Testfälle für eingebettete Systeme bisweilen durch die Hardware eingeschränkt—anstelle von Millionen von Testfällen können ggf. nur Tausende ausgeführt werden. Viertens sind eingebettete Systeme (heute noch) durch einen eher komplexen Kontrollfluss als durch komplexe
92
verwendete Datentypen charakterisiert. Das hat Konsequenzen insofern, als strukturelle Abdeckungskriterien für den ersten Fall besser verstanden zu sein scheinen. Schließlich sind Modelle eingebetteter Systeme und insbesondere Modelle ihrer Umwelt häufig kontinuierlicher oder hybrider Natur, was direkte Konsequenzen für die Technologie der Testfallgenerierung zeitigt. Vielversprechende Forschungsgebiete. Erste Evidenz für den erfolgreichen und möglicherweise kosteneffektiven Einsatz des MBT ist verfügbar. Die folgenden Fragen harren allerdings noch einer soliden Beantwortung: Wieviele Fehler werden während der Modellierungsphase allein gefunden? Wie effektiv ist die Automatisierung? Wie schneidet MBT im Vergleich mit konkurrierenden Technologien ab? Wie verhalten sich Kosten und Nutzen zueinander, insbesondere unter der Annahme, dass existierende Testmanagementsysteme eingesetzt werden? Welche domänenspezifischen Charakteristika gibt es? Welche organisatorischen und prozessbezogenen Voraussetzungen sind unabdingbar? Die Technologie der Testfallerzeugung (s. die Überblicksarbeiten zu existierenden Werkzeugen [2,27]) ist zumindest für deterministische ereignisdiskrete Systeme ohne harte Echtzeitanforderungen soweit ausgereift, dass empirische Studien zur Beantwortung dieser Fragen bei allen existierenden Schwierigkeiten in Angriff genommen werden können. Eine weitere relevante offene Frage, die aus dem Feld des MBT herausführt, liegt in der Entscheidung über adäquate Abstraktionsniveaus bei der ingenieurmäßigen Erstellung von Modellen von SUT und Umwelt, unterstützt etwa durch mehr oder weniger domänenspezifische Abstraktionsmuster. Ebenfalls aus dem Gebiet des MBT heraus führen Forschungen, wie Modelle effizient erstellt werden können. Das beinhaltet Versionierungsmechanismen für Modelle, Modell-Debugger, werkzeuggestützte Entwicklungsschritte wir Refactorings und Regressionstests. Die Verknüpfung von Verhaltensmodellen mit Testmiddleware scheint technisch ebenfalls noch nicht befriedigend gelöst. Die Forschung zu Spezifikationssprachen für Selektionskriterien (nicht für die Tests selbst, wie TTCN-3) befindet sich noch in den Anfängen. Schließlich ist bis heute unklar, auf welcher Grundlage Selektionskriterien für konkrete Anwendungen oder Fehlerklassen definiert werden sollen. Der Verfasser ist überzeugt, dass das MBT eine vielversprechende Technologie darstellt. Die zugrundeliegenden Ideen erscheinen insbesondere dann attraktiv, wenn sie im Zusammenhang übergreifender modellbasierter Entwicklungsprozesse gesehen werden. Danksagung. B. Köpf, J. Philipps und B. Schätz bin ich für wertvolle Anregungen und Kommentare zu einer frühen Version dieses Aufsatzes dankbar.
5 Literaturverzeichnis 1.
2.
A. Belinfante, J. Feenstra, R. d. Vries, J. Tretmans, N. Goga, L. Feijs, S. Mauw, L. Heerink : Formal test automation: A simple experiment. Proc. 12th Intl. workshop on Testing of Communicating Systems, S. 179-196, 1999 A. Belinfante, L. Frantzen, C. Schallhart: Tools for Test Case Generation. [6], S. 391-438
93
3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
17. 18.
19. 20.
21. 22. 23. 24. 25. 26. 27. 28. 29.
94
E. Bernard, B. Legeard, X. Luck, F. Peureux: Generation of test sequences from formal specifications: GSM 11.11 standard case-study, SW Practice&Experience 34 (10):915-948, 2004 R. Binder: Testing Object-Oriented Systems: Models, Patterns&Tools. Addison Wesley, 1999 M. Blackburn, R. Busser, A. Nauman: Why model-based test automation is different and what you should know to get started. Proc. Intl. Conf. on Practical SW Quality and Testing, 2004 M. Broy, B. Jonsson, J.-P. Katoen, M. Leucker, A. Pretschner (Hrsg.): Model-Based Testing—a tutorial volume. Springer LNCS 3472, 2005 O. Buehler, J. Wegener: Automatic testing of an autonomous parking system using evolutionary computation. SAE world congress, 2004. J. Clarke: Automated Test Gen. from Behavioral Models. Proc.11th SW Quality Week, 1998 D. Clarke, T. Jéron, V. Rusu, E. Zinovieva: Automated Test and Oracle Generation for Smart-Card Applications. Proc. E-smart, S. 58-70, 2001 I. Craggs, M. Sardis, T. Heuillard: AGEDIS Case Studies: Model-Based Testing in Industry. Proc. 1st Eur. Conference on Model Driven Software Engineering,S. 129-132, 2003 S. Dalal, A. Jain, N. Karunanithi, J. Leaton, C. Lott, G. Patton, B. Horowitz: Model-based testing in practice. Proc. ICSE'99, S. 285-294, 1999 J. Dushina, M. Benjamin, D. Geist: Semi-formal test generation with Genevieve. Proc. 38th conf. on Design automation, S. 617-622, 2001 A. Endres, D. Rombach: A Handbook of Software and Systems Engineering. Add Wes, 2003 M. Fagan: Reviews and Inspections. In Software Pioneers—Contributions to Software Engineering, Springer, S. 562-273, 2002 E. Farchi, A. Hartman, S. Pinter: Using a model-based test generator to test for standard conformance. IBM Systems Journal 41 (1):89-110, 2002 L. Fournier, A. Koyfman, M. Levinger: Developing an Architecture Validation Suite: Application to the PowerPC Architecture. Proc. 36th ACM Design Automation Conference, S. 189-194, 1999 M. Horstmann, W. Prenninger, M. El-Ramly: Case Studies. [6], S.439-461 H. Kahlouche, C. Viho, M. Zendri: An industrial experiment in automatic generation of executable test suites for a cache coherency protocol. Proc. IFIP TC6 11th Intl. Workshop on Testing Communication Systems, S. 211-226, 1998 J. Musa: Software Reliability Engineering. Author House, 2. Auflage, 2004 J. Philipps, A. Pretschner, O. Slotosch, E. Aiglstorfer, S. Kriebel, K. Scholl: Model-based test case generation for smart cards. Proc. 8th Intl. Workshop on Formal Methods for Industrial Critical Systems, S. 168-192, 2003 W. Prenninger, A. Pretschner: Abstractions in Model-Based Testing. ENTCS 116:59-71, 2005 A. Pretschner: Model-Based Testing in Practice. Proc. FM’2005, S. 537-541, 2005 A. Pretschner, J. Philipps: Methodological Issues in Model-Based Testing. [6], S. 281-291 A. Pretschner, W. Prenninger, S. Wagner, C. Kühnel, M. Baumgartner, B. Sostawa, R. Zölch, T. Stauner: One Evaluation of MBT and its Automation. Proc. ICSE 2005, S.392-401 J. Shen, J. Abraham: An RTL Abstraction Technique for Processor Micorarchitecture Validation and Test Generation. J. Electronic Testing: Theory&Application 16 (1-2):67-81, 1999 H. Stachowiak: Allgemeine Modelltheorie. Springer, 1973 M. Utting, A. Pretschner, B. Legeard: A Taxonomy of Model-Based Testing. Eingereicht bei J. Information and Software Technology, 2005 G. Walton, J. Poore: Generating transition probabilities to support model-based software testing. Software: Practice and Experience 30(10):1095-1106, 2000 H. Zhu, P. Hall, J. May: Software Unit Test Coverage and Adequacy. ACM Computing Surveys 29:366-427, 1997
Real-time Operating Systems for Self-coordinating Embedded Systems Franz J. Rammig, Marcelo G¨otz, Tales Heimfarth, Peter Janacik, Simon Oberth¨ur Heinz Nixdorf Institut Universit¨at Paderborn F¨urstenallee 11 D-33102 Paderborn {franz, mgoetz, tales, pjanacik, oberthuer}@uni-paderborn.de Abstract: It can be observed that most technological artefacts are becoming intelligent “things that think” and most of these intelligent objects will be linked together to an “Internet of things”. To master this omnipresent virtual “organism”, completely new design and operation paradigms have to evolve. In this paper we discuss how research of our group at the University of Paderborn is providing fundamental principles, methods, and tools to design real-time operating systems for this virtual “organism” of the future. Based on our fine-granular library for the construction of reflexive RTOS, the necessary configuration tool and its on-line version are discussed. Next step towards self-coordination is a profile management system to support self-optimization of the RTOS. The included flexible resource manager allows migration of RTOS services dynamically between programmable processors and re-configurable HW. In a final step the RTOS itself can be distributed. Its services are provided by a cluster of instances instead of a single one. This makes a sophisticated dynamically self-optimizing communication system necessary.
1
Introduction
In the world of information technology it is no longer the computer in the classical sense where the majority of IT applications are executed; computing is everywhere. More than 20 billion processors have already been fabricated and the majority of them can be assumed to still be operational. At the same time virtually every PC worldwide is connected via the Internet. This combination of traditional and embedded computing creates an artefact of a complexity, heterogeneity, and volatility unmanageable by classical means. Metaphorically speaking, it may be treated as an organism made up of computers, networks, system software, applications, and, most importantly, human beings. This virtual organism as it exists today is still in a state of adolescence. Each of our technical artefacts with a built-in processor can be seen as a “Thing that Thinks”, a term introduced by MIT’s Thinglab. It can be expected that in the near future these billions of Things that Think will become an “Internet of Things”, a term originating from ETH Zurich. This means that (using the above metaphor) we will be constantly surrounded by a virtual “organism” of Things that Think. This organism cannot be managed by any traditional means. As a consequence, completely new RTOS approaches are needed. The virtual organism is volatile by
95
nature. Its constituents are mobile and adapt to changing environmental contexts in a selforganizing manner. This means that the RTOS itself has to be self-adapting as well, which includes that it has to be reflexive. Techniques are needed to allow such an RTOS to sense its environment, reflect this information at its present state, decide about self-modifications and execute this self-modification. Some approaches developed in our group to deal with these challenges will be sketched out in this contribution. These approaches are based on the assumption that system services are provided by means of alternative profiles. An intelligent profile manager selects the presently best suited collection of services and their respective profiles. Re-configurable hardware is commercially available and introduces an additional degree of potentials and at the same time of volatility. Systems consisting of programmable microcontrollers and re-configurable HW can be tailored dynamically towards actual demands by application software. It depends on the actual characteristics of application load whether processor capacity or FPGA area are the more valuable good. This means that RTOS services should migrate dynamically between SW and HW implementation. An additional challenge arises if the global interaction of all these objects is envisioned. Together with potential mobility of the devices, a degree of volatility is introduced that is unknown in traditional systems. Centralized approaches seem to be completely inadequate to cope with this challenge. We therefore developed a cross-layer communication system that uses decentralized techniques to provide a communication backbone in highly volatile environments. These techniques are inspired by the behaviour of ant colonies. If such a self-adapting and self-optimizing communication backbone has been established, a new perspective on the RTOS becomes possible. There may be no longer a need to provide all potentially requested services by each instance of the RTOS on the various nodes. In principle it would be sufficient to provide the services by a complete cluster of instances as a whole. However careful tailoring of service distribution is necessary as any remote service provisioning is very costly due to the extremely high power consumption of communication.
2
Related Work
Some work on customization and configuration as approach for adapting a system to the requirements of an application has been reported in literature. In the field of (real-time) operating systems (OS) various approaches for customization have been proposed. S YNTHE SIS [Mas92] adapts its code by partially evaluating and recompiling condition statements depending on available input data at run time. This can result in changing compare instructions and conditional jumps by unconditional jumps and vice versa. Likewise, the OS K42 [SAH+ 03] includes system support for online reconfiguration by a hot-swap mechanism using C++ virtual function tables. Reconfigurable hardware/software based (hybrid) architectures are being very attractive for implementation of run-time reconfigurable embedded systems. Moreover, the hardwaresoftware allocation of application tasks to dynamically reconfigurable embedded systems (by means of task migration) allows for customization of their resources during run-time to meet the demands of executing applications, as can be seen in [HMM04] and [MNC+ 03].
96
Nevertheless, the current research efforts spent in this field are just focused on application level, leaving to the RTOS the responsibility to provide the necessary mechanisms and run-time support (see [BJS04], [WK01] and [NCV+ 03]). In [BJS04], e.g., the resources are dynamically arranged to support dynamic application tasks arriving into the system. However, the RTOS itself is still static. In our novel proposal, we expand and adapt those concepts to the RTOS level. Thus, not just the application but also the RTOS itself may also be reconfigured over a hybrid architecture. Current OS are not able to work on top of ad hoc networks in a distributed manner (e. g. VxWorks [Sys99], Apertos [Yok92]). OS for sensor networks like TinyOS [ea00] do not support complex, distributed applications using elaborate OS services like our approach. Several of our approaches are based on the division of labour in ants [BDT99]. Conducted experiments suggest that resilience of a colony as a whole is determined by the elasticity observed at the individual level, which is modelled as follows: Intensity of stimulus s associated with a particular task, determined by quantitative cues sensed; response threshold θ, determining the tendency of an individual to respond to a stimulus. Finally, n describing the steepness of the threshold. They are combined in the response function: n Tθ (s) = sns+θn .
3
Basic Principles of the DREAMs Library and the TereCs Configuration System
OS and run-time platforms even for heterogeneous processor architectures can be constructed from customizable components (skeletons) out of the D REAMS’s (Distributed Real-time Extensible Application Management System) library [Dit99]. By creating a configuration description all desired objects of the system have to be interconnected and afterwards fine-grained customized. The goal of that process is to add only those components and properties that are required by the application. The creation of a final configuration description for D REAMS was automated during the project TEReCS (Tools for Embedded Real-Time Communication Systems) [B¨ok03]. During that project a methodology was developed in order to synthesize and configure the OS for distributed embedded applications. TEReCS distinguishes between knowledge about the application and expert knowledge about the customizable OS. Knowledge about the application is considered as a requirement specification. This specification is input to the configurator and abstractly describes the behavior of the application and some constraints (deadlines), which have to be assured. The behavior of the application is defined by the OS calls it requests. The complete and valid design space of the customizable OS is modelled by an AND/OR service dependency graph in a knowledge base. This domain knowledge contains options, costs, and constraints and defines an over-specification by containing alternative options. The configuration process removes some domain specific knowledge by exploiting knowl-
97
edge about the application. Thereby, a configuration for the run-time platform will be generated. In the AND/OR graph nodes represent services of the OS and are the smallest atomic items, which are subject to the configuration. Mandatory dependencies between services are specified by AND edges, optional or alternative are specified by OR edges. Services and their dependencies have costs and can be prioritized. Constraints for the alternatives can be specified. Root nodes of the graph are interpreted as system primitives/system calls of the OS. Each of these primitives points to one concrete service. The service dependencies span a complete graph. The leaf nodes can refer to hardware devices. These devices are communication devices, which again refer to communication media.
4
Self-Optimization
For building an RTOS system, which optimizes itself and provides the released resources optimally to the applications, we have to answer the three following questions: First, how can we get information about the dynamic resource requirements during run-time of an application? A suitable interface between the application and the OS is required. Second, how can we describe the design space for reconfiguration of the RTOS system? A model is required that describes the dependencies between the system services. Third, based on this information: Which is an adequate system configuration? A resource management system is required to activate/deactivate the system services and to release resources for the applications. Our self-optimizing RTOS consists of three components Profile Framework, Online TEReCS and Flexible Resource Management (FRM), which are briefly described in this section. A concrete example and a prototype are provided in [OBG05]. Profile Management The Profile Framework, described in detail in [OB04], has two main purposes: The first purpose is to model information about the dynamic resource requirements of the application and of the system services. The knowledge about the resource requirements of the applications is necessary to optimize the system by deactivating services that are currently not required. The resource requirements of the system services are necessary to determine the amount of resources, which can be released and to guarantee that applications and system services get their required resources under hard real-time conditions. The second purpose is to provide released resources from deactivated system services to the applications. By means of this framework the developer can define a set of profiles per application. Profiles describe different service levels of the application, including different quality and different resource requirements. Additionally each profile holds information about the time to activate and deactivate the profile. All resource allocations of an application require an announcement to the FRM. The maximal assignment delay, specified in each profile per resource, is the worst case time the assignment of the resource can be delayed from the announcement until its allocation. Online Configuration System: Online TEReCS
98
The Online TEReCS component has knowledge of the design space of the customizable components, models system services as profiles, and is responsible for the low-level reconfiguration of the system services. For the online case of the configuration a coarse grained hierarchy of this graph is used on the system service level – one service can be composed of many components. Thus, the overall decision space is more restricted and the number of generated profiles is easy to manage. For a system service, which can be in a deactivated or in an activated state, two profiles are created. One profile for the activated and one profile for the deactivated state. In the profile for the activated state the service specifies the required resources to fulfill its task. In the profile for the deactivated state the service occupies the resources it provides in the activated state. Hereby, it is guaranteed that the services can only be deactivated if the provided services are not required. Flexible Resource Manager The major goal of the FRM [OB04] is to optimize the resource utilization and the over-all system quality by selecting profiles for activation under the actual conditions. To maximize the utilization the FRM puts the resources, which are held back for worst case resource requirements of an application, at other application’s disposal. Normally, an application acquires as many resources as it requires for worst-case scenarios. Thus, the application has always enough resources for its tasks and can fulfill its service at any time. These resources are only required when the worst-case scenario occurs. In our approach the FRM tries to minimize this internal waste of resources, by making these resources temporarily available to other applications under hard real-time conditions. The FRM is responsible for switching between the profiles of the applications and system services under the defined switching conditions. The decision is made based on a quality function, which considers the actual resource requirements, the importance of an application, and the quality of the profiles. To guarantee hard real-time conditions, an acceptance test for profile activation is integrated in the optimization process.
5
Reconfigurable Hardware/Software-based RTOS
Differently from the normal approach where the design of such RTOS is done offline, the proposed approach suggests the use of new reconfigurable architectures (e.g. Virtex-II ProTM FPGA) in order to support the development of a hardware/software reconfigurable OS [G¨ot04]. In this proposed architecture, the Real-Time OS (RTOS) is capable to adapt itself to current application requirements, tailoring the RTOS components for this purpose. Therefore, the system continuously analyzes the requirements and reconfigures the RTOS components at the hybrid architecture optimizing the use of system resources. Hence, the system is capable to decide on-the-fly which RTOS components are needed and also to which execution environment (CPU or FPGA) they should be assigned. Our system concept is based on a microkernel approach, where the RTOS services are provided as a set of hardware and software components. These components can, during run-time, be reallocated (reconfigured) over the hybrid architecture. The usage of microkernel also in-
99
corporates the nature advantage of flexibility and extensibility (among others) of it, which is very desired in our case in order to better perform the reconfigurability aspects. RTOS Service Assignment The decision of which RTOS service is to be placed in hardware or software, is based on the amount of resources and the communication costs needed by each service. If an RTOS component is allocated at the software environment, it will usually increase the processor load. Otherwise, at the hardware environment it will require some amount of circuit area available. Similarly, the communication requirements of each service will infer in different communication costs depending on its placement. To solve this assignment problem, a cost function has been proposed [GRP05], which tries to minimize the total amount of resource used by the RTOS component set currently needed by the application. Besides the limited amount of resources available for the RTOS, a weighted load balancing of the resources used is specified as a system constraint. Thus, it is possible to influence the placement decision based on the current valuable goodness of the resources required, since the resources are shared between RTOS and application software. Moreover, through a correct load balancing, it can be avoided that one execution environment gets near to its full utilization and so, making the system capable to absorb variations of the application demands. System Reconfiguration As the application requirements are considered to be dynamic, the component costs are not static and depend on the current application demands. This leads to the fact that a certain system configuration (component allocation) may no longer be valid after application changes. Therefore, a continuous evaluation of the components partitioning is necessary. Whenever the system reaches an unbalanced situation, the RTOS components should be reallocated in order to bring the system again into the desired configuration. In this situation, not just the new assignment problem needs to be solved again, but also the costs (time) necessary to reconfigure the system from the current state to new one need to be evaluated. This evaluation is necessary since we are dealing with real-time systems and so, it has a limited time available for reconfiguration activities (which depends on the current application time constraints). For this case, our approach consists on scheduling the RTOS components reconfiguration together with the application tasks. Therefore, techniques based on RTOS scheduling theory, like fixed/dynamic priority servers, are used to provide a safely time for reconfiguration activities and still guarantee the correct application tasks timeliness.
6
Self-optimizing Communication System
In the introduced virtual “organism” made up of mobile constituents, wireless communication plays an important role. It is the logical next step after having considered wired communication in our previous work, which is only suited for static networks. Given its relatively high cost, the means of wireless communication has to be utilized economically.
100
Employed within this context, self-organization promises lower complexity and communication overhead, as well as, increased robustness and good scalability properties. We aim to use this powerful paradigm at all levels of the network stack. Our efforts are predominantly directed towards the following aspects: topology control, combined link metrics, as well as, adaptive ant colony-based multipath routing. Network regions with higher node density tend to lead to a greater amount of energy waste through overhearing, collisions, and retransmissions after frame losses, while not increasing the network’s capacity. Therefore, we develop an emergent topology control reducing the number of active nodes in such areas. It divides nodes in transporters, actively participating in network operation (e. g. part of a routing backbone), and workers, not involved in these activities. The underlying mechanism for state transitions is motivated by the division of labour in ants. State changes are realised using a response function, as reviewed in Section 2. The underlying idea behind the response function for the worker-to-transporter transition is to use a threshold function that decreases the tendency for a worker to become a transporter with more energy consumed and a lower density of neighboring worker nodes. The stimulus rises with a longer disconnection time from the backbone. On the other hand, the underlying idea of the response function for the transporter-to-worker transition is to use a threshold that decreases, when the backbone around a transporter becomes denser. The stimulus rises with the amount of energy consumed since becoming transporter. Efficient utilisation of the wireless medium can only be realised given a good estimate of the “real” quality (in terms of the expected reception success) of the underlying links. Based thereon, protocols and applications at upper layers are given the means to adjust their optimization strategies. None of the basic, conventional metrics provides fully satisfying results: Received signal strength measurements are rough, but quick estimates. The observation of transmission successes yields precise results, but only after enough data is provided. Neither of these metrics recognises volatile links, so that upper layers could avoid them. Hence, we use a combined link metric, the so called virtual distance, incorporating received signal strength, reception success rate, and a history component. At the network layer, we extend state-of-the-art ant colony-based multipath routing by several elements. Our choice for ant colony-based routing was motivated by its promising characteristics: utilisation of multiple paths, probabilistic decisions, consideration of lower-layer feedback, and local work, helping to achieve more resilience, a higher degree of load balancing, and a lower communication overhead. To accelerate the transitory phase in ant-colony routing, we propose a novel waycost function enabling pheromone adjustments that more accurately reflect underlying properties. To enable this, packets carry a field containing the combined link metric-based, accumulated waycost taking into account all visited (i.e. utilized) links. The amount of pheromone deposited on a packet’s way then decreases exponentially with increasing waycost. In order to reduce the frequency of expensive route failures and reconstructions due to changes incurred by topology control, we further propose a fuzzy distinction between transporters and workers: during a next-hop decision, the probability for choosing a transporter is increased. In ns-2 [The] simulations, we demonstrated the scalability in terms of node number and density, as well as, the stability of the results of topology control. Further, the results
101
showed a significant improvement of the quality of utilised links using the combined link metric.
7
NanoOS – Service Provisioning by Clusters of OS Instances
In an “Internet of things” scenario, heterogeneous sorts of devices are connected through different network infrastructures. Vantages can be achieved with this scenario with the introduction of distributed computing instead of bare centralized one. We can generalize the idea of self-optimization from one node to a network of connected devices. In our approach, we are considering small devices connected through an ad hoc network. In order to support complex functionality in constrained nodes, the OS uses a novel approach: it distributes the services among the nodes. This means that each node of the system has just a small part of the kernel of the complete OS; a group of nodes together form an instance of the OS. Thereby the resource requirements in each node are much less than on a node with all services locally instanced. The prototype of an OS, built over the self-optimizing communication system presented in the previous section, enables this vision. It is called NanoOS [HR04]. In the NanoOS, each application has one goal and is composed by a set of tasks; tasks are the atomic unit of the distributed application. The developer is responsible for the division of the application in several cooperative tasks. For this the OS supports hierarchic grouping of tasks. The services and tasks can migrate in order to optimize the communication. Each service is autonomous, it is an agent that tries to find a good position in the network, a node with enough resources and where the communication with the clients (application tasks) is minimized. Resource-aware Clustering The distribution of the services brings several problems. The consistency of the kernel in each node should assure also a global consistency of the entire “distributed” kernel (global consistency). The connection quality plays an important role in this case. In order to restrict the traffic between nodes with good connection quality and also to reduce significantly the organization overhead of the OS (small routing table, service discovery scope and consistency control), the entire system is divided in clusters. Each cluster should contain the necessary resource for all services running inside the cluster. This brings the concept of a complete OS instance per cluster. Cluster: set of nodes where all the services required by the tasks in this set are available in nodes inside the set. We developed a heuristic that uses just a small amount of local communication to find the clusters that contain a minimum amount of resources. As result of our clustering algorithm, each node will be assigned to a cluster φ ∈ 0, .., n − 1 where n is the number of clusters. During the clustering, a node can be of type clusterhead (task that represent a cluster), member (ordinal member of a cluster) or not clustered (task that does not belong to any cluster). The main idea of the algorithm is to use the principle of the stimulus/threshold found in the division of labor of some social insects: members of a nest with different
102
morphology have different threshold to do a determined task. In our case, nodes with good communication and plenty neighborhood have a smaller threshold to become clusterhead than nodes with few loosely connected neighbors. The stimulus to become clusterhead increases with the time that a node is of not clustered type. Service Distribution The distribution algorithm is responsible for deciding where each service of the OS should be placed inside a cluster. The algorithm is executed in each service that is independent to decide the destination node. The main goal of the distribution algorithm is to reduce the global communication overhead (in a continuous self-optimization process), therefore the state of the wireless links is an important parameter used in the optimization process. For this reason, we used the presented link metric that rates the connection quality of the adhoc links (virtual distance). The positioning of the services is done based on this virtual distance graph and the resource availability in each node. It tries to minimize the sum of all virtual distances of all remote system calls. This is an NP-Complete combinatorial problem with similarities with the QAP (Quadratic Assignment Problem). To solve it distributively, we developed an heuristic based on the principles of the swarm intelligence, more specifically, Ant Colony Optimization [BDT99]. Each service of the OS is modeled as a food source and the calls coming from different nodes are the ants looking for the service. Each node has a pheromone table. In each node where an ant passes when going in the direction of the food, it increases the pheromone of correspondent service in the same proportion to the communication cost of the request. The optimization is done when the service (food source) moves in the direction of the higher pheromone; that means the service migrates in the direction from where more calls are coming.
8
Conclusion
With the library for real-time operating services called DREAMS we are providing a sound basis for the construction of tomorrow’s real-time operating systems. We extended this fundamental component-based library by means of a configuration system that can be applied even in on-line mode. Strategic decisions are made by a profile management system, supported by a flexible resource manager. Our reflexive RTOS is able to migrate services dynamically between SW and HW implementations to make sure that always the actually most valuable resources are available for application processes. A fully decentralized, self-organizing communication system for ad-hoc networks, based on ant colony inspired techniques opens the path to highly distributed, highly dynamic systems. This communications system allows even to distribute RTOS services over a cluster of instances of the RTOS in such a way that the total functionality of the RTOS is no longer provided by each individual instance but by the cluster in total. In the future this innovative approach will be extended further. More sophisticated learning algorithms and even more biologically inspired techniques will be included. The solution will be applied in a variety of applications ranging from sensor networks via cooperative mini-robots up to swarm-based space missions.
103
References E. Bonabeau, M. Dorigo, and G. Theraulaz. Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York, NY, 1999. [BJS04] Krishnamoorthy Baskaran, Wu Jigang, and Thamipillai Srikanthan. Hardware Partitioning Algorithm for Reconfigurable Operating System in Embedded Systems. In Sixth Real-Time Linux Workshop, 2004. [B¨ok03] C. B¨oke. Automatic Configuration of Real-Time Operating Systems and Real-Time Communication Systems for Distributed Embedded Applications. Phd thesis, Paderborn University, Paderborn, Germany, 2003. [Dit99] C. Ditze. Towards Operating System Synthesis. Phd thesis, Paderborn University, Paderborn, Germany, 1999. [ea00] J. Hill et al. System architecture directions for networked sensors. In Proc. of the 9th int. conf. on architectural support for programming languages and OS, 2000. [G¨ot04] Marcelo G¨otz. Dynamic Hardware-Software Codesign of a Reconfigurable Real-Time Operating System. In ReConFig. Mexican Society of Computer Science, 2004. [GRP05] Marcelo G¨otz, Achim Rettberg, and Carlos E. Pereira. Towards Run-time Partitioning of a Real Time Operating System for Reconfigurable Systems on Chip. In Proc. of IESS, Manaus, Brazil, 2005. [HMM04] J. Harkin, T. M. McGinnity, and L. P. Maguire. Modeling and optimizing run-time reconfiguration using evolutionary computation. Trans. on Embedded Computing Sys., 2004. [HR04] T. Heimfarth and A. Rettberg. NanoOS - Reconfigurable OS for Embedded Mobile Devices. In In Proc. of the International Workshop on Dependable Embedded Systems, Florianopolis, Brazil, 2004. [Mas92] H. Massalin. Synthesis: An Efficient Implementation of Fundamental Operating System Services. Phd thesis, Columbia University, 1992. [MNC+ 03] Jean-Yves Mignolet, Vincent Nollet, Paul Coene, Diederik Verkest, Serge Vernalde, and Rudy Lauwereins. Infrastructure for Design and Management of Relocatable Tasks in a Heterogeneous Reconfigurable System-on-Chip. In DATE, 2003. [NCV+ 03] V. Nollet, P. Coene, D. Verkest, S. Vernalde, and R. Lauwereins. Designing an Operating System for a Heterogeneous Reconfigurable SoC. In Proc. of IPDPS, 2003. [OB04] S. Oberth¨ur and C. B¨oke. Flexible Resource Management - A framework for selfoptimizing real-time systems. In B. Kleinjohann, Guang R. Gao, H. Kopetz, L. Kleinjohann, and A. Rettberg, editors, Proc. of IFIP Working Conference on Distributed and Parallel Embedded Systems (DIPES’04). Kluwer Academic Publishers, 23 - 26 August 2004. [OBG05] S. Oberth¨ur, C. B¨oke, and B. Griese. Dynamic Online Reconfiguration for Customizable and Self-Optimizing Operating Systems. In Proc. of the 5th ACM international conference on Embedded software (EMSOFT’2005), pages 335–338, 18 - 22 September 2005. Jersey City, New Jersey. [SAH+ 03] C. Soules, J. Appavoo, K. Hui, D. Silva, G. Ganger, O. Krieger, M. Stumm, R. Wisniewski, M. Auslander, M. Ostrowski, B. Rosenburg, and J. Xenidis. System Support for Online Reconfiguration, 2003. [Sys99] Wind River Systems. VxWorks 5.4 - Product Overview, June 1999. [The] The network simulator. Online. http://www.isi.edu/nsnam/ns/, accessed April 8, 2005. [WK01] Grant Wigley and David Kearney. The Development of an Operating System for Reconfigurable Computing. In FCCM, 2001. [Yok92] Y. Yokote. The Apertos Reflextive Operating System: The Concept and Its Implementation. In OOPSLA Proceedings, 1992. [BDT99]
104
Some motivation and current results for synchronous modeling and implementation Jan Romberg Abstract: Synchronous modeling and programming has been around for roughly two decades now, and has traditionally been associated with design of hardware, abstract control algorithms, and non-distributed software. In this paper, we argue that synchronous modeling is a practically viable option for model-based design and implementation: we’ll list some evidence that, for the embedded sector, synchronous techniques have some superior characteristics over, for instance, asynchronous UML-based modeling techniques. We also argue that the true potential of synchronous techniques for construction of larger, concurrent systems has not been fully realized to date: to that end, some current advancements for implementing synchronous programs in distributed settings are described.
1
Motivation: Why synchronous?
In embedded systems design, there is obviously a need for varying modeling paradigms and degrees of precision at different development phases. The spectrum ranges from informal, weakly structured, largely textual requirements models to detailed behavioral models of a system. In this paper, we shall restrict ourselves to the “lower” end of this spectrum: detailed, behaviorally defined models of embedded control systems, which may serve as a basis for model-based verification and validation. The first question we shall examine is: What is an adequate way of modeling, i.e. expressing, a design for an embedded system at this level? As a part of the answer, we will identify some weak spots in current asynchronous UML-based methods, which are favorably solved by synchronous techniques. Our treatment will by no means cover all relevant aspects, and will be heavily biased towards concurrency and timing issues. The second question considered is: Are synchronous models implementable in realistic settings? We’ll present some current results that allow some optimism in this respect, and identify some open issues for research.
1.1
Comparison: The contestants
Synchronous modeling in a nutshell. Synchronous programming and modeling techniques have been popularized by languages such as S TATEMATE, E S -
105
TEREL , or the discrete-time subset of S IMULINK . Our own work includes contributions to the AutoF OCUS tool, which also uses a synchronous model of execution. The characterizing features of synchronous models relevant to this discussion is the existence of a global, discrete time, statically boundable resource consumption, and the determinism of computation and communication with respect to the timebase. The first feature is quite intuitive and probably needs no further explanation. In a common time grid, both aperiodic and periodic computations of varying frequency can be represented by using special symbols to indicate absence of messages. Advanced compiler features, such as the clock calculi of L USTRE, S IGNAL [BCE+ 03], and AutoF OCUS [BBR+ 05], may be employed for both comfortable and consistent modeling of multiclock designs. The second feature, statically boundable time and memory consumption, follows from (1) the (frequent) restriction of individual processes to the finite-state, finite-iteration case, and (2) the restriction to length-preserving processes on the semantics level, so composition preserves finiteness. The third feature, determinism of computation and communication, implies among other things that the timing of message emission and consumption is fixed with respect to the logical timebase.
A sparring partner: UML-RT As the other subject of our comparison, we use the notation formerly known as “Real-Time UML”, now subsumed in the UML 2.0 standard [OMG05]. For the sake of argumentation, we use the semantics of state machines and communication realized in IBM’s Rational RealTime and Telelogic Tau tools as a reference implementation of the UML standard. These tools are both popular, and share many characteristics with other real-time UML tools evaluated in a case study [SRS+ 03]. The current UML standard itself [OMG05] is too vague about semantic issues for an adequate assessment. Because there is no “official” published semantics for the above tools either, a rough characterization of the semantics implemented by the respective simulators is considered here, which we’ll call singlequeue UML-RT. Singlequeue UML-RT uses no predefined time grid for message emission and consumption, giving it an “asynchronous” or “untimed” flavor. Messages emitted from individual objects, or capsules, are stored in a single1 global queue which is common to all capsules of the design. The FIFO property of the global queue effectively ensures the absence of race conditions on the simulation level: for any pair of messages, the mutual order of consumption is equal to the order of emission.
1.2
Three criteria for “good” models
According to [Sel03], the success of model-based engineering is bound to criteria such as abstraction, understandability, and predictiveness, among others. The author of [Sel03] claims that the popular UML 2.0 standard already provides adequate 1 There are UML-RT variants which use different priority levels for messages, resulting effectively in several global queues. For simplicity, we shall not consider this case here.
106
mechanisms with respect to these three criteria. Upon close inspection, however, we shall argue that at least the singlequeue approach for UML-RT has weaknesses with respect to abstraction, understandability, and predictiveness. This is especially true when concurrency and timing issues are considered. Abstraction and predictiveness Abstraction is useful if details not relevant for a certain purpose (e.g. making an implementation-independent design) can be hidden from an abstract representation. For fidelity of this representation, it is essential that the abstract model is also predictive, i.e. results or properties obtained on an abstract level will be preserved all the way to an implementation in an understandable way. In our opinion, this should be especially true for the behavior and timing of the model. The simulation semantics of singlequeue UML-RT models, however, is not guaranteed to correspond closely with the actual semantics of the implementation. Some examples: Races and unpredicted behavior. The simulation semantics of UML-RT is very costly to implement in distributed settings: it necessitates a distributed agreement on the global message order. Consequently, tools such as Rose RealTime or Telelogic Tau use a cheaper local-queue strategy for distributed implementation. The corresponding (non-deterministic) semantics on the implementation level introduces unpredicted behaviors to the implementation. For instance, in multithreaded implementations of UML-RT models, the relative order of subsequent messages, as seen by a receiver in the simulation, is not guaranteed to be preserved. As a consequence of such race conditions, the resulting behavior may be qualitatively different. For instance, the implemenation may reach a state that is not reachable in the “abstract” model, and vice versa. Unknown timing and memory consumption. The overall time and memory consumption of a model is undecidable in UML-RT, and may overrun any bound for some models. Tools and simulators usually make no attempt at predicting resource consumption, and a particular timing or scheduling order observed in the simulation may or may not correspond to the implementation. As a consequence, Dohmen and Somers [DS02] conclude that “UMLRT does not support the [..] implementation and verification of hard realtime constraints.” 2 In synchronous modeling, on the other hand, the timing of computations and message transit is clear from the semantics and an appropriate refinement mapping, and relative timing of message arrival is unambigously defined in the model. The 2 There are a number of academic contributions for real-time analysis of restricted UML models, such as [SPFR98], which typically rely on a fixed mapping of capsules/objects to tasks, and a fixed assignment of task priorities. It is questionable, however, whether this additional mapping information should be considered part of the “model”, as it would severely limit implementation-independence and portability of the design, especially in distributed settings.
107
model semantics yields obligations for the implementation, e.g. allowable execution times and message delays, that an implementor has to prove. Granted, the timing and concurrency assumptions inherent in synchronous models are rather strong, and may be in conflict with some platform-related considerations in costsensitive domains such as automotive. For instance, worst-case execution time estimation for modern processors is hard, and if estimates are made too conservative in order to safely implementing the synchronous semantics, the goal of having high processor utilization (and building a cost-effective system) is compromised. Understandability In order to be effective and understandable, modeling techniques should be as close to the domain as possible, while offering a clean and concise set of modeling concepts. In this context, we will take a quick look at two example issues: (discretized) continuous controller design, and communication/concurrency primitives. Continuous controller design. UML-RT is generally not considered strong in the design of continuous controllers, as the notation was originally conceived with very different applications in mind. Consequently, for the frequent case of continuous and discrete/continuous controller design, UML-RT is not very popular as a modeling notation. For the automotive sector, this fact is documented by the high market share of data-flow tools such as ASCET or S IMULINK (roughly 75%) vs. other tools reported in a recent market study [Han03]. Technically, the integration of block diagrams and data-flow algorithms for control laws with asynchronous UML-RT poses some issues, as control laws are inherently programmed with respect to a global, synchronous timebase. In comparison, synchronous programming is a suitable paradigm both for discrete controller modeling (e.g. S TATEMATE, E STEREL) and continuous controller modeling (e.g. S IMULINK). Communication/concurrency primitives. Being based on sequential programming languages, UML-RT offers several different constructs for concurrency, control flow, and communication. For instance, in UML-RT, two objects may call each other through synchronous method calls. Special kinds of objects (called “capsules” in UML-RT) may also call each other through asynchronous messages. These different options for communication and composition can be problematic: they typically encourage developers to encode implementation-specific considerations in the model. For instance, a developer may choose to model an client/server-style interaction between two objects as a synchronous method call. This seemingly minor decision ties the two objects together for the implemententation; once the decision has been made, replacing the synchronous call by a distributable transaction is usually very hard and time-consuming. Synchronous modeling languages, on the other hand, can usually restrict themselves to a very limited set of constructs for communication and com-
108
position. These constructs, such as messages, are typically implementationindependent. For instance, for communication, discrete-time S IMULINK only distinguishes between “signals” for data flows, and “triggers” for events. AutoF OCUS, and other synchronous languages, do not even distinguish event and data traffic.
2
Implementations of synchronous models
Because synthesis of implementations from behavioral models is steadily growing in importance, our second question is concerned with the implementation of synchronous models based on present-day platforms. Two aspects of synchronous program implementation will be briefly described. Firstly, we will discuss translation to sequential programs. An important issue in this respect is the synthesis of multitasking implementations, and the correct choice and configuration of inter-process communication (IPC). Secondly, for distributed implementation, a loose synchronization scheme for event-triggered bus systems such as CAN is described. Translation to sequential programs Singlethread sequential code generation for synchronous programs has been intensively studied [HRR91], and efficient code generation from synchronous models is already provided by numerous commercial code generators. A specific problem in this context, which has been addressed in the AutoMoDe project [BBR+ 05], is the mapping of synchronous data-flow designs in AutoF OCUS to the ASCET tool of ETAS. ASCET models, which basically combine graphical dataflow modeling with sequential language semantics, are used as a suitable intermediate format. The availability of highly optimized, production-quality code generation for automotive embedded platforms makes ASCET especially interesting in this respect. For the AutoF OCUS-ASCET translation, optimization issues like minimal allocation of heap variables for data-flow algorithms have been addressed. The resulting translation algorithm synthesizes optimized ASCET methods or processes from AutoF OCUS data-flow designs. Translation to multitasking implementations A specific issue that has been dealt with in the AutoMoDe project [BBR+ 05] is semantics-preserving inter-task communication for pre-emptive OSEK task sets using data consistency mechanisms3 . In wait-free IPC, the operating system uses a double-buffering technique to ensure that a reader task will have consistent input values for the duration of its activation. Using wait-free IPC, the implementation scheme developed in AutoMoDe can implement a zero-delay or unit-delay communication link specified 3 There are a number of inter-task communication primitives known from the literature which ensure atomic and consistent accesses to shared data. For control law computations in resource-restricted applications, wait-free IPC has emerged as the mechanism of choice [PMSB96].
109
in the synchronous AutoF OCUS model. The kind of implemented delay depends on the relation of the sender and receiver activation frequency. Translation to distributed implementations In order to implement a synchronous design, distributed processes need to match received messages to time indices from a common time base. Present-day bus systems such as Controller Area Network (CAN) are not designed for providing a common, fault-tolerant time base. Furthermore, message latencies be locally determined. [RB04] presents an implementation scheme for synchronous programs based on event-triggered bus system such as CAN. The technique guarantees semantics-preserving implementation under given operational conditions. The implementation scheme is based on a simple, fault tolerant synchronization layer, which uses application data traffic to keep nodes loosely synchronized. For time-triggered distributed architectures such as TTA or the static segment of FlexRay, the deterministic assumptions of the model are naturally reflected by the platform. [CCM+ 03] demonstrates how designs in the synchronous tool SCADE can be mapped to such architectures.
3
Conclusion, and open issues
The synchronous programming model provides a precise basis for specifying behavior and timing of distributable models. For embedded controller design, comfortable and understandable notations are available that support both discrete and continuous controller design. For predicting behavioral properties of the final implementation, the synchronous approach has some compelling advantages over other popular approaches, such as singlequeue UML-RT. Despite the progress in implementation techniques, the inherent conflict of the strong timing and concurrency assumptions in synchronous models with industrial needs necessitates further research. One could envision “soft” conformance relations for synchronous designs, which allow to weaken some of the inherent assumptions in a well-defined manner for implementing systems. A first step in this direction are GALS (Globally Asynchronous, Locally Synchronous) techniques for synchronous designs, which are mainly suited for discrete controllers [Ben01], or related loosely coupled schemes such as [RB04]. Soft conformance techniques for continuous and mixed discrete/controllers would be an important contribution to the practical applicability of the synchronous approach.
References [BBR+ 05]
110
A. Bauer, M. Broy, J. Romberg, Bernhard Schätz, P. Braun, U. Freund, N. Mata, R. Sandner, and D. Ziegenbein. AutoMoDe: Notations, Methods, and Tools for
Model-Based Development of Automotive Software. In Proceedings of the 2005 SAE World Congress, Detroit, MI, 2005. Society of Automotive Engineers. [BCE+ 03] A. Benveniste, P. Caspi, S. Edwards, N. Halbwachs, P. Le Guernic, and R. De Simone. The Synchronous Languages Twelve Years Later. Proceedings of the IEEE, 2003. [Ben01]
A. Benveniste. Some synchronization issues when designing embedded systems from components. In Proceedings of 2001 Workshop on Embedded Software, EMSOFT’01, volume 2211 of LNCS, pages 32–49, 2001.
[CCM+ 03] P. Caspi, A. Curic, A. Maignan, C. Sofronis, S. Tripakis, and P. Niebert. From Simulink to SCADE/Lustre to TTA: A layered approach for distributed embedded applications. In Proceedings of the 2003 ACM SIGPLAN conference on Languages, Compilers, and Tools for Embedded Systems, pages 153–162. ACM Press, 2003. [DS02]
L.A.J. Dohmen and L.J. Somers. Experiences and Lessons Learned Using UMLRT to Develop Embedded Printer Software. In M. Oivo and S. Komi-Sirviö, editors, Proceedings of PROFES 2002, volume 2559 of LNCS, pages 475–484, 2002.
[Han03]
Software Tools Heading Mainstream. The Hansen Report on Automotive Electronics, July/August 2003.
[HRR91]
N. Halbwachs, P. Raymond, and C. Ratel. Generating Efficient Code from DataFlow Programs. In Proceedings of the Third International Symposium on Programming Language Implementation and Logic Programming, Passau, Germany, 1991. Springer Verlag.
[OMG05]
Object Management Group. Unified Modeling Language (UML) Superstructure, August 2005. Version 2.0 formal/05-07-04.
[PMSB96] S. Poledna, Th. Mocken, J. Schiemann, and Th. Beck. ERCOS: An Operating System for Automotive Applications. Research Report 21/1996, Technische Universität Wien, Institut für Technische Informatik, 1996. [RB04]
J. Romberg and A. Bauer. Loose Synchronization of Event-Triggered Networks for Distribution of Synchronous Programs. In Proceedings 4th ACM International Conference on Embedded Software, Pisa, Italy, September 2004.
[Sel03]
B. Selic. The Pragmatics of Model-Driven Development. 20(5):19–25, 2003.
[SPFR98]
M. Saksena, A. Ptak, P. Freedman, and P. Rodziewicz. Schedulability analysis for automated implementations of real-time object-oriented models. In IEEE Real-Time Systems Symposium, 1998.
[SRS+ 03]
B. Schätz, J. Romberg, M. Strecker, O. Slotosch, and K. Spies. Modeling Embedded Software: State of the Art and Beyond. In Proceedings of ICSSEA 2003 16th International Conference on Software and Systems Engineering and their Applications, 2003.
IEEE Software,
111
112
Testing of Embedded Control Systems with Continous Signals Ina Schieferdecker Technical University Berlin Fraunhofer FOKUS [email protected]
Jürgen Großmann DaimlerChrysler AG [email protected]
Abstract The systematic testing approaches developed within the telecommunication domain for conformance and interoperability testing of communication protocols have been extended and broadened to allow the testing of local and distributed, reactive and proactive systems in further domains such as Internet, IT, control systems in automotive, railways, avionics and alike. With the application of these testing principles it became apparent that the testing of systems with continuous systems is different to that of discrete systems. Although every continuous signal can be discretized by sampling methods (and hence mapped to the discrete signal paradigm), abstraction and performance issues in this setting become critical. This paper investigates the different options to support tests of embedded control systems in the framework of TTCN-3.
1
Introduction
Control systems in real-time and safety-critical environments are hybrid: they use both discrete signals for communication and coordination between system components and continuous signals for monitoring and controlling their environment via sensor and actuators. A test technology for control systems needs to be able to analyze the functional and timed behaviour of these systems being characterized by a set of discrete and continuous signals and their relations. While the testing of discrete controls is well understood and available via the standardized test technology TTCN-3[9], the specification-based testing of continuous control and of the relation between the discrete and the continuous control is not. A variety of test methods exist, which address different aspects – however, the concepts have not yet been consolidated. This is also shown by the fact that consortia like AutoSar, ESA or the MOST Forum are looking for an appropriate test technology. Appropriateness of a test technology is to be understood from different perspectives: 1.
The adequateness of testing concepts and their syntactical presentation (textual or graphical) to the user
2.
The applicability to various elements of the control systems, e.g. to discrete, continuous, local and distributed components
3.
The applicability to various target systems, e.g. application components, communication components, control components, etc.
113
4.
The portability to various target platforms, e.g. to platforms of the component providers and component integrators as well as to platforms of the test device vendors
5.
The usability for different development approaches, e.g. HIL, SIL, MIL, etc.
6.
The usability for different testing kinds, e.g. component level tests, system level tests, acceptance level tests, functional and non-functional tests, regression tests
TTCN-3 as such addresses already the majority of these aspects: it has constructs for •
message-based and procedure-based communication (making it applicable for asynchronous, decoupled and synchronous systems in client-server or peer-to-peer architectures),
•
detailed test behaviours which allow to describe sequential, alternative, looping or parallel testing scenarios
•
local and distributed test setups, so that physically distributed and/or heterogeneous systems with different access technologies can be tested
•
an open and adaptable architecture to customize an executable test system to various target systems and target test platforms
•
different presentation formats to highlight specific aspects of the test definitions or make it better fit to an application domain
•
accessing different data formats of the system/component to be tested
It is a platform-independent, universal and powerful test specification technology, which allows selecting the abstraction level for the test specifications – from very abstract to very detailed, technical test specifications. It is also a test implementation language, which precisely define how to convert the abstract test specifications into executable tests. Also the tracing and evaluation of test results allows different presentation formats for textual and graphical logs. However, TTCN-3 lacks continuous signals as a language construct – which limits the power of TTCN-3 with respect to the adequateness of test concepts, the applicability to various target systems and the usability for different development approaches in the context of control systems. This paper discusses various options for testing continuous controls and analyses the use/extension of TTCN-3 for testing automotive control systems, in particular. The paper is structured as follows: Section 2 reviews current approaches of testing control systems in the automotive domain. Section 3 discusses the basic concepts for testing continuous controls. Section 4 analyses how TTCN-3 can be used and extended to address the testing of continuous controls. Section 5 presents an example. Conclusions finish the paper.
114
2
Related Work
Established test tools in automotive from e.g. dSPACE [2], Vector[3] etc. are highly specialised for the automotive domain and come usually together with a test scripting approach which directly integrates with the respective test device. However, all these test definitions special to the test device and by that not portable to other platforms and not exchangeable. Some, e.g. ETAS [4], have already adopted TTCN-3, however, have taken it as it is without analysing further if the specific needs of the automotive domain are better to be reflected in the language itself. Hence, other platform independent approaches have been developed such as CTE [5], MTEST [6], and TPT [1]. CTE supports the classification tree method for high level test designs, which are applicable to partition tests according to structural or ∈ O with o =

Heat map generated from DNA microarray data reflecting gene expression values in several conditions

A heat map, atop a color bathymetric map, indicating the probable location of missing Malaysia Airlines Flight 370 based on a Bayesian method analysis of possible flight paths of the aircraft.^[4]

Retrieved from 'https://en.wikipedia.org/w/index.php?title=Heat_map&oldid=907628661'