Modellbasierte Entwicklung eingebetteter Systeme VI.

Transcrição

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 weitergefü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 softwareintensive 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/Problemgröß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 Gü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. Zusätzlich soll es möglich sein aus einer Menge von Modellen optimale Kandidaten automatisch zu bestimmen. Die Modellerstellung soll weitgehend durch semantisch-fundierte
Modelltransformationen unterstützt werden.
1 Einleitung
Die immer weiter steigende Komplexität sowie die fortschreitende Integration sicherheitsrelevanter Funktionen in eingebettete Systemen stellt hohe Anforderungen an deren Zuverlässigkeit und Ausfallsicherheit. Je nach Anwendungsdomäne (z.B. Avionik, Automobil, Bahn) sind unterschiedliche Normen und Standards verfügbar, nach denen entwickelt
werden muss, um eine notwendige Zertifizierung für ein System zu erreichen.
Traditionellen Ansätzen zur Sicherheitsanalyse wie z.B. Fehlerbaumanalyse (FTA) werden die qualitativen Sicherheitsanalysen, also die Untersuchung welche Fehlerkombinationen zu einer kritischen Situation führen können, beruhen im Wesentlichen allein auf der
Expertise des durchfü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 möglich die
Analyse automatisch mit Deduktionstechniken durchzuführen.Das führt zu präziseren und
signifikanteren Ergebnisse verglichen mit rein traditionellen Techniken.
Für die Praxis ist aber die quantitative Bewertung wesentlich wichtiger (z.B. für die Zertifizierung). Dazu muss zum Beispiel die Frage ”Wie groß ist die Wahrscheinlichkeit, dass
ein kritisches Systemversagen auftritt?” beantwortet werden. Praktisch alle bestehenden
Ansätze – sowohl traditionelle als auch modell-basierte – beantworten diese Frage, indem aus den Ergebnissen der qualitativen Analysen aufbauend Abschätzungen bestimmt
werden. Dies bringt eine Reihe von Unsicherheiten und Schwierigkeiten mit sich (z.B.
common cause Fehler, stochastische Abhängigkeiten im Umgebungsverhalten, etc.).
Dank neuester Entwicklungen auf dem Gebiet der probabilistischen Modellprüfer [KNP05,
aPKaOaSaZ07, KKZ05] wird es möglich diese Problematik zu umgehen. Stochastische
Zusammenhänge können jetzt direkt funktionalen Systemmodellen hinzugefügt werden.
Aus diesen Modellen können dann stochastische Bewertungen des Systems abgeleitet werden. Dies führt zu wesentlich präziseren Wahrscheinlichkeitsabschätzungen und einem
7
weniger fehleranfälligen Analyseprozess.
Erste Ansätze hierzu existieren bereits [GCW07, BCK+ 09]. Diese Ansätze sind aber sehr
technologielasitg. In ProMoSA wird wesentlich stärker als in diesen Ansätzen auf die korrekte probabilistische Modellierung von Fehl- und Umweltverhalten eingegangen. Dies
geschieht durch eine möglichst enge Einbindung in den Systementwurfsprozess. Als absolute Neuerung soll versucht werden statt vollständiger spezifizierter Modelle nur unterspezifizierte Modelle zu verwenden. Aus der Menge all dieser Modelle sollen dann optimale Modelle bezüglich verschiedener Metriken durch Optimierungsverfahren gefunden
werden. Dies ist von großer Relevanz für die Praxis. Denn sehr häufig ist es beim Systementwurf schwierig bestimmte Parameter oder Konfigurationen gut abzuschä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 gelöst werden.
2 Überblick
Ziel des Projekts ist es neue, modell-basierte Techniken zur quantitativen Sicherheitsanalyse zu entwickeln. Grundlage dafür bilden aktuelle Fortschritte aus den Gebieten Modelltransformationen, probabilistische Analysewerkzeuge und numerische Schätz- und Optimierungsverfahren. Modelltransformationen werden verwendet, um die im Entwurfsprozess vorhandenen Modelle zu erweitern und in die Sprachen der Analysewerkzeuge zu
übersetzen. Die Berechnungen der Wahrscheinlichkeitswerte werden mit automatischen,
probabilistischen Analysewerkzeugen durchgeführt. Mit Hilfe von Schätz- und Optimierungsverfahren können Entscheidungshilfen und aussagekräftige Bewertungen abgegeben
werden.
In dem vorgeschlagenen Projekt sollen zwei wesentliche Verbesserungen erreicht werden,
die weit ü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 für die Sicherheitsanalyse verwendbare Modelle generiert werden1. Dies macht die Analyse wesentlich effizienter in
der Durchführung. Zusätzlich wird die Aussagekraft gestärkt, da die Adä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 für ein gegebenes System abzuleiten, soll
durch Vorgabe von Sicherheitszielen aus einer ganzen Klasse möglicher Systeme mittels
Optimierung das beste Design bestimmt werden. Als Konsequenz müsste man dann eher
von einem Sicherheitsdesignprozess sprechen als von Sicherheitsanalyse. Für dieses Ziel
sind auch wesentliche Fortschritte bei der modell-basierten, stochastischen Analyse notwendig. Bisher gibt es nur wenige Ansätze, die quantitative Werte direkt undmathematisch
fundiert aus funktionalen Modellen ableiten.
1 Natürlich
8
ist bei diesen Verfeinerungen noch zusätzliches Wissen notwendig.
Der Nutzen des Gesamtprojekt lä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 für eine Bahnstrecke mit Ausweichspur, die zum Ü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 genügt es sich hier auf den Fall, dass sich zwei Züge aus einer Richtung
nähern zu beschrä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 Achszähler im Boden versenkt. Diese
können detektieren, ob, in welcher Richtung und wieviele Achsen diese Kontrollpunkte
passieren. Diese Information wird zyklisch dem Kontrollsystem der Ausweichstrecke mitgeteilt2 . Zusätzlich melden sich die Züge per Funk für eine Durchfahrt an. Jeder Zug teilt
dazu zyklisch seine Position und Geschwindigkeitmit. Zur Positionsbestimmung verfügen
die Züge einerseits über GPS und zusätzlich über ein Odometer, mit dem die aktuelle
Position aus früheren Daten und der Geschwindigkeit bestimmt werden kann.
Für ein effizientes überholen ist es notwendig, dass möglichst geringe Geschwindigkeitsveränderungen durchzuführen sind. Das bedeutet, dass beide Zügemöglichst wenig Bremsen und Beschleunigen müssen und eventuelle Zeitverzögerungen gering bleiben. Dazu
müssen virtuelle Bremswege, Umschaltzeiten der Weichen, Beschleunigungskoeffizienten
etc. mit berücksichtigt werden. Wichtig ist, dass trotzdem Kollisionen sicher vermieden
werden und auch die Weichen rechtzeitig Ihre Schaltvorgänge abschließen können (Vermeiden von Entgleisen). Dies versucht man in der Regel durch das Einführen von entsprechenden Sicherheitszuschlägen zu erreichen. ü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. Zusätzlich soll es möglich sein aus einer
Menge von Modellen optimale Kandidaten automatisch zu bestimmen. Die Modellerstellung soll weitgehend durch semantisch-fundierte Modelltransformationen unterstützt werden.
Am obigen Beispiel wü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
mö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 Züge implementieren könnte.
9
wareentwurfs. Dieses wird dann schrittweise erweitert. In diesem Modell sind in der Regel noch Freiheitsgrade vorhanden. So könnten beispielsweise Sicherheitszuschläge oder
Mindestabstände noch offen gelassen werden. Im nächsten Schritt wird dieses Modell um
stochastische Zusammenhänge erweitert. Hier würden beispielsweise für Fehlermodi die
entsprechenden Fehlerraten adäquat hinzugefügt. Resultat ist ein stochastisches Modell
bzw. genauer gesagt eine Menge von Modellen. Einzelne Modelle können durch Wahl der
freien Parameter erzeugt werden und modell-basiert analysiert werden. Bei dieser Art von
Analyse werden z.B. stochastische Abhängigkeiten (z.B. mehrfacher Ausfall der Kommunikation) genauso wie implizite Abhängigkeiten (z.B. müssen für ein korrektes überholen
in manchen Situationen beide Weichen gleichzeitig bei Anderen zeitversetzt geschaltet
werden). Optimale Lösungen können mit genetischen Algorithmen innerhalb dieses Modellraums bestimmt werden. Optimal kann in diesem Zusammenhang entweder direkt ein
Sicherheitseigenschaft sein oder auch eine extern berechnet Größe (wie beispielsweise
Kosten oder Performanz). Die geplanten Optimierungsverfahren sollen auch in der Lage
sein mit gegenläufigen Zielen umgehen zu können. In diesem Fall werden keine Optima
bestimmt, sondern lediglich die besten Kompromisse (mathematisch entspricht dies den
Pareto-Mengen). Im obigen Beispiel kö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 wäre dies etwa die Notwendigkeit einer effizienten Überholmöglichkeit und die einzuhaltenden Sicherheitsziele. Aus diesen Anforderungen wird
eine erste grobe Idee des Systems erstellt. Also beispielsweise die Lösung mit einer begrenzten Nebenstrecke sowie dynamischen, von der Geschwindigkeit der Züge abhängenden Sperrbereichen (II). In diesem Grobentwurf sind noch viele Details offen, wie beispielsweise Sicherheitszuschläge, verwendete Weichen (mit zugehö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 Ausfälle und deren Verteilungsfunktionen sowie Spezifikationen
10
der Umgebung). In der Regel findet in diesem Schritt auch eine Verfeinerung der Kontrollogik statt. Insgesamt erhä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 enthält eine Reihe freier Parameter, die noch bestimmt werden
müssen. Im Beispiel oben würden in diesem Schritt Verhaltensmodelle der Züge und auch
probabilistische Ausfallmodelle der Sensoren und Aktuatoren zum rein funktionalen Modell der Software hinzukommen.
Durch Wahl der Parameter können jederzeit Modellinstanzen gebildetwerden. Jede einzelne Instanz beschreibt ein semantisch-fundiertes Modell eines möglichen Systems. Dieses
Modell kann zurmodell-basierten Analyse verwendetwerden (beispielsweisemit probabilistischem model checking). Dazu wird die Modellinstanz automatisch in Eingabesprache
eines entsprechenden Tools ü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 mö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. zusätzlicher Energieverbrauch)3.
Aufgrund dieser Bewertung wird dann mit Optimierungsverfahren entschieden, ob eine
weitere Verbesserung möglich ist oder nicht. Technisch wird dies durch Mehrkriterienoptimierung umgesetzt. Unabhängig vom gewählten Verfahren ist hier praktisch immer
mehrmaliges Auswerten verschiedener Modellinstanzen notwendig. Diese Iteration kann
aber vollautomatisch erfolgen (IV). Im Beispiel würde das System mit verschiedenen Sicherheitszuschlägen und Maximalgeschwindigkeiten jeweils analysiert und bewertet, bis
eine gute Lösung gefunden ist.
In einem abschließenden Schritt muss der Ingenieur entscheiden, ob das System den erforderlichen Qualitätskriterien genügt. Falls ja kann man im Entwurfsprozess fortschreiten,
falls nein sind Änderungen am Grobkonzept notwendig. Dies erfordert in der Regel eine
zusätzliche, kreative Ingenieurtätigkeit4.
4 Zusammenfassung und Ausblick
Das aktuelle Projekt geht weit über bestehende Ansätze hinaus, da es zum Ziel hat auf formalen Methoden beruhende Sicherheitsanalysetechniken direkt in den Systementwurfsprozess zu integrieren. Dazu sind neben den technischen Hürden (z.B. semantik-erhaltende
Modelltransformationen) auch wesentliche Beiträ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 wäre natürlich ein alle Aspekte umfassendes Gesamtmodell wünschenswert.
Das ist aber leider in der Praxis nicht mit vertretbarem Aufwand realisierbar.
4 Man könnte auch versuchen diese Iteration beispielsweise durch genetische Algorithmen zu unterstützen.
Das resultierende Problem ist dann aber ähnlich schwierig wie das Problem der Programmsynthese und bringt
beträ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 möglich.
11
onswerkzeuge. Die einzelnen zugrundeliegenden Formalismen weisen größere semantische Unterschiede auf (z.B. zeitdiskrete vs. zeitkontinuierliche Ansä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. Für die Blackbox-Optimierung scheinen genetische Algorithmen das Mittel
der Wahl. Diese benötigen aber in der Regel sehr viele Funktionsauswertungen. Deshalb
müssen wahrscheinlich stochastische Schä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 andMarië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 Einschränkungen an die zulä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 für Informatik, Technische Universität Mü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 für Informatik, Technische Universität Mü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 für Informatik, Technische Universität Mü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 Grönniger, and Bernhard Rumpe. System Model Semantics
of Class Diagrams. Informatik-Bericht 2008-05, Technische Universität Braunschweig,
2008.
Marı́a V. Cengarle, Hans Grönniger, and Bernhard Rumpe. System Model Semantics of
Statecharts. Informatik-Bericht 2008-04, Technische Universität Braunschweig, 2008.
Constanze Deiters and Sebastian Herold. Konformität zwischen Code und Architektur
- logikbasierte Überprü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 Grö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 Grönniger, Holger Krahn, Bernhard Rumpe, Martin Schindler, and Steven Vö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 Grö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 Völkel. Mit Sprachbaukästen zur
schnelleren Softwareentwicklung: Domänenspezifische Sprachen modular entwickeln.
Objektspektrum, 4:42–47, 2008.
[KRV08b] Holger Krahn, Bernhard Rumpe, and Steven Vö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 Universität Mü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 Universität München
{sommerst,knoll}@in.tum.de
Abstract: Bei der Entwicklung von komponentenbasierten Systemen werden in der
Regel Middlewarearchitekturen bzw. Laufzeitsysteme zur Verknü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 unterstü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 Erhöhung der Wiederverwendbarkeit werden verteilte, eingebettete Systeme hä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. Während im Bereich von verteilten Standard-IT-Systemen überwiegend
generische Ansätze, z.B. basierend auf CORBA, eingesetzt werden, dominieren im Bereich von eingebetteten, verteilten Systemen domänenspezifische Laufzeitsysteme [SV06],
um den besonderen Anforderungen, z.B. in Bezug auf Ressourceneinschrä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 können nicht-funktionale Aspekte, wie Ausfü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 für das Laufzeitsystem entwickeln generische Architekturen, die durch die
Entwicklungswerkzeuge automatisiert an die Anwendung angepasst werden können. Komponentenentwickler stellen sowohl Software-, als auch Hardwarekomponenten zur Verfüg-
23
ung und müssen die Einbindung in die Laufzeitsystemarchitektur durch Bereitstellung entsprechender Schnittstellen bei Softwarekomponenten oder durch Entwicklung von passender Firmware bei Hardwarekomponenten sicherstellen. Anwendungsentwickler wählen
schließlich werkzeugunterstützt die einzelnen Komponenten zur Realisierung der Anwendung aus und spezifizieren die zu berücksichtigenden nicht-funktionalen Anforderungen.
In den derzeit verfügbaren Entwicklungswerkzeugen wird lediglich der Anwendungsentwickler bei der Erstellung durch modellgetriebene Werkzeuge unterstützt. Im Rahmen
dieser Arbeit wollen wir eine weitergehende Unterstü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 erläutert die Ergebnisse eines ersten Prototyps.
Zunächst werden in Abschnitt 2 die zur Untersuchung verwendete Domäne erläutert und
der Ansatz motiviert. Abschnitt 3 beschreibt die vorgeschlagene Vorgehensweise. Abschnitt 4 fasst den Beitrag zusammen und gibt einen Ausblick über die nächsten geplanten
Schritte.
2
Beispiel für Anwendungsdomäne: Verteilte Sensor-Aktor-Systeme
Im Rahmen des SOA Projektes1 wurde ein modellgetriebenes Entwicklungswerkzeug für verteilte Sensor-Aktor-Systeme entwickelt. Diese Systeme zeichnen sich durch die hohe Heterogenitä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 unterstü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 Heterogenität fü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 hardwareunabhängigen Berechnungsfunktion sein können. Diese Softwaredienste können durch das im Rahmen des
Projektes entstandene Entwicklungswerkzeug vom Endanwender ausgewählt, den entsprechenden Hardwareknoten zugewiesen und konfiguriert werden. Die für die Ausfü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
häufig erweitert werden. Beispiele hierfür sind das Hinzufügen neuer Dienste zur Umsetzung von Regelungsalgorithmen oder Kontrolllogiken, aber auch die Unterstützung neuer
Hardwareplattformen. Der Aufwand fü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 Ethernetunterstützung erweitert. Hierzu musste das Metamodell um Komponenten mit
Ethernetunterstützung erweitert werden und die notwendigen Attribute definiert werden.
Dabei erfolgte jedoch keine Trennung in die grundsätzliche Kommunikationsfä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 erhöhte sich der Aufwand bei der Beschreibung
von weiteren Komponenten mit evtl. ähnlichen/gleichen Fähigkeiten. Zudem erschwerte
diese Praxis die Wiederverwendung von Vorlagen für die Codegenerierung für Komponenten mit gleichen Funktionalitäten.
Die Ähnlichkeit der Problemstellung zwischen Anwendungsentwicklung und Entwicklung des Modellierungs- und Codegenerierungswerkzeuges motiviert einen mehrstufigen
Ansatz. Das Konzept der domänenspezifischen Entwicklungswerkzeuge zur Entwicklung
von Systemen kann ebenso auf die Entwicklung von domänenspezifischen Entwicklungswerkzeugen angewandt werden. Das Ergebnis ist ein mehrstufiger Entwicklungsansatz,
der im nächsten Abschnitt näher erläutert wird.
3
Ansatz
Ziel des in diesem Beitrag vorgestellten Ansatzes ist die optimale Unterstützung der Entwickler durch einen modellgetriebenen, mehrstufigen Ansatz. Die Grundidee leitet sich
dabei von dem allgemeinen Ansatz domänenspezifischer
Sprachen bezü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
für die nächste Phase generiert.
describes
instanceof
M3: Meta-Metamodel
describes
instanceof
M2: Metamodel
describes
instanceof
M1: Model
describes
instanceof
M0: Instances
Die Stärken des modellgetriebenen Ansatzes mittels Abbildung 2: Modellhierardomänenspezifischer Sprachen ergeben sich insbesondere chie [SV06]
bei der Entwicklung von gleichartigen Systemen. Dies ist
nicht nur auf das eigentliche Endsystem beschränkt, sondern
gilt auch für die zu erstellenden Entwicklungswerkzeuge. Im Fall von komponentenbasierten Systemen kann somit der Ansatz nicht nur für die Erstellung der Endanwendung
durch Zusammenfügen der Komponenten, sondern auch schon auf die Entwicklung von
ä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 unterstützt:
1. Spezifikation der für das Laufzeitsystem relevanten Informationen durch den Laufzeitsystemexperten
2. Spezifikation der zur Verfügung stehenden Komponenten durch Komponentenhersteller
3. Spezifikation der Anwendung durch den Anwendungsentwickler
Im Folgenden werden diese einzelnen Phasen näher erläutert.
Modellierung der zur Beschreibung der Komponenten benötigten Attribute In der
ersten Phase des Ansatzes können die Laufzeitsystemexperten spezifizieren, welche Informationen benötigt werden, um Komponenten zu beschreiben. Auf Basis der Modelle der
ersten Phase können Regeln, Analysen und Schritte zur Codegenerierung festgelegt werden. Mittels komponentenunspezifischen Regeln kö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 für das Laufzeitsystem beschrieben. Dieser
Code umfasst alle Funktionalitä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 benötigen Attribute. Durch diese allgemeine
Spezifikation von Fähigkeiten kann die Realisierung auf Laufzeitsystemebene unabhängig
von den konkreten später verwendeten Komponenten auf Basis der Funktionalitäten und
deren Attributeigenschaften erfolgen. So kann beispielsweise einfach geprüft werden, ob
die vorhandene Bandbreite (spezifiziert im Attribut Speed von Ethernet) den Anforderungen der Anwendungen Rechnung trägt. Durch die sehr grundlegende Definition der
26
Abbildung 4: Beispielmodell der 1. Phase
Beschreibung von Komponenten kann sichergestellt werden, dass das Metamodell ähnlich
den Metamodell von UML-Klassendiagrammen sehr selten oder nie verändert wird. Das
Metamodell der ersten Phase ist somit die Basis für die weiteren Schritte.
Ein Ausschnitt des fü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 Funktionalitä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 unterstützten Funktionen und Attribute berücksichtigen und diese modellieren. Das spätere Hinzufügen von neuartigen Fähigkeiten oder
zusätzlichen Attributen kann bei Bedarf erfolgen. Somit wird der Aufwand der ersten Modellierung reduziert, ohne eine spätere Erweiterbarkeit zu erschweren. Eine nachträgliche
Erweiterung des Metamodells führt auch nicht zur Inkompatiblität alter Modelle der späteren Phasen: werden neue Fähigkeiten hinzugefügt, so sind die weiteren Modelle ohne
Einschränkung nutzbar. Im Falle von zusätzlichen Attributen können Default-Werte benutzt werden, die sicherstellen, dass sich die Codegenerierung bei auf alten Modellen basierten Systemen nicht ändert.
Ein ähnlicher Ansatz ist auch für die Softwarekomponenten möglich und wurde im Rahmen des Projektes umgesetzt.
Modellierung der verfügbaren Komponenten Komponentenhersteller können in der
zweiten Phase ihre bereitgestellten Komponenten beschreiben und die Codegenerierungsfunktionalität in Bezug auf ihre Komponenten ergänzen. Hierzu wird zunä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 lässt sich der Zusammenhang mit den Eingabedaten aus dem Modell der ersten Phase leicht erkennen aus Objekten sind Klassen entstanden. Diese kö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 können Hersteller Werte für
unveränderbare Attribute festlegen (z.B. CPU-Geschwindigkeit), mögliche Attributwerte
einschränken (Begrenzung der Geschwindigkeit auf die von der Hardwarekomponente unterstützten Werte), Standardwerte für Attribute auswählen oder die Konfiguration für die
nachfolgende Phase offen lassen (z.B. IP-Adresse).
Abbildung 6 zeigt einen Ausschnitt des Modells der zweiten Phase fü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 können die Komponentenhersteller die Generierungsschritte des komponentenspezifischen Codes beschreiben. Dieser Code umfasst unter anderem die eigentliche
Funktionalität der Komponente und Hardwareabstraktionsschichten.
Das in der zweiten Phase entstehende Modell wird aufgrund der hohen Vielfalt verschiede-
28
ner Komponenten regelmäßig erweitert. Von dieser Erweiterung sind jedoch die bestenden
Komponenten nicht betroffen, insofern sind alte Modelle basierend auf den ursprünglichen
Metamodellen weiterhin kompatibel und von den Änderungen nicht betroffen. Ein weiterer Vorteil des Ansatzes ist die Möglichkeit, das für die Generierung notwendige Wissen
zu kapseln. Dadurch kann der Schutz von geistigem Eigentum sichergestellt werden2 .
Der vorgestellte Ansatz ist ebenfalls für die Beschreibung der verfügbaren Softwarekomponenten umgesetzt.
Modellierung der Anwendung Die dritte Phase erlaubt schließlich dem Anwendungsersteller die Auswahl und Zusammenstellung der einzelnen Komponenten für die Anwendung ähnlich einem Baukastensystem, sowie deren abschließende Konfiguration. Die Festlegung von Werten und die Einschränkung der Werte für einzelne Attribute in der zweiten
Phase fü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 gehö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 berücksichtigen zu mü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 zugehöriges Modell ist in Abbildung 8 zu sehen. Die modellierte Anwendung besteht
dabei aus zwei PC-Modulen mit jeweils einer Etherneterweiterungskarte, welche für die
2 Die
Unterstützung der Kapselung ist derzeit noch nicht implementiert
29
Abbildung 7: Generisches und konkretes Metamodell der 3. Phase
spätere Anwendung geeignet konfiguriert werden. Auf Basis des Modells der dritten Phase wird die Codegenerierung ausgefü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 können.
Implementierung Die Implementierung des Ansatzes erfolgte auf Basis des Eclipse
Modeling Frameworks (EMF) [SBPM08]. Dieses stellt eine äquivalente Implementierung
des Essential Meta Object Facility (EMOF) [OMG06] der Object Management Group
30
(OMG) dar und bietet eine reichhaltige Anzahl an Möglichkeiten zur Introspektie. Die
Umsetzung der Modell-zu-Metamodell-Transformationen gründet dabei auf manueller Implementierung der Werkzeuganforderungen. Während die Generierung des Metamodells
der zweiten Phase zielführend umzusetzen war, war die Generierung des dritten Metamodells deutlich erschwert. Dies ist darauf zurückzuführen, dass für diese Generierung
neben dem Modell der zweiten Phase auch Informationen des Modells der ersten Phase
notwendig waren, um Strukturinformationen ü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 gegenwärtige Umsetzung bezieht sich dabei auf die Generierung der
Metamodelle. Die Einbindung der Codegenerierung und Modellanalyse aus dem SOAAnsatz ist der nä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 möglich.
Codegenerierung Der vorgestellte Ansatz bringt auch im Bereich der Codegenerierung
einige Veränderungen mit sich. Grob lässt sich die Codegenerierung in zwei Bereiche aufteilen. Der erste Bereich beschäftigt sich mit der Generierung und Anpassung der Komponententreiber an die Anforderungen der Anwendung. Im zweiten Bereich wird schließlich das zugehörige Laufzeitsystem erstellt, welches als Container für die zuvor erstellten
Komponententreiber (Komponenten) dient. Die Interoperabilität der beiden Codegenerierungen wird dabei über die Einhaltung vordefinierter Schnittstellen sichergestellt. Für die
einzelnen Codegenerierungen sind unterschiedliche Personenkreise zuständig. So wird
die Generierung der Komponententreiber von den Komponentenherstellern der jeweiligen Komponenten übernommen, wä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 Systeminteroperabilität wird dabei durch das Entwicklungswerkzeug übernommen.
In der aktuellen Umsetzung ist der hier vorgestellte Ansatz der Codegenerierung noch
nicht vollstä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 Unterstützung der Anwendungsentwickler, steht dabei auch die Unterstützung von Laufzeitsystemexperten und Kom-
31
ponentenherstellern im Vordergrund. Domänenspezifische Entwicklungswerkzeuge werden heute insbesondere eingesetzt, um ähnliche Systeme vereinfacht zu entwickeln. Dabei
werden die Gemeinsamkeiten der Systeme als Domänenkonzepte im Modellierungswerkzeug und dem Codegenerator gekapselt. Dieser Ansatz wird jedoch heute überwiegend
für die Entwicklung von Systemen verwendet, nicht aber für die vom Entwicklungswerkzeug benötigten Metamodelle. Im Rahmen des vorgestellten Ansatzes wurde aufgezeigt,
dass dies jedoch möglich und im Bereich von komponentenbasierten Systemen auch zu
wesentlichen Verbesserungen fü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 zunächst auf der Modellierungsebene getestet. Die bisherigen Ergebnisse
deuten auf eine wesentlich vereinfachte Erweiterbarkeit des Systems hin. In den nä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, Jö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 Quirós, Ulrich Epple
Lehrstuhl fü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,
Dü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 Münnemann, R Bö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]
Jö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 Quiró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. Quiró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 Quiró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 Quirós. Model-based Decentralised Automatic Management
of Product Flow Paths in Processing Plants. PhD thesis, submitted to
RWTH Aachen University, 2009.
[SMU08]
Schmitz St., Schlütter M., and Epple U. R&I - Grundlage durchgängigen
Engineerings. In VDI-Berichte 2032, Automation 2008: Lösungen für die
Zukunft, pages Kurzfassung: S. 55–59, Langfassung: CD, Dü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. Mü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 Lämmel and Jö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 Schätz and Christian Pfaller
fortiss GmbH
Guerickestr. 25, 80805 Mü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 Schä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 Schäfer
Fachgebiet Softwaretechnik, 1 s-lab (Software Quality Lab), Heinz Nixdorf Institut
Universitä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
Funktionalitäten in Fahrzeugen werden zunehmend ü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
durchgä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 kostengünstiger erfolgen. Die Systeme werden
∗ Diese Arbeit ist im Sonderforschungsbereich 614 - Selbstoptimierende Systeme des Maschinenbaus“, Uni”
versität Paderborn, entstanden und wurde auf seine Veranlssung unter Verwendung der ihm von der Deutschen
Forschungsgemeinschaft zur Verfügung gestellten Mittel veröffentlicht.
77
zudem oft in sicherheitskritischen Bereichen eingesetzt. Somit ergeben sich hohe Qualitä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 unterstützen modellbasierte Entwicklungsverfahren die effiziente Umsetzung der erhöhten Anforderungen
an den Entwicklungsprozess, welche insbesondere mit der Entwicklung sicherheitsrelevanter Funktionen einhergehen.
Mit der Einführung modellbasierter Entwicklungsverfahren ergeben sich allerdings neue
Probleme:
1. Um das volle Potential modellbasierter Entwicklungsverfahren ausschöpfen zu
können, müssen diese durchgängig eingeführt werden. Dies bedeutet aber auch, dass
bestehende (traditionell entwickelte) Altkomponenten integriert werden müssen. Eine Neuentwicklung wird nicht angestrebt, da die Wiederverwendung von (Software)
Altsystemen (Altkomponenten) zum einen die Möglichkeit bietet die Entwicklung
der Systeme zu beschleunigen. Zum anderen wird durch die Verwendung von Altkomponenten auf bewährte Qualität zurückgegriffen. Es muss also die Frage nach
der geeigneten Migrationsstrategie fü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 müssen von den Automobilherstellern
(OEM) oder deren Zulieferern auf den einzelnen Steuergerä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 Rückgewinnung des Modells einer
Altkomponente (allein) aus dem vorhandenen ausführbaren (kompilierten) Quellcode und
den definierten Schnittstellen das Thema dieses Papiers.
In [GHH08a] haben wir bereits einen Ansatz vorgestellt, der im Vergleich zu bisherigen
Ansätzen (z. B. [HNS03]) eine Integration unter Berücksichtigung von Sicherheitseigenschaften unterstützt. Voraussetzung für diesen Ansatz ist, dass die Altkomponenten an ihrer Schnittstelle eine Beobachtung des aktuellen Zustands des Kommunikationsverhaltens
ermöglicht. Wie wir in [GHH08a] gezeigt haben, erfüllt dieser Ansatz die Anforderungen, um Anwendungen des RailCab Projektes2 und Anwendungen, die den AUTOSARStandard erfüllen, zu analysieren. Unsere Erfahrungen im industriellen Kontext haben allerdings gezeigt, dass darüber hinaus häufig Anwendungen existieren, die nur Informationen über die einund ausgehenden Nachrichten beschreiben oder zusätzlich den Quellcode
zur Verfügung stellen.
Wir stellen daher einen Ansatz vor, der fü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 ermöglichen wird (iterativ) das Modell des Verhaltens für die Integration gelernt
und überprüft, ob es den Sicherheitsanforderungen standhält. Der Kontext, das Protokollverhalten der Komponente, mit dem die Altkomponente interagieren soll, wird in der
Analyse berücksichtigt, um nur die relevanten Interaktionen zu betrachten. Fü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
beschäftigen. Im Folgenden werden die entsprechenden Ansätze vorgestellt und gegenüber
dem hier vorgestellten Ansatz abgegrenzt. Am bekanntesten ist die Technik der regulären
Inferenz, die als nächstes vorgestellt wird.
Reguläre Inferenz - Black-box Integration
Regulä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 regulä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 Zugehörigkeitsanfragen
(membership queries) an den Lehrer erlernt. Es wird überprüft, ob eine Zeichenkette w ∈ Σ∗ in L(M ) enthalten ist. Weiterhin ist zum Erlernen der Sprache noch eine
Ä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 Zugehörigkeitsanfragen
und nutzt die Antworten, um einen vermuteten Automaten (Kandidat) zu erstellen. Ist
der Kandidat stabil (verändert sich nicht gegenüber vorherigen Iterationen), wird eine
Ä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 zurückgegeben, um A zurückzuweisen. In diesem Fall werden weitere Zugehörigkeitsanfragen gestellt, bis der nächste mögliche Automat erstellt ist und so weiter.
Algorithmus von Angluin Der bekannteste regulä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 für die Reihen, während die Suffixe die Spalten der Tabelle
indizieren. Ein Prefix ist eine Zeichenkette, der zu einem Zustand des Systems führt. Eine
Suffix wird genutzt, um die Prefixe auseinanderzuhalten, die zu verschiedenen Zuständen
führen. Die Komplexität des L∗ Algorithmus ist wie folgt. Die obere Grenze für die An3 Darüber hinaus ist es möglich die relevanten Information für unser iteratives Lern/-Beweisverfahren
[GHH08a] aus dem Source Code zu extrahieren.
79
zahl der Äquivalenzanfragen beträgt n (n ist die Anzahl der Zustände von M). Die obere
Grenze für die Anzahl der Zugehörigkeitsanfragen beträgt O(|Σ|n2 m).
Domänenspezifische Ansätze Es existieren verschiedene Ansätze, die auf dem Lernalgorithmus von Angluin basieren. Einige Ansätze, wie in [HNS03, Ber06] beschrieben,
erweitern Angluins Algorithmus, zur Verbesserung der Laufzeit für bestimmte Applikationen oder Domänen. Diese Ansätze nutzen Angluin’s Algorithmus und fügen z.B.
zusätzliche Technologien, wie Testen und Verifikation hinzu. Hierdurch werden primär
die Zugehörigkeitsanfragen reduziert. Eine Technik, um eine Black-Box mittels Model
Checking zu überprüfen, wird von Peled und anderen in [PVY99] vorgestellt.
Äquivalenzüberprüfungen Die beschriebenen Lernverfahren benötigen ein Orakel,
welches überprüft, ob der erlernte Kandidat äquivalent zu der Black-Box ist. Ist dies nicht
der Fall, wird ein Gegenbeispiel angegeben. Konformitätstest ist ein weitverbreiteter Ansatz, um die Äquivalenz zu überprüfen. Konformitätstests bieten ein systematisches Verfahren an, um Antworten für Äquivalenzanfragen zu ermitteln. [PVY99] oder [Ber06] sind
z.B. Lernansätze die hierauf basieren. Wie auch diese Ansätze, basieren die meisten Konformitätstest-Ansätze auf dem Verfahren von Vasilevskii und Chow [Vas73, Cho78]. Entsprechend Vasilevskii existiert eine obere Grenze für die Gesamtlänge einer Testsequenz.
Diese ist O(k 2 l|Σ|l−k+1 ). Daher besteht eine exponentielle Differenz zwischen der Anzahl der Zustände k des Systems und der Hypothese l. Eine allgemeine Annahme für den
Konformitätstest ist, dass A mindestens so viele Zustände wie M hat [BGJ+ 05].
Fazit Im Prinzip basieren die hier betrachteten Lernalgorithmen alle auf dem von
Angluin. Bis auf [PVY99], versuchen alle Ansä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. Ähnlich zu [PVY99] ist unser Black-Box-Ansatz in der Lage reale Fehler nach jedem Lernschritt zu finden. Darüber
hinaus ermöglichen wir ein reaktives Verhalten in Form von einund ausgehenden Nachrichten sowie Zeit(-anforderungen) zu berücksichtigen.
Voraussetzungen Folgende Voraussetzungen müssen erfüllt sein, um den Algorithmus
von Angluin anzuwenden: 1) Das Systemverhalten muss als deterministischer endlicher
Automat (DFA) repräsentierbar sein. 2) Um Testeingaben auszuführen, muss es über ein
entsprechendes (Test-) Laufzeitframework möglich sein, die Altkomponente zu stimulieren. 3) Die Eingaben müssen dementsprechend auch bekannt sein. 4) Die Altkomponente
muss einen eindeutigen Startzustand besitzen, in dem diese extern versetzt werden kann.
5) Die regulä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 für die Zustä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 dafür,
80
die Altkomponente überhaupt ausführen zu können bzw. anzusteuern. Ohne diese Informationen ist eine Integration der Altkomponente in ein reales System nicht möglich. 4) ergibt
sich zum Teil aus 1) (der eindeutige Startzustand). Wenn eine Altkomponente nicht wiederholt initialisierbar wäre, könnte sie nur einmal gestartet werden. Eine Integration wäre
damit höchst fraglich, da keinerlei Tests mit der Umgebung durchgeführt werden könnten.
5) ist für die von uns betrachteten reaktiven Systeme keine Einschränkung. Voraussetzung
6) ist die größte Einschränkung, da diese Information eigentlich nicht bekannt ist. Daher
muss dieser Wert geschätzt werden. Grundsätzlich scheint es möglich, dass der Kontextautomat eine gute Orientierung ist. Eine hohe Abschätzung nach oben und die Erkenntnis, dass der erlernte Automat weniger Zustände als die obere Abschätzung der Anzahl
der Zustände hat, führen dazu, dass auch diese Annahme akzeptabel ist. Ein wiederholtes
Ausfü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 ermöglichen, haben wir die M ECHATRONIC UML entwickelt (z. B. [GHH+ 08b]). Der relevante Ausschnitt fü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 berü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 für
den Scheibenwischer und aus der (Gegen-) Rolle coordination für die Automatisierung
und Koordination des Scheibenwischers. Zusätzlich werden für jedes Kommunikationsmuster Sicherheitseigenschaften spezifiziert, die formal mittels Model Checking überprüft
werden4 . Eine Standardbedingung für sicherheitskritische Systeme ist, dass keine Verklemmung auftreten darf (engl. Deadlock). Eine weitere mö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
ermö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 Qualitä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 kö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 ermöglicht wird das Modell des Verhaltens einer Altkomponente iterativ zu erlernen und iterativ Sicherheitseigenschaften zu überprü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 für die Beispielanwendung gezeigt werden, dass
coordination||learned.wiper |= coordination.of f implies learned.wiper.of f ∧
¬δ(keinDeadlock) für 1) und learned.wiper ≤ wiper für 2) gilt.
Eine Verfeinerung lässt sich ebenfalls ü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 erfüllt wird, in den komplementären Automaten durch einen Fehlerzustand berücksichtigt. In der Analyse wird dann gezeigt, dass
dieser Fehlerzustand nicht erreichbar ist.
Wir werden im Folgenden zeigen wie wir eine kompositionale Analyse für die Betrachtung von Black-Box Komponenten durchführen können, womit wir entsprechend auch
eine Verfeinerung zeigen können. Generelle Idee ist dabei das Verfahren von [Ang87] für
82
die Domäne mechatronischer Systeme anzupassen. Das heißt insbesondere, dass wir einund ausgehende Nachrichten, Kontextverhalten und Zeit berücksichtigen.
Der Ansatz besteht aus den folgenden Schritten:
1. lernen eines Kandidaten des Protokollverhaltens der Altkomponente (mit erweiterten Angluin Ansatz),
2. kompositionale Überprüfung des Kandidaten aus 1. unter Berücksichtigung des
Kontextverhaltens und Sicherheitseigenschaften an die Integration.
(a) Wenn aus 2. ein Gegenbeispiel erfolgt, dann wird überprüft, ob dieses Gegenbeispiel durch die Altkomponente bestätigt wird. Ist dies der Fall, ist die Integration fehlerhaft. (Das Verhalten kann und sollte trotzdem vollständig erlernt
werden, um eine Anpassung des Kontextes zu ermöglichen.). Ist dies nicht der
Fall, wird mit 1. fortgefahren unter Berücksichtigung des Gegenbeispiels.
(b) Folgt aus 2. kein Gegenbeispiel, dann wird überprüft, ob das erlernte Verhalten äquivalent zur Altkomponente ist (Conformance Test mit Vasilevskii und
Chow [Vas73, Cho78]).
3. Folgt aus der Äquivalenzprüfung (2.(b)), dass der Automat äquivalent ist, ist die
Lernphase abgeschlossen und die Integration korrekt. Ist dies nicht der Fall, wird
auf Basis der Ergebnisse der Äquivalenzprüfung mit 1. fortgefahren.
Erweiterter Lernalgorithmus Wie in Abschnitt 3 dargestellt, beantwortet der Lehrer Zugehörigkeitsanfragen (-tests) an die Altkomponente und stellt Gegenbeispiele zur
Verfügung, wenn die Ä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 bestätigt
wird, ist die Integration fehlerhaft. Andernfalls nutzen wir dieses Gegenbeispiel um den
folgenden Kandidaten zu erlernen. Die Berücksichtigung des Kontextes ermöglicht uns
gezielter das relevante zu erlernende Verhalten zu ermitteln und frühzeitig Fehler in der
Integration zu ermitteln.
Falls das Model Checking kein Gegenbeispiel liefert, wird eine Äquivalenzanfrage mittels des Verfahrens von Vasilevskii und Chow durchgeführt (siehe Abschnitt 3). Dieses
Verfahren ist aufgrund seiner guten Laufzeiteigenschaften für Konformitätstests weit verbreitet. Eingabe in das Verfahren ist der Kandidat der Altkomponente sowie die obere
Anzahl an erwarteten Zuständen der Altkomponente. Der Algorithmus bestätigt entweder
die Äquivalenz oder gibt ein Gegenbeispiel zurück, welches wiederum als Eingabe für den
Angluin Algorithmus verwendet werden kann.
Unter der Annahme, dass eine obere Schranke für die Zustände bekannt ist, kann durch
das vorgestellte Verfahren tatsächlich sichergestellt werden, dass entweder ein Fehler in
der Integration festgestellt wird oder die Integration unter Berücksichtigung der Sicherheitseigenschaften korrekt ist.
Den zugrunde liegenden Automaten des Angluin Ansatzes haben wir um Mealy Automaten erweitert (siehe auch [HNS03]). Dies ermöglicht zusätzlich die Betrachtung von Ein/Ausgabeverhalten. Der grundsätzliche Unterschied entsteht dadurch, dass der Angluin Ansatz auf Basis eines DFA als Antwort auf eine Anfrage ein akzeptierendes Wort erwartet.
83
Zeit Grundsä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 Ausführung einer Altkomponente ist daher Voraussetzung für die korrekte Funktionsweise. Somit ist die Angabe der Periode der Altkomponente notwendig für eine Integration. Das implementierte System garantiert eine
korrekte Funktionsweise unter Verwendung dieser Periode (siehe auch Abschnitt 3).
Ist dies der Fall, können die zeitlichen Bedingungen durch die Periode des Systems diskretisiert werden (kö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 Abhängigkeit von der Periode
Zeiteigenschaften zu überprüfen, bzw. zu identifizieren. Dies wird ermöglicht durch eine Anfrage in Form eines leeren Wortes für jede mögliche vielfache Zeitbedingung der
Periode. Für jeden Zustand wird damit zusätzlich überprüft, ob er in Abhängigkeit von
unterschiedlich langen Zeitintervallen, die ein vielfaches der Periode sind und durch ein
leeres Wort repräsentiert werden, unterschiedlich reagiert. Durch diese Form der Diskretisierung der Zeit, muss der Lernansatz im Wesentlichen nur um zusätzliche Eingabewörter
erweitert werden.
Anwendungsbeispiel Wir haben den beschriebenen Ansatz unter anderem an dem in
Abschnitt 4 eingeführten Scheibenwischerbeispiel evaluiert. Wir haben dabei eine Scheibenwischerumsetzung basierend auf dem Patent [Reg96] testweise umgesetzt. Die dort
beschriebene Spezifikation betrachten wir ähnlich zu einer Beschreibung einer Altkomponente. Interessanterweise haben wir nach nur wenigen Schritten einen Konflikt identifiziert. Es ist nicht möglich aus Zustand wiper 2 direkt wieder den Scheibenwischer auszuschalten. Grund hierfür ist, dass die Altkomponente nur ein Ausschalten des Scheibenwischers aus der kleinsten Stufe ermö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 für die Integration einer Altkomponente ist, dass sie eine hohe Qualität in der Praxis gezeigt hat und auch den Entwicklungsprozess beschleunigt. Um also
die Altkomponente erfolgreich zu integrieren, muss der Kontext angepasst werden. Eine
Möglichkeit wäre, das Ausschalten aus Zustand wiper 2 und Zustand wiper 3 jeweils über
den Zustand wiper 1 umzusetzen.
Für das Erlernen des gezeigten Beispiels wurde nicht mehr als 1 min. benötigt. Weitere
Beispiele bis zu 15 Zuständen konnten problemlos innerhalb von 2 min. erkannt werden. Natürlich ist die Zeit für das Erlernen maßgeblich von der Antwortzeit des Systems
abhängig. Liegt also eine lange Periode vor, wird entsprechend auch mehr Zeit benötigt,
um das Verhalten der Altkomponente zu beobachten.
6
Resümee und Ausblick
Wir haben in diesem Beitrag einen Ansatz vorgestellt, der es ermöglicht mechatronische
Altkomponenten unter Berücksichtigung von Sicherheitseigenschaften in ein Systemmo-
84
Abbildung 3: Ausschnitt erlerntes Verhalten
dell zu integrieren. Dies ist eine häufig gestellte Fragestellung in der industriellen Praxis. Zulieferer der Automobilindustrie sowie OEMs müssen häufig vorhandene Komponenten von Drittanbietern integrieren, ohne das Modell der Komponente zu kennen. Das
vorgestellte iterative Verfahren ermöglicht das Verhaltensmodell einer Altkomponente zu
erlernen und Sicherheitsanalysen auf den erlernten Modellen durchzuführen. Weiterhin
ermöglichen wir durch die Integration von Systemidentifikationsverfahren die Erkennung
von Reglerverhalten, welches zwingend benötigt wird, um die Korrektheit der Integration
der Altkomponente sicherzustellen. Eine Werkzeugunterstützung dieses Verfahrens haben
wir in [HBB+ 09] vorgestellt. Die bisherigen Evaluierungen haben ergeben, dass der Ansatz sich durchaus für mechatronische Systeme bewährt hat. Jedoch soll dieser Aspekt
weiterhin untersucht werden, sowie eine Übertragung in andere Domä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 Rogé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 Böger, Christian Brenner,
Kathrin Brö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 Schä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 Grü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-Nürnberg, 2007. Arbeitsberichte des Instituts für Informatik, Friedrich-Alexander-Universität Erlangen Nü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 Universitä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 Universität Mü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 für Eisenbahnsteuerungs- und Überwachungssysteme. Europäische Norm., 2001.
[DHJ+ 08]
F. Deissenböck, B. Hummel, E. Jürgens, B. Schä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 Jürgens, Florian Deissenbö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 Jürgens, Florian Deissenbö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.

Modellbasierte Entwicklung eingebetteter Systeme VI.

Transcrição

Documentos relacionados

Victorinox Rescue Tool One Hand

Stoffwechsel-Typisierung (Metabolic Typing ohne

Falke TK2 Cool Socke

Falke TK2 Wool Socke

SNO-SEAL Schuhpflege Wax

Stickstoff-Federsysteme / Manifold systems

Product RE 60 3-in-1 Elektrowerkzeug 3-in

Artikeldatenblatt - Mesch-Shop

The most beautiful wooden chairs

klicken, um PDF runterzuladen.