Inkrementelle Konstruktion von Madl Implication Graphs für Feature Model Evolution

Management of configurable software is often supported by using software product lines. A feature model represents a software product line by modeling the configurable features in a hierarchical tree-structure. Additionally, it defines the set of valid configurations. When constructing a configuration, a SAT solver is called multiple times after each (de-)selection of a feature to determine which features have to be (de-)selected afterwards. For a large-scale feature model, the high number of necessary SAT calls may take up to several hours. A modal implication graph (MIG) describes dependencies between features to reduce the number of SAT calls in the configuration process and, thus, the required time. However, the construction of a MIG can take up to several hours for large feature models. Moreover, the MIG has to be recalculated after every change in a feature model with state-of-the-art methods which leads to high computational effort. In this thesis, we introduce a concept to incrementally calculate a MIG by adapting it to changes in the feature model. To this end, we calculate and use the differences in the conjunctive normal forms (CNFs) representing the feature model versions before and after an evolution step. Based on these CNF differences, the MIG is modified. We evaluate our concept with regard to (1) the correctness of the incremental calculation, (2) the advantage in the computation time when incrementally calculating, (3) the number of SAT calls we reduced, and (4) the accuracy of the incremental calculation. Our empirical evaluation strongly indicates high benefits of the incremental construction regarding the number of required SAT calls and computation time. Our empirical evaluation shows that the incremental construction saves up to 91% of computation time and up to 86% of SAT calls.Die Verwaltung von konfigurierbarer Software wird häufig durch die Verwendung von Software-Produktlinien unterstützt. Ein Feature-Model repräsentiert eine Software-Produktlinie durch Modellierung der konfigurierbaren Features in einer hierarchischen Baumstruktur. Zusätzlich definiert es die Menge der gültigen Konfigurationen. Beim Erstellen einer Konfiguration wird ein SAT-Solver nach jeder (De-)Selektion eines Features mehrfach aufgerufen, um zu bestimmen, welche Features danach (de-)selektiert werden müssen. Die hohe Anzahl der notwendigen SAT-Aufrufe kann für komplexe Feature-Modelle zu Laufzeiten von mehreren Stunden führen. Ein modaler Implikationsgraph (MIG) beschreibt Abhängigkeiten zwischen Features, um die Anzahl der SAT-Aufrufe im Konfigurationsprozess und damit die benötigte Zeit zu reduzieren. Allerdings kann die Konstruktion eines MIGs bei großen Feature-Modellen bis zu mehrere Stunden dauern. Außerdem muss der MIG nach jeder Änderung eines Feature-Models bei aktuellem Stand der Technik neu berechnet werden, was zu einem hohen Rechenaufwand führt. In dieser Arbeit führen wir ein Konzept zur inkrementellen Berechnung eines MIGs ein, indem der MIG nach einem Evolutionsschritt angepasst wird statt neu berechnet zu werden. Zu diesem Zweck berechnen und nutzen wir die Unterschiede in den konjunktiven Normalformen (CNFs), die die Feature-Model Versionen vor und nach einem Evolutionsschritt repräsentieren. Basierend auf dieser CNF-Differenz wird der MIG angepasst. Wir evaluieren unser Konzept im Hinblick auf (1) die Korrektheit der inkrementellen Berechnung, (2) den Vorteil in der Rechenzeit bei inkrementeller Berechnung, (3) die Anzahl der reduzierten SAT-Aufrufe und (4) die Genauigkeit der inkrementellen Berechnung. Unsere empirische Evaluation zeigt signifikante Vorteile der inkrementellen Konstruktion in Bezug auf die Anzahl der benötigten SAT-Aufrufe und die benötigte Berechnungszeit. Unsere empirische Evaluation zeigt, dass die inkrementelle Konstruktion bis zu 91% der Berechnungszeit und bis zu 86% der SAT-Aufrufe einspart