Quality-Optimised Differencing Algorithms for Models
Final Report Abstract
Modellbasierte Methoden der Softwareentwicklung benötigen Werkzeuge, die das kollaborative Arbeiten und die Versionierung von Modellen unterstützen. Eine Kernfunktion dieser Versionierungswerkzeuge ist der Vergleich von zwei Modellen. Eine Darstellung von deren Unterschieden bezeichnet man als Modelldifferenz. Modelldifferenzen sind nicht eindeutig, für zwei gegebene Modelle gibt es i.a. viele Möglichkeiten, die Unterschiede darzustellen. Diese Modelldifferenzen sind unterschiedlich kompakt, lesbar oder weiterverarbeitbar, weisen also unterschiedliche Qualität auf. Ein großes praktisches Problem stellt die Ineffizienz der Grundalgorithmen zur Differenzberechnung dar. Die Effizienzprobleme hängen stark von Charakteristika der Modelltypen, der Größe der Modelle und diversen technischen Randbedingungen ab. In vielen Fällen muß die Differenzberechnung daher modelltypspezifische Heuristiken einsetzen. Hauptziel dieses Projekts war die Präzisierung des Qualitätsbegriffs für Modelldifferenzen und die Evaluation und Optimierung von Differenzalgorithmen sowohl hinsichtlich Laufzeit als auch der erzielten Qualität der Differenzen. Heuristiken können nur empirisch evaluiert werden, der Forschungsansatz des Projekts sah daher vor, Differenzalgorithmen anhand repräsentativer Benchmarks empirisch zu vergleichen. Für viele gängige Modelltypen sind keine geeigneten natürlichen Testdaten verfügbar, deswegen sollten fehlende Benchmarks künstlich erzeugt werden. Hierzu wurde ein völlig neuer Modell- und Differenzgenerator, der konsistente Modelle mit vorgegebenen statistischen Merkmalen generieren kann, entwickelt und in mehreren Publikationen vorgestellt. Um möglichst “natürliche” Differenzen zu generieren, wurde die Evolution von 9 realen Projekten analysiert und mit stochastischen Modellen beschrieben, und zwar hinsichtlich der Verteilung von Editieroperationen innerhalb von Differenzen und hinsichtlich der zeitlich variierenden Größe von Differenzen mit ARMA- und ARMA-GARCH Zeitserienmodellen. Als Nebenprodukt dieser Aktivitäten hat das Projekt eine der größten heute existierenden Sammlungen von Modellen und Modelldifferenzen erstellt und für andere Forschungen auf der Webseite des Projekts frei verfügbar gemacht. Der ursprüngliche, der Antragstellung zugrundeliegende Begriffsrahmen definierte eine Differenz technisch i.w. als ein Matching, d.h. eine Menge korrespondierender Paare von Modellelementen. Dieser Begriffsrahmen erwies sich konzeptuell als zu limitiert. Auf Basis einer Analyse der Anforderungen von Modellversionierungswerkzeugen wurde er erweitert zu einer Familie von Modelldifferenztypen. Diese Differenztypen unterscheiden sich hauptsächlich in den enthaltenen technischen Informationen und in der Menge der in den Differenzen benutzten Editieroperationen. Das Problem, die Differenzberechnung zu optimieren, besteht daher wesentlich darin, in einer konkreten Anwendung zunächst den richtigen Differenztyp zu bestimmen. Ungeplante Erkenntnisse des Projekts in diesem Zusammenhang waren: (a) Mehrere wichtige Differenzwerkzeuge haben obligatorische Anforderungen an Differenzen, die von keinem derzeit bekannten Differenzberechnungsverfahren garantiert werden, d.h. hier besteht noch wesentlicher Forschungsbedarf. (b) Der Aufwand kann nicht isoliert im Matcher optimiert werden, denn je nach Differenztyp sind weitere, oft wesentlich aufwendigere Verarbeitungsschritte erforderlich. Nach Festlegung des Differenztyps ist eine modelltypspezifische Matcher-Heuristik zu bestimmen. Zur Unterstützung dieser Konfigurationsarbeit wurden einzelne Komponenten von Matchern hinsichtlich der erzeugten Matchings und Laufzeiten analysiert und Regeln zur Optimierung der Konfiguration abgeleitet. Bei ähnlichkeitsbasierten Matchern ist eine sehr große Zahl numerischer Konfigurationsparameter zu bestimmen. Zu Reduktion dieses Konfigurationsaufwands wurde ein evolutionärer Algorithmus entwickelt, der erfolgreich fast alle numerischen Konfigurationsparameter automatisch optimiert.
Publications
- Generating Realistic Test Models for Model Processing Tools; p.620-623 in: Proc. 26th IEEE/ACM Intl. Conf. Automated Software Engineering (ASE’11); ACM; 2011
Pietsch, P.; Shariat Yazdi, H.; Kelter, U.
- Adaptability of Model Comparison Tools; p.306-309 in: Proc. 27th IEEE/ACM Intl. Conf. Automated Software Engineering (ASE’12); ACM; 2012
Kehrer, T.; Kelter, U.; Pietsch, P.; Schmidt, M.
- Controlled Generation of Models with Defined Properties; p.95-106 in: Proc. Software Engineering 2012 (SE2012), Berlin; Lecture Notes in Informatics, GI; 2012
Pietsch, P.; Shariat Yazdi, H.; Kelter, U.
- Statistical Analysis of Changes for Synthesizing Realistic Test Models; p.225-238 in: Proc. Software Engineering 2013 (SE2013), Aachen; Lecture Notes in Informatics, GI; 2013 (Best Paper Award der SE2013)
Shariat Yazdi, H.; Pietsch, P.; Kehrer, T.; Kelter, U.
- Statistical Analysis and Simulation of Design Models Evolution; Dissertation, U.Siegen
Shariat Yazdi, H.
- Synthesizing Realistic Test Models; Computer Science Research and Development, Springer 30:3-4, August 2015, p.231-253
Shariat Yazdi, H.; Pietsch, P.; Kehrer, T.; Kelter, U.
