Supporting the Statistical Analysis of Variability Models by Processing Binary Decision Diagrams

Abstract

Abstract When one of the main aims of the Software Engineering is saving costs and time, the software product lines play an essential role. In this eld, the key lies in identifying reusable components or features that can be applied in future projects. Much research is being done to provide customizable solutions that match speci c problems and thus satisfy a variety of non-functional requirements, such as runtime eciency, computer memory consumption, security level, etc. Customization is often accomplished through a con guration process where the desired features are selected. The space of possible con gurations is usually constrained to avoid features incompatibilities, and guaranteeing that feature inter-dependencies are satis ed. There are many questions of interest inside this restricted space: Are all con gurations free of errors? Is there any dead code that cannot be activated because of the inter-feature constraints? What is the component reusability range? What is the typical size of a nal product in terms of components? Etc. The con guration space may potentially be 2n for n features. Hence, processing the complete set of solutions is impossible except for the most trivial cases. After removing the invalid con gurations that do not satisfy the inter-feature constraints, the solution space is reduced substantially. Nevertheless, it is usually still large enough to be suitable to work with it. One strategy to address these diculties is selecting a representative sample of the space and, once the computation is done, extrapolating the conclusions to the whole problem. At this point, the problem turns into the way of obtaining a reliable random sample to avoid wrong interpretations. This thesis presents a set of algorithms that support both (i) working with the whole population of valid con gurations by using a highly-optimized Boolean structure known as Binary Decision Diagrams, and (ii) generating random samples from the con guration space. Moreover, a whole infrastructure in two programming languages (C++ and R) is provided to incorporate new algorithms on Binary Decision Diagrams e ortlessly. Finally, this thesis reports the empirical validation of our algorithms and framework on a benchmark composed of real variability models, whose number of features ranges from 45 to 17 365. Keywords: Software product lines, Feature models, Binary decision diagrams, Boolean functions.