Model-Based Runtime Adaptation of Resource Constrained Devices V O M FA C H B E R E I C H 1 8 E L E K T R O - U N D I N F O R M AT I O N S T E C H N I K Z U R E R L A N G U N G D E R W Ü R D E E I N E S D O K T O R - I N G E N I E U R S ( D R . - I N G . ) G E N E H M I G T E D I S S E RTAT I O N V O N M S C . K A R S T E N S A L L E R G E B O R E N A M 3 0 . M A I 1 9 8 1 I N D A R M S TA D T R E F E R E N T: P R O F. D R . R E R . N AT. A . S C H Ü R R K O R R E F E R E N T: P R O F. D R . - I N G . I N A S C H A E F E R TA G D E R E I N R E I C H U N G : 1 4 . A U G U S T 2 0 1 4 TA G D E R D I S P U TAT I O N : 1 2 . D E Z E M B E R 2 0 1 4 D 1 7 D A R M S TA D T 2 0 1 5 The work of Karsten Saller was supported by the German Research Foundation (DFG) in the Collaborative Research Center (SFB) 1053 “MAKI - Multi-Mechanis- m-Adaptation for the Future Internet” at the Technische Universität Darmstadt. Please cite this document as: URN: urn:nbn:de:tuda-tuprints-43224 URL: http://tuprints.ulb.tu-darmstadt.de/id/eprint/4322 This document was provided by tuprints, TU Darmstadt E-Publishing-Service http://tuprints.ulb.tu-darmstadt.de tuprints@ulb.tu-darmstadt.de This publication complies to the Creative Commons License: Attribution – Non-Commercial – No Derivative Works 3.0 http://creativecommons.org/licenses/by-nc-nd/3.0/ Karsten Saller: Model-Based Runtime Adaptation of Resource Constrained Devices , © August 2014 urn:nbn:de:tuda-tuprints-43224 http://tuprints.ulb.tu-darmstadt.de/id/eprint/4322 http://tuprints.ulb.tu-darmstadt.de tuprints@ulb.tu-darmstadt.de http://creativecommons.org/licenses/by-nc-nd/3.0/ D E C L A R AT I O N O F A U T H O R S H I P I warrant that the thesis presented here, is my original work and that I have not received outside assistance. All references and other sources used by me have been appropriately acknowledged in the work. I further declare that the work has not been submitted for the purpose of academic examination, either in its original or similar form, anywhere else. I hereby grant the Real-Time Systems Lab the right to publish, reproduce and distribute my work. Darmstadt, 14. August 2014 Karsten Saller We have seen that computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. — Donald E. Knuth [Knu74] D A N K S A G U N G Mein besonderer Dank gilt Dr. Malte Lochau, der mich maßgeblich bei der Umsetzung meiner Ideen und Konzepte unterstützt hat und mich unermüdlich beim Schreibprozess dieser Arbeit beigestanden hat. Es freut mich zu wissen, dass unsere gemeinsamen Arbeiten auch zukünftig in den Sonderforschungsbere- ich MAKI einfließen werden. Ebenso wichtig für mich war die Unterstützung von meinem Doktorvater Prof. Dr. Andy Schürr. Er hat meine Ideen stets gefördert und mir dabei auch meine Freiheit gelassen, unterschiedliche Themen und Konzepte zu verfolgen. Damit konnte ich meinen eigenen Weg in der For- schung finden, wofür ich Prof. Schürr sehr dankbar bin. Gerne erinnere ich mich an unsere regelmäßigen Treffen, an denen wir meine Ideen besprochen haben. Schließlich möchte ich mich auch bei Prof. Dr. Ina Schaefer bedanken, die mich auf dem FOSD-Treffen 2012 in der Softwareproduktlinien Community willkom- men hieß und zudem das Zweitgutachten dieser Arbeit übernommen hat. Rückblickend möchte ich hier auch meine Kollegen Christian Groß, Max Lehn, Kamill Panitzek und Dominik Stingl erwähnen, die mich seit Beginn meiner Forschungsaktivitäten in der QuaP2P-Gruppe bis zu meinem Ende der Promotion begleiteten. Zusammen haben wir auch an dem Sonderforschungsbereich MAKI gearbeitet, der unsere Forschungsaktivitäten aus QuaP2P die nächsten Jahre fort- führen und intensivieren wird. Zu vielen Teilen der vorliegenden Arbeit haben Studenten im Rahmen von zahlreichen studentischen Arbeiten beigetragen. Hier möchte ich insbesondere die ausgezeichneten Bachelorarbeiten von Stefan Bauregger und Thomas Schna- bel hervorheben. Zudem möchte ich Ingo Reimund an dieser Stelle für seine langjährige Unterstützung als wissenschaftliche Hilfskraft danken. Stellvertretend für die vielen guten Freunde, die mich auf meinem Lebensweg begleitet haben, möchte ich hier meine langjährigen Kommilitonen Daniel Ack- ermann, Matthias Bernges und Johannes Kohlmann nennen. Rückblickend auf meine Zeit am Fachgebiet Echtzeitsysteme möchte ich zudem Anthony Anjorin und Dr. Sebastian Oster danken, die immer gerne zu einem Gedankenaustausch bereit waren. Schließlich möchte ich meinen Eltern dafür danken, dass sie mir diesen Weg ermöglicht und mich stets unterstützt haben. Darmstadt, im August 2014 A B S T R A C T Dynamic Software Product Line (DSPL) engineering represents a promising ap- proach for planning and applying runtime reconfiguration scenarios to self-adap- tive software systems. Reconfigurations at runtime allow those systems to con- tinuously adapt themselves to ever changing contextual requirements. With a systematic engineering approach such as DSPLs, a self-adaptive software system becomes more reliable and predictable. However, applying DSPLs in the vital do- main of highly context-aware systems, e.g., mobile devices such as smartphones or tablets, is obstructed by the inherently limited resources. Therefore, mobile devices are not capable to handle large, constrained (re-)configuration spaces of complex self-adaptive software systems. The reconfiguration behavior of a DSPL is specified via so called feature mod- els. However, the derivation of a reconfiguration based on a feature model (i) in- duces computational costs and (ii) utilizes the available memory. To tackle these drawbacks, I propose a model-based approach for designing DSPLs in a way that allows for a trade-off between pre-computation of reconfiguration scenarios at de- velopment time and on-demand evolution at runtime. In this regard, I intend to shift computational complexity from runtime to development time. Therefore, I propose the following three techniques for (1) enriching feature models with context information to reason about potential contextual changes, (2) reducing a DSPL specification w.r.t. the individual characteristics of a mo- bile device, and (3) specifying a context-aware reconfiguration process on the basis of a scalable transition system incorporating state space abstractions and incremental re- finements at runtime. In addition to these optimization steps executed prior to runtime, I introduce a concept for (4) reducing the operational costs utilized by a reconfiguration at runtime on a long-term basis w.r.t. the DSPL transition system deployed on the device. To realize this concept, the DSPL transition system is enriched with non-functional properties, e.g., costs of a reconfiguration, and behavioral properties, e.g., the probability of a change within the contextual situation of a device. This provides the possibility to determine reconfigurations with minimum costs w.r.t. estimated long-term changes in the context of a device. The concepts and techniques contributed in this thesis are illustrated by means of a mobile device case study. Further, implementation strategies are presented and evaluated considering different trade-off metrics to provide detailed insights into benefits and drawbacks. Z U S A M M E N FA S S U N G Dynamische Software Produktlinien (DSPLs) stellen einen vielversprechenden Ansatz für die Planung und Ausführung von Rekonfigurationen selbst-adaptiver Softwaresystemen dar. Laufzeitrekonfigurationen erlauben es einem System sich kontinuierlich den sich ständig ändernden kontextuellen Anforderungen anzu- passen. Jedoch wird die Anwendbarkeit von DSPLs auf eine kontextsensible Domäne, wie die der mobilen Endgeräte (Smartphones, Tablets, etc.), durch eine inhärente Limitierung von Ressourcen eingeschränkt. Daher sind solche mo- bilen Endgeräte nicht in der Lage, mit den (Re-)Konfigurationsräumen komplexer adaptiver Systeme umzugehen. Das Rekonfigurationsverhalten einer DSPL wird mittels so genannter Feature- Modelle spezifiziert. Die Ableitung einer Rekonfiguration auf der Basis eines Fea- ture-Modells verbraucht jedoch (i) Berechnungsressourcen und (ii) Speicher. Um diese Nachteile in den Griff zu bekommen stelle ich einen modellbasierten Ansatz für die Spezifikation einer DSPL vor, der darauf ausgelegt ist, einen Ausgleich zwischen zur Entwicklungszeit vorberechneten Rekonfigurationsszenarien und bedarfsgetriebenen Rekonfigurationen zur Laufzeit zu bieten. Daher verschiebe ich den Berechnungsaufwand während der Laufzeit eines Endgerätes und zur Entwicklungszeit einer DSPL. Hierfür schlage ich die folgenden Techniken vor: (1) Anreichern von Feature-Modellen mit kontextuellen Informationen, um mö- gliche Änderungen im Gerätekontext zu erkennen, (2) Reduktion der DSPL-Spezifikation in Bezug auf die individuellen Charak- teristiken eines mobilen Endgerätes sowie (3) Erstellung eines kontextsensiblen Rekonfigurationsprozesses auf Basis ei- nes Zustandsraumes, der zur Laufzeit inkrementell verfeinert wird. Zusätzlich, zu diesen Optimierungsschritten, die zur Entwicklungszeit ausgeführt werden, stelle ich ein Konzept vor, welches angedacht ist, um zur Laufzeit ausge- führt zu werden: (4) Lang-Zeit Reduktion der Ausführungskosten einer Rekonfiguration zur Lauf- zeit auf Basis eines DSPL-Transitionssystems. Um dies umzusetzen, wird ein DSPL-Transitionssystem mit nicht-funktionalen Eigenschaften angereichert, wie z.B. Kosten einer Rekonfiguration. Darüber hin- aus wird das Kontextverhalten mittels Wahrscheinlichkeiten erfasst, um zu be- schreiben, wann ein Kontext betreten bzw. verlassen wird. Hiermit können Rekonfigurationen ausgewählt werden, die, in Bezug auf die zu erwartenden Kontextänderungen, auf eine lange Sicht hin minimale Kosten verursachen. Die in dieser Arbeit erarbeiteten Techniken und Konzepte werden anhand eines Fallbeispiels über mobile Endgeräte vorgestellt. Zusätzlich werden Implemen- tierungsstrategien diskutiert und evaluiert in Bezug auf mögliche Vor- und Nach- teile der Ansätze. P U B L I C AT I O N S Some ideas and figures have appeared previously in the following publications. Book Chapters M. Lehn, T. Triebel, C. Gross, D. Stingl, K. Saller, W. Effelsberg, A. Kovacevic, and R. Steinmetz. Designing Benchmarks for P2P Systems, pages 209–229. From Active Data Management to Event-Based Systems and More. Springer, 2010. K. Saller, K. Panitzek, and M. Lehn. Benchmarking Methodology, volume 7847 of LNCS, pages 19–67. Springer, 2013. Published in "Benchmarking Peer-to-Peer Systems - Understanding the Quality of Service in Large-Scale Distributed Sys- tems". D. Stingl, C. Gross, and K. Saller. Decentralized Monitoring in Peer-to-Peer Systems, volume 7847 of LNCS, pages 81–111. Springer, 2013. Published in "Benchmark- ing Peer-to-Peer Systems - Understanding the Quality of Service in Large-Scale Distributed Systems". Journal Article A. Anjorin, K. Saller, I. Reimund, S. Oster, I. Zorcic, and A. Schürr. Model-driven rapid prototyping with programmed graph transformations. Journal of Visual Lan- guages & Computing, 24(6), pages 441–462, 2013. Special Issue on Graph Transfor- mation and Visual Modeling Techniques II. Refereed Conference And Workshop Papers A. Anjorin, K. Saller, M. Lochau, and A. Schürr. Modularizing Triple Graph Gram- mars using Rule Refinement. In S. Gnesi and A. Rensink, editors, Proceedings of Fundamental Approaches to Software Engineering, LNCS. Springer, pages 340–354, 2014. A. Anjorin, K. Saller, S. Rose, and A. Schürr. A Framework for Bidirectional Model-to-Platform Transformations. In K. Czarnecki and G. Hedin, editors, Pro- ceedings of the 5th International Conference on Software Language Engineering (SLE), LNCS. Springer, pages 124–143, 2012. P. Mukherjee, K. Saller, A. Kovacevic, K. Graffi, A. Schürr, and R. Steinmetz. Trace- ability Link Evolution with Version Control. In Evolutionäre Software- und Syste- mentwicklung - Methoden und Erfahrungen (ESoSyM-2011), Workshop im Rahmen der Konferenz SE. Bonner Köllen Verlag, pages 151–161, 2011. D. Stingl, C. Gross, K. Saller, S. Kaune, and R. Steinmetz. Benchmarking De- centralized Monitoring Mechanisms in Peer-to-Peer Systems. In Proceedings of the third joint WOSP/SIPEW international conference on Performance Engineering. ACM, pages 193–204, April 2012. K. Saller, M. Lochau, and I. Reimund. Context-Aware DSPLs: Model-Based Run- time Adaptation for Resource-Constrained Systems. In Proceedings of the 17th In- ternational Software Product Line Conference co-located workshops, pages 106 – 113. ACM Press, ACM, August 2013. K. Saller, S. Oster, A. Schürr, J. Schroeter, and M. Lochau. Reducing Feature Mod- els to Improve Runtime Adaptivity on Resource Limited Devices. In Proceedings of the 16th International Software Product Line Conference (SPLC), volume 2 of ACM, pages 135 – 142. ACM, 2012. K. Saller, D. Stingl, and A. Schürr. D4M, a Self-Adapting Decentralized Derived Data Collection and Monitoring Framework. In Workshops der wissenschaftlichen Konferenz Kommunikation in Verteilten Systemen 2011 (WowKiVS 2011), volume 37 of Electronic Communications of the EASST, pages 1–12, March 2011. Technical Report M. Riecker, W. Müller, M. Hollick, and K. Saller. A Secure Monitoring and Control System for Wireless Sensor Networks. Technical Report TR-RI-11-313, Universität Paderborn, Paderborn, 2011. xii C O N T E N T S I Introduction & Background 1 1 Introduction 3 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Self-Adaptation of Model-Based Software Systems 13 2.1 Self Adaptive Software Systems . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Adaptivity in Mobile Devices . . . . . . . . . . . . . . . . . . 14 2.1.2 Classification of Self-Adaptive Software Systems . . . . . . 17 2.1.3 The MAPE-K Feedback Loop . . . . . . . . . . . . . . . . . . 22 2.1.4 Research Challenges in SAS . . . . . . . . . . . . . . . . . . 25 2.2 Software Product Line Engineering . . . . . . . . . . . . . . . . . . . 27 2.2.1 Fundamentals of SPL Engineering . . . . . . . . . . . . . . . 28 2.2.2 Feature Models . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.3 Dynamic Software Product Lines . . . . . . . . . . . . . . . 37 2.2.4 Research Challenges in DSPLs . . . . . . . . . . . . . . . . . 41 II Systematic Context-Awareness 43 3 Concept and Contributions 45 3.1 DSPL based MAPE-K Feedback Loop . . . . . . . . . . . . . . . . . 46 3.1.1 Evolution at Design Time . . . . . . . . . . . . . . . . . . . . 47 3.1.2 Adaptivity at Runtime . . . . . . . . . . . . . . . . . . . . . . 48 3.2 Optimization of a DSPL Engineering Process . . . . . . . . . . . . . 50 3.2.1 Optimization at Design Time . . . . . . . . . . . . . . . . . . 50 3.2.2 Optimization and Deployment Preparation . . . . . . . . . 53 3.2.3 Optimization at Runtime . . . . . . . . . . . . . . . . . . . . 55 4 Autonomous Adaptation Based on DSPLs 57 4.1 Formal Characteristics of a DSPL . . . . . . . . . . . . . . . . . . . . 58 4.1.1 Fundamentals of Propositional Logic . . . . . . . . . . . . . 58 4.1.2 Feature Models as Propositional Formula . . . . . . . . . . 61 4.1.3 Derivation of a Configuration with a Constraint Solver . . . 64 4.1.4 DSPL Extension . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.2 Context-Sensitive DSPLs . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.1 Contexts to Execute an Autonomous Reconfiguration . . . 73 4.2.2 Integration of a Context-Model into a DSPL . . . . . . . . . 74 III Resource Constraint Runtime Adaptation 79 5 Reduction of a Feature Model 81 5.1 Device Specific Reduction and Deployment . . . . . . . . . . . . . . 83 5.2 Feature Model Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.3 The Reduction Process . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.3.1 Implementation of a Feature Model Reduction . . . . . . . 88 xiv contents 5.3.2 Proof of Correctness . . . . . . . . . . . . . . . . . . . . . . . 91 5.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.4.1 Evaluation Setup . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6 State Space Reduction 97 6.1 Complete State Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.1.1 Extension of a State Space to a Transition System . . . . . . 102 6.1.2 Context-Enriched State Space . . . . . . . . . . . . . . . . . . 104 6.2 Incomplete State Space . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.2.1 On-Demand, Pre-Planning, and a Hybrid Combination . . 107 6.2.2 Context Coverage Criteria . . . . . . . . . . . . . . . . . . . . 110 6.3 Abstraction with Partial States . . . . . . . . . . . . . . . . . . . . . . 113 6.3.1 Unrestricted Features and Partial States . . . . . . . . . . . . 114 6.3.2 Identification of Unrestricted Features . . . . . . . . . . . . 116 6.4 Three-Valued Reconfiguration Semantics . . . . . . . . . . . . . . . 123 6.4.1 Reconfiguration Transitions . . . . . . . . . . . . . . . . . . . 124 6.4.2 Correctness of the Reconfiguration Transition System . . . 129 6.5 Implementation of a Context-Aware Reconfiguration Process . . . . 132 6.5.1 Pre-Planning of a PKS . . . . . . . . . . . . . . . . . . . . . . 132 6.5.2 Runtime Reconfiguration based on a PKS . . . . . . . . . . 135 6.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.6.1 DSPL Pre-Planning at Design Time . . . . . . . . . . . . . . 138 6.6.2 DSPL Reconfiguration at Runtime . . . . . . . . . . . . . . . 141 6.6.3 Identification of Unrestricted Features . . . . . . . . . . . . 144 7 Reconfiguration Prediction 147 7.1 Planning via Model Checking . . . . . . . . . . . . . . . . . . . . . . 149 7.1.1 Model Checking . . . . . . . . . . . . . . . . . . . . . . . . . 150 7.1.2 Reconfiguration Planning . . . . . . . . . . . . . . . . . . . . 152 7.2 Combining Costs and Probabilities of Reconfigurations . . . . . . . 153 7.2.1 Cost Model for Reconfigurations . . . . . . . . . . . . . . . . 154 7.2.2 Probabilistic Behavioral Model of Contextual Changes . . . 157 7.2.3 Probabilistic Weighted Automaton . . . . . . . . . . . . . . . 159 7.3 Reconfiguration Planning Algorithm . . . . . . . . . . . . . . . . . . 165 7.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 7.4.1 Comparison of Cost Prediction . . . . . . . . . . . . . . . . . 171 7.4.2 Length of a Contextual Run . . . . . . . . . . . . . . . . . . . 172 7.4.3 Possible Costs Savings across Contextual Changes . . . . . 173 7.4.4 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 IV Conclusions 175 8 Discussion of Related Work 177 8.1 Model-Based Runtime Adaptation . . . . . . . . . . . . . . . . . . . 177 8.2 Context Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.3 Refinement of Feature Models . . . . . . . . . . . . . . . . . . . . . . 182 8.4 (Re-)Configuration State Space . . . . . . . . . . . . . . . . . . . . . 182 8.5 Prediction and Planning of Adaptations . . . . . . . . . . . . . . . . 185 contents xv 9 Conclusions 189 9.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 9.2 Observations and Open Problems . . . . . . . . . . . . . . . . . . . . 192 9.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 9.4 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 B I B L I O G R A P H Y 197 Curriculum Vitae 211 L I S T O F F I G U R E S Figure 1.1 Amount of smartphones sold to customers worldwide from 2007 to 2013 according to Gartner [Gar14]. . . . . . . . . . . . 4 Figure 1.2 Percentage of smartphone operating systems and vendor specific customization in the U.S. in the second quarter of 2012 according to Nielsen [Nie14]. . . . . . . . . . . . . . . . . 6 Figure 1.3 Road-Map of this Thesis . . . . . . . . . . . . . . . . . . . . . 11 Figure 2.1 Adaptation Dimensions of Mobile Devices . . . . . . . . . . 15 Figure 2.2 Contextual Situations of a Mobile Devices . . . . . . . . . . . 15 Figure 2.3 Required Capabilities of a Smartphone at a Concert . . . . . 16 Figure 2.4 MAPE-K Feedback Loop [IBM06] . . . . . . . . . . . . . . . . 23 Figure 2.5 Software Product Line Engineering Approach [PBv05] . . . 29 Figure 2.6 Two Product Variations of a Smartphone . . . . . . . . . . . 30 Figure 2.7 Configuration of a Product Line . . . . . . . . . . . . . . . . 31 Figure 2.8 Syntactical Constructs of Feature Model Diagrams . . . . . . 33 Figure 2.9 Binary Cross-Tree Constraints between Features . . . . . . . 34 Figure 2.10 Google Nexus SPL . . . . . . . . . . . . . . . . . . . . . . . . 35 Figure 2.11 Product Configuration Google Nexus 4 . . . . . . . . . . . . 36 Figure 2.12 Feature Model Nexus DSPL . . . . . . . . . . . . . . . . . . . 39 Figure 2.13 DSPL Reconfiguration Sequence . . . . . . . . . . . . . . . . 40 Figure 3.1 MAPE-K Feedback Loop for DSPLs (adopted acc. [BHS12]) 47 Figure 3.2 Overview of a resource friendly DSPL adaptation method- ology. The main intention of this thesis is to establish an autonomous adaptation process based on a DSPL and to improve the resource consumption of a DSPL at runtime. The 9 techniques to realize these propositions are divided into three distinct stages in the life cycle of a DSPL, i.e., (i) Design Time, (ii) Deploy Preparation, and (iii) Runtime. . . 51 Figure 4.1 Extract of Nexus DSPL as a BDD . . . . . . . . . . . . . . . . 65 Figure 4.2 Mapping of Contexts to the Nexus DSPL . . . . . . . . . . . 75 Figure 5.1 Reduction Possibility of the Nexus DSPL Feature Model . . 82 Figure 5.2 Deployment of Device Specific Feature Models . . . . . . . . 84 Figure 5.3 Reduction Process for a context-aware DSPL . . . . . . . . . 88 Figure 5.4 Reduced Feature Model for the Nexus DSPL in Figure 4.2 . 90 Figure 5.5 Comparison of Average Computational Time . . . . . . . . . 93 Figure 5.6 Comparison of Average Number of Executed Operations . . 94 Figure 5.7 Comparison Memory Consumption during Reconfigurations 94 Figure 5.8 Break-Even Point Pre-Computation and On-Demand Re- configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 xvi List of Figures xvii Figure 6.1 Overview of the reduction of a DSPL configuration state space. The left-hand-side depicts a context-feature model specification at design-time, which is used to deploy a con- text-specific incomplete configuration state space on the de- vice. This state space is used to reconfigure the device at runtime based on changes in the contextual situation, as depicted on the right-hand side. Since the state space is in- complete, states may be unknown at runtime and have to be derived on-demand if the respective contextual situation emerges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Figure 6.2 On-Demand Configuration and Pre-Planned State Space . . 100 Figure 6.3 Example Configuration State . . . . . . . . . . . . . . . . . . 101 Figure 6.4 (Re-)Configuration in an SPL and DSPL . . . . . . . . . . . . 102 Figure 6.5 Context-Aware DSPL . . . . . . . . . . . . . . . . . . . . . . . 105 Figure 6.6 Configuration State for the Context Office . . . . . . . . . . 106 Figure 6.7 Context-Aware DSPL, Incomplete State Space . . . . . . . . 107 Figure 6.8 Strategies for Reconfiguration at Runtime . . . . . . . . . . . 109 Figure 6.9 Partial State Abstraction of four fully Configured States . . . 115 Figure 6.10 BDDs with Different Ordering of Variables . . . . . . . . . . 117 Figure 6.11 Overview of the identification of unrestricted variables. Dur- ing the deployment preparation, a feature model formula is transformed into a BDD representation. Based on a given partial configuration, the variables in the BDD are re-ordered several times to identify the configuration, contains the most unrestricted variables. This refined partial configu- ration is then integrated into the state space and deployed on the mobile device for a runtime reconfiguration. . . . . . 119 Figure 6.12 Variable Reordering According to Metric . . . . . . . . . . . 120 Figure 6.13 Computation of a Successor Generation Computed (adopted acc. [RN04]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Figure 6.14 The Modified Crossover of Variable Orderings (adopted acc. [ZBC96]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Figure 6.15 Reconfigurations in a Partial Kripke Structure . . . . . . . . 129 Figure 6.16 State Space Reduction Scaling across Number of Features . 138 Figure 6.17 State Space Reduction Scaling across Context-CTCR . . . . . 139 Figure 6.18 Presence of Unrestricted Feature Variables, Scaling across Number of Features . . . . . . . . . . . . . . . . . . . . . . . . 141 Figure 6.19 Presence of Unrestricted Context Variables, Scaling across Context-CTCR . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Figure 6.20 State Coverage at Runtime . . . . . . . . . . . . . . . . . . . . 143 Figure 6.21 Reconfiguration Ratio at Runtime with Partial States . . . . 143 Figure 6.22 Time To Discover Unrestricted Features Scaling across Size of fm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Figure 6.23 Discovery of Unrestricted Features Scaling across Size of fm 146 Figure 7.1 Reconfiguration based on Prediction of Contextual Changes 148 Figure 7.2 Reconfiguration Paths Explored by a Model Checker . . . . 151 Figure 7.3 Weighted Reconfiguration Automaton . . . . . . . . . . . . . 153 Figure 7.4 Probabilistic Contextual Automaton . . . . . . . . . . . . . . 157 Figure 7.5 Conceptual Life Cycle of the Planning Algorithm . . . . . . 165 Figure 7.6 PA Simulation Model . . . . . . . . . . . . . . . . . . . . . . . 170 Figure 7.7 Cost-Probability Distribution . . . . . . . . . . . . . . . . . . 171 Figure 7.8 Delta in Estimated Costs between c2 and c7 across m’ . . . . 172 Figure 7.9 Possible Cost Reduction Across Contextual Changes . . . . 173 L I S T O F TA B L E S Table 6.1 Power-Set 3-wise Context Combination . . . . . . . . . . . . 111 Table 7.1 Adaptation Sequence Without Prediction . . . . . . . . . . . 156 Table 7.2 Adaptation Path With Prediction . . . . . . . . . . . . . . . . 160 Table 7.3 Transition Matrix for WA Simulation Model . . . . . . . . . 170 xviii A C R O N Y M S AP Access Point BDD Binary Decision Diagram BGP Border Gateway Protocol cfm context-feature model representation as a propositional formula context-CTCR Context-Cross-Tree Constraint Ration CNF Conjunctive Normal Form CPU Central Processing Unit CTCR Cross-Tree-Constraint Ratio DSPL Dynamic Software Product Line fm feature model representation as a propositional formula FTP File Transfer Protocol GPS Global Positioning System GSM Global System for Mobile Communications HSDPA High Speed Downlink Packet Access IP Internet Protocol KS Kripke Structure LAR Location Aided Routing LTE Long Term Evolution Communication Protocol MAPE-K Monitor-Analyze-Plan-Execute-Knowledge PA Probabilistic Automaton PC Personal Computer PKS Partial Kripke Structure PWA Probabilistic-Weighted Automaton QMC Quine and Mc-Cluskey algorithm RC Research Challenge SAS Self-Adaptive Software System xx acronyms SCP Secure Copy Protocol SPL Software Product Line VoIP Voice over IP WA Weighted Automaton WLAN Wireless Local Area Network Part I I N T R O D U C T I O N & B A C K G R O U N D I n t r o d u c t i o n & F u n d a m e n t a l s 1 I N T R O D U C T I O N Software systems have to deal with a constant growth of information they have to process. Such software systems are present in the daily life of a person, be it a smartphone a person carries or a data-center that delivers the results for a web- search query. Every smartphone is equipped with a software system providing numerous functionalities to the user. The growth in the smartphone market also increases the demand to satisfy the requirements of each potential user for such software systems. For example, the plot in Figure 1.1 illustrates the importance and the growth of the mobile device market. In 2007 a total amount of 122.32 million smartphones were sold worldwide. Until 2013 the smartphone market increased by 800% to 967.78 million sold devices [Gar14]. The simultaneous increase of information and the integration of technology in our surroundings require new approaches for designing, implementing, execut- ing, and managing upcoming software systems for mobile devices. Such software systems have to be • adaptable in order to react on changes in their context at runtime, • configurable in order to satisfy the needs of a stakeholder at design time, • responsive in order to access certain functionality in real-time, and • energy-efficient in order to provide their functionality as long as possible. Highly dynamic systems increasingly exceed a level of complexity that is man- ageable by a person. This implies that the human effort to handle such systems, i.e., tasks such as setup, running, maintaining the system, increases with the com- plexity of the software system. For example, the market for android applications consists of 1.2 million applications1 that constitute a multitude of external ser- vices, e.g., an integration of Facebook, Skype, or several email accounts, for an optimal user experience. However, the more applications and services are be- ing integrated into a mobile device the higher is the demand for a simple us- age [BE01, CE10, FSSA06]. Self-adaptation is emerging as a necessary technique to manage the complex- ity in software systems [CLG+09]. Self-adaptive software systems are software systems that are able to adjust their behavior in response to their ever chang- ing requirements imposed by their contextual situation, e.g., their physical envi- ronment or by the software system itself. This is especially the case for highly dynamic systems such as context-aware or ubiquitous systems [Bro10]. 1 http://www.appbrain.com/stats/number-of-android-apps In t r o d u c t i o n & Fu n d a m e n t a l s 4 introduction Year 2007 2008 2009 2010 2011 2012 2013 Sold Smartpho 122,32 139,29 172,38 296,56 472 680,11 967,78 0 200 400 600 800 1.000 1.200 2007 2008 2009 2010 2011 2012 2013 Sold Smartphones in Million Units Figure 1.1: Amount of smartphones sold to customers worldwide from 2007 to 2013 ac- cording to Gartner [Gar14]. To tackle the issue of complexity in self-adaptive software systems, techniques from the domain of autonomous computing may be applied. Autonomous comput- ing [Hor01] describes systems that adapt without the need of human interaction. Thus, an autonomous system configures, adapts, and maintains itself at runtime. Autonomous Systems . Biological systems, such as the human nervous sys- tem, provided the guidelines for the concept of an autonomous system. The human nervous system acts autonomously to external or internal stimuli. For ex- ample, the size of our pupil adapts itself according to the current light intensity. If the human nervous system would not react autonomously a human would have to continuously concentrate on adapting the body to the environment. Autonomous software systems require appropriate abstractions and models for understanding, controlling, and designing the autonomous behavior, which is ex- ecuted at runtime. According to [CE10, CLG+09, Hor01], the issue of designing autonomous behavior constitutes an important research challenge. Understand- ing the problem and selecting a suitable solution requires precise models for rep- resenting important aspects of the self-adaptive system, its users, and its context. Furthermore, suitable software engineering methods are required to model im- portant aspects of a self-adaptive software system, such as controlling the adap- tivity of an autonomous system, the user behavior, and the requirements imposed by a contextual situation. Current software engineering approaches specify a sys- tem at design time in a static manner according to identified requirements as agreed with some stakeholders. Thus, the design of the system is derived prior to runtime and does not reflect the dynamic aspects, which occur at runtime. Since an adaptive system has to adjust its operational state at runtime, techniques to model autonomous behavior occurring at runtime are also considered to be an important research challenge [CE10, CLG+09]. Consequently, to develop autonomous self-adaptive software systems a soft- ware engineering approach is required that • abstracts from the complexity of an adaptive system and • is applicable to represent the dynamic aspects of an ever-changing context. I n t r o d u c t i o n & F u n d a m e n t a l s introduction 5 Among numerous techniques to tackle the challenges imposed by autonomous systems, Model Driven Development is an extensively investigated domain and has proven itself as a viable concept to abstract from the complex aspects of an (autonomous) self-adaptive software system. Model Driven Development. Model driven development [AK03, BG01, Voe11] is a software development methodology that intends to capture important aspects of a system through appropriate models. In this regard, model driven development focuses on modeling concepts rather than on computing or algo- rithmic concepts. The specified models are usable to automatically analyze the system. Therefore, model driven development techniques support key aspects for an autonomous adaptation. To execute an adaptation autonomously, the system requires knowledge as a semantic base, e.g., when an adaptation is to be exe- cuted and which system properties have to be adapted [IBM06]. The knowledge, which is required to derive an adaptation decision autonomously at runtime, is specifiable via model driven development concepts [BBF09]. Software Product Lines . Software Product Line Engineering is a domain that uses models to abstract from complexity imposed by large-scale software systems. Software Product Lines (SPLs) are a popular approach for the systematic reuse of software artifacts in development of a family of similar software systems instead of a single software system. Prominent SPLs are the Microsoft Office Suite or the Android operating system for mobile devices from Google. For example, the plot depicted in Figure 1.2 illustrates the vendor specific customization of the different operating systems for mobile devices, i.e., Android from Google and iOS from Apple. Android, as an SPL, is customized by different vendors. For example, 34% of the Android operating system deployed on mobile devices are customized by Samsung, 27% are customized by HTC, 21% are customized by Motorola, and 18% are customized by other remaining vendors [Nie14]. In contrast to that, iOS is not customized by any other vendor than the owning company Apple. SPLs offer a systematic reuse of software artifacts within a range of prod- ucts sharing a common set of features, i.e., units of functionality. For example, connectivity features, e.g., Long Term Evolution Communication Protocol (LTE), Global System for Mobile Communications (GSM), Wireless Local Area Net- work (WLAN), in the Android operating system are re-usable by vendors that develop a customized Android variant. Particular features may be considered for the entire SPL as not necessarily being part of each software product. In this regard, a feature constitutes • a product characteristic, i.e., a system property relevant for some stake- holder as identified during domain engineering, and • a product configuration parameter for deriving stakeholder-specific product variants [CW07]. In order to derive a specific software product of an SPL, features are selected to be either part of the product or they are deselected from the product [PBv05]. Such variability is specified via so called feature models. In t r o d u c t i o n & Fu n d a m e n t a l s 6 introduction Share of Smartphone Users Apple iOS 100% Samsung And 34% Costomized Software Product HTC Android 27% Standard Software Product Motorola Andr 21% Others Androi 18% Usage of Costomized Software Product Usage of Standard Software Product 0% 20% 40% 60% 80% 100% Apple iOS Samsung Android HTC Android Motorola Android Others Android Figure 1.2: Percentage of smartphone operating systems and vendor specific customiza- tion in the U.S. in the second quarter of 2012 according to Nielsen [Nie14]. Feature models provide a comprehensive formalism for specifying common- ality and variability among the different members of a family of similar soft- ware products organized in an SPL [KCH+90]. A feature model corresponds to a specification of feature constraints, i.e., dependency and incompatibility relations between features. For example, a routing protocol feature requires an Internet connection and a GSM-based connection may not be active in combination with a WLAN-based connection. For instance, vendors such as Samsung and HTC configure the Android oper- ating system as a customized product variant for their devices, e.g., the user inter- face on Samsung devices differs from the user interface of HTC devices. Hence, SPL techniques are used to abstract from complex aspects of a system, i.e., the variability of a product line, in a systematic manner. Therefore, these techniques seem to be a suitable approach to manage the runtime behavior of self-adaptive software systems. However, an SPL is used for systems that remain static in its composition of features at runtime. Prior to runtime, a software product is de- rived and once the product is derived it may not be further adjusted. In contrast to that, a self-adaptive software system needs to be continuously adjusted at runtime. Dynamic Software Product Lines . The engineering of Dynamic Soft- ware Product Lines (DSPLs) enhances SPL engineering by allowing a product to be not only configured once at design time. Instead, a DSPL supports flex- ible reconfigurations at runtime [BSBG08]. This enables a product implementa- tion to dynamically evolve and meet continuously changing requirements of the context [BHS12]. A promising field of application for DSPLs constitutes the vi- tal domain of adaptable mobile devices [HPS12] such as (Android) smartphones. For instance, if a flash-crowd of people emerges as a context at runtime, e.g., on a concert, a transition from a configuration relying on an infrastructure-based communication to a new configuration, which uses an ad hoc-based communica- tion might become necessary [ICP+99]. However, depending on the variability I n t r o d u c t i o n & F u n d a m e n t a l s 1.1 problem statement 7 constraints imposed on the system, such an adaptation may involve more than a single adjustment from infrastructure-based communication to an ad hoc-based communication. For example, both communication paradigms rely on different routing protocols, e.g., an infrastructure-based communication requires the Bor- der Gateway Protocol (BGP) [RLH06] and ad hoc-based communication requires a Location Aided Routing (LAR) protocol [KV00]. Such interdependencies be- tween features may become very complex and include a multitude of features, e.g., location aided routing requires the Global Positioning System (GPS) to be active. These constraints are specified in a feature model and are used as adapta- tion knowledge to derive a system reconfiguration that satisfies the ever changing requirements imposed by a contextual situation at runtime. In this regard, DSPL techniques are applicable to specify the runtime variability of a self-adaptive software system. However, to achieve an autonomous adapta- tion, a transition system may be used to specify when a reconfiguration is to be executed. Transition Systems . Another kind of model, which may be used to specify the adaptation behavior of an autonomous system, are transition systems. Recent research on DSPLs proposes model-based approaches for pre-planning reconfig- uration scenarios at design time. Those reconfiguration scenarios are specified as a transition system [Hel12, DPS12, WDSB09], which is deployed as adaptation knowledge on the device. Thereby, a state represents a device configuration and transitions specify reconfiguration options. Thus, a transition system models the reconfiguration behavior of a DSPL at runtime and further provides the means to analyze such reconfiguration behavior, e.g., identify deadlocks or configura- tions that may never be active at runtime. However, a complete transition system of a DSPL may become very complex since for every possible configuration the transition system contains the corresponding configuration state. For example, under the assumption that there are no constraints between features, a DSPL that consists of 20 features has 220 = 1, 048, 576 different possibilities to configure the DSPL. 1.1 Problem Statement I chose the domain of mobile devices as a candidate to validate my research. This domain is suited for variability modelling techniques due to the high degree of similarities among different systems. For example, a different product configu- ration of the Android operating system is required for each of the devices of the Goggle Nexus product line, e.g., the Nexus 4 smartphone, the Nexus 7 tablet etc. Further, mobile devices benefit from autonomous self-adaptive software systems since autonomy eases the usage of a device and improves the user experience. Note that, although I chose a particular application domain for my research, my research is not limited to the domain of mobile devices. To derive an autonomous self-adaptive software system on the basis of DSPLs, I identified the following four problem statements as important research issues. In t r o d u c t i o n & Fu n d a m e n t a l s 8 introduction (1) Context-Awareness of a DSPL. Existing DSPLs approaches do not yet support awareness of the contextual situation of the system. Without aware- ness the DSPL is not capable to autonomously reconfigure itself according to the ever changing contextual situations. To establish an autonomous self-adaptive software system based on a DSPL, such an awareness has to be established and seamlessly integrated into the modelling techniques of a DSPL [OGC12]. (2) Resource Consumption of a Reconfiguration at Runtime . Mo- bile devices have to cope with resource constraints that drastically restrict compu- tational runtime capabilities for complex reconfiguration planning and execution tasks [BHS12]. Existing approaches fail to handle context-aware adaptations of resource-constrained devices due to two reasons. First, it is not possible to deploy the complete configuration space [Hel12] of a complex system onto the device due to limited memory. Second, it is not possible to dynamically explore the configuration space on-demand [FFF+13] at runtime due to limited processing capabilities. Thus, neither a complete state space nor an on-demand reconfigu- ration is feasible for mobile devices, and it remains open how both approaches may be combined to leverage the benefits and mitigate the drawbacks of both approaches. (3) Flexibility at Runtime . Following DSPL techniques, every change in the configuration state of the system requires the derivation of a new product configuration w.r.t. the constraints specified in a feature model. Minor changes that occur at runtime change the operational state of the system. However, such minor changes do not necessarily require the derivation of a new product config- uration [HPS12]. For example, the reconfiguration from a GSM-based connection to a WLAN-based connection does not affect the configuration of completely in- dependent features such as the selection of a keyboard layout. Up to now, this issue has not been addressed. (4) Reduction of Operational Cost. Recent generations of mobile de- vices are very feature rich and, therefore, permit a multitude of possible con- figurations. Thereupon, reconfigurations at runtime allow those devices to con- tinuously adapt themselves to ever changing environmental context. For each change in the contextual situation of a device, there may be multiple configura- tions, which satisfy the requirements of a context. The operational cost of a self- -adaptive software system may be reduced by choosing the cheapest configuration. Since self-adaptive software systems are permanently executed, those configura- tions have to be chosen on a long-term basis to achieve a significant reduction of operational cost. However, to this end, it is unknown how such a configuration has to be chosen to reduce the operational cost at runtime on a long-term basis. Summarizing these research issues, this thesis aims to satisfy the goals of • establishing an autonomous, model-based adaptation process (G1) and • reducing the resource consumption of an adaptation at runtime (G2). I n t r o d u c t i o n & F u n d a m e n t a l s 1.2 contributions 9 The next Section introduces the contributions provided in this thesis to achieve the two goals G1 and G2. 1.2 Contributions My research shows that runtime adaptations are specifiable by leveraging variabil- ity models and transition systems at runtime as adaptation knowledge. According to my categorization of problem statements (1) to (4), I provide four fundamental contributions in this thesis. Formal Framework for Context-Aware DSPLs . In order to provide a model-based methodology to specify an autonomous self-adaptive software sys- tem I develop a formal framework and define (re-)configuration semantics of a DSPL. Therefore, I specify feature model constraints as propositional logic for- mula, as suggested in [Bat05, CW07], and extend it to be applicable to the domain of three-valued logics. However, in contrast to existing approaches, e.g., on con- text modelling [ACG09, LY04, BBH+10], contextual requirements are seamlessly integrated into the specification of a DSPL. In this regard, a context-feature model is introduced to autonomously reason about reconfiguration choices at runtime. This has the crucial benefit that traditional (D)SPL techniques are still applicable with my concept of a context-aware DSPL. Further, a context-feature model provides the means to automatically derive a transition system. Such a transition system allows to (i) specify the reconfigura- tion behavior in detail and (ii) analyze the reconfiguration behavior at runtime. Reduction of a Feature Model . As previously stated in the problem statements, applying DSPL-based methodologies to devices that are limited in their resources is a difficult task. Specifying constraints using a feature model requires a constraint solver to calculate a configuration that matches both the specified constraints and the requirements. The more features and constraints a feature model contains, the harder the computation of a configuration. Thus, every contextual change utilizes available resources, such as draining the battery. Therefore, I establish an approach to reduce a feature model specification w.r.t. the capabilities of a device. This improves the resource consumption of a DSPL oriented configuration process at runtime. To achieve such a reduction, I remove features that have to be permanently active at runtime, e.g., the display driver on a smartphone, or are incompatible to the capabilities of a device, e.g., features that rely on a cellular communication on a tablet that only supports WLAN. In contrast to existing approaches [ACLF11, RSA11], my approach focuses on maxi- mizing the amount of features that are reconfigurable at runtime. Context-Specific Reduction of the Configuration Space . A self- -adaptive software system for mobile devices has to be responsive and should consume as less resources as possible. Due to the memory consumption and uti- lization of computational resources, it is neither possible to deploy the complete configuration space onto the device nor to dynamically explore the configuration In t r o d u c t i o n & Fu n d a m e n t a l s 10 introduction space on-demand at runtime. To overcome the deficiencies of existing approaches, I apply my formal DSPL framework to establish techniques to reduce the config- uration space in addition to the reduction of a feature model specification. The reduction of a configuration state space is based on the observation that users of mobile devices move in certain well-known contextual patterns [JL10, MSRJ12, Ver09]. The design of the transition system for controlling reconfigu- rations allows for tailoring incomplete configuration state spaces on the basis of context-aware reduction criteria. This constitutes a trade-off between comprehen- sively pre-planned configurations and on-demand evolutions of the configuration space at runtime. In addition, relying on a partial Kripke Structure [BG99] as interpretation of a transition system allows the usage of partial states. A partial state is applicable to (i) further reduce the memory consumption by subsuming comparable configuration states as well as (ii) gain flexibility in the configuration states, thereby, avoiding unnecessary reconfigurations. Prediction of Contextual Changes . The well-established Planning as Model Checking paradigm provides a flexible, cost-sensitive approach for choosing among multiple reconfiguration options in a transition system. However, existing approaches [CRT98, GT00, PT01] lack (i) to combine fine-grained planning infor- mation comprising explicitly quantified cost models, e.g., for energy consumption and predicted contextual changes, and (ii) to cope with the limited resources of mobile devices. To tackle these drawbacks, a novel planning framework based on model checking techniques is proposed. Therefore, the transition system describ- ing reconfigurations is enriched with the probability for a reconfiguration to occur and cost of a reconfiguration. With such a model it is possible to determine re- configurations with minimum cost w.r.t. estimated long-term contextual changes emerging at runtime. 1.3 Outline Figure 1.3 shows the road-map of this thesis. The complete thesis consists of nine chapters. A brief variant highlighting the key concepts and contributions given in this thesis consists of three core chapters. The complete nine chapters provide a story-line as follows. Chapter 2. This chapter presents the fundamental concepts and state-of-the-art approaches on self-adaptive software systems, SPLs, and DSPLs. It provides the reader with a basis to understand the overall thesis. In addition to that, a running example is introduced, based on a Google Nexus product line. Chapter 3. The third chapter introduces how a DSPL and self-adaptive software systems are combinable. Further, the chapter provides a detailed overview on the contributions of this thesis. Chapter 4. This chapter introduces the fundamentals for my formal framework to specify an autonomous, context-aware DSPL. In this regard, the configuration semantics of a traditional SPL is stepwise extended to establish the configuration semantics of a context-aware DSPL. I n t r o d u c t i o n & F u n d a m e n t a l s 1.3 outline 11 Part I: Introduction & Background 1. Introduction 2. Self-Adaptation of Model-Based Software Systems Part II: Systematic Context Awareness 3. Concept and Contributions 4. Autonomous Adaptation based on DSPL Part III: Resource Constraint Runtime Adaptation 7. Reconfiguration Prediction 6. State Space Reduction 5. Reduction of a Feature Model Part III: Conclusions 8. Discussion and Related Work 9. Conclusions & Future Work Part Preface Background Contribution Remarks Complete Version Brief Version Figure 1.3: Road-Map of this Thesis Chapter 5. My first approach to reduce the computational efforts of a recon- figuration at runtime is introduced in the fifth chapter. To achieve such an im- provement, the variability specification of a DSPL is reduced according to the individual characteristics of a device. Chapter 6. In the sixth chapter my concept of a DSPL reconfiguration based on a transition system is introduced. Further, techniques to reduce the resource utilization of such a transition system are investigated. This chapter also inves- tigates possibilities to achieve a certain flexibility in the configuration states of a DSPL by using abstraction techniques. Chapter 7. My concept to reduce the operational cost of a DSPL-based self- -adaptive software system is discussed in the seventh chapter. This chapter briefly introduces Model Checking as a tool to predict the reconfiguration cost w.r.t. pos- sible upcoming contextual changes. Chapter 8. This chapter provides an overview on relevant approaches that have been proposed to support runtime reconfigurations. These approaches are classified according to the concepts and techniques introduced in Chapters 4 to 7. Chapter 9. The ninth Chapter concludes the thesis by critically discussing the results of the provided contributions. Further, future research topics are proposed to tackle the identified limitations of this thesis. I n t r o d u c t i o n & F u n d a m e n t a l s 2 S E L F - A D A P TAT I O N O F M O D E L - B A S E D S O F T WA R E S Y S T E M S This chapter introduces the background of this thesis. The focus of the first part is on the introduction of the application domain Self-Adaptive Software Systems (SAS). Starting with an overview of self-adaptation at runtime and how an adaptation is processed, related notions are explained and introduced based on a running example. SAS are used in numerous domains such as peer-to-peer or robotics. However, the focus of this thesis is an au- tonomous adaptation of mobile devices. The second part introduces a model-based approach to handle runtime adap- tivity, called Dynamic Software Product Lines (DSPLs). The concepts of a DSPL are based on the specification of variability constraints, which may be used to manage runtime-adaptations in a systematic manner. Therefore, an overview of DSPLs is given about their origin, which modeling concepts are commonly used to specify a DSPL, and how a DSPL processes a reconfiguration at runtime. Finally, open research issues in the domain DSPLs are pointed out. 2.1 Self Adaptive Software Systems The current explosion of information, technological progress, and distribution of software-intensive systems, leads to large-scale systems with an inherent de- gree of complexity. Especially the continuous growth [TYH+13] and development within the domain of mobile devices demand for innovative approaches for build- ing, running, and managing such software systems. A consequence is the need of a continuous evolution of the respective software. These systems have to become more versatile, flexible, resilient, dependable, robust, energy-efficient, recoverable, customizable, configurable, and self-optimizing. These aspects are achievable by an adaptation to the dynamically changing context, i.e., the environment or sys- tem characteristics [CLG+09]. Therefore, the domain of Self-Adaptive Software Systems (SAS) deals with the development of systems, which are able to adjust their behavior in response to an ever changing context. “Whenever the system’s context changes the system has to decide whether it needs to adapt. [. . . ] we consider context as any informa- tion, which is computationally accessible and upon which behavioral variations depend.” [CLG+09] In t r o d u c t i o n & Fu n d a m e n t a l s 14 self-adaptation of model-based software systems This quotation includes the key aspect of SAS and also provides a definition of a context. SAS have to cope with the inherent dynamics of their context. To satisfy certain specifications and goals, SAS adapt themselves accordingly, whenever the context changes and requirements are violated. In this thesis, a context describes information, which are computationally accessible, such as derived information about the environment, e.g., office-location or rainy-day, about the users, e.g., listing to music or reading mail, and about the system itself, e.g., low-battery or silent-mode. To satisfy stated goals the SAS has to be flexible and derive a suitable adaptation from this contextual information. Self-adaptation is an important research topic in several application domains, such as autonomic computing, dependable computing, embedded systems, mo- bile ad-hoc networks, mobile and autonomous robots, multi-agent systems, peer- to-peer applications, sensor networks, and service-oriented architecture [Bro10]. In all these domains flexibility at runtime is essential. However, little endeavor has been made to establish a systematic software engineering approach to handle the inherent dynamics at runtime [CLG+09]. In the following an overview and classification for self-adaptive software sys- tems is given. Additionally, the paradigm Monitor-Analyze-Plan-Execute-Know- ledge (MAPE-K) is introduced as a control loop to regulate SAS. Thereupon, re- search challenges that are addressed in this thesis and limitations of this thesis are discussed. 2.1.1 Adaptivity in Mobile Devices As mobile devices, e.g., smartphones, tablets, or notebooks, become more and more integrated into the everyday living of a person, mobile devices are exposed to continuous changes in their environmental context. This is especially the case for smartphones, because most people have their smartphone with them when they are mobile and change their location. Naturally, every device is differently constrained in its capabilities due to its mobility, production costs, and user-spe- cific requirements, e.g., lightweightness. Thus, it depends on the capabilities of a smartphone how the contextual environment may be exploited, e.g., a WLAN chip has to be integrated in the device to connect to a WLAN access point in the contextual environment. However, the capabilities of a smartphone may change over time, e.g., the battery is continuously drained at runtime or the device may be upgraded. An additional category, which influences the adaptation of a smart- phone, are the activities the user imposes on the device itself, i.e., the usage of the device. Every contextual category states certain requirements and together they restrict the possibilities in which a device is able to adapt itself. As depicted in Figure 2.1, if the user sits at home, is reading an eBook, and the smartphone reaches a low battery threshold, the device has to find a suitable configuration within the highlighted plane that satisfies all contexts. Note that the contextual categorization location, device, activities is a matter of granularity. Therefore, additional contextual categories are imaginable, e.g., network, service, quality, or social context [PNS+00, RDN06]. I n t r o d u c t i o n & F u n d a m e n t a l s 2.1 self adaptive software systems 15 Activity Location Device Home Reading Full Battery Figure 2.1: Adaptation Dimensions of Mobile Devices Location. Depending on the contextual location, smartphones provide the means to access a large variety of available ubiquitous services. In recent years, the availability of these ubiquitous and mobile services have significantly in- creased due to the different form of connectivity provided by mobile devices, e.g., WLAN access points, cellular networks, or GPS navigation [Yan12]. To provide an optimum of service functionality smartphones have to exploit their surrounding environment, e.g., using a WLAN connection if an access point is available. Thus, a smartphone has to cope with the mobility of its user. Figure 2.2 depicts this problem. A user expects different functionality or services, i.e., goals, depending on the contextual situation of the smartphone. Figure 2.2: Contextual Situations of a Mobile Devices Example 2.1 (Impact of Mobility on a Smartphone). Figure 2.2 depicts several contextual situations and in each situation the user expects different functionality or a different behavior. If the smartphone is con- nected to a desktop Personal Computer (PC) the smartphones becomes an external hard drive. An example for a very location sensitive situation is driving in a car, where the smartphone becomes a navigation device. Thus, the goal of a In t r o d u c t i o n & Fu n d a m e n t a l s 16 self-adaptation of model-based software systems smartphone may change in different contextual situations. An example for a cost-optimization is the change of situation where the user is within the area of a WLAN access point, e.g., at home, or all communication is processed via a cellular network. Another requirement emerges if the user is in his office, where he has to be able to receive and send emails. A mobility pattern of the user may be as follows on a working day: “home → car → office → car → home → couch → desktop PC”. However, such a mo- bility pattern on a weekend day will most likely be very different and include different contextual situations, e.g. going to a concert. This example shows that mobile devices, and especially smartphones, are exposed to continuous changes of contextual situations. These situations occur based on certain mobility patterns of the individual user. Device Capabilities . A smartphone is only able to access numerous ubiq- uitous services, which are provided by a certain environment according to its own capabilities. These capabilities are either static or change over the lifetime of the device. The Central Processing Unit (CPU) of a smartphone is an example for a static capability, whereas the battery load and available storage space are continuously changing at runtime. Figure 2.3: Required Capabilities of a Smartphone at a Concert Example 2.2 (Capabilities of a Smartphone). According to Figure 2.2 a user wants to take pictures and probably publish them via a social network if he is on a concert. However, this is only possible if the smartphone is able to satisfy the requirements (i) the smartphone has a camera integrated to take a picture, (ii) the smartphone supports the avail- able communication standard, e.g., WLAN, GSM, or LTE, to share the pictures, (iii) there is enough storage space available to store the pictures, and (iv) the smartphone has sufficient energy resources available to execute the tasks. User Activity. Independent of the external contextual environment of a smart- phone the user may request certain functionality or services on-demand. In this I n t r o d u c t i o n & F u n d a m e n t a l s 2.1 self adaptive software systems 17 case, the smartphone has to respond accordingly and provide the functionality or service according to its capabilities and external ubiquitous services. Example 2.3 (Usage Impact on a Smartphone). If the user wants to do some on-line shopping, a connection to the Internet has to be established. However, depending on the contextual environment and local capabilities, a connection is establishable in different ways, e.g., via LTE or WLAN. Depending on the user preferences, the smartphone has to choose between the available connection types, e.g., if the user prefers a cheaper connection, the smartphone would choose WLAN instead of LTE. Summarizing, independent from the mobility patterns of a user, the device is only able to adapt according to its capabilities. The expectations of a user, i.e. the requirements, depend on the environment and ubiquitous services or interfaces, which are provided. If there is a change in the context of the smartphone, the intentional goal of the smartphone may also change, e.g., the smartphone becomes an external hard drive if it is connected to a PC and it becomes a camera if the user is at a concert. Thus, to optimize the convenience of a user, smartphones have to change, i.e. adapt, themselves automatically to satisfy user-specific and context-specific requirements. This overview shows that mobile devices, such as smartphones, are self-adap- tive software systems. The next section provides detailed insights into the overall adaptation process of SAS by describing key technical aspects and characteristics of these systems. 2.1.2 Classification of Self-Adaptive Software Systems The application of a self-adaptation depends on various aspects, e.g. the chang- ing needs of a user, environmental characteristics, and system properties. Under- standing the problem and selecting suitable solutions require precise models to represent environment, users, and the system [CLG+09]. This section introduces a classification scheme taken from [CLG+09, ALMW09] to describe the most im- portant facets of SAS. The classification is divided into the four groups (i) goal of an adaptation, (ii) cause of a change, (iii) adaptation mechanism, and (iv) effects of an adaptation. Goals . Goals are objectives the system has to achieve or constraints that have to hold at runtime [LLYM06]. Such goals may be functional, e.g., “activate GPS during a navigation process”, or non-functional, e.g., “response time for a GPS signal has to be below 2 seconds”. Existing approaches, e.g., goal models [LY04], propose to use quantifiers and hierarchical decomposition into sub-goals to model complex goal structures for SAS. An example goal for mobile devices may be “always provide a connection to the Internet” and a sub-goal may be “prefer WLAN-connection to a cellular-connection”. Important aspects for goals of an SAS are • Evolution. Depending on the context of a device the goal specification of a system may change dynamically at runtime. However, the specification of a In t r o d u c t i o n & Fu n d a m e n t a l s 18 self-adaptation of model-based software systems goal may also change in a static manner at design time if the SAS is changed, e.g., goals are exchanged during a system update. • Flexibility. Goals do not necessarily specify a rigid system but may be also flexible. The more rigged a goal is the less system configurations are available, which satisfy the requirements of that goal. In that manner, a goal may be rigid, constrained, or unconstrained. A flexible goal is able to handle contextual situations, which are not specified explicitly at runtime. • Dependency. If a system has to meet multiple goals, these potential goals may be related to each other. Thus, goals may be complementary or conflict- ing to each other. Alternatively, they may also be independent from other goals, i.e., they do not affect each other. Example 2.4 (Goals of SAS). The goal “activate flash at night when camera is active” is the static initial specifi- cation of a goal at design time. At runtime, this goal becomes active whenever the user activates the camera during a concert and, therefore, photos are taken with flash. With an update a new filter is deployed on the SAS and with the filter also the goal changes to “activate dark-filter at night when camera is active”. A dynamic evolution of a goal occurs at runtime. For example, a goal states “use GPS during navigation”. Whenever the smartphone realizes that a GPS sig- nal is not accurate and localization is more precise with an additional cellular triangulation, the goal is updated dynamically at runtime to “use GPS and cel- lular triangulation during navigation”. The goal “activate dark-filter at night when camera is active” is flexible because it still supports dynamic adaptations. For example, there are no restrictions regarding using flash or GPS while taking a photo. The less requirements a goal specifies the more flexibility is provided to handle additional or even unknown contexts, emerging at runtime. The goals “use GPS during navigation” and “activate flash at night when cam- era is active” are independent of each other. However, the goal “deactivate all communication signals at night” contradicts the goal “use GPS during navigation”, which implies that a smartphone may not be used to navigate at night. Change . An adaptation is triggered by changes in the context of a device. If the context changes the requirements for the device also change. Thus, the system has to adapt itself accordingly to re-satisfy the new requirements. To plan a suitable adaptation, information on location, type, and frequency of a change, is important to anticipate the occurrence of a change. • Source. A change may occur external to the device, i.e., within the environ- ment, or internal within the device, i.e., within the system. Internal changes are investigateable in more detail, whereas the detection of external changes relies on the information of sensors. I n t r o d u c t i o n & F u n d a m e n t a l s 2.1 self adaptive software systems 19 • Type. The type of the requirement change is either functional, i.e., a func- tionality is required or prohibited, or non-functional, i.e., a the system has to satisfy a certain level of quality. • Frequency. The frequency of a change determines the number of changes over a certain period. The scale may range from once a week over several times per minute to numerous times per second. • Anticipation. Adaptations are predictable. Such predictions may be used to pro-actively prepare an adaptation. However, different adaptation strategies are necessary, depending on the degree of anticipation. If an adaptation is foreseeable, the adaptation is still uncertain, though likely to occur. There- fore, the system has to plan and reason about such an adaptation. In contrast to that, an adaptation may also be unforeseeable, i.e., unknown or sponta- neously occurring, in which case the system is not able to plan an according adaption [JL10]. Example 2.5 (Change in SAS). An example for an external trigger to adapt the system is the movement of the user. If the user leaves the context of his home and enters the context of his car, the smartphone adapts itself by deactivating WLAN and activating GPS and the navigation system. An example for an internal trigger to adapt the system is the remaining amount of energy left in the battery. If the remaining energy is low, all media related applications are closed and are prevented to be opened. A functional goal refers to provided services or functionality of the system. An example for a functional goal is “deactivate WLAN connection in a car”. In contrast to that refers a non-functional goal to the qualitative aspects of a system. For example, the goal “the responsiveness has to be below 1 second” is a qualitative aspect of a connection. On a standard working day the user enters and leaves his office once, thus the frequency of these changes is once a day. If the user has a repeating mobility-pattern, an adaptation may be anticipated. For example, if the user always follows the pattern “home → car → office → car → home” the smartphone is able to predict the according adaptations with a certain probability. In that example, the smartphone prepares the adaptation to the context car if the user is still in the context home. However, if there is an unforeseeable event and the car of the user breaks down, the mobility pattern changes, e.g., “home→ car→ street”, and the smartphone has to adapt whenever the unforeseen contextual change occurs. Mechanism . The implemented mechanisms capture the reaction of a system towards a change. Therefore, the adaptation mechanism represents the core of an adaptation process. Adaptation mechanisms cover different levels of autonomy and there are several different possibilities to control an adaptation. Additionally, the impact of an adaptation mechanism has to be considered. In t r o d u c t i o n & Fu n d a m e n t a l s 20 self-adaptation of model-based software systems • Type. An adaptation is related to either changing the parameter configu- ration of the system or to changing the structure of the active system im- plementation, i.e., exchanging or rewiring its components. Therefore, an adaptation is either structural, parametric, or a combination of both. • Autonomy. Existing terminology states that an adaptation is either executed autonomous, assisted, or autonomic. An autonomous adaptation process is executed without external influences, besides the contextual information. An assisted adaptation is executed with the support of an external user, e.g., if an adaptation is not executable automatically. Autonomic adaptations are also executable without any external influence. In addition to autonomous adaptations, an autonomic adaptation process is able to learn and to derive new adaptation strategies dynamically at runtime [SSH06]. • Organization. Adaptations are either executed centralized on a single sys- tem, or are distributed over several interacting systems, e.g. peer-to-peer systems, in a decentralized manner. A decentralized adaptation is not con- trolled by a single component or system. Instead, decisions have to be made collaboratively in a network of systems. Similarly, an adaptation is either re- stricted to local adaptations, i.e., one single system, or to global adaptations, i.e., within a network of systems. • Duration. Depending on the domain, the duration of an adaptation may be a critical aspect to deal with. An adaptation may last from milliseconds up to several hours. However, this characteristic has to be considered relative to the application domain. Example 2.6 (Adaptation Mechanisms of SAS). If a smartphone is connected to a desktop PC, the smartphone becomes an ex- ternal harddisk. This is an example for a structural adaptation because a specific driver is activated on the smartphone to turn it into an external harddisk. If the smartphone has to adapt to a silent mode, the ringtone and other notification signals become silent. This is an example for a parametric adaptation because the volume parameter is adjusted to zero. An example for an assisted adaptation is the manual selection of the user to communicate via WLAN instead of LTE. In this case, the adaptation is man- ually triggered and requirements are specified by the input of the user. The automatic activation of GPS and starting of the navigation system whenever the user enters a car is an example for an autonomous adaptation. In this case, the smartphone adapts itself automatically based on the contextual information. If the smartphone recognizes that a connection via LTE is better, e.g., more re- sponsive, than a connection via GSM and triggers an adaptation for this reason, the smartphone is capable for autonomic adaptations. In this case, the smart- phone is able to learn and optimize the overall adaptation process by changing adaptation goals or creating new adaptation goals on its own. Until this point of this thesis, the given examples for an adaptation are in- tended for a single systems, i.e., centralized on a single smartphone. However, if I n t r o d u c t i o n & F u n d a m e n t a l s 2.1 self adaptive software systems 21 data has to be exchanged between two smartphones, the smartphones have to reason about the protocol, e.g., Secure Copy Protocol (SCP) or File Transfer Pro- tocol (FTP), and type of communication, e.g. Bluetooth or WLAN. They have to agree on one single solution within the capabilities of both devices. This is an example for a decentralized adaptation because the adaptation has to be or- ganized between the participating smartphones without a central smartphone that makes a decision. Starting the navigation system of a smartphone after arriving in a new coun- try may trigger the download of the required street maps to perform a valid adaptation. In this case the adaptation may last for several minutes or hours, depending on the available connection and the amount of data. Although this is not safety critical, e.g., it does not lead to a traffic accident, it may lead to inconvenience if the user is impatient. Effects . Every adaptation has an impact on the system it adapts. While the mechanism category deals with the adaptation itself, the listed effects are associ- ated to the overall SAS, for which the adaptation is performed. • Criticality. The criticality of adaptations describes the impact of erroneous adaptations. This ranges from harmless to goal-critical or safety-critical. • Predictability. Another important aspect are effects of an adaptation on the system and whether they are foreseeable. An adaptation may perform as expected, in which case guarantees may be specified. However, an adap- tation may further perform differently each time it is executed, e.g, if the adaptation is flexible regarding the result. In that case, only limited or none guarantees are specifiable. • Overhead. The overhead deals with the additional negative impacts on the overall system performance during an adaptation. An adaptation constantly has to be non-intrusive to the system and, therefore, should always consume a minimal amount of memory and computational power [MRD08]. In the worst case, an intrusive adaptation leads to thrashing and, thereby, a system ceases to provide its services [BMSG+09]. Example 2.7 (Adaptation Effects on SAS). The adaptation “activate the navigation system” fails if the smartphone has not enough battery available to support GPS and the navigation. In that case the adaptation fails to complete. The failing of this adaptation is non-critical if the user is not yet driving. However, if such an adaptation fails while the user is driving his car and depends on the navigation system, a failure becomes more critical because it distracts the user. The adaptation for the contextual requirement “deactivate all communication signals at night” results always in the same system configuration where all com- munication related aspects of the smartphone are deactivated. The more flexi- ble requirement for the contextual requirement “activate dark-filter at night when camera is active” may not always lead to the same system configuration. The In t r o d u c t i o n & Fu n d a m e n t a l s 22 self-adaptation of model-based software systems requirement specifies no restrictions regarding the activation of additional fil- ters, such as a black-white filter. Therefore, one adaptation may activate the black-white filter and the next adaptation for that context may not activate that filter. In that case, the effects of the adaptation are not foreseeable. Every adaptation consumes resources. For example, every context has to be identified, e.g., by using the sensors of the smartphone to identify if the user enters a car. Thereupon, the adaptation mechanism has to compute, which changes are to be made and how the requirements are to be satisfied, e.g., GPS has to be activated and the navigation system has to be loaded. Finally, the adaptation has to be executed, e.g., GPS is being activated and the navigation system is being loaded. The more resources such an adaptation consumes, the more overhead it generates. If the adaptation consumes most of the available resources, other services, e.g., receiving emails, may be suspended. The adaptation aspects of goals, change, mechanism, and effects are used to describe and to evaluate the capabilities of an SAS. Although this classification provides a holistic overview of the concept behind SAS the matter of a technical implemen- tation is still unaddressed. Therefore, the Monitor-Analyze-Plan-Execute-Knowl- edge (MAPE-K) paradigm is introduced in the next section, as a common ap- proach to handle the inherent dynamics of mobile devices at runtime. 2.1.3 The MAPE-K Feedback Loop The decisions when, what, and how to adapt a mobile device have to be made by the SAS at runtime to cope with dynamic behavior of a user. To facilitate system- atic control of the adaptation process, the system continuously reasons about its contextual situation. For example, a mobile device collects contextual information, e.g., its geographical location and available connection types, to reason about how to establish a connection to the Internet in this contextual situation. Feedback loops are a common paradigm to facilitate an adaptation process at runtime in a coordinated, reliable manner [BMSG+09, CLG+09]. The feedback enables a static or dynamic evolution of the system and is used to optimize the adaptation behavior. Positive feedback occurs when an initial change in a system is reinforced. In contrast, negative feedback triggers a response that counteracts an executed decision. Example 2.8 (Positive and Negative Feedback). According to some non-functional requirement, the connection with the best throughput is to be preferred. Initially starting with a HSDPA connection, the smartphone continuously checks for other connection types. If GSM becomes available, the smartphone tests this connection type as an alternative. Since GSM has a lower throughput than HSDPA, the adaptation process emits a neg- ative feedback for that decision. The same happens if LTE becomes available. In contrast to GSM, the adaptation process emits a positive feedback because the throughput via LTE is higher than via HSDPA. Therefore, the system is going to prefer LTE over HSDPA automatically in upcoming adaptation decisions. I n t r o d u c t i o n & F u n d a m e n t a l s 2.1 self adaptive software systems 23 The basic principle of such feedback loops is a refinement of the sense-plan-act approach used in the AI community [Nil80]. With a feedback loop the adaptation process may become completely autonomous. The first concrete architecture of a feedback loop for autonomous SAS was introduced in a blueprint of IBM [IBM06]. This feedback loop is depicted in Figure 2.4. The loop facilitates a controlled autonomous adaptation by executing the four tasks (i) monitor, (ii) analyze, (iii) plan, and (iv) execute. These tasks share a common knowledge basis. This approach is commonly known as the MAPE-K loop. Infor- mation Change RequestFeedback Know- ledge Change Plan Figure 2.4: MAPE-K Feedback Loop [IBM06] Monitoring . The monitoring task is responsible for capturing basic informa- tion of the contextual situation, e.g., via sensor data. This information is corre- lated to specific aspects, e.g., the current location and available connection types. Such information includes network topology information, property settings, sta- tus of resources, offered capacities, and throughput. The information is either static or the information is highly dynamic and continuously changes over run- time. A monitor aggregates this information, e.g., for a better information scal- ability [SGS13] in a large decentralized network of smartphones. Thereafter the information is filtered to the most relevant aspects for an adaptation before pass- ing them to the analyze task. For example, assume that in a contextual situation only the location and throughput are of relevance. In that case, the information about responsiveness and lighting conditions are discarded. Analyze . The analysis of the monitoring information provides the means to recognize contextual situations and to derive higher order information. Based on the analysis of that data a decision is met whether an adaptation is necessary or not. The gathered monitoring information about the current contextual situation is correlated to the requirements a context imposes on the system. For example, if the context office becomes active, the analysis task checks if the requirement “able to send and receive email” is already satisfied with the current system configura- In t r o d u c t i o n & Fu n d a m e n t a l s 24 self-adaptation of model-based software systems tion or if an adaptation is necessary. Additionally, the adaptation behavior may be analyzed to employ prediction techniques to plan and prepare for upcoming adaptations. Therefore, the device has to be able to learn about contextual situ- ations and the adaptation behavior executed on the device. If the requirements change due to a change in the contextual situation, the analyze task passes an according change request to the plan task. Plan. The plan task derives a procedure to execute a desired adaptation of the system to satisfy the imposed requirements. An adaptation procedure may range from a single command, e.g., “activate WLAN”, to a complex adaptation sequence, e.g., “activate WLAN”, “deactivate GPS”, and “set ringtone volume to 0”. Further- more, the planning is driven by specific goals, i.e., functional or non-functional requirements, when an adaptation plan is derived. This ranges from a problem solution, i.e., satisfying all requirements and goals, to a complex optimization pro- cess to derive the best system configuration for a contextual situation. The derived change plan is passed to the execute task to apply all changes and reconfigure the system at runtime transparently. Execute . In the execution task, suitable methods and mechanisms are sched- uled to perform the changes in the current system configuration. These changes may range from parameter changes, e.g., ringtone volume, to the exchange of components or code fragments, e.g., discarding email notification component or changing the keyboard component from English to the German. The execute task is responsible for carrying out these changes within a running system in an ordered sequence of non-conflicting tasks. Knowledge Basis . The four tasks monitor, analyze, plan, and execute share a common knowledge model. This knowledge includes specifications or profiled in- formation required by the adaptation process. For example, the knowledge model includes contextual information, adaptation behavior profiles, monitoring metrics, adaptation policies, as well as system capabilities. The specified knowledge is ei- ther explicitly specified, i.e., everything that may happen is covered within the model, or implicitly specified, i.e., uncertain or unknown behavior may occur at runtime, which is not covered within the model. The knowledge model is imple- mented as a registry, dictionary, database, or any other repository that provides access to knowledge according to the interfaces prescribed by the architecture. The knowledge is obtainable in three ways [IBM06]. 1. Knowledge is a-priori specified at design time and deployed on the system locally before runtime, 2. the knowledge is continuously retrieved from an external knowledge source, e.g., an external database in the Internet, or 3. the adaptation process itself generates knowledge, e.g., leveraging moni- toring information, planning decisions, and profiles of contextual changes. This information is either used to continuously update or extend existing knowledge at runtime. I n t r o d u c t i o n & F u n d a m e n t a l s 2.1 self adaptive software systems 25 The knowledge is representable via three different types [IBM06]. • Solution Topology Knowledge. Captured knowledge about components and their architecture, e.g., dependencies between components such as nav- igation system requires GPS. • Policy Knowledge. A policy is knowledge that is used to decide whether an adaptation is necessary and which changes have to be applied. Thus, a policy corresponds to a set of constraints or preferences that influence the analyze task and planning task. • Problem Determination Knowledge. Problem determination knowledge includes monitored data, symptoms and decision trees. This knowledge is used to further derive or update existing knowledge at runtime, i.e., via learning algorithms or profiling. The main part of this thesis is focused on the plan task based on a knowledge model. Relation to the other tasks of monitoring, analyze, and execute are pointed out, but it is assumed that these tasks are provided as a black-box. The next section points out research challenges that are addressed in this thesis. 2.1.4 Research Challenges in SAS The domain of SAS provides numerous challenges still to be faced in research. Therefore, this section lists specific challenges for SAS in the domain of mobile de- vices, which are addressed in the remainder of this thesis. The scope of this thesis is restricted by the introduction of certain limitations and assumptions. Therefore, the Research Challenges (RCs) of (i) a systematic engineering, (ii) flexibility at runtime, (iii) autonomy, and (iv) intrusiveness are introduced in the following. RC1: Systematic Engineering . “A major challenge [. . . in the development of adaptation mecha- nisms . . . ] is to accommodate a systematic engineering approach that integrates control-loop approaches with decentralized agent inspired approaches.” [CLG+09] This quotation highlights the importance of a systematic engineering approach for SAS. This implies a consistent development methodology from requirement engineering, e.g., goal modelling, over an a-priori specification of the common knowledge basis, e.g., policies to describe the adaptation behavior, to the con- tinuous update and extension of this knowledge at runtime. Since the usage of a feedback loop, i.e., MAPE-K, is state of the art to control SAS, a systematic engineering approach has to be integratable into such a loop. Although this quo- tation highlights the importance of a decentralized applicability, this issue is not addressed further in the remainder of this thesis. In t r o d u c t i o n & Fu n d a m e n t a l s 26 self-adaptation of model-based software systems RC2: Flexibility at Runtime . To cope with the dynamically changing contexts, an adaptation is specified explicitly or implicitly. In an explicit speci- fication all adaptation possibilities are assumed to be known and integrated into the knowledge model. For example, an explicit specification covers all contextual situations depicted in Figure 2.2. Therefore, a mobile device is capable to adapt to all these contextual situations. However, if a new contextual situation emerges at runtime, e.g., entering an airplane or combining two existing contexts such as home and couch, the mobile device is not able to adapt to this context on its own. In contrast, an implicit specification is an incomplete specification and intends to cover a basic set of contextual situations with the ability to extend and update the knowledge at runtime. For example, the contextual situations home and couch are specified individually. If the specification is implicit, the mobile device is able to adapt to a combination of both situations either completely autonomous or with the assistance of the user. Hence, such a specification is more flexible and open to new contextual situations, emerging at runtime. However, the result of such an adaptation that is derived on-demand at runtime is not always predictable. An important research issue is to provide certain flexibility within the adaptation process to cope with unknown contextual situations [BMSG+09]. At the same time an adaptation has to be reliable and foreseeable [ALMW09], i.e., such that an adaptation exposes always the same behavior. RC3: Autonomous Adaptation. An autonomous adaptation implies a process without any interaction with external actors, e.g., a user or developer. Therefore, the adaptation process has to evaluate the context and derive neces- sary adaptation strategies on its own [SSH06]. Especially for mobile devices the user experience is of importance. Hence, an adaptation of a mobile device should not bother the user. The adaptation has to be executed automatically and should be transparent to the user [Har06]. RC4: Non-intrusive Adaptation. “In highly dynamic systems, e.g., mobile systems, where the envi- ronmental parameters change frequently, the overhead of adaptation due to frequent changes in the system could be so high that the sys- tem ends up in thrashing. [However, . . . ] responsiveness is a crucial property in real-time software systems [. . . ]" [CLG+09] This quotation refers to the effects an adaptation process imposes on the system. The more resources are utilized within any of the MAPE-K tasks, the more likely the system starts thrashing up to the point of a complete system failure. Although these effects are mitigated by scaling the hardware resources of the system, e.g., more memory, bigger CPU, etc., such a solution is either costly or infeasible. Es- pecially mobile devices are constrained in their resources, i.e., the battery will be drained eventually. Thus, SAS for mobile devices have to operate resource-effi- cient to cope with the high frequency of dynamic contextual changes. RC5: Predictability of Adaptations . A prediction of contextual changes may be used to optimize the adaptation process, e.g, by pre-computing an adap- I n t r o d u c t i o n & F u n d a m e n t a l s 2.2 software product line engineering 27 tation or by harmonizing a sequence of adaptations. However, a prediction of an adaptation or a sequence of adaptations for a mobile device is complicated due to the broad spectrum of contextual situations and the spontaneous, unforeseeable behavior of a user [MSRJ12]. Limitations and Assumptions . In the remainder of this thesis I address the research challenges RC1 to RC5 with a specific focus on the plan task based on a common knowledge model. Note that the approach is designed to operate on resource constrained devices, i.e., mobile devices. In this regard, I neglect details about the monitoring, analyze, and execute tasks of MAPE-K but assume them as a provided black-box, which is accessible to retrieve certain information or execute certain tasks. Hence, I also do not explicitly address intersecting topics, e.g., con- text reasoning, dynamic class loading, feedback evaluation, and information correlation. Mobile devices are heterogeneous in their characteristics, e.g., one device sup- ports LTE whereas another device does not. To handle such heterogeneity in a systematic manner, software product lines are used. The next section introduces the domain of software product line engineering. Furthermore, an extension of software product line engineering is introduced that focuses on the systematic management of runtime adaptations. 2.2 Software Product Line Engineering In traditional software engineering a software system was typically not regarded as being variable. Either each software system was developed for the needs of the customer individually or the customer bought a software system with all possible features. Since the implemented code of a software system is easy and cheap to copy, transport, and replace, a structured development process for similar soft- ware systems seemed not to be necessary. However, in recent years the situation in software engineering has changed. The complexity of software systems are more and more exceeding the limits of what is feasible to handle with traditional software engineering approaches [PBv05]. In a highly competitive and segmented market, such as the mobile device in- dustry, mass production is not enough anymore and mass customization of the respective software systems is due to become a must for market success [BSRC10, Par76]. An example for this is the vendor specific Android operating system. Mass customization aims to meet as many individual needs of a customer as pos- sible. In addition to that, the mass production has to be as efficient as possible. To maintain efficiency during the production, practitioners propose to build prod- ucts from existing assets that share more commonalities than singularities. These assets, i.e., features of a product, have to be flexible in the common sense of vari- able to be reused in other software products in the same product line. This means that, for a structured engineering process of software product lines, features have to be identified and to which extent they differ, fulfill the same requirements, or share a similar underlying architecture. Clement elevated Software Product Line (SPL) engineering to a dominant devel- opment paradigm [Cle99]. The goal of an SPL engineering process is to maximize In t r o d u c t i o n & Fu n d a m e n t a l s 28 self-adaptation of model-based software systems the reuse of software artifacts within the range of products sharing a common set of software characteristics [Bos01, CN01, PBv05]. SPLs are intended for the devel- opment of domain specific software products, which are individually tailored for the individual needs or problem statement of a customer based on the variability of a software system. The SPL concept is based on the idea to combine the advan- tages of custom tailored software and commercial off-the-shelf software. Custom developed software are intended to solve a specific problem. Usually, developing such software is expensive since the software is intended for a broad market. In contrast to customized software, off-the-shelf software is intended for a wide area of domains used by a broad spectrum of users. Example 2.9 (Software Product Lines). Commercial examples for software product lines are the Android Operating System for mobile devices or the Office suite from Microsoft Windows. SPLs intend to develop software products for a certain domain. Thereby, SPLs address the needs and requirements of various users as well as provide the means for products that address specific problems or requirements from a user. Clements and Northrop define SPLs as follows “A software product line is a set of software-intensive systems, shar- ing a common, managed set of features that satisfy the specific needs of a particular market segment or mission and that are developed from a common set of core assets in a prescribed way.” [CN01]. This quotation provides the most basic information about SPLs: • SPL shifts the focus from the development of single software products to a family of similar software products. • Features are software related entities that in their individual combination define the final software product. • SPLs are created for a specific domain, based on expert knowledge or related functionality. Thus, SPLs are able to support developers to efficiently derive customized soft- ware products from a common repository instead of developing every product from the scratch. This section introduces the fundamental concepts of SPL engineering. There- after, feature models are introduced and how they are used to specify the variable characteristics of an SPL. Finally, dynamic software product lines are introduced as an conceptual extension of SPLs, to shift the process of a product configuration from design time to runtime. 2.2.1 Fundamentals of SPL Engineering The SPL engineering process consists of two main activities: (i) domain engineer- ing and (ii) application engineering [CN01, vSR07, PBv05, WL99]. I n t r o d u c t i o n & F u n d a m e n t a l s 2.2 software product line engineering 29 • Domain Engineering. This process is responsible for creating a repository of reusable software assets, i.e., software features, and identifying common- alities and variability of an SPL. The domain engineering process, depicted in the upper part of Figure 2.5, consists of five activities: product manage- ment, domain requirement engineering, domain design, domain