Modellbasierte Entwicklung eingebetteter Systeme VI.
Transcrição
Modellbasierte Entwicklung eingebetteter Systeme VI.
MBEES 2010 MBEES 2010 MBEES 2010 MBEES 2010 MBEES 2010 Tagungsband des Dagstuhl-Workshops Modellbasierte Entwicklung eingebetteter Systeme VI Holger Giese Michaela Huhn Jan Philipps Bernhard Schätz Tagungsband Dagstuhl-Workshop MBEES: Modellbasierte Entwicklung eingebetteter Systeme VI Model-Based Development of Embedded Systems 03.02.2010 – 05.02.2010 fortiss GmbH Guerickestr. 25 80805 München Organisationskomitee Holger Giese, Univ. Potsdam Michaela Huhn, TU Braunschweig Jan Philipps, Validas AG Bernhard Schätz, fortiss GmbH Programmkomitee Dr. Mirko Conrad, The Mathworks GmbH Prof. Dr. Holger Giese, Hasso-‐Plattner-‐Institut an der Universität Potsdam Dr. Michaela Huhn, TU Braunschweig Dr. Hardi Hungar, OFFIS Prof. Dr. Stefan Kowalewski, RWTH Aachen Ulrich Nickel, Hella KGaA Hueck&Co Dr. Oliver Niggemann, dSPACE GmbH Jan Philipps, Validas AG Dr. Ralf Pinger, Siemens AG Prof. Dr. Bernhard Rumpe, RWTH Aachen Dr. Bernhard Schätz, TU München Wladimir Schamai, EADS Prof Dr.-‐Ing. Birgit Vogel-‐Heuser, TU München Prof. Dr. Albert Zündorf, Universität Kassel Inhaltsverzeichnis Ein Framework zur automatisierten Ermittlung der Modellqualität bei eingebetteten Systemen Jan Scheible 1 ProMoSA - Probabilistic Models for Safety Analysis Frank Ortmeier, Matthias Güdemann 7 Towards Architectural Programming of Embedded Systems Arne Haber, Jan O. Ringert, Bernhard Rumpe 13 Modell-zu-Metamodell-Transformationen zur Entwicklung von komponentenbasierten Systemen Christian Buckl, Gerd Kainz, Stephan Sommer, Alois Knoll Model-based Decentralised Management of Product Flow Paths Gustavo Quirós, Ulrich Epple 23 33 Model-based Development of Automation Systems Oliver Niggemann1, Alexander Maier Jürgen Jasperneite 45 Static and Dynamic Boundary Value Analysis Stephan Weißleder 55 Test Case Integration: From Components to Systems Bernhard Schätz, Christian Pfaller 65 Reverse Engineering vernetzter automotiver Softwaresysteme Stefan Henkler, Jan Meyer, Wilhelm Schäfer, Ulrich Nickel 77 Variability and Evolution in Model-based Engineering of Embedded Systems Goetz Botterweck, Andreas Polzer, Stefan Kowalewski 87 Some Observations on SCADE Model Clones Michaela Huhn, Dirk Scharff 97 Usability-Evaluation von modellbasiertem Engineering in der Automatisierungstechnik – Ergebnisse und Kriterien Birgit Vogel-Heuser 107 Qualifying Software Tools According to ISO 26262 Mirko Conrad, Patrick Munier, Frank Rauch 117 Using Model-Based Design in an IEC 62304-Compliant Software Development Process David Hoadley 129 Complete and Virtual System Models for System Development Gert Döhmen, Dietmar Sander, Andreas Lehmann 132 Dagstuhl-Workshop MBEES: Modellbasierte Entwicklung eingebetteter Systeme VI (Model-Based Development of Embedded Systems) Das Schlagwort der modellgetriebenen Entwicklung ist inzwischen bei der Ent-‐ wicklung eingebetteter Software allgegenwärtig. Die Generierung von ablauffä-‐ higer, einbettbarer Software aus ausführbaren Modellen steht heute im Zentrum der industriellen Anwendung; doch auch andere Anwendungen von Modellen, die intensiv in der Forschung und Entwicklung untersucht wurden, setzen sich in der Praxis zunehmend durch: Umgebungs-‐ und Plattformmodelle – also der elek-‐ tronischen, elektrischen und auch mechanischen Anteile des Systems ebenso wie die vom System kontrollierten physikalischen und betrieblichen Abläufe – zur Validierung und Verifikation von eingebetteten Systemen, Testmodelle – also insbesondere Beschreibungen der wesentlichen Funktionen eines Gesamtsy-‐ stems – zur Unterstützung der Absicherungsprozesse, Architekturmodelle zur Integration von Systemteilen, um nur einige besonders prominente Beispiele zu nennen. Weiterhin werden Modelle zum Entwurf und zur Dokumentation von Systemen genutzt, aber auch erste Ansätze zum Einsatz bei Analyse, Betrieb, Wartung und Diagnose zeigen sich. Der Stand der Technik nähert sich deutlich der 2005 im ersten Workshop angedachten Durchgängigkeit von Methoden und Werkzeugen eines modellbasierten Entwicklungsprozesses. Trotzdem sind eine Reihe von Fragen insbesondere jenseits des funktionellen Entwurfs der eingebetteter Sy-‐ steme noch zu lösen, wie etwa die Erweiterung von Modellen um sicherheitsre-‐ levante Aspekte wie Zuverlässigkeit, die Ableitung von Diagnosemodellen und Sicherheitsnachweise. Wie in den Jahren zuvor, bestätigen auch dieses Jahr die Beiträge die Grundthese der MBEES-‐Workshop-‐Reihe, dass sich die Modelle, die in einem modellbasier-‐ ten Entwicklungsprozess eingesetzt werden, an der Problem-‐ anstatt der Lö-‐ sungsdomäne orientieren müssen. Diese strikte Zweckorientierung zieht zwei Aspekte bei einer Modellauswahl nach sich: einerseits die Bereitstellung anwen-‐ dungsorientierter Modelle (z.B. MATLAB/Simulinkartige, Statechart-‐artige) und ihrer zugehörigen konzeptuellen (z.B. Komponenten, Nachrichten, Zustände) und semantischen Aspekte (z.B. synchroner Datenfluss, ereignisgesteuerte Kommunikation); andererseits die Abstimmung auf die jeweilige Entwicklungs-‐ phase, mit Modellen von der Anwendungsanalyse (z.B. Beispielszenarien, Schnittstellenmodelle) bis hin zur Implementierung (z.B. Bus-‐ oder Task-‐ Schedules, Implementierungstypen). Wichtiger Aspekt ist dabei insbesondere die Abstimmung der einzelnen Modelle und ihrer zugeordneten Sichten und Ab-‐ straktionen für eine durchgängige modellbasierte Entwicklung. Durch die zunehmende Durchdringung der Entwicklung eingebetteter System mittels des modellbasierten Ansatzes rücken Fragen in den Vordergrund, die sich mit dem gesamten Produktlebenszyklus beschäftigen: Dies sind einerseits mit Fragestellungen zu vor-‐ und nachgelagerten Entwicklungstätigkeiten, wie der Architekturentwicklung und -‐optimierung oder der Systemintegration, sowie andererseits Themen, die sich mit der Evolution von Systemen und der Qualität von Modellen selbst beschäftigen. In bewährter Tradition stellen die in diesem Tagungsband zusammengefassten Papiere sowohl gesicherte Ergebnisse, als auch Work-‐In-‐Progress, industrielle Erfahrungen und innovative Ideen aus die-‐ sem Bereich zusammen und erreichen damit eine interessante Mischung theore-‐ tischer Grundlagen und praxisbezogener Anwendung. Genau wie bei den ersten fünf, in den Jahren 2005 bis 2009 erfolgreich durch-‐ geführten Workshops sind damit wesentliche Ziele dieses Workshops erreicht: -‐ Austausch über Probleme und existierende Ansätze zwischen den unter-‐ schiedlichen Disziplinen (insbesondere Elektro-‐ und Informationstechnik, Ma-‐ schinenwesen/Mechatronik und Informatik) -‐ Austausch über relevante Probleme in der Anwendung/Industrie und existie-‐ rende 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 Ent-‐ wicklung eingebetteter Systeme, GI-‐FG Echtzeitprogrammierung, MDA Initiative der OMG) Die Themengebiete, für die dieser Workshop gedacht ist, sind fachlich sehr gut abgedeckt. Die Beiträge adressieren verschiedenste Aspekte modellbasierter Entwicklung eingebetteter Softwaresysteme, unter anderem: -‐ Domänenspezifische Ansätze zur Modellierung von Systemen -‐ Modelle in der architekturzentrierten Entwicklung -‐ Bewertung der Qualität von Modellen -‐ Modellbasierte Validierung, Verifikation und Diagnose -‐ Evolution von Modellen -‐ Modelleinsatz in der standardkonformen Entwicklung Das Organisationskomitee ist der Meinung, dass mit den Teilnehmern aus Indu-‐ strie, Werkzeugherstellern und der Wissenschaft die bereits seit 2005 erfolgte Community-‐Bildung erfolgreich weitergeführt wurde Der nunmehr sechste MBEES Workshop belegt, dass eine solide Basis zur Weiterentwicklung des Themas modellbasierter Entwicklung eingebetteter Systeme existiert. Die Durchführung eines erfolgreichen Workshops ist ohne vielfache Unter-‐ stützung nicht möglich. Wir danken daher den Mitarbeitern von Schloss Dagstuhl und natürlich unseren Sponsoren. Schloss Dagstuhl im Februar 2010, Das Organisationskomitee: Holger Giese, Hasso-‐Plattner-‐Institut an der Universität Potsdam Michaela Huhn, TU Braunschweig Jan Philipps, Validas AG Bernhard Schätz, fortiss GmbH Mit Unterstützung von Dagmar Koss, fortiss GmbH 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. Schloss Dagstuhl wurde 1760 von dem damals regierenden Fürsten Graf Anton von Öttingen-SoeternHohenbaldern erbaut. 1989 erwarb das Saarland das Schloss zur Errichtung des Internationalen Begegnungsund 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. Die fortiss GmbH ist ein Innovationszentrum für softwareintensive Systeme in Form eines An-Instituts der Technischen Universität München. Als Forschungs- und Transferinstitut liegt der Fokus auf der angewandten Forschung zukünftiger Software- und Systemlösungen mit Schwerpunkt eingebettete und verteilte Systeme sowie Informationssysteme. Bearbeitete Themenfelder sind dabei unter anderem Modellierungstheorien einschließlich funktionaler, zeitlicher und nicht-funktionaler Aspekte, Werkzeugunterstützung zur Erstellung von dömanenspezifischen, modellbasierten Entwicklungswerkzeugen, Architekturen insbesondere für langlebige und sicherheitskritische Systeme, sowie modellbasierte Anforderunganalyse und Qualitätsicherung. Lösungen werden dabei vorwiegend in den Anwendungsfeldern Automobilindustrie, Luft- und Raumfahrt, Automatisierungstechnik, Medizintechnik, Kommunikationstechnik, öffentliche Verwaltung und Gesundheitswirtschaft erarbeitet. Die Validas AG ist ein Beratungsunternehmen im Bereich Software-Engineering für eingebettete Systeme. Die Validas AG bietet Unterstützung in allen Entwicklungsphasen, vom Requirements- Engineering bis zum Abnahmetest. Die Auswahl und Einführung qualitätssteigender Maßnahmen folgt dabei den Leitlinien modellbasierter Entwicklung, durchgängiger Automatisierung und wissenschaftlicher Grundlagen. Besonderer Fokus der Arbeit des Fachgebiets "Systemanalyse und Modellierung" des Hasso Plattner Instituts liegt im Bereich der modellgetriebenen Softwareentwicklung für software- intensive Systeme. Dies umfasst die UML- basierte Spezifikation von flexiblen Systemen mit Mustern und Komponenten, Ansätze zur formalen Verifikation dieser Modelle und Ansätze zur Synthese von Modellen. Darüber hinaus werden Transformationen von Modellen, Konzepte zur Codegenerierung für Struktur und Verhalten für Modelle und allgemein die Problematik der Integration von Modellen bei der modellgetriebenen Softwareentwicklung betrachtet. Ein Framework zur automatisierten Ermittlung der Modellqualität bei eingebetteten Systemen Jan Scheible ([email protected]) Daimler AG - Group Research and Advanced Engineering Abstract: Die Modelle, die in der Automobilindustrie zur Modellbasierten Softwareentwicklung von eingebetteten Systemen verwendet werden, werden immer größer und komplexer. Zwar findet die Modellbasierte Entwicklung auf einer höheren Abstraktionsebene als die herkömmliche, handcodierte Softwareentwicklung statt, jedoch resultieren im Modell gemachte Fehler direkt in Fehler im Quellcode. Dieses Research Abstract stellt einen Ansatz zur automatisierten Ermittlung der Modellqualität von Matlab Simulink-Modellen vor. Dadurch wird nicht nur eine detaillierte Aussage über die momentane Qualität der Modelle ermöglicht, sondern auch eine Verbesserung der Modellqualität durch Befolgen der abgeleiteten Handlungsempfehlungen erreicht. 1 Problemstellung In der Automobilindustrie wird in den letzten Jahren verstärkt auf die Modellbasierte Softwareentwicklung von eingebetteten Systemen gesetzt (vergleiche [KCFG05]). Die Modelle nehmen dabei den Stellenwert ein, den zuvor der handgeschriebene Quellcode eingenommen hat. Sie sind das zentrale Entwicklungsartefakt und werden (über die Codegenerierung und Compilierung) direkt auf den eingebetteten Systemen ausgeführt. Ein Werkzeug zur Modellbasierten Entwicklung ist z. B. Matlab Simulink mit dSPACE Targetlink. Die Modelle bestehen aus Blöcken, welche durch Signale verbunden werden. Mittels Subsystemen werden die Modelle hierarchisch gegliedert. Der Umfang der Modelle steigt stetig. So hat momentan ein großes Modell typischerweise ca. 15.000 Blöcke, 700 Subsysteme und eine Subsystemhierarchie mit 16 Ebenen. Außerdem geben Werkzeuge wie Matlab Simulink den Entwicklern sehr viele Freiheiten. Deshalb wird in [CD06] vorgeschlagen, den erlaubten Sprachumfang für sicherheitsrelevante Systeme einzuschränken. Sowohl die großen Umfänge als auch die Freiheiten der Entwickler, die sich aus der herkömmlichen und zusätzlich aus der Modellbasierten Softwareentwicklung ergeben, führen zu vielen potentiellen Fehlerquellen. Daher ist der Ansatz dieses Beitrags die automatisierte Ermittlung der Modellqualität anhand von Kriterien, welche qualitativ hochwertige Modelle auszeichnen. Die Qualitätskriterien werden dabei in einem Qualitätsmodell strukturiert. Die Untersuchung der Modelle auf die Erfüllung der Qualitätskriterien wird mit Hilfe von Modellmetriken durchgeführt. Aus dem Qualitätsmodell und den Informationen der Modellmetriken wird die Modellqualitätsbewertung gebildet. Falls ein Modell nicht die gewünschte Qualität hat, kann durch 1 das Befolgen der Handlungsempfehlungen die Qualität des Modells verbessert werden. Um eine Erweiterbarkeit und projektspezifische Anpassbarkeit zu erreichen, wird im Rahmen dieser Arbeit schließlich ein Framework definiert. Unterstützt wird der Ansatz z. B. durch Fieber et. al [FHR08]. Sie beschreiben die automatisierte Ermittlung der Modellqualität als nächsten Schritt, da nur so der große Umfang bewältigt werden kann. Da Modelle das zentrale Artefakt der Modellbasierten Softwareentwicklung sind, wird außerdem in [FHR08] und [MA07] die Hypothese unterstützt, dass die Softwarequalität direkt von der Modellqualität abhängig ist. Deshalb ist davon auszugehen, dass qualitativ hochwertige Modelle auch zu qualitativ hochwertiger Software führen. Des Weiteren ermöglicht der Ansatz der automatisierten Qualitätsermittlung sowohl das Ermitteln eines aktuellen Ist-Stands, um die aktuelle Modellqualität einschätzen zu können, als auch eine abschließende Qualitätsbewertung bei Abgabe eines Modells. 2 Lösungsidee Modellqualität Die Qualität eines Modells wird bewertet, indem geprüft wird, ob das Modell Kriterien mit einem positiven Einfluss auf gewünschte Faktoren wie z. B. Wartbarkeit, Lesbarkeit oder Robustheit erfüllt. Daher hat ein Modell, das alle Kriterien erfüllt, eine hohe Modellqualität. Für den Ansatz dieses Beitrags sind alle Kriterien von Interesse, die einen Rückschluss auf gewünschte Faktoren und somit die Modellqualität zulassen. Qualitätsmodell Zur Strukturierung der Kriterien wird ein Qualitätsmodell mit einem Aufbau ähnlich [CM78] verwendet. Dazu werden Faktoren definiert, welche Einfluss auf die Modellqualität haben. Die Erfüllung der Faktoren wird an Hand von den Kriterien festgemacht. Inwieweit die Kriterien erfüllt sind, wird mit Hilfe von Metriken gemessen. Zusätzlich besitzt jedes Kriterium eine Beschreibung, wie es sich auf seinen übergeordneten Qualitätsfaktor auswirkt. Dadurch wird der Zusammenhang zwischen Faktoren und Kriterien explizit dokumentiert. Das Qualitätsmodell wird im Folgenden FCM-Modell (Factors-Criteria-Metrics-Modell) genannt. Modellqualität Komplexität Wartbarkeit Lesbarkeit Busse mit zu vielen Signalen deuten auf zu breite Schnittstellen hin zu viele verschiedene Abtastraten erschweren das Verständnis wenig Signalüberkreuzungen erleichtern das Verständnis wenige Skalierungen am Ein- und Ausgang verhindern Skalierungsfehler DD-Einträge zur Portdefinition erzwingen eine konsistente Verwendung von Datentypen Kriterien Vermeidung zu breiter Busse Vermeidung zu vieler Abtastraten Vermeidung von Überkreuzungen Korrekte Skalierung Verwendung des Data Dictionaries Metriken #Signale pro Bus #Abtastraten #Signalüberkreuzungen #Skalierungen #Ports ohne DD-Eintrag Faktoren Codegenerierbarkeit Abbildung 1: Auszug aus dem FCM-Modell Abbildung 1 zeigt einen Auszug aus dem FCM-Modell zur Modellqualitätsbewertung. Bisher enthält das FCM-Modell 10 Faktoren, 26 Kriterien und 43 Metriken. Die Fakto- 2 ren ähneln denen in [CM78], sind aber um neue, modellspezifische Faktoren wie z. B. Codegenerierbarkeit (vergleiche Abbildung 1) erweitert worden. Wenn beispielsweise das Kriterium „Verwendung des Data Dictionaries“ verletzt wird, hat das einen negativen Einfluss auf den Faktor Codegenerierbarkeit, da z. B. der Datentyp der betroffenen Ports nicht mehr zentral an einer Stelle änderbar ist. Dies ist ein Indikator für unsaubere Modellierung, führt jedoch nicht zwingend zu Fehlern. Daher kann solch eine Verletzung einerseits als Anlass zur Korrektur bei einer Ist-Stand-Ermittlung dienen, anderseits kann sie unter Umständen, z. B. aus Zeitmangel ignoriert werden. Modellmetriken Im Gegensatz zur Ermittlung der Softwarequalität in [CM78] messen die Metriken bei der Ermittlung der Modellqualität nicht auf dem Quellcode, sondern auf dem Simulink-Modell. Die Aufgabe der Metriken ist, die Erfüllung von Qualitätskriterien zu messen, daher wird folgende Definition aus [BBL76] übernommen: „The term ’metric’ is defined as a measure of extent or degree to which a product (...) possesses and exhibits a certain (quality) characteristic.“ Eingeordnet nach den Eigenschaften von [Mil99] sind die Metriken sowohl direkt als auch indirekt. Direkte Metriken messen auf dem Modell, indirekte verwenden eine externe Datenquelle, welche aufbereitete Informationen über das Modell bereitstellt. Ein Beispiel für eine externe Datenquelle sind die Ergebnisse eines Prüfers für Modellierungsrichtlinien wie MXAM von MES, welche Rückschlüsse auf die Standardkonformität eines Modells zulassen. Die Metriken können außerdem primitiv (z. B. „#Blöcke“, um abzuschätzen, ob der Umfang des Modells gerechtfertigt ist) oder berechnet (z. B. „#Blöcke pro Subsystem“, um auf zu große Subsysteme schließen zu können) sein. Zusätzlich müssen die Messwerte der Metriken mindestens auf einer Ordinalskala liegen. Zusätzlich gibt jede Metrik einen erlaubten Minimal- und Maximalwert für ihre Messergebnisse vor. Sie messen entweder einen Messwert pro Subsystem oder einen Messwert für das gesamte Modell. Jede Metrik hat einen Typ, welcher bestimmt, wie die Messwerte erhoben werden. Für Metriken vom Typ atomar wird ein einzelner Messwert pro Modell gemessen. Bei Metriken vom Typ akkumulierend oder arithmetisches Mittel hingegen wird ein Messwert pro Subsystem gemessen und aufaddiert. Beim Typ arithmetisches Mittel wird zusätzlich noch durch die Anzahl der Subsysteme geteilt. Schließlich besitzt jede Metrik eine Priorität (1 = normal, 2 = hoch). Modellqualitätsbewertung Die Messwerte der Metriken und das FCM-Modell bilden die Grundlage der Modellqualitätsbewertung. In [CM78] werden dazu alle Messwerte der Metriken normalisiert und dann eine gewichtete Summe für jeden Qualitätsfaktor berechnet. In diesem Beitrag werden die Messwerte dadurch normiert, dass sie in Bezug zur Problemgröße gesetzt werden. Wenn beispielsweise der Umfang der Spezifikation als Problemgröße verwendet wird, dann kann der Bezug z. B. als kontinuierliche Funktion wie Messwertnormiert = Messwert/Problemgröße formuliert oder durch die Einteilung in diskrete Klassen (z. B. kleines, mittleres oder großes System) hergestellt werden. Zur Berechnung der endgültigen Modellqualität wird jede Metrik gewichtet. Das Gewicht 3 ist 0, falls der skalierte Messwert zwischen den von der Metrik vorgegebenen Grenzen liegt. Andernfalls entspricht das Gewicht der Priorität der Metrik. Pro Qualitätsfaktor werden alle Gewichte addiert und durch die Summe der Prioritäten geteilt. Das Ergebnis ist eine Prozentzahl pro Qualitätsfaktor, welche angibt, zu wie viel Prozent die Kriterien des Qualitätsfaktors nicht erfüllt sind. Somit besteht eine Modellqualitätsbewertung aus einem n-Tupel, wobei n die Anzahl der Qualitätsfaktoren ist. Handlungsempfehlung Um die Modellqualität auf Basis der Modellqualitätsbewertung verbessern zu können, besitzt jede Metrik eine Handlungsempfehlung. Die Handlungsempfehlung gibt an, wie die Modellqualität verbessert werden kann, wenn der Messwert einer Metrik außerhalb der vorgegebenen Grenzen liegt. Bei indirekten Metriken, die externe Datenquellen verwenden, wird zur detaillierten Auswertung auf die externe Datenquelle verwiesen. Die gesamte Menge der Handlungsempfehlungen bildet eine Wissensdatenbank. Framework Das FCM-Modell ist nicht monolithisch, sondern wird durch verschiedene Qualitätsaspekte gebildet, die in einem Framework verwaltet werden. Dadurch können einzelne Qualitätsaspekte an- oder abgeschaltet sowie neue Qualitätsaspekte hinzugefügt werden. Ein Qualitätsaspekt besteht aus einem Teilbaum mit Faktoren, Kriterien und Metriken. Qualitätsaspekte sind z. B. die Codegenerierung mit Targetlink oder die Einhaltung von Modellierungsrichtlinien. Abbildung 2 zeigt, wie Qualitätsaspekte zu einem FCM-Modell vereinigt werden. Bei der Vereinigung werden Knoten mit gleichen Namen als identisch angesehen. Modellqualität Kriterium 1 Faktor 1 U Aspekt 2 Aspekt 1 Faktor 1 Metrik 1 Faktor 1 Kriterium 1 Kriterium 2 Metrik 2 Metrik 3 = Kriterium 1 Metrik 1 Metrik 2 Kriterium 2 Metrik 3 Abbildung 2: Schematische Darstellung der Vereinigung zweier Aspekte Prototyp Ein in Java implementierter Prototyp setzt bereits das Framework um und enthält erste einfache Metriken. Die Anbindung an Matlab Simulink wird durch die Nutzung des Simulink Parsers der TUM realisiert. Auch die Visualisierung der Messwerte mit ihren Minimal- und Maximalwerten in einem Kiviat-Diagramm (vergleiche [Dra96]) und eine Visualisierung der Modellqualitätsbewertung wurde bereits prototypisch umgesetzt. 3 Verwandte Arbeiten Fey und Stürmer führen in [FS07] folgende Maßnahmen zur Qualitätssicherung von Simulink-Modellen auf: Modellbasiertes Testen, Modell-Review, Code-Review und stati- 4 sche Code-Analyse. Der Ansatz dieses Beitrags kann als statische Modellanalyse eingeordnet werden, da die Analyse direkt auf dem Modell stattfindet und das Modell dabei nicht ausgeführt wird. Zusätzlich zu den aufgeführten Maßnahmen hat sich das Aufstellen und Prüfen von Modellierungsrichtlinien als Standard etabliert [SDP08, WDTG09]. Allerdings lassen sich zum einen nur ein Teil der Modellierungsrichtlinien automatisiert prüfen und zum anderen können viele Qualitätskriterien, wie z. B. eine sinnvolle Aufteilung in Subsysteme, nicht als formale Richtlinien definiert werden. In der Automobilindustrie sind die MAAB-Richtlinien [MAA07] weit verbreitetet. Sie geben herstellerunabhängige Regeln vor, um den Austausch von Modellen zu vereinfachen und die Anzahl der potentiellen Fehler zu reduzieren. Deissenboeck et al. [DWP+ 07] stellen ein Qualitätsmodell für die Wartbarkeit auf. Sie modellieren nicht nur die Qualitätskriterien, sondern auch ihren Einfluss auf die nötigen Aktivitäten. In einer Fallstudie erweitern sie ihr Qualitätsmodell um Simulink-spezifische Kriterien und Aktivitäten. Automatisierte Qualitätsbewertung steht nicht in ihrem Fokus und das Qualitätsmodell konzentriert sich auf die Wartbarkeit. Die Aktivitäten sind vergleichbar mit den Handlungsempfehlungen im Ansatz dieses Beitrags. Bobkowska stellt in [Bob09] einen generischen Ansatz vor, der Qualitätskriterien und die Wahl der Methode zur Bewertung berücksichtigt. In einer Fallstudie zur Vorhersage der Qualität eines Softwareprojekts, welches UML verwendet, wird von ihr ein FCM-Modell nach Cavano und McCall [CM78] verwendet. Ein mit dem Ansatz dieses Beitrags vergleichbares Framework für UML-Modelle beschreiben Lange und Chaudron [LC05]. Sie unterscheiden zwischen Entwicklung und Wartung, da bei UML-Modellen in den jeweiligen Phasen andere Qualitätskriterien relevant sind. Sie verwenden zum Großteil OO-Metriken und nur einige modellspezifische Metriken wie z. B. Anzahl der überkreuzenden Linien. 4 Zusammenfassung und Ausblick In diesem Research Abstract wurde ein Ansatz zur automatisierten Qualitätsbewertung anhand von Qualitätskriterien vorgestellt. Die Qualitätskriterien wurden in einem Qualitätsmodell in den Kontext der Modellqualität gesetzt. Die Erfüllung der Kriterien wird mit Hilfe von Modellmetriken gemessen. Handlungsempfehlungen für nicht erfüllte Qualitätskriterien bilden eine Wissensdatenbank zur qualitätsorientierten Modellierung. Abschließend wurde gezeigt, wie verschiedene Qualitätsaspekte ein Framework zur projektspezifischen Anpassbarkeit und Erweiterbarkeit bilden. Der nächste Schritt besteht vor allem in der Vervollständigung des Prototyps, welcher zur Evaluierung des bestehenden FCM-Modells verwendet werden soll. Mit Hilfe der Evaluierungs-Ergebnisse soll dann geprüft werden, in welcher Hinsicht das Qualitätsmodell noch angepasst werden muss. Ziel ist, ein Qualitätsmodell für eine robuste Ermittlung der Modellqualität zu finden und zutreffende Handlungsempfehlungen zur Verbesserung der Modelle geben zu können. 5 Literatur [BBL76] B. W. Boehm, J. R. Brown und M. Lipow. Quantitative evaluation of software quality. In Proceedings of the 2nd international conference on Software engineering, Seiten 592–605, Los Alamitos, CA, USA, 1976. IEEE Computer Society Press. [Bob09] A. E. Bobkowska. Model-driven software development, Kapitel Integrating quality criteria and methods of evaluation for software models, Seiten 78–93. Information Science Reference, 2009. [CD06] M. Conrad und H. Dörr. Einsatz von Modell-basierten Entwicklungstechniken in sicherheitsrelevanten Anwendungen: Herausforderungen und Lösungsansätze. In Proceedings Dagstuhl Workshop Modellbasierte Entwicklung eingebetteter Systeme, 2006. [CM78] J. P. Cavano und J. A. McCall. A framework for the measurement of software quality. In Proceedings of the software quality assurance workshop on Functional and performance issues, Seiten 133–139, 1978. [Dra96] T. Drake. Measuring Software Quality: A Case Study. Computer, IEEE Computer Society Press, 29(11):78–87, 1996. [DWP+ 07] F. Deissenboeck, S. Wagner, M. Pizka, S. Teuchert und J.-F. Girard. An Activity-Based Quality Model for Maintainability. In Proc. of the 23rd IEEE International Conference on Software Maintenance. IEEE CS Press, 2007. [FHR08] F. Fieber, M. Huhn und B. Rumpe. Modellqualität als Indikator für Softwarequalität: eine Taxonomie. Informatik-Spektrum, 31(5):408–424, October 2008. [FS07] I. Fey und I. Stürmer. Quality Assurance Methods for Model-based Development: A Survey and Assessment. SAE SP, NUMB 2126:69–76, 2007. [KCFG05] T. Klein, M. Conrad, I. Fey und M. Grochtmann. Modellbasierte Entwicklung eingebetteter Fahrzeugsoftware bei DaimlerChrysler. Inform., Forsch. Entwickl., 20(1-2):3–10, 2005. [LC05] C. F. J. Lange und M. R. V. Chaudron. Managing Model Quality in UML-Based Software Development. In Proc. of the 13th IEEE International Workshop on Software Technology and Engineering Practice, Seiten 7–16. IEEE Computer Society, 2005. [MA07] P. Mohagheghi und J. Aagedal. Evaluating Quality in Model-Driven Engineering. In Proceedings of the International Workshop on Modeling in Software Engineering, Seite 6. IEEE Computer Society, 2007. [MAA07] MAAB. The MathWorks Automotive Advisory Board, "Controller Style Guidelines for Production Intent Using MATLAB, Simulink and Stateflow", Version 2.1, 2007. [Mil99] E. E. Mills. Metrics in the software engineering curriculum. Ann. Softw. Eng., 6(14):181–200, 1999. [SDP08] I. Stürmer, C. Dziobek und H. Pohlheim. Modeling Guidelines and Model Analysis Tools in Embedded Automotive Software Development. In Proceedings Dagstuhl Seminar Modellbasierte Entwicklung eingebetteter Systeme, 2008. [WDTG09] S. Wagner, F. Deissenboeck, S. Teuchert und J.-F. Girard. Model-driven software development, Kapitel Assuring Maintainability in Model-Driven Development of Embedded Systems, Seiten 353–373. Information Science Reference, 2009. 6 ProMoSA - Probabilistic Models for Safety Analysis Frank Ortmeier and Matthias Güdemann [email protected], [email protected] Abstract: Das Ziel des ProMoSA Vorhabens st die Entwicklung eines durchgehend modell-basierten Ansatzes zur Sicherheitsanalyse. Dabei sollen sowohl quantitative als auch qualitative Aspekte aus einem gemeinsamen Modell abgeleitet werden. Zusätzlich soll es möglich sein aus einer Menge von Modellen optimale Kandidaten automatisch zu bestimmen. Die Modellerstellung soll weitgehend durch semantisch-fundierte Modelltransformationen unterstützt werden. 1 Einleitung Die immer weiter steigende Komplexität sowie die fortschreitende Integration sicherheitsrelevanter Funktionen in eingebettete Systemen stellt hohe Anforderungen an deren Zuverlässigkeit und Ausfallsicherheit. Je nach Anwendungsdomäne (z.B. Avionik, Automobil, Bahn) sind unterschiedliche Normen und Standards verfügbar, nach denen entwickelt werden muss, um eine notwendige Zertifizierung für ein System zu erreichen. Traditionellen Ansätzen zur Sicherheitsanalyse wie z.B. Fehlerbaumanalyse (FTA) werden die qualitativen Sicherheitsanalysen, also die Untersuchung welche Fehlerkombinationen zu einer kritischen Situation führen können, beruhen im Wesentlichen allein auf der Expertise des durchführenden Ingenieurs. Neuere, modell-basierte Analyseverfahren wie z.B. [BV03, ADS+ 04, OPE+ 06, ORS06] erlauben die modell-basierte Untersuchung nach kritischen Fehlerkombinationen. Bei diesen Techniken ist es (teilweise) sogar möglich die Analyse automatisch mit Deduktionstechniken durchzuführen.Das führt zu präziseren und signifikanteren Ergebnisse verglichen mit rein traditionellen Techniken. Für die Praxis ist aber die quantitative Bewertung wesentlich wichtiger (z.B. für die Zertifizierung). Dazu muss zum Beispiel die Frage ”Wie groß ist die Wahrscheinlichkeit, dass ein kritisches Systemversagen auftritt?” beantwortet werden. Praktisch alle bestehenden Ansätze – sowohl traditionelle als auch modell-basierte – beantworten diese Frage, indem aus den Ergebnissen der qualitativen Analysen aufbauend Abschätzungen bestimmt werden. Dies bringt eine Reihe von Unsicherheiten und Schwierigkeiten mit sich (z.B. common cause Fehler, stochastische Abhängigkeiten im Umgebungsverhalten, etc.). Dank neuester Entwicklungen auf dem Gebiet der probabilistischen Modellprüfer [KNP05, aPKaOaSaZ07, KKZ05] wird es möglich diese Problematik zu umgehen. Stochastische Zusammenhänge können jetzt direkt funktionalen Systemmodellen hinzugefügt werden. Aus diesen Modellen können dann stochastische Bewertungen des Systems abgeleitet werden. Dies führt zu wesentlich präziseren Wahrscheinlichkeitsabschätzungen und einem 7 weniger fehleranfälligen Analyseprozess. Erste Ansätze hierzu existieren bereits [GCW07, BCK+ 09]. Diese Ansätze sind aber sehr technologielasitg. In ProMoSA wird wesentlich stärker als in diesen Ansätzen auf die korrekte probabilistische Modellierung von Fehl- und Umweltverhalten eingegangen. Dies geschieht durch eine möglichst enge Einbindung in den Systementwurfsprozess. Als absolute Neuerung soll versucht werden statt vollständiger spezifizierter Modelle nur unterspezifizierte Modelle zu verwenden. Aus der Menge all dieser Modelle sollen dann optimale Modelle bezüglich verschiedener Metriken durch Optimierungsverfahren gefunden werden. Dies ist von großer Relevanz für die Praxis. Denn sehr häufig ist es beim Systementwurf schwierig bestimmte Parameter oder Konfigurationen gut abzuschätzen. Dies gilt im Besonderen dann, wenn die zugrunde liegende Metrik relativ komplex ist (z.B. die Gesamtausfallwahrscheinlichkeit des Systems soll minimal sein). In ProMoSA soll dieses Problem durch eine Kombination von genetischen Algorithmen, probabilistischen model checkern und externen Metriken gelöst werden. 2 Überblick Ziel des Projekts ist es neue, modell-basierte Techniken zur quantitativen Sicherheitsanalyse zu entwickeln. Grundlage dafür bilden aktuelle Fortschritte aus den Gebieten Modelltransformationen, probabilistische Analysewerkzeuge und numerische Schätz- und Optimierungsverfahren. Modelltransformationen werden verwendet, um die im Entwurfsprozess vorhandenen Modelle zu erweitern und in die Sprachen der Analysewerkzeuge zu übersetzen. Die Berechnungen der Wahrscheinlichkeitswerte werden mit automatischen, probabilistischen Analysewerkzeugen durchgeführt. Mit Hilfe von Schätz- und Optimierungsverfahren können Entscheidungshilfen und aussagekräftige Bewertungen abgegeben werden. In dem vorgeschlagenen Projekt sollen zwei wesentliche Verbesserungen erreicht werden, die weit über den aktuellen Stand der Technik hinausgehen. Erstens sollen modell-basierte Sicherheitsanalysen direkt in den Systementwurfsprozess integriert werden. Das bedeutet, dass aus den im Systementwurf vorhandenen Modellen für die Sicherheitsanalyse verwendbare Modelle generiert werden1. Dies macht die Analyse wesentlich effizienter in der Durchführung. Zusätzlich wird die Aussagekraft gestärkt, da die Adäquatheit der zur formalen Analyse verwendeten Modelle durch die semi-automatische Generierung wesentlich steigt. Als zweite Verbesserung soll eine neue Art der quantitativen Sicherheitsanalyse entwickelt werden. Statt – wie bisher – nnur”Bewertungen für ein gegebenes System abzuleiten, soll durch Vorgabe von Sicherheitszielen aus einer ganzen Klasse möglicher Systeme mittels Optimierung das beste Design bestimmt werden. Als Konsequenz müsste man dann eher von einem Sicherheitsdesignprozess sprechen als von Sicherheitsanalyse. Für dieses Ziel sind auch wesentliche Fortschritte bei der modell-basierten, stochastischen Analyse notwendig. Bisher gibt es nur wenige Ansätze, die quantitative Werte direkt undmathematisch fundiert aus funktionalen Modellen ableiten. 1 Natürlich 8 ist bei diesen Verfeinerungen noch zusätzliches Wissen notwendig. Der Nutzen des Gesamtprojekt lässt sich am Besten an einem kleinen Beispiel veranschaulichen. Das folgende Beispiel kommt aus dem Bereich der autonomen Verkehrsregelung. In Abbildung 1 ist ein alternatives, flexibles Steuerkonzept für eine Bahnstrecke mit Ausweichspur, die zum Überholen oder – auf eingleisigen Trassen – auch zum Passieren von Gegenverkehr benutzt werden kann, skizziert. Die offensichtlichen Sicherheitsziele sind Vermeidung von Kollisionen und von Entgleisen durch Weichenfehlstellungen. Zur Veranschaulichung genügt es sich hier auf den Fall, dass sich zwei Züge aus einer Richtung nähern zu beschränken. 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 000000000000 111111111111 111111111111 000000000000 111111111111 Sicherheitsabstand ... ... 111111111111 000000000000 000000000000 000000000000 000000000000 111111111111 111111111111 000000000000 111111111111 111111111111 000000000000 111111111111 Sicherheitsabstand Bremsweg Umschaltweg Abbildung 1: Hauptgleis mit Nebengleis und Weiche Um maximalen Durchsatz zu erreichen, soll auf eine Einteilung der Gleise in starre, unflexible Streckensegmente verzichtet werden. Deshalb sind in relativ großem Abstand in beiden Richtungen vor der Ausweichstrecke jeweils Achszähler im Boden versenkt. Diese können detektieren, ob, in welcher Richtung und wieviele Achsen diese Kontrollpunkte passieren. Diese Information wird zyklisch dem Kontrollsystem der Ausweichstrecke mitgeteilt2 . Zusätzlich melden sich die Züge per Funk für eine Durchfahrt an. Jeder Zug teilt dazu zyklisch seine Position und Geschwindigkeitmit. Zur Positionsbestimmung verfügen die Züge einerseits über GPS und zusätzlich über ein Odometer, mit dem die aktuelle Position aus früheren Daten und der Geschwindigkeit bestimmt werden kann. Für ein effizientes überholen ist es notwendig, dass möglichst geringe Geschwindigkeitsveränderungen durchzuführen sind. Das bedeutet, dass beide Zügemöglichst wenig Bremsen und Beschleunigen müssen und eventuelle Zeitverzögerungen gering bleiben. Dazu müssen virtuelle Bremswege, Umschaltzeiten der Weichen, Beschleunigungskoeffizienten etc. mit berücksichtigt werden. Wichtig ist, dass trotzdem Kollisionen sicher vermieden werden und auch die Weichen rechtzeitig Ihre Schaltvorgänge abschließen können (Vermeiden von Entgleisen). Dies versucht man in der Regel durch das Einführen von entsprechenden Sicherheitszuschlägen zu erreichen. übernommenwerden all diese Aufgaben von einer Kontrollsoftware. Ziel von ProMoSA ist die Entwicklung eines durchgehend modell-basierten Ansatzes zur Sicherheitsanalyse. Dabei sollen sowohl quantitative als auch qualitative Aspekte aus einem gemeinsamen Modell abgeleitet werden. Zusätzlich soll es möglich sein aus einer Menge von Modellen optimale Kandidaten automatisch zu bestimmen. Die Modellerstellung soll weitgehend durch semantisch-fundierte Modelltransformationen unterstützt werden. Am obigen Beispiel würde etwa ein formales Modell der Software, der Aktorik (z.B. Bremsen), der Sensorik (z.B. GPS), der Umgebung (z.B. Fahrverhalten des Zuges) sowie möglicher Fehlermodi erstellt (z.B. Abweichungen bei der Geschwindigkeitsmessung). Als Ausgangspunkt dient dabei zum Beispiel das Modell aus den ersten Phasen des Soft2 Interessant ist, dass man das vorgestellte Kontrollsystem mit einfachen Erweiterungen auch komplett dezentral auf den Steuerrechnern der Züge implementieren könnte. 9 wareentwurfs. Dieses wird dann schrittweise erweitert. In diesem Modell sind in der Regel noch Freiheitsgrade vorhanden. So könnten beispielsweise Sicherheitszuschläge oder Mindestabstände noch offen gelassen werden. Im nächsten Schritt wird dieses Modell um stochastische Zusammenhänge erweitert. Hier würden beispielsweise für Fehlermodi die entsprechenden Fehlerraten adäquat hinzugefügt. Resultat ist ein stochastisches Modell bzw. genauer gesagt eine Menge von Modellen. Einzelne Modelle können durch Wahl der freien Parameter erzeugt werden und modell-basiert analysiert werden. Bei dieser Art von Analyse werden z.B. stochastische Abhängigkeiten (z.B. mehrfacher Ausfall der Kommunikation) genauso wie implizite Abhängigkeiten (z.B. müssen für ein korrektes überholen in manchen Situationen beide Weichen gleichzeitig bei Anderen zeitversetzt geschaltet werden). Optimale Lösungen können mit genetischen Algorithmen innerhalb dieses Modellraums bestimmt werden. Optimal kann in diesem Zusammenhang entweder direkt ein Sicherheitseigenschaft sein oder auch eine extern berechnet Größe (wie beispielsweise Kosten oder Performanz). Die geplanten Optimierungsverfahren sollen auch in der Lage sein mit gegenläufigen Zielen umgehen zu können. In diesem Fall werden keine Optima bestimmt, sondern lediglich die besten Kompromisse (mathematisch entspricht dies den Pareto-Mengen). Im obigen Beispiel könnten das sein maximale Sicherheit vs. minimaler Energieverlust. 3 Grundlegende Idee Etwas allgemeiner ist der geplante Prozess in Abbildung 2 dargestellt. Ausgangspunkt ist eine Reihe von Anforderungen beispielsweise als Ergebnis einer Requirements Analysis (I). Im oben genannten Beispiel wäre dies etwa die Notwendigkeit einer effizienten Überholmöglichkeit und die einzuhaltenden Sicherheitsziele. Aus diesen Anforderungen wird eine erste grobe Idee des Systems erstellt. Also beispielsweise die Lösung mit einer begrenzten Nebenstrecke sowie dynamischen, von der Geschwindigkeit der Züge abhängenden Sperrbereichen (II). In diesem Grobentwurf sind noch viele Details offen, wie beispielsweise Sicherheitszuschläge, verwendete Weichen (mit zugehörigen Umschaltzeiten) oder auch Maximalgeschwindigkeiten. Verbessere Grobkonzept Definition des Modellraums Analyse und Optimierung Erstellung Fehlermodell Mehrkriterien− optimierung Ausgabe Parameter [nein] Definition der Requirements Analyse Erstellung Umweltmodell Systemklasse I Erzeugung Modell II modell−basierte, stochastische Optimierung [nein] [ja] Anforderungen komplett? erfuellt? [ja] Ausgabe Bewertung Analyse Ausgabe Testszenarien Erstellung Systemmodell III manueller Schritt IV automatisierter Schritt Abbildung 2: Grundidee des geplanten Vorgehens Diese Spezifikation wird mit semantisch fundierten Modelltransformationen erweitert (beispielsweise um relevante Ausfälle und deren Verteilungsfunktionen sowie Spezifikationen 10 der Umgebung). In der Regel findet in diesem Schritt auch eine Verfeinerung der Kontrollogik statt. Insgesamt erhält man am Ende dieses Schrittes ein relativ detailliertes Modell des Kontrollsystems, eingebettet in seine Umgebung (III). Dieses Modell ist in der Regel unterspezifiziert und enthält eine Reihe freier Parameter, die noch bestimmt werden müssen. Im Beispiel oben würden in diesem Schritt Verhaltensmodelle der Züge und auch probabilistische Ausfallmodelle der Sensoren und Aktuatoren zum rein funktionalen Modell der Software hinzukommen. Durch Wahl der Parameter können jederzeit Modellinstanzen gebildetwerden. Jede einzelne Instanz beschreibt ein semantisch-fundiertes Modell eines möglichen Systems. Dieses Modell kann zurmodell-basierten Analyse verwendetwerden (beispielsweisemit probabilistischem model checking). Dazu wird die Modellinstanz automatisch in Eingabesprache eines entsprechenden Tools übersetzt. Hier ist besonders wichtig, dass die Transformation semantik-erhaltend ist. Durch verschiedene Analysemethoden kann dann eine Bewertung der Modellinstanz abgegeben werden. Hier sollen sowohl Eigenschaften als Bewertungskriterien möglich sein, die direkt aus dem Modell ableitbar sind (z.B. wie etwa das Kollisionsrisiko) als auch Kriterien die sich zwar aus den Parametern ableiten lassen, aber durch externe Bewertungsfunktionen bestimmt werden (z.B. zusätzlicher Energieverbrauch)3. Aufgrund dieser Bewertung wird dann mit Optimierungsverfahren entschieden, ob eine weitere Verbesserung möglich ist oder nicht. Technisch wird dies durch Mehrkriterienoptimierung umgesetzt. Unabhängig vom gewählten Verfahren ist hier praktisch immer mehrmaliges Auswerten verschiedener Modellinstanzen notwendig. Diese Iteration kann aber vollautomatisch erfolgen (IV). Im Beispiel würde das System mit verschiedenen Sicherheitszuschlägen und Maximalgeschwindigkeiten jeweils analysiert und bewertet, bis eine gute Lösung gefunden ist. In einem abschließenden Schritt muss der Ingenieur entscheiden, ob das System den erforderlichen Qualitätskriterien genügt. Falls ja kann man im Entwurfsprozess fortschreiten, falls nein sind Änderungen am Grobkonzept notwendig. Dies erfordert in der Regel eine zusätzliche, kreative Ingenieurtätigkeit4. 4 Zusammenfassung und Ausblick Das aktuelle Projekt geht weit über bestehende Ansätze hinaus, da es zum Ziel hat auf formalen Methoden beruhende Sicherheitsanalysetechniken direkt in den Systementwurfsprozess zu integrieren. Dazu sind neben den technischen Hürden (z.B. semantik-erhaltende Modelltransformationen) auch wesentliche Beiträge zum Prozess notwendig (z.B. wie/in welcher Reihenfolge modelliert man Fehlverhalten, was ist Fehlverhalten, wie kombiniert man verschieden Wahrscheinlichkeitsmaße). Die zweite wesentlich Herausforderung besteht in der geplanten Austauschbarkeit verschiedener Modellierungs- und Verifikati3 Aus rein theoretischer Sicht wäre natürlich ein alle Aspekte umfassendes Gesamtmodell wünschenswert. Das ist aber leider in der Praxis nicht mit vertretbarem Aufwand realisierbar. 4 Man könnte auch versuchen diese Iteration beispielsweise durch genetische Algorithmen zu unterstützen. Das resultierende Problem ist dann aber ähnlich schwierig wie das Problem der Programmsynthese und bringt beträchtliche Probleme mit sich. Deshalb wird dieser Ansatz in der ersten Phase des Projektes nicht weiter verfolgt. In der ersten Phase des Projektes werden nur Designvarianten betrachtet, die sich durch unterschiedliche Wahl von freien Parametern ergeben. Eine Verallgemeinerung ist in der zweiten Phase möglich. 11 onswerkzeuge. Die einzelnen zugrundeliegenden Formalismen weisen größere semantische Unterschiede auf (z.B. zeitdiskrete vs. zeitkontinuierliche Ansätze). Aus theoretischer Sicht sind diese zwar in einander einbettbar5. Aus praktischer Sicher sind aber beispielsweise manche Fehlerarten sehr einfach im einen Formalismus abbildbar und nur mit großem Aufwand im Anderen. Die dritte wesentliche Herausforderung liegt in der Performanz. Für die Blackbox-Optimierung scheinen genetische Algorithmen das Mittel der Wahl. Diese benötigen aber in der Regel sehr viele Funktionsauswertungen. Deshalb müssen wahrscheinlich stochastische Schätzverfahren verwendet werden. Es bleibt zu untersuchen, wie effizient durch diese Kombination die Optimierung werden kann. Literatur [ADS+ 04] Parosh Aziz Abdulla, Johann Deneux, Gunnar Stalmarck, Herman Agren und Ove Akerlund. Designing Safe, Reliable Systems using SCADE. In Proceedings of ISOLA’04. Springer-Verlag, 2004. [aPKaOaSaZ07] David N. Jansen andJoost-Pieter Katoen andMarcel Oldenkamp andMariëlle Stoelinga andIvan Zapreev. How Fast and Fat Is Your Probabilistic Model Checker? In Haifa Verification Conference, HVC’07, LNCS. Springer, 2007. To be published. [BCK+ 09] Marco Bozzano, Alessandro Cimatti, Joost-Pieter Katoen, Viet Yen Nguyen, Thomas Noll und Marco Roveri. http://compass.informatik.rwth-aachen.de/, 2009. [BV03] M. Bozzano und Adolfo Villafiorita. Improving System Reliability via Model Checking: theFSAP/NuSMV-SA Safety Analysis Platform. In Proceedings of SAFECOMP’03, Seiten 49–62. Springer-Verlag, 2003. [GCW07] L. Grunske, R. Colvin und K. Winter. Probabilistic Model-Checking Support for FMEA. In Proc. 4th International Conference on Quantitative Evaluation of Systems (QEST’07), 2007. [KKZ05] J. P. Katoen, M. Khattri und I. S. Zapreev. A Markov reward model checker. In 2nd Int. Conf. on Quantitative Evaluation of Systems, Turin, Italy, Seiten 243–245, Los Alamitos, California, 2005. IEEE Computer Society. [KNP05] M. Kwiatkowska, G. Norman und D. Parker. Quantitative analysis with the probabilistic model checker PRISM. Electronic Notes in Theoretical Computer Science, 153(2):5–31, 2005. [OPE+ 06] O.Akerlund, P.Bieber, E.Boede, M.Bozzano, M.Bretschneider, C.Castel, A.Cavallo, M.Cifaldi, J.Gauthier, A.Griffault, O.Lisagor, A.Luedtke, S.Metge, C.Papadopoulos, T.Peikenkamp, L.Sagaspe, C.Seguin, H.Trivedi und L.Valacca. ISAAC, a framework for integrated safety analysis of functional, geometrical and human aspects. In Proceedings of ERTS 2006, 2006. [ORS06] F. Ortmeier, W. Reif und G. Schellhorn. Deductive Cause-Consequence Analysis (DCCA). In Proceedings of IFAC World Congress. Elsevier, 2006. 5 mit 12 kleinen Einschränkungen an die zulässigen Systeme Towards Architectural Programming of Embedded Systems Arne Haber, Jan O. Ringert, Bernhard Rumpe Software Engineering, RWTH Aachen University, Germany http://www.se-rwth.de/ Abstract: Integrating architectural elements with a modern programming language is essential to ensure a smooth combination of architectural design and programming. In this position statement, we motivate a combination of architectural description for distributed, asynchronously communicating systems and Java as an example for such an integration. The result is an ordinary programming language, that exhibits architecture, data structure and behavior within one view. Mappings or tracing between different views is unnecessary. A prototypical implementation of a compiler demonstrates the possibilities and challenges of architectural programming. 1 Java with Architectural Elements As stated in [MT00] there are a number of languages that support design, analysis, and further development of software-system-architectures. These languages are commonly known as Architecture Description Languages (ADL) and allow a high level description of software systems of a specific domain. Using an ADL enables reasoning about specific system properties in an early development stage [GMW97]. Furthermore, there are quite often mappings from architecture to a General Purpose Language (GPL), producing code frames for the GPL. This helps ensuring the architectural consistency initially, but when the code evolves the architecture becomes implicitly polluted or when the architecture shall be evolved this needs to be done on the code level. Tracing is therefore important to keep architecture and code aligned. However, it would be much better to integrate both, architecture and code into one single artifact such that tracing is not necessary anymore. [MT00] defines a component as a unit of computation or storage that may represent the whole software system or just a single small procedure. Components in distributed systems partially run in a distributed manner on different hardware. As a consequence they do not share memory and the communication through shared variables or ordinary method calls is not feasible. So they communicate with each other through channels called connectors by asynchronous message passing. Here a component always has an explicitly defined interface of needed and offered connectors. In contrast to this, object oriented classes respectively their instances in a GPL are mostly accessed through their implemented interfaces synchronized by blocking method calls. But a class does not explicitly describe the interfaces it uses. In addition, the hierarchical containment that is intensely used in ADLs to structure systems, is almost completely missing in the object oriented paradigm. A common way to structure object oriented systems is the usage of packages. However 13 one is not able to express hierarchical containment with this technique. Several approaches like JavaBeans [JB09] enrich an existing GPL with a component concept. Nevertheless they do not exceed or extend the borders drawn by the target object oriented GPL. These approaches mainly introduce new libraries written in plain GPL code or map a language extension into the original GPL. Doing so, Java has been enriched by JavaBeans with a concept to use components in an object oriented environment, but the traceability from architecture to code has not been increased very much. And this traceability is necessary, because the developer is exposed with both views, the architecture and the code. We believe that one way to raise this traceability respectively to make it unnecessary is to combine an existing ADL with a common GPL in such a way that architectural definitions are explicit and essential part of the language. We decided to use the ADL MontiArc that resembles a common understanding of how to model distributed communicating systems, similar to automotive function nets [GHK+ 07], or UML’s composite structure diagrams [OMG07], and with a precise underlying calculus like FOCUS [BS01] as described in Sect. 4. As our target GPL we decided to use Java, because it is a widely accepted modern language. We integrate classes, methods, and attributes into components. This gives us a new programming language with the working title “AJava” and enables us to combine concrete behavior descriptions with an abstract high-level architectural description directly in one artifact. Enhanced with a syntax highlighting Eclipse-editor that supports functions like auto-completion, folding, error messages, and hyperlinking to declarations, one is able to program architectures in a familiar and comfortable development environment. Further tool support is given by a prototypical compiler for a subset of AJava based on the DSL framework MontiCore [GKR+ 08]. The concrete syntax of AJava will be shown in the next section with an introducing example. In Sect. 3 we discuss aspects of the design and variations of AJava. Our approaches to building a compiler and defining semantics are presented in Sect. 4. This paper ends with related approaches and a conclusion in sections 5 and 6. 2 Integrated Component Programming As an example of how to model and implement an embedded system in AJava we present a coffee machine which takes the selection of a type of coffee as input. Connected to the machine is a milk dispenser which is managed by the coffee machine specifying the needed amount of milk and receiving an error signal if the milk tank is empty. The coffee machine itself is composed of a display, the coffee processing unit and bean sensors to monitor the available amount of coffee and espresso beans. A graphical representation of the main component is given in Fig. 1. Its corresponding implementation in AJava is given in listing 1. Please note that the textual representation is covering all features in Fig. 1, although some connectors are not explicitly given but derived from the component’s context. We assume, regarding the development process, that appropriate editors show the textual representation as main development artifact and the 14 CoffeeMachine String message Display String message CoffeeType selection Boolean milkEmpty Boolean milkEmpty CoffeeType selection CoffeeProcessingUnit Integer cpu milkAmount Boolean espressoEmpty BeanSensor Boolean espressoBs beanEmpty Integer milkAmount Boolean coffeeEmpty Boolean beanEmpty BeanSensor coffeeBs Figure 1: Architecture of the CoffeeMachine component diagram as outline for a better navigation. The component CoffeeMachine in listing 1 defines a public Java enumeration CoffeeType (ll. 8–9) that can be used by all other components. The interface of a component (its ports) is declared after the keyword port (ll. 3–6) where each port needs a type T. Admissible types are all Java types. The port then accepts incoming data of type T or its subtypes. If port names are omitted they will be set to their type’s name (if it is unique). Inner components are instantiated using the keyword component. E.g. in l. 15 a component of type Display is instantiated and in l. 14 a component of type CoffeeProcessingUnit is created with name cpu. Naming components is optional as long as types are unique. Further elements of the architectural description are connectors that connect one outgoing port with one to arbitrarily many incoming ports. Explicit connections are made via the connect statement (l. 17) or at instantiation of an inner component. This short form for connectors can be seen in l. 12 connecting port beanEmpty of inner component espressoBS to a corresponding port of the coffee processing unit. In many cases explicit definition of connectors is not necessary if connections can be derived by port names. The automatic derivation is activated by autoconnect port (l. 2) but can be overridden and extended by explicit connections. Messages can only be transmitted (asynchronously) between ports via these communication channels, there is no other form of inter-component communication (cf. Sect. 3). The behavioral component CoffeeProcessingUnit (CPU) is displayed in listing 2. In contrast to architectural components like CoffeeMachine behavioral components contain no further components but implement a concrete behavior (cf. Sect. 3.3). The CoffeeProcessingUnit contains an interface declaration (ll. 2–8) like all components in AJava do. The CPU declares a private state variable milkAvailable (l. 10) and amongst others the dispatcher method onMilkEmptyReceived (l. 12). This 15 1 2 3 4 5 6 component CoffeeMachine { autoconnect port; port in CoffeeType selection, in Boolean milkEmpty, out Integer milkAmount; 7 public enum CoffeeType { LatteMacchiato, Espresso, Cappucino, Coffee } 8 9 10 component BeanSensor espressoBS [beanEmpty->cpu.espressoEmpty], coffeeBS; component CoffeeProcessingUnit cpu; component Display; 11 12 13 14 15 16 connect coffeeBS.beanEmpty->cpu.coffeeEmpty; 17 18 } Listing 1: Structural component CoffeeMachine in AJava syntax method by convention dispatches incoming messages arriving on port milkEmpty of type Boolean. Thus the communication is event triggered, but other implementations will be possible, where data is buffered by the environment or the component’s ports, allowing a possibly explicitly defined scheduling strategy to manage the input buffer. The example method (ll. 12–19) reacts on input from a sensor and sends an according text message via its outgoing port message (ll. 14, 16). This port is connected to the display of the coffee machine (cf. Fig. 1) which is not known inside the CPU component. Please note that outgoing ports have similarities to private variables and in their implementation they offer a sending procedure to transmit data from this port. 3 Discussion of the Designed Language The proposed language AJava is pointing out one way towards a new paradigm or at least a paradigm integration between object-orientation and architectural design. The resulting language will not be a silver bullet, but should enable programmers to write evolvable and well-structured code more easily. However, many language design decisions are still to be considered based on empirical evidence that is collected using this prototypical language. In the following, some issues on the design of AJava and its semantics are introduced and discussed. They mostly tackle trade-offs between Java’s features for interaction between objects, and harnessing the complexity of the architecture described in AJava. 16 1 2 3 4 5 6 7 8 component CoffeeProcessingUnit { port in CoffeeType selection, in Boolean espressoEmpty, in Boolean coffeeEmpty, in Boolean milkEmpty, out Integer milkAmount, out String message; 9 private boolean milkAvailable; //... public void onMilkEmptyReceived(Boolean milkEmpty) { if (milkEmpty) { this.message.send("Sorry, no milk today."); } else { this.message.send("Got milk!"); } this.milkAvailable = !milkEmpty; } 10 11 12 13 14 15 16 17 18 19 20 } Listing 2: The coffee processing unit implemented in AJava 3.1 Communication forms between components Components in AJava can contain attributes, variables, and even encapsulated Java classes. Intuitively components are similar to objects and could use their regular ways of communication. This would allow method calls, event passing, shared variables and more mechanisms used in object oriented systems to also be used among components. The design of ADLs and MontiArc in general favors however a more limited form of communication: message passing via channels connecting ports of components. In the context of AJava this restriction would prohibit that a component calls a method or reads attributes of another component. The second communication form especially ensures the classical communication integrity (cf. [LV95]) that claims that components only communicate through explicitly defined interfaces and such the effect and resulting behavior of a reused component is much easier to predict. 3.2 Communication via Channels Channels are typed connections from one source port to one or more target ports. Channels can also be fed back, where source and target port belong to the same component. A programmer might want to pass references to objects from one component to another to share object state. While this might be convenient and feasible if two components run in the same VM, it pollutes clean design, because it forces components to run on the same physical engine. Furthermore, it couples components in an implicit way, making reuse 17 much more difficult. Language design variants are to only communicate via (a) messages of simple types or (b) encode the full object structure and send it over the channel. The latter however, can lead to much unnecessary traffic and might lead to semantic changes due to different object identities of otherwise identical objects. This could be improved through optimizing strategies, e.g. a transparent implementation of lazy sending of data parts, and explicit encoding of object identities. 3.3 Structural vs. Behavioral Components Several ADLs like ROOM [SGW94] force the system designer to compose system-behavior as the accumulated behavior of all leaf-components in the lowest hierarchy layer. Other approaches like [OL06], in that case UML Composite Structure Diagrams are used to model architectures, allow behavior on all hierarchy-layers of system-architectures. On the one hand, both variants can be translated into each other. On the other hand, reuse and convenient modeling of parts of the software seem to be pretty much affected by these two different approaches. For example a structural refinement does not necessary yield to a behavioral refinement in the latter case. By now AJava follows the first strategy and separates between structural and behavioral components. We believe that the effort needed to break down functionality to leaf-nodes pays off with better traceability of functionality and the ability to replace whole branches with dummies for better testability. However, experiments of a controlled mixture of behavioral elements and a structural decomposition within a component could show, how e.g. to integrate scheduling or message dispatching strategies within components that allow the programmer a fine grained control over the messages processed. 3.4 Embedded components In contrast to general purpose components running on regular VMs an embedded AJava component should be able to run on an embedded systems with few resources. Compiling against small VMs like kaffe [Kaf09] or JamVM [Jam09] restricts the used Java version and compiler. JamVM is extremely small but only supports the Java Language Specification Version 2, so some new concepts like e.g. generics or annotations are not available. To avoid this drawback we might use Java SE For Embedded Use [EJ09] that is currently compatible with Java 6. However this VM requires much more resources and reduces the application range of AJava components to devices with more powerful cpus like e.g. mobile phones. Please note that AJava can, besides its application for embedded systems, also be used for general purpose software development tasks. 18 4 Language Realization and Semantics For a precise understanding of the AJava language, a formal specification of the key concepts is most helpful. For a definition of its features and semantics we follow the methodology proposed in [HR04]. In a first step we defined its syntax as a context free grammar using the DSL framework MontiCore [GKR+ 08], a framework for quick development of modeling and also programming languages. From there we explored and still explore the language through application of a prototypical AJava compiler. The objective of this compiler is to translate AJava sources to complete and self-contained Java classes. The system engineer only works on AJava artifacts and not the generated Java code. Although as sketch of the formal denotational semantics is understood, a precise definition will later be defined based on [GRR09] to define system model semantics for AJava. The current implementation of the MontiCore compiler generator derives the abstract syntax tree as well as an instance of the ANTLR parser [Ant08] that can process AJava programs. In previous works MontiCore grammars for Java as well as an architectural description language MontiArc have been developed independently. As MontiCore supports the reuse and combination of independently defined languages e.g. through embedding of languages [KRV08b] the development of a composed compiler was relatively quick and straightforward. 4.1 Communication realization As discussed in Sect. 3 several variants of communication mechanisms are possible, scaling from strict port communication to liberal method calls between any kinds of objects. While method calls can be realized directly in Java, port to port communication in a distributed system has to be implemented in a different way. Ideally components need not care about the physical deployment of their communication partners. This also means that all components, either on one machine or distributed, use the same communication interface. Generally components run in their own thread and asynchronous communication is realized through buffering to decouple components. This creates the need for a smart communication layer encapsulating the inter-component communication. As AJava components are realized in Java, existing communication methods like RMI [RMI09] or CORBA [OMG08] are of particular interest. As both protocols use TCP for inter-component communication they are not feasible for embedded bus communication. Instead a hand written communication layer that maps component port communication to e.g. the Java CAN API [BN00] is more suitable. Additional capabilities, like buffering or an explicit possibility of a component to manipulate its input buffer, will need extra infrastructure to be implemented. The suitability of different communication layers for AJava components in an embedded environment is to be investigated. 19 4.2 Formal Semantics Operational semantics of AJava is defined by supplying a translation to Java code. This definition of semantics makes it hard to apply automated reasoning about features of the language and properties of programs since the translation rules are not explicitly given in a way accessible to theorem provers. So far there is no complete reasoning framework for the whole Java language. Advances however have been made in formalizing the language, and proving the type system correct [Ohe01]. The approach favored here is the semantic mapping of AJava to the system model described in [BCR06, BCR07a, BCR07b]. This approach has been introduced in [CGR08a, CGR08b] for class diagrams and state charts. Inter-object communication can be specified in two ways in the system model: composable state machines or through communication of components in FOCUS style [BCR07b]. A logic for realizable component networks based on [GR07] is currently under development and will be suited for the definition of AJava’s semantics with respect to certain of the above discussed design decisions. For the most natural semantics component communication directly maps to asynchronous communication over typed Focus channels. Both approaches mentioned so far only support the abstract definitions of timing. Reasoning about timing in real-time systems thus has to be further investigated. 5 Related Work Another approach to combine the GPL Java with an ADL is ArchJava [ACN02] that introduces components, ports, and connectors to an object oriented environment. In contrast to AJava ArchJava facilitates dynamic architectures as described in [MT00]. This way components can be added and removed to systems during runtime. The major disadvantage of ArchJava compared to AJava is that ArchJava’s components have no support of distribution across the borders of a single VM. A common approach to implement components in Java is the usage of JavaBeans [JB09]. Again, the main disadvantage compared to an integrated ADL based programming language is either a missing mapping from architecture to code or the need for synchronization of many different heterogeneous documents describing the system. In addition JavaBeans communicate via method calls hence they are bound to run on a single VM. To avoid this drawback they can be combined with RMI, but as discussed in Sect. 4.1, this is not feasible for embedded systems. Another approach to ensure architectural consistency is presented in [DH09]. The described prototype ArchCheck automatically derives a base of logical facts from java source code describing existing dependencies. Architectural consistency rules are manually derived from architectural descriptions and checked by an interpreter according to the derived base of rules and facts. Compared to AJava this approach is not bounded to one system domain as AJava only copes information flow architectures. But again, the involved artifacts have to be synchronized manually in contrast to AJava that automatically enforces 20 the architectural consistency by design of the language. 6 Conclusion We propose a possible way to combine architectural and concrete behavioral descriptions into the programming language AJava. This language integrates Java and the ADL MontiArc rendering artificial mappings between architecture and implementation superfluous. This work is still in a preliminary stage. Based on our tooling framework [GKR+ 08, KRV08b, KRV08a], we are currently developing an enhanced version of the compiler for our language. This prototype together with other experience on definition of programming languages [Rum95] will help us to contribute to a possible smooth extension of a GPL with appropriate architectural elements, such that the level of programming is raised towards architecture and may be in the future also towards requirements. References [ACN02] [Ant08] [BCR06] [BCR07a] [BCR07b] [BN00] [BS01] [CGR08a] [CGR08b] [DH09] [EJ09] Jonathan Aldrich, Craig Chambers, and David Notkin. ArchJava: connecting software architecture to implementation. In International Conference on Software Engineering (ICSE) 2002. ACM Press, 2002. Antlr Website www.antlr.org, 2008. Manfred Broy, Marı́a Victoria Cengarle, and Bernhard Rumpe. Semantics of UML – Towards a System Model for UML: The Structural Data Model. Technical Report TUM-I0612, Institut für Informatik, Technische Universität München, June 2006. Manfred Broy, Marı́a Victoria Cengarle, and Bernhard Rumpe. Semantics of UML – Towards a System Model for UML: The Control Model. Technical Report TUM-I0710, Institut für Informatik, Technische Universität München, February 2007. Manfred Broy, Marı́a Victoria Cengarle, and Bernhard Rumpe. Semantics of UML – Towards a System Model for UML: The State Machine Model. Technical Report TUM-I0711, Institut für Informatik, Technische Universität München, February 2007. Dieter Buhler and Gerd Nusser. The Java CAN API-a Java gateway to field bus communication. In Factory Communication Systems, 2000. Proceedings. 2000 IEEE International Workshop on, pages 37–43, 2000. Manfred Broy and Ketil Stølen. Specification and Development of Interactive Systems. Focus on Streams, Interfaces and Refinement. Springer Verlag Heidelberg, 2001. Marı́a V. Cengarle, Hans Grönniger, and Bernhard Rumpe. System Model Semantics of Class Diagrams. Informatik-Bericht 2008-05, Technische Universität Braunschweig, 2008. Marı́a V. Cengarle, Hans Grönniger, and Bernhard Rumpe. System Model Semantics of Statecharts. Informatik-Bericht 2008-04, Technische Universität Braunschweig, 2008. Constanze Deiters and Sebastian Herold. Konformität zwischen Code und Architektur - logikbasierte Überprüfung von Architekturregeln. Objektspektrum, 4:54–59, 2009. Java SE for Embedded Use website http://java.sun.com/javase/embedded/, 2009. 21 [GHK+ 07] Hans Grönniger, Jochen Hartmann, Holger Krahn, Stefan Kriebel, and Bernhard Rumpe. View-Based Modeling of Function Nets. In Proceedings of the Object-oriented Modelling of Embedded Real-Time Systems (OMER4) Workshop, Paderborn,, October 2007. [GKR+ 08] Hans Grönniger, Holger Krahn, Bernhard Rumpe, Martin Schindler, and Steven Völkel. MontiCore: a framework for the development of textual domain specific languages. In 30th International Conference on Software Engineering (ICSE 2008), Leipzig, Germany, May 10-18, 2008, Companion Volume, pages 925–926, 2008. [GMW97] David Garlan, Robert T. Monroe, and David Wile. Acme: An Architecture Description Interchange Language. In Proceedings of CASCON’97, pages 169–183, Toronto, Ontario, November 1997. [GR07] Borislav Gajanovic and Bernhard Rumpe. ALICE: An Advanced Logic for Interactive Component Engineering. In 4th International Verification Workshop (Verify’07), Bremen, 2007. [GRR09] Hans Grönniger, Jan Oliver Ringert, and Bernhard Rumpe. System Model-Based Definition of Modeling Language Semantics. In FMOODS/FORTE, pages 152–166, 2009. [HR04] David Harel and Bernhard Rumpe. Meaningful Modeling: What’s the Semantics of “Semantics“? Computer, 37(10):64–72, 2004. [Jam09] JamVM website http://www.kaffe.org/, 2009. [JB09] JavaBeans website http://java.sun.com/javase/technologies/desktop/javabeans/index.jsp, 2009. [Kaf09] Kaffe website http://www.kaffe.org/, 2009. [KRV08a] Holger Krahn, Bernhard Rumpe, and Steven Völkel. Mit Sprachbaukästen zur schnelleren Softwareentwicklung: Domänenspezifische Sprachen modular entwickeln. Objektspektrum, 4:42–47, 2008. [KRV08b] Holger Krahn, Bernhard Rumpe, and Steven Völkel. MontiCore: Modular Development of Textual Domain Specific Languages. In Proceedings of Tools Europe, 2008. 22 [LV95] David C. Luckham and James Vera. An Event-Based Architecture Definition Language. IEEE Trans. Softw. Eng., 21(9):717–734, 1995. [MT00] Nenad Medvidovic and Richard N. Taylor. A Classification and Comparison Framework for Software Architecture Description Languages. IEEE Transactions on Software Engineering, 2000. [Ohe01] David von Oheimb. Analyzing Java in Isabelle/HOL: Formalization, Type Safety and Hoare Logic. PhD thesis, Technische Universität München, 2001. [OL06] Ian Oliver and Vesa Luukkala. On UML’s Composite Structure Diagram. In Proceedings of the 5th Workshop on System Analysis and Modelling, 2006. [OMG07] Object Management Group. Unified Modeling Language: Superstructure Version 2.1.2 (07-11-02), 2007. http://www.omg.org/docs/formal/07-11-02.pdf. [OMG08] CORBA specification http://www.omg.org/spec/CORBA/3.1/, 2008. [RMI09] RMI Website http://java.sun.com/javase/technologies/core/basic/rmi/index.jsp, 2009. [Rum95] Bernhard Rumpe. Gofer Objekt-System – Imperativ Objektorientierte und Funktionale Programmierung in einer Sprache vereint. In Tiziana Margaria, editor, Kolloquium Programmiersprachen und Grundlagen der Programmierung, Adalbert Stifter Haus, Alt Reichenau, 11.10.1995, 1995. [SGW94] Bran Selic, Garth Gullekson, and Paul T. Ward. Real-Time Object-Oriented Modeling. John Wiley & Sons, April 1994. Modell-zu-Metamodell-Transformationen zur Entwicklung von komponentenbasierten Systemen Christian Buckl, Gerd Kainz fortiss GmbH {buckl,kainz}@fortiss.org Stephan Sommer, Alois Knoll Technische Universität München {sommerst,knoll}@in.tum.de Abstract: Bei der Entwicklung von komponentenbasierten Systemen werden in der Regel Middlewarearchitekturen bzw. Laufzeitsysteme zur Verknüpfung der Komponenten eingesetzt. Werden diese Architekturen modellgetrieben entwickelt, kann man zwischen drei Arten von Entwicklern unterscheiden: Laufzeitsystemexperten, Komponentenentwicklern und Anwendungsentwicklern. In diesem Beitrag wird aufgezeigt, wie man durch einen mehrphasigen modellgetriebenen Entwicklungsansatz diese Experten optimal unterstützen kann. Dabei wird insbesondere auf die Bedeutung von Modell-zu-Metamodell-Transformationen verwiesen. Die Vorteile des Ansatzes werden am Beispiel der Entwicklung von verteilten Sensor-Aktor-Systemen aufgezeigt. 1 Einleitung Zur Erhöhung der Wiederverwendbarkeit werden verteilte, eingebettete Systeme häufig komponentenbasiert entwickelt [Szy02]. Dabei wird als Softwarearchitektur eine Komponenten-Container-Architektur umgesetzt. Der Container in Form von Middlewarearchitekturen oder Laufzeitsystemen realisiert hierbei die Kommunikation zwischen den einzelnen Komponenten. Während im Bereich von verteilten Standard-IT-Systemen überwiegend generische Ansätze, z.B. basierend auf CORBA, eingesetzt werden, dominieren im Bereich von eingebetteten, verteilten Systemen domänenspezifische Laufzeitsysteme [SV06], um den besonderen Anforderungen, z.B. in Bezug auf Ressourceneinschränkungen, Rechnung zu tragen. Dabei ist in den letzten Jahren ein Trend zur Verwendung von modellgetriebenen Methoden zur automatischen Generierung dieser Laufzeitsysteme zu beobachten. Hierdurch können nicht-funktionale Aspekte, wie Ausführung im verteilten System durch Realisierung der Kommunikation und Absicherung von Quality-of-ServiceEigenschaften durch Auswahl relevanter Kommunikationsprotokolle, sichergestellt werden. Bei der Entwicklung kann dabei zwischen drei Arten von Entwicklern unterschieden werden. Experten für das Laufzeitsystem entwickeln generische Architekturen, die durch die Entwicklungswerkzeuge automatisiert an die Anwendung angepasst werden können. Komponentenentwickler stellen sowohl Software-, als auch Hardwarekomponenten zur Verfüg- 23 ung und müssen die Einbindung in die Laufzeitsystemarchitektur durch Bereitstellung entsprechender Schnittstellen bei Softwarekomponenten oder durch Entwicklung von passender Firmware bei Hardwarekomponenten sicherstellen. Anwendungsentwickler wählen schließlich werkzeugunterstützt die einzelnen Komponenten zur Realisierung der Anwendung aus und spezifizieren die zu berücksichtigenden nicht-funktionalen Anforderungen. In den derzeit verfügbaren Entwicklungswerkzeugen wird lediglich der Anwendungsentwickler bei der Erstellung durch modellgetriebene Werkzeuge unterstützt. Im Rahmen dieser Arbeit wollen wir eine weitergehende Unterstützung auch der Laufzeitsystementwickler, sowie der Komponentenentwickler, erreichen. Zur Umsetzung schlagen wir einen dreiphasigen modellgetriebenen Entwicklungsansatz vor. In jeder Phase kann der entsprechende Experte die relevanten Aspekte des Systems modellieren. Die einzelnen Phasen werden durch eine Modell-zu-Metamodell-Transformation verbunden. Dieser Beitrag diskutiert den verfolgten Ansatz und erläutert die Ergebnisse eines ersten Prototyps. Zunächst werden in Abschnitt 2 die zur Untersuchung verwendete Domäne erläutert und der Ansatz motiviert. Abschnitt 3 beschreibt die vorgeschlagene Vorgehensweise. Abschnitt 4 fasst den Beitrag zusammen und gibt einen Ausblick über die nächsten geplanten Schritte. 2 Beispiel für Anwendungsdomäne: Verteilte Sensor-Aktor-Systeme Im Rahmen des SOA Projektes1 wurde ein modellgetriebenes Entwicklungswerkzeug für verteilte Sensor-Aktor-Systeme entwickelt. Diese Systeme zeichnen sich durch die hohe Heterogenität der verwendeten Hardwarekomponenten aus. Im konkreten Fall wurden sowohl linuxbasierte Rechner, ZigBee-Sensorknoten mit dem Betriebssystem TinyOS, sowie Atmel 8-Bit-Controller ohne Betriebssystem unterstützt. Des Weiteren wurden auch sehr unterschiedliche Sensoren und Aktoren verwendet. Abbildung 1 zeigt einen im Projekt entstandenen Demonstrator. Abbildung 1: Demonstrator Durch Verwendung einer dienstorientierten Architektur konnte die Heterogenität für den Anwendungsentwickler abstrahiert werden [BSS+ 09]. Das System wurde als eine Menge von Softwarediensten interpretiert, wobei diese Dienste sowohl Softwarekomponenten zur Interaktion mit der Sensorik bzw. Aktorik, als auch Softwarekomponenten zur Entwicklung einer hardwareunabhängigen Berechnungsfunktion sein können. Diese Softwaredienste können durch das im Rahmen des Projektes entstandene Entwicklungswerkzeug vom Endanwender ausgewählt, den entsprechenden Hardwareknoten zugewiesen und konfiguriert werden. Die für die Ausführung der Anwendung notwendige Middleware wird durch einen modellbasierten Codegenerator generiert [BSS+ 08]. 1 http://www6.in.tum.de/Main/ResearchEsoa 24 Durch die hohe Vielfalt von Sensor-/Aktorsystemen musste das Entwicklungswerkzeug häufig erweitert werden. Beispiele hierfür sind das Hinzufügen neuer Dienste zur Umsetzung von Regelungsalgorithmen oder Kontrolllogiken, aber auch die Unterstützung neuer Hardwareplattformen. Der Aufwand für diese Integration stellte sich als sehr hoch heraus und setzte insbesondere gute Kenntnisse des Entwicklungswerkzeuges voraus. Im konkreten Fall wurde das existierende System aus Zigbee-Komponenten um Komponenten mit Ethernetunterstützung erweitert. Hierzu musste das Metamodell um Komponenten mit Ethernetunterstützung erweitert werden und die notwendigen Attribute definiert werden. Dabei erfolgte jedoch keine Trennung in die grundsätzliche Kommunikationsfähigkeit Ethernet inkl. Definition der notwendigen Attribute (z.B. IP-Adresse, Netzwerkmaske, Gateway) und die Beschreibung der Komponente, sondern ausschließlich eine Beschreibung der konkreten Komponente. Dadurch erhöhte sich der Aufwand bei der Beschreibung von weiteren Komponenten mit evtl. ähnlichen/gleichen Fähigkeiten. Zudem erschwerte diese Praxis die Wiederverwendung von Vorlagen für die Codegenerierung für Komponenten mit gleichen Funktionalitäten. Die Ähnlichkeit der Problemstellung zwischen Anwendungsentwicklung und Entwicklung des Modellierungs- und Codegenerierungswerkzeuges motiviert einen mehrstufigen Ansatz. Das Konzept der domänenspezifischen Entwicklungswerkzeuge zur Entwicklung von Systemen kann ebenso auf die Entwicklung von domänenspezifischen Entwicklungswerkzeugen angewandt werden. Das Ergebnis ist ein mehrstufiger Entwicklungsansatz, der im nächsten Abschnitt näher erläutert wird. 3 Ansatz Ziel des in diesem Beitrag vorgestellten Ansatzes ist die optimale Unterstützung der Entwickler durch einen modellgetriebenen, mehrstufigen Ansatz. Die Grundidee leitet sich dabei von dem allgemeinen Ansatz domänenspezifischer Sprachen bezüglich einer Modellhierarchie, wie in Abbildung 2 dargestellt, ab. In jeder Phase des Entwicklungsprozesses kann der jeweilige Experte die entsprechenden Informationen modellieren. Durch eine Modell-zuMetamodell-Transformation werden dann die Metamodelle für die nächste Phase generiert. describes instanceof M3: Meta-Metamodel describes instanceof M2: Metamodel describes instanceof M1: Model describes instanceof M0: Instances Die Stärken des modellgetriebenen Ansatzes mittels Abbildung 2: Modellhierardomänenspezifischer Sprachen ergeben sich insbesondere chie [SV06] bei der Entwicklung von gleichartigen Systemen. Dies ist nicht nur auf das eigentliche Endsystem beschränkt, sondern gilt auch für die zu erstellenden Entwicklungswerkzeuge. Im Fall von komponentenbasierten Systemen kann somit der Ansatz nicht nur für die Erstellung der Endanwendung durch Zusammenfügen der Komponenten, sondern auch schon auf die Entwicklung von ähnlichen Komponenten benutzt werden. Dieser Ansatz wurde im Rahmen des SOAProjektes umgesetzt. 25 HardwareSpecification * CapabilityType StringAttribute Capability * * Connector * Attribute * ConnectorAttribute IntAttribute EnumAttribute Abbildung 3: Metamodell der 1. Phase Insgesamt werden im derzeitigen Ansatz drei Phasen unterstützt: 1. Spezifikation der für das Laufzeitsystem relevanten Informationen durch den Laufzeitsystemexperten 2. Spezifikation der zur Verfügung stehenden Komponenten durch Komponentenhersteller 3. Spezifikation der Anwendung durch den Anwendungsentwickler Im Folgenden werden diese einzelnen Phasen näher erläutert. Modellierung der zur Beschreibung der Komponenten benötigten Attribute In der ersten Phase des Ansatzes können die Laufzeitsystemexperten spezifizieren, welche Informationen benötigt werden, um Komponenten zu beschreiben. Auf Basis der Modelle der ersten Phase können Regeln, Analysen und Schritte zur Codegenerierung festgelegt werden. Mittels komponentenunspezifischen Regeln können allgemeine Tests zur Korrektheit der Eingabemodelle der dritten Phase, wie zum Beispiel die korrekte Verschaltung von Komponenten, definiert werden. Durch die Implementierung von Analyse- und Konfigurationsalgorithmen kann festgelegt werden, wie zum Beispiel ein korrekter Schedule oder die Kanalbelegung / das Routing berechnet werden kann. Zudem wird auf Basis des Modells der ersten Phase die Codegenerierung für das Laufzeitsystem beschrieben. Dieser Code umfasst alle Funktionalitäten, die nicht komponentenspezifisch und typischerweise als Middleware realisiert werden. Abbildung 3 zeigt das zugrundeliegende Metamodell in Bezug auf die Beschreibung von Hardwarekomponenten. Das Metamodell erlaubt den Laufzeitsystemexperten die Definition von Funktionsklassen, wie z.B. Kommunikation, sowie von konkreten Funktionen, wie z.B. Ethernet, und der zur Beschreibung benötigen Attribute. Durch diese allgemeine Spezifikation von Fähigkeiten kann die Realisierung auf Laufzeitsystemebene unabhängig von den konkreten später verwendeten Komponenten auf Basis der Funktionalitäten und deren Attributeigenschaften erfolgen. So kann beispielsweise einfach geprüft werden, ob die vorhandene Bandbreite (spezifiziert im Attribut Speed von Ethernet) den Anforderungen der Anwendungen Rechnung trägt. Durch die sehr grundlegende Definition der 26 Abbildung 4: Beispielmodell der 1. Phase Beschreibung von Komponenten kann sichergestellt werden, dass das Metamodell ähnlich den Metamodell von UML-Klassendiagrammen sehr selten oder nie verändert wird. Das Metamodell der ersten Phase ist somit die Basis für die weiteren Schritte. Ein Ausschnitt des für das SOA Projekt verwendeten Modells wird in Abbildung 4 gezeigt. In diesem Modell werden die beiden Funktionsklassen P rocessingU nit und Com− munication, sowie jeweils eine konkrete Funktionalität CP U und Ethernet Ethernet beschrieben. Der große Vorteil des dreistufigen Ansatzes zeigt sich an dieser Stelle. Der Laufzeitsystemexperte muss nur die zurzeit unterstützten Funktionen und Attribute berücksichtigen und diese modellieren. Das spätere Hinzufügen von neuartigen Fähigkeiten oder zusätzlichen Attributen kann bei Bedarf erfolgen. Somit wird der Aufwand der ersten Modellierung reduziert, ohne eine spätere Erweiterbarkeit zu erschweren. Eine nachträgliche Erweiterung des Metamodells führt auch nicht zur Inkompatiblität alter Modelle der späteren Phasen: werden neue Fähigkeiten hinzugefügt, so sind die weiteren Modelle ohne Einschränkung nutzbar. Im Falle von zusätzlichen Attributen können Default-Werte benutzt werden, die sicherstellen, dass sich die Codegenerierung bei auf alten Modellen basierten Systemen nicht ändert. Ein ähnlicher Ansatz ist auch für die Softwarekomponenten möglich und wurde im Rahmen des Projektes umgesetzt. Modellierung der verfügbaren Komponenten Komponentenhersteller können in der zweiten Phase ihre bereitgestellten Komponenten beschreiben und die Codegenerierungsfunktionalität in Bezug auf ihre Komponenten ergänzen. Hierzu wird zunächst auf Basis des Modells der ersten Phase automatisch ein passendes Metamodell generiert, das nun in der zweiten Phase instanziiert werden kann. Die statische Grundstruktur des generierten Metamodells und ein Metamodell, basierend auf dem Beispielmodell der 1. Phase aus Abbildung 4, ist in Abbildung 5 zu sehen. Im generierten Metamodell lässt sich der Zusammenhang mit den Eingabedaten aus dem Modell der ersten Phase leicht erkennen aus Objekten sind Klassen entstanden. Diese können nun von den Herstellern dazu ver- 27 Hardware * Module BaseModule * ExtensionModule Capability CapabilityType1 ... * Capability1 Connector Connector1 ... Attribute1 ... ... Abbildung 5: Generisches und konkretes Metamodell der 2. Phase wendet werden, ihre Komponenten zu beschreiben. Dabei können Hersteller Werte für unveränderbare Attribute festlegen (z.B. CPU-Geschwindigkeit), mögliche Attributwerte einschränken (Begrenzung der Geschwindigkeit auf die von der Hardwarekomponente unterstützten Werte), Standardwerte für Attribute auswählen oder die Konfiguration für die nachfolgende Phase offen lassen (z.B. IP-Adresse). Abbildung 6 zeigt einen Ausschnitt des Modells der zweiten Phase für das Projekt. Im Beispiel beschreibt das Modell zwei Hardwaremodule: einen PC auf Basis eines Dual-CoreProzessors, sowie eine Ethernetkarte. Auf Basis der Informationen in diesem Modellierungsschritt können die Komponentenhersteller die Generierungsschritte des komponentenspezifischen Codes beschreiben. Dieser Code umfasst unter anderem die eigentliche Funktionalität der Komponente und Hardwareabstraktionsschichten. Das in der zweiten Phase entstehende Modell wird aufgrund der hohen Vielfalt verschiede- 28 Abbildung 6: Beispielmodell der 2. Phase ner Komponenten regelmäßig erweitert. Von dieser Erweiterung sind jedoch die bestenden Komponenten nicht betroffen, insofern sind alte Modelle basierend auf den ursprünglichen Metamodellen weiterhin kompatibel und von den Änderungen nicht betroffen. Ein weiterer Vorteil des Ansatzes ist die Möglichkeit, das für die Generierung notwendige Wissen zu kapseln. Dadurch kann der Schutz von geistigem Eigentum sichergestellt werden2 . Der vorgestellte Ansatz ist ebenfalls für die Beschreibung der verfügbaren Softwarekomponenten umgesetzt. Modellierung der Anwendung Die dritte Phase erlaubt schließlich dem Anwendungsersteller die Auswahl und Zusammenstellung der einzelnen Komponenten für die Anwendung ähnlich einem Baukastensystem, sowie deren abschließende Konfiguration. Die Festlegung von Werten und die Einschränkung der Werte für einzelne Attribute in der zweiten Phase führen hier zu einer deutlichen Vereinfachung des Aufwandes und kann dabei helfen Fehlkonfigurationen zu vermeiden. Abbildung 7 zeigt wiederum die Grundstruktur des generierten Metamodells und das zum Beispiel gehörende Metamodell der dritten Phase. Wie in dem Metamodell aus Abbildung 7 ersichtlich ist, kommt es in der dritten Phase zu einer starken Zunahme an unterschiedlichen Typen / Komponenten, welche lediglich eine Spezialisierung der bereits in Phase 2 vorhandenen Komponenten darstellen, z.B. EthernetCard Ethernet und P C Ethernet. Dies ist notwendig, um die vom Komponentenhersteller spezifizierten Wertebereiche korrekt widerzuspiegeln. Um in der nachfolgenden Codegenerierung nicht alle diese unterschiedlichen Typen / Komponenten berücksichtigen zu müssen, werden diese vor der Codegenerierung mittels einer eigenen Modell-zu-Modell-Transformation in die entsprechenden Basistypen umgewandelt und somit die Typhierarchie wieder deutlich vereinfacht. Ein zugehöriges Modell ist in Abbildung 8 zu sehen. Die modellierte Anwendung besteht dabei aus zwei PC-Modulen mit jeweils einer Etherneterweiterungskarte, welche für die 2 Die Unterstützung der Kapselung ist derzeit noch nicht implementiert 29 Abbildung 7: Generisches und konkretes Metamodell der 3. Phase spätere Anwendung geeignet konfiguriert werden. Auf Basis des Modells der dritten Phase wird die Codegenerierung ausgeführt. Dabei ist zu beachten, dass die Mechanismen der Codegenerierung bereits auf Basis der Modelle der ersten und zweiten Phase wie beschrieben durch den Laufzeitsystemexperten bzw. den Komponentenhersteller spezifiziert werden können. Implementierung Die Implementierung des Ansatzes erfolgte auf Basis des Eclipse Modeling Frameworks (EMF) [SBPM08]. Dieses stellt eine äquivalente Implementierung des Essential Meta Object Facility (EMOF) [OMG06] der Object Management Group Abbildung 8: Beispielmodell der 3. Phase 30 (OMG) dar und bietet eine reichhaltige Anzahl an Möglichkeiten zur Introspektie. Die Umsetzung der Modell-zu-Metamodell-Transformationen gründet dabei auf manueller Implementierung der Werkzeuganforderungen. Während die Generierung des Metamodells der zweiten Phase zielführend umzusetzen war, war die Generierung des dritten Metamodells deutlich erschwert. Dies ist darauf zurückzuführen, dass für diese Generierung neben dem Modell der zweiten Phase auch Informationen des Modells der ersten Phase notwendig waren, um Strukturinformationen über das zweite Modell zu erhalten. Dadurch baut die zweite Transformation teilweise auf einer generischen / variablen Basis auf und muss diese entsprechend weiterverarbeiten. Wegen der großen Unterschiede in den verschiedenen Modell-zu-Metamodell-Transformationen konnten bis jetzt auch noch keine nennenswerten Gemeinsamkeiten extrahiert werden. Vielmehr muss jede Transformation vom Entwicklungsteam neu implementiert werden, um den jeweiligen Anforderungen zu entsprechen. Die gegenwärtige Umsetzung bezieht sich dabei auf die Generierung der Metamodelle. Die Einbindung der Codegenerierung und Modellanalyse aus dem SOAAnsatz ist der nächste Schritt. Jedoch ist bereits jetzt eine wesentlich verbesserte Strukturierung des Modells durch die Trennung der ersten beiden Phasen erkennbar. Des Weiteren ist die Erweiterung der Modelle wesentlich vereinfacht und auch durch Entwickler ohne vertiefte Kenntnisse in unserem Ansatz möglich. Codegenerierung Der vorgestellte Ansatz bringt auch im Bereich der Codegenerierung einige Veränderungen mit sich. Grob lässt sich die Codegenerierung in zwei Bereiche aufteilen. Der erste Bereich beschäftigt sich mit der Generierung und Anpassung der Komponententreiber an die Anforderungen der Anwendung. Im zweiten Bereich wird schließlich das zugehörige Laufzeitsystem erstellt, welches als Container für die zuvor erstellten Komponententreiber (Komponenten) dient. Die Interoperabilität der beiden Codegenerierungen wird dabei über die Einhaltung vordefinierter Schnittstellen sichergestellt. Für die einzelnen Codegenerierungen sind unterschiedliche Personenkreise zuständig. So wird die Generierung der Komponententreiber von den Komponentenherstellern der jeweiligen Komponenten übernommen, während das Laufzeitsystem vom Werkzeughersteller erzeugt / konfiguriert wird. Hierdurch lassen sich die vorhandenen Expertisen besser nutzen, da sich die einzelnen Experten ausschließlich auf ihr jeweiliges Gebiet zu konzentrieren brauchen. Die Sicherstellung der Systeminteroperabilität wird dabei durch das Entwicklungswerkzeug übernommen. In der aktuellen Umsetzung ist der hier vorgestellte Ansatz der Codegenerierung noch nicht vollständig realisiert und integriert. Dies muss erst noch erfolgen und die Ergebnisse mit bestehenden Systemen verglichen werden. 4 Zusammenfassung Dieser Beitrag diskutierte einen neuen Ansatz zur mehrphasigen, modellgetriebenen Entwicklung von komponentenbasierten Systemen. Neben der Unterstützung der Anwendungsentwickler, steht dabei auch die Unterstützung von Laufzeitsystemexperten und Kom- 31 ponentenherstellern im Vordergrund. Domänenspezifische Entwicklungswerkzeuge werden heute insbesondere eingesetzt, um ähnliche Systeme vereinfacht zu entwickeln. Dabei werden die Gemeinsamkeiten der Systeme als Domänenkonzepte im Modellierungswerkzeug und dem Codegenerator gekapselt. Dieser Ansatz wird jedoch heute überwiegend für die Entwicklung von Systemen verwendet, nicht aber für die vom Entwicklungswerkzeug benötigten Metamodelle. Im Rahmen des vorgestellten Ansatzes wurde aufgezeigt, dass dies jedoch möglich und im Bereich von komponentenbasierten Systemen auch zu wesentlichen Verbesserungen führen kann. Vorteile sind im Besonderen eine wesentlich bessere Strukturierung und die Auftrennung der Entwicklung des modellbasierten Codegenerators in zwei Phasen in Bezug auf das Laufzeitsystem bzw. die Komponenten. Der Ansatz wurde am Beispiel eines Werkzeuges zur Entwicklung von verteilten SensorAktor-Systemen zunächst auf der Modellierungsebene getestet. Die bisherigen Ergebnisse deuten auf eine wesentlich vereinfachte Erweiterbarkeit des Systems hin. In den nächsten Schritten muss der Ansatz nun noch auf die Codegenerierung angewandt werden und der Ansatz im Vergleich zu dem bisherigen System evaluiert werden. Literatur [BSS+ 08] Christian Buckl, Stephan Sommer, Andreas Scholz, Alois Knoll und Alfons Kemper. Generating a tailored middleware for wireless sensor network applications. In Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, Seiten 162–169. IEEE, jun 2008. [BSS+ 09] Christian Buckl, Stephan Sommer, Andreas Scholz, Alois Knoll, Alfons Kemper, Jörg Heuer und Anton Schmitt. Services to the field: An approach for resource constrained sensor/actor networks. In 2009 International Conference on Advanced Information Networking and Applications Workshops, Seiten 476–481. IEEE, 2009. [OMG06] OMG. Meta Object Facility (MOF) Core Specification Version 2.0, Jan 2006. [SBPM08] Dave Steinberg, Frank Budinsky, Marcelo Paternostro und Ed Merks. EMF: Eclipse Modeling Framework. Addison-Wesley Professional, 2. Auflage, 2008. 32 [SV06] Thomas Stahl und Markus Voelter. Model-Driven Software Development: Technology, Engineering, Management. Wiley, 1. Auflage, May 2006. [Szy02] Clemens Szyperski. Component Software. Addison-Wesley Professional, Nov 2002. Model-based Decentralised Management of Product Flow Paths∗ Gustavo Quirós, Ulrich Epple Lehrstuhl für Prozessleittechnik RWTH Aachen University [email protected] Abstract: This paper is an extract from [Qui09], which presents the model of product flow paths as a novel reference model for performing product transport operations in a correct and safe manner within processing plants. Thereby, the management of product flow paths is defined as a collection of tasks which enable process control systems to embrace the model of product flow paths and apply it to its operations. Furthermore, the use of a formal model permits the automation of many of the engineering tasks that are necessary for this. 1 Introduction Many of the techniques used in process control engineering are not based on a well-defined theory, but rather on years of experience. The techniques used at present for controlling the movement of products in a plant mostly fall into this category. This is due in part to the fact that these movement operations are simple to understand and to carry out, when compared with the more complex dynamic control tasks that spawned the development of control theory. The main disadvantage of using a manual engineering approach is that it doesn’t scale well with the size and complexity of the plant. Effectively, designing proper control sequences for large and complex plants can prove to be a daunting task that must be handled by teams of engineers with an adequate amount of experience. Even then, the correctness of these designs is difficult to assert. Also, if any changes are made to the plant, then the entire design of the control logic must be revised and updated, incurring in more engineering effort. The availability of a formal model for the transport of material in processing plants would ease the tasks of designing and implementing the components of process control systems that automate the movement of products in a plant. Because of this, the model of product flow paths [Qui09] has been introduced as a novel reference model for performing product transport operations in a correct and safe manner within processing plants. Thereby, the management of product flow paths is defined as a collection of tasks which enable process control systems to embrace the model of product flow paths and apply it to its operations. Most importantly, the use of a formal model further permits the automation of many of the engineering tasks that are necessary for this, by supporting the automatic synthesis of product flow path management systems. ∗ This research has been partially funded by the DFG Research Training Group 1298 “Algorithmic synthesis of reactive and discrete-continuous systems” (AlgoSyn). 33 2 Product Flow Path Management According to the product flow path model, product flow paths are represented as objects in a process control system, together with their attributes and operations. A product flow path management system is a system that provides the functionality that is needed by a process control system in order to apply the concept of product flow paths to its operation. A product flow path management system must accomplish a collection of tasks that are required for the usage of product flow paths. The discovery of product flow routes [QME08] is a task which, given certain conditions, identifies valid flow routes through the plant that flow path objects can use to perform product transport operations. Since the life cycle of a product flow path begins when the flow path is created, and ends when the flow path is deleted, operations which manage the existence of product flow paths in the plant must also be carried out by a product flow path management system. Furthermore, before a product flow path is used, it must meet various conditions that assert the correctness of the corresponding product flow operation, such as the avoidance of potentially hazardous situations. The assurance of product flow paths [QE08] is the general task of providing the proper conditions for the operation of a product flow path in a plant. This comprises the tasks of allocating and locking product flow paths, as well as their counterparts of deallocating and unlocking flow paths. Once a product flow path is assured, it may be activated in order to begin a product flow operation. The activation and deactivation of a product flow path is executed by the product flow path management system. For this, the services of the process control system which are commonly available for interacting with plant devices may be used. During its operation, a product flow path must be monitored [QJE09] in order to supervise its correct operation and promptly detect any related anomalies. Also, the system must issue alerts with respect to product flow path alerts, such as when the monitoring task detects situations that are potentially hazardous, or when the assurance of a given flow path fails. Finally, the system should document the behaviour of product flow paths by recording, for every flow path, every transition between states that occurs during the flow path’s life, as well as the occurrence of every alarm that is issued by the flow path. The information that is generated by this task should be archived in a proper manner, for instance, in a local file or in a database system. Figure 1 shows the class diagram of the flow path management system model. 2.1 Decentralised Product Flow Path Management The management of product flow paths in processing plants may be implemented by following a traditional centralised approach. The main problem of following a totally centralised structure [Pol94] is that it offers a low availability of the process control functionality, because the failure of the process control computer affects the entire process. Therefore, the most common architecture used by process control systems at present is decentralised, where the functionality of process monitoring and control is spread across multiple process control computers. Because of this, we adopt decentralised techniques in the design of a product flow path management system. In doing this, many of the advantages of a decentralised approach can be foreseen as benefiting the management of product flow paths: the failure of a decentralised controller and its successive servicing only affect the operation of a limited number of flow paths, larger flow paths may be handled in a scalable manner, unrelated flow paths are handled independently and therefore more efficiently, and finally, the product flow path management system can be adapted to the plant in a more flexible manner. 34 Manage 1 * FlowRoute Origin FlowPathManager FlowPath 1 Use 0,1 Identifier * Manage 1 Target CreationTime Length Allocated CreateFlowRoute Elements Locked CreateFlowPath DiscoverFlowRoutes Active Alert Monitoring FlowPathLogger FlowPathAlert Type Timestamp Elements FlowPaths Allocate * Emit 1 Lock 1 Use * Activate LogFlowPathCreation Deactivate LogFlowPathState Unlock LogFlowPathDeletion Deallocate LogFlowPathAlert Delete StartMonitoring StopMonitoring Figure 1: Class diagram of the product flow path management system model. 2.2 Decentralised Component Model The decentralisation model that is followed in [Qui09] can be regarded as plantoriented: the decentralised system consists of a collection of active participants called components, and every component of the system corresponds to an element of the plant. This one-to-one mapping between plant elements and system components allows a clear and localised formulation of the algorithms that the system performs, because every component has complete access to the information regarding its local element, and no direct access to the information regarding the other elements in the plant. In this manner, the notions of information hiding and encapsulation from the methodology of object-oriented software design [GHJV95] are followed. In order for the algorithms to function in a decentralised manner, the components of the system must exchange information with one another, and in our system the components achieve this by sending and receiving messages. Thus, the technique of message-passing [Lyn96] is employed. The exchange of messages is restricted in a plant-oriented manner as well: every component has one communication port for every connector of its local element, and these ports are interconnected through bidirectional communication links in accordance with the connection relation of the plant elements. Thus, the communication structure of the decentralised system is an analogy of the plant layout, which means that components may only exchange messages with other components whose local plant elements are directly connected to their own local elements in the plant. This causes the flow of messages to be restricted to the same paths as the flow of products in the plant, which further means that there is a correspondence between flow routes and message routes. Rather than being a limitation, this communication scheme actually simplifies the design of the algorithms used by a product flow path management system, because within them every component of the system only executes the necessary operations which regard its own plant element, and delegates the rest of the required operations to the rest of the components in the route. Figure 2 shows the structure of a decentralised component-based system which corresponds to a sample filling station. The decentralised component-based approach presented here is inspired by geographical railway control as presented in [Pac04]. We hereby make an analogy be- 35 R15 T1 V1 P1 V5 J1 J3 V3 R1 T1 T3 R3 J4 R16 V6 J2 P2 P1 V1 V3 P2 R13 R5 R7 R14 V7 J4 V5 V2 R11 J1 R9 V6 R10 J2 R12 V7 R4 T4 V4 T2 R6 R8 V2 V4 T4 T2 Join J3 T3 Pipe Valve Pump Tank R2 Component Communication Figure 2: Graphical representation of a sample filling station plant (left), and a depiction of the decentralised component-based system which corresponds to it (right). There exists one component for every plant element, and the connection structure of the plant defines the communication structure of the system. tween railway structure and plant structure: whereas geographical control systems consist of logical objects which are laid out along the structure of the train track network, in the present approach, components are laid out in analogy to the structure of the plant. In this way, we benefit from the many advantages that geographical railway control has over the more traditional centralised techniques, such as the simplified construction, extension and maintenance of the system. As we will see, this also offers the opportunity of achieving the automatic construction of a decentralised system. In spite of the many similarities between railway networks and processing plants, it is not feasible to directly reuse the techniques already applied in railway control systems in order to control the flow of products in a processing plant, as there exist basic technological differences between these two kinds of systems. Rather, the flow path model presented in [Qui09] strives to satisfy the requirements for the operation of processing plants, while adopting and adapting useful ideas from other fields such as railway control. 3 3.1 Formal Models Abstract Plant Model In order to reason about product flow paths in a plant, a map of the plant is needed which represents the possible locations in the plant where products may be found as they flow, as well as the directions this flow may take. Such a representation is almost completely given already for any plant by its corresponding plant diagrams, be it P&ID or a similar CAE model. Nevertheless, these representations often carry ambiguities [SMU08]. Because of this, an abstract plant model is presented here which explicitly defines the possible locations of products in a plant, and the possible movement of products through the plant. This plant model is abstract because it represents all elements of the plant in a uniform way, considering those aspects which are important for modelling product flow and leaving out any additional details about the nature of the elements. Additionally, it is generic, meaning that any plant element may be directly modelled in it, even novel, unknown or uncommon elements. This model is based on 36 the RIVA model [JEM+ 05], and instances of the abstract plant model may in many cases be created for a given plant in a semi-automatic or fully-automatic manner using readily available plant data. As presented in [QME08, QE08, QJE09, Qui09], a plant is formally represented by a tuple (T, E, C, τ, , ◦) with sets of plant element types T , plant elements E and product connectors C. The set T contains an enumeration of the distinct types of elements found in the plant, and may be defined according to the application scenario. Every plant element is of a given type, and the function τ maps each element to its corresponding type. Elements have one or more connectors which may be used to link them to other plant elements, and the function maps every connector to the plant element which owns it. Finally, the binary relation ◦ represents the interconnection of element connectors as it is found in the physical plant: in an exclusive one-to-one manner. In accordance to this model, a product may find itself “inside” a given plant element at a given time, which means that the set of elements E corresponds to the set of possible product locations in the plant. Product connectors are considered interfaces that an element has, and are therefore not seen as product locations proper. As the graph of the plant represents the way the plant is structured, we consider that products are able to move from node to node through the edges of this graph: a product may move between an element e and one of its connectors c, and it may move between a connector c1 and a connector c2 if c1 ◦ c2 . However, in a real plant the movement of material is bound to many conditions, and the way in which we model these conditions in this work is the topic of the next section. 3.2 Flow Allowance Model Having a formal representation of the structure of a plant, we still need to model the flow of products through this plant structure, that is, we need to model how this flow occurs. Usually, the flow of products does not depend so much on the cause of the flow, but rather on characteristics of the plant itself, such as the shape of the containing elements, the interconnection of the elements, the settings of limiting elements like valves, etc. This property of determining the location and direction of flow in a passive manner is denoted as flow allowance in this work, which contrasts and complements the active role played by an element such as a pump in the movement of products. This is stated in the following conceptual definition: the property of a physical system of permitting material to flow through it is called flow allowance. As in the case of the abstract plant model presented earlier, the flow allowance model outlined here is generic, which allows it to model the possibility of flow through any element of a plant, even new or uncommon elements. This modelling power is required in order to guarantee the applicability of this approach to the widest possible range of plants and plant devices. We express the property of flow allowance using Boolean values or bits, where 0 represents the inhibition of flow and 1 represents the allowance of flow. The main reasons for this design decision are the simple interpretation of the values, the simple combination of the values in the case of parallel and serial connection of plant elements, and the requirement of this kind of discrete valuation for implementing the tasks of discovery, safety monitoring and safety locking of product flow paths. Because flow allowance is compositional, we explicitly model the flow allowance of each individual plant element, which implicitly models the flow allowance of the entire plant. Because flow allowance is in general a dynamic property, we model the flow allowance of a plant in terms of flow allowance settings which may be changed during the operation of the plant. Because flow allowance has a given direction, we model the allowance of flow in each of the different directions through a plant element. 37 c1 Pipe c1 c2 φe (c1 ) = (1, 1) φe (c2 ) = (1, 1) c2 Valve (closed) c1 c2 φe (c1 ) = (0, 0) φe (c2 ) = (0, 0) Holding Valve c1 c2 φe (c1 ) = (1, 0) φe (c2 ) = (0, 1) Join c1 c2 c3 φe (c1 ) = (1, 1) φe (c2 ) = (1, 1) φe (c3 ) = (1, 1) e cn Figure 3: Left: A plant element e ∈ E is modelled as a “product room” that may be entered and exited through its connectors c1 . . . cn , which are seen as “product doors”. Products may mix freely inside the element. Right: Flow allowance settings for various types of plant elements. A pipe is an element with two connectors which allow flow in both directions. A valve is a 2-connector element whose connectors may allow or inhibit flow in both directions; pictured is the flow allowance setting of a closed valve. A holding valve is a 2-connector element where one connector allows incoming flow only while the other allows outgoing flow only. Finally, a 3-way pipe join is a 3-connector element whose connectors allow flow in both directions. Figure 3 shows the way in which the flow allowance of a plant element is modelled. A flow allowance setting φe of an element e corresponds to an assignment of a pair of Boolean values to every connector c of e. The first of these values represents the allowance of input flow through this connector and into the element; consequently, the second value represents the allowance of output flow through this connector and out of the element, as shown in Figure 3 (left). These values are individually given I O by the functions φIe and φO e respectively, such that φe (c) = (φe (c), φe (c)). By specifying the input and output flow allowance at every connector of the element e, a flow allowance setting φe describes the flow allowance of e at a given time, where a given control state of the element is in effect. Figure 3 (right) shows some examples of flow allowance settings for several plant elements. Most common plant devices have a single interior room where all products that enter the device are able to mix. Therefore, all these devices may be directly modelled by a plant element e ∈ E as shown in Figure 3. However, some plant devices, most notably heat exchangers [VM99], have two or more product cavities that are isolated from each other, and therefore permit the flow of two or more products through them without causing them to mix. For these devices, a different modelling technique is needed, which models every internal product cavity as a unique element e ∈ E, effectively requiring more than one element to model a single plant device. 3.3 Flow Steps and Flow Routes As presented in [Qui09], a flow path corresponds to a section of the plant which is a route that may be used by a product to flow through the plant. Consequently, we denote this plant section as a flow route, and distinguish it from the actual flow path object which is related to it and which manages the product flow path and executes its corresponding operations. The routes of product flow are modelled as sequential paths through the plant. There are several reasons for this design decision, and by modelling 38 e e c c1 e c2 c O I ∃φe ∈ Φ(e) : φO ∃φe ∈ Φ(e) : φI e (c) = 1∃φe ∈ Φ(e) : [φe (c1 ) = 1, φe (c2 ) = 1] e (c) = 1 e1 e1 c11 e1 c11 ∈ S I ... e2 c21 e2 c22 c21 e2 c22 ∈ S M en ... cn1 en cn1 en ∈ S F Figure 4: Above: Scenarios of an initial flow step (left), middle flow step (centre) and final flow step (right). Below: A sequential flow route e1 e2 . . . en . flow routes as simple paths through the plant we achieve a useful model that is accurate and comfortable to work with while at the same time expressive enough to handle both simple and complex plant designs. As a product flows through the plant, it moves through several plant elements according to the respective flow allowance setting of each of the elements. Because of this, we first define the possible ways in which a product may flow within each plant element by defining the set of flow steps of the plant as a set of sequences of elements and connectors. Later on, we may use this definition to build up flow routes by joining several flow steps, one after the other. Flow steps are classified as initial, middle and final flow steps. These attributes refer to the position of each flow step within a complete flow route, and also correspond to the three possible scenarios of sequential product flow within an element which are shown in Figure 4 (above). Initial flow steps represent the flow of a product from the interior of an element e to one of its connectors c. Middle flow steps represent the flow of a product that enters an element e through one of its connectors c1 and leaves e through another one of its connectors c2 . Lastly, final flow steps represent the flow of a product that enters an element e through one of its connectors c and reaches the interior of e. In this way, the set of flow steps S contains all possible flow steps which may be used to construct flow routes in the plant. Building upon our definition of flow steps, we can now formulate the concept of a flow route of the plant. Since the possible locations of products in the plant correspond to the set E of elements of the plant, and since a flow route is given by a sequential path through the plant which is permitted by the flow allowance model of the plant, then a flow route must begin with an initial flow step, and end with a final flow step. Thus, the meaning of a flow route is the ability to move material from e1 , represented by the initial flow step, to en , represented by the final flow step, along a sequence of intermediate elements, represented by middle flow steps. Flow routes are free from any repeated items. The restriction is important and has been included in the definition of flow routes in order to avoid cycles, which simplifies the representation of flow routes as data structures and the algorithms which work with these flow routes. Also, the modelling of simultaneous bidirectional flow between any two elements in the plant is avoided as a consequence, because a flow route where no element appears twice represents a form of “forward only” flow, which best describes the intended and assumed flow of products in processing plants. 39 flow ... ei ... en ... e1 ej mixture ... leak Figure 5: A flow route r1 = e1 . . . ei . . . en , and a corresponding branch flow route r2 = . . . ej . . .. Product flow is intended along the flow route from e1 to en . Additional outgoing flow from ei to the branch flow route represents a product leak. Likewise, additional incoming flow to ei from the branch flow route represents a product mixture. 3.4 Product Leaks and Product Mixtures In an enclosed flow route, products that are able to flow along the route are not able to deviate from the route and leave it. At the same time, other products are not able to flow into the flow route and mix with the product flowing along the route. Thanks to these two properties, an enclosed flow route effectively isolates the products within the route from other products which are found outside of the route. These two properties are, respectively, the avoidance of product leaks and product mixtures along the flow route. Based on the abstract plant model and the flow allowance model, the definition of enclosed flow routes at a given flow allowance state has the intention of identifying general scenarios which correspond to undesired and potentially hazardous situations that may arise during the usage of a product flow path. This model-based approach defines an aspect of safety which regards the avoidance of these particular situations. A flow route r2 which leaves or joins a flow route r1 is called a branch flow route. Figure 5 shows a flow route and a corresponding branch flow route which stems out from it. In order for the flow route to be enclosed, it must be free from product leaks and mixtures, which means that both incoming and outgoing flow to and from the route must be blocked by the elements in every neighbouring branch flow route. In order to define our notion of product leaks and mixtures, we identify two subclasses of plant elements: product sources (E ↑ ) and product sinks (E ↓ ). The former are elements which can yield material that may flow to other points in the plant, and the latter are elements which can consume material which flows from other points in the plant. With this, a product leak occurs in a flow route r1 when there exists a diverging open flow route r2 which begins at an element ei in r1 and ends at a product sink element in E ↓ . In turn, a product mixture occurs in a flow route r1 when there exists a joining open flow route r2 which begins at a product source element in E ↑ and ends at an element ei in r1 . In this way, we have a precise characterisation of product leaks and mixtures using the abstract plant model and the flow allowance model. These modelled situations represent a necessary condition for actual leaks and mixtures of products along a flow route in the plant, and may be used by a product flow path management system to both detect and prevent potentially hazardous situations in the plant. 40 Explore RIVA Parameter Files iFBSPro Read Synthesis (Tcl) Tks Instantiate and Parametrise Engineering Station Flow Path Management iFBSPro Figure 6: Synthesis of a product flow path management system from a RIVA model and parameter files. 4 Model-based Synthesis One of the advantages of the decentralised component model architecture that has been adopted in this work is that it enables a simple way to automatically construct a component-based system for a given plant, based on the abstract model of this plant. This synthesis approach is therefore regarded as model-based, and can be compared to similar approaches like domain-driven design [Eva03], model-driven architectures [MSUW02] or the use of domain-specific languages [vDKV00]. The main advantage of such techniques is that the model may be created by experts from the application domain, without requiring any knowledge about the desired system. Also, errors are easier to detect in the model than in the corresponding system. As seen in Figure 2, the deployment structure of a decentralised product flow path management system follows the structure of the plant. Therefore, if a machinereadable representation of the formal plant model is available, an algorithm may read this representation and, based on the information contained therein, create and configure the objects of a decentralised product flow path management system that corresponds to the plant. After the execution of the synthesis algorithm, the decentralised product flow path management system is ready to begin its operation. Additionally, proper communication links have been established among the decentralised controllers, such that the execution of every product flow path management operation is possible, even for flow paths whose elements span multiple decentralised controllers. A prototypical implementation that is presented in [Qui09] accomplishes this form of system synthesis based on a RIVA model of the plant. The synthesis task is implemented as a program written in the Tcl language, and Figure 6 depicts the general operation of this program. The synthesis program uses an extension for Tcl (Tks), which enables the program to access function block servers (iFBSpro) using the ACPLT/KS [Alb03] protocol. When the program is executed in an engineering station machine, the program connects to a server that hosts an instantiated RIVA model of the plant, and explores this model by performing a traversal of the object tree in the server. Based on the information found in this model, the synthesis program creates and parametrises objects in one or more servers that are designated to host the target system, and these objects correspond to the instance model of a flow path management system. Also, the synthesis program reads several parameter files from the engineering station where the program executes, which tell the program in which server to place the decentralised components of the target system that it creates, and how to configure these objects in order for them to function properly. 41 Figure 7: Left: The pumping station. Right: PCS 7 system and flow path management system. The prototypical flow path management system has been successfully synthesised and used with a model pumping station at the Chair of Process Control Engineering, which is a scaled-down industrial plant that is used for hands-on teaching about process control engineering to undergraduate students. This plant is shown in Figure 7 (left). Although small in size, the plant features state-of-the-art plant devices, control systems, operator and engineering stations and communication infrastructure which collectively reflect the technological environment found in modern industrial settings. Therefore, it serves well for the purpose of testing the application of this technology to real plants. The access to online plant data, which allows the flow path management system to determine the current flow allowance state of the plant, was achieved with the help of a Siemens PCS 7 process control system as shown in Figure 7 (right). 5 Conclusions The model of product flow paths has been introduced in [Qui09] as a novel attempt to provide a formal framework for the correct execution of product flow operations in processing plants. This model is centred around the idea of a product flow path, which is a software object that is responsible for controlling, monitoring and documenting the movement of products along a determined flow route in the plant. Thereby, the management of product flow paths comprises the automated tasks that are necessary for the adoption of the product flow path model within a process control system. The automation of product flow path management tasks requires precise information about the possibility of product flow in the plant, and this is provided by means of a formal model that represents the structure of the plant and the flow allowance of the elements in the plant. Based on this model, a formal definition of the concept of a product flow route in a plant has been given. Also, the properties of a flow route at a given flow allowance state of the plant have been formulated in a way which may be used by algorithms to detect potentially hazardous situations such as product leaks and product mixtures. This formal framework conforms the base of an algorithmic solution for the automation of product flow path management tasks. This work has presented a decentralisation scheme that may be applied to the tasks involved in the management of product flow paths in a plant. Inspired on the decentralised operation of geographical railway control systems, a model for designing and implementing decentralised product flow path management systems has been devel- 42 oped by following a decentralised component-based approach, where the structure of the decentralised system follows the structure of the corresponding plant. The objects of a decentralised product flow path management system may be distributed across multiple controllers in a process control system. An automatic synthesis approach for this kind of systems has been developed, which is based on a formal model of the structure of the plant, and on the flow allowance model of the elements in the plant. By accessing the information in these models, a synthesis algorithm automatically creates and parametrises the objects of a product flow path management system, which is then ready to begin its operation. This model-based synthesis technique replaces the task of constructing a flow path management system for a plant with the simpler task of creating and verifying a model of the plant. A prototypical implementation of the technology presented in this work has been developed as a proof of concept. A decentralised product flow path management system is realised as a collection of function block servers which host function blocks that correspond the flow path objects, the decentralised components and the rest of the objects of this system. Furthermore, the decentralised components communicate with each other and across the servers of the system. The automatic synthesis approach described in this work is implemented for this prototype by means of a synthesis program that explores a RIVA model of the plant and based on the information contained therein, creates and parametrises the objects of a decentralised product flow path management system for the modelled plant. This prototypical product flow path management system was tested with real-life pumping station, where the corresponding flow path management system was connected to a process control system of the plant in order to allow the decentralised algorithms to operate with online plant data. References [Alb03] H. Albrecht. On Meta-Modeling for Communication in Operational Process Control Engineering. PhD thesis, RWTH Aachen University, Düsseldorf, Germany, 2003. [Eva03] Eric J. Evans. Domain-Driven Design: Tackling Complexity in the Heart of Software. Addison-Wesley Longman, Amsterdam, 1. a. edition, September 2003. [GHJV95] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design patterns: elements of reusable object-oriented software. AddisonWesley Professional, 1995. [JEM+ 05] R Jorewitz, U Epple, A Münnemann, R Böckler, W Wille, and R Schmitz. Automation of Performance Monitoring in an Industrial Environment. In PCIC Europe 2005, 2nd European Conference on Electrical and Instrumentation Applications in the Petroleum and Chemical Industry, pages 116–120, Basel, Switzerland, Oct. 26-28 2005. [Lyn96] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996. [MSUW02] Stephen J. Mellor, Kendall Scott, Axel Uhl, and Dirk Weise. ModelDriven Architecture. Advances in Object-Oriented Information Systems, 2426:233–239, 2002. [Pac04] Jörn Pachl. Railway Operation and Control. VTD Rail Publishing, Mountlake Terrace, USA, 2004. [Pol94] Martin Polke, editor. Process Control Engineering. VCH Verlagsgesellschaft, Weinheim, Germany, 1994. 43 44 [QE08] Gustavo Quirós and Ulrich Epple. From railroads to processing plants: Decentralised automatic assurance of product flow paths. In EKA 2008, Entwurf komplexer Automatisierungssysteme: Beschreibungsmittel, Methoden, Werkzeuge und Anwendungen, Magdeburg, Germany, 1517 April, 2008. [QJE09] G. Quirós, R. Jorewitz, and U. Epple. Model-based Safety Monitoring of Product Flow Paths. In Breitenecker F., Troch I. (Hrsg): MATHMOD 2009: 6th Vienna Conference on Mathematical Modelling, Vienna, Austria, Feb. 11–13, 2009. AGRESIM Report Nr. 35. ARGESIM / ASIM. [QME08] Gustavo Quirós, Martin Mertens, and Ulrich Epple. Function blocks for decentralised analysis of product flow paths. In ETFA 2008, 13th IEEE International Conference on Emerging Technologies and Factory Automation, Hamburg, Germany, 15-18 September, 2008. [Qui09] Gustavo Quirós. Model-based Decentralised Automatic Management of Product Flow Paths in Processing Plants. PhD thesis, submitted to RWTH Aachen University, 2009. [SMU08] Schmitz St., Schlütter M., and Epple U. R&I - Grundlage durchgängigen Engineerings. In VDI-Berichte 2032, Automation 2008: Lösungen für die Zukunft, pages Kurzfassung: S. 55–59, Langfassung: CD, Düsseldorf, June 2008. VDI-Verlag. [vDKV00] Arie van Deursen, Paul Klint, and Joost Visser. Domain-specific languages: an annotated bibliography. SIGPLAN Not., 35(6):26–36, 2000. [VM99] Wilhelm R. A. Vauck and Hermann A. Müller. Grundoperationen chemischer Verfahrenstechnik. Wiley-VCH, Weinheim, 11, revised and enlarged edition, 1999. 1,2 2 1,2 1 2 45 , 46 , Plant Signals Software Component 1 Software Component 2 Plant Roboter Angle1 Angle2 Velocity Conveyor Belt Start Velocity Position Packaging Start Plant Model Robot Plant Model Conveyor Belt 47 Robot PLC 1 PLC 2 Start Belt Angle 1 Software Module 1 Start Belt Belt Position Software Module 2 Start Belt BUS Start Belt 48 , , Xtext Grammar generate Metamodel MetaModel Modeling Tool Chain Simulation Tool Chain instantiate PSM Eclipse Text Editors generate PIM generate generate Model Simulation Model OSGi Runtime 49 , , Simulink Model RTW Embedded Coder C-Code Generation .c Code Automatic Wrapping OSGi Bundle 50 <<interface>> Plant Signal 1 real Angle .c Code OSGi Service 51 , 52 , 53 , 54 , Static and Dynamic Boundary Value Analysis Stephan Weißleder [email protected] Abstract: Model-based testing is a very popular testing technique. It is often used to design test cases automatically. Much of the existing work on automatic modelbased test generation is focussed on automatically creating abstract test cases that are focussed on, e.g., evaluating guard conditions or traversing transition sequences. The selection of concrete input parameters that enable these abstract test cases is an important problem. In this paper, we present and compare two existing approaches to input parameter selection: static and dynamic boundary value analysis. 1 Introduction Model-based testing is an important testing technique that is based on comparing the system under test (SUT) to formal specifications in the form of models. The advantages of this technique are automatic test design and reduced test maintenance costs. Furthermore, the creation of formal test models also helps validating requirements and supports test-first approaches. In this paper, we use UML state machines [Obj07] as test models. Coverage criteria are popular means to measure the fault detection capability of test suites. They are also used to steer the test generation [HLL94, CM94, LH01, AOH03, KLPU04]. Several coverage criteria have been proposed and shown to be useful. Coverage criteria can be compared using subsumption relations. Automatic model-based test generation with behavioral specifications has been investigated for several decades [DF93, BJK05, UPL06, Utt08]. Many existing approaches are focussed on the generation of abstract test cases, i.e., test information about required input and expected output without concrete input parameter values. The selection of meaningful input parameters, however, is an important problem. Input parameters can be grouped to equivalence classes (partitions) [WJ91, BW00, Nta01, DDB+ 05]. The types of input parameters can be ordered or unordered. For ordered types, e.g., integer or double, boundary value analysis (BVA) is an important means of selecting proper representatives of partitions. Experience has shown that many faults occur close to boundaries of the partitions [WC80, CHR82]. In this paper, we present and compare static and dynamic BVA for UML state machines as two flavors of BVA. The paper is structured as follows. In Section 2, we present an example test model that is used for further explanations. We introduce static boundary value analysis in Section 3 and dynamic boundary value analysis in Section 4. In Section 5, we compare both approaches. Finally, we present conclusion, discussion, and future work in Section 6. 55 2 Example In this section, we shortly describe the used example. It consists of a sorting machine test model describing the behavior of a machine that wraps up an object and subsequently sorts the resulting package depending on its size. A possible application field of such machines can be found in post offices. idle / recognize() object inserted / initialize() detectItemEvent(object : Item) / detectItem(object) [recognized == false] [recognized == true] storePackageEvent object fits in package object evaluated [width >= 20 and width <= 30] storePackageEvent object recognized object not recognized storePackageEvent [width < 20] [width > 30] object is too small object is too big storePackageEvent Figure 1: State machine of a sorting machine. Item <<Use>> SortingMachine height : Integer height : Integer width : Integer width : Integer recognized : Boolean recognize() : Boolean detectItem(Item) initialize() context: SortingMachine::recognize() post: if(height@pre < 20) then recognized = true else recognized = false endif context: SortingMachine::detectItem(object : Item) post: (height = (object.height * 2) + 2) and (width = (object.width + 2) * 2) Figure 2: Class diagram of a sorting machine. Figure 1 shows a state machine and Figure 2 shows the corresponding class diagram of the sorting machine. The sorting machine’s task is to sort items depending on their size after wrapping them up. The operations of the class SortingMachine are referenced from the state machine. The operations’ postconditions influence the behavior of the state machine. For instance, the size of the package is described in the postcondition of the operation detectItem(Item). The diagrams define the rules for the packaging as follows: The original width of the object should be doubled by foam plus two extra size units for each side of a plastic box: (width = (object.width + 2) ∗ 2). The height is handled as follows: (height = (object.height ∗ 2) + 2). The sorting is determined by the postcondition of recognize() and by the guard conditions of the outgoing transitions of the states object recognized and object evaluated: Objects that are too tall are sorted out using the guards of the outgoing transitions of state object evaluated. These objects are considered as not recognized. The remaining objects are sorted depending on their width. The values of height and width of the parameter of detectItem(Item) both influence the packaging. 56 3 Static Boundary Value Analysis The selection of meaningful representatives from input partitions is an important problem. Boundary value analysis is focussed on boundary values of partitions, i.e., values whose distances to representatives from other partitions is below a certain threshold distance. For instance, for a guard condition x > 0, 1 is a meaningful boundary value for x. The question is how to derive these boundary values for automatically generated tests. [x = y] A [x >= y] B A [x = y + 1] [x > y + 1] B Figure 3: Semantic-preserving test model transformation for static boundary value analysis. In static boundary value analysis, boundary value analysis is included by static changes. In model-based test generation, this means transforming the test model. As an example, Simon Burton defines heuristics in his PhD thesis [Bur01] that are used to transform the test model, e.g. by splitting one inequation of the test model into several ones. For instance, he transformed an expression that corresponds to a guard [x >= y] into three guards [x = y], [x = y + 1], and [x > y + 1]. Figure 3 presents this transformation applied to a simple UML state machine. The idea of this transformation is that the satisfaction of single guards forces the test generator to select boundary values for the guard variables: The satisfaction of, e.g., All-Transitions [UL06, page 117], requires the satisfaction of each guard and, thus, the inclusion of static BVA. There are similar approaches for model checkers or constraint solvers that include the transformation or mutation of the test model. For instance, the tool Qtronic [Con] implements the approach of static BVA. Figure 4 depicts the transformed sorting machine for static BVA. / initialize() object inserted / recognize() object evaluated idle detectItemEvent(object : Item) / detectItem(object) [recognized == false] [recognized == true] [width = 20 and width <= 30] storePackageEvent storePackageEvent [width = 21 and width <= 30] object fits in package object not recognized [width > 21 and width <= 30] object recognized [width >= 20 and width = 30] [width = 31] [width > 31] [width >= 20 and width = 29] [width >= 20 and width < 29] [width = 19] storePackageEvent object is too small [width < 19] object is too big storePackageEvent Figure 4: Static boundary value analysis for the sorting machine. The advantages of this approach is the easy implementation and the linear test effort. As we will see in Section 5.1, however, this approach has also several shortfalls. 57 4 Dynamic Boundary Value Analysis In dynamic boundary value analysis, the boundary values are defined dynamically during the test generation process. In contrast to static BVA, the generated boundary values of dynamic BVA are specific for each abstract test case. There are several approaches to implement dynamic BVA. In this section, we present a short list of such approaches. Our own approach is called abstract backward analysis. It is based on the weakest precondition calculus [Dij76, Whi91, CN00] and on searching backward. During the generation of abstract test cases, all necessary information to enable the abstract test case is collected and transformed into constraints of input parameters. As a result, the abstract test case also contains constraints about the enabling input parameters. These constraints define partitions and can, thus, be used for BVA. This approach has been implemented in the model-based test generation prototype ParTeG [Wei, WS07, Wei09a]. In this implementation, the test generation algorithm starts at certain model elements that are specified by the applied structural coverage criterion and iterates backward to the initial node. We illustrate the approach of dynamic BVA for satisfying All-States [UL06, page 115] on the sorting machine in Figure 1. We show the creation of one test case that should visit the state object is too big: Since there is an obvious path back to the initial node, the path search is not the main problem. Instead, we focus on creating the weakest precondition. Traversing two transitions backward, the algorithm collects two guard expressions: width > 30 and recognized = true. The next transition references the operation recognize(), whose postcondition is used to transform recognized = true into the weakest precondition height < 20. The next transition references a postcondition that is used to replace the system attributes height and width with input parameters. The results of the transformation are the two expressions (object.width + 2) ∗ 2 > 30 and (object.height ∗ 2) + 2 < 20, respectively (see postconditions in Figure 2). These expressions can then be transformed to object.width > 13 and object.height < 9. The generated abstract test case is valid. The remaining task is to identify the concrete input values: object.width is set to 14 and object.height is set to 8. The result is a concrete test case that visits the intended state object is too big and also satisfies the boundary-based coverage criterion Multi-Dimensional [KLPU04]. There are no test model transformations necessary. However, this approach makes high demands on the used test generator. Furthermore, searching backward results in several limitations concerning the evaluation of complex mathematical functions. There are further approaches to dynamic BVA that are based on searching forward. For instance, an evolutionary approach can be used to create tests that cover certain parts of the model: A fitness function that returns good fitness values for parameters that are close to partition boundaries results in test cases with such input parameters that are close to these boundaries. Furthermore, any standard test generation approach can be combined with a constraint solver that is able to include linear optimization, e.g., lp solve [BEN04], for generating input parameter values. Besides the presented approaches to dynamic BVA, there are industrial approaches to support dynamic BVA for automatic test generation with UML or B/Z [KLPU04, Sma]. 58 5 Comparison of Static and Dynamic Boundary Value Analysis In this section, we compare static and dynamic BVA. The first difference of both approaches is obvious: Static BVA is focussed on revealing faults at the guard and, therefore, transforms the guard. It assumes that the newly created guard conditions are feasible. In contrast, dynamic BVA is focussed on finding input parameters that allow to get as close as possible to the boundary values of each abstract test case’s guard conditions. In the following, we compare both approaches with respect to the fault detection capabilities and the costs of the correspondingly generated test suites. 5.1 Fault Detection Capabilities The dynamic approach for BVA has some advantages over the static one concerning their fault detection capabilities. We present two of the most important advantages. First, it is not guaranteed that the concrete attribute values of the guards can be equal to the constants they are compared to. For the example of the sorting machine, it would be necessary to create boundary values for [x = y + 2] instead of [x = y + 1] because x is twice the value of an integer input parameter and y is assumed to be an even number. Thus, we consider BVA important for the place where input parameters are specified and not where they or derived attributes are used (at the guard). The reason is that the input parameters are used to steer the SUT, and there are many situations in which the attributes of the transition guard cannot be directly accessed. Figure 5 shows a test model that is [x = y] C ev(i) / x = 3*i A [x = y + 1] [x > y + 1] B Figure 5: Problematic scenario for static boundary value analysis. transformed as proposed for static BVA: The value of x is set to three times the value of the input parameter i. If we assume that x, y, and i are integers and y is fix, it is easy to see that at most two of the three guards can be satisfied and that x = y and x = y + 1 can never be jointly satisfied by any set of test cases for one test model. As a consequence, at most one of the corresponding boundary values will be selected for test generation - the remaining one is a random value for x > y + 1. In contrast, the dynamic approach creates partitions on the input values and selects values that are closest to the boundary, e.g. if y is divisible by 3, then i = y/3 and i = y/3 + 1 are selected, which results in x = y and x = y + 3, respectively. The static approach can be extended by including static analysis and creating the transition guard [x = y + 3] instead of [x = y + 1]. This would solve the issue of infeasible guard values for the presented scenario. There may be, however, several paths leading to that guard, e.g., one that sets x three times the value of an input parameter and one that sets it to the value times seven. Figure 6 shows a corresponding state machine. In this case, several transitions with new guards are created. Due to overlapping guards, 59 [x = y] ev(i) / x = 3*i [x = y + 3] C [x > y + 3] A B [x = y + 7] ev(i) / x = 7*i [x > y + 7] Figure 6: Different computations for the same input parameters. this may result in an indeterministic model. For instance, the satisfaction of [x = y + 7] implies the satisfaction of [x > y + 3]. Since all transitions have the same effect and target state, however, this indeterminism has no effect. This example is also an example for the violation of the Markov property; this property states that only the current state machine state and the future input are important for future behavior. As a consequence, the traversed transition sequences are important and, thus, the transformation of guard conditions into trace-specific conditions of input parameters is important. In a scenario where x is increased depending on the number of transition loops, this would result in a potentially infinite number of additional guards to cover all possible paths, which makes this approach infeasible for such scenarios (see Figure 7). [x = y] ev1 / x = x@pre + 1 [x = y + 1] C ev2 A [x > y + 1] B [x = y + 2] [x > y + 2] ... Figure 7: Boundary values depending on the number of loop iterations. Second, the statically defined boundary values only have to be included in at least one test case. As shown above, there might be several paths leading to the transformed guard condition. Splitting the guard condition as presented for the static approach has the effect that only one of these paths has to satisfy a certain boundary value: The satisfaction of any control-flow-based coverage criterion only demands to test a guard without considering the transition sequence that leads to it. So the number of transition sequences per tested guard condition for which BVA does not necessarily have to exceed 1. Figure 8 depicts such a scenario: Satisfying [x = y] for the event ev1 implies that it is not necessary to satisfy this guard for the event ev2. In contrast, the dynamic approach includes BVA for each created abstract test case. Transforming the test model graph into a tree could help to solve this issue for the static approach. This is, however, infeasible for test models with transition loops. [x = y] ev1 C ev2 A [x = y + 1] [x > y + 1] B Figure 8: Another problematic scenario for static boundary value analysis. 60 Finally, we also created two test suites for the combination of Multiple Condition Coverage [UL06, page 114] and Multi-Dimensional [KLPU04] for dynamic BVA as provided by ParTeG and for Multiple Condition Coverage on a transformed model for static BVA as proposed by Burton. We applied mutation analysis [Ham77, DLS78, OLR+ 96, ABLN06, SW09] on the SUT to compare the fault detection capabilities of the test suites. We used the five sufficient mutation operators identified by Offutt et al. [OLR+ 96], the Missing Condition Operator [BOY00], and the Transition Target Operator, which changes the target state of a transition’s representation in the SUT. Mutation analysis for the sorting machine with dynamic BVA results in detecting 71 mutants, whereas the static approach is only able to detect 58 mutants. Amongst others, this is caused by infeasible guard conditions of the static approach. This also influences the satisfaction of the coverage criterion Multiple Condition Coverage: The dynamic approach satisfies 100 % of Multiple Condition Coverage, the static approach only 81 %. We also applied mutation analysis for the redundant test model of an industrial train control test model as presented in [Wei09a]: The test suite for the static approach detected 834 mutants. The test suite for the dynamic BVA detected 839 mutants. Thus, the presented theoretic advantages of dynamic over static BVA are fortified by two experiments (see Table 1). Test Model Sorting Machine Train Control (Industrial) Static BVA 58 834 Dynamic BVA 71 839 Table 1: Detected mutants for static and dynamic boundary value analysis. 5.2 Test Costs Although the static BVA has a lower fault detection capability than the dynamic BVA, it still increases the fault detection capability compared to the application of Multiple Condition Coverage on the original test model. Since there are at most 3 additional transitions for each (in-)equation of each guard, the static approach results in linear effort. Thus, it is a cheap possibility to increase the fault detection capability of the test suite. Compared to this, the dynamic BVA results in higher effort measured in the number of test cases. This is caused by the fact that dynamic BVA is done for each abstract test case, and each test case can have restrictions for several input parameters that may also influence each other (cf. the triangle classification problem [Mye79, UL06]). For each test case, the satisfaction of a boundary-based coverage criterion results in exponential effort depending on the number of input parameters. With pair-wise input parameter selection, this effort might be decreased. Test Model Sorting Machine Train Control (Industrial) Static BVA 6 261 Dynamic BVA 9 759 Table 2: Number of test cases for static and dynamic boundary value analysis. 61 This is fortified by the two examples: For the sorting machine, the static approach creates 6 test cases and the dynamic one 9 test cases. For the industrial test model, the static approach results in 261 test cases and the dynamic approach in 759 (see Table 2). The 759 concrete test cases were generated from 258 abstract test cases. The significant increase of the test suite size for detecting the last mutants was expected in case studies [ABLN06]. 6 Conclusion, Discussion, and Future Work In this paper, we presented and compared the static and the dynamic approach to boundary value analysis. We used an example of a sorting machine to illustrate the two different approaches and to show the corresponding impacts. We also used a test model of an industrial cooperation for our experiments. We applied mutation analysis to measure the impact of both approaches. There are case studies that show that mutation analysis is a good predictor for the test suite’s fault detection capability of real faults [ABL05]. Correspondingly, the result of our comparison is that dynamic BVA is capable of detecting a higher number of faults than static BVA. The dynamic approach results in higher test costs measured in the number of test cases. As a consequence, the decision of applying the dynamic or the static approach is part of the overall test management and risk management. Given enough time and a strong interest in quality, dynamic BVA has to be preferred. There are several points to discuss. Since static boundary value analysis is solely based on model transformations, there is no general restriction to the selected test generator. As we pointed out, however, dynamic boundary value analysis makes high demands on the used test generator. We did not focus on a concrete test generation approach, and the set of applicable test generation approaches and their effects need to be identified. Furthermore, the comparison of both approaches to BVA depends on the structure of the test model. There may be test models (e.g. without loops or complex system attribute assignments) for which the application of the static approach results in the same fault detection capability as the application of the dynamic approach. Further case studies are necessary to investigate the average complexity of industrial test models. For the future, we plan to reduce the test effort of dynamic BVA in ParTeG. We realized that some boundary values do not need to be selected twice if the corresponding transition paths in the state machine are overlapping to a certain degree. We think that this can be solved by determining overlapping def-use-paths. The criteria for identifying these overlapping paths still need to be elaborated. We also plan to investigate the impact of test model transformations as presented in [Wei09b, Wei09a] on the static approach. References [ABL05] 62 James H. Andrews, Lionel C. Briand, and Yvan Labiche. Is Mutation an Appropriate Tool for Testing Experiments? In ICSE’05: Proceedings of the 27th International Conference on Software Engineering, pages 402–411, New York, NY, USA, 2005. ACM. [ABLN06] James H. Andrews, Lionel C. Briand, Yvan Labiche, and Akbar S. Namin. Using Mutation Analysis for Assessing and Comparing Testing Coverage Criteria. IEEE Transactions on Software Engineering, 32:608–624, 2006. [AOH03] Paul Ammann, Jeff Offutt, and Hong Huang. Coverage Criteria for Logical Expressions. In ISSRE’03: Proceedings of the 14th International Symposium on Software Reliability Engineering, page 99, Washington, DC, USA, 2003. IEEE Computer Society. [BEN04] Michel Berkelaar, Kjell Eikland, and Peter Notebaert. http://lpsolve.sourceforge.net/5.5/, 2004. [BJK05] Manfred Broy, Bengt Jonsson, and Joost P. Katoen. Model-Based Testing of Reactive Systems: Advanced Lectures (Lecture Notes in Computer Science). Springer, August 2005. [BOY00] Paul E. Black, Vadim Okun, and Yaacov Yesha. Mutation Operators for Specifications. In ASE’00: Proceedings of the 15th IEEE International Conference on Automated Software Engineering, page 81, Washington, DC, USA, 2000. IEEE Computer Society. [Bur01] Simon Burton. Automated Generation of High Integrity Tests from Graphical Specifications. PhD thesis, University of York, 2001. [BW00] Eckard Lehmann (Bringmann) and Joachim Wegener. Test Case Design by Means of the CTE XL. Copenhagen, 2000. [CHR82] Lori A. Clarke, Johnette Hassell, and Debra J. Richardson. A Close Look at Domain Testing. IEEE Transactions on Software Engineering, 8(4):380–390, 1982. [CM94] John Joseph Chilenski and Steven P. Miller. Applicability of Modified Condition/Decision Coverage to Software Testing. In Software Engineering Journal, Issue, volume 9, pages 193–200, September 1994. [CN00] Ana Cavalcanti and David A. Naumann. A Weakest Precondition Semantics for Refinement of Object-Oriented Programs. IEEE Transactions on Software Engineering, 26(8):713–728, 2000. [Con] Conformiq. Qtronic. http://www.conformiq.com/. lp solve 5.1. + [DDB 05] Zhen Ru Dai, Peter H. Deussen, Maik Busch, Laurette Pianta Lacmene, Titus Ngwangwen, Jens Herrmann, and Michael Schmidt. Automatic Test Data Generation for TTCN3 using CTE. In International Conference Software and Systems Engineering and their Applications (ICSSEA), December 2005. [DF93] Jeremy Dick and Alain Faivre. Automating the Generation and Sequencing of Test Cases from Model-Based Specifications. In FME’93: Proceedings of the First International Symposium of Formal Methods Europe on Industrial-Strength Formal Methods, pages 268–284, London, UK, 1993. Springer-Verlag. [Dij76] Edsger W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976. [DLS78] Richard A. DeMillo, Richard J. Lipton, and Fred G. Sayward. Hints on Test Data Selection: Help for the Practicing Programmer. Computer Journal, 11(4):34–41, 1978. [Ham77] Richard G. Hamlet. Testing Programs with the Aid of a Compiler. IEEE Transactions on Software Engineering, 3(4):279–290, 1977. [HLL94] Joseph R. Horgan, Saul London, and Michael R. Lyu. Achieving Software Quality with Testing Coverage Measures. Computer Journal, 27(9):60–69, 1994. 63 [KLPU04] Nikolai Kosmatov, Bruno Legeard, Fabien Peureux, and Mark Utting. Boundary Coverage Criteria for Test Generation from Formal Models. In ISSRE’04: Proceedings of the 15th International Symposium on Software Reliability Engineering, pages 139–150, Washington, DC, USA, 2004. IEEE Computer Society. [LH01] Ralf Lämmel and Jörg Harm. Test case characterisation by regular path expressions. In Ed Brinksma and Jan Tretmans, editors, Proceedings of Formal Approaches to Testing of Software (FATES’01), Notes Series NS-01-4, pages 109–124. BRICS, 2001. [Mye79] Glenford J. Myers. Art of Software Testing. John Wiley & Sons, Inc., New York, NY, USA, 1979. [Nta01] Simeon C. Ntafos. On Comparisons of Random, Partition, and Proportional Partition Testing. IEEE Transactions on Software Engineering, 27(10):949–960, 2001. [Obj07] Object Management Group. http://www.uml.org, 2007. Unified Modeling Language (UML), version 2.1. [OLR+ 96] A. Jefferson Offutt, Ammei Lee, Gregg Rothermel, Roland H. Untch, and Christian Zapf. An Experimental Determination of Sufficient Mutant Operators. ACM Transactions on Software Engineering and Methodology, 5(2):99–118, 1996. 64 [Sma] Smartesting. Test Designer. http://www.smartesting.com. [SW09] Ben H. Smith and Laurie Williams. Should Software Testers Use Mutation Analysis to Augment a Test Set? Journal of Systems and Software, 82(11):1819–1832, 2009. [UL06] Mark Utting and Bruno Legeard. Practical Model-Based Testing: A Tools Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2006. [UPL06] Mark Utting, Alexander Pretschner, and Bruno Legeard. A Taxonomy of Model-Based Testing. Technical Report 04/2006, Department of Computer Science, The Universiy of Waikato (New Zealand), 2006. [Utt08] Mark Utting. The Role of Model-Based Testing. Verified Software: Theories, Tools, Experiments: First IFIP TC 2/WG 2.3 Conference, VSTTE 2005, Zurich, Switzerland, October 10-13, 2005, Revised Selected Papers and Discussions, pages 510–517, 2008. [WC80] Lee J. White and Edward I. Cohen. A Domain Strategy for Computer Program Testing. IEEE Transactions on Software Engineering, 6(3):247–257, 1980. [Wei] Stephan Weißleder. ParTeG (Partition Test Generator). http://parteg.sourceforge.net. [Wei09a] Stephan Weißleder. Influencing Factors in Model-Based Testing with UML State Machines: Report on an Industrial Cooperation. In Models’09: 12th International Conference on Model Driven Engineering Languages and Systems, October 2009. [Wei09b] Stephan Weißleder. Semantic-Preserving Test Model Transformations for Interchangeable Coverage Criteria. In MBEES’09: Model-Based Development of Embedded Systems, April 2009. [Whi91] Robin W. Whitty. An Exercise in Weakest Preconditions. Software Testing, Verification & Reliability, 1(1):39–43, 1991. [WJ91] Elaine J. Weyuker and Bingchiang Jeng. Analyzing Partition Testing Strategies. IEEE Transactions on Software Engineering, 17(7):703–711, 1991. [WS07] Stephan Weißleder and Holger Schlingloff. Deriving Input Partitions from UML Models for Automatic Test Generation. In Holger Giese, editor, MoDELS Workshops, volume 5002 of Lecture Notes in Computer Science, pages 151–163. Springer, 2007. Test Case Integration: From Components to Systems Bernhard Schätz and Christian Pfaller fortiss GmbH Guerickestr. 25, 80805 München, Germany {schaetz,pfaller}@fortiss.org Abstract: In a component-based development approach system integration generally implies the packaging of software components on hardware units, hiding the interface of a component inside the unit. Thus, integration testing is done on the (logical) component as well as the (technical) unit level, to ensure the correctness of each component in isolation as well as of the complete system combined with the implementation platform. However, analysing the correct functionality of a bundled and deployed component requires direct access to the interface of the component. Here, integrating a component test case into the behavior of the remaining system provides means to verify the functionality of a component from the interface of the unit without additional instrumentation. We show how a to mechanically transform a test case of a component into a black-box test case of the overall system. 1 Introduction In a component-based approach, quality assurance in the constructive phase is usually performed in the form of component tests, and integration or system tests, often using different testing specifications and environments. When integrating components in the overall system, the actual implementation platform may differ from the development platform, leading to a deviation in the component behavior. This raises the issue of testing the functionality of a component integrated in a larger system without the use of an – instrumented – development platform, allowing to perform glass-box-testing. Especially in the construction of customized embedded systems, quality assurance is faced with two problems, when most components of the system are reused and only a few components are changed or replaced: Testing of the final implementation should be restricted as much as possible to the changed/custom-made components to efficiently cope with the large number customized systems; system tests have to be performed on the implementation-level platform, which does not supply glass-box-testing with access to all internal data needed for testing a component without costly or invasive instrumentation of the implementation. Thus an approach is introduced that allows to transform component tests to system tests, supporting the verification of test cases for individual components using only the interface of the overall system. A transformation is not always possible, as for a given component test an equivalent test case on system level may not exist. In software testing test cases are derived for a certain system under test (SUT) with the aim of detecting faults in this SUT. The test cases are defined over the interface of the considered SUT, and the interface of the test execution and observation harness usually reflects this interface of the SUT; thus test cases can by applied directly. This is the standard situation of test case derivation and execution. In some cases the situation is different: Assume that a specific component which is already an integrated part of a larger system 65 (consisting of further components) should be tested. We assume further that there is no direct access to the component’s interface from the system interface. Now the question arises how to test the (sub-)component if we only have the possibility to execute test cases and observe its results at the interface of the complete system. To distinguish between the complete system and the considered specific component we use the term component under test (CUT) for such a component in the further. Hence it is the aim of the presented method to do component testing but execute the test cases at the interface of the integrated system—we do not aim on system or integration tests. In practice there are many situations where such settings occur, for example: There is already a test harness for executing tests at the system level, but no test harness or execution environment for test cases on component level is available; a new third-party component (which may be faulty) was integrated in an otherwise unchanged system and there is no direct access to the component interface available; setting up a specific test execution environment for every single component is to costly and too time consuming, or not possible. Especially, if embedded devices are to be tested on the implementation level control unit, internal data within that unit may not be accessible from the outside. Such an approach may be also useful if we (later) know about a certain defect in an integrated subcomponent and want to see the effect of that defect to the complete system at the interface of the implementation-level platform. Reuse may also be a motivation for executing component tests on system interface level: Often component tests are already available and these should be translated in a way that they can be executed at the implementation-level – it will be very useful to know which of these test cases actually test the CUT independently from the surrounding components. The other way around there might already exist system tests and we want to know which of these system tests shed specific light on the behavior of a single sub-component. To illustrate the approach, the example of an automotive electronic control unit of a power-controlled window is used, as shown in Figure 1: Window Control translates a button signal But indicating the direction of the intended movement of the window (Ind = Up, Hd, Dn) into a motor signal Mot indicating the executed movement of the window (Dir = Lo, Zr, Hi), provided battery signal Bat indicating the current voltage (Vlt = Lo, Hi) states sufficient power; error signal Err indicating the error code (Cod = LV, OK) provides a low voltage error otherwise. Error Store stores an error signal Err indicating the error code; if requested to return or reset the error status by a request signal Req indicating the command (Cmd = Vt, Rs, No), the result of the request Res indicates the corresponding information (Inf = Ft, OK, No). Diagnosis Management translates a diagnostic signal Dia – indicating the diagnostic command – into a corresponding request signal Req – indicating the requested command – and forwards the result signal Res – indicating the returned information – and a status signal Sts – indicating the status information. Since all three components are packaged and deployed onto the control unit, only the external signals received and sent via Bat, But, Dia, Mot, and Sts are available for testing any software component deployed on the unit. Thus, to check the validity of a test case as shown in Figure 4, verifying the reset-set-query functionality of the Error Store component, a corresponding test case is needed that is immediately executable at the interface of the control unit and is indirectly assuring the validity of the test case of the component. 66 But:Ind But:Ind Mot:Dir Mot:Dir Window Control Bat:Vlt Bat:Vlt Res:Inf Err:Cod Dia:Cmd Error Store Req:Cmd Diagnosis Management Dia:Cmd Err:Cod Res:Inf Req:Cmd Sts:Inf Sts:Cod Figure 1: Power-Window Control Unit: System including Error Store Req?Vt,Err?OK :Res!OK Req?Vt:Res!Ft Req?No,Err?LV: Res!No Req?Rs,Err?OK: Res!OK Normal Req?Vt,Err?LV: Res!OK Req?Rs,Err?LV: Req?Rs,Err?OK: Res!OK Res!OK Failure Req?Rs, Err?LV:Res!OK Req?Rs,Err?OK: Res!OK Req?No,Err?OK: Res!No Req?Vt,Err?OK :Res!OK Req?No:Res!No Normal Req?Vt:Res!Ft Req?No,Err?LV: Res!OK Req?Vt,Err?LV: Res!OK Req?Rs,Err?LV: Res!OK Failure Req?Rs, Err?LV:Res!OK Req?Rs,Err?OK: Res!OK Req?No,Err?OK: Res!No Req?No:Res!No Figure 2: Correct and Defect Behavior of the Error Store Component 2 Describing Behavior In this section, components are introduced as building blocks for the construction of reactive systems. To describe their behavior, transition systems are used. Here, the notation and formalism introduced in [Sch07], resp., is used which allows the modular formalization of clocked, hierarchical transition systems. For reasons of brevity, in the following only non-hierarchical state-transition diagrams are considered. 2.1 Transition Systems Figure 2 shows the notation used to describe the transition system of a component for the example of the Error Store component. Here the set Loc of control locations, describes its control state; e.g., the set Loc = {Normal, Failure}; the set V ar of variables, describes its data state; e.g., the set V ar = {Err, Req, Res}; Furthermore, the set Trans describes the transitions of the form (a, pre, post, b), each consisting of a start location a and end location b from the set of locations Loc, as well as a pre-state pre and post-state post expressions assigning values to variables from Var ; e.g., the transition covering the simultaneous occurrence of a voltage error and the empty command is described by the labeled transition from Normal to Failure with a label consisting of Req?No, Err?LV and Res!No Using these elements, the behavior of a transition system in terms of simple single-step executions is defined. Each transition corresponds to a single step of computation/interaction. When entered through its entry location, it reads the values of its variables; it then changes the variable state by writing new values and terminates by exiting via its exit location. To describe a transition, we use the notation described in [Sch07]. Using the above example, the first part of the label states that whenever the no-command signal No is received 67 via variable Req and – at the same time – the voltage-error signal LV is received via variable Err, then the transition is enabled. The second part of the label states that, whenever the transition is triggered, in the next state the no-error signal No is sent via variable Res. These parts use a short-hand notation for reading pre-transtion values and writing posttransition values. They correspond to terms`Err = LV and Res´= No, respectively, using variables`v with v ∈ V ar for values of v prior to execution of the transition, and variables v´with v ∈ V ar for values of v after its execution. The formalization of a transition system is based on the assignment of values to variables −−→ modeling of the data state via Var = Var → Val .1 Abstracting from a concrete syntax, a transition is described as the structure (a, t, b) with entry location a, exit location b, and −−→ −−→ transition label t over Var × Var . t = (before, after ) corresponds a conjunction of the preand the post-part of the label. Its behavior is the set of simple executions containing all elements (a, before ◦after , b), (a, before ◦after ), (a, before),and (a, hi)2 . Thus, the behavior of the above transition is the set of all simple executions (Normal, before ◦ after , Failure), (Normal, before ◦ after ), (Normal, before), and (Normal, hi), such that before(Err) = LV and before(Req) = No, as well as after (Res) = No. Note that transitions need not explicitly assign a value to each of its variables from V ar; non-assigned variables in the pre- as well as post-condition are implicitly treated as getting a value nondeterministically assigned. E.g., The request-transition in the Failure-location of Figure 2 with label Req?Vt : Res!Ft corresponds to a set of executions of the above form with before(Err) ∈ {OK, LV}. 2.2 Component Behavior The description of a component capsules the transition system. Graphically, it consists of the description of the transition system, e.g., provided by Figure 2, and by the description of its interface, e.g., provided by the Error Store element in Figure 1. Therefore, including its transition system, a component is described by declaring a (non-empty) subset Init ⊆ Loc of initial control locations; e.g., the location Normal, marked by a black dot in Figure 2; and furthermore declaring a (non-empty) subset of InOut ⊆ V ar of input and output variables for exchanging signals with the environment; e.g., the input variables Err and Req as well as output variable Res, depicted by empty and filled circles in Figure 1. For the subsequent formalization, for a state s : Var → V al with Var 0 ⊆ Var , the 0 0 0 c Var is used for restrictions (s c Var )(v) = s(v) for all v ∈ Var . It is notation s extended to sequences of states through point-wise application. For sequences r and t we furthermore use the notation r ◦ t to describe the concatenation of r and t. First, the set of executions of a component is introduced. An execution is either a triple −−→∗ (a, t, b) consisting of a finite sequence t ∈ Var of states corresponding to an execution starting at location a and ending at location b, changing variables according to t; or it is a pair (a, t) consisting of a finite sequence t of states, starting at location a. In the context of testable behavior a restriction to finite observations is sufficient. The set of executions is inductively characterized by all (a, t, b) and (a, t) with • (a, t, b) and (a, t) are simple executions of the transition system of the component • t = t1 ◦ s ◦ t2 is the concatenation of t1 , s, and t2 such that (a, t1 ◦ s, c) and (c, s ◦ t2 , b) as well as (c, s ◦ t2 ) are executions of the component for some b ∈ Loc. 1 We 2 hi 68 assume a universal set V al containing all possible values of variables. describes the empty sequence. Res?OK: Req!No,Sts!Ft Dia?Vt,Res?OK: Dia?Vt,Res?Ft: Req!Vt,Sts!OK Req!Vt,Sts!Ft Dia?Vt:Req!Vt,Sts!OK Res?No: Req!No,Sts!No Res?OK:Req!No, Sts!OK Ready Dia?No,Res?No: Req!No,Sts!No Dia?Rs:Req!Rs,Sts!OK Dia?Rs,Res?OK: Dia?Rs,Res?Ft: Req!Rs,Sts!OK Req!Rs,Sts!Ft Res?Ft: Req!No,Sts!Ft Bat?Lo,But?Up: Err!LV,Mot!Zr Bat?Lo,But?Dn: Err!LV,Mot!Zr But?Dn:Mot!Zr,Err!OK Up But?Up:Mot!Zr,Err!OK Stop Bat?Hi,But?Up: Mot!Up,Err!OK But?Hd: Mot!Hi,Err!OK Busy Res?Ft: Req!No,Sts!Ft Down Bat?Hi,But?Dn: Mot!Lo,Err!OK But?Hd:Mot!Zr,Err!OK But?Hd: Mot!Lo,Err!OK Figure 3: Behavior of the Diagnosis Management and Window Control Components Using the example of the Error Store, (Normal, s1 ◦ s2 ◦ s3 , Failure) with s1 (Err) = OK, s1 (Req) = No, s1 (Res) = No, s2 (Err) = OK, s2 (Req) = Rs, s2 (Res) = No, s3 (Err) = LV, s3 (Req) = No, s3 (Res) = OK is a possible execution of the component. In a second step, executions are reduced to observations. Since observations about a component are restricted to its interface, locations and non-input/output-variables are removed from the executions to form observations. Thus, the set of all observations s of a component is defined by the set of all executions (a, t, b) and (a, t) with a is an initial interface location of the component, i.e., a ∈ Init 3 ; s is the restriction of t to the component interc InOut; b is an interface location of the component. Finally, the behavior face, i.e., s = t −−−−→∗ of a component is the set Obs ⊆ InOut of all its observations. Again using the example of the Error Store component, s1 ◦ s2 ◦ s3 as defined above is a possible observation of the component, since here InOut = Var and Normal ∈ Init. 2.3 Component Networks To deal with the issues of system integration described in Section 1, the definition of observations of components must be extended to hierarchical systems, i.e., components which themselves contain subcomponents communicating via common variables. Graphically, networks of components communicating over variables are described by component diagrams as shown in Figure 1. The communication via common variables is indicated by lines, linking output variables to input variables. For each non-hierarchical component its behavior is described by a transition system; e.g., the behaviors of Diagnosis Management and Window Control are shown in Figure 3. As introduced in Subsection 2.2 in the case of the description of components, the interface InOut S of a network S in term of its input and output variables is a subset of the combined interfaces InOut Ci of its components Ci . As in the previous case, non-interface variables 3 As an extension, also initial values of output variables may be defined. 69 ErrorStore Req.No Err.OK Req.Rs Err.OK Res.No Res.No Res.OK Req.No Err.LV Res.No Req.Vt Err.OK Res.Ft Req.No Err.OK Figure 4: Reset-Set-Query-Test Case of the Error Store S from ( i=1,...,n InOut Ci )\InOut S are considered to be hidden variables, used only for internal communication. Like the interface of a network of components, the behavior of a network can be deduced from the behaviors of its components. An observation of the complete system S is obtained from the projection to the behavior of its subcomponents V c InOut S ∈ Obs S ⇔ i=1,...,n t c InOut Ci ∈ Obs Ci C1 , . . . Cn . Formally, t 3 Generating Tests In this section, test cases are introduced as (sets) of observations, defining the validity of a test case of a component as its containment in behavior of the component. Furthermore, the notion of an integrated test case is introduced, demonstrating its ability to test a component behavior of the system level. Finally, its automatic generation using model checking is −−−−−→∗ illustrated. Instead of using the set-based notation Obs C ⊆ InOut C from Section 2 for the observations of a component C with interface InOut C , an equivalent predicate-based −−−−−→∗ notation C : InOut C → B is used via the characteristic predicate C(t) ⇔ t ∈ Obs C 3.1 Test Case Specification Intuitively, a test case describes an observation of a component or system, i.e., a sequence of values sent and received on the interface of a component or systems. Since in Section 2, the behavior of a component or system is described as a set of observations about it, a test case simply is an element of that set. While basically such an element can be described by a simple (linear) transition system, often special diagrams are used. Graphically, a test case can, e.g., be specified using variations of Message Sequence Charts or Sequence Diagrams. Figure 4 shows the representation of such a test case, using a timed varaint of sequence diagrams. The test case description consists of • a labeled life line described by a vertical line for the component participating in the test case, indicating the sequence of observations from top to bottom; e.g., the life line of the Error Store component • a set of interactions depicted as labeled arrows describing the exchange of data between the participating component as well as its environment; e.g., receiving the 70 value Rs via variable Req from the environment (or test bed), or sending the value No via variable Res to the environment (or test bed) • a set of time regions delimited by dashed lines collecting simultaneous interactions within those regions; e.g., the region containing the simultaneous receiving of No and LV via Req and Err, resp., as well as the sending of OK via Res Note that this technique can also be applied to describe the interaction between several components as well as their environment. Figure 5 shows such a description for a sequence of interactions of Error Store, Diagnosis Management and Window Control. Such a diagram can be described as an observation (or set of observations) about the interface of the participating components; the diagram describes a sequence (or set of sequences) of states, with each state assigning a value to an interface variable according to its corresponding time region. Thus, e.g., Figure 4 describes an observation of length 5, with the third state assigning the values OK, No, and LV to the variables Res, Req, and Err, resp. With components with input and output variables as described above, the description of a test case consists of two parts: The specification of the input signals received by the SUT from the environment; the specification of the output signals sent from the SUT to the environment. The SUT the satisfies this test case, when the output actually provided by the system corresponds to the output prescribed by the test case, given the system received the input prescribed by the test case. Similar to the description of the components, a predicate-based notation is also used for test case via def c In C ∈ Obs T c In C ⇒ t c Out C ∈ Obs T c Out C T (t) = t for a set Obs T characterizing the behavior specified by a test case for a component C with input variables In and output variables Out.4 Intuitively, a test case and its graphical representation is interpreted as the set of observations about the component under test that correspond to the prescribed behavior, i.e., with either an input differing from the prescribed input or an output corresponding to the prescribed output. Thus, a test case characterizes all legal behaviors of that component under test; it therefore is a super-set of all the expected observations of the component. Consequently, a test case is valid for a given component if the set of observations corresponding to the test case contains the set of observations corresponding to the behavior of the component under test. If interpreting the description of the test case as well as the behavior of the component as predicates over observations over the alphabet of the component, the following definition of the validity of a test case is obtained. Definition 3.1 (Satisfied Test Case) A system or component C satisfies a test case T if −−−→∗ ∀t ∈ Var C .C(t) ⇒ T (t) ◦ For example, the sequence diagram in Figure 4 shows a possible behavior of the Error Store specified by the transition system of Figure 2. 3.2 Integrated Test Cases In the following, components C and B are subcomponents of system A, with interfaces Var C , Var B , and Var A , resp, where Var A ⊆ Var B ∪ Var C . Furthermore, C is assumed to be completely integrated into A, i.e., having no direct connection to the environment of A; Figure 1 shows an example of such a situation with C corresponding to ErrorStore, 4 The c restriction tVar is extended to restrictions on sets of sequences via element-wise application. 71 Window Control Mot.Zr Bat.Hi But.Up Mot.Hi Bat.Lo But.Up Mot.Zr Bat.Hi But.Up Diagnosis Managment ErrorStore Res.No Sts.OK Err.OK Req.No Dia.Rs Err.OK Res.No Req.Rs Sts.No Dia.No Res.OK Sts.No Err.LV Mot.Hi Bat.Hi But.Up Err.OK Mot.Hi Bat.Hi But.Up Err.OK Mot.Hi Bat.Hi But.Up Err.OK Dia.Vt Req.No Res.No Sts.OK Dia.No Req.Vt Res.Ft Sts.No Dia.No Req.No Res.No Req.No Sts.Ft Dia.No Figure 5: Composed Observation of ErrorStore, DiagnosisManagement, and WindowControl B corresponding to DiagnoseManagement and WindowControl, and A corresponding to their composition. The following definition, theorem, and proof can be easily extended to the more general case with C being only partially integrated. During integration the interface of a component C embedded into the overall system might not be directly observable. To ensure a certain property given in form of a test case T , indirect observation may be needed. Intuitively, we are looking for test case S for the overall system – consisting of C and the rest of the system B – such that if the SUT fulfills that test case S, also C must fulfill test case T . This concept of a test case for a component, integrated into a overall system to deduce a test case for the complete system, is captured below, again interpreting a test case as well as system specification as a predicate over the observations corresponding to the test case and system specification, resp. Definition 3.2 (Integrated Test Case) A test case S is a test case for T integrated into B −−−→∗ def if5 S(s) = ∀t ∈ Var C .(B(s, t) ⇒ T (t)) ◦ For example in the case of the power window implemented by the network of ErrorStore, DiagnoseManagement, and WindowControl as shown in Figure 1, the reset-set-query test case shown in Figure 4 cannot be directly validated since the interface of ErrorStore is completely hidden within the control unit. Any observation on its ports Err, Req, and Res can only be made indirectly over the interface of the control unit. The explicit characterization of an integrated test case S given by 3.2, which is especially suited for the application of text case generation as shown in Subsection 4, can also be equivalently characterized more implicitly: c Var A ) ⇔ (B(t c Var B ) ⇒ C(t c Var C ) S(t −−−→∗ −−−→∗ notation (r, s) for r ∈ Var 1 and s ∈ Var 2 with Var 1 ∩ Var 2 = ∅ is used to denote the sequence c c t of point-wise combined states with tVar 1 = r and tVar 2 = s. 5 The 72 Thus, to verify that Error Store actually satisfies the behavior prescribed by the component test case, a different test case is needed, which is ensuring the validity of the test case for Error Store; relying only on the behavior of Diagnose Management and Window Control, but not on the behavior of Error Store; reading and writing the values of Err, Req, and Res through the interface of the control unit. Figure 5 shows the description of such an integrated test case. The greyed-out parts of the test case description correspond to execution of the reset-set-query test case of Error Store, which is not directly observable from the interface of the control unit; the solid parts correspond to the reading and writing of ports at the interface of the unit, performed, e.g., by the test-bed for the control unit. This is reflected in the life lines of the integrated test case. While the interactions attached to the life line of Error Store correspond to the component test case shown in Figure 4, the interactions attached to the life lines of Diagnose Management and Window Control reflect their corresponding behavior as described by the transition systems in Figure 3. If the values of the input ports Bat, But, and Dia are written as described by the integrated test case, the behaviors of Diagnosis Management and Window Control ensure that the corresponding values of the internal ports Err and Req are assigned to the values prescribed by the component test case. Symmetrically, the behavior of Diagnose Management (and Window Control) ensures that if the values of the output port Sts (and Mot) are read as described by the integrated test case, the values of the internal port Res are assigned to the values prescribed by the component test case. A system test executable in a test-bed for the control unit can be obtained from Figure 5 simply by removing the greyed-out part corresponding to the component test. Note that the validity of the system test ensures the validity of the component test, as stated below: Theorem 3.1 (Satisfied Integrated Test Case) An integrated test case S is a positive system test for a component test, i.e., component C satisfies test case T if the system consisting of B and C satisfies S, provided such a test is possible within the context of B. • The proof for this and the following theorem can be preformed immediately using firstorder logic. Note that an integrated test case may not exist. In such a case, only the trivial solution S(t) = F exists. Furthermore, the invalidity of the system test ensures the invalidity of the component test, as stated in the following theorem. Theorem 3.2 (Unsatisfied Integrated Test Case) An integrated test case S actually is a negative system test for the component test, i.e., component C does not satisfy test case T if the system consisting of B and C does not satisfy S. • 4 Implementation To provide tool-support for the generation of integrated test cases, the model of component test cases must be implemented in a way that enables the mechanization of their integration using a suitable framework. In the following, the use of a symbolic model checker for the implementation and mechanization is demonstrated. 4.1 WS1S Formalization To effectively use the definition of integrated test cases, support for the generation of test cases is needed. As behavior is defined by (possibly infinite) sets of finite traces, test cases are defined as elements of such sets, and integrated test cases are defined via first-order 73 expressions over those sets, a trace-based formalism is best-suited. Here WS1S (weak second order monadic structure with one successor function) is used for automatic test case generation. This formalism is supported by the model checker Mona [KM01]. Using WS1S, behavior is specified by predicates over observation traces, which are – as defined above – sequences of states, i.e. sequences of assignment of values to variables. Intuitively, these predicates are built up from the most elementary propositions about observations, declaring that a variable has a certain value at a specific point in time in a observation. E.g., looking at the observation corresponding to the reset-set-query-test case in Figure 4, a suitable proposition is “variable Req has value Vt in the fourth state”. Using this approach, a trace can be precisely described by characterizing the states, for which a certain variable has a specific value. E.g., in the above example, a part of the description is characterized by “variable Req has value No in states 0,2,4, value Rs in state 1, and value Vt in state 3” (numbering states beginning with 0). Using this approach, predicates are defined by characterizing a trace via the sets of state indices, for which these basic propositions – linking variables and values – hold. WS1S provides variables (and quantors) over sets of indices, called second-order variables (or quantors) in contrast to zero-order and first-order variables (quantors) for Booleans or indices. Using these second-order variables for sets corresponding to all combinations of variables and values, the above test case can be formalized as pred ErrorStoreTest( var2 ErrOK, ErrLV, ReqNo, ReqVt, ReqRs, ResNo, ResOK, ResFt) = (0 in ErrOK & 0 in ReqNo & 0 in ResNo) & (1 in ErrOK & 1 in ReqRs & 1 in ResNo) & (2 in ErrLV & 2 in ReqNo & 2 in ResOK) & (3 in ErrOK & 3 in ReqVt & 3 in ResNo) & (4 in ErrOK & 4 in ReqNo & 4 in ResFt); with var2 declaring second-order parameters, and e.g., ReqNo corresponding to the set of indices characterizing states with Req = No.6 Using the same principle, also the observations of transition-systems can be formalized in a similar fashion, leading to corresponding predicates for WinCtrl and DiagMgt for the WindowControl and DiagnoseManagement components. The definition 3.2 of an integrated test case in Section 3 can be directly implemented in WS1S, allowing an automatic construction of the corresponding trace using the witness functionality provided by Mona: pred SystemTest( var2 BatLo, BatHi, ButDn, ButHd, ButUp, DiaVt, DiaRs, DiaNo, MotLo, MotZr, MotHi, StsNo, StsOK, StsFt) = all2 ErrOK, ErrLV ReqNo, ReqVt, ReqRs, ResNo, ResOK, ResFt: (( WinCtrl(BatLo, BatHi, ButDn, ButHd, ButUp, MotLo, MotZr, MotHi, ErrOK, ErrLV) & DiagMgt(RqSRd, RqSBs, DiaNo, DiaVt, DiaRs, ResNo, ResOK, ResFt, ReqNo, ReqVt, ReqRs, StsNo, StsOK, StsFt)) => ErrorStoreTest(ErrOK, ErrLV, ReqNo, ReqVt, ReqRs, ResNo, ResOK, ResFt)); 4.2 Observation Synthesis To effectively generate an observation, the witness functionality of model checkers can be exploited. By use of this functionality, the model checker selects an element from a satisfiable, i.e., non-empty model. In case of WS1S, Mona selects a shortest observation, 6 For reasons of readability disjointness assertions like ReqNo inter ReqRs ensuring unique signal values are skipped here. 74 satisfying the predicate characterizing the integrated test case. For example, using the witness functionality of Mona and applying it to the example of the Error Store component, the sequence diagram in Figure 4 can be synthesized. Using the above predicate SystemTest, Mona can check for its satisfiability, returning the following witness: BatLo ButDn DiaVt MotLo StsNo = = = = = {1}, BatHi = {0,2,3,4,5} {}, ButHd = {}, ButUp = {0,1,2,3,4,5} {2}, DiaRs = {0}, DiaNo = {1,3,4,5} {}, MotZr = {0,2}, MotHi = {1,3,4,5} {1,2,4}, StsOK = {0,3} StsFt = {5} This corresponds to the observation in Figure 5, using the notion for sequence diagrams. 4.3 Integration Automation Test case integration consists of two steps: First, the specification of a test case for the CUT – e.g., given by a sequence diagram – is integrated into the specification of the rest of the system - e.g., given by an architectural description as well as the behavior of the remaining components – using the approach described in the previous subsection. Then, the instantiation of the obtained integrated test case is verified w.r.t. to the actual implementation. To illustrate the application, the integration of a changed Error Store component in an otherwise unchanged Power-Window Control Unit system is used. From these specifications, the corresponding WS1S formalizations can be automatically generated as presented above. Combined with the integrated test case, the complete specification is handed over to the Mona model checker for processing. If a non-trivial solution exists, a suitable shortest test case is generated; otherwise, the user is informed that no suitable test case can be generated since the specification of the integrated test case is unsatisfiable. Once the integrated test case has been generated, the behavior of the overall system – containing the component under test – has to be verified with respect to the test case, to show whether the overall system – and therefore also the component under test – respects the prescribed behavior. Figure 2 shows the actually implemented behavior of the Error Store component. It deviates from the intended behavior in the output generated during the registration of a low voltage error Err?LV and an empty request Req?No when changing from state Normal to state Failure: while the intended behavior is the provision of an empty result Res!No, the actual behavior is the provision of the OK result Res!OK. To check whether the implemented system actually satisfies the integrated test case, the implementation – e.g., in form of an electronic control unit – is embedded into test environment allowing to write the inputs and read the outputs at the system interface and thus to execute the – instantiated – test case. To instantiate the test case, its abstract input signals – e.g., the diagnostic command signals Vt, Rs, No – are translated in corresponding concrete binary signals – e.g., 0x00, 0x01, 0x02 – and each round sent to the implementation via the test bed. Similarly, the concrete binary signal received each round are translated back to abstract signals. Comparing the abstract output values obtained through the test environment with the outputs prescribed by the integrated test case shows whether the system under test satisfies the test case. In case of the defect Error Store component, the observation shown in Figure 6 is obtained, demonstrating that the SUT does not satisfy the integrated test case. 5 Conclusion The introduced approach enables the automatic generation of test cases for integrating a component into a larger overall system. This combination delivers a test case executable 75 Window Control Mot.Zr Bat.Hi But.Up Mot.Hi Bat.Lo But.Up Mot.Zr Bat.Hi But.Up Res.No Sts.OK Err.OK Req.No Dia.Rs Err.OK Res.No Req.Rs Sts.No Dia.No Res.OK Sts.No Err.LV Mot.Hi Bat.Hi But.Up Err.OK Mot.Hi Bat.Hi But.Up Err.OK Mot.Hi Bat.Hi But.Up Diagnose Managment ErrorStore Res.OK Sts.OK Dia.No Req.Vt Res.Ft Sts.OK Dia.No Req.No Res.No Err.OK Dia.Vt Req.No Req.No Sts.Ft Dia.No Figure 6: Deviation from Integrated Testcase caused by defect Error Store Component at the interface of the overall system, which verifies that the component satisfies the given component test case if the overall system satisfies the resulting system test case. A typical area for the application of such an approach is, e.g., the construction of embedded software; here, on the implementation level often no means are provided of directly observing the interface of a component integrated in a larger system. This approach is especially useful in the context of system evolution, when only the component under test has been altered, leaving the rest of the system unchanged. Note that instead of deducing an observation about the overall system from a given observation of a component plus the remainder of the system, also the opposite approach – deducing the required component behavior from the observed system behavior – has its merits, e.g., in the context of fault localisation when trying to identify possible faulty behavior of a changed component that can result in a faulty behavior at system level, identified during the testing of the otherwise unchanged system. To solve that problem, the same formalizations and techniques can be applied. While the infra structure of symbolic model checkers often does not scale for the analysis of systems composed from several components, the approach proves to be feasible in the domain of reactive body control using enumeration data types for signal and state variables. Since the tool-supported method allows a stepwise construction of the integrated test case, avoiding an explicit construction of the complete behavior of the remaining system, only the relevant ‘cone of behavior’ is built from the integrated test case. References [KM01] Nils Klarlund and Anders Møller. MONA Version 1.4 User Manual. BRICS, Department of Computer Science, University of Aarhus, 2001. [Sch07] Bernhard Schätz. Modular Functional Descriptions. In Proceedings 4th International Workshop on Formal Aspects fo Component Software (FACS’07), Nice, 2007. To appear in ENTCS. 76 Reverse Engineering vernetzter automotiver Softwaresysteme∗ Stefan Henkler, Jan Meyer1 , Wilhelm Schäfer Fachgebiet Softwaretechnik, 1 s-lab (Software Quality Lab), Heinz Nixdorf Institut Universität Paderborn, Warburger Str. 100, 33098 Paderborn shenkler,janny,[email protected] Ulrich Nickel Hella KGaA Hueck & Co. Rixbecker Str. 75, D-59552 Lippstadt [email protected] 1 Zusammenfassung Funktionalitäten in Fahrzeugen werden zunehmend über (verteilte) Funktionsnetze bzw. der Vernetzung mechatronischer Komponenten realisiert. Damit kommt der Koordination der Funktionen und mechantronischen Komponenten eine wesentliche Rolle zu, da diese das Regelungs- und Steuerungsverhalten maßgeblich beeinflusst. Der wesentliche Ansatz, eine korrekte Gesamtfunktion sicher zu stellen ist, das System und die Software durchgängig modellbasiert zu entwickeln. Dies wird durch den Einsatz bereits vorhandener (zugelieferter) Komponenten aber erschwert. Die Integration solcher (Black-Box-) Komponenten wird in diesem Beitrag betrachtet. Dieser Beitrag ist eine Zusammenfassung des Beitrags [HMSN10]. 2 Einleitung Komplexe mechatronische Systeme, wie sie beispielsweise in Transportsystemen (Automobil oder Luftfahrt) vorkommen, sind typischerweise durch eine Vernetzung von (mechatronischen) Komponenten realisiert. Software wird dabei unter anderem eingesetzt, um durch Kommunikation das Wissen von anderen Komponenten zu nutzen. Es entstehen komplexe Funktionsnetze aus (Software-)Komponenten, welche sowohl steuerungsals auch regelungstechnische Aufgaben realisieren. Die Entwicklung von mechatronischen Systemen muss, um den Marktanforderungen gerecht zu werden, immer schneller und kostengünstiger erfolgen. Die Systeme werden ∗ Diese Arbeit ist im Sonderforschungsbereich 614 - Selbstoptimierende Systeme des Maschinenbaus“, Uni” versität Paderborn, entstanden und wurde auf seine Veranlssung unter Verwendung der ihm von der Deutschen Forschungsgemeinschaft zur Verfügung gestellten Mittel veröffentlicht. 77 zudem oft in sicherheitskritischen Bereichen eingesetzt. Somit ergeben sich hohe Qualitätsanforderungen an die Software und damit auch an den zugrundeliegenden Entwicklungsprozess. Diesen Herausforderungen wird heutzutage mit modellbasierten Entwicklungsverfahren begegnet, die Sicherheitsanalysen auf der Modellebene durch Simulation sowie formale mathematisch fundierte Verfahren erlauben. Gleichzeitig unterstützen modellbasierte Entwicklungsverfahren die effiziente Umsetzung der erhöhten Anforderungen an den Entwicklungsprozess, welche insbesondere mit der Entwicklung sicherheitsrelevanter Funktionen einhergehen. Mit der Einführung modellbasierter Entwicklungsverfahren ergeben sich allerdings neue Probleme: 1. Um das volle Potential modellbasierter Entwicklungsverfahren ausschöpfen zu können, müssen diese durchgängig eingeführt werden. Dies bedeutet aber auch, dass bestehende (traditionell entwickelte) Altkomponenten integriert werden müssen. Eine Neuentwicklung wird nicht angestrebt, da die Wiederverwendung von (Software) Altsystemen (Altkomponenten) zum einen die Möglichkeit bietet die Entwicklung der Systeme zu beschleunigen. Zum anderen wird durch die Verwendung von Altkomponenten auf bewährte Qualität zurückgegriffen. Es muss also die Frage nach der geeigneten Migrationsstrategie für Altkomponenten beantwortet werden. 2. Mit der Entwicklung neuer Standards, wie z.B. AUTOSAR1 wird das Thema Software als Produkt explizit vorangetrieben. Das bedeutet, dass sich ein Funktionsnetzwerk aus den Komponenten unterschiedlicher Hersteller zusammensetzt. Diese zugelieferten oder zugekauften Komponenten müssen von den Automobilherstellern (OEM) oder deren Zulieferern auf den einzelnen Steuergeräten integriert werden. Da eine Integration auch dieser Komponenten (von Drittanbietern) in einen modellbasierten Entwicklungsansatz naheliegend ist [Bal00], setzt dies voraus, dass auch ein geeignetes Modell dieser Komponenten vorhanden ist. Dies ist gerade in industriellen Projekten oft nicht gegeben. Zur Behebung dieser Probleme wird die automatische Rückgewinnung des Modells einer Altkomponente (allein) aus dem vorhandenen ausführbaren (kompilierten) Quellcode und den definierten Schnittstellen das Thema dieses Papiers. In [GHH08a] haben wir bereits einen Ansatz vorgestellt, der im Vergleich zu bisherigen Ansätzen (z. B. [HNS03]) eine Integration unter Berücksichtigung von Sicherheitseigenschaften unterstützt. Voraussetzung für diesen Ansatz ist, dass die Altkomponenten an ihrer Schnittstelle eine Beobachtung des aktuellen Zustands des Kommunikationsverhaltens ermöglicht. Wie wir in [GHH08a] gezeigt haben, erfüllt dieser Ansatz die Anforderungen, um Anwendungen des RailCab Projektes2 und Anwendungen, die den AUTOSARStandard erfüllen, zu analysieren. Unsere Erfahrungen im industriellen Kontext haben allerdings gezeigt, dass darüber hinaus häufig Anwendungen existieren, die nur Informationen über die ein- und ausgehenden Nachrichten beschreiben oder zusätzlich den Quellcode zur Verfügung stellen. Wir stellen daher einen Ansatz vor, der für Black-Box-Komponenten (nur Schnittstelleninformation der Altkomponente bekannt) eine korrekte Integration zeigen kann. Um 1 http://www.autosar.org/ 2 http://www-nbp.uni-paderborn.de/ 78 dies zu ermöglichen wird (iterativ) das Modell des Verhaltens für die Integration gelernt und überprüft, ob es den Sicherheitsanforderungen standhält. Der Kontext, das Protokollverhalten der Komponente, mit dem die Altkomponente interagieren soll, wird in der Analyse berücksichtigt, um nur die relevanten Interaktionen zu betrachten. Für WhiteBox-Komponenten (Source Code der Altkomponente bekannt) haben wir einen Ansatz in [HBB+ 09] vorgestellt3 . 3 Stand der Technik Es existieren bereits einige Arbeiten, die sich mit dem Erlernen von Verhalten beschäftigen. Im Folgenden werden die entsprechenden Ansätze vorgestellt und gegenüber dem hier vorgestellten Ansatz abgegrenzt. Am bekanntesten ist die Technik der regulären Inferenz, die als nächstes vorgestellt wird. Reguläre Inferenz - Black-box Integration Reguläre Inferenz betrachtet das System als Black-Box. Es wird angenommen, dass das betrachtete Black-Box-System durch einen endlichen deterministischen Automaten (Deterministic Finite Automaton, DFA) modelliert werden kann. Das sich daraus ergebende Problem ist die Identifizierung der regulären Sprache L(M ) des Systems M. Hierzu werden spezielle Lernalgorithmen verwendet. Ein Lerner, der zu Beginn nur das Alphabet P ∗ von M kennt, versucht die Sprache L(M ) dadurch zu erlernen, dass er Anfragen an einen Lehrer (Teacher) und an ein Orakel stellt. L(M ) wird durch Zugehörigkeitsanfragen (membership queries) an den Lehrer erlernt. Es wird überprüft, ob eine Zeichenkette w ∈ Σ∗ in L(M ) enthalten ist. Weiterhin ist zum Erlernen der Sprache noch eine Äquivalenzanfrage (equvalence query) notwendig. Diese fragt das Orakel, ob der erlernte DFA A korrekt ist. Dies ist der Fall, wenn L(A) = L(M ). Ansonsten wird ein Gegenbeispiel gegeben. Typischerweise fragt der Lerner eine Sequenz von Zugehörigkeitsanfragen und nutzt die Antworten, um einen vermuteten Automaten (Kandidat) zu erstellen. Ist der Kandidat stabil (verändert sich nicht gegenüber vorherigen Iterationen), wird eine Äquivalenzanfrage an das Orakel gestellt, um herauszufinden, ob das Verhalten dem der Black-Box entspricht. Ist dies der Fall, terminiert der Algorithmus. Andernfalls wird ein Gegenbeispiel zurückgegeben, um A zurückzuweisen. In diesem Fall werden weitere Zugehörigkeitsanfragen gestellt, bis der nächste mögliche Automat erstellt ist und so weiter. Algorithmus von Angluin Der bekannteste reguläre Inferenzalgorithmus ist L∗ , entwickelt von Angluin [Ang87]. Der Algorithmus organisiert die Informationen, die durch Anfragen und Antworten erlangt werden, in einer so genannten Beobachtertabelle. Die in dieser Tabelle gespeicherten Zeichenketten bestehen dabei aus einem Prefix und einem Suffix. Die Prefixe sind Indizes für die Reihen, während die Suffixe die Spalten der Tabelle indizieren. Ein Prefix ist eine Zeichenkette, der zu einem Zustand des Systems führt. Eine Suffix wird genutzt, um die Prefixe auseinanderzuhalten, die zu verschiedenen Zuständen führen. Die Komplexität des L∗ Algorithmus ist wie folgt. Die obere Grenze für die An3 Darüber hinaus ist es möglich die relevanten Information für unser iteratives Lern/-Beweisverfahren [GHH08a] aus dem Source Code zu extrahieren. 79 zahl der Äquivalenzanfragen beträgt n (n ist die Anzahl der Zustände von M). Die obere Grenze für die Anzahl der Zugehörigkeitsanfragen beträgt O(|Σ|n2 m). Domänenspezifische Ansätze Es existieren verschiedene Ansätze, die auf dem Lernalgorithmus von Angluin basieren. Einige Ansätze, wie in [HNS03, Ber06] beschrieben, erweitern Angluins Algorithmus, zur Verbesserung der Laufzeit für bestimmte Applikationen oder Domänen. Diese Ansätze nutzen Angluin’s Algorithmus und fügen z.B. zusätzliche Technologien, wie Testen und Verifikation hinzu. Hierdurch werden primär die Zugehörigkeitsanfragen reduziert. Eine Technik, um eine Black-Box mittels Model Checking zu überprüfen, wird von Peled und anderen in [PVY99] vorgestellt. Äquivalenzüberprüfungen Die beschriebenen Lernverfahren benötigen ein Orakel, welches überprüft, ob der erlernte Kandidat äquivalent zu der Black-Box ist. Ist dies nicht der Fall, wird ein Gegenbeispiel angegeben. Konformitätstest ist ein weitverbreiteter Ansatz, um die Äquivalenz zu überprüfen. Konformitätstests bieten ein systematisches Verfahren an, um Antworten für Äquivalenzanfragen zu ermitteln. [PVY99] oder [Ber06] sind z.B. Lernansätze die hierauf basieren. Wie auch diese Ansätze, basieren die meisten Konformitätstest-Ansätze auf dem Verfahren von Vasilevskii und Chow [Vas73, Cho78]. Entsprechend Vasilevskii existiert eine obere Grenze für die Gesamtlänge einer Testsequenz. Diese ist O(k 2 l|Σ|l−k+1 ). Daher besteht eine exponentielle Differenz zwischen der Anzahl der Zustände k des Systems und der Hypothese l. Eine allgemeine Annahme für den Konformitätstest ist, dass A mindestens so viele Zustände wie M hat [BGJ+ 05]. Fazit Im Prinzip basieren die hier betrachteten Lernalgorithmen alle auf dem von Angluin. Bis auf [PVY99], versuchen alle Ansätze das ganze Verhalten zu synthetisieren. Erst anschließend werden Konfliktsituationen gefunden. Unser Ansatz betrachtet im Vergleich dazu besonders das enge Zusammenspiel zwischen dem Kontext und der Altkomponente. Somit ist es nicht erforderlich das gesamte Verhalten der Altkomponente zu erlernen. Nur der relevante Teil der Integration ist erforderlich. Ähnlich zu [PVY99] ist unser Black-Box-Ansatz in der Lage reale Fehler nach jedem Lernschritt zu finden. Darüber hinaus ermöglichen wir ein reaktives Verhalten in Form von ein- und ausgehenden Nachrichten sowie Zeit(-anforderungen) zu berücksichtigen. Voraussetzungen Folgende Voraussetzungen müssen erfüllt sein, um den Algorithmus von Angluin anzuwenden: 1) Das Systemverhalten muss als deterministischer endlicher Automat (DFA) repräsentierbar sein. 2) Um Testeingaben auszuführen, muss es über ein entsprechendes (Test-) Laufzeitframework möglich sein, die Altkomponente zu stimulieren. 3) Die Eingaben müssen dementsprechend auch bekannt sein. 4) Die Altkomponente muss einen eindeutigen Startzustand besitzen, in dem diese extern versetzt werden kann. 5) Die reguläre Sprache des Systems muss Prefix geschlossen sein. D.h. wenn ein Wort akzeptiert wird, muss auch jeder Prefix des Wortes akzeptiert werden. 6) Weiterhin muss eine obere Grenze für die Zustände der Altkomponente bekannt sein, da sonst nicht das gesamte Verhalten erlernt werden kann. Voraussetzung 1) ist immer auf der Implementierungsebene gegeben. Selbst ein Zufallszahlengenerator ist deterministisch implementiert. 2) und 3) sind Voraussetzungen dafür, 80 die Altkomponente überhaupt ausführen zu können bzw. anzusteuern. Ohne diese Informationen ist eine Integration der Altkomponente in ein reales System nicht möglich. 4) ergibt sich zum Teil aus 1) (der eindeutige Startzustand). Wenn eine Altkomponente nicht wiederholt initialisierbar wäre, könnte sie nur einmal gestartet werden. Eine Integration wäre damit höchst fraglich, da keinerlei Tests mit der Umgebung durchgeführt werden könnten. 5) ist für die von uns betrachteten reaktiven Systeme keine Einschränkung. Voraussetzung 6) ist die größte Einschränkung, da diese Information eigentlich nicht bekannt ist. Daher muss dieser Wert geschätzt werden. Grundsätzlich scheint es möglich, dass der Kontextautomat eine gute Orientierung ist. Eine hohe Abschätzung nach oben und die Erkenntnis, dass der erlernte Automat weniger Zustände als die obere Abschätzung der Anzahl der Zustände hat, führen dazu, dass auch diese Annahme akzeptabel ist. Ein wiederholtes Ausführen des Lernverfahrens mit unterschiedlichen Zustandsgrenzen geben zudem die Gewissheit, dass der Automat korrekt ist. 4 Modellierung und Analyse Um die modellbasierte Entwicklung von mechatronischen Systemen zu ermöglichen, haben wir die M ECHATRONIC UML entwickelt (z. B. [GHH+ 08b]). Der relevante Ausschnitt für den in diesem Papier vorgestellten Reverse Engineering Ansatz ist die Modellierung der Architektur, das Verhalten mittels Koordinationsmustern und die Einbettung von Regelerverhalten. Die Architektur eines mechatronischen Systems ist maßgeblich durch die Vernetzung der einzelnen Komponenten gegeben. Daher berücksichtigen wir zur Spezifikation der Architektur, neben Komponenten (Wipercoordination und Wiper), sogenannte (Echtzeit-) Koordinationsmuster (WiperCoordination), die die Struktur der Vernetzung sowie das Verhalten beschreiben. Abbildung 1 zeigt die Kommunikationsstruktur der Scheibenwischerautomatisierung. Die Kommunikationsstruktur besteht aus den beiden Rollen wiper für den Scheibenwischer und aus der (Gegen-) Rolle coordination für die Automatisierung und Koordination des Scheibenwischers. Zusätzlich werden für jedes Kommunikationsmuster Sicherheitseigenschaften spezifiziert, die formal mittels Model Checking überprüft werden4 . Eine Standardbedingung für sicherheitskritische Systeme ist, dass keine Verklemmung auftreten darf (engl. Deadlock). Eine weitere mögliche Bedingung ist, dass der Scheibenwischer nicht noch aktiv sein darf, wenn die Koordination der Steuerung aus ist. Das Verhalten wird mit Real-Time Statecharts, eine Erweiterung von Statecharts um Zeit, spezifiziert. Semantisch basieren Real-Time Statecharts auf Timed Automata [AD94], so dass ein Model Checking durch eine Abbildung auf das UPPAAL5 Eingabemodell ermöglicht wird. Einen Ausschnitt des Verhaltens der coordination Rolle des WiperCoordination Musters ist in Abbildung 2 gezeigt. Die wiper Rolle wird in unserer Anwendung durch eine vorhandene Altkomponente umgesetzt, die bereits ihre Qualität in realen Anwendungen gezeigt hat. Da allerdings kein Modell dieser Komponente vorliegt, kann auch nicht die Sicherheit durch modellbasierte Analyseverfahren, wie gefordert, umgesetzt werden. Wir betrachten daher die coordination 4 Als Spezifikationssprache verwenden wir TCTL (Timed Computation Tree Logic) 5 www.uppaal.com 81 Rolle als unsicher. Im folgenden Abschnitt zeigen wir ein Lernverfahren, auf Basis dessen die geforderten Eigenschaften trotzdem formal analysiert werden können. Abbildung 1: Komponentenarchitektur automatic / wait Rain.mid / step2 init . . . off / wiper.off / Wiper.mid wait_wiper2 wiper2 {t_wiper} . 0 <= t_wiper <= 100 . . Abbildung 2: Ausschnitt Kontextverhalten 5 Kompositionales Black-Box Checking Im vorherigen Abschnitt haben wir gezeigt, wie eine Altkomponente in eine mit M ECHA TRONIC UML modellierte Komponentenarchitektur eingebettet wird (siehe Abbildung 1). In diesem Abschnitt stellen wir ein Verfahren vor, mit dem es ermöglicht wird das Modell des Verhaltens einer Altkomponente iterativ zu erlernen und iterativ Sicherheitseigenschaften zu überprüfen. Die Korrektheit der Integration kann entweder gezeigt werden durch eine 1) (kompositionale) formale Verifikation der Altkomponente mit dem Kontext (coordination Rolle) oder durch eine 2) Verifikation der Verfeinerung der abstrakt spezifizierten Rolle (wiper) und der Altkomponente (Wiper). Es muss für die Beispielanwendung gezeigt werden, dass coordination||learned.wiper |= coordination.of f implies learned.wiper.of f ∧ ¬δ(keinDeadlock) für 1) und learned.wiper ≤ wiper für 2) gilt. Eine Verfeinerung lässt sich ebenfalls über eine parallele Komposition zeigen, indem aus dem abstrakten Modell ein Testautomat abgeleitet wird [JLS00]. Ein Testautomat wird durch Komplementbildung des abstrakten Automaten (wiper) erstellt. Zudem wird das Verhalten, welches nicht durch den Automaten erfüllt wird, in den komplementären Automaten durch einen Fehlerzustand berücksichtigt. In der Analyse wird dann gezeigt, dass dieser Fehlerzustand nicht erreichbar ist. Wir werden im Folgenden zeigen wie wir eine kompositionale Analyse für die Betrachtung von Black-Box Komponenten durchführen können, womit wir entsprechend auch eine Verfeinerung zeigen können. Generelle Idee ist dabei das Verfahren von [Ang87] für 82 die Domäne mechatronischer Systeme anzupassen. Das heißt insbesondere, dass wir einund ausgehende Nachrichten, Kontextverhalten und Zeit berücksichtigen. Der Ansatz besteht aus den folgenden Schritten: 1. lernen eines Kandidaten des Protokollverhaltens der Altkomponente (mit erweiterten Angluin Ansatz), 2. kompositionale Überprüfung des Kandidaten aus 1. unter Berücksichtigung des Kontextverhaltens und Sicherheitseigenschaften an die Integration. (a) Wenn aus 2. ein Gegenbeispiel erfolgt, dann wird überprüft, ob dieses Gegenbeispiel durch die Altkomponente bestätigt wird. Ist dies der Fall, ist die Integration fehlerhaft. (Das Verhalten kann und sollte trotzdem vollständig erlernt werden, um eine Anpassung des Kontextes zu ermöglichen.). Ist dies nicht der Fall, wird mit 1. fortgefahren unter Berücksichtigung des Gegenbeispiels. (b) Folgt aus 2. kein Gegenbeispiel, dann wird überprüft, ob das erlernte Verhalten äquivalent zur Altkomponente ist (Conformance Test mit Vasilevskii und Chow [Vas73, Cho78]). 3. Folgt aus der Äquivalenzprüfung (2.(b)), dass der Automat äquivalent ist, ist die Lernphase abgeschlossen und die Integration korrekt. Ist dies nicht der Fall, wird auf Basis der Ergebnisse der Äquivalenzprüfung mit 1. fortgefahren. Erweiterter Lernalgorithmus Wie in Abschnitt 3 dargestellt, beantwortet der Lehrer Zugehörigkeitsanfragen (-tests) an die Altkomponente und stellt Gegenbeispiele zur Verfügung, wenn die Äquivalenz nicht gegeben ist. Wir erweitern Angluin’s Algorithmus um Gegenbeispiele des Model Checking, des schrittweise erlernten Verhaltens der Altkomponente mit dem Kontext. Wenn ein Gegenbeispiel durch die Altkomponente bestätigt wird, ist die Integration fehlerhaft. Andernfalls nutzen wir dieses Gegenbeispiel um den folgenden Kandidaten zu erlernen. Die Berücksichtigung des Kontextes ermöglicht uns gezielter das relevante zu erlernende Verhalten zu ermitteln und frühzeitig Fehler in der Integration zu ermitteln. Falls das Model Checking kein Gegenbeispiel liefert, wird eine Äquivalenzanfrage mittels des Verfahrens von Vasilevskii und Chow durchgeführt (siehe Abschnitt 3). Dieses Verfahren ist aufgrund seiner guten Laufzeiteigenschaften für Konformitätstests weit verbreitet. Eingabe in das Verfahren ist der Kandidat der Altkomponente sowie die obere Anzahl an erwarteten Zuständen der Altkomponente. Der Algorithmus bestätigt entweder die Äquivalenz oder gibt ein Gegenbeispiel zurück, welches wiederum als Eingabe für den Angluin Algorithmus verwendet werden kann. Unter der Annahme, dass eine obere Schranke für die Zustände bekannt ist, kann durch das vorgestellte Verfahren tatsächlich sichergestellt werden, dass entweder ein Fehler in der Integration festgestellt wird oder die Integration unter Berücksichtigung der Sicherheitseigenschaften korrekt ist. Den zugrunde liegenden Automaten des Angluin Ansatzes haben wir um Mealy Automaten erweitert (siehe auch [HNS03]). Dies ermöglicht zusätzlich die Betrachtung von Ein/Ausgabeverhalten. Der grundsätzliche Unterschied entsteht dadurch, dass der Angluin Ansatz auf Basis eines DFA als Antwort auf eine Anfrage ein akzeptierendes Wort erwartet. 83 Zeit Grundsätzlich muss sich eine Altkomponente in der betrachteten sicherheitskritischen Umwelt deterministisch verhalten. Die rechtzeitige vorhersagbare Reaktion auf Ereignisse ist von hoher Bedeutung. Diese Systeme werden daher typischerweise periodisch umgesetzt. Eine zeitgerechte periodische Ausführung einer Altkomponente ist daher Voraussetzung für die korrekte Funktionsweise. Somit ist die Angabe der Periode der Altkomponente notwendig für eine Integration. Das implementierte System garantiert eine korrekte Funktionsweise unter Verwendung dieser Periode (siehe auch Abschnitt 3). Ist dies der Fall, können die zeitlichen Bedingungen durch die Periode des Systems diskretisiert werden (können nur ein Vielfaches der Periode sein). Wenn dieses Vielfache nicht bekannt ist, kann diese Komponente auch nicht sicher eingesetzt werden. Diese Vorgabe wird von unserem Lernverfahren ausgenutzt, um in Abhängigkeit von der Periode Zeiteigenschaften zu überprüfen, bzw. zu identifizieren. Dies wird ermöglicht durch eine Anfrage in Form eines leeren Wortes für jede mögliche vielfache Zeitbedingung der Periode. Für jeden Zustand wird damit zusätzlich überprüft, ob er in Abhängigkeit von unterschiedlich langen Zeitintervallen, die ein vielfaches der Periode sind und durch ein leeres Wort repräsentiert werden, unterschiedlich reagiert. Durch diese Form der Diskretisierung der Zeit, muss der Lernansatz im Wesentlichen nur um zusätzliche Eingabewörter erweitert werden. Anwendungsbeispiel Wir haben den beschriebenen Ansatz unter anderem an dem in Abschnitt 4 eingeführten Scheibenwischerbeispiel evaluiert. Wir haben dabei eine Scheibenwischerumsetzung basierend auf dem Patent [Reg96] testweise umgesetzt. Die dort beschriebene Spezifikation betrachten wir ähnlich zu einer Beschreibung einer Altkomponente. Interessanterweise haben wir nach nur wenigen Schritten einen Konflikt identifiziert. Es ist nicht möglich aus Zustand wiper 2 direkt wieder den Scheibenwischer auszuschalten. Grund hierfür ist, dass die Altkomponente nur ein Ausschalten des Scheibenwischers aus der kleinsten Stufe ermöglicht. Abbildung 3 zeigt einen Ausschnitt des erlernten Verhaltens, welches diesen Fakt verdeutlicht. Laut der vorgegebenen Spezifikation aus Patent [Reg96] ist dies erlaubt. Die Motivation für die Integration einer Altkomponente ist, dass sie eine hohe Qualität in der Praxis gezeigt hat und auch den Entwicklungsprozess beschleunigt. Um also die Altkomponente erfolgreich zu integrieren, muss der Kontext angepasst werden. Eine Möglichkeit wäre, das Ausschalten aus Zustand wiper 2 und Zustand wiper 3 jeweils über den Zustand wiper 1 umzusetzen. Für das Erlernen des gezeigten Beispiels wurde nicht mehr als 1 min. benötigt. Weitere Beispiele bis zu 15 Zuständen konnten problemlos innerhalb von 2 min. erkannt werden. Natürlich ist die Zeit für das Erlernen maßgeblich von der Antwortzeit des Systems abhängig. Liegt also eine lange Periode vor, wird entsprechend auch mehr Zeit benötigt, um das Verhalten der Altkomponente zu beobachten. 6 Resümee und Ausblick Wir haben in diesem Beitrag einen Ansatz vorgestellt, der es ermöglicht mechatronische Altkomponenten unter Berücksichtigung von Sicherheitseigenschaften in ein Systemmo- 84 Abbildung 3: Ausschnitt erlerntes Verhalten dell zu integrieren. Dies ist eine häufig gestellte Fragestellung in der industriellen Praxis. Zulieferer der Automobilindustrie sowie OEMs müssen häufig vorhandene Komponenten von Drittanbietern integrieren, ohne das Modell der Komponente zu kennen. Das vorgestellte iterative Verfahren ermöglicht das Verhaltensmodell einer Altkomponente zu erlernen und Sicherheitsanalysen auf den erlernten Modellen durchzuführen. Weiterhin ermöglichen wir durch die Integration von Systemidentifikationsverfahren die Erkennung von Reglerverhalten, welches zwingend benötigt wird, um die Korrektheit der Integration der Altkomponente sicherzustellen. Eine Werkzeugunterstützung dieses Verfahrens haben wir in [HBB+ 09] vorgestellt. Die bisherigen Evaluierungen haben ergeben, dass der Ansatz sich durchaus für mechatronische Systeme bewährt hat. Jedoch soll dieser Aspekt weiterhin untersucht werden, sowie eine Übertragung in andere Domänen, wie z.B. der dienstorientierten Systeme, betrachtet werden. Literatur [AD94] Rajeev Alur und David Dill. A Theory of Timed Automata. Theoretical Computer Science, 126(2):183–235, 1994. [Ang87] Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87–106, 1987. [Bal00] Helmut Balzert. Lehrbuch der Softwaretechnik - Software-Entwicklung. SpektrumAkademischer, 2. Auflage, 2000. [Ber06] Therese Berg. Regular Inference for Reactive Systems. Licentiate thesis, it, April 2006. [BGJ+ 05] Therese Berg, Olga Grinchtein, Bengt Jonsson, Martin Leucker, Harald Raffelt und Bernhard Steffen. On the Correspondence Between Conformance Testing and Regular Inference. In Fundamental Approaches to Software Engineering, Jgg. Volume 3442/2005, Seiten 175–189. Springer Berlin / Heidelberg, 2005. 85 [Cho78] T. S. Chow. Testing Software Design Modeled by Finite-State Machines. IEEE Trans. Softw. Eng., 4(3):178–187, 1978. [GHH08a] Holger Giese, Stefan Henkler und Martin Hirsch. Combining Compositional Formal Verification and Testing for Correct Legacy Component Integration in Mechatronic UML. In Rogério de Lemos, Felicita Di Giandomenico, Cristina Gacek, Henry Muccini und Marlon Vieira, Hrsg., Architecting Dependable Systems V, Jgg. 5135 of LNCS, Seiten 248–272. SPRINGER, 2008. [GHH+ 08b] Holger Giese, Stefan Henkler, Martin Hirsch, Vladimir Roubin und Matthias Tichy. Modeling Techniques for Software-Intensive Systems. In Dr. Pierre F. Tiako, Hrsg., Designing Software-Intensive Systems: Methods and Principles. Langston University, OK, 2008. 86 [HBB+ 09] Stefan Henkler, Moritz Breit, Christopher Brink, Markus Böger, Christian Brenner, Kathrin Bröker, Uwe Pohlmann, Manel Richtermeier, Julian Suck, Oleg Travkin und Claudia Priesterjahn. F RiT S Cab : Fujaba Re-Engineering Tool Suite for Mechatronic Systems. In Pieter Van Gorp, Hrsg., Proceedings of the 7th International Fujaba Days, Seiten 25–29, Eindhoven University of Technology, The Netherlands, November 2009. accepted. [HMSN10] Stefan Henkler, Jan Meyer, Wilhelm Schäfer und Ulrich Nickel. Reverse Engineering mechatronischer Systeme. In Seventh Paderborner Workshop Entwurf mechatronischer Systeme, accepted, HNI-Verlagsschriftenreihe, 2010. [HNS03] Hardi Hungar, Oliver Niese und Bernhard Steffen. Domain-Specific Optimization in Automata Learning. In Computer Aided Verification, Jgg. Volume 2725/2003, Seiten 315–327. Springer Berlin / Heidelberg, 2003. [JLS00] Henrik Ejersbo Jensen, Kim Guldstrand Larsen und Arne Skou. Scaling up Uppaal Automatic Verification of Real-Time Systems Using Compositionality and Abstraction. In FTRTFT ’00: Proceedings of the 6th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, Seiten 19–30, London, UK, 2000. Springer-Verlag. [PVY99] Doron Peled, Moshe Y. Vardi und Mihalis Yannakakis. Black Box Checking. In FORTE XII / PSTV XIX ’99: Proceedings of the IFIP TC6 WG6.1 Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XII) and Protocol Specification, Testing and Verification (PSTV XIX), Seiten 225–240, Deventer, The Netherlands, The Netherlands, 1999. Kluwer, B.V. [Reg96] Hendrik Cornelis DE. (NL) Regt. Vehicle windscreen wiper motor control circuit, October 1996. [Vas73] M. P. Vasilevskii. Failure diagnosis of automata. Cybernetics and Systems Analysis, 9(4):653–665, July 1973. Variability and Evolution in Model-based Engineering of Embedded Systems Goetz Botterweck Lero – The Irish Software Engineering Research Centre Limerick, Ireland [email protected] Andreas Polzer, Stefan Kowalewski Embedded Software Laboratory, RWTH Aachen Aachen, Germany {polzer | kowalewski}@embedded.rwth-aachen.de Abstract: In this paper, we report on techniques for variability and evolution in Model-based Engineering of Embedded Systems. The techniques are based on an integration of domain-specific languages for embedded systems with model-driven techniques for Software Product Lines. In particular, we discuss (1) product configuration with interactive tools, (2) product derivation with model transformations, and (3) first steps towards feature-oriented evolution planning. 1 Introduction Since many embedded systems are managed and developed as product lines of similar systems it seems to be natural that techniques for Model-based Engineering of Embedded Systems (MBEES) should be combined with techniques from Variability Modelling and Software Product Lines (SPL) to get the best of both worlds. However, although there are interesting first results in this direction, many challenges remain: • Integration – Despite the fact that appropriate concepts are available in the separate engineering disciplines (MBEES and SPL) the integration of the corresponding techniques and tools into consistent frameworks and tool-chains remains challenging. In particular, when trying to introduce variability and model-driven product line techniques to embedded systems, we have to respect existing domain-specific languages and the corresponding engineering practices, which are established in industry. • Lack of support for variability – Domain-specific modelling languages (DSML) for embedded systems lack support for variability. Hence, to realise variability we have to represent it either internally in the DSML with helper constructs (e.g., custom blocks that are tagged as “variation points”) or integrate the DSML with external 87 variability modelling techniques (e.g., by mapping blocks to features in a feature model). • Consistency and semantics of variable models – For isolated instances of the DSML we usually have semantics (explicitly or implicitly, e.g., through an implementation) and can check if the given instance is a valid model (according to the language definition). However, when dealing with a whole product line it is much more difficult to determine if all potential variants are valid models. The problem gets even more complex when we check the fulfillment of requirements (e.g., through formal verification or tests). • Complexity handling – Many authors in variability modelling and software product lines report complexity problems. These problems do not come from technical limitation alone. Product line engineering (PLE) involves many interactive activities and the sheer complexity of the involved artefacts (e.g., the number of variation points and dependencies between them) quickly reach the cognitive limitation of the human engineers. • Insufficient efficiency – Although there has been some progress in model-driven PLE [DRGN07, VG07, HKW08], in real projects the processes are often performed with insufficient efficiency. This is partly caused by lack of proper automated techniques. Another reason is the complexity of model-driven frameworks, e.g., when setting up automated workflows which process he models. It should be noted that we do not claim that we solve all these challenges. Instead the described issues set the context and objectives for the following discussion. In the remainder of the paper, we report on our current research in the area of variability and evolution of embedded systems, including interactive product configuration (Section 3), product derivation including the realisation of variability through model transformation (Section 4) and first steps towards model-based support for feature-oriented evolution planning (Section 5). The paper concludes with a brief overview of related work and final thoughts. 2 Overview of Our Approach Before we go into more detail, we give an overview of our framework. The approach (cf. Figure 1) can be structured along two dimensions. Vertically, we distinguish Domain Engineering and Application Engineering. This is consistent with well-known frameworks for Software Product Lines (SPL), e.g., [PBvdL05, CN02]. These two levels can be augmented with a third level of Language Engineering. Horizontally, we move (from left to right) from abstract Requirements over Features towards the concrete Implementation. Please note that we mark processes with numbers ( to ) and artefacts with uppercase letters ( to ). In addition, we use indexes (e.g., d and a ) to distinguish artefacts on Domain Engineering and Application Engineering level. 88 Language Eng. Requirements Features Implementation Meta-model Requirements Metamodel Implementation DSL Metamodel Feature Metamodel Model Process 1 2 Feature Implementation Feature Analysis Mappings Domain Engineering Legend Domain Feature Model Product Line Requirements Bd Ad Domain Implementation Model Cd 3 4 Product Derivation Application Engineering Product Configuration 5 Pruning Application Feature Model Product Requirements Aa Application Implementation Model Ca Figure 1: Overview of the workflow with artefacts and processes. 2.1 Domain Engineering Many SPL approaches use two types of models (see Figure 1): A model describing the available choices, e.g., a feature or variability model d and one or more implementation models describing how these choices are implemented Cd . Usually these models are mapped onto each other d to support further processing. The activities during Domain Engineering start with Feature Analysis creating a Domain Feature Model d , which defines the scope and configuration options of the SPL. Subsequently, in Feature Implementation a corresponding implementation is created. This can, for instance, be given in the native Simulink format (*.mdl files). To access this in our model-based approach, which relies on Eclipse-based model frameworks, we have to convert it into a model. For this we use techniques based on Xtext [EFb]. (see [PBWK09, BPK09a, BPK09b] for more details) and g. As a result we get the corresponding Domain Implementation Model Cd and Feature-Implementation Mappings d , which are required as input for Application Engineering. 89 List of feature model primitives Interactive Feature Graph Ad Cd Bd f1 exludes f3 User asking why c2 is automatically selected f2 requires f3 f1 is implemented by c1 Eliminated feature f2 is implemented by c2 Visual explanations: user selected f3 and f3 requires c2 Selected feature Figure 2: Configuration of a product line model in the S2T2 Configurator. 2.2 Application Engineering In our framework the activities in Application Engineering are grouped in two processes, Product Configuration and Product Derivation. In Product Configuration configuration decisions are made, taking into account the product-specific requirements and the Domain Feature Model d . The result defines the product in terms of features and is saved as the Application Feature Model a . In Product Derivation the configuration is turned into a product. The derivation starts with the Domain Implementation Model Cd and derives a product-specific implementation. After additional pruning , we get the Application Implementation Model Ca , which can be used in further processing steps (e.g., Simulink code generation) to create the executable product. In the following sections, we will look at these processes in more detail. 3 Product Configuration When configuring a product one major challenge is the complexity of the underlying models, caused, e.g., by the large number of variation points and dependencies between them. 90 This complexity is less problematic because of technical limitations (e.g., performance of algorithms) but because of the limited cognitive capacity of human engineers during the interactive parts of the process (e.g., when understanding all consequences of a particular configuration choice). One potential solution are approaches that support cognitive tasks that involve complex models, e.g., by applying software visualisation to enable visual configuration and visually-informed variability management [CNP+ 08]. However, with the objective of configuring a product, just a visual representation is not enough. In addition, we require a formal semantics that defines how configuration options and constraints are to be interpreted and executed during interactive configuration. For instance, to define the consequences of selecting a particular feature. In our work, we have taken formal semantics of feature models [CW07] and designed an interactive tool, S2T2 Configurator, which integrates a formal reasoning engine and a visual interface [BJS09, BSP09]. Figure 2 shows a very simple sample model in S2T2 Configurator. The visualisation is optimised to allow interaction with multiple submodels and the mappings between them (corresponding to the models d , Cd , d in Figure 1). It should be noted that the shown visual elements for the implementation model Cd are simplified representations, which are shown here for configuration purposes. For instance, this allows the engineer to specify that a certain component is not available at the moment. S2T2 Configurator will then update the available features accordingly. These simplified representations can automatically be derived from the real implementation models [BPK09a]. 4 Product Derivation After the product-specific configuration has been determined, the corresponding implementation needs to be derived. In the presented approach, this done in two steps, Negative Variability and Pruning. 4.1 Negative Variability The technique of Negative Variability assumes that the Domain Implementation Model Cd contains the union of all potential implementations. A product-specific implementation is then derived by selectively copying elements based on the configuration decisions stored in Application Feature Model a and the Feature-Implementation Mappings . The corresponding model transformation deletes all elements that are mapped to eliminated features and keeps all elements that are mapped to selected features. As an example consider the process in Figure 3, which applies a feature configuration (not shown in the figure) and removes all implementation elements that correspond to eliminated features. In the example, one block for a compass sensor (red block) and one block that implements the compass-based variant of an automatic parking mechanism (one of the blue blocks) are removed. 91 Domain Implementation Model Cd 4 Intermediate Step (before Pruning) Product Derivation 5 Application Implement. Model Pruning Ca Figure 3: Example of product derivation including pruning. 4.2 Pruning After the initial negative variability step the resulting implementation model contains dangling elements, e.g., lines that are no longer connected to blocks. Hence, an additional step is required, which we call Pruning (cf. Figure 3). Pruning requires knowledge about the semantics of the particular domain-specific language [BPK09b]. For instance, when deleting a Block in Simulink, we have to remove the corresponding Ports and as well. These Ports, in turn, might be referenced by Lines and so on. More details on the approach and the used higher-order model transformations can be found in [BPK09b]. 92 Feature Model Car Body Multimedia Devices Car Body Multimedia Devices Other Features Radio Monochrome Display Color Display requires Navigation Color Radio Display Radio Other Features Navigation DVD Enter‐ tainment requires Navigation Mono. Display Monochrome Monochrome Color Display Navi. Display Navi. Display Color Display Data Storage Hard Disk Drive DVD Drive requires Navigation Display Monochrome Color Navi. Display Navi. Display Implementation Structure Model Product Line Multimedia Devices Other Features Radio Radio Monochrome Display Car Body Car Body Multimedia Devices Other Features 2008 Evolution State 2009 Evolution State 2010 Evolution State 2011 Evolution State Figure 4: Example product line evolving over time. Car Body Multimedia Radio DVD Entertainment Navigation Radio Color Display Navigation Display Requires Radio External Data Storage (a) Feature model describing choices. Time Feature Multimedia Devices Radio Color Radio Display Navigation Navi. Requires Radio External Data Storage Navigation Display DVD Entertainment 2008 2009 2010 Today 2011 (b) Gantt-chart describing evolution plan. Figure 5: Example of feature-driven evolution planning with EvoFM. 5 Evolution Planning Industries that successfully apply product lines often have a strategic perspective and apply long-term planning and evolution of their product portfolios. This is particular true for embedded systems. A typical example is the automotive industry, where an integrated design of hardware and software is applied and requires careful synchronisation of the involved processes. With EvoFM [BPPK09] we strive to provide model-driven support for an feature-oriented planning of evolution. As an example scenario consider the sequence of product lines shown in Figure 4. Each product line (i.e., each evolution step) consists of several interrelated models (e.g., a Domain Feature Model and an Implementation Model as discussed earlier). Figure 5 gives a first impression of how EvoFM can be used to plan evolution. Please note that EvoFM does not represent a different view on the regular feature models in the product line. Instead it provides an abstract representation of the changes and variability that happen over time along the evolution path. For instance, the example EvoFM model shown in Figure 5(a) indicates that the functional cluster Radio will remain present throughout the 93 evolution (hence, it is a mandatory feature in EvoFM), whereas Radio Color Display, Navigation etc. are subject of evolution and can be introduced or removed (optional feature). Note the special feature Requires Radio representing the potential introduction or removal of a dependency. Given this model, evolution steps can be planned as its configurations. A sequence of evolution steps can be represented with a Gantt-Chart visualisation (see Figure 5(b)). Given a history of past evolution steps, the current product line models, and the evolution plan, we then can derive future instances of product line models. This is not trivial and involves many challenges. For instance, we have to trade-off between an abstract evolution model (easier to create and handle, hard to derive concrete product line models) and an more concrete evolution model with lots of technical details (harder to create and handle, easier to derive concrete product line models). More details on EvoFM, the underlying framework, and some usage scenarios, can be found in [BPPK09]. 6 Related Work Weiland [WR05] addresses variability in Simulink by marking standard blocks to represent choices. Hence, the implementation model also contains the variability information. A variant is chosen by setting the parameters and selecting a specific signal path. Kubica [Kub07] starts from a feature model in pure::variants, where the required features are chosen. Then, the corresponding Simulink model is built automatically from templates and fragments. There are other techniques for variability in DSML. For instance, Voelter and Groher [VG07] describe how to use openArchitectureWare [ope] for SPL Engineering. They evaluate their approach with a small sample product line of Smart Home applications. When dealing with variability, a typical challenge is the mapping of features to their implementation. Czarnecki and Antkiewicz [CA05] used a template-based approach where visibility conditions are described in OCL. Heidenreich et al. [HKW08] introduce FeatureMapper, a which can map features to arbitrary EMF-based models [EFa]. 7 Conclusions We would argue that the integration of techniques from (1) model-driven software in the large, software product lines, and variability modelling with (2) model-driven engineering of embedded systems promises great potential. Nevertheless, many challenges and research questions remain, e.g., in the improvement of efficiency, the integration of interactive and automated techniques, and the model-driven support for evolution. Future work involves the improvement of the model transformations, which implement the product derivation and pruning operations. Moreover, to realise the EvoFM approach we 94 are currently developing a catalog of evolution operations, which specify how particular evolution changes affect the product line models during an evolution step. Here we see major challenges in the handling of incomplete or inconsistent evolution plans. Acknowledgements This work is partially supported by Science Foundation Ireland under grant no. 03/CE2/I303 1 to Lero – The Irish Software Engineering Research Centre, http://www.lero.ie. References [BJS09] Goetz Botterweck, Mikolas Janota, and Denny Schneeweiss. A Design of a Configurable Feature Model Configurator. In Proceedings of the 3rd International Workshop on Variability Modelling of Software-Intensive Systems (VAMOS 09), January 2009. [BPK09a] Goetz Botterweck, Andreas Polzer, and Stefan Kowalewski. Interactive Configuration of Embedded Systems Product Lines. In International Workshop on Model-driven Approaches in Product Line Engineering (MAPLE 2009), colocated with the 12th International Software Product Line Conference (SPLC 2008), 2009. [BPK09b] Goetz Botterweck, Andreas Polzer, and Stefan Kowalewski. Using Higher-order Transformations to Derive Variability Mechanism for Embedded Systems. In ACES-MB 2009, 2nd International Workshop on Model Based Architecting and Construction of Embedded Systems, collocated with MODELS, 2009. [BPPK09] Goetz Botterweck, Andreas Pleuss, Andreas Polzer, and Stefan Kowalewski. Towards Feature-driven Planning of Product-Line Evolution. In 1st International Workshop on Feature-oriented Software Development (FOSD 2009), collocated with MODELS, 2009. [BSP09] Goetz Botterweck, Denny Schneeweiss, and Andreas Pleuss. Interactive Techniques to Support the Configuration of Complex Feature Models. In 1st International Workshop on Model-Driven Product Line Engineering (MDPLE 2009), held in conjunction with ECMDA 2009, Twente, The Netherlands, June 2009. [CA05] Krzysztof Czarnecki and Michal Antkiewicz. Mapping Features to Models: A Template Approach Based on Superimposed Variants. In GPCE’05, Tallinn, Estonia, September 29 - October 1 2005. [CN02] Paul Clements and Linda M. Northrop. Software Product Lines: Practices and Patterns. The SEI series in software engineering. Addison-Wesley, Boston, MA, USA, 2002. [CNP+ 08] Ciaran Cawley, Daren Nestor, Andre Preussner, Goetz Botterweck, and Steffen Thiel. Interactive Visualisation to Support Product Configuration in Software Product Lines. In Second International Workshop on Variability Modelling of Software-intensive Systems (VAMOS 2008), Essen, Germany, January 2008. [CW07] Krzysztof Czarnecki and Andrzej Wasowski. Feature Diagrams and Logics: There and Back Again. In SPLC ’07: Proceedings of the 11th International Software Product Line Conference (SPLC 2007), pages 23–34, Washington, DC, USA, 2007. IEEE Computer Society. 95 [DRGN07] Deepak Dhungana, Rick Rabiser, Paul Grünbacher, and Thomas Neumayer. Integrated tool support for software product line engineering. In ASE ’07: Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, pages 533–534, New York, NY, USA, 2007. ACM. [EFa] Eclipse-Foundation. EMF - Eclipse Modelling Framework. eclipse.org/modeling/emf/. [EFb] Eclipse-Foundation. Xtext. http://www.eclipse.org/Xtext/. [HKW08] Florian Heidenreich, Jan Kopcsek, and Christian Wende. FeatureMapper: Mapping features to models. In ICSE Companion ’08: Companion of the 13th international conference on Software engineering, pages 943–944, New York, NY, USA, 2008. ACM. [Kub07] Stefan Kubica. Variantenmanagement modellbasierter Funktionssoftware mit SoftwareProduktlinien. PhD thesis, Univ. Erlangen-Nürnberg, 2007. Arbeitsberichte des Instituts für Informatik, Friedrich-Alexander-Universität Erlangen Nürnberg. [ope] openarchitectureware.org. Official Open Architecture Ware Homepage. http:// www.openarchitectureware.org/. http://www. [PBvdL05] Klaus Pohl, Guenter Boeckle, and Frank van der Linden. Software Product Line Engineering : Foundations, Principles, and Techniques. Springer, New York, NY, 2005. [PBWK09] Andreas Polzer, Goetz Botterweck, Iris Wangerin, and Stefan Kowalewski. Variabilitaet im modellbasierten Engineering von eingebetteten Systemen. In 7. Workshop Automotive Software Engineering, collocated with Informatik 2009, Luebeck, Germany, September 2009. 96 [VG07] Markus Voelter and Iris Groher. Product Line Implementation using Aspect-Oriented and Model-Driven Software Development. In 11th International Software Product Line Conference (SPLC 2007), Kyoto, Japan, September 2007. [WR05] J. Weiland and E. Richter. Konfigurationsmanagement variantenreicher SimulinkModelle. In Informatik 2005 - Informatik LIVE!, Band 2. Koellen Druck+Verlag GmbH, Bonn, September 2005. Some Observations on SCADE Model Clones Michaela Huhn Dirk Scharff Institute for Software Systems Engineering Technische Universität Braunschweig Braunschweig, Germany {m.huhn|d.scharff}@tu-braunschweig.de Abstract: Clones, i.e. similar fragments within code or models, have been recognized as a relevant factor for maintenance and evolution of software artifacts. We extend the CloneDetective [JDH09], an open source clone detection toolkit, by a preprocessor for the handling of SCADE models. The extension comprises SCADE state machines, which leads to a first notion of clones in state-based behavior. We evaluate clone detection on SCADE models in two case studies. Moreover, further perspectives to integrate clone detection into model quality assurance are discussed. 1 Introduction Modeling at the level of detailed design and subsequent automated code generation has made its way as the prevailing development methodology in the embedded domain, in particular for safety-critical applications [Tec09] and in the automotive domain [BOJ04]. In difference to the incomplete models often used for specification in early design phases, modeling at the level of detailed design is employed as a graphical programming notation. On the one hand this kind of modeling offers domain-specific extensions and abstractions, on the other hand it is systematically restricted due to demands of determinism and efficient code generation. As domain-specific models are replacing manual code as the primary software artifacts from which the production code is generated, they become the final objective of development, maintenance and evolution. In other words, these models are an integral part of the strategic, intellectual property in the embedded domain. Due to economic reasons, many business scenarios aim at reuse of software and models. Hence, so-called internal qualities [ISO01], i.e. characteristics with a strong impact on development, maintenance, and evolution, are key factors for models nowadays as they formerly have been for code. Consequently, guidelines to improve comprehensibility and uniformity have been transferred from programming to modeling [HMD+ 04]. Another aspect which we consider here is the treatment of clones, i.e. multiple occurrences of similar or identical fragments within the code or model. Cloning often is intended by the developer for good reasons, however, clones may cause additional effort in maintenance and evolution [RCK09]: Not only for bug fixing, but also for feature extension or modification, all instances of a clone have to be examined for the necessity of change. 97 Whereas numerous works investigate clone detection on the basis of code (as surveyed in [RCK09]), the research on clones in model-based development is still in its beginnings [DHJ+ 08]. First answers have been given on the questions of match detection of model clones and graph-based heuristics to handle huge models [DHJ+ 08, NNP+ 09]. Clone detection has been applied on Matlab/Simulink models [Inc09, DHJ+ 08] and on UML sequence diagrams [LMZS06]. However, the impact of clones on model quality and the various possibilities to employ clone detection in quality assurance are discussed rarely, which is mostly due to the very few experiments performed so far. Contribution. This paper extends the CloneDetective [JDH09], an automated clone detection workbench developed at TU Munich, to SCADE models [Tec09]. For that, a SCADE parser and a SCADE-specific preprocessing of models has been implemented. In addition to data-flow oriented modeling using block diagrams, SCADE offers state-based modeling. Thus, we extended the preprocessing in such a way that clone matching applies for a first meaningful notion of state machine clones. This extension shall serve as a starting point for further investigations on state-based models. We applied clone detection to two medium size case studies from railway industries to extend the empirical knowledge on clones in model-based development. Based on discussions with developers from industries we identify different scenarios for model quality assurance methods built upon clone detection. In Sec. 2 we briefly outline the principles of graph-based clone detection, introduce SCADE as a modeling language for safety-critical applications, and describe the preprocessing and extensions needed to employ the CloneDetective on SCADE models. Next we present two case studies from rail automation industries and the bare results yield from clone detection. In Sec. 4 we classify the findings and deduce possible application scenarios for clone detection. In Sec. 5 we conclude. 2 Clone Detection According to [RCK09], we call two model fragments M1 , M2 clones of each other, if they are similar, i.e. S(M1 ) = S(M2 ) where S is some predefined similarity function. Similarity may be formalized in terms of syntactic or semantic affinity. The following similarity functions and their corresponding clone types are considered frequently [RCK09]: Type-I clones are syntactically identical fragments that differ only w.r.t. elements that are irrelevant already for a parser (e.g. comments, layout) Type-II clones may additionally differ w.r.t. the identifiers, literals, and types. Type-III clones are fragments that are modified further: In addition, parts may be altered added or removed. Type-IV clones are semantically equivalent, but are implemented by using different, but related syntactic constructs. 98 Parsing / Preprocessing Clone Detection Clone Clustering Reporting Figure 1: Clone detection phases Clone detection consists of four phases as shown in figure 1. The preprocessing phase is highly language dependent. In section 2.2 we will introduce our approach for the SCADE language. For the steps clone detection and clone clustering we essentially employ the existing CloneDetective components which we briefly sketch below. The reporting steps purpose is illustration of clone detection results typically as a web page showing the clones. In [DHJ+ 08], the authors describe a heuristic graph-based approach for model clone detection which they apply to Matlab/Simulink models: In a preprocessing step analog to the one described in Sec. 2.2, models are mapped to a graph. Now, let G = {V , E , L} be a directed graph with node set N , edge set E, and the labeling function L for nodes1 . Further, let Ω be the maximal set of pairs of nodes with matching labels, i.e. Ω = {(vi , vj ) ∈ V × V | vi 6= vj , ∧ L(vi ) = L(vj )}. Ψ is the set of clones which are represented as set of node pairs, initially Ψ = ∅. For each element in ω = (vi , vj ) ∈ Ω do the following: S Set ∆ to {ω}. If there is a pair ω 0 ∈ Ω \( Ψ ∪∆) which is a direct neighbor of any $ ∈ ∆, add ω 0 to ∆ . Continue doing this until there is no additional pair. ∆ is now the maximal clone containing ω. This clone is now added to the clone set, i.e. Ψ0 = Ψ ∪{∆}. The clone pairs in Ψ are then clustered to clone classes. A naive approach would miss any relationship with smaller clones being included in bigger ones. To fix this issue the authors check the inclusion relationship between reported pairs and are thus able to report these clones as well. Depending on the labeling function, Type-III or Type-II clones are detected. The approach has been implemented as CloneDetective within the ConQAT (Continuous Quality Assessment Toolkit) workbench, an open source initiative by Technische Universität München. For details we refer to [DHJ+ 08]. 2.1 SCADE Models for Embedded Software Control SCADE is a tool suite by Esterel Technologies for the model based design and verification of safety-critical, embedded systems. The SCADE code generator is certified according to the EN 50128 [CEN01], and also to other safety standards, for being used in a software development process for the higher software integrity levels, i.e. SIL 3 and 4. SCADE is based on the synchronous language Lustre which was developed in the early 1980s. SCADE offers block diagrams and operators that are familiar to engineers from control theory and differential calculus. Furthermore, SCADE supports state-based modeling by 1 In fact, the edges may be labeled as well, but the heuristics ignores edge labels. 99 Figure 2: Small fragments of SCADE models: Block diagram and state machine state-machines which can easily combined with data flows in several ways. The SCADE suite features a simulation and verification environment allowing the developer to quickly validate model behavior. Using the certified code generator the models can be directly compiled to C code for easy deployment, eliminating the need for low level testing. Figure 2 shows fragments of a SCADE model. On the left hand side of the figure a data flow is depicted, inter alia providing inputs for the state-machine on the right hand side. 2.2 Preprocessing SCADE Models SCADE models are stored in XML format. The grammar for the concrete syntax, as it is offered to the developer within the SCADE suite, slightly differs from the XML scheme. The preprocessing step maps the SCADE model (from the XML format) to a graph. It reflects the syntactical structure of the original SCADE model to ease the mapping between detected clones and model fragments. In the following paragraphs we will distinguish between syntactic differences of SCADE and its XML-scheme and transformations applied to the graph afterwards. Basically, the XML document is parsed: Data flows are mapped to nodes and directed edges by recursively stepping through the XML tree and constructing corresponding node objects. Some nodes, e.g. call-nodes encapsulating a compound operator with its arguments, are present in the XML schema but not in the SCADE concrete syntax itself. Thus, call nodes - and a number of similar XML elements - are skipped in the transformation to the directed graph. A necessary transformation that has to be applied to the graph is variable abstraction. Obviously, any variable serves the same purpose as a wired connection. The problem with variables is their handling in clone detection. If we’d keep them in the graph, they would be a difference disconnecting two clone parts from another, making the clones smaller and thus prohibiting them from even being detected as clones. It’s impossible to skip variables 100 transition 1 state 1 state 2 data flow 1 transition 2 data flow 2 Figure 3: Example graph representation of a state machine already in the parsing phase, because they are needed to identify other occurrences of them while parsing the rest of the document. Let Γ be the set of nodes with outbound edges leading to the variable and Ω the set of nodes with inbound edges from variable nodes. Variable nodes are dropped by first constructing a set of directed edges Γ × Ω directly connecting each node from Γ with each node from Ω and then removing the variable node and all adjacent edges from the graph. In this paper we upgrade model clone detection to state machines just by extending the preprocessing to the sublanguage dealing with state machines and leaving the clone detection kernel itself unchanged. As the clone detection kernel within CloneDetective decides on similarity on the basis of node labels only, state machines are transformed to a graph as follows: Both, states and transitions are represented by graph nodes. If a transition is connected to a state this is represented by a directed edge. The crucial question is how to build the node labels used by the similarity function in such a way that state machine clones are detected that are meaningful to the developer. In SCADE states and transitions feature variables and signals, i.e. arbitrary data flows may be associated to them. As a first proposal we want to treat two states (or transitions) as clone candidates only if they coincide on the type and host equivalent data flows. Therefore the data flow connected to a state or transition is encoded as a node label. The equivalence classes of states and transitions are evaluated by recursively concatenating the equivalence class representatives of the associated operators as illustrated in Figure 3. There are technical differences, but the effect of the encoding is similar to [NNP+ 09]. The result is a rather strict notion of similarity within state machines. Figure 4 shows a simple ConQAT model using the SCADE front end. The node ScadeScope parses the models and passes the preprocessed model to the ScadeCloneDetector using the ModelCloneDetectorFactory from [DHJ+ 08] on the model. The remaining nodes TableLayouter and HTMLPresentation generate a HTML document containing the results of clone detection. 3 Case Studies Here, we describe two case studies carried out in research and development projects at rail automation industries. The studies were developed independently from this paper and are 101 Figure 4: ConQAT model for SCADE clone detection offered to us for model quality assessment, in particular clone detection. On main lines, integrated train traffic control and supervision systems guarantee minimal risk of the passengers and optimal assistance for the personnel. But these systems require immense capital expenditures as they are usually based on advanced, highly reliable technology installed at the tracks. Regional or secondary lines are often not equipped with ACT due to economic constraints. However, railway suppliers have started to prototype new light-weight solutions based on upcoming smart sensor integration. Both our case studies focus on train control at secondary lines. At the current status of development, none of them implements a safety function, but they provide the train driver or dispatcher with additional information that may induce safety-relevant reactions. Moreover, future extensions may include safety functions. Thus, it was decided to select SCADE as a software development framework. Both case studies represent the base version of a particular system, for which variants are already planned. 3.1 Distributed train driver assistance system The first case study offers driver assistance and improves railway safety in a good valued manner. It is a distributed solution that acts autonomously with few low complexity auxiliary sensors to be installed on trains only. Each instance of the system analyses the current traffic situation on the track surrounding the train and issues warnings to the driver if necessary. This enables the driver to react properly. The SCADE model of the assistance system consists of approx. 650 nodes in 32 operators. With a portion of 44%, the model seems to contain many clones, at first glance. But looking closer, it becomes obvious that more than half of the detected clones are grouped around flatten and make operators, i.e. they concern the (de-)composition of structured data (see discussion in the next section). From the remaining ones, a subset could easily be abstracted to an operator, for others refactoring was not obvious. 102 Untitled Untitled Untitled Figure 5: Result of clone detection 3.2 Zugleitbetrieb Zugleitbetrieb (ZLB) is a low complexity centralized train operation system similar to ”train order” working in Australia or ”track warrant control” in North America. The basic concept is concentrating train control in a so-called dispatching center. Nowadays, train drivers exchange messages with a dispatcher usually via telecommunication. He/she handles route calls, does route reservations, lockings and clearances on the basis of his/her manual records on these messages and informs the drivers whether they are allowed to enter a requested route segment. Thus, the core safety requirement, namely to -1prevent trains from entering conflicting routes, solely depends on the dispatcher checking his/her records. Automated ZLB provides the dispatcher with automated decision support. It can be extended with driver assistance to display the dispatcher’s orders to the driver. -11Moreover, automatic train protection can be implemented if-Automated ZLB enhanced further with track-side equipment. The SCADE model of Automated ZLB core functionality consists of 1396 nodes in 87 operators. For the second case study, model clone detection totals at 53.5% of the models overall volume. In difference to the first, type composition with make and flatten nodes has only minor impact on reported clones: By setting the weight of make/flatten nodes to zero, the clone detections still results in 48.9%. The reason for this is a flat data type model while the type model of the first study is quite complex. However, it turned out that in the second case study half of the clones resulted from state machines. As our approach requires structural identical states and transitions to be connected to equivalent data-flows to be treated a clone-candidate this indicates that significant amounts of the model are identical. Figure 5 shows parts of the resulting HTML-page for the second case study together with the first clone. The clone corresponds to right hand side of the model fragment shown in figure 2. 103 Table 1: Clone detection result overview study 3.1 3.2 4 nodes 634 1264 clustered clones 12 29 clones overall volume 283 676 clone percentage 44.5% 53.5% Clone Detection in Model Quality Assurance Based on the figures from the case studies we discussed the perspectives of clone detection in model quality assurance with industrial senior application engineers. Thereby the following issues were identified: Language-dependent clones. SCADE offers a number of operators to (de)compose structured data types, of which make/flatten are the most prominent ones. In cases where multiple structured data are used, sequences of decomposing them to access the innermost components, or building the composition, easily forms a class of clones of significant weight. One could argue that these composition clones should be ignored by clone detection as they are unavoidable when dealing with structured data. However, discussion showed that such sequences are often created by copy & paste. They are perceived as clumsy and error-prone at least compared to the more compact access to structured data in modern programming languages. So, these clones seem to be significant for maintenance and evolution steps. Reuse of library functions. SCADE provides five built-in libraries with operators implementing frequently used functionality in a standardized way. For these operators, two questions are of interest: (1) Are the library operators chosen well for reuse? To answer this positively, one would expect a lot of occurrences of library operators. In case, they occur frequently within bigger clones, this indicates that even larger fragments could be generalized to library operators. (2) How well does the developers know and use the library? To answer the latter question, analysis should not only comprise syntactically similar but also a restricted version of Type-IV clones. User-defined operators. SCADE allows for user-declared operators and templates. The question is, however, when developers prefer “copy & paste“ plus “modify“, and when they consider model refactoring and operator declaration to be the adequate step. Here, it was suggested to dig into model repositories and track clones and user-declared operators during model evolution. Clone evolution. Related to the previous issue, is the question how different occurrences of a clone evolve over time. Recent work clone detection on code [JDHW09] has given some empirical evidence that the probability of errors is increased in inconsistently modified clones. So, one would expect this hypothesis to be approved for model clones. Another set of aspects concerning similarities of model fragments concern the homogeneous, structured use of concepts within a model. As any language, SCADE provides a number of concepts that are perceived as quite complex by itself or in a certain context. Moreover, the developer may choose from a set of variants in the concrete syntax to denote a certain concept. Obviously, comprehensibility of a model is improved by denoting 104 the same concept uniformly by the same operator and by a clear separation of conceptual different fragments of the model: Uniform use of operators. For instance, the SCADE operators pre and followed by are syntactic derivatives for feedback loops. To achieve a uniform usage, often modeling guidelines are introduced advocating for a favored operator. An alternative is to limit the number of syntactically different operators for a certain concept within a model, but leaving the actual choice to the developer. As application characteristics and individual experiences differ, this is considered more appropriate than strictly giving privilege to a specific operator. Similar arguments apply for the various redundant operators supporting state-based modeling. However, this kind of desired self-similarity can be detected by a parser extension simpler than clone detection. Separation of different conceptual fragments within the model. Our interview partners agreed that a clear separation of different concepts within a model is a prerequisite to understandability. Thus, the (de)composition of data, iteration, and timing should not be mixed with data processing fragments. Clone detection could be employed to search for separation patterns and anti-patterns and as a further step also guided refactoring has been suggested. So as a result of our discussion we learned that analysing similarities and dissimilarities in models is a much broader field than just clone detection. Acknowledgement. We are grateful to Stefan Gerken and Uwe Steinke from Siemens Industry Sector Mobility for fruitful discussions on SCADE model qualities. 5 Conclusion We extended the CloneDetective by a preprocessor for SCADE models. Besides block diagrams, our extension handles the SCADE state machines, and leads to a first, rather strict notion of state machines clones that requires not only structural equivalence of state machine clone candidates but also equivalence of the data flows associated to corresponding states and transitions. This notion of state machine clone has been found immediately useful when applied to a case study, because it identifies copy & paste of state machine fragments and respects structural levels. However, variants of state machine clones have to be investigated further, and a reasonable refactoring to remove state machine clones is not straight forward. As a proof of concept we applied clone detection to two medium size industrial case studies. The classification of the findings affirmed impressions and instincts of the developers on the SCADE modeling language but also on the specific models. These results initiated a discussion on the perspectives of integrating clone detection in a tool for SCADE model quality assurance. 105 References [BOJ04] M. Beine, R. Otterbach, and M. Jungmann. Development of Safety-Critical Software Using Automatic Code Generation. In SAE World Congress, 2004. [CEN01] CENELEC. EN 50128: Software für Eisenbahnsteuerungs- und Überwachungssysteme. Europäische Norm., 2001. [DHJ+ 08] F. Deissenböck, B. Hummel, E. Jürgens, B. Schätz, S. Wagner, J.F. Girard, and S. Teuchert. Clone detection in automotive model-based development. In Proceedings of the 30th International Conference on Software Engineering, pages 603–612, 2008. [HMD+ 04] Michaela Huhn, Martin Mutz, Karsten Diethers, Bastian Florentz, and Michael Daginnus. Applications of Static Analysis on UML Models in the Automotive Domain. In 5th Symposium on Formal Methods for Automation and Safety in Railway and Automotive Systems (FORMS/FORMAT 2004), pages 161–172, 2004. [Inc09] The MathWorks Inc. SIMULINK Simulation and Model-Based Design, 2009. www.mathworks.com/products/simulink/. [ISO01] ISO/IEC. ISO/IEC 9126-1: Software engineering ”‘Product quality”‘ Part 1: Quality model , June 2001. [JDH09] Elmar Jürgens, Florian Deissenböck, and Benjamin Hummel. CloneDetective - A workbench for clone detection research. In ICSE ’09: Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, pages 603–606, Washington, DC, USA, 2009. IEEE Computer Society. [JDHW09] Elmar Jürgens, Florian Deissenböck, Benjamin Hummel, and Stefan Wagner. Do code clones matter? In ICSE ’09: Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, pages 485–495, Washington, DC, USA, 2009. IEEE Computer Society. [LMZS06] Hui Liu, Zhiyi Ma, Lu Zhang, and Weizhong Shao. Detecting Duplications in Sequence Diagrams Based on Suffix Trees. In 13th Asia-Pacific Software Engineering Conference, (APSEC), pages 269–276. IEEE Computer Society, 2006. [NNP+ 09] Hoan Anh Nguyen, Tung Thanh Nguyen, Nam H. Pham, Jafar M. Al-Kofahi, and Tien N. Nguyen. Accurate and Efficient Structural Characteristic Feature Extraction for Clone Detection. In Marsha Chechik and Martin Wirsing, editors, 12th Intern. Conference on Fundamental Approaches to Software Engineering, (FASE), volume 5503 of LNCS, pages 440–455. Springer, 2009. 106 [RCK09] Chanchal Kumar Roy, James R. Cordy, and Rainer Koschke. Comparison and evaluation of code clone detection techniques and tools: A qualitative approach. Sci. Comput. Program., 74(7):470–495, 2009. [Tec09] Esterel Technologies. SCADE Suite, 2009. www.esterel-technologies.com/. Usability-Evaluation von modellbasiertem Engineering in der Automatisierungstechnik – Ergebnisse und Kriterien Birgit Vogel-Heuser Lehrstuhl für Informationstechnik im Maschinenwesen Technische Universität München Boltzmannstraße 15 85748 Garching b. München [email protected] Abstract: Viele Aussagen zur Anwendbarkeit der UML oder anderer Notationen in der Automatisierungstechnik beruhen auf subjektiven Einschätzungen und Erfahrungen. Es fehlen systematische Verfahren, mit denen der Nachweis über die Anwendbarkeit einer Notation im Engineering der Automatisierungstechnik geführt werden kann. Allgemeine Ansätze zur Usability-Untersuchung müssen auf den Anwendungsfall des Konstruierens in der Automatisierungstechnik, des Entwurfsprozesses, übertragen werden. Der Beitrag stellt die Untersuchungsergebnisse für Eingebettete Systeme in der Automatisierungstechnik für den Maschinen- und Anlagenbau vor und zeigt die Herausforderung bei der Gestaltung von experimentellen Evaluationen mit großen Probandengruppen. Die Ergebnisse zeigen das Spannungsfeld, in dem experimentelle Ansätze zur Bewertung komplexer Modellierungssprachen stehen. Die wesentliche Herausforderung ist die Festlegung der Komplexität der Aufgabenstellung: einerseits um relevante Aussagen treffen zu können und andererseits um das Training und die Versuchsdauer mit einer hinreichend großen Probandenzahl pro Versuchsbedingung experimentell bewältigen zu können. 1 Notationen im Engineering der Automatisierungstechnik für den Maschinen- und Anlagenbau Ausgehend von dem BMW-Prinzip [Sc99], der Unterscheidung von Beschreibungsmittel (im Beitrag synonym mit Notation verwendet), Methode und Werkzeug, sind für die Anwendung im Engineering der Automatisierungstechnik für den Maschinen- und Anlagenbau nicht nur das Beschreibungsmittel an sich, sondern auch die ggf. dazu verfügbare Methode und das Werkzeug entscheidend. Die Anforderungen an das Beschreibungsmittel ergeben sich aus der Prozessklasse des zu automatisierenden technischen Prozesses, der Automatisierungsgeräte und dem Projekt. Im Anlagenbau handelt es sich häufig um hybride Prozesse (diskret und kontinuierlich bzw. Batch), heterogene Automatisierungssysteme und einen iterativen Geschäftsprozess im Projekt (Abbildung 1). Wesentliche Anforderungen an Notation, Methode und Werkzeug sind die Zuordnung von Softwaremodellen zur Maschinen- bzw. Automatisierungshardware 107 (siehe verteilte Automatisierungshardware) sowie die Unterstützung der notwendigen Tätigkeiten in den verschiedenen Phasen des Engineering-Lebenszyklus (siehe hierzu Abbildung 1). Bezogen auf den Wunsch nach einem Modell-basierten Engineering zeigt sich in der Realität des Anlagenbaus häufig die Notwendigkeit noch auf der Baustelle, im Zielland, abschließende Modell- und damit Programmkorrekturen durchzuführen. Dies gilt insbesondere für neue Anlagentypen bzw. Maschinentypen, da diese weder vollständig als Modell im CAD bzw. CAE vorliegen noch als Simulation. Sie werden erst auf der Baustelle aufgrund ihrer Größe zusammengesetzt und somit wird die Funktionalität der Anlage erst mit dem Rohstoff (Papier, Holz o.ä.) überprüft und ggf. angepasst. Für die Nutzung eines Modell-basierten Engineering ist also entweder eine bidirektionale Schnittstelle zwischen Modellierungswerkzeug und Programmierwerkzeug (der IEC 61131-3 [VW08]) notwendig oder eine enge Integration des Modellierungswerkzeugs in die Programmierumgebung, d.h. das Modell ist der Code [WV09] und dieser muss auf Standardautomatisierungsgeräten implementierbar und wartbar sein. Abbildung 1: Anforderungen an Beschreibungsmittel, Methode und Werkzeug in der Automatisierungstechnik für den Maschinen- und Anlagenbau [Vo09] Die folgenden Untersuchungen beziehen sich auf diese Anwendungsdomäne und versuchen über die bisher subjektive Bewertung und Expertenevaluation [KVF04] hinaus einen systematischen Ansatz mit Hilfe von aus der Arbeitswissenschaft bekannten Methoden der Laborevaluation zu erarbeiten Grundsätzlich müssten alle Dimensionen der Abbildung 1 berücksichtigt werden, um eine realistische Arbeitsaufgabe und Arbeitssituation zu untersuchen. Dies ist unter Laborbedingungen schwierig zu realisieren. Aus Sicht der Anbieter von Engineering-Umgebungen stellt 108 sich die Frage, ob ein neues Beschreibungsmittel (wie UML [UML07]), eine unterstützende Methode und/oder ein erstelltes Werkzeug Verbesserungen im Vergleich zu den bisherigen bieten. Als erster Ansatz wird ein vergleichendes Design erwogen: altes Engineering-Werkzeug im Vergleich mit dem neuen Engineering-Werkzeug. Da die Eigenschaften der Engineering-Werkzeuge häufig sehr unterschiedlich sind, wird je nach ausgewählter Aufgabenstellung der Vergleich nicht objektiv sein können. Ein zweite zu klärende Grundsatzfrage lautet: Ist und wenn ja, wie ist beispielsweise Objektorientierung im Engineering der Automatisierungstechnik effektiv einsetzbar. Im Mittelpunkt dieser Frage steht also das Paradigma der Objektorientierung, welches konkrete Ausprägungen in der BMW-Dimension (welches Werkzeug, welche Methode) hat. Die Evaluation würde in diesem Falle enger auf die Eigenschaften der Objektorientierung gegenüber nicht-objektorientierten Ansätzen fokussieren. Kriterien zur Einschränkung des Versuchsdesigns für diese Fragestellungen werden in Kapitel 4 diskutiert. 2 Prinzipielle Kriterien beim Vergleich von Notationen für die Modellierung Die Anwendbarkeit von Modellierungssprachen ist bisher wenig untersucht [GW04]. Bisher existieren kaum systematische Verfahren, mit denen der Nachweis über die Anwendbarkeit einer Notation geführt werden kann [KV09]. Patig [Pa08, Pa09] und Gemino und Wand [GW04] stellen Ergebnisse verschiedener Experimente zur Untersuchung der Usability von Modellierungsnotationen zusammen. Patig fokussiert auf die Datenmodellierung bzw. die Usability von Metamodellen, während die Zusammenstellung von Gemino und Wand auch UML bzw. die Erstellung von Diagrammen, also eine Konstruktionsaufgabe, beinhaltet, aber nicht den Einsatz der UML für die Erstellung von Diagrammen. Außerdem stellen sowohl Patig als auch Gemino und Wand Kriterien für Usability-Untersuchungen zusammen, die mit unseren Erkenntnissen abgeglichen und ergänzt in Abbildung 2 dargestellt sind. Im Folgenden werden einige von Katzke und Vogel-Heuser [KV09] gefundene Kriterien für den Vergleich von zwei Notationen diskutiert und anhand des Vergleichs der UML 2.0 und der UML-PA (UML für die Prozessautomatisierung [K08]) veranschaulicht. Die Zusammenstellungen von Patig und Gemino und Wand [GW04] wurden insbesondere hinsichtlich der Aspekte Qualität der Ergebnisse, Training und Arbeitsaufgabe detailliert. Die Gründe für diese Erweiterung resultieren aus eigenen Evaluationen (Abbildung 1), die detailliert in Kapitel 3 erläutert werden. „Die empirische Untersuchung einer These zum Vergleich zweier Notationen (Sprachen) lohnt sich dann, wenn die Menge der betrachteten Unterschiede, von denen ein Effekt erwartet wird, klar definiert ist (Gegenstandsbestimmung [Rü08]) (…)“ 109 Einflussfaktoren Arbeitsaufgabe Training Art des Trainings Komplexität/ Art der Aufgabe Schwierigkeit/Größe (Aufgabentyp) Dauer Verständnis/ Analyse Werk- Vorgehenszeug weise Steuerbarkeit Gruppenarbeit /Einzelarbeit Werkzeug Skills Intelligenztest Anzahl pro Zelle z.B. Anzahl States Pausen Denk- Recherche- Diskussionspausen pausen pausen Vorgehensweise Demographische Daten m/w Dauer Vollständigkeit Korrektheit der Elemente der Elemente Modellierung Programmiersprache Notation Abhängige Variablen Qualität des Ergebnisses bezogen auf Mastermodell (Experten) Design/ Konstruktiv Unterbrechungen Programmierung Film Probanden Alter Akzeptanz der Aufgabenstellung Kentnisse Erhebung mit Wissenstest Abbildung 2: Einflussfaktoren für Experimente zur Anwendbarkeit von Modellierungsnotationen bzw. Programmiersprachen 110 „(…) jede Änderung für sich oder gemeinsam mit anderen Änderungen einen Effekt hervorrufen kann. Die Auswahl der betrachteten Unterschiede sollte motiviert sein (Gegenstandserklärung [Rü08]). In den Syntax- und Semantikspezifikationen der UML und der UML-PA existieren viele Unterschiede. Einige Änderungen unterstützen eine Kette von Modellzusammenhängen, die in Modellierungs- und Interpretationssituationen gemeinsam in einem Anwendungsfall der Sprache [He07] wirken, bei dem die unterschiedlichen Effekte im Gebrauch der Sprachen festgestellt werden sollen. das vorhandene Datenmaterial der explorativen Voruntersuchung Hinweise auf differenzierte Thesen liefert, die aber unter den vielen variablen Einflüssen des Vorversuches nicht evaluiert werden konnten (Theorie folgt aus Empirie [He07]). der beobachtbare Effekt nicht auch aus anderen Eigenschaften sicher geschlossen werden kann. Solche Effekte sind möglich, wenn in den Anwendungsmodellen bereits vorhandene, redundante Informationen genutzt werden können, um Teile der Modellierung nachfolgender Schritte zu generieren. In der UML-PA können detaillierte Verhaltensspezifikationen aus den Beschreibungen einzelner Szenarien generiert werden. Der UML fehlen dazu Informationen im Modellzusammenhang. Infolgedessen sind in der UML zusätzliche Modellierungsschritte erforderlich.“ [KV09] Die Versuche zur Anwendbarkeit und Verständlichkeit von Modellierungssprachen sollten sich nur in den betrachteten Sprachmerkmalen unterscheiden. Die Aufgabenstellung, die Arbeitsmittel und die Versuchsumgebung sollten sich eindeutig festlegen lassen, so dass die Versuche unter gleichen Laborbedingungen durchgeführt werden können. Die einzigen, nicht vollständig vermeidbaren Unterschiede liegen in den intraindividuellen Merkmalen (z.B. Kenntnisstand, Gedächtnisleistung, Abstraktionsvermögen, Aufmerksamkeit, Sicherheit, Synthesefähigkeit bzw. Problemlösefähigkeit) der Versuchspersonen. Diese Merkmale haben in unseren Versuchen einen wesentlich stärkeren Einfluss auf die Ergebnisse als erwartet. In Folgeuntersuchungen wurde deshalb ein Standard-Intelligenztest sowie ein Eingangstest für den Kenntnisstand in allen relevanten Gebieten (Logik, Modularität, Modellierungskenntnisse und fähigkeiten sowie Programmierkenntnisse und -fähigkeiten) eingesetzt. Die Methoden zur Bewertung der konstruktiven Fähigkeiten (Synthesefähigkeiten) und der Problemlösefähigkeit der Probanden vor einem Experiment sind noch zu klären. Zu jedem solcher Merkmale können die Gruppen entweder homogen oder heterogen zusammengesetzt sein. Heterogen zusammengesetzte Gruppen bieten den Vorteil, dass signifikante Ergebnisse eine höhere externe Validität aufweisen als die Beobachtungen homogener Gruppen [Sc05]. Dafür ist bei ihnen die zu erwartende Streuung der Messgrößen ausgeprägter und es werden mehr Versuchspersonen benötigt. Grundsätzlich sollten 12 bis 16 Versuchspersonen pro Versuchszelle erreicht werden. 3 Stand der Forschung zur Evaluation von UML Eine Zusammenstellung eigener Untersuchungen zeigt Tabelle 1. Die Untersuchung der Anwendbarkeit der Modellierungssprachen UML und ICL (Idiomatic Control Language) wurde in Laborexperimenten evaluiert [FPV07] [Fr09]. Die Untersuchungen zeigen deutlich den Konflikt, in dem experimentelle Ansätze zur Bewertung komplexer Modellierungssprachen stehen. In einem ersten Versuchsdesign wurde die Eignung der Modellierungssprachen zur Beschreibung SPS-basierter Systeme untersucht (Tabelle 1, Spalte UML vs. ICL Steuerungsprogrammierung [Fr09]). Das Versuchsdesign von Friedrich [Fr09] hat gezeigt, dass die Auswahl des Ausschnitts der Aufgabenstellung für die Evaluation von entscheidender Bedeutung ist, insbesondere vor dem Hintergrund der möglichen Aufwendungen (Zeit) für das Training (0,5 Tage) von unerfahrenen Probanden (z.B. Auszubildende oder Studierende im Praxisverbund (StiP)). Die hohe Fehlerrate beim Versuch mit UML zeigte, dass die Probanden offensichtlich nicht ausreichend trainiert waren bzw. die Aufgabenstellung nicht ausreichend gut verstanden hatten bzw. diese zu komplex war. 111 Tabelle 1: Vergleich unserer Untersuchungen zur UML in der Automatisierungstechnik Sequenzdiagramm, State Chart Verhalten nein 2-3 TN pro UML-Variante, pro Zelle 5 Teams Einzelperson, pro Zelle 6 TN Gruppengröße - fehlende Vorgehensweise - kaum Modellierung von Struktur, nur keine signifikanter Unterschied zwischen den Fehlerrate nur T1 ok., Streuung hoch, Verhalten Auswertung noch nicht abgeschlossen, Gruppen; Zusammenhang zwischen Sichten Vollständigkeit Schritte max. 94% UML-PA, - Prozess selber analysieren und modellieren Training nicht ausreichend, hohe Fehlerraten; der Diagramme nicht verstanden. 75% UML führt zu besserer Programmierleistung als Starke Tooleffekte (Autoplazierung fehlt) vorgegebenes Modell ; Fehlerrate deutlich zu hoch: VD1 43,84%; VD2 63,96% Ergebnisse gegebenes Modell (Ansteuerung PneumatikZylinder) erweitern um Fehlerbehandlungsroutinen gemäß textueller Spezifikation Einzelperson, pro Zelle 12 TN Modellierung Sortieranlage mit UML, UMLPA und UML-PA mit Anleitung (VD1) - Modellieren: UML/ICL/ohne; Programmieren: IEC 61131-3; (VD2) - aus Modell (UML/ICL/Text) Aufgabe verstehen; Programmieren: IEC 61131-3 1 und 2-er Gruppen (Teameffekte) Vorkenntnisse Modellierung und Test zum Arbeitsgedächtnis, VerarbeiProgrammierung ermittelt durch Fragebogen tungsgeschwindigkeit (Auszug Intelligenztest) Vorlesung ( UML Alltagsbsp.) 60' + Übung (Übungsbsp."Party planen"), 60' Programmier-umgebung, 60' State Charts, 60' Ablaufsprache Zeit, Fehler, Analyse der Ergebnisse, Beobachtung Versuchsaufgaben Wirkkette vom Sensor zum Aktuator, T1: UML-PA besser durch ein Diagramm als UML mit mehreren Diagrammen zur Erkennung zusammenhängender Informationen ermittelt durch Corsi Block Tapping Test (Prüfen des Kurzzeitgedächtnisses) nicht erhoben persönliche Eig. d. Probanden Vollständigkeit Modellelemente, Zeiten für Kommunikation in Gruppe/ Recherche Modell, Messgrößen angepasste UML-Statecharts: CoDeSys V3 + UML Plug-In; Ablaufsprache: CoDeSys V3 keine State Chart vs. Ablaufsprache keine nicht betrachtet UML: Klassendiagramme, Sequenzdiagramme, State Chart State Chart Ablaufsprache nicht betrachtet/ nicht betrachtet Angepasste UML-Statecharts vs. IEC 611313 Ablaufsprache Studenten BSc. Mechatroniker + Informatiker, Azubis Mechatroniker (3. Lehrjahr) Steuerungsmodellierung und programmierung UML- IEC 61131-3 [FRAUKKE] nicht betrachtet State Chart ja/ja, aber von Probanden nicht genutzt ja, UML-PA: Einschränkungen der Auswahl und Vorgehensweise durch Tool; Online-Hilfe keine, Papier und Bleistift zur Überprüfung der Modelle Zeit, Fehler im Modell, Fehler im Programm, Zeit, Fehler, Steigung zum Ziel Analyse Modell + Programm durch Experten Vorlesung (Schulung mit ppt, Geschwindigkeit einstellbar) + Vorlesung (90' pro Einheit) + Übung (45' pro Einführungsaufgabe (selbstständig, Einheit), kein Individualtraining, 3 Einheiten Kennenlernen Editor) + 1h Training (UML(UML, ICL, IEC 61131-3) PA) in Gruppen der UML-PA Vorlesung (1h) + Übung (1h) UML und UMLPA ja, Einschränkungen der Diagramme durch Tool Toolunterstützung bei der Modellierung Trainingsmethode/ Trainingsgegenstand/ Trainingszeiten in Gruppen der UML-PA Vorgehensweise Composite Structure Diagram, Instanzenstrukturdiagramm Klassendiagramm uneingeschränkte UML vs. Composite untersuchte Diagramme Structure Diagram, Instanzenstruktur der UML- Instanzenstruktur UML-PA vs. UML PA Hardware/Software Deployment ja/ja Struktur, Modularität nicht eingeschränkt/nicht betrachtet UML-PA vs. UML 2.0 eingeschränkte UML vs. UML-PA vs. Anleitung auf UML-PA Notation UML 1.5 / ICL Studenten Bsc. Informatik + Mechatronik mit StiPs, Studenten Elektrotechnik + ähnlichem Vorwissen (Vortest) Informationstechnik, Azubis, Techniker Studenten Bsc. Informatik + Mechatronik Auswirkung Modellierung auf die Steuerungsprogrammierung (Sortieranlage) UML vs. ICL Steuerungsprogrammierung [Fr09] Probanden Hauptuntersuchung: Wirkkette von Sensor zum Aktuator (keine aktive Modellierung) Modellierung UML-PA vs. UML [Ka08] Voruntersuchung: Modellierung einer Sortieranlage Evaluationsexperimente Untersuchungsgegenstand Kriterium Notation Modell Versuch 112 Insgesamt zeigen die Versuche, dass die UML trotz der Kritikpunkte grundsätzlich Vorteile für das Software-Engineering in der Automatisierungstechnik für den Maschinen- und Anlagenbau bietet. Die Ergebnisse zeigten jedoch auch, dass die UML in der uneingeschränkten Form nur bedingt geeignet ist, um die Steuerungsprogrammierung zu unterstützten. Die Vielzahl der Diagramme und die große Freiheit in der Modellierung führten besonders bei den unerfahrenen Anwendern zur Verwirrung und damit auch zu der geringen Qualität der Modelle und der hohen Fehlerrate der Programme (Zelle Versuch, Ergebnisse). Eine differenzierte Betrachtung verschiedener Aspekte (Strukturmodelle, Interaktionen, Detailverhalten, Zusammenhang der Diagramme) der UML fand bisher kaum statt. Andererseits ist gerade die Verbindung verschiedener Sichten in einem zusammenhängenden Modell eine wesentliche Eigenschaft der UML, die bei der Betrachtung einzelner Diagramme oder Elemente der UML verloren gehen würde. Die Beobachtungen zeigten, dass neben der Sprachdefinition auch Vorgehensweisen und Werkzeugkonzepte die Anwendbarkeit einer Modellierungssprache beeinflussen (siehe Kriterien Tabelle 1). Die vergleichende Evaluation der UML-PA als domänenspezifisches Profil der UML mit der UML 2.0 [Ka08] zeigte bei der ersten These1 eindeutige Ergebnisse, allerdings bei einem sehr eingeschränkten Versuchsdesign (Arbeitsaufgabe mit geringen Freiheitsgraden) und einer sehr kleinen Probandengruppe. Die wesentliche Herausforderung ist die Festlegung der Komplexität der Aufgabenstellung: einerseits um für die Anwendung in der Industrie relevante Aussagen treffen zu können und andererseits um das Training und die Versuchsdauer mit einer hinreichend großen Probandenzahl pro Versuchsbedingung experimentell im Labor bewältigen zu können. Grundlage für die Festlegung der Arbeitsaufgabe für das Versuchsdesign ist in der Regel eine Tätigkeitsanalyse entweder mittels der Task Action Grammar [Sh01] [PG89] oder GOMS [Wa93]. Insbesondere für konstruktive Aufgaben gestaltet sich diese aufgrund des hohen Freiheitsgrades und damit der vielen verschiedenen zulässigen Tätigkeitssequenzen (Kombinationen von atomaren Tätigkeitseinheiten, Sub Goal Templates) schwierig. 4 Kriterien zur Einschränkung des Versuchsdesigns Anhand der Arbeiten von Katzke [Ka08], Friedrich [Fr09] sowie der Ergebnisse des Projekts FRAUKKE [FRAUKKE] (Tabelle 1) sollen im Folgenden einige Kernfragen zur Einschränkung des Versuchsdesigns beispielhaft diskutiert werden, und zwar: Training, Arbeitsaufgabe und Werkzeugunterstützung. Die Arbeitsaufgabe ist direkt abhängig von der zu zeigenden These. Bei einem vergleichenden Design werden in der Regel insbesondere die angenommenen Stärken des neuen Ansatzes experimentell 1 These 1: „Eine definierte Menge zusammenhängender Informationen kann in der aus einem Diagrammtyp bestehenden Instanzendarstellung der UML-PA in kürzerer Zeit erkannt und wiedergegeben werden, als in den über verschiedene Diagrammtypen verteilten Instanzendarstellungen der UML“ 113 evaluiert (bei Katzke die Instanzenstrukturdiagramme als integrierte Diagramme). Die Komplexität der Arbeitsaufgabe ist direkt von der möglichen Versuchs- und Trainingsdauer abhängig. Im Engineering sind Versuchsdauern (inklusive Training) von mindestens 3-4 Stunden notwendig. Bei Friedrich zeigte sich, dass das Training nicht ausreichend war. Die Arbeitsaufgabe konnte von den Probanden nicht ausreichend gut erfüllt werden. Dies ist für die Bachelorstudenten sehr erstaunlich, da diese bereits in verschiedenen Grundlagenveranstaltungen und Praktika die UML erlernt hatten. Die Frage, wie die Probanden in einer begrenzten Zeit sicher mit der Arbeitsaufgabe vertraut gemacht werden können, ist für das Engineering der Automatisierungstechnik noch nicht beantwortet. Als weitere Randbedingung stellt sich die Frage der Werkzeugunterstützung. Katzke hat bewusst ein sehr stark eingeschränktes Werkzeug benutzt und argumentiert, dass damit die Methode UML-PA unterstützt wird, während bei der UML wenig Unterstützung und damit Verwirrung gegeben sei. Friedrich hat sich gegen ein Werkzeug entschieden, einerseits weil für die ICL (Idiomatic Control Language), die Vergleichsnotation zur UML, kein geeignetes Werkzeug verfügbar war, aber auch, weil die Behauptung, dass die Ergebnisse nur aufgrund eines bestimmten Werkzeugs (welches entweder besonders gut oder besonders ungeeignet sei) auftraten, ausgeschlossen werden sollte. Die Frage, ob die UML für die Automatisierungstechnik einsetzbar und nützlich ist, sollte bereits vor der Entwicklung und der Verfügbarkeit eines integrierten Werkzeugs (bidirektionale Kopplung) beantwortet werden. Erst wenn diese Frage positiv beantwortet ist, würde sich eine zugeschnittene Werkzeugentwicklung für die Automatisierungstechnik lohnen. Mittlerweile liegt jedoch ein erster Prototyp eines integrierten Werkzeugs vor [WV09]. Der überdurchschnittlich starke Einfluss des Werkzeugs auf die Evaluationsergebnisse wird in einer neuen Untersuchung (Tabelle 1, Spalte UML-IEC 61131-3 [FRAUKKE]) bestätigt, bei der ein UML-Plugin in einer IEC 61131-3 Umgebung evaluiert wurde. Die Probanden haben sich in hohem Maße über bestimmte Eigenschaften des Werkzeugs, wie eine fehlende Autoplazierung, beschwert und haben dies als sehr störend eingeschätzt, wie das narrative Interview nach dem Experiment ergab. In diesem Experiment scheint der Störeinfluss des Werkzeugs größer gewesen zu sein als der Effekt der verschiedenen Notationen. Andererseits sind Untersuchungen zum Model Driven Engineering nur werkzeuggestützt sinnvoll möglich, weil das Modell das Programm darstellt und nur so der Code aus dem Modell erzeugt werden kann. Aus diesem Experiment ist jedoch zu folgern, dass Prototypen, die einen unzureichenden Stand haben bzw. von den Probanden erwartete Features nicht anbieten, keine Evaluation der zu Grunde liegenden Notation erlauben. 5 Zusammenfassung und Ausblick Der Beitrag hat einige der Probleme bei der Evaluation von Beschreibungsmitteln, Methoden und Werkzeugen am Beispiel der realen Engineering-Aufgaben in der Domäne der Automatisierungstechnik gezeigt und verdeutlicht den Forschungsbedarf einerseits im Hinblick auf die konkrete Fragestellung in der Domäne der Automatisierungstechnik, und andererseits in der Methode für die Evaluation von Beschreibungsmittel, Methode und Werkzeug hinsichtlich der Usability im Allgemeinen. 114 Literaturverzeichnis [FPV07] Friedrich, D.; Pantförder, D.; Vogel-Heuser, B.: Evaluation of UML in process automation – results of an experimental approach. In: Proc. 10th IFAC IFIP/IFORS/IEA Symposium Analysis, Design and Evaluation of Human-Machine Systems. Seoul, Korea, 04. - 06.09.2007. [Fr09] Friedrich, D.: Anwendbarkeit von Methoden und Werkzeugen des konventionellen Softwareengineerings zur Modellierung und Programmierung von Steuerungssystemen. Dissertation, University Press, Kassel, 2009. [FRAUKKE] FRAUKKE – FRAUenKompetenz in Konstruktions- und Entwicklerberufen. gefördertes Projekt, HMWK, Hessen. [GW04] Gemino, A.; Wand, Y.: A Framework for Empirical Evaluation of Conceptual Modeling Techniques. In: Requirements Engineering, Heft 09/2004, SpringerVerlag, London; S. 248-260. [He07] Heimerl, P.: Fallstudien als forschungsstrategische Entscheidung. In (Buber, R.; Holzmüller, H. H.): Qualitative Marktforschung. Konzepte – Methoden – Analysen. Springer-Verlag, Berlin, 2007; S. 381-400. [Ka08] Katzke, U.: Spezifikation und Anwendung einer Modellierungssprache für die Automatisierungstechnik auf Basis der Unified Modeling Language (UML). Dissertation, University Press, Kassel, 2008. [KV09] Katzke, U.; Vogel-Heuser, B.: Vergleich der Anwendbarkeit von UML und UMLPA in der anlagennahen Softwareentwicklung der Automatisierungstechnik. In: at – Automatisierungstechnik, Heft 07/2009, Oldenbourg, München; S. 332-340. [KVF04] Katzke, U.; Vogel-Heuser, B.; Fischer, K.: Analysis and state of the art of modules in industrial automation. In: atp international – Automation Technology in Practice international, Heft 01/2004, Oldenbourg, München; S. 23-31. [Pa08] Patig, S.: A Practical Guide To Testing the Understandability of Notations. In (Hinze, A.; Kirchberg, M. Hrsg.): Proc. 5th Asia-Pacific Conference on Conceptual Modelling (APCCM 2008). Wollongon, Australia, January 2008; S. 49-58. [Pa09] Patig, S.: Preparing Meta-Analysis of Metamodel Understandability. In: Proc. Workshop Empirical Studies of Model Driven Engineering (ESMD 2008), Toulouse, France. 29.09.2008; S. 11-20. [PG89] Payne, J.; Green, G.: Task-Action Grammar: the model and its developments. In (Diaper, D. Hrsg.): Task Analysis for Human-Computer Interaction. Ellis Horwood Ltd., Chichester, 1989; S. 75-107. [Rü08] Rüßler, H.: Einführung in die Fachhochschule Dortmund, 2008. [Sc05] Schmid, U.: Empirische Forschungsmethoden. In: Einführung in die Angewandte Informatik III. Vorlesung, Otto-Friedrich Universität Bamberg, 2005. empirische Sozialforschung. Vorlesung, 115 116 [Sc99] Schnieder, E.: Methoden der Automatisierung. Beschreibungsmittel, Modellkonzepte und Werkzeuge für Automatisierungssysteme. Vieweg, Wiesbaden, 1999. [Sh01] Shepherd, A.: Hierarchical Task Analysis. Taylor & Francis, Cornwall, 2001. [UML07] Unified Modeling Language – Superstructure – Version 2.1.1. Object Management Group, Needham, MA, 2007. [Vo09] Vogel-Heuser, B.: Objektorientierung im Engineering der Automatisierungstechnik: Fluch oder Segen? In (Vogel-Heuser, Birgit Hrsg.): Automation & Embedded Systems. Effizienzsteigerung im Engineering. University Press, Kassel; S. 8-19. [VW08] Vogel-Heuser, B.; Wannagat, A.: Modulares Engineering und Wiederverwendung in CoDeSys V3. Oldenbourg, München, 2008. [Wa93] Wandmacher, J.: Software-Ergonomie. de Gruyter, Berlin 1993. [WV09] Witsch, D.; Vogel-Heuser, B.: Einsatz von UML-Diagrammen in der Steuerungsprogrammierung. In (Vogel-Heuser, Birgit Hrsg.): Automation & Embedded Systems. Effizienzsteigerung im Engineering. University Press, Kassel, 2009; S. 30-77. Qualifying Software Tools According to ISO 26262 Mirko Conrad1, Patrick Munier2, Frank Rauch3 1 The MathWorks, Inc., Natick, MA, USA [email protected] 2 The MathWorks, SAS, Grenoble, France [email protected] 3 TÜV SÜD Automotive GmbH Munich, Germany [email protected] Abstract: The growing adoption of safety standards in the automotive industry results in an increasing interest in as well as an increasing uncertainty about software tool certification and qualification. With ISO 26262 on the horizon, new tool qualification requirements need to be understood and implemented by automotive software practitioners. This paper summarizes the tool qualification approach of ISO/DIS 26262 and contrasts it with tool certification and qualification requirements outlined in other safety standards and guidelines. The authors also report about their first-hand experiences with qualifying development and verification tools according to ISO/DIS 26262 in practice. 1 Tool Certification / Qualification Approaches in Standards and Guidelines This section is intended to provide an overview about the requirements in popular safety standards and guidelines pertaining to qualifying or certifying software tools. The following discussion should provide the context for a more detailed discussion of the ISO/DIS 26262 tool qualification approach in sections 2 and 3. So far, there is no single approach for tool qualification or certification across standards. Rather, different standards attach different levels of importance to tool certification / qualification and suggest different approaches to gain confidence in the tools used. Typically, tool users are responsible in the end for the certifying or qualifying the software tools they are using. Tool vendors can support these efforts by providing certification or qualification kits that ease the certification or qualification efforts on the user‘s side. The safety standards and guidelines discussed in the following paragraphs target different application sectors with domain-specific requirements. The amount, scope, complexity and criticality of software tools used during the development of high-integrity systems may differ between these sectors. From the authors‘ point of view, this might be one of the reasons for having divergent tool qualification / certification requirements. 1.1 DO-178B DO-178B is considered to be one of the most stringent safety standards used in industry. It clearly defines the conditions under which a software tool needs to be qualified (DO-178B, 117 section 12.2), i.e. tool qualification is required if the answer to each of the following three questions is ‗yes‘: (1) Can the tool insert an error into the airborne software or fail to detect an existing error in the software within the scope of its intended usage? (2) Will the output of the tool not be verified as specified in Section 6 of DO-178B? (3) Will the output from the tool be used to meet or replace an objective of DO-178B, Annex A? Tool qualification is defined as the ―process necessary to obtain certification credit1 for a software tool within the context of a specific airborne system‖ (DO-178B, Glossary) There are two types of tools that may require qualification: development and verification tools. If the answer to the question: (4) Is the tool output part of the airborne software, such that the output can insert an error into the software? is ‗yes‘ the tool needs to be qualified as development tool, otherwise it needs to be qualified as verification tool. Verification tools are simpler to qualify, because they cannot, by definition, inject errors into the final product. Development tool qualification requires that the development process for the tool satisfies the same objectives as the software development process of the airborne software. The software level assigned to the tool is the same as for the airborne software it produces unless the applicant can justify a reduction of the tool‘s software level to the certification authorities. Verification tool qualification requires the user to demonstrate that the tool complies with its operational requirements under normal operation conditions. In practice this can be achieved with documented tool operational requirements and a set of test cases that allow one to verify, that the tool correctly implements these requirements under normal operating conditions. Tools need to be qualified on a per project basis. Tool qualification activities are subject to a planning phase that is documented in a tool qualification plan. Using qualified tools allows one to achieve dedicated certification credits. DO-178B tool qualification is widely discussed e.g. in [HB07, KZ09]. 1.2 IEC 61508 IEC 61508 (Ed. 1.0) includes the concept of tool certification. The standard recommends (for SIL 1) or highly recommends (for SIL 2-4) the use of certified tools and translators (IEC 61508-3, table A.3). Wherever possible, tools should be certified so that some level of confidence can be assumed regarding the correctness of their outputs (IEC 61508-7, clause C4.3.). As an alternative, tools with increased confidence from use are highly recommended for all SILs. The standard provides little guidance on how to certify a tool. As a result a variety of different tool certification approaches has been used in practice [KM03, JG03, Glö08, TMW08, TMW09, SLM09, BB09]. Developing a software tool as per IEC 61508-3 is just one of multiple options here. Tool certification is viewed as a generic measure to increase the confidence in the tools used, if increased confidence from use cannot be claimed. No certification credits are offered in 1 118 Acceptance by the certification authority that using a tool satisfies a certification requirement exchange for tool certification. This way there is little incentive for applicants to certify tools if it can be avoided. Requirements for tool qualification are limited, because the IEC 61508 software life cycle for embedded software is set-up to uncover potential tool errors. IEC 61508-3 also emphasizes the use of an integrated tool chain (IEC 61508-3, clause 7.4.4.2). The upcoming second edition IEC 61508 (Ed. 2.0) distinguishes between online2 and offline3 tools. Software offline support tools are divided into the following categories (cf. IEC 61508-4 Ed. 2.0, clause 3.2.11): T1: tools that cannot directly or indirectly contribute to the executable code of the system T2: tools supporting verification or test of the design or the executable code; errors in these tools can fail to reveal defects T3: tools generating outputs that can directly or indirectly contribute to the executable code of the system Depending on the tool‘s classification, the identification of use cases and related hazards is required. T3 offline tools require evidence that the tool conforms to its specification or manual. This evidence may be based on confidence from use or on application independent validation. If such evidence is not available, application-specific measures to uncover potential tool errors, such as back-to-back testing, could be implemented by the applicant. Each new version of an off-line support tool shall be qualified. This delta qualification may rely on evidence provided for an earlier version. Both editions of IEC 61508 very much value confidence from use as a measure to gain confidence in the tools used. 1.3 ISO/DIS 26262 Although ISO/DIS 26262 is considered a derivative standard of IEC 61508, tool qualification approaches in these two standards differ significantly. ISO/DIS 26262 contains detailed guidance on software tool qualification (ISO/DIS 26262-8, 11). The objective of tool qualification is to provide evidence that a software tool is suitable for use in the development of safety-related software according to ISO/DIS 26262. The use cases for a tool need to be documented and analyzed. This analysis shall evaluate if the malfunctioning software tool or its erroneous output can lead to the violation of a safety requirement. In addition, the probability of preventing or detecting such errors in the output of the tool needs to be evaluated. Based on this analysis, a required tool confidence level (TCL) is determined. The required TCL, together with the Automotive Safety Integrity Level (ASIL) of the safetyrelated software developed using the software tool, guides the selection of the appropriate tool qualification methods. These tool qualification methods are listed in tables 2, 3, and 4 of ISO/DIS 26262-8. Increased confidence from use is one of the possible qualification methods, however the level of recommendation in the above mentioned tables decreases for the higher TCLs and ASILs. 2 Software on-line support tool: software tool that can directly influence the safety-related embedded system during its run time Software off-line support tool: software tool that supports a phase of the software development life cycle; cannot directly influence the safety-related embedded system during its run time 3 119 With this approach, ISO/DIS26262 provides very detailed guidance to classify the tools and to estimate the required level of tool qualification. However, unlike earlier draft versions, ISO/DIS 26262 does not distinguish between different tool categories. Details of the ISO/DIS 26262 tool qualification will be discussed in chapters 2 and 3. [Sau09] touches upon this topic as well. 1.4 MISRA-C MISRA-C sees compilers and static checking tools as trusted processes. This means that there is certain level of reliance on the output of the tools. It needs to be ensured that this trust is not misplaced (MISRA-C:2004, section 4.2.3). MISRA-C:2004 suggests documented validation testing as the method of choice to gain confidence in the tools used. Ideally, the tool supplier should carry out the validation tests. The tool vendor should be able to provide records of the verification activities and change records to document a controlled software tool development. The tool vendor should also have a bug reporting and tracking mechanism. The size of the user base together with an assessment of the bugs reported over the last 6-12 months is seen as an indication of the stability of the tool. If tool validation information is not available from the tool vendor, confidence in the tool can be gained by the tool user for example by adopting the following approaches: Documented validation testing Assessment of the development processes use by the tool supplier Review of the tool‘s performance 2 The ISO/DIS 26262 Tool Qualification Approach This section provides a brief overview about the tool qualification approach as outlined in the draft standard. 2.1 ISO/DIS 26262 ISO 26262 is an emerging international safety standard titled Road vehicles — Functional safety. This sector specific standard for the automotive industry is intended to be applied to safety-related systems that include one or more E/E systems4, and are installed in series production passenger cars with a maximum gross weight of up to 3.5 tons. The draft international standard, ISO/DIS 26262 was published in summer 2009. Part 8 of the draft international standard, ISO/DIS 26262-8 Supporting processes, addresses multiple crossfunctional topics, including the qualification of software tools. 2.2 Tool Qualification Overview The use of software tools can simplify or automate activities and tasks required by ISO 26262 for the development of safety-related software (ISO/DIS 26262-8, 11.2). The objective of ISO 26262 software tool qualification is to provide evidence that a software tool is suitable for use 4 Systems that consists of electrical and electronic elements, including: programmable electronic elements, power supplies, input devices, communication paths, and output devices. 120 in the development of safety-related software, such that confidence can be achieved in the correct execution of activities and tasks required by ISO 26262 (ISO/DIS 26262-8, 11.1). To determine the required tool confidence level (TCL), the use cases of the tool shall be analyzed. This analysis shall evaluate: If a malfunctioning software tool and its erroneous output can lead to the violation of any safety requirement allocated to the safety-related software to be developed. The probability of preventing or detecting such errors in the output of the tool. The evaluation considers measures internal to the software tool (for example, monitoring), as well as measures external to the software tool (for example, guidelines, tests, and reviews) that are implemented in the development process for the safety-related software. The required TCL, together with the Automotive Safety Integrity Level (ASIL) of the safetyrelated software developed using the software tool, allows the selection of the appropriate tool qualification methods. Tool qualification can be carried out for individual tools as well as for tool chains or sets of tools. The ISO/DIS 26262 tool qualification process requires the creation of the following tool qualification work products (ISO/DIS 26262-8, 11.5; see the appendix for a summary): Software Tool Qualification Plan Software Tool Documentation Software Tool Classification Analysis Software Tool Qualification Report 2.3 Software Tool Qualification Plan (STQP) The software tool qualification plan is a planning document created in an early phase of the development of the safety-related system. Besides stating the applicant, and the application under consideration, it identifies the tool and tool version to be qualified, the intended configuration and operational environment. In this sense, the STQP shares conceptual similarities with tool qualification plans used in DO-178B projects. The tool qualification plan also lists the intended tool use cases. It is supposed to list the tool qualification methods and available means to detect malfunctions or erroneous output of the tool. 2.4 Software Tool Documentation (STD) The software tool documentation comprises different information that the tool applicant may need when using the tool. It comprises information such as: tool overview, available tool documentation set, operational environment and constraints, installation instructions, known issues. The STD also provides information necessary to check whether the use cases, configurations and operational environment listed in the STQP are supported by the tool. It has similarities to the description of tool operational requirements as per DO-178B. 121 2.5 Software Tool Classification Analysis (STCA) The tool classification is necessary to determine the required tool confidence level (TCL). It depends on the particular tool use cases used during the development of the application under consideration. The tool confidence level can be derived using the schematics provided in Fig. 1. Fig.1: ISO/DIS 26262 Tool Classification Scheme Tool Impact (TI) First, the intended use cases for the tool shall be analyzed to determine if a safety requirement can be violated if the software tool is malfunctioning or producing erroneous output. If a violation of a safety requirement is not possible, tool impact TI0 shall be chosen. Otherwise, the tool impact is TI1 (ISO/DIS 26262-8, 11.4.3.2.a). Tool Error Detection (TD) Second, the intended software tool use cases shall be analyzed to determine the probability of preventing or detecting that the software tool is malfunctioning or producing erroneous output. The degree of confidence, that a malfunction or an erroneous output from the tool can be prevented or detected, determines the tool error detection TD as outlined in Table 1 (ISO/DIS 26262-8, 11.4.3.2.b). Tab.1: Tool Error Detection Levels Degree of confidence Tool error detection high TD1 medium TD2 low TD3 no systematic verification measures in subsequent development phases malfunctions or erroneous outputs can only be detected randomly TD4 Tool Confidence Level (TCL) If TI and TD have been chosen, the tool confidence level (TCL) can be determined following the schematics provided in Figure 1 (ISO 26262-8, 11.4.3.4). Having multiple use cases for a tool can potentially result in multiple TCLs. To determine the required tool qualification measures, the maximum TCL required (TCLREQ) to support these use cases needs to be established. TCLREQ needs to be documented in the STQP. 122 Tool Qualification Methods (TCM) A tool classified at TCL1 does not require specific tool qualification methods to be carried out. For software tools classified at any of the other tool confidence levels, specific methods for software tool qualification shall be applied. These specific methods are listed in ISO/DIS 26262-8, tables 2, 3, and 4 and have ASIL specific recommendations. From the authors‘ perspective, some of these methods seem to be feasible for commercial off the shelf tools only. As an example, permissible tool qualification methods for TCL2 are given in Table 2. To qualify a tool classified at TCL2 up to ASIL D, methods 1b, 1c, 1d or a suitable combination of these could be used. Tab. 2: Tool Qualification Methods for TCL2 Method A ASIL B C D 1a Increased confidence from use ++ ++ ++ ++ 1b Evaluation of the development process ++ ++ ++ ++ 1c Validation of the software tool + + + + 1d Development in compliance with a safety standard + + + + (+ … method recommended; ++ … method highly recommended) The selected tool qualification methods to be carried out need to be documented in the STQP. 2.6 Software Tool Qualification Report (STQR) The software tool qualification reports documents the actual tool qualification, i.e. provides evidence that the tool qualification was carried out as planned. Usage constraints and malfunctions identified during the qualification, if any, shall be documented here as well. 3 Experiences with tool qualification according to ISO/DIS 26262 A practitioner’s perspective MathWorks automotive industry customers have expressed their need for compliance with the upcoming ISO 26262 standard [TMW09] and for tools qualified as per ISO 26262 in particular. In order to support this customer need, a practicable ISO 26262 tool qualification approach had to be developed and implemented. In this section the authors discuss their first hand experiences with the ISO/DIS 26262 tool qualification approach gained during the qualification of the Real-Time Workshop® Embedded Coder™ code generator and the PolySpace® Client/Server for C/C+ code verifiers from MathWorks. These qualification activities happened in 2009. 3.1 Implementation of the ISO 26262 tool qualification approach ISO 26262 allows different levels of qualification, including a self-qualification (1st party qualification). To increase confidence into the proposed approach, MathWorks decided to submit the tool qualification approach to an accredited certification body for review and approval. Due to their reputation for software tool certifications / qualifications according to 123 various standards, TÜV SÜD Automotive GmbH was chosen for the tool qualification assessment. Due to their large customer base, MathWorks supports customers developing high-integrity systems according to different standards. Tool certification packages for IEC 61508 and qualification kits for DO-178B were already productized when the ISO 26262 qualification activities were launched. So it was desirable to re-use certification / qualification approaches and artifacts developed for these other standards wherever feasible. A suitable way to leverage existing certification approaches was to add the ISO 26262 tool qualification on top of the existing IEC 61508 in-context tool certifications. These existing certifications are based on specific workflows (reference workflows) to be utilized by the applicant when using the tool for developing or verifying software for IEC 61508 applications. In the context of ISO 26262 tool qualification, these workflows can be re-used to describe and limit the intended tool use cases as well as to list available means to detect malfunctions or erroneous output of the tool. In the following, we will illustrate this approach using the Real-Time Workshop Embedded Coder code generator as an example: The reference workflow describes a workflow for application-specific verification and validation of models and generated code developed using the Simulink® modeling environment and the Real-Time Workshop Embedded Coder C code generator. The main constructive development activities as well as the corresponding verification and validation activities are summarized in Fig. 2. [Con09, CS09] provide more detailed discussions. Fig.2: Reference Workflow for Application Specific Verification and Validation of Models and Generated Code The verification and validation measures described in this reference workflow form available means to detect or prevent potential malfunctions or erroneous outputs of the code generator. This description was used to determine the tool error detection (TD) for the code generator. According to the certification report, applying the entire workflow for Application-Specific Verification and Validation of Models and Generated Code provides a high degree of confidence that potential malfunctions or erroneous output of the code generator can be detected or prevented, i.e. the tool error detection is TD1 resulting in a tool confidence level of TCL1. Tool qualification for the code generator can be claimed without carrying out additional tool qualification methods. 124 To give the user more flexibility when integrating Real-Time Workshop Embedded Coder into their development processes MathWorks also aimed at supporting use cases that only utilize a suitable subset of the reference workflow5. Assuming that the selected subset provides a medium degree of confidence to detect or prevent potential malfunctions or erroneous output of the code generator, the tool error detection is TD2 resulting in a tool confidence level of TCL2. In this case, tool qualification methods need to be selected according to Table. 2. The PolySpace verifiers for C/C++ were classified at TCL2 as well. In case of both products, a combination of the tool qualification methods (1b) Evaluation of the development process and (1c) Validation of the software tool were used. The assessment of the development process was carried out by TÜV SÜD as part of the IEC 61508 tool certification procedure. The assessment criteria were enhanced to match the ISO 26262 requirements. The software tool validation was carried out differently for the two tools. In case of PolySpace for example, existing test artifacts that were created as part of the DO-178B tool qualification kit for PolySpace were reused. For both tools, the tool classification reports, artifacts to demonstrate compliance with the documented development processes and evidence for the validation of the tools were submitted to TÜV SÜD for review. TÜV SÜD assessed the artifacts and stated their suitability to claim tool qualification in the certification reports for Real-Time Workshop Embedded Coder and PolySpace. To further support users of Real-Time Workshop Embedded Coder when claiming tool qualification, a Tool Qualification Package was created. The package contains templates for the tool qualification work products identified by ISO/DIS 26262-8 as well as evidence documenting the independent assessment by TÜV SÜD of the tool qualification measures carried out by MathWorks. In the tool qualification package, the tool qualification work products are integrated into one single document to account for the overlap and dependencies between the different work products (see section 4 for a detailed discussion of this issue). 3.2. Discussion The authors see the following issues with the tool qualification approach outlined in ISO/DIS 26262: No formal qualification credits Similar to IEC 61508, ISO/DIS 26262 has a generic requirement for tool qualification, but doesn‘t offer formal certification credits in exchange for tool qualification. This way there is little incentive for applicants to certify tools if it can be avoided. As such, it is feared that the tool classification will be dressed up to reduce or avoid tool qualification methods. Assuming a proper tool classification and qualification, one could argue that a qualified tool used in accordance with an appropriate reference workflow might provide the required confidence in the correct execution of activities automated by this tool. Following this argument, the verification activities for these automated activities defined in the standard can be reduced or eliminated. Since there is no straightforward mapping between activities/tools 5 The applicant needs to document the chosen workflow subset in a conformance demonstration template that ships with the tool qualification package. 125 and their corresponding verification activities, this will be open to interpretation until common practices have been established. No distinction between verification and development tools Unlike DO-178B and IEC 61508 Ed. 2.0, ISO/DIS 26262 does not differentiate between tools that can introduce errors (aka development tools) and tools that can only fail to detect errors (aka verification tools). Imposing the same tool qualification requirements for both classes of tools does not account for the different criticalities of these tool categories. Providing a generic reduction of the TCL for verification tools could be one means of addressing this issue. If this is not addressed properly in new versions of the standard, the authors are concerned that the tool categories are treated differently when assigning a TD level. However, this would be less transparent than a clear statement in the standard itself. Re-using the same arguments for several tools A single means to detect or prevent errors in a tool could be used in the argumentation to lower the tool confidence level for several tools. This seems to result in a lower confidence for the overall tool chain, when compared with using different means to lower the confidence levels of different tools. However, ISO/DIS 26262 does not seem to provide any guidance on how to deal with these cases of ‗double accounting‘. It would be helpful to have some kind of ‗TD/TCL arithmetic‘ that allows the determination of tool confidence and tool error detection levels when combining tools or tool chains that have been classified already. Difficulty to provide a reasonable tool classification without considering the entire tool chain The above-mentioned issue also leads to the problem that proper tool classifications and qualifications are difficult to achieve without considering the entire tool chain. This raises questions of how feasible the qualification of individual tools is in practice. Overlap between STQP and STCA There seems to be overlap or at least a strong interdependence between parts of the STQP and the STCA. The STCA seems to be prerequisite to complete the sections of the STQP that are concerned with the tool qualification methods and the required Tool Confidence Level. On the other hand, the documentation of the tool use cases and the means for detecting malfunctions or erroneous output seem to be input for the tool classification. In the final standard, the authors would like to see a clearer separation of concerns between the two documents and a suggested order in which they should be created. No established tool qualification best practices The reported ISO 26262 tool qualification activities were carried out at a time where no reference qualifications were available. The authors believe, that the definition of suitable verification and validation measures to be used in combination with a qualified tool is a means to provide practitioners with the necessary guidance to successfully utilize these tools in projects that need to comply with the requirements of ISO 26262. Until common best practices have been established, the chosen qualification approach could be used as a reference for other tool qualifications. 4 Summary and Conclusions With the advent of ISO 26262 automotive practitioners need to figure out how implement the tool qualification requirements of this standard in practice. 126 The authors reported on their experiences with one of the first (if not the first) ISO/DIS 26262 tool qualifications of commercially available production code generation and verification tools. The successful ISO/DIS 26262-8 tool qualifications of MathWorks Real-Time Workshop Embedded Coder, PolySpace Client for C/C++ and PolySpace Server for C/C++ demonstrated the feasibility of applying this functional safety standard to both development and verification tools. The author‘s believe that the definition of suitable verification and validation measures to be used in combination with the qualified tools provides practitioners with the necessary guidance to successfully apply Model-Based Design and advanced code verification tools in projects that need to comply with the requirements of ISO/DIS 26262. Appendix: ISO/DIS 26262 Tool Qualification and Work Products Tool Qualification Planning Tool Documentation Tool Classification Tool Qualification • Software Tool Qualification Plan (STQP) • Applicant, application information (incl. max. ASIL) • Tool name, tool version, tool configuration, operational environment • Tool use case(s) • Available means to detect malfunctions or erroneous output of the tool. • Maximum TCL required (TCLREQ), tool qualification methods • Software Tool Documentation (STD) • Tool overview • Available tool documentation set • Operational environment and constraints • Installation instructions • Known issues • Software Tool Classification Analysis (STCA) • Tool error detection • Tool confidence level • Tool qualification methods • Software Tool Qualification Report (STQR) • Evidence that the tool qualification has been carried out as planned • Usage constraints and malfunctions identified during the qualification (if any) Fig. 3: ISO/DIS 26262 Tool Qualification and Work Products (Overview) References [BB09] M. Beine, A. Bärwald: Einsatz zertifizierter Codegenerierungswerkzeuge in sicherheitsgerichteteten Entwicklungen. Safetronic 2009, Munich, Germany, 2009. [Con07] M. Conrad: Using Simulink® and Real-Time Workshop® Embedded Coder for IEC 61508 Applications. White Paper, Safety Users Group, 2007 www.safetyusersgroup.com/documents/AR070002/EN/AR070002.pdf [Con09] M. Conrad: Testing-based translation validation of generated code in the context of IEC 61508. Formal Methods in System Design, 2009. DOI 10.1007/s10703-009-0082-0 [CS09] M. Conrad, G. Sandmann: A Verification and Validation Workflow for IEC 61508 Applications. SAE Techn. Paper #2009-01-0271, SAE World Congress 2009 [DO-178B] RTCA/DO-178B. Software Considerations in Airborne Systems and Equipment Certification. 1992 [Glö08] T. Glötzner: IEC 61508 Certification of a Code Generator, ICSS2008 127 [HB07] V. Hilderman, T. Baghai: Avionics Certification – A complete guide to DO-178 (Software) DO-254 (Hardware). Avionics Communications Inc., VA, USA, 2007 [IEC 61508-3] IEC 61508-3:1998. Int. Standard Functional safety of electrical/ electronic/ programmable electronic safety-related systems - Part 3: Software requirements. 1998. [IEC 61508-6] IEC 61508-6:1998. Int. Standard Functional safety of electrical/ electronic/ programmable electronic safety-related systems - Part 6: Guidelines on the application of IEC 61508-2 and IEC 61508-3. 1998. [ISO/DIS 26262-8] ISO/DIS 26262-8:2009. Draft International Standard Road vehicles — Functional safety - Part 8: Supporting processes. 2009. [JG03] F. Junker, G. Glöe: Guaranteed Product Safety According to the IEC 61508 Standard. RealTimes 1/2003 [KM03] M. Kühl, K. D. Müller-Glaser: Qualitätssicherung und Zertifizierung beim Softwareentwurf sicherheitskritischer Kfz-Steuergeräte mit X-By-Wire-Technologie (Quality Assurance and Software Certification in respect to Software Construction of Safety Critical X-by-Wire Systems). Elektronik im Kraftfahrzeug, Baden-Baden, Germany 2003. VDI Berichte 1789/2003:467-475 [MBD] Model-Based Design web page. The MathWorks Inc., www.mathworks.com/applications/controldesign/description [MISRA-C] MISRA-C:2004. Guidelines for the use of the C language in critical systems. 2004. [KZ09] A. Kornecki, J. Zalewski: Certification of software for real-time safety-critical systems: state of the art. Innovations Syst Softw Eng (2009) 5:149–161 [PM99] Y. Papadopoulos, J. A. McDermid: The Potential for a Generic Approach to Certification of Safety-Critical Systems in the Transportation Sector. Journal of Reliability Engineering and System Safety 63 (1999) 47-66 [RTW-EC] Real-Time Workshop® Embedded CoderTM product page. The MathWorks Inc., www.mathworks.com/products/rtwembedded [Sau09] J. Sauler: Die ISO 26262 für Automotive kommt! Elektronikpraxis TV (in German), 2009 Part 1: www.youtube.com/watch?v=wqbNrgRcEVo Part 2: www.youtube.com/watch?v=vWkdIRINb8o [SLM09] S. Schneider, T. Lovric, P. S. Mai: The Validation Suite Approach to Safety Qualification of Tools. SAE World Congress 2009, Detroit, MI, USA, 2009. [TMW08] The MathWorks Real-Time Workshop Embedded Coder Certified By TÜV SÜD Automotive GmbH. Press Release, The MathWorks, Inc., 2008 www.mathworks.com/company/pressroom/articles/article31189.html [TMW09] The MathWorks Real-Time Workshop Embedded Coder and PolySpace Products Qualified According To ISO 26262. Press Release, The MathWorks, Inc., 2009 www.mathworks.com/company/pressroom/articles/article39270.html 128 Using Model-Based Design in an IEC 62304-Compliant Software Development Process David Hoadley, Ph.D.1 1 The MathWorks, Inc., Novi, MI, USA [email protected] 1 Introduction IEC 62304 [1] is an international standard (hereafter referred to as the Standard) that specifies software development life cycle processes to improve the safety of medical devices. It defines a series of activities and tasks that are required for medical device software engineering. We will discuss how MathWorks tools for Model-Based Design, which have been used to create high-integrity software [2-4], can be used to create control system and signal processing software in a manner compliant with the Standard. 2 Software development processes 2.1 Software design and implementation In addition to representing functional behavior, Simulink® can be used to segregate a software design into major structural components, indicate their external properties, and demonstrate the relationship among the components. One application would be to separate risk control measures into a Simulink subsystem or referenced model to more intuitively track them and potentially lower the software safety class for other parts of the software architecture. Simulink Verification and Validation™ provides a facility called the Requirements Management Interface that establishes navigable links between textual requirements and components of models. Software in safety class C (the greatest potential for harm) of the Standard requires a documented, verified detailed design for each software unit. The Simulink model or subsystem that represents each unit can be an important part of this detailed design. Additional software standards such as MAAB [5], DO-178B [6], IEC 61508 [7] and MISRA-C® [8], can facilitate validation of the unit design. Simulink Verification and Validation features automated model checks for these standards. Design validation can also include simulations of functional, requirements-derived test cases. Model coverage can be collected during this process to test the completeness of the functional test cases. Real-Time Workshop® Embedded Coder™ can transform a Simulink model into a well structured, optimized software implementation in the C or C++ languages [9]. 129 2.2 Software unit verification Test scenarios created to perform functional detailed design verification on the software unit’s Simulink model can be used and augmented to perform implementation functional unit verification. Generated code can be compiled on the host, or the computer that the developer is using to design and create software, and invoked as an S-Function in a test harness model for direct model to code comparison (so called software-in-the-loop or SIL testing). In addition, it is possible to perform such tests on target-compiled code via the Embedded IDE Link™ product. This processor-in-the-loop (PIL) technique can be used to help verify that the executable software has the same behavior as the Simulink model when being executed as if part of the final device. Code coverage can be captured during testing to demonstrate that no unintended functionality was introduced. 3 Software risk management Model-Based Design supports software risk management primarily by the aforementioned capability to link requirements to model elements. This link and Simulink Verification and Validation’s Requirements Report allows one to trace from a documented hazard to control measures in the model (design) to the implementation of these measures in a generated software item. The traceability extends to the particular lines of code via comments, and is navigable via the code generation HTML Report and Simulink/Real-Time Workshop’s Navigate to Code feature. 4 Software configuration management The models and data created as part of the software engineering process must be identified and managed along with the resulting software items. Some typical artifacts that may be created during development activities include Simulink models, MATLAB scripts and functions, data dictionaries, generated production code, S-Functions and other user block libraries, simulation input data (test vectors) and results, and generated documentation such as design documents and test results [10]. 5 Summary Model-Based Design can be effective in an IEC 62304-compliant software development process. Links are supported between process artifacts (such as requirements documents) and models, allowing the relationship from requirement to design to implementation to remain strong. See Figure 1 for some common usage scenarios of the tools and the documentation artifacts that they can produce. 130 Figure 1 - Applicability of Model-Based Design Tools for IEC 62304-Compliant Software Development References IEC 62304, “Medical Device Software – Software Life Cycle Processes”, International Electrotechnical Commission, Edition 1.0b, 2006 2. “Medrad Ensures Safety of MRI Vascular Injection Pump Using MathWorks Tools”, 2004, http://www.mathworks.com/company/user_stories/userstory6313.html 3. “Alstom Generates Production Code for Safety-Critical Power Converter Control Systems”, 2005, http://www.mathworks.com/company/user_stories/userstory10591.html 4. “Achieving Six Sigma Software Quality Through the Use of Automatic Code Generation”, Bill Potter (Honeywell International), 2005, http://www.mathworks.com/programs/techkits/pcg_tech_kits.html 5. “Control Algorithm Modeling Guidelines Using MATLAB, Simulink, and Stateflow”, MathWorks Automotive Advisory Board - Version 2.1, 2007 6. “Software Considerations in Airborne Systems and Equipment Certification”, RTCA/DO178B, RTCA Inc., 1992 7. IEC 61508-3:1998. Int. Standard Functional safety of electrical/ electronic/ programmable electronic safety-related systems - Part 3: Software requirements. 1998 8. MISRA-C:2004. The Motor Industry Software Reliability Association: Guidelines for the use of the C language in critical systems, 2004 9. “Certify embedded systems developed using Simulink and PolySpace products to IEC 61508 and ISO 26262”, http://www.mathworks.com/products/iec-61508/ 10. “Configuration Management of the Model-Based Design Process”, Gavin Walker (MathWorks), Jonathan Friedman (MathWorks), and Rob Aberg (MathWorks), Proceedings of the Society of Automotive Engineers World Congress 2007 (2007-01-1775) 1. 131 Complete and Virtual System Models for System Development Gert Döhmen, Dietmar Sander, Andreas Lehmann Airbus Operations GmbH Kreetslag 10 21129 Hamburg [email protected] [email protected] Abstract: The paper presents a novel approach on virtual system development resulting from the EU-project SPEEDS on Speculative and Exploratory Design in Systems Engineering. This project aims to define the new generation of end-to-end methodologies, processes and supporting tools for embedded system design. The results of the project will enable European systems industry to evolve from modelbased design of hardware/software systems, towards integrated component-based construction of complete and virtual system models. 1 Component-based design using HRC SPEEDS (cf. [S08]) is a European Union 6th Framework IST Project in Embedded Systems Development. Its objectives include to enable component-based construction of complete virtual system models by commercial of the shelf tools, allowing early analysis of non-functional design constraints, virtual system integration and the new concept of hosted simulation. While focusing here on more dedicated results of interoperability, SPEEDS project provides an appropriate Heterogeneous Rich Component model – called HRC – which is (1) expressive enough to cover the complete development cycle from high-level specifications to design models and which (2) addresses both functional and non-functional aspects (cf. [Jo08]). HRCs are characterized by formal contracts attached to model components allowing various analysis techniques to validate a design already in early design stages. HRC-based modelling extends the conventional component-based modelling techniques by providing a unique, multi-dimensional framework to be used in all development phases. Such dimensions could be e.g. architectural, functional, or safety viewpoints. 132 In addition to traditional static interfaces that only define the interaction points of components, richer information is exposed on the boundaries of HRCs, in terms of contracts [En08]. Attached to a component, contracts abstract dynamic and static constraints on the component in terms of assumption/promise pairs, with the meaning that a promise in terms of a property offered by the component is guaranteed only if the environment fulfils the required assumption. At this stage the SPEEDS approach helps the designer by providing analysis techniques that allows an early virtual integration test on HRC. Based on the contracts one can check for example, whether the local contracts of system components together with the components interconnections are consistent with the global system contracts. 2 Interoperability within the Engineering Environment The system engineering process, as it is supported by the SPEEDS Engineering Environment, enables the interaction of multiple modelling and analysis tools. Since SPEEDS ensures such interoperability with the common tool independent data model – a mapping between HRC and tool specific objects is implemented into each tool adapter. The interoperability is ensured with Software infrastructure comprising an engineering bus with an underlying HRC conform repository. Since only the adapter are the top layer of the bus architecture is a tool specific implementation - lower services can be customized in the development process via most appropriate SPEEDS-enabled tools. Figure 1: Engineering Environment supporting Heterogeneous Rich Components 133 3 Architecture Design and Assessment We discuss a simple water tank example. The architecture design on two levels of abstraction is performed with Rhapsody: The top design level comprises the system entity having interfaces of the water outflow and supply. The subsystems on a lower design level comprise the physical components of a water tank, a floating sensor, an inlet valve and a controller, each represented by a HRC component with electric and fluidic interfaces. The functional behaviour – thus the implementation of components is performed with SCADE that retrieve the architecture from the repository and attach CCode to respective HRC components. The contracts are defined afterwards via an Assumption/Promise Editor to define assumptions of environmental condition – e.g. water pressure – and related promises like boundaries and timing properties of outflow. Hosted simulation checks the model completeness by executing fused C-Code that is retrieved from the repository by the DESYRE engine. As next analysis step the design target is verified so that formalized requirements in terms of contracts hold throughout a specified time period. The results of this satisfaction checking is traced back to the HRCcomponents in order to obtain – together with additional contract checking mechanisms – full feedback onto the model maturity. Since the entire modelling and analysis is performed on the common HRC-model – the seamless cross-tool operability ensures consistent and correct component based virtual design with extended semantic. Figure 2: Tools interaction via HRC Bibliography [S08] [En08] [Jo08] 134 SPEEDS White Paper. www.speeds.eu.com/downloads/SPEEDS_WhitePaper.pdf Engel, A.; Winokur, M.; Döhmen, G.; Enzmann, M.: Assumptions / Promises – Shifting the Paradigm in Systems-Engineering. In: Proc. 18th Annual Int. Symposium of INCOSE, Utrecht 2008. Josko, B.; Ma, Q.; Metzner, A.: Designing Embedded Systems using Heterogeneous Rich Components. In: Proc. 18th Annual Int. Symposium of INCOSE, Utrecht 2008.